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.3429142e-05
Overall Rank: 2,187 | 84.81%
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
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
1,297	The Picasso Database Query Optimizer Visualizer	2010	VLDB	0.00012732768
2,632	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	8.4153283e-05
2,652	Multi-Objective Parametric Query Optimization	2015	VLDB	8.3662031e-05
4,342	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	6.2680535e-05
4,480	Variance Aware Optimization of Parameterized Queries	2010	SIGMOD	6.1433292e-05
4,517	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.1143396e-05
4,876	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8544467e-05
5,344	Efficiently Approximating Query Optimizer Plan Diagrams	2008	VLDB	5.5579641e-05
5,476	On the Production of Anorexic Plan Diagrams	2007	VLDB	5.4866057e-05
6,471	Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees	2017	SIGMOD	5.0438582e-05
6,639	Leveraging Query Logs and Machine Learning for Parametric Query Optimization	2022	VLDB	4.976781e-05
6,879	ROX: Run-time Optimization of XQueries	2009	SIGMOD	4.8934866e-05
7,122	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8199209e-05
8,130	Robust Query Processing: Mission Possible	2020	VLDB	4.5746794e-05
8,162	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	4.5686903e-05
9,692	ROME: Robust Query Optimization via Parallel Multi-Plan Execution	2024	SIGMOD	4.2986161e-05
10,205	RIB: Robust Learning-based Index Benefit Estimation	2026	SIGMOD	4.1905499e-05
10,635	Robust Plan Evaluation based on Approximate Probabilistic Machine Learning	2025	VLDB	4.1905499e-05
10,757	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	4.1905499e-05
12,497	Asking the Right Questions: Model-driven Optimization using Probes	2006	PODS	4.1905499e-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,193	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.5575291e-05
1,725	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB	0.0001073575
1,644	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.0001102889
4,517	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD	6.1143396e-05
786	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00016624743
6,372	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0878306e-05
1,064	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB	0.00014348262
5,687	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS	5.3711581e-05
439	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023183237
1,234	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00013115865