Lightweight Compression Techniques for Optimizing Complex Database Queries

• Applicant: Professor Dr.-Ing. Wolfgang Lehner
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2014 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 255187874

• Final Report Year: 2019

Final Report Abstract

Die Bedeutung von In-Memory Datenbanksystemen steigt zunehmend sowohl im wissenschaftlichen als auch im kommerziellen Kontext. Derartige Datenbanksysteme verfolgen einen hauptspeicherzentrischen Architekturansatz, der sich dadurch auszeichnet, dass alle performanzkritischen Operationen und internen Datenstrukturen für den Zugriff der Hauptspeicherhierarchie (z.B. effiziente Nutzung der Cachehierarchie etc.) ausgelegt sind. Üblicherweise gehen In-Memory Datenbanksysteme davon aus, dass alle relevanten Datenbestände auch vollständig in den Hauptspeicher eines Rechners oder eines Rechnerverbundes (Clusterkonfiguration) abgelegt werden können. Im Rahmen des Projektes haben wir uns speziell mit dem spaltenorientierten, hauptspeicherzentrischen Architekturansatz auseinandergesetzt, wo die Inhalte von Tabellen spaltenweise (bzw. attributweise) und nicht mehr zeilenweise physisch abgespeichert werden. Der Vorteil dieses Ansatzes besteht darin, dass analytische Anfragen wie beispielsweise Aggregate über Attributen nur noch die Attribute lesen müssen, die für die Beantwortung der Anfrage notwendig sind. In früheren Arbeiten wurde gezeigt, dass damit die Performanz von analytischen Anfragen gegenüber der klassischen zeilenweise Speicherung von Tabellen wesentlich gesteigert wird. Zunehmend werden jedoch Zwischenergebnisse, die während der Anfrageausführung erzeugt werden, zum Performanzengpass in hauptspeicherzentrischen Architekturen, da jeder Zugriff auf ein Zwischenergebnis genauso teuer ist wie ein Zugriff auf die Basisdaten; entsprechend ist auch der Aufwand, Zwischenergebnisse zu generieren ähnlich teuer wie Änderungen an Basisrelationen durchzuführen. Aus diesem Grund bestand die Zielstellung des Projektes darin, den Nutzen leichtgewichtiger Kompressionsverfahren in spaltenorientierten Datenbanksystemen zur Optimierung der Zwischenergebnisse zu eruieren. Die erzielten Forschungsergebnisse für dieses Ziel lassen in Wesentlichen in drei Bereiche einordnen: 1) Es wurde eine umfangreiche, detaillierte und experimentelle Aufarbeitung der leichtgewichtigen Kompressionstechniken durchgeführt und somit eine solide Grundlage für das Projekt geschaffen, 2) es wurden unterschiedliche Integrationsgrade zwischen Planoperatoren und Kompression herausgearbeitet und 3) alle entwickelten Konzepte wurde in einem eigenen Forschungsprototypen MorphStore integriert, um die Ergebnisse umfassend zu evaluieren. Des Weiteren sind eine Vielzahl von nationalen und internationalen Veröffentlichungen während der Projektbearbeitung entstanden.

Publications

• A benchmark framework for data compression techniques. In Performance Evaluation and Benchmarking: Traditional to Big Data to Internet of Things - 7th TPC Technology Conference, TPCTC 2015, Kohala Coast, HI, USA, August 31 - September 4, 2015. Revised Selected Papers, pages 77–93
  Patrick Damme, Dirk Habich, and Wolfgang Lehner
  
• Direct transformation techniques for compressed data: General approach and application scenarios. In Advances in Databases and Information Systems - 19th East European Conference, ADBIS 2015, Poitiers, France, September 8-11, 2015, Proceedings, pages 151–165
  Patrick Damme, Dirk Habich, and Wolfgang Lehner
  
• Lightweight data compression algorithms: An experimental survey (experiments and analyses). In Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21-24, 2017, pages 72–83
  Patrick Damme, Dirk Habich, Juliana Hildebrandt, and Wolfgang Lehner
  
• Metamodeling lightweight data compression algorithms and its application scenarios. In Proceedings of the ER Forum 2017 and the ER 2017 Demo Track co-located with the 36th International Conference on Conceptual Modelling (ER 2017), Valencia, Spain, - November 6-9, 2017, pages 128–141
  Juliana Hildebrandt, Dirk Habich, Thomas Kühn, Patrick Damme, and Wolfgang Lehner
  
• Query processing based on compressed intermediates. In Proceedings of the VLDB 2017 PhD Workshop co-located with the 43rd International Conference on Very Large Databases (VLDB 2017), Munich, Germany, August 28, 2017
  Patrick Damme
  
• From a comprehensive experimental survey to a cost-based selection strategy for lightweight integer compression algorithms. ACM Trans. Database Syst., 44(3):9:1–9:46, 2019
  Patrick Damme, Annett Ungethüm, Juliana Hildebrandt, Dirk Habich, and Wolfgang Lehner
  
• Morphstore - in-memory query processing based on morphing compressed intermediates LIVE. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019., pages 1917–1920
  Dirk Habich, Patrick Damme, Annett Ungethüm, Johannes Pietrzyk, Alexander Krause, Juliana Hildebrandt, and Wolfgang Lehner