A paginação é difícil; o modelo RDBMS não é adequado para um grande número de consultas de curta duração com rolagem com estado. Como você observou, o uso de recursos tende a ser muito alto.

Você tem as opções:

• LIMIT e OFFSET
• Usando um cursor
• Copiar os resultados para uma tabela temporária ou para o memcached ou similar e depois lê-los a partir daí
• x > id e LIMIT

Destes, prefiro x > id com um LIMIT . Basta lembrar o último ID que você viu e pedir o próximo. Se você tiver uma sequência monotonamente crescente, isso será simples, confiável e, para consultas simples, será eficiente.