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.7783355e-05
Overall Rank: 6,409 | 57.05%
DOI: 10.14778/2732977.2732997
PDF: Download (CC BY-NC-ND 3.0)

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,185	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011586181
5,446	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	6.1117489e-05
8,517	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	5.3110227e-05
10,368	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0064651e-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.00037420958
129	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.00030314403
213	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00024695393
322	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021032289
554	Orthogonal Optimization of Subqueries and Aggregation	2001	SIGMOD	0.00016487919
1,293	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011143846
1,732	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.7561649e-05
2,261	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.7351549e-05
2,671	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1310287e-05
4,486	On the Correct and Complete Enumeration of the Core Search Space	2013	SIGMOD	6.5638966e-05

Semantically Similar Papers

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