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.1611913e-05
Overall Rank: 2,660 | 82.12%
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
869	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013348278
1,726	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.788916e-05
3,133	Statistics on Views	2003	VLDB	7.6127492e-05
3,214	Efficient and Provable Multi-Query Optimization	2017	PODS	7.5269127e-05
4,038	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD	6.8389401e-05
4,464	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.5877622e-05
6,136	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.8759799e-05
6,396	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.7993259e-05
6,804	Stacked Indexed Views in Microsoft SQL Server	2005	SIGMOD	5.6782614e-05
7,597	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.4872821e-05
11,443	LEAP: A Low-cost Spark SQL Query Optimizer using Pairwise Comparison	2025	VLDB	4.9793485e-05
12,121	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.9793485e-05
13,228	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	4.9793485e-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.00031392616
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021088704
470	Optimization of Large Join Queries	1988	SIGMOD	0.00017755852
725	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014465736
796	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00013938011
821	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD	0.00013660347
859	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013418999
1,032	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012401489
1,376	Experiences Building the Open OODB Query Optimizer	1993	SIGMOD	0.00010874518
2,626	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.2068909e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
2	1,186	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,015	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
5	5,482	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
6	2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
7	4,415	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD
8	1,726	Optimal Top-Down Join Enumeration	2007	SIGMOD
9	6,396	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB
10	321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB