Optimizing Join Enumeration in Transformation-based Query Optimizers

Summary: Two cross-product-free rulesets for join-order enumeration in Volcano/Cascades-based optimizers to curb cross-product explosion and duplicate derivations. One extends a simple but complete ruleset; the other is a top-down–inspired efficient set integrated into Volcano/Cascades, proven complete and implemented in PyroJ, delivering up to 100x speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10972
Venue: VLDB
Year: 2014
Pagerank: 5.9071133e-05
Overall Rank: 6,340 | 56.51%
DOI: 10.14778/2732977.2732997

Incoming Non-self Citations Over Time

Authors

1. Anil Shanbhag (Indian Institute of Technology Mumbai)
2. S. Sudarshan (Indian Institute of Technology Mumbai)

BibTeX Citation

@article{shanbhag_vldb14,
        title = {{Optimizing Join Enumeration in Transformation-based Query Optimizers}},
        author = {Shanbhag, Anil and Sudarshan, S.},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {12},
        pages = {1243--1254},
        doi = {10.14778/2732977.2732997},
        url = {https://doi.org/10.14778/2732977.2732997},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
5,399	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	6.2319315e-05
8,374	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	5.4399097e-05
11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	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
71	Including Group-By in Query Optimization	1994	VLDB	0.00038021159
128	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.0003072825
206	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00025092273
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
543	Orthogonal Optimization of Subqueries and Aggregation	2001	SIGMOD	0.0001682612
1,298	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011259156
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.91063e-05
2,275	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.8196821e-05
2,627	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.3284491e-05
4,418	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.7137462e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	143	Optimization of Nonrecursive Queries	1986	VLDB
2	3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
3	774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD
4	1,052	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD
5	2,996	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB
6	128	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD
7	316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB
8	11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB
9	1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD
10	2,627	The Complexity of Transformation-Based Join Enumeration	1997	VLDB