Dependency-aware parallel enumeration for join-order optimization : search for the best design options / Andreas Meister, Gunter Saake (Arbeitsgruppe Datenbanken und Software Engineering)

Abstract

In relational databases, the execution time of queries can vary by several orders of magnitude depending on the join order. Therefore, efficient join orders need to be selected. A commonly used technique to select efficient join orders is dynamic programming. Since dynamic programming performs an exhaustive search, especially sequential variants of dynamic programming are limited to simple optimization problems based on the complexity and time limit of the optimization. To extend the applicability to complex optimization problems, Han et al. proposed the parallelization strategy dependency-aware parallel enumeration DPEGEN. In this paper, we provide an overview and evaluation of different design options for DPEGEN considering four different query topologies. On the one hand, we reevaluate existing design options, regarding: the partial order, the buffer size, and threading across dependencies. On the other hand, we evaluate new design options, regarding: the enumeration processing, the memo-table type, and buffer type. Based on our results, we recommend to use a sequential dynamic programming variant for the optimization of small queries or linear and cyclic queries. For large star and clique queries, we recommend to use an array-based memo-table with a mapped, initialized array-based buffer using the partial order ’size of larger quantifier set’ with a minimal buffer size of 8,000 in combination with a complete enumeration and without ’threading across dependencies’.