Oceanbase查询改写：聚合子查询提升

概述

默认情况下，对于包含子查询的语句需要按照嵌套的方式进行执行，效率十分低下。为此，Oceanbase中定义了聚合子查询提升规则，能够对满足条件的聚合子查询提升为连接，提升查询性能。

基本原理

聚合子查询提升规则主要包含对以下两种情况的处理：

1. 聚合优先提升：当聚合子查询中不包含相关条件或只包含equal相关条件时，可以将聚合子查询改写为视图表，然后将其与父查询中的表进行连接。
2. 连接优先提升：当聚合子查询中包含equal条件以外的相关条件时，可以将子查询中的from表先与父查询进行连接，然后对连接结果进行聚合。

聚合优先提升

考虑如下情况：

SELECT c1, c2 FROM t1 WHERE c1 > (SELECT max(c1) FROM t2 WHERE t2.c2 = t1.c2)

在上述查询语句中，子查询的相关条件为相等条件，因此可以对其进行聚合优先提升改写，如下所示：

SELECT t1.c1, t1.c2 FROM t1, (SELECT max(c1) AS c1, c2 FROM t2 GROUP BY c2) v
	WHERE t1.c1 > v.c1 AND t1.c2 = v.c2

连接优先提升

SELECT c1, c2 FROM t1 
	WHERE c1 = (SELECT max(c1) FROM t2 WHERE t2.c2 > t1.c2) --c1为主键

在上述查询语句中，子查询的相关条件不是相等条件，因此可以对其连接优先提升进行改写，如下所示：

SELECT t1.c1, t1.c2 FROM t1, t2 GROUP BY t1.c1 
	WHERE t2.c2 > t1.c2 HAVING t1.c1 = max(t2.c1)

代码解析

聚合子查询提升规则的入口为ObTransformAggrSubquery::transform_one_stmt，执行流程如下：

1. 调用extract_no_rewrite_select_exprs函数收集无需进行改写的子查询表达式，如果子查询中的条件能够找到匹配的索引，则不对该表达式进行改写并将其存储到需要忽略的表达式集合中（下称no_rewrite_exprs_）。
2. 调用transform_with_aggregation_first函数执行聚合优先提升改写。
3. 调用transform_with_join_first函数执行连接优先提升改写。

聚合优先提升

transform_with_aggregation_first函数会遍历查询语句各组成部分的表达式，然后调用do_aggr_first_transform函数对其中的子查询表达式进行改写。后者首先会调用gather_transform_params函数收集当前表达式下能够被改写的子查询表达式作为改写参数，然后遍历这些参数，执行如下流程对其中的子查询进行改写：

1. 调用choose_pullup_method函数确定提升时使用的连接方法为外连接还是内连接。
2. 调用fill_query_refs函数收集涉及子查询的列引用，后面改写为视图后需要用视图导出列对其进行替换。
3. 调用transform_child_stmt函数对子查询进行改写。
4. 调用transform_upper_stmt函数对父查询进行改写。

gather_transform_params函数会递归地找到当前表达式中包含的子查询，然后调用check_subquery_validity函数检查子查询是否满足改写条件。如果子查询包含于no_rewrite_exprs_中，则忽略该子查询。另外，对于exist/not_exist类型的表达式，只能使用连接优先的方式进行改写。

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

1. 检查子查询的基本属性是否满足如下条件：
1. 子查询不包含having表达式、limit表达式和窗口函数。
2. 子查询不是集合语句。
2. 调用is_valid_group_by函数检查子查询中的group by表达式是否如下条件之一：
1. 不包含任何group by表达式。
2. 存在group by表达式，但其中不包含相关表达式，且每一个表达式为常量表达式或者能在where条件中找到常量约束。
3. 调用check_subquery_aggr_item函数检查子查询中聚合项的聚合类型是否为count/sum/min/max之一。
4. 调用check_subquery_select函数检查子查询中的select列是否不包含相关表达式和子查询。
5. 调用check_subquery_table_item函数检查子查询的表信息中是否不存在包含相关表达式的视图表。
6. 调用check_subquery_on_conditions函数检查子查询中涉及的join表的连接条件中是否不包含相关条件。
7. 调用check_subquery_semi_conditions函数检查子查询中的semi join连接条件中是否不包含相关条件。
8. 调用check_subquery_conditions函数检查子查询的where条件中的相关条件是否都为直接相关的equal条件，且不包含子查询，同时收集满足上述相关表达式（下称nested_conditions_）。

choose_pullup_method函数首先会遍历子查询的select列，判断其中是否所有的列都满足空值传递。如果满足，则进一步判断子查询表达式对于其所在区域的所有过滤条件（即所有where条件或having条件）是否存在空值拒绝条件。如果子查询中没有相关条件且不包含group by表达式或者存在空值拒绝条件则使用内连接，否则使用外连接。

transform_child_stmt函数负责对子查询部分进行改写，该函数首先移除子查询原有的group by表达式，然后提取出nested_conditions_中属于子查询一端的列，然后将其作为新的group by表达式并添加到子查询的select列中。如果新的group by列为空（即不包含相关条件），则仍然使用旧的group by表达式。

transform_upper_stmt函数负责对父查询进行改写，执行流程如下：

1. 从父查询中移除子查询，然后将子查询作为视图表添加到父查询中。
2. 调用deduce_query_values函数收集子查询视图导出的列表达式，将其中不满足空值传递的列改写为case when表达式，然后用收集的列表达式集合替换原查询语句中对子查询的列引用。
3. 调用transform_from_list函数，根据前面确定的连接方式为父查询中的from表和新创建的视图表建立连接。nested_conditions_中的相关条件此时将成为连接条件使用，因此会事先将其中涉及子查询的列表达式替换成对应视图导出的列表达式。

连接优先提升

transform_with_join_first函数首先会调用check_stmt_valid函数检查查询语句是否输出唯一结果（因为后面需要提取唯一键作为group by表达式），然后使用查询语句中的子查询数目作为循环次数，在循环中执行如下流程对语句进行改写：

1. 调用get_trans_param函数找到查询语句中下一个能够被改写的表达式。该函数会按照group by前（where条件、group by表达式和聚合项，下称pre_group_by_exprs）和group by后（select列和having表达式，下称post_group_by_exprs）分别收集查询语句中的表达式，然后先后进行遍历判断。
2. 调用fill_query_refs函数收集涉及子查询的列引用，后面改写为视图后需要用子查询的select列对其进行替换。
3. 调用get_trans_view函数为当前查询创建spj子视图，后续查询将基于该视图进行。创建完成后，如果原查询语句包含group by表达式且当前处理的表达式位于post_group_by_exprs中，则需要将group by表达式下推至视图查询内。如果原查询语句本身不包含group by表达式，则直接使用该语句作为视图。
4. 调用do_join_first_transform函数执行改写。

每轮循环过后，都会使用基于当前视图进行下一轮改写，因此多轮改写会形成嵌套视图。如果在循环条件到达前，get_trans_param函数返回的可改写表达式为空，说明此时已经没有可以改写的表达式，应该提前退出。

get_trans_param函数首先会调用gather_transform_params函数收集当前表达式下能够被改写的子查询表达式作为改写参数，然后遍历这些参数，执行如下流程进一步判断其能否被改写：

1. 确定提升时使用的连接方法，如果当前表达式为exist/not_exist表达式，则调用choose_pullup_method_for_exists函数进行判断，否则调用choose_pullup_method函数进行判断。
2. 当上一步确定的连接方法为外连接时，调用check_can_use_outer_join函数判断使用外连接是否合法。

如果上述条件满足，则该函数会返回当前的表达式和对应的改写参数。

gather_transform_params函数对于连接优先提升的改写方式，会调用重载的check_subquery_validity函数，执行流程如下：

1. 检查子查询的基本属性是否满足如下条件：
1. 子查询不包含group by表达式和窗口函数。
2. 子查询不是集合语句。
3. 如果子查询包含于exist/not_exist表达式，则必须包含having条件，并进一步调用check_subquery_having检查having条件中所有条件是否都包含聚合表达式，且不包含相关条件和子查询。
4. 如果子查询不包含于exist/not_exist表达式，则不能包含having条件和limit表达式，并进一步调用check_subquery_select函数检查子查询中的select列是否不包含相关表达式和子查询。
2. 调用check_subquery_aggr_item函数检查子查询中聚合项的聚合类型是否为count/sum/min/max之一。
3. 调用check_count_const_validity函数检查子查询中的聚合项中是否不包含count(null)。
4. 调用check_subquery_table_item函数检查子查询的表信息中是否不存在包含相关表达式的视图表。
5. 调用check_subquery_on_conditions函数检查子查询中涉及的join表的连接条件中是否不包含相关条件。
6. 调用check_subquery_semi_conditions函数检查子查询中的semi join连接条件中是否不包含相关条件。
7. 检查子查询中是否存在直接相关条件，且该条件中不包含子查询。

choose_pullup_method_for_exists函数负责确定exist/not_exist表达式在改写时应该使用的连接方式，如果当前表达式为not_exist表达式，则使用外连接。如果为exist表达式，则遍历子查询中的having条件，判断其中是否存在空值拒绝条件，如果存在则使用内连接，否则使用外连接。

check_can_use_outer_join函数负责检查将当前表达式使用外连接改写是否合法，判断条件如下：

1. 表达式下的子查询中不包含semi join。
2. 表达式下的子查询中的where条件里不存在包含子查询的条件。
3. 表达式下的子查询中的聚合项应该满足空值传递或者查询语句中存在非空列（对于count(1)或count(*)这类不满足空值传递的情况）。

do_join_first_transform函数负责对当前查询语句进行改写，执行流程如下:

1. 调用get_unique_keys函数获取当前查询语句的唯一键作为语句的group by条件。如果当前改写已经不是第一次改写，则说明当前语句下存在已经改写过的视图表，直接使用视图表的group by条件作为自身的条件。
2. 调用replace_count_const函数使用非空列将不满足空值传递的聚合函数改写为case when表达式。
3. 从当前查询语句中移除子查询，如果子查询所在的条件表达式为exist/not_exist条件，则从当前查询语句中where条件中移除该表达式，并添加到having条件中。如果为not_exist条件，则还需要先使用lnnvl对条件进行取反。如果不是exist/not_exist条件，则需要将涉及子查询的列引用替换为子查询内的select列。
4. 将子查询的表信息合并到父查询中，然后调用transform_from_list函数将子查询作为视图表添加到父查询中的from表中，并使用子查询的where条件作为连接条件，根据前面确定的连接方式建立连接。
5. 将子查询中的各项表达式合并到父查询中，然后调用rebuild_conditon函数对合并后父查询中的where条件中的表达式按照如下逻辑进行重分配：
1. 对于包含聚合函数的表达式，会被分配到父查询的having条件中。
2. 对于包含子查询的表达式，如果该表达式也位于子查询的where条件中，则会被分配到父查询的where条件中。
3. 其他情况，分配到父查询的where条件中。