Finding the best design options for the parallel dynamic programming approach with skip vector arrays for join-order optimization / Andreas Meister, Gunter Saake (Arbeitsgruppe Datenbanken und Software Engineering)

Abstract

Relational databases need to select efficient join orders as join orders can significantly influence the query execution times. Dynamic programming determines efficient join orders by applying an exhaustive search. Based on the exhaustive search, the applicability of sequential dynamic programming variants is limited to simple queries. To extend the applicability, Han et al. proposed the parallel dynamic programming variant using skip vector arrays (PDPSVA) with specific design options regarding block size, partition reorganization, allocation schema, partition sorting, skip vector arrays, solution mapping, and solution merging. In this paper, we extend the evaluation of Han et al. by empirically evaluating the proposed design choices considering different query topologies. Based on our evaluation results, we identified irrelevant (partition reorganization, allocation schema, and solution merging) and relevant design options (block size, partition sorting, skip vector arrays, solution mapping). For relevant design options, we provide insights how to achieve the best performance for PDPSVA. Overall, our evaluation results should help to use PDPSVA correctly for further evaluations.