Похоже у нас очень плохо написан запрос пэдженеции для форумов. Когда страница очень глубокая это приводит к диким тормозам. Новый индекс это несколько улучшил. Но основная проблема осталась.

Надо править код. Там кто-то лютых вложенных запросов нахерачил. Запрос с:

WHERE
    t1.rn BETWEEN 40226 AND 40245

выполняется по 20 секунд и жрет процессор как не в себя.
Запрос редкостной глупости. Вместо того, чтобы сначала выбрать сроки и потом для них считать что-то, происходит скан всех записей до 40226 с массой вложенных запросов к другим таблицам.

Ну роботы поисковиков и т.п. убивают сайт долбя в этот запрос.