Seminar Data Warehousing SS 05 Thema 11: Optimierung - Materialisierte Sichten Katja Thomas

Seminar Data WarehousingSS 05

Thema 11: Optimierung - Materialisierte Sichten

Katja Thomas

26.04.23 Thema 11: Optimierung – Materialisierte Sichten 2

Gliederung

1. Begriff der Materialisierten Sicht2. Voraussetzungen für die Verwendung materialisierter Sichten

2.1 Gültige Ersetzung2.2 Additivität der Funktionen2.3 Aggregationsgitter

3. Auswahl der zu materialsierenden Daten3.1 Statische Auswahl3.2 Dynamische Auswahl

4. Wartung und Aktualisierung4.1 Prinzip der Effizienten Aktualisierung4.2 Konsistenzbedingungen

5. Zusammenfassung6. Literatur


1. Begriff der Materialisierten Sicht Materialisierte Sicht

relationales, abgespeichertes Ergebnis einer Sicht „vorab berechneter“ Ausschnitt der Faktentabellen

Einige Eigenschaften eines Data Warehouse Systems: beinhaltet große Datenmengen häufige und komplexe Anfragen meist nur lesender Zugriff viele Anfragen beziehen sich auf gleiche Relationen, haben ähnliche

Gestalt, bauen aufeinander auf Wahrscheinlichkeit der Wiederverwendung von Anfragen relativ hoch hohe Effizienz beim Zugriff auf die Daten (Anfragen) erforderlich

Ergebnis des Einsatzes von MS: gewollte Redundanz von Daten um Anfragen effizienter bearbeiten zu

können Wiederverwendbarkeit der Vorberechnungen Reduzierung der Ausführungszeiten der Anfragebearbeitung


1. Begriff der Materialisierten Sicht

Beispiel für die Anwendung von materialisierten SichtenWieviel wurde seit 2004 in unseren Filialen in Thüringen verkauft?

Anfrage Q Materialisierte Sicht M

ΣVerkäufeγJahr, ArtikelNr ΣVerkäufeγArtikelNr

⋈ ArtikelNr ⋈FilialNr

⋈FilialNr Verkauf σBLand=„Thüringen“

σ Jahr≥“2004“ σBLand=„Thüringen“ σ Geschäfte

Verkauf Geschäfte Produkt

⋈ Join Σ Summe γ Gruppierung σ Auswahl


1. Begriff der Materialisierten Sicht

SQL-Definition für DB2 „Automatic Summary Tables“CREATE SUMMARY TABLE NamederMS AS (SELECT…FROM…WHERE…GROUP BY…) DATA INITIALLY DEFERRED REFRESH DEFERRED;REFRESH TABLE NamederMS;

Verkäufe γJahr, ArtikelNr

⋈ ArtikelNr

σJahr≥“2004“ σ

M Produkt


2. Voraussetzungen2.1 Gültige Ersetzung

Ziel: Gewährleistung der Transparenz systemseitig

Verwendung darf keinen Einfluss auf Anfrageformulierung des Anwenders haben

Umformung der eingehenden Anfragen notwendig: query rewrite

Gültige Ersetzung:

Anfrage Q’ ist eine gültige Ersetzung von Anfrage Q unter Verwendung von M (materialisierte Sicht) falls Q und Q’ das gleiche Multimengenergebnis haben

Transformation der eingehenden Anfrage und aller materialisierten Sichten in Normalform

paarweiser Vergleich der Anfragegraphen


2. Voraussetzungen2.1 Gültige Ersetzung

Problematisch bei der Ersetzung: Restriktiondbedingungen weniger restriktive Anfragen stellen: verallgemeinerte Projektion: generalized projection

duplikateliminierende Projektion äquivalent zu Aggregationsoperation über gleiche Attributmenge

SELECT Distinct Preis, Produktgruppe, RegionFROM R

Ist äquivalent zuSELECT Preis, Produktgruppe, RegionFROM RGROUP BY Preis, Produktgruppe, Region

beschränkte Anwendbarkeit

Verwendung von Multiblockanfragen Aufteilung der Anfrage Q in Qa und Qb Ersetzen von Qa

Ausführen des Restrukturierungsalgorithmus zur Verwendung einer Monoblockanfrage

UNION ALL


2. Voraussetzungen2.2 Additivität der Funktionen

Additivität von Aggregationsfunktionen

Voraussetzung für Wiederverwendung von Vorberechnungen Möglichst nur Additive Aggregationsfunktionen verwenden

Aggregationsfunktionen (Median)

Additiv-berechenbare Aggregationsfunktionen

Semi-additiveAggregationsfunktionen

Additive

Aggregationsfunktionen

(SUM)

(MIN)

(AVG)

Quelle: angelehnt an Abb. 7-3 Seite 218 [Leh03]


2. Voraussetzungen2.3 Aggregationsgitter

Aggregationsgitter: stellt Ableitungsbeziehungen in Form von azyklischen

Abhängigkeitsgraphen dar Eine Menge von Gruppierungen bilden ein Aggregationsgitter Grundlage für die Abschätzung des Speicherplatz-Mehraufwandes der

Materialisierung zeigt an, welche Kombinationen von Gruppierungsattributen

direkt/indirekt von anderen Kombinationen ableitbar sind Oberstes Element = Superaggregat

B ableitbar aus (A, B), (B, C) und (A, B, C)

( )

( A ) ( B ) ( C )

( A, B ) ( A, C)

( A, B, C )

( B, C )


2. Voraussetzungen2.3 Aggregationsgitter

Mächtigkeit der Knotenmenge bei n Gruppierungsattributen: |N| = (j=1,.., n) 2 = 2n

exponentielles Wachstum: z.B. 16 Gruppierungsattribute: 65536 Knoten Speicheraufwand bei Materialisierung aller Knoten optimale Teilmenge bestimmen, die man vorberechnet

Dünnbesetztheit des Datenbestandes (sparsity factor): viele Gruppierungskombinationen sind äquivalent gibt an, welcher Anteil an möglichen Ausprägungen von

Attributkombinationen tatsächlich existieren Abschätzung:f(n) = n(1-(1-1/n)k) = n-n(1-1/n)k

Reduktion der Knotenmenge möglich


3. Auswahl 3.1 Statisches Auswahlverfahren

möglichst optimale Menge an zu materialisierenden Sichten auswählen

Grundidee: bestimmte Menge von Sichten durch Administrator oder Algorithmus zu

bestimmten Zeitpunkt auswählen Keine Veränderung bis zur nächsten Aktualisierung des DWs Nur historisches, nicht aktuelles Anfrageverhalten berücksichtigt

Aufwand und Nutzen materialisierter Sichten Verhältnis von zusätzlichem Speicherbedarf (Kosten/Aufwand) und

Verkürzung der Anfragelaufzeiten (Nutzen) Einführung eines linearen Kostenmodells zum Vergleich von

Speicherplatz und Berechnungskostenersparnis Bedingung der Monotonie



Kostenfunktion: cq(n) Kosten der Berechnung von Anfrage q aus dem zu n

korrespondierenden Gitterpunkt im Aggregationsgitter cq(n) = , falls q aus der zu n gehörenden Aggregationskombination

nicht berechenbar

Monotonie einer Kostenfunktion Monoton, wenn für 2 beliebige Knoten ni und nj N aus

Aggregationsgitter gilt:|ni| < |nj| cq(ni) < cq(nj)|n| = Größe des jeweiligen Gitterpunktes

Monotonie steigt mit Größe und Anzahl der zu verarbeitenden Einheiten dieses Gitterpunktes



Kosten einer Materialisierungskonfiguration Aufwand der Beantwortung einer Anfrage q in Bezug auf eine Menge

von Gitterpunkten M = (n1,...,nk) resultiert in den minimalen Kosten in Bezug auf alle Gitterpunkte aus M

cq(M) = min (n M) (cq(n)) Gesamtanfragekosten:

C(Q,M) = (q Q) f(qi) * cq(M)

F(qi) = Häufigkeit der Anfrage qi

Aktualisierungskosten U(M) = (n M) h(n)* u(n)

h(n) = Aktualisierungsrateu(n) = Aktualisierungskosten für einen Gitterpunkt

GesamtkostenCGesamt(Q, M) = C(Q,M) + U(M)



Nutzen einer Materialisierungskonfiguration: Nutzen eines möglicherweise zu materialisierenden

AggregationsgitterknotensM = Menge der bereits materialisierten KnotenQ = Menge der Anfragen

Nutzenabschätzung eines zusätzlich matwerialisierten Knotens n BQ(n, M) = CQ(M) – CQ(M {n})

falls ( CQ((M {n}) < CQ(M)) ) BQ(n, M) = 0

sonst

Nutzen eines zusätzlich materialisierten Gitterknotens ergibt sich aus Differenz der Gesamtkosten von Q und Materialisierungskonfiguration ohne und mit dem neu zu materialisierenden Gitterpunkt

falls Kostenerhöhung – Nutzwert von 0



Algorithmus nach Harinarayan, Rajaraman, Ullman nach Greedy- Prinzip Vorraussetzung: Annahme der Gleichverteilung vorgegebenes

Aggregationsgitter maximaler Speicherplatz S Menge zu materialisierender Aggregationsknoten mit möglichst großem

Nutzen für Gesamtsystem auswählen Geschätzer Speichermehraufwand s benötigt, den Materialisierung

erfordern würde

Ablaufschema (Pseudocode): Eingabe:- Menge aller Aggregationsgitterknoten N

- Erwartete Kardinalität für jeden Knoten ni N: |ni|

- Maximaler Speichermehraufwand S Ausgabe: - Menge der zu materialisierenden Gitterknoten M

(Materialisierungskandidaten)



Begin// Aufnahme des Gitterpunktes, der die feinste Partitionierung //(Detaildaten) darstellt in M// Sicherstellen der Auswertbarkeit aller möglichen Anfragen

M = { nDetaildaten }s = 0 // noch kein zusätzlicher Speichermehraufwand

// Kandidatenauswahl solange S nicht überschrittenWHILE (s < S)

//Berechne Gitterpunkt mit maximalem Nutzen bezüglich M//n ist der Gitterpunkt //mit n (N \ M): Bn(M) = max (ni M) (Bni(M))M = M {n} // Füge n der Materialisierungsmenge

hinzus = s + |n| // Addiere Größe zum Speichermehraufwand

ENDWHILE//Menge der zu materialisierenden Knoten ist ErgebnisRETURN M

End



Beispiel: 3 Tabellen: Monat A1, Region A2, Produktgruppe A3

( )1

( A1 ) 12 ( A2 ) 50 ( A3 ) 100

( A1, A2 ) 600 ( A1, A3 ) 1192

( A1, A2, A3 ) 6000

( A2, A3 ) 3161

1. Auswahl 2. Auswahl

PAPRARPAR

5400 * 4 = 216004808 * 4 = 192322839 * 4 = 113565988 * 2 = 119765950 * 2 = 119005900 * 2 = 11800

----4808 * 2 = 96162839 * 3 = 8517588 * 2 = 1176550 * 2 = 11005900 * 2 = 11800

Quelle: Abb. 7-22 [BaGu04]



Komplexität des Verfahrens: O(n3) Erreicht mindestens 63% des Optimums

Reduktion der Knotenanzahl/des Aggregationsgitters durch Heuristiken (nach Baralis, Paraboschi, Teniente [BaPT97] vor Anwendung des Algorithmus Reduktion von redundanten Gitterknoten aufgrund funktionaler

Abhängigkeiten Iterative Konstruktion eines Teilgitters, bei dem für eine vorgegebene

Menge von Anfragen paarweise alle größten gemeinsamen Vorgänger ermittelt und dem Teilgitter hinugefügt werden

Eliminierung aller Knoten, welche keine Verdichtung um vorgegebenen Faktor versprechen



Nachteile der statischen Auswahl:

Interaktive Komponente von OLAP-Anwendungen wird nicht berücksichtigt Ziel des Anwenders ist bestimmten, uU neuen Zusammenhang zu untersuchen schwer vorhersagbar

Ständige Veränderung des Anfrageverhaltens möglich und Aktualität damit fraglich bzw schwer zu sichern

Häufige Veränderung der Daten führt zu schnellem Veralten der Sichten und damit zu hohem Aktualisierungsaufwand

Verwendung Dynamischer Verfahren


3. Auswahl 3.2 Dynamisches Auswahlverfahren

Grundidee: Anfragedynamik beachten um Nachteile auszugleichen Anfrageergebnisse in reserviertem Pufferbereich materialisieren

Semantisches Caching: Cache:

schneller Pufferspeicher, um häufig benutze Festplattenblöcke in Hauptspeicherseiten für beschleunigten Zugriff vorzuhalten

Inhalt ist der Pufferverwaltung nicht bekannt semantikfrei Verdrängungsstrategie nach Einlagerungszeitpunkt,

Referenzierungshäufigkeit Semantisches Caching:

Semantik und Zusammenhänge der Daten von Bedeutung Daten bestimmen, ob das gepufferte Objekt verwendet werden

kann Speichermedium: Hauptspeicher oder Festplatte, da Schwerpunkt

auf schnellerer Berechnung Verdrängungsentscheidung durch Nutzenabschätzung des Objekts



Verdrängung von materialisierten Sichten: maximale Speichergröße vorgegeben bei Überschreitung: Verdrängungsentscheidung zu treffen Verdrängung erfolgt Seitenweise, dh. falls neues Objekt größer als eine

Seite ist Verdrägung von meheren Objekten notwendig Mögliche Entscheidungsfaktoren:

Zeit des letzten Zugriffs Referenzierungshäufigkeit Größe der materialisierten Sicht Kosten, die Neuberechnung/Aktualisierung der MS verursachen

würde Anzahl Anfragen, die in der Vergangenheit oder prinzipiell damit

beantwortet wurden/ werden könnten Ablauf:

Nutzwert aller Sichten berechnen aus gewichteter Kombination dieser Faktoren

Sortierung nach Nutzenwert Verdrängung der materialisierten Sichten mit geringsten Nutzenwerten


Beispiel:

Auch initiale Füllung des Caches nach statischem Verfahren möglich


Detaildaten

Anfrage A7

Cache

A6

A2

A1A4

A3

A5

Quelle: Abb 7-25 [BaGu04]

?


Ziel: Aktualisierung beschleunigen da tausende Sichten in einem DWS Sperren während Aktualisierung so kurz wie möglich halten

Mögliche Arten der Aktualisierung: Rematerialisierung: Löschung und Neuberechnung einer Sicht

ineffizient, da meist nur geringe Änderung des Datenbestandes Inkrementelle Aktualisierung:

Änderungen auf Basis der veränderten Detaildaten berechnen und inkrementell in Sicht integrieren

Versuch, nach Modifikation (Einfügung, Löschung, Änderung von Tupeln) den neuen Zustand zu berechnen:

V’ = V V = (V - -(V)) + (V).V’ neuer Zustand der SichtV alter ZustandV Änderungen an der Sicht V(V) Menge zu löschender Tupel+ (V) Menge hizuzufügender TupelAdditive Vereinigung bewahrt Duplikate

4. Aktualisierung4.1 Prinzip der Effizienten Aktualisierung



Effizienz von inkrementeller Aktualisierung, in Abhängigkeit von:

Menge der zur Verfügung stehenden Informationen Definition der Sicht + ihre Ausprägungen Möglichkeit des Zugriffs auf (meist teure) Basisrelationen

Vermeidung dieses Zugriffs: Sicht autonom aktualisierbar mit Informationen über Integritätsbedingungen, Verwendung von Hilfssichten, Counting-Algorithmus

Mächtigkeit der Anfragekonstrukte je mächtiger desto komplexer Aktualisierung meiste Algorithmen unterstützen noch keine Aggregatfunktionen

verarbeitbare Modifikationstypen viele Algorithmen können Tupeländerungen nicht direkt abbilden Ersetzen diese durch jeweils eine Lösch- und eine Einfügeoperation Infoverlust führt zu unnötigen Zugriffen auf die Basisrelationen



Parameter einer Aktualisierungsstrategie:1. Granularität

bestimmt Art der Aktualisierung Sichten mit gemeinsamen Basisdaten müssen konsistent gehalten

werden

2. Zeitpunkt der Aktualisierung Sofortige Aktualisierung:

TA, die Basisrelation verändert, aktualisiert auch alle abgeleiteten Daten

Sichten immer aktuell vs Kosten der ModifikationsTA Verzögerte Aktualisierung:

Bei Zugriff auf die Sicht Aktualität gewährleistet vs lesende TA trägt Kosten der

Aktualisierung durch Wartezeit Snapshot-Aktualisierung:

Nach anwendungsspeziefischen Gründen Schnelle TAs (modifikation, lesen) vs Zugriff auf veraltete Daten


4. Aktualisierung4.2 Konsistenzaspekte

Durch Materialisierte Sichten ergeben sich Konsistenzaspekte, die sich auf gesamtes Data Warehouse beziehen

Klassifikation:

Anwenderdefinierte Aktualitätsanforderungen Zeitliche Abstandsmaße:

Zeitspanne, die eine MS maximal älter sein darf als Basisrelationen, auf denen sie basiert

Wertmäßige Abstandsmaße Absolut oder prozentual Abstand in denen Daten (BR und Sicht) abweichen dürfen

Versionsbezogene Abstandsmaße Durch Aktualisierung entsteht neue Version Zahl der Versionen, die nach aktuellem Stand der Sicht

generiert wurden



Anfragekonsistenz errechnetes Ergebnis hätte auch durch Anfrage an die Datenquellen

berechnet werden können muss immer gelten, um Richtigkeit der Analysen zu sichern

Bsp: Anfrage an 2 Sichten mit unterschiedlichen Aktualitätsstand liefern Ergebnisse, die keinem Aktualitätsniveau zugeordnet werden könnten

Ergebnis entspricht zu keinem Zeitpunkt dem Zustand der Quelldaten

Verletzung der Anfragekonsistenz

Sitzungskonsistenz Reihe von aufeinander Aufbauenden Anfragen (Drill-down, Roll-up

Operationen) = Sitzung Gleiches Aktualitätsniveau der Anfragen einer Sitzung

gewährleisten Problem: nur durch Lesesperre auf gesamtes System zu

gewährleisten, da unklar, auf welche Relationen zugegriffern werden wird während einer Sitzung

alle an einer Anfrage beteiligten Relationen müssen dem selben Aktualitätsniveau entsprechen



Aktualisierungsgranulate Welche Objekte können unabhängig voneinander aktualisiert

werden Aktualisierung des gesamten DW

Keine Inkonsistenzen vs keine Nebenläufigkeit Aktualisierung einzelner Sichten

Nebenläufigkeit für Anwender gewährleistet Beachten der Aktualisierung aller mit der Sicht

referenzierten Sichten Gemeinsame Aktualisierung einer Teilmenge der Sichten

Individuelle Aktualisierungsstrategie für jede Relation im DW

Hoher Aktualisierungs und Verwaltungaufwand


5. Zusammenfassung

Redundant abgespeichertes Ergebnis einer Sicht Zur Verkürzung der Ausführungszeiten von Anfragen darf keinen Einfluss auf Anfrageformulierung des Anwenders haben,

Transparenz gewährleisten (Vorausetzungen) Auswahl als Kompromiss zwischen Verkürzung der Anfragelaufzeiten und

zusätzlich benötigtem Speicher Statische / Dynamische Auswahl Wartung der Sichten bei verändertem Ausgangsdatenbestand soll effizient

erfolgen können Konsistenz zwischen den materialisierten Sichten und dem

Basisdatenbestand muss gewährleistet werden


6. Literatur

[BaGu04] Bauer, A; Günzel, H.: Data Warehouse Systeme. Architektur, Entwicklung, Anwendung. Heidelberg: dpunkt.verlag. 2004

[Leh03] Lehner, W.: Datenbanktechnologie für Data-Warehouse-Systeme. Konzepte und Methoden. Heidelberg:dpunkt.verlag.2002

[HRU96] Harinarayn, V.; Rajaraman, A.; Ullman, J.D.: Implementing data cubes efficiently. Proc. ACMSIGMOD. 1996.

[BPT97] Baralis, E.; Paraboschi, S.; Teniente, E.: Materialized view selection in a multi-dimensional datacube. In VLDB, pages 156-165. 1997

[Gup97] Gupta, H.: Selection of views to materialize in a data warehouse. In Proc. Sixth ICDT. 1997.

[YKL97] Yang, J.; Karlapalem, K; Li, Q.: Tackling the challenges of materialized view design in data warehousing environment. In the Proc. of Int'l

Workshop on Research Issues in Data Engineering (RIDE'97).1997.[ZMHW95] Zhuge, Y.; Molina, H. G.; Hammer, J.; Widom, J.: View maintenance in a

warehousing environment. In Proc. ACM SIGMOD '95.1995. [Mak99] Makkonen, J.: Lifespan of Data in a Warehouse. Department of

Computer Science, University of Helsinki. 1999.

Documents

Seminar Data Warehousing SS 05 Thema 11: Optimierung - Materialisierte Sichten Katja Thomas