MySQL :: A new dimension to MySQL query optimizations

It’s not radical to claim that one of the most important tasks of any DBMS query optimizer is to find the best join order for the tables participating in a query. Is it, e.g., better to read country or city first in

SELECT * 
FROM country JOIN city ON country.id=city.countryid 
WHERE city.population > 1000000 AND 
      country.region="EMEA"

SELECT *

FROM country JOIN city ON country.id=city.countryid

WHERE city.population > 1000000 AND

country.region="EMEA"

employee or department first in

SELECT *
FROM employee JOIN department ON employee.dept_no=department.dept_no
WHERE employee.first_name="John" AND
      employee.hire_date BETWEEN "2012-01-01" AND "2012-06-01" AND
      department.location="Paris"

SELECT *

FROM employee JOIN department ON employee.dept_no=department.dept_no

WHERE employee.first_name="John" AND

employee.hire_date BETWEEN "2012-01-01" AND "2012-06-01" AND

department.location="Paris"

If the optimizer gets this wrong, the resulting response time may be disastrous (or hilarious, depending on your sense of humour).

Simply put (and ignoring some edge cases), the MySQL optimizer does the following to find the cheapest combination of access methods and join order for the second query above:

Calculate the lowest cost for join order employee-department (and repeat for the reverse join order):

Pick cheapest access method for employee: full scan vs index lookup on first_name vs range scan on hire_date.
Pick cheapest access method for department: full scan vs index lookup on dept_no vs index lookup on location. This cost has to be multiplied by the number of times it is performed, i.e. the number rows from employee that evaluate to true for all relevant conditions. We call this number “prefix rows”.

Unfortunately there is a big flaw in how the optimizer calculates the prefix rows number.

You see, prefix rows for department is considered by the optimizer to be the same as the number of rows read by the access method of employee. But this misses the fact that there may be multiple conditions on the same table. For example, if first_name=”John” is used for index lookup in the employee table and there are 100 Johns, prefix rows would be considered to be 100. But there are probably a whole lot of those Johns that were not hired between January and June in 2012. Those Johns will not be joined with rows in department. Yet the optimizer fails to recognize this and thus multiplies the cost of the access method for department by 100. This, in turn, causes the optimizer to favour sub-optimal join orders in a great deal of cases.

Introducing: Condition filtering

You have probably guessed it by now: Starting from 5.7, MySQL will calculate prefix rows by taking all query conditions into account and is therefore likely to find better plans. I’m afraid it takes too long to explain the gory details of it all in one post, so I’ll follow up with a technical explanation soon. For now, let’s just enjoy the benchmark results we get from DBT-3 SF1 and SF10 (CPU bound shown, but disk bound is similar).

The response time is relative to MySQL 5.6, so a value of 100 means “no change”. The rest of the DBT-3 queries have the same execution plans as before.

If you’re curious about how it works, you can try it out right now in the “April” MySQL 5.7 lab release!