Perlen der Informatik 4
Informationen:
Inhalt:
In Perlen der Informatik 4 lernen Sie die Architektur und Algorithmik von Hauptspeicher-Datenbanksystemen kennen (und selber zu programmieren ;-). Die bisherigen Hauptspeicher-Datenbanksysteme waren eher Nischenprodukte, die für spezielle Anwendungen verwendet wurden. Dies hat sich durch den technologischen Fortschritt im Hardwarebereich geändert, wie man derzeit insbesondere durch die SAP HANA-Entwicklung sehen kann: Man hat heute Datenbank-Server mit Hauptspeicherkapazitäten jenseits eines Tera-Bytes, die Server haben viele Rechenkerne (multi-core) und es wurden neue Algorithmen und Datenstrukturen für Hauptspeicher-effiziente Datenverarbeitung entwickelt (Column-Stores, Kompression, Cache-effiziente Indexstrukturen, etc.)
Sie lernen in dieser Vorlesung, wie man richtig schnelle (Datenbank-) Anwendungen realisiert. Die Algorithmen werden parallelisiert, um auf modernen Multi-Core-Rechnern massiv parallel ausgeführt zu werden. Es soll aber eine "hands-on" Veranstaltung werden, bei der Sie selber (kleine) "proof-of-concept"-Prototypen bauen werden. Dies geschieht am besten in einer systemnahen Programmiersprache wie C/C++ auf einem Linux-Rechner.
Material:
- Einfuehrung.pptx
- SIGMOD Programming Contest slides
- trivial_oltp_olap.cpp
- 3-Way QuickSort in Umbra
- threaded_sort.cpp Multithreaded Sortierung, Stopwatch.hpp Klasse zur Zeitmessung (wird in threaded_sort.cpp benötigt), cpp_concepts.cpp Weitere C++ Konzepte (smart_ptr,for each loop,virtuelle Methoden)
- Parallel Sort using Range Partitioning: rangesort.cpp
- RowColumnStore.pptx
- Row Store Beispiel, Column Store Beispiel, Column Store+SSE Beispiel
- Radix Baum: Paper
- Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age
- massiv paralleler sort/merge-Join: PowerPoint, Paper
- HashJoins.pptx
- Hash join code, Hash join code mit cache misses
- Profiling: perf wiki, Intel PCM
- Branching Example
- SSE Code Stub
- Code SIGMOD programming contest 2017
- GeoJoin.pdf
- Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates