背景

分组查询是数据库中使用场景非常广泛的一个操作，作用是对查询出来的数据按照某些列进行分组与汇聚，得到汇聚或者运算后的结果，其性能对于数据库查询而言，也是非常重要的一环。本文将介绍一下数据库基本的分组操作与一些优化手段。

产生分组操作的场景

通常以下四种场景可能产生分组操作：

01 直接使用 Group by 关键字

比如下面的例子，统计每个部门入职时间大于三年的员工数，首先选择出入职时间大于三年的所有员工数，然后按照部门进行分组操作，就能得到想要的结果。

SELECT dept, count(*)FROM employeesWHERE  enroll_date > sysdate – 3 yearsGROUP BY dept

02 其他关键字(Distinct)或者隐式分组操作

比如：

select count(*) from employees;

统计所有的员工数，可以认为，这是所有的数据都在一个分组的分组操作。

select distinct dept from employees;

统计员工的部门，相同的部门只出现一次，这个可以认为是只有分组没有汇聚计算的分组操作。

其等价于下列语句：

select dept from employees group by dept;

注：一些数据库的 distinct 和 group by 内部是统过一个算子来实现的，一些数据库是通过不同的算子实现的，所以，在平时的测试中，有的数据库这两种等价改写的效率是一致的，有的数据库这两种等价改写的效率是不同的。

03 适用于分析系统的高级分组操作

比如：rollup，cube，grouping sets，本文主要聚焦在简单 group 上，对该部分本文不做详细分析。

04 优化器自动添加的分组操作

有时候，语句中是没有明显的 group by 操作的，但是查看执行计划的时候，却发现了分组操作，这是 YashanDB 优化器在某些场景下，自动添加分组操作实现了一个等价操作，通常是 Distinct 这种没有汇聚的分组。

比如：TPCC 中的一个语句：

SELECT count(*) AS low_stock FROM ( SELECT s_w_id, s_i_id, s_quantity  FROM bmsql_stock  WHERE s_w_id = ? AND s_quantity < ? AND s_i_id IN (   SELECT ol_i_id   FROM bmsql_district        JOIN bmsql_order_line ON ol_w_id = d_w_id    AND ol_d_id = d_id    AND ol_o_id >= d_next_o_id - 20    AND ol_o_id < d_next_o_id   WHERE d_w_id = ? AND d_id = ?  ));  

生成的执行计划如下：

+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+| Id | Operation type                 | Name                 | Owner      | Rows     | Cost(%CPU)  | Partition info|+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+|  0 | SELECT STATEMENT               |                      |            |          |             | ||  1 |  AGGREGATE                     |                      |            |         1|        2( 0)| ||  2 |   NESTED INDEX LOOPS INNER     |                      |            |         1|        2( 0)| ||  3 |    SORT DISTINCT               |                      |            |         3|        1( 0)| ||  4 |     VIEW                       |                      |            |         3|        1( 0)| ||  5 |      NESTED INDEX LOOPS INNER  |                      |            |         3|        1( 0)| ||* 6 |       TABLE ACCESS BY INDEX ROWID| BMSQL_DISTRICT       | REGRESS    |         1|        1( 0)| ||* 7 |        INDEX UNIQUE SCAN       | BMSQL_DISTRICT_PKEY  | REGRESS    |         1|        1( 0)| ||  8 |       TABLE ACCESS BY INDEX ROWID| BMSQL_ORDER_LINE     | REGRESS    |         1|        1( 0)| ||* 9 |        INDEX RANGE SCAN        | BMSQL_ORDER_LINE_PKEY| REGRESS    |         3|        1( 0)| ||*10 |    TABLE ACCESS BY INDEX ROWID | BMSQL_STOCK          | REGRESS    |         1|        1( 0)| ||*11 |     INDEX UNIQUE SCAN          | BMSQL_STOCK_IDX1     | REGRESS    |         1|        1( 0)| |+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+

计划中有一个 SORT DISTINCT，YashanDB 优化器将 in 子查询改写为 join 后，认为先对 semi 部分去重，再和左边的表进行 nested loop join 性能比较好，自动添加了个 Distinct 操作来实现去重（没有汇聚的分组）。

当然，对于该计划，有些数据库是通过 Right Semi 操作来实现的。这是一个简单的例子，在很多场景下，都可能发现数据库优化器自动添加了 Distinct/Unique 操作，来优化查询路径。

分组操作的常见算法

分组常用的分组算法有：Hash 分组、排序分组、TOPN 分组、基于多列 Distinct 的特殊分组等，下面将展开介绍每一种算法。

01 Hash 分组

Hash 分组的实现包含以下几个步骤：首先，对分组列先计算其 Hash 值；其次，根据一定的算法（比如，直接取模）将 Hash 值映射到 Hash 桶上，这样 Hash 值相同的值落在一个 Hash 桶内；最后，对每个桶内数据做分组操作，也就实现了全局分组的操作。

影响 Hash 分组性能和 Hash 表效率的关键因素主要有几个：

• Hash 冲突的多少。冲突越高，性能越低。因为在一个桶内，如果使用链表，则是遍历扫描的；如果使用开放地址法，不同 Hash 值之间的地址占用也会增加 Hash 查找的次数。那如何来规避冲突的可能性呢？关键通过控制 Hash 表的大小，如果 Hash 表的大小小于不同分组值的个数，则 Hash 冲突是一定产生的，所以 Hash 表的大小需要尽可能的大于数据不同值的个数，另外，Hash 桶的个数一般采用素数，来减少 Hash 冲突的可能性。

• Hash 表动态增长导致的数据拷贝操作。解决办法主要是尽可能一次性分配足够的 Hash 表内存，这就要求需要对 Hash 表大小尽可能估计准确，数据库一般通过统计信息计算来估算经过分组之后的条数有多少，为分配 Hash 表提供依据。

下面看一个简单的例子：

假设表中数据为：1，3，5，7，9。Hash 算法采用取原值，则数据的 Hash 也为 1，3，5，7，9。Hash 值到 Hash 桶的映射采用取模。

我们来分析下不同 Hash 桶下的影响：

情况 1：我们假设 Hash 桶有 3 个，数据存放情况如下：3 个桶都被使用到，0 号桶和 1 号桶中各存放 2 条记录，2 号桶中存放了一条记录，有 Hash 冲突产生。

情况 2：我们假设 Hash 桶有 5 个，数据存放情况如下：5 个桶都被使用到，而且每个桶内只有一个不同值，这时候，Hash 比较的效率是最高的。

情况 3：我们假设 Hash 桶有 6 个，数据存放情况如下：只有 3 个桶被使用到，1 号桶中存放了 2 条记录，3 号桶中存放了 2 条记录，5 号桶中放了 1 条记录。

虽然分配了 6 个桶，但是只有 3 个桶有数据，效果还不及 5 个桶的时候。所以在使用上，需要 Hash 表尽可能的既保证大小足够存放不同值，又保证值尽可能的离散分布在 Hash 桶上。

02 基于排序数据的分组

基于有序数据进行分组

如果分组之前，数据已经按照分组列排序了，那么分组的实现就比较简单了，每一行判断和上一行是在同一个分组内，只需要扫描一遍，整个分组就完成了。

所以，优化器对于分组操作，会有一条尝试下层增加排序的路径，这条路径上，保证了到分组操作之前，数据已经是按照分组列排序好了。满足排序的方式主要有几种：

方式 1：

通过添加排序算子实现：下层为保证数据有序，可以显示的添加一个 Sort 算子，用以保证查询的结果是按照分组键来排序的。

方式 2：

经过产生隐式数据排序的算子后，数据可能本身就已经有序，可以避免额外排序的产生。这些算子可能包括索引扫描、Merge sorted join 等。当索引列或者 Join 条件产生的排序可以满足分组列时，可以直接使用基于排序数据的分组。

注：该情况仅限于有序的索引，主要是 B+树索引。R-Tree 索引和反向索引等都无法保证输出数据是有序的，另外，Index Fast Full Scan 是基于索引数据的存储直接访问的，返回的数据不具备有序性。

基于无序数据进行分组

如果数据无序，也可以在分组的过程中，一边排序一边汇聚，这是分组操作的另一个可能的算子路径，YashanDB 采用 SDT group 来表示这种分组。

SDT 与上述有序数据分组的区别如下：

a. 基于添加排序的分组，有个完整独立的排序操作和分组操作。

1，3，2，3，1 → SORT：1，1，2，3，3 → GROUP：1，2，3

b.SDT 分组：在排序的过程中，如果发现是相同的分组，则直接进行汇聚计算。在行数较多，distinct 值较少的情况下，这种方法可以显著的减少内存的使用。

1，3，2，3，1 → SORT-GROUP：(1，1)，2，(3，3)

在结构上，每个不同的分组值，只保留一个值与前面的汇总结果。

03 TopN 分组

在部分场景下，有些分组操作的语句不需要返回所有分组，只需要返回前几个分组即可。这种场景下，如果 TopN 的列是分组列相关的，分组操作是不需要保留所有分组值的，继而产生 TopN 分组的优化需求。

以下是一个简单的例子：

分组结构上，只保留前 TopN 个不同的分组值，一个新值来后，判断是否属于 TopN，如果属于 TopN，则替换掉分组中的一个存在的最大/最小值。

TOP2: 1，3，2，3，1

1 → 1,3  → 2,3

04 多个 Distinct 的分组

除了分组外，如果汇聚函数中同时出现 distinct 操作，则需要实现每个分组内的数据再进行除重操作。

这种操作对于数据库而言，实现的代价相对来说是比较大的，尤其是分组数特别多，每个分组的数据不太多时；而且出现多个 distinct 时，需要启动非常多的除重操作。

针对这样的场景，数据库会实现一个额外的算法来减少除重个数，通过补空加一个排序，代替分组以及每个分组内的除重操作。具体看如下例子：

select count(distinct c2) from table group by c1

该语句首先根据 c1 分组，然后每个分组内对 c2 分别进行除重，直接按照 c1 和 c2 进行分组/排序。因为是按照 c1 和 c2 排序的，c1 内相同的 c2 是放在一起的，所以一次排序就可以实现 group 和 distinct 的计算。

也可以通过如下两次 Group 来等价实现：

select count(*) from (select c2 from table group by c1, c2) group by c1;

由上面的例子，我们可以看出，当只有一个 distinct 时，distinct 的列可以直接追加在 group 列的后面，通过一次排序或者分组，数据的顺序就可以同时满足分组和除重操作。

当有多个 distinct 时，是否也可以通过一次排序来实现呢？我们看一下下面的例子：

select count(distinct c2), count(distinct c3) from table group by c1;

该例子同时存在一个 group 和两个 distinct 操作。该操作 c2 的 distinct 操作和 c3 的 distinct 操作是完全无关，分别计算的，我们可以在计算 c2 的时候，对 c3 列完全补空值，计算 c3 的时候，对 c2 列完全补空值，因为空值不影响汇聚计算结果。

这样，我们通过将数据翻一倍，c1 列保持原值，c2 列保持原值的时候，c3 列补空，c3 列保持原值的时候，c2 列补空，然后通过对 c1,c2,c3 排序，数据上可以同时满足 c1 的分组和 c2,c3 的 distinct 计算。

数据实现如下：

表中原始数据，2 条

扩展后数据，2 条*2(distinct 的个数)

c1, c2, c3 → c1, NULL , c3 + c1 , c2 , NULL → Sort c1, c2, c3 → 一遍扫描实现。

通过该算法可以极大的减少分组操作的个数，但是整体排序的数据量会变大（原始数据乘以汇聚函数带 Distinct 的个数）。优化器会根据代价，来确定是否选择该算法。

分组操作的优化规则

01 分组列优化

参与分组的列需要进行比较操作，所以在等价的情况下，参与分组的列越少越好。那 YashanDB 优化器是如何尽可能的减少分组列的个数的呢？

优化方式 1：常量优化/等价关系优化

这里的常量指的是运行时判断为常量，主要包括输入的常量、SQL 传入的参数等。以下为几个优化示例：

输入常量:

select *** from t1 group c1, 2 → select *** from t1 group by c1

输入参数:

select *** from t1 group c1, :1 → select *** from t1 group by c1

等价关系:

select *** from t1 where b1 = 2 group by b1, c1 → select *** from t1 where b1 = 2 group by c1

优化器会从全局推导出某个 group by 中的列是否为运行时常量，从而决定是否可以优化掉。

优化方式 2：主键优化/Key constraint 优化

以下是主键优化的几个示例：表 T1 上存在主键(a1, b1) 

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

因为 a1,b1 为主键列（非空的唯一索引列也具备同样功能），通过 a1,b1 可以唯一的表示整行，所以 a1，b2 的分组与所有列的分组等价。

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

通过内在的等价关系，寻找满足主键条件的相关列进行优化。

如果数据已经进行过一次分组，则分组列可以唯一表示分组后的每一行，后续再出现类似的分组操作，也可以使用这些分组列来进行优化，数据库通过 key constraint 来表示这种关系，从而实现后续分组的优化。

优化方式 3：列顺序优化

从逻辑意义上，分组结果与分组列的顺序是无关的，也就是说 group by a1, b1 与 group by b1, a1 是等价的，但是排序是与列的顺序强相关的。

当同时存在排序和分组时，YashanDB 优化器在选择排序分组算法时，会尝试优化分组顺序，从而保证排序可以利用分组的顺序，优化掉一次排序操作。具体示例如下：

Select *** from t1 group by a1, b1 order by b1 → select *** from group by b1, a1 order by b1

分组列为 a1, b1，排序列为 b1，当使用排序分组时，如果按照 a1,b1 排序的，则最后还要按照 b1 再排序一次，如果时按照 b1,a1 排序的，那么按照 b1 排序本身就天然满足了，就不需要额外的排序了。

02 分布式/并行下的分组

分组是对全局数据进行的，在分布式或者基于数据流的并行执行下，是否可以将分组操作并行化，在每个线程内进行呢？什么情况下需要进行这种分组呢？

下面我们来看一下 YashanDB 对于分布式或者并行下分组的实现方式（并行与分布式类似，以下以分布式为例）。

select *** from t1 group by c1

以一个简单的语句在分布式的执行为例，可以有如下图所示的几种执行方式：

方式 1：

把所有数据节点(DN)的数据都发送到协调节点(CN)上来，在 CN 上进行一个全局数据的分组操作。适合数据量较小的操作。

方式 2：

在每个数据节点内先进行一次分组操作，然后将每个数据节点上汇总的数据再发送到协调节点，协调节点再做一次全局分组操作。

方式 3：

分布式下，当分布键是分组键的子集时，数据的分布保证了每个数据节点上的数据都在不同的分组内，则每个数据节点进行分组后，无需全局分组，一次分组就可以实现。可以将分组操作并行的执行，分布式下最理想的分组方式。

方式 4：

每个数据节点上的数据，先按照分组键子集进行数据重分发，分发的数据满足不同节点上的数据是属于不同分组的，然后每个节点内进行分组操作即可。

注：CN 为 SQL 入口协调节点，DN 为分布式的数据节点。

假设有 10 个数据节点，我们以几个不同数据分布场景为例子，介绍下如何选择合适的执行方式：

场景一：

t1: 100 万记录，数据随机均匀分布在 10 个数据节点上。极端场景，分组键 c1 都是重复值 1。这个场景下，每个数据节点有 100 万/10=10 万数据。

方式 1：

所有数据都要分发到协调节点，数据分发 100 万。在协调节点上执行一个 100 万的分组操作。

100 万分发+100 万 CN 上的集中分组操作。

方式 2：

每个数据节点并行的执行 10 万记录的分组操作，汇总完后每个数据节点的数据为 1 条，然后总的 10 条记录发送到协调节点，进行一个 10 条记录的分组。

10 条分发+10 万分组操作+10 条分组操作（CN）。

方式 3：

数据分布不满足。

方式 4：

先将 100 万按照分组键分发，由于分组键的取值都是 1，所以都会分发到一个数据节点上，其他的 DN 都没数据，所以无法并行执行，然后在这个节点上进行一个分组，最后发到 CN。

100 万分发+100 万单 DN 分组+1 条数据分发。

可以看出，在这个场景下，方式 2 是最佳的执行方式。

场景二：

t1: 数据量不变，还是 100 万，但是分组键 c1 数据是唯一的但不是分布键，也没定义为主键。

方式 1：

和场景一的代价相同，100 万分发+100 万 CN 上的集中分组操作。

方式 2：

每个数据节点上执行一次 10 万的分组，因为数据是唯一的，分组后的数据还是 10 万条，所以数据节点上的分组操作是无效分组。然后都发送到 CN，在进行一次分组。

10 万数据节点分组+100 万分发+100 万 CN 节点分组。

方式 3：

数据分布不满足。

方式 4：

先按照分组键进行分发，因为分组键是唯一的，可以均匀的分布到各个数据节点，每个节点做分组操作即可。

100 万数据分发+10 万数据节点分组操作+100 万数据分发。

对比下，方式 4 是相对最佳的执行方式。

场景三：

t1: 数据量不变，按分组键 c1 均匀分布式在数据节点上。

方式 1：

和前面场景的代价相同，100 万分发+100 万 CN 上的集中分组操作。

方式 2：

根据分布键不同值的多少，如果数据只有一个值，则和场景一一样，如果数据是唯一的，则和场景二一样，所以代价在二者之间。

10 条分发+10 万分组操作+10 条分组操作（CN）和 10 万数据节点分组+100 万分发+100 万 CN 节点分组之间。

方式 3：

因为数据本身满足分布，数据节点上的分组就是全局分组。

每个数据节点 10 万分组，分组后数据直接发送给协调节点给客户端即可。发送数据取决于分组后数据大小。最佳执行方式。

方式 4：

先进行 100 万的数据分发，分发后按照在每个数据节点上的数据最大为 100 万行（数据全重复），最小为 10 万行（数据可以完全均匀分布）， 这样分组操作实际上是 10 万到 100 万之间，然后发送到协调节点，相比较方式 3，多了一次 100 万的数据分发。

通过以上几个场景，可以看出，在分布式下，即使是完全相同的数据量，根据分布键和分组键的关系以及分组键不同值的多少，都可能选择不同的执行方式。YashannDB 优化器将根据统计信息，来选择最佳的执行方式，并尽可能的保证统计信息的正确性。当然，网络吞吐、内存大小等，也会影响到优化器选择。

总结

除了以上介绍的基本优化之外，YashanDB 优化器对分组操作还做了一些其他的优化，比如：Group by 下推，Partition wised group 等。对于分析的多维分组，cube、 rollup、 grouping sets 等，数据库依据不同的数据分布和多维分组列关系，也做了不同程度优化，本文暂不做过多阐述。

本文是 Meetup 第十期“调优实战专场”的第一篇技术文章，下一篇《YashanDB Meetup 系列文章》将带来 YashanDB 常用的 SQL 调优思路与手段。欢迎关注“YashanDB”公众号，持续关注本系列文章！