Spaltenorientierte Datenbank

Eine Spaltenorientierte Datenbank ist ein Datenbankmanagementsystem, das seine Inhalte spaltenweise statt zeilenweise abspeichert. Das hat für Anwendungen wie ein Data-Warehouse, wo Aggregate über große Zahlen ähnlicher Elemente gebildet werden, Vorzüge.^[1][2] Der spaltenorientierte Zugang steht im Kontrast zum zeilenorientierten, dem die meisten bekannten Datenbanksysteme folgen.

Beschreibung

Eine Datenbank stellt meistens ihre Daten als zweidimensionale Tabellen aus Zeilen und Spalten dar; diese müssen aber in eindimensionaler Form gespeichert werden. Zum Beispiel könnte eine Datenbank die folgende Tabelle enthalten:

Personalnr	Nachname	Vorname	Gehalt
1	Schmidt	Josef	40000
2	Müller	Maria	50000
3	Meier	Julia	44000

Diese einfache Tabelle enthält eine Spalte für die Personalnummer, Namensspalten und ein Gehalt.

Diese Tabelle existiert im Arbeitsspeicher und auf der Festplatte des Computers. Beide Speicherarten haben gemeinsam, dass die Daten aus der Sicht des Betriebssystems in einer eindimensionalen Folge von Bytes angeordnet sind. Die Aufgabe ist also zu lösen, die zweidimensionale Struktur einer Datenbanktabelle in eine eindimensionale Folge von Bytes abzubilden.

Eine zeilenorientierte Datenbank hängt alle Datenwerte einer Zeile aneinander, es folgt die nächste Zeile usw.

 1,Schmidt,Josef,40000;2,Müller,Maria,50000;3,Meier,Julia,44000;

Eine spaltenorientierte Datenbank geht stattdessen Spalte für Spalte vor:

1,2,3;Schmidt,Müller,Meier;Josef,Maria,Julia;40000,50000,44000;

Die physische Organisation einer Datenbank wird von Partitionierung, Indizes, Caching, Views, OLAP-Würfel und transaktionale Aspekte wie Write-Ahead-Logging stark beeinflusst. Unter der Berücksichtigung all dieser Einflüsse stellt sich heraus, dass OLTP-Systeme eher zeilenorientiert, OLAP-Systeme eine Balance aus Zeilen- und Spaltenorientierung anstreben.

Vor- und Nachteile

Vergleiche zwischen zeilenorientierten und spaltenorientierten Systemen konzentrieren sich typischerweise vor allem auf die Effizienz des Festplattenzugriffs, der im Vergleich zu anderen Operationen des Computers erhebliche Zeit verbraucht. Das Lesen eines Megabytes sequentiell gespeicherter Daten kann genauso lang dauern, wie ein einziger Direktzugriff.^[3]. Und da die Zugriffszeit der Festplatten sich im Vergleich zur CPU-Geschwindigkeit nur langsam verbessert (siehe Mooresches Gesetz), wird diese Sichtweise auch bleiben, solange die Systeme ihre Daten auf Festplatten speichern. In stark vereinfachter Form kann man sich durch die folgenden Beobachtungen ein Bild der Vor- und Nachteile der spalten- und zeilenorientierten Organisation machen.

1. Spaltenorientierte Systeme sind effizienter, wenn ein Aggregat über viele Zeilen, aber nur wenige Spalten gebildet werden muss, da man dann im Gegensatz zum zeilenorientierten System nur diese und nicht alle Spalten lesen muss (SELECT Gehalt FROM tabelle;).
2. Spaltenorientiere Systeme sind effizienter, wenn eine Spalte gleichzeitig für alle Zeilen der Tabelle einen neuen Wert erhält, da man die Spaltendaten effizient schreiben kann und die Daten der anderen Spalten nicht berücksichtigen muss (Bsp.: Gehaltserhöhung: UPDATE tabelle SET Gehalt = Gehalt*1,03;).
3. Zeilenorientierte Systeme sind effizienter, wenn gleichzeitig viele Spalten einer einzigen Zeile benötigt werden und wenn die Zeilenbreite sehr klein ist, da dann die ganze Zeile mit einem einzigen Plattenzugriff gelesen werden kann. (SELECT * FROM tabelle WHERE Personalnr = 1;)
4. Zeilenorientierte Systeme sind beim Einfügen einer neuen Zeile effizienter, wenn alle Daten dieser Zeile auf einmal vorliegen, da dann die Zeile mit einem einzigen Zugriff geschrieben werden kann (INSERT INTO tabelle VALUES(4,Maier,Karl-Heinz,45000);).

In der Praxis sind zeilenorientierte Architekturen für typische OLTP-Aufgaben (z. B. Buchhaltungssysteme) mit vielen interaktiven Transaktionen günstig. Spaltenorientiere Systeme sind gut für OLAP-Aufgaben geeignet (z. B. analytische Informationssysteme, die typischerweise durch eine kleine Anzahl sehr komplexer Abfragen über alle Datensätze charakterisiert sind. Es gibt aber auch eine Anzahl bewährter zeilenorientierter relationaler OLAP-Datenbanken, die Terabytes oder gar Petabytes von Daten bearbeiten können, so etwa Teradata.

Kompression

Spaltendaten haben einen einheitlichen Typ; daher stehen in spaltenorientierten Systemen einige Möglichkeiten der Plattenplatzoptimierung zur Verfügung, die bei zeilenorientierten Daten nicht möglich sind. Zum Beispiel machen sich viele Kompressionsschemata wie der Lempel-Ziv-Welch-Algorithmus (LZW) oder die Lauflängenkodierung die Ähnlichkeit benachbarter Daten für die Kompression zunutze. Zwar können diese Techniken auch für zeilenorientierte Daten eingesetzt werden, aber eine typische Implementation wird weniger effektive Ergebnisse erreichen.^[4][5].

Um die Kompression zu verbessern, sortieren einige Implementationen (zum Beispiel Vertica) die Spalten. In Verbindung mit Bitmap-Indizes kann Sortieren die Kompression um eine Größenordnung verbessern.^[6]. Um die Kompression der lexikographischen Ordnung bei der Lauflängenkodierung zu verbessen, empfiehlt es sich, die Spalten kleiner Kardinalität als die ersten Sortierungsschlüssel zu verwenden.^[7]. So wäre es bei einer Tabelle mit den Spalten Name, Geschlecht, Alter am günstigsten, zunächst anhand des Geschlechtes (Kardinalität 2), dann des Alters (Kardinalität < 150), und dann des Namens zu sortieren.

Spaltenkompression führt zu einer Reduzierung des Plattenplatzverbrauchs auf Kosten der Lesegeschwindigkeit. Sämtliche Daten einer einzelnen Spalte lassen sich viel effizienter lesen, wenn diese Daten an derselben Stelle abgespeichert sind, wie das bei einer zeilenorientierten Architektur der Fall ist. Der Zugriff auf einzelne Daten wird mit zunehmender Kompression schwieriger, da man erst große Datenmengen dekomprimieren muss, um einen einzigen Satz zu lesen. Daher werden spaltenorientierte Architekturen oft mit zusätzlichen Mechanismen bereichert, um die Notwendigkeit, auf komprimierte Daten zuzugreifen, zu minimieren.^[8].

Implementierungen

Spaltenspeicherung kam in der Form Invertierter Dateien schon in der Frühzeit der Datenbanksyteme, beginnend in den 1970ern. Zum Beispiel implementierte Statistics Canada das RAPID-System^[9] schon 1976 und benutzte es für die kanadische Volkszählung und einige andere statistische Anwendungen. RAPID wurde auch weltweit von anderen statistischen Organisationen bis in die 1980er genutzt, von Statistics Canada sogar bis in die 1990er.

Für viele Jahre war Sybase IQ das einzige auf dem Markt erhältliche Produkt im Bereich der spaltenorientierten Datenbanksyteme. Das hat sich allerdings inzwischen durch viele Open-Source- und kommerzielle Anwendungen stark geändert:

• Kommerziell
  • Oracle Retail Predicative Application Serve (RPAS)
  • SAND CDBMS
  • SenSage
  • SAP HANA
  • Sybase IQ
  • SADAS
  • Vertica und sein akademischer Bruder C-Store
  • Valentina
  • KDB
  • Kickfire
  • Addamark, heute Sensage Scalable Log Server
  • 1010datas Tenbase database
  • DataProbe
  • EXASolution
  • InfiniDB Enterprise Edition, Integration mit MySQL
  • Infobright Enterprise Edition, Integration mit MySQL (früher Brighthouse)
  • Skytide XOLAP Server
  • Space-Time Research SuperSTAR
  • ParAccel Analytic Database
  • Aster Data Systems
  • FluidDB
  • Die Ingres & Vectorwise initiative
  • smartFOCUS smartSERVER ADS
• Open-source (kostenpflichtig)
  • RC21
• Open-source (Freie Software)
  • Calpont InfiniDB Community Edition, (MySQL-Frontend), GPLv2
  • Apache Cassandra (Apache Software Foundation)
  • C-Store (mit kommerziellem Bruder Vertica, keine Weiterentwicklung seit Oktober 2006
  • GenoByte Spaltenbasiertes Speichersystem für Genotypdaten
  • Lemur Bitmap Index C++ Library (GPL)
  • FastBit
  • Infobright Community Edition
  • LucidDB und Eigenbase
  • MonetDB Universitätsprojekt
  • Metakit
  • S (Programmierprache) und GNU R benutzen spaltenorientierte Daten für statistische Analysen.

Einzelnachweise

1. ↑ A decomposition storage model, Copeland, George P. and Khoshafian, Setrag N., SIGMOD '85, 1985.
2. ↑ C-Store: A column-oriented DBMS, Stonebraker et al., Proceedings of the 31st VLDB Conference, Trondheim, Norway, 2005
3. ↑ The Star Schema Benchmark and Augmented Fact Table Indexing, Pat & Betty O’Neil, Xuedong Chen and Stephen Revilak, TPC Technology Conference 8/24/09
4. ↑ D. J. Abadi, S. R. Madden, N. Hachem, Column-stores vs. row-stores: how different are they really?, in: SIGMOD’08, 2008, pp. 967–980.
5. ↑ N. Bruno, Teaching an old elephant new tricks, in: CIDR ’09, 2009.
6. ↑ Daniel Lemire, Owen Kaser, Kamel Aouiche, Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering 69 (1), S. 3-28, 2010.
7. ↑ Daniel Lemire and Owen Kaser, Reordering Columns for Smaller Indexes (arXiv:0909.1346)
8. ↑ Brighthouse: an analytic data warehouse for ad-hoc queries, Slezak et al., Proceedings of the 34th VLDB Conference, Auckland, New Zealand, 2008
9. ↑ A DBMS for Large Statistical Databases, Turner, Hammond, Cotton, Proceedings of VLDB 1979, Rio de Janeiro, Brazil.