How MySQL does sorting with Order By

There are two filesort algorithms in MySQL for sorting and retriving select queries results.

1. Original Filesort Algorithm : This method uses only the ORDER BY columns. (prior to MySQL 4.1)
2. Modified Filesort Alforithm : This method uses ORDER BY columns and the columns which are used in query. (MySQL 4.1 and newer version)

(if TEXT or BLOB columns will be involved in SELECT than MySQL will always use Original Filesort Algorithm)

The Original Filesort will work like this:

1. First It will read all rows according to key or by table scanning and the rows which doesn’t match the WHERE clause will be skipped.
2. It will store a pair of values in a buffer (the sort key and the row pointer) for each row. The size of the buffer is the value of the sort_buffer_size system variable.
3. When the buffer gets full, it will run a quicksort on it and store the result in a temporary file. Than it will save a pointer to the sorted block. (If all pairs will fit into the sort buffer, than temporary file will not be created for storing result)
4. It will repeat the same steps for all rows and it will have sorted small blocks in several temporary files.
5. Finally it will merge all the sorted blocks (temporary files) to one temporary file.
6. On the last merge, only the pointer to the row (the last part of the sort key) is written to a result file.
7. Give the results by reading the rows in sorted order from the result file.

Here, MySQL will read rows twice in this algorithm. Once when it will use WHERE clause and another when it will sorting the values for preparing result. so for avoiding this, Modified Filesort Algorithm has been created. In this algorithm, it will not store only sort key value and row pointer but also the columns which are required in query. Modified Filesort Algorithm will work like this:

1. It will read all rows according to key or by table scanning and the rows which doesn’t match the WHERE clause will be skipped.
2. It will store sort key value, row pointer and columns which are required in query.
3. It will sort the records by sort key value.
4. It will fetch the rows from sorted order. Here, MySQL doesn’t need to read rows twice as the value of those columns which are required in query, are already stored with sort key value and pointer.

Leave a Reply

Your email address will not be published. Required fields are marked *