Indexes and queries

from the Artful MySQL Tips List

The main use of indexes is to speed up queries. Most MySQL indexes are BTrees. They're efficient for single lookups and range scans.

The two main MySQL storage engines, InnoDB and MyISAM, use BTrees differently. InnoDB clusters row data with its primary key (PK) or unique key, so a PK lookup finds row data right there in the index. A "secondary" or covering index contains the covering index's column values and the PK, which it uses to find matching row data. Each MyISAM index, though, is simply a separate BTree with pointers into the data file. These differences matter: if a query filters a table on city and joins it on id, InnoDB can use a city index to efficiently find id values for the join.

Per query clause, to avoid a full table scan, the optimiser looks for an index whose selectivity is adequate (boolean values have least), and whose columns the WHERE clause tests directly against constant values for equality, inequality or a range (BETWEEN...AND..., LIKE '...%'), and/or are directly GROUPed, and/or are directly ORDERed. In that order, unless the ORDER BY clause can speed up the WHERE lookup. "Directly" means without an intervening expression or function call, and in the case of ORDER BY, no DESC argument.

Index column order is important. Given index(lnam,fnam), ...lnam="Smith" And fnam Like 'J%'... will be much faster than ...lnam Like 'S%' And fnam='John'..., and the index will not help at all with ...lnam Like '%th'.... Numeric index(j,i) finds ...i>M And j=N faster than index(i,j). When a table is INNER JOINed (or the righthand table in a LEFT JOIN, or the lefthand table in a RIGHT JOIN), it is helpful if the the JOIN column is included in the above.

If the query has a LIMIT clause and the optimiser can apply an index to the ORDER BY clause, the query engine will stop processing rows when the LIMIT is satisfied.

It's often thought that indexes on small tables are unimportant, but if a table is accessed repeatedly, for example in a function call on a big table, seemingly insignificant seek times can add up to cumulative times of minutes or hours.

Useful articles on indexes & queries ...

Return to the Artful MySQL Tips page