关于sql:一文详解SQL关联子查询

简介： 本文次要介绍什么是关联子查问以及如何将关联子查问改写为一般语义的sql查问。

本文次要介绍什么是关联子查问以及如何将关联子查问改写为一般语义的sql查问。

在背景介绍中咱们将讲讲常见的关联子查问的语义，关联子查问语法的益处以及其执行时对数据库系统的挑战。第二章中咱们将次要介绍如何将关联子查问改写为一般的查问的模式，也就是解关联。第三章中咱们会介绍解关联中的优化办法。

一背景介绍

关联子查问是指和内部查问有关联的子查问，具体来说就是在这个子查问里应用了内部查问蕴含的列。

因为这种能够应用关联列的灵活性，将sql查问写成子查问的模式往往能够极大的简化sql以及使得sql查问的语义更加不便了解。上面咱们通过应用tpch schema来举几个例子以阐明这一点。tpch schema是一个典型的订单零碎的database，蕴含customer表，orders表，lineitem表等，如下图：

如果咱们心愿查问出“所有素来没有下过单的客户的信息”，那么咱们能够将关联子查问作为过滤条件。应用关联子查问写出的sql如下。能够看到这里的not exists子查问应用列内部的列c_custkey。

-- 所有素来没有下过单的客户的信息select c_custkeyfrom customer where  not exists (    select      *    from      orders    where      o_custkey = c_custkey  )

如果不写成下面的模式，咱们则须要思考将customer和orders两个表先进行left join，而后再过滤掉没有join上的行，同时咱们还须要markorder的每一行，使得原本就是null的那些。查问sql如下：

-- 所有素来没有下过单的客户的信息select c_custkeyfrom  customer  left join (    select      distinct o_custkey    from      orders  ) on o_custkey = c_custkeywhere  o_custkey is null

从这个简略的例子中就能够看到应用关联子查问升高了sql编写的难度，同时进步了可读性。

除了在exists/in子查问中应用关联列，关联子查问还能够呈现在where中作为过滤条件须要的值。比方tpch q17中应用子查问求出一个聚合值作为过滤条件。

-- tpch q17SELECT Sum(l1.extendedprice) / 7.0 AS avg_yearly FROM   lineitem l1,        part pWHERE  p.partkey = l1.partkey        AND p.brand = 'Brand#44'        AND p.container = 'WRAP PKG'        AND l1.quantity < (SELECT 0.2 * Avg(l2.quantity)                          FROM   lineitem l2                         WHERE  l2.partkey = p.partkey);

除了呈现在where外面，关联子查问能够呈现在任何容许呈现单行(scalar)的中央，比方select列表里。如果咱们须要做报表汇总一些customer的信息，心愿对每一个customer查问他们的订单总额，咱们能够应用上面蕴含关联子查问的sql。

-- 客户以及对应的生产总额select  c_custkey,  (    select sum(o_totalprice)    from      orders    where o_custkey = c_custkey     ）from  customer

更简单一些的比方，咱们心愿查问每一个customer及其对应的在某个日期前曾经签收的订单总额。利用关联子查问只须要做一些小的扭转如下：

select  c_custkey,  (    select      sum(o_totalprice)    from      orders    where      o_custkey = c_custkey      and '2020-05-27' > (        select          max(l_receiptdate)        from          lineitem        where          l_orderkey = o_orderkey      )     ）from   customer

看了这些例子，置信大家都曾经感触到应用关联子查问带来的便捷。然而同时关联子查问也带来了执行上的挑战。为了计算关联后果的值（子查问的输入），须要iterative的执行形式。

以之前探讨过的tpch 17为例子：

SELECT Sum(l1.extendedprice) / 7.0 AS avg_yearly FROM   lineitem l1,        part pWHERE  p.partkey = l1.partkey        AND p.brand = 'Brand#44'        AND p.container = 'WRAP PKG'        AND l1.quantity < (SELECT 0.2 * Avg(l2.quantity)                          FROM   lineitem l2                         WHERE  l2.partkey = p.partkey);

这里的子查问局部应用了内部查问的列 p.partkey。

SELECT 0.2 * Avg(l2.quantity) FROM   lineitem l2WHERE  l2.partkey = p.partkey  -- p.partkey是内部查问的列

优化器将这个查问示意为如下图的逻辑树：

如果数据库系统不反对查看逻辑树，能够通过explain命令查看物理打算，个别输入如下图：

+---------------+| Plan Details  |+---------------+ 1- Output[avg_yearly] avg_yearly := expr 2    -> Project[] expr := (`sum` / DOUBLE '7.0') 3        - Aggregate sum := `sum`(`extendedprice`) 4            -> Filter[p.`partkey` = l1.`partkey` AND `brand` = 'Brand#51' AND `container` = 'WRAP PACK' AND `quantity` < `result`] 5                - CorrelatedJoin[[p.`partkey`]] 6                    - CrossJoin 7                        - TableScan[tpch:lineitem l1] 8                        - TableScan[tpch:part p] 9                    - Scalar10                        -> Project[] result := (DOUBLE '0.2' * `avg`)11                            - Aggregate avg := `avg`(`quantity`)12                                -> Filter[(p.`partkey` = l2`partkey`)] 13                                    - TableScan[tpch:lineitem l2]

咱们将这个连贯内部查问和子查问的算子叫做CorrelatedJoin(也被称之为lateral join, dependent join等等。它的左子树咱们称之为内部查问(input)，右子树称之为子查问(subquery)。子查问中呈现的内部的列叫做关联列。在栗子中关联列为p.partkey。

例子中对应的逻辑打算和相干定义如下图所示，explain返回后果中第6-8行为内部查问，9-13行为子查问，关联部位在子查问中第12行的filter。

这个算子的输入等价于一种iterative的执行的后果。也就将左子树的每一行关联列的值带入到右子树中进行计算并返回一行后果。有些相似将子查问看成一个user defined function（udf），内部查问的关联列的值作为这个udf的输出参数。须要留神的是，咱们须要子查问是确定的，也就是对同样值的关联列，每次运行子查问返回的后果应该是确定的。

在上图的栗子中，如果内部查问有一行的p.partkey的值为25，那么这一行对应的correlatedjoin的输入就是上面这个查问的后果：

-- p.partkey = 25 时对应的子查问为SELECT 0.2 * Avg(l2.quantity) FROM   lineitem l2WHERE  l2.partkey = 25

须要留神的是，如果计算结果为空集，则返回一行null。而如果运行中子查问返回了超过一行的后果，应该报运行时谬误。在逻辑打算里，用enforcesinglerow这个node来束缚。

从下面的介绍中能够发现，CorrelatedJoin这个算子突破了以往对逻辑树自上而下的执行模式。一般的逻辑树都是从叶子节点往根结点执行的，然而CorreltedJoin的右子树会被带入左子树的行的值重复的执行。

correlatedjoinnode的输入就是在内部查问的后果上减少了一列，然而能够看到这种iterative的执行形式的复杂度和将内部查问和子查问关联产生之前的那局部树进行cross join的复杂度雷同。

同时，这样iterative的执行形式对分布式数据库系统来说是很大的挑战。因为须要批改执行时调度的逻辑。而且咱们能够看到，这样的执行形式如果不进行后果的缓存，会进行很多反复后果的计算。

传统的优化器的优化规定没有特地的针对Correlatedjoin node进行解决，为了反对关联子查问的这种iterative的模式，在优化器初始阶段就会把Correlatedjoin进行等价转换，转换过后的逻辑树用join，aggregation等一般算子来进行关联子查问后果的计算。这个过程被称为解关联（decorrelation/unnesting）。上面一章咱们次要介绍常见的解关联的形式。

二常见的解关联形式

为了不便起见，咱们在这一章只探讨scalar关联子查问，就是会输入一列值的关联子查问。

在探讨如何解关联之前，咱们总结一下关联子查问的输入有以下特点：

correlated join算子的计算结果为在内部查问上减少一列。
减少的那一列的后果为将内部查问关联列的值带入子查问计算得出的。当计算结果超过一行则报错，计算结果为空则补充null。
不同于join算子，correlated join不扭转内部查问的其余列（不少行也不收缩）。

解开关联的关键在于使得子查问取得对应的内部查问的行的值。

体现在打算上，就是将correleted join算子向右下推到产生关联的部位的上面。当correlated join算子的左右子树没有关联列的时候，correlated join算子就能够转换成join算子。这样子查问就通过和内部查问join的形式取得了关联列的值，从而能够自上而下计算，回到本来的计算形式。如下图，下图中rest subquery为在关联产生部位之前的子查问局部。当correlated join 推到产生关联的部位之下，就能够转换为一般的join了。

correlated join推过的那些算子都是须要进行改写，以放弃等价性（上图的栗子中subquery变为了subquery’）。

1 下推规定

论文Orthogonal Optimization of Subqueries and Aggregation[2]给出了将correlatedjoin_算子下推到其余算子（filter，project，aggregation，union 等）上面的的等价转换规则。然而文中的correlatedjoin_算子是会过滤内部查问的行数的，相似于inner join（论文中称为）。咱们这里探讨更加general的相似于left join的 correlatedjoin (论文中称为 )，并探讨如果要保障内部查问行数不被过滤须要做哪些改写。

因为篇幅限度，上面咱们只介绍下推到filter，project，aggregation算子上面的等价规定。

为了简略起见，咱们在逻辑树中去掉了enforcesinglerow。

转换1 无关联时转换为join

回顾前文所说，correlated join算子的左子树为input，右子树为subquery。当correlated join的左右子树没有关联的时候，这个时候对外部查问的每一行，子查问的后果都是雷同的。

咱们就能够把correlated join转换成一般的没有join criteria的leftjoin算子。

注：须要在subquery上增加enforcesinglerow来保障join语义和correlatedjoin雷同（不会造成input的收缩）。

转换2 简略关联条件时转换为join

当correlated join右子树中最下面的节点为一个关联filter而他的上面无关联时，能够间接将这个filter放到left join的条件中，也能够了解为filter上提。如下图：

转换3 下推穿过filter

论文中correlatedjoin*能够间接推过filter。如果须要下推的为correlatedjoin，则须要对filter进行改写，改写成带有case when的project。当subquery的行不满足filter的条件时应输入null。

转换4 下推穿过project

correlated join下推过project，须要在project中增加input的输入列。

转换5 下推穿过aggregation

correlated join下推到带有group by的aggregation时，须要对aggregation进行改写。

改写为在aggregation的group by的列中减少内部查问的全部列。这里要求内部查问肯定有key，如果没有则须要生成长期的key。生成能够的算子在图中为assignuniqueid算子。

如果aggregation为全局的，那么还须要进行额定的解决。如下图：

correlated join下推到全局aggregation的时候，须要对aggregation减少input的列(以及key)作为group by的列。这个下推规定还须要一个前提，那就是aggregation函数须要满足满足个性 agg(Ø)=agg(null) 。这个的意思就是aggragtion函数须要对空集和对null的计算结果是雷同的。

注：在mysql和AnalyticDB for MySQL（阿里云自研的云原生数据仓库[1]，兼容mysql语法，下文简称ADB）的语法里，sum, avg等都不满足这个个性。空集的平均值为0, 而对蕴含null值的任意汇合取平均值后果为null不为0。所以须要mark子查问里的每一行，对空集进行特地的解决，在这里就不开展解释了。

论文Orthogonal Optimization of Subqueries and Aggregation[2]重复使用下面这些规定进行correlatedjoin的下推，直到correlatedjoin能够转换为一般的join。

带入之前的tpch q17的栗子中，咱们先应用将correlated join推到子查问中的project上面，查问变为：

而后下推穿过这个agg，并改写这个agg，如下图：

这里咱们疏忽 avg(Ø)!=avg(null) 。如果思考这个状况，则须要mark子查问全副的行，在correlated join之后依据子查问的后果联合mark的值对空集进行特地解决（将mark了的行的值从null变为0）。感兴趣的读者能够参考下一张中q17的最终打算。

接着间接调用之前的规定2，上提这个filter。这样这个查问就变为一般的没有关联的查问了。

2 后果复用

回顾上一节所说，子查问的查问后果是带入每一行关联列的值之后计算得出的，那么不言而喻雷同值的关联列带入子查问中计算出的后果是完全相同的。在下面的栗子中，对同样的p.partkey，correlatedjoin输入的子查问的后果是相等的。如下图中内部查问partkey为25的话产生的关联子查问时是完全相同的，那么后果也天然雷同。

15年Newmann的论文Unnesting Arbitrary Queries[3]介绍了一种办法就是先对外部查问里关联列取distinct，再将correlated join返回的值和本来的内部查问依据关联列进行left join，如下图所示：

这里的not distinct join的条件对应mysql外面的<=>，null<=>null的后果为true，是能够join到一起的。

带入到之前的例子中如下图所示，对外部查问的关联列partkey先进行distinct，而后带入子查问计算结果，最初再通过join将对应的后果接到本来的内部查问上。

如果进行了上述转换，那么咱们能够认为新的input的关联列永远是distinct的。而当初的correlatedjoin*算子能够容许input的列被过滤。这样做的益处除了对于雷同的列不进行反复的子查问的计算之外，次要还有上面两个：

新的内部查问是永远有key的，因为distinct过了。
correlatedjoin*算子因为过滤内部查问的列，所以它的下推更为简略（不须要assignuniqueid，不须要保留全副行）。

进行上述的转换后，紧接着再套用之前的等价下推规定，咱们又能够将correlatedjoin*下推到一个左右子树没有关联的中央，从而改写为inner join。

如果依照Unnesting Arbitrary Queries[3]的办法进行解关联，须要将input的一部分后果进行复用，这个复用须要执行引擎的反对。须要留神的是，当零碎不反对复用的时候，咱们须要执行两次input的子树（如下图），这个时候就须要input这颗子树的后果是deterministic的，否则无奈用这个办法进行解关联。

三关联子查问的优化

在ADB的优化器中，逻辑打算会依据每一条转换规则进行匹配和转换，也就意味着在关联解开之后不须要关怀解关联产生的打算的效率而将它间接交给后续的优化规定。然而事实并不是那么的美妙，因为后续规定不够齐备，以及解关联之后失落了内部查问和子查问之间的关系，咱们心愿在解关联的时候就将打算尽可能优化。

1 exists/in/filter关联子查问

在之前的章节中为了简化，咱们只探讨了scalar子查问。因为exists/in这些子查问都能够改写成scalar子查问。比方将exists改写为count(*) > 0

然而能够看到，如果子查问的返回后果被用来过滤内部查问的行，实际上会简化整个解关联的过程。所以咱们对exists/in这样的子查问进行非凡解决，在语法解析时就进行辨别。在解关联的过程中，如果能够应用semijoin/antijoin算子进行解关联则间接解开关联，否则后续会转化成scalar子查问也就是correlatedjoin的模式。

2 关联条件的上提

看到这里会发现，随着correlatedjoin的下推，这个逻辑树会变得更加简单，所以咱们在下推之前会在子查问外部进行关联算子的上提。当这个逻辑就是产生关联的算子越高，correlatedjoin就能够早点推到关联部位的上面。比方上面这个查问：

SELECT t1.c2FROM  t1WHERE t1.c2 < (    SELECT 0.2 * max(t2.x)    FROM      t2    WHERE t2.c1 = t2.c1   GROUP BY t2.c1  );

这里因为t2.c1 = t2.c1能够推到agg 下面(因为对于子查问这是一个在group by列上的条件)，咱们就能够进行上面的转换。先把关联的filter上提（有时须要改写），这样就只有把correlatedjoin推过filter，调用转换2就能够了。

更具体的例子就是前文提到的tpch q17。这里的scalar子查问作用在过滤条件中的状况也能够进行进一步改写。

下图为依照之前说的实践下推correlated join并改写为left join之后的逻辑打算。

而因为这个scalar子查问是作为filter条件的，这种状况下子查问没有后果返回为null对应的内部查问是肯定会被过滤掉的。所以correlatedjoin能够间接转为 correlatedjoin*，再加上将filter进行上提，咱们能够失去上面的打算。这样改写的益处是能够在join前先进行agg(early agg)。害处就是如果不小心解决，很容易造成语义不等价造成count bug。

3 代价相干的子查问优化

利用window算子解关联

回顾到目前为止咱们讲的这些，是不是印象最粗浅的在于correlatedjoin算子是在内部查问上减少一列。而他的这个行为和window算子相似。window算子的语义就是不扭转输出的行数，只是在每一行上减少一个在window的frame里计算出的值。所以咱们能够利用window算子进行解关联，如果感兴趣能够参考这两篇论文Enhanced Subquery Optimizations in Oracle[4]和 WinMagic : Subquery Elimination Using Window Aggregation[5]。

window解关联的改写就是在内部查问蕴含子查问中全副的表和条件时，能够间接应用window将子查问的后果拼接到内部查问上。他益处是节约了很多tablescan。比如说tpch q2。能够进行上面的改写：

这里之所能改写成window是因为内部查问蕴含了外部查问全副的表和条件。而且agg函数min也满足个性agg(Ø)=agg(null) （如果不满足，须要对行进行mark以及用case when 改写输入）。

能够看到改写后tablescan的数量大大减少。更进一步，优化器前面的优化规定会进行依据primarykey的信息以及agg函数的个性进行join 和 window的程序替换从而进一步缩小window算子输出的数据量（filter-join pushdown）。

这些益处很多文章里都说了。咱们在这里讨论一下这样改写的不好的中央：

比方在pk未能显示提供/agg的函数对duplicates敏感的状况下，window算子会阻挡filter-join的下推，从而打断了joingraph造成join的两头后果变大。
如果改写为两棵子树的join，filter-join能够下推到其中一颗子树上。而进行window改写后，filter-join无奈下推。
在pipeline的执行模型下/&应用cte的状况下，扫表取得的收益无限。
传统优化器对join&agg的优化解决/优化规定比对window好/丰盛很多。

综上所述，什么时候应用window进行改写关联子查问须要进行收益和代价的预计。

CorrelatedJoin在内部查问中的下推

在将correlatedJoin往子查问方向下推之前，咱们会将correlatedjoin先在内部查问中进行下推(比方推过cross join等)。

这样做是因为correlatedJoin永远不会造成数据的收缩，所以实践上应该早点做。但实际上correlatejoin下推后也可能切割joingraph，从而造成和window改写差不多的问题。

4 等价列的利用

如果在子查问中存在和内部等价的列，那么能够先用这个列改写子查问中的关联列缩小关联的中央从而简化查问。上面举一个简略的例子。

Select t1.c2From  t1Where  t1.c3 < (    Select min(t2.c3)    From t2    Where t1.c1 = t2.c1   group by t1.c1  )  -- 在子查问中应用t2.c1 代替 t1.ct进行简化Select t1.c2From  t1Where  t1.c3 < (    Select min(t2.c3)    From t2    Where t1.c1 = t2.c1   group by t2.c1  )

5 子查问相干的优化规定

一个方面correaltedjoin这个算子的个性给了咱们一些进行优化的信息。上面举一些例子：

通过correaltedjoin算子之后的行数与左子树的行数雷同。
enforcesinglerow的输入为1行。
内部查问的关联列决定(function dependency)correaltedjoin的新增的输入列。
assignuniqueid产生的key具备unique的属性等，可用于之后化简aggregation和group by等。
子查问里的sort能够被裁剪。

另一个方面，在子查问的改写中，能够通过属性推导进行子查问的化简。比方：

如果本来内部查问就是unique的则没有别要减少uniqueid列。
enforcesinglerow的子节点的输入如果永远为1行则能够进行裁剪。
关联列在project上的子查问，如下图，在一些状况下改写为exists子查问。

select t1.orderkey,  (    select      min(t1.orderkey)    from      orders t2    where      t2.orderkey > t1.orderkey  )from  orders t1order by  1

6 须要留神的中央

子查问解关联中最须要留神的中央就是两个中央，一个是确保仅对外部查问进行加一列的操作，一个是对null值的解决。

计数谬误

文献中常提到的是一个经典的解关联容易出错的中央。比方上面的查问，咱们有一个前提条件就是t1.c3全都是小于0的。在这个状况下子查问参加的关联条件应该是没有任何过滤度的。而改写成inner join则会过滤掉一些行。语义上是不等价的。

Select t1.c2From  t1Where  t1.c3 < (    Select COUNT (*)    From t2    Where t1.c1 = t2.c1  )

分布式下的leftmarkjoin

另一个容易出错的中央是论文Unnesting Arbitrary Queries[3]中的LeftMarkJoin，其输入的后果与in的语义雷同。简略来说就是上面这个查问的后果。

select t1.c1     in ( select      t2.c1    from      t2)from  t1

这个查问对应的逻辑打算如下：

其输入后果为在左子树后果上加一列in的后果，in的后果有三种可能true,false和null。

在分布式环境下，对这个算子进行repartition和落盘很容易造成和null值相干的计算出错。

举一个简略的例子，当leftmarkjoin为repartition的执行形式时，会对左表和右表的数据依据c1的hash值进行重散布reshuffle。那么t1.c1中为null的行会被shuffle到同一台executor上。这个时候如果右表没有数据被shuffle到这台机器上，那么这一台executor并不知道对于null的这些行该输入null还是false。因为null in空集的后果为false，而null in 任何非空集合的后果为null。此时这台executor并不知道右表是否为空。

解开关联后的效率

在最开始的时候咱们提到了iterative的执行形式，这里咱们须要阐明对有些关联子查问来说即便关联被解开为join/agg等算子，计算查问后果也须要一个cross join的代价。

比方上面这个两个查问，第一个是咱们常见的关联子查问的样子，能够转换成inner join + early agg的模式。而第二个解开关联后则会变成一个left join on非等值条件（代价同cross join）。

-- sql 1SELECT t1.c1  FROM t1 WHERE t1.c2 > (    SELECT min(t2.c2)      FROM t2     WHERE t2.c1 = t1.c1   );-- sql 2SELECT t1.c1  FROM t1 WHERE t1.c2 > (    SELECT min(t2.c2)      FROM t2     WHERE t2.c1 > t1.c1   );

sq1解开关联后的打算如下：

sql2解开关联后的打算如下：

对于sql1来说，从语义上了解，内部查问的每一行带入子查问里扫过的行都是没有重叠的，所以代价和innerjoin on等值条件是一样的。再加上同样的内部行对应的子查问中min的后果雷同能够利用early agg从而能够进一步优化。

对于sql2来说，从语义上了解，内部查问的每一行都必须要带入子查问中扫过所有的行能力判断在满足t2.c1 > t1.c1这个条件下的子查问的输入应该是什么。为了计算出后果这个代价是无奈通过优化节约的。然而对同样的t1.c1输入始终是雷同的，Unnesting Arbitrary Queries[3]中的后果复用依然能够产生优化。

参考文献
[1] https://www.aliyun.com/product/ApsaraDB/ads
[2] Galindo-Legaria，César和Milind Joshi。“子查问和聚合的正交优化。” ACM SIGMOD记录30.2（2001）：571-581。
[3] Neumann，Thomas和Alfons Kemper。“勾销嵌套任意查问。” 商业，技术和网络数据库系统（BTW 2015）（2015年）。
[4]贝拉姆康达（Bellamkonda），斯里坎特（Srikanth）等。“加强了Oracle中的子查问优化。” VLDB基金会论文集2.2（2009）：1366-1377
[5] Zuzarte，Calisto等人。“ Winmagic：应用窗口聚合打消子查问。” 2003 ACM SIGMOD国内数据管理国内会议论文集。2003。
[6] Neumann，Thomas，Viktor Leis和Alfons Kemper。“联接的残缺故事（inHyPer）。” 商业，技术和网络数据库系统（BTW 2017）（2017）。
[7]加利福尼亚州加林多-莱加里亚（Galindo-Legaria），参数化查问和嵌套等效项。技术报告，Microsoft，2001年。MSR-TR-2000-31，2000年。
原文链接
本文为阿里云原创内容，未经容许不得转载。

一 背景介绍

二 常见的解关联形式