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.
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 ein1. 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.2
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.3
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.4
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 getrennt5. Die Datenbank für das DSS wird Data Warehouse genannt und von Inmon und Jürgens6 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.7
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 OLAP8
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.9
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.10
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Beispiel eines B-Trees11
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.12
[...]
1 vgl. O’Neil, 1987
2 vgl. O’Neil;O’Neil, 2001, S.470f
3 vgl. Geisler, 2006, S.121
4 vgl. Geisler, 2006, S.122
5 vgl. Jürgens, 2002, S.5ff
6 Inmon, 2002, S.33 und Jürgens, 2002, S.7
7 vgl. Jürgens, 2002, S.10
8 Modifiziert nach Jürgens, 2002, S.9
9 vgl. Mehta;Sahni, 2005, S.15-1 f
10 vgl. Lane, 2005, S.6-4
11 Quelle: Mehta;Sahni, 2005, S.15-4
12 vgl. Ramakrishnan;Gehrke, 2002, S.344ff
- Citation du texte
- Ralf Brunner (Auteur), 2008, Bitmap Indizes und ihre Einsatzmöglichkeiten, Munich, GRIN Verlag, https://www.grin.com/document/137769
-
-
-
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X. -
-
Téléchargez vos propres textes! Gagnez de l'argent et un iPhone X.