子查询允许用户直接引用外层查询的列，有很强的语义表达能力，所以被广泛使用，例如在 TPCH 的 22 个查询中，有 13 个查询都包含子查询。
这也是 SQL 优化器中的难点之一，通常需要进行去关联化操作，将其改写为类似 SemiJoin 这种更高效的算子。
简介
子查询几乎可以出现在 SQL 的任何地方，包括 SELECT、FROM、WHERE 等子句中。可以分为关联子查询 (Correlated) 和非关联子查询 (Non-Correlated)，后者执行很简单，只需要先执行子查询，再执行外层即可，如下是 TPCH-Q13 的非关联子查询。
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
) AS c_orders
GROUP BY c_count
ORDER BY custdist DESC, c_count DESC;
在 TPCH 测试集中，还包括了：
Q2Q4Q16Q17Q18Q20Q21在Where子句中，另外，Q4/21含Exists、Q16含Not In、Q18/20含In，而且Q20多层嵌套，Q21同时含Exists和Not Exists。Q7Q8Q9Q13Q22在From字句，而且Q22是多层子查询。Q11Having字句，
如无特殊说明，下面的子查询都是指关联子查询。
关联子查询
其特别之处在于，外层的查询需要依赖子查询的结果，以 TPCH-Q17 为例，简单介绍其实现的语义。
SELECT
SUM(l_extendedprice) / 7.0 AS avg_yearly
FROM
lineitem, part
WHERE
p_partkey = l_partkey
AND p_brand = 'Brand#23'
AND p_container = 'MED BOX'
AND l_quantity < (
SELECT
0.2 * AVG(l_quantity)
FROM
lineitem
WHERE
l_partkey = p_partkey
);
从语义上来看，可以通过如下方式理解。
------ S1 某个品牌、包装类型的零件信息，会有多个零件信息 ==> 240rows
SELECT * FROM part WHERE p_brand = 'Brand#23' AND p_container = 'MED BOX';
------ S2 从上述信息中，查询其中某个零件供货信息 ==> 32rows
SELECT * FROM lineitem WHERE l_partkey = 4880;
------ S3 对应该零件，供货量平均数量20%的值 ==> 4.94
SELECT avg(l_quantity)*0.2 FROM lineitem WHERE l_partkey = 4880;
------ S4 对应该零件，供货量小于平均数量20%的记录 ==> 5rows
SELECT * FROM lineitem WHERE l_partkey = 4880 AND l_quantity < 4.94;
------ S5 对应该零件，供货量小于平均数量20%的总价均值
SELECT sum(l_extendedprice)/7.0 AS avg_yearly FROM lineitem WHERE l_partkey = 4880 AND l_quantity < 4.94;
执行时，会遍历 S1 结果集，重复执行 S2-S5 步骤。
分类
按照不同的场景又分成了如下几类：
标量子查询 Scalar Valued
子查询的输出不会超过一行一列，结果可以为空，此时会返回 NULL 结果，但是，绝对不能出现多于一行，否则会在运行时报错。如上 TPCH-Q17 的 SQL 语句就是标量子查询，子查询出现在 Where 子句中，也可以在 Select 子句中。
存在性检测 Existential Test
特指 EXISTS 的子查询，返回一个布尔值，可以放在任何布尔值的地方，如果出现在 WHERE 子句中，也是 SemiJoin 了，如下是 TPCH-Q4 的 SQL 语句。
SELECT
o_orderpriority, COUNT(*) AS order_count
FROM
orders
WHERE
o_orderdate >= date '1993-07-01'
AND o_orderdate < date '1993-07-01' + interval '3' month
AND EXISTS (
SELECT
*
FROM
lineitem
WHERE
l_orderkey = o_orderkey
AND l_commitdate < l_receiptdate
)
GROUP BY o_orderpriority
ORDER BY o_orderpriority;
集合比较 Quantified Comparision
特指 IN、SOME、ANY 的查询，返回一个布尔值，同上，可能出现在任何可以放布尔值的地方，如下是 TPCH-Q18 的 SQL 语句。
SELECT
c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice, SUM(l_quantity)
FROM
customer, orders, lineitem
WHERE
o_orderkey IN (
SELECT
l_orderkey
FROM
lineitem
GROUP BY
l_orderkey
HAVING
SUM(l_quantity) > 300
)
AND c_custkey = o_custkey
AND o_orderkey = l_orderkey
GROUP BY
c_name,
c_custkey,
o_orderkey,
o_orderdate,
o_totalprice
ORDER BY
o_totalprice DESC,
o_orderdate;
Apply 算子
以上述的 TPCH-Q17 标量计算为例。
当查询计划执行器 (Executor) 执行到过滤条件时，会调用表达式执行器 (Evaluator)，而此时条件表达式中包含标量子查询，所以 Evaluator 又会调用 Executor 计算标量子查询。
这种 Executor Evaluator Executor 的交替执行十分低效！
为了更方便优化器进行操作，于是引入了 Apply 算子。
基本概念
Apply 算子和 Join 很像，分为左右两部分，其右表达式是一个子查询或者表达式，左侧的每一行都和右表达式进行一次计算，然后返回结果给客户端。Apply 先获取左表达式的数据，然后将获取的数据依次对根据右表达式计算；而 Join 则是先获取两张表的笛卡尔积。
Apply 是 SQLServer 中的命名，在 HyPer 被称为 Correlated Join 。
将左子树称为外部查询 (Input)，右子树称为子查询 (Subquery)，子查询中出现的外部列称为关联列，上述 Q17 就是 p_partkey 列。
不过其执行过程仍然与传统方式类似，对于 Input 输入，通过遍历方式传入到 Subquery 中执行，如果不缓存结果，可能会存在重复执行的问题，执行的效率也很低，接着就需要进行解关联 (Decorrelation/Unnesting)。
解关联
为了简单，如下只讨论 Scalar 关联子查询，其执行过程相当于在 Input 中增加一列，增加的列结果为将关联列带入子查询的结果，那么解开的关键就是使子查询获取到对应外部查询行的值。
从执行计划上看，就是将 Apply 算子向右下推到产生关联部分的下面，当 Apply 算子左右没有关联列时，就可以转换为 Join 算子。
注意，下推过程中为了保持等价，算子需要进行改写。在 Orthogonal Optimization of Subqueries and Aggregation 论文中有关于下推时的等价转换规则。
总结
几乎所有的关联子查询都可以去关联化。