MySQL查询优化：ORDER BY

通常我们通过explain查看MySQL执行计划时，经常会看到在Extra列中显示Using filesort。其实这种情况就说明MySQL使用了排序。Using filesort经常出现在order by、group by、distinct、join查询等情况下。

一、使用索引来满足ORDER BY

为了优化SQL语句的排序性能，最好的情况是避免排序，合理利用索引是一个不错的方法，因为索引本身也是有序的，如果在需要排序的字段上面建立了合适的索引，那么就可以跳过排序的过程，提高SQL的查询速度。下面我通过一些典型的SQL来说明哪些SQL可以利用索引减少排序，哪些SQL不能。

假设t1表存在索引：idx_k_c(k,c)，idx_pad(pad)

mysql> show index from sbtest1;
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| sbtest1 |          0 | PRIMARY  |            1 | id          | A         |      986400 |     NULL | NULL   |      | BTREE      |         |               |
| sbtest1 |          1 | idx_k_c  |            1 | k           | A         |      193765 |     NULL | NULL   |      | BTREE      |         |               |
| sbtest1 |          1 | idx_k_c  |            2 | c           | A         |      986400 |     NULL | NULL   |      | BTREE      |         |               |
| sbtest1 |          1 | idx_pad  |            1 | pad         | A         |      986400 |     NULL | NULL   |      | BTREE      |         |               |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
4 rows in set (0.00 sec)

mysql> show index from sbtest1;

+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

| sbtest1 | 0 | PRIMARY | 1 | id | A | 986400 | NULL | NULL | | BTREE | | |

| sbtest1 | 1 | idx_k_c | 1 | k | A | 193765 | NULL | NULL | | BTREE | | |

| sbtest1 | 1 | idx_k_c | 2 | c | A | 986400 | NULL | NULL | | BTREE | | |

| sbtest1 | 1 | idx_pad | 1 | pad | A | 986400 | NULL | NULL | | BTREE | | |

+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

4 rows in set (0.00 sec)

1. 可以利用索引避免排序的SQL

ORDER BY的索引优化

mysql> desc select k,c from sbtest1 order by k,c;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+
| id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+
|  1 | SIMPLE      | sbtest1 | NULL       | index | NULL          | idx_k_c | 13      | NULL | 993720 |   100.00 | Using index |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> desc select k,c from sbtest1 order by k,c;

+----+-------------+---------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+--------+----------+-------------+

1 row in set, 1 warning (0.00 sec)

WHERE + ORDER BY的索引优化

mysql> desc select k,c from sbtest1 where k=136150 order by c desc;  
+----+-------------+---------+------------+------+---------------+---------+---------+-------+------+----------+--------------------------+
| id | select_type | table   | partitions | type | possible_keys | key     | key_len | ref   | rows | filtered | Extra                    |
+----+-------------+---------+------------+------+---------------+---------+---------+-------+------+----------+--------------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | ref  | idx_k_c       | idx_k_c | 4       | const |    1 |   100.00 | Using where; Using index |
+----+-------------+---------+------------+------+---------------+---------+---------+-------+------+----------+--------------------------+
1 row in set, 1 warning (0.00 sec)

mysql> desc select * from sbtest1 where k<136250 order by k desc;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+
| id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k_c       | idx_k_c | 4       | NULL |    2 |   100.00 | Using where; Using index |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+
1 row in set, 1 warning (0.00 sec)

mysql> desc SELECT * FROM sbtest1 WHERE k = 498670 AND c > 3145137358 ORDER BY c desc;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+
| id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k_c       | idx_k_c | 13      | NULL |   72 |   100.00 | Using index condition |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

mysql> desc SELECT * FROM sbtest1 WHERE k < 498670 AND c > 3145137358 ORDER BY k desc;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+
| id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k_c       | idx_k_c | 13      | NULL |   72 |   100.00 | Using index condition |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

mysql> desc select k,c from sbtest1 where k=136150 order by c desc;

+----+-------------+---------+------------+------+---------------+---------+---------+-------+------+----------+--------------------------+

+----+-------------+---------+------------+------+---------------+---------+---------+-------+------+----------+--------------------------+

| 1 | SIMPLE | sbtest1 | NULL | ref | idx_k_c | idx_k_c | 4 | const | 1 | 100.00 | Using where; Using index |

