19.11.2018 - Ausarbeitungen können ab jetzt im Review System eingereicht werden: http://dbis.cs.tu-dortmund.de/seminar-ws1819/
23.10.2018 - Zuordnung der Themen
Tiefgreifende Entwicklungen der Hardwaretechnologie rütteln ganz gewaltig an etablierten Techniken der Datenbankimplementation. Hauptspeicher ist nicht mehr unbedingt eine knappe Ressource, die einzig als Cache für Festplatten verwendet wird – Rechner mit 1 TB und mehr an Hauptspeicher sind verfügbar und erschwinglich. Parallelitätsgrade mit hunderten von Prozessoren sind keine Fiktion mehr. Dazu gesellen sich ganz revolutionäre Technologien wie etwa „non-volatile memories“ – nicht-flüchtiger Speicher mit Zugriffscharakteristika ähnlich denen von DRAM – oder Netzwerke mit Hardwarebeschleunigung und extrem hoher Bandbreite.
Im Seminar wollen wir auf einige der (möglichen) Auswirkungen solcher Technologien auf Datenbankarchitekturen schauen. Ein Schwerpunkt wird dabei die Indexverwaltung sein.
Indexstrukturen wie B-Bäume oder Hashtabellen werden für einen effizienten Zugriff bestimmter Daten für Anfragen und Operationen verwendet. Many-Core-Systeme mit großen Mengen Hauptspeicher erlauben zwar hohe Parallelitätsgerade, müssen jedoch bei der Entwicklung von entsprechenden Datenstrukturen mit beachtet werden.
Eube Vorbesprechung zum Seminar wird am Montag, dem 15. Oktober 2018 um 16:15 Uhr um Raum OH12/E.003 stattfinden. Im Rahmen der Vorbesprechung findet auch eine Themenvergabe statt. Bitte schauen Sie sich schon im Vorfeld einige der angegebenen Forschungsarbeiten an, damit Sie entsprechende Präferenzen nennen können.
Bitte senden Sie eine Liste mit maxinal drei priorisierten Themenwünschen bis Montag, den 22. Oktober 2018 per Mail an jan.muehlig@tu-dortmund.de.
Das Seminar wird als Blockseminar am 21. und 22. Januar 2019 jeweils von 08:00 bis 16:00 Uhr stattfinden.
Für die Vorträge sind 25 bis 30 Minuten pro Teilnehmer vorgesehen. Im Anschluss zu jedem Vortrag finden sowohl eine inhaltliche Diskussion als auch eine Diskussion zum Vortragsstil statt. Bei der Präsentation Ihres Vortrages können Sie das Werkzeug frei wählen.
Die nachfolgende Themenliste ist noch unvollständig, soll aber einen Eindruck der Seminarinhalte geben:
1a. Indexstrukturen in Main Memory Datenbanksystemen (Patrick Brinkmann)
Dieser Beitrag soll einen Überblick über mögliche Datenstrukturen wie diverse Baum-Varianten und Hashtabellen für die Verwaltung von Indizes geben.
Lehman, Tobin J., and Michael J. Carey. "A study of index structures for main memory database management systems." Proc. VLDB. Vol. 1. 1986. PDF
1b. Vergleich von T-Baum und B-Baum (Tim Schmidt)
Während B-Bäume auch in Datenbanksystemen mit persistenten Speichern genutzt werden, sind T-Bäume vermehrt für Hauptspeichersysteme gedacht. Diese Arbeit vergleicht beide Indexstrukturen im Hinblick auf Mehrbenutzerunterstützung.
Lu, Hongjun, Yuet Yeung Ng, and Zengping Tian. "T-tree or b-tree: Main memory database index structure revisited." adc. IEEE, 2000. PDF
2. Indexstrukturen für moderne Hardware (Sascha Kiesow)
Die In-Memory Database Engnine Hekaton, welche in SQL Server zum Einsatz kommt, setzt auf Bw-Bäume als Datenstruktur für Indizes. Die sperr-freie B-Baum Variante verspricht eine bessere Nutzung von Caches und die Minimierung von Schreibvorgängen auf "zufällige" Adressen.
Levandoski, Justin, et al. "Indexing on modern hardware: Hekaton and beyond." Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. ACM, 2014. PDF
Levandoski, Justin J., David B. Lomet, and Sudipta Sengupta. "The Bw-Tree: A B-tree for new hardware platforms." Data Engineering (ICDE), 2013 IEEE 29th International Conference on. IEEE, 2013. PDF
3. Leistungssteigerung durch Transactional Memory (Nikolas Mueller)
Mit Transactional Memory soll die Synchronisation nebläufiger Kontrollflüsse vereinfacht werden. Eine Gruppe von Intel, SAP und der TU Dresden hat diese Möglichkeit der Synchronisation in verschiedene Datenstrukturen für Indizes implementiert und evaluiert.
Karnagel, Tomas, et al. "Improving in-memory database index performance with Intel® Transactional Synchronization Extensions." High Performance Computer Architecture (HPCA), 2014 IEEE 20th International Symposium on. IEEE, 2014. PDF
4a. Cache-effiziente B+-Bäume (Sören Ohlsen)
Bei Cache Sensitive Search Trees (CSS-Trees) handelt es sich um eine Datenstruktur, welche die Leistung Caches bewusst für statische Daten ausnutzen. Änderungen der Daten sind hingegen teuer. In dieser Arbeit wird versucht, die Eigenschaften der CSS-Bäume auf den B+-Baum zu übertragen.
Rao, Jun, and Kenneth A. Ross. "Making B+-trees cache conscious in main memory." Acm Sigmod Record. Vol. 29. No. 2. ACM, 2000. PDF
4b. ART: Ein Cache-effizienter Baum (Mariam Tayyem)
Der Adaptive Radix Tree verspricht Hashtabellen-ähnliche Geschwindigkeit für Suchanfragen und unterstützt trotzdem Range Scans. Erreicht wird dies durch eine optimale Nutzung der CPU-Caches.
Leis, Viktor, Alfons Kemper, and Thomas Neumann. "The adaptive radix tree: ARTful indexing for main-memory databases." 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 2013. PDF
5. PALM: Ein B+-Baum für viel Parallelität (Alex Schmulbach)
Sewall et al. versuchen Latch-Contentions in B+-Bäumen, welche in massiv parallelen Umgebungen auftreten, mittels Gruppierung der Anfragen zu vermeiden und beobachten in ihrem System PALM eine verdopplung des Durchsatzes im Vergleich mit anderen Systemen.
Sewall, Jason, et al. "PALM: Parallel architecture-friendly latch-free modifications to B+ trees on many-core processors." Proc. VLDB Endowment 4.11 (2011): 795-806. PDF
6a. HOT: Ein höhenoptimierter, cache-effizienter Trie (Patrick Nowak)
Der Hight Optimized Trie (HOT) ermöglicht einen konstant hohen Fanout und gute Cache-Effizienz zu ermöglichen, indem die Anzahl der berücksichtigten Bits in jedem Knoten dynamisch variiert werden.
Binna, Robert, et al. "HOT: A Height Optimized Trie Index for Main-Memory Database Systems." Proceedings of the 2018 International Conference on Management of Data. ACM, 2018. PDF
6b. Bereichsfilter auf Fast Succinct Tries (Alexander Brichta)
Die Datenstruktur SuRF basiert auf Fast Succinct Tries und stellt eine alternative zu Bloom-Filtern dar, unterstützt jedoch sowohl Suchanfragen einzelner Schlüssel als auch ganzer Schlüsselbereiche. Innerhalb dieser Arbeit werden Bloom-Filter von RocksDB durch SuRF ersetzt und evaluiert.
Zhang, Huanchen, et al. "SuRF: practical range query filtering with fast succinct tries." Proceedings of the 2018 International Conference on Management of Data. ACM, 2018. ACM(erreichbar aus dem Uni-Netz)
7. B-Tree Versionierung (Roman Bernhard)
B-Bäume speichern Paare aus Schlüsseln und Werten. In dieser Arbeit werden B-Bäume um die Versionierung der Tupel ergänzt, um damit eine Grundlage für Transaktionen in B-Bäumen zu schaffen.
Becker, Bruno, et al. "An asymptotically optimal multiversion B-tree." The VLDB Journal—The International Journal on Very Large Data Bases 5.4 (1996): 264-275. PDF
8. Transaktionen auf dem multiversion B+-Tree (Thilo Kamradt)
Aufbauend auf B-Bäumen mit Versionen, wird in dieser Arbeit beschrieben, die transaktionale Workloads mit B+-Bäumen durchgeführt werden können.
Haapasalo, Tuukka, et al. "Transactions on the multiversion b+-tree." Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. ACM, 2009. PDF
9. Versionierte Indexstrukturen auf moderner Hardware (Tim Uhlott)
Diese Arbeit beschreibt, wie Indexstrukturen mit verschiedenen Versionen von moderner Hardware profitieren können.
Riegger, Christian, Tobias Vinçon, and Ilia Petrov. "Multi-version indexing and modern hardware technologies: a survey of present indexing approaches." Proceedings of the 19th International Conference on Information Integration and Web-based Applications & Services. ACM, 2017. PDF
10. B+-Baum für heterogene Plattformen (Andreas Lang)
Co-Prozessoren wie GPUs lassen sich auch für Anfragen auf Datenbanksystemen profitabel einsetzen. In der Arbeit von Shahvarani et al. wird ein Einsatz von B+-Bäumen auf CPUs und GPUs diskutiert.
Shahvarani, Amirhesam, and Hans-Arno Jacobsen. "A hybrid b+-tree as solution for in-memory indexing on cpu-gpu heterogeneous computing platforms." Proceedings of the 2016 International Conference on Management of Data. ACM, 2016. ACM (erreichbar aus dem Uni-Netz)
11. GPU-basiertes, spekulatives Query Processing (Jonas Kauke)
Die Parallelität von GPGPUs lässt sich effizient beim Query Processing ausnutzen. Volk et al. zeigen dies am Beispiel eines Präfix-Baums für Index-Operationen.
Volk, Peter Benjamin, Dirk Habich, and Wolfgang Lehner. "GPU-Based Speculative Query Processing for Database Operations." ADMS@ VLDB. 2010. PDF
12. Bitmap-Indizes mittels FPGA (Florian Grieskamp)
Die Erstellung von Bitmap-Indizes ist sehr aufwendig und kann durch den Einsatz von parallel rechnenden FPGAs beschleunigt werden.
Nguyen, Xuan-Thuan, et al. "An FPGA-Based Hardware Accelerator for Energy-Efficient Bitmap Index Creation." IEEE Access 6 (2018): 16046-16059. PDF
13. Indexstrukturen und Maschinenlernen (Marius Gunnemann)
Der Trend des deep-learning macht auch vor Datenbanksystemen keinen Halt. Kraska et al. beschreiben, wie sich Indexstrukturen durch gelernte Modelle ersetzen lassen.
Kraska, Tim, et al. "The case for learned index structures." Proceedings of the 2018 International Conference on Management of Data. ACM, 2018. ACM (erreichbar aus dem Uni-Netz)
14a. Big Data mittels Indezierung erforschen (Leonard Kleinhans)
Zahlreiche Anwendungen produzieren kontinuierlich große Mengen an Datenreihen. In einigen Szenarien müssen Analysten in der Lage sein, diese Daten sofort abzufragen. Mit den aktuellen Indexierungsmethoden ist dies bei sehr großen Datenseriensammlungen derzeit nicht möglich. Diese Arbeit beschreibt die Indexierung und Abfrage sehr großer Datenreihenbestände.
Zoumpatianos, Kostas, Stratos Idreos, and Themis Palpanas. "Indexing for interactive exploration of big data series." Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, 2014. PDF
14b. Big Data-Indizierung auf Basis des Log-Structured-Merge-Trees (Mariam Tayyem)
Der Log-Structured-Merge-Tree wird vor allem für die Indezierung von Dateien mit hohem Insert-Volumen verwendet, als Beispiel können hier Transaktions-Logs genannt werden. In dieser Arbeit wird der LSM-Tree für die Indezierung von GPS-Daten verwendet
Kim, Young-Seok, et al. "A Comparative Study of Log-Structured Merge-Tree-Based Spatial Indexes for Big Data." Data Engineering (ICDE), 2017 IEEE 33rd International Conference on. IEEE, 2017. PDF
O’Neil, Patrick, et al. "The log-structured merge-tree (LSM-tree)." Acta Informatica 33.4 (1996): 351-385. PDF (erreichbar aus dem Uni-Netz)
15. Indexstrukturen für Non-Volatile Memory (Finn Thieme)
Viele Indexstrukturen sind ausschließlich auf die Verwendung von DRAM konzipiert. Diese Arbeit beleuchtet verschiedene Mechanismen, NVM zu nutzen.
Sha, Edwin Hsing-Mean, et al. "Towards the Design of Efficient and Consistent Index Structure with Minimal Write Activities for Non-Volatile Memory." IEEE Transactions on Computers 67.3 (2018): 432-448. UB Dortmund (erreichbar aus dem Uni-Netz)
16. HiKV: Ein Hybrider Key-Value-Store für DRAM und NVM (Christopher Kukkel)
HiKV ist ein Speicher für Paare bestehend aus Schlüssel und Wert, welcher sowohl DRAM als auch NVM nutzen kann.
Xia, Fei, et al. "Hikv: A hybrid index key-value store for dram-nvm memory systems." 2017 USENIX Annual Technical Conference (USENIX ATC 17). 2017. PDF
17. BzTree: Eine sperr-freie Datenstruktur für NVM (Cihat Atlin)
Der BzTree ist eine sperr-freie B-Baum-Variante für NVM.
Arulraj, Joy, et al. "Bztree: A high-performance latch-free range index for non-volatile memory." Proceedings of the VLDB Endowment 11.5 (2018): 553-565. PDF