11

Click here to load reader

Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

Embed Size (px)

Citation preview

Page 1: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

Histogramme in der Datenbankoptimierung

Marian Marx26.06.2008

Page 2: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

Inhaltsverzeichnis

1. Histogramme im Allgemeinen1.1 Definition Histogramm1.2 Beispiel Histogramm2. Histogramme in der Datenbankoptimierung2.1 Motivation2.2 Vorteile2.3 Konstruktionsmöglichkeiten2.4 Histogrammarten2.5 Equi-width vs. Equi-depth (Anwendungsbeispiel)2.6 Erstellung und Pflege3. Histogramme bei Oracle4. Quellen

Seite 2

Page 3: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

1. Histogramme im Allgemeinen

1.1 Definition Histogramm

Das Wort Histogramm leitet sich einmal von griechischen 'histo' (Gewebe, Netz) und zum anderen vom griechischen 'gramm' (Darstellung, Aufzeichnung) ab. Ein Histogramm ist die graphische Darstellung der Häufigkeiten von Messwerten.Dabei werden die bereits nach der Größe sortierten Daten in k Klassen eingeteilt, diese müssen nicht zwingen gleich breit sein. Über jeder dieser k Klassen wird ein Rechteck errichtet, dessen Fläche proportional zur klassenspezifischen Häufigkeit ist.Histogramme werden auch als Balken- oder Säulendiagramme bezeichnet. Sie finden neben DBMS auch besonders großen Einsatz in der Bildverarbeitung.

1.2 Beispiel Histogramm

Im folgenden soll an einem kleinen Beispiel der Aufbau und die resultierenden Ergebnisse eines Histogramms gezeigt werden.Im Beispiel geht es um die Anzahl der PKW pro 1000 Einwohner in 32 europäischen Ländern. Zuerst werden die nach der Größe sortierten Daten (Zahl der PKW pro 1000 Einwohner: 0 – 700) in 5 unterschiedlich Große Klassen eingeteilt. Anhand der Klassenbreite und der Zahl der Länder wird die Säulenhöhe berechnet, die für das eigentlich Histogramm relevant ist.

Seite 3

Page 4: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende Diagramm auswerten. Man erkennt, das in 28% von 32 europäischen Ländern 400 bis 500 PKWs auf 1000 Einwohner kommen.

2. Histogramme in der Datenbankoptimierung

2.1 Motivation

Ziel der Datenbankoptimierung ist es, das Kostenmodell eines Anfrageprozesses zu verbessern. Das Kostenmodell besteht hierbei aus folgenden drei Komponenten:

– Kostenfunktionen zur Abschätzung der Kosten für die Ausführung von Operationen bzw. Anfragen

– Statistiken über die Größe der Relationen (Kardinalität, Tupelgröße) sowie Wertebereich und Werteverteilung der Attribute

– Formeln zur Berechnung der Größe von (Zwischen-)Ergebnissen auf Basis der Statistiken, die wiederum in die Kostenfunktionen eingehen

Seite 4

Page 5: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

Die exakte Berechnung der Kosten ist allerdings sehr schwierig, wenn nicht sogar unmöglich.Ein weiterer Aspekt der bisher falschen Kostenabschätzungen ist die Annahme, das die Attributwerte in einem vorgegebenen Bereich gleich verteilt sind. Wenn man aber beispielsweise einen Supermarkt betrachtet, der sehr viele Produkte unter 10 Euro und nur ein Produkt (z.B. ein Notebook) für 999 Euro, so würde diese Annahme zu einer extrem falschen Kostenabschätzungen führen.Für eine Verbesserung der Attributselektivität sind folgen drei Arten möglich:

– Parameterisierte FunktionenEs werden genaue Angaben von Parametern einer Funktion getroffen, um die Datenverteilung möglichst gut widerzuspiegeln. Allerdings ist dies bei einer irregulären Verteilung der Attributwerte nicht möglich.

– StichprobenWie der Name schon sagt, wird hier die Selektivität anhand von zufälligen Stichproben der gespeicherten Datensätze bestimmt. Je nach Größe des Wertebereichs und Anzahl der Stichproben, kann diese Art der Attributselektivität zu sehr ungenauen Ergebnissen führen.

– HistogrammeBei Histogrammen wird eine Approximation der tatsächlichen Verteilung der Attribut-werte vorgenommen.

2.2 Vorteile

Von den drei eben genannten Varianten kommen insbesondere Histogramme in kommerziellen Datenbankmanagementsystemen zum Einsatz. Dies liegt an folgenden Vorteilen von Histogrammen:Histogramme liefern eine sehr gute Annäherung der Kostenabschätzungen, vor allem für ungleiche Verteilungen der Attributwerte und dies bei geringem Speicherbedarf (meist nur einige wenige 100 Byte pro Attribut). Des weiteren erweitern Histogramme die Heuristiken für Selektivitätsabschätzungen und führen insbesondere für Bereichsanfragen zu einer besseren Zwischenergebnisabschätzung.

Seite 5

Page 6: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

2.3 Konstruktionsmöglichkeiten

Die Konstruktion von Histogrammen in DBMS gleicht der Konstruktion von allgemeinen Histogrammen. Hierbei wird der Wertebereich der Attributwerte in ß>=1 disjunkte Teilmengen partitioniert, die in DBMS auch als Buckets bezeichnet werden.Jedes Bucket enthält eine Gruppen von Elementen, die bezüglich eines Sortierparameters benachbart sind. Für jedes Bucket wird eine Annäherung des Wertes oder der Häufigkeit vorgenommen.Dies wird in der folgenden Abbildung verdeutlicht:

Allerdings gibt es einige Freiheitsgrade, die zu verschiedenen Formen von Histogrammen führen. Im Folgenden werden einige dieser Aufgezählt:

– Anzahl der Elemente aus der Datenmenge pro BucketBei so genannten „End-Biased-Histogrammen“ sind beispielsweise alle Buckets, bis auf eins, einelementig

– Wahl der Sortier- und QuellparameterSortierparameter: Auf welcher Basis Elemente in einem Bucket zusammengefasst werden.Quellparameter: Welcher Parameter im Bucket repräsentiert wird.

– Approximation der WerteDiese können beispielsweise als stetige Werte approximiert werden (continuous value assumption).

– Approximation der HäufigkeitMeist wird hier angenommen, das alle Werte gleich verteilt sind

Seite 6

Page 7: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

2.4 Histogrammarten

Im laufe der Zeit sind durch die oben genannten Freiheitsgrade verschiedene Formen von Histogrammen entstanden. Je nach Problemstellung und Erfolg der genauen Kosten-abschätzungen konnten sich die verschiedenen Histogrammarten mehr oder weniger durchsetzten:

– Equi-sum-HistogrammeBei dieser Histogrammart ist die Summe der Quellwerte der Bucket gleich und entspricht somit dem ß-ten Teil der Summe aller Quellwerte.

– V-optional-HistogrammeHier wird versucht, die gewichtete Varianz der Quellwerte zu minimieren.

– Spline-basierte-HistogrammeBei den Spline-basierten-Histogrammen wird die maximale absolute Differenz zwischen einem Quellwert und dem Mittelwert aller Quellwerte minimiert.

Da die eben genannten drei Formen für einige Problemstellung noch zu ungenau waren, haben sich besonders in den letzten Jahren noch zwei weiter Histogrammarten herauskristallisiert. Diese kommen aufgrund ihrer guten Eigenschaften vermehrt in kommerziellen Datenbankmanagementsystemen zum Einsatz. Ziel, der in diesen beiden Histogrammarten verwendeten Technik, ist es, die Gruppierung von stark verschiedenen Quellwerten in einem Bucket zu verhindern:

– Maxdiff-HistogrammeHier werden die Bucketgrenzen zwischen den ß-1 größten Quellwertstufen gesetzt.

– Compressed-HistogrammeBei den Compressed-Histogrammen werden die k-höchstwertigen Quellwerte, getrennt von den anderen Quellwerten, jeweils in ein eingenes (somit einelementiges) Bucket gesteckt.

Insbesondere bei den letzten zwei Histogrammarten konnte deren gute Güte nachgewiesen werden. Diese ergibt sich durch eine sehr hohe Genauigkeit der Abschätzung der Ergebnisgrößen, speziell bei Bereichsanfragen. Des weiteren ist bei diesen beiden Histogrammarten der Erstellungsaufwand geringer als bei den bisherigen Histogrammarten.

Seite 7

Page 8: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

2.5 Equi-width vs Equi-depth (Anwendungsbeispiel)

Im folgenden soll Anhand eines kleinen Beispiels die Wirkungsweise von Histogrammen verdeutlicht werden. Ebenso wird gezeigt, das nicht jede Histogrammart für eine Problem-stellung geeignet ist.Die beiden hier dargestellten Histogramme gehören zu den Equi-sum-Histogrammen.

Das Equi-width-Histogramm wird konstruiert, indem der Wertebereich in fest vorgegebene Bereiche unterteilt wird. Im obigen Beispiel hat jedes Bucket des Equi-width-Histogramms eine Intervallgröße von 10. Somit ergibt sich beispielsweise für das Intervall [0, 9] eine Buckethöhe/Häufigkeit von 225. Hier sieht man auch gleich den Unterschied zum Equi-depth-Histogramm. Beim Equi-depth-Histogramm sind die Intervalle verschieden groß, wobei das Intervall [0, 1] sogar vier mal benutzt wird, um die Höhe der einzelnen Buckets (im obigen Beispiel hat jedes Bucket die Höhe/Häufigkeit von 25) gleich zu halten.Der Vorteil des Equi-depth-Histogramms im Gegensatz zum Equi-width-Histogramms ist hierbei, das eine bessere Repräsentation von nichtuniformen Verteilungen möglich ist. Dies zeigt auch die im Folgenden erklärte Punktanfrage.

Seite 8

Page 9: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

Beispiel Punktanfrage

Im folgenden soll mit Hilfe der beiden oben erwähnten Histogramme eine Punktanfrage der Form 'Preis = 1' durchgeführt werden.

Bei der Kostenabschätzungen ohne Histogramm und der Annahme das alle Werte gleich verteilt sind, würde dies für den Wertebereich [0, 99] und 250 Datensätzen den Wert von ca. 3 Ergebnistupeln liefern.

Bei der Equi-width-Variante sucht man sich das Bucket, in dem der Wert '1' enthalten ist. Dies ist das erste Bucket, welches das Intervall [0, 9] besitzt. In diesem Intervall gibt es 225 Datensätze. Nun wird angenommen, das jeder Wert des Intervalls gleich verteilt ist. Somit ergibt sich für die Punktanfrage beim Equi-width-Histogramm ein Kostenabschätzungen von ca. 23 Ergebnistupeln. Dies ist schon eine wesentlich bessere Abschätzung, im Gegensatz zu dem Wert ohne Verwendung eines Histogramms. Eine noch bessere Ergebnisabschätzung würde man hier bekommen, wenn man beispielsweise die Breite, und somit die Intervalle, der einzelnen Buckets verkleinert.

Das Equi-depth-Histogramm liefert für die Punktanfrage ein noch etwas besseres Ergebnis. Auch hier wird geschaut, in welchen Buckets der Wert '1' vorkommt. Dies sind insgesammt 4 Buckets mit je dem Intervall [0, 1]. Da jedes Bucket die Höhe 25 hat, sind dies für alle 4 Buckets insgesamt 100 Ergebnistupel. Allerdings muss man auch beim Equi-depth-Histogramm von einer Gleichverteilung der Werte eines Intervalls ausgehen und somit wird der Wert durch 2 geteilt. Somit ergibt sich eine Kostenabschätzungen von 50 Ergebnistupeln, was nochmals eine Verdopplung der Abschätzung des Equi-width-Histogramms bedeutet.

2.6 Erstellung und Pflege

Nur wenn Histogramme die tatsächlich Datenverteilung approximieren, können sinnvolle Abschätzungen gemacht werden. Dafür ist es notwendig, Histogramme nach der Erstellung möglichst bei jeder Änderung der Basisrelation zu erneuern bzw. zu aktuallisieren.Es gibt zwei Arten der Erstellung und Pflege von Histogrammen, welche im folgenden kurz beschrieben werden.

Seite 9

Page 10: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

Statische HistogrammeStatische Histogramme werden einmal explizit aufgebaut und bleiben dann unverändert. Eine Anpassung von statischen Histogrammen ist nur durch eine Neuberechnung möglich. Meist reicht hierzu ein Scan der Basisrelation, was je nach Größe der Relation vertretbare Kosten sind. Bei V-optional-Histogrammen beträgt die Erstellung allerdings quadratische Laufzeit und ist deshalb nicht zu empfehlen.

Dynamische HistogrammeDynamische Histogramme werden, im Gegensatz zu den statischen Histogrammen, bei jeder Datenänderung versucht anzupassen. Für die Pflege von dynamischen Histogrammen gibt es zwei Arten:– Verwaltung von Stichproben der Basisrelation

Bei einer Änderungsoperation auf die Basisrelation wird versucht, diese auf Operationen der Stichproben abzubilden.

– Auswertung der Anfrageergebnissen (query feedback)Anhand der Kostenabschätzung und den tatsächlichen Anfrageergebnissen wird versucht das Histogramm anzupassen, ohne die eigentlich Basisrelation erneut lesen zu müssen.

3. Histogramme bei Oracle

Oracle verwendet zwei Histogrammarten. Zum einen die Equi-depth-Histogramme, welche bei Oracle eher unter dem Namen „höhenbalanciertes Histogramm“ laufen. Und zum anderen die so genannten „Frequency-Histogramme“. Diese sind eine Variante der Compressed-Histogramme, wobei jeder Attributwert sein eigenes Bucket bekommt. Frequency-Histogramme werden von Oracle automatisch angelegt, wenn die Anzahl der Attributwert kleiner ist als die Bucketanzahl.Die Speicherung der Histogramme erfolgt bei Oracle in den sogenannten {USER|DBA|ALL}_HISTOGRAMS-Sichten oder direkt in der zugrunde liegenden Basisrelation. Hierfür werden zwei Spalten benötigt. Zum einen die Spalte ENDPOINT_NUMBER, welche die Bucketnummer enthält. Und zum anderen die Spalte ENDPOINT_VALUE, welche die Buckethöhe speichert.

Seite 10

Page 11: Histogramme in der Datenbankoptimierungkudrass/Lehrmaterial/DB2-VL/DB2-08/13B... · Nachdem die berechneten Säulenhöhen im Histogramm eingetragen wurden, kann man das vorliegende

4. Quellen

Gunter Saake, Andreas Heuer, Kai-Uwe Sattler; Datenbanken - Implementierungstechniken, 2. Auflage, mitp, 2005

OnlinequellenWikipeida – Artikel zu HistogrammenYannis Ioannidis: The History of Histograms, Proc. 23rd VLDB Conference, Berlin 2003

Seite 11