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.5687882e-05
Overall Rank: 1,821 | 87.76%
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.00016245271
1,606	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00010089789
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.250242e-05
2,524	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3439125e-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,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,950	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3421691e-05
5,039	Leveraging Query Logs and Machine Learning for Parametric Query Optimization	2022	VLDB	6.3023214e-05
5,078	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	6.2857912e-05
5,223	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.2212838e-05
6,800	ROX: Run-time Optimization of XQueries	2009	SIGMOD	5.6792071e-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,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,681	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	4.9793485e-05
11,283	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.9793485e-05
12,971	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	4.9793485e-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,597	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,893	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,106	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
7	996	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
8	5,735	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