+----+-------------+---------+------------+------+---------------+---------+---------+-------+------+----------+--------------------------+

1 row in set, 1 warning (0.00 sec)

mysql> desc select * from sbtest1 where k<136250 order by k desc;

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+--------------------------+

1 row in set, 1 warning (0.00 sec)

mysql> desc SELECT * FROM sbtest1 WHERE k = 498670 AND c > 3145137358 ORDER BY c desc;

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.00 sec)

mysql> desc SELECT * FROM sbtest1 WHERE k < 498670 AND c > 3145137358 ORDER BY k desc;

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+------+----------+-----------------------+

1 row in set, 1 warning (0.00 sec)

2. 不能利用索引避免排序的SQL

# 排序字段在多个索引中,无法使用索引排序,查询一次只能使用一个索引;
mysql> desc select * from sbtest1 where k>591670 order by k,c,pad;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+
| id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                                 |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k_c       | idx_k_c | 4       | NULL | 65524 |   100.00 | Using index condition; Using filesort |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+
1 row in set, 1 warning (0.00 sec)
 
# 排序键顺序与索引中列顺序不一致,无法使用索引排序;
mysql> desc select * from sbtest1 where k>591670 order by c,k;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+
| id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                                 |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k_c       | idx_k_c | 4       | NULL | 65524 |   100.00 | Using index condition; Using filesort |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+
1 row in set, 1 warning (0.00 sec)
 
# 升降序不一致,无法使用索引排序;
mysql> desc select k,c from sbtest1 where k>591670 order by k asc,c desc;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+
| id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                                    |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k_c       | idx_k_c | 4       | NULL | 65524 |   100.00 | Using where; Using index; Using filesort |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+
1 row in set, 1 warning (0.00 sec)
 
# 条件1是范围查询,无法使用索引排序,具体跟组合索引数据分布有关系;
mysql> desc select k,c from sbtest1 where k>591670 order by c;
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+
| id | select_type | table   | partitions | type  | possible_keys | key     | key_len | ref  | rows  | filtered | Extra                                    |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | range | idx_k_c       | idx_k_c | 4       | NULL | 65524 |   100.00 | Using where; Using index; Using filesort |
+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+
1 row in set, 1 warning (0.00 sec)

# 排序字段在多个索引中,无法使用索引排序,查询一次只能使用一个索引;

mysql> desc select * from sbtest1 where k>591670 order by k,c,pad;

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+

1 row in set, 1 warning (0.00 sec)

# 排序键顺序与索引中列顺序不一致,无法使用索引排序;

mysql> desc select * from sbtest1 where k>591670 order by c,k;

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+---------------------------------------+

1 row in set, 1 warning (0.00 sec)

# 升降序不一致,无法使用索引排序;

mysql> desc select k,c from sbtest1 where k>591670 order by k asc,c desc;

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+

1 row in set, 1 warning (0.00 sec)

# 条件1是范围查询,无法使用索引排序,具体跟组合索引数据分布有关系;

mysql> desc select k,c from sbtest1 where k>591670 order by c;

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+

+----+-------------+---------+------------+-------+---------------+---------+---------+------+-------+----------+------------------------------------------+

1 row in set, 1 warning (0.00 sec)

当你逻辑表达式为OR时，使用索引排序会丢失：

mysql> desc SELECT * FROM sbtest1 WHERE k = 498670 OR c=3145137358 ORDER BY c;
+----+-------------+---------+------------+------+---------------+------+---------+------+--------+----------+-----------------------------+
| id | select_type | table   | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra                       |
+----+-------------+---------+------------+------+---------------+------+---------+------+--------+----------+-----------------------------+
|  1 | SIMPLE      | sbtest1 | NULL       | ALL  | idx_k_c       | NULL | NULL    | NULL | 993720 |    10.00 | Using where; Using filesort |
+----+-------------+---------+------------+------+---------------+------+---------+------+--------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)

mysql> desc SELECT * FROM sbtest1 WHERE k = 498670 OR c=3145137358 ORDER BY c;

+----+-------------+---------+------------+------+---------------+------+---------+------+--------+----------+-----------------------------+

+----+-------------+---------+------------+------+---------------+------+---------+------+--------+----------+-----------------------------+

