Die Datenverarbeitung auf einer weltweit stetig wachsenden Informationsmenge und die hohen Anforderungen an die Energieeffizienz der Rechensysteme sind allgegenwärtige Herausforderungen der heutigen Zeit. Dabei werden zunehmend Datenbanken und deren Funktionalitäten eingesetzt, um diese großen Datenmengen effizient zu verwalten, abzuspeichern und zu verarbeiten. Auf Grund ihrer universellen Anwendbarkeit und der hohen Leistungsfähigkeit werden zumeist hoch-performante General-Purpose (GP) Prozessoren für administrative als auch für die Anfrageverarbeitung in Datenbanksystemen eingesetzt. Die Anfrageverarbeitung führt dabei eine Reihe von Operatoren wie z. B. das Suchen, Sortieren, oder Hashing aus, die signifikant die Gesamtleistung des Datenbanksystems beeinflussen. Um die weiter steigenden Anforderungen an Durchsatz, Latenz und Verlustleistung zu erfüllen, wurden bisher die Taktfrequenzen und damit die Leistungsfähigkeit von GP-Prozessoren kontinuierlich erhöht. In Zukunft werden jedoch die physikalischen Eigenschaften der verwendeten Halbleitermaterialien die Rechenleistung begrenzen. Diese Arbeit entwickelt und analysiert Beschleunigerarchitekturen für die Datenbank-Anfrageverarbeitung, um die Leistungsfähigkeit der zugrundeliegenden Datenbankoperatoren zu steigern. Die Datenbankbeschleuniger (DBA) werden als anwendungsspezifische Hardwareblöcke (ASIC) und als Prozessor mit erweiterten Befehlssatz (ASIP) implementiert, die eine Parallelisierung der Algorithmen auf Bit-, Daten- und Befehlsebene ermöglichen. Der erste Ansatz erlaubt eine hohe Beschleunigung bei gleichzeitig niedrigem Flächen- und Leistungsverbrauch der Hardware. Im Gegensatz dazu steht beim ASIP-Ansatz bereits ein konfigurierbarer Basisprozessor zur Verfügung, der die Befehlssteuerung übernimmt und damit eine einfache Anpassung des DBAs an zahlreiche Datenbankoperatoren ermöglicht. Die vorgestellten DBAs erreichen damit die Leistungsfähigkeit von optimierten GP-Prozessoren bei einer um bis zu drei Größenordnungen höheren Energie- und Flächeneffizienz. Für die Parallelisierung der Datenbankoperatoren auf Taskebene werden die DBAs in das Tomahawk Multiprozessorsystem auf einem Chip (MPSoC) integriert, das ein skalierbares Network-on-Chip und DMA-Controller für einen intelligenten Datentransfer bereitstellt. Eine zentrale Scheduling-Einheit arbeitet dabei den Anfrageausführungsplan ab und steuert die Zuweisung der Tasks auf die Verarbeitungseinheiten und den Transfer der Daten zu einem externen Speicher. Des Weiteren ist die Skalierung von Taktfrequenzen und Versorgungsspannungen möglich, um Durchsatz und Leistungsverbrauch an die Lastanforderungen anzupassen und damit den Energieverbrauch zu minimieren. Darüber hinaus wird das Tomahawk MPSoC mit Hilfe von Simulationen in einem virtuellen Prototyp und mit analytischen Modellen der Datenbankoperatoren hinsichtlich der Skalierbarkeit untersucht. Diese Auswertungen zeigen das Verhalten der Algorithmen bei steigender Prozessoranzahl und wachsenden Kardinalitäten sowie in Abhängigkeit der Speicherbandbreiten und relevanter algorithmusspezifischer Parameter.

In Zeiten wachsender Datenbankgrößen ist es unumgänglich, Anfragen näherungsweise auszuwerten um schnelle Antworten zu erhalten. Dieser Artikel stellt verschiedene Methoden vor, dieses Ziel zu erreichen, und wendet sich anschließend dem Sampling zu, welches mit Hilfe einer Stichprobe schnell zu adäquaten Ergebnissen führt. Enthalten Datenbankanfragen Verbund- oder Gruppierungsoperationen, so sinkt die Genauigkeit vieler Sampling-Verfahren sehr stark; insbesondere werden vor allem kleine Gruppen nicht erkannt. Dieser Artikel befasst sich mit hierarchischen gruppenbasiertem Sampling, welches Sampling, Gruppierung und Verbundoperationen kombiniert. / In times of increasing database sizes it is crucial to process queries approximately in order to obtain answers quickly. This article introduces several methods for achieving this goal and afterwards focuses on sampling, yielding appropriate results by using only a subset of the actual data. If database queries contain join or group-by operations, the accuracy of many sampling methods drops significantly; especially small groups are not recognized. This article is concerned with hierarchical group-based sampling, which combines sampling, grouping and joins.

Aktuelle Studien belegen ein rasantes, mehrdimensionales Wachstum in analytischen Datenbanken: Das Datenvolumen verzehnfachte sich in den letzten vier Jahren, die Anzahl der Nutzer wuchs um durchschnittlich 25% pro Jahr und die Anzahl der Anfragen verdoppelte sich seit 2004 jährlich. Bei den Anfragen handelt es sich zunehmend um komplexe Verbundanfragen mit Aggregationen; sie sind häufig explorativer Natur und werden interaktiv an das System gestellt. Eine Möglichkeit, der Forderung nach Interaktivität bei diesem starken, mehrdimensionalen Wachstum nachzukommen, stellen Stichproben und eine darauf aufsetzende näherungsweise Anfrageverarbeitung dar. Diese Lösung bietet signifikant kürzere Antwortzeiten sowie Schätzungen mit probabilistischen Fehlergrenzen. Mit den Operationen Verbund, Gruppierung und Aggregation als Hauptbestandteile analytischer Anfragen ergeben sich folgende Anforderungen an das Design von Stichproben in analytischen Datenbanken: Zwischen den Stichproben fremdschlüsselverbundener Relationen ist die referenzielle Integrität zu gewährleisten, sämtliche Gruppen sind angemessen zu repräsentieren und Aggregationsattribute sind auf extreme Werte zu untersuchen. In dieser Dissertation wird für jedes dieser Teilprobleme ein Stichprobenverfahren vorgestellt, das sich durch speicherplatzbeschränkte Stichproben und geringe Schätzfehler auszeichnet. Im ersten der vorgestellten Verfahren wird durch eine korrelierte Stichprobenerhebung die referenzielle Integrität bei minimalem zusätzlichen Speicherplatz gewährleistet. Das zweite vorgestellte Stichprobenverfahren hat durch eine Berücksichtigung der Streuung der Daten eine angemessene Repräsentation sämtlicher Gruppen zur Folge und unterstützt damit beliebige Gruppierungen, und im dritten Verfahren ermöglicht eine mehrdimensionale Ausreißerbehandlung geringe Schätzfehler für beliebig viele Aggregationsattribute. Für jedes dieser Verfahren wird die Qualität der resultierenden Stichprobe diskutiert und bei der Berechnung speicherplatzbeschränkter Stichproben berücksichtigt. Um den Berechnungsaufwand und damit die Systembelastung gering zu halten, werden für jeden Algorithmus Heuristiken vorgestellt, deren Kennzeichen hohe Effizienz und eine geringe Beeinflussung der Stichprobenqualität sind. Weiterhin werden alle möglichen Kombinationen der vorgestellten Stichprobenverfahren betrachtet; diese Kombinationen ermöglichen eine zusätzliche Verringerung der Schätzfehler und vergrößern gleichzeitig das Anwendungsspektrum der resultierenden Stichproben. Mit der Kombination aller drei Techniken wird ein Stichprobenverfahren vorgestellt, das alle Anforderungen an das Design von Stichproben in analytischen Datenbanken erfüllt und die Vorteile der Einzellösungen vereint. Damit ist es möglich, ein breites Spektrum an Anfragen mit hoher Genauigkeit näherungsweise zu beantworten. / Recent studies have shown the fast and multi-dimensional growth in analytical databases: Over the last four years, the data volume has risen by a factor of 10; the number of users has increased by an average of 25% per year; and the number of queries has been doubling every year since 2004. These queries have increasingly become complex join queries with aggregations; they are often of an explorative nature and interactively submitted to the system. One option to address the need for interactivity in the context of this strong, multi-dimensional growth is the use of samples and an approximate query processing approach based on those samples. Such a solution offers significantly shorter response times as well as estimates with probabilistic error bounds. Given that joins, groupings and aggregations are the main components of analytical queries, the following requirements for the design of samples in analytical databases arise: 1) The foreign-key integrity between the samples of foreign-key related tables has to be preserved. 2) Any existing groups have to be represented appropriately. 3) Aggregation attributes have to be checked for extreme values. For each of these sub-problems, this dissertation presents sampling techniques that are characterized by memory-bounded samples and low estimation errors. In the first of these presented approaches, a correlated sampling process guarantees the referential integrity while only using up a minimum of additional memory. The second illustrated sampling technique considers the data distribution, and as a result, any arbitrary grouping is supported; all groups are appropriately represented. In the third approach, the multi-column outlier handling leads to low estimation errors for any number of aggregation attributes. For all three approaches, the quality of the resulting samples is discussed and considered when computing memory-bounded samples. In order to keep the computation effort - and thus the system load - at a low level, heuristics are provided for each algorithm; these are marked by high efficiency and minimal effects on the sampling quality. Furthermore, the dissertation examines all possible combinations of the presented sampling techniques; such combinations allow to additionally reduce estimation errors while increasing the range of applicability for the resulting samples at the same time. With the combination of all three techniques, a sampling technique is introduced that meets all requirements for the design of samples in analytical databases and that merges the advantages of the individual techniques. Thereby, the approximate but very precise answering of a wide range of queries becomes a true possibility.

Today, data is collected in ever increasing scale and variety, opening up enormous potential for new insights and data-centric products. However, in many cases the volume and heterogeneity of new data sources precludes up-front integration using traditional ETL processes and data warehouses. In some cases, it is even unclear if and in what context the collected data will be utilized. Therefore, there is a need for agile methods that defer the effort of integration until the usage context is established. This thesis introduces Query-Time Data Integration as an alternative concept to traditional up-front integration. It aims at enabling users to issue ad-hoc queries on their own data as if all potential other data sources were already integrated, without declaring specific sources and mappings to use. Automated data search and integration methods are then coupled directly with query processing on the available data. The ambiguity and uncertainty introduced through fully automated retrieval and mapping methods is compensated by answering those queries with ranked lists of alternative results. Each result is then based on different data sources or query interpretations, allowing users to pick the result most suitable to their information need. To this end, this thesis makes three main contributions. Firstly, we introduce a novel method for Top-k Entity Augmentation, which is able to construct a top-k list of consistent integration results from a large corpus of heterogeneous data sources. It improves on the state-of-the-art by producing a set of individually consistent, but mutually diverse, set of alternative solutions, while minimizing the number of data sources used. Secondly, based on this novel augmentation method, we introduce the DrillBeyond system, which is able to process Open World SQL queries, i.e., queries referencing arbitrary attributes not defined in the queried database. The original database is then augmented at query time with Web data sources providing those attributes. Its hybrid augmentation/relational query processing enables the use of ad-hoc data search and integration in data analysis queries, and improves both performance and quality when compared to using separate systems for the two tasks. Finally, we studied the management of large-scale dataset corpora such as data lakes or Open Data platforms, which are used as data sources for our augmentation methods. We introduce Publish-time Data Integration as a new technique for data curation systems managing such corpora, which aims at improving the individual reusability of datasets without requiring up-front global integration. This is achieved by automatically generating metadata and format recommendations, allowing publishers to enhance their datasets with minimal effort. Collectively, these three contributions are the foundation of a Query-time Data Integration architecture, that enables ad-hoc data search and integration queries over large heterogeneous dataset collections.

Today, data is collected in ever increasing scale and variety, opening up enormous potential for new insights and data-centric products. However, in many cases the volume and heterogeneity of new data sources precludes up-front integration using traditional ETL processes and data warehouses. In some cases, it is even unclear if and in what context the collected data will be utilized. Therefore, there is a need for agile methods that defer the effort of integration until the usage context is established. This thesis introduces Query-Time Data Integration as an alternative concept to traditional up-front integration. It aims at enabling users to issue ad-hoc queries on their own data as if all potential other data sources were already integrated, without declaring specific sources and mappings to use. Automated data search and integration methods are then coupled directly with query processing on the available data. The ambiguity and uncertainty introduced through fully automated retrieval and mapping methods is compensated by answering those queries with ranked lists of alternative results. Each result is then based on different data sources or query interpretations, allowing users to pick the result most suitable to their information need. To this end, this thesis makes three main contributions. Firstly, we introduce a novel method for Top-k Entity Augmentation, which is able to construct a top-k list of consistent integration results from a large corpus of heterogeneous data sources. It improves on the state-of-the-art by producing a set of individually consistent, but mutually diverse, set of alternative solutions, while minimizing the number of data sources used. Secondly, based on this novel augmentation method, we introduce the DrillBeyond system, which is able to process Open World SQL queries, i.e., queries referencing arbitrary attributes not defined in the queried database. The original database is then augmented at query time with Web data sources providing those attributes. Its hybrid augmentation/relational query processing enables the use of ad-hoc data search and integration in data analysis queries, and improves both performance and quality when compared to using separate systems for the two tasks. Finally, we studied the management of large-scale dataset corpora such as data lakes or Open Data platforms, which are used as data sources for our augmentation methods. We introduce Publish-time Data Integration as a new technique for data curation systems managing such corpora, which aims at improving the individual reusability of datasets without requiring up-front global integration. This is achieved by automatically generating metadata and format recommendations, allowing publishers to enhance their datasets with minimal effort. Collectively, these three contributions are the foundation of a Query-time Data Integration architecture, that enables ad-hoc data search and integration queries over large heterogeneous dataset collections.

Aktuelle Studien belegen ein rasantes, mehrdimensionales Wachstum in analytischen Datenbanken: Das Datenvolumen verzehnfachte sich in den letzten vier Jahren, die Anzahl der Nutzer wuchs um durchschnittlich 25% pro Jahr und die Anzahl der Anfragen verdoppelte sich seit 2004 jährlich. Bei den Anfragen handelt es sich zunehmend um komplexe Verbundanfragen mit Aggregationen; sie sind häufig explorativer Natur und werden interaktiv an das System gestellt. Eine Möglichkeit, der Forderung nach Interaktivität bei diesem starken, mehrdimensionalen Wachstum nachzukommen, stellen Stichproben und eine darauf aufsetzende näherungsweise Anfrageverarbeitung dar. Diese Lösung bietet signifikant kürzere Antwortzeiten sowie Schätzungen mit probabilistischen Fehlergrenzen. Mit den Operationen Verbund, Gruppierung und Aggregation als Hauptbestandteile analytischer Anfragen ergeben sich folgende Anforderungen an das Design von Stichproben in analytischen Datenbanken: Zwischen den Stichproben fremdschlüsselverbundener Relationen ist die referenzielle Integrität zu gewährleisten, sämtliche Gruppen sind angemessen zu repräsentieren und Aggregationsattribute sind auf extreme Werte zu untersuchen. In dieser Dissertation wird für jedes dieser Teilprobleme ein Stichprobenverfahren vorgestellt, das sich durch speicherplatzbeschränkte Stichproben und geringe Schätzfehler auszeichnet. Im ersten der vorgestellten Verfahren wird durch eine korrelierte Stichprobenerhebung die referenzielle Integrität bei minimalem zusätzlichen Speicherplatz gewährleistet. Das zweite vorgestellte Stichprobenverfahren hat durch eine Berücksichtigung der Streuung der Daten eine angemessene Repräsentation sämtlicher Gruppen zur Folge und unterstützt damit beliebige Gruppierungen, und im dritten Verfahren ermöglicht eine mehrdimensionale Ausreißerbehandlung geringe Schätzfehler für beliebig viele Aggregationsattribute. Für jedes dieser Verfahren wird die Qualität der resultierenden Stichprobe diskutiert und bei der Berechnung speicherplatzbeschränkter Stichproben berücksichtigt. Um den Berechnungsaufwand und damit die Systembelastung gering zu halten, werden für jeden Algorithmus Heuristiken vorgestellt, deren Kennzeichen hohe Effizienz und eine geringe Beeinflussung der Stichprobenqualität sind. Weiterhin werden alle möglichen Kombinationen der vorgestellten Stichprobenverfahren betrachtet; diese Kombinationen ermöglichen eine zusätzliche Verringerung der Schätzfehler und vergrößern gleichzeitig das Anwendungsspektrum der resultierenden Stichproben. Mit der Kombination aller drei Techniken wird ein Stichprobenverfahren vorgestellt, das alle Anforderungen an das Design von Stichproben in analytischen Datenbanken erfüllt und die Vorteile der Einzellösungen vereint. Damit ist es möglich, ein breites Spektrum an Anfragen mit hoher Genauigkeit näherungsweise zu beantworten. / Recent studies have shown the fast and multi-dimensional growth in analytical databases: Over the last four years, the data volume has risen by a factor of 10; the number of users has increased by an average of 25% per year; and the number of queries has been doubling every year since 2004. These queries have increasingly become complex join queries with aggregations; they are often of an explorative nature and interactively submitted to the system. One option to address the need for interactivity in the context of this strong, multi-dimensional growth is the use of samples and an approximate query processing approach based on those samples. Such a solution offers significantly shorter response times as well as estimates with probabilistic error bounds. Given that joins, groupings and aggregations are the main components of analytical queries, the following requirements for the design of samples in analytical databases arise: 1) The foreign-key integrity between the samples of foreign-key related tables has to be preserved. 2) Any existing groups have to be represented appropriately. 3) Aggregation attributes have to be checked for extreme values. For each of these sub-problems, this dissertation presents sampling techniques that are characterized by memory-bounded samples and low estimation errors. In the first of these presented approaches, a correlated sampling process guarantees the referential integrity while only using up a minimum of additional memory. The second illustrated sampling technique considers the data distribution, and as a result, any arbitrary grouping is supported; all groups are appropriately represented. In the third approach, the multi-column outlier handling leads to low estimation errors for any number of aggregation attributes. For all three approaches, the quality of the resulting samples is discussed and considered when computing memory-bounded samples. In order to keep the computation effort - and thus the system load - at a low level, heuristics are provided for each algorithm; these are marked by high efficiency and minimal effects on the sampling quality. Furthermore, the dissertation examines all possible combinations of the presented sampling techniques; such combinations allow to additionally reduce estimation errors while increasing the range of applicability for the resulting samples at the same time. With the combination of all three techniques, a sampling technique is introduced that meets all requirements for the design of samples in analytical databases and that merges the advantages of the individual techniques. Thereby, the approximate but very precise answering of a wide range of queries becomes a true possibility.

Durch stetig wachsende Datenmengen in aktuellen Data-Warehouse-Datenbanken erlangen Stichproben eine immer größer werdende Bedeutung. Insbesondere interaktive Analysen können von den signifikant kürzeren Antwortzeiten der approximativen Anfrageverarbeitung erheblich profitieren. Linked-Bernoulli-Synopsen bieten in diesem Szenario speichereffiziente, schemaweite Synopsen, d. h. Synopsen mit Stichproben jeder im Schema enthaltenen Tabelle bei minimalem Mehraufwand für die Erhaltung der referenziellen Integrität innerhalb der Synopse. Dies ermöglicht eine effiziente Unterstützung der näherungsweisen Beantwortung von Anfragen mit beliebigen Fremdschlüsselverbundoperationen. In diesem Artikel wird der Einsatz von Linked-Bernoulli-Synopsen in Data-Warehouse-Umgebungen detaillierter analysiert. Dies beinhaltet zum einen die Konstruktion speicherplatzbeschränkter, schemaweiter Synopsen, wobei unter anderem folgende Fragen adressiert werden: Wie kann der verfügbare Speicherplatz auf die einzelnen Stichproben aufgeteilt werden? Was sind die Auswirkungen auf den Mehraufwand? Zum anderen wird untersucht, wie Linked-Bernoulli-Synopsen für die Verwendung in Data-Warehouse-Datenbanken angepasst werden können. Hierfür werden eine inkrementelle Wartungsstrategie sowie eine Erweiterung um eine Ausreißerbehandlung für die Reduzierung von Schätzfehlern approximativer Antworten von Aggregationsanfragen mit Fremdschlüsselverbundoperationen vorgestellt. Eine Vielzahl von Experimenten zeigt, dass Linked-Bernoulli-Synopsen und die in diesem Artikel präsentierten Verfahren vielversprechend für den Einsatz in Data-Warehouse-Datenbanken sind. / With the amount of data in current data warehouse databases growing steadily, random sampling is continuously gaining in importance. In particular, interactive analyses of large datasets can greatly benefit from the significantly shorter response times of approximate query processing. In this scenario, Linked Bernoulli Synopses provide memory-efficient schema-level synopses, i. e., synopses that consist of random samples of each table in the schema with minimal overhead for retaining foreign-key integrity within the synopsis. This provides efficient support to the approximate answering of queries with arbitrary foreign-key joins. In this article, we focus on the application of Linked Bernoulli Synopses in data warehouse environments. On the one hand, we analyze the instantiation of memory-bounded synopses. Among others, we address the following questions: How can the given space be partitioned among the individual samples? What is the impact on the overhead? On the other hand, we consider further adaptations of Linked Bernoulli Synopses for usage in data warehouse databases. We show how synopses can incrementally be kept up-to-date when the underlying data changes. Further, we suggest additional outlier handling methods to reduce the estimation error of approximate answers of aggregation queries with foreign-key joins. With a variety of experiments, we show that Linked Bernoulli Synopses and the proposed techniques have great potential in the context of data warehouse databases.

