Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
Kapitel 8Anfragebearbeitung
Logische OptimierungPhysische OptimierungKostenmodelle„Tuning“
2
Ablauf der Anfrageoptimierung
ScannerParser
Sichtenauflösung
Anfrage-Optimierer
CodeerzeugungAusführung
DeklarativeAnfrage
AlgebraischerAusdruck
Auswertungs-Plan (QEP)
3
Kanonische Übersetzung
select A1, ..., Anfrom R1, ..., Rkwhere P
R1 R2
R3
Rk
P
A1, ..., An
4
Kanonische Übersetzungselect Titelfrom Professoren, Vorlesungenwhere Name = ´Popper´ and PersNr = gelesenVon
Professoren Vorlesungen
Name = ´Popper´ and PersNr=gelesenVon
Titel
Titel (Name = ´Popper´ and PersNr=gelesenVon (Professoren Vorlesungen))
5
Erste Optimierungsideeselect Titel from Professoren, Vorlesungenwhere Name = ´Popper´ and PersNr = gelesenVon
Professoren
Vorlesungen
PersNr=gelesenVon
Titel
Titel (PersNr=gelesenVon ((Name = ´Popper´ Professoren) Vorlesungen))
Name = ´Popper´
6
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 VarianteZiel: „avoiding the worst case“
Optimierung von Datenbank- Anfragen
7
1. Aufbrechen von Konjunktionen im Selektionsprädikat c1c2 ... cn (R ) c1(c2 (…(cn(R )) …))2. ist kommutativ c1(c2 ((R )) c2 (c1((R )) 3. -Kaskaden: Falls L1 L2 … Ln, dann gilt
L1( L2 (…( Ln(R )) …)) L1 (R )4. Vertauschen von und
Falls die Selektion sich nur auf die Attribute A1, …, An der Projektionsliste bezieht, können die beiden Operationen vertauscht werden
A1, …, An (c(R )) c (A1, …, An(R ))5. X, , und IXI sind kommutativ R IXIc S S IXIc R
Äquivalenzerhaltende Transformationsregeln
8
6. Vertauschen von mit IXI Falls das Selektionsprädikat c nur auf Attribute der
Relation R zugreift, kann man die beiden Operationen vertauschen:
c(R IXIj S) c(R) IXIj S
Falls das Selektionsprädikat c eine Konjunktion der Form „c1 c2“ ist und c1 sich nur auf Attribute aus R und c2 sich nur auf Attribute aus S bezieht, gilt folgende Äquivalenz:
c(R IXIj S) c1(R) IXIj (c2 (S))
Äquivalenzerhaltende Transformationsregeln
9
7. Vertauschung von mit IXIDie Projektionsliste L sei: L = {A1,…,An, B1,…,Bm}, wobei Ai Attribute aus R und Bi Attribute aus S seien. Falls sich das Joinprädikat c nur auf Attribute aus L bezieht, gilt folgende Umformung:
L (R IXIc S) (A1, …, An (R)) IXIc (B1, …, Bn (S))Falls das Joinprädikat sich auf weitere Attribute, sagen wir A1', …, Ap', aus R und B1', …, Bq' aus S bezieht, müssen diese für die Join-Operation erhalten bleiben und können erst danach herausprojiziert werden:
L (R IXIc S) L (A1, …, An, A1‘, …, An ‘ (R) IXIc B1, …, Bn, B1‘, …, Bn ‘ (R)) Für die X-Operation gibt es kein Prädikat, so dass die
Einschränkung entfällt.
Äquivalenzerhaltende Transformationsregeln
10
8. Die Operationen IXI, X, , sind jeweils (einzeln betrachtet) assoziativ. Wenn also eine dieser Operationen bezeichnet, so gilt:
(R S ) T R (S T )9. Die Operation ist distributiv mit , , . Falls
eine dieser Operationen bezeichnet, gilt: c(R S) (c (R)) (c (S))10. Die Operation ist distributiv mit .
c(R S) (c (R)) (c (S))
Äquivalenzerhaltende Transformationsregeln
11
11. Die Join- und/oder Selektionsprädikate können mittels de Morgan's Regeln umgeformt werden: (c1 c2) (c1) (c2) (c1 c2) (c1) (c2)
12. Ein kartesisches Produkt, das von einer Selektions-Operation gefolgt wird, deren Selektionsprädikat Attribute aus beiden Operanden des kartesischen Produktes enthält, kann in eine Joinoperation umgeformt werden.Sei c eine Bedingung der Form A B, mit A ein Attribut von R und B ein Attribut aus S.
c(R X S ) R IXIc S
Äquivalenzerhaltende Transformationsregeln
12
1. Mittels Regel 1 werden konjunktive Selektionsprädikate in Kaskaden von -Operationen zerlegt.
2. Mittels Regeln 2, 4, 6, und 9 werden Selektionsoperationen soweit „nach unten“ propagiert wie möglich.
3. Mittels Regel 8 werden die Blattknoten so vertauscht, dass derjenige, der das kleinste Zwischenergebnis liefert, zuerst ausgewertet wird.
4. Forme eine X-Operation, die von einer -Operation gefolgt wird, wenn möglich in eine IXI-Operation um
5. Mittels Regeln 3, 4, 7, und 10 werden Projektionen soweit wie möglich nach unten propagiert.
6. Versuche Operationsfolgen zusammenzufassen, wenn sie in einem „Durchlauf“ ausführbar sind (z.B. Anwendung von Regel 1, Regel 3, aber auch Zusammenfassung aufeinanderfolgender Selektionen und Projektionen zu einer „Filter“-Operation).
Heuristische Anwendung der Transformationsregeln
13
Anwendung der Transformationsregelnselect distinct s.Semesterfrom Studenten s, hören h Vorlesungen v, Professoren pwhere p.Name = ´Sokrates´ and v.gelesenVon = p.PersNr and v.VorlNr = h.VorlNr and h.MatrNr = s.MatrNr
s h
v
p
p.Name = ´Sokrates´ and ...
s.Semester
14
Aufspalten der Selektionsprädikate
s h
v
p
p.Name = ´Sokrates´ and ...
s.Semester
s hv
p
p.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´
s.MatrNr=h.MatrNr
v.VorlNr=h.VorlNr
15
Verschieben der Selektionsprädikate„Pushing Selections“
s h
vp
p.PersNr=v.gelesenVon
s.Semester
p.Name = `Sokrates`s.MatrNr=h.MatrNr
v.VorlNr=h.VorlNr
s hv
p
p.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´s.MatrNr=h.MatrNr
v.VorlNr=h.VorlNr
16
Zusammenfassung von Selektionen und Kreuzprodukten zu Joins
s h
vp
p.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´s.MatrNr=h.MatrNr
v.VorlNr=h.VorlNr
s h
vpIXIs.MatrNr=h.MatrNr
IXIp.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´
IXIv.VorlNr=h.VorlNr
17
Optimierung der JoinreihenfolgeKommutativität und Assoziativität ausnutzen
s
h
v
p
IXIs.MatrNr=h.MatrNr
IXIp.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´
IXIv.VorlNr=h.VorlNr
s h
vp
IXIp.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´IXIv.VorlNr=h.VorlNr
IXIs.MatrNr=h.MatrNr
18
Was hat´s gebracht?
s
h
v
p
IXIs.MatrNr=h.MatrNr
IXIp.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´
IXIv.VorlNr=h.VorlNr
s h
vp
IXIp.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´IXIv.VorlNr=h.VorlNr
IXIs.MatrNr=h.MatrNr
13
13
4
1
3
4
4
19
Einfügen von Projektionen
s
h
v
p
IXIs.MatrNr=h.MatrNr
IXIp.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´
IXIv.VorlNr=h.VorlNrs
h
v
p
IXIs.MatrNr=h.MatrNr
IXIp.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´
IXIv.VorlNr=h.VorlNrh.MatrNr
20
Eine weitere Beispieloptimierung
21
22
23
24
25
26
27
28
Pull-based Query Evaluation
opennext
ReturnErgebnis
29
Pipelining vs. Pipeline-Breaker
R S
...
...
...
T
...
...
...
30
Pipelining vs. Pipeline-Breaker
R S
...
...
...
T
...
...
...
31
Pipeline-Breaker
Unäre OperationensortDuplikatelimination (unique,distinct)Aggregatoperationen (min,max,sum,...)
Binäre OperationenMengendifferenz
Je nach ImplementierungJoinUnion
32
Beispiele:Op6 Employee IXI DNO = Dnumber DepartmentOp7 Department IXI MgrSSN = SSN Employee
Zu betrachten allgemein:Implementierungs-Varianten für R IXIA=B S
Implementierung der Verbindung (JOIN)
33
Literatur:
E. Elmasri and S. Navathe: Fundamentals of Database Systems. Benjamin Cummings, 1999, Redwood City, CA.
G. Moerkotte: Konstruktion von Anfrageoptimierer für Objektbanken. Shaker-Verlag, 1995, Aachen.
G. Graefe: Query Evaluation Techniques for Large Databases, ACM Computing Surveys, 1993, volume 25, number 2, pages 73-170.Ein ganz toller ÜbersichtsartikelPflichtlektüre
Optimierung zentralisierter Anfragen
34
35
J1 nested (inner-outer) loop„brute force“-Algorithmusforeach r Rforeach s Sif s.B = r.A then Res := Res (r s)
Implementierung der Verbindung: Strategien
36
37
Block-Nested Loop Algorithmus
m-k m-k m-k m-k m-kR
kS k k k k k
38
J2 Zugriffsstruktur auf SIndex Nested Loop Join
beim Durchlauf von R werden nur die in S qualifizierenden Tupel gelesen
dazu ist ein Index auf B erforderlicherfordert 1-2 Plattenzugriffe pro Tupel (Indexzugriff + S-Tupel)
foreach r Rforeach s S[B=r.A]
Res := Res (r s)
Implementierung der Verbindung: Strategien
39
40
J3 Sort-Merge Join erfordert zwei Sortierungen
1. R muss nach A und2. S nach B sortiert sein
sehr effizient falls A oder B Schlüsselattribut ist, wird jedes Tupel in R und S
nur genau einmal gelesen
Implementierung der Verbindung: Strategien
A 5 5 5 6 6 6 7 7
R
B 4 4 4 5 5 6 7 7 7
S
A B5 55 55 55 55 55 56 66 66 6
Ergebnis:
41
42
J4 Hash-Join R und S werden mittels der gleichen Hashfunktion h –
angewendet auf R.A und S.B – auf (dieselben) Hash-Buckets abgebildet
Hash-Buckets sind i.Allg. auf Hintergrundspeicher (abhängig von der Größe der Relationen)
Zu verbindende Tupel befinden sich dann im selben BucketWird (nach praktischen Tests) nur von J3 „geschlagen“,
wenn die Relationen schon vorsortiert sind
Implementierung der Verbindung: Strategien
43
Implementierung der Verbindung: Strategien
Ar1 5r2 7r3 8r4 5
R SB 5 s17 s210 s35 s4
r1 5
s15
r4 5
s45
10 s3
r2 7
s27
r3 8
h(A) h(B )
Bucket 3Bucket 2Bucket 1
45
„Normaler“ blockierender Hash-Join mit Überlauf: Partitionieren
Send
R
Send
S
receive
P1
P2
P3
Partitionh(R.A)
Partitionh(S.A)
receive
P1
P2
P3
46
„Normaler“ blockierender Hash-Join mit Überlauf: Build/Probe
Send
R
Send
S
P1
P2
P3
Partitionh(R.A)
buildHashtabelle
probe
Lade Blöcke von P1P1
P2
P3
48
49
50
51
52
Hybrid Hash-JoinFange so an, als wenn der Build-Input S vollständig in den
Hauptspeicher passen würdeSollte 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 R Jedes Tupel aus R, dessen potentielle Join-Partner im
Hauptspeicher sind, wird sogleich verarbeitet
Hybrid Hash-Join ist dann besonders interessant, wenn der Build-Input knapp größer als der Hauptspeicher istKostensprung beim normalen Hash-Join
Wird oft auch Grace-Hash-Join genannt, weil er für die Datenbankmaschine Grace in Japan erfunden wurde
53
Hybrid Hash-Join
R S
P1
P2
P3
Hashtabelle
54
Hybrid Hash-Join
R S
P3
P1
P2
Hashtabelle
55
Hybrid Hash-Join
R S
P2
P3
P1
Hashtabelle
56
Hybrid Hash-Join
R
P2
P3
Partitionh(R.A) P2
P3
Hashtabelle
probe
Wenn r zur ersten Partition
gehört
59
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746
272
133
R S
•Nested Loop: O(N2)
•Sortieren: O(N log N)
•Partitionieren und Hashing
60
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746272133
R SR3
90427613882
445
17
Mod
3
61
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746272133
R SR3
90427613882
445
17
S6
273
974
1344172
Mod
3
Mod
3
62
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23
445
769013174288
S44179746272133
R SR3
90427613882
445
17
S6
273
974
1344172
Mod
3
Mod
3
63
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R SR39042761388244517
S62739741344172
6273
Mod 5
Build-Phase
Hashtabelle
64
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R S = {3, }R39042761388244517
S62739741344172
6273
Mod 5
Probe-Phase
65
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R S = {3, }R39042761388244517
S62739741344172
97134
Mod 5
Build-Phase2. Partition
66
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R S = {3, }R39042761388244517
S62739741344172
97134
Mod 5
Probe-Phase2. Partition
67
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R S = {3, 13 }R39042761388244517
S62739741344172
97134
Mod 5
Probe-Phase2. Partition
68
Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus
R23445769013174288
S44179746272133
R39042761388244517
S62739741344172
Mod
3
Mod
3
R S = {3, 13, 2, 44, 17 }
69
Parallelausfü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.
70
111100
111100 False
drops
6 Bit(realistisch |R|*k Bits)
Join mit Hashfilter (Bloom-Filter)
R1
R2pa
rtiti o
nier
en
S1
S2
parti
ti oni
eren
71
..
..
..
..
..
..
Join mit Hashfilter(False Drop Abschätzung)Wahrscheinlichkeit, dass ein bestimmtes Bit j gesetzt ist
W. dass ein bestimmtes rR das Bit setzt: 1/bW. dass 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
72
Vergleich: Sort/Merge-Join versus Hash-Join
R run run S
merge m
erge
R partition partition S
73
Illustration: Externes Sortieren
971735
27162
9913
74
Illustration: Externes Sortieren
971735
27162
9913
75
Illustration: Externes Sortieren
971735
27162
9913
97
173
76
Illustration: Externes Sortieren
971735
27162
9913
3
1797
sort
77
Illustration: Externes Sortieren
971735
27162
9913
33
1797
1797
sortrun
78
Illustration: Externes Sortieren
971735
27162
9913
53
1797
2716
run
79
Illustration: Externes Sortieren
971735
27162
9913
53
17975
1627
1627
sortrun
80
Illustration: Externes Sortieren
971735
27162
9913
23
17975
1627
9913
run
81
Illustration: Externes Sortieren
971735
27162
9913
23
17975
16272
1399
1399
sortrun
82
Illustration: Externes Sortieren
33
17975
16272
1399
52
mergerun
83
Illustration: Externes Sortieren
2
33
17975
16272
1399
52
mergerun
84
Illustration: Externes Sortieren
23 3
317975
16272
1399
513
mergerun
85
Illustration: Externes Sortieren
235 17
317975
16272
1399
513
mergerun
86
Illustration: Externes Sortieren
235 17
317975
16272
1399
1613
mergerun
87
Illustration: Externes Sortieren
235
13
173
17975
16272
1399
1613
run
88
Externes Sortieren: Merge mittels Heap/Priority Queue
317975
16272
1399
mergerun
3
5 2
89
Externes Sortieren: Merge mittels Heap/Priority Queue
317975
16272
1399
mergerun
2
5 3
90
Externes Sortieren: Merge mittels Heap/Priority Queue
2 317975
16272
1399
run2
5 3
91
Externes Sortieren: Merge mittels Heap/Priority Queue
2 317975
16272
1399
run13
5 3
Ganz wichtig: aus dem grünen Run nachladen(also aus dem Run, aus
dem das Objekt stammte)
92
Externes Sortieren: Merge mittels Heap/Priority Queue
2 317975
16272
1399
run3
5 13
93
Externes Sortieren: Merge mittels Heap/Priority Queue
23
317975
16272
1399
run3
5 13
94
Externes Sortieren: Merge mittels Heap/Priority Queue
23
317975
16272
1399
run17
5 13
95
Externes Sortieren: Merge mittels Heap/Priority Queue
23
317975
16272
1399
run5
17 13
96
Mehrstufiges Mischen / Merge
m
m
Level 0
Level 1
Level 2
97
Replacement Selection während der Run-Generierung
971735
27162
9913
Ersetze Array durch einen Heap
98
Replacement Selection während der Run-Generierung
971735
27162
9913
Heap
97
99
Replacement Selection während der Run-Generierung
971735
27162
9913
Heap
1-97
1-17
100
Replacement Selection während der Run-Generierung
971735
27162
9913
Heap
1-17
1-97
101
Replacement Selection während der Run-Generierung
971735
27162
9913
Heap
1-17
1-97 1-3
102
Replacement Selection während der Run-Generierung
971735
27162
9913
Heap
1-3
1-97 1-17
103
Replacement Selection während der Run-Generierung
971735
27162
9913
3Heap
1-3
1-97 1-17
104
Replacement Selection während der Run-Generierung
971735
27162
9913
3Heap
1-5
1-97 1-17
105
Replacement Selection während der Run-Generierung
971735
27162
9913
35
Heap
1-5
1-97 1-17
106
Replacement Selection während der Run-Generierung
971735
27162
9913
35
Heap
1-27
1-97 1-17
107
Replacement Selection während der Run-Generierung
971735
27162
9913
35
Heap
1-27
1-97 1-17
108
Replacement Selection während der Run-Generierung
971735
27162
9913
35
Heap
1-17
1-97 1-27
109
Replacement Selection während der Run-Generierung
971735
27162
9913
35
17
Heap
1-17
1-97 1-27
110
Replacement Selection während der Run-Generierung
971735
27162
9913
35
17
Heap
2-16
1-97 1-27
Nächster Run, kleiner
als 17
111
Replacement Selection während der Run-Generierung
971735
27162
9913
35
17
Heap
2-16
1-97 1-27
Nächster Run, kleiner
als 17
112
Replacement Selection während der Run-Generierung
971735
27162
9913
35
17
Heap
1-27
1-97 2-16
113
Replacement Selection während der Run-Generierung
971735
27162
9913
35
1727
Heap
1-27
1-97 2-16
114
Replacement Selection während der Run-Generierung
971735
27162
9913
35
1727
Heap
2-2
1-97 2-16
115
Replacement Selection während der Run-Generierung
971735
27162
9913
35
1727
Heap
2-2
1-97 2-16
116
Replacement Selection während der Run-Generierung
971735
27162
9913
35
172797
Heap
1-97
2-2 2-16
117
Replacement Selection während der Run-Generierung
971735
27162
9913
35
172797
Heap
1-99
2-2 2-16
118
Replacement Selection während der Run-Generierung
971735
27162
9913
35
17279799
Heap
1-99
2-2 2-16
119
Replacement Selection während der Run-Generierung
971735
27162
9913
35
17279799
Heap
2-13
2-2 2-16
120
Replacement Selection während der Run-Generierung
971735
27162
9913
35
17279799
Heap
2-2
2-13 2-16
121
Replacement Selection während der Run-Generierung
971735
27162
9913
35
172797992
1316
Heap
2-2
2-13 2-16
122
Implementierungs-DetailsNatürlich darf man nicht einzelne Datensätze zwischen
Hauptspeicher und Hintergrundspeicher transferierenJeder „Round-Trip“ kostet viel Zeit (ca 10 ms)
Man transferiert größere BlöckeMindestens 8 KB Größe
Replacement Selection ist problematisch, wenn die zu sortierenden Datensätze variable Größe habeDer neue Datensatz passt dann nicht unbedingt in den frei gewordenen Platz, d.h., man benötigt eine aufwendigere Freispeicherverwaltung
Replacement Selection führt im Durchschnitt zu einer Verdoppelung der Run-LängeBeweis findet man im [Knuth]
Komplexität des externen Sortierens? O(N log N) ??
123
Algorithmen auf sehr großen Datenmengen
R23
445
789013174289
S44179756
272
139
R S
•Nested Loop: O(N2)
•Sortieren: O(N log N)
•Partitionieren und Hashing
124
Übersetzung der logischen Algebra
R S
IXIR.A=S.B
R S
HashJoinR.A=S.B
R S
MergeJoinR.A=S.B
[SortR.A] [SortS.B]
R
S
IndexJoinR.A=S.B
[HashS.B | TreeS.B]
R
S
NestedLoopR.A=S.B
[Bucket]
125
Übersetzung der logischen Algebra
P
R
SelectP
R
IndexSelectP
R
126
Übersetzung der logischen Algebra
l
R
[NestedDup]
ProjectlR
[SortDup]
Sort
Projectl
R
[IndexDup]
[Hash | Tree]
Projectl
R
127
Ein AuswertungsplanEin Auswertungsplan
128
Wiederholung der Optimierungsphasenselect distinct s.Semesterfrom Studenten s, hören h Vorlesungen v, Professoren pwhere p.Name = ´Sokrates´ and v.gelesenVon = p.PersNr and v.VorlNr = h.VorlNr and h.MatrNr = s.MatrNr
s h
v
p
p.Name = ´Sokrates´ and ...
s.Semester
129
s
h
v
p
IXIs.MatrNr=h.MatrNr
IXIp.PersNr=v.gelesenVon
s.Semester
p.Name = ´Sokrates´
IXIv.VorlNr=h.VorlNr
130
Kostenbasierte OptimierungGeneriere alle denkbaren Anfrageauswertungspläne
EnumerationBewerte deren Kosten
KostenmodellStatistikenHistogrammeKalibrierung gemäß verwendetem RechnerAbhängig vom verfügbaren SpeicherAufwands-Kostenmodell
Durchsatz-maximierendNicht Antwortzeit-minimierend
Behalte den billigsten Plan
131
132
Sind verschiedene Strategien anwendbar, so benötigt man zur Auswahl eine Kostenfunktion. Sie basiert auf dem Begriff der Selektivität.
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/iabgeschätzt werden.
Selektivität
133
134
Abschätzung für einfache Fälle
135
Parametrisierte Verteilung
Histogramm
136
137
Block-Nested Loop Algorithmus
m-k m-k m-k m-k m-kR
kS k k k k k
138
I/O-Kosten: Block Nested Loop Join
139
Tuning von DatenbankenStatistiken (Histogramme, etc.) müssen explizit
angelegt werdenAnderenfalls liefern die Kostenmodelle falsche Werte In Oracle …
analyze table Professoren compute statistics for table;
Man kann sich auch auf approximative Statistiken verlassenAnstatt compute verwendet man estimate
In DB2 …runstats on table …
140
Analysieren von Leistungsengpässen
Geschätzte Kosten von
Oracle
141
Baumdarstellung
142
BeispielAnfrage
SELECT *FROM A, B, CWHERE A.a = B.a AND
B.b = C.a ;
• Blätter Tabellen• innere Knoten Operatoren• Annotation Ausführungsorte
shipclient
IdxNLJ1
idxscan3
fscan2fscan1
A1
C3B2
HashJ1
Auswertungsplan
143
Algorithmen - AnsätzeErschöpfende Suche
Dynamische Programmierung (System R)A* Suche
Heuristiken (Planbewertung nötig)Minimum Selectivity, Intermediate Result,...
KBZ-Algorithmus, AB-AlgorithmusRandomisierte Algorithmen
Iterative ImprovementSimulated Annealing
144
ProblemgrößeSuchraum (Planstruktur)
● # Bushy-Pläne mit n Tabellen [Ganguly et al. 1992]:
n en (2(n-1))!/(n-1)!
2 7 25 146 1680
10 22026 1,76*1010
20 4,85 * 109 4,3*1027
(2(n-1))!(n-1)!
● Plankosten unterscheiden sich um Größenordnungen● Optimierungsproblem ist NP-hart [Ibaraki 1984]
145
Dynamische Programmierung II
Identifikation von 3 Phasen1. Access Root - Phase: Aufzählen der Zugriffspläne2. Join Root - Phase: Aufzählen der Join-Kombinationen3. Finish Root - Phase: sort, group-by, etc.
146
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
O S-O
OptimalerSubplan
OptimalerSubplan
147
DP - Beispiel
Index Pläne{ABC}{BC}{AC}{AB}{C}{B}{A}
1. Phase: Zugriffspläne ermitteln
148
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
149
DP - Beispiel
Index Pläne{ABC}{BC} ...{AC} s(A) IXI s(C), s(C) IXI s(A){AB} s(A)IXIs(B), s(A)IXIis(B), is(B)IXIs(A),... {C} scan(C){B} scan(B), iscan(B){A} scan(A)
Pruning2. Phase: Join-Pläne ermitteln (2-fach,...,n-fach)
150
DP - Beispiel
Index Pläne{ABC} (is(B) IXI s(A)) IXI s(C){BC} ...{AC} s(A) IXI s(C){AB} s(A) IXI is(B), is(B) IXI s(A) {C} scan(C){B} scan(B), iscan(B){A} scan(A)
3. Phase: Finalisierung
151
EnumerationEffiziente Enumeration [Vance 96]
anstatt zunächst alle 2-elem,3-elem, ..., n-elem Pläne sequentiell zu enumerieren: effizientes Interleaving
nur Pläne aus bereits berechneten Zeilen notwendig
Beispiel:1. A 2. B 3. AB 4. C 5. AC 6. BC 7. ABC