面试就面试，问我原理干嘛，Order By

本文转载自微信公众号「飞天小牛肉」，作者小牛肉。转载本文请联系飞天小牛肉公众号。

假设有这么一张用户表 user：

• id int(11)：主键
• username varchar(16)：用户名
• age int(11)：年龄
• city varchar(16)：城市

假设有这么一个需求：查询出城市是 “南京” 的所有用户名，并且按照用户名进行排序，返回前 1000 个人的姓名、年龄。

众所周知，排序使用的关键字是 order by，不难写出这样的 SQL 语句：

select city, username, age from user where city = '南京' order by username limit 1000;

这篇文章，我们就来解释下，涉及 order by 的语句具体是怎么执行的，以及有什么参数会影响执行的行为

全字段排序

为避免全表扫描，我们在查询条件的 city 字段上面建立索引。然后用 explain 命令来看看这个语句的执行情况：

偷个懒，因为我其实一条数据也没插入(狗头保命)，所以大伙儿在上图中看见的 explain 分析出来的这条 SQL 的影响行数 rows 是 1

Extra 这个字段中的 Using filesort 表示的就是需要排序，MySQL 会给每个线程分配一块内存用于排序，称为 sort_buffer。

通常情况下，这个语句执行流程如下所示 ：

1)初始化 sort_buffer，放入 city、username、age 这三个字段;

2)从索引 city 找到第一个满足 city='南京' 条件的主键 id

3)到主键 id 的索引树上查找到对应的整行数据(回表查询)，然后取出 city、username、age 三个字段的值，存入 sort_buffer 中

4)从索引 city 取下一个记录的主键 id

5)重复步骤 3、4 直到 city 的值不满足查询条件为止

6)对 sort_buffer 中的数据按照字段 username 做快速排序

按照字段 username 做快速排序这个动作，可能在内存中完成，也可能需要使用外部排序，这取决于排序所需的内存和 sort_buffer 的大小，由参数 sort_buffer_size 决定。

如果要排序的数据量小于 sort_buffer_size，排序就在内存中完成。但如果排序数据量太大，内存放不下，则就需要利用磁盘临时文件来辅助排序。

解释下这里使用磁盘临时文件来进行辅助排序的含义，外部排序常用的排序算法是多路归并排序算法，具体步骤如下：

• 到主键 id 索引树上查找到对应的整行数据后，取 city、username、age 三个字段的值，存入 sort_buffer 中，能存多少是多少，当 sort_buffer 快要满时，就对 sort_buffer 中的数据进行排序，排完后，把数据临时放到磁盘的一个小文件中，然后清空 sort_buffer(这样的话，一个很大的数据，就会被分成若干个临时磁盘文件)
• 继续回到主键 id 索引树取数据，重复上一步，直到取出所有满足条件的数据
• 最后，归并已经有序的若干个临时磁盘文件，形成一个完整的有序大文件

7)按照排序结果取前 1000 行返回给客户端

可以看出，整个排序过程，我们要查询的 city、username、age 全都参与了，所以，暂且把这个排序过程，称为全字段排序

整条语句的执行流程的示意图如下所示：

针对上面利用磁盘临时文件进行辅助排序的过程，不知道大家会不会有个很自然的想法：sort_buffer 内存放不下，需要用到临时磁盘文件，磁盘文件越多，排序效率显然就会越低下。那为什么还要把排序不相关的字段 city、username 放到 sort_buffer 中呢?只存放排序相关的 age 字段，这样划分的磁盘文件不就相对变少了嘛~

这就是 rowid 排序