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: 11071
Venue: VLDB
Year: 2014
Pagerank: 6.1820087e-05
Overall Rank: 5,537 | 62.02%
DOI: 10.14778/2733085.2733088

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,256	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011457194
3,961	MB2: Decomposed Behavior Modeling for Self-Driving Database Management Systems	2021	SIGMOD	6.987575e-05
6,024	Expand your Training Limits! Generating Training Data for ML-based Data Management	2021	SIGMOD	6.0031118e-05
6,939	Multi-Tenant Cloud Data Services: State-of-the-Art, Challenges and Opportunities	2022	SIGMOD	5.7338637e-05
7,829	Robust Query Processing: Mission Possible	2020	VLDB	5.5360082e-05
8,572	T3: Accurate and Fast Performance Prediction for Relational Database Systems With Compiled Decision Trees	2025	SIGMOD	5.4102362e-05
8,698	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.3830073e-05
9,615	Wii: Dynamic Budget Reallocation In Index Tuning	2024	SIGMOD	5.2436464e-05
10,151	Coresets for Robust Query Optimization	2026	PODS	5.093636e-05
10,413	Understanding and Detecting Query Performance Regression in Practical Index Tuning: [Experiments & Analysis]	2026	SIGMOD	5.093636e-05
10,494	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	5.093636e-05
10,815	Esc: An Early-Stopping Checker for Budget-aware Index Tuning	2025	VLDB	5.093636e-05
10,830	PlanRGCN: Predicting SPARQL Query Performance	2025	VLDB	5.093636e-05
12,020	Lifting the Haze off the Cloud: A Consumer-Centric Market for Database Computation in the Cloud	2017	VLDB	5.093636e-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.00077458002
17	Provenance Semirings	2007	PODS	0.00059843817
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
492	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001756877
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
624	Performance Prediction for Concurrent Database Workloads	2011	SIGMOD	0.00015683402
682	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00015014887
984	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB	0.00012825643
1,028	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00012557617
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,104	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00012157634
1,143	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011999403
1,562	Estimating Progress of Execution for SQL Queries	2004	SIGMOD	0.00010354429
1,595	Query Optimization in Heterogeneous DBMS	1992	VLDB	0.00010249433
1,879	Predictable Performance for Unpredictable Workloads	2009	VLDB	9.5613416e-05
2,270	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	8.8310714e-05
3,482	Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads	2013	VLDB	7.3751635e-05
3,506	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.3581509e-05
4,197	Buffer Pool Aware Query Optimization	2005	CIDR	6.8406917e-05
7,149	Distribution-Based Query Scheduling	2013	VLDB	5.6878283e-05

Semantically Similar Papers

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