Universität Karlsruhe (TH) © 2009 Univ,Karlsruhe, IPD, Prof. LockemannDBI 9 Kapitel 9 Relationale Operatoren

UniversitätKarlsruhe (TH)

© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 9

Kapitel 9

Relationale Operatoren

2


Gegenstand des Kapitels

Mengenorientiertes Datenmodell

Datenmodell

Dateien

Dateiverwaltung

Geräteschnittstelle

Anfragebearbeitung

Satzorientiertes Datenmodell

Speicherstruktur

Schneller Transport zwischen Haupt- und Hintergrundspeicher

Hauptspeicherseiten u. Segmente

Segment- u. Pufferverwaltung Bevorratung von Daten im Hauptspeicher (rechtzeitige Bereitstellung vor Benutzung)

Transparenter homogener Speicher Datentypen:

Seite = feste Anzahl von BytesSegment = var. Anzahl von Seiten

Operatoren:Anforderung/Freigabe von SeitenSegmente anlegen/öffnen/schließen

Datentypen:Block = feste Anzahl von BytesDatei = variable Anzahl v. Blöcken

Operatoren: Dateien anlegen/öffnen/schließen Lesen/Schreiben von Blöcken

Geräte-E/A

Satz- u. Satzmengenverwaltung

Satzzugriffsstrukturen

Zugriffsschicht

Vorschau auf zukünftig benötigte Daten

Vermeiden nicht aktuell benötigter Daten

Datentypen:Sätze und Satzmengen

Operatoren:Operatoren auf Sätzen

Datentypen:Satzmengen

Operatoren:Operatoren auf Mengen

Datentypen:phys. Zugriffsstrukturen auf Sätze

Operatoren:seq. Durchlauf, gezielte Suche

Optimaler Einsatz der logischen Ressourcen

Performanz

3


Kapitel 9.1Kapitel 9.1

KostenmodellKostenmodell

4


Ausgangspunkt Verarbeitet werden Materialisierungen, nicht externe

Relationen. Materialisierungen haben den Charakter von Relationen. Daher lassen sich auf sie die relationalen Operatoren

anwenden.

Aufgabe Zur Implementierung jeden relationalen Operators existieren

mehrere Algorithmen. Bestimmung der jeweiligen Kostenfunktion.

Bei der Bearbeitung einer Anfrage muss ein kostengünstiger Algorithmus ausgewählt werden: Berücksichtigung von Einflussfaktoren bei der Auswahl.

Aufgabe

5


Elemente der Kostenfunktion

Kostenfunktionalgebraischer Ausdruck

Indexinformationen Ballungsinformationen

Kardinalitäten

1. Zugriffskosten auf Hintergrundspeicher für Basisrelationen aber auch für große Zwischenergebnisse

2. Speicherkosten der Zwischenergebnisse (Ergebniskardinalität!)3. CPU-Kosten für die Berechnung (wird i.Allg. vernachlässigt)4. Kommunikationskosten

Spielen erst bei der verteilten Anfrageoptimierung eine Rolle

Ausführungskosten

Bestimmen die Anzahl der Zugriffe auf den Hintergrundspeicher

6


Einflussfaktoren

Kostenmodellalgebraischer Ausdruck

Indexinformationen Ballungsinformationen

Kardinalitäten

Ausführungskosten

vorhanden / nicht vorhanden

Liefert einen Multiplikator: Größe der einzelnen Basis- oder Zwischenrelation. Die Größe jeder Zwischenrelation muss daher zuvor abgeschätzt werden. Charakterisierung einer Operation dann durch ihre Selektivität

Selektivität =erwartete Anzahl der Ergebnistupel

Zahl der Basistupel d. Operation

7


Selektivitätsabschätzung

Da nahezu alle relationalen Operatoren auf einem Vergleich von Attributwerten basieren, beruht die Abschätzung auf der Kenntnis der Attributwertverteilungen.

Im Allgemeinen muss Aufwand getrieben werden, um die Verteilung der Attributwerte zu bestimmen.

Verfahren: Parametrische Verfahren

Parameterfreie (Histogramm-) Verfahren

Selektivität

ggf. Stichprobenverfahren

8


Approximieren die Verteilung durch mathematische Wahrscheinlichkeitsverteilung, z.B. Normalverteilung Knappe Beschreibung durch wenige Parameter Nur diese müssen ermittelt werden, z.B. Minimum und

Maximum bei Gleichverteilung, Erwartungswert und Varianz bei Normalverteilung

Erweiterung auf mehrere Dimensionen zur Erfassung korrelierter Attribute, wie beispielsweise „Position“ und „Einkommen“ bei Angestellten einer Firma z.B. multivariate Normalverteilung, bestimmt durch

Erwartungswertvektor und Kovarianzmatrix

Nachteile: Art der Verteilung darf sich nicht im Laufe der Zeit ändern mangelnde Universalität

Parametrische Verfahren (1)

9


Parametrische Verfahren (2)

10


Approximation durch Stufenfunktion.

Äquidistante Unterteilung, für jedes Intervall wird die Anzahl der Attributwerte bestimmt, die hineinfallen. Innerhalb der Intervalle wird Gleichverteilung angenommen.

Die Erweiterung des Histogramm-Verfahrens auf mehrere Dimensionen zur Erfassung von Korrelationen ist leicht möglich.

Histogrammverfahren (1)

11


Fehler hängt nicht nur von der Auflösung ab, sondern auch von der Verteilung selbst, die ja unbekannt ist.

Abhilfe durch nicht äquidistante Unterteilung des Wertebereichs: Gleiche Höhenintervalle statt gleicher Breite.


relative schlechte Abschätzung (große

Abweichung Verteilung zu Histogramm).

12


Vorzüge generell: Universalität: Keine Voraussetzungen bzgl.

Wahrscheinlichkeitsverteilung Verbreitetes Verfahren als Voraussetzung für die

Anfrageoptimierung Nachteile generell:

Höherer Speicheraufwand Schätzung der Selektivität aufwendiger, da auf mehr Daten

zugegriffen werden muss Erstellung bei gleichen Höhenintervallen ist teurer, da die

Attributwerte sortiert werden müssen Neuerstellung/Neuberechnung des Histogramms in

periodischen Zeitabständen erforderlich Insbesondere Fortschreiben unter Beibehalten der gleichen

Höhenintervalle schwer möglich


13


Aufwandsverringerung: Repräsentative Stichprobe der Datenbasis zur Parameterschätzung bei parametrischen Verfahren

Histogrammberechnung ohne Durchsuchen der gesamten Datenbasis, wichtig besonders bei nicht-äquidistanter Unterteilung.

Stichprobenumfang hängt nur von der gewünschten Genauigkeit ab, nicht von der Größe der Datenbasis.

Stichprobenverfahren (Sampling)

14


Verwaltung der Informationen für die Parameter Kardinalität der Relationen

Größe der Tupel

Ballungseigenschaften der Daten

Indexstrukturen zur Unterstützung des Zugriffs

Verteilungen / Histogramme

Periodisches Fortschreiben z.B. in Zeiten niedriger Systemlast

oder parallel zu den Anwendungen

Datenwörterbuch

15



Unäre OperatorenUnäre Operatoren

16


Kostenparameter

Parameter Bedeutung T(R) Kardinalität (Tupelzahl) der Relation R B(R) Anzahl der Seiten, auf denen Tupel aus R liegen Bf(R) blocking factor (Anzahl Tupel pro Seite für R) X(Idx) Höhe des Indexes (B-Baum) Idx B(Idx) Anzahl der Stellvertreter-Knoten des Indexes

(nur bei B*-Baum) V(R,Attr) Anzahl verschiedener Werte für die Attributfolge

Attr der Relation R S(R,Attr) Selektivität einer Attributfolge

Parameter für die Kostenfunktionen

17


Selektion: Exact Match (1)

S1 Lineare Suche (Ballung nicht in Sortierreihenfolge)

Kosten (Zahl der Hintergrundspeicherzugriffe):

a) Selektion auf Nicht-Schlüssel-Attribut

CS1a = B(R)

b) Selektion auf Schlüssel-Attribut

CS1b = B(R)/2

Relation Employee: T(E) = 10.000, B(E) = 2.000, Bf(E) = 5SSN=007(Employee)

CS1b = B(E) / 2 = 1000DNO=5(Employee)

CS1a = B(E) = 2000

Employee (Fname, Lname, SSN, BDate, Address, Sex, Salary, SuperSSN, DNO)

18



S2 Binäre Suche (Ballung gemäß Sortierung nach dem Suchkriterium)


a) Selektion auf Nicht-Schlüssel-Attribut:

CS2a = log2 B(R) + (T(R)S(R,Attr))/ Bf(R) 1

b) Selektion auf Schlüssel-Attribut):

CS2b = log2 B(R)

19



S3 Nutzung eines Primärindexes, um ein einziges Tupel zu lesen


a) B*-Baum: CS3a = X(Idx) + 2

b) B+-Baum (Clusterindex): CS3b = X(Idx) + 1

c) Hash-Index: CS3c 1

Relation Employee: T(E) = 10.000,SSN=007(Employee)

Primärindex auf SSN mit X(Idx) = 4: CS3a = X(Idx) + 2 = 6Clusterindex auf SSN mit X(Idx) = 4: CS3b = X(Idx) + 1 = 5


20



S4 Nutzung eines Sekundärindexes, um Tupel mit gleichem Wert zu lesen


a) B*-Baum: CS4a = X(Idx) + 1 + T(R)S(R,Attr)

b) B+-Baum(Clusterindex): CS4b = X(Idx) + ((T(R)S(R,Attr)) / Bf(R))

Relation Employee: T(E) = 10.000, B(E) = 2.000, Bf(E) = 5Sekundärindex auf DNO mit X(Idx) = 2,

S(E,DNO) = 1/125 (125 verschiedene DNO-Werte) DNO=5(Employee)

CS4a = X(Idx) +1 + T(E)S(E,DNO) = 3 + 80 = 83CS4b = X(Idx) +(T(E)S(E,DNO))/Bf(E) = 2 + 16 = 18


21


Selektion: Range Query (1)

S5 Lineare Suche (Ballung nicht in Sortierreihenfolge)


a) Range Query: CS5a = B(R)

Relation Employee: T(E) = 10.000, B(E) = 2.000, Bf(E) = 5DNO >5(Employee)

CS5a = B(E) = 2000


22


Selektion: Range Query (2)

S6 Nutzung eines Indexes (Vergleichsprädikat <, >, , )


a) Sekundärindex (also keine Ballung von sortierten Tupeln): Annahme: die Hälfte der Tupel erfüllt das Selektionsprädikat:

CS6a = X(Idx) + B(Idx)/2 + T(R)/2

b) Clusterindex (Ballung von sortierten Tupeln): Sehr grobe Abschätzung mit Annahme wie bei a):

CS6b = X(Idx) + B(R)/2

Relation Employee: T(E) = 10.000, B(E) = 2.000, Bf(E) = 5Sekundärindex auf DNO mit X(Idx) = 2, B(Idx) = 4

DNO>5(Employee)CS6a = X(Idx) + B(Idx)/2 + T(E)/2 = 5004


23


Selektion: Konjunktive Suchprädikate (1)

S7

a) Vorauswahl der Tupel gemäß eines der Glieder der Konjunktion, die durch S2, S3, S4, S6 unterstützt wird, dann Zugriff auf die vorausgewählten Tupel und Test des verbleibenden Teils des Selektionsprädikats.

b) Nutzung einer mehrdimensionalen Indexstruktur.

c) Schnittmengenbildung von ID-Listen aus mehreren Indexen gemäß S3, S4 oder S6, je nach anwendbarem Index.

d) Lineare Suche.

24


Selektion: Konjunktive Suchprädikate (2)

DNO=5 and Salary>30000 and Sex=F Employee

Relation Employee: T(E) = 10.000, B(E) = 2.000, Bf(E) = 5Clusterindex auf Salary mit X(Idx) = 3Sekundärindex auf DNO mit X(Idx) = 2, S(E,DNO) = 1 / 125 (125 verschiedene DNO-Werte)Sekundärindex auf Sex mit X(Idx) = 1,S(E,Sex) = 1 / 2 (2 verschiedene Sex-Werte)

CS7d = B(E) = 2.000S7a: Vorauswahl nach DNO=5:CS4a = X(Idx) +1 + T(E)S(E,DNO) = 3 + 80 = 83, restliche Bedingungen durch Inspektion der ausgewählten TupelS7a: Vorauswahl nach Salary>30.000:CS6b = X(Idx) + B(E)/2 = 3 + 2000 / 2 = 1003, restliche Bedingungen durch Inspektion der ausgewählten TupelS7a: Vorauswahl nach Sex=F:

CS4a = X(Idx) +1 + T(E)S(E,DNO) = 2 + 5000 = 5002, restl. Bedingungen durch Inspektion d. ausgewählten Tupel

Kann weit besser sein Verteilung?

25


Disjunktive Selektionsprädikate können kaum unterstützt werden

Beispiel: DNO = 5 or Salary > 30000 or Sex = F Employee

Selbst wenn es Indexe auf Salary und DNO gibt, muss man dennoch alle Tupel der Relation (physisch) lesen, um „Sex = F“ auszuwerten.

Selektion: Disjunktive Suchprädikate

26


sel(p,R) = p(R) / T(R)

Empfohlene Schätzung bei Annahme Gleichverteilung: A Schlüssel von R: Unabhängig von Verteilung

sel(A=c,R) = 1/T(R) V(R,A) verschiedene Werte für A:

sel(A=c,R) = 1/V(R,A) Vergleich arithmetisch

sel(A<c,R) = (c-Amin)/(Amax-Amin)

sel(A>c,R) = (Amax-c)/(Amax-Amin) Vergleich nicht-arithmetisch

sel(A<c,R) = sel(A>c,R) = 1/3

Selektion: Selektivität

Schreibaufwand: (T(R) sel(p,R))/Bf(R) .

27


Fall 1: A(R) mit R sortiert nach A.

Alle r A(R) werden in das Ergebnis aufgenommen, für die gilt r previous(r). Aufwand: CP1a = B(R)

Fall 2: A(R) mit Index auf A.

Nutze Sortierung durch Index. Aufwand: CP2 = X(Idx) + B(Idx) + T(R)

Fall 3: A(R) mit R nicht sortiert nach A.

A(R) wird zunächst nach A sortiert, dann wie nach Fall 1.

Aufwand: CP3 = B(R) + B(R)logm-1(B(R)/m)

Projektion mit Duplikateliminierung (1)

Schreibaufwand: (höchstens) B(R).

28



Projektion mit Duplikateliminierung (2)

RA(R) schon gesehen?

m-1 Puffer Ausgabe-Puffer

nein

Wichtig für die Performanz: A(R) sollte in den Puffer passen. Schnelle Zugriffsstruktur, z.B. Hashing.

Nächstes Tupel lesen, auf A projizieren:

Nachsehen ob A(R) schon im Puffer

A(R) in Puffer und Ausgabe schreiben

29


Empfohlene Schätzung:

Ohne Duplikateliminierung

sel(A,R) = A(R) / T(R)

sel(A,R) = T(R)/T(R) = 1

Mit Duplikateliminierung:


sel(A,R) = min (T(R), V(R,Ai) mit A=(A1, A2, ..., An)

Projektion: Selektivität

n

i 1

30


Gruppierung (1)

Schreibaufwand: B(R).

Schreibaufwand und Hauptspeicherbedarf geringer bei Aggregierung.

Fall 1: A(R) mit R sortiert nach A.

Mit jedem Wechsel von A(R) wird eine Gruppe abgeschlossen und ein neue begonnen. Das Ergebnis, gegebenenfalls zuerst aggregiert, wird

geschrieben. Aufwand: CG1 = B(R)

Fall 2: A(R) mit Index auf A.

Nutze Sortierung durch Index, ansonsten wie oben. Aufwand: CG2 = X(Idx) + B(Idx) + T(R)

31



A(R) wird zunächst nach A sortiert, dann wie nach Fall 1.

Aufwand: CG3 = B(R) + B(R)logm-1(B(R)/m)


Partitionierung: Anwendung einer Hashfunktion auf A.

Aufwand hängt von Güte der Partitionierung ab sowie von der Notwendigkeit, die Partitionen auf den Hintergrundspeicher zu schreiben.

Gruppierung (2)

Schreibaufwand: B(R).

Schreibaufwand und Hauptspeicherbedarf geringer bei Aggregierung.

32


Empfohlene Schätzung:


sel(A,R) = min (T(R), V(R,Ai) mit A=(A1, A2, ..., An)

Gruppierung (3)

n

i 1

33



Gleich-Verbindung (Equi-Join)Gleich-Verbindung (Equi-Join)

34


Kostenparameter

Parameter Bedeutung T(R) Kardinalität (Tupelzahl) der Relation R B(R) Anzahl der Seiten, auf denen Tupel aus R liegen Bf(R) blocking factor (Anzahl Tupel pro Seite für R) X(Idx) Höhe des Indexes (B-Baum) Idx B(Idx) Anzahl der Stellvertreter-Knoten des Indexes

(nur bei B*-Baum) V(R,Attr) Anzahl verschiedener Werte für die Attributfolge

Attr der Relation R S(R,Attr) Selektivität einer Attributfolge

Equi-Join: R ⋈A=B S mit Spezialfall natural join Parameter für die Kostenfunktionen

35


Kapitel 9.3.1Kapitel 9.3.1

Nested-Loops-MethodenNested-Loops-Methoden

36


foreach r R doforeach s S do

if s.B = r.A then Res := Res (r s)

Grundmuster

37


Block-Nested-Loops-Verbindung (1)

Geg.: Puffergröße m in Blöcken zum Lesen der Relationen sowie B(R) und B(S)

Dann Nutze m-1 Pufferblöcke für die äußere Schleife (z.B. zum Lesen von R) Nutze 1 Pufferblock für die innere Schleife (z.B. zum Lesen von S)

R S

1

m-1

38



Geg.: Puffergröße m in Blöcken zum Lesen der Relationen sowie B(R) und B(S)

Dann Nutze m-1 Pufferblöcke für die äußere Schleife (z.B. zum Lesen von R) Nutze 1 Pufferblock für die innere Schleife (z.B. zum Lesen von S)

Algorithmus, o.B.d.A. hier: B(R) ist Vielfaches von m-1

for (i = 0; i < B(R)/(m-1), i++) { Lese Blöcke i(m-1) bis (i+1)(m-1)-1 von R for (int j = 0, j < B(S), j++) { Lese Block j von S; Führe nach Grundmuster Join

bzgl. zuletzt gelesener Blöcke von R und bzgl. zuletzt gelesenem Block von S

im Hauptspeicher (also auf Puffer) durch }}

39


Kostenfunktion (1)

Es werden in B(R)/(m-1) Abschnitten insgesamt B(R) Seiten in der äußeren Schleife eingelesen

In jedem Abschnitt werden B(S) Seiten neu eingelesen

Kosten:

CBNL = B(R) + (B(R)/(m-1) B(S)) +

(T(R) T(S) sel(R⋈S))/Bf(R⋈S)

Bf(R⋈S): Blockungsfaktor der Join-Tupel

sel(R⋈S): Selektivität des Ergebnisses

Lesen der Relationen in den PufferLesen der Relationen in den Puffer Schreiben des Join-Resultats

auf die FestplatteSchreiben des Join-Resultats auf die Festplatte

40



Für den Fall zweier Relationen A und B mit B(A) >> B(B) setze R := B (also die von der Seitenzahl her kleinere Relation ist die äußere Relation). Bessere Chance dass B(R)/(m-1) klein bleibt (Extremfall

B(R) = (m-1) ).

41


Anfrage: Employee ⋈DNO = Dnumber DepartmentAnnahmen: Employee wie gehabt (T(E) = 10000; B(E) = 2000) Department (T(D) = 125, B(D) = 13) Join-Selektivität ist sel(E⋈D) 1/T(D) (= 1/125)

weil Dnumber Schlüssel von Department ist Bf(E⋈D) sei 4

Kostenfunktion (2)

Employee als äußere Schleife

CBNL = B(E) + B(D) B(E)/(m-1) + (T(E) T(D) sel(E⋈D)) / Bf(E⋈D)m=2:CBNL = 2.000 + 13 2.000 + (10.000 125 (1/125))/4) = 30.500m=6:CBNL = 2.000 + 13 400 + (10.000 125 (1/125))/4) = 9.700


Department (Dname, Dnumber, MgrSSN, MgrStartDate)

42


Anfrage: Employee ⋈DNO = Dnumber DepartmentAnnahmen: Employee wie gehabt (T(E) = 10000; B(E) = 2000) Department (T(D) = 125, B(D) = 13) Join-Selektivität ist sel(E⋈D) 1/T(D) (= 1/125)


Kostenfunktion (3)



m=6:Employee als äußere SchleifeCBNL = B(E) + B(D) B(E)/(m-1) + (T(E) T(D) sel(E⋈D)) / Bf(E⋈D)CBNL = 2.000 + 13 400 + (10.000 125 (1/125))/4) = 9.700Department als äußere SchleifeCBNL = B(D) + B(E) B(D)/(m-1) + (T(E) T(D) sel(E⋈D)) / Bf(E⋈D)CBNL = 13 + 2.000 3 + (10.000 125 (1/125))/4) = 8.513

43



Misch-MethodenMisch-Methoden

44


Entfällt falls R und S bereits sortiert

Schritt 1: Sortierungen1. R muss nach A und2. S nach B sortiert werden

Schritt 2: Mischen (Merge-Join) Falls A oder B Schlüsselattribut ist, wird jedes Tupel in R und

S nur genau einmal gelesen

Sort-Merge-Join

45


Merge-Join

Falls für alle c A=c(R) oder A=c(S) klein, müssen R und S nur einmal eingelesen werden:

CMJ = B(R) + B(S) + (T(R) T(S) sel(R⋈S)) / Bf(R⋈S)

Gilt insbesondere, wenn Join-Attribut in einer der beiden Relationen eindeutiger Schlüssel.

Sort-Merge-Join

CSMJ: Für jede zu sortierende Relation kommt nach Kap.8 Sortieraufwand hinzu (hier für R):

2B(R) + 2B(R)logm-1(B(R)/m) = 2B(R)(1+logm-1(B(R)/m))

(m: Mischgrad)

Kostenfunktionen (1)

46


Anfrage: Employee ⋈DNO = Dnumber Department Employee wie gehabt (T(E) = 10000; B(E) = 2000) Department (T(D) = 125, B(D) = 13) Join-Selektivität ist sel(E⋈D) 1/T(D) (= 1/125)


Kostenfunktion (2)



m=6:Employee und Department bereits sortiertCMJ = B(E) + B(D) + (T(E) T(D) sel(E⋈D)) / Bf(E⋈D)CMJ = 2000 + 13 + (10.000 125 (1/125))/4) = 4.513Employee und Department noch zu sortieren

CSMJ = CMJ + 2B(E)(1+log5(B(E)/6)) + 2B(D)(1+log5(B(D)/6)) CSMJ 25.000

47



Index-MethodenIndex-Methoden

48


foreach r R doforeach s S[B=r.A] do

Res := Res (r s) beim Durchlauf von R werden jeweils in S die zu R.A

korrespondierenden Tupel gelesen dazu ist ein Index auf S.B erforderlich

Grundmuster

49



Sekundärindex auf S.B:

CIJa = B(R) + T(R) (X(IdxB) + 1 + T(S)S(S,B)) + (T(R) T(S) sel(R⋈S)) / Bf(R⋈S)

Clusterindex auf S.B:

CIJb = B(R) + T(R) (X(IdxB) + (T(S)S(S,B))/Bf(S) ) + (T(R) T(S) sel(R⋈S)) / Bf(R⋈S)

Primärindex auf S.B (B ist Schlüssel):

CIJc = B(R) + T(R) (X(IdxB) + 2) + (T(R) T(S) sel(R⋈S)) / Bf(R⋈S)

50


Anfrage: Employee ⋈DNO = Dnumber Department Employee (T(E) = 10000; B(E) = 2000)

Sekundärindex auf DNO mit X(Idx) = 2 S(E,DNO) = 1 / 125 (125 verschiedene DNO-Werte)

Department (T(D) = 125, B(D) = 13) Primärindex auf Dnumber in Department mit X(Idx) = 1

Join-Selektivität ist sel(E⋈D) 1/T(D) (= 1/125) Bf(E⋈D) = 4


Employee als äußere SchleifeCIJc = B(E) + T(E)(X(IdxDnum) + 2) = 2000 + 10.0003 = 30.200 Department als äußere Schleife

CIJa = B(D) + T(D) (X(IdxDNO)+1+T(E)S(E,DNO)) = 13+12583 = 10.388Schreibaufwand(T(E) T(D) sel(E⋈D)) / Bf(E⋈D) = (10.000 125 (1/125))/4) = 2.500



51



Hash-MethodenHash-Methoden

52


Probe-Phase

Build-Phase

Partitioniere Relation R in R1, R2, ..., Rp gemäß Hashfunktion h so dass für alle Tupel r Ri h(r.A) Hi.

Führe Scan auf Relation S aus, wende auf jedes Tupel s S die Hashfunktion h an. Fällt h(s.B) in den gewählten Bereich Hi, suche dort einen r-Partner

Grundmuster:repeat

beginwhile memory not exhausted doinsert next(R) into partition[h(next(R).A)];

foreach s S doforeach r partition[h(s.B)] do

if r.A = s.B Res := Res (r s)end

until R exhausted

Simple Hash Join (1)

53


Problem: R passt nicht in den Hauptspeicher. Schritt 1 (Build): Führe Scan auf kleinere Relation R aus, wende

auf jedes Tupel r R die Hashfunktion h an. Fällt h(r.A) in den gewählten Bereich Hi (anfangs i=1), trage r in den Arbeitsbereich ein, andernfalls in einen Puffer für R. Falls Puffer überläuft, schreibe seinen Inhalt in eine Datei für „übergangene“ r-Tupel.

Schritt 2 (Probe): Führe Scan auf Relation S aus, wende auf jedes Tupel s S die Hashfunktion h an. Fällt h(s.B) in den gewählten Bereich Hi, suche im zugehörigen Arbeitsbereich einen r-Partner. Falls erfolgreich, bilde Ergebnistupel, andernfalls speichere s in Puffer für S. Falls Puffer überläuft, schreibe seinen Inhalt in eine Datei für „übergangene“ s-Tupel.

Schritt 3: Wiederhole die beiden Schritte mit den übergangenen Tupeln so lange, bis R erschöpft ist.


Voraussetzung: Jede Partition passt in den Hauptspeicher.Empfehlung: Wähle h so dass alle Partitionen etwa gleich groß sind.

54


1.Iteration:


Amin Amax

R

H1 RRest

SRest

Bmin BmaxS

55


Abwandlung des Simple Hash Join, indem statt der Dateien der übergangenen Tupel die Partitionen für R und S komplettiert werden.

Fange so an, als wenn der Build-Input R vollständig in den Hauptspeicher passen würde.

Sollte sich dies als zu optimistisch herausstellen, verdränge eine Partition nach der anderen aus dem Hauptspeicher.

Mindestens eine Partition wird aber im Hauptspeicher verbleiben.

Danach beginnt die Probe-Phase mit der Relation S. Jedes Tupel aus S, dessen potentielle Join-Partner im

Hauptspeicher sind, wird sogleich verarbeitet, andernfalls wird es in die entsprechenden Partitionen eingeordnet.

Danach müssen nur noch die verbliebenen Partitionen zusammengeführt werden.

Hybrid Hash Join (1)

Besonders interessant, wenn der Build-Input knapp größer als der Hauptspeicher ist.

56



S R

P1

P2

P3

Hashtabelle

Zwischenstand Build(R)

57



S R

P3

P1

P2

Hashtabelle

Verdrängen einer Partitition

58



S R

P2

P3

P1

Hashtabelle

Verdrängen einer Partitition

59



S

P2

P3

Partitionh(S.B) P2

P3

Hashtabelle

probe

Wenn s zur ersten Partition

gehört

Zwischenstand während Partitionierung von S

60


Grundgedanke:

Entwicklung aus dem Hybrid Hash Join heraus, indem auch die Verzahnung bei den im Hauptspeicher gehaltenen Partitionen zugunsten eines expliziten Aufbaus aller Partitionierungen nach hinten verschoben wird.

Strikte Trennung von Partitionierung und Ergebnisberechnung.

Grace Hash Join (1)

61


Grace Hash Join (2)

Partitionierung 1: Partitioniere kleinere Relation, evtl. wiederholt, gemäß Hashfunktionen hi bis jede Partition in den Hauptspeicher passt.

62


Grace Hash Join (3)

Partitionierung 2: Partitioniere größere Relation, evtl. wiederholt, gemäß der selben Hashfunktionen hi. Partitionen müssen nicht in den Hauptspeicher passen.

63


Grace Hash Join (4)

Hole der Reihe nach jede Build-Partition in den Hauptspeicher, organisiere sie als Hashtabelle, vergleiche entsprechende Probe-Partition mit Hashtabelle.

64


Grace Hash Join (5)

Lies RSchreibe RLies S Schreibe S Lies R,S

Schwierige analytische Kostenabschätzung („Güte“ der Hashfunktion geht ein). Grob:

CGHJ = 3 (B(R) + B(S)) + ((jsT(R)T(S))/BfRS )

65


Grace Hash Join (6)

Send

S

Send

R

receive

P1

P2

P3

Partitionh(S.A)

P1

P2

P3

Partitionh(R.A)

receive

66


Grace Hash Join (7)

P1

P2

P3

Partitionh(S.A)

P1

P2

P3

build

Hashtabelle

probe

Lade Blöcke von P1

67


Grace Hash Join (8)

Beispiel:

68


2 Varianten:

1. TIDs werden in die Partitionen gehasht passt leichter in den Hauptspeicher

2. Vollständige Tupel werden in die Partitionen gehasht

Anmerkung: Grace Hash Join (und Hybrid Hash Join) lassen sich gut

parallelisieren.

Grace Hash Join (9)

69



AbschätzungenAbschätzungen

70


Aufwandsvergleich

Elementvergleich Elementvergleich, der zu Join-Ergebnis führt

Nested-Loop Merge Hash

71


js = (R ⋈p S) / (R S) = (R ⋈p S) / (R S) Sonderfälle:

p = true: js = 1 keine 2 Tupel aus R und S erfüllen p: js = 0 p (R.A=S.B)

falls A Schlüssel von R ist: Join erfolgt über eine Fremdschlüsselbeziehung mit Fremdschlüssel in S Jedes Tupel in S kann sich mit höchstens einem Tupel aus R verbinden T(R ⋈p S) T(S)

sel(R ⋈p S) = T(R ⋈p S) / (T(R) T(S))

≤ T(S) / (T(R) T(S))

≤ 1 / T(R) falls B Schlüssel von S ist: entsprechend js 1/T(S)

Join-Selektivität (1)

72


js = (R ⋈p S) / (R S) = (R ⋈p S) / (R S) Empfohlene Abschätzung bei p (R.A=S.B):

A, B ein-attributig

T(R ⋈p S) = (T(R)T(S)) / max( V(R,A),V(S,B) )

js = 1 / max( V(R,A),V(S,B) A, B mehr-attributig (Spezialfall 2 Attribute):

T(R ⋈p S) = (T(R)T(S)) /

( (max(V(R,A1),V(S,B1)) (max(V(R,A2),V(S,B2)) )

js = 1 / ( (max(V(R,A1),V(S,B1)) (max(V(R,A2),V(S,B2)) )

Join-Selektivität (2)

73



Mengen-OperatorenMengen-Operatoren

74


Schnitt (1)

Schnitt RS:

Lässt sich als Semi-Join über alle Attribute ausdrücken.

Im Grundsatz über die Algorithmen aus Kap. 9.4 umsetzbar.

Illustration am Beispiel GraceHash Join.

75


Schnitt (2)

R23

445

769013174288

S44179746

272

133

R3

90427613882

445

17

S6

273

974

1344172

Mod

3

Mod

3

Partitionierung

76


Schnitt (3)

R23

445

769013174288

S44179746

272

133

R3

90427613882

445

17

S6

273

974

1344172

Mod

3

Mod

3

Build/Probe

77


Schnitt (4)

R3

90427613882

445

17

S6

273

974

1344172

6273

Mod 5

HashtabelleBuild-Phase

78


Schnitt (5)

R S = { , }R3

90427613882

445

17

S6

273

974

1344172

6273

Mod 5

Probe-Phase3

79


Schnitt (6)

R S = {3, }R3

90427613882

445

17

S6

273

974

1344172

97134

Mod 5

Build-Phase

80


Schnitt (7)

R S = {3, 13 }R3

90427613882

445

17

S6

273

974

1344172

97134

Mod 5

Probe-Phase

81


Schnitt (8)

R23

445

769013174288

S44179746

272

133

R3

90427613882

445

17

S6

273

974

1344172

Mod

3

Mod

3

R S = {3, 13, 2, 44, 17 }

82


Vereinigung (1)

Mischen: Schritt 1: Sortierungen unter Duplikateliminierung

R und S müssen sortiert werden Entfällt falls R und S bereits sortiert

Schritt 2: Mischen In jeder Iteration: Falls aktuelle Tupel gleich, wird nur eines

übernommen, aber die Position beider fortgeschaltet. Andernfalls wird das kleinere übernommen und dessen Position fortgeschaltet.

Ergebnis sortiert.

C = B(R) + B(S) + ((1-f)(T(R)+T(S))/BfRS )

+ B(R)logm-1(B(R)/m) + B(S)logm-1(B(S)/m)

(f: Anteil an Duplikaten)

83


Einfügen: Unsortiertes Ergebnis ohne Duplikate

Vereinigung (2)

RSchon

gesehen?

m-1 Puffer Ausgabe-Puffer

nein

Wichtig für die Performanz: RS sollte in den Puffer passen, daher

nur für beschränkte Kardinalität brauchbar.Falls S duplikatfrei, nur R im Puffer.

Schnelle Zugriffsstruktur, z.B. Hashing.

SSchritt 1 Schritt 2

Documents

Universität Karlsruhe (TH) © 2009 Univ,Karlsruhe, IPD, Prof. LockemannDBI 9 Kapitel 9 Relationale Operatoren