面试官：order by 是怎样排序的？怎么优化？

左手的ㄟ右手 2023-01-24 02:14 164阅读 0赞

# 01 前言 #

刚换了新工作，用了两周时间准备，在 3 天之内拿了 5 个 offer，最后选择了广州某互联网行业独角兽 offer，昨天刚入职。这几天刚好整理下在面试中被问到有意思的问题，也借此机会跟大家分享下。

这家企业的面试官有点意思，一面是个同龄小哥，一起聊了两个小时（聊到我嘴都干了）。二面是个从阿里出来的架构师，视频面试，我做完自我介绍之后，他一开场就问我：

> 对 MySQL 熟悉吗？

我一愣，随之意识到这是个坑。他肯定想问我某方面的原理了，恰好我研究过索引。就回答：

> 对索引比较熟悉。

他：

> order by 是怎么实现排序的？

还好我又复习，基本上排序缓冲区、怎么优化之类的都答到点子上。今天也跟大家盘一盘 order by，我将从原理讲到最终优化，给大家聊聊 order by，希望对你有所帮助。

国际惯例，先上思维导图。**PS：文末有福利**

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mVhFUz0d-1626411356236)(https://gitee.com/turodog/awesome\_image/raw/master/images/order%20by%20%E6%80%8E%E4%B9%88%E4%BC%98%E5%8C%96%EF%BC%9F%20(1)\].png)

## 1.1 往期精彩 ##

[MySQL 查询语句是怎么执行的？][MySQL]

[MySQL 索引][MySQL 1]

[MySQL 日志][MySQL 2]

[MySQL 事务与 MVCC][MySQL _ MVCC]

[MySQL 的锁机制][MySQL 3]

[MySQL 字符串怎么设计索引？][MySQL 4]

[面试官：数据库自增 ID 用完了会咋样？][ID]

## 1.2 先举个栗子 ##

现在有一张订单表，结构是这样的：

CREATE TABLE `order` (
    id INT ( 11 ) NOT NULL AUTO_INCREMENT COMMENT '主键',
    user_code VARCHAR ( 16 ) NOT NULL COMMENT '用户编号',
    goods_name VARCHAR ( 64 ) NOT NULL COMMENT '商品名称',
    order_date TIMESTAMP NULL DEFAULT CURRENT_TIMESTAMP COMMENT '下单时间',
    city VARCHAR ( 16 ) DEFAULT NULL COMMENT '下单城市',
    order_num INT ( 10 ) NOT NULL COMMENT '订单号数量',
    PRIMARY KEY ( `id` ) 
    ) ENGINE = INNODB AUTO_INCREMENT = 100 DEFAULT CHARSET = utf8 COMMENT = '商品订单表';

造点数据：

// 第一步：创建函数
    delimiter //
    
    DROP PROCEDURE
    IF
    	EXISTS proc_buildata;
    CREATE PROCEDURE proc_buildata ( IN loop_times INT ) BEGIN
    DECLARE var INT DEFAULT 0;
    WHILE
    	var < loop_times DO
    	
    	SET var = var + 1;
    INSERT INTO `order` ( `id`, `user_code`, `goods_name`, `order_date`, `city` , `order_num`)
    VALUES
    	( var, var + 1, '有线耳机', '2021-06-20 16:46:00', '杭州', 1 );
    
    END WHILE;
    
    END // delimiter;
    
    // 第二步：调用上面生成的函数，即可插入数据，建议大家造点随机的数据。比如改改城市和订单数量
    CALL proc_buildata(4000);

我生成的数据是这样的：

![3060a3c86aad1bf9acaf2c656c1204f9.png][]

现有需求：**查出 618 期间，广州的小伙伴的订单数量和用户编号，并按照订单数量升序，只要 1000 条**。

根据需求可以得出以下 SQL，相信小伙伴都很熟悉了。

select city, order_num, user_code from `order` where city='广州' order by order_num limit 1000;

那这个语句是怎么执行的呢？有什么参数可以影响它的行为吗？

# 02 全字段排序 #

得到这个需求，我第一反应是先给 city 字段加上索引，避免全表扫描：

ALTER TABLE `order` ADD INDEX city_index ( `city` );

用 explain 看看执行情况

![29ee61b8c0463a51fe19dd656a981917.png][]

注意到最后一个 extra 字段的结果是：**Using filesort**，表示需要排序。**其实 MySQL 会给每个线程分配一块内存用于排序，称为 sort\_buffer**。

为了更直观了解排序的执行流程，我粗略画了个 city 索引的图示：

![081d3cbe067a08437cbec3298e93001d.png][]

可见，现在满足 sql 条件的就是 ID-3 到 ID-X 这一段数据。sql 的整个流程是这样的：

*  1、初始化 sort\_buffer，放入 city、order\_num、user\_code 这三个字段；
 *  2、从索引 city 找到第一个满足 city=’ 广州’条件的主键 id，也就是图中的 ID\_3；
 *  3、到主键 id 索引取出整行，取 city、order\_num、user\_code 三个字段的值，存入 sort\_buffer 中；
 *  4、从索引 city 取下一个记录的主键 id；
 *  5、重复步骤 3、4 直到 city 的值不满足查询条件为止，对应的主键 id 也就是图中的 ID\_X；
 *  6、对 sort\_buffer 中的数据按照字段 order\_num 做快速排序；
 *  7、按照排序结果取前 1000 行返回给客户端。

这个过程称之为全字段排序，画个图，长这样：

![6281edae43713235898c3c7c535ded91.png][]

其中，**按 order\_num 排序**这个步骤，可能在内存中完成，也可能需要使用外部排序，这取决于排序所需的内存和参数 **sort\_buffer\_size**。

也就是 MySQL 为排序开辟的内存（sort\_buffer）的大小。如果要排序的数据量小于 sort\_buffer\_size，排序就在内存中完成。但如果排序数据量太大，内存顶不住，就得磁盘临时文件辅助排序。

当然，在 MySQL5.7 以上版本可以用下面介绍的**检测方法（后面都有用到）**，来查看一个排序语句是否使用了临时文件。PS：**这里的语句直接复制到 navicat 执行即可，要一起执行（都复制进去，点下执行）**

/* 打开optimizer_trace，只对本线程有效 */
    SET optimizer_trace='enabled=on'; 
    
    /* @a保存Innodb_rows_read的初始值 */
    select VARIABLE_VALUE into @a from  performance_schema.session_status where variable_name = 'Innodb_rows_read';
    
    /* 执行语句 */
    select city, order_num, user_code from `order` where city='广州' order by order_num limit 1000; 
    
    /* 查看 OPTIMIZER_TRACE 输出 */
    SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`;
    
    /* @b保存Innodb_rows_read的当前值 */
    select VARIABLE_VALUE into @b from performance_schema.session_status where variable_name = 'Innodb_rows_read';
    
    /* 计算Innodb_rows_read差值 */
    select @b-@a;

执行完之后，可从 OPTIMIZER\_TRACE 表的 TRACE 字段得到以下结果：

![936c2a1b13b735b21e440638dd73da2e.png][]

其中 examined\_rows 表示需要排序的行数 6883；sort\_buffer\_size 就是排序缓冲区的大小；sort\_buffer\_size 就是我 MySQL 的排序缓冲区大小 256 KB。

另外，sort\_mode 的值是 packed\_additional\_fields，它表示排序过程对数据做了优化，也就是数据占用多少就算多少内存。举个栗子：不存在数据定义长度 16，就按这个长度算，如果数据只占 2，只会按长度 2 分配内存。

number\_of\_tmp\_files 代表的是用了几个外部文件来辅助排序。我这里是用了两个，内存放不下时，就使用外部排序，外部排序一般使用**归并排序**算法。可以这么简单理解，**MySQL 将需要排序的数据分成 2 份，每一份单独排序后存在这些临时文件中。然后把这 2 个有序文件再合并成一个有序的大文件**。

最后一个查询语句，select @b-@a 的值是 6884，表示整个过程只扫描了 6883 行，为啥显示 6884？

因为查询 OPTIMIZER\_TRACE 表时，需用到临时表；而 InnDB 引擎把数据从临时表取出时，Inndb\_rows\_read 值会加 1。

所以，把 internal\_tmp\_disk\_storage\_engine 设置为 MyISAM 可解决此问题。

# 03 rowid 排序 #

上面的全字段排序其实会有很大的问题，你可能发现了。**我们需要查询的字段都要放到 sort\_buffer 中，如果查询的字段多了起来，内存占用升高，就会很容易打满 sort\_buffer** 。

这时，就要用很多的临时文件辅助排序，导致性能降低。

那问题来了：

> 我们思考的方向应该是降低排序的单行长度，哪有没有方法能做到呢？

肯定是有的，MySQL 之所以走全字段排序是由 max\_length\_for\_sort\_data 控制的，它的 默认值是 1024。

show variables like 'max_length_for_sort_data';

![5efe8e014a57ce10f28b8a3e11878510.png][]

因为本文示例中 city,order\_num,user\_code 长度 = 16+4+16 =36 < 1024, 所以走的是全字段排序。我们来改下这个参数，改小一点，

SET max_length_for_sort_data = 16;

当单行的长度超过这个值，MySQL 就认为单行太大，要换一个算法。原来 city、user\_code、order\_num 占用的长度是 36，显然放不下全部查询字段了。这时就要换算法：**sort\_buffer 只存 order\_num 和 id 字段**。

这时的流程应该是这样的：

*  1、初始化 sort\_buffer，确定放入两个字段，即 order\_num 和 id；
 *  2、从索引 city 找到第一个满足 city=’ 广州’条件的主键 id，也就是图中的 ID\_3；
 *  3、回表，取 order\_num、id 这两个字段，存入 sort\_buffer 中；
 *  4、从索引 city 取下一个记录的主键 id；
 *  5、重复步骤 3、4 直到不满足 city=’ 广州’条件为止，也就是图中的 ID\_X；
 *  6、对 sort\_buffer 中的数据按照字段 order\_num 进行排序；
 *  7、遍历排序结果，取前 1000 行，再次回表取出 city、order\_num 和 user\_code 三个字段返回给客户端。

图示：由图可见，这种方式其实多了一次回表操作、但 sort\_buffer\_size 占用却变小了。

![36aa77de1305ed9fb3a7d9c858930718.png][]

此时，执行上面的检测方法，可以发现 OPTIMIZER\_TRACE 表中的信息变了。

*  sort\_mode 变成了 <sort\_key, rowid>，**表示参与排序的只有 order\_num 和 id 这两个字段**。
 *  number\_of\_tmp\_files 变成 0 了，是因为这时参与排序的行数虽然仍然是 6883 行，但是每一行都变小了，因此需要排序的总数据量就变小了，sort\_buffer\_size 能满足排序用的内存，所以临时文件就不需要了。

![e7d9370d9e3e24970ae34bb94d92c6a6.png][]

examined\_rows 的值还是 6883，表示用于排序的数据是 6883 行。但是 select @b-@a 这个语句的值变成 7884 了。因为这时候除了排序过程外，在排序完成后，还要回表一次。由于语句是 limit 1000，所以会多读 1000 行。

![098338e3d2a30d06c4f2f2420b6be26b.png][]

## 3.1 做个小结 ##

rowid 排序中，**排序过程一次可以排序更多行，但是需要回表取数据**。

如果内存足够大，MySQL 会优先选择全字段排序，把需要的字段都放到 sort\_buffer 中，这样排序后就会直接从内存返回查询结果了，不用回表。

这也就体现了 MySQL 的一个设计思想：**如果内存够，就要多利用内存，尽量减少磁盘访问**。

**对于 InnoDB 表来说，rowid 排序会要求回表多造成磁盘读，因此不会被优先选择**。

这两种都是因为数据本身是无序的，才要放到 sort\_buffer 并生成临时文件才能做排序。

> 哪有没有办法，让数据本身就有序呢？回想下，我们学过的索引就是有序的。

# 04 索引优化 #

这时，要是我把 city、order\_num 建一个组合索引，得出的数据是不是就是天然有序的了？比如：

alter table `order` add index city_order_num_index(city, order_num);

此时，order 表的索引长这样：

![1e463a2af71ded366c5be1f3f5c58d65.png][]

文章开头的 sql 执行语句。执行流程长这样：

*  1、从索引 (city,order\_num) 找到第一个满足 city=’ 广州’条件的主键 id；
 *  2、回表，取 city、order\_num、user\_code 三个字段的值，作为结果集的一部分直接返回；
 *  3、从索引 (city,order\_num) 取下一个记录主键 id；
 *  4、重复步骤 2、3，直到查到第 1000 条记录，或者是不满足 city=’ 广州’条件时循环结束。

![95f46768473036734fa620b4b7435a22.png][]

用 explain 看下，这个过程不需要排序，更不需要临时表。**只需要一次回表**：

![9b585356c928be69fe0f5a584727f8f0.png][]

从图中可以看到，**Extra 字段中没有 Using filesort 了，也就是不需要排序了**。而且由于 (city,order\_num) 这个联合索引本身有序，只要找到满足条件的前 1000 条记录就可以退出了，再回表一次。也就是说，只需要扫描 2000 次。

> 问题来了，还有没有更优解呢？

# 05 终极优化 #

上面的方法，还是有一次回表，主要是因为索引中不包括 user\_code。回顾下我们之前学过的 sql 优化，是怎么避免回表的？

**查询字段，加到组合索引中呀**，对应到这张表，就是把 user\_code 也加到组合索引中：

alter table `order` add index city_order_num_user_code_index(city, order_num, user_code);

此时的流程长这样，直接取数据就完事了：

![068f603b541dcdd158f1f4463f3bc29e.png][]

explain 看下执行情况：

![f5852b2baeabe5eb7b97ff99b63a6ff8.png][]

从图中可知，**Extra 字段中多了 Using index 了，也就是使用了索引覆盖**。连回表都不需要了，只需扫描 1000 次。

完美~

## 5.1 参数调优 ##

除此以外，还可以通过调整参数优化 order by 的执行。**比如调整 sort\_buffer\_size 尽量大点**，因为 sort\_buffer 太小，排序数据量大的话，会借助磁盘临时文件排序。如果 MySQL 服务器配置高的话，可以稍微调大点。

再**比如把 max\_length\_for\_sort\_data 的值调大点**。如果该值过小，则会增加回表次数、降低查询性能。

# 06 order by 常见面试题 #

> 1、查询语句有 in 多个属性时，SQL 执行是否有排序过程？

假设现在有联合索引 (city,order\_num,user\_code)，执行以下 SQL 语句：

select city, order_num, user_code from `order` where city in ('广州') order by order_num limit 1000

in 单个条件，毫无疑问是不需要排序的。explain 一下：

![99c13f4041506d5f4afdbbae82606504.png][]

但是，in 多个条件时；就会有排序过程，比如执行以下语句

select city, order_num, user_code from `order` where city in ('广州','深圳') order by order_num limit 1000

explain 以下，看到最后有 Using filesort 就说明有排序过程。这是为啥呢？

![74e90d7333c64fb76e069c12e8f9fc4d.png][]

因为 order\_num 本来就是组合索引，满足 “city=广州” 只有一个条件时，它是有序的。满足 “city=深圳” 时，它也是有序的。但是两者加到一起就不能保证 order\_num 还是有序的了。

> 2、分页 limit 过大，导致大量排序。咋办？

select * from `user` order by age limit 100000,10

*  可以记录上一页最后的 id，下一页查询时，查询条件带上 id，如：where id > 上一页最后 id limit 10。
 *  也可以在业务允许的情况下，限制页数。

> 3、索引存储顺序与 order by 不一致，如何优化？

假设有联合索引 (age,name)， 我们需求修改为这样：**查询前 10 个学生的姓名、年龄，并且按照年龄小到大排序，如果年龄相同，则按姓名降序排**。对应的 SQL 语句应该是：

select name, age from student order by age, name desc limit 10;

explain 一下，**extra 的值是 Using filesort**，走了排序过程：

![7c454df3a8d5ee866c6806c907d925f7.png][]

这是因为，(age,name) 索引树中，age 从小到大排序，**如果 age 相同，再按 name 从小到大排序**。而 order by 中，是按 age 从小到大排序，如果 age 相同，再按 name 从大到小排序。也就是说，索引存储顺序与 order by 不一致。

我们怎么优化呢？如果 MySQL 是 8.0 版本，支持 **Descending Indexes**，可以这样修改索引：

CREATE TABLE `student` (
      `id` bigint(11) NOT NULL AUTO_INCREMENT COMMENT '主键id',
      `student_id` varchar(20) NOT NULL COMMENT '学号',
      `name` varchar(64) NOT NULL COMMENT '姓名',
      `age` int(4) NOT NULL COMMENT '年龄',
      `city` varchar(64) NOT NULL COMMENT '城市',
      PRIMARY KEY (`id`),
      KEY `idx_age_name` (`age`,`name` desc) USING BTREE
    ) ENGINE=InnoDB AUTO_INCREMENT=15 DEFAULT CHARSET=utf8 COMMENT='学生表';

> 4、没有 where 条件，order by 字段需要加索引吗

日常开发中，可能会遇到没有 where 条件的 order by，这时候 order by 后面的字段是否需要加索引呢。如有这么一个 SQL，create\_time 是否需要加索引：

select * from student order by create_time;

无条件查询的话，即使 create\_time 上有索引，也不会使用到。**因为 MySQL 优化器认为走普通二级索引，再去回表成本比全表扫描排序更高**。所以选择走全表扫描，然后根据全字段排序或者 rowid 排序来进行。

如果查询 SQL 修改一下：

select * from student order by create_time limit m;

无条件查询，如果 m 值较小，是可以走索引的。因为 MySQL 优化器认为，根据索引有序性去回表查数据，然后得到 m 条数据，就可以终止循环，那么成本比全表扫描小，则选择走二级索引。

# 07 总结 #

这篇文章跟你聊了聊 order by 的执行流程，以及全字段排序和 rowid 排序的区别，从而得知，**MySQL 更愿意用内存去换取性能上的提升**。

与此同时，通过组合索引的索引覆盖小技巧，我们还可以减少回表的次数。**以后设计索引的时候如果业务有涉及排序的字段，尽量加到索引中，并且把业务中其余的查询字段（比如文中的 city、user\_code）加到组合索引中，更好地实现索引覆盖**。

当然，索引也有缺点。它占空间，有维护的代价。所以大家设计的时候还是需要根据自己的实际业务去考虑。

最后，我还跟你探讨了关于 order by 的四个经典面试题，希望对你有帮助。

### 7.1 参考 ###

*  blog.csdn.net/weixin\_28917279/article/details/113424610
 *  https://time.geekbang.org/column/article/73479
 *  https://zhuanlan.zhihu.com/p/380671457

# 08 idea 激活 #

[jetbrains 全家桶激活][jetbrains]

# 09 大厂面试题 & 电子书 #

如果看到这里，喜欢这篇文章的话，请帮点个**好看**。

初次见面，也不知道送你们啥。干脆就送**几百本电子书**和**2021最新面试资料**吧。微信搜索**JavaFish**回复**电子书**送你 1000+ 本编程电子书；回复**面试**送点面试题；回复**1024**送你一套完整的 java 视频教程。

面试题都是有答案的，详细如下所示：有需要的就来拿吧，**绝对免费，无套路获取**。

![面试题][f7fb80ac3cce1e9520824533308f57b3.png]

[MySQL]: https://mp.weixin.qq.com/s/lRY7b9iS_xDDuyKNQKUWSg
[MySQL 1]: https://mp.weixin.qq.com/s/ZDM_ttWCstw0mUwGtUEciw
[MySQL 2]: https://mp.weixin.qq.com/s/yG2pQW7qkTPF4TLBk8qgwQ
[MySQL _ MVCC]: https://mp.weixin.qq.com/s/l62CAZ55ZU9f9fsLOQR71A
[MySQL 3]: https://mp.weixin.qq.com/s/cuD8QiadO64VcSncpY18KQ
[MySQL 4]: https://mp.weixin.qq.com/s/71eMW6ejKX-E3zfU79jNQA
[ID]: https://mp.weixin.qq.com/s/1gmpJqBmCBsNPlLbrN0Q7Q
[3060a3c86aad1bf9acaf2c656c1204f9.png]: /images/20221004/99258d565fd84681aaef79263f4c533f.png
[29ee61b8c0463a51fe19dd656a981917.png]: /images/20221004/ad69c6c4919c4260a2cec693dfff40bf.png
[081d3cbe067a08437cbec3298e93001d.png]: /images/20221004/73fe90c6098b42be8771f213fdd739a9.png
[6281edae43713235898c3c7c535ded91.png]: /images/20221004/2e6c771d41364565996e149fa024251a.png
[936c2a1b13b735b21e440638dd73da2e.png]: /images/20221004/c88c738447404e9cba35a5aac6997639.png
[5efe8e014a57ce10f28b8a3e11878510.png]: /images/20221004/adba01002276450f9013174bbdb4e18e.png
[36aa77de1305ed9fb3a7d9c858930718.png]: /images/20221004/16e4cbd90ee94245b78d4327ebd94d79.png
[e7d9370d9e3e24970ae34bb94d92c6a6.png]: /images/20221004/97f43d8da87544b3b6664fd164728b2a.png
[098338e3d2a30d06c4f2f2420b6be26b.png]: /images/20221004/c3ce758f5f144e31b67a549148e34e3e.png
[1e463a2af71ded366c5be1f3f5c58d65.png]: /images/20221004/2d23755fbaca4a47a840f9c92ba31360.png
[95f46768473036734fa620b4b7435a22.png]: /images/20221004/38346945dac6469683c76266c1da3e67.png
[9b585356c928be69fe0f5a584727f8f0.png]: /images/20221004/35d5f8940cd346d281dd61109734cf37.png
[068f603b541dcdd158f1f4463f3bc29e.png]: /images/20221004/268cd7f4515944b69a99b7b387bb3de6.png
[f5852b2baeabe5eb7b97ff99b63a6ff8.png]: /images/20221004/9ec6631f28aa4f9db6df2d4f25689551.png
[99c13f4041506d5f4afdbbae82606504.png]: /images/20221004/f28bea75f32b4664bd1f3555e5899433.png
[74e90d7333c64fb76e069c12e8f9fc4d.png]: /images/20221004/993cbf86682243c1ac738ded65c9aef1.png
[7c454df3a8d5ee866c6806c907d925f7.png]: /images/20221004/757d76de88334bed95cf4cafac6a4973.png
[jetbrains]: https://www.yuque.com/docs/share/1f249293-1ef5-4df1-a1a3-06507d19345c?#%20%E3%80%8Ajetbrains%20%E5%85%A8%E5%AE%B6%E6%A1%B6%E6%BF%80%E6%B4%BB%E3%80%8B
[f7fb80ac3cce1e9520824533308f57b3.png]: /images/20221004/26f2d223dee24f5fba3121f22d1f0bcb.png