解锁 YashanDB 高效查询的关键功能 Group by 分组

作者介绍

黄靖东

YashanDB 资深研发工程师

01 前言

在数据库领域，高效的数据处理能力是开发者的必备技能。Group by 分组操作的运用关系到 SQL 查询性能的优劣。面向不同的业务场景，会有不同的分组优化策略，本文旨在深度剖析各类复杂业务场景下，如何选择高效的 Group by 分组策略，帮助突破数据处理瓶颈，实现分组效率的快速提升。

02 分组的概念

Group by 子句是对一个表达式或者多个表达式进行分组，并对分组数据进行聚集运算。Having 子句是对分组之后的结果进行过滤。

常见的分组分类方式有两种，一种是按照功能分类，另一种是按照算法分类。

按照功能分类

1、只有聚集

select sum(a), sum(b) from test_table

执行上述语句时，所有的数据都视作一个整体，形成单一分组，这是分组的一个特例。

2、只有分组

select a, b from test_table group by a, b

依据指定的 a，b 字段，拆分后的每个小组内的数据在这两个字段上具有相同的值。

3、分组和聚集

select a, sum(b) from test_table group by a

先按照 a 字段对数据分组，然后针对每组内的 b 值进行求和聚合。

4、多分组聚集

1) Groupin Set

select  a, b, sum(c) from test_table group by GROUPING SETS((a), (a, b), ())

执行上述语句，可以将多个 Group by 结果汇总到一起，相当于执行：

group by a, group by a, b , group by ()

2）Rollup

select  a, b, sum(c) from test_table group by rollup(a, b)

执行上述语句，将按照特定的层级顺序对数据进行聚合，相当于依次执行：

group by ()， group by a,  group by a, b

3）Cube

select  a, b, sum(c) from test_table group by cube(a, b)

执行上述语句，将会全面展开数据分组聚合可能性，相当于执行：

group by a, b, group by a,  group by b,  group by ()

按照算法分类

1、Hash 分组

是指利用哈希函数为数据生成对应的哈希值，根据哈希值先找到 Hash 桶，然后遍历哈希桶的分组找到匹配的分组。在执行过程中，通过构建 Hash Set 结构来管理分组信息。

2、排序分组

本文仅指根据数据的有序性进行分组。

03 分组优化方式和适用场景

Hash 分组

Hash 分组执行时依赖 Hash Set 结构，分组的过程就是在 Hash Set 中查找分组上下文，当找不到分组上下文时，就可以插入新的分组上下文。分组上下文中存放着分组的所有聚集运算。Hash Set 会根据分组 key 的 hash 值，分为多个桶，Hash 冲突会增加桶内元素数量，因此 Hash 分组算法需要考虑 hash 冲突尽可能小。解决冲突对于分组的性能有很大的好处。

影响 Hash 冲突的主要因素有：

•Hash 算法：选择 Fnv，Crc 等低冲突的算法可以保证冲突不会很大。

•Hash 桶大小：桶大小也跟冲突有关，当桶越大，冲突的概率就越低。

**适用场景：**当分组数量比较小时，Hash 分组性能会比较好。

排序分组

排序分组是利用数据的有序性来进行分组。按照场景有下面几种算法：

1、基于排序的分组

先进行数据排序，扫描有序数据进行分组。排序分组不需要所有的分组结束才有输出结果；且对比 Hash 分组，其所需要的内存资源要少些。

比如数据：1,3,2,3,1 经过排序后得到 1,1,2,3,3

对这些有序数据，扫描到 1 后作为第一个分组，到第二个 1，其已经存在对应的分组；扫描到 2 时，此时和 1 不是同一分组，此时可以结束分组 1 的计算，2 作为一个新的分组；扫描到 3 时，此时 3 和 2 不是同一分组，结束分组 2 的计算，3 作为新的分组；扫描到下面的 3 时，此时所有数据都结束，3 分组也可以结束分组计算了。

**适用场景：**常用在数据的分组数比较多且内存资源非常紧张的场景。

2、基于索引的分组

借助已有的索引结构，直接按照索引顺序读取数据进行分组。这种分组跟基于排序分组的区别在于不需要增加额外的排序算子对数据进行排序。但是要求分组 key 是排序 key 的前缀子集。

**适用场景：**当分组 key 上已经建立了索引。

3、排序分组

是指在排序过程中，当分组的基数非常少时（通常为个位数），可以在排序过程中采用插入排序来进行分组。相比 hash 分组，其少了 hash 计算的开销，并且有效利用了数据的有序性，可以快速找到对应的分组。

**适用场景：**分组数只有个位数的场景，以最小的计算成本实现准确分组。

4、TopN 分组

在对数据排序的过同时，仅保留 N 个需要的分组。

比如对数据（1,3,2,3）做 Top2 分组，数据按照升序排序，Top2 就是取最小的 2 个分组。

扫描到 1 时，其成为一个分组；3 进来后，也作为一个新的分组 3，插入到 1 之后；2 进入后，其比 3 小，得到新分组 2；此时有三个分组了，只需要保留前两个分组 1，2；再进来 3 之后，比 2 大，不需要建立新的组。最后得到 1，2 两个分组。

**适用场景：**分组之后需要对分组 Key 进行排序，且存在 limit 子句限制输出数量时，TopN 分组能够精准满足需求，快速得到分组数据。例如：

select a, sum(b) from test_table group by a order by a limit 2;

分组列的优化

前面看到分组过程中，对于 Hash 分组会对分组 Key 进行算 Hash，比较等操作，排序分组会根据分组 key 进行排序，会有比较多的比较运算。可以通过算法减少这些分组 key 的计算，达到优化分组的目的。

1、常量优化

例 1：

select a from test_table group by a, 1;

如上述语句，当分组 key 中有常量 1，1 对分组结果没有影响，所以计划改写会把常量 1 去掉，等价于：

select a from test_table group by a

例 2：

select a from test_table where b = 1 group by a, b;

由于有条件 b=1，分组 key 中包含了 b，相当于 b 是常量，不影响分组结果，可以从分组 key 中去掉，等价于：

select a from test_table where b = 1 group by a;

**适用场景：**分组 key 中含有常量或者推导出来有常量的情况。

2、等价关系优化

select b1 from t1, t2 where t1.b1 = t2.b2 group by b1, b2

由于 t1.b1 = t2.b2，对 b1 分组和 b2 分组都是一样的结果，因此可以去掉 b2

select b1 from t1, t2 where t1.b1 = t2.b2 group by b1

**适用场景：**当分组 key 中包含等价类关系时，只保留一个关键元素即可，避免重复计算。

3、主键优化

例 1：如果 a1,b1 是 t1 的主 key

select a1, c1 from t1 group by a1, b1, c1

由于 a1, b1 是主 key，其已经决定了 t1 表的分组，因此 c1 可以去掉。

select a1, c1 from t1 group by a1, b1

例 2：如果存在关联关系使得分组 key 包含等价关系

select a1, b2 from t1, t2 where t1.b1 = t2.b2 group by a1, b2, c1

由于 t1.b1 = t2.b2，因此 group by 等价保护 t1 表的唯一 key，因此 c1 也可以去掉。

select a1, b2 from t1, t2 where t1.b1 = t2.b2 group by a1, b1

**适用场景：**分组 key 中包含表的主 key 的场景。建议合理建立主 key，去除冗余字段，优化分组过程。

4、分组顺序变化

例如 group a, b 和 group by b, a 是一样的结果。当分组和其他的算子组合时，交换分组 key 的顺序可以带来优化。

Select a1, b1 from t1 group by a1, b1 order by b1

先对 a1,b1 进行分组，然后对 b1 进行分组，对于排序分组 a1, b1，其出来的结果是按照 a1, b1 有序的。如果我们交换 b1, a1 的顺序，那么出来的结果就是按照 b1 有序的，那么后面的排序 order by b1 就可以去掉了，省掉了后面的排序操作。

select a1, b1 from t1 group by b1, a1 order by b1

**适用场景：**分组之后需要对分组 key 进行排序的场景。

聚集带 Distinct 的算法

select count(distinct c2) from t1 group by c1

聚集上带 distinct 时，有两种算法：

**方式一：**先按照 C1 分组，在每个组内按照 C2 除重。

**方式二：**先按照 C1,C2 分组（去重），再执行一遍不带 distinct 的分组汇聚，等价如下：

Select count(c2) from (select c1, c2 from t1 group by c1, c2) group by c1;

**适用场景：**Hash 分组和排序分组都支持上面两种算法，但是当分组数比较多，资源紧张时，使用排序分组会更加合适。

分组并行

分组并行是利用多 Cpu core 同时进行分组，其可以大幅降低分组查询的时延。在追求低时延且 CPU 充足的情况下，需要开启并行；而在业务并发比较多且 CPU 或者内存资源紧张时，不建议开启并行。

分组并行的策略有两种：两阶段并行和一阶段并行。

1、两阶段并行

各线程内先做一次分组，后由一个线程基于一阶段的结果再做一次分组汇总结果。

适用场景：

1）聚集函数支持两阶段，例如 Count,Sum,Max/Min。对于 Count 聚集，第二阶段的聚集需要变成 Sum 聚集；

2）分组数比记录数少。两阶段分组的主要目的是通过一阶段就可以把总数据量压低，让第二阶段的计算量足够小。如果分组后记录数还是比较大，用两阶段的效果就会比较差。

2、一阶段并行

数据经过分发(按照 Group key 或者其子集)之后，再做分组。

当分区 key 是分组 key 的子集时，就可以不需要做数据分发了。

**适用场景：**一阶段并行是比较通用的并行策略，两阶段不适合的场景，其都可以适用。当分组数量和输入差不多的情况下，必须选择一阶段并行，才能达到性能最优。当分区 key 是分组 key 的子集，没有数据分发，性能更加优，建议合理规划表的分区 key。

聚集函数的优化

聚集运算在分组聚集中，开销占比是比较大的。聚集运算的数据类型对性能的影响比较大的，特别是 SUM 运算，int 类型和 float 类型都比较快。使用 Number 类型时有下面的建议：

•指定 p（precision）和 s（scale），避免精度过大和 scale 不对齐需要额外的计算开销。

•p 值定义在满足业务要求的情况下尽量小，减少不必要的存储开销和计算成本。

•避免用字符串类型代替 number 类型。字符串转成 number 类型时，其 P 是最大精度 38，而 Scale 是浮动值，插入数据时没有做归一化，应避免数据类型混用情况。

例如

create table test(a number(6, 2))

插入值：2.34，3.4，4.78

由于 number 类型指定了 p 和 s，插入存储后会规整成 scale 都为 2 的 number 值: 2.34，3.40，4.78

select  sum(a) from test;

进行 sum 计算时：由于 scale 都是相同的，进行 sum 运算之后，其 scale 还是 2，可以把 number 当成整数 234，340，478 进行运算，其结果是 scale 为 2 的 number 值。

这种 scale 为固定值的 number 类型，在计算引擎内存会变成内部的数据类型进行计算。数据库用户感知不到内部类型的存在。

**适用场景：**当 number 的 p 值和 s 值可以指定的情况下，最好执行 p 和 s，并且 p 值在满足业务精度要求的情况下，尽可能小。

向量化提升分组性能

在 YashanDB 的向量化执行引擎中，向量化会对分组做下面的优化。

1、减少函数调用

所有的计算都按照批量数据的方式计算，会明显减少函数的调用，例如在 Hash Group 中计算 Hash 值时，一次性处理多个数据，极大提升计算效率。

2、按照列计算表达式，减少 cache miss

访问数据都是采用按列读取的方式，会明显减少 cache miss。

3、利用批量数据的信息加速计算

以计算 Count 值为例：

select count(col1) from test_table;

count(col1)是要取列 col1 值不为 NULL 的总记录行数，由于向量化执行器引擎里面，每列数据有专门的 Bitmap 表示数据是否为 NULL，因此只需要取这个列的 Not Null Bitmap 就可以快速计算其非 NULL 的 count 值。

**适用场景：**在分组数据比较多的场景，用向量化执行引擎可以通过高效批量处理，显著提升分组效率，加速数据处理进程。

分组下推

在分组操作和 join 操作同时出现的场景下，将分组下推到 join 之下，可以利用分组减少 join 操作的数据记录数（当分组数和记录数几乎一样时，根据 Cost 会选择不出来分组下推的计划），可以减少 Hash join 的开销。

select t1.a1, sum(t1.b1)  from t1 join t2 on t1.a1 = t2.a2 group by t1.a1;

等价

select t1.aa1, sum(t1.sumb1) from (select a1 aa1, sum(b1) sumb1 from t1 group by a1) t1 join t2 on t1.aa1 = t2.a2 group by t1.aa1;

上面语句的执行计划如下：

从计划中可以看到分组下推到了 Hash join 之下。

**适用场景：**一是适用于分组之后结果比原始表记录数大幅减少的场景；二是常用于分组或者聚集函数不能含有 NULL 值敏感的函数（例如 NVL）时。

05

结语

总之，不同的分组策略各自有着独特的适用场景，在实际的数据库操作中，我们需要依据数据规模、业务需求、系统资源等多方面因素综合考量。精准选择并灵活运用这些分组策略，才能让我们在面对海量数据处理时游刃有余。本次只是介绍了一些常用的优化算法，后面我们还会分享更多的优化算法，并且针对一些优化算法再深入呈现，敬请关注。