What strategy does MySQL optimizer use when choosing between two indexes?

Question

In question:

Optimize a query with two range conditions

the OP wanted to know if there were a way to optimize his query. In an answer given the query were rewritten as a LEFT JOIN, and that was the same thought that I had as well. However, that did not help, the execution plan remained the same.

table   type    possible_keys                 key
book    ref     author_id,publish_date,i0,i1  author_id

So I removed the index author_id and created a new index like:

  KEY `i2` (`author_id`, `country`, `org`, `publish_date`, `price`)

I was a bit surprised to see the new plan:

table   type    possible_keys                 key
book    ref     publish_date,i0,i1,i2         i0

why did it not choose i2 over i0 when it did choose author_id before? I got even more puzzled when I switched places in the table for i0 and i2:

PRIMARY KEY (`id`),
KEY `publish_date` (`publish_date`),
KEY `i2` (`author_id`, `country`, `org`, `publish_date`, `price`),
KEY `i0` (`country`, `org`, `author_id`, `price`, `publish_date`),
KEY `i1` (`country`, `org`, `author_id`, `publish_date`, `price`) 

Now all the sudden index i2 were chosen:

table   type    possible_keys                 key
book    ref     publish_date,i2,i0,i1         i2

Do I miss something or does the optimizer pick the first declared index that it benefits from even though there are better indexes declared later on?

With the following indexes and a query where predicates involve author_id, country, org, publish_date, price:

KEY `author_id` (`author_id`),
KEY `i2` (`author_id`, `country`, `org`, `publish_date`, `price`)

I would expect the optimizer to choose i2 over author_id, but if I get it right it depends on the order they are defined.

Are these observations true in general or does it only happen for small tables?

Answer 1

Index selection is based on the estimated number of rows that will be accessed when using the different indexes. The order the indexes is declared in should only make a difference if the estimated cost is the same for both indexes. In your case, the three columns org, country, and author_id can be used for index lookup. Any index that start with these three columns may be used and will have equal cost.

The most likely reason for your observations is that the InnoDB index statistics have not been updated after the bulk insert. If I do ANALYZE TABLE on the two tables, the optimizer selects i0 index instead of author_id.

If you want to understand more about why a particular query plan is chosen, I recommend to look at the optimizer trace for the query.

Answer 2

Without the SELECT to look at, all I can do is hand-waving.

• INDEX(a,b) is bulkier than INDEX(a); a possible rational for using the latter is that it might entail fewer index blocks. In general, you should not have both; only have the larger index.
• 5 columns in a composite index is about the limit for 'practicality'.
• The Optimizer has changed multiple times recently -- the "Cost model" is improving constantly. But it does not yet take into consideration SSD vs HDD, nor what is cached already.
• There are cases where the Optimizer validly ignores LEFT; don't count on that to force a different query plan. Meanwhile, please do not use LEFT unless you really expect missing rows in the 'righthand' table; it confuses the reader.
• I don't think 'cardinality' of individual columns is used for picking an index.
• =, IS NULL, !=, IN, LIKE and various "range" predicates are handled differently. = is the easiest to optimize; in some cases IN and LIKE turn into =.
• AND is easy to optimize; OR is not.
• Don't hide an indexed column inside a function; it can't use the index. (Eg, DATE(col) = ...)
• An index will be shunned if more than about 20% of the rows would be touched -- a table scan is likely to be faster.
• The Optimizer does not have good statistics on composite keys; this probably leads to some of what you are seeing.
• I doubt if the definition order of indexes matters. Do you have a simple test case that demonstrates such?

See my Cookbook for creating an optimal index, given a SELECT.