É lento porque precisa localizar o
offset superior linhas e escaneie as próximas 100. Nenhuma quantidade de otimização mudará isso quando você estiver lidando com grandes deslocamentos. Isso ocorre porque sua consulta literalmente instruir o mecanismo de banco de dados para visitar muitas linhas usando
offset 3900000 -- são 3,9 milhões de linhas. Opções para acelerar um pouco isso não são muitas. RAM super-rápida, SSDs, etc. ajudarão. Mas você só ganhará por um fator constante ao fazê-lo, o que significa que está apenas chutando a lata pela estrada até atingir um deslocamento maior o suficiente.
Garantir que a tabela caiba na memória, com muito mais de sobra, também ajudará por um fator constante maior - exceto na primeira vez. Mas isso pode não ser possível com uma tabela ou índice grande o suficiente.
Garantir que você está fazendo varreduras somente de índice funcionará até certo ponto. (Veja a resposta de velis; tem muito mérito.) O problema aqui é que, para todos os propósitos práticos, você pode pensar em um índice como uma tabela armazenando um local de disco e os campos indexados. (É mais otimizado do que isso, mas é uma primeira aproximação razoável.) Com linhas suficientes, você ainda terá problemas com um deslocamento maior o suficiente.
Tentar armazenar e manter a posição precisa das linhas também é uma abordagem cara. (Isso é sugerido por, por exemplo, benjist.) Embora tecnicamente viável, sofre de limitações semelhantes às que resultam do uso de MPTT com uma estrutura de árvore:você ganhará significativamente em leituras, mas terminará com tempos de gravação excessivos quando um nó for inserido, atualizado ou removido de tal forma que grandes partes dos dados precisem ser atualizadas junto.
Como esperamos que seja mais claro, não há nenhuma bala mágica real quando você está lidando com deslocamentos tão grandes. Muitas vezes é melhor olhar para abordagens alternativas.
Se você estiver paginando com base no ID (ou em um campo de data ou em qualquer outro conjunto de campos indexáveis), um truque em potencial (usado pelo blogspot, por exemplo) seria fazer sua consulta iniciar em um ponto arbitrário no índice.
Colocado de outra forma, em vez de:
example.com?page_number=[huge]
Faça algo como:
example.com?page_following=[huge]
Dessa forma, você mantém um rastro de onde está em seu índice, e a consulta se torna muito rápida porque pode ir direto para o ponto de partida correto sem passar por um zilhão de linhas:
select * from foo where ID > [huge] order by ID limit 100
Naturalmente, você perde a capacidade de pular para, por exemplo, página 3000. Mas pense com sinceridade:quando foi a última vez que você pulou para um número de página enorme em um site em vez de ir direto para seus arquivos mensais ou usar sua caixa de pesquisa?
Se você está paginando, mas deseja manter o deslocamento da página de qualquer maneira, outra abordagem é proibir o uso de um número de página maior. Não é bobagem:é o que o Google está fazendo com os resultados da pesquisa. Ao executar uma consulta de pesquisa, o Google fornece um número estimado de resultados (você pode obter um número razoável usando
explain ) e, em seguida, permitirá que você navegue pelos principais milhares de resultados - nada mais. Entre outras coisas, eles fazem isso por motivos de desempenho - precisamente aquele que você está encontrando. 
