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 = + =