Cenário resumido: uma tabela com mais de 16 milhões de registros [tamanho de 2 GB]. Quanto maior o deslocamento de LIMIT com SELECT, mais lenta a consulta se torna, ao usar ORDER BY * primary_key *

assim

SELECT * FROM large ORDER BY `id`  LIMIT 0, 30 

leva muito menos do que

SELECT * FROM large ORDER BY `id` LIMIT 10000, 30 

Isso só encomenda 30 registros e mesmo assim. Portanto, não é a sobrecarga da ORDER BY.
Agora, ao buscar as últimas 30 linhas, leva cerca de 180 segundos. Como posso otimizar essa consulta simples?