On the Calculation of Optimality Ranges for Relational Query Execution Plans

Summary: Precise optimality ranges for intermediate cardinalities in plans; replaces fixed heuristics with bounds over all competing plans. Derives worst-case bounds on enumeration; real workloads need far fewer plans, enabling Mid-Query Re-Optimization gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hcbcccdea9e2c7e0a
Venue: SIGMOD
Year: 2018
Pagerank: 5.4872821e-05
Overall Rank: 7,597 | 48.93%
DOI: 10.1145/3183713.3183742

Incoming Non-self Citations Over Time

Authors

1. Florian Wolf (Ilmenau University of Technology; SAP)
2. Norman May (SAP)
3. Paul R. Willems (SAP)
4. Kai-Uwe Sattler (Ilmenau University of Technology)

BibTeX Citation

@inproceedings{wolf_sigmod18,
        title = {{On the Calculation of Optimality Ranges for Relational Query Execution Plans}},
        author = {Wolf, Florian and May, Norman and Willems, Paul R. and Sattler, Kai-Uwe},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3183742},
        url = {https://dl.acm.org/doi/10.1145/3183713.3183742},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,113	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	5.8823242e-05
6,706	Tempura: A General Cost-Based Optimizer Framework for Incremental Data Processing	2021	VLDB	5.7049776e-05
6,791	dbET: Execution Time Distribution-based Plan Selection	2023	SIGMOD	5.6811782e-05
8,164	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.3852872e-05
8,389	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.3413016e-05
9,730	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	5.1349531e-05
9,784	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR	5.1285917e-05
10,368	Coresets for Robust Query Optimization	2026	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034106982
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021088704
481	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00017603972
836	Proactive Re-Optimization	2005	SIGMOD	0.00013557047
884	Dynamic Programming Strikes Back	2008	SIGMOD	0.00013267935
1,298	Parametric Query Optimization for Linear and Piecewise Linear Cost Functions	2002	VLDB	0.00011120288
1,726	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.788916e-05
2,251	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.7511987e-05
2,660	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1611913e-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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD
2	646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD
3	272	An Overview of Query Optimization in Relational Systems	1998	PODS
4	3,361	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD
5	6,113	Robustness Metrics for Relational Query Execution Plans	2018	VLDB
6	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
7	15	How Good Are Query Optimizers, Really?	2016	VLDB
8	5,199	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD
9	3,367	Exact Cardinality Query Optimization for Optimizer Testing	2009	VLDB
10	386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB