Database Systems and Modern CPU Architecture

Harddisk RAM

Offensichtlich spielt der effiziente Zugriff auf den Sekundärspeicher (Festplatten) für Datenbanksysteme ein Schlüsselrolle. Vielleicht nicht ganz so offensichtlich ist, daß Charakteristika moderner CPUs und Primärspeicher (RAM) die Performance von Datenbanksystemen mindestens ebenso bestimmen:

1. Die RAM-Kapazität hat schon seit einiger Zeit Größenordnungen erreicht, die eine Verlagerung aller Datenbankoperationen von der Festplatte in den Hauptspeicher ermöglichen. Zugriffe wollen aber sorgfältig geplant sein: in der für einen Speicherzugriff benötigten Zeit kann eine moderne CPU bis zu 106 Instruktionen ausführen.

2. Moderne, pipelined CPUs bieten weitreichende Möglichkeiten, die Ausführung von Datenbankoperationen zu parallelisieren. In spezifischen Situationen spekulieren CPUs gar über die Notwendigkeit, eine Instruktion auszuführen, um höheren Durchsatz zu erzielen.

Allerdings nutzen Datenbanksysteme und -algorithmen diese Vorteile moderner Rechnerarchitektur typischerweise nicht— im Gegenteil: Datenbanksysteme zeigen oft unterdurchschnittliche Performance.

In dieser Vorlesung analysieren wir diese modernen CPU-Architekturen (u.a. MIPS, Intel IA-32 und Itanium) und lernen eine Vielzahl von Verfahren kennen, die Datenbanksysteme — oder allgemein alle Programme, die eine Menge von Daten “schaufeln” — auf modernen CPUs und im Hauptspeicher richtig “auf Trab” bringen können.

Inhalte

• Architektur moderner CPUs und die Speicherhierarchie
• Pipelining und Parallelität auf CPU-Instruktionsebene
• Cache-Speicher, TLB, assoziative Speicher
• Sprungvorhersage in CPUs
• Sequentieller und randomisierter Speicherzugriff
• Speicherzugriffsmuster bei der Anfrageauswertung in RDBMS
• Tuplespeicherung in relationalen DBMS (RDBMS)
• Vertikal fragmentierte RDBMS und Anfrageauswertung
• Cache-bewusste Datenbank-Algorithmen (z.B., Joins, Sortierung)
• Hauptspeicherdatenbanksysteme
• Kompression zur Datendurchsatzsteigerung

Materialien

Grundlage der Vorlesungsinhalte sind, neben dem Buch von Hennessy und Patterson Computer Architecture: A Quantitative Approach, die folgenden Forschungsarbeiten:

• Peter Boncz, Stefan Manegold, and Martin L. Kersten. Database Architecture Optimized for the New Bottleneck: Memory Access. Proc. VLDB Conference, 1999.

• Anastassia Ailamaki, David J. DeWitt, and Mark D. Hill. Data Page Layouts for Relational Databases on Deep Memory Hierarchies. VLDB Journal 11(3), 2002.

• Jingren Zhou and Kenneth A. Ross. Buffering Databse Operations for Enhanced Instruction Cache Performance. Proc SIGMOD Conference, 2004.

• Stefan Manegold, Peter Boncz, and Martin Kersten. Optimizing Main-Memory Join On Modern Hardware. Transactions on Knowledge and Data Engineering 14(4), 2002.

• Stefan Manegold, Peter Boncz, Niels Nes, and Martin Kersten. Cache-Conscious Radix-Decluster Projections. Proc. VLDB Conference, 2004.

• Jingren Zhou, John Cieslewicz, Kenneth A. Ross, and Mihir Shah. Improving Database Performance on Simultaneous Multithreading Processors. Proc. VLDB Conference, 2005.

• Kenneth A. Ross. Selection Conditions in Main Memory. Transactions on Database Systems 29(1), 2004.

• Anastassia Ailamaki, David J. DeWitt, Mark D. Hill, and David A. Wood. DBMSs On A Modern Processor: Where Does Time Go?. Proc. VLDB Conference, 1999.

• Stefan Manegold, Peter Boncz, and Martin L. Kersten. Generic Database Cost Models for Hierarchical Memory Systems. Proc. VLDB Conference, 2002.

• Jingren Zhou and Kenneth A. Ross. Implementing Database Operations Using SIMD Instructions. Proc. SIGMOD Conference, 2002.

• Marcin Zukowski, Sándor Héman, Niels Nes, and Peter Boncz. Super-Scalar RAM-CPU Cache Compression. Proc. ICDE Conference, 2006.

• Shimin Chen, Phillip B. Gibbons, and Todd C. Mowry. Improving Index Performance through Prefetching. Proc. SIGMOD Conference, 2001.

• Peter Boncz, Marcin Zukowski, and Niels Nes. MonetDB/X100: Hyper-Pipelining Query Execution. Proc CIDR Conference, 2005.