Star Join & Kostenbasierte Optimierung

Star Join & Kostenbasierte Optimierung
Architektur von Datenbanksystemen II
Star Join
Übungsaufgabe zum 09.06.2015
J OIN-ALGORITHMUS
§ für folgendes Scenario
Dimension
Table D3
§ Große Faktentabelle F mit sehr vielen Einträgen
(Tupel)
§ kleine Dimensionstabellen, die jeweils eine 1:N
Beziehung zur F haben (Meta-Information zum
Fact-Eintrag)
Dimension
Table D1
Fact
Table F
§ SELECT ..
FROM F,D1, D2, D3, .., Dn
WHERE F.x1 = D1.x1 and
F.x2 = D2.x2 and
...
F.xn = Dn.xn and
D1.y1 > yyyy1 and
D2.y2 > yyyy2 and
...
§ Besondere Situation? Besonderer Algorithmus möglich?
Dimension
Table D2
...
Dimension
Table Dn
3
Verbundoperationen in Star-Queries
VORAUSSETZUNGEN
FÜR EINEN
STAR-J OIN
§ Faktentabelle ist immer Bestandteil einer Star-Query
§ Verbund mit Dimensionstabelle reflektiert eine indirekte Selektion über Einschränkungen auf der Dimensionsrelation
(“Erweiterung der Faktentabelle um dimensionale Attribute on the fly...”)
PROBLEME
§
§
§
§
BEI EINER KLASSISCHEN
VERBUNDOPERATION
Faktentabelle ist in der ersten Verbundoperation bereits enthalten
Dimensionstabellen werden sukzessive verknüpft
Größe des Datenstromes startet mit |F| und nimmt erst schrittweise ab
Nur ein einziger ein-dimensionaler Index kann nur in der ersten Verbundoperation verwendet werden
4
Star-Join mit Restrukturierung
STAR-J OIN MIT RESTRUKTURIERUNG
§ Bildung des kartesischen Produktes der Dimensionstabellen
§ Zugriff auf Faktentabelle mit n-fachen Index
§ Nachteil: kartesisches Produkt kann sehr groß werden!
5
Star-Join mit Vorselektion
IDEE
§ Beibehaltung der regulären Verbundstrategie
§ Reduktion der Größe der Faktentabelle in einer Vorstufe (Vorselektion)
§ Benötigt: Jeweils ein Index auf den Fremdschlüsselattributen von F
REALISIERUNG
§ lokale Selektion auf den Dimensionstabellen
§ Semi-Verbund mit der korrespondierenden Indexstruktur
der Faktentabelle (interne Satzadressen bleiben erhalten)
§ Schnittmengenbildung aller Teilergebnisse
§ Resultierende Satzadressen identifizieren exakt
die benötigten Einträge der Faktentabelle
6
Star-Join mit unscharfer Vorselektion
BEWERTUNG
DER
VORSELEKTION
§ Vorteil: Faktentabelle besitzt vor der Verbundoperation bereits endgültige Größe
§ Nachteil: extrem aufwändige Schnittmengenbildung der RID-Listen
EINFÜHRUNG
EINER
UNSCHÄRFE: BLOOM -FILTERTECHNIK
§ Erzeugung einer mit 0 initialisierten Bitliste im Hauptspeicher
§ Aufbauphase (build phase)
- Hashfunktion bestimmt Position der Bitliste für jeden RID-Eintrag: auf 1 setzen
§ Testphase (probing phase)
- Verwurf eines RID, falls korrespondierender Bitlisteneintrag 0 ist
- anderfalls: Aufnahme in das Ergebnis (unscharf!)
§ Beispiel
- Build Phase:
h(RID 14)=3, h(RID 21)=12
- Probing Phase:
h(RID 14)=3 --> korrektes Ergebnis, h(RID 65)=4 --> korrekter Verwurf,
h(RID 31)=25 --> fälschlicherweise Übernahme in Ergebnis
- Güte abhängig von der Größe der Bitliste; Korrektur durch echte Verbundoperationen
7
Star-Join mit unscharfer Vorselektion
8
Kostenbasierte Optimierung
Kostenbasierte Optimierung
KONZEPTIONELL
§ Generiere alle denkbaren Anfrageausführungspläne
§ Bewerte deren Kosten anhand eines Kostenmodells
-
Statistiken
Kalibrierung gemäß verwendeter Rechner
Abhängig vom verfügbaren Speicher
Aufwands-Kostenmodell
• Durchsatz-maximierend
• Antwortzeit-minimierend
Achtung! Nicht zu lange optimieren
§ Führe billigsten Plan aus
10
TPC-H Q3
11
Kostenmodell: Komponenten
KOSTENFUNKTION
§ Zur Abschätzung der Kosten für Ausführung von Operationen bzw. Anfragen
STATISTIKEN
§ Über Größe der Relationen (Kardinalität, Tupelgröße), Wertebereiche und –verteilungen
FORMELN
§ Zur Berechnung der Größen von (Zwischen-)Ergebnissen auf der Basis der Statistiken
12
Kostenfunktion
KOSTENARTEN
§ I/O-Kosten: verursacht durch das Lesen und Schreiben von Blöcken vom bzw. auf den Externspeicher
§ CPU-Kosten: für interne Berechnungen, Vergleiche etc.
§ Kommunikationskosten: im Fall verteilter Datenbanksysteme
ÜBLICHE KOSTENFUNKTION
§ 𝑐𝑜𝑠𝑡 = 𝑐𝑜𝑠𝑡𝐼𝑂 + 𝑊 ∗ 𝑐𝑜𝑠𝑡𝐶𝑃𝑈
§ Faktor W zur Kalibrierung bzgl. Hardware
13
Statistiken
ZU JEDER BASISRELATION
§ Anzahl der Tupel
§ Tupelgröße
ZU (JEDEM ) ATTRIBUT
PROBLEM
§ Erstellung und Update der Statistiken
§ Deshalb meist nur explizit/manuell zu initiieren
§ runstats()
§ Min/Max
§ Werteverteilung (Histogramm)
§ Anzahl der distinct Werte
ZUM SYSTEM
§
§
§
§
Speichergröße
Bandbreite
I/O-Kosten
CPU Zeiten
14
Kosten von Operationen (Formeln)
WESENTLICHES KOSTENMERKMAL
§ Anzahl der Tupel im Input
§ Insbesondere: Passt die Relation in den Hauptspeicher?
§ Selektion, Projektion, Sortierung, Join
OUTPUT IST INPUT
DES
NÄCHSTEN OPERATORS
DESHALB
§ Ein Kostenmodell schätzt u.a. für jede Operation die Anzahl der Ausgabetupel
§ „Selektivität“ in Bezug auf Inputgröße
§ #Ausgabetupel = #Eingabetupel * Selektivität
§ auch „Selektivitätsfaktor“ genannt
15
Kostenschätzung - Selektion
EIGENSCHAFTEN
§ Anzahl der Tupel sinkt
§ Tupelgröße bleibt
16

Download Report