Походу, это единственное, что сработало.

Очень интересно узнать, скольно в тестовой базе
постов, тегов и связей. И время по запросам здесь приведённым.

В sakila всего 1000 записей в films, все запросы
слишком быстро отрабатывают что бы разница была видна достоверно.

mysql> select count(*) from wp_posts;
+----------+
| count(*) |
+----------+
| 72645 |
+----------+
1 row in set (0.06 sec)

mysql> select count(*) from wp_term_relationships;
+----------+
| count(*) |
+----------+
| 186297 |
+----------+
1 row in set (0.04 sec)

mysql> select count(*) from wp_term_taxonomy;
+----------+
| count(*) |
+----------+
| 17442 |
+----------+
1 row in set (0.00 sec)

Зачем 17442 тегов/категорий, я не знаю, редакторы что-то намудили, в реальности при выборках используется штук может 50, одновременно в запросе - штук 10.

> И время по запросам здесь приведённым.

Для исходного, тривиального, около двух секунд.
Для варианта коллеги metaclass@lj - 0.05 секунды для LIMIT 3000,100
Вариант коллеги kvasimodo@lj пришлось прервать, не дождался конца, как и мой вариант с SELECT ... WHERE ID IN(SELECT ...)
Остальные варианты не смотрел.

>Для варианта коллеги [info]metaclass - 0.05 секунды для LIMIT 3000,100
mysql> select count(*) from wp_posts;
+----------+
| count(*) |
+----------+
| 72645 |
+----------+
1 row in set (0.06 sec)

Что то я не понимаю, как запрос с full-scan для таблицы posts может
отработать быстрее чем count(*)?

Покажите пожалуйста план.

P.S. У mysql есть фишка, он хорошо кеширует результаты запросов,
то что первый раз он мог считать за 10 секунд, если запрос выполнить
повторно не меняя базу - результат выпадет в миллисекунды.

> Что то я не понимаю, как запрос с full-scan для таблицы posts может
отработать быстрее чем count(*)?

Почему с full scan? Там выборка по индексу.
Вот он план.
С увеличением номера страницы будет расти и время.
Для LIMIT 28300, 100 будет около 0.5 секунды.

> P.S. У mysql есть фишка, он хорошо кеширует результаты запросов,
то что первый раз он мог считать за 10 секунд, если запрос выполнить
повторно не меняя базу - результат выпадет в миллисекунды.

Ненене, меня этим не провести, я жду минуты по три между запросами, само собой.

Хмм, наверное mysql достаточно умный что бы проверять записи в том
порядке в котором он их выдаёт и остановиться когда хватит.

Интересно, а сколько времени займёт поиск по редкому тегу, для которого
меньше 100 записей в базе?

P.S. >Ненене, меня этим не провести, я жду минуты по три между запросами, само собой.
Можно просто запрос немного исправить, "--" где нибудь добавить или пробелов,
тогда он будет выполнен как новый.

> Хмм, наверное mysql достаточно умный что бы проверять записи в том
порядке в котором он их выдаёт и остановиться когда хватит.

Конечно, он же группирует их по индексу.
Как только он наберет резалтсет, он остановится.

> Интересно, а сколько времени займёт поиск по редкому тегу, для которого
меньше 100 записей в базе?

Полный просмотр всего множества, ограниченного первыми двумя условиями.
Там где-то половина всей таблицы и выходит.
То есть, лучше, в данном случае, когда теги часто встречаются - быстрее сотня наберется.