临时表和文件排序实现 Group By

2022-04-26 11:00 浏览：474

本文是 group by 实现过程分析的第 2 篇文章，第 1 篇是 MySQL 怎么用索引实现 group by? <- 点击阅读

了解 MySQL 内部临时表中包含什么字段?为哪些字段建立索引?有助于理解使用临时表和文件排序实现 group by，所以之前写了一篇关于内部临时表的文章你好奇过 MySQL 内部临时表存了什么吗? <- 点击阅读

本文内容基于 MySQL 5.7.35 源码。
1、概述
查看 group by 语句的执行计划，在输出结果的 Extra 列中，跟 group by 实现方式有关的信息有 4 种：
① Using index for group-by，表示使用松散索引扫描减少了需要扫描的记录数量，节省了执行时间。
② Using index for group-by(scanning) ，在松散索引扫描流程中使用顺序扫描逻辑，避免了使用临时表对记录去重，这种方式是顺序松散索引扫描(这名字不是来自于官方，是我根据这种实现方式的特点取的名字)。
③ Using temporary; Using filesort，表示使用临时表 + 文件排序，先使用临时表存储分组数据，再对临时表中记录进行排序。
④ Using filesort，表示只使用文件排序，先对 from 子句的表中记录进行排序，再对排好序的记录进行聚合操作。
还有一种实现方式是紧凑索引扫描，在输出结果的 Extra 列中找不到它的蛛丝马迹。
如果 Extra 列中没有出现上面 4 种信息，并且 key 列的值不为 NULL，表示实现 group by 时也用到了索引，这种实现方式就是紧凑索引扫描。
松散索引扫描、顺序松散索引扫描、紧凑索引扫描 3 种实现方式，在这篇文章中都已经有过介绍了：MySQL 怎么用索引实现 group by? <- 点击阅读
接下来，我们一起来看看 ③ ④ 两种方式(临时表 + 文件排序、文件排序)是怎么实现 group by 的。
2、准备工作
本文示例 SQL 使用的表结构如下：
CREATE TABLE `t_group_by` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `e1` enum('北京','上海','广州','深圳','天津','杭州','成都','重庆','苏州','南京','哈尔滨','沈阳','长春','厦门','福州','南昌','泉州','德清','长沙','武汉') DEFAULT '北京',
  `i1` int(10) unsigned DEFAULT '0',
  `c1` char(11) DEFAULT '',
  `d1` decimal(10,2) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_e1` (`e1`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
3、临时表 + 文件排序
在研究使用临时表实现 group by 之前，我一直有个疑问：使用了临时表，为什么还要再进行文件排序呢?
之所以有这样的想法，是因为我知道临时表中会为 group by 字段建立索引，既然建立了索引，那么临时表中的记录就已经是排好序的了。
问题出现在我想当然的认为 group by 上建立的索引是 B-TREE 索引，而完全忽略了另一种索引，就是 HASH 索引。
HASH 索引中的记录并不是排好序的，而包含 group by 的查询语句，隐含了对查询结果按照 group by 字段排序的逻辑，所以还需要使用文件排序。
临时表中为 group by 字段建立索引的目的，是为了更快的找到要更新的记录，而不是为了让记录有序。
因为包含 group by 的查询语句中，一般都会有聚合函数，并且临时表中保存的是聚合函数的计算结果，每从 from 子句的表中读取一条记录，进行聚合函数计算之后，都会用 group by 字段作为条件，把聚合函数计算结果更新到临时表中。
既然建立索引的目的是用于查找，HASH 索引的查找速度显然要比 B-TREE 索引快，使用 HASH 索引也就成为了这种场景下最合适的选择。
使用临时表 + 文件排序实现 group by，临时表和文件排序的用途总结如下：
临时表，保存 group by 分组的结果记录。
文件排序，所有分组的结果记录都写入临时表之后，把临时表中的记录按照 group by 字段值排序。
接下来，我们用一个具体例子来分析使用临时表 + 文件排序实现 group by 的过程，示例 SQL 如下：
select
    e1, count(i1) as sum_i1
from t_group_by
where d1 > 5452415
group by e1
示例 SQL 执行过程中和 group by 相关的关键步骤如下：
词法分析 & 语法分析阶段，count(i1) as sum_i1 解析为 Item_sum_count 类的实例，其中 2 个实例属性如下：
args，count() 函数可以对多个字段联合计数，args[0] ~ args[N] 保存着 count() 函数参数的字段引用。
示例 SQL 中，args[0] 保存着对 i1 字段的 Item_field 类实例的引用，此时，Item_field 类实例还没有关联到i1 字段的 Field 类实例。
count，保存分组计数。e1 字段每一个不同的值就是一个分组，count 是分组中 i1 字段值不为 NULL 的记录数量。
Item_field 未关联 Field
查询准备阶段
第 1 步，i1 字段的 Item_field 类实例关联 t_group_by 表中 i1 字段的 Field 类实例。
Item_field 已关联 Field
第 2 步，创建临时表。
临时表包含 e1、sum_i1 字段，sum_i1 字段值是分组计数，也就是 Item_sum_count 类实例的 count 属性的值。
临时表中还会为 e1 字段建立唯一索引，索引方式(HASH 或 B-TREE)是临时表存储引擎默认的。
对于 MEMORY 存储引擎，索引方式默认为HASH。
对于 MyISAM、InnoDB 存储引擎，索引方式默认为 B-TREE。
执行阶段
临时表 + 文件排序执行过程
第 1 步，读取符合 where 条件的记录。
server 层从存储引擎读取一条记录，并进行 where 条件判断。
如果读取出来的记录不符合 where 条件，继续读取下一条记录。
如果读取出来的记录符合条件，进入第 2 步。
第 2 步，分组计数。
对 i1 字段值不为 NULL 的记录进行分组计数。
如果当前读取记录的 e1 字段值和前一条记录的 e1 字段值不一样，说明要开始新分组。初始化分组计数，Item_sum_count 类的实例属性 count 设置为 1。
如果当前读取记录的 e1 字段值和前一条记录的 e1 字段值一样，说明还是同一个分组。增加分组计数，Item_sum_count 类的实例属性 count 加 1。
第 3 步，更新分组计数到临时表。
以 e1 字段值作为 where 条件，把 Item_sum_count 类的实例属性 count 的值更新到临时表中。
第 1 ~ 3 步是循环执行的过程，直到已经从存储引擎读取到所有符合 where 条件的记录，这个循环执行的过程才会结束。
第 4 步，对临时表中的记录进行排序。
从存储引擎读取符合 where 条件的所有记录之后，把数据发送给客户端之前，需要按照临时表中 e1 字段值对临时表中的记录进行排序。
经过上面的执行过程分析之后，相信大家对于使用临时表 + 文件排序实现 group by 的执行过程能有更清晰的认识了。
4、只使用文件排序
使用临时表 + 文件排序、只使用文件排序，这两种方式中虽然都包含文件排序，但是它们的含义是不一样的。
临时表 + 文件排序，这里的文件排序，表示对临时表中的记录进行排序。
只使用文件排序，这里的文件排序，表示对 from 子句的表中记录进行排序。例如 select e1, count(i1) from t_group_by group by e1 中的 t_group by 表。
为什么对 from 子句的表中记录排序之后，group by 操作就不需要使用临时表了?
要回答这个问题，我们先来看看包含 group by 的查询语句通常要实现的两个逻辑：分组、聚合。
分组，就是把 group by 字段值一样的记录紧挨着放到一起，这样就能知道谁是分组的第一条记录，谁是分组的最后一条记，判断上一个分组结束和新分组开始就非常简单了。
排好序的记录方便判断分组开始和结束
聚合，对分组中的记录进行计数、求和、求平均值等各种操作。
如果能够使用索引(仅指 B-TREE 索引)实现 group by，索引中的记录已经是排好序的了，实际上相当于已经分好组了，可以直接进行聚合操作，而不需要借助临时表进行分组。
说到这里，关于问题的答案已经呼之欲出了。
想必大家都已经想到了，对 from 子句的表中记录按照 group by 字段值排序之后，有点类似于为 group by 字段建立了索引，记录排好序之后也就分好组了，可以直接进行聚合，而不需要再借助临时表进行分组。
对于上面关于分组和聚合的描述，大家可能会有个疑问：想要聚合就一定要先进行分组吗?
这个当然不是，从实现角度来说，不分组也可以聚合。但是，如果聚合之前不先分组，挨着的记录可能属于不同的分组，执行过程中就需要记录多个分组的聚合结果。
分组越多，用于记录分组聚合结果消耗的内存就越多，这显示不是 MySQL 能够接受的。所以，在 MySQL 中，要聚合，就要先分组。
接下来，我们一起来看看只使用文件排序实现 group by 的过程吧。
以一个 SQL 为例来分析执行过程，示例如下：
select
    e1, count(i1) as sum_i1
from t_group_by
where d1 > 5452415
group by e1
词法分析 & 语法分析阶段、查询准备阶段和使用临时表 + 文件排序方式一样，同一篇文章中就不再赘述了。在此，仅对执行阶段进行分析。
只使用文件排序的执行过程
第 1 步，读取 t_group_by 表中所有符合条件的记录并进行排序。
第 2 步，读取一条已经排好序的记录，并判断上一个分组是否结束。
如果当前读取记录的 e1 字段值和前一条记录的 e1 字段值不一样，说明分组已经发生变化，需要结束老分组，开始新分组，进入第 3 步。
如果当前读取记录的 e1 字段值和前一条记录的 e1 字段值一样，说明还是同一个分组，进入第 4 步。
第 3 步，结束老分组，开启新分组。
结束老分组，把 e1 字段值和分组计数发送给客户端。
开启新分组，如果 i1 字段值不为 NULL，把 Item_sum_count 类的实例属性 count 设置为 1，否则设置为 0。
然后回到第 2 步，读取下一条记录。
第 4 步，更新当前分组计数。
如果 i1 字段值不为 NULL，Item_sum_count 类的实例属性 count 加 1，然后进入第 1 步继续执行。
然后回到第 2 步，读取下一条记录。
第 2 ~ 4 步是循环执行的过程，直到读取完符合 where 条件的所有记录、以及把所有分组数据发送给客户端之后结束。
看过使用索引实现 group by 那篇文章的小伙伴应该能发现，上面的执行过程中的第 2 ~ 4 步和紧凑索引扫描方式是一样的。
5、总结
第 3 小节，以一个具体 SQL 为例，分析了 group by 的具体执行过程。
临时表中会写入分组数据，并且会为 group by 字段建立 HASH 索引。因为 HASH 索引中记录不是有序的，所以，写入所有分组数据到临时表之后，需要对临时表中的记录按照 group by 字段进行排序。
第 4 小节，介绍了只使用文件排序实现 group by 的过程。这种方式的执行过程和紧凑索引扫描类似。
不同之处在于，多了一步对 from 子句的表中符合 where 条件的记录进行排序。排好序之后的执行过程就和紧凑索引扫描一样了。
本文转载自微信公众号「一树一溪」，可以通过以下二维码关注。转载本文请联系一树一溪公众号。