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