SQL 子查询怎么优化？写的很深的这种！

朴灿烈づ我的快乐病毒、 2023-01-13 12:54 46阅读 0赞

点击上方“程序猿技术大咖”，关注并选择“设为星标”

回复“加群”获取入群讨论资格！

**子查询** （Subquery）的优化一直以来都是 SQL 查询优化中的难点之一。关联子查询的基本执行方式类似于 Nested-Loop，但是这种执行方式的效率常常低到难以忍受。当数据量稍大时，必须在优化器中对其进行**去关联化** （Decoorelation 或 Unnesting），将其改写为类似于 Semi-Join 这样的更高效的算子。

前人已经总结出一套完整的方法论，理论上能对任意一个查询进行去关联化。本文结合 SQL Server 以及 HyPer 的几篇经典论文，由浅入深地讲解一下这套去关联化的理论体系。它们二者所用的方法大同小异，基本思想是想通的。

# 子查询简介 #

子查询是定义在 SQL 标准中一种语法，它可以出现在 SQL 的几乎任何地方，包括 SELECT, FROM, WHERE 等子句中。

总的来说，子查询可以分为**关联子查询（Correlated Subquery）** 和**非关联子查询（Non-correlated Subquery）** 。后者非关联子查询是个很简单的问题，最简单地，只要先执行它、得到结果集并物化，再执行外层查询即可。下面是一个例子：

SELECT c_count, count(*) AS custdist
    FROM (
             SELECT c_custkey, count(o_orderkey) AS c_count
             FROM CUSTOMER
                      LEFT OUTER JOIN ORDERS ON c_custkey = o_custkey
                 AND o_comment NOT LIKE '%pending%deposits%'
             GROUP BY c_custkey
         ) c_orders
    GROUP BY c_count
    ORDER BY custdist DESC, c_count DESC;

**非关联子查询不在本文讨论范围之列** ，除非特别声明，以下我们说的子查询都是指关联子查询。

关联子查询的特别之处在于，其本身是不完整的：**它的闭包中包含一些外层查询提供的参数**。显然，只有知道这些参数才能运行该查询，所以我们不能像对待非关联子查询那样。

根据产生的数据来分类，子查询可以分成以下几种：

**标量（Scalar-valued）** 子查询：输出一个只有一行一列的结果表，这个标量值就是它的结果。如果结果为空（0 行），则输出一个 NULL。但是注意，超过 1 行结果是不被允许的，会产生一个运行时异常。

标量子查询可以出现在任意包含标量的地方，例如 SELECT、WHERE 等子句里。下面是一个例子：

SELECT c_custkey
    FROM CUSTOMER
    WHERE 1000000 < (
        SELECT SUM(o_totalprice)
        FROM ORDERS
        WHERE o_custkey = c_custkey
    )

Query 1: 一个出现在 WHERE 子句中的标量子查询，关联参数用红色字体标明了

SELECT o_orderkey, (
        SELECT c_name
        FROM CUSTOMER
        WHERE c_custkey = o_custkey
    ) AS c_name FROM ORDERS

Query 2: 一个出现在 SELECT 子句中的标量子查询

**存在性检测（Existential Test）** 子查询：特指 EXISTS 的子查询，返回一个布尔值。如果出现在 WHERE 中，这就是我们熟悉的 Semi-Join。当然，它可能出现在任何可以放布尔值的地方。

SELECT c_custkey
    FROM CUSTOMER
    WHERE c_nationkey = 86 AND EXISTS(
            SELECT * FROM ORDERS
            WHERE o_custkey = c_custkey
        )

Query 3: 一个 Semi-Join 的例子

**集合比较（Quantified Comparision）** 子查询：特指 IN、SOME、ANY 的查询，返回一个布尔值，常用的形式有：`x = SOME(Q)` （等价于 `x IN Q`）或 `X <> ALL(Q)`（等价于 `x NOT IN Q`）。同上，它可能出现在任何可以放布尔值的地方。

SELECT c_name
    FROM CUSTOMER
    WHERE c_nationkey <> ALL (SELECT s_nationkey FROM SUPPLIER)

Query 4: 一个集合比较的非关联子查询

# 原始执行计划 #

我们以 Query 1 为例，直观地感受一下，为什么说关联子查询的去关联化是十分必要的。

