[NOTE] This description is also present in refman
MySQL has two
filesort algorithms for sorting
and retrieving results. The original method uses only the
ORDER BY columns. The modified method uses not
ORDER BY columns, but all the columns
used in the query.
The optimizer selects which
to use. Prior to MySQL 4.1, it uses the original algorithm. As of
MySQL 4.1, it normally uses the modified algorithm except when
TEXT columns are
involved, in which case it uses the original algorithm.
filesort algorithm works as
Read all rows according to key or by table scanning. Rows that
do not match the
WHERE clause are skipped.
For each row, store a pair of values in a buffer (the sort key
and the row pointer). The size of the buffer is the value of
sort_buffer_size system variable.
When the buffer gets full, run a qsort (quicksort) on it and store the result in a temporary file. Save a pointer to the sorted block. (If all pairs fit into the sort buffer, no temporary file is created.)
Repeat the preceding steps until all rows have been read.
Do a multi-merge of up to
regions to one block in another temporary file. Repeat until
all blocks from the first file are in the second file.
Repeat the following until there are fewer than
MERGEBUFF2 (15) blocks left.
On the last multi-merge, only the pointer to the row (the last part of the sort key) is written to a result file.
Read the rows in sorted order by using the row pointers in the
result file. To optimize this, we read in a big block of row
pointers, sort them, and use them to read the rows in sorted
order into a row buffer. The size of the buffer is the value
variable. The code for this step is in the
sql/records.cc source file.
One problem with this approach is that it reads rows twice: One
time when evaluating the
WHERE clause, and
again after sorting the pair values. And even if the rows were
accessed successively the first time (for example, if a table scan
is done), the second time they are accessed randomly. (The sort
keys are ordered, but the row positions are not.)
filesort algorithm incorporates an
optimization such that it records not only the sort key value and
row position, but also the columns required for the query. This
avoids reading the rows twice. The modified
filesort algorithm works like this:
Read the rows that match the
For each row, record a tuple of values consisting of the sort key value and row position, and also the columns required for the query.
Sort the tuples by sort key value
Retrieve the rows in sorted order, but read the required columns directly from the sorted tuples rather than by accessing the table a second time.
Using the modified
filesort algorithm, the
tuples are longer than the pairs used in the original method, and
fewer of them fit in the sort buffer (the size of which is given
sort_buffer_size). As a result, it is
possible for the extra I/O to make the modified approach slower,
not faster. To avoid a slowdown, the optimization is used only if
the total size of the extra columns in the sort tuple does not
exceed the value of the
max_length_for_sort_data system variable. (A
symptom of setting the value of this variable too high is that you
should see high disk activity and low CPU activity.)