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: h63ac9c1f3be98950
Venue: VLDB
Year: 2014
Pagerank: 5.7993259e-05
Overall Rank: 6,396 | 57.00%
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,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.0001160797
5,425	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	6.1349269e-05
8,493	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	5.3310013e-05
10,334	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0254535e-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
73	Including Group-By in Query Optimization	1994	VLDB	0.00037522101
129	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.0003040756
213	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00024759805
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021088704
552	Orthogonal Optimization of Subqueries and Aggregation	2001	SIGMOD	0.0001653835
1,301	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011112842
1,726	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.788916e-05
2,251	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.7511987e-05
2,660	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1611913e-05
4,464	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.5877622e-05

Semantically Similar Papers

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