DBScholar

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
hb4cd1dc4b5ae38d0
Venue
PODS
Year
1999
Pagerank
0.0001193884
Overall Rank
1,122 | 92.46%
DOI
10.1145/303976.303990

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{chu_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Least Expected Cost Query Optimization: An Exercise in Utility}},
        url = {https://dl.acm.org/doi/10.1145/303976.303990},
        doi = {10.1145/303976.303990},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chu, Francis and Halpern, Joseph Y. and Seshadri, Praveen},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank Citing Paper Year Venue Pagerank
569 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016245271
836 Proactive Re-Optimization 2005 SIGMOD 0.00013557047
888 Pay-as-you-go User Feedback for Dataspace Systems 2008 SIGMOD 0.00013255989
1,606 The Picasso Database Query Optimizer Visualizer 2010 VLDB 0.00010089789
1,612 AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions 2003 VLDB 0.00010072731
2,826 Relaxed Currency and Consistency: How to Say "Good Enough" in SQL 2004 SIGMOD 7.9678605e-05
3,396 Variance Aware Optimization of Parameterized Queries 2010 SIGMOD 7.3418098e-05
3,527 Identifying Robust Plans through Plan Diagram Reduction 2008 VLDB 7.2310714e-05
4,045 Adaptive Query Processing in the Looking Glass 2005 CIDR 6.8328968e-05
4,657 On the Production of Anorexic Plan Diagrams 2007 VLDB 6.4824233e-05
4,855 Efficiently Approximating Query Optimizer Plan Diagrams 2008 VLDB 6.3799739e-05
4,893 A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters 2003 SIGMOD 6.3677985e-05
4,912 A Top-Down Approach to Achieving Performance Predictability in Database Systems 2017 SIGMOD 6.3578361e-05
5,039 Leveraging Query Logs and Machine Learning for Parametric Query Optimization 2022 VLDB 6.3023214e-05
5,316 CliffGuard: A Principled Framework for Finding Robust Database Designs 2015 SIGMOD 6.1836681e-05
5,656 Uncertainty Aware Query Execution Time Prediction 2014 VLDB 6.0488629e-05
5,988 On the Stability of Plan Costs and the Costs of Plan Stability 2010 VLDB 5.9257426e-05
7,954 Robust Query Processing: Mission Possible 2020 VLDB 5.4190023e-05
8,345 MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates 2020 SIGMOD 5.3511996e-05
8,389 PARQO: Penalty-Aware Robust Plan Selection in Query Optimization 2024 VLDB 5.3413016e-05
8,449 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB 5.3350162e-05
8,524 ROME: Robust Query Optimization via Parallel Multi-Plan Execution 2024 SIGMOD 5.3231221e-05
9,730 PAR2QO: Parametric Penalty-Aware Robust Query Optimization 2025 VLDB 5.1349531e-05
10,368 Coresets for Robust Query Optimization 2026 PODS 4.9793485e-05
12,971 Asking the Right Questions: Model-driven Optimization using Probes 2006 PODS 4.9793485e-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.0023947656
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
109 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.0003276959
149 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00028981723
289 Optimization of Dynamic Query Evaluation Plans 1994 SIGMOD 0.0002196543
424 Cost-based Query Scrambling for Initial Delays 1998 SIGMOD 0.0001848836
487 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00017462723
708 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00014629998
792 Parametric Query Optimization 1992 VLDB 0.00013942753
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,690 Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection 2022 VLDB
2 682 Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques 2012 VLDB
3 73 Including Group-By in Query Optimization 1994 VLDB
4 646 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD
5 5,656 Uncertainty Aware Query Execution Time Prediction 2014 VLDB
6 2,516 Optimization of Queries with User-defined Predicates 1996 VLDB
7 446 Query Optimization for Parallel Execution 1992 SIGMOD
8 3,396 Variance Aware Optimization of Parameterized Queries 2010 SIGMOD
9 996 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB
10 1,821 Least Expected Cost Query Optimization: What Can We Expect? 2002 PODS