KaiwuDBkaiwudb logo

博客专区

关系查询执行计划的鲁棒性度量

2023-03-30

标签: 鲁棒性metrics 计划选择

PART 01

导读





本篇博客主要讲解于 VLDB 上发表的一篇论文:它所提出的三个新的用于量化关系查询执行计划鲁棒性的 metrics,以及一种新的计划选择策—选择计划时同时考虑估计成本和估计鲁棒性。


论文原文:http://www.vldb.org/pvldb/vol11/p1360-wolf.pdf


2.png



PART 02

背景介绍


数据库系统中查询执行计划的质量决定了查询执行的速度。数据库系统根据成本模型,计算计划成本,在给定查询的一组等效计划中找到一个好的查询执行计划。


在成本计算的过程中,成本模型和基数估计错误均会导致误差的产生。Leis 等人的工作表明,相较与成本模型,基数估计的误差原则上是无界的,估计误差可达六个数量级,由于基数估计的误差,传统的查询优化会选择次优甚至糟糕的执行计划。


基数估计错误的根本原因是错误的假设,主要包含以下四个方面:

(1)数据分布

(2)列相关性

(3)join关系

(4)统计不准确


目前已经提出的几种改进基数估计的方法,如直方图或采样,可以更好地处理不同的数据分布。列组统计可以通过提高表中列相关性的精度等方式在一定程度上提高其准确性,但基数估计错误导致的成本估计错误仍然是查询优化中的主要问题。


因此,本文提出了一种新的计划选择策略,在考虑估计成本之外,为计划分配一个鲁棒值,鲁棒值的权重仅次于估计成本,选择计划时可从估计成本和计划鲁棒性两方面进行比较;对鲁棒值的分配则通过提出的三个新的 metrics 来衡量。


PART 03

问题描述与符号表示


1. 针对存在估计误差的情况,寻找一个强鲁棒性的问题形式化:

 · λ/λ/λ:估计的 cardinality/cost/selectivity


 · °/°/° :  真实的 cardinality/cost/selectivity


 · λ↓ / λ估计的 cardinality 的下限/上限


2.  估计误差系数 cerr :估算成本与真实成本的绝对商

 

3.png


鲁棒性度量为计划候选对象分配一个鲁棒性值。理想情况下,鲁棒性值是 cerr 上限的近似值,鲁棒性最强计划是在候选计划集合中代价误差因子 cerr  最小的计划。


3. 理想的鲁棒性度量应该满足以下 3 个一致性

 · 估计误差系数 cerr 改善:估计的鲁棒性最强的计划的成本误差因子 cerr  应小于估计的最优计划


 · 估计误差系数 cerr 的主导性:根据鲁棒性度量,鲁棒性最强的计划在成本误差因素 cerr 下主导所有计划候选,即其他计划的成本误差系数不应小于鲁棒性最强的计划;


 · 估计误差系数 cerr 限制鲁棒性度量应给出计划的成本误差系数 cerr 的上限。具有较大鲁棒性值的计划可能具有较大的 cerr,而具有较小鲁棒性值的计划应该具有较小的 cerrcerr  的上限应与鲁棒性值成正比,但 cerr 本身不必与鲁棒性成正比。


4. 为了在执行前量化计划的鲁棒性,定义了参数成本函数:

参数化成本函数(PCF):是查询执行计划或子计划的成本,被建模为一个成本参数的函数。


5. 定义一个查询执行计划 P

P=(O, Ep),其中 O为操作符的集合,E为边的集合,如下图所示,每一条边表示一个中间结果,其上包含对应的 λ , λ, f ° , c °


4.png

图 1 查询计划示例


PART 04

三种鲁能性 metrics


1. Cardinality-Slope Robustness Metric

将查询执行计划中所有边的 PCF 都考虑在内,首先定义边 的 cardinality-slope(e ∈ Ep)。


定义1边 的cardinality-slope δf,e 是在给定边 e 的 λ 时的斜率。PCFf  为计划 P 在边 e 上通过 cardinality f 计算的成本。


理论上,估计错误可能发生在查询执行计划的所有边上。实际上,基数估计的统计模型的精度因不同类型的运算符而异。


例如,由于键上的约束,外键连接后的边可以比 m:n 连接后的边缘更精确地估计。此外,基表扫描后的边可以比过滤谓词后的边更精确地估计。为了考虑估计误差的不同风险,需要定义一个边缘加权函数 φ


定义2:边加权函数 φ E→ [0.0,1.0] 指定每条边 e 的误差敏感度值介于 0.0(不敏感)和 1.0(非常敏感)之间。


定义3:计划 P 的 Cardinality-Slope Robustness Metric rδf (p) 定义为:


5.png


因此,鲁棒值越小,计划就越稳健。


2. Selectivity-Slope Robustness Metric

将查询执行计划中所有操作符的 PCF 都考虑在内。首先定义操作符 op 的 Selectivity-Slope(op ∈ Op)。


定义4:操作符 op 的 Selectivity-Slope δs,op 是在给定操作符 op 的 λ 时 PCFs,op 的斜率。PCF为计划 P 在操作符 op 上通过 selectivity s 计算的成本。


定义5:操作符加权函数:ϕ:→ [0.0,1. 0] 是运算符 op 的加权函数。


定义6:计划 P 的 Selectivity-Slope Robustness Metric rδs (p)定义为:


6.png


3. Cardinality-Integral Robustness Metric

Cardinality-Integral Robustness Metric 考虑到了计划稳健性和估计成本之间的权衡。Cardinality-Slope Robustness Metric 和 Selectivity-Slope Robustness Metric 都使用 PCF 斜率作为鲁棒性指标。


然而,与斜率较缓的计划相比,斜率较陡的计划在基数值较大范围内的成本仍然较小。因此,引入 λ / f λ 分别表示边 e 上估计的 cardinality 的下限/上限,并计算在 λ↓ 和 λ 之间的 cost,即考虑 PCF 在 f λ 和  λ 之间的积分。


定义7:边 的 Cardinality-Integral value ∫f,e 和 7.jpg


定义8:计划 P 的 Cardinality-Integral Robustness Metrir∫f  定义为:


8.png


PART 05

总结


图 2 总结了三个鲁棒性指标。Cardinality-Slope Robustness Metric(图 2(a))反映了查询执行计划中所有边上基数估计错误的估计成本与实际成本之间的预期差异。


Selectivity-Slope Robustness Metric(图 2(b))考虑了所有边上的考虑了较大绝对基数误差的风险 ∆f。与 Cardinality-Slope Robustness Metric 和 Selectivity-Slope Robustness Metric 相反。


Cardinality-Integral Robustness Metric(图 2(c))不仅仅关注计划的鲁棒性,还考虑了估计成本。此外,它可以考虑边的基数的更现实的范围,而不是考虑所有数值上可能的基数。这三个指标都支持任何类型的运算符、运算符实现和查询执行计划树,因为计划的成本始终可以建模为基数的 PCF。


9.jpg

图 2 Cardinality-Slope, Selectivity-Slope 和

Cardinality-Integral Robustness Metric 对比分析


PART 06

计划性选择策略


鲁棒方案选择策略分为三个阶段:首先,枚举鲁棒方案候选集,每个候选计划都是整个查询的计划,而不是子计划;其次,通过应用三个度量来计算每个计划候选的鲁棒性值;最后,选择估计的鲁棒性最强的计划,即具有最小鲁棒值的候选计划执行。


除了鲁棒性之外,选择一个成本低的查询执行计划仍然是一个主要的优化目标。因此候选计划的第一个标准是,他们的成本必须最低,因此引入了 k-cheapest plans 的定义。


定义9:k-cheapest plans 指预估成本最小的前 k 个计划。


k-cheapest plans 大大减少了计划候选的数量,并为独立于计划空间的计划数量提供了一个严格的上限。


由于 Cardinality-Slope Robustness Metric 和 Selectivity-Slope Robustness Metric 没有考虑到成本方面的限制,因此引入了近似最优计划。


定义10:近似最优计划指估计成本最多为估计最优计划成本的 λ- 倍的计划。在实验中,k 和 λ 分别取值 500 和 1.2。


PART 07

实验分析


1. 实验数据


工作负载:

1)Join Order Benchmark(JOB)(将原始查询修改为纯连接查询,将表的电影 id 限制为 100000 行)


2)用生成的数据和连接查询合成的。查询拓扑有:链式、循环式和雪花式


实验对比:

以 Estimated Optimal plan (EO)为 baseline,将三个度量 cardinality-slope (FS), selectivity-slope (SS), 和 cardinality-integral metric (FI) 计算选择的方案与其对比。离线执行所有的鲁棒候选计划,并将执行时间最短的计划记为最快的计划(FA)。


实验从查询执行时间,估计误差系数 cerr 改善两方面进行了分析比较。


2. 查询执行时间


10.png

图 3 计划执行策略的执行时间比较


图 3 (a)为在工作负载 1 下,通过三个 metrics 选出的计划的执行时间与估计最优计划 EO 以及实际执行最快计划 FA 的执行时间对比。


其中表现最佳的 Q2,Q7 相较于 EO 来说,加速比最大,且与 FA 的执行时间差距很小。图 3 (b) 和 (c) 为在工作负载 2 下,随机拓扑的实验结果以及链式拓扑、循环拓扑和雪花拓扑的累计查询执行时间(∑)、最佳加速比 (↑EO)和最差回归比(↓EO)时间表。


对于这三个指标,强鲁棒性的计划选择比传统的计划选择实现了更好的累计执行执行时间。此外,对于所有查询拓扑,这三个指标都比回归因子实现了更大的加速。将 Q37、Q95 和 Q98 的结果与 FA 进行比较,表明在这些情况下,所有鲁棒的计划选择策略都接近真正的最优。


3. 估计误差系数  cerr  改善

此部分实验结果对理想的鲁棒性度量的三个一致性进行的验证


1)Cost Error Factor Improvement

根据第一个一致性要求,估计的最稳健计划的成本误差因子 cerr  应小于估计的最优计划。为了衡量成本误差因素的改善,计算了估计的最佳计划( cerr ,EO)的  cerr r 与另一个计划( cerr ,p)的  cerr  之间的差异:


11.png


所以该差值为正时,则表示 cerr  有所改善。


12.png

图 4  计划执行策略的 cerr  改善情况比较


图4 (a) 为在工作负载 1 下,不同策略选择的计划的 cerr 改善情况。使用 SS 和 FI 进行鲁棒计划的选择,在 31 个查询中,30 个取得了改善效果。使用 FS 进行鲁棒计划的选择,在 31 个查询中,29 个取得了改善效果。


图 4 (b) 和 (c) 为在工作负载 2 下,显示了随机拓扑的实验结果,以及链拓扑、循环拓扑和雪花拓扑的平均结果(µ∆cerr ,最大(↑∆cerr ),最小(↑∆cerr )。对于三个 metrics,计划选择达到正 µ∆cerr 。比较 ↑∆cerr 和 ↑∆cerr ,FS、SS 和 FI 的 cerr  表明,最大增益总是大于 cerr  的最大损耗。


图 4(c) 中 FI 与 FS 和 SS 的比较表明,FI 总是获得较差的结果。原因是 FI 已经平衡了计划鲁棒性和估计成本。相反,FS 和 SS 只关注计划鲁棒性,并通过将鲁棒性计划候选对象限制为接近最优的计划来实现这一权衡。


2)Cost Error Factor Dominance

根据第二个一致性要求,由鲁棒计划选择的鲁棒性最强的计划应在所有候选计划中占主导地位。为了度量 cerr 的主导地位,定义了计划 p 的 ρcerr,p


13.png


 ρcerr,p 为 100% 表示一个计划具有所有候选中最小的 cerr ,即是鲁棒性最强的计划。


实际上,不可能对每个查询都实现 100% 的 ρcerr,p,因为由鲁棒性度量指定的鲁棒性值是 cerr  上限的近似值。因此,将 δcerr,p 定义为计划 p 和鲁棒性最强的计划 r 的 cerr  之间的差异:


14.png


δcerr,p 接近 0 则表示计划 p 的 cerr  与候选计划中 cerr 最小的计划相似,即鲁棒性最强的计划。


15.png

图 5 计划执行策略的 cerr 主导情况比较


对于图 5 (a),总的来说,对于 31 个执行的查询中的 13 个,使用 FS 和 SS 的稳健计划选择实现了 100% 的 ρcerr,p,图 5(b)绘制了随机拓扑的是实验结果以及链拓扑、循环拓扑和雪花拓扑,平均结果(µρcerr,p,最大(↑∆ρcerr,p,最小(↑∆ρcerr,p)对于所有查询拓扑,FS 和 SS 的 µ∆ρcerr,p(83%–93%)明显大于 EO(21%–47%)。


3)Correlated Cost Error Factor Limit

根据第三个一致性要求,具有较大鲁棒性值的计划可能具有较大的 cerr,而具有较小鲁棒性值的计划应该具有较小的 cerr由于基数估计可能很精确,并且总是会导致较小的成本误差因子 cerr ,即使分配了较大的鲁棒性值,鲁棒性数值和 cerr 之间的相关性也不能用于评估第三个要求。


所以将一个查询的所有鲁棒的候选计划绘制到一个图中。图 6 显示了 Selectivity-Slope Metric 的一些实验结果。可以看出,即使 rδs 和 cerr 之间没有很强的相关性,也满足了相关的成本误差因的子限制要求。


16.jpg

图 6 Selectivity-Slope Robustness Metric 的 cerr 限制


PART 08


总结

本文提出了三个新的鲁棒性度量 metrics,它们有效地量化了优化时查询执行计划的鲁棒性,并考虑了计划选择过程中潜在基数估计错误的影响,并通过实验评估证明了三个鲁棒性度量 metrics 的有效性,表明了鲁棒计划的选择优于传统计划的选择。在计划选择时,提出了一种新的计划选择策略,该策略在选择执行计划时同时考虑了估计成本和估计鲁棒性。


与其他鲁棒性选择方法相比,本文思路不限制计划拓扑,可以独立于其他计划计算单个计划的鲁棒值,并且不受统计模型的限制。此外,本文对问题的形式化规范和鲁棒性度量的要求为未来的鲁棒查询处理研究奠定了坚实的基础。


免费体验 KaiwuDB 全新功能

立即体验

关于我们
联系我们

KaiwuDB B站

KaiwuDB
B站

KaiwuDB 微信公众号

KaiwuDB
微信公众号

© 上海沄熹科技有限公司 Shanghai Yunxi Technology Co., Ltd.    沪ICP备2023002175号-1
400-870-1188
1V1 方案咨询
marketing@kaiwudb.org.cn