leftjoin⼦查询_SQL⼦查询的优化
⼦查询（Subquery）的优化⼀直以来都是 SQL 查询优化中的难点之⼀。关联⼦查询的基本执⾏⽅式类似于 Nested-Loop，但是这种执⼦查询
去关联化（Decoorelation 或 Unnesting），将其改写为类⾏⽅式的效率常常低到难以忍受。当数据量稍⼤时，必须在优化器中对其进⾏去关联化
似于 Semi-Join 这样的更⾼效的算⼦。
前⼈已经总结出⼀套完整的⽅法论，理论上能对任意⼀个查询进⾏去关联化。本⽂结合 SQL Server 以及 HyPer 的⼏篇经典论⽂，由浅⼊深地讲解⼀下这套去关联化的理论体系。它们⼆者所⽤的⽅法⼤同⼩异，基本思想是想通的。
本⽂的例⼦都基于 TPC-H 的表结构，这⾥ 有⼀份供你参考。
⼦查询简介
⼦查询是定义在 SQL 标准中⼀种语法，它可以出现在 SQL 的⼏乎任何地⽅，包括 SELECT, FROM, WHERE 等⼦句中。
⾮关联⼦查询（Non-correlated Subquery）。后者⾮关联⼦关联⼦查询（Correlated Subquery）和⾮关联⼦查询（Non-correlated Subquery）
总的来说，⼦查询可以分为关联⼦查询（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）
标量（Scalar-valued）⼦查询：输出⼀个只有⼀⾏⼀列的结果表，这个标量值就是它的结果。如果结果为空（0 ⾏），则输出⼀个NULL。但是注意，超过 1 ⾏结果是不被允许的，会产⽣⼀个运⾏时异常。多表left join
标量⼦查询可以出现在任意包含标量的地⽅，例如 SELECT、WHERE 等⼦句⾥。下⾯是⼀个例⼦：
SELECT c_custkey
FROM CUSTOMER
WHERE 1000000 < (
SELECT SUM(o_totalprice)
FROM ORDERS
WHERE o_custkey = c_custkey  -- Correlated!
)
▲ Query 1: ⼀个出现在 WHERE ⼦句中的标量⼦查询
SELECT o_orderkey, (
SELECT c_name
FROM CUSTOMER
WHERE c_custkey = o_custkey  -- Correlated!
) AS c_name FROM ORDERS
▲ Query 2: ⼀个出现在 SELECT ⼦句中的标量⼦查询
存在性检测（Existential Test）⼦查询：特指 EXISTS 的⼦查询，返回⼀个布尔值。如果出现在 WHERE 中，这就是我们熟悉的存在性检测（Existential Test）
Semi-Join。当然，它可能出现在任何可以放布尔值的地⽅。
SELECT c_custkey
FROM CUSTOMER
WHERE c_nationkey = 86 AND EXISTS(
SELECT * FROM ORDERS
WHERE o_custkey = c_custkey  -- Correlated!
)
▲ Query 3: ⼀个 Semi-Join 的例⼦
集合⽐较（Quantified Comparision）⼦查询：特指 IN、SOME、ANY 的查询，返回⼀个布尔值，常⽤的形式有：x = SOME(Q)集合⽐较（Quantified Comparision）
（等价于 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 的交替调⽤⼗分低效
这种 Executor - Evaluator - Executor 的交替调⽤⼗分低效！考虑到 Filter 上可能会有上百万⾏数据经过，如果为每⾏数据都执⾏⼀次⼦查询，那查询执⾏的总时长显然是不可接受的。
Apply 算⼦
上⽂说到的 Relation - Expression - Relation 这种交替引⽤不仅执⾏性能堪忧，⽽且，对于优化器也是个⿇烦的存在——我们的优化规则都是在匹配并且对 Relation 进⾏变换，⽽这⾥的⼦查询却藏在 Expression ⾥，令⼈⽆从下⼿。
为此，在开始去关联化之前，我们引⼊ Apply 算⼦：
Apply 算⼦（也称作 Correlated Join）接收两个关系树的输⼊，与⼀般 Join 不同的是，Apply 的 Inner 输⼊（图中是右⼦树）是⼀个Apply 算⼦
带有参数的关系树。
Apply 的含义⽤下图右半部分的集合表达式定义：对于 Outer Relation
中的每⼀条数据
，计算 Inner Relation
，输出它们连接（Join）起来的结果
。Apply 的结果是所有这些结果的并集（本⽂中说的并集指的是 Bag 语义下的并集，也就是 UNION ALL）。
Apply 是 SQL Server 的命名，它在 HyPer 的⽂章中叫做 Correlated Join。它们是完全等价的。考虑到 SQL Server 的⽂章发表更早、影响更⼴，本⽂中都沿⽤它的命名。
根据连接⽅式（
）的不同，Apply ⼜有 4 种形式：
Cross Apply
：这是最基本的形式，⾏为刚刚我们已经描述过了；
Left Outer Apply
：即使
为空，也⽣成⼀个
。
Semi Apply
：如果
不为空则返回
，否则丢弃；
Anti-Semi Apply
：如果
为空则返回
，否则丢弃；
我们⽤刚刚定义的 Apply 算⼦来改写之前的例⼦：把⼦查询从 Expression 内部提取出来。结果如下：
有且只有⼀⾏结果，所以可以直接转成 Apply。但某些情况下，可能⽆法肯定⼦查询⼀上⾯的例⼦中，我们可以肯定 Scalar Agg ⼦查询有且只有
定能返回 0 或 1 ⾏结果（例如，想象⼀下 Query 2 如果 c_custkey 不是唯⼀的），为了确保 SQL 语义，还要在 Apply 右边加⼀个
算⼦：
可以将所有的⼦查询转换成 Apply 算⼦，⼀个通⽤的⽅法如下：
理论上，我们可以将所有的⼦查询转换成 Apply 算⼦
1. 如果某个算⼦的表达式中出现了⼦查询，我们就把这个⼦查询提取到该算⼦下⾯（留下⼀个⼦查询的结果变量），构成⼀个
算⼦。如果不⽌⼀个⼦查询，则会产⽣多个
。必要的时候加上
算⼦。
2. 然后应⽤其他⼀些规则，将
转换成
、
、
。例如上⾯例⼦中的⼦查询结果
被⽤作 Filter 的过滤条件，NULL 值会被过滤掉，因此可以安全地转换成
。
下⾯这个例⼦中，Filter 条件表达式中包含
、
两个⼦查询。转换之后分别⽣成了对应的 Apply 算⼦。其中
⽆法确定只会⽣成恰好⼀条记录，所以还加上了
算⼦。
基本消除规则
第⼀组规则是最基本的规则，等式中的
说明它不限制连接类型，可以是
中的任意⼀个。
这两条规则是⾮常显⽽易见的，翻译成⼤⽩话就是：如果 Apply 的右边不包含来⾃左边的参数，那它就和直接 Join 是等价的。
下⾯是对 Query 3 应⽤规则 (2) 的例⼦：
Project 和 Filter 的去关联化
尽可能把 Apply 往下推、把 Apply 下⾯的算第⼆组规则描述了如何处理⼦查询中的 Project 和 Filter，其思想可以⽤⼀句话来描述：尽可能把 Apply 往下推、把 Apply 下⾯的算⼦向上提。
⼦向上提

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。