Beschleunigung von Datenbank-Indexen mittels GPUs

- Masterarbeit -


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. Da nach dem aktuellen Stand der Technik keine Indexstruktur existiert, welche für alle möglichen Einsatzszenarios gleich gut geeignet ist, werden teilweise auch unterschiedliche Indexstrukturen in einem System zu hybriden Indexstrukturen kombiniert [3, 8]. [8] unterscheidet dabei:

- Statische Indexe bieten nur lesenden Zugriff auf einen statischen Datensatz. Statische Indexe können zumeist komprimiert werden, in dem z.B. Zeiger durch Berechnungsvorschriften ersetzt werden. Aktualisierungen sind zumeist nur durch eine äußerst kostspielige Reorganisation der kompletten Indexstruktur möglich.

- Dynamische Indexe bieten schreibenden wie auch lesenden Zugriff auf seinen enthaltenen Datensatz. I.d.R. werden Zeigerstrukturen verwendet, um ein schnelles Aktualisieren zu ermöglichen, so dass der Hauptspeicherbedarf für dynamische Indexe recht groß ist.

- Strukturhybride Indexe sind nach [8] eine Variante des LSM-Baumes für Hauptspeicherdatenbanken zur Verringerung des Hauptspeicherbedarfs. Ein strukturhybrider Index besteht aus einem dynamischen Index, in dem Aktualisierungen wie Einfügen und Löschen vorgenommen werden, sowie einem statischen Index, der einen statischen Datensatz enthält und für den Hauptspeicher komprimiert ist. Bei Suchanfragen werden die Suchergebnisse des dynamischen wie auch des statischen Indexes vereint. Falls der dynamische Index nach vielen Aktualisierungen zu groß wird, so wird dieser in den statischen Index eingebracht.

Da der dynamische und der statische Index intern unterschiedliche Datenstrukturen verwenden, nennen wir diese Indexe strukturhybrid. Die einzelnen Indexe dieser strukturhybriden Indexstrukturen weisen jedoch auch häufig unterschiedliche Anforderungen an die Hardware auf, sind durch unterschiedlichen Speicherzugriffsmuster gekennzeichnet und weisen unterschiedliche Parallelisierungsmöglichkeiten auf. Werden nun unterschiedliche Indexe mit ihren unterschiedlichen Charakteristika für ein DBMS kombiniert, diese aber auf der gleichen Hardwareplattform ausgeführt, bleibt ein signifikantes Optimierungspotential ungenutzt. Im Rahmen dieser Masterarbeit soll daher anhand ausgewählter Indexstrukturen untersucht werden, wie strukturhybride Indexstrukturen auf heterogenen Hardwareplatformen wie CPU mit GPU-Koprozessoren ausgeführt 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, ...

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