作者 方物
为确保理解顺畅 在阅读之前请提前了解以下概念或原理
根据 SQL 标准 将一个查询块嵌套进一个表达式中 我们就得到了一个子查询。
关系型数据库中的查询块 通常由关系代数算子组成的树状计划来表达。而每个算子中的表达式与外层的查询树的关系是暧昧不清的。
查询树中的表达式藏着另一棵查询树 本质在于通过表达式来描述查询树间的关系。比如说自定义函数、比较运算符、逻辑运算符。由于表达式类型繁多且过于复杂 很难直接通过传统的关系代数抽象模拟子查询与主查询间的关系。这让子查询成为关系型数据库中实现的难点之一。
既然子查询的实现对数据库来说如此复杂 执行的效率也未必高 为何还要实现这种 SQL 语法呢 除了 SQL 标准以外还有其它原因吗
... WHERE AGE ALL(SELECT AGE ...) ... WHERE SALARY ANY(SELECT SALARY ...)
将各个查询树理解为一个数据集 通过 JOIN 来描述数据间的交并集关系在部分场景下是非常晦涩的。但观察以上 SQL AGE ALL 和 SLARY ANY 的子查询描述非常接近自然语言 能大大简化用户构建复杂查询的过程。因此从某种意义上来讲 可以将子查询理解为一种历史悠长的 SQL 语法糖。
一言以蔽之 子查询就是一个把复杂留给数据库 把简单送给用户的经典案例。
想要了解子查询 必须先对其进行分类。从语义上可以将其划分为
SELECT c_custkey FROM CUSTOMER WHERE 1000000 ( SELECT SUM(o_totalprice) FROM ORDERS WHERE o_custkey c_custkey )
SELECT c_name FROM CUSTOMER WHERE c_nationkey ALL (SELECT s_nationkey FROM SUPPLIER)
SELECT c_custkey FROM CUSTOMER WHERE c_nationkey 86 AND EXISTS( SELECT * FROM ORDERS WHERE o_custkey c_custkey )
语义上的划分更易理解 但数据库会基于逻辑运算的角度抽象出另一种划分方式
将子查询进行逻辑拆解后 并不代表它就是一个普通的表达式。关系型数据库的表达式计算过程中 函数会尽量以行数据作为输入输出。
对集合进行处理的函数通常会抽象为一个新的算子 例如聚合函数会单独用 Agg 算子处理。同样的道理子查询也应该抽象为一个单独的算子。算子与表达式切割时的边界划分问题也遵循相同的逻辑。
数据库引擎一般不会将复杂的数据集运算混淆到表达式计算中 从实现的复杂度考虑 也会尽量明确集合运算与行运算的边界。
最后基于子查询本身是否有关联项 还可以分为关联子查询及非关联子查询。凡是非关联子查询本质上都可以视做为一个常量 而关联子查询处理时必须要考虑子查询内外层的数据关系。对这层数据关系的处理便是子查询优化技术的重点。
SQL 作为一种声明式的语言 仅仅描述了它需要什么样的数据 具体怎么操作则还要看数据库自己的发挥。查询优化技术发展到如今 2021 子查询必然会导致性能下降的说法已经过于武断了。
关联子查询的本意为外表每一行数据与子查询集合数据的运算。当外表数据行过多时 这一嵌套的过程将不可避免导致性能低下。因此子查询优化很重要的一步就是去关联化 unnesting 如今的去关联技术已经日趋成熟 HyPer 2015 年就宣称自己能够《Unnesting Arbitrary Queries》。
上一节提到 由于处理的是集合数据 子查询应该从表达式中剥离出来 以算子的方式展示在执行计划中。这个指代子查询的算子一般称之为 Apply。
将子查询转为 Apply 算子后 关联项还残留在子查询的查询树内 所以没有办法直接将 Apply 以 Join 的方式处理。
因此 子查询优化通常最重要的一步是去关联化。
SELECT c_custkey FROM CUSTOMER WHERE 1000000 ( SELECT SUM(o_totalprice) FROM ORDERS WHERE o_custkey c_custkey )
我们以上面 SQL 为例 直观地感受一下 为什么说关联子查询的去关联化是十分必要的。
下面是未经去关联化的原始查询计划 Relation Tree 。实际执行时 查询计划执行器 Executor 在执行到 Apply 时 针对每一行数据 都要去执行一遍 Apply 右侧的查询树。这样通过嵌套的方式处理关联子查询 处理耗时会随数据量增长呈直线上升状态 如果是多层子查询嵌套 耗时呈指数级上升也不奇怪。为了避免长耗时带来的糟糕体验 必须要将子查询去关联化。
基于规则去关联化 Unnesting base on rule
上世纪八九十年代 SQL 标准拓展了子查询的存在范围。掀起了一股研究如何去关联化的热潮 当时研究的主流之一便是基于规则的去关联化。
在 01 年发布的《Orthogonal Optimization of Subqueries and Aggregation》论文是基于规则去关联化的集大成作 其中总结了 9 条转换规则
下图中的两次转换分别对应规则 3 与 规则 1。
示例中的转换过程是有前提条件的 Join 与 Filter 间的关系契合 AND 逻辑运算符是关键。
基于规则的转换无法处理所有模式的子查询 比如以下几个例子
// 复杂示例1 disjunction 中的子查询 SELECT * FROM supplier a WHERE s_address IN (select s_name from supplier where a.s_phone s_phone) OR s_name 1 // 复杂示例2 子查询包含聚合与非等值关联项 SELECT * FROM T1 WHERE AGE (SELECT AVG(AGE) FROM T2 WHERE T1.NAME! NAME) // 复杂示例3 多层嵌套子查询 (SELECT * FROM T1 WHERE ID IN (SELECT ID FROM T2 WHERE T3.NAME NAME)) ...
Magic Set 去关联化 Unnesting base on magic
Magic Set 是一种非常古老的数据处理技术 最早应用在演绎数据库 Deductive Database 中。如今在关系型数据库中子查询去关联化上也发挥着很重要的作用。
考虑这样的一条 SQL
SELECT s.name, e.course FROM students s, exams e WHERE s.id e.sid AND (s.major ’CS’ or s.major ’Games Eng’) AND e.grade (SELECT avg(e2.grade) 1 --one grade worse FROM exams e2 --than the average grade WHERE s.id e2.sid OR --of exams taken by (e2.curriculum s.major AND --him/her or taken s.year e2.date)) --by elder peers
这个 SQL 的 Unnesting 主要难在有非等值关联项 s.year e2.date 这将导致无法在关联项所在的 filter 层避免 Join 计算。
△图例来自 HyPer 的论文《Unnesting Arbitrary Queries》
在 HyPer 的论文中 尝试将关联项涉及列的数据 copy 一份 引入到子查询内部。用 Join 计算来替换关联项 从而实现了去关联化。
从实现上看 是以一部分空间和额外的 Join 计算为代价 实现了子查询的去关联化。
数据库通常会利 Semi Join 算子簇表达去关联化后的子查询。这里会遇到另一个问题 Apply 与 Semi Join 的关系代数定义无法完全等价。
semi join “半连接” 意味着仅输出一张表的列 另一张表的列不向上层输出
// 复杂示例1 disjunction 中的子查询 SELECT * FROM supplier a WHERE s_address IN (select s_name from supplier where a.s_phone s_phone) OR s_name 1
考虑以上 SQL 子查询处于 OR 表达式之间 这会导致无法将其简单的转为 SemiJoin 因为 Filter 与 SemiJoin 叠加的过滤关系与 OR 相违。
针对这个场景 HyPer 引入了 Mark Join 替换 SemiJoin 。
在 Mark Join 上层的 Filter 中 会形成 markvalue OR sname 1 的表达式。通过增加一列输出的方式避免与 OR 语义的违背。
采用 Mark 机制 让 Join 多输出了一列 不但破坏了 Join 的关系代数含义 执行层也需要做相应的大规模改造。但它除了能解决上面示例中的 OR 子查询以外 对 Project、Scalar 类子查询也可支持 这种做法很有借鉴意义。
Oracle 2009 年发表的 《Enhanced subquery optimizations in Oracle》向大家展示了数量繁多的子查询重写优化。这些技术基于 TPC-H 中的子查询做了针对性的优化 估计是 Oracle 的程序员在 TPC-H 打榜时写的。
这些重写技术对参数的提取和推导有很高要求。随便列一下其中的内容
将多个类似子查询合并的技术 如下图的 Q2 转 Q3 Q4 转 Q5
子查询与主表合并
子查询除了与类似的子查询合并以外 还可以与主表合并。例如 Q8 转 Q11
窗口函数优化
简单讲就是带 Agg 的子查询被重写成了窗口函数。重写的前提是外部查询块包含所有子查询的表以及过滤条件。例如
Q1: SELECT T1.X FROM T1,T2 WHERE T1.y T2.y and T2.name ming and T2.z relop (SELECT AGG(T2.w) FROM T2 WHERE T2.y T1.y and T2.name ming );
外部查询块有 T1 和 T2 两张表 包含了子查询中所有的查询表(T2) 并且同时也包含了所有的过滤条件 T2.name ming 。relop 是关系操作符的简写。
满足以上条件之后就可以将 Q1 重写为 Q2
Q2: SELECT T1.x FROM T1,( SELECT AGG (T2.w) OVER (PARTITION BY y) AS win_agg, FROM T2 WHERE T2.name ming ) V WHERE T1.y V.y and V.z relop win_agg
如果 T1 与 T2 的连接是无损连接 lossless join 的话 Q1 可以转为 Q3
Q3: SELECT V.x FROM ( SELECT T1.x, T2.z, AGG (T2.w) OVER (PARTITION BY T2.y) AS win_agg FROM T1, T2 WHERE T1.y T2.y ) V WHERE V.z relop win_agg
关于 lossless join 这里不做展开讨论 实际上 Q2 和 Q3 之间的区别可以理解为 Agg 与 Join 的 reorder。
在将 Q1 重写为 Q2 之后 会在 CBO 中根据 Cost 判断是否需要转化为 Q3 的形式。这里举个具体的例子 Q4 TPC-H Q17
Q4: SELECT sum(l_extendedprice) / 7.0 AS avg_yearly 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 );
在 50G 的场景下 各个 plan 的计算量如下所示
原始执行计划重写为窗口函数后 明显可以看到减少了一次 10^8 级别的扫描。
对比重写为窗口函数的两个执行计划 从处理的行数可以看到 Plan2 窗口函数的 Cost ?要小很多。但要转成 Plan2 的情况需要一些前提条件 类似 Agg 与 Join reorder 的判断。在 lossless join 的场景下是可以直接转为 Plan2 的 Q4 part 与 lineitem 之间是外键连接 因此是符合这个条件。
另外 Plan2 的 Join 利用 Batch Key Access 算法 相当于对 lineitem 表进行 10^4 次索引扫描 Cost 极低。
窗口函数优化对 TPC-H Q2 和 Q17 都有显著的 RT 提升效果 在分布式数据库中 实测窗口函数 BKA 优化对 Q17 有近百倍提升。
查询优化并不是子查询技术的全部 从实现角度分析 执行过程中的陷阱更加防不胜防。
Count 陷阱主要存在于没有?group by 的 Count 子查询中。考虑以下 SQL
SELECT * FROM T1 WHERE T1.NUM (SELECT COUNT(ID) FROM T2 WHERE T1.AGE AGE)
如果将其转为以下的执行树 当 T2 的某 age 数量为 0 时 SemiJoin 的连接会因为 T1.age T2.age 表达式结果为 Null 从而无法输出正确的结果。本质上的原因是由于 COUNT 聚合函数的特殊性导致。想要解决必须要 Join 节点输出 Null 行 类似 Left 类型的特性。
观察以下两个子查询 想要输出 User 表中不同名或不同年龄的人
// SQL1 SELECT * FROM USER T1 WHERE AGE NOT IN (SELECT AGE FROM USER T2 WHERE T1.NAME T2.NAME); // SQL2 SELECT * FROM USER T1 WHERE NOT EXISTS (SELECT 1 FROM USER T2 WHERE T1.NAME T2.NAME AND T1.AGE AGE);
表面看上去两个子查询是等价的 实际上假如 USER 表中有一行 age 为 NULL 的数据 SQL1 不会输出 SQL2 会将其输出。
NOT EXISTS 等价于 Anti Join Anti Join 的执行器在处理 on 条件时 如果执行结果为 null 则认为没有匹配。问题在于 not in 的子查询的操作数也转成了 on 条件之一 与关联项通过 and 连接。这时就会出现多输出的正确性问题。
那么这种情况下 可以选择不将 NOT IN 子查询转为连接 例如 PG 在处理 NOT IN 子查询保留了原来的处理方式。
但还有一种选择 Oracle 在 《Enhanced Subquery Optimizations inOracle》一文中提到 他们采用了一种新的算子 Null-Aware Anti Join NAAJ 来处理。还是以 SQL1 为例 NAAJ 的处理算法如下
如果 T2 是空集 则返回所有行 如果 T2 的 Age 有任意一行为 Null 则不返回任何行 如果 T1 的 Age 在某行值为 Null 则不返回该行 对于 T1 的每一行 如果 NA 条件执行为 Null 或 TRUE 则不返回该行 否则返回。
注意?NAAJ?中的?NA?条件是经过反转的 NOT?IN?- ?NA ????? ALL??- ??NA
分布式数据库的优势在于拥有更多的计算和存储资源可供调用 但由于数据分布在不同的节点 节点间的数据传输 IO 很容易成为性能瓶颈。执行子查询时尤其要考虑如何扬长避短。
子查询的嵌套执行会导致网络 IO 随数据量上涨。除了执行缓慢以外 还会导致整体的资源消耗变大 系统容量变低。
去关联化除了可以将 O(N^2) 的时间复杂度消除为 O(N) 可以避免大量的网络 IO 开销。
如果数据的分布满足条件 子查询还可以整体下推到存储节点进行计算 充分利用了集群的计算性能以外 也避免了大量 Scan 数据在网络层的传输。
所以说在分布式系统中 如何将更多的子查询转为连接执行尤为重要。
物化的思路除了可以用于关联项消除以外 还可以用于削减连接计算中的网络传输数据。
如图所示当连接一端的数量量较小时 可以将其全量或部分捞出 Semi 可以部分 Anti 必须全量 作为常量代入到另一侧的执行计划中去处理。
即便是无法转为连接的子查询 依然可以通过子查询的逻辑特性来削减网络 IO 的数据量。
假设子查询的 condition 为 E Semi 类型的 Apply 算子的子查询一侧都可以增加以下过滤条件
E OR (E IS NULL) 对于 E1 OR E2 OR E3 ... 来讲 En 为 FALSE 的表达式是可以忽略的
如果是 anti 类型 则可以增加以下过滤条件
// E NOT E E OR (E IS NOT NULL) 对于 E1 AND E2 AND E3 ... 来讲 En 为 TRUE 的表达式是可以忽略的
分别举例
SELECT * FRMO R WHERE ID IN (SELECT ID FROM R ...)
SELECT * FRMO R WHERE AGE ALL(SELECT AGE FROM R ...)
注意?Anti?下推的表达式需要反转
通过这样的方式 可以在子节点提前过滤掉不需要的数据。即便在空集的情况下 这个 filter 下推也是成立的。
Cache 是永不过时的优化技术 在 Apply 中合理的利用缓存具有化腐朽为神奇的效果。
举个最简单的多层 Apply SQL
SELECT * FROM T1 WHERE 100 (SELECT col1 FROM T2 WHERE T1.pk T2.pk AND 100 (SELECT col2 FROM T3 WHERE T2.pk T3.pk))
假设 T1 T2 T3 都为 1000 行数据 先看一下 Apply 的执行过程
T1 表作为最外层的主表 只需要扫描一次。扫出的数据有 1000 行 所以 Apply 会往 T2 这边扫扫描 1000 次 同理 每次扫描 T2 都需要扫 1000 次 T3。最终 T2 的扫描次数是 1000 次 T3 的扫描次数是 10^6 次。
这意味着在千行的数据量场景下 多层的 Apply 会导致十万乃至百万级的网络 IO 次数。即便 Apply 是预期的慢查询 但这种 Cost 是不可接受的。
由此引入 Cache 最主要的目的在于减少网络 IO 次数
如上图所示 虽然到 Cache Node 的 IO 次数没有变化 但 IO 的级别从网络降级到了内存。网络上的 IO 三张表各自仅进行一次。内存的存取速度与网络天壤之别 这里不再放具体 SQL RT 数据支撑。
在这篇文章中我们简单聊了很多关于子查询的优化技术 如 Magic Set、窗口函数等 相信可以让大家体会到子查询优化的脑洞与精妙。同时实践时的陷阱 不管是对数据库还是对开发者来说 都有很重要的参考意义。
最后我们分享了分布式数据库中处理子查询的一些心得 希望能给大家带来一些启发。
【相关阅读】
PolarDB-X 让“Online DDL”更Online
如今云计算是全球应对新冠疫情危机的核心技术。的确,几大领先的公有云提供商在2...
对于vlookup函数,很多人都有会这样的想法:vlookup函数的第三参数为什么就不能...
456...
【51CTO.com原创稿件】去年年底,国际数据公司(IDC)发布的《中国金融云市场(2...
CSRF 攻击的原理 CSRF 攻击,英文全称就是 Cross Site Request Forgy,意思就是...
本文转载自公众号读芯术(ID:AI_Discovery)。 要想掌握编程,大量练习是不可或缺...
梯度下降是一种优化算法,遵循目标函数的负梯度以定位函数的最小值。 梯度下降的...
阿里云与西奥电梯联合共同打造西奥可信电梯物联网平台,通过工业互联网的规则引...
CDC 是什么 CDC 是变更数据捕获(Change Data Capture)技术的缩写,它可以将源...
今年春节黄金周期间,全国零售和餐饮企业销售额首次突破万亿元,根据电商大数据...