Oceanbase查询改写：where子查询提升

概述

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

基本原理

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

1. 子查询转半/反连接：当查询语句的where条件中存在any/all或exist/not_exist子查询时，根据查询语义，将子查询表达式转化为半连接或反连接。
2. 子查询转内/外连接：当查询语句的where条件中存在非any/all/exist/not_exist子查询，且子查询返回单行结果时，可以将子查询表达式转化为内/外连接。

子查询转半/反连接

考虑如下情况：

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

上述查询为相关子查询，如果没有经过改写，则只能嵌套执行。根据语义，可以将含子查询的表达式改写为半连接，如下所示：

SELECT c1, c2 FROM t1 WHERE c1 SEMI JOIN t2 ON t1.c2 = t2.c2 AND t1.c1 > t2.c1

子查询转内/外连接

考虑如下情况：

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

上述查询条件中包含子查询，如果子查询中包含唯一键（包含主键）的equal条件时，子查询至多返回一条记录，此时可以将子查询转化为内连接，如下所示：

SELECT c1, c2 FROM t1 JOIN t2 ON t2.c1 = 0 AND t1.c2 > t2.c2

代码解析

where子查询提升规则的入口为ObWhereSubQueryPullup::transform_one_stmt，该函数的主要执行流程如下：

1. 调用transform_anyall_query函数将where条件中的any/all或exist/not_exist子查询改写为半连接或反连接。
2. 调用transform_single_set_query函数将where条件中返回单行结果的非any/all/exist/not_exist子查询改写为内连接或外连接。
3. 调用add_limit_for_exists_subquery函数为exist/not_exist子查询添加limit 1表达式。

子查询转半/反连接

transform_anyall_query函数会遍历查询语句中的where条件，然后调用transform_one_expr函数对每个表达式执行改写。

transform_one_expr函数首先会调用recursive_eliminate_subquery函数递归地遍历表达式中嵌套的子查询，后者最终会调用eliminate_subquery函数尝试简化或消除子查询。如果exist/not_exist表达式中存在可以被消除的子查询，则调用eliminate_subquery_in_exists函数将exist/not_exist表达式改写为恒真/恒假的常量表达式，从而消除子查询。如果当前子查询无法被消除，则按照如下逻辑进行简化：

• 对于exist/not_exist类型的子查询：
1. 调用eliminate_select_list_in_exists函数尝试将select项替换为select 1，移除distinct标记和窗口函数。
2. 调用eliminate_groupby_in_exists函数尝试移除group by表达式。
3. 移除order by表达式。
• 对于any/all类型的子查询：
1. 调用eliminate_groupby_in_any_all函数尝试移除group by表达式。
2. 如果为相关子查询，则调用eliminate_distinct_in_any_all函数尝试移除distinct标记。
3. 如果为不相关子查询，则尝试添加limit 1表达式。

遍历完成后，transform_one_expr函数会调用gather_transform_params函数建立改写相关参数，并判断能否进行改写。执行完成后，会调用do_transform_pullup_subquery函数进行改写，执行逻辑如下：

1. 如果子查询不属于spj查询（如包含group by表达式），则需要调用create_spj函数为子查询创建spj视图表，然后使用基于视图表的查询继续后面的改写。
2. 如果为相关子查询，则调用pullup_correlated_subquery_as_view函数进行改写。
3. 如果为不相关子查询，则调用pullup_non_correlated_subquery_as_view函数进行改写。

pullup_correlated_subquery_as_view函数会将相关子查询改写为基于视图的半连接或反连接，执行逻辑如下：

1. 为子查询创建视图表，然后从父查询语句中移除子查询。
2. 调用generate_conditions函数为any/all子查询生成相关的（correlated）查询条件，后续这些条件将作为连接条件的一部分使用。对于any子查询，生成的条件与原条件一致；对于all子查询，生成的条件与原条件相反（如=转为<>，>转为<=）。完成后，将条件合并到子查询的where条件中。
3. 从子查询的where条件中提取出相关的（correlated）查询条件，调用generate_semi_info函数，使用这些条件生成连接信息。对于any或exist子查询，会生成半连接；对于all或not_exist子查询，会生成反连接。
4. 将子查询的各项参数提升到父查询。

pullup_non_correlated_subquery_as_view函数的逻辑较为类似，这里不再赘述。

子查询转内/外连接

transform_single_set_query函数会遍历where条件中的表达式，调用get_single_set_subquery函数找到能够被改写的子查询。能够被改写的子查询需要满足如下条件：

1. 子查询中必须包含equal条件，且右参数必须为常量。
2. 子查询的equal条件对应的列应该满足唯一性。结合条件1，这里的意思应该是根据equal条件能够唯一确定一条记录。
3. 子查询的所有select列应该满足空值传递（如select 1这样的列则不满足）。这里主要是因为子查询会被提升为右表，当右表记录不存在时，select表达式也必须返回null。

对于每条能够被改写的子查询，会调用unnest_single_set_subquery函数进行改写，执行逻辑如下：

1. 将子查询的各项参数提升到父查询。
2. 调用trans_from_list函数将子查询改写为外连接或内连接，这里确定连接方式的依据主要是子查询所在的表达式是否满足空值拒绝，如果满足则使用内连接，否则使用外连接。
3. 调用replace_inner_stmt_expr函数将子查询所在表达式的参数替换成select列。
4. 从父查询中移除子查询。