Kapitel 8
Anfragebearbeitung
Logische Optimierung
Physische Optimierung
Kostenmodelle
„Tuning“
Ablauf der Anfrageoptimierung
Deklarative
Anfrage
Scanner
Parser
Sichtenauflösung
Algebraischer
Ausdruck
AnfrageOptimierer
AuswertungsPlan (QEP)
Codeerzeugung
Ausführung
© A. Kemper / A. Eickler
2
Kanonische Übersetzung
A1, ..., An
P

select A1, ..., An
from R1, ..., Rk
where P
Rk


R1
© A. Kemper / A. Eickler
R3
R2
3
Kanonische Übersetzung
select Titel
from Professoren, Vorlesungen
where Name = ´Popper´ and
PersNr = gelesenVon
Titel
Name = ´Popper´ and PersNr=gelesenVon

Professoren
Vorlesungen
Titel (Name = ´Popper´ and PersNr=gelesenVon (Professoren  Vorlesungen))
© A. Kemper / A. Eickler
4
Erste Optimierungsidee
select Titel
from Professoren, Vorlesungen
where Name = ´Popper´ and
PersNr = gelesenVon
Titel
PersNr=gelesenVon

Name = ´Popper´
Vorlesungen
Professoren
Titel (PersNr=gelesenVon ((Name = ´Popper´ Professoren)  Vorlesungen))
© A. Kemper / A. Eickler
5
Optimierung von Datenbank- Anfragen
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 SchnittstellenOperatoren 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“
© A. Kemper
/ A. Eickler
6
Äquivalenzerhaltende
Transformationsregeln
1. Aufbrechen von Konjunktionen im Selektionsprädikat
c1c2 ... 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. , ,  und A sind kommutativ
R Ac S  S Ac R
© A. Kemper / A. Eickler
7
Äquivalenzerhaltende
Transformationsregeln
….
8. Die Operationen A, , ,  sind jeweils (einzeln
betrachtet) assoziativ. Wenn also  eine dieser Operationen
bezeichnet, so gilt:
(R S ) T  R (S T )
….
Die formalen Regeln sind für uns nicht so wichtig. Folgende
Regeln sollten „intuitiv“ verständlich sein:
© A. Kemper / A. Eickler
8
Heuristische Anwendung der
Transformationsregeln
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 -Operation, die von einer -Operation gefolgt
wird, wenn möglich in eine join-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).
© A. Kemper / A. Eickler
9
Anwendung der Transformationsregeln
select distinct s.Semester
from Studenten s, hören h
Vorlesungen v, Professoren p
where p.Name = ´Sokrates´ and
v.gelesenVon = p.PersNr and
v.VorlNr = h.VorlNr and
h.MatrNr = s.MatrNr
s.Semester
p.Name = ´Sokrates´ and ...

p


s
© A. Kemper / A. Eickler
v
h
10
Aufspalten der Selektionsprädikate
s.Semester
s.Semester
p.PersNr=v.gelesenVon
p.Name = ´Sokrates´ and ...
v.VorlNr=h.VorlNr

p.Name = ´Sokrates´
p




s
s.MatrNr=h.MatrNr
v
p

h
v
s
h
© A. Kemper / A. Eickler
11
Verschieben der Selektionsprädikate
„Pushing Selections“
s.Semester
s.Semester
p.PersNr=v.gelesenVon
v.VorlNr=h.VorlNr
p.PersNr=v.gelesenVon
s.MatrNr=h.MatrNr
p.Name = ´Sokrates´


v.VorlNr=h.VorlNr

p.Name = `Sokrates`

p
s.MatrNr=h.MatrNr


v
p
v
s
h
s
h
© A. Kemper / A. Eickler
12
Zusammenfassung von Selektionen und
Kreuzprodukten zu Joins
s.Semester
p.PersNr=v.gelesenVon
s.Semester
Ap.PersNr=v.gelesenVon

v.VorlNr=h.VorlNr
p.Name = ´Sokrates´

s.MatrNr=h.MatrNr

s
v
h
p
Av.VorlNr=h.VorlNr
p.Name = ´Sokrates´
As.MatrNr=h.MatrNr
s
h
© A. Kemper / A. Eickler
v
p
13
Optimierung der Joinreihenfolge
Kommutativität und Assoziativität ausnutzen
s.Semester
s.Semester
As.MatrNr=h.MatrNr
Ap.PersNr=v.gelesenVon
Av.VorlNr=h.VorlNr
Av.VorlNr=h.VorlNr
p.Name = ´Sokrates´
As.MatrNr=h.MatrNr
s
h
v
s
Ap.PersNr=v.gelesenVon
p
h
p.Name = ´Sokrates´
p
© A. Kemper / A. Eickler
v
14
Was hat´s gebracht?
s.Semester
s.Semester
4
4
As.MatrNr=h.MatrNr
Ap.PersNr=v.gelesenVon
4
13
Av.VorlNr=h.VorlNr
Av.VorlNr=h.VorlNr
p.Name = ´Sokrates´
13
As.MatrNr=h.MatrNr
s
h
v
p
s
3
Ap.PersNr=v.gelesenVon
1
h
p.Name = ´Sokrates´
p
© A. Kemper / A. Eickler
v
15
Einfügen von Projektionen
s.Semester
s.Semester
As.MatrNr=h.MatrNr
As.MatrNr=h.MatrNr
h.MatrNr
Av.VorlNr=h.VorlNr
s
Av.VorlNr=h.VorlNr
Ap.PersNr=v.gelesenVon
Ap.PersNr=v.gelesenVon
h
h
p.Name = ´Sokrates´
p
v
s
p.Name = ´Sokrates´
p
© A. Kemper / A. Eickler
v
16
© A. Kemper / A. Eickler
17
Implementationen
des Join-Operators
Nested-Loop
Index-Join
Hash-Join
Sort/Merge-Join
Wann ein Index-Join benutzt wird, sollten Sie
entscheiden können!
© A. Kemper / A. Eickler
18
Implementierung der Verbindung:
Strategien
J1 nested (inner-outer) loop
„brute force“-Algorithmus
foreach r  R
foreach s  S
if s.B = r.A then Res := Res  (r  s)
© A. Kemper / A. Eickler
19
© A. Kemper / A. Eickler
20
© A. Kemper / A. Eickler
21
© A. Kemper / A. Eickler
22
Implementierung der Verbindung:
Strategien
J4 Hash-Join
 R und S werden mittels der gleichen Hashfunktion h –
angewendet auf R.A und S.B – auf (dieselben) HashBuckets abgebildet
 Hash-Buckets sind i.Allg. auf Hintergrundspeicher
(abhängig von der Größe der Relationen)
 Zu verbindende Tupel befinden sich dann im selben Bucket
 Wird (nach praktischen Tests) nur vom Merge-Join
„geschlagen“, wenn die Relationen schon vorsortiert sind
© A. Kemper / A. Eickler
23
Join (auch Mengendurchschnitt) mit
einem Hash/Partitionierungs-Algorithmus
R
2
3
44
17
97
3
13
17
42
4
RS
•Nested Loop: O(N2)
•Sortieren: O(N log N)
•Partitionieren und Hashing
Siehe auch Kap. 7
© A. Kemper / A. Eickler
S
44
17
97
4
6
27
2
13
3
24
R
3
3
42
97
13
88
2
44
17
17
R join S
S
6
27
3
97
4
13
44
17
2
© A. Kemper / A. Eickler
Mod 3
R
2
3
44
17
97
3
13
17
42
4
Mod 3
Join mit
einem Hash/Partitionierungs-Algorithmus
S
44
17
97
4
6
27
2
13
3
25
Vergleich: Sort/Merge-Join versus
Hash-Join
R
run
run
S
R
partition
partition
S
© A. Kemper / A. Eickler
26
Übersetzung der logischen Algebra
NestedLoopR.A=S.B
R
MergeJoinR.A=S.B
[Bucket]
[SortR.A] [SortS.B]
S
R
S
AR.A=S.B
R
S
IndexJoinR.A=S.B
R
HashJoinR.A=S.B
[HashS.B | TreeS.B]
R
S
© A. Kemper / A. Eickler
S
27
Übersetzung der logischen Algebra
IndexSelectP
R
P
R
SelectP
R
© A. Kemper / A. Eickler
28
Übersetzung der logischen Algebra
[IndexDup]
[SortDup]
[Hash | Tree]
l
Sort
Projectl
R
Projectl
R
[NestedDup]
R
Projectl
R
© A. Kemper / A. Eickler
29
Ein Auswertungsplan
Ein Auswertungsplan
© A. Kemper / A. Eickler
30
Wiederholung der Optimierungsphasen
select distinct s.Semester
from Studenten s, hören h
Vorlesungen v, Professoren p
where p.Name = ´Sokrates´ and
v.gelesenVon = p.PersNr and
v.VorlNr = h.VorlNr and
h.MatrNr = s.MatrNr
s.Semester
p.Name = ´Sokrates´ and ...

p


s
© A. Kemper / A. Eickler
v
h
31
s.Semester
As.MatrNr=h.MatrNr
Av.VorlNr=h.VorlNr
s
Ap.PersNr=v.gelesenVon
h
p.Name = ´Sokrates´
v
p
© A. Kemper / A. Eickler
32
© A. Kemper / A. Eickler
33
Selektivität
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/i
abgeschätzt werden.
© A. Kemper / A. Eickler
34
Parametrisierte Verteilung
Histogramm
© A. Kemper / A. Eickler
35
© A. Kemper / A. Eickler
36
I/O-Kosten: Block Nested Loop Join
© A. Kemper / A. Eickler
37
Tuning von Datenbanken
 Statistiken (Histogramme, etc.) müssen explizit angelegt
werden
 Anderenfalls liefern die Kostenmodelle falsche Werte
 In Oracle …
analyze table Professoren compute statistics for table;
Man kann sich auch auf approximative Statistiken verlassen
Anstatt compute verwendet man estimate
 In DB2 …
runstats on table …
© A. Kemper / A. Eickler
38
Analysieren von
Leistungsengpässen
Geschätzte
Kosten von
Oracle
© A. Kemper / A. Eickler
39
Übung mit einigen Anfragen auf Ihrer
Projekt-Datenbank:
Display Estimated Execution Plan
Im Query-Tool vom Management Studio
© A. Kemper / A. Eickler
40

Kapitel 8 Anfragebearbeitung