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: h125eac5eb7a916bf
Venue: VLDB
Year: 1997
Pagerank: 8.1574087e-05
Overall Rank: 2,660 | 82.13%
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
870	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013342453
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.7849752e-05
3,134	Statistics on Views	2003	VLDB	7.6093829e-05
3,215	Efficient and Provable Multi-Query Optimization	2017	PODS	7.5233633e-05
4,040	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD	6.8357679e-05
4,465	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.5849117e-05
6,138	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.8732713e-05
6,399	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.796784e-05
6,809	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	5.6755734e-05
7,603	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.4846849e-05
11,449	LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison	2025	VLDB	4.9769913e-05
12,127	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.9769913e-05
13,234	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	4.9769913e-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
118	The EXODUS Optimizer Generator	1987	SIGMOD	0.00031381726
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021082176
469	Optimization of Large Join Queries	1988	SIGMOD	0.00017749337
726	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014459508
796	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00013931773
821	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00013655214
859	Query Optimization by Simulated Annealing	1987	SIGMOD	0.0001341356
1,032	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012396854
1,376	Experiences Building the Open OODB Query Optimizer	1993	SIGMOD	0.0001086956
2,627	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.2030431e-05

Semantically Similar Papers

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