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: 8432
Venue: VLDB
Year: 1997
Pagerank: 7.9694937e-05
Overall Rank: 2,878 | 80.00%
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
867	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00015757737
2,053	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.682841e-05
3,398	Statistics on Views	2003	VLDB	7.1381433e-05
3,505	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0304901e-05
3,563	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD	6.9686532e-05
4,939	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	5.8131374e-05
6,333	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.1013149e-05
6,438	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.0552953e-05
6,830	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	4.9081078e-05
8,193	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.5575291e-05
10,872	LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison	2025	VLDB	4.1905499e-05
11,628	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.1905499e-05
12,754	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	4.1905499e-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
134	The EXODUS Optimizer Generator	1987	SIGMOD	0.00043070028
388	Optimization of Large Join Queries	1988	SIGMOD	0.00024654816
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556
569	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00019912758
699	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.0001794078
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
1,313	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012629432
1,465	Experiences Building the Open OODB Query Optimizer	1993	SIGMOD	0.00011846984
2,771	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.149365e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1905499e-05
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
6,732	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS	4.9435849e-05
7,829	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6373918e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
4,390	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.2193128e-05
2,053	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.682841e-05
6,438	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.0552953e-05
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556