Efficient indexing for big data in Hadoop MapReduce and main memory databases

Abstract

In recent years, the database community has witnessed the advent and breakthrough of many new system designs like the famous Hadoop MapReduce or main memory databases like MonetDB, Hekaton, SAP Hana, and HyPer to solve the problems of “Big Data”. The system architectures in this generation of emerging systems often radically differ from traditional relational databases. For database research, this trend creates new challenges to design and optimize data structures for those novel architectures. Premier candidates for innovations are index structures, which are traditionally among the most crucial performance factors in databases. In this thesis, we focus on efficient indexing methods for Hadoop MapReduce and main memory databases. Our work consists of three independent parts that resulted from different research projects. In the first part, we introduce HAIL, a novel approach for efficient static and adaptive indexing in Hadoop MapReduce. We believe that efficient indexing becomes increasingly important in the context of very large data sets. HAIL combines very low index build times that are often even invisible for users, with significant runtime improvements for selective MapReduce jobs. We provide extensive experiments, and show that HAIL can improve job runtimes by up to 68x over Hadoop. In the second part of this thesis, we present an in-depth evaluation of the adaptive radix tree ART, a recent and very promising competitor in the domain of tree-indexes for main memory databases. ART was reported by its inventors to be significantly faster than previous tree indexes and even competitive to hash tables. However, the original evaluation of ART did not consider Judy Arrays, which is, to the best of our knowledge, the first data structure introducing adaptivity to radix trees. Furthermore, the hash table used in the comparison with ART was just a textbook implementation of chained hashing and not a more sophisticated state-of-the-art hash tables. We provide an extended analysis and experimental evaluation of ART, including a detailed comparison to Judy Arrays, hashing via quadratic probing, and three variants of Cuckoo hashing. Our results give a more differentiated look on ART. In particular, we present striking conceptual similarities between ART and Judy Arrays and show that well-engineered hash tables can beat the lookup throughput of adaptive radix trees by up 6x. In the third part, motivated by our previous results, we take a closer look at hashing methods in main memory databases. We identify seven key factors that influence hashing performance, evaluate their impact, and discuss the implications on hashing in modern databases. Our study indicates that choosing the right hashing method and configuration can make an order of magnitude difference in insert and lookup performance. We also provide a guideline for practitioners on when to use which hashing method.

In den letzten Jahren hat die Datenbank-Community das Aufkommen und den Durchbruch von vielen neuartigen Systementwürfen erlebt, deren übergeordnetes Ziel es ist, die Probleme im Bereich “Big Data” zu lösen. Wichtige Beispiele hierfür sind das berühmte Hadoop MapReduce oder Hauptspeicher-Datenbanken wie MonetDB, Hekaton, SAP Hana und Hyper. Die Architekturen in dieser Generation von Systemen unterscheiden sich oft grundlegend von den Ansätzen traditioneller relationaler Datenbanken. Für die Datenbankforschung schafft diese Entwicklung neue Herausforderungen im Zusammenhang mit dem Entwurf passender Datenstrukturen und deren Optimierung in diesem neuen Kontext. Zu den herausragenden Kandidaten für Innovationen zählen hierbei Indexstrukturen, die traditionell zu den wichtigsten Leistungsfaktoren in Datenbanken gehören. In dieser Arbeit konzentrieren wir uns auf effiziente Indexierungsmethoden für Hadoop MapReduce und Hauptspeicher-Datenbanken. Unser Beitrag besteht dabei aus drei unabhängigen Teilen, die jeweils aus verschiedenen Forschungsprojekten in diesem Bereich entstanden sind. Im ersten Teil präsentieren wir HAIL als neue Methode für effizientes statisches und adaptives Indizieren in Hadoop MapReduce, einem Framework für verteilte Datenverarbeitung auf großen Rechnernetzwerken. Wir glauben, dass effiziente Indizierung im Hinblick auf die sehr großen Datenmengen in typischen Hadoop Systemen besonders wichtig ist. HAIL kombiniert eine sehr niedrige Indexierungszeit, die für die Nutzer zumeist sogar unsichtbar bleibt, mit erheblichen Laufzeitverbesserungen für selektive MapReduce Jobs. Wir präsentieren umfangreiche Experimente hierzu und zeigen, dass HAIL Job-Laufzeiten gegenüber Hadoop um bis zu 68x verbessert. Im zweiten Teil dieser Arbeit präsentieren wir eine umfassende Analyse von ART, einem adaptiven Radix-Baum, der einen sehr vielversprechenden Wettbewerber auf dem Gebiet der Indexbäume für Hauptspeicher-Datenbanken darstellt. Die Erfinder von ART erklären in ihrer Arbeit, dass ART deutlich schneller als vorherige Indexbäume ist und sogar an die Leistung von Hash Tabellen heranreicht. Allerdings fehlt in dieser ursprünglichen Studie ein Vergleich von ART mit Judy Arrays, welches nach unserem Wissen der erste adaptive Radix-Baum ist. Des Weiteren basieren die gezeigten Ergebnisse im Zusammenhang mit Hash Tabellen lediglich auf einem Vergleich von ART mit einer einfachen Implementierung von Chained Hashing, anstelle von optimierten Hash Tabellen auf dem neusten Stand der Technik. Wir liefern eine erweiterte Studie zu ART, einschließlich detaillierter Vergleiche mit Judy Arrays, mit Quadratic Probing sowie mit drei Varianten von Cuckoo Hashing. Unsere Ergebnisse erlauben eine differenziertere Bewertung von ART. Insbesondere erläutern wir auch die auffälligen konzeptionellen Ähnlichkeiten zwischen ART und Judy Arrays. Weiterhin zeigen unsere experimentellen Ergebnisse, dass der Durchsatz für Suchanfragen bei Hash Tabellen um bis zu einem Faktor von 6 höher ist als bei adaptiven Radix-Bäumen. Im dritten Teil, zu dem uns unsere vorangehenden Ergebnisse motiviert haben, werfen wir einen genaueren Blick auf Hashing-Verfahren für Hauptspeicher-Datenbanken. Wir identifizieren sieben Schlüsselfaktoren, welche die Leistung von Hash Tabellen beeinflussen. Darüber hinaus diskutieren wir die Auswirkungen dieser Faktoren und die Konsequenzen für Hashing in modernen Datenbanken. Unsere Studie zeigt deutlich, dass die Wahl der richtigen Hash-Verfahren und deren korrekte Konfiguration einen Unterschied von einer Größenordnung bei der Leistung für Einfüge- und Suchoperationen machen kann. Abschließend bieten wir auch einen praktischen Leitfaden an, der dabei hilft, das beste Hashing-Verfahren für eine konkrete Problemstellung zu finden.