Dependency-aware parallel enumeration for join-order optimization : search for the best design options / Andreas Meister, Gunter Saake (Arbeitsgruppe Datenbanken und Software Engineering)
VerfasserMeister, Andreas ; Saake, Gunter
ErschienenMagdeburg : Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, [07.01.2020]
Umfang1 Online-Ressource (34 Seiten, 0,52 MB) : Illustrationen, Diagramme
SerieTechnical report ; 01-2020
 Das Dokument ist frei verfügbar
Dependency-aware parallel enumeration for join-order optimization [0.52 mb]
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’.