innodb?
Этот запрос сколько в среднем строк обрабатывает (возвращает или аггрегирует)?
Сколько колонок учавствует в формировании результата? Все?
Если много, то как они кластеризованы относительно первичного ключа? случайно или есть корреляция?
Какая средняя длина одной строки?