GPU-accelerated dynamic programming for join-order optimization

Andreas Meister, Gunter Saake
Otto-von-Guericke University, Universitatsplatz 2, 39104 Magdeburg, Saxony-Anhalt, Germany
Otto-von-Guericke-Universität Magdeburg, 2020


   title={GPU-accelerated dynamic programming for join-order optimization},

   author={Meister, Andreas and Saake, Gunter},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2022 hgpu.org

All rights belong to the respective authors

Contact us: