Database Paper Browser

Back to papers

Least Expected Cost Query Optimization: An Exercise in Utility

Summary: Challenges standard optimizer assumptions that optimizing for expected parameter values and assuming static runtime parameters yields good plans; these break under high variability. Presents a System R–style algorithm that picks plans with least expected execution cost over parameter distributions, improving robustness in variable environments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1168
Venue
PODS
Year
1999
Pagerank
0.00013117798
Overall Rank
1,236 | 91.41%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank Citing Paper Year Venue Pagerank
684 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00018179769
692 Pay-as-you-go User Feedback for Dataspace Systems 2008 SIGMOD 0.00018083948
1,272 Proactive Re-Optimization 2005 SIGMOD 0.00012920076
1,300 The Picasso Database Query Optimizer Visualizer 2010 VLDB 0.00012733214
1,986 AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions 2003 VLDB 9.8536784e-05
2,660 Relaxed Currency and Consistency: How to Say "Good Enough" in SQL 2004 SIGMOD 8.3603587e-05
4,348 Identifying Robust Plans through Plan Diagram Reduction 2008 VLDB 6.2660237e-05
4,482 Variance Aware Optimization of Parameterized Queries 2010 SIGMOD 6.1482936e-05
4,516 A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters 2003 SIGMOD 6.1178799e-05
4,617 Adaptive Query Processing in the Looking Glass 2005 CIDR 6.0446738e-05
5,340 Efficiently Approximating Query Optimizer Plan Diagrams 2008 VLDB 5.5623066e-05
5,466 On the Production of Anorexic Plan Diagrams 2007 VLDB 5.4909203e-05
5,505 A Top-Down Approach to Achieving Performance Predictability in Database Systems 2017 SIGMOD 5.4734224e-05
5,581 CliffGuard: A Principled Framework for Finding Robust Database Designs 2015 SIGMOD 5.424205e-05
6,278 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 5.1309442e-05
6,561 On the Stability of Plan Costs and the Costs of Plan Stability 2010 VLDB 5.0099895e-05
6,667 Leveraging Query Logs and Machine Learning for Parametric Query Optimization 2022 VLDB 4.9688874e-05
7,963 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB 4.613363e-05
8,127 Robust Query Processing: Mission Possible 2020 VLDB 4.579056e-05
8,158 MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates 2020 SIGMOD 4.5730772e-05
8,448 PARQO: Penalty-Aware Robust Plan Selection in Query Optimization 2024 VLDB 4.5100508e-05
9,693 ROME: Robust Query Optimization via Parallel Multi-Plan Execution 2024 SIGMOD 4.3027391e-05
10,751 PAR2QO: Parametric Penalty-Aware Robust Query Optimization 2025 VLDB 4.1945683e-05
12,488 Asking the Right Questions: Model-driven Optimization using Probes 2006 PODS 4.1945683e-05
Previous Page 1 / 1 Next

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
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0040449103
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
106 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.00048400734
220 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00033194808
339 Optimization of Dynamic Query Evaluation Plans 1994 SIGMOD 0.00026851113
399 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00024315433
456 Cost-based Query Scrambling for Initial Delays 1998 SIGMOD 0.00022717134
784 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00016675823
876 Parametric Query Optimization 1992 VLDB 0.00015716096
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,727 Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection 2022 VLDB 6.8141709e-05
1,019 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB 0.00014625603
51 Including Group-By in Query Optimization 1994 VLDB 0.00067123727
790 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.0001663283
6,278 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 5.1309442e-05
438 Query Optimization for Parallel Execution 1992 SIGMOD 0.00023199245
2,860 Optimization of Queries with User-defined Predicates 1996 VLDB 7.9934503e-05
4,482 Variance Aware Optimization of Parameterized Queries 2010 SIGMOD 6.1482936e-05
1,070 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB 0.00014316791
2,180 Least Expected Cost Query Optimization: What Can We Expect? 2002 PODS 9.3481968e-05