Query Performance Optimization - High Performance MySQL - page 226

you can use STRAIGHT_JOIN and write the query in the order you think is best—but
such times are rare. In most cases, the join optimizer will outperform a human.
The join optimizer tries to produce a query execution plan tree with the lowest ach-
ievable cost. When possible, it examines all potential combinations of subtrees, begin-
ning with all one-table plans.
Unfortunately, a join over n tables will have n -factorial combinations of join orders to
examine. This is called the search space of all possible query plans, and it grows very
quickly—a 10-table join can be executed up to 3,628,800 different ways! When the
search space grows too large, it can take far too long to optimize the query, so the server
stops doing a full analysis. Instead, it resorts to shortcuts such as “greedy” searches
when the number of tables exceeds the limit specified by the optimizer_search_depth
variable (which you can change if necessary).
MySQL has many heuristics, accumulated through years of research and experimen-
tation, that it uses to speed up the optimization stage. This can be beneficial, but it can
also mean that MySQL might (on rare occasions) miss an optimal plan and choose a
less optimal one because it's trying not to examine every possible query plan.
Sometimes queries can't be reordered, and the join optimizer can use this fact to reduce
the search space by eliminating choices. A LEFT JOIN is a good example, as are correlated
subqueries (more about subqueries later). This is because the results for one table de-
pend on data retrieved from another table. These dependencies help the join optimizer
reduce the search space by eliminating choices.
Sort optimizations
Sorting results can be a costly operation, so you can often improve performance by
avoiding sorts or by performing them on fewer rows.
We showed you how to use indexes for sorting in Chapter 3 . When MySQL can't use
an index to produce a sorted result, it must sort the rows itself. It can do this in memory
or on disk, but it always calls this process a filesort , even if it doesn't actually use a file.
If the values to be sorted will fit into the sort buffer, MySQL can perform the sort entirely
in memory with a quicksort . If MySQL can't do the sort in memory, it performs it on
disk by sorting the values in chunks. It uses a quicksort to sort each chunk and then
merges the sorted chunks into the results.
There are two filesort algorithms:
Two passes (old)
Reads row pointers and ORDER BY columns, sorts them, and then scans the sorted
list and rereads the rows for output.
The two-pass algorithm can be quite expensive, because it reads the rows from the
table twice, and the second read causes a lot of random I/O. This is especially
expensive for MyISAM, which uses a system call to fetch each row (because