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.0208799e-05
Overall Rank: 6,543 | 54.49%
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,736	Efficient Computation of Multiple Group By Queries	2005	SIGMOD	5.3482537e-05
6,763	Robustness Metrics for Relational Query Execution Plans	2018	VLDB	4.9338479e-05
8,448	PARQO: Penalty-Aware Robust Plan Selection in Query Optimization	2024	VLDB	4.5100508e-05
8,845	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	4.4374415e-05
12,338	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	4.1945683e-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.0040449103
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
813	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.0001639584
978	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014881073
3,422	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB	7.1134801e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
7,976	On the Optimality of Strategies for Multiple Joins	1990	PODS	4.613363e-05
7,824	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6418459e-05
10,283	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1945683e-05
6,949	Tree-Width and Functional Dependencies in Databases	2008	PODS	4.8898337e-05
4,194	On the Complexity of Approximate Query Optimization	2002	PODS	6.3697822e-05
978	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014881073
1,826	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00010400425