Anfrage-Optimierung und -Bearbeitung in Verteilten DBMS Relationenalgebra, Transformationen,...

Anfrage-Optimierung und -Bearbeitung in Verteilten DBMS

Relationenalgebra, Transformationen, Vereinfachungen,verteilte Joins,Kostenmodell

2

Formale GrundlagenRelationenalgebraSelektion Projektion Kreuzprodukt Vereinigung Differenz Umbenennung: V(R) AB(R) Join/Verbund, Semijoin, Outer Joins Durchschnitt Division

3

4

5

6

7

8

9100.000300

30.000.000

9.000.000.000

300

10

Äquivalenzregeln der Relationenalgebra

11

12

13

14

15

Besonders wichtige Äquivalenzen in Verteilten DBMS

)(

2212

21112121

1111 jpimjnijmjpini

pp

ppp

SRSR

SRSR

SRSRSSRR

16

Semijoin/Abgeleitete Partitionierung: Join-Optimierung

17

18

19

20

21

22

23

Optimierungs-Erfolg

300

300

3 100

1100.000

2

Optimierung

> 9.000.000.000Kosten-Units

Ca. 100.000Kosten-Units

(selbst das ist durch Index-Join noch

reduzierbar)

24

Transformation globaler Anfragen in lokale Anfragen

TEILE: {[TeileNr,LiefNr,Preis,...]}TEILE1 := 0TeileNr300 TEILETEILE2 := 300TeileNr500 TEILETEILE3 := 500 TeileNr999 TEILETEILE = TEILE1 TEILE2 TEILE3

Anfrage: 25TeileNr351 TEILE Transformation durch Einsetzen der Partitionierungs-

Definition25TeileNr351 (TEILE1 TEILE2 TEILE3)

25

Operator-Baum

25TeileNr351

TEILE1TEILE2 TEILE3

26

Operator-Baum:„Pushing Selections“

TEILE1 TEILE2 TEILE3

25TeileNr351 25TeileNr351

25TeileNr351

...(RS) = ...(R) ...(S)

27

Operator-Baum:inklusive Knoten-Annotation

TEILE1 TEILE2 TEILE3

25TeileNr351 25TeileNr351

25TeileNr351

Knoten AKnoten A Knoten B Knoten C

Knoten D(Client)

send

receivesend send

receivereceive

28

Operator-Baum:inklusive Knoten-Annotation

TEILE1 TEILE2 TEILE3

25TeileNr351 25TeileNr351

25TeileNr351

Knoten AKnoten A Knoten B Knoten C

Knoten D(Client)

send

receivesend send

receivereceive

29

Erkennung und Entfernung überflüssiger Teilausdrücke

TEILE1 TEILE2 TEILE3

25TeileNr351 25TeileNr351

25TeileNr351

Knoten AKnoten A Knoten B Knoten C

Knoten D(Client)

send

receivesend send

receivereceive

TEILE3 := 500 TeileNr999 TEILE

30

Formalisierung: Qualifizierungsprädikate

FqqSRqSqR

FqqSRqSqR

qqSRqSqR

qqSRqSqR

qSRqSqR

qqSRqSqR

qRqR

FqRqR

qqR

SRsjFS

sjFR

SRFSFR

SRSR

SRSR

RSR

SRSR

RAttrRAttr

RFRF

RR

:::

:::

:::

:::

:::

:::

::

:)(:

algebraRelationender gErweiterun

kat rungsprädiQualifizie R,Relation :

31

Qualifizierung der Beispielanfrage

TEILE1:0<=TeileNr<300

TEILE2:300<=TeileNr<500

TEILE3:500<=TeileNr<999

25TeileNr35125TeileNr351

25TeileNr351

500<=TeileNr<999 25TeileNr351

0<=TeileNr<300 25TeileNr351

25TeileNr300

300TeileNr351

32

33

34

35

36

37

38

39

Parallelausführung einer verteilten Anfrage Voraussetzung: Asynchrone Kommunikationsend/receive-Operatoren mit entsprechend

großem Puffer

TEILE1 TEILE2 TEILE3

25TeileNr351 25TeileNr351

25TeileNr351

Knoten AKnoten A Knoten B Knoten C

Knoten D(Client)

sendreceive

send send

receivereceive

40

41

Pull-based Query Evaluation

opennext

ReturnErgebnis

42

Send/Receive-Iteratoren

receive receive

send send

43

Send/Receive-Iteratoren

receive receive

send send

Sende Tupelasynchron

44

Parallelausführung bei horizontaler Partitionierung R = R1R2R3R4 F R= F R1 F R2 F R3 F R4

Send

F

R1

Send

F

R2

Send

F

R3

Send

F

R4

union

receive receive receive receive

45

Parallelausführung bei abgeleiteter horizontaler Partitionierung

R = R1R2R3R4; S = S1S2S3S4 Si = S lsj

F Ri R F S

Send

F

R1 S1

Send

F

R2 S2

Send

F

R3 S3

Send

F

R4 S4

union

receive receive receive receive

46

Prallelausführung von Aggregat-Operationen

Min: Min(R.A) = Min ( Min(R1.A), ... , Min(Rn.A) ) Max: analog Sum: Sum(R.A) = Sum ( Sum(R1.a), ..., Sum(Rn.A) ) Count: analog Avg: man muß die Summe und die Kardinalitäten der

Teilrelationen kennen; aber vorsicht bei Null-Werten! Avg(R.A) = Sum(R.A) / Count(R) gilt nur wenn A keine Nullwerte

enthält.

47

Pipelining vs. Pipeline-Breaker

R S

...

...

...

T

...

...

...

48

Pipelining vs. Pipeline-Breaker

R S

...

...

...

T

...

...

...

49

Pipeline-Breaker

Unäre OperationensortDuplikatelimination (unique,distinct)Aggregatoperationen (min,max,sum,...)

Binäre OperationenMengendifferenz

Je nach Implementierung JoinUnion

50

51

Nested Loop Join in Verteilten Datenbanken

52

Block Nested Loop Join:zentrale Datenbank

53

Block Nested Loop Join:verteilte Datenbank R wird an die Heimatstation von S geschickt Sobald ein „hinreichend“ großer Block von R-Tupeln

angekommen ist, wird durch S iteriert Der Block von R-Tupeln sollte tunlichst in eine Hash-

Tabelle geladen werden

54

55

Merge Join in Verteilten Datenbanken R und S sollten möglichst an ihren Heimatknoten

sortiert werden in (unkooperativen) Multi-Datenbanken nicht immer

möglich Noch besser, die Heimatknoten lesen R und S sortiert

„von der Platte“ (Pipelining)Cluster-IndexSekundär-Index

Merge-Join wird dann z.B. dort ausgeführt, wo das Ergebnis gebraucht wird

56

57

Index Join in Verteilten Datenbanken Sollte dort dort ausgeführt werden, wo der Index liegthier Heimatstation von SR muss dorthin transferiert werden

Alternative: einen temporären Index aufbauenHash Join

58

„Normaler“ blockierender Hash-Join: Build-Phase

Send

R

Send

S

receive receive

Puffer

Hashtabelle

Keine Ergebnisse

59

„Normaler“ blockierender Hash-Join: Probe-Phase

Send

R

Send

S

receive receive

Puffer

h(...)Hashtabelle

60

„Normaler“ blockierender Hash-Join mit Überlauf: Partitionieren

Send

R

Send

S

receive

P1

P2

P3

Partitionh(R.A)

P1

P2

P3

Partitionh(S.A)

receive

Potenzielle Joinpartner

61

„Normaler“ blockierender Hash-Join mit Überlauf: Partitionieren

Send

R

Send

S

receive

P1

P2

P3

Partitionh(R.A)

P1

P2

P3

Partitionh(S.A)

receive

62

„Normaler“ blockierender Hash-Join mit Überlauf: Build/Probe

Send

R

Send

S

receive

P1

P2

P3

Partitionh(R.A)

P1

P2

P3

build

Hashtabelle

probe

Lade Blöcke von P1

63

64

65

Resümee: Hash Join(in verteilten Datenbanken) Der Build-Input (hier S) muß erst vollständig transferiert

sein, bevor das erste Join-Tupel generiert werden kann Man kann die erste Partition schon „join-en“ während der

Probe-Input (hier R) noch angeliefert wird Die 2. Partition kann aber erst bearbeitet werden,

sobald der Probe-Input vollständig empfangen wurde Normalerweise nimmt man die kleinere Relation als Build-

Input In verteilten Systemen muß man die

Kommunikationskosten mit berücksichtigen möglicherweise nimmt man die größere Relation wenn

sie schneller transferiert werden kann dynamisches Umschalten zwischen Build- und Probe-

Input, falls der Build-Input zu langsam geliefert wird

66

Double-Pipelined Hash-Join

Send

R

Send

S

receive receive

Hashtabelle

probeeinfügen

Hashtabelle

Ergebnis-Tupel

X-Join

67

Double-Pipelined Hash-Joinmit „Überlauf“

Send

R

Send

S

receive receive

Hashtabelle

probeeinfügen

Hashtabelle

Ergebnis-Tupel

2.Partition

3.Partition

2. Partition

3. Partition

1.Partition

68

Spezielle Join-Pläne für Verteilte DBMS Semi-Join zur Reduktion des Datentransfer-VolumensR F

S = (R lsjF S) F

S R F

S = (R lsjF S) F

(R rsjF S)

Hash-Filter-Join

anstatt des Semijoin-Ergebnisses wird ein Bitvektor, der das Semijoin-Ergebnis approximiert, generiert.

69

70

71

72

73

Semi-Join-Pläne beim Mehrwege-Join R(A,B) S(B,C) T(C,D) Join-Graph: [ R lsj (S lsj T) ] S T [ R lsj (S lsj T) ] [ S lsj T ] T [ R lsj S ] [ S lsj T ] T [ R lsj S ] [ R rsj S ] T [ R lsj S ] [ R rsj S lsj T ] T [ R lsj S ] [ R rsj S lsj T ] [ T lsj S ] [[ R S ] lsj T ] T .......Finde den besten Plan: full reducer

nur bei azyklischen Join-Graphen möglich

R S TB C

74

111100

111100 False

drops

C

6 Bit

12 Attribute (4 Tupel, inkl. 2 False Drops)

15 Attribute

Join mit Hashfilter(Bloom-Filter)

75

..

..

..

..

..

..

Join mit Hashfilter(False Drop Abschätzung) Wahrscheinlichkeit, dass ein bestimmtes Bit j gesetzt

istW. dass ein bestimmtes rR das Bit setzt: 1/bW. dasss kein rR das Bit setzt: (1-1/b)|R|

W. dass ein rR das Bit gesetzt hat: 1- (1-1/b)|R|

01..j..

b-1

76

Join mit Hashfilter(False Drop Abschätzung) W. dass irgendein rR ein bestimmtes Bit gesetzt

hat: 1- (1-1/b)|R|

Wieviele Bits sind gesetzt? b * [1- (1-1/b)|R|]

Mehrere rR können dasselbe Bit setzen Approximation: alle rR setzen unterschiedliche BitsW. dass ein bestimmtes Bit j gesetzt ist: |R| / bb >> |R|

..

..

..

..

..

..

01..j..

b-1

77

Join mit Hashfilter(False Drop Abschätzung) W. dass irgendein rR ein bestimmtes Bit gesetzt

hat: 1- (1-1/b)|R|

W. dass ein bestimmtes sS ausgewählt wird:1- (1-1/b)|R|

Wieviele sS werden ausgewählt? |S| * [1- (1-1/b)|R|]

Approximation: alle r setzen unterschiedliche BitsW. dass ein bestimmtes Bit j gesetzt ist: |R| / b |S|*(|R|/b) Elemente aus S werden ausgewählt

..

..

..1....

01..j..

b-1

78

Weitere Einsatzmöglichkeiten für Hash-Filter Für Signatur-Files (~Indexe für die Filterung von Daten) Beim „normalen“ Hash-Join beim Partitionieren der einen Relation wird eine

Bitmap (mgl. pro Partition) gebautbeim Partitionieren der anderen Relation

wird/werden diese Bitmaps zum Filtern verwendetz.B. in MS SQL-Server eingebaut

Zur abgeleiteten Partitionierung hierarchischer Datenstrukturenearly partitioning

79

Traditioneller Join Plan

Resultat

R

S

A

A

T

R S T

80

Traditioneller Hash Team Join Plan[Graefe, Bunker, Cooper: VLDB 98, MS SQL Server]

R

S

A

A

T

Resultat

A

AR.AR.A

S.AS.A

T.AT.A

R AA S T

81

Generalized Hash Teams

SA B

4 3

6 2

3 5

7 0

R BA S T

TB ...

3 ...

0 ...

5 ...

2 ...

ST

A B ...

4 3 ...

3 5 ...

6 2 ...

7 0 ...

R... A

... 4

... 3

... 6

... 7

82

bit maps

0 0 0

1 0 1

2 0 1

3 1 0

4 1 0

SA B

4 3

6 2

3 5

7 0

Generalisierte Hash Teams[Kemper et al., VLDB 1999 und VLDBJ 2000]

TB ...

3 ...

0 ...

5 ...

2 ...

R... A

... 4

... 3

... 6

... 7

R BA S T

R BA S T

6 m

od 5

=

1

Partitioniereüber B

ungerade: gelbgerade: grün

83

Generalisierte Hash Team für Gruppierung/Aggregation

select c.City, sum(o.Value)from Customer c, Order owhere c.C# = o.C#group by c.City

Agg

Bit-maps(BM)

OrderCustomer

Ptn on C# Ptn on C#

Ptn on City

OrderCustomer

Ptn on City Ptn on BM

Agg

Join und

Gruppierungs-

Team

84

Group (Customer Order )C#City

Customer

Order

C#

City

C# Partitioniere mit

Bitmaps für C#

Customer: {[C#, Name, City, ...]}Order: {[O#, C#, Wert, ...]}Lineitem: {[O#, L#, Anzahl, Preis, ...]}

Partitioniere über City und generiere

Bitmaps für C#

85

Group (Customer Order Lineitem)C#City O#

Customer

Order

Lineitem

O#

C#

City

C#

O#

Partitioniere über City und generiere

Bitmaps für C#

Partitioniere mitBitmaps für O#

Partitioniere mitBitmaps für C#und generiere

Bitmaps für O#

86

bit maps

0 0 0

1 0 1

2 0 1

3 1 1

4 1 0

False Drops

R BA S T

R BA S TR... A

... 4

... 3

... 6

... 7

SA B

4 3

6 2

3 5

7 0

8 4

TB ...

3 ...

0 ...

5 ...

2 ...

4 ...

87

Überlappende Partitionen

T

S

R

Customer

Order

Lineitem

PartitioniereüberC# und generiereBitmaps für O#

Partitioniere mitBitmaps

Partitioniereüber B undgeneriere

Bitmaps für A

Partitioniere mit den

Bitmaps für A

(Customer Order Lineitem)C# O#

88

Anwendbarkeit der Generalisierten Hash Teams

• für die Partitinierung partitioning hierarchischer Strukturen A B

Partitioniereüber B

Partitionieremit Bitmaps

für A

• aber auch korrekt für nicht-strikte Hierarchien A B (aber Leistungs-Degradierung zu befürchten)

89

bit maps

0 0 0

1 0 1

2 0 1

3 1 1

4 1 0

Nicht-strikte HierarchieA B

R BA S T

R BA S TR... A

... 4

... 3

... 6

... 7

SA B

4 3

6 2

3 5

7 0

3 2

TB ...

3 ...

0 ...

5 ...

2 ...

T

S

R

90

Grundsätze: Sehr hohes Abstraktionsniveau der mengenorientierten Schnittstelle

(SQL). Sie ist deklarativ, nicht-prozedural, d.h. es wird spezifiziert, was man

finden möchte, aber nicht wie. Das wie bestimmt sich aus der Abbildung der mengenorientierten

Operatoren auf Schnittstellen-Operatoren der internen Ebene (Zugriff auf Datensätze in Dateien, Einfügen/Entfernen interner Datensätze, Modifizieren interner Datensätze).

Zu einem was kann es zahlreiche wie‘s geben: effiziente Anfrageauswertung durch Anfrageoptimierung.

i.Allg. wird aber nicht die optimale Auswertungsstrategie gesucht (bzw. gefunden) sondern eine einigermaßen effiziente Variante Ziel: „avoiding the worst case“

Optimierung zentralisierter Anfragen

91

Optimierung durch Dynamische Programmierung Standardverfahren in heutigen relationalen

Datenbanksystemen Voraussetzung ist ein Kostenmodell als

Zielfunktion I/O-KostenCPU-Kosten

DP basiert auf dem Optimalitätskriterium von Bellman

Literatur zu DP: D. Kossmann und K. Stocker: Iterative Dynamic

Programming, TODS, 2000 (online)

O S-O

OptimalerSubplan

OptimalerSubplan

92

„Klassische“ Optimierung durchDynamisches Programmieren

TablescanIndexscan Clusterindex Sekundärindex

O S-O

Wenn zwei Pläne ver-gleichbar sind, behalte

nur den billigsten

93

DP - Beispiel

Index Pläne

{ABC}

{BC}

{AC}

{AB}

{C}

{B}

{A}

1. Phase: Zugriffspläne ermitteln

94

DP - Beispiel

Index Pläne

{ABC}

{BC}

{AC}

{AB}

{C} scan(C)

{B} scan(B), iscan(B)

{A} scan(A)

1. Phase: Zugriffspläne ermitteln

95

DP - Beispiel

Index Pläne

{ABC}

{BC} ...

{AC} s(A) s(C), s(C) s(A)

{AB} s(A) s(B), s(A) is(B), is(B) s(A),...

{C} scan(C)

{B} scan(B), iscan(B)

{A} scan(A)

Pruning

2. Phase: Join-Pläne ermitteln (2-fach,...,n-fach)

96

DP - Beispiel

Index Pläne

{ABC} (is(B) s(A)) s(C)

{BC} ...

{AC} s(A) s(C)

{AB} s(A) is(B), is(B) s(A)

{C} scan(C)

{B} scan(B), iscan(B)

{A} scan(A)

3. Phase: Finalisierung

97

„Fine Points“ der DP-Optimierung Komplexität O(3n) Unvergleichbarkeit von zwei PlänenR sort-merge-join SR hash-join Sersterer ist vermutlich teurer, generiert aber ein

gemäß Join-Attribut sortiertes Ergebnisunvergleichbare Pläne

führt möglicherweise später zu einem billigeren (merge-)Join (mit bspw. T)

Man spricht von „interesting physical properties“ Also, haben wir nur eine partielle Ordnung zwischen

den semantisch äquivalenten Plänen (Zeile 3 und 4)Widerspricht eigentlich dem Optimalitätskriterium,

das für die Anwendbarkeit von DP erforderlich ist

98

Erweiterungen für Verteilte Datenbanken Replizierte Relationen: generiere accessPlans für alle

Möglichkeitentable_scan(Angestellte,Pasau) idx_scan(Angestellte.Gehalt,Passau)table_scan(Angestellte,NewYork)

Ausführung des Joins (Zeile 9)am Knoten wo das äußere/linke Join-Argument generiert wirdam Knoten wo das innere/rechte Join-Argument generiert

wird

an allen weiteren „interessanten“ Knoten Für S={Ri1,...,Rik} sind alle Heimatknoten von {R1,...,Rn}\

{Ri1,...,Rik} und der Knoten, an den das Ergebnis kommen muss, interessant

O S-O

99

Optimierung in VDBMSs: Replikation

T TS

V

V R

R

S

100

Optimierung in VDBMSs: Join-Reihenfolge und Ausführungsort

T TS

V

V R

R

S

101

Optimierung in VDBMSs: Join-Reihenfolge und Ausführungsort

T TS

V

V R

R

S

102

Optimierung in VDBMSs: Join-Reihenfolge und Ausführungsort

T TS

V

V R

R

S

103

Optimierung in VDBMSs

T3

V1

R2

S9

3

7

7

104

Optimierung in VDBMSs

T3

V1

R2

S9

3

7

7

105

Optimierung in VDBMSs

T3

V4R2

S9

3

9

7

106

Erweiterungen für Verteilte Datenbanken (2) Pruning eines Plans P1 wenn es einen semantisch

äquivalenten Plan P2 gibt mit:

Was kostet der Datentransfer zwischen den Knoten? In einem homogenen Netzwerk kann man von gleichen

Kosten zwischen allen Knoten ausgehen. Plan P1 kann auf jeden Fall schon eliminiert werden,

wenn man das Ergebnis von P2 billiger nach x schicken kann, wobei x der Knoten ist, an dem P1 sein Ergebnis generiert.

Zeitkomplexität: O(s3 * 3n)

107

Replikationsinformation

Kommunikationskosten:Bandbreite, Latenz zwischen

den StationenAllokationsinformation

108

Kostenmodelle In herkömmlichen Datenbanksystemen:

Durchsatzoptimierung (throughput)Aufwands-Kostenmodell W

In verteilten Anwendungen: Antwortzeit-Optimierung (response time)

Antwortzeit-Kostenmodell T Beispielanfrage q mit optimalem Wo bzw ToBetrachte einen Auswertungsplan p für q

Wp bzw Tpman sollte aber nicht beliebig viel Aufwand treiben, um Tp

zu optimieren

109

Zunächst: Überblick über Aufwandsabschätzung Selektivitätsabschätzung Kostenmodellierung der wichtigsten OperatorenNested Loops JoinMerge Join Index JoinHash Join

Parallelverarbeitung (pipelining)Sequenzielle Ausführung (pipeline-breaker)

Danach: Überblick über Antwortzeit-Kostenmodell

110

Attribute, die Teil des Primärschlüssels sind, sind unterstrichen.

Beispiel-Datenbankschema

Fname Lname SSN BDate Adress Sex Salary SuperSSN DNOEmployee

Dname Dnumber MgrSSN MgrStartDateDepartment

Dnumber Dlocation

DeptLocations

ProjectPname Pnumber Plocation Dnum

WorksOnESSN PNO Hours

111

Die Selektivität eines Suchprädikats schätzt die Anzahl der qualifizierenden Tupel relativ zur Gesamtanzahl der Tupel in der Relation.

Beispiele:die Selektivität einer Anfrage, die das

Schlüsselattribut einer Relation R spezifiziert, ist 1/ #R, wobei #R die Kardinalität der Relation R angibt.

Wenn ein Attribut A spezifiziert wird, für das i verschiedene Werte existieren, so kann die Selektivität als

(#R/i) / #R oder 1/i abgeschätzt werden.

Selektivität

112

Join-Selektivität

113

Histogrammverfahren: Beispiel:

Systematische Kostenabschätzung

In den Intervallen [i3,i4] und [i4,i5] relative schlechte Abschätzung (große Abweichung Verteilung zu Histogramm).

114

Histogrammverfahren: Abhilfe kann durch nicht äquidistante Unterteilung geschaffen

werden: Gleiche Höhe statt gleiche Breite. Vorteil:

Fehler hängt nicht mehr von der Verteilung ab Nachteil:

Erstellung ist teurer, da die Attributwerte sortiert werden Fortschreiben unter Erhalten der gleichen Höhe ist kaum

möglich, stattdessen i.d.R. Neuerstellung des Histogramms in periodischen Zeitabständen

Systematische Kostenabschätzung

115

foreach r R foreach s S

if s.B = r.A then Res:=Res (r s)Günstigste Realisierung:

nB-1 Rahmen für die äußere Schleife (nB: Zahl der Pufferrahmen) 1 Rahmen für die innere Schleife

repeat:lese nB-1 Blöcke der Relation R in HashTabelle einrepeat:

lese 1 Block der Relation Svergleiche jedes Hauptspeicher-Tupel aus R mit jedem Hauptspeicher-Tupel aus S und verbinde sie gegebenenfalls

until: alle Blöcke aus S sind gelesenuntil: alle Blöcke aus R sind gelesen

Kostenabschätzung für Block-Nested Loop Join (BNL)

116

Seitenzugriffe ist das „Maß der Dinge“ Allerdings haben neuere empirische Arbeiten gezeigt, dass CPU-Kosen nicht zu

vernachlässigen sind Auch muss man unbedingt zwischen „random IO“ und „sequential/chained IO“

differenzieren Beispiel:

Employee DNO=Dnumber Department

#E = 5000 Tupel auf bE = 2000 Seiten verteilt#D = 50 Tupel auf bD = 10 Seiten verteiltnB = 6 Pufferrahmen

Kostenabschätzung für BNL-Join

117

Es werden bE Seiten in der äußeren Schleife eingelesen Es wird bE / (nB1) mal Department neu eingelesen Damit werden bD bE / (nB1)

Seiten in der inneren Schleife eingelesen Also werden

bE + bE / (nB1) bD = 2000 + 2000 / 5 10 = 6000

Seiten gelesen

Kostenabschätzung für BNL-Join

Employee Department

118

Vertauschung der Join-Reihenfolge:Department DNO=DnumberEmployee

Kosten:bD + bD / (nB1) bE = 10 + 10 / 5 2000 = 4010

Man kann also durch Vertauschen der Join-Reihenfolge erhebliche Kosten einsparen.

Grundsätzlich bei BNL-Join: die von der Seitenzahl her kleinere Relation nach außen verlagern.

Für die innere nur 1 Seite (müssen aber große sein)

Kostenabschätzung für BNL-Join

119

Beispiel: Employee SSN = MgrSSN Department(V1) Annahme: Primärindex für Employee.SSN und Sekundärindex

für Department.MgrSSN INL-Join kann also in beiden Richtungen ausgeführt werden,

also auch:Department MgrSSN = SSN Employee (V2)

Zusatzannahme: Indexdatei physisch in B-Baum realisiert. Indexhöhe ( Höhe des B-Baums)

xSSN = 4 xMgrSSN = 2

Selektivitäten: Employee.SSN: 1 Satz pro SSN Department.MgrSSN: im Mittel n Sätze pro MgrSSN

Kosten für V1:bE +(#E (xMgrSSN+n)) = 2000 + 5000 (2+n) = 12000 + 5000n

Kosten für V2:bD +(#D (xSSN+1)) = 10 + 50 5 = 260

Kostenabschätzung für Index-NL-Join

120

Beide Relationen müssen geordnet sein. Sonst evtl. Sortierung vorschalten (mit

entsprechenden Kosten) Sortierung erlaubt dann im günstigsten Fall (Join-

Attribut in mindestens einer der beiden Relationen „unique“) „single pass“-Merge-Lauf.

Also werden in unserem Beispiel bE + bD = 2000 + 10

Seiten gelesen.

Kostenabschätzung für Merge-Join

121

Hash-Join gilt als sehr effizient. Schwierige analytische Kosenabschätzung (insb. Hybrid hash join). q ist der Anteil von R, der in den Hauptspeicher passt

Literatur: Steinbrunn, Moerkotte, Kemper. Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB Journal, Vol 6, No 3, Aug 1997. online

Kostenabschätzung für Hash Join

Memorysize

Fudge Factor

122

Strategien bei der Optimierung für Parallele Ausführung Beispielanfrage q mit optimalem Wo bzw ToBetrachte einen Auswertungsplan p für q

Wp bzw Tp man sollte aber nicht beliebig viel Aufwand treiben, um

Tp zu optimieren! 2 Strategien:Limitiere Durchsatz-Degradierung

Wp <= k * Wo muss geltensonst: Tp :=

Kosten/Nutzen-Verhältnis muss stimmen(To - Tp)/(Wp - Wo) <= k muss geltensonst: Tp :=

123

Beispielanfrage

R1

scan

R3

scan

sort

R2

scan

sort

merge

Nested Loops

parallel

Pipelinebreaker

Pipelinebreaker

pipelining

124

Beispielanfrage: Kosten nach Aufwandsabschätzung

R1

scan

R3

scan

sort

R2

scan

sort

merge

Nested Loops

parallel

3

2

10->135->6

1

2->21

2->2+2+21=25

125

Beispielanfrage: Deskriptoren First Tuple/Last Tuple

R1

scan

R3

scan

sort

R2

scan

sort

merge

Nested Loops

parallel

FT:0LT:3

FT:0LT:2

FT:10->13LT:10->13

FT:5->6LT:5->6

FT:0LT:1

FT:0->13LT:2->15

FT:0->13LT:2->15

126

Antwortzeit-Abschätzung eines Operatorbaums t1||t2 schätzt die RT (response time) zweier

unabhängiger paralleler Ausführungseinheiten S1 und S2 t1||t2 := max(t1,t2)

t1;t2 schätzt die RT zweier sequentieller Ausführungseinheiten t1;t2 := t1+t2

Pipeline S1 wird „gefüttert“ von einer materialisierten Sub-Query S2. Die Pipeline S1S2 braucht demnach t1 t2 := t1 - t2

127

Antwortzeit-Abschätzung einerPipeline Produzent P mit Deskriptor (Pf,Pl) Konsument C mit Deskriptor (Cf,Cl) Der Antwortzeit-Deskriptor (Tf,Tl) der Pipeline T

= „P ---> C“ ergibt sich dann wie folgtTf = (Pf;Cf) := Pf +CfTl = (Pf; Cf; ((Pl Pf)||(Cl Cf))

Max(...)die langsamere der beiden Pipelines bestimmt die Antwortzeit

128

Deskriptoren First Tuple/Last Tuple: Herleitung

R1

scan

R3

scan

sort

R2

scan

sort

merge

Nested Loops

parallel

FT:0LT:3

FT:0LT:2

FT:10->13LT:10->13

FT:5->6LT:5->6

FT:0LT:1

FT:0->13LT:2->15

FT:0->13LT:2->15

Merge;(sort;scan_R1)||(sort;scan_R2)FT: 0+max(6,13)LT: 2+max(6,13)

Pipelinebreakeralso FT=LTSort ; scan:FT= 10+3LT=10+3

NL;Merge;(sort;scan_R1)||(sort;scan_R2)

129

Erweiterung des Kostenmodells:Ressourcen haben beschränkte Bandbreite

130

Resource Contention: R1 und R2 auf derselben Platte

R1

scan

R3

scan

sort

R2

scan

sort

merge

Nested Loops

parallel

FT:0LT:3 4

r=(3,....)

FT:0LT:2

FT:10->13 14LT:10->13 14

FT:5->6 9LT:5->6 9

FT:0LT:1 4r=(1,..)

FT:0->13 14LT:2->15 16

FT:0->13 14LT:2->15 16

131

Einbeziehung der Kommunikationskosten Betrachte Send/Receive-Iteratoren als „ganz normale“

Operatoren Schicken des ersten Tupels:Latenzzeit des Netzes

Danach Pipelining Transfervolumen/Bandbreite

send

receive

132

Mehrdimensionales Kostenmodell

Aufwand

Ers

tes

Tu

pel

Letz

tes

Tupe

l

Hoher Aufwand,niedrige Antw.-Zeit

Niedriger Aufwand,hohe Antw.-Zeit

133

Anfrageoptimierung: partielle Ordnung der Pläne (QEPs)

Aufwand

Antwort-zeit

P

Q

R

Von P dominierte (= ausgeblendete)PläneVon Q ausgeblendete

Pläne

134

Anfragebearbeitung in heterogenen Multi-Datenbanken

Teil2, ab S. 96