XMD

无语

一文详解 SQL 关联子查询

发表于 更新于 分类于 ， 阅读次数： 1
本文字数： 12k 阅读时长 ≈ 11 分钟

本文主要介绍什么是关联子查询以及如何将关联子查询改写为普通语义的 sql 查询。

在背景介绍中我们将讲讲常见的关联子查询的语义，关联子查询语法的好处以及其执行时对数据库系统的挑战。第二章中我们将主要介绍如何将关联子查询改写为普通的查询的形式，也就是解关联。第三章中我们会介绍解关联中的优化方法。

背景介绍

关联子查询是指和外部查询有关联的子查询，具体来说就是在这个子查询里使用了外部查询包含的列。

因为这种可以使用关联列的灵活性，将 sql 查询写成子查询的形式往往可以极大的简化 sql 以及使得 sql 查询的语义更加方便理解。下面我们通过使用 tpch schema 来举几个例子以说明这一点。tpch schema 是一个典型的订单系统的 database，包含 customer 表，orders 表，lineitem 表等，如下图：

假如我们希望查询出 “所有从来没有下过单的客户的信息”，那么我们可以将关联子查询作为过滤条件。使用关联子查询写出的 sql 如下。可以看到这里的 not exists 子查询使用列外部的列 c_custkey。

1
2
3
4
5
6
7
8
9
10
11
12
13
-- 所有从来没有下过单的客户的信息
select c_custkey
from
  customer
where
  not exists (
    select
      *
    from
      orders
    where
      o_custkey = c_custkey
  )

如果不写成上面的形式，我们则需要考虑将 customer 和 orders 两个表先进行 left join，然后再过滤掉没有 join 上的行，同时我们还需要 markorder 的每一行，使得本来就是 null 的那些。查询 sql 如下：

1
2
3
4
5
6
7
8
9
10
11
12
-- 所有从来没有下过单的客户的信息
select c_custkey
from
  customer
  left join (
    select
      distinct o_custkey
    from
      orders
  ) on o_custkey = c_custkey
where
  o_custkey is null

从这个简单的例子中就可以看到使用关联子查询降低了 sql 编写的难度，同时提高了可读性。

除了在 exists/in 子查询中使用关联列，关联子查询还可以出现在 where 中作为过滤条件需要的值。比如 tpch q17 中使用子查询求出一个聚合值作为过滤条件。

1
2
3
4
5
6
7
8
9
10
-- tpch q17
SELECT Sum(l1.extendedprice) / 7.0 AS avg_yearly 
FROM   lineitem l1, 
       part p
WHERE  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。

1
2
3
4
5
6
7
8
9
10
11
-- 客户以及对应的消费总额
select
  c_custkey,
  (
    select sum(o_totalprice)
    from
      orders
    where o_custkey = c_custkey 
    ）
from
  customer

更复杂一些的比如，我们希望查询每一个 customer 及其对应的在某个日期前已经签收的订单总额。利用关联子查询只需要做一些小的改变如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 为例子：

1
2
3
4
5
6
7
8
9
SELECT Sum(l1.extendedprice) / 7.0 AS avg_yearly 
FROM   lineitem l1, 
       part p
WHERE  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。

1
2
3
SELECT 0.2 * Avg(l2.quantity) 
FROM   lineitem l2
WHERE  l2.partkey = p.partkey  -- p.partkey是外部查询的列

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

如果数据库系统不支持查看逻辑树，可以通过 explain 命令查看物理计划，一般输出如下图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
+---------------+
| 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                    - Scalar
10                        -> 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 的输出就是下面这个查询的结果：

1
2
3
4
-- p.partkey = 25 时对应的子查询为
SELECT 0.2 * Avg(l2.quantity) 
FROM   lineitem l2
WHERE  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 就可以早点推到关联部位的下面。比如下面这个查询：

1
2
3
4
5
6
7
8
9
10
SELECT t1.c2
FROM
  t1
WHERE 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 等价列的利用

如果在子查询中存在和外部等价的列，那么可以先用这个列改写子查询中的关联列减少关联的地方从而简化查询。下面举一个简单的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Select t1.c2
From
  t1
Where
  t1.c3 < (
    Select min(t2.c3)
    From t2
    Where t1.c1 = t2.c1
    group by t1.c1
  )
  
-- 在子查询中使用t2.c1 代替 t1.ct进行简化

Select t1.c2
From
  t1
Where
  t1.c3 < (
    Select min(t2.c3)
    From t2
    Where t1.c1 = t2.c1
    group by t2.c1
  )

5 子查询相关的优化规则

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

  1. 经过 correaltedjoin 算子之后的行数与左子树的行数相同。
  2. enforcesinglerow 的输出为 1 行。
  3. 外部查询的关联列决定 (function dependency) correaltedjoin 的新增的输出列。
  4. assignuniqueid 产生的 key 具备 unique 的属性等，可用于之后化简 aggregation 和 group by 等。
  5. 子查询里的 sort 可以被裁剪。

另一个方面，在子查询的改写中，可以通过属性推导进行子查询的化简。比如：

  1. 如果原本外部查询就是 unique 的则没有别要增加 uniqueid 列。
  2. enforcesinglerow 的子节点的输出如果永远为 1 行则可以进行裁剪。
  3. 关联列在 project 上的子查询，如下图，在一些情况下改写为 exists 子查询。
1
2
3
4
5
6
7
8
9
10
11
12
13
select t1.orderkey,
  (
    select
      min(t1.orderkey)
    from
      orders t2
    where
      t2.orderkey > t1.orderkey
  )
from
  orders t1
order by
  1

6 需要注意的地方

子查询解关联中最需要注意的地方就是两个地方，一个是确保仅对外部查询进行加一列的操作，一个是对 null 值的处理。

计数错误

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

1
2
3
4
5
6
7
8
9
Select t1.c2
From
  t1
Where
  t1.c3 < (
    Select COUNT (*)
    From t2
    Where t1.c1 = t2.c1
  )

分布式下的 leftmarkjoin

另一个容易出错的地方是论文 Unnesting Arbitrary Queries [3] 中的 LeftMarkJoin，其输出的结果与 in 的语义相同。简单来说就是下面这个查询的结果。

1
2
3
4
5
6
7
8
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）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
-- sql 1
SELECT t1.c1
  FROM t1
 WHERE t1.c2 > ( 
   SELECT min(t2.c2) 
     FROM t2 
    WHERE t2.c1 = t1.c1
   );

-- sql 2
SELECT 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 年。

------------- 本文结束感谢您的阅读 -------------

相关文章