インデックス作成の指針

・フィールドが格納している値の種類が少ない(カーディナリティが低い)場合、そのフィールドにインデックスを作成してもあまり効果はない。
マルチカラムインデックスに関する注意
・インデックスの要素となる列を含む条件式は、「AND」で結合しなければならない。
・一番目に定義された列を含む条件式を設定しなければならない。

INDEX(a,b,c)

という、マルチカラムインデックスを定義した場合、
マルチカラムインデックスが有効なWHERE句の例は以下。

WHERE a=1 AND b=2 AND c=3
WHERE a=1 AND b=2
WHERE a=1
WHERE a=1 OR a=2
WHERE (a=1 OR a=2) AND b=2
WHERE a=1 AND c=3

となる。つまり、aを条件に入れるのは必須。
また、例からもわかるように、マルチカラムインデックスでaに対するインデックスを振っているので
単独でaに対するインデックスを振る必要はない。
無駄なインデックスを振ってしまう、よくあるパターンなので注意すること。
マルチカラムインデックスが無効なWHERE句の例は以下

WHERE a=1 OR b=2
WHERE a=1 OR b=2 AND c=3
WHERE b=2 AND c=3

よーするにORの高速化は無理ってこと。
詳細はMySQL全機能リファレンスのp269～270を参照のこと。