The Complexity of Transformation-Based Join Enumeration

Summary: Shows that standard associativity/commutativity transformations generate O(4^n) duplicate join operators. A duplicate-free transformation scheme reaches the O(3^n) lower bound, improving 8-table optimization by up to 5×. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8622
Venue: VLDB
Year: 1997
Pagerank: 8.3284491e-05
Overall Rank: 2,627 | 81.98%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Arjan Pellenkoft (Centrum Wiskunde & Informatica; Microsoft)
2. César A. Galindo-Legaria (Microsoft)
3. Martin Kersten (Centrum Wiskunde & Informatica)

BibTeX Citation

@article{pellenkoft_vldb97,
        title = {{The Complexity of Transformation-Based Join Enumeration}},
        author = {Pellenkoft, Arjan and Galindo-Legaria, César A. and Kersten, Martin},
        journal = {PVLDB},
        series = {{VLDB} '97},
        pages = {306--315},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013611183
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.91063e-05
3,093	Statistics on Views	2003	VLDB	7.7664764e-05
3,268	Efficient and Provable Multi-Query Optimization	2017	PODS	7.5810998e-05
3,970	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD	6.9835426e-05
4,418	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.7137462e-05
6,026	Parallelizing Extensible Query Optimizers	2009	SIGMOD	6.0024042e-05
6,340	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.9071133e-05
6,671	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	5.807209e-05
7,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.6041473e-05
11,091	LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison	2025	VLDB	5.093636e-05
11,819	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	5.093636e-05
12,938	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	5.093636e-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
119	The EXODUS Optimizer Generator	1987	SIGMOD	0.0003183602
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
463	Optimization of Large Join Queries	1988	SIGMOD	0.00018064961
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
801	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00013909408
839	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013692785
1,037	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012494928
1,341	Experiences Building the Open OODB Query Optimizer	1993	SIGMOD	0.00011108876
2,582	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.3875949e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
2	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
3	5,854	Conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis	2023	PODS
4	7,858	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
5	5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
6	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
7	4,346	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD
8	1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD
9	6,340	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB
10	316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB