Bitmap Indizes und ihre Einsatzmöglichkeiten

Inhaltsverzeichnis

Tabellenverzeichnis

Abbildungsverzeichnis

Abkürzungsverzeichnis

Kurzfassung

Abstract

1 Einleitung
1.1 Notwendigkeit von Indizes
1.2 OLAP vs. OLTP

2 B-Tree Indizes
2.1 B-Tree
2.2 B+-Tree und B*-Tree
2.3 Kombination mehrerer Dimensionen

3 Bitmap Indizes
3.1 Funktionsweise
3.2 Kombination mehrerer Dimensionen
3.3 Komprimierung
3.3.1. Byte basierte Komprimierung
3.3.2. Wort basierte Komprimierung
3.4 Kodierung

4 Query Optimizer

5 Fallstudie
5.1 Befüllung und Indizierung
5.2 Abfragen
5.2.1. Zählen aller Bürger
5.2.2. Zählen mit zwei Dimensionen
5.2.3. Personen pro Bundesland
5.2.4. Durschnittseinkommen mit 5 Dimensionen
5.2.5. Durschnittseinkommen und NULL-Wert
5.2.6. Range Query
5.3 Updates
5.4 Inserts
5.5 Deletes

6 Zusammenfassung der Ergebnisse
6.1 Speicherplatz
6.2 Abfragen
6.3 Inserts, Updates und Deletes

7 Fazit

Literaturverzeichnis

A Anhang
A.1 Erstellen der Tabelle buerger
A.2 Prozedur: Füllen mit Zufallswerten
A.3 Befüllen und vervielfältigen der Tabelle
A.4 Erzeugen von Statistiken
A.5 Abfrage: Zählen mit zwei Dimensionen
A.6 Prozedur: zufällige Updates
A.7 Prozedur: zufällige Deletes

Tabellenverzeichnis

Tabelle 1: Unterschiede zwischen OLTP und OLAP

Tabelle 2: Beispiel eines Bitmap Index

Tabelle 3: Bitmap Operation: männlich AND ledig

Tabelle 4: Aufbau der Bundesbürger-Tabelle

Tabelle 5: Erstellen der Tabellen und Indizes

Tabelle 6: Ergebnis - Zählen aller Bürger

Tabelle 7: Ergebnis - Zählen mit zwei Einschränkungen

Tabelle 8: Ergebnis - Personen pro Bundesland

Tabelle 9: Ergebnis - Durchschnittseinkommen mit 5 Dimensionen

Tabelle 10: Ergebnis - Durchschnittseinkommen und NULL-Wert

Tabelle 11: Ergebnis - Range-Abfragen

Tabelle 12: Ergebnis - Updates

Tabelle 13: Ergebnis - Inserts

Tabelle 14: Ergebnis - Deletes

Abbildungsverzeichnis

Abbildung 1: Beispiel eines B-Trees

Abbildung 2: Beispiel eines B+-Trees

Abbildung 3: BBC komprimierte Bytefolge

Abbildung 4: Beispiel eines kodierten Bitmap Index

Abbildung 5: Performance-Analyse von kodierten Bitmap Indizes

Abbildung 6: Ausführungsplan mit Bitmap Indizes

Abbildung 7: Ausführungsplan mit B-Tree Indizes

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Kurzfassung

Für das schnelle Auffinden von Daten in einer Datenbank werden Indizes verwendet. Heutzutage unterstützen einige Datenbanken, unter anderem Oracle und DB2, die Verwendung von Bitmap Indizes. Im Gegensatz zu B-Tree Indizes sind sie vor allem für Spalten geringer Kardinalität und für multidimensionale Abfragen geeignet. Speziell durch die Verbreitung von Data Warehouses und die Notwendigkeit, statistische Auswertungen über große Datenmengen durchzuführen, gewinnen Bitmap Indizes an Bedeutung.

Ziel dieser Arbeit ist es, Bitmap Indizes näher zu beleuchten und mit den traditionellen B-Tree Indizes zu vergleichen. Es wird herausgearbeitet, unter welchen Umständen der Einsatz von Bitmap Indizes Vorteile bringt und wann von ihrer Verwendung abgesehen werden sollte.

Nach einer kurzen Einführung in die Thematik, werden B-Tree Indizierung und Bitmap Indizierung vorgestellt und in einer Fallstudie anhand einer Oracle Beispieldatenbank praktisch gegenübergestellt.

Bitmap Indizes überzeugen durch ihre kompakte Größe und bieten Geschwindigkeitsvorteile bei einer Vielzahl komplexer Abfragen über große Datenmengen hinweg. Sie können nicht nur für Attribute mit sehr kleiner Kardinalität, sondern durchaus auch für Attribute mittlerer bis höherer Kardinalität effizient eingesetzt werden.

Die größten Performance-Verbesserungen bieten Bitmap Indizes bei der Beantwortung komplexer Kombinationen, wenn die resultierende Selektivität so hoch ist, dass nur noch wenige Datensätze tatsächlich betrachtet werden müssen.

Abstract

Indexes are used to locate data records in a database in a quick way indexes are used. Nowadays several databases, like Oracle and DB2, do support the use of bitmap indexes. Unlike B-tree indexes they are especially suitable for columns with low cardinality and for multidimensional queries. Because of the spread of data warehouses and the need to make complex statistical analysis over large sets of data, bitmap indexes gain in importance.

The goal of this paper is to have a closer look on bitmap indexes and compare them to traditional B-tree indexes. It will be demonstrated under which conditions the use of bitmap indexes will help to gain advantages and when someone should abandon using it.

After a short introduction of the topic, b-tree indexes and bitmap indexes will be presented and practically compared on the basis of an example database implemented in Oracle.

Bitmap Indexes convince because of their compact size and provide speed advantages in numerous complex queries on large sets of data. They can not only be used for attributes with very low cardinality but can also be used efficiently for attributes with medium or higher cardinality.

The biggest performance improvements are provided executing complex queries, when the resulting selectivity is that high, that only very few data records actually have to be read.

Einleitung

Für das schnelle Auffinden von Daten in einer Datenbank werden Indizes verwendet. Traditionelle B-Tree Indizes sind allerdings nicht zwangsläufig die beste Wahl und werden bei sinkender Selektivität ineffizienter. Model 204 setzte als erste kommerzielle Datenbank bereits in den 80er-Jahren eine Art Bitmap Index ein¹. Heutzutage unterstützen auch weitere Datenbanken, unter anderem Oracle und DB2, die Verwendung von Bitmap Indizes. Im Gegensatz zu B-Tree Indizes sind sie vor allem für Spalten geringer Kardinalität und für multidimensionale Abfragen geeignet. Speziell durch die Verbreitung von Data Warehouses (DWH) und die Notwendigkeit komplexe statistische Auswertungen über große Datenmengen durchzuführen gewinnen Bitmap Indizes an Bedeutung.

Ziel dieser Arbeit ist es, Bitmap Indizes näher zu beleuchten und mit den traditionellen B-Tree Indizes zu vergleichen. Es wird herausgearbeitet, unter welchen Umständen der Einsatz von Bitmap Indizes Vorteile bringt und wann von ihrer Verwendung abgesehen werden sollte.

Im Folgenden wird mit einer Einführung in die Thematik der Indizierung und einer Erläuterung der Begriffe OLTP (Online Transaction Processing) und OLAP (Online Analytical Processing) begonnen. Anschließend werden die Indizierungsmöglichkeiten der B-Tree Indizierung und Bitmap Indizierung vorgestellt. Mit einer Fallstudie zum praktischen Vergleich der Indizierungsarten anhand einer Oracle Beispieldatenbank stellt Kapitel 5 das Kernstück dieser Arbeit dar. Abgerundet wird die vorliegende Bachelorarbeit mit einer Zusammenfassung und kritischen Diskussion der theoretischen und praktischen Erkenntnisse und einem abschließendem Fazit.

1.1 Notwendigkeit von Indizes

Computer Hardware wurde in den letzten Jahrzehnten kontinuierlich schneller und billiger. Allerdings konnte die Entwicklung der Festplatten nicht mit der Entwicklung der Prozessoren mithalten. Der Lesekopf einer Festplatte muss in Position gebracht werden, dann wird gewartet bis die rotierende Platte an der richtigen Position ist und erst dann können Daten gelesen oder geschrieben werden. Aus Performance-Gründen ist es das Ziel einer Datenbank diese mechanischen Zugriffe auf ein Minimum zu beschränken.²

Um Datensätze einer Datenbank aufzufinden und auszulesen, gibt es verschiedene Ansätze. Der Full Table Scan, das sequentielle Durchsuchen aller Datensätze, ist der Worst Case und steht immer zur Verfügung. Dieser ist bei großen Datenmengen sehr zeitintensiv, da alle Datensätze einer Tabelle, egal ob benötigt oder nicht, von der Festplatte gelesen werden müssen.

Um nicht auf alle Datensätze zugreifen zu müssen, gibt es verschiedene Techniken der Indizierung. Dazu existiert eine von der Datenstruktur getrennt gehaltene Indexstruktur mit sortierten Attributen und Zeigern auf die entsprechenden Datensätze. Es kann nun im Vergleich zum Full Table Scan wesentlich zeiteffizienter in der Indexstruktur gesucht werden und Zugriffe auf die Festplatte werden reduziert.³

Allerdings ist es nicht zwingend sinnvoll, für jedes Attribut einen Index anzulegen. Der Index selber belegt ebenfalls Speicherplatz, und zusätzlich muss er bei Änderungen in der Datenbank aktualisiert werden. Diese Pflege des Index wirkt sich demzufolge beim Hinzufügen, Löschen oder Ändern von Datensätzen negativ auf die Performance aus. Es liegt also in der Verantwortung des Datenbankdesigners abzuwägen, für welche Spalten die Verwendung von Indizes angebracht ist und für welche nicht.⁴

1.2 OLAP vs. OLTP

Bei einer traditionellen OLTP Datenbank werden Daten fortlaufend durch Transaktionen verändert. Diese Transaktionen müssen die vier Eigenschaften Atomarität, Konsistenz, Isolation und Dauerhaftigkeit aufweisen. DSS (Decision Support Systems) oder MIS (Management Information Systems) erstellen häufig Berichte indem sie Daten lesen, gruppieren und aufsummieren. Die Möglichkeit mit einem DSS auf die operative OLTP Datenbank zuzugreifen hat den Vorteil nur eine Datenbank verwalten zu müssen, wodurch der administrative Aufwand gering bleibt. Das DSS kann allerdings in diesem Fall nur auf die aktuellen Daten zugreifen was historische Analysen verhindert. Weiters ist eine OLTP Datenbank für Transaktionen im Mehrbenutzerbetrieb optimiert, was auch das Sperren betroffener Datensätze beinhaltet. Da analytische Abfragen oft sehr viele Datensätze betreffen, verringern diese die Gesamtperformance der operativen Datenbank. Um diese Probleme zu umgehen, wird häufig die Datenbank für das DSS von der operationalen Datenbank physikalisch getrennt⁵. Die Datenbank für das DSS wird Data Warehouse genannt und von Inmon und Jürgens⁶ wie folgt definiert:

- Subject oriented (Themenorientiert): Das Ziel der Daten in einem Data Warehouse ist es, die Entscheidungsfindung, Planung und Kontrolle zu verbessern. Im Gegensatz dazu sind OLTP-Anwendungen dafür ausgelegt Arbeitsabläufe zu unterstützen.
- Integrated (Vereinheitlichung): Die Daten eines Data Warehouses werden von unterschiedlichen Quellen, welche die Daten in verschiedenen Formaten speichern, geladen. Sie müssen überprüft, bereinigt und in ein einheitliches Format transformiert werden, um schnellen Zugriff zu gewährleisten.
- Time variant (Zeitorientierung): In OLTP-Anwendungen werden die aktuellen Daten zum Zeitpunkt des Zugriffs abgefragt. In einem Data Warehouse werden Daten in definierten periodischen Abständen aktualisiert, dadurch entsprechen die Daten dem Stand der letzten Aktualisierung.
- Non-volatile (Beständigkeit): Nach dem Einfügen der Daten in das Data Warehouse werden Daten weder verändert noch gelöscht. Die einzigen Ausnahmen sind, wenn falsche Daten eingetragen wurden oder die Kapazitätsgrenzen des Data Warehouses erreicht werden und eine Archivierung notwendig wird.

Anwendungen wie DSS oder MIS, welche Data Warehouses benutzen, werden OLAP-Anwendungen genannt. OLAP-Anwendungen werden typischerweise mit einem RDBMS (Relational Database Management System) umgesetzt, da diese Technologie gut verstanden wird und in der Lage ist große Datenmengen zu verwalten. OLAP-Anwendungen welche auf RDBMS basieren, werden auch ROLAP (Relational Online Analytical Processing) genannt.

Bei OLTP-Anwendungen wird das Datenmodell normalisiert, um die Konsistenz bei Insert, Update und Delete Anweisungen zu gewährleisten und um Redundanzen zu vermeiden. Das oberste Ziel einer OLAP-Anwendung ist es, in kurzer Zeit Statistiken über viele Datensätze zu liefern. Um dieses Ziel zu erreichen, wird im Gegensatz zu OLTP ein denormalisiertes Datenmodell verwendet.⁷

Abschließend werden in Tabelle 1 die Unterschiede zwischen OLTP und OLAP übersichtlich und zusammenfassend aufgelistet.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Unterschiede zwischen OLTP und OLAP⁸

2 B-T REE I NDIZES

In diesem Kapitel wird auf den B-Tree und dessen Varianten den B+-Tree und B*-Tree eingegangen. Die unterschiedlichen Bezeichnungen werden in der Literatur nicht konsequent getrennt, so spricht Oracle bei ihrer Implementierung von B-Tree obwohl es technisch gesehen eine Weiterentwicklung eines solchen ist.

2.1 B-Tree

In einem Baum werden Schlüssel, also die zu indizierenden Ausprägungen eines Attributes, und Ihre physikalische Position, die Rowid, gespeichert. Der B-Tree ist eine Erweiterung der binäreren Suchbäume, für die Speicherung großer Datenmengen auf Festplattenspeicher ausgelegt und per Definition immer ausgeglichen. Binäre Suchbäume sind wegen der großen Anzahl von Sprüngen von Knoten zu Knoten und der damit verbundenen Festplattenzugriffe nicht geeignet. Da bei jedem Festplattenzugriff ein ganzer Block gelesen wird, werden beim B-Tree die Knoten erweitert, um mehr als zwei Einträge, bis maximal der Blockgröße entsprechend viele Einträge zu speichern. Um die gleichmäßige Perfomance zu garantieren, verlangt der B-Tree, dass jeder Knoten, mit Ausnahme des Wurzelknotens, mindestens zur Hälfte gefüllt ist. Eine exakte Such-, Einfüge- oder Löschabfrage ist demnach von der Ordnung O(logB n), wobei B die maximale Anzahl von Einträgen pro Knoten und n die Gesamtzahl der Einträge repräsentiert. Die Höhe eines Baumes ist für einige Milliarden Einträge nur ~5, wenn man davon ausgeht, dass B in der Größenordnung von 100 liegt.⁹

B-Tree Indizes indizieren nur vorhandene Werte, ignorieren also NULL Werte. Eine Abfrage, welche z.B. die Anzahl der NULL Werte zählen soll, kann somit nicht den Index benutzen.¹⁰

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Beispiel eines B-Trees¹¹

In Abbildung 1 enthält jeder Indexknoten („Nicht-Blattknoten“) zwischen zwei und vier Verweisen auf Kindknoten, und jeder Blattknoten enthält zwischen zwei und vier Objekten. Der Wurzelknoten A enthält ein Objekt mit dem Wert 25 und zwei Verweise auf Kindknoten. Im linken Unterbaum befinden sich nur Objekte mit einem Wert <= 25, und im rechten Unterbaum besitzt jedes Objekt einen Wert > 25. Alle Blattknoten (D bis I) befinden sich auf derselben Tiefe: ihr Abstand zum Wurzelknoten A ist 2. Im Moment gibt es zwei volle Knoten: den Knoten B und den Blattknoten D.

2.2 B + -Tree und B*-Tree

Der B+-Tree ist eine Variante des B-Trees mit zwei prinzipiellen Änderungen. Die eigentlichen Datenelemente werden in dieser Variante auf die Blattknoten verlegt, also enthalten die Indexknoten nun lediglich die Schlüssel, welche zur Verzweigung verwendet werden. Dadurch gewinnt man in den Indexknoten Platz und kann folglich breiter verzweigen. Durch die breitere Verzweigung wird die Höhe des Baumes verringert, was die Anzahl der Festplattenzugriffe reduziert und das Traversieren des Baumes beschleunigt. Die zweite Änderung ist, dass alle Blattknoten in einer doppelt verketteten Liste miteinander verbunden werden. Dies ist besonders dann von Vorteil, wenn der Baum in einem Intervall durchlaufen werden soll.¹²

[...]

¹ vgl. O’Neil, 1987

² vgl. O’Neil;O’Neil, 2001, S.470f

³ vgl. Geisler, 2006, S.121

⁴ vgl. Geisler, 2006, S.122

⁵ vgl. Jürgens, 2002, S.5ff

⁶ Inmon, 2002, S.33 und Jürgens, 2002, S.7

⁷ vgl. Jürgens, 2002, S.10

⁸ Modifiziert nach Jürgens, 2002, S.9

⁹ vgl. Mehta;Sahni, 2005, S.15-1 f

¹⁰ vgl. Lane, 2005, S.6-4

¹¹ Quelle: Mehta;Sahni, 2005, S.15-4

¹² vgl. Ramakrishnan;Gehrke, 2002, S.344ff