Databases Reference
In-Depth Information
MyISAM relies on the operating system's cache to hold the data). On the other
hand, it stores a minimal amount of data during the sort, so if the rows to be sorted
are completely in memory, it can be cheaper to store less data and reread the rows
to generate the final result.
Single pass (new)
Reads all the columns needed for the query, sorts them by the
ORDER BY
columns,
and then scans the sorted list and outputs the specified columns.
This algorithm is available only in MySQL 4.1 and newer. It can be much more
efficient, especially on large I/O-bound datasets, because it avoids reading the rows
from the table twice and trades random I/O for more sequential I/O. However, it
has the potential to use a lot more space, because it holds all the desired columns
from each row, not just the columns needed to sort the rows. This means fewer
tuples will fit into the sort buffer, and the filesort will have to perform more sort
merge passes.
It's tricky to say which algorithm is more efficient, and there are best and worst
cases for each algorithm. MySQL uses the new algorithm if the total size of all the
columns needed for the query, plus the
ORDER BY
columns, is no more than
max_length_for_sort_data
bytes, so you can use this setting to influence which
algorithm is used. See
“Optimizing for Filesorts” on page 377
in
Chapter 8
for
more on this topic.
MySQL might use much more temporary storage space for a filesort than you'd expect,
because it allocates a fixed-size record for each tuple it will sort. These records are large
enough to hold the largest possible tuple, including the full length of each
VARCHAR
column. Also, if you're using UTF-8, MySQL allocates three bytes for each character.
As a result, we've seen cases where poorly optimized schemas caused the temporary
space used for sorting to be many times larger than the entire table's size on disk.
When sorting a join, MySQL might perform the filesort at two stages during the query
execution. If the
ORDER BY
clause refers only to columns from the first table in the join
order, MySQL can filesort this table and then proceed with the join. If this happens,
EXPLAIN
shows “Using filesort” in the
Extra
column. In all other circumstances—such
as a sort against a table that's not first in the join order, or when the
ORDER BY
clause
contains columns from more than one table—MySQL must store the query's results
into a temporary table and then filesort the temporary table after the join finishes. In
this case,
EXPLAIN
shows “Using temporary; Using filesort” in the
Extra
column. If
there's a
LIMIT
, it is applied after the filesort, so the temporary table and the filesort can
be very large.
MySQL 5.6 introduces significant changes to how sorts are performed when only a
subset of the rows will be needed, such as a
LIMIT
query. Instead of sorting the entire
result set and then returning a portion of it, MySQL 5.6 can sometimes discard un-
wanted rows before sorting them.
