Proactive Re-optimization

Abstract

Traditional query optimizers rely on the accuracy of estimated statistics to choose good execution plans. This design often leads to suboptimal plan choices for complex queries, since errors in estimates for intermediate subexpressions grow exponentially in the presence of skewed and correlated data distributions. Re-optimization is a promising technique to cope with such mistakes. Current re-optimizers first use a traditional optimizer to pick a plan, and then react to estimation errors and resulting suboptimalities detected in the plan during execution. The effectiveness of this approach is limited because traditional optimizers choose plans unaware of issues affecting re-optimization. We address this problem using <i>proactive re-optimization</i>, a new approach that incorporates three techniques: <ol> <li> the uncertainty in estimates of statistics is computed in the form of bounding boxes around these estimates </li> <li> these bounding boxes are used to pick plans that are robust to deviations of actual values from their estimates </li> <li> accurate measurements of statistics are collected quickly and efficiently during query execution </li> </ol> We present an extensive evaluation of these techniques using a prototype proactive re-optimizer named <i>Rio</i>. In our experiments Rio outperforms current re-optimizers by up to a factor of three.