When Can We Trust Progress Estimators for SQL Queries? Surajit Chaudhuri, Raghav Kaushik, and Ravishankar Ramamurthy   View Paper (PDF)   Return to Estimation and Approximation (Research) 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 prac- tice and discuss possible ways of combining the estimators. ©2006 Association for Computing Machinery