GPU-accelerated dynamic programming for join-order optimization / Andreas Meister, Gunter Saake (Arbeitsgruppe Datenbanken und Software Engineering)
Anzeigen / Download619.19 KB
Discovery
1698007345
URN
urn:nbn:de:gbv:3:2-120482
DOI
ISBN
ISSN
Autorin / Autor
Beiträger
Körperschaft
Erschienen
Magdeburg : Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, 07.01.2020
Umfang
1 Online-Ressource (28 Seiten, 0,6 MB) : Illustrationen, Diagramme
Ausgabevermerk
Sprache
eng
Anmerkungen
Inhaltliche Zusammenfassung
Relational databases need to select efficient join orders, as inefficient join orders can increase the query execution time by several orders of magnitude. To select efficient join orders, relational databases can apply an exhaustive search using dynamic programming. Unfortunately, the applicability of sequential dynamic programming variants is limited to simple queries due to the exhaustive search, complexity, and time constraints of the optimization. To extend the applicability, different parallel CPU-based dynamic programming variants were proposed. As GPUs provide more computational resources than CPUs, we propose to use GPUs to further extend the applicability of dynamic programming by reducing the optimization time. Specifically, in this paper, we discuss and evaluate different parallel GPUbased dynamic programming variants, based on DPSIZE and DPSUB. For our evaluation, we used four different query topologies with an increasing query size of up to 20 tables. Our evaluation results indicate that specialized GPUbased dynamic programming variants can significantly reduce the optimization time for complex queries (e.g. up to 93% for clique queries with 15 tables). For larger queries with a lower complexity (linear, cyclic, or star), the evaluated GPU-based dynamic programming variants can provide equivalent optimization times, providing the option to outsource the join-order optimization to GPUs.
Schriftenreihe
Technical report ; 02-2020 ppn:570164265