A customer of ours had an interesting problem regarding a query that was taking too long, around 55s. Looking at the query with the query profiler we found that it was spending most of its time in the "statistics" phase. Now the query was pretty complex, it contained nearly 20 tables with INNER JOINs, LEFT JOINs and even some subqueries. However the tables were small and fetching all the data shouldn't have taken the 55 seconds the query was taking. The problem was that the optimiser was spending too much time evaluating and finding the optimal execution plan.
There are two options in MySQL with which you can control the optimiser's behaviour a bit. The first one is optimizer_prune_level. The pruner discards non-optimal execution plans early without evaluating them fully. It is turned on by default and is not recommended to turn off unless there's a really good reason. For testing purposes we turned the pruner off for this query, but after evaluating the query for over half an hour we gave up on the test and decided to call it infinity. This is understandable, for a 20 table join there are 20! (~2.4 x 10^18) possible execution paths, so evaluating all of them would take forever (now this query contained LEFT JOINs and subqueries so that number is not exactly correct, but still used here to spread fear).
The second interesting option is the optimizer_search_depth. This defines how deep into the execution path the optimizer should look before deciding which plan to use. If this is set to a value higher than the number of tables in the query it means that all possible execution plans (except pruned ones) will be examined. If it's set lower than the number of tables in the query, the optimiser will not evaluate each path to its full extent but choose the first level based on all plans evaluated to the specified depth and then do a new evaluation for the next level and so on until the full execution plan has been chosen. Trying a few different values we got the following results:
SET SESSION optimizer_search_depth = 1;
-> statistics 0.000591
SET SESSION optimizer_search_depth = 5;
-> statistics 0.002321
SET SESSION optimizer_search_depth = 10;
-> statistics 0.365812
SET SESSION optimizer_search_depth = 15;
-> statistics 5.054150
SET SESSION optimizer_search_depth = 0;
-> statistics 0.026904
All of the above are much better than the 58.497217s we got with the default search depth of 62. Note that the value 0 (zero) is a special case where the optimiser chooses and sets the optimal search depth for each query, thus adding a bit of overhead to the optimisation process.
So why not just tune down the search depth to 1 for all queries? The problem here is that you can then miss optimal execution plans as the optimizer won't go deep enough down the execution plan before choosing which plan to use at each level. You might get an execution plan that is horribly wrong. So the best way to go if you have many queries with more than 15 tables is to choose an intermediate value of 7-8 or so, which will produce the optimal execution plan in 99% of all cases, but won't waste too much time finding it.
The best solution is of course to optimize all the 15+ table queries yourself but that's another story!