Adaptive Join Order Optimization Using Search Space Linearization

Abstract:

Join ordering is one of the core problems of query optimization, as differences in join order can affect the execution time of queries by orders of magnitudes. Unfortunately the problem is NP hard in general, and real world queries can join hundreds of relations, which makes exact solutions prohibitive expensive. In this talk we show how to tackle the join ordering problem by using a search space linearization technique.
This adaptive optimization mechanism allows for a smooth transition from guaranteed optimality to a more greedy approach, depending on the size of problem. In practice, a surprisingly large number of queries can be solved optimally or near optimally, with very low optimization times even for hundreds of relations.