Aqui está como eu lido com isso. Para a primeira página que eu busco, eu uso
SELECT id, col, col, col
FROM output
ORDER BY id DESC
LIMIT 10000
Então, no meu programa cliente (node.js) eu capturo o
id valor da última linha do conjunto de resultados. Quando eu preciso da próxima página, eu faço isso. SELECT id, col, col, col
FROM output
WHERE id < my_captured_id_value
ORDER BY id DESC
Isso explora o índice. E funciona corretamente mesmo se você tiver excluído algumas linhas da tabela.
A propósito, você provavelmente quer um índice descendente se sua primeira página de paginação tiver os maiores ids.
CREATE UNIQUE INDEX index_id ON output USING btree (ID DESC) . Dica profissional
SELECT * é prejudicial ao desempenho em bancos de dados grandes. Sempre liste as colunas que você realmente precisa. 
