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.6464837e-05
Overall Rank: 2,318 | 84.42%
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.00015429949
1,688	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	9.8645784e-05
4,417	Dynamic Workload Management for Very Large Data Warehouses - Juggling Feathers and Bowling Balls	2007	VLDB	6.6088398e-05
5,386	PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics	2013	VLDB	6.1522468e-05
5,656	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.0488629e-05
5,983	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.926918e-05
6,241	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.8381762e-05
6,456	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB	5.7782179e-05
7,376	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	5.540013e-05
7,460	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	5.5215755e-05
7,967	Resource Bricolage for Parallel Database Systems	2015	VLDB	5.415894e-05
8,139	ConEx: A System for Monitoring Queries	2007	SIGMOD	5.3920783e-05
9,133	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	5.2229655e-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.00076195956
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
91	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.0003475226
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029627449
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011771949

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
2	5,656	Uncertainty Aware Query Execution Time Prediction	2014	VLDB
3	6,660	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,241	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD
6	1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD
7	13,050	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,587	Estimating Progress of Execution for SQL Queries	2004	SIGMOD
10	6,456	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB