Publikationen

Compiling database queries into compact and efficient machine code has proven to be a great technique to improve query performance and to exploit characteristics of modern hardware. Furthermore, compilation frameworks like LLVM provide powerful optimization techniques and support different backends. However, the time for generating machine code becomes an issue for short-running queries or queries which could produce early results quickly. In this work, we present an adaptive approach integrating graph query interpretation and compilation. While query compilation and code generation are running in the background, the query execution starts using the interpreter. As soon as the code generation is finished, the execution switches to the compiled code. Our evaluation shows that autonomously switching execution modes helps to hide compilation times.

Over the past thirty years, database management systems have been established as one of the most successful software concepts. In todays business environment they constitute the centerpiece of almost all critical IT systems. The reasons for this success are manyfold. On the one hand, such systems provide abstractions hiding the details of underlying hardware or operating systems layers. On the other hand, database management systems are ACID compliant, which enables them to represent an accurate picture of a real world scenario, and ensures correctness of the managed data.However, the currently used database concepts and systems are not well prepared to support emerging application domains such as eSciences, Industry 4.0, Internet of Things or Digital Humanities. Furthermore, volume, variety, veracity as well as velocity of data caused by ubiquitous sensors have to be mastered by massive scalability and online processing by providing traditional qualities of database systems like consistency, isolation and descriptive query languages. At the same time, current and future hardware trends provide new opportunities such as many-core CPUs, co-processors like GPU and FPGA, novel storage technologies like NVRAM and SSD as well as high-speed networks provide new opportunities.In this talk we present our research results for the use of modern hardware architectures for data management. We discuss the design of data structures for persistent memory and the use of accelerators like GPU and FPGA for database operations.

Intro -- I Grundlegende Konzepte -- Vorbemerkungen und Überblick -- Informatik, Algorithmen und Datenstrukturen -- Historischer Überblick: Algorithmen -- Historie von Programmiersprachen und Java -- Grundkonzepte der Programmierung in Java -- Algorithmische Grundkonzepte -- Intuitiver Algorithmusbegriff -- Beispiele für Algorithmen -- Bausteine für Algorithmen -- Pseudocode-Notation für Algorithmen -- Struktogramme -- Rekursion -- Sprachen und Grammatiken -- Begriffsbildung -- Reguläre Ausdrücke -- Backus-Naur-Form (BNF) -- Elementare Datentypen -- Datentypen als Algebren -- Signaturen von Datentypen -- Der Datentyp bool -- Der Datentyp integer -- Felder und Zeichenketten -- Terme -- Bildung von Termen -- Algorithmus zur Termauswertung -- Datentypen in Java -- Primitive Datentypen -- Referenzdatentypen -- Operatoren -- Algorithmenparadigmen -- Überblick über Algorithmenparadigmen -- Applikative Algorithmen -- Terme mit Unbestimmten -- Funktionsdefinitionen -- Auswertung von Funktionen -- Erweiterung der Funktionsdefinition -- Applikative Algorithmen -- Beispiele für applikative Algorithmen -- Imperative Algorithmen -- Grundlagen imperativer Algorithmen -- Komplexe Anweisungen -- Beispiele für imperative Algorithmen -- Das logische Paradigma -- Logik der Fakten und Regeln -- Deduktive Algorithmen -- Weitere Paradigmen -- Genetische Algorithmen -- Neuronale Netze -- Umsetzung in Java -- Ausdrücke und Anweisungen -- Methoden -- Applikative Algorithmen und Rekursion -- Literaturhinweise zum Teil I -- II Algorithmen -- Ausgewählte Algorithmen -- Suchen in sortierten Folgen -- Sequenzielle Suche -- Binäre Suche -- Sortieren -- Sortieren: Grundbegriffe -- Sortieren durch Einfügen -- Sortieren durch Selektion -- Sortieren durch Vertauschen: BubbleSort -- Sortieren durch Mischen: MergeSort -- QuickSort -- Sortieren durch Verteilen: RadixSort.

Die optimale Nutzung von moderner Hardware zur Beschleunigung von Datenbank-Anfragen ist keine triviale Aufgabe. Viele DBMS als auch DSMS der letzten Jahrzehnte basieren auf Sachverhalten, die heute kaum noch Gültigkeit besitzen. Ein Beispiel hierfür sind heutige Server-Systeme, deren Hauptspeichergröße im Bereich mehrerer Terabytes liegen kann und somit den Weg für Hauptspeicherdatenbanken geebnet haben. Einer der größeren letzten Hardware Trends geht hin zu Prozessoren mit einer hohen Anzahl von Kernen, den sogenannten Manycore CPUs. Diese erlauben hohe Parallelitätsgrade für Programme durch Multithreading sowie Vektorisierung (SIMD), was die Anforderungen an die Speicher-Bandbreite allerdings deutlich erhöht. Der sogenannte High-Bandwidth Memory (HBM) versucht diese Lücke zu schließen, kann aber ebenso wie Many-core CPUs jeglichen Performance-Vorteil negieren, wenn dieser leichtfertig eingesetzt wird. Diese Arbeit stellt die Many-core CPU-Architektur zusammen mit HBM vor, um Datenbank sowie Datenstrom-Anfragen zu beschleunigen. Es wird gezeigt, dass ein hardwarenahes Kostenmodell zusammen mit einem Kalibrierungsansatz die Performance verschiedener Anfrageoperatoren verlässlich vorhersagen kann. Dies ermöglicht sowohl eine adaptive Partitionierungs und Merge-Strategie für die Parallelisierung von Datenstrom-Anfragen als auch eine ideale Konfiguration von Join-Operationen auf einem DBMS. Nichtsdestotrotz ist nicht jede Operation und Anwendung für die Nutzung einer Many-core CPU und HBM geeignet. Datenstrom-Anfragen sind oft auch an niedrige Latenz und schnelle Antwortzeiten gebunden, welche von höherer Speicher-Bandbreite kaum profitieren können. Hinzu kommen üblicherweise niedrigere Taktraten durch die hohe Kernzahl der CPUs, sowie Nachteile für geteilte Datenstrukturen, wie das Herstellen von Cache-Kohärenz und das Synchronisieren von parallelen Thread-Zugriffen. Basierend auf den Ergebnissen dieser Arbeit lässt sich ableiten, welche parallelen Datenstrukturen sich für die Verwendung von HBM besonders eignen. Des Weiteren werden verschiedene Techniken zur Parallelisierung und Synchronisierung von Datenstrukturen vorgestellt, deren Effizienz anhand eines Mehrwege-Datenstrom-Joins demonstriert wird.

Cover -- Inhaltsverzeichnis -- Vorwort -- Was sind Datenbanken? -- Warum Datenbanken? -- Datenbanksysteme -- Anforderungen: Die Codd'schen Regeln -- DBMS-Architektur -- Datenunabhängigkeit -- Transaktionen -- Konkrete Datenbankmanagementsysteme -- Einsatzgebiete und Grenzen -- Beispielanwendungen -- Übersicht über die Kapitel des Buches -- Übungsaufgaben -- Relationale Datenbanken - Daten als Tabellen -- Relationen für tabellarische Daten -- Integritätsbedingungen: Schlüssel und Fremdschlüssel -- Tabellendefinition in SQL -- Anfrageoperationen auf Tabellen -- Selektion -- Projektion -- Natürlicher Verbund -3mu -- Umbenennung -- Mengenoperationen , , - -- Anfragen in SQL -- Änderungsoperationen in SQL -- Zusammenfassung -- Übungsaufgaben -- Das Entity-Relationship- Modell -- Eigenschaften von Datenbankmodellen -- Einführung in das Entity-Relationship-Modell -- Grundkonzepte -- Ein einfaches Beispiel für ein ER-Schema -- ER-Modellierungskonzepte -- Wert und Attribut -- Entity und Entity-Typ -- Beziehung und Beziehungstyp -- Identifizierung durch Schlüssel -- Kardinalitäten -- n:m-Beziehung -- 1:n-Beziehung -- 1:1-Beziehung -- Optionale und zwingende Beziehungen -- Abhängige Entity-Typen -- Die Ist-Beziehung -- Alternative Notationen für Kardinalitäten -- Zusammenfassung -- Übungsaufgaben -- Datenbankentwurf -- Der Datenbankentwurfsprozess -- Ziele des Datenbankentwurfs -- Das Phasenmodell -- Formalisierung des Relationenmodells -- Logischer Datenbankentwurf: Abbildung auf Relationen -- Übersicht über die Abbildungsregeln -- Abbildung von Entity-Typen -- Abbildung von Beziehungstypen -- Abbildung eines abhängigen Entity-Typs -- Abbildung der Ist-Beziehung -- Komplexere Beispiele -- Zusammenfassung -- Übungsaufgaben -- Normalisierung für eine redundanzfreie Datenbank -- Funktionale Abhängigkeiten -- Schema-Eigenschaften -- Update-Anomalien.