下面是 Query 1 的未经去关联化的原始查询计划（Relation Tree）。与其他查询计划不一样的是，我们特地画出了表达式树（Expression Tree），可以清晰地看到：子查询是实际上是挂在 Filter 的条件表达式下面的。

![03c0b4bc4217ff6d4bbccbfe5725733a.png][]

实际执行时，查询计划执行器（Executor）在执行到 Filter 时，调用表达式执行器（Evaluator）；由于这个条件表达式中包含一个标量子查询，所以 Evaluator 又会调用 Executor 计算标量子查询的结果。

**这种 Executor - Evaluator - Executor 的交替调用十分低效** ！考虑到 Filter 上可能会有上百万行数据经过，如果为每行数据都执行一次子查询，那查询执行的总时长显然是不可接受的。

# Apply 算子 #

上文说到的 Relation - Expression - Relation 这种交替引用不仅执行性能堪忧，而且，对于优化器也是个麻烦的存在——我们的优化规则都是在匹配并且对 Relation 进行变换，而这里的子查询却藏在 Expression 里，令人无从下手。

为此，在开始去关联化之前，我们引入 Apply 算子：

**Apply 算子** （也称作 Correlated Join）接收两个关系树的输入，与一般 Join 不同的是，Apply 的 Inner 输入（图中是右子树）是一个带有参数的关系树。

Apply 的含义用下图右半部分的集合表达式定义：对于 Outer Relation RR 中的每一条数据 rr，计算 Inner Relation E(r)E(r)，输出它们连接（Join）起来的结果 r⊗E(r)r⊗E(r)。Apply 的结果是所有这些结果的并集（本文中说的并集指的是 Bag 语义下的并集，也就是 UNION ALL）。

![724adb2655bea9e60f20b12a1d6494b1.png][]

> Apply 是 SQL Server 的命名，它在 HyPer 的文章中叫做 Correlated Join。它们是完全等价的。考虑到 SQL Server 的文章发表更早、影响更广，本文中都沿用它的命名。

根据连接方式（⊗⊗）的不同，Apply 又有 4 种形式：

*  **Cross Apply** A×A×：这是最基本的形式，行为刚刚我们已经描述过了；
 *  **Left Outer Apply** ALOJALOJ：即使 E(r)E(r) 为空，也生成一个 r∘\{NULLs\}r∘\{NULLs\}。
 *  **Semi Apply** A∃A∃：如果 E(r)E(r) 不为空则返回 rr，否则丢弃；
 *  **Anti-Semi Apply** A∄A∄：如果 E(r)E(r) 为空则返回 rr，否则丢弃；

我们用刚刚定义的 Apply 算子来改写之前的例子：把子查询从 Expression 内部提取出来。结果如下：

![68e64fabb7dc2217368123fc1cafb602.png][]

上面的例子中，我们可以肯定 Scalar Agg 子查询**有且只有** 一行结果，所以可以直接转成 Apply。但某些情况下，可能无法肯定子查询一定能返回 0 或 1 行结果（例如，想象一下 Query 2 如果 c\_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 算子。

![f23902e6c7e0443dc499b51466e899b5.png][]

# 基本消除规则 #

第一组规则是最基本的规则，等式中的 ⊗⊗ 说明它不限制连接类型，可以是 \{×,LOJ,∃,∄\}\{×,LOJ,∃,∄\} 中的任意一个。

![c939100d63032705242748aaa6b29e61.png][]

这两条规则是非常显而易见的，翻译成大白话就是：如果 Apply 的右边不包含来自左边的参数，那它就和直接 Join 是等价的。

下面是对 Query 3 应用规则 (2) 的例子：

![3f7d13f1338d2a11acf3c2083593abb1.png][]

# Project 和 Filter 的去关联化 #

第二组规则描述了如何处理子查询中的 Project 和 Filter，其思想可以用一句话来描述：**尽可能把 Apply 往下推、把 Apply 下面的算子向上提** 。

![914222d56df234976bd23bb20f8c1328.png][] ![83beca46f7a7560830cc565f628a3b41.png][]

注意这些规则仅处理 Cross Apply 这一种情况。其他 3 种 Apply 的变体，理论上都可以转换成 Cross Apply，暂时我们只要知道这个事实就可以了。

你可能会问：通常我们都是尽可能把 Filter、Project 往下推，为什么这里会反其道而行呢？关键在于：Filter、Project 里面原本包含了带有关联变量的表达式，但是把它提到 Apply 上方之后，**关联变量就变成普通变量了！** 这正是我们想要的。

我们稍后就会看到这样做的巨大收益：**当 Apply 被推最下面时，就可以应用第一组规则，直接把 Apply 变成 Join** ，也就完成了子查询去关联化的优化过程。

下面是对 Query 2 应用规则 (3) 的例子。之后再应用规则 (1)，就完成了去关联化过程。

![9f81431774604df22d26dd2db6b16159.png][]

# Aggregate 的去关联化 #

第三组规则描述如何处理子查询中的 Aggregate（即 Group By）。和上一组一样，我们的指导思想仍然是：**尽可能把 Apply 往下推、把 Apply 下面的算子向上提** 。

下面等式中，GA,FGA,F 表示带有 Group By 分组的聚合（Group Agg），其中 AA 表示分组的列，FF 表示聚合函数的列；G1FGF1 表示不带有分组的聚合（Scalar Agg）。

![5ca4f014d8fa42cc3a5c8a69b5fb21d2.png][]

这一组规则不像之前那么简单直白，我们先看一个例子找找感觉。下面是对 Query 1 运用规则 (9) 的结果：

![a97a0cb0b1fe6f01a9014f9c1ae67b1f.png][]

