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: 1272
Venue: PODS
Year: 2002
Pagerank: 9.738718e-05
Overall Rank: 1,795 | 87.69%
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
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
1,604	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00010230973
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.3517129e-05
2,540	Multi-Objective Parametric Query Optimization	2015	VLDB	8.45187e-05
3,506	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.3581509e-05
3,513	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	7.354613e-05
4,616	On the Production of Anorexic Plan Diagrams	2007	VLDB	6.6048588e-05
4,790	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.5068083e-05
4,817	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB	6.4944225e-05
5,124	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.3567981e-05
5,281	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	6.2842378e-05
5,394	Leveraging Query Logs and Machine Learning for Parametric Query Optimization	2022	VLDB	6.2336084e-05
5,529	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.18591e-05
6,688	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.8015211e-05
7,829	Robust Query Processing: Mission Possible	2020	VLDB	5.5360082e-05
8,211	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.4658735e-05
9,796	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.21848e-05
10,494	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	5.093636e-05
10,881	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	5.093636e-05
10,986	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.093636e-05
12,681	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	5.093636e-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,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
2	1,470	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB
3	1,321	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB
4	4,790	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD
5	664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
6	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	984	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
8	5,615	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS
9	434	Query Optimization for Parallel Execution	1992	SIGMOD
10	1,104	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS