When Can We Trust Progress Estimators for SQL Queries?

Summary: Worst-case: for SQL progress estimation, no estimator beats the trivial 0–100% bound; they propose an optimal error-bound estimator for that regime. In typical SQL workloads, progress estimates are accurate with small errors; empirical results show such good scenarios are common, and combining estimators improves robustness. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hf843912bce30dd9e
Venue: SIGMOD
Year: 2005
Pagerank: 8.6429103e-05
Overall Rank: 2,320 | 84.41%
DOI: 10.1145/1066157.1066223

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Microsoft)
2. Raghav Kaushik (Microsoft)
3. Ravishankar Ramamurthy (Microsoft)

BibTeX Citation

@inproceedings{chaudhuri_sigmod05,
        title = {{When Can We Trust Progress Estimators for SQL Queries?}},
        author = {Chaudhuri, Surajit and Kaushik, Raghav and Ramamurthy, Ravishankar},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066223},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066223},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
629	Performance Prediction for Concurrent Database Workloads	2011	SIGMOD	0.00015428007
1,688	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	9.860716e-05
4,419	Dynamic Workload Management for Very Large Data Warehouses - Juggling Feathers and Bowling Balls	2007	VLDB	6.6057136e-05
5,392	PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics	2013	VLDB	6.1494698e-05
5,658	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.0460211e-05
5,983	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.9241225e-05
6,243	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.8357659e-05
6,458	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB	5.7755054e-05
7,378	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	5.537392e-05
7,464	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	5.5189616e-05
7,971	Resource Bricolage for Parallel Database Systems	2015	VLDB	5.4133337e-05
8,146	ConEx: A System for Monitoring Queries	2007	SIGMOD	5.3895274e-05
9,134	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.2223611e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076265429
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00034748721
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029858107
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029618887
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028977821
284	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022205848
471	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017744392
1,158	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011767292

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,658	Uncertainty Aware Query Execution Time Prediction	2014	VLDB
2	7,492	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
3	6,664	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD
4	1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD
5	6,243	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD
6	1,158	Toward a Progress Indicator for Database Queries	2004	SIGMOD
7	13,056	Online Estimation For Subset-Based SQL Queries	2005	VLDB
8	682	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB
9	1,588	Estimating Progress of Execution for SQL Queries	2004	SIGMOD
10	6,458	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB