Hybrid^2-Indexstrukturen für Hauptspeicherdatenbanken

• Antragsteller: Professor Dr. Sven Groppe; Professor Dr.-Ing. Thilo Pionteck
• Fachliche Zuordnung: Rechnerarchitektur, eingebettete und massiv parallele Systeme ; Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
• Förderung: Förderung von 2019 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 422742661

• Erstellungsjahr: 2025

Zusammenfassung der Projektergebnisse

Ein wichtiger Verarbeitungsschritt von Datenbankmanagementsystemen (DBMS) ist der Zugriff auf Indexstrukturen. Dieser stellt den Ausgangspunkt für alle nachfolgenden Verarbeitungsschritte dar und ist somit für die Gesamtperformance eines DBMS von entscheidender Bedeutung. Würden Datenzugriffe ohne die Verwendung von Indexstrukturen erfolgen, müssten die gesamten Daten gelesen werden, auch wenn das Zugriffsergebnis nur einen kleinen Teil der Daten enthalten soll. In der Literatur gibt es eine Vielzahl von Indexstrukturen, die hinsichtlich verschiedener Eigenschaften wie Speicherbedarf, Zugriffszeiten beim Einfügen, Suche nach einzelnen Einträgen oder Suche über Bereiche optimiert sind. Die meisten dieser Verfahren sind für CPU-Implementierungen optimiert, nur wenige für Hardware-Beschleuniger wie GPUs oder sogar FPGAs. Ein häufiger Nachteil bei der Verwendung von Hardwarebeschleunigern für die Indexverarbeitung ist, dass nicht alle Indexoperationen effizient auf der jeweiligen Hardwareplattform ausgeführt werden können und dass die Transferzeiten zwischen dem CPU-basierten Hostsystem und dem Hardwarebeschleuniger den Geschwindigkeitsgewinn übersteigen. In diesem Projekt wurden verschiedene Ansätze zur Beschleunigung von Indexstrukturen auf CPUs, GPUs, FPGAs und APUs untersucht. Der Fokus lag dabei auf Adaptive Radix (ART) Bäumen, Hashtable-basierten Indexstrukturen und B+ Bäumen. Neben Optimierungen für eine Hardwareplattform wurden auch hybride Ansätze untersucht, bei denen CPU und Hardwarebeschleuniger gemeinsam auf eine Datenstruktur zugreifen und unterschiedliche Aufgaben übernehmen. Die Optimierungen betrafen insbesondere die Anpassung der Datenstrukturen zur effizienten Nutzung der Speicherschnittstellen der einzelnen Hardwareplattformen sowie die Erhöhung der Parallelität in der Verarbeitung. Weiterhin wurde die Aktualisierung von Indexstrukturen auf Basis von Hashtabellen auf GPUs mittels inkrementeller Updates untersucht. Dabei wurden viele verschiedene Verfahren zur Kollisionsvermeidung bzw. -behandlung wie Listen oder Vorsortierung untersucht.

Projektbezogene Publikationen (Auswahl)

• “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