TUM Informatik III: Seminar - Datenbanken auf modernen Hardwarearchitekturen

TU München - Fakultät für Informatik
Lehrstuhl III: Datenbanksysteme

Seminar - Datenbanken auf modernen Hardwarearchitekturen

Hauptseminar Informatik im Sommersemester 2011

Betreuer:

Prof. Alfons Kemper
Prof. Thomas Neumann

Vorträge:

Viktor Leis: Scapegoat Trees

Binary search trees are a very common method for implementing a dictionary data structure which allows to search for, insert, and delete elements by key. Red-Black and AVL trees have worst-case cost of O(log(n)) for all three operations. This is achieved by reorganizing the tree during the insert and delete operations but requires the storage of additional information at each node. Scapegoat trees avoid this space overhead but occasionally require rebuilding the whole tree which results in an amortized cost of O(log(n)) per insert or delete operation.

Timo Besenreuther: Cache Performanz auf moderner Hardware von PAX zu FAST

Relationale Datenbanksysteme wurden klassisch hinsichtlich der Hintergrundspeicherzugriffe optimiert, um ihre Performance zu steigern. Im Jahre 2001 wurde das Speichermodell PAX (Partition Attributes Across) eingeführt, welches zusätzlich auf Hauptspeicherzugriffe optimiert, indem die Datenseiten so organisiert werden, dass Caches optimal ausgenutzt werden können. In dieser Arbeit wird zuerst PAX im Detail erklärt: Warum es erfunden wurde, wie es funktioniert und wo der entscheidende Unterschied zu klassischem Modellen liegt. Danach wird die Performanz von PAX in einem Benchmark auf moderner Hardware mit einem klassischen Modell (NSM) verglichen. Abschließend gibt diese Arbeit einen kurzen Überblick über die Entwicklungen, die sich bis zum heutigen Tage aus PAX ergeben haben. Die PAX-Ideen zur Cacheoptimierung werden heute auch auf Suchbäumen angewendet, wie das FAST-Verfahren zeigt.

Manuel Söhner: Spaltenorientierte Datenbanken

Das Thema umfasst die, aufgrund der spaltenweisen Speicherung des Inhalts, für OLAP-Szenarien (z.B. Data Warehouses und Data Mining) besser geeigneten Column-Stores. Ich werde auf den Unterschied zu Row-Stores eingehen und die Architektur sowie die Gründe für die Performance-Vorteile von leseoptimierten DBMS beschreiben. Dazu werde ich die wichtigsten Kompressionsverfahren und Joins sowie Frühe und Späte Materialisierung ansprechen. Im Speziellen werden die Besonderheiten von C-Store und den beiden Varianten von MonetDB näher erläutert. Als Ausblick für zukünftige Verbesserungen in der Entwicklung werden hybride und weitere Performance-steigernde Ansätze beleuchtet, um zu klären, wie die Nachteile von Column-Stores (z.B. bei Schreibzugriffen) beseitigt werden können.

Daniel Strittmatter: Hauptspeicherdatenbanken am Beispiel von VoltDB - Der neue Weg für OLTP?

Zum Thema gehören die Hardware-Entwicklungen, die Hauptspeicherdatenbanken (speziell für OLTP) heute attraktiv machen, der Aufbau einer solchen DB-Architektur im Vergleich zu den großen, festplattenbasierten relationalen DBMS, Verteilungs- und Recovery-Strategien. Außerdem wird auf Benchmarking von OLTP-Workloads mittels TPC-C und das Abschneiden der verschiedenen Datenbanksysteme eingegangen. Des Weiteren wird die Umsetzung dieser Konzepte am Beispiel von VoltDB untersucht und die Vor- und Nachteile von Hauptspeicherdatenbanken (bzw. spezialiserten DBMS vs. "one size fits all" DBMS) beschrieben.

Michael Bigontina: Cache-Optimierung durch vertikale Partitionierung - Von PAX zu HYRISE

Die Arbeit beschäftigt sich mit PAX und anderen Techniken zur Cache-Optimierung durch vertikale Partitionierung. Zu Beginn wird ein Überblick über klassische Techniken zur Datenspeicherung (NSM, DSM) gegeben und es werden kurz einige Beispiele von Ansätzen vor PAX erklärt. Im Hauptteil wird auf den Aufbau und die Funktionsweise von PAX eingegangen. Danach werden kurz wichtige nachfolgende Entwicklungen aufgezeigt (z.B. Data Morphing). Abschließend wird mit HYRISE eine der neuesten Entwicklungen auf diesem Gebiet präsentiert.

Andreas Bigontina: Hashing-Strategien und das Cache-Oblivious-Model

Diese Arbeit wird einen Überblick über etablierte Kollisionsauflösungsstrategien geben und anschließend auf Cuckoo Hashing genauer eingehen. Im zweiten Teil wird die Idee hinter dem Cache-Oblivious-Model beschrieben und dessen Umsetzung dann anhand einiger Hashing-Strategien gezeigt. Ziel ist es, schlussendlich einen Vergleich der effizientesten Hashing-Strategien im Hinblick auf ihre cache-oblivious Variationen zu erhalten.

Thomas Szyrkowiec: Anfrageprozessor-Optimierungen bei Datenbanksystemen im Hauptspeicher

In den letzten Jahren hat die Geschwindigkeit der Prozessoren entsprechend dem Moore'schen Gesetz exponentiell zugenommen. Im Vergleich dazu verbessern sich die Speicherzugriffszeiten nur sehr geringfügig und es entsteht eine immer größere Kluft. Um dennoch eine möglichst schnelle Bereitstellung von Daten aus dem wachsenden Hauptspeicher gepaart mit einer höheren CPU Auslastung zu erhalten, müssen Optimierungen angewendet werden um diesen Missstand bestmöglich zu überdecken. Die Ansätze hierfür konzentrieren sich auf die Eigenschaften der Hardware und damit vor allem auf die Caches und die CPU. So lässt sich mit dem Wissen über die Größe und Bandbreite der Speicher eine zügigere Ausführung erreichen und zusammen mit einer Abstimmung auf die CPU und dem Wissen über ihre Vorhersagen eine weitestgehend verbesserte Leistung erlangen. Dabei spielt auch die Anordnung und Kombination von Anweisungen innerhalb der grundlegenden Abläufe, wie beispielsweise Joins und Selections, eine Rolle. Die entsprechenden Ansätze werden in dieser Ausarbeitung näher beleuchtet.

Gerhard Mesch: HyPer (HYbrid OLTP & OLAP High PERformance Database System)

HyPer ist ein modernes Hauptspeicher-Datenbanksystem, das die Hardware-unterstützte virtuelle Speicherverwaltung des Betriebssystems für die Datenverwaltung und die Synchronisation zwischen OLTP-Transaktionen und OLAP-Anfragen effektiv ausnutzt. In Bezug auf die "`in-core"' Datenverwaltung werden die relationalen Daten direkt, also ohne zusätzliche Indirektion durch eine DBMS-kontrollierte Puffer- und Seitenverwaltung, auf den virtuellen Adressraum des OLTP-Prozesses abgebildet. Dieser Prozess kann transaktionskonsistente Snapshots der Datenbank anlegen, indem ein neuer OLAP-Prozess abgespaltet wird (in Linux mit dem Systembefehl fork). Der copy on write-Mechanismus des Betriebssystems/Prozessors sorgt für die Konsistenzerhaltung dieses Snapshots, indem Seiten mit sich ändernden Datenobjekten repliziert werden. Dieser Snapshot-Mechanismus entspricht dem alt-bekannten Schattenspeicherkonzept, das Lorie schon 1977 erfunden hat. HyPer's Leistungsfähigkeit wird anhand des neuen "`Mixed Workload CH-BenCHmark"' nachgewiesen, der die Transaktionsverarbeitung des TPC-C- und die Anfragen des TPC-H-Benchmarks in einer gemischten, parallel auf demselben Datenbestand auszuführenden Workload vereint. Die Leistungsfähigkeit eines derartigen hybriden Datenbanksystems kann für die effektive Unterstützung sogenannter "`real-time business intelligence"' ausgenutzt werden.