How does mysql order by implemented internally?

Question

How does Mysql order by implemented internally? would ordering by multiple columns involve scanning the data set multiple times once for each column specified in the order by constraint?

Answer 1

Here's the description:

http://dev.mysql.com/doc/refman/5.0/en/order-by-optimization.html

Unless you have out-of-row columns (BLOB or TEXT) or your SELECT list is too large, this algorithm is used:

• Read the rows that match the WHERE clause.

• 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.

Ordering by multiple columns does not require scanning the dataset twice, since all data required for sorting can be fetched in a single read.

Note that MySQL can avoid the order completely and just read the values in order, if you have an index with the leftmost part matching your ORDER BY condition.