子查问（Subquery）的优化始终以来都是 SQL 查问优化中的难点之一。关联子查问的根本执行形式相似于 Nested-Loop，然而这种执行形式的效率经常低到难以忍受。当数据量稍大时，必须在优化器中对其进行去关联化（Decoorelation 或 Unnesting），将其改写为相似于 Semi-Join 这样的更高效的算子。
前人曾经总结出一套残缺的方法论，实践上能对任意一个查问进行去关联化。本文联合 SQL Server 以及 HyPer 的几篇经典论文，由浅入深地解说一下这套去关联化的理论体系。它们二者所用的办法大同小异，根本思维是想通的。
本文的例子都基于 TPC-H 的表构造，这里 有一份供你参考。
子查问简介
子查问是定义在 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;
▲ TPCH-13 是一个非关联子查问
非关联子查问不在本文探讨范畴之列，除非特地申明，以下咱们说的子查问都是指关联子查问。
关联子查问的特别之处在于，其自身是不残缺的：它的闭包中蕴含一些外层查问提供的参数。显然，只有晓得这些参数能力运行该查问，所以咱们不能像看待非关联子查问那样。
依据产生的数据来分类，子查问能够分成以下几种：
标量（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 的条件表达式上面的。
img 理论执行时，查问打算执行器（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 外部提取进去。