Robust query processing through progressive optimization
Robust query processing through progressive optimization
复制标题
通过渐进式优化实现稳健的查询处理
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
H. Pirahesh
中科院分区：
文献类型：
--
作者：
V. Markl;Vijayshankar Raman;David E. Simmen;G. Lohman;H. Pirahesh
实际上，每个商业查询优化器都使用基于准确的基数估计的成本模型选择查询的最佳计划。由于使用不准确的统计信息，关于属性独立性，参数标记等的无效假设等，可能会出现基数估计错误。基数估计错误可能会导致优化器选择次优计划。我们提出了一种非常强大的查询处理方法，因为它能够从基数估计错误中检测并恢复。我们称这种方法为“渐进查询优化”（POP）。 POP验证了针对查询执行过程中测量的实际值的基数估计。如果估计值和实际值之间存在重大分歧，则可能会停止执行，并可能发生重新优化。优化和执行步骤之间的振荡可能发生多次。重优化步骤可以利用在上一个执行步骤中计算的实际基数和部分结果。检查点运算符（检查）验证了针对实际的红衣主教的优化器的基数估算。每个检查都有一个指示计划有效的基数界限的条件。我们通过对查询计划运营商的新敏感性分析来计算此有效性范围。如果违反了检查条件，请检查触发器重新挑选。 POP已在领先的商业DBM中进行了原型。使用TPC-H查询对POP进行的实验评估说明了鲁棒性POP增加了查询处理，同时仅产生的开销可忽略不计。将POP应用于现实世界数据库和工作负载的案例研究表明，POP的潜力将复杂的OLAP查询加速了几乎两个数量级。
Virtually every commercial query optimizer chooses the best plan for a query using a cost model that relies heavily on accurate cardinality estimation. Cardinality estimation errors can occur due to the use of inaccurate statistics, invalid assumptions about attribute independence, parameter markers, and so on. Cardinality estimation errors may cause the optimizer to choose a sub-optimal plan. We present an approach to query processing that is extremely robust because it is able to detect and recover from cardinality estimation errors. We call this approach "progressive query optimization" (POP). POP validates cardinality estimates against actual values as measured during query execution. If there is significant disagreement between estimated and actual values, execution might be stopped and re-optimization might occur. Oscillation between optimization and execution steps can occur any number of times. A re-optimization step can exploit both the actual cardinality and partial results, computed during a previous execution step. Checkpoint operators (CHECK) validate the optimizer's cardinality estimates against actual cardinalities. Each CHECK has a condition that indicates the cardinality bounds within which a plan is valid. We compute this validity range through a novel sensitivity analysis of query plan operators. If the CHECK condition is violated, CHECK triggers re-optimization. POP has been prototyped in a leading commercial DBMS. An experimental evaluation of POP using TPC-H queries illustrates the robustness POP adds to query processing, while incurring only negligible overhead. A case-study applying POP to a real-world database and workload shows the potential of POP, accelerating complex OLAP queries by almost two orders of magnitude.