Effiziente Zugriffsmethoden zur Analyse, Modifikation und aggregierten Darstellung multidimensionaler Daten in memory-basierten OLAP-Anwendungen
Zusammenfassung der Projektergebnisse
OLAP-Systeme („On-Line Analytical Processing“) bieten die Möglichkeit der interaktiven Exploration und Manipulation großer zusammengefasster Datenbestände (Data Warehouses). Sie sind damit ein integraler Bestandteil der so genannten Business Intelligence. Grundlegendes abstraktes Datenmodell von OLAP ist der Data Cube, der die Datensätze als Zellen einer multidimensionalen Tabelle modelliert, die gemäß Benutzeranfragen aufbereitet und in geeigneten Sichten präsentiert werden können. In-Memory-OLAP-Systeme, bei denen alle relevanten Daten im Hauptspeicher gehalten werden, haben zusätzlich den Anspruch, auch Planungsszenarien und so genannte What-if-Anfragen effizient zu unterstützen, für die eine schnelle Rückschreibefähigkeit der verwendeten Datenstrukturen Voraussetzung ist. Allen im OLAP relevanten Operationen ist gemeinsam, dass sie in einer für die Benutzer akzeptablen, im Idealfall möglichst nicht wahrnehmbaren Zeit ausgeführt werden sollen, um ein interaktives Explorieren der Datenbestände zu ermöglichen. Vor allem die letztere Anforderung wird in derzeitigen Systemen häufig bei weitem nicht erfüllt. Zentrale Fragestellung des vorliegenden Projekts war es, wie Aggregationsanfragen sowie Rückschreibeoperationen im memory-basierten OLAP mittels geeigneter Algorithmen und Datenstrukturen effizient unterstützt werden und deren Antwortzeiten drastisch gesenkt werden können. Neben der Untersuchung und Weiterentwicklung sequentieller Verfahren stand als Schwerpunkt der Arbeiten insbesondere die massiv parallele Verarbeitung von OLAP-Anfragen mittels alternativer Hardware im Fokus. In Projekt wurden neue Algorithmen und Datenstrukturen zur effizienten Repräsentation multidimensionaler Datenräume im Kontext von OLAP-Anwendungen entwickelt. Dabei lag ein besonderer Fokus auf der speicherresidenten Repräsentation der Daten sowie neben dem lesenden Zugriff auf die Daten auch auf deren effizienten Veränderung. Insbesondere wurden zusätzlich zu sequentiellen Algorithmen und Datenstrukturen Möglichkeiten der Parallelisierung untersucht, insbesondere mit Hilfe von Grafikkarten (GPUs) als Coprozessoren. Um neben der reinen Aggregation auch komplexere Rechenoperationen (so genannte Rules) zu beschleunigen, wurde im Projekt auch untersucht, wie solche multidimensionalen Formeln mit Hilfe paralleler Algorithmen effizienter berechnet werden können. Als Hauptergebnis des Projekts wurden eine GPU-basierte Datenstruktur zur platzeffizienten Repräsentation von OLAP-Cubes sowie dazugehörige Algorithmen zur schnellen multidimensionalen Aggregation entwickelt. Diese übertreffen die Geschwindigkeit bestehender sequentieller Verfahren um bis Faktor 50. Beim für Planungsszenarien relevanten Rückschreiben aggregierter Werte (mit impliziter Änderung darunter liegender Basiszellen) wurde teils eine Geschwindigkeitssteigerung um mehr als Faktor 150 gemessen. Da die Algorithmen mit der Zahl der verwendeten Grafikkarten skaliert, kann durch den Einsatz zusätzlicher GPUs die Leistung entsprechend erhöht werden. Die Verwendung mehrerer GPUs ist auch aus Platzgründen relevant, da größere OLAP-Würfel trotz der komprimierten Speicherung in unserer Datenstruktur möglicherweise nicht vollständig im Speicher einer GPU vorgehalten werden können. Auch für multidimensionale Rechenformeln wurden parallele Algorithmen entwickelt, die auf GPU-Hardware zu einer deutlichen Reduktion der Rechenzeiten führen. In diesem Bereich sehen wir auch Potenzial für zukünftige Arbeiten. Einige der wesentlichen Ergebnisse befinden sich bereits im Stadium der kommerziellen Verwertung. Der Projektpartner hat damit begonnen eine Variante seines In-Memory-OLAP Servers Palo mit unseren Algorithmen zu entwickeln, die im Jahr 2010 in einer Vorabversion an den Markt ging und ab dem kommenden Release der Software mit separater Lizenzierung erhältlich sein wird.
Projektbezogene Publikationen (Auswahl)
- Efficient online aggregates in dense-region-based data cube representations. In Proceedings of the 11th International Conference on Data Warehousing and Knowledge Discovery (DaWaK 2009), Linz, Austria, Springer LNCS 5691, August 2009
K. Haddadin, T. Lauer
- Efficient range-sum queries along dimensional hierarchies in data cubes. In Proceedings of the 1st International Conference on Advances in Databases, Knowledge, and Data Applications (DBKDA 2009), Le Gosier, France, IEEE, März 2009
T. Lauer, D. Mai, P. Hagedorn
- Accelerating Business Intelligence Applications with Fast Multidimensional Aggregation. NVIDIA GPU Technology Conference 2010, San Jose, CA, USA, September 2010
T. Lauer, C. Anselm
- Exploring Graphics Processing Units as Parallel Coprocessors for Online Aggregation. Proceedings of DOLAP 2010, Toronto, Canada, ACM Press, October 2010
T. Lauer, A. Datta, Z. Khadikov und C. Anselm
- OSBI trifft Forschung: GPUs als parallele Coprozessoren für OLAP- Aggregationen. In: U. Haneke, S. Trahasch, T. Hagen, T. Lauer (Hrsg.): Open Source Business Intelligence, Hanser 2010
T. Lauer
- Real-Time Computation of Advanced Rules in OLAP Databases. Proceedings of ADBIS 2011, Wien, Austria, September 2011
S. Wittmer, T. Lauer, A. Datta
