Improvements for many-table joins in MySQL 5.6

A lot has happened in MySQL 5.6 for queries joining many tables. For the most common use cases we have drastically reduced the cost of finding the execution plan. We have also improved the heuristics and removed bugs so that the final plan is often better than it used to be. Read on if you are one of those people who do 15 way joins!

Finding a query execution plan
First some background. You can skip this part if you know how MySQL picks the table join order in 5.5.

When presented with a query, MySQL will try to find the best order to join tables by employing a greedy search algorithm. The outcome is what we call a query execution plan, QEP. When you join just a few tables, there's no problem calculating the cost of all join order combinations and then pick the best plan. However, since there are (#tables)! possible combinations, the cost of calculating them all soon becomes too high: for five tables, e.g., there are 120 combinations which is no problem to compute. For 10 tables there are 3.6 million combinations and for 15 tables there are 1307 billion. You get the picture. For this reason, MySQL makes a trade off: use heuristics to only explore promising plans. This is supposed to significantly reduce the number of plans MySQL needs to calculate, but at the same time you risk not finding the best one.


There are two variables you can use to tune how many plans MySQL should explore before settling for the best plan it has found so far: optimizer_prune_level and optimizer_search_depth. I'm not going to describe those here as you can read all about them in the manual, numerous blogs and the discussion forum.

What has changed
With that introduction, let's take a look at the improvements in 5.6. Below you can see the response time in 5.5 and 5.6 for a query a customer reported to have problems with. The query is a join of 24 tables where two tables need to be scanned, two tables can be ref-accessed and 20 tables can can be eq-ref accessed.

As you can imagine, finding a good QEP dominates the response time for optimizer_search_depth=6 and higher in 5.5. Even though it's easy to get excited by a graph like this, it hides important details due to the huge differences between MySQL versions. Take a look at the raw numbers:

optimizer search depth	Time finding QEP			Calculated partial plans
	5.5	5.6	Relative	5.5	5.6	Relative
1	0.001	0.001	1.000	300	300	1.000
2	0.003	0.003	1.000	1892	1850	0.977
4	0.064	0.018	0.281	149011	10599	0.071
6	1.46	0.025	0.017	3348408	16652	0.005
8	19.1	0.300	0.016	38064246	21012	0.001
10	166.5	0.035	0.000	293826342	25651	0.000
12	> 999.999	0.040	0.000	1819396800	31302	0.000
24		0.083	0.000		60497	0.000

"Time finding QEP" is the "statistics" phase of SHOW PROFILE. "Partial plans" is the output of status variable Last_query_partial_plans which was added in 5.6. It outputs how many times greedy search has calculated a partial QEP. I back-ported this variable into my local copy of 5.5 to be able to compare the two server versions in the experiments.

As you can see, the number of explored plans in MySQL 5.5 increases by an order of magnitude every time optimizer_search_depth is increased by two. Furthermore, using a higher optimizer_search_depth value than 12 is going to take forever so I didn't bother. The case for MySQL 5.6 is significantly better and is the main reason for the much lower response time in the graph above: Already at optimizer_search_depth=4 the difference between the two versions is significant.

The code changes that made this possible are:

1. Before greedy search starts searching for a good plan, the tables are pre-ordered to something that has a high chance of resembling the final plan. This ordering before greedy search has been changed: in 5.5, it orders the table in increasing number or rows. The idea is that it's good to start with the smallest table so that as few rows as possible need to be joined with the next table. In 5.6 key dependency is also taken into account: let's say table 'a' has fewer rows that table 'b', but table 'a' can be accessed through index lookup if table 'b' is read first. In 5.5 that would give an initial ordering of a,b. In 5.6 that gives an initial ordering of b,a.
    
2. In 5.5 there was a bug that intermingled the presorted tables. After greedy search had iterated three or four levels down, the initial table order was not recognizable. No matter how good the pre-ordering is, it does not help if the order is messed up! That bug was obviously fixed.
    
3. When a table that can be accessed through eq_ref index lookup is added to a partial plan, at most one row in that table can match each row generated by the partial plan. It is not useful to compare two plans that differ only in the order of eq_ref tables. As a matter of fact, whenever it is possible to add an eq_ref table to a partial plan there's no need to calculate any other alternative plans at this stage at all since nothing can be cheaper than adding an eq_ref table. In 5.6, MySQL treats a sequence of eq_ref tables as an entity. Once it is possible to add an eq_ref table to the plan, MySQL will check if there are more eq_ref tables and immediately add these.

Together, these three changes make up an abundance of difference for many-table joins. Notice that 1) and 3)  only affect QEPs with eq-ref tables, but on the other hand it's not sane to join 10 or 20 tables without proper indexes anyway. That's why I claimed that "we have drastically reduced the cost of finding the execution plan for the most common use cases".

There is one last MySQL 5.6 greedy search improvement left to describe: In 5.5 there was a bug that made greedy search fail to consider the CPU cost of processing the rows of a partial plan when doing the calculations. Combined with the bug that intermingled the presorted tables (see 2 above), the result was that for many queries the plan did not improve by increasing the optimizer_search_depth. Let's take another look at the details for the query discussed above, but this time let's focus on the execution part:

optimizer search depth	Handler_read% calls
	5.5	5.6	Relative
1	1267	83	0.066
2	2916	75	0.026
4	3815	75	0.020
6	3815	75	0.020
8	3815	75	0.020

One would expect the plan to converge towards the optimal plan as more and more time was spent on optimizing. That's not the case for MySQL 5.5 for this query! The plan actually gets worse up to optimizer_search_depth=4 and then remains constant. All that time we spent optimizing was wasted. For MySQL 5.6 the plan found at optimizer_search_depth=2 is most likely the optimal plan or at least very close to it so improvements are not possible (but there's no way to be sure since it's not feasible to optimize the query with pruning disabled). This bug is fixed in 5.6. Obviously :-)

On test case used above
I'm afraid I can't provide the database dump or 24-table query the customer reported to have a problem with, but if you want to check out the improvements I suggest you copy greedy_optimizer.test (and some friends in the include directory) from 5.6 and try to run it in 5.5. The tests that are new in the 5.6 version of greedy_optimizer.test mimic the problem reported in the bug. On my desktop it takes about 14 seconds in MySQL 5.6 but timed out after 900 seconds in MySQL 5.5. I didn't care to rerun the test without timeout since 900 seconds is more than enough to prove my point. But you can try if you want to :-)

Credits
Apart from the changes to sorting before greedy search (which I did), the described changes were identified and fixed by Ole John Aske.