关于前端:一文终结SQL-子查询优化

33次阅读

共计 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 外部提取进去。

正文完
 0