Complete Join Reordering for Null-Intolerant Joins

The join reordering problem is a core task in query optimization to find the most efficient evaluation order for join operations. The Enhanced Compensation-based Approach (ECA) is the state-of-the-art approach for this problem which is based on using new operators called compensation operators to enlarge the query plan search space with more join reorderings. However, ECA cannot provide complete join reorderability for queries involving one or more full outerjoins. In this paper, we present the first complete join reordering solution, named CJR. By introducing a new and more expressive compensation operator and an enhanced set of rewriting rules, CJR is able to provide complete join reorderability for all join queries with null-intolerant join predicates. Our experimental results on the Join Order Benchmark demonstrate that CJR can improve query performance by a factor of 12.32.