Lexikon

Spaltenorientierte Datenbank

1 Einleitung

Relationale Datenbank-Management-Systeme (RDBMS) sind aus Unternehmen und anderen Institutionen nicht mehr wegzudenken. In ihnen lagert ein Großteil der strukturierten Daten, die bei der Ausführung von Geschäftsprozessen anfallen und verarbeitet werden. Diese Daten werden sowohl für die Bearbeitung von
Geschäftsvorfällen benötigt, als auch für Auswertungen, die zukünftige Entscheidungen beeinflussen können (Entscheidungsunterstützung). Ersteres wird im Allgemeinen als Online Transaction Processing (OLTP) bezeichnet, letzteres hingegen als Online Analytical Processing (OLAP). Schon seit langem besteht darüber Einigkeit, dass die beiden Verarbeitungsschritte auf getrennten Systemen laufen sollten. Dies hat den Grund, dass für beides unterschiedliche Optimierungen am RDBMS vorgenommen werden müssen: beispielsweise sind für analytische Ad-hoc-Anfragen viele Indizes oder materialisierte Sichten von Vorteil, während diese für schreibende Transaktionen eher hinderlich sind, da sie bei jeder Datenänderung aktualisiert werden müssten. Architektonisch sind diese Systeme in der Praxis jedoch meistens gleich. Erst in den letzten Jahren hat sich in der Datenbank-Forschung der Trend herauskristallisiert, gänzlich unterschiedliche Architekturen für diese verschiedenen Anwendungen zu entwerfen, da dies einen Geschwindigkeitsgewinn von Größenordnungen verspricht. Dieser Artikel beschreibt die daraus hervorgegangene Familie der spaltenorientierten Datenbanken und ihrer Derivate, welche für analytische Anfragen (OLAP) optimiert sind. Der nächste Abschnitt erklärt das Konzept der spaltenorientierten Datenbank zunächst anschaulich während Abschnitt 3 dies anhand der Speicher- Hierarchie eines zeitgemäßen Rechners konkretisiert. Hierbei finden nicht nur die rein spaltenorientierten, sondern generell vertikal fragmentierte Datenmodelle Berücksichtigung. Danach wird auf den Aspekt der Kompression genauer eingegangen, die spaltenorientierte Anfragebearbeitung beleuchtet und abschließend die verschiedenen verfügbaren Systeme in diesem Bereich erläutert.

2 Spaltenorientierung

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.

3 Klassifikation physischer Datenmodelle anhand der Speicher-Hierarchie

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.

4 Kompression

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.

5 Spaltenorientierte Anfrage-Ausführung

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.

6 Verfügbare Spaltenorientierte RDBMS

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

6.1 C-Store und Vertica

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.

6.2 MonetDB

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.

6.3 Kommerzielle Systeme

Ü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. 

7 Ausblick

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.

8 Danksagung

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

Literatur

[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.

Autor und Copyright

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