When can we trust progress estimators for SQL queries?

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.

REFERENCES

• 1: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.275-286, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: N. Bruno and S. Chaudhuri. Statistics on query expressions. In SIGMOD, 2002.
• 3: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: S. Chaudhuri and V. Narasayya. The sky server database. http://skyserver.sdss.org.
• 5: Surajit Chaudhuri , Vivek Narasayya , Ravishankar Ramamurthy, Estimating progress of execution for SQL queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007659]
• 6: Peter J. Haas, Large-Sample and Deterministic Confidence Intervals for Online Aggregation, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.51-63, August 11-13, 1997
• 7: Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 8: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Selectivity and cost estimation for joins based on random sampling, Journal of Computer and System Sciences, v.52 n.3, p.550-569, June 1996 [doi>10.1006/jcss.1996.0041 ]
• 9: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 10: Yannis E. Ioannidis, Query optimization, ACM Computing Surveys (CSUR), v.28 n.1, p.121-123, March 1996 [doi>10.1145/234313.234367]
• 11: Yannis E. Ioannidis , Stavros Christodoulakis, On the propagation of errors in the size of join results, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.268-277, May 29-31, 1991, Denver, Colorado, United States
• 12: Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.106-117, June 01-04, 1998, Seattle, Washington, United States
• 13: Gang Luo , Jeffrey F. Naughton , Curt J. Ellmann , Michael W. Watzke, Toward a progress indicator for database queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007658]
• 14: Gang Luo , Jeffrey F. Naughton , Curt J. Ellmann , Michael W. Watzke, Increasing the Accuracy and Coverage of SQL Progress Indicators, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.853-864, April 05-08, 2005 [doi>10.1109/ICDE.2005.79]
• 15: Volker Markl , Vijayshankar Raman , David Simmen , Guy Lohman , Hamid Pirahesh , Miso Cilimdzic, Robust query processing through progressive optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007642]
• 16: Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
• 17: The TPCH Benchmark. http://www.tpc.org.
• 18: Program for TPC-D Data Generation with Skew. ftp://ftp.research.microsoft.com/users/viveknar/tpcdskew.