Mysql数据库order by实现原理

业务背景

在应用开发过程中，业务场景可能需要根据某个字段进行排序，并返回指定结果集，就需要用到order by，今天我们来聊聊 order by 的执行流程。

假设你要查询城市是“北京”的所有人的名字，并且按照名字进行排序返回前1000个人的姓名和年龄。建表语句如下：

mysql> create table `user` (
	`id` int(11),
	`name` varchar(16) NOT NULL,
	`age` int(11) NOT NULL,
	`city` varchar(16) NOT NULL,
	PRIMARY KEY(`id`),
	KEY `city` (`city`)
)ENGINE=InnoDB;

SQL语句如下：

mysql> select name, age from user where city = "北京" order by name limit 1000;

全字段排序

为了避免全表扫描，我们需要在city字段上创建索引，用explain命令查看这条语句的执行情况：

mysql> explain select name, age from user where city = "北京" order by name limit 1000;

可以看到 key 为 city，确实走了索引，扫描行数rows为4000，表示city为北京的记录有4000条，Extra字段中的“Using filesort”，表示需要排序，Mysql 会给每个线程分配一段内存用于排序，这段内存称为sort_buffer。

执行流程：

1. 初始化sort_buffer；
2. 从city索引找到第一个满足city=“北京”条件的主键Id，也就是途中的ID-x；
3. 到主键ID-x索引找到这条记录，拿到name、city、age三个字段的值放入sort_buffer；
4. 从city索引找下一条记录，取到主键id；
5. 重复步骤3、4 直到city不满足条件为止，也就是到途中的ID-y为止；
6. 对sort_buffer中的数据按照name做快速排序；
7. 返回排序结果的前1000条记录；

说明：
步骤6中，按照name字段排序的动作，可能在内存中完成，也可能需要使用外部排序，取决于排序数据所需要的内存和参数sort_buffer_size。sort_buffer_size就是Mysql为排序分配的内存。如果排序的数据量小于sort_buffer_size，排序就在内存中完成，否则就需要利用磁盘的临时文件进行辅助排序。

rowid排序

上面讲到的全字段排序，我们在拿到主键id后，取了结果集的所需全部字段（name、city、age）放入sort_buffer，按照name排序完可以直接返回。这个算法有个问题，就是sort_buffer放入的字段太多，导致内存中放入的行数很少，可能分成很多个临时文件，排序的性能会很差。

rowid排序思路：只把要排序的name字段和主键id放入sort_buffer，也就是尽可能多的放入更多的行。但是，因为sort_buffer中少了city和age字段，不能直接返回了，执行流程如下：

1. 初始化sort_buffer，确认放入两个字段（name、id）；
2. 从city索引找到第一个city=“北京”的主键id，也就是图中的ID-x；
3. 根据主键id索引，拿到name、id两个字段放入sort_buffer；
4. 从city索引找下一条记录，取到主键id；
5. 重复步骤3、4 直到city不满足条件为止，也就是到途中的ID-y为止；
6. 对sort_buffer中的数据按照name做快速排序；
7. 遍历排序结果，取前1000行的id，再回到原表中，拿到city、age、name三个字段，返回结果。

全字段排序 和 rowid排序比较

Msyql的设计思想：如果内存够，尽量使用内存，尽量减少磁盘访问。

如果Mysql认为内存太小，就会使用rowid排序，好处是可以放入更多行的数据，缺点需要再回原表查询数据。

思考：order by是否一定需要排序？

答案是：不一定。可以利用覆盖索引，优化order by语句，比如，可以创建city_name_age的联合索引，该联合索引树的叶子结点的值就已经包含了我们需要的结果，这样的话就不需要回表了哦。