子查询（Subquery）的优化一直是SQL查询优化的难点之一。相关子查询的基本执行方式类似于Nested-Loop，但是这种执行方式的效率往往低得令人难以忍受。当数据量稍大时，必须在优化器中进行解关联（DecoorelationorUnnesting），改写为像Semi-Join这样更高效的算子。前人总结出了一套完整的方法论，理论上可以解除任何查询的关联。本文结合SQLServer和HyPer的几篇经典论文，由浅入深地讲解这种去关联的理论体系。两者用的方法差不多，基本思路都想通了。本文中的例子都是基于TPC-H的表结构，这里抄一份给大家参考。子查询简介子查询是SQL标准中定义的一种语法，它几乎可以出现在SQL的任何地方，包括SELECT、FROM、WHERE等子句。一般来说，子查询可以分为相关子查询（CorrelatedSubquery）和非相关子查询（Non-correlatedSubquery）。后面的非相关子查询是一个很简单的问题。最简单的，只需要先执行，得到结果集并物化，再执行外层查询。下面是一个例子：SELECTc_count,count(*)AScustdistFROM(SELECTc_custkey,count(o_orderkey)ASc_countFROMCUSTOMERLEFTOUTERJOINORDERSONc_custkey=o_custkeyANDo_commentNOTLIKE'%pending%deposits%'GROUPBYc_custkey)c_ordersGROUPBYc_countORDERBYcustdistDESC,c_countDESC;▲TPCH-13是一个非关联子查询非关联子查询不在本文讨论范围内，如无特殊说明，我们下面所指的子查询均指相关子查询子查询。相关子查询的特殊之处在于它本身是不完整的：它的闭包包含外部查询提供的一些参数。显然，除非知道这些参数，否则无法运行查询，因此我们不能对不相关的子查询执行此操作。按照生成的数据分类，子查询可以分为以下几种类型：标量值子查询：输出只有一行一列的结果表，标量值就是它的结果。如果结果为空（0行），则输出NULL。但是请注意，不允许超过1行的结果，否则会产生运行时异常。标量子查询可以出现在任何包含标量的地方，例如在SELECT、WHERE等子句中。下面是一个例子：SELECTc_custkeyFROMCUSTOMERWHERE1000000<(SELECTSUM(o_totalprice)FROMORDERSWHEREo_custkey=c_custkey)▲查询1：一个出现在WHERE子句中标量子查询，关联参数使用红色字体标记了SELECto_orderkey,(SELECTc_nameFROMCUSTOMERWHEREc_custkey=o_custkey)ASc_nameFROMORDERS▲Query2:出现在SELECT子句中的标量子查询如果出现在WHERE中，这就是我们熟悉的Semi-Join。当然，它可以出现在任何可以放置布尔值的地方。SELECTc_custkeyFROMCUSTOMERWHEREc_nationkey=86ANDEXISTS(SELECT*FROMORDERSWHEREo_custkey=c_custkey)▲查询3：ASemi-Join实例集比较（QuantifiedComparison）子查询：特指IN、SOME、ANY查询，返回布尔值，常用形式有：x=SOME(Q)（相当于xINQ）或X<>ALL(Q)（相当于xNOTINQ）。同上，它可能出现在任何可以放置布尔值的地方。SELECTc_nameFROMCUSTOMERWHEREc_nationkey<>ALL(SELECTs_nationkeyFROMSUPPLIER)▲查询四：集合比较的非关联子查询的原执行计划我们以查询一为例，直观感受一下为什么要对关联子查询去关联。下面是查询1的原始查询计划（RelationTree），没有去关联。与其他查询计划不同的是，我们特意画了表达式树（ExpressionTree），可以很明显的看出子查询其实是挂在了Filter的条件表达式下的。当img真正执行时，查询计划执行器（Executor）在执行到Filter时调用表达式执行器（Evaluator）；由于此条件表达式包含一个标量子查询，因此Evaluator将调用Executor来计算标量子查询结果。这种Executor-Evaluator-Executor的交替调用效率很低！考虑到可能有上百万行的数据经过Filter，如果对每一行数据执行一个子查询，整个查询的执行时间显然是无法接受的。上面提到的Apply运算符中的Relation-Expression-Relation，不仅执行性能堪忧，对于优化器来说也是一个麻烦的存在——我们的优化规则都是在匹配和转换Relation，而这里隐藏了子查询表情，让人难以上手。为此，我们在开始去关联之前引入Apply算子：Apply算子（也叫CorrelatedJoin）接收两棵关系树的输入。与一般的Join不同，Apply的Innerinput（右子树的图）是一个带有参数的关系树。Apply的含义由下图右半部分的集合表达式定义：对于OuterRelationRR中的每条数据rr，计算InnerRelationE(r)E(r)，并输出它们的结果连接(Join)r?E(r)r?E(r)。Apply的结果就是所有这些结果的并集（本文所说的并集是指Bag语义下的并集，即UNIONALL）。"Apply是SQLServer的名字，在HyPer的文章中叫做CorrelatedJoin，它们是完全等价的。考虑到SQLServer的文章发表时间较早，影响面较广，所以本文使用它的名字。根据连接方式(??)，Apply有四种形式：CrossApplyA×A×：这是最基本的形式，我们刚才描述的行为；LeftOuterApplyALOJALOJ：即使E(r)E(r)为空,也生成一个r°{NULLs}r°{NULLs}.SemiApplyA?A?:IfE(r)E(r)isnotempty,returnrr,otherwisediscard;Anti-SemiApplyA?A?:IfE(r)E(r)为空，返回rr，否则丢弃；我们用刚刚定义的Apply运算符重写前面的例子：从Expression内部提取子查询，结果如下：在上面的例子中，我们可以确定ScalarAgg子查询只有一行结果，因此可以直接转换为Apply。但在某些情况下，可能无法确定子查询将返回0或1row的结果（比如假设Query2ifc_custkey不是唯一的），为了保证SQL语义，在Apply的右边要加一个Max1RowMax1Row算子：Max1Row(E)=?????Null,E,error,if|E|=0if|E|=1otherwiseMax1Row(E)={Null,if|E|=0E,if|E|=1error,otherwise理论上我们可以把所有的子查询都转换成Apply算子。一般的方法如下：1.如果一个运算符的表达式如果公式中出现了子查询，我们将运算符下的子查询提取出来（留下一个子查询结果变量），组成一个ALOJALOJ运算符。如果有多个子查询，则会生成多个ALOJALOJ。添加Max1RowMax1Row运算符时必需。2.然后应用一些其他规则将ALOJALOJ变换为A×A×,A?A?,A?A?。比如上面例子中的子查询结果XX作为Filter的过滤条件，NULL值会被过滤掉，所以可以放心的转换成A×A×。在下面的示例中，Filter条件表达式包含两个子查询Q1Q1和Q2Q2。转换后分别生成对应的Apply算子。其中Q2Q2不能确定恰好会生成一条记录，所以还增加了Max1RowMax1Row算子。基本消除规则第一组规则是最基本的规则。等式中的??表示不限制连接类型，可以是{×,LOJ,?,?}{×,LOJ,?,?}中的任意一种。这两条规则很明显，翻译成通俗的英文：如果Apply的右边不包含来自左边的参数，那么它就相当于直接Join。以下是将规则（2）应用于查询3的示例：Project和Filter的解除关联第二组规则描述了如何处理子查询中的Project和Filter。按下并抬起Apply下面的运算符。请注意，这些规则仅处理交叉应用案例。Apply的其他三个变体理论上可以转换为CrossApply。我们暂时只需要知道这个事实即可。你可能会问：通常我们把Filter和Project尽量往下推，为什么这里要反着来？关键是：Filter和Project本来就是带关联变量的表达式，但是上面提到Apply之后，关联变量就变成了普通变量！这正是我们想要的。后面我们会看到这样做的巨大好处：当Apply被推到最底层时，可以应用第一组规则，直接把Apply变成Join，子查询解除关联的优化过程就完成了。下面是将规则(3)应用于查询2的示例。然后应用规则(1)来完成解除关联过程。Aggregatede-association第三组规则描述了如何处理子查询中的Aggregate（即GroupBy）。和上一组一样，我们的指导思想还是：尽可能把Apply往下推，把Apply下面的operator往上抬。下式中，GA、FGA、F表示以GroupBy分组的聚合（GroupAgg），其中AA表示分组的列，FF表示聚合函数的列；G1FGF1表示没有分组的聚合（ScalarAgg）。img的规则集不像以前那么简单明了。让我们看一个例子来感受一下。下面是将rule(9)应用到Query1的结果：Rule(9)在Apply下推的同时将ScalarAgg变成GroupAgg，其中分组列是R的key，这里是CUSTOMER的主键c_custkey。“如果R没有主键或者唯一键，理论上我们可以在Scan的时候生成一个。为什么转换前后是等价的呢？在转换之前，我们对R的每一行做了一个ScalarAgg聚合计算，然后把聚合的结果进行合并；转换之后，我们先准备好所有要聚合的数据（这个叫做augment），然后用GroupAgg一次做所有的聚合，这也解释了为什么要用ALOJALOJ而不是原来的A×A×：在原来的ScalarAgg上，即使输入是空集，它也会输出NULL。如果我们在这里使用ALOJALOJ，我们会得到相同的行为（*）；否则，如果我们使用A×A×有个问题——不对应ORDERS的客户在结果中消失了！规则（8）处理GroupAgg，道理是一样的，只是还要保留原来的分组列。详见ScalarAggconversion*细心的读者可能会注意到生成的聚合函数规则(9)右边是F′F′，带单引号，暗示它可能与原来的聚合函数FF有些不同。那么在什么情况下会有所不同呢？本题比较深入，不感兴趣的同学可以略过。首先，让我们考虑一下。GroupAgg和ALOJALOJ的行为真的和转换前一样吗？事实上，他们不是。举一个反例：SELECTc_custkey,(SELECTCOUNT(*)FROMORDERSWHEREo_custkey=c_custkey)AScount_ordersFROMCUSTOMER想象一下：客户Eric没有订单，那么这个查询应该返回一行['Eric',0]。但是，当我们应用规则(9)进行转换时，我们得到['Eric',1]的值，这是错误的！为什么会这样？改造后，我们首先使用LeftOuterJoin准备中间数据（augment），然后使用GroupAgg进行聚合。LeftOuterJoin为客户Eric生成一个['Eric',NULL,NULL,...]行；在后面的GroupAgg中，聚合函数COUNT(*)认为Eric有1行数据，所以输出['Eric',1]。这是一个具有类似问题的更复杂的示例：SELECTc_custkeyFROMCUSTOMERWHERE200000<(SELECTMAX(IF_NULL(o_totalprice,42))--o_totalpricemaybeNULLFROMORDERSWHEREo_custkey=c_custkey)作为总结，问题的根源是：F(?)≠F({NULL})F(?)≠F({NULL})，这样的聚合函数FF就有这个问题。转换后的GroupAgg无法区分它看到的NULL数据是OuterJoin生成的还是原来存在的。有时，这两种情况会在预转换后的ScalarAgg中产生不同的结果。幸运的是，SQL标准中定义的聚合函数F(col)F(col)是可以的——它们都满足F(?)=F({NULL})F(?)=F({NULL})，我们只需要稍微改变FF来解决这个问题。例如1，将COUNT(*)替换为非空列（如主键）的Count，例如：COUNT(o_orderkey)；比如2，需要把MIN(IF_NULL(o_totalprice,42))分成两步怎么办：定义一个中间变量X，先用Project计算X=IF_NULL(o_totalprice,42)，然后去关联聚合函数MIN(X)。集合操作的分离最后一组优化规则是针对带有Union（对于UNIONALL）、Subtract（对于EXCEPTALL）和InnerJoin运算符的子查询。再次强调一下，我们的指导思想是：Apply尽量往下推，Apply下面的operator往上抬。下式中，××表示CrossJoin，?R.key?R.key表示根据RR的Key自然连接：r°e1°e2r°e1°e2。和之前一样，我们假设RR有主键或唯一键，如果没有，可以在Scan的时候加一个。请注意，这些规则与我们之前看到的规则有很大不同：RR在等式的右侧出现了两次。这样，我们要么复制这个子树，要么做一个DAG执行计划，反正会很麻烦。事实上，这套规则很少能派上用场。正如[2]中提到的，在TPC-HSchema下甚至很难用UnionAll写出有意义的子查询。还有几个我觉得比较重要的点，以FAQ的形式列在下面。?任何相关子查询都可以脱节吗？可以说是这样的。加入少量限制后，理论上可以证明任何关联的子查询都可以解除关联。证明方法见文献[1]、[3]。以[1]为例，其思路大致如下：对于任意一个查询关系树，首先从表达式中提取关联的子查询，用Apply运算符表示；逐步去除非基本关系运算符，首先通过等价变换去除Union和Subtract；进一步缩减算子集，去掉OuterJoin、ALOJALOJ、A?A?、A?A?；最后，去掉所有的A×A×，剩下的关系树只包含一些基本的关系算子，即去关联完成。另一方面，现实世界中用户使用的子查询大多比较简单，本文描述的规则可能已经覆盖了99%的场景。虽然理论上可以处理任何子查询，但实际上，没有已知的DBMS实现所有这些转换规则。?HyPer和SQLServer方法之间的相同点和不同点是什么？HyPer的理论涵盖了更多的解离场景。例如对于Join等各种算子，对应的等价变换规则在[3]中给出（作为例子，下图是OuterJoin的变换）。在[1]中，只是证明了这些情况可以归结为可处理的情况（实际上可以想象，一定不能处理）。另外一个细节是，在HyPer中也有这样一条规则：其中，D=ΠF(T2)∩A(T1)(T1)D=ΠF(T2)∩A(T1)(T1)，也就是说DistinctT1T1的项目结果（所谓的魔术集）。直接看方程比较晦涩，但是看下面的例子就很容易理解：图中，在做Apply之前，先获取需要应用的列的Distinct值集合，使用这些值做Apply，然后用普通的Join把apply的结果连接起来。这样做的好处是：如果要申请的数据有很多重复，那么DistinctProject之后需要申请的行数就大大减少了。这样即使后面不优化Apply，迭代执行的成本也会降低很多。?本文提到的转换规则应该用在RBO还是CBO中？也就是说，de-association之后的执行计划是否一定比de-association之前好呢？答案是，不一定。直观上，如果Apply左边的数据量比较少（比如只有1条数据），直接带入Apply右边的计算是比较好的做法。另一种情况是右边有合适的索引。在这种情况下，多次Apply的代价是不可接受的。所以把这些规则放到一个CBO优化器中比较合适，优化器根据成本估算来选择最优方案。甚至，在某些情况下，我们会用这些方程从右到左来做“附加相关”。这与使用HashJoin或NestedLoopJoin相同。实际上，NestedLoopJoin是Apply的特例。如果存在合适的索引，NestedLoopJoin比HashJoin更高效的情况并不少见。
