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: 1121
Venue: PODS
Year: 1997
Pagerank: 5.0160682e-05
Overall Rank: 6,541 | 54.55%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Wolfgang Scheufele
2. Guido Moerkotte

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,742	Efficient Computation of Multiple Group By Queries	2005	SIGMOD	5.3432178e-05
6,763	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	4.9291549e-05
8,440	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	4.505741e-05
8,845	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	4.4331879e-05
12,346	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	4.1905499e-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.0040465394
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00041430126
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556
811	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00016385568
979	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014871114
3,424	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB	7.1066545e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
7,979	On the Optimality of Strategies for Multiple Joins	1990	PODS	4.6089395e-05
7,829	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6373918e-05
10,295	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1905499e-05
6,946	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8874695e-05
4,189	On the Complexity of Approximate Query Optimization	2002	PODS	6.3681294e-05
979	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014871114
1,825	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00010392367