开发者社区> 游客ebdjhbkyk4vb4> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

子查询优化论文解读 - 《Orthogonal Optimization of Subqueries and Aggregation》

简介: Orthogonal Optimization of Subqueries and Aggregation
+关注继续查看

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 - 本文提出的基于原语正交组合的优化策略

image.png

上面提到的几个算法的执行效率最终取决于表大小,选择率,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(闭包);

image.png

对关系R中每行数据r,执行表达式E,返回符合条件的r集合;

上述例子中的SQL的关系代数描述为:

image.png

由于每次调用参数表达式E(r)之后都会返回一行r,因此通过apply算子后,custom总数不变。

SegmentApply算子

  1. Apply算子:scalar valued,标量做为subquery的参数;
  2. SegmentApply算子:table-valued做为subquery的参数;
    image.png
    关系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表达式的评估。

image.png

2.2 引入Apply

通过Apply可以将subquery嵌套消除。在对subquery的scalar标量进行操作前,先通过Apply

计算出结果。

image.png

关系R和子查询Q之间通过Apply算子连接,表达式e的参数为Q计算出来的scalar标量值q。

转换之后带有Apply算子的树,如下图:

image.png

该转换方法同样适用于多层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条转换规则;

image.png

比如,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 一次性地做完所有聚合;

image.png

因此,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的进行)

image.png

如果上拉之前有对groupby聚合后结果集的filter过滤,那么groupby上拉之后,也可以在having中执行该filter过滤,比如Q1的处理。

对于semijoin和antisemijoin,就是在上面的基础上增加了空、非空的判断。

3.2 GroupBy和outerjoin

由于outerjoin最终的结果分成matched和unmatched,如果把groupby下推到LOJ的右子节点:

1. 对于match的结果groupby结果集在下推和不下推是一样的;

2. 对于unmatch的结果,groupby下推后就没有了对应的分组;

image.png

因此要在把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(*))
    image.png
    该方法能把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. 先计算出0.2 * AVG的值做为一个新列;
    2. 然后和S自身进行join,条件是l_quantity < x;
      整个过程只需要对LINEITEM扫描一次就可以了。

image.png

转换的形式化表达:

image.png

4. SQL Server中优化器的3个阶段

Parse and bind阶段

sql文本翻译成operator树,此时树中包含子查询。

Query normalization阶段

(逻辑优化)简化operator树:outerjoin转成join;消除空表达式;递归消除多层关联/非关联子查询;

Cost-based optimization阶段

(物理优化)join顺序;上拉/下推groupby和join;

基于Volcano优化器,通过一些transformation rule来扩展搜索空间;

5. 性能数据

image.png

当然最终的性能不仅取决于优化器,还有执行器。

6. CONCLUSIONS

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Es Bucket聚合(桶聚合) Terms Aggregation与Significant Terms Aggregation
Es Bucket聚合(桶聚合) Terms Aggregation与Significant Terms Aggregation
44 0
什么是 Rxjs 的 subscription
什么是 Rxjs 的 subscription
39 0
Internationalization(i18n) support in SAP CRM,UI5 and Hybris
i18n(其来源是英文单词 internationalization的首末字符i和n,18为中间的字符数)是“国际化”的简称。对程序来说,在不修改内部代码的情况下,能根据不同语言及地区显示相应的界面。
17 0
Internationalization(i18n) support in SAP CRM,UI5 and Hybris
Internationalization(i18n) support in SAP CRM,UI5 and Hybris
27 0
Internationalization(i18n) support in SAP CRM,UI5 and Hybris
i18n(其来源是英文单词 internationalization的首末字符i和n,18为中间的字符数)是“国际化”的简称。对程序来说,在不修改内部代码的情况下,能根据不同语言及地区显示相应的界面。
55 0
Paper:《Adam: A Method for Stochastic Optimization》的翻译与解读
Paper:《Adam: A Method for Stochastic Optimization》的翻译与解读
78 0
84
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载