On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)

Summary: Proves finding optimal bushy join plans with cross products is NP-hard, independent of the query graph, so no polynomial algorithm exists for generating optimal bushy trees. For chain queries they provide two polynomial algorithms to generate optimal left-deep plans allowing cross products. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1120
Venue: PODS
Year: 1997
Pagerank: 5.9532278e-05
Overall Rank: 6,164 | 57.72%
DOI: 10.1145/263661.263687

Incoming Non-self Citations Over Time

Authors

1. Wolfgang Scheufele (University of Mannheim)
2. Guido Moerkotte (University of Mannheim)

BibTeX Citation

@inproceedings{scheufele_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)}},
        url = {https://dl.acm.org/doi/10.1145/263661.263687},
        doi = {10.1145/263661.263687},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Scheufele, Wolfgang and Moerkotte, Guido},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,470	Efficient Computation of Multiple Group By Queries	2005	SIGMOD	6.2070458e-05
6,019	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	6.0060149e-05
8,305	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	5.4568571e-05
9,007	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	5.3338237e-05
12,532	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
708	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014727576
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
3,508	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB	7.3566888e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
2	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
3	8,294	On the Optimality of Strategies for Multiple Joins	1990	PODS
4	7,858	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
5	9,969	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB
6	7,029	Tree-Width and Functional Dependencies in Databases	2008	PODS
7	3,553	On the Complexity of Approximate Query Optimization	2002	PODS
8	774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD
9	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
10	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