Hybrid^2-Index Structures for Main Memory Databases
Security and Dependability, Operating-, Communication- and Distributed Systems
Final Report Abstract
An important processing step of database management systems (DBMS) is the access to index structures. This is the starting point for all subsequent processing steps and is therefore of crucial importance for the overall performance of a DBMS. If data accesses were to take place without the use of index structures, the entire data would have to be read, even if the access result is to contain only a small part of the data. In the literature, there are a variety of index structures that are optimized with respect to various properties such as memory requirements, access times when inserting, searching for individual entries or searching over ranges. Most of these methods are optimized for CPU implementations, only a few for hardware accelerators such as GPUs or even FPGAs. A common disadvantage of using hardware accelerators for index processing is that not all index operations can be efficiently executed on the respective hardware platform and that the transfer times between the CPU-based host system and the hardware accelerator exceed the performance gain. In this project, various approaches for accelerating index structures on CPUs, GPUs, FPGAs and APUs were investigated. The focus was on adaptive radix trees (ART), hashtable-based index structures and B+ trees. In addition to optimizations for a single hardware platform, hybrid approaches were also examined in which the CPU and hardware accelerator jointly access a data structure and perform different tasks. The optimizations were particularly concerned with adapting the data structures for efficient use of the memory interfaces of the individual hardware platforms and increasing parallelism in processing. Furthermore, the updating of index structures based on hash tables on GPUs using incremental updates was investigated. Many different methods for collision avoidance and handling, such as lists or pre-sorting, were examined.
Publications
-
“Parallelizing Approximate Search on Adaptive Radix Trees”. Proceedings of the 28th Italian Symposium on Advanced Database Systems, Villasimius, Sud Sardegna, Italy (virtual due to Covid-19 pandemic), 56--67, 2020
Tobias Groth, Sven Groppe, Martin Koppehel & Thilo Pionteck
-
CuART - a CUDA-based, scalable Radix-Tree lookup and update engine. 50th International Conference on Parallel Processing, 1-10. ACM.
Koppehel, Martin; Groth, Tobias; Groppe, Sven & Pionteck, Thilo
-
Accelerated Parallel Hybrid GPU/CPU Hash Table Queries with String Keys. Lecture Notes in Computer Science, 191-203. Springer International Publishing.
Groth, Tobias; Groppe, Sven; Pionteck, Thilo; Valdiek, Franz & Koppehel, Martin
-
Hybrid CPU/GPU/APU accelerated query, insert, update and erase operations in hash tables with string keys. Knowledge and Information Systems, 65(10), 4359-4377.
Groth, Tobias; Groppe, Sven; Pionteck, Thilo; Valdiek, Franz & Koppehel, Martin
