Optimization Strategy of Bidirectional Join Enumeration in 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. As modern microprocessors employ multiple cores to accelerate computations, the parallel optimization algorithm has been proposed to parallelize the Bottom-up DP query optimization process. However Top-down DP method can derive upper bounds for the costs of the plans it generates which is not available to typical Bottom-up DP method since such method generate and cost all subplans before considering larger containing plans. This paper combined the enhancements of two approaches and proposes a comprehensive and practical algorithm based graph-traversal driven, referred to here as DPbid, for parallelizing query optimization in the multi-core processor architecture. This paper has implemented such a search strategy and experimental results show that can improve optimization time effective compared to known existing algorithms.
Y. H. Chen et al., "Optimization Strategy of Bidirectional Join Enumeration in Multi-Core CPUS", Applied Mechanics and Materials, Vols. 44-47, pp. 383-387, 2011