The development of in-memory query engines is constantly adapting to evolving hardware features to maintain high performance for modern data analytics. To achieve this, parallelizing query processing is crucial for leveraging the full potential of modern hardware. While traditional parallelization techniques like multi-threading and distributed computing are well-established, the increasing availability and continuous advancements of data-level parallelism, known as Single Instruction Multiple Data (SIMD), have made SIMD a cutting-edge approach for improving single-query performance. Three general trends can be identified in the evolution of SIMD hardware: (i) continual increase in the available degree of data-level parallelism through wider SIMD registers, (ii) ongoing expansion of functional capabilities, and (iii) notable heterogeneity of the SIMD hardware landscape. The increasing width of SIMD registers, ranging from 128-bit to 512-bit for Intel and ARM platforms and up to 16 Kb on the NEC SX-Aurora TSUBASA vector engine, provides significant potential for data-level parallelism. This trend benefits query operators with linear access patterns, such as simple scans or arithmetic operations. However, it can negatively impact operators that rely on random access patterns or introduce loop-carried dependencies, such as sorting or a Hash-Join. With the introduction of novel instruction set extensions, like Intel's AVX-512, the functional capabilities of SIMD hardware have been continuously extended, allowing more complex operations to be efficiently executed in parallel. Consequently, this thesis outlines the opportunities and challenges of wider SIMD registers for in-memory query processing and how novel instruction set extensions can be used to mitigate some challenges. Additionally, the SIMD hardware landscape has become increasingly heterogeneous, with different architectures available. This diversity poses a significant challenge for academia and industry, as it requires constant adaptation and re-evaluation of SIMD-based algorithms and data structures. To address this challenge, we implemented a SIMD hardware abstraction library called Template SIMD Library (TSL), which provides a unified interface to different architectures. In this thesis, we present the design and implementation of TSL, demonstrating its capabilities by implementing a set of SIMD-based algorithms for in-memory query processing. We also show that even modern FPGAs benefit from the SIMD paradigm and can be programmed using high-level synthesis tools, such as Intel's oneAPI. Moreover, we demonstrate the potential of SIMD-based FPGA programming by implementing SIMD-based algorithms for in-memory query processing on different FPGA cards and integrating the necessary functionality into the TSL. Finally, we propose a novel workload-aware SIMD query processing approach called SIMQ. This approach leverages SIMD registers to share data access and SIMD instructions to share computation across queries.:1 Introduction 1.1 Single Instruction Multiple Data (SIMD) 1.1.1 Utilizing SIMD 1.1.2 SIMD in OLAP Query Processing 1.2 Thesis Goals and Contributions 1.2.1 Implications of SIMD Advancements on Analytical Query Processing 1.2.2 Leveraging SIMD to Optimize OLAP Query Throughput 1.2.3 Embracing the Heterogeneity of SIMD-aware Hardware 1.3 Impact of Thesis Contributions 1.3.1 Publications of Thesis Contribution 1.3.2 Open Source Contributions 1.3.3 Further Publications 1.4 Structure of the Thesis 2 Evaluating the Vector Supercomputer SX-Aurora TSUBASA 2.1 Problem Statement 2.2 Hardware System SX-Aurora TSUBASA 2.2.1 Overall Architecture 2.2.2 Vector Processing and Specific Systems 2.2.3 Execution Model and Programming Approach 2.3 MorphStore — In-Memory Database System 2.4 Comparative Evaluation 2.4.1 Selected Investigated Operations 2.4.2 Experimental Setup and Methodology 2.4.3 Single-Thread Evaluation Results 2.4.4 Multi-Thread Evaluation Results 2.4.5 Summary 2.5 Future Work 2.6 Conclusion 3 Fighting Duplicates in Hashing 3.1 Problem Statement 3.2 Background 3.2.1 Linear Probing 3.2.2 State-of-the-Art Vectorized Implementation of Linear Probing 3.2.3 Novel SIMD Instructions 3.3 CD-aware Vectorized Implementation of Linear Probing 3.3.1 CD-aware Hash Table Data Structures 3.3.2 Handling of Bucket Duplicates 3.3.3 Handling of Key Duplicates 3.4 Experimental Evaluation 3.4.1 Evaluation Result for Hashing without Value Handling 3.4.2 Evaluation Results for Hashing with Value Handling 3.5 Related Work 3.6 Conclusion and Future Work 4 Leveraging SIMD to Optimize OLAP Query Throughput 4.1 Problem Statement 4.2 Background and Related Work 4.2.1 Vectorization in General 4.2.2 Vectorization in Database Systems 4.2.3 Work Sharing in Database Systems 4.3 Sharing Vector Registers 4.3.1 SISQ: Single Instruction Single Query 4.3.2 SIMQ: Single Instruction Multiple Queries 4.4 Evaluation 4.4.1 Single-Threaded Evaluation 4.4.2 Multi-Threaded Evaluation 4.5 Discussion 4.6 Conclusion 5 Program your (custom) SIMD instruction set on FPGA in C++ 5.1 Problem Statement 5.2 FPGA Programming in C++ 5.2.1 Naïve C++ programming 5.2.2 Data Parallel C++ programming. 5.2.3 Using specialized data types 5.2.4 Analyzing FPGA resources 5.2.5 Summary 5.3 Programming SIMD instruction set 5.3.1 Register Definition 5.3.2 Instruction Definition 5.3.3 Comparing with RTL kernels 5.4 Use Case Studies 5.4.1 FilterCount 5.4.2 Binary Packing 5.5 Custom SIMD instructions 5.6 DPC++ Best practices 5.7 Related Work 5.8 Conclusion 6 Mastering the SIMD Heterogeneity 6.1 Problem Statement 6.2 Background 6.2.1 Applicability 6.2.2 Evolving API 6.3 TSLGen - Generative Framework 6.3.1 General Concepts 6.3.2 Framework Description 6.4 Advanced Features 6.4.1 Test Generation 6.4.2 Build Environment Files Generation 6.4.3 Further Extensions 6.4.4 Toolsupport 6.5 Use-Case Studies 6.5.1 Case Studies Description 6.5.2 Applicability 6.5.3 Extensibility 6.6 Discussion 6.7 Related Work 6.8 Conclusion 7 Tutorial on SIMD - Foundations, Abstraction, and Advanced Techniques 7.1 Problem Statement 7.2 Foundations 7.3 Abstraction 7.4 Advanced Techniques 7.4.1 Wider SIMD Registers 7.4.2 Flexibly-Sized SIMD Registers 7.4.3 Partition-based SIMD Processing 7.4.4 Increasing Heterogeneity 7.5 Summary / Kontinuierlich wachsende Mengen an zu verwaltenden Daten und komplexer werdende analytische Anfragen erfordern eine stetige Weiterentwicklung und Verbesserung von In-Memory Query Engines. Die effiziente Ausnutzung sich ständig weiterentwickelnder Hardware-Features fällt dabei eine entscheidende Rolle zu. Ein grundlegender Ansatz zur Beschleunigung von Algorithmen besteht in der Parallelisierung der Verarbeitung. Neben Scale-up und Scale-out Ansätzen, wie Multi-Thread beziehungsweiße Distributed Computing, existiert die Möglichkeit der Datenlevel parallelen (Single Instruction Multiple Data (SIMD)) Verarbeitung. Durch die zunehmende Verfügbarkeit und kontinuierliche Weiterentwicklung ist vorallem SIMD eine häufig eingesetzte Technik zur Beschleunigung verschiedenster Algorithmen in Forschung und Industrie geworden. Drei allgemeine Trends lassen sich im Bezug auf die Entwicklung von SIMD-Hardware identifizieren: (i) eine kontinuierliche Zunahme des verfügbaren Grades an Datenparallelismus durch breitere SIMD-Register, (ii) eine kontinuierliche Erweiterung des Funktionsumfangs und (iii) eine große Heterogenität der SIMD-Hardware-Landschaft. Die zunehmende Breite der verfügbaren SIMD-Register, die von 128 bit bis 512 bit für Inel und ARM Plattformen und bis zu 16 Kb auf der NEC SX-Aurora TSUBASA reicht, nützt vorallem Algorithmen mit linearem Zugriffsmuster ohne relevante Abhängigkeiten zwischen den einzelnen zu verarbeitenden Daten. Algorithmen welche auf nicht-lineare Zugriffsmuster angewiesen sind oder deren Verhalten stark von den zu Grunde liegenden Daten abhängig ist, können jedoch häufig nicht von einem höheren Grad an Datenlevel Parallelismus profitieren. Ein Beispiel für solch einen Algorithmus ist der Hash-Join, dessen Ziel es ist, zwei Relationen über einen gemeinsamen Schlüssel zu verknüpfen. Durch die Einführung neuer Befehlssatzerweiterungen wie AVX-512 von Intel werden die funktionalen Fähigkeiten der der verfügbaren SIMD-Hardware kontinuierlich erweitert, wodurch bisherige Annahmen neu bewertet werden müssen. Die vorliegende Arbeit untersucht die Möglichkeiten und Herausforderungen breiterer SIMD-Register für die In-Memory Anfrageverarbeitung und inwiefern neue Befehlssatzerweiterungen genutzt werden können, um wichtige Herausforderungen in der Datenlevel paralleln Verarbeitung zu bewältigen. Der dritte Trend, die zunehmende Ausdifferenzierung verfügbarer Hardware erschwert den konsistenten Einsatz von SIMD. Unterschiedliche Funktionen, Datentypen und Konzepte verhindern eine einfache Portierung bereits optimierter Algorithmen. Neue Funktionalitäten erfordern mitunter eine architekturspezifische Anpassung des gesamten Algorithmus um vorhandene Möglichkeiten bestmöglich auszunutzen. Um dieser Herausforderung zu begegnen, wird die im Rahmen dieser Dissertation entwickelte SIMD-Hardwareabstraktionsbibliothek namens Template SIMD Library (TSL) vorgestellt, die eine einheitliche Schnittstelle bereitstellt um auf einer Vielzahl von Architekturen mit unterschiedlichen Datentypen Datenlevel parallelität auszunutzen. Darüber hinaus wird gezeigt, dass selbst moderne FPGAs vom SIMD-Paradigma profitieren und mit Hilfe von high-level synthesis Tools (HLS) wie Intels oneAPI programmiert werden können. Das Potenzial von SIMD zur Beschleunigung der Verarbeitung auf FPGAs wird durch diverse Benchmarks von Datenbank-spezifischen Algorithmen auf zwei verschiedenen FPGA-Karten aufgezeigt und die erforderliche Funktionalität in die TSL integriert. Während alle bisherigen Ansätze zum Einsatz von SIMD in der In-Memory Anfrageverarbeitung auf die Beschleunigung einzelner Anfragen abzielten, wird in der vorliegenden Arbeit ein neues Konzept zur Workload-Optimierung namens SIMQ vorgestellt. Dieser Ansatz nutzt SIMD-Register als von der Hardware bereitgestellte Ressource, um gemeinsame Datenzugriffe unterschiedlicher Anfragen zusammenzuführen.:1 Introduction 1.1 Single Instruction Multiple Data (SIMD) 1.1.1 Utilizing SIMD 1.1.2 SIMD in OLAP Query Processing 1.2 Thesis Goals and Contributions 1.2.1 Implications of SIMD Advancements on Analytical Query Processing 1.2.2 Leveraging SIMD to Optimize OLAP Query Throughput 1.2.3 Embracing the Heterogeneity of SIMD-aware Hardware 1.3 Impact of Thesis Contributions 1.3.1 Publications of Thesis Contribution 1.3.2 Open Source Contributions 1.3.3 Further Publications 1.4 Structure of the Thesis 2 Evaluating the Vector Supercomputer SX-Aurora TSUBASA 2.1 Problem Statement 2.2 Hardware System SX-Aurora TSUBASA 2.2.1 Overall Architecture 2.2.2 Vector Processing and Specific Systems 2.2.3 Execution Model and Programming Approach 2.3 MorphStore — In-Memory Database System 2.4 Comparative Evaluation 2.4.1 Selected Investigated Operations 2.4.2 Experimental Setup and Methodology 2.4.3 Single-Thread Evaluation Results 2.4.4 Multi-Thread Evaluation Results 2.4.5 Summary 2.5 Future Work 2.6 Conclusion 3 Fighting Duplicates in Hashing 3.1 Problem Statement 3.2 Background 3.2.1 Linear Probing 3.2.2 State-of-the-Art Vectorized Implementation of Linear Probing 3.2.3 Novel SIMD Instructions 3.3 CD-aware Vectorized Implementation of Linear Probing 3.3.1 CD-aware Hash Table Data Structures 3.3.2 Handling of Bucket Duplicates 3.3.3 Handling of Key Duplicates 3.4 Experimental Evaluation 3.4.1 Evaluation Result for Hashing without Value Handling 3.4.2 Evaluation Results for Hashing with Value Handling 3.5 Related Work 3.6 Conclusion and Future Work 4 Leveraging SIMD to Optimize OLAP Query Throughput 4.1 Problem Statement 4.2 Background and Related Work 4.2.1 Vectorization in General 4.2.2 Vectorization in Database Systems 4.2.3 Work Sharing in Database Systems 4.3 Sharing Vector Registers 4.3.1 SISQ: Single Instruction Single Query 4.3.2 SIMQ: Single Instruction Multiple Queries 4.4 Evaluation 4.4.1 Single-Threaded Evaluation 4.4.2 Multi-Threaded Evaluation 4.5 Discussion 4.6 Conclusion 5 Program your (custom) SIMD instruction set on FPGA in C++ 5.1 Problem Statement 5.2 FPGA Programming in C++ 5.2.1 Naïve C++ programming 5.2.2 Data Parallel C++ programming. 5.2.3 Using specialized data types 5.2.4 Analyzing FPGA resources 5.2.5 Summary 5.3 Programming SIMD instruction set 5.3.1 Register Definition 5.3.2 Instruction Definition 5.3.3 Comparing with RTL kernels 5.4 Use Case Studies 5.4.1 FilterCount 5.4.2 Binary Packing 5.5 Custom SIMD instructions 5.6 DPC++ Best practices 5.7 Related Work 5.8 Conclusion 6 Mastering the SIMD Heterogeneity 6.1 Problem Statement 6.2 Background 6.2.1 Applicability 6.2.2 Evolving API 6.3 TSLGen - Generative Framework 6.3.1 General Concepts 6.3.2 Framework Description 6.4 Advanced Features 6.4.1 Test Generation 6.4.2 Build Environment Files Generation 6.4.3 Further Extensions 6.4.4 Toolsupport 6.5 Use-Case Studies 6.5.1 Case Studies Description 6.5.2 Applicability 6.5.3 Extensibility 6.6 Discussion 6.7 Related Work 6.8 Conclusion 7 Tutorial on SIMD - Foundations, Abstraction, and Advanced Techniques 7.1 Problem Statement 7.2 Foundations 7.3 Abstraction 7.4 Advanced Techniques 7.4.1 Wider SIMD Registers 7.4.2 Flexibly-Sized SIMD Registers 7.4.3 Partition-based SIMD Processing 7.4.4 Increasing Heterogeneity 7.5 Summary