引子

现在有个市民信息表，给出的建表语句如下：

1
2
3
4
5
6
7
8
9
CREATE TABLE `t` (
           `id` int(11) NOT NULL,
           `city` varchar(16) NOT NULL,
           `name` varchar(16) NOT NULL,
           `age` int(11) NOT NULL,
           `addr` varchar(128) DEFAULT NULL,
           PRIMARY KEY (`id`),
           KEY `city` (`city`)
         ) ENGINE=InnoDB;

如果要从表中找出杭州所有人的名字，并按照姓名排序返回前 1000 个的姓名和年龄。

SQL 语句如下：

1
select city,name,age from t where city='杭州' order by name limit 1000  ;

语句看起来清晰简洁，一个 order by 再加一个 limit 就搞定了。

但是这条语句背后的执行原理是什么呢？

执行原理

全盘扫描进行排序比较耗时，从前面讲索引的部分我们可以知道，一个优化的方法是给字段加索引。

在这张表里，我们给哪个字段加索引呢？

观察 where 后面的 condition，因为 condition 是以 city 为条件进行过滤的，所以需要加索引的字段自然是 city。

从前面的文章我们也可以知道如何去查看一条语句的执行情况：使用 explain 命令。

执行情况如下图所示。

执行情况

city 字段加索引的示意图如下所示。

city字段加索引

全字段排序

全字段排序的执行过程如下：

  1. 初始化 sort buffer，放入 name、city 和 age 三个字段；
  2. 从 city 索引中找到第一个满足 city = ‘杭州’条件的主键 id，也就是上图中的 ID_X；
  3. 根据步骤 2 中获取到的主键 id，从主键索引上取出整行，再从该行中拿出来 city、name 和 age 三个字段的值放入步骤 1 的 sort buffer 中；
  4. 迭代，重复步骤 2、3，直到 city 不满足查询条件为止。
  5. 对 sort buffer 中的数据按照字段 name 进行排序
  6. 截取排序后的前 1000 行，返回到客户端。

其示意图如下：

全字段排序

以上过程步骤 1 到步骤 6的描述中，可能最泛泛而过的应该就是步骤 5 中的“进行排序”四个字了。

那么这个排序是如何进行的呢？

排序方式有二：内存排序和内存外排序。

使用哪种呢？

看情况而定，简单来说，sort buffer 够用，就使用内存排序；sort buffer 不够用，则使用磁盘临时文件辅助排序。

sort buffer 的大小是可以设定的么？

通过设置 sort_buffer_size 这个参数的值可以调整 sort buffer 的大小。

内存排序的方式是采用快速排序的方式进行，外部排序实际情况中是如何操作的呢？

使用的是：归并算法。

分而治之，sort buffer 一下装不下这么多数据，那就分成多份可以装进 sort buffer 中的数据，对于每一份数据在内存中排序后写入临时文件中，然后把这些临时文件合并成为一个有序的大文件。

row id 排序

全字段排序的方法麻烦的地方不在于如何将数据分成多份，而在于如何将多份已经排序后的临时文件合并成为一个大有序文件。

临时文件越多，合并起来也会越复杂。

所以全字段排序的缺点在于：临时文件数量不能太多。

什么时候临时文件数量多呢？

sort buffer “太小”的时候。

想象一下，如果装入 sort buffer 中的每一行数据中字段数越多，则每行占用的空间就越大，自然 sort buffer 可容纳的行数就越少了，于是不得不用更多的临时文件，临时文件越多排序性能越差。

那么针对这种行所占空间大的情况下，如何改进呢？

对症下药。

原来不是行的空间大么，我现在只放两个字段：name（需要根据这个进行排序）和 主键 id。

这已经是精简到极致了。

排序的执行过程如下：

  1. 初始化 sort buffer，确定放入两个字段：name 和 id；
  2. 从 city 索引中找到第一个满足 city=’杭州‘的叶子节点，从中找出主键id，也就是图中的 ID_X
  3. 根据 ID_X 从主键索引中取出整行数据，取出来 name 和 id 两个字段，放入 sort buffer 中
  4. 重复进行步骤 2、3 直到没有满足 city=’杭州‘的叶子节点存在
  5. 对 sort buffer 中的数据按照字段 name 进行排序
  6. 遍历排序结果的前 1000 行数据，并按照主键 id 值回到原表中取出 city、name 和 age三个字段加入结果集返回给客户端

执行示意图如下所示：

row id 排序

对比全字段排序方法，此排序方法多进行一次回原表中取字段的过程。

全字段排序 vs row id 排序

不同的排序方法有不同的适用场景，哪一种方法更优，完全取决于当时的应用场景。

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

  1. 在 sort buffer 相对于排序数据太小的场景下，使用全字段排序会产生较多的临时文件，影响排序效率，这个时候会选择 row id 的排序算法，但是这种方法需要回原表取数据。
  2. 在 sort buffer 足够使用的情况下，MySQL 会优先选择全字段排序，全字段排序较 row id 排序算法磁盘读写次数更少。

不用排序

最好的竞争方式就是避免竞争，最好的排序方法就是不排序。

虽然看起来像废话，但还是不得不说：如果原来的数据就是有序的，那就无须排序。

怎么才能保证原来的数据就是有序的呢？

我们现在已经有了一个 city 索引，已经保证了 city 字段是有序的，如果还要保证 name 是有序的，自然是为 name 也建立索引咯。

本文中的场景是二者兼而有之，那么自然想到建立一个联合索引：city 和 name。

使用以下命令建立联合索引：

alter table t add index city_user(city, name);

我们可以回顾联合索引的作用：天然按照 city 和 name 字段进行排序，首先保证 city 有序，然后如果 city 有序则在 city 下面取到的 name 也必然是有序的。

采用联合索引后的查询流程变成了：

  1. 从联合索引（city，name）找到第一个满足 city=’杭州‘ 条件的主键 id；
  2. 根据这个主键 id 回到主键索引树上取出该行整行的记录，然后得到 name、city 和 age 三个字段的值，作为结果的一部分返回
  3. 从（city，name）中取到下一个记录主键 id
  4. 重复步骤 2、3，直到没有 city=’杭州‘ 这个条件不满足

使用 explain 命令进行验证：

联合索引的explain

分析图中结果：

  1. Extra 一栏没有了 Using filesort，说明不需要使用排序了
  2. city 和 name 的联合索引会保证有序，所以此查询也不用扫描 4000 行，只要找到满足条件的前 1000 行即可。

（全文完）

参考资料

  1. 丁奇《MySQL 45讲》