Mysql - ORDER BY详解

有志者，事竟成！如果你在学习数据库，那么本文《Mysql - ORDER BY详解》，就很适合你！文章讲解的知识点主要包括MySQL、PHP、后端、程序员，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

0 索引

• 1 概述
• 2 索引扫描排序和文件排序简介
• 3 索引扫描排序执行过程分析
• 4 文件排序
• 5 补充说明
• 6 参考资料

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

EXPLAIN 
SELECT * 
    FROM order_detail
        WHERE create_time >= '2018-08-11 00:00:00' and create_time  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 |
+------+-------------+--------------+-------+--------------------+-------------+---------+------+------+-----------------------------+

我们试着分析一下这个SQL的执行过程：

• 利用create_time索引，对满足WHERE子句create_time >= '2018-08-11 00:00:00' and create_time 的rowid进行回表（第一次回表），回表之后可以拿到该rowid对应的userid，若userid满足userid > 140000的条件时，则将该行的rowid，money(ORDER BY的列)放入排序缓冲区。
• 若排序缓冲区能放下所有rowid, money对，则直接在排序缓冲区（内存）进行快排。
• 若排序缓冲区不能放下所有rowid, money对，则分块快排，将块存入临时文件（磁盘），再对块进行归并排序。
• 遍历排序后的结果，对每一个rowid按照排序后的顺序进行回表操作（第二次回表），取出SELECT子句需要的所有字段。

熟悉计算机系统的人可以看出，第二次回表会表比第一次回表的效率低得多，因为第一次回表几乎是顺序I/O；而由于rowid是根据money进行排序的，第二次回表会按照rowid乱序去读取行记录，这些行记录在磁盘中的存储是分散的，每读一行 磁盘都可能会产生寻址时延（磁臂移动到指定磁道）+旋转时延（磁盘旋转到指定扇区），这即是随机I/O。

所以为了避免第二次回表的随机I/O，MySQL在4.1之后做了一些改进：在第一次回表时就取出此次查询用到的所有列，供后续使用。我们称之为单次传输排序。

单次传输排序（MySQL4.1之后引入）

还是上面那条SQL，我们再看看单次传输排序的执行过程：

• 利用create_time索引，对满足WHERE子句create_time >= '2018-08-11 00:00:00' and create_time 的rowid进行回表（第一次回表），回表之后可以拿到改rowid对应的userid，若userid满足userid > 140000的条件时，则将此次查询用到该行的所有列（包括ORDER BY列）取出作为一个数据元组(tuple)，放入排序缓冲区。
• 若排序缓冲区能放下所有tuples，则直接在排序缓冲区（内存）进行快排。
• 若排序缓冲区不能放下所有tuples，则分块快排，将块存入临时文件（磁盘），再对块进行归并排序。
• 遍历排序后的每一个tuple，从tuple中取出SELECT子句需要所有字段。

单次传输排序的弊端在于会将所有涉及到的列都放入排序缓冲区，排序缓冲区一次能放下的tuples更少了，进行归并排序的概率增大。列数据量越大，需要的归并路数更多，增加了额外的I/O开销。所以列数据量太大时，单次传输排序的效率可能还不如两次传输排序。

当然，列数据量太大的情况不是特别常见，所以MySQL的filesort会尽可能使用单次传输排序，但是为了防止上述情况发生，MySQL做了以下限制：

• 所有需要的列或ORDER BY的列只要是BLOB或者TEXT类型，则使用两次传输排序。
• 所有需要的列和ORDER BY的列总大小超过max_length_for_sort_data字节，则使用两次传输排序。

我们开发者也应该尽可能让filesort使用单次传输排序，不过EXPLAIN不会告诉我们这个信息，所以我们只能肉眼检查各列的大小看看是否会触发上面两个限制 导致两次传输排序的发生。

5 补充说明

如第3小节所述，既然filesort的效率未必比索引扫描排序低，为什么很多人会想避免filesort呢？
谷歌一下using filesort，几乎都是"如何避免filesort"相关的内容。:

这是因为通常ORDER BY子句会与LIMIT子句配合，只取出部分行。如果只是为了取出top1的行 却对所有行进行排序，这显然不是一种高效的做法。这种场景下 按顺序取的索引扫描排序可能会比filesort拥有更好性能（当然也有例外）。

Whether the optimizer actually does so depends on whether reading the index is more efficient than a table scan if columns not in the index must also be read.

官方文档告诉我们optimizer会帮我们选择一种高效的ORDER BY方式。
但也不能完全依赖optimizer的判断，这时合理建立索引、引导它使用指定索引可能是更好的选择。

6 参考资料

MySQL 8.0 Reference Manual :: 8.2.1.14 ORDER BY Optimization
《高性能MySQL》
Sergey Petrunia's blog » How MySQL executes ORDER BY
MySQL filesort algorithms - Valinv
MySQL技术内幕:InnoDB存储引擎(第2版)
B+ Tree Visualization
B+ Trees(pdf)
MySQL :: MySQL 8.0 Reference Manual :: 8.8.2 EXPLAIN Output Format
What do Clustered and Non clustered index actually mean? - Stack Overflow

到这里，我们也就讲完了《Mysql - ORDER BY详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于mysql的知识点！