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: 3668
Venue: SIGMOD
Year: 2005
Pagerank: 9.5207583e-05
Overall Rank: 2,113 | 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
716	Performance Prediction for Concurrent Database Workloads	2011	SIGMOD	0.00017623897
1,768	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	0.00010608933
3,128	Dynamic Workload Management for Very Large Data Warehouses – Juggling Feathers and Bowling Balls	2007	VLDB	7.5192383e-05
5,547	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.4452585e-05
5,699	PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics	2013	VLDB	5.3655096e-05
6,277	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1260947e-05
6,341	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.0980049e-05
6,478	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB	5.040535e-05
7,084	Stop-and-Restart Style Execution for Long Running Decision Support Queries	2007	VLDB	4.8330538e-05
7,606	ConEx: A System for Monitoring Queries	2007	SIGMOD	4.693557e-05
7,914	Resource Bricolage for Parallel Database Systems	2015	VLDB	4.6136905e-05
8,961	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	4.4171776e-05
9,012	Hit the Gym: Accelerating Query Execution to Efficiently Bootstrap Behavior Models for Self-Driving Database Management Systems	2024	VLDB	4.4059413e-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.0010813443
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
216	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033560137
221	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00033182072
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
650	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001865144
1,229	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00013153898

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,277	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1260947e-05
7,462	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB	4.7189301e-05
7,220	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	4.7926382e-05
1,867	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010264932
6,341	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.0980049e-05
1,229	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00013153898
12,576	Online Estimation For Subset-Based SQL Queries	2005	VLDB	4.1905499e-05
1,017	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014627121
1,509	Estimating Progress of Execution for SQL Queries	2004	SIGMOD	0.0001158945
6,478	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB	5.040535e-05