Como posso acelerar uma consulta MySQL com um grande deslocamento na cláusula LIMIT?

Talvez você possa criar uma tabela de indexação que forneça uma chave sequencial relacionada à chave em sua tabela de destino. Em seguida, você pode unir essa tabela de indexação à sua tabela de destino e usar uma cláusula where para obter as linhas desejadas com mais eficiência.

#create table to store sequences
CREATE TABLE seq (
   seq_no int not null auto_increment,
   id int not null,
   primary key(seq_no),
   unique(id)
);

#create the sequence
TRUNCATE seq;
INSERT INTO seq (id) SELECT id FROM mytable ORDER BY id;

#now get 1000 rows from offset 1000000
SELECT mytable.* 
FROM mytable 
INNER JOIN seq USING(id)
WHERE seq.seq_no BETWEEN 1000000 AND 1000999;