Stanford InfoLab Publication Server

Proactive Re-optimization

Babu, Shivnath and Bizarro, Pedro and DeWitt, David (2005) Proactive Re-optimization. In: 24th ACM International Conference on Management of Data (SIGMOD 2005) , June 14-16, 2005, Baltimore, Maryland.




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.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:Query optimization, adaptive query processing
Subjects:Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:709
Deposited By:Import Account
Deposited On:03 Mar 2005 16:00
Last Modified:22 Dec 2008 17:47

Download statistics

Repository Staff Only: item control page