Многостолбцовый индекс будет наиболее эффективным в ситуациях, когда все критерии являются частью многостолбцового индекса, даже в большей степени, чем наличие нескольких отдельных индексов.
Кроме того, имейте в виду, что если у вас есть многостолбцовый индекс, но вы не используете первый столбец, индексированный многостолбцовым индексом (или иначе не начинаете с начала и оставайтесь рядом с ранее использованным индексы), многостолбцовый индекс не принесет никакой пользы. (Например, если у меня есть индекс по столбцам [B, C, D], но есть WHERE, который использует только [C, D], этот многостолбцовый индекс не принесет пользы.)
Ссылка: http://dev.mysql.com/doc/refman/5.0/en/multiple-column-indexes.html:
MySQL может использовать многостолбцовые индексы для запросов, которые проверяют все
столбцы в индексе или запросы, которые проверяют только первый столбец,
первые два столбца, первые три столбца и т. д. Если вы укажете
столбцы в правильном порядке в определении индекса, один
составной индекс может ускорить несколько видов запросов на одном
таблица.