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: 1273
Venue: PODS
Year: 2002
Pagerank: 9.3481968e-05
Overall Rank: 2,180 | 84.84%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
1,300	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00012733214
2,631	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	8.4101843e-05
2,659	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3604734e-05
4,348	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	6.2660237e-05
4,482	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	6.1482936e-05
4,516	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.1178799e-05
4,874	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8594632e-05
5,340	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB	5.5623066e-05
5,466	On the Production of Anorexic Plan Diagrams	2007	VLDB	5.4909203e-05
6,479	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	5.0483805e-05
6,667	Leveraging Query Logs and Machine Learning for Parametric Query Optimization	2022	VLDB	4.9688874e-05
6,874	ROX: Run-time Optimization of XQueries	2009	SIGMOD	4.8978984e-05
7,126	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8232367e-05
8,127	Robust Query Processing: Mission Possible	2020	VLDB	4.579056e-05
8,158	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	4.5730772e-05
9,693	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	4.3027391e-05
10,205	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	4.1945683e-05
10,627	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.1945683e-05
10,751	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	4.1945683e-05
12,488	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	4.1945683e-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	Pagerank
8,213	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.557937e-05
1,726	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.00010741411
1,647	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011033757
4,516	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.1178799e-05
790	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001663283
6,374	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0927058e-05
1,070	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB	0.00014316791
5,676	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS	5.376109e-05
438	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023199245
1,236	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00013117798