Spaltenorientierte Datenbank

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 zu lösende Aufgabe ist also, 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 transaktionalen Aspekten 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[Bearbeiten]

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.

  • 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.
    Beispiel: SELECT SUM(Gehalt) FROM tabelle;
  • Spaltenorientierte 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.
    Beispiel Gehaltserhöhung: UPDATE tabelle SET Gehalt = Gehalt * 1.03;
  • 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.
    Beispiel: SELECT * FROM tabelle WHERE Personalnr = 1;
  • 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.
    Beispiel: INSERT INTO tabelle (Personalnr, Nachname, Vorname, Gehalt) 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, oder auch IBM PureData System for Analytics (IBM Netezza).

Kompression[Bearbeiten]

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 verbessern, 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.

Bei einer spaltenorientierten Datenbank, wo jede einzelne Spalte für sich komprimiert werden kann, hat die Spaltenreihenfolge in der Tabelle auf die Komprimierung zwar keinen Einfluss. Die Reihenfolge kann aber in jedem Fall bei zusammengesetzten Indices zu besseren Kompressionsraten führen. Jedoch kann beim Umsortieren der Nutzen eines Index' für eine Abfrage verloren gehen, die nur einen Teil der Indexfelder vorgibt. Umfasst der Index über alle Mitarbeiter beispielsweise Name und Werk, wird die Kompression zu steigern sein, wenn er nach Werk und Name umsortiert wird. Für eine Suche nach Name ist der Index danach allerdings üblicherweise nicht mehr zu gebrauchen.

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

Seit Mitte der 2000er Jahre gilt die Annahme, die Komprimierung sei unter dem Strich langsamer, nicht mehr unbedingt. Mit zunehmender Rechenleistung ist es zumeist schneller geworden, kleine Datenmengen von Platte zu holen und danach zu dekomprimieren, anstatt große unkomprimierte Datenmengen zu lesen. Dasselbe gilt für Schreibzugriffe. So setzen auch die Hersteller zeilenorientierter Datenbanken wie Oracle auf Komprimierung und empfehlen diese auf geeigneten Servern zur Geschwindigkeitssteigerung.[9]

Implementierungen[Bearbeiten]

Spaltenspeicherung kam in der Form Invertierter Dateien schon in der Frühzeit der Datenbanksysteme, beginnend in den 1970ern. Zum Beispiel implementierte Statistics Canada das RAPID-System[10] 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 Datenbanksysteme. Das hat sich allerdings inzwischen durch viele Open-Source- und kommerzielle Anwendungen stark geändert:

Einzelnachweise[Bearbeiten]

  1. A decomposition storage model, Copeland, George P. and Khoshafian, Setrag N., SIGMOD '85, 1985.
  2. C-Store: A column-oriented DBMS (PDF; 174 kB), Stonebraker et al., Proceedings of the 31st VLDB Conference, Trondheim, Norway, 2005
  3. The Star Schema Benchmark and Augmented Fact Table Indexing (PDF; 501 kB), 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 (PDF; 185 kB), 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 (PDF; 456 kB), Slezak et al., Proceedings of the 34th VLDB Conference, Auckland, New Zealand, 2008
  9. Oracle Advanced Compression in Oracles Technet
  10. A DBMS for Large Statistical Databases, Turner, Hammond, Cotton, Proceedings of VLDB 1979, Rio de Janeiro, Brazil.
  11. http://www-01.ibm.com/software/data/db2/linux-unix-windows/db2-blu-acceleration/
  12. http://www.tpc.org/tpch/default.asp