How MySQL uses indexes

All indexes (PRIMARY, UNIQUE and INDEX()) are stored in B-trees. Strings are automatically prefix- and end-space compressed.

Indexes are used to:

• Quickly find the rows that match a WHERE clause.
• Retrieve rows from other tables when performing joins.
• Find the MAX() or MIN() value for a specific key.
• Sort or group a table if the sorting or grouping is done on a leftmost prefix of a usable key (e.g., ORDER BY key_part_1,key_part_2 ). The key is read in reverse order if all key parts are followed by DESC.
• Retrieve values without consulting the data file, in some cases. If all used columns for some table are numeric and form a leftmost prefix for some key, the values may be retrieved from the index tree for greater speed.

Suppose you issue the following SELECT statement:

mysql> SELECT * FROM tbl_name WHERE col1=val1 AND col2=val2;

If a multiple-column index exists on col1 and col2, the appropriate rows can be fetched directly. If separate single-column indexes exist on col1 and col2, the optimizer tries to find the most restrictive index by deciding which index will find fewer rows and using that index to fetch the rows.

If the table has a multiple-column index, any leftmost prefix of the index can be used by the optimizer to find rows. For example, if you have a three-column index on (col1,col2,col3), you have indexed search capabilities on (col1), (col1,col2) and (col1,col2,col3).

MySQL can't use a partial index if the columns don't form a leftmost prefix of the index. Suppose you have the SELECT statements shown below:

mysql> SELECT * FROM tbl_name WHERE col1=val1;
mysql> SELECT * FROM tbl_name WHERE col2=val2;
mysql> SELECT * FROM tbl_name WHERE col2=val2 AND col3=val3;

If an index exists on (col1,col2,col3), only the first query shown above uses the index. The second and third queries do involve indexed columns, but (col2) and (col2,col3) are not leftmost prefixes of (col1,col2,col3).

MySQL also uses indexes for LIKE comparisons if the argument to LIKE is a constant string that doesn't start with a wildcard character. For example, the following SELECT statements use indexes:

mysql> select * from tbl_name where key_col LIKE "Patrick%";
mysql> select * from tbl_name where key_col LIKE "Pat%_ck%";

In the first statement, only rows with "Patrick" <= key_col < "Patricl" are considered. In the second statement, only rows with "Pat" <= key_col < "Pau" are considered.

The following SELECT statements will not use indexes:

mysql> select * from tbl_name where key_col LIKE "%Patrick%";
mysql> select * from tbl_name where key_col LIKE other_col;

In the first statement, the LIKE value begins with a wildcard character. In the second statement, the LIKE value is not a constant.

Searching using column_name IS NULL will use indexes if column_name is a index.

MySQL normally uses the index that finds least number of rows. An index is used for columns that you compare with the following operators: =, >, >=, <, <=, BETWEEN and a LIKE with a non-wildcard prefix like 'something%'.

Any index that doesn't span all AND levels in the WHERE clause is not used to optimize the query.

The following WHERE clauses use indexes:

... WHERE index_part1=1 AND index_part2=2
... WHERE index=1 OR A=10 AND index=2      /* index = 1 OR index = 2 */
... WHERE index_part1='hello' AND index_part_3=5
          /* optimized like "index_part1='hello'" */

These WHERE clauses do NOT use indexes:

... WHERE index_part2=1 AND index_part3=2  /* index_part_1 is not used */
... WHERE index=1 OR A=10                  /* No index */
... WHERE index_part1=1 OR index_part2=10  /* No index spans all rows */