When Can we Trust Progress Estimators for SQL Queries?
- Surajit Chaudhuri ,
- Raghav Kaushik ,
- Ravishankar Ramamurthy ,
- Ravi Ramamurthy
SIGMOD |
Published by Association for Computing Machinery, Inc.
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. By placing different types of restrictions on the data and query characteristics, we show that it is possible to design effective progress estimators with small error bounds. We show where previous solutions lie in this spectrum. We then demonstrate empirically that these “good” scenarios are common in practice and discuss possible ways of combining the estimators.
Copyright © 2007 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org. The definitive version of this paper can be found at ACM's Digital Library --http://www.acm.org/dl/.