Для оптимизации скорости работы SQL-запросов в MySQL лучше:

• Создавать комбинированный индекс по колонкам, которые вы выбираете при помощи AND. Не забывайте при этом про «левую сторону». Выборка по (col2) или (col2, col3) не будет использовать комбинированный индекс (col1, col2, col3), т.к. он начинается с col1.
• Создавать одиночные индексы на каждую колонку, выбираемую через OR (в этом случае будет задействован поиск по пересечению индексов, что медленней комбинированного индекса, который тут использоваться не может, но быстрее, чем без индексов вообще)
• Если с помощью индексов не удается отсеить порядка 80% записей, то MySQL считает лучшим полное сканирование таблицы.
• При JOIN очень важная последовательность выборки. Если вы джоините таблицу со значительно меньшим кол-вом записей, то (хотя, вероятно,это поймет и сам планировщик MySQL) логичней было бы выбрать записи в ней, а уже потом по выбранным записям подключить основную, более огромную таблицу. Если иначе, то сначала выбирается огромное кол-во данных из большой таблицы, а уже потом к ним подключается маленькая выборка по второй.
• Всегда стоит использовать наиболее уникальные индексы (характеризумые мощностью данных, т.е. их уникальностью). Командой SHOW KEYS FROM table можно увидеть индексы, уникальность характеризуется колонкой Cardinality.
• Почти всегда используется B-tree индекс, который очень хорош тогда, когда мощность данных большая. Можно также использовать пространственный индекс R-tree (для определенного типа данных) и хэш-индекс для таблиц типа Memory (хэш индекс хорош, когда используется точное сравнение и несколько хуже, когда используется больше меньше, потому что данные хранятся в виде значения хэш-функции и в этом же виде сравниваются).
• B-tree индекс не будет использоваться в операторе LIKE, если его значение начинается со спецсимвола % или содержит другое поле.