ABSTRACT

子查询的挑战

1. 执行器在扫表时出现递归，在从表A扫描一条数据，执行qual表达式时，表达式中包含子查询，在表A的上下中又会去扫描表B，最终扫描表B次数非常多；
2. 优化器难以深入优化，对其他表的子查询在表达式中，而优化器只对From中的表进行交换扩展join空间；
3. 执行效率低，每扫描到表A的一行数据都要去表B执行一次扫描，复杂度高，同时无法发挥预读；

现状

当前对subquery，grouping，agg的处理策略中有很多重叠的部分，比如某些对子查询的优化算法中包含了部分的groupby优化。本论文提出通过小的正交的原语操作，组合出丰富的执行策略，这些策略通过组合可以完全替换之前对subquery，grouping，agg的优化策略。

本文的思路

1. 对子查询形式化表达，并描述了9种规则，形式化了所有子查询；
2. 对子查询优化算法，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算子

1. Apply算子：scalar valued，标量做为subquery的参数；
2. 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被拆分成多个聚合函数：

1. 下层的称为Local Agg；(先对右表进行一次细粒度聚合，比如count(*)，一定程度上减少了结果集)
2. 上层的称为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

1. 左边的LINEITEM按照L_PARTKEY分组；
2. 一个分组S做为参数传给SegmentApply的右子树；
3. 右子树对这个分组S进行JOIN：

1. 1. 先计算出0.2 * AVG的值做为一个新列；
   2. 然后和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

1. 子查询和聚类查询的优化应该进行正交分解，优化单个小操作符，最终通过组合出所有场景的优化算法；
2. 引入apply关系操作符对子查询进行形式化，以及对groupby形式化，对query的优化处理能进行很好的抽象；
3. 去关联化应该借助关系代数的等价转换在query normalization阶段；
4. 聚合查询的优化应该考虑代价，而不是启发式的；