Towards a Robust Query Optimizer: A Principled and Practical Approach Brian Badcock Surajit Chaudhuri Stanford University Microsoft Research SIGMOD 2005
Towards a Robust Query Optimizer: A Principled and Practical Approach Brian Badcock Surajit Chaudhuri Stanford University Microsoft Research SIGMOD 2005
目录 研究背景 口传统查询优化器的问题 论文的解决方案 对查询优化器的改进 口随机 sampling 口置信度阈值 分析 总结
目录 ◼ 研究背景 ❑ 传统查询优化器的问题 ❑ 论文的解决方案 ◼ 对查询优化器的改进 ❑ 随机sampling ❑ 置信度阈值 ◼ 分析 ◼ 总结
研究背景 传统查询优化器的问题 口传统的查询计划的代价估算 属性值的独立性( Attribute value independence) 口在很多情况下表中列的取值是独立的 ■多维属性值分布的描述 a Multidimensional Histograms a Graphical models 口随着维度的增加,桶的数量呈指数级增长( curse of dimensionality ■假设估计的结果是正确的
研究背景 ◼ 传统查询优化器的问题 ❑ 传统的查询计划的代价估算 ◼ 属性值的独立性（ Attribute value independence ） ❑ 在很多情况下表中列的取值是独立的 ◼ 多维属性值分布的描述 ❑ Multidimensional Histograms ❑ Graphical models ❑ 随着维度的增加，桶的数量呈指数级增长（ curse of dimensionality ） ◼ 假设估计的结果是正确的
本文的出发点 Selectivity的估测是满足一个分布的 不同的访问计划在不同的 Selectivity下是不同 口嵌套循环join Selectivity!y低的情况下代价较大 代价比较稳定 a Index join Selectivity!y低的情况下代价较小 代价不稳定 采用 Sample的方法
本文的出发点 ◼ Selectivity的估测是满足一个分布的 ◼ 不同的访问计划在不同的Selectivity下是不同 ❑ 嵌套循环join ◼ Selectivity低的情况下代价较大 ◼ 代价比较稳定 ❑ Index join ◼ Selectivity低的情况下代价较小 ◼ 代价不稳定 ◼ 采用Sample的方法
Where Predictability Shows Up 50 40 C1=81(S)≈100s 35 g2(S)≈25+10 30 20 Plan 1 15 Plan 2 0 0% 20% 40% 60%80%100% Query Selectivity Figure l: Execution Costs for Two Hypothetical Plans
Where Predictability Shows Up c g s s c g s s ( ) 25 10 ( ) 100 2 2 1 1 = + =
Where Predictability Shows Up 50 1=81()≈100 40 35 (s)≈25+10s 30 20 Plan 1 15 Plan 2 81(c1) 10 100 25 0 0% 20% 40% 60%80%100% 10 Query Selectivity Figure l: Execution Costs for Two Hypothetical Plans
Where Predictability Shows Up 10 25 ( ) 100 1 ( ) ( ) 25 10 ( ) 100 2 2 1 2 1 1 1 1 2 2 1 1 − = = = = = + = − − c s g c s g c c c g s s c g s s
Where Predictability Shows Up 0<S<1 0.8 0.7 . Plan 1 Plan 2 0 0.5 ≥0.4 →0<c1<100 0.3 0.2 25 0 10 30 Execution Cost →25≤c,≤35 Figure 2 Probability Density Function for Execution Cost
Where Predictability Shows Up 25 35 1 10 25 0 0 100 1 100 1 0 0 1 2 2 1 1 − c c c c s
技术途径 需要解决的问题 a Selectivity的概率分布如何应用于查询优化 口如何得到概率分布 论文的思路 口评估方法对数据库系统的体系结构没有影响 a使用 SAMPLE的方法进行代价分析的好处 口使用 SAMPLE的方法描述查询的 Selectivity
技术途径 ◼ 需要解决的问题 ❑ Selectivity的概率分布如何应用于查询优化 ❑ 如何得到概率分布 ◼ 论文的思路 ❑ 评估方法对数据库系统的体系结构没有影响 ❑ 使用SAMPLE的方法进行代价分析的好处 ❑ 使用SAMPLE的方法描述查询的Selectiviy
基于概率分布的查询优化 ■假设:能够获得针对 Selectⅳvy的代价概率分布 两种方案的比较 口平均代价 口最坏代价 Confidence threshold 口有T%的可能性最终的计算代价小于估计的结果 ■累计分布函数( cumulative distribution function) D CDFY
基于概率分布的查询优化 ◼ 假设：能够获得针对Selectivity的代价概率分布 ◼ 两种方案的比较 ❑ 平均代价 ❑ 最坏代价 ◼ Confidence threshold ❑ 有T%的可能性最终的计算代价小于估计的结果 ◼ 累计分布函数（cumulative distribution function） ❑ CDF(Y)= Y 0 f(z)
Dealing with Predictability If we look at the distributions we see that plan 2 hits 80% of all plans(all execution patterns)with a cost of 31.9. Plan 1 only hits 80% of all plans at a cost of 33.5 0.8 0.7 --..Plan 1 0.6 Plan 2 Execution Cost Figure 2 Probability Density Function for Execution Cost
Dealing with Predictability ◼ If we look at the distributions, we see that Plan 2 hits 80% of all plans (all execution patterns) with a cost of 31.9. Plan 1 only hits 80% of all plans at a cost of 33.5