The Complexity of Transformation-Based Join Enumeration

Summary: Complexity of transformation-based join enumeration with exhaustive rule application is analyzed. Duplicates from commutativity/associativity yield O(4^n) operators; a duplication-avoiding scheme within the transformation framework attains the O(3^n) join-enumeration bound, with up to 5x speedup on an 8-table query. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8431
Venue: VLDB
Year: 1997
Pagerank: 7.9808408e-05
Overall Rank: 2,869 | 80.05%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
870	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00015771912
2,050	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.6886663e-05
3,397	Statistics on Views	2003	VLDB	7.1437062e-05
3,462	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0703696e-05
3,560	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD	6.9723858e-05
4,938	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	5.8184655e-05
6,337	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.1053757e-05
6,443	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.0599139e-05
6,832	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	4.9128255e-05
8,213	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.557937e-05
10,868	LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison	2025	VLDB	4.1945683e-05
11,624	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.1945683e-05
12,745	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	4.1945683e-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
132	The EXODUS Optimizer Generator	1987	SIGMOD	0.00042994082
387	Optimization of Large Join Queries	1988	SIGMOD	0.0002471967
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
566	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00019970535
703	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00017916705
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
1,313	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.0001263831
1,466	Experiences Building the Open OODB Query Optimizer	1993	SIGMOD	0.00011857675
2,765	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.1572726e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1945683e-05
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
6,728	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9483326e-05
7,824	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6418459e-05
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
4,397	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.2230918e-05
2,050	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.6886663e-05
6,443	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.0599139e-05
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348