Efficient Enumeration of the Complete Join Search Space
Altan Birler, Thomas Neumann · 2025
Join plan enumeration is a critical step in query optimization, impacting the performance of queries by orders of magnitude. Many queries contain complex non-inner joins, such as outer joins and semi joins, which make the efficient enumeration of all valid join plans difficult. There are existing solutions, but they are either incomplete or expensive. We improve the state-of-the-art join plan enumeration, efficiently handling all cases, including outer joins. Our approach is both complete and efficient by exploiting the properties of relational join transformations.