Database Research Group

WSI – Database Systems Research Group

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:


Slides
NrChapterDownload
1Introduction and Motivationpdf
2CPU Architeture and Instruction Setspdf
3Pipeliningpdf
4Branch Predictionpdf
5Pipelined Query Executionpdf
6Memory Close to the CPU: Cachespdf
7Cache-Aware Database System Internalspdf
Additional material (code, data)