共计 2975 个字符,预计需要花费 8 分钟才能阅读完成。
子查问(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 外部提取进去。