Есть смысл сделать дополнительное поле - sequence, которое будет всегда содержать последовательные числа, ==>
 
ID     sequence
1      1
3      2
5      3
10    4
 
Теперь чтобы достать данные для любой страницы задаем интервал для sequence, а не лимит, и обычный индекс тут будет рулить А при изменении таблицы пересчет sequence выполняется одним запросом очень быстро

arvitaly, ага, просто пиздато будет делаться перезапись:
1. Миллиона строк
2. Перезапись индекса.
И особенно круто это будет если изменения происходят не один раз в день.

Если нет номеров страниц, можно фильтровать по последней выбранной записи так, что бы всегда выбирать первые n записей. Юзверь посмотрит десяток страниц и можно будет закэшить с определёнными параметрами сортировки и фильтрации выборку и потом показывать страницы ))