Spaltenorientierte Datenbank

Der Begriff der spaltenorientierten Datenbank (engl. column-oriented database) bezieht sich zunächst auf die Art und Weise, in der die Daten auf dem verwendeten persistenten Speichermedium (z.B. Festplatte) abgelegt werden. In traditionellen Datenbanken liegen dort immer alle Felder (Attribute) einer Tabellenzeile (Tupel) hintereinander, weshalb solche Datenbanken auch als zeilenorientiert und deren physisches Datenmodell oft als n-ar bezeichnet werden. Dies ist günstig, wenn in einer Transaktion wenige komplette Tupel gelesen oder geschrieben werden sollen. Im Gegensatz dazu kann bei einer rein spaltenorientierten Datenbank jede Spalte in einer eigenen Datei liegen, d.h. auf einen Wert eines Attributs eines Tupels folgt in Lese-Reihenfolge nicht das nächste Attribut des selben Tupels, sondern das gleiche Attribut des nächsten Tupels (siehe Abb. 1). Intuitiv funktioniert dies, da beim OLAP meistens wenige Attribute von sehr vielen Tupeln benötigt werden und durch die Spaltenorientierung die restlichen Attribute nicht gelesen werden müssen. Weitere Gründe werden später in diesem Artikel erläutert.

Die Speicherhierarchie (siehe Abb. 2) stellt eine hierarchische Ordnung von Speichertechniken (persistent und volatil) in einem Rechner dar, die sich aus verfügbarer Größe (meist umgekehrt proportional zum Kaufpreis) und Zugriffsgeschwindigkeit der Technologien ergibt. Neben Größe und Geschwindigkeit hat jede Ebene dieser Hierarchie eine Blockgröße, die die unteilbare Einheit eines Transfers in die nächsthöhere Ebene oder der Verdrängung aus selbiger vorgibt und nach oben in der Hierarchie immer kleiner wird. Die Anzahl solcher Transfers gilt als Kostenmaß für die Operationen in einem RDBMS.

Basierend auf dieser Speicherhierarchie betrachten wir nun einige in der Literatur beschriebene physische Datenmodelle und klassifizieren sie anhand von Trennung und Zusammenhalt der Attribute eines Tupels durch Seitengrenzen:

NSM. Im n-ären Speichermodell sind die Attribute nicht absichtlich voneinander getrennt, es sei denn, ein Datensatz ragt wegen seiner Länge über eine Cache-Zeile oder eine Festspeicherseite hinaus.

Spalten. Spaltenorientierte Datenbanken trennen Spalten durch Seitengrenzen des Festspeichers voneinander. Es gibt keine Verwaltungseinheit, innerhalb derer sich alle Attribute eines Tupels befinden. Der Zusammenhang der Attributwerte ist durch deren Position in der jeweiligen Spalte gegeben. Dadurch wird das sequentielle Lesen kompletter Spalten begünstigt. Schreiben von Tupeln wird dadurch jedoch sehr teuer und wird oft durch Differenzdateien realisiert.

PAX. In diesem Speichermodell werden die Attribute von Tupeln durch Zeilengrenzen des CPU-Cache getrennt, aber durch Festspeicherseiten zusammengehalten (siehe Abb. 1). Dadurch entsteht zunächst keine Ersparnis beim Lesen von Daten vom Festspeicher in den Hauptspeicher. Liegen die Daten jedoch ohnehin im RAM, entsteht somit eine spaltenorientierte Datenbank auf einer höheren Ebene der Speicherhierarchie. Müssen viele einzelne Tupel rekonstruiert oder geschrieben werden, kann ein Geschwindigkeitsvorteil gegenüber einem Column-Store realisiert werden, dessen Schwäche beim Zugriff auf einzelne Tupel auf dem Festspeicher liegt. PAX geniesst eine hohe Akzeptanz im akademischen Bereich, es sind allerdings noch keine verfügbaren Systeme auf dieser Basis bekannt.

DSM. Das Decomposition Storage Model (DSM) spaltet Relationen in binäre Relationen, die jeweils einen künstlichen Primärschlüssel (Surrogat) und eine Datenspalte umfassen. Da die Attribute eines Tupels in verschiedenen Festspeicherseiten liegen und durch nichts zusammengehalten werden, kann man beim DSM von einer spaltenorientierten Datenbank sprechen. Der Zusammenhang der Attributwerte wird durch Assoziation über das Surrogat erreicht. Das DSM verleitet schnell zu dem falschen Schluss, dass sich eine spaltenorientierte Datenbank in einer traditionellen Datenbank nachbilden liesse, in dem man alle Tabellen in zweispaltige Relationen aufteilt. Dass dies u.a. auf Grund der dann dominierenden Metadaten nicht sinnvoll ist, haben mehrere Untersuchungen gezeigt.

Ob die spaltenweise Speicherung die Kompression der Daten tatsächlich vereinfacht, weil dann Daten gleichen Typs aufeinander folgen, ist umstritten. Die beiden Konzepte werden jedoch oft kombiniert, um die tatsächlich gelesene Datenmenge weiter zu reduzieren. Es werden dabei allerdings keine der bekannten Kompressionsverfahren wie LZW oder BZ2 eingesetzt, sondern leichtgewichtige Verfahren, die es erlauben, relationale Operationen auf den komprimierten Daten auszuführen. So können z.B. mehrfach vorkommende Werte durch Kürzel fixer oder variabler Länge ersetzt werden, die durch ein Wörterbuch bei Bedarf wieder in die ursprünglichen Werte übersetzt werden können. Folgen oft identische Werte direkt aufeinander, können diese Sequenzen lauflängencodiert abgelegt werden. Sortierte ganzzahlige Daten können durch Differenzbildung zum jeweiligen Vorgänger oder zu einem lokalen Minumum in weniger Bits untergebracht werden. Manche dieser Kompressionsmethoden erschweren den wahlfreien Zugriff auf einzelne Tupel, was aber für OLAP-Anfragen ohnehin untypisch ist.

Wie bereits oben beim DSM erwähnt, reicht die reine Spaltenorientierung nicht aus, um grosse Fortschritte bei der Anfrage-Bearbeitung zu erreichen. Stattdessen haben die existierenden Systeme neue Strategien entwickelt, um auf (komprimierten) Spalten zu operieren. Die Benutzerschnittstelle bleibt zwar weiterhin SQL, aber die dahinter liegende Ausführungsplanung und -optimierung ändert sich. Da bei analytischen Anfragen oft viele Datensätze benötigt werden, um Werte zu verdichten und das sequentielle Lesen der Daten aus technischen Gründen meistens schneller geht und eventuelle Kompression wahlfreie Zugriffe erschwert, hat es sich als effektive Strategie etabliert, mehrere Spalten parallel zu scannen und somit immer die benötigten Attribute in einem Fenster im schnellen, flüchtigen Speicher zu haben. Operatoren werden nicht mehr als Iteratoren über einzelne Tupel realisiert, sondern als Iteratoren über ganze Blöcke von Werten.

Weiterhin ändern sich einige Optimierungsziele, wenn ein spaltenorientiertes Datenmodell zugrunde gelegt wird. Während bei klassischen RDBMS gilt, dass die Projektionsoperatoren, die die benötigten Attribute aus allen verfügbaren herausprojizieren, möglichst früh auszuführen sind, wird daraus eine späte Materialisierung in einer spaltenorientierten Datenbank, da dann die benötigten Attribute erst so spät wie möglich hinzu geladen werden sollten.

Nicht nur die Spaltenorientierung sollte so lange wie möglich während der Ausführung beibehalten werden, sondern auch die Kompression. Untersuchungen haben gezeigt, dass ein Column-Store, der komprimierte Spalten liest und sofort zu unkomprimierten Relationen zusammensetzt, sich ähnlich wie eine zeilenorientierte Datenbank verhält.

In diesem Abschnitt seien kurz die wesentlichen Eigenschaften der wichtigen spaltenorientierten Datenbanken aus Forschung und Wirtschaft vorgestellt.

C-Store [Aba08] wurde im Rahmen einer Dissertation entwickelt, die 2008 am MIT eingereicht wurde. Das physische Datenmodell beruht auf überlappenden Projektionen (Teilmengen der Spalten einer Relation), die in unterschiedlichen Sortierungen vorliegen können und spaltenweise gespeichert werden. Die Spalten werden aggressiv komprimiert und durch paralleles Scannen nach dem Reissverschluss-Prinzip wieder zu Tupeln zusammengesetzt. Die Kompression wird dabei so lange wie möglich beibehalten. änderungen werden in eine vorgelagerte schreiboptimierte Datenbank gespeichert, die regelmässig in den komprimierten Datenbestand hinein synchronisiert wird.

Michael Stonebraker (der Schöpfer von Ingres und Postgres), der an der Betreuung der Dissertation beteiligt war, hat inzwischen ein Unternehmen namens Vertica1 mitgegründet, welches die kommerzielle Weiterentwicklung von C-Store vertreibt.

Seit Mitte der 90er wird am Centrum Wiskunde & Informatica (CWI) in Amsterdam ein System namens MonetDB [Bon02] mit dem Schwerpunkt auf leselastigen Anfragen entwickelt. Der Fokus war dabei von Anfang an auf modernen Rechnerarchitekturen (z.B. auf grossen Hauptspeichern, die damals bereits in akzeptablen Grössen für eine komplette Datenbank verfügbar waren), wobei dies später noch im Projekt "X100" (kurz für times hundred, also hundertmal so schnell) in Richtung moderner CPUs weiter ausgebaut wurde. MonetDB setzt verschiedene Konzepte um, so z.B. Spaltenorientierung durch die Implementation des Decomposition Storage Model (DSM) (s.o.), welches mittels Hash-Tabellen im Hauptspeicher realisiert wird. Dazu werden immer ganze Spalten oder grosse Teile davon auf einmal in den Hauptspeicher geladen. Weiterhin ist der Datenbank-Kern nicht als relationales System ausgelegt, sondern nur als virtuelle Maschine, die sich auf die Verarbeitung von Spalten versteht. Datenmodelle wie das relationale Modell (oder XML und XQuery) werden in Frontends realisiert, die mit dem Datenbank-Kern über eine Assembler-Sprache kommunizieren.

Über den Aufbau der Systeme mit kommerziellem Hintergrund ist weit weniger bekannt als über die Forschungsprototypen. Nur genannt seien hier neben Vertica (s.o.) das Open-Source RDBMS LucidDB 2 sowie Sybase IQ3, welches als einziges spaltenorientiertes System von einem grossen Datenbankhersteller stammt. 

Verschiedene spaltenorientierte Datenmodelle und Ausführungsstragtegien wurden in den letzten Jahren vorgeschlagen. über Details wird manchmal noch gestritten; Einigkeit besteht jedoch darüber, dass das klassische NSM für analytische Anfragen ungeeignet ist. Einige halten es im Zeitalter von MulticoreSystemen mit grossem Hauptspeicher sogar bei OLTP für ungeeignet. Beispielsweise arbeitet dass Hasso-Plattner-Institut in Potsdam an einem vereinten, spaltenorientierten Datenmodell für OLTP und OLAP, welches im Hauptspeicher und ohne jegliche Indizes realisiert werden soll. Obwohl mit der Spaltenorientierung Beschleunigungen von mehreren Grössenordnungen erreicht wurden, bleibt abzuwarten, ob und wann die arrivierten Hersteller diese Trends aufgreifen, da dies grundlegende änderungen an ihren Systemen bedeuten würde.

Mein Dank gilt Heinz F. Schweppe, Ulrike Barich und Jürgen Bross für viele hilfreiche Kommentare zu diesem Artikel.

[Aba08] Daniel J. Abadi. Query Execution in Column-Oriented Database Systems. PhD thesis, Massachusetts Institute of Technology, February 2008.

[Bon02] P. A. Boncz. Monet: A Next-Generation DBMS Kernel For QueryIntensive Applications. Ph.d. thesis, Universiteit van Amsterdam, Amsterdam, The Netherlands, May 2002.

Daniel Bösswetter 
Freie Universität Berlin, Institut für Informatik 
Arbeitsgruppe Datenbanken und Informationssysteme
Takustrasse 9, 14195 Berlin
E-Mail

© 2010 Informatik Spektrum, Springer-Verlag