+----+-------------+---------+------------+------+---------------+------+---------+------+--------+----------+-----------------------------+

1 row in set, 1 warning (0.00 sec)

这可以通过使用UNION来解决：

SELECT * FROM t1 FORCE INDEX（key1_key2_key3）
  WHERE key1 = 1 ORDER BY key2，key3 LIMIT 10
UNION 
SELECT * FROM t1 FORCE INDEX（key1_key2_key3）
WHERE key1 = 2 ORDER BY key2， key3 LIMIT 10
ORDER BY key2，key3 LIMIT 5，5;

SELECT * FROM t1 FORCE INDEX（key1_key2_key3）

WHERE key1 = 1 ORDER BY key2，key3 LIMIT 10

UNION

SELECT * FROM t1 FORCE INDEX（key1_key2_key3）

WHERE key1 = 2 ORDER BY key2， key3 LIMIT 10

ORDER BY key2，key3 LIMIT 5，5;

我们要注意的是：

MySQL一次查询只能使用一个索引，如果要对多个字段使用索引，建立复合索引。
在ORDER BY操作中，MySQL只有在排序条件不是一个查询条件表达式的情况下才使用索引。

另外，重点说一下下面两个SQL，一个可以走索引排序，一个不可以走索引排序：

# WHERE + ORDER BY的索引优化;
mysql> desc select k,c from sbtest1 where k=136150 order by c desc; 

# 条件1是范围查询,无法使用索引排序,具体跟组合索引数据分布有关系;
mysql> desc select k,c from sbtest1 where k>591670 order by c desc;

# WHERE + ORDER BY的索引优化;

mysql> desc select k,c from sbtest1 where k=136150 order by c desc;

# 条件1是范围查询,无法使用索引排序,具体跟组合索引数据分布有关系;

mysql> desc select k,c from sbtest1 where k>591670 order by c desc;

主要区别索引k是不是等于，我们发现k条件是等于时order by c就可以走索引排序，k条件不是等于时order by c就不能走索引排序。这个主要跟组合索引的数据分布规则有关。在MySQL中，组合索引的第一个字段一定是升序的，而第二个字段就不一定了。所以当k>591670 order by c desc时就需要额外的排序动作。

看一下组合索引的规则就明白了为什么会这样，提供下面一些数据：

mysql> select a,b from t1;
+------+------+
| a    | b    |
+------+------+
|    1 |    2 |
|    3 |    3 |
|    2 |    1 |
|    2 |    2 |
|    5 |    4 |
|    1 |    4 |
+------+------+
6 rows in set (0.00 sec)

mysql> select a,b from t1;

+------+------+

| a | b |

+------+------+

| 1 | 2 |

| 3 | 3 |

| 2 | 1 |

| 2 | 2 |

| 5 | 4 |

| 1 | 4 |

+------+------+

6 rows in set (0.00 sec)

如果给a,b添加一个组合索引，那么这个组合索引的数据分布规则其实就是select a,b from t1 order by a,b的结果，如下：

mysql> select a,b from t1 order by a,b;
+------+------+
| a    | b    |
+------+------+
|    1 |    2 |
|    1 |    4 |
|    2 |    1 |
|    2 |    2 |
|    3 |    3 |
|    5 |    4 |
+------+------+
6 rows in set (0.00 sec)

mysql> select a,b from t1 order by a,b;

+------+------+

| a | b |

+------+------+

| 1 | 2 |

| 1 | 4 |

| 2 | 1 |

| 2 | 2 |

| 3 | 3 |

| 5 | 4 |

+------+------+

6 rows in set (0.00 sec)

第一列a肯定是排序好的（默认是升序），而第二个字段b其实就不是排序的了。但是如果a字段有相同的值时，那么b字段就是排序的了。明白了这个其实就很好明白上面的两条SQL了，为什么k=？时可以使用到索引排序，而k>？时无法使用到索引排序了。

二、排序实现的算法

对于不能利用索引避免排序的SQL，数据库不得不自己实现排序功能以满足用户需求，此时SQL的执行计划中会出现“Using filesort”，这里需要注意的是filesort并不意味着就是文件排序，其实也有可能是内存排序，这个主要由sort_buffer_size参数与结果集大小确定。

