Mysql - ORDER BY详解

阳光穿透心脏的1/2处 2023-03-04 06:31 12阅读 0赞

## 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顺序插入)

![在这里插入图片描述][20200801151727383.png]  
现在我们想按照**userid**从小到大的顺序取出所有用户信息，执行以下SQL

SELECT * 
      FROM userinfo
        ORDER BY userid;

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

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

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

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

介绍索引扫描排序之前，先 [看看索引的用途][Link 1]  
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**正序返回。  
![在这里插入图片描述][20200801152252117.png]  
写出如下SQL并EXPLAIN一下:

`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`  
![在这里插入图片描述][20200801152629102.png]  
接下来是上文的**第二种场景**，索引只用于**ORDER BY子句**，这即是索引扫描排序：  
我们可以继续使用上文的SQL，通过**FORCE INDEX子句强制Optimizer使用ORDER BY子句的索引create\_time:**

可以看到**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 效率更高**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXNodWFpNTI4_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20200801152938570.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXNodWFpNTI4_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXNodWFpNTI4_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXNodWFpNTI4_size_16_color_FFFFFF_t_70 3]

[20200801151727383.png]: /images/20230208/c48ab36a5dc34c3a91206628b6b262d8.png
[Link 1]: https://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.html
[20200801152252117.png]: /images/20230208/ede37df579e3480aa11f6bba6f91bb31.png
[20200801152629102.png]: /images/20230208/21d05815e82a4089b14516f1740277fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXNodWFpNTI4_size_16_color_FFFFFF_t_70]: /images/20230208/0fdd9ebadb2e4fb6bd227a349f72bb8e.png
[20200801152938570.png]: /images/20230208/72f11c37e3b4451ea10aec5e4df6b388.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXNodWFpNTI4_size_16_color_FFFFFF_t_70 1]: /images/20230208/c51d30e023874bee8d1c9931c5d7c068.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXNodWFpNTI4_size_16_color_FFFFFF_t_70 2]: /images/20230208/c2b044e7941147e5b4103fa0ddcebf80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXNodWFpNTI4_size_16_color_FFFFFF_t_70 3]: /images/20230208/63d5b343eea54181855793e64310ae14.png