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: 3729
Venue: SIGMOD
Year: 2005
Pagerank: 8.8310714e-05
Overall Rank: 2,270 | 84.43%
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
624	Performance Prediction for Concurrent Database Workloads	2011	SIGMOD	0.00015683402
1,665	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	0.00010069173
4,327	Dynamic Workload Management for Very Large Data Warehouses - Juggling Feathers and Bowling Balls	2007	VLDB	6.7574155e-05
5,287	PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics	2013	VLDB	6.2815429e-05
5,537	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.1820087e-05
5,863	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	6.0626421e-05
6,138	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.9640712e-05
6,333	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB	5.9094287e-05
7,244	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	5.6638746e-05
7,822	Resource Bricolage for Parallel Database Systems	2015	VLDB	5.5371287e-05
7,974	ConEx: A System for Monitoring Queries	2007	SIGMOD	5.515738e-05
8,572	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	5.4102362e-05
8,984	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.3395569e-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.00077458002
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
492	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001756877
1,143	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011999403

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,366	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
2	566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
3	6,543	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD
4	1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD
5	6,138	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD
6	1,143	Toward a Progress Indicator for Database Queries	2004	SIGMOD
7	12,760	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,562	Estimating Progress of Execution for SQL Queries	2004	SIGMOD
10	6,333	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB