Query Simplification: Graceful Degradation for Join-Order Optimization

Summary: New approach to join-order optimization: when exact planning is intractable on large queries, simplify the join graph within a time budget. Safe-first, then riskier simplifications enable optimal results, with a directing strategy and graceful degradation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4197
Venue: SIGMOD
Year: 2009
Pagerank: 7.1051056e-05
Overall Rank: 3,813 | 73.85%
DOI: 10.1145/1559845.1559889

Incoming Non-self Citations Over Time

Authors

1. Thomas Neumann (Max Planck Institute)

BibTeX Citation

@inproceedings{neumann_sigmod09,
        title = {{Query Simplification: Graceful Degradation for Join-Order Optimization}},
        author = {Neumann, Thomas},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559889},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559889},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
3,205	On Optimizing Operator Fusion Plans for Large-Scale Machine Learning in SystemML	2018	VLDB	7.6386536e-05
3,903	Keep It Simple: Testing Databases via Differential Query Plans	2024	SIGMOD	7.0304586e-05
4,849	Bitvector-aware Query Optimization for Decision Support Queries	2020	SIGMOD	6.4803828e-05
5,626	Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware	2023	SIGMOD	6.1440728e-05
7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.5237338e-05
7,910	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	5.5181056e-05
9,042	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.3256042e-05
9,450	Engineering High-Performance Database Engines	2014	VLDB	5.2660195e-05
9,969	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	5.1845938e-05
10,218	Detecting Join Bugs in Database Engines via Join Implication Reasoning	2026	SIGMOD	5.093636e-05
10,852	Accio: Bolt-on Query Federation	2025	VLDB	5.093636e-05
11,160	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	5.093636e-05
11,338	A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.0024089429
143	Optimization of Nonrecursive Queries	1986	VLDB	0.0002959213
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
463	Optimization of Large Join Queries	1988	SIGMOD	0.00018064961
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
1,013	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012652549
1,298	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011259156
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.91063e-05
2,996	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB	7.8745175e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,272	SQL Query Optimization: Reordering for a General Class of Queries	1996	SIGMOD
2	3,553	On the Complexity of Approximate Query Optimization	2002	PODS
3	463	Optimization of Large Join Queries	1988	SIGMOD
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	18	How Good Are Query Optimizers, Really?	2016	VLDB
6	11,909	Improving Join Reorderability with Compensation Operators	2018	SIGMOD
7	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
8	3,959	Simplicity Done Right for Join Ordering	2021	CIDR
9	7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
10	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD