关于java:深入解析快速教会你-SQL-子查询优化

子查问 （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 的条件表达式上面的。

理论执行时，查问打算执行器（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）。

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 外部提取进去。后果如下：

下面的例子中，咱们能够必定 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 算子。

根本打消规定

第一组规定是最根本的规定，等式中的 ⊗⊗ 阐明它不限度连贯类型，能够是 {×,LOJ,∃,∄}{×,LOJ,∃,∄} 中的任意一个。

这两条规定是十分不言而喻的，翻译成大白话就是：如果 Apply 的左边不蕴含来自右边的参数，那它就和间接 Join 是等价的。

上面是对 Query 3 利用规定 (2) 的例子：

Project 和 Filter 的去关联化

第二组规定形容了如何解决子查问中的 Project 和 Filter，其思维能够用一句话来形容：尽可能把 Apply 往下推、把 Apply 上面的算子向上提。

留神这些规定仅解决 Cross Apply 这一种状况。其余 3 种 Apply 的变体，实践上都能够转换成 Cross Apply，临时咱们只有晓得这个事实就能够了。

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

咱们稍后就会看到这样做的微小收益：当 Apply 被推最上面时，就能够利用第一组规定，间接把 Apply 变成 Join，也就实现了子查问去关联化的优化过程。

上面是对 Query 2 利用规定 (3) 的例子。之后再利用规定 (1)，就实现了去关联化过程。

Aggregate 的去关联化

第三组规定形容如何解决子查问中的 Aggregate（即 Group By）。和上一组一样，咱们的指导思想依然是：尽可能把 Apply 往下推、把 Apply 上面的算子向上提。

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

这一组规定不像之前那么简略直白，咱们先看一个例子找找感觉。上面是对 Query 1 使用规定 (9) 的后果：

规定 (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 的时候加上一个。

留神到，这些规定与之前咱们见过的规定有个显著的不同：等式左边 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] 中仅仅是证实了这些状况都能够被规约到可解决的情景（实际上嘛，可想而知，肯定是没有解决的）。

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

其中，D=ΠF(T2)∩A(T1)(T1)D=ΠF(T2)∩A(T1)(T1)，示意对 T1T1 的 Distinct Project 后果（所谓的 Magic Set）。间接看等式比拟艰涩，看上面的例子就容易了解了：

图中，在做 Apply 之前，先拿到须要 Apply 的列的 Distinct 值汇合，拿这些值做 Apply，之后再用一般的 Join 把 Apply 的后果连贯下来。

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

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

答案是，不肯定。

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

所以把这些规定放进一个 CBO 的优化器是更适合的，优化器依据代价预计选出最优的打算来。甚至，在某些状况下，咱们还会自右向左地使用这些等式，做“加关联化”。

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