Uncertainty Aware Query Execution Time Prediction

Summary: Uncertainty-aware query time prediction using the optimizer cost model; treats operator selectivities and CPU/I/O constants as random variables, not fixed constants. Infers a distribution of prediction errors with low overhead and shows strong correlation between estimated and actual errors. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hce6338a0e374e430
Venue: VLDB
Year: 2014
Pagerank: 6.0266818e-05
Overall Rank: 5,670 | 62.00%
DOI: 10.14778/2733085.2733088
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Wentao Wu (University of Wisconsin)
2. Xi Wu (University of Wisconsin)
3. Hakan Hacıgümüş (NEC Corporation)
4. Jeffrey F. Naughton (University of Wisconsin)

BibTeX Citation

@article{wu_vldb14,
        title = {{Uncertainty Aware Query Execution Time Prediction}},
        author = {Wu, Wentao and Wu, Xi and Hacıgümüş, Hakan and Naughton, Jeffrey F.},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {14},
        pages = {1857--1868},
        doi = {10.14778/2733085.2733088},
        url = {https://doi.org/10.14778/2733085.2733088},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,261	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011289724
3,959	MB2: Decomposed Behavior Modeling for Self-Driving Database Management Systems	2021	SIGMOD	6.8804723e-05
6,113	Expand your Training Limits! Generating Training Data for ML-based Data Management	2021	SIGMOD	5.8662826e-05
6,768	Multi-Tenant Cloud Data Services: State-of-the-Art, Challenges and Opportunities	2022	SIGMOD	5.6693759e-05
7,483	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	5.5007125e-05
7,975	Robust Query Processing: Mission Possible	2020	VLDB	5.3985544e-05
8,872	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.2459616e-05
9,829	Wii: Dynamic Budget Reallocation In Index Tuning	2024	SIGMOD	5.1066866e-05
10,446	Coresets for Robust Query Optimization	2026	PODS	4.9605343e-05
10,676	Understanding and Detecting Query Performance Regression in Practical Index Tuning: [Experiments & Analysis]	2026	SIGMOD	4.9605343e-05
10,753	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	4.9605343e-05
11,288	Esc: An Early-Stopping Checker for Budget-aware Index Tuning	2025	VLDB	4.9605343e-05
11,302	PlanRGCN: Predicting SPARQL Query Performance	2025	VLDB	4.9605343e-05
12,364	Lifting the Haze off the Cloud: A Consumer-Centric Market for Database Computation in the Cloud	2017	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 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.00076079812
17	Provenance Semirings	2007	PODS	0.00059660827
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
78	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036725074
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029532435
296	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021874894
471	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017691682
568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016221103
628	Performance Prediction for Concurrent Database Workloads	2011	SIGMOD	0.00015421836
676	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014838681
996	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB	0.00012595827
1,044	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.0001232071
1,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
1,124	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00011898749
1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011739527
1,587	Estimating Progress of Execution for SQL Queries	2004	SIGMOD	0.00010119368
1,630	Query Optimization in Heterogeneous DBMS	1992	VLDB	0.00010013052
1,926	Predictable Performance for Unpredictable Workloads	2009	VLDB	9.3500398e-05
2,329	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	8.6188984e-05
3,384	Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads	2013	VLDB	7.3392425e-05
3,531	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.2065332e-05
4,260	Buffer Pool Aware Query Optimization	2005	CIDR	6.6824533e-05
6,841	Distribution-Based Query Scheduling	2013	VLDB	5.6512839e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	371	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD
2	1,124	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS
3	12,807	Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations	2010	VLDB
4	7,886	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
5	3,384	Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads	2013	VLDB
6	10,446	Coresets for Robust Query Optimization	2026	PODS
7	676	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB
8	8,451	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
9	2,696	Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection	2022	VLDB
10	568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD