Spaltenorientierte Datenbank
Eine spaltenorientierte Datenbank ist ein Datenbankmanagementsystem, das seine Inhalte spaltenweise (und nicht zeilenweise) physisch abspeichert. Das hat Vorteile bei Anwendungen wie einem Data-Warehouse, wo Aggregate über große Zahlen ähnlicher Elemente gebildet werden.[1][2] Der spaltenorientierte Ansatz 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 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
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 groß 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
Spaltendaten haben einen einheitlichen Datentyp; 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 Indizes 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
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 proprietäre Anwendungen stark geändert:
- Proprietär
- ParStream
- Oracle 12c Enterprise Edition mit der neuen kostenpflichtigen In-Memory Option
- Oracle Retail Predicative Application Serve (RPAS)
- SAND CDBMS
- SenSage
- SAP HANA
- Sybase IQ
- SADAS
- Vertica und sein akademischer Bruder C-Store
- Valentina
- KDB
- Kickfire
- Db2 – IBM DB2 with BLU Acceleration[11]
- Addamark, heute Sensage Scalable Log Server
- 1010datas Tenbase database
- DataProbe
- Exasol
- 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
- Ingres
- smartFOCUS smartSERVER ADS
- Microsoft SQL Server 2012 mit dem neuen Feature Column Store Index.
- Freie Software (Open-source)
- RC21, GPL[12]
- Calpont InfiniDB Community Edition, (MySQL-Frontend), GPLv2
- Apache Cassandra (Apache Software Foundation)
- C-Store (mit kommerziellem Support durch die Firma 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
- MariaDB[13]
- Metakit
- MonetDB besondere Eignung für statistische Analysen mit R (Mozilla Public License)
- Apache Druid
Einzelnachweise
- George P. Copeland, Setrag N. Khoshafian: A decomposition storage model. SIGMOD ’85, 1985, doi:10.1145/318898.318923.
- C-Store: A column-oriented DBMS. (PDF; 174 kB) In: Stonebraker et al.: Proceedings of the 31st VLDB Conference, Trondheim 2005
- Pat & Betty O’Neil, Xuedong Chen, Stephen Revilak: The Star Schema Benchmark and Augmented Fact Table Indexing. (PDF; 501 kB) TPC Technology Conference 8/24/09
- D. J. Abadi, S. R. Madden, N. Hachem: Column-stores vs. row-stores: how different are they really? SIGMOD’08, 2008, S. 967–980.
- N. Bruno: Teaching an old elephant new tricks. (PDF; 185 kB) CIDR ’09, 2009.
- Daniel Lemire, Owen Kaser, Kamel Aouiche: Sorting improves word-aligned bitmap indexes. In: Data & Knowledge Engineering, 69 (1), 2010, S. 3–28. arxiv:0901.3751
- Daniel Lemire, Owen Kaser: Reordering Columns for Smaller Indexes, arxiv:0909.1346
- Slezak et al.: Brighthouse: an analytic data warehouse for ad-hoc queries (PDF; 456 kB), Proceedings of the 34th VLDB Conference, Auckland 2008
- Oracle Advanced Compression. Oracle Technet
- Turner, Hammond, Cotton: A DBMS for Large Statistical Databases. In: Proceedings of VLDB 1979, Rio de Janeiro.
- ibm.com
- http://www.vermontdatabase.com/rc21home.htm
- Informatik Aktuell: MariaDB ColumnStore