Data Warehouse Technologien

7

Indexstrukturen

Indexe in Datenbanksystemen sind Datenstrukturen (oder Dateiformate), die

den Zugriff auf die eigentlichen Daten beschleunigen. Ein Index könnte zum

Beispiel ein Suchbaum sein, der den Zugriff auf einen bestimmten Wert mit lo-

garithmischem Aufwand ermöglicht, anstatt eine komplette Datei durchsuchen

zu müssen. In relationalen DBMS ist in Abwesenheit von Indexen beim Zugriff

ein sogenannter Full-Table-Scan nötig, der eine Relation komplett durchläuft.

Faktentabellen im Data Warehouse sind in der Regel so groß, dass ein Full-

Table-Scan in vielen Fällen nicht sinnvoll ist. Hierfür ein kleines Rechenbei-

spiel: Ein Scan über eine 10-GB-Tabelle bei einer Lesegeschwindigkeit von 10

MB/s würde ca. 17 Minuten dauern. Natürlich gibt es (wenige) Anfragen, die

den gesamten Datenbestand betreffen, und bei denen man einen Full-Table-

Scan einsetzen muss.

Typische Anfragen betreffen aber oft nur einen verhältnismäßig kleinen

Anteil der vorhandenen Daten: Je nach Beschränkung der einzelnen Dimensio-

nen umfasst die Antwort nur wenige Prozent oder Promille (oder noch weniger)

aller Daten. Hier ist die Verwendung von Indexstrukturen sinnvoll, um die An-

zahl der zu lesenden Datenseiten zu minimieren.

7.1 Klassifikation von Indexstrukturen

In den letzten Jahrzehnten ist eine Vielzahl von Indexstrukturen entwickelt

worden. Sie lassen sich anhand unterschiedlicher Kriterien klassifizieren (für

eine ausführliche Diskussion sei auf [SSH11] verwiesen), von denen die folgen-

den für DW-Systeme besonders relevant sind:

195

• Clustering: Daten, die voraussichtlich oft zusammen verarbeitet werden,

werden auch in der Speicherung physisch nahe beieinander abgelegt.

Man kann zwei Arten des Clustering unterscheiden:

– Tupel-Clustering: Tupel, die voraussichtlich zusammen gelesen wer-

den, werden auf der gleichen physischen Seite abgelegt.

– Seiten-Clustering: Hier erfolgt ein Hintereinanderablegen zusammen-

gehöriger Seiten im Sekundärspeicher. Das Seiten-Clustering erlaubt

das Prefetching von Seiten.

• Dimensionalität: Indexverfahren unterscheiden sich in ihrer Dimensiona-

lität. Die Dimensionalität gibt an, wie viele Attribute (Dimensionen) einer

zugrunde liegenden Relation für die Berechnung des den Zugriff beschleu-

nigenden Indexschlüssels verwendet werden.

• Symmetrie: Wenn die Performance bei mehrdimensionalen Indexstruktu-

ren unabhängig von der Reihenfolge der Indexattribute ist, handelt es

sich um eine symmetrische mehrdimensionale Indexstruktur. Ansonsten

spricht man von einer asymmetrischen mehrdimensionalen Indexstruktur.

Es kann zwischen eindimensionalen, mehrdimensionalen und hochdimen-

sionalen Indexstrukturen unterschieden werden. Für Data-Warehouse-

Anwendungen sind insbesondere mehrdimensionale Indexstrukturen für

eine Dimensionalität zwischen 3 und 10 von Interesse.

Typisches Beispiel für eine asymmetrische Indexstruktur ist es, wenn ei-

ne eigentlich eindimensionale Struktur (etwa ein B-Baum) für den mehrdi-

mensionalen Zugriff dadurch genutzt wird, dass mehrere Attributwerte der

verschiedenen Dimensionen konkateniert werden. Der Zugriff ist asymme-

trisch, da die erste verwendete Dimension die Sortierreihenfolge dominiert.

• Tupelverweise: Die Datenwerte, auf die zugegriffen werden soll, können in-

nerhalb der Indexstruktur verfügbar, oder erst nach einer weiteren Indi-

rektion über einen Tupelidentifikator (TID) zugreifbar sein.

• Primärindexe (Zugriff über Primärschlüssel) können derart realisiert wer-

den, dass die Datenwerte innerhalb der Indexstruktur selber gespeichert

sind. Sekundärindexe (unterstütztes Attribut ist nicht Primärschlüssel)

müssen eine Indirektion über einen Tupelidentifikator nutzen.

• Dynamisches Verhalten: Hiermit ist der Aufwand zur Aktualisierung der

Indexstruktur bei Einfügen, Ändern und Löschen gemeint. Ebenfalls sub-

sumiert wird hier das in einigen Datenstrukturen auftretende Problem der

„Entartung“ (bekannt aus binären Suchbäumen, die bei ungünstiger Ein-

fügereihenfolge zur linearen Liste entarten können).

196 7 Indexstrukturen

Diese Eigenschaften gilt es zu beachten, wenn die Eignung einer Indexstruktur

für den Einsatz in DW-Systemen untersucht wird.

Da Datenwürfel inhärent mehrdimensional sind und typische Anfragen

logisch zusammenhängende Bereiche der Dimensionen auswählen

1

, kommt

mehrdimensionalen Bereichsanfragen eine besondere Bedeutung zu. Hier wer-

den in den Dimensionen jeweils Bereiche ausgewählt. Diese Art Anfrage wird

auch als Fensteranfrage bezeichnet.

Abbildung 7.1 verdeutlicht den Einsatz verschiedener zugriffsunterstüt-

zender Datenstrukturen bei Fensteranfragen anhand eines zweidimensionalen

Bereiches. Die skizzieret Anfrage soll alle Produkte eines bestimmten Berei-

ches (lexikographischer Bereich oder eines hierarchischen Clusters, vergleiche

Abschnitt 7.6) für einen zusammenhängenden Zeitraum analysieren. In der Ab-

bildung ist der gesuchte Bereich schwarz hinterlegt, die bei der genutzten Me-

thode gelesenen Tupel grau, und die korrekterweise nicht gelesenen Einträge

wiss.

Zeit (Tage)

Produkt (Artikel)

Zeit (Tage)

Produkt (Artikel)

Zeit (Tage)

Produkt (Artikel)

Zeit (Tage)

Produkt (Artikel)

Multidimensionaler Index

Clusternder PrimärindexFull-Table-Scan

Mehrere Sekundärindexe,

Bitmap-Indexe

Abbildung 7.1: Indexstrukturen bei einer mehrdimensionalen Bereichssuche

• Ein Full-Table-Scan muss alle Werte lesen, nicht nur die gesuchten Werte.

Somit ist die gesamte gespeicherte Tabelle grau hinterlegt.

1

Eine typische Auswahl an Tagen wäre „die Tage der letzten drei Monate“ und nicht etwa „alle

ungeraden Freitage“.

7.1 Klassifikation von Indexstrukturen 197