A while ago, I explained how range access in a multiple-part index works and why MySQL can't utilize key parts beyond the first occurrence of some often used comparison operators. Luckily, there is a great improvement underway in MySQL 5.6 that will remedy much of this limitation. Meet Index Condition Pushdown.
How does ICP work?
Index Condition Pushdown is a new way for MySQL to evaluate conditions. Instead of evaluating conditions on rows read from a table, ICP makes it possible to evaluate conditions in the index and thereby avoid looking at the table if the condition is false.
Let's assume that we have a multiple-part index covering columns (keypart_1, ..., keypart_n). Further assume that we have a condition with a comparison operator on keypart_1 that does not allow keypart_2,...,keypart_n to be used as a range condition (more on that here).
When MySQL does range access without ICP enabled, the index is traversed to locate rows in the table that are within the range(s) relevant for the conditions on keypart_1. The rows in these ranges are read from the table and returned from the storage engine to the MySQL server. The server then evaluates the remaining conditions, including those that apply to keypart_2,..,keypart_n.