Uncertainty Aware Query Execution Time Prediction
Preprint
Abstract
Predicting query execution time is a fundamental issue underlying many database management tasks. Existing predictors rely on information such as cardinality estimates and system performance constants that are difficult to know exactly. As a result, accurate prediction still remains elusive for many queries. However, existing predictors provide a single, point estimate of the true execution time, but fail to characterize the uncertainty in the prediction. In this paper, we take a first step towards providing uncertainty information along with query execution time predictions. We use the query optimizer's cost model to represent the query execution time as a function of the selectivities of operators in the query plan as well as the constants that describe the cost of CPU and I/O operations in the system. By treating these quantities as random variables rather than constants, we show that with low overhead we can infer the distribution of likely prediction errors. We further show that the estimated prediction errors by our proposed techniques are strongly correlated with the actual prediction errors.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Predicting query execution time: Are optimizer cost models really unusable?2013
- GSLPI: A Cost-Based Query Progress Indicator2012
- Learning-based Query Performance Modeling and Prediction2012
- Robust query processing2011
- Q-Cop: Avoiding bad query mixes to minimize client timeouts under heavy loads2010
- Predicting Multiple Metrics for Queries: Better Decisions Enabled by Machine LearningInternational Conference on Data Engineering, 2009
- Estimating progress of execution for SQL queries2004
- Toward a progress indicator for database queries2004
- Generic Database Cost Models for Hierarchical Memory Systems2002
- Selectivity and Cost Estimation for Joins Based on Random SamplingJournal of Computer and System Sciences, 1996