When can we trust progress estimators for SQL queries?
- 14 June 2005
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 575-586
- https://doi.org/10.1145/1066157.1066223
Abstract
The problem of estimating progress for long-running queries has recently been introduced. We analyze the characteristics of the progress estimation problem, from the perspective of providing robust, worst-case guarantees. Our first result is that in the worst case, no progress estimation algorithm can yield anything even moderately better than the trivial guarantee that identifies the progress as lying between 0% and 100%. In such cases, we introduce an estimator that can optimally bound the error. However, we show that in many "good" scenarios, it is possible to design effective progress estimators with small error bounds. We then demonstrate empirically that these "good" scenarios are common in practice and discuss possible ways of combining the estimators.Keywords
This publication has 13 references indexed in Scilit:
- Estimating progress of execution for SQL queriesPublished by Association for Computing Machinery (ACM) ,2004
- Toward a progress indicator for database queriesPublished by Association for Computing Machinery (ACM) ,2004
- Robust query processing through progressive optimizationPublished by Association for Computing Machinery (ACM) ,2004
- Join synopses for approximate query answeringPublished by Association for Computing Machinery (ACM) ,1999
- On random sampling over joinsPublished by Association for Computing Machinery (ACM) ,1999
- Ripple joins for online aggregationPublished by Association for Computing Machinery (ACM) ,1999
- Efficient mid-query re-optimization of sub-optimal query execution plansPublished by Association for Computing Machinery (ACM) ,1998
- Selectivity and Cost Estimation for Joins Based on Random SamplingJournal of Computer and System Sciences, 1996
- Query optimizationACM Computing Surveys, 1996
- On the propagation of errors in the size of join resultsPublished by Association for Computing Machinery (ACM) ,1991