Time: upon consultation
Quantity: 0V/0Ü/8P
Language: German (English on request)
Modules: INF-04-KP, INF-PM-FPG, MINF-04-KP-FG3

Hands-on hashing

Motivation

Im Bereich der effizienten Verarbeitung von analytischen Anfragen (OLAP) sind Joins von substantieller Bedeutung. Generell kann bei Join-Implementierung zwischen Nested-Loop-, Sort-Merge- und Hash-Joins unterschieden werden. Durch seine robusten Eigenschaften und hohe durchschnittliche Performance hat sich der Hash-Join in der Praxis durchgesetzt. Das spiegelt sich auch im Bereich der Datenbankforschung wider. In den vergangenen Dekaden bis heute wurden und werden Hash-Joins in allen denkbaren Dimensionen erforscht (z.B. strukturelle Aspekte, verwendete Hash-Funktionen, Hash-Kollisionsbehebungstechniken, etc.) [1]. Im besonderen Maße hat die verwendete Hashfunktion Einfluss auf die Gesamtausführungszeit eines Hash-Joins, da sie für jeden Wert ausgeführt werden muss und mögliche Kollisionen entsprechend behandelt werden müssen. Dementsprechend sollte eine ideale Hash-Funktion möglichst performant sein und die Eingabedaten möglichst uniform im Zielraum abbilden. Besonders letzteres ist jedoch stark von den verarbeiteten Daten und deren Eigenschaften abhängig.

Aufgabe

Im Praktikum “Hands on hashing” werden die teilnehmenden Studierenden den Einfluss von Daten und Dateneigenschaften auf verschiedene Hash-Funtkionen strukturiert untersuchen. Dafür werden in einem ersten Schritt ausgewählte Daten eines “Real-World Benchmarks ” (Join-Order Benchmark (JOB) [2]) analysiert (Kardinalität, Werteverteilung, …) und klassifiziert.

Im nächsten Schritt werden durch die Studierenden verschiedene Hash-Funktionen implementiert und getestet (z.B. Multiply-Shift [3], Multiply-Add-Shift [4], Tabulation Hashing [5], SpookyHash, SDBM, Murmur [6], HighwayHash, SipHash).
Die Hash-Funktionen werden anschließend in ein vom Lehrstuhl für Datenbanken bereitgestelltes Framework integriert und unter Verwendung der analysierten Daten gebenchmarked.

Abschließend werden die geleistete Arbeit sowie die Ergebnisse von den Studenten in einem Kolloquium vorgestellt und diskutiert.

Anforderungen

  • Grundlegende Kenntnisse in C/C++, Algorithmisches Verständnis, Interesse im Bereich der Datenverarbeitung, Freude am Programmieren und Benchmarken (erforderlich)
  • Kenntnisse in SIMD-Verarbeitung (wünschenswert, falls nicht vorhanden, werden wir eine Einführung geben)

Ansprechpartner

Administratives

  • Umfang: 0/0/8 SWS
  • Einschreibung per E-Mail über Dirk Habich oder Johannes Pietrzyk bis Donnerstag, den 15.04.2021, 23:59 GMT+2

Literatur

[1] Richter, S. et al.: A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing. Proc. VLDB Endow. 9(3), 96-107 (2015).
[2] Leis, V. et al.: Query optimization through the looking glass, and what we found running the Join Order Benchmark. VLDBJ 27(5), 643-668 (2018).
[3] Dietzfelbinger, M. et al.: A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms 25(1), 19 – 51 (1997).
[4] Dietzfelbinger, M.: Universal hashing and k-wise independent random variables via integer arithmetic without primes. STACS, 569–580 (1996).
[5] Patrascu, M., Thorup, M.: The power of simple tabulation hashing. J. ACM 59(3), 14:1–14:50, (2012).
[6] Appleby, A.: Murmurhash3 64-bit finalizer. Version 19/02/15. https://code.google.com/p/smhasher/wiki/MurmurHash3