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.5646318e-05
Overall Rank: 1,821 | 87.77%
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
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016244162
1,607	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00010085995
1,989	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.2469024e-05
2,524	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3400278e-05
3,396	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	7.3386533e-05
3,527	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.2283486e-05
4,659	On the Production of Anorexic Plan Diagrams	2007	VLDB	6.4794607e-05
4,857	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB	6.3772435e-05
4,894	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.3648584e-05
4,945	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3418058e-05
5,042	Leveraging Query Logs and Machine Learning for Parametric Query Optimization	2022	VLDB	6.2995365e-05
5,081	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	6.2830143e-05
5,227	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.2183387e-05
6,802	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6773357e-05
7,958	Robust Query Processing: Mission Possible	2020	VLDB	5.4164639e-05
8,348	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.3486679e-05
8,531	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	5.3206021e-05
9,735	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.1325223e-05
10,692	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	4.9769913e-05
11,291	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9769913e-05
12,977	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	4.9769913e-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,603	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
2	1,449	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB
3	1,298	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB
4	4,894	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD
5	644	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
6	6,108	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	995	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
8	5,736	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS
9	446	Query Optimization for Parallel Execution	1992	SIGMOD
10	1,122	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS