|
Das Dokument ist frei verfügbar |
|
| Nachweis | Kein Nachweis verfügbar |
|
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. |
|
|