共计 7470 个字符,预计需要花费 19 分钟才能阅读完成。
作者:Eric Fu\
链接:https://ericfu.me/subquery-op…
子查问 (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 的条件表达式上面的。
理论执行时,查问打算执行器(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 算子:
实践上,咱们 能够将所有的子查问转换成 Apply 算子,一个通用的办法如下:
- 如果某个算子的表达式中呈现了子查问,咱们就把这个子查问提取到该算子上面(留下一个子查问的后果变量),形成一个 ALOJALOJ 算子。如果不止一个子查问,则会产生多个 ALOJALOJ。必要的时候加上 Max1RowMax1Row 算子。
- 而后利用其余一些规定,将 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] 中为例,思路大抵是:
- 对于任意的查问关系树,首先将关联子查问从表达式中提取进去,用 Apply 算子示意;
- 一步步去掉其中非根本关系算子,首先,通过等价变换去掉 Union 和 Subtract;
- 进一步放大算子汇合,去掉 OuterJoin、ALOJALOJ、A∃A∃、A∄A∄;
- 最初,去掉所有的 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 是很常见的事件。
References
- https://www.microsoft.com/en-…
- http://citeseerx.ist.psu.edu/…
- https://dl.gi.de/bitstream/ha…
- https://dl.gi.de/bitstream/ha…
近期热文举荐:
1.600+ 道 Java 面试题及答案整顿(2021 最新版)
2. 终于靠开源我的项目弄到 IntelliJ IDEA 激活码了,真香!
3. 阿里 Mock 工具正式开源,干掉市面上所有 Mock 工具!
4.Spring Cloud 2020.0.0 正式公布,全新颠覆性版本!
5.《Java 开发手册(嵩山版)》最新公布,速速下载!
感觉不错,别忘了顺手点赞 + 转发哦!