Datenverarbeitung auf heterogener Hardware

The primary objective of data processing research on modern hardware is to understand how to utilize emerging technology to process data efficiently. Over the last decades, Software Engineers and Computer Scientists have made significant progress towards this goal, providing highly-tuned algorithms, systems & mechanisms for a wide variety of different device types. However, while we mostly understand how to exploit multiple identical devices, the question of how to build database engines that can deal with a diverse number of them remains open. Already today, with multi-core CPUs, graphics cards, FPGAs, and vector processors, we have access to a staggering variety of different architectures, and experts agree that hardware diversity will continue to grow. As we enter this era of heterogeneity, developing new approaches to deal with a multitude of different hardware architectures is becoming increasingly important. Tomorrow’s database systems will need to exploit and embrace this trend towards increased hardware heterogeneity to meet the performance requirements of the modern information society. In this thesis, we present our contributions to the area of data processing on heterogeneous hardware. In particular, we discuss the following two major topics: In the first part of this thesis, we discuss how to manage hardware heterogeneity by reducing the development overhead to implement a database engine that can run on different hardware architectures. For this, we propose an alternative system design, based on a single set of hardware-oblivious operators which are compiled down to the actual hardware at runtime. Relying on hardware abstraction, learning mechanisms and self-tuning algorithms, this approach can drastically reduce the enormous development overhead that typically comes with supporting a variety of architectures, while still achieving competitive performance to hand-tuned code. We also present Ocelot, a prototypical hardware-oblivious database engine to demonstrate the feasibility of this concept. In the second part of this thesis, we introduce a novel approach to exploit hardware heterogeneity in a relational database engine by utilizing graphics processing units to assist the query optimizer. Based on this idea of GPU-Assisted Query Optimization, we then introduce a self-tuning, multivariate selectivity estimator based on Kernel Density Estimation that is specifically designed to exploit the properties of modern graphics cards and multi-core CPUs. This approach enables us to develop a novel estimator that is highly scalable, can adapt itself to changes in both the database and the query workload, and typically outperforms the accuracy of established state-of-the-art methods. For both topics, we motivate our decisions, present and discuss experimental evaluations, provide both the source code and scripts to allow other authors to reproduce our results, and outline potential directions for future work.Der Bereich der Datenbankforschung auf moderner Hardware beschäftigt sich mit der Frage, wie wir neuartige Hardware effizient zur Datenverarbeitung einsetzen können. Forscher und Entwickler haben hierzu in den letzten Jahren wichtige Beiträge geleistet und Ansätze sowie Systeme zur Datenverarbeitung auf verschiedensten Kategorien von Prozessoren vorgestellt. Ein wichtiger Aspekt wurde dabei jedoch häufig übergangen: Obwohl wir heute sehr gut mit einzelnen (oder mehreren) Prozessoren der selben Art umgehen können, ist es noch relativ unklar, wie ein Datenbanksystem entworfen werden sollte, das auch verschiedene Prozessoren effizient verwenden kann. Dieses Problem der Hardwareheterogenität wird zunehmend relevant: Bereits heute verfügen Computer häufig über eine Vielzahl von verschiedenen Prozessoren, wie zum Beispiel CPUs, Grafikkarten, FPGAs oder Vektorprozessoren. Experten sind sich einig, dass diese Vielfalt weiter anwachsen wird, und dass wir auf dem Weg in ein neues Zeitalter der Heterogenität sind. Um mit den wachsenden Anforderungen der modernen Informationsgesellschaft Schritt zu halten, wird es daher zunehmend wichtig werden, dass wir neuartige Verfahren entwickeln um Hardwareheterogenität in Datenbanksystemen ausnutzen und verwalten zu können. In dieser Arbeit stellen wir unsere Forschungsbeiträge zu diesem Bereich vor. Dies umfasst insbesondere die folgenden zwei Themen: Im ersten Teil dieser Arbeit besprechen wir Ansätze zur Verwaltung von Hardwareheterogenität in Datenbanksystemen. Insbesondere führen wir das Konzept von hardwareunabhängigen Datenbankoperatoren ein. Dies zielt darauf ab, den Entwicklungsaufwand zu reduzieren, der normalerweise bei der Portierung eines Datenbanksystems auf eine neue Hardwarearchitektur anfällt: Anstelle von speziell angepassten Algorithmen werden hierbei abstrakte Operatordefinitionen verwendet, welche vom System erst zur Laufzeit automatisch auf die vorhandene Hardware abgebildet werden. Zudem stellen wir mit Ocelot ein protoypisches System vor um die Machbarkeit des Konzepts hardwareunabhängiger Datenbanken zu belegen. Im zweiten Teil der Arbeit führen wir mit GPU-unterstützter Anfrageoptimierung einen neuen Ansatz zur Verwendung von heterogener Hardware in Datenbanksystemen ein. Hierauf aufbauend stellen wir anschließend einen sich selbst optimierenden, multivariaten Selektivitätsschätzer vor, welcher von uns speziell an die Eigenschaften moderner Grafikkarten und CPUs angepasst wurde. Der Schätzer ist hochskalierbar, passt sich selbstständig an Änderungen der Datenbank und Anfragen an und erzielt eine Genauigkeit, die in der Regel deutlich über dem aktuellen Stand der Technik liegt. Für beide Themen leiten wir eine ausführliche Motivation her, präsentieren und diskutieren die Ergebnisse unserer experimentellen Auswertung, stellen unsere Quelltexte und Skripte zur Verfügung um es anderen Autoren zu ermöglichen, unsere Ergebnisse nachzuvollziehen, und skizzieren mögliche Richtungen für anschließende Forschungsarbeiten