Как вариант - продублировать таблицу вверх ногами
Что-то типа если X стремится к 0 больше чем к 70000, то выборку делать из первой таблицы, иначе из второй сверху
Память не экономим и больше напряга при записи, но зато сэкономишь эти 4 секунды
 
Еще вариант - разбиваешь таблицу на несколько таблиц, от 1 до 10000 в одну, от 10001 до 20000 в другую, потом в третью и тд
 
Глупости наверное, но может добавить скорости

Ivan, оба твои варианта хуета какая-то.
Вообще достаточно было бы узнать некий идентификатор (если сортировка по дате, то и идентификатором будет "дата+реальный ID записи")  последней выбранной записи (то есть последней записи на актуальной странице) и после этого отправлять этот идентификатор гет-запросом ко второй странице, которая, по сути, делает выборку с четким лимитом 30 записей от указанного нами идентификатора.
 
Проблема будет в том, что по сути для добавлении в базу очередной записи все "постраничные" ссылки будут изменять адреса, то есть Гугль будет теряться. А вот пользователю по большей мере похуй. И даже отчасти хорошо - его ссылка всегда будет вести именно на тот список записей, который он видел и неделю назад. А в случае с большинством примеров из стандартной пагинации список записей на конкретном номере страницы со временем постоянно меняется.

Ivan

Как вариант - продублировать таблицу вверх ногами

Сортировку может просто в другую сторону делать?

Хотя вариант Алекса я б хотел увидеть в виде кода.
А вариант Статуса тоже не помешает, хотя, из того что я понял, получается какой-то бред.

нубяры xDDDD

Givi

Хотя вариант Алекса я б хотел увидеть в виде кода.

Да вы что ебнулись все, такую баянистую тему найти не можете
http://habrahabr.ru/blogs/mysql/44608/

не понял, покажи как это в коде

Да принцип тот же что и в статье привязка к идешнику

раскопал из старого, но это тоже самое что и говорит AlexB:

вообще вместо limit n,m нужно:
1. отказаться от выбора страницы № пять тысяч шестьсот восемьдесят три, а оставить только первая - предыдущая - следующая - последняя
2. делать индексы по критериям отбора и id и отбирать вместо limit n, m -> where ... and ld > lim order by ..., id limit n

если список юзеров на не надо фильтровать по другим критериям можно прямо каждому проставить на какой они странице, пиздануть индекс и дело в шляпе...

но обычно нужно фильтровать - это раз. И новые записи ж все время добавляются - это два

Абырвалг, ну табличку сделать целую с сортировкой по страницам и т.п. или вообще сторед проц возможно можно написать..

как бы да, но у нас например для разных людей разный контент - накладываются ограничения то территории проживания и видам спорта, которые интересны

Абырвалг, ну еще никто не запрещал, ну например демонам инициировать запрос для кеширования данных, тогда вообще все будет быстренько работать даже с первым запросом. Ну это я наперед забежал если че)))

партишены в помощь

ну например демонам инициировать запрос для кеширования данных

И при изменении данных каждый раз чистить кеш?