Programmierabstraktionen, Übersetzung und Ausführungstechniken für massiv parallele Datenanalyse

Aufgrund fallender Preise zur Speicherung von Daten kann man derzeit eine explosionsartige Zunahme in der Menge der verfügbaren Daten beobachten. Diese Entwicklung gibt Unternehmen und wissenschaftliche Institutionen die Möglichkeit empirische Daten in ungekannter Größenordnung zu analysieren. Für viele Firmen ist die Analyse der gesammelten Daten aus ihrem operationalen Geschäft längst zu einem zentralen strategischen Aspekt geworden. Im Gegensatz zu der seit längerem schon betriebenen Business Intelligence, bestehen diese Analysen nicht mehr nur aus traditionellen relationalen Anfragen. In zunehmendem Anteil kommen komplexe Algorithmen aus den Bereichen Data Mining und Maschinelles Lernen hinzu, um versteckte Muster in den Daten zu erkennen, oder Vorhersagemodelle zu trainieren. Mit zunehmender Datenmenge und Komplexität der Analysen wird jedoch eine neue Generation von Systemen benötigt, die diese Kombination aus Anfragekomplexität und Datenvolumen gewachsen sind. Relationale Datenbanken waren lange Zeit das Zugpferd der Datenanalyse im großen Stil. Grund dafür war zum großen Teil ihre deklarativen Anfragesprache, welche es ermöglichte die logischen und physischen Aspekte der Datenspeicherung und Verarbeitung zu trennen, und Anfragen automatisch zu optimieren. Das starres Datenmodell und ihre beschränkte Menge von möglichen Operationen schränken jedoch die Anwendbarkeit von relationalen Datenbanken für viele der neueren analytischen Probleme stark ein. Diese Erkenntnis hat die Entwicklung einer neuen Generation von Systemen und Architekturen eingeläutet, die sich durch sehr generische Abstraktionen für parallelisierbare analytische Programme auszeichnen; MapReduce kann hier beispielhaft genannt werden, als der zweifelsohne prominenteste Vertreter dieser Systeme. Zwar vereinfachte und erschloss diese neue Generation von Systemen die Datenanalyse in diversen neuen Anwendungsfeldern, sie ist jedoch nicht in der Lage komplexe Anwendungen aus den Bereichen Data Mining und Maschinelles Lernen effizient abzubilden, ohne sich dabei extrem auf spezifische Anwendungen zu spezialisieren. Verglichen mit den relationalen Datenbanken haben MapReduce und vergleichbare Systeme außerdem die deklarative Abstraktion aufgegeben und zwingen den Anwender dazu systemnahe Programme zu schreiben und diese manuell zu optimieren. In dieser Dissertation werden verschiedene Techniken vorgestellt, die es ermöglichen etliche der zentralen Eigenschaften von relationalen Datenbanken im Kontext dieser neuen Generation von daten-parallelen Analysesystemen zu realisieren. Mithilfe dieser Techniken ist es möglich ein Analysesystem zu beschreiben, dessen Programme gleichzeitig sowohl generische und ausdrucksstark, als auch prägnant und deklarativ sind. Im einzelnen stellen wir folgende Techniken vor: Erstens, eine Programmierabstraktion die generisch ist und mit komplexen Datenmodellen umgehen kann, aber gleichzeitig viele der deklarativen Eigenschaften der relationalen Algebra erhält. Programme, die gegen dies Abstraktion entwickelt werden können ähnlich optimiert werden wie relationale Anfragen. Zweitens stellen wir eine Abstraktion für iterative daten-parallele Algorithmen vor. Die Abstraktion unterstützt inkrementelle (delta-basierte) Berechnungen und geht mit zustandsbehafteteten Berechnungen transparent um. Wir beschreiben wie man einen relationalen Anfrageoptimierer erweitern kann so dass dieser iterative Anfragen effektiv optimiert. Wir zeigen dabei dass der Optimierer dadurch in die Lage versetzt wird automatisch Ausführungspläne zu erzeugen, die wohlbekannten, manuell erstellten Programmen entsprechen. Die Abstraktion subsumiert dadurch spezialisierte Systeme (wie Pregel) und bietet vergleichbare Performanz. Drittens stellen wir Methoden vor, um die Programmierabstraktion in eine funktionale Sprachen einzubetten. Diese Integration ermögliche es prägnante Programme zu schreiben und einfach wiederzuverwendenden Komponenten und Bibliotheken, sowie Domänenspezifische Sprachen, zu erstellen. Wir legen dar wie man die Übersetzung und Optimierung des daten-parallelen Programms mit dem Sprachübersetzer der funktionalen Sprache so integriert, dass maximales Optimierungspotenzial besteht.We are witnessing an explosion in the amount of available data. Today, businesses and scientific institutions have the opportunity to analyze empirical data at unpreceded scale. For many companies, the analysis of their accumulated data is nowadays a key strategic aspect. Today’s analysis programs consist not only of traditional relational-style queries, but they use increasingly more complex data mining and machine learning algorithms to discover hidden patterns or build predictive models. However, with the increasing data volume and increasingly complex questions that people aim to answer, there is a need for new systems that scale to the data size and to the complexity of the queries. Relational Database Management Systems have been the work horses of large-scale data analytics for decades. Their key enabling feature was arguably the declarative query language that brought physical schema independence and automatic optimization of queries. However, their fixed data model and closed set of possible operations have rendered them unsuitable for many advanced analytical tasks. This observation made way for a new breed of systems with generic abstractions for data parallel programming, among which the arguably most famous one is MapReduce. While bringing large-scale analytics to new applications, these systems still lack the ability to express complex data mining and machine learning algorithms efficiently, or they specialize on very specific domains and give up applicability to a wide range of other problems. Compared to relational databases, MapReduce and the other parallel programming systems sacrifice the declarative query abstraction and require programmers to implement low-level imperative programs and to manually optimize them. This thesis discusses techniques that realize several of the key aspects enabling the success of relational databases in the new context of data-parallel programming systems. The techniques are instrumental in building a system for generic and expressive, yet concise, fluent, and declarative analytical programs. Specifically, we present three new methods: First, we provide a programming model that is generic and can deal with complex data models, but retains many declarative aspects of the relational algebra. Programs written against this abstraction can be automatically optimized with similar techniques as relational queries. Second, we present an abstraction for iterative data-parallel algorithms. It supports incremental (delta-based) computations and transparently handles state. We give techniques to make the optimizer iteration-aware and deal with aspects such as loop invariant data. The optimizer can produce execution plans that correspond to well-known hand-optimized versions of such programs. That way, the abstraction subsumes dedicated systems (such as Pregel) and offers competitive performance. Third, we present and discuss techniques to embed the programming abstraction into a functional language. The integration allows for the concise definition of programs and supports the creation of reusable components for libraries or domain-specific languages. We describe how to integrate the compilation and optimization of the data-parallel programs into a functional language compiler to maximize optimization potential