ABSTRACT
子查询的挑战
- 执行器在扫表时出现递归，在从表A扫描一条数据，执行qual表达式时，表达式中包含子查询，在表A的上下中又会去扫描表B，最终扫描表B次数非常多；
- 优化器难以深入优化，对其他表的子查询在表达式中，而优化器只对From中的表进行交换扩展join空间；
- 执行效率低，每扫描到表A的一行数据都要去表B执行一次扫描，复杂度高，同时无法发挥预读；
现状
当前对subquery，grouping，agg的处理策略中有很多重叠的部分，比如某些对子查询的优化算法中包含了部分的groupby优化。本论文提出通过小的正交的原语操作，组合出丰富的执行策略，这些策略通过组合可以完全替换之前对subquery，grouping，agg的优化策略。
本文的思路
- 对子查询形式化表达，并描述了9种规则，形式化了所有子查询；
- 对子查询优化算法，groupby优化算法正交解耦，最终通过组合能优化所有子查询+groupby+agg场景（理论上）；
这些原语分成两大类：
1. 去关联化（correlation removal）；
2. outerjoin和groupby；
本文重点讲述subquery的去关联化（query flattening）和agg的优化方法。SQL Server基于这些原语对subquery和agg做了优化。
INTRODUCTION
1.1 subquery - 当前的执行策略
vector agg和scala agg
vector agg:返回值是一个向量，如果表是空的，则返回空；
select o_orderdate, sum(o totalprice) from orders group by o_orderdate
scalar agg:返回值是单个数值，如果表为空，最终返回值取决于聚合函数，比如：count返回0；sum返回NULL；
select sum(o totalprice) from orders
G(A, F)表示vector-agg；
G(1, F)表示scala-agg；
关联子查询SQL：找出消费大于1000000的客户
遍历customer表，对每个客户在orders表中求值他的消费总额度。这里subquery用了scala的聚合。subquery使用了外层query的参数c_custkey，因此它是一个关联子查询。
Q1: select c_custkey from customer where 1000000 < (select sum(o_totalprice) from orders where o_custkey = c_custkey)
列出3个已知的执行策略
1) Correlated execution
最直接的执行算法是和SQL的写法一致，类似nestloop，用外层query的每个customer去遍历内层query的orders表。
通常这种执行策略性能是非常的，因为复杂度是笛卡尔乘积。但是有些场景这种执行效率也会很高，比如外层query的结果集非常小，或者内层query有索引。
2) 先Outerjoin然后agg
使用set-oriented算法，先收集一个custom对应的所有的order，然后在custom分组，聚合。
该算法最早被Dayal提出。
select c_custkey from customer left outer join orders on o_custkey = c_custkey group by c_custkey having 1000000 < sum(o totalprice)
使用outerjoin是为了和subquery语义保证一致：
1. Correlated execution中，每个custom都去计算一次scalar agg，即使没有相关的order存在；
2. outerjoin时，每个custom也是返回一行，即使没有order存在，然后再计算agg；
outerjoin能保证这两种执行行为是等价的。
3) 先agg然后join
先对orders表执行分组，聚合，过滤出符合要求的分组，然后和custom进行join。相当于把agg下推到join的下面。
该算法是被Kim提出来。
select c_custkey from customer, (select o_custkey from orders group by c_custkey having 1000000 < sum(o_totalprice)) as AggResult where o_custkey = c_custkey
1.2 subquery - 本文提出的基于原语正交组合的优化策略
上面提到的几个算法的执行效率最终取决于表大小，选择率，agg的压缩率。需要根据代价动态的选择，而不是直接使用某种策略。
我们通过正交的原语组合出上述的几种执行算法，甚至能探索出更多的执行算法，然后根据代价选择最优的执行算法。
Algebrize into initial operator tree
通过引入了Apply算子来形式化关联subquery，这是一个二阶的关系代数运算符，用来表达参数化的子查询。
Remove correlations
去关联化就是把apply改些成其他算子，比如outerjon。
Simplify outerjoin
outerjoin简化成join，这样可以和join使用同一个执行框架，只需要增加nul-rejection的判断。去关联化通常产生outerjon，然后再简化成join。
比如：1000000 < x会拒绝x为null的情况，因此可以将outerjoin最终转换成jion。
Reorder GroupBy
在outerjoin的上游或者下游重排序agg。
1.3 Apply算子：使用关系代数来描述关联subquery
apply算子：
1. 类似LISP中的APPLY和MAPCAR：对一个集合操作，并收集结果，他是一个集合操作运算符；
2. 关系数据库中类似nestloop；
3. 对象数据库中类似lambda-calculus(闭包)；
对关系R中每行数据r，执行表达式E，返回符合条件的r集合；
上述例子中的SQL的关系代数描述为：
由于每次调用参数表达式E(r)之后都会返回一行r，因此通过apply算子后，custom总数不变。
SegmentApply算子
- Apply算子：scalar valued，标量做为subquery的参数；
- SegmentApply算子：table-valued做为subquery的参数；
关系R做为输入，使用某个列A对R进行分组（类似groupby A），将一个个分组S做为参数，传给E。SegmentApply算子可转换成Apply算子和一些其他基本的算子。
通过引入Apply算子，以关系代数的方式形式化subquery，在原有关系代数的基础上增加了sql执行的可选择空间。
普通的关系代码描述的集合操作，Appply算子和普通关系代数算子不同的是：Apply是一次执行一个tuple，tuple-at-a-time。
2. 子查询的形式化表达
2.1 operator tree
首先，parser解析SQL成operator树。
WHERE子句被解析成一个表达式，左子树是常量1000000，右子树是subquery，这个subquery返回标量。
subquery中包含关联参数。如果直接对这个表示树执行，那么执行过程类似nestloop方式：对外层的每个行都调用scalar表达式的评估。
2.2 引入Apply
通过Apply可以将subquery嵌套消除。在对subquery的scalar标量进行操作前，先通过Apply
计算出结果。
关系R和子查询Q之间通过Apply算子连接，表达式e的参数为Q计算出来的scalar标量值q。
转换之后带有Apply算子的树，如下图：
该转换方法同样适用于多层subquery嵌套。
经过Apply转换之后operator tree，执行模式仍然是nestloop方式。然而消除了计算scalar和查表的递归嵌套：
1. 在Apply之前，每次从custom扫描到一行数据后，紧接着要执行qual过滤（1000000<scalar值），此时求值scalar值需要扫描另外一个表，此时还在扫描表custom的上下文中，扫描表处于递归中；
2. Apply可以实现为一个类似nestloop的循环，从左边表查一条数据，无需执行qual过滤，直接返回一行结果，这个扫描算子就执行结束了，然后执行右边的子查询，扫描另外一个表，计算scalar值，最后在上层select中过滤1000000 < x；
2.3 Apply算子的消除规则
无需在执行器中真正的实现Apply算子，可以通过9种规则消除Apply算子，转换成join算子。
方法就是：
1. 先用Apply算子替换子查询；
2. Apply算子下推（堆到agg、filter下面，相当于agg、filter上移），直到右边的表不再包含左边表的参数为止（参数被Apply算子本身表达）；
3. 最终得到最简化的Apply算子形式；
4. 应用9条转换规则；
比如，Q1的处理：
1. 应用规则9，把Apply下推到scalar agg下面；
2. 应用规则2，此时Apply左右
第一步中将ScalarAgg转变成了GroupAgg，分组类是R的key（c_custkey），正确性：
变换前，
1. 变换前给每个 R 的行，通过Apply算子右边的ScalarAgg聚合计算一次；
2. 再把聚合的结果合并起来；
变换后，
1. 通过Apply算子将所有要聚合的数据预先准备好（这被称为 augment）；
2. 然后使用 GroupAgg 一次性地做完所有聚合；
因此，GroupAgg时，分组的key是c_custkey。
2.4 任意子查询的去关联化
可以通过上述的方法把任意子查询去关联化，比如：对于子查询中包含EXISTS, NOT EXISTS，可以转换成scalar COUNT聚合，是否大于0。
Max1row
下面sql的子查询在select中，会有3种可能的结果：
1. select o_orderkey返回null，那么这个子查询最终返回null；
2. select o_orderkey返回一行，那么这个子查询最终就返回该行；
3. select o_orderkey返回多行，那么此时需要产生run-time-error；
因此位于select中的子查询，引入Max1row算子，对子查询结果集进行检查，如果超过了1行就报run-time-error；
Q2: select c_name, (select o_orderkey from orders where o_custkey = c_custkey) from customer
并不是所有的子查询都需要Max1row的判断，比如：
select o_orderkey, (select c_name from customer where c_custkey = o_custkey) from orders
conditional scalar execution
CASE WHEN <COND> THEN <VALUE1> ELSE <VALUE2> END
当条件为true时，VALUE2不应该被执行，也需要产生run-time-error；
通过扩展Apply with conditional来实现。
这种语法在实际业务中并不常见。
2.5 子查询的分类
Class 1. Subqueries that can be removed with no additional common subexpressions
通常，移除Apply需要引入额外的通用表达式（公因式）。
比如规则5，在消除Apply后需要引入两次R。
能够简单的被select/project/join/agg描述的子查询，在去除Apply时相对简单些。
Class 2. Subqueries that are removed by introducing additional common subexpressions
sql中包含相同的subexpr，在使用Apply消除子查询时，复杂度非常高。SQL server并没有在normalization阶段去关联化，只是在cost-based空间搜索时进行了特殊优化。
而且此类sql的实际意义不大，比如:
select *, from partsupp where 100 > (select sum(s acctbal) from (select s_acctbal from supplier where s_suppkey = ps_suppkey union all select _ retailprice from part where p_partkey = ps_partkey) as unionresult)
Class 3. Exception subqueries
需要引入scalar相关的运行时报错，比如前面的例子：
Q2: select c_name, (select o_orderkey from orders where o_custkey = c_custkey) from customer
3. 聚合查询的优化
高效的处理子查询中带有agg。通过关系代数来简化groupby/agg的重排序。最终得到一些执行agg的转换规则。
3.1 Reordering GroupBy
经过agg后能减少结果集，因此借助agg做为filter的一种手段。另外，join的条件也可能减少结果集，或者join可以借助索引，如果先进行agg，那么索引就无法使用。因此，最终filter，join，semijoin，agg的执行顺序需要计算代价，通过代价来动态决定。
本小节通过形式化的方法来描述其他论文中对此类优化的理论。
Groupby和filter
groupby算子将拥有相同的grouping列进行分组，最终每个分组产生一行结果。同一个组里唯一相同的就是他们的grouping列。
因此filter算子能够下推或者上拉的充要条件是：filter中的列是grouping列的子集。
Groupby和join - groupby下推
Groupby能够下推到join下面，需要grouping列，agg函数，和join条件需要满足一定的条件：
1. join条件中的一个列p属于R，那么需要属于groupping集合；（保证grouping列包含了R中的所有参与jon的列）
2. S的key属于groupping集合；（保证一个groupby组中不会出现S中两个行，因为它的key在groupby中）
3. agg函数必须只使用R的列；（保证能够下推到R上）
总结，把groupby下推到R上，grouping的类列分成两部分：
1. 一个部分是S的列 - 必须是S的key，保证一个分组里最终只有一行S；
2. 一部分是R的列 - 更上层的filter列，保证groupby能够下推到这个filter下；
Groupby和join - groupby上拉
groupby上拉需要满足2个条件：
1. 左边的表S有唯一key；（保证groupby聚合前后，每个分组里都只有S的一行数据）
2. join条件没有用到agg的函数结果；（保证groupby上拉，不影响join的进行）
如果上拉之前有对groupby聚合后结果集的filter过滤，那么groupby上拉之后，也可以在having中执行该filter过滤，比如Q1的处理。
对于semijoin和antisemijoin，就是在上面的基础上增加了空、非空的判断。
3.2 GroupBy和outerjoin
由于outerjoin最终的结果分成matched和unmatched，如果把groupby下推到LOJ的右子节点：
1. 对于match的结果groupby结果集在下推和不下推是一样的；
2. 对于unmatch的结果，groupby下推后就没有了对应的分组；
因此要在把groupby下推到LOJ下面后，在LOJ上面增加一个project：如果发现一行unmatched行，那么就给它加上null对应的agg结果。比如：如果是count(*)，那么就增加0；
3.3 Local Aggregates
上面介绍到groupby下推有3个条件，当不满足这3个条件时，就不能下推groupby。
可以下推部分groupby的工作量到下层。聚合函数f被拆分成多个聚合函数：
- 下层的称为Local Agg；(先对右表进行一次细粒度聚合，比如count(*)，一定程度上减少了结果集)
- 上层的称为Global Agg；（在join后，进行一次最终的聚合，比如sum(*)）
该方法能把LocalGroupby下推到左边或者右边，无需新增算子。
3.4 Segmented execution
SegmentApply和Apply的区别是：参数并不是S中的一行，而是一个集合。
找出lineitem中quantity小于平均的20%。子查询的结果并不需要返回具体的平均值X，它仅仅是用来过滤。
select l_partkey, l_extendedprice from lineitem, (select l_partkey as l2_partkey, 0.2 * avg(l_quantity) as x from lineitem group by l_partkey) as aggresult where l_partkey = l2_partkey and l_quantity < x
- 左边的LINEITEM按照L_PARTKEY分组；
- 一个分组S做为参数传给SegmentApply的右子树；
- 右子树对这个分组S进行JOIN：
- 先计算出0.2 * AVG的值做为一个新列；
- 然后和S自身进行join，条件是l_quantity < x;
整个过程只需要对LINEITEM扫描一次就可以了。
转换的形式化表达：
4. SQL Server中优化器的3个阶段
Parse and bind阶段
sql文本翻译成operator树，此时树中包含子查询。
Query normalization阶段
（逻辑优化）简化operator树：outerjoin转成join；消除空表达式；递归消除多层关联/非关联子查询；
Cost-based optimization阶段
（物理优化）join顺序；上拉/下推groupby和join；
基于Volcano优化器，通过一些transformation rule来扩展搜索空间；
5. 性能数据
当然最终的性能不仅取决于优化器，还有执行器。
6. CONCLUSIONS
- 子查询和聚类查询的优化应该进行正交分解，优化单个小操作符，最终通过组合出所有场景的优化算法；
- 引入apply关系操作符对子查询进行形式化，以及对groupby形式化，对query的优化处理能进行很好的抽象；
- 去关联化应该借助关系代数的等价转换在query normalization阶段；
- 聚合查询的优化应该考虑代价，而不是启发式的；