MySQL内部实现排序主要有3种方式：原始排序算法（回表排序），优化后的排序算法（不回表排序）和优先队列排序算法；主要涉及3种排序算法：快速排序、归并排序和堆排序。

原始排序算法（回表排序算法）

原始filesort算法的工作原理如下：

1）根据索引或者全表扫描，按照过滤条件获得需要查询的排序字段值和row ID；

2）将要排序字段值和row ID组成键值对，存入sort buffer中；是一对元组；

3）如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort（快速排序算法）在内存中排好序，并写到临时文件中；

4）重复上述步骤，直到所有的行数据都正常读取了完成；

5）若排序中产生了临时文件，需要利用磁盘外部排序，将row ID写入到结果文件中；

6）根据结果文件中的row ID按序读取用户需要返回的数据。由于row ID不是顺序的，导致回表时是随机IO，为了进一步优化性能（变成顺序IO），MySQL会读一批row ID，并将读到的数据按排序字段顺序插入缓存区中（内存大小read_rnd_buffer_size）。然后有序去取记录，将随机IO转为顺序IO，将获取的结果集返回给用户。

从上述流程来看，是否使用文件排序主要看sort buffer是否能容下需要排序的的结果集，这个buffer的大小由sort_buffer_size参数控制。此外一次排序还需要两次IO，一次是取排序字段+row ID到sort buffer中，第二次是通过上面取出的row ID回表取其他所需要返回的列。由于返回的结果集是按排序字段排序，因此row ID是乱序的，通过乱序的row ID回表取数据时会产生大量的随机IO，所以对于回表取数据MySQL本身会优化，即在取之前先将row ID排序，并放入缓冲区，这个缓存区大小由参数read_rnd_buffer_size控制，然后有序去取记录，将随机IO转为顺序IO。这就是最原始的排序算法了。

优化后的排序算法（不回表排序）

1）根据索引或者全表扫描，按照过滤条件获得需要查询的数据；

2）将要排序的列值和用户需要返回的字段组成键值对，存入sort buffer中；

3）如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(快速排序算法)在内存中排好序，并写到临时文件中；

4）重复上述步骤，直到所有的行数据都正常读取了完成；

5）用到了临时文件的，需要利用磁盘外部排序，将排序后的数据写入到结果文件中；

6）直接从结果文件中返回用户需要的字段数据，而不是根据row ID再次回表查询。

原始排序算法除了排序本身，还需要额外两次IO操作。优化后的排序算法相对于原始排序算法减少了第二次IO操作。主要区别在于，优化后的排序算法一次性取出SQL中出现的所有字段并放入sort buffer中，而不是只取排序需要的字段和row ID。由于sort buffer中包含了查询需要的所有字段，因此排序完成后可以直接返回，无需二次回表。这种方式的代价在于，同样大小的sort buffer，能存放的“SQL所有字段”数目要小于“排序字段+row ID”，如果sort buffer不够大，可能导致需要写临时文件，造成额外的IO。当然MySQL提供了参数max_length_for_sort_data，只有当排序SQL里出现的所有字段小于max_length_for_sort_data时，才能利用优化排序方式，否则只能使用原始排序算法。

优先队列排序（内存中排序）

为了得到最终的排序结果，我们都需要将所有满足条件的记录进行排序才能返回。那么相对于优化后的排序算法，是否还有优化空间呢？MySQL 5.6版本开始针对Order by limit M,N语句，在空间层面做了优化，加入了一种新的排序方式–优先队列，类似于FIFO先进先出队列。

算法稍微有点改变，以原始排序（回表排序）模式为例。

sort_buffer_size足够大

如果Limit限制返回N条数据，并且N条数据比sort_buffer_size小，那么MySQL会把sort buffer作为priority queue，在第二步插入priority queue时会按序插入队列；在第三步，队列满了以后，并不会写入外部磁盘文件，而是直接淘汰最尾端的一条数据，直到所有的数据都正常读取完成。

算法如下：

1）根据索引或者全表扫描，按照过滤条件获得需要查询的数据；

2）将要排序的列值和row ID组成键值对，按序存入中priority queue中；

3）如果priority queue满了，直接淘汰最尾端记录；

4）重复上述步骤，直到所有的行数据都正常读取了完成；

5）最后一轮循环，仅将row ID写入到结果文件中；

6）根据结果文件中的row ID按序读取用户需要返回的数据。为了进一步优化性能，MySQL会读一批row ID，并将读到的数据按排序字段要求插入缓存区中(内存大小read_rnd_buffer_size)。

sort_buffer_size不够大

否则，N条数据比sort_buffer_size大的情况下，MySQL无法直接利用sort buffer作为priority queue，正常的文件外部排序还是一样的，只是在最后返回结果时，只根据N个row ID将数据返回出来。具体的算法就不列举了。

这里MySQL到底是否选择priority queue是在sql/filesort.cc的check_if_pq_applicable()函数中确定的，具体的代码细节这里就不展开了。

另外，我们也没有讨论Limit m,n的情况，如果是Limit m,n，上面对应的“N个row ID”就是“M+N个row ID”了，MySQL的Limit m,n其实是取m+n行数据，最后把M条数据丢掉。从上面我们也可以看到sort_buffer_size足够大对Limit数据比较小的情况，优化效果是很明显的。

这种方式采用堆排序实现。堆排序算法特征正好可以解limit这类排序的问题，虽然仍然需要所有字段参与排序，但是只需要M+N个元组的sort buffer空间即可，对于M，N很小的场景，基本不会因为sort buffer不够而导致需要临时文件进行归并排序的问题。对于升序，采用大顶堆，最终堆中的元素组成了最小的N个元素，对于降序，采用小顶堆，最终堆中的元素组成了最大的N的元素。

三、文件排序算法比较

优化器通常选择使用优化后的排序算法，但除了列BLOB或TEXT列之外，在这种情况下它使用原始排序算法。第二种模式是第一种模式的改进，避免了二次回表，采用的是用空间换时间的方法。但是由于sort buffer就那么大，如果用户要查询的数据非常大的话，很多时间浪费在多次磁盘外部排序，导致更多的IO操作，效率可能还不如第一种方式。

所以，MySQL给用户提供了一个max_length_for_sort_data的参数。当“排序的键值对大小” > max_length_for_sort_data时，MySQL认为磁盘外部排序的IO效率不如回表的效率，会选择第一种排序模式；反之，会选择第二种不回表的模式。

假设一个表t1有四个VARCHAR列a，b，c和d，使用filesort查询：

SELECT * FROM t1 ORDER BY a, b;

1	SELECT * FROM t1 ORDER BY a, b;

该查询按照a和b，但返回所有列，因此查询所引用的列是a，b，c和d。根据该filesort算法优化选择，查询的执行过程如下：

对于原始算法，sort buffer元组具有以下内容：

(fixed size a value, fixed size b value, row ID into t1)

1	(fixed size a value, fixed size b value, row ID into t1)

优化程序对固定大小值进行排序。排序后, 优化器将按顺序读取元组, 并使用每个元数据中的row ID从t1中读取行以获取选择列表列值。

对于优化排序算法，排序缓冲区元组具有以下内容:

(fixed size a value, fixed size b value, a value, b value, c value, d value)

1	(fixed size a value, fixed size b value, a value, b value, c value, d value)

优化程序对固定大小值进行排序。排序后, 优化器将按顺序读取元组, 并使用a、b、c和d的值来获取选择列表列值, 而无需再次读取t1。

对于优化后的算法，排序缓冲区元组具有以下内容:

(fixed size a value, fixed size b value,
a length, packed a value, b length, packed b value,
c length, packed c value, d length, packed d value)

(fixed size a value, fixed size b value,

a length, packed a value, b length, packed b value,

c length, packed c value, d length, packed d value)

如果a、b、c或d的任何一个为null，则它们在排序缓冲区中不带空格，而不是在位掩码中。

优化程序对固定大小值进行排序。排序后，优化器将按顺序读取元组，并使用a、b、c和d的值来获取选择列表列值, 而无需再次读取t1。

四、外部排序

1. 两路外部排序

我们先来看一下最简单，最普遍的两路外部排序算法。假设内存只有100M，但是排序的数据有900M，那么对应的外部排序算法如下：

1）从要排序的900M数据中读取100MB数据到内存中，并按照传统的内部排序算法（快速排序）进行排序；

2）将排序好的数据写入磁盘；

3）重复1，2两步，直到每个100MB chunk大小排序好的数据都被写入磁盘；

4）每次读取排序好的chunk中前10MB（= 100MB / (9 chunks + 1)）数据，一共9个chunk需要90MB，剩下的10MB作为输出缓存；

5）对这些数据进行一个“9路归并”，并将结果写入输出缓存。如果输出缓存满了，则直接写入最终排序结果文件并清空输出缓存；如果9个10MB的输入缓存空了，从对应的文件再读10MB的数据，直到读完整个文件。最终输出的排序结果文件就是900MB排好序的数据了。

2. 多路外部排序

上述排序算法是一个两路排序算法（先排序，后归并）。但是这种算法有一个问题，假设要排序的数据是50GB而内存只有100MB，那么每次从500个排序好的分片中取200KB（100MB / 501 约等于200KB）就是很多个随机IO，效率非常慢，对应可以这样来改进：

1）从要排序的50GB数据中读取100MB数据到内存中，并按照传统的内部排序算法（快速排序）进行排序；

2）将排序好的数据写入磁盘；

3）重复1，2两步，直到每个100MB chunk大小排序好的数据都被写入磁盘；

4）每次取25个分片进行归并排序，这样就形成了20个（500/25=20）更大的2.5GB有序的文件；

5）对这20个2.5GB的有序文件进行归并排序，形成最终排序结果文件。

对应的数据量更大的情况可以进行更多次归并。

3. sort_merge_passes

MySQL手册中并没有把sort_merge_passes到底是什么，该值比较大时说明了什么，通过什么方式可以缓解这个问题说明。

我们把上面MySQL的外部排序算法搞清楚了，这个问题就清楚了。

其实sort_merge_passes对应的就是MySQL做归并排序的次数，也就是说，如果sort_merge_passes值比较大，说明sort_buffer和要排序的数据差距越大，我们可以通过增大sort_buffer_size或者让填入sort_buffer_size的键值对更小来缓解sort_merge_passes归并排序的次数。

五、优化ORDER BY

使用索引来优化或者避免排序。
排序和查询的字段尽量少。只查询你用到的字段，不要使用select *；使用Limit查询必要的行数据，这样会使用优先队列排序。
对于未使用优化后的排序算法的语句，请尝试将max_length_for_sort_data值增大，触发使用优化后的排序算法。
tmpdir建议独立存放，放在高速存储设备上。
要提高ORDER BY速度，请检查是否可以让MySQL使用索引而不是额外的排序阶段。如果不可能，您可以尝试以下策略：
增加sort_buffer_size变量值，避免磁盘排序。理想情况下，该值应足够大，以使整个结果集适合于排序缓冲区 (以避免写入磁盘和合并传递)，至少该值必须足够容纳十五个元组。
考虑到存储在排序缓冲区中的列值的大小受max_sort_length系统变量值的影响。例如，如果元组存储长字符串列的值，并且您增加了max_sort_length的值，则排序缓冲区元组的大小也会增加，并且可能要求您增加sort_buffer_size。对于作为字符串表达式的结果计算的列值 (如调用字符串值函数的)，filesort算法无法判断表达式值的最大长度，因此它必须为每个元组分配max_sort_length字节。
增加read_rnd_buffer_size变量值。
每行使用较少的内存，只需声明列大小，因为它们需要保存存储在其中的值。例如，如果值从不超过16个字符，则char(16)比char(200)好。
监控Sort_merge_passes状态变量。sort_merge_passes对应的就是MySQL做归并排序的次数，也就是说，如果sort_merge_passes值比较大，说明sort_buffer和要排序的数据差距越大，我们可以通过增大sort_buffer_size或者让填入sort_buffer_size的键值对更小来缓解sort_merge_passes归并排序的次数。

注意：Using where; Using temporary; Using filesort和Using where; Using temporary这两种情况，解说如下：

Using where; Using temporary; Using filesort：表示进行关联查询时（MySQL中关联查询的概念要更宽泛，不仅仅指两张表的关联才叫关联查询），使用了临时表，并在生成临时表后，又进行了文件排序。而Using where; Using temporary表示，仅仅生成了临时表，而没有进行文件排序（在生成临时表的时候已经排序完毕了）。

有人可能注意了：什么时候会Using temporary，比如 group by 的时候就会创建临时表，而且group by一定包含了排序，因此，当group by字段和查询的字段和order by的字段都是同一个字段时，那么就会发生explain的Extra列就会出现：Using where; Using temporary（使用了临时表，而且使用了索引排序，而不是文件排序(filesort)。

六、ORDER BY执行计划信息

用EXPLAIN SELECT … ORDER BY，你可以检查MySQL是否可以使用索引来解决查询。如果你在Extra列中看到Using filesort，说明不能使用索引排序。Filesort使用类似于MEMORY存储引擎所使用的固定长度的行存储格式，诸如VARCHAR使用固定长度存储的可变长度类型。

另外，如果使用优化器跟踪输出会包含一个filesort_summary模块。例如：

"filesort_summary": {
  "rows": 100,
  "examined_rows": 100,
  "number_of_tmp_files": 0,
  "sort_buffer_size": 25192,
  "sort_mode": "<sort_key, packed_additional_fields>"
}

"filesort_summary": {

"rows": 100,

"examined_rows": 100,

"number_of_tmp_files": 0,

"sort_buffer_size": 25192,

"sort_mode": "<sort_key, packed_additional_fields>"

}

该sort_mode值提供有关使用的filesort算法以及排序缓冲区中的元组内容的信息：

<sort_key, rowid>：这表示使用原始排序算法。排序缓冲区元组是包含原始表行的排序键值和row ID的对，元组按排序键值排序，row ID用于读取表中的行。

<sort_key, additional_fields>：这表示使用优化后的排序算法。排序缓冲区元组包含查询引用的排序键值和列，元组按排序键值排序，列值直接从元组中读取。

<sort_key, packed_additional_fields>：这表示使用优化后的排序算法。排序缓冲区元组包含查询引用的排序键值和打包列，元组按排序键值排序，列值直接从元组中读取。

EXPLAIN不区分ORDER BY是使用优化后的排序算法还是内存排序（优先队列）算法，但在优化器跟踪输出中可以看到，如果存在内存排序算法，则会存在”filesort_priority_queue_optimization”模块。

有关优化器跟踪的信息，请参阅MySQL内部：跟踪优化器，初识MySQL 5.6的optimizer trace

七、补充

假设一个表t1有一个主键id，以及a、b字段；a字段有一个idx_a索引，b字段有一个idx_b字段。下面进行如下查询：

SELECT * FROM t1 where a = 'xxx' ORDER BY id;

1	SELECT * FROM t1 where a = 'xxx' ORDER BY id;

因为经常看见有人这么写查询语句，其实这个ORDER BY id是不需要的，除非是想降序需要添加ORDER BY id DESC。大致原因就是 a 字段已经有了索引，并且是“=”查询，所以查出来的结果必然是顺序的（索引默认是升序的）。又由于InnoDB数据组织方式是根据主键排序的，所以a = ‘xxx’的查询结果必然是根据主键排序的。

大概的数据插入及查询转换如下：

(insert)     (select)
id a          a id
1  2          1  2
2  1          2  1
3  2   ---->  2  3
4  2          2  4
5  4          4  5

(insert) (select)

id a a id

1 2 1 2

2 1 2 1

3 2 ----> 2 3

4 2 2 4

5 4 4 5

比如查询a = 2，那么查询出来的数据就是根据id升序的。

如果把ORDER BY变成b字段呢？

SELECT * FROM t1 where a = 'xxx' ORDER BY b;

1	SELECT * FROM t1 where a = 'xxx' ORDER BY b;

由于b不是主键，所以需要排序操作。

另外即使采用的是InnoDB存储引擎表，对于没有使用ORDER BY子句的选择查询，其结果也可能不会是按照主键顺序进行排序的。因为没有ORDER BY子句的查询只代表从集合中查询数据，而集合是没有顺序概念的。因此要牢记，不要为表中的行假定任何特定的顺序。就是说，在实际使用环境中，如果确实需要有序输出行记录，则必须使用ORDER BY子句。当然，排序需要成本，可以通过变量来查看数据库的排序操作。示例如下：

mysql> show status like '%Sort%';
+-------------------+-------+
| Variable_name     | Value |
+-------------------+-------+
| Sort_merge_passes | 0     |
| Sort_range        | 0     |
| Sort_rows         | 7     |
| Sort_scan         | 1     |
+-------------------+-------+
4 rows in set (0.06 sec)