Optimization Strategy of Top-Down Join Enumeration on Modern Multi-Core CPUs

Most contemporary database systems query optimizers exploit System-R’s bottom-up dynamic programming method (DP) to find the optimal query execution plan (QEP) without evaluating redundant sub-plans. The distinguished exceptions are Volcano/Cascades using transforms to generate new plans according to a top-down approach. As recent research has revealed, bottom-up dynamic programming can improve performance with respect to the shape of the join graph and parallelism. However top-down join enumeration dynamic programming method can derive upper bounds for the costs of the plans it generates which is not available to typical bottom-up DP method. In this paper, we propose a comprehensive and practical framework for parallelizing top-down dynamic programming query optimization with complex non-inner join in the multi-core processor architecture, referred as PTDhyp. We have implemented such a search strategy and experimental results show that can improve optimization time effective compared to known existing algorithms.