规则 (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，道理也是一样的，只不过原来的分组列也要留着。

**ScalarAgg 转换中的细节＊**

细心的读者可能注意到，规则 (9) 右边产生的聚合函数是 F′F′，多了一个单引号，这暗示它和原来的聚合函数 FF 可能是有些不同的。那什么情况下会不同呢？这个话题比较深入了，不感兴趣的同学可以跳过。

首先我们思考下，GroupAgg 以及 ALOJALOJ 的行为真的和变换前一模一样吗？其实不然。举个反例：

SELECT c_custkey, (
        SELECT COUNT(*)
        FROM ORDERS
        WHERE o_custkey = c_custkey
    ) AS count_orders
    FROM CUSTOMER

设想一下：客户 Eric 没有任何订单，那么这个查询应当返回一个 `['Eric', 0]` 的行。但是，当我们应用了规则 (9) 做变换之后，却得到了一个 `['Eric', 1]` 的值，结果出错了！

为何会这样呢？变换之后，我们是先用 LeftOuterJoin 准备好中间数据（augment），然后用 GroupAgg 做聚合。LeftOuterJoin 为客户 Eric 生成了一个 `['Eric', NULL, NULL, ...]` 的行；之后的 GroupAgg 中，聚合函数 `COUNT(*)` 认为 Eric 这个分组有 1 行数据，所以输出了 `['Eric', 1]`。

下面是个更复杂的例子，也有类似的问题：

SELECT c_custkey
    FROM CUSTOMER
    WHERE 200000 < (
        SELECT MAX(IF_NULL(o_totalprice, 42)) -- o_totalprice may be NULL
        FROM ORDERS
        WHERE o_custkey = c_custkey
    )

作为总结，问题的根源在于：F(∅)≠F(\{NULL\})F(∅)≠F(\{NULL\})，这样的聚合函数 FF 都有这个问题。

**变换后的 GroupAgg 无法区分它看到的 NULL 数据到底是 OuterJoin 产生的，还是原本就存在的** ，有时候，这两种情形在变换前的 ScalarAgg 中会产生不同的结果。

幸运的是，SQL 标准中定义的聚合函数 F(col)F(col) 都是 OK 的——它们都满足 F(∅)=F(\{NULL\})F(∅)=F(\{NULL\})，我们只要对 FF 稍加变换就能解决这个问题。

*  对于例子一，将 `COUNT(*)` 替换成一个对非空列（例如主键）的 Count 即可，例如：`COUNT(o_orderkey)`；
 *  对于例子二，需要把 `MIN(IF_NULL(o_totalprice, 42))` 分成两步来做：定义中间变量`X`，先用 Project 计算 `X = IF_NULL(o_totalprice, 42)`，再对聚合函数 `MIN(X)` 进行去关联化即可。

# 集合运算的去关联化 #

最后一组优化规则用来处理带有 Union（对应 `UNION ALL`）、Subtract（对应 `EXCEPT ALL`） 和 Inner Join 算子的子查询。再强调一遍，我们的指导思想是：**尽可能把 Apply 往下推、把 Apply 下面的算子向上提** 。

下面的等式中，×× 表示 Cross Join，⋈R.key⋈R.key 表示按照 RR 的 Key 做自然连接：r∘e1∘e2r∘e1∘e2 。和之前一样，我们假设 RR 存在主键或唯一键，如果没有也可以在 Scan 的时候加上一个。

![81e843c4d59ab64e1dea465ceca28eae.png][] ![e148b93f4a9705f8dbbd0b1f5bfde44e.png][]

注意到，这些规则与之前我们见过的规则有个显著的不同：等式右边 RR 出现了两次。这样一来，要么我们把这颗子树拷贝一份，要么做成一个 DAG 的执行计划，总之会麻烦许多。

事实上，这一组规则很少能派上用场。在 \[2\] 中提到，在 TPC-H 的 Schema 下甚至很难写出一个带有 Union All 的、有意义的子查询。

# **其他** #

有几个我认为比较重要的点，用 FAQ 的形式列在下面。

**► 是否任意的关联子查询都可以被去关联化？**

可以说是这样的，在加上少量限定之后，理论上可以证明：任意的关联子查询都可以被去关联化。

证明方法在 \[1\]、\[3\] 中都有提及。以 \[1\] 中为例，思路大致是：

1.  对于任意的查询关系树，首先将关联子查询从表达式中提取出来，用 Apply 算子表示；
2.  一步步去掉其中非基本关系算子，首先，通过等价变换去掉 Union 和 Subtract；
3.  进一步缩小算子集合，去掉 OuterJoin、ALOJALOJ、A∃A∃、A∄A∄；
4.  最后，去掉所有的 A×A×，剩下的关系树仅包含基本的一些关系算子，即完成了去关联化。

另一方面，现实世界中用户使用的子查询大多是比较简单的，本文中描述的这些规则可能已经覆盖到 99% 的场景。虽然理论上任意子查询都可以处理，但是实际上，没有任何一个已知的 DBMS 实现了所有这些变换规则。

**► HyPer 和 SQL Server 的做法有什么异同？**

HyPer 的理论覆盖了更多的去关联化场景。例如各种 Join 等算子，\[3\] 中都给出了相应的等价变换规则（作为例子，下图是对 Outer Join 的变换）。而在 \[1\] 中仅仅是证明了这些情况都可以被规约到可处理的情形（实际上嘛，可想而知，一定是没有处理的）。

![7187345222ccec092be33846c65f635a.png][]

另一个细节是，HyPer 中还存在这样一条规则：

![96017a499169316f5d535019909def4e.png][]

其中，D=ΠF(T2)∩A(T1)(T1)D=ΠF(T2)∩A(T1)(T1)，表示对 T1T1 的 Distinct Project 结果（所谓的 *Magic Set*）。直接看等式比较晦涩，看下面的例子就容易理解了：

![02e6e857f8976728894f4644266b4f1c.png][]

图中，在做 Apply 之前，先拿到需要 Apply 的列的 Distinct 值集合，拿这些值做 Apply，之后再用普通的 Join 把 Apply 的结果连接上去。

这样做的好处是：如果被 Apply 的数据存在大量重复，则 Distinct Project 之后需要 Apply 的行数大大减少。这样一来，即使之后 Apply 没有被优化掉，迭代执行的代价也会减小不少。

**► 本文说的这些变换规则，应该用在 RBO 还是 CBO 中呢？换句话说，去关联化后之后的执行计划一定比去关联化之前更好吗？**

答案是，不一定。

直观的看，如果 Apply 的左边数据量比较少（例如，仅有 1 条数据），那直接带入 Apply 的右边计算反而是更好的方式。另一种情况是，右边有合适的索引，这种情况下，多次 Apply 的代价也并非不可接受。

所以把这些规则放进一个 CBO 的优化器是更合适的，优化器根据代价估计选出最优的计划来。甚至，在某些情况下，我们还会自右向左地运用这些等式，做“加关联化”。

这和用 HashJoin 还是 NestedLoopJoin 是同样的道理。事实上，NestedLoopJoin 就是 Apply 的一个特例。如果存在合适的索引，NestedLoopJoin 效率高于 HashJoin 是很常见的事情。

--------------------

感谢您的阅读，也欢迎您发表关于这篇文章的任何建议，关注我，技术不迷茫！

![5f34bde8f1fdf0bafd10eae4ac98bfc2.gif][]

*  [JDK1.8新特性(四)：函数式接口][JDK1.8]
 *  [MySQL性能优化(七)：MySQL执行计划，真的很重要，来一起学习吧][MySQL_MySQL]
 *  [微服务架构下的核心话题 (三)：微服务架构的技术选型][Link 1]

![b225bd0e79fb3eb8abfb4d5bc82af1e1.gif][]

喜欢就点个"在看"呗，留言、转发朋友圈

[03c0b4bc4217ff6d4bbccbfe5725733a.png]: /images/20221022/78ba1ad555cb49e4b9721208186e8b2b.png
[724adb2655bea9e60f20b12a1d6494b1.png]: /images/20221022/4e735e102fdf4e80be611864af0e9a60.png
[68e64fabb7dc2217368123fc1cafb602.png]: /images/20221022/be740b529fb84c5c8be3132cb6e2bc63.png
[f23902e6c7e0443dc499b51466e899b5.png]: /images/20221022/fab78706ed9f465a87216f7205f60c4f.png
[c939100d63032705242748aaa6b29e61.png]: /images/20221022/c5c72dc241a5488888308f52c98a3f4f.png
[3f7d13f1338d2a11acf3c2083593abb1.png]: /images/20221022/f30b8db7050643e18260320106513b61.png
[914222d56df234976bd23bb20f8c1328.png]: https://img-blog.csdnimg.cn/img_convert/914222d56df234976bd23bb20f8c1328.png
[83beca46f7a7560830cc565f628a3b41.png]: /images/20221022/8baba86396f24697b901199e487f2666.png
[9f81431774604df22d26dd2db6b16159.png]: /images/20221022/4c80c2a010f04ac6a37d79ab2fcbde04.png
[5ca4f014d8fa42cc3a5c8a69b5fb21d2.png]: /images/20221022/ded7792655b24d7fa974f7e395ba2e51.png
[a97a0cb0b1fe6f01a9014f9c1ae67b1f.png]: /images/20221022/8b0df80f0faa41e0bb936685d0a393db.png
[81e843c4d59ab64e1dea465ceca28eae.png]: https://img-blog.csdnimg.cn/img_convert/81e843c4d59ab64e1dea465ceca28eae.png
[e148b93f4a9705f8dbbd0b1f5bfde44e.png]: /images/20221022/8eeab125c69640ad8eadfa276b2c9333.png
[7187345222ccec092be33846c65f635a.png]: /images/20221022/179e9bb276834e979d95723f9c07b50c.png
[96017a499169316f5d535019909def4e.png]: /images/20221022/a70de8a86fcd4f608084cb808459a822.png
[02e6e857f8976728894f4644266b4f1c.png]: /images/20221022/8eec79ea8c36467a8824d26f4ba03b6b.png
[5f34bde8f1fdf0bafd10eae4ac98bfc2.gif]: /images/20221022/2bdd9254f288445ea7c8b331292903c3.png
[JDK1.8]: http://mp.weixin.qq.com/s?__biz=MzA5MzUwOTY4NQ%3D%3D&chksm=905d88fba72a01ed52ba7e5403ba39bbb4386bd23a7906db45d831311c7216ecbd5a7efeff8d&idx=1&mid=2247485857&scene=21&sn=be80b248bcc6c080755953219a1f2b78#wechat_redirect
[MySQL_MySQL]: http://mp.weixin.qq.com/s?__biz=MzA5MzUwOTY4NQ%3D%3D&chksm=905d8838a72a012e057b5671b8a429c1dacbfcd15bc480ee020c59a1f636e906fcd5edca659d&idx=1&mid=2247485794&scene=21&sn=cef01641815309e84aa2fbbd692bf5b4#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzA5MzUwOTY4NQ%3D%3D&chksm=905d8970a72a00662feffcea58c746fa0098b98a6a92af9dfd9490b7a84cab6b432c9f4ec831&idx=1&mid=2247485482&scene=21&sn=e6385ef8cc1cf13c8f17a6e29de238b6#wechat_redirect
[b225bd0e79fb3eb8abfb4d5bc82af1e1.gif]: /images/20221022/d9ee9f4e226a4a1198cc474ae1ed5357.png