Least Expected Cost Query Optimization: What Can We Expect?

Summary: Evaluates least-expected-cost planning versus optimizing for a 'typical' parameter; carefully chosen typical values often suffice for expected runtime. But expected-cost minimization encodes a linear utility of runtime (ratios) and can be suboptimal; least-expected-cost optimization yields significant gains under several alternative cost/utility models. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hedf309d4c33a7723
Venue: PODS
Year: 2002
Pagerank: 9.5366955e-05
Overall Rank: 1,831 | 87.73%
DOI: 10.1145/543613.543651

Incoming Non-self Citations Over Time

Authors

1. Francis Chu (Cornell University)
2. Joseph Halpern (Cornell University)
3. Johannes Gehrke (Cornell University)

BibTeX Citation

@inproceedings{chu_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{Least Expected Cost Query Optimization: What Can We Expect?}},
        url = {https://dl.acm.org/doi/10.1145/543613.543651},
        doi = {10.1145/543613.543651},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chu, Francis and Halpern, Joseph and Gehrke, Johannes},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016221103
1,604	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00010086711
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.2323722e-05
2,531	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3140235e-05
3,406	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	7.3151509e-05
3,531	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.2065332e-05
4,674	On the Production of Anorexic Plan Diagrams	2007	VLDB	6.4584193e-05
4,876	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB	6.357646e-05
4,916	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.3450917e-05
4,971	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3209003e-05
5,062	Leveraging Query Logs and Machine Learning for Parametric Query Optimization	2022	VLDB	6.2791511e-05
5,101	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	6.2623728e-05
5,248	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.1980997e-05
6,816	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6593309e-05
7,975	Robust Query Processing: Mission Possible	2020	VLDB	5.3985544e-05
8,361	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.3310744e-05
8,550	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3030089e-05
9,767	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.115551e-05
10,753	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	4.9605343e-05
11,347	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9605343e-05
13,019	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,619	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
2	1,453	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB
3	1,304	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB
4	4,916	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD
5	646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
6	6,122	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	996	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
8	5,730	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS
9	448	Query Optimization for Parallel Execution	1992	SIGMOD
10	1,124	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS