高效查询秘诀,解码 YashanDB 优化器分组查询优化手段
![高效查询秘诀,解码YashanDB优化器分组查询优化手段](https://static001.geekbang.org/infoq/d6/d647b85f0eccd4e190239b9e3a4eabc1.png)
背景
分组查询是数据库中使用场景非常广泛的一个操作,作用是对查询出来的数据按照某些列进行分组与汇聚,得到汇聚或者运算后的结果,其性能对于数据库查询而言,也是非常重要的一环。本文将介绍一下数据库基本的分组操作与一些优化手段。
产生分组操作的场景
通常以下四种场景可能产生分组操作:
01 直接使用 Group by 关键字
比如下面的例子,统计每个部门入职时间大于三年的员工数,首先选择出入职时间大于三年的所有员工数,然后按照部门进行分组操作,就能得到想要的结果。
02 其他关键字(Distinct)或者隐式分组操作
比如:
统计所有的员工数,可以认为,这是所有的数据都在一个分组的分组操作。
统计员工的部门,相同的部门只出现一次,这个可以认为是只有分组没有汇聚计算的分组操作。
其等价于下列语句:
注:一些数据库的 distinct 和 group by 内部是统过一个算子来实现的,一些数据库是通过不同的算子实现的,所以,在平时的测试中,有的数据库这两种等价改写的效率是一致的,有的数据库这两种等价改写的效率是不同的。
03 适用于分析系统的高级分组操作
比如:rollup,cube,grouping sets,本文主要聚焦在简单 group 上,对该部分本文不做详细分析。
04 优化器自动添加的分组操作
有时候,语句中是没有明显的 group by 操作的,但是查看执行计划的时候,却发现了分组操作,这是 YashanDB 优化器在某些场景下,自动添加分组操作实现了一个等价操作,通常是 Distinct 这种没有汇聚的分组。
比如:TPCC 中的一个语句:
生成的执行计划如下:
计划中有一个 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 冲突产生。
![](https://static001.geekbang.org/infoq/2f/2fe46b306b59a0cb1af216ac0ff3e355.webp?x-oss-process=image%2Fresize%2Cp_80%2Fformat%2Cpng)
情况 2:我们假设 Hash 桶有 5 个,数据存放情况如下:5 个桶都被使用到,而且每个桶内只有一个不同值,这时候,Hash 比较的效率是最高的。
![](https://static001.geekbang.org/infoq/54/548c0f32b69fab064b21eea6290946ec.webp?x-oss-process=image%2Fresize%2Cp_80%2Fformat%2Cpng)
情况 3:我们假设 Hash 桶有 6 个,数据存放情况如下:只有 3 个桶被使用到,1 号桶中存放了 2 条记录,3 号桶中存放了 2 条记录,5 号桶中放了 1 条记录。
![](https://static001.geekbang.org/infoq/72/7284f77ab4e9faa6642d9450ff878c9c.webp?x-oss-process=image%2Fresize%2Cp_80%2Fformat%2Cpng)
虽然分配了 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 时,需要启动非常多的除重操作。
针对这样的场景,数据库会实现一个额外的算法来减少除重个数,通过补空加一个排序,代替分组以及每个分组内的除重操作。具体看如下例子:
该语句首先根据 c1 分组,然后每个分组内对 c2 分别进行除重,直接按照 c1 和 c2 进行分组/排序。因为是按照 c1 和 c2 排序的,c1 内相同的 c2 是放在一起的,所以一次排序就可以实现 group 和 distinct 的计算。
也可以通过如下两次 Group 来等价实现:
由上面的例子,我们可以看出,当只有一个 distinct 时,distinct 的列可以直接追加在 group 列的后面,通过一次排序或者分组,数据的顺序就可以同时满足分组和除重操作。
当有多个 distinct 时,是否也可以通过一次排序来实现呢?我们看一下下面的例子:
该例子同时存在一个 group 和两个 distinct 操作。该操作 c2 的 distinct 操作和 c3 的 distinct 操作是完全无关,分别计算的,我们可以在计算 c2 的时候,对 c3 列完全补空值,计算 c3 的时候,对 c2 列完全补空值,因为空值不影响汇聚计算结果。
这样,我们通过将数据翻一倍,c1 列保持原值,c2 列保持原值的时候,c3 列补空,c3 列保持原值的时候,c2 列补空,然后通过对 c1,c2,c3 排序,数据上可以同时满足 c1 的分组和 c2,c3 的 distinct 计算。
数据实现如下:
表中原始数据,2 条
![](https://static001.geekbang.org/infoq/98/98cbf9e868c471825d5e16634226e25f.webp?x-oss-process=image%2Fresize%2Cp_80%2Fformat%2Cpng)
扩展后数据,2 条*2(distinct 的个数)
![](https://static001.geekbang.org/infoq/2f/2fefe1284c6717f277227166861e2291.webp?x-oss-process=image%2Fresize%2Cp_80%2Fformat%2Cpng)
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:
每个数据节点上的数据,先按照分组键子集进行数据重分发,分发的数据满足不同节点上的数据是属于不同分组的,然后每个节点内进行分组操作即可。
![](https://static001.geekbang.org/infoq/33/330db120f0451fcbf91ebf1e550ce09c.webp?x-oss-process=image%2Fresize%2Cp_80%2Fformat%2Cpng)
注: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”公众号,持续关注本系列文章!
评论