Implementierung und Evaluation GPU beschleunigter B+-Bäume in C++/OpenCL

- Bachelorarbeit -


Beschreibung:

Da der Indexzugriff Ausgangspunkt für alle nachfolgenden Verarbeitungsschritte von Anfragen eines DBMS ist, ist ein schneller Indexzugriff wesentlich für die Gesamtperformanz der DBMS. Würden Datenzugriffe ohne die Verwendung von Indexen erfolgen, so müssten die gesamten Daten eingelesen werden, auch wenn das Zugriffsergebnis nur einen kleinen Teil der Daten beinhalten soll. In der Literatur existieren eine Vielzahl von Indexstrukturen, welche hinsichtlich unterschiedliche Eigenschaften wie Speicherbedarf [2, 3, 4, 7], Zugriffszeiten für Einfügen [5, 6], Suchen von einzelnen Einträgen [3, 6] oder Bereichssuche [1, 3] optimiert sind.

 

Im Rahmen dieser Bachelorarbeit soll daher anhand von B+-Bäumen untersucht werden, wie sie mit GPU-Koprozessoren beschleunigt werden können.

 

[1] D. Comer. Ubiquitous B-Tree. ACM Comput. Surv., 11(2):121–137, June 1979.

[2] V. Leis, A. Kemper, and T. Neumann. The adaptive radix tree: Artful indexing for main-memory databases. In ICDE, 2013.

[3] Y. Mao, E. Kohler, and R. T. Morris. Cache craftiness for fast multicore key-value storage. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys ’12, pages 183–196, 2012.

[4] D. R. Morrison. Patricia - practical algorithm to retrieve information coded in alphanumeric. J. ACM, 15(4):514–534, Oct. 1968.

[5] P. O’Neil et al. The log-structured merge-tree (LSM-tree). Acta Informatica, 33(4):351–385, 1996.

[6] R. Pagh and F. Rodler. Cuckoo hashing. J. Algorithms, 51(2):122–144, 2004.

[7] J. Rao and K. A. Ross. Making b+- trees cache conscious in main memory. In SIGMOD, 2000.

[8] H. Zhang, D. G. Andersen, A. Pavlo, M. Kaminsky, L. Ma, and R. Shen. Reducing the storage overhead of main-memory oltp databases with hybrid indexes. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD), pages 1567–1581, 2016.

 

Anforderungen/Kenntnisse:
OpenCL, GPU-Programmierung, Datenbank-Indexe wie etwa B+-Bäume, Radixbäume (mit Varianten wie etwa adaptive Radixbäume), Hashtabellen, LSM-Trees, Mass-Tree, ...

Bearbeitung:

Felix Esch

Betreuung:

Prof. Dr. rer.nat. habil. Sven Groppe
Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 3101 5706