Oceanbase查询改写：groupby移动

概述

当查询语句中同时存在连接操作和分组聚合操作时，可能会产生大量的io。为此，Oceanbase中定义了groupby移动规则，能够对满足条件的分组聚合操作进行提升或下推，提升查询性能。

基本原理

groupby移动规则主要包含对以下两种情况的处理：

1. groupby下推：当分组聚合操作位于连接操作之后时，可以将其进行下推，从而通过提前聚合减少连接阶段的数据量。
2. groupby提升：当分组聚合操作位于连接操作之前时，可以将其进行提升，从而通过连接筛选减少分组聚合阶段的数据量。

groupby下推

考虑如下情况：

SELECT sum(t1.c2) FROM t1, t2 WHERE t1.c1 = t2.c1 GROUP BY t1.c3;

对于上述查询，可以将通过改写将group by表达式下推，从而减少连接阶段的数据量，如下所示：

SELECT sum(c2_sum * t2_cnt) FROM
	(SELECT t1.c1, t1.c3, sum(t1.c2) AS c2_sum FROM t1 GROUP BY t1.c1, t1.c3) v1,
	(SELECT t2.c1, count(*) AS t2_cnt FROM t2 GROUP BY t2.c1) v2
WHERE v1.c1 = v2.c1 GROUP BY v1.c3

groupby提升

SELECT t1.c3, c2_sum FROM 
  t1,
	(SELECT t2.c3, sum(t2.c2) AS c2_sum FROM t2 GROUP BY t2.c3) v
WHERE v.c3 = t1.c3

对于上述查询，如果连接操作能够筛选掉较多的数据，则可以通过改写提升group by表达式，从而减少参与聚合的数据量，如下所示：

SELECT t1.c3, sum(t2.c2) AS c2_sum FROM 
  t1,
	t2
WHERE t2.c3 = t1.c3 GROUP BY t2.c3, t1.c1    --c1为t1表的唯一键

代码解析

groupby移动规则的入口为ObTransformGroupByPlacement::transform_one_stmt，执行流程如下：

1. 调用transform_groupby_push_down函数执行groupby下推改写。
2. 调用transform_groupby_pull_up函数执行groupby提升改写。

groupby下推

transform_groupby_push_down函数执行流程如下：

1. 调用check_groupby_push_down_validity函数判断当前语句是否能够被执行下推改写。
2. 调用compute_push_down_param函数收集下推参数。
3. 调用do_groupby_push_down函数执行下推改写。

check_groupby_push_down_validity函数会对查询语句的各项成员进行检查，执行流程如下：

1. 检查查询语句的基本属性是否满足如下条件：
1. 查询语句必须包含聚合函数和group by表达式，且不包含窗口函数、半连接信息和子查询。
2. 查询语句不是集合语句。
2. 调用check_groupby_validity函数检查查询语句的select列、order by表达式及having表达式是否都包含于group by表达式。
3. 调用check_collation_validity函数检查查询语句中数据类型为string或者lob的列对应的collation类型是否一致。
4. 检查聚合函数类型是否都属于min/max/count/sum中的一种，且不含distinct参数。

compute_push_down_param函数负责收集下推参数，判断应该如何将查询语句中涉及的表划分到不同的视图中。该函数首先会为表信息中的每张表分配一个表集合，然后将满足条件的集合进行合并，执行逻辑如下：

1. 遍历查询语句中的聚合项，如果某个聚合函数的参数涉及多张表，则将这些表合并到同一视图中。
2. 遍历查询语句中的where条件，将满足如下条件的表达式涉及的表合并到同一视图中：
1. 该表达式为两表连接条件（涉及两表的关系比较条件）。
2. 左右参数中任意一侧的列表达式涉及的表与聚合项涉及的表存在重叠，且该列能够找到匹配的索引。
3. 遍历查询语句中的join表，将满足如下条件之一的join表涉及的表合并到同一视图中：
1. 与该join表存在交集的集合中已经至少分配了两张表。
2. 查询语句中的聚合项中存在某个聚合函数的参数涉及该join表的内表侧数据表，且该参数关于对应的数据列不满足空值传递（此时无法找到等价的语义进行拆分）。

没有被合并的join表会被记录到单独的集合中供下推阶段使用（下称flattern_joined_tables）。

do_groupby_push_down函数会根据上一步得到的下推参数，进一步分配各视图查询中需要的查询条件，然后执行改写，处理流程如下：

1. 遍历查询语句中的where条件，调用distribute_filter函数将条件表达式分配到对应表集合的下推参数中。如果该条件涉及的表属于某个表集合的子集，且不涉及任何外连接的内表，则将其放入下推参数的过滤条件中，否则抽取其涉及的列放到下推参数的join列中。
2. 遍历flattern_joined_tables中的join表，调用distribute_joined_on_conds函数将连接条件分配到对应表集合的下推参数中。如果该条件为外连接内表侧的单表条件，则将其放入下推参数的过滤条件中，否则抽取其涉及的列放到下推参数的join列中。同时，上述下推到过滤条件中的单表条件会从连接条件中被移除。
3. 调用distribute_group_aggr函数将聚合项和group by表达式分配到对应表集合的下推参数中。该函数首先会将查询语句中的group by表达式和聚合表达式分配到对应的下推参数中，然后为每个下推参数添加count(*)聚合项。如果原查询语句中的count/sum聚合项的数目与当前下推参数中聚合项的数目相同（聚合项完全下推到当前视图）或当前下推参数中的join列满足唯一性（count(*)固定为1），则不需要进行创建。另外，如果满足上述唯一性（提前聚合不会减少中间结果）或join列为空（改写后语义不匹配），则会将放弃对该下推参数进行改写，同时会将上一步下推到过滤条件中的单表条件还原到连接条件中。
4. 调用transform_groupby_push_down函数执行改写，处理流程如下：
1. 遍历下推参数，调用push_down_group_by_into_view函数为各参数创建视图表。
2. 遍历父查询中的聚合项，调用transform_aggregation_expr函数为其创建改写后的聚合项，然后对旧的聚合项进行替换。该函数会将类型为count/sum类型的聚合函数表达式转换为对应的乘法表达式，如sum(t1.c2)会被转化为sum(t1.c2 * t2_cnt)。
3. 将视图表添加到父查询中，用视图表导出的列替换原来的select列。

push_down_group_by_into_view函数首先会为下推参数创建空的查询语句作为视图表，然后使用下推参数对其进行填充，执行逻辑如下：

1. 从原查询语句中移除当前下推参数中的过滤条件，添加到视图查询的where条件中。
2. 从原查询语句中移除属于当前下推参数的表集合中的表信息，并将该表信息和对应的from表添加到视图查询中。如果该from表为基表或视图表，则是直接从父查询中移除并添加到视图查询中即可；如果为合并到视图中的join表，则还需要从父查询中移除对应的join表信息并添加到视图查询中；如果为flattern_joined_tables中的表，则将该join表的对应非join子表添加到视图查询中，同时调用update_joined_table函数更新join表中的对应子节点为当前视图表。
3. 从原查询语句中移除属于当前视图表的列，添加到视图语句中，同时将当前下推参数中的join列添加到视图语句的group by表达式中。
4. 为视图语句中的group by表达式创建对应的select列。
5. 使用当前下推参数中的聚合表达式为视图语句创建聚合项，并为其创建对应的select列。

groupby提升

transform_groupby_push_down函数执行流程如下：

1. 调用check_groupby_pullup_validity函数判断当前语句是否能够被执行提升改写，同时收集待改写视图的改写参数。
2. 调用get_trans_view函数为查询语句创建spj子视图，如果查询语句中不包含group by表达式则不进行创建，直接使用原始语句。
3. 遍历待改写参数集合，调用do_groupby_pull_up函数执行提升改写。
4. 调用accept_transform函数对改写后的执行开销进行评估，以此判断是否应该接受改写。

check_groupby_pullup_validity函数会对查询语句的各项成员进行检查，执行流程如下：

1. 调用check_collation_validity函数检查查询语句中数据类型为string或者lob的列对应的collation类型是否一致。
2. 调用ObTransformUtils::check_can_set_stmt_unique函数检查查询语句是否输出唯一结果。
3. 收集改写判断过程中需要忽略的表（下称ignore_tables），主要包含以下几部分：
1. 作为semi join左表的表。
2. 子查询涉及的表。
3. 使用聚合函数列作为连接条件参数的视图表。
4. 遍历查询语句中的from表，调用重载的check_groupby_pullup_validity函数根据表的类型判断其是否满足改写条件，执行逻辑如下：
1. 如果当前表为基表，不影响改写。
2. 如果当前表为视图表，需要按照如下流程进行进一步判断：
1. 判断当前表是否包含于ignore_tables中，如果是则不影响改写。
2. 调用is_valid_group_stmt函数检查视图查询是否满足如下改写要求：
1. 查询语句中必须包含group by表达式和聚合项，且不包含窗口函数、limit表达式和order by表达式。
2. 查询语句中不包含distinct标记，也没有semi join信息。
3. 查询语句的select列、order by表达式及having表达式都包含于group by表达式。
3. 如果参数中设置了需要进行having条件检查（下称need_check_having_），则当前视图查询的having条件必须为空。
4. 如果参数中设置了需要进行空值传递检查（下称need_check_null_propagate_），则当前视图中的所有聚合函数项对于视图查询中的列都需要满足空值传递或者能够找到非空列（即可以使用case when进行改写）。

对于满足上述条件的视图表，该函数会将其改写参数添加到待改写集合中。

1. 如果当前表为join表，则递归地对其子节点进行判断。在递归调用前，需要根据join类型设置检查参数，执行逻辑如下：
1. 如果为内连接，则不为任何一侧子节点的函数调用设置need_check_having_和need_check_null_propagate_参数。
2. 如果为左（右）外连接，则为内表侧子节点的函数调用设置need_check_having_和need_check_null_propagate_参数。
3. 如果为全外连接，则同时为两侧子节点的函数调用设置need_check_having_和need_check_null_propagate_参数。另外，全外连接节点的两侧子节点至少一个需要为基表，否则退出改写流程。

do_groupby_pull_up函数会使用当前改写参数执行改写，处理流程如下：

1. 将当前视图表添加到ignore_tables中，然后调用ObTransformUtils::generate_unique_key函数为父查询中不在ignore_tables中的from表提取唯一键，并添加到父查询的group by表达式中（这里主要是为了适配连接操作的语义）。
2. 遍历视图查询的select列表，收集其中被导出到父查询中的聚合函数表达式及对应的父查询列表达式（下称aggr_select和aggr_column）。
3. 调用wrap_case_when_if_necessary函数对aggr_select中不满足空值传递的表达式改写为case when表达式。
4. 将视图查询的group by表达式、聚合项和having条件与上一步改写后的aggr_select一同放到提升表达式集合中，然后抽取其涉及的视图查询中的列（下称view_columns），将这些列导出到父查询中并收集对应的父查询列（下称stmt_columns）。
5. 将视图查询中的group by表达式、聚合项和having条件提升到父查询中，执行流程如下：
1. 使用stmt_columns替换aggr_select中对应的view_columns中的列，并将父查询aggr_column中的列替换为aggr_select中的表达式（即执行select列中聚合表达式的提升）。
2. 将视图查询的group by表达式移除，添加到父查询中。然后使用stmt_columns替换group by表达式中对应的view_columns中的列（即执行group by表达式的提升）。
3. 将视图查询的聚合项移除，添加到父查询中。然后使用stmt_columns替换聚合项中对应的view_columns中的列（即执行聚合项的提升）。
4. 将视图查询的having条件移除，添加到父查询中。然后使用stmt_columns替换having条件中对应的view_columns中的列（即having条件的提升）。
6. 对父查询中的where条件进行重新分配，将包含聚合函数的条件移动到having条件中。