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: 3667
Venue: SIGMOD
Year: 2005
Pagerank: 9.5286436e-05
Overall Rank: 2,111 | 85.32%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
718	Performance Prediction for Concurrent Database Workloads	2011	SIGMOD	0.0001763106
1,770	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	0.00010618229
3,122	Dynamic Workload Management for Very Large Data Warehouses – Juggling Feathers and Bowling Balls	2007	VLDB	7.5264988e-05
5,539	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.4503121e-05
5,688	PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics	2013	VLDB	5.3702808e-05
6,278	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1309442e-05
6,345	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.1023048e-05
6,484	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB	5.0453762e-05
7,088	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	4.8376651e-05
7,604	ConEx: A System for Monitoring Queries	2007	SIGMOD	4.6980644e-05
7,913	Resource Bricolage for Parallel Database Systems	2015	VLDB	4.6180739e-05
8,956	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	4.4214154e-05
9,006	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	4.4101482e-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
14	Online Aggregation	1997	SIGMOD	0.0010801504
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
217	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033536712
220	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00033194808
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
650	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00018659177
1,228	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00013164884

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,278	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1309442e-05
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
7,221	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	4.797194e-05
1,874	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010244443
6,345	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.1023048e-05
1,228	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00013164884
12,567	Online Estimation For Subset-Based SQL Queries	2005	VLDB	4.1945683e-05
1,019	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014625603
1,512	Estimating Progress of Execution for SQL Queries	2004	SIGMOD	0.00011597041
6,484	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB	5.0453762e-05