LD>>Этот запрос сколько в среднем строк обрабатывает (возвращает или аггрегирует)?
MC>В среднем — сотни. В худшем случае — тысячи.

тогда индекс вполне можно добавить. у Вас получается 120 строк на одну страницу innodb, а селективность около 1/1000. Те даже в худшем случае равномерного случайного распределения будет в 10 раз быстрее фулскана.


LD>>Сколько колонок учавствует в формировании результата? Все?
MC>Допустим до 5 колонок.

LD>>Если много, то как они кластеризованы относительно первичного ключа? случайно или есть корреляция?
MC>В MySql нет кластерных индексов.

Это в postgres, если я правильно понимаю нет. В innodb первичный ключ — кластерный.

LD>>Какая средняя длина одной строки?
MC>136