Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Masterseminar: Datenbankoperationen auf Moderner Hardware

Prof. Dr. Ulf Leser

Datenbankoperationen sind traditionell auf eine Minimierung der Kommunikation mit Sekundärspeicher optimiert. Durch wachsende Größen von Hauptspeichern und die zunehmende Leistungsfähigkeit von CPUs stellt die IO-Schnittstelle aber heutzutage oft nicht mehr den zentralen Flaschenhals dar, stattdessen treten Themen wie Parallelisierung, Cache-Level, Kompression, oder Einsatz spezieller Hardware (GPUs, FPGA) in den Vordergrund. In dem Seminar beschäftigen wir uns mit Ansätzen, typische Datenbankoperationen optimal auf moderner Hardware zu implementieren.

Das Seminar findet im wesentlichen als Blockseminar am Ende des Semesters statt. Vorher sind aber Einführungstermine und individuelle Themenbesprechungen zu besuchen.

Voraussetzungen

  • Gute Kenntnisse in Algorithmen und Datenstrukturen (z.B. gleichnamige Vorlesung)
  • Kenntnisse in Datenbanken (z.B. Einführung in Datenbanken)

Schein und Anrechenbarkeit

Das Seminar ist anrechenbar für

  • Diplom Informatik
  • Master Informatik
  • Master Wirtschaftsinformatik

Voraussetzungen für den Schein sind:

  • der Besuch der Einführungsveranstaltungen,
  • die regelmäßige Kommunikation mit dem jeweiligen Betreuer,
  • eine Kurzpräsentation des Themas in der Mitte des Semesters,
  • das Halten eines wissenschaftlichen Vortrags im Blockseminar am Ende des Semesters, und
  • das Erstellen einer schriftlichen Ausarbeitung (Seminararbeit).

Anmeldung

Die Teilnehmerzahl ist begrenzt, die Anmeldung erfolgt über AGNES.

Termine und Ablauf

Am Dienstag, den 18.10.2016 findet die Einführungsveranstaltung statt, die für alle Teilnehmenden verpflichtend ist. Dort werden die Themen erläutert und vergeben.

Das Seminar wird als Blockseminar am Ende des Semesters abgehalten. Jede(r) Studierende muss dort einen ca. 30 minütigen Vortrag über das zugewiesene Thema halten. Vorher finden mindestens zwei Treffen mit dem/der Betreuer(in) statt, einmal zur Vorbesprechung des Themas und einmal zur Besprechung der Folien. Außerdem wird es in der Mitte des Semesters einen Termin geben, in dem alle Studierenden in einer 5-minütigen Flash-Präsentation ihr Thema vorstellen, um Querverbindungen zu erkennen und die rechtzeitige Beschäftigung mit dem Thema sicherzustellen. Schließlich muss zu jedem Thema eine ca. 15 seitige Seminararbeit verfasst werden. Ggf. gehören auch praktische Umsetzungen mit den Systemen zur Aufgabe.

Zusätzlich zu der themenspezifischen Literatur, über die die Vorträge gehalten werden, gibt es für alle Teilnehmer verpflichtende Einführungslektüre.

Alle Pflichttermine in der Übersicht:

  • 18.10.16, 15-17 Uhr: Einführung und Themenvergabe, Raum: RUD 26, 1'303
  • Bis 30.11.2017: Treffen mit dem Betreuer zur Themenbesprechung und -eingrenzung
  • Vor Weihnachten: Flash-Präsentationen; Raum TBA
  • Bis 20.1.2017: Treffen mit dem Betreuer zur Besprechung der Folien
  • Semesterende: Blockseminar, Raum TBA
  • Bis 31.3.2017: Abgabe Seminararbeit

Vorlagen


Zeitplan Blockseminar

13.2.2017; Raum: RUD25, 4.410
15:00 UhrSchwaßVectorized Instructions
15:45 UhrSchekahnMain-Memory Index Structures
16:30 UhrMünchmeyerMany-Core CPUs
17:15 UhrDiedrichFPGAs
14.2.2017; Raum: RUD25, Humboldt-Kabinett
9:00 UhrWiegandtMain-Memory Graph Databases
9:45 UhrGordeevGPUs
10:30 UhrDimitrovHardware Transactional Memory
11:15 UhrWeberModern Database Systems


Themen

Topic Paper Vortragende(r) Betreuer(in)
Einführende Literatur für alle Teilnehmer
  • Larson, Paul and Levandoski, Justin: Modern Main-Memory Database Systems, VLDB Tutorial, 2016.
  • Zhang, Hao et al.: "In-Memory Big Data Management and Processing: A Survey", IEEE Trans. Knowl. Data Eng. 27(7), 2015.
    
  Ulf Leser, Stefan Sprenger
Vectorized Instructions
  • Polychroniou, Orestis et al.: "Rethinking SIMD Vectorization for In-Memory Databases", SIGMOD, 2015.
  • Polychroniou, Orestis and Ross, Kenneth A.: "Vectorized Bloom Filters for Advanced SIMD Processors", DaMoN, 2014.
  • Polychroniou, Orestis and Ross, Kenneth A.: "High Throughput Heavy Hitter Aggregation for Modern SIMD Processors", DaMoN, 2013.
  • Willhalm, Thomas et al.: "SIMD-Scan: Ultra Fast in-Memory Table Scan using on- Chip Vector Processing Units", VLDB, 2009.
 Lucas Schwaß Sprenger
Main-Memory Index Structures
  • Leis, Viktor et al.: "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases", ICDE, 2013.
  • Kim, Changkyu et al.: "FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs", SIGMOD, 2010.
  • Rao, Jun and Ross, Kenneth A.: "Making B+-Trees Cache Conscious in Main Memory", SIGMOD, 2000
 Jens Schekahn Leser
Main-Memory Graph Databases David Wiegandt Leser
Many-Core CPUs
  • Jha, Saurabh et al.: "Improving Main Memory Hash Joins on Intel Xeon Phi Processors: An Experimental Approach", VLDB, 2015.
  • Balkesen, Cagri et al.: "Main-Memory Hash Joins on Multi-Core CPUs: Tuning to the Underlying Hardware", ICDE, 2013.
  • Blanas, Spyros et al.: "Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs", SIGMOD, 2011.
 Jannes Münchmeyer Leser
NUMA-aware algorithms
  • Leis, Viktor et al.: "Morsel-driven parallelism: a NUMA-aware query evaluation framework for the many-core age", SIGMOD, 2014.
  • Albutiu, Martina-Cezara et al.: "Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems", PVLDB 5(10), 2012.
  • Majo, Zoltan and Gross, Thomas R.: "Memory System Performance in a NUMA Multicore Multiprocessor", SYSTOR, 2011.
 Sprenger
FPGAs
  • Halstead, Robert J. et al.: "FPGA-based Multithreading for In-Memory Hash Joins", CIDR, 2015.
  • István, Zsolt et al.: "A flexible hash table design for 10GBPS key-value stores on FPGAS", FPL, 2013.
  • Mueller, Rene et al.: "Data Processing on FPGAs", VLDB, 2009.
  • Mueller, Rene and Teubner, Jens: "FPGA: What’s in it for a Database?", SIGMOD, 2009.
 Maximilian Diedrich Sprenger
GPUs
  • Sitaridi, Evangelia A. and Ross, Kenneth A.: "Optimizing select conditions on GPUs", DaMoN, 2013.
  • Kaldewey, Tim et al.: "GPU join processing revisited", DaMoN, 2012.
  • Bakkum, Peter and Skadron, Kevin: "Accelerating SQL Database Operations on a GPU with CUDA", GPGPU, 2010.
 Andre Gordeev Sprenger
Hardware Transactional Memory
  • Cervini, David et al.: "Applying HTM to an OLTP system: No free lunch", DaMoN, 2015.
  • Wang, Zhaoguo et al.: "Using restricted transactional memory to build a scalable in-memory database", EuroSys, 2014.
  • Leis, Viktor et al.: "Exploiting Hardware Transactional Memory in Main-Memory Databases", ICDE, 2014.
 Dimitar Dimitrov Sprenger
Modern Database Systems
  • S. Idreos et al.: "MonetDB: Two decades of research in column-oriented database architectures", IEEE Data Eng. Bull. 35(1), 2012.
  • F. Färber et al.: "SAP HANA database: data management for modern business applications", SIGMOD Record 40(4), 2011.
  • T. Neumann: "Efficiently compiling efficient query plans for modern hardware", VLDB, 2011.
 Elke Weber Leser