Но если делать сортировку через ORDER BY ..., то получится что я отсортирую только строки, попадающие под условия лимита, а провести ее надо для всей таблицы и только после этого выводить постранично.
Вы понимаете не правильно.
Сначала происходит order by всех строк в результирующей выборке.
Потом через limit определяется сколько и каких строк Вы получите от sql сервера.
Запрос
select id from table
order by id desc
limit 10
вернет 10 самых больших 10 id из всей таблицы
Ну и мануал почитайте, там все описано в каком порядке применяется
dev.mysql.com/doc/refman/5.7/en/select.html