0 索引

1 概述

MySQL有两种方式可以实现 ORDER BY：

1.通过索引扫描生成有序的结果
2.使用文件排序(filesort)

围绕着这两种排序方式，我们试着理解一下ORDER BY的执行过程以及回答一些常见的问题。（下文仅讨论InnoDB存储引擎）

2 索引扫描排序和文件排序(filesort)简介

我们知道InnoDB存储引擎以 B+树 作为索引的底层实现，B+树的 叶子节点 存储着所有数据页而内部节点不存放数据信息，并且所有叶子节点形成一个**(双向)链表**。
举个例子，假设userinfo表的userid字段上有主键索引，且userid目前的范围在1001~1006之间，则userid的索引B+树如下：(这里只是为了举例，下图忽略了InnoDB数据页默认大小16KB、双向链表，并且假设B+树度数为3、userid顺序插入)

现在我们想按照userid从小到大的顺序取出所有用户信息，执行以下SQL

SELECT * FROM userinfoORDER BY userid;

MySQL会直接遍历上图userid索引的叶子节点链表，不需要进行额外的排序操作。这就是用索引扫描来排序。

但如果userid字段上没有任何索引，图1的B+树结构不存在，MySQL就只能先扫表筛选出符合条件的数据，再将筛选结果根据userid排序。这个排序过程就是filesort。

下文将详细介绍这两种排序方式。

3 索引扫描排序执行过程分析

介绍索引扫描排序之前，先 看看索引的用途
SQL语句中，WHERE子句和ORDER BY子句都可以使用索引：WHERE子句使用索引避免全表扫描，ORDER BY子句使用索引避免filesort（用“避免”可能有些欠妥，某些场景下全表扫描、filesort未必比走索引慢），以提高查询效率。
虽然索引能提高查询效率，但在一条SQL里，对于一张表的查询 一次只能使用一个索引（注：排除发生index merge的可能性），也就是说当WHERE子句与ORDER BY子句要使用的索引不一致时，MySQL只能使用其中一个索引(B+树)。

也就是说，一个既有WHERE又有ORDER BY的SQL中，使用索引有三个可能的场景:

	1.只用于WHERE子句 筛选出满足条件的数据2.只用于ORDER BY子句 返回排序后的结果3.既用于WHERE又用于ORDER BY，筛选出满足条件的数据并返回排序后的结果

举个例子，我们创建一张order_detail表 记录每一笔充值记录的userid(用户id)、money(充值金额)、create_time(充值时间)，主键是自增id：

CREATE TABLE `order_detail` (`id` int(11) NOT NULL AUTO_INCREMENT,`userid` int(11) NOT NULL,`money` float NOT NULL,`create_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,PRIMARY KEY (`id`),KEY `userid` (`userid`),KEY `create_time` (`create_time`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

写脚本插入100w行数据（InnoDB别用COUNT(*)查总行数，会扫全表，这里只是为了演示）:

SELECT COUNT(*) FROM order_detail;
+----------+
| COUNT(*) |
+----------+
|  1000000 |
+----------+SELECT * FROM order_detail LIMIT 5;
+----+--------+-------+---------------------+
| id | userid | money | create_time         |
+----+--------+-------+---------------------+
|  1 | 104832 |  3109 | 2013-01-01 07:40:38 |
|  2 | 138455 |  6123 | 2013-01-01 07:40:42 |
|  3 | 109967 |  7925 | 2013-01-01 07:40:46 |
|  4 | 166686 |  4307 | 2013-01-01 07:40:55 |
|  5 | 119837 |  1912 | 2013-01-01 07:40:58 |
+----+--------+-------+---------------------+

现在我们想取出userid=104832用户的所有充值记录，并按照充值时间create_time正序返回。

写出如下SQL并EXPLAIN一下:

EXPLAINSELECT *FROM order_detailWHERE userid = 104832ORDER BY create_time;
+------+-------------+--------------+------+---------------+--------+---------+-------+------+-----------------------------+
| id   | select_type | table        | type | possible_keys | key    | key_len | ref   | rows | Extra                       |
+------+-------------+--------------+------+---------------+--------+---------+-------+------+-----------------------------+
|    1 | SIMPLE      | order_detail | ref  | userid        | userid | 4       | const |    8 | Using where; Using filesort |
+------+-------------+--------------+------+---------------+--------+---------+-------+------+-----------------------------+

key列的值是userid，可以看出这条SQL会使用userid索引用作WHERE子句的条件过滤，而ORDER BY子句无法使用该索引，只能使用filesort来排序。这就是上文的第一个场景，整个执行流程大致如下：

1.先通过userid索引找到所有满足WHERE条件的主键id（注:从b+树根节点往下找叶子节点，时间复杂度为O(logN))
2.再根据这些主键id去主键索引(聚簇索引))找到这几行的数据，生成一张临时表（时间复杂度为O(M*logN)，M是临时表的行数）
3.对临时表进行排序（时间复杂度O(M*logM)，M是临时表的行数)

由于本例中M的值可以大概参考rows列的值8，非常小，所以整个执行过程只花费0.00 sec

接下来是上文的第二种场景，索引只用于ORDER BY子句，这即是索引扫描排序：
我们可以继续使用上文的SQL，通过FORCE INDEX子句强制Optimizer使用ORDER BY子句的索引create_time:

EXPLAINSELECT *FROM order_detailFORCE INDEX (create_time)WHERE userid = 104832ORDER BY create_time;
+------+-------------+--------------+-------+---------------+-------------+---------+------+--------+-------------+
| id   | select_type | table        | type  | possible_keys | key         | key_len | ref  | rows   | Extra       |
+------+-------------+--------------+-------+---------------+-------------+---------+------+--------+-------------+
|    1 | SIMPLE      | order_detail | index | NULL          | create_time | 4       | NULL | 998056 | Using where |
+------+-------------+--------------+-------+---------------+-------------+---------+------+--------+-------------+

可以看到Extra字段里的Using filesort已经没了，但是扫过的rows大概有998056行(准确的值应该是1000000行，InnoDB这一列只是估值)。这是因为索引用于ORDER BY子句时，会直接遍历该索引的叶子节点链表，而不像第一种场景那样从B+树的根节点出发 往下查找。执行流程如下：

1.从create_time索引的第一个叶子节点出发，按顺序扫描所有叶子节点
2.根据每个叶子节点记录的主键id去主键索引(聚簇索引))找到真实的行数据，判断行数据是否满足WHERE子句的userid条件，若满足，则取出并返回

整个时间复杂度是O(M*logN)，M是主键id的总数，N是聚簇索引叶子节点的个数(数据页的个数)
本例中M的值为1000000，所以整个执行过程比第一种场景花了更多时间，同一台机器上耗时1.34 sec

上述两个例子恰好说明了另一个道理：在某些场景下使用filesort比不使用filesort 效率更高。

 EXPLAIN SELECT * FROM order_detail WHERE create_time >= '2018-08-11 00:00:00' and create_time < '2018-08-12 00:00:00' and userid > 140000 order by money desc;+------+-------------+--------------+-------+--------------------+-------------+---------+------+------+-----------------------------+| id | select_type | table        | type | possible_keys      | key         | key_len | ref | rows | Extra | +------+-------------+--------------+-------+--------------------+-------------+---------+------+------+-----------------------------+| 1 | SIMPLE       | order_detail | range| userid,create_time | create_time | 4       | NULL | 1   | Using where; Using filesort | +------+-------------+--------------+-------+--------------------+-------------+---------+------+------+-----------------------------+