Ich habe bereits mehrfach mitbekommen, dass anscheinend kaum jemand weiß, dass man Indizes auch über mehrere Spalten anlegen kann.
Zuerst sollte erwähnt werden, dass MySQL im Normalfall pro Query nur EINEN pro Tabelle Index auf einmal nutzen kann (es gibt Ausnahmen, merged-index, aber nur unter bestimmten Umständen in bestimmten Queries).
Ein Beispiel für den Einsatz eines Index über mehrere Spalten, wäre z.B. das folgende: