Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | loreley-ament |
View: | 103 times |
Download: | 0 times |
UniversitätKarlsruhe (TH)
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10
Anfragebearbeitung
2
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
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
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.1Kapitel 10.1
VorgehensmodellVorgehensmodell
4
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Sehr hohes Abstraktionsniveau der mengenorientierten Schnittstelle (SQL). Anfragen sind deklarativ (nicht-prozedural), d.h. es wird
spezifiziert, was man finden möchte, aber nicht wie. Chance und Herausforderung: Das wie bestimmt sich aus
der Abbildung der Anfrage auf die Operatoren der internen Ebene. Zu einem was kann es zahlreiche wie‘s geben:
Verschiedene Algorithmen (Kapitel 9), die auf unterschiedlichen Abbildungen der Relationen auf interne Dateien und logische Zugriffspfade beruhen.
Reihenfolge der Operatoren, um hohe Selektivität zu erreichen. Effiziente Anfrageauswertung durch Anfrageoptimierung.
Ziel: Gesucht wird nicht die optimale Auswertungsstrategie, sondern eine einigermaßen effiziente Variante (z.B. „avoiding the worst case“).
Ziel
5
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Ablauf der Anfragebearbeitung
Anfrage-Übersetzer
Sichtauflösung
Anfrage-Optimierer
CodeerzeugungAusführung
DeklarativeAnfrage
AlgebraischerAusdruck
Auswertungs-Plan (QEP)
6
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
LaufzeitÜbersetzungszeit
Verfeinerter Ablauf der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Ergebnis
Standardisierung
Optimierung
Ausführung DBS-Laufzeitsystem
Planparametri-sierung
Code-Erzeugung
Anfrage in interner Form
algebraischer Ausdruck auf internen Dateien QEP
QEP
Code
Logische Optimierung
Physische Optimierung
Kostenbasier-te Auswahl
7
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Ergebnis
Ausführung DBS-Laufzeitsystem
Planparametri-sierung
Code-Erzeugung
QEP
QEP
Code
Verfeinerter Ablauf der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Standardisierung
Optimierung
Anfrage in interner Form
algebraischer Ausdruck auf internen Dateien
Logische Optimierung
Physische Optimierung
Kostenbasier-te Auswahl
Traditionelle Übersetzung,Ergebnis ist ein standardisierter algebraischer Ausdruck auf Relationen und mit Annahme NSM damit auch auf internen Dateien
8
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Planparametri-sierung
QEP
QEP
Code
Verfeinerter Ablauf der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Ergebnis
Standardisierung
Optimierung
Ausführung DBS-Laufzeitsystem
Anfrage in interner Form
algebraischer Ausdruck auf internen Dateien
Logische Optimierung
Physische Optimierung
Kostenbasier-te Auswahl
Code-Erzeugung
Umformung zunächst unabhängig und dann abhängig von Zugriffstrukturen, dann Bewertung der Pläne.
9
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Optimierung
algebraischer Ausdruck auf internen Dateien
Logische Optimierung
Physische Optimierung
Kostenbasier-te Auswahl
Verfeinerter Ablauf der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Ergebnis
Standardisierung
Ausführung DBS-Laufzeitsystem
Planparametri-sierung
Code-Erzeugung
Anfrage in interner Form
QEP
QEP
Code
Bei Standardanfragen wird das Ergebnis von Übersetzung und Optimierung gespeichert. Bei Aufruf muss dann der QEP nur noch geeignet parametrisiert werden.
10
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Standardisierung
Anfrage in interner Form
algebraischer Ausdruck auf internen Dateien
Logische Optimierung
Verfeinerter Ablauf der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Ergebnis
Optimierung
Ausführung DBS-Laufzeitsystem
Planparametri-sierung
Code-Erzeugung
QEP
QEP
Code
Physische Optimierung
Kostenbasier-te Auswahl
Sofern QEP nicht vom Laufzeitsystem interpretiert wird, muss er in ausführbaren Code übersetzt werden.
11
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.2Kapitel 10.2
AnfrageübersetzungAnfrageübersetzung
12
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Stellung in der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Ergebnis
Standardisierung
Optimierung
Ausführung DBS-Laufzeitsystem
Planparametri-sierung
Code-Erzeugung
Anfrage in interner Form
algebraischer Ausdruck auf internen Dateien QEP
QEP
Code
Logische Optimierung
Physische Optimierung
Kostenbasier-te Auswahl
13
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Grundsätze
Prinzipielles Vorgehen zur Umsetzung deklarativ imperativ: Definiere Algebra von Operatoren, die einzelne
Algorithmen kapseln und als Basis-Bausteine eines imperativen Programms dienen. Als Operator-Algebra dient (zunächst) die relationale Algebra.
SQL-Ausdrücke werden zunächst standardisiert (in bestimmte Standardformen überführt).
Für die Standardformen erfolgt Übersetzung anhand von Syntaxbaum. Imperative Programme sind dann Bäume von Operatoren. Ordne jeder Grammatikregel der deklarativen Sprache eine
Übersetzungsregel zu, die besagt, wie der äquivalente Operatorbaum zu konstruieren ist.
Operatorbaum ist Eingabe für die Optimierungsphase.
14
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.2.1Kapitel 10.2.1
Standardisierung der SQL-AnfrageStandardisierung der SQL-Anfrage
15
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Bestandteile der Übersetzung
Externes Datenmodell relationaler DBMS bietet: Relation als fundamentalen Datentyp, Sichten, Konsistenzbedingungen, Schutzmechanismen, Anfragesprache SQL.
Übersetzung von SQL-Anfragen in interne Operator-Ausdrücke auf Relationen.
Behandlung von Sichten durch Query modification: Definition wird in Anfrage eingearbeitet.
Überwachung von Konsistenzbedingungen (ggf. zusätzliche Operatoraufrufe) bei Änderungen, gelegentlich Einbau in die Anfrage zur Nutzung bei der Anfragebearbeitung.
Durchsetzung der Schutzmechanismen durch Rechte-Überprüfung bei Übersetzung der Anfrage.
16
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Grundmuster der SQL-Übersetzung
Select-Ausdruck
select A1, A2,..., An
from R1, R2,..., Rm
whereB
wird überführt in:
A1, A2,..., An (B (R1 R2 ... Rm)) .
Wir illustrieren die Vorgehensweise direkt an der SQL-Anfrage.Üblicherweise wird die Transformation an Ausdrücken einer (meist baumartigen) Zwischensprache vorgenommen.
Der Select-Ausdruck muss dazu gewissen Standards genügen, die wir nachfolgend entwickeln Schrittweise Transformation der ursprünglichen Anfrage.
17
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Transformation (1)
Beseitigen konjunktiver Bedingungen:
select A1, A2,..., An from R1, ..., Rm where B
mit B B1 ... Bk (B in disjunktiver Normalform).
Ersetze Anfrage durch
(select A1, A2,..., An from R1, ..., Rm where B1) union(select A1, A2,..., An from R1, ..., Rm where B2) union ... union(select A1, A2,..., An from R1, ..., Rm where Bk) .
18
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Transformation (2)
Select-Ausdruck
select A1, A2,..., An
from R1, R2,..., Rm
whereB
wird überführt in:
A1, A2,..., An (B (R1 R2 ... Rm)) .
Probleme: B kann geschachtelte Anfragen enthalten. Ri kann ein Tabellenausdruck sein, der von R1, ..., Ri-1
abhängt. group by und having-Klauseln müssen berücksichtigt
werden. A1, A2,..., An können Aggregatfunktionen sein.
19
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Behandlung geschachtelter Anfragen (1)
Rückführung von in/not in auf any bzw. all:
Ersetze x in (select A from R1, ..., Rm where B)
durch x =any (select A from R1, ..., Rm where B) .
Ersetze x not in (select A from R1, ..., Rm where B)
durch x <>all (select A from R1, ..., Rm where B) .
20
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Behandlung geschachtelter Anfragen (2)
Rückführung von any und all auf exists bzw. not exists:
Ersetze xany (select A from R1, ..., Rm where B)
durch exists (select from R1, ..., Rm where B and x A) .
Ersetze xall (select A from R1, ..., Rm where B)
durch not exists (select from R1, ..., Rm where B and not x A).
21
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Behandlung geschachtelter Anfragen (3)
Rückführung von not exists auf exists:
Ersetze select A1, A2,..., An from R1, ..., Rm where B and not exists (T)
durch select A1, A2,..., An
from ((select from R1, ..., Rm where B) except (select from R1, ..., Rm where B and exists
(T)))
22
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Behandlung geschachtelter Anfragen (4)
Elimination von exists:
Ersetze select A1, A2,..., An
from R1, ..., Rm
where Band exists (select from Rm+1, ..., Rk where B')
durch select A1, A2,..., An
from R1, ..., Rm, Rm+1, ..., Rk
where B and B' .
23
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Transformation (3)
Select-Ausdruck
select A1, A2,..., An
from R1, R2,..., Rm
whereB
wird überführt in:
A1, A2,..., An (B (R1 R2 ... Rm)) .
Probleme: B kann geschachtelte Anfragen enthalten. Ri kann ein Tabellenausdruck sein, der von R1, ..., Ri-1
abhängt. group by und having-Klauseln müssen berücksichtigt
werden. A1, A2,..., An können Aggregatfunktionen sein.
24
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Allgemeiner Tabellenausdruck im Ergebnis
Standardisiere select auf Attribute:
Ersetze allgemeinen Tabellenausdruck T (z.B. select mit group
by/having, join, values etc.)
durch select
from (T) as R(A1,A2,...,An) ,
wobei R ein frei gewählter, sonst nirgendwo vorkommender Name ist und A1, A2,..., An Namen für die Spalten von T sind.
25
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (1)
FLUGZEUGTYP(FtypId, Name, CockpitCrew, First, Business, Economy)
FLUG(FlugNr, FtypId, von, nach, Entfernung, Abflugzeit, Ankunftszeit, Tage)
BUCHUNG(FlugNr, TicketNr, PlatzNr, Datum)
„Suche nach Flügen, die an irgendeinem Tag überbucht sind“:
select FlugNrfrom FLUG F, FLUGZEUGTYP FTwhere F.FtypId = FT.FtypIdand FT.First + FT.Business + FT.Economy <any
(select count (TicketNr) from BUCHUNG B where B.FlugNr = F.FlugNr group by Datum)
26
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (2)
select FlugNrfrom FLUG F, FLUGZEUGTYP FTwhere F.FtypId = FT.FtypIdand FT.First + FT.Business + FT.Economy <any
(select count (TicketNr) from BUCHUNG B where B.FlugNr = F.FlugNr group by Datum)
Allg. Tabellenausdruck T im Ergebnis select from (T) as R(A1,A2,...,An)
27
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (3)
select FlugNrfrom FLUG F, FLUGZEUGTYP FTwhere F.FtypId = FT.FtypIdand FT.First + FT.Business + FT.Economy <any
(select from (select count (TicketNr)
from BUCHUNG B where B.FlugNr = F.FlugNr group by Datum)
as T(count))
Rückführung von any auf exists:xany (select A from R1, ..., Rm where B) exists (select from R1, ..., Rm where B and x A)
28
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (4)
select FlugNrfrom FLUG F, FLUGZEUGTYP FTwhere F.FtypId = FT.FtypIdand exists
(select from (select count (TicketNr)
from BUCHUNG B where B.FlugNr = F.FlugNr group by Datum)
as T(count)where FT.First+FT.Business+FT.Economy <
T.count)Beseitigen von exists:from R1, ..., Rm from R1, ..., Rm, Rm+1, ..., Rk where B where B and B' and exists (select from Rm+1, ..., Rk where B')
29
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (5)
select FlugNrfrom FLUG F, FLUGZEUGTYP FT,
(select count (TicketNr) from BUCHUNG B where B.FlugNr = F.FlugNr group by Datum) as T(count)
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < T.count
30
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Transformation (4)
Select-Ausdruck
select A1, A2,..., An
from R1, R2,..., Rm
whereB
wird überführt in:
A1, A2,..., An (B (R1 R2 ... Rm)) .
Probleme: B kann geschachtelte Anfragen enthalten. Ri kann ein Tabellenausdruck sein, der von R1, ..., Ri-1
abhängt. group by und having-Klauseln müssen berücksichtigt
werden. A1, A2,..., An können Aggregatfunktionen sein.
31
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Behandlung von from-Abhängigkeiten (1)
Komplikation:
Tabellenausdrücke in from-Klausel können von weiter links stehenden Tabellenausdrücken abhängen. In diesem Fall kann from-Klausel nicht direkt in kart. Produkt
übersetzt werden.
from FLUG F, FLUGZEUGTYP FT,(select count (TicketNr)
from BUCHUNG B where B.FlugNr = F.FlugNr group by Datum) as T(count)
Dann sukzessives Eliminieren von Abhängigkeiten wie bei geschachtelten Anfragen.
32
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Behandlung von from-Abhängigkeiten (2)
Herausfaktorisieren von relationalen Operatoren:
Ersetze from R1, ..., Rm, (T1 union T2)
durch from ((select from R1, ..., Rm, T1)
union (select from R1, ..., Rm, T2)) ,
und analog für intersect, except, join.
33
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Behandlung von from-Abhängigkeiten (3)
Herausfaktorisieren von select:
Ersetze from R1, ..., Rm,
(select E1, ..., En
from Rm+1, ..., Rk
where B)
durch from (select R1., ..., Rm., E1, ..., En
from R1, ..., Rm, Rm+1, ..., Rk
where B)
(ggf. mit Auflösung von Namenskonflikten).
34
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Behandlung von from-Abhängigkeiten (4)
Ebenso mit Gruppierung:
Ersetze from R1, ..., Rm,
(select E1, ..., En
from Rm+1, ..., Rk
where B group by En+1, ..., El
having B')
durch from (select R1., ..., Rm., E1, ..., En
from R1, ..., Rm, Rm+1, ..., Rk
where B group by R1., ..., Rm., En+1, ..., El
having B')
35
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (6)
select FlugNrfrom FLUG F, FLUGZEUGTYP FT,
(select count (TicketNr) from BUCHUNG B where B.FlugNr = F.FlugNr group by Datum) as T(count)
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < T.count
Herausfaktorisieren von select mit group by
36
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (7)
select FlugNrfrom (select F., FT., count (TicketNr)
from FLUG F, FLUGZEUGTYP FT,BUCHUNG B
where B.FlugNr = F.FlugNr group by F., FT., Datum) as DFT(F.,FT.,count)
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < DFT.count
DFT(F.,FT.,count) ist Abkürzung.Genauer: Anstelle von F.* und FT.* hat man sich die gesamte Folge der Attribute vorzustellen, DFT hat also 15 Attribute.
37
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Fazit: Standardisiertes Ergebnis
Sukzessive Anwendung vorhergehender Regeln führt schließlich auf einfache Anfragen, d.h. Anfragen der Form:
einzelne Basistabelle,
einzelnes ungeschachteltes select-Statement (evtl. mit Gruppierung), dessen from-Klausel wieder eine einfache Anfrage ist,
relationale Verknüpfung (union, intersect, except, join) einfacher Anfragen.
38
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.2.2Kapitel 10.2.2
Übersetzung in StandardformÜbersetzung in Standardform
39
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Übersetzungsregeln
select A1, A2,..., An
from R1, R2,..., Rm
where B
R1 R2
R3
Rm
B
A1, A2,..., An
A1, A2,..., An (B (R1 R2 ... Rm))
Basistabellen werden durch Referenzen auf entsprechende Datenstrukturen ersetzt.
Folge einfacher Anfragen in der from-Klausel führt auf kartesisches Produkt.
select-Anweisung (evt. mit Gruppierung) wird in Kombination aus Selektions- und Projektionsoperator auf die from-Klausel übersetzt.
Gruppierung wird in Operator der erweiterten Algebra übersetzt.
Relationale Verknüpfung (union, intersect, except, join) einfacher Anfragen wird in entsprechende relationale Operatoren übersetzt.
40
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (8)
select FlugNrfrom (select F., FT., count (TicketNr)
from FLUG F, FLUGZEUGTYP FT,BUCHUNG B
where B.FlugNr = F.FlugNr group by F., FT., Datum) as DFT(F.,FT.,count)
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < DFT.count
Folge einfacher Anfragen in der inneren from-Klausel
41
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (9)
select FlugNrfrom (select F., FT., count (TicketNr)
from FLUG F FLUGZEUGTYP FT BUCHUNG B
where B.FlugNr = F.FlugNr group by F., FT., Datum) as DFT(F.,FT.,count)
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < DFT.count
Innere where-Klausel
42
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (10)
select FlugNrfrom (select F., FT., count (TicketNr)
from B.FlugNr = F.FlugNr (FLUG F FLUGZEUGTYP FT BUCHUNG B)
group by F., FT., Datum) as DFT(F.,FT.,count)
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < DFT.count
Gruppierung
43
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (11)
select FlugNrfrom (select F., FT., count (TicketNr)
from F., FT., Datum (B.FlugNr = F.FlugNr (FLUG F
FLUGZEUGTYP FT BUCHUNG B))
) as DFT(F,FT,count)
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < DFT.count
Innere select-Klausel
44
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (12)
select FlugNrfrom (F., FT., count (TicketNr) (
F., FT., Datum (B.FlugNr = F.FlugNr (FLUG F
FLUGZEUGTYP FT BUCHUNG B))
)) as DFT(F,FT,count)
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < DFT.count
Übersetzung der as-Klausel durch Rename-Operator auf die DFT-Attribute
45
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (13)
select FlugNrfrom F.,FT.,count (F., FT., count (TicketNr) (
F., FT., Datum (B.FlugNr = F.FlugNr (FLUG F
FLUGZEUGTYP FT BUCHUNG B))))
where F.FtypId = FT.FtypIdand FT.First+FT.Business+FT.Economy < DFT.count
Verbleibende where-Klausel
46
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (14)
select FlugNrfrom F.FtypId = FT.FtypId FT.First+FT.Business+FT.Economy < DFT.count (
F.,FT.,count (F., FT., count (TicketNr) (
F., FT., Datum (B.FlugNr = F.FlugNr (FLUG F
FLUGZEUGTYP FT BUCHUNG B)))))Streng genommen stehen hier
die umbenannten DFT-Attribute
Verbleibende select-Klausel
47
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (15)
F.FlugNr (F.FtypId = FT.FtypId FT.First+FT.Business+FT.Economy < count (F.,FT.,count (F., FT., count (TicketNr) ( F., FT., Datum (B.FlugNr = F.FlugNr (FLUG F FLUGZEUGTYP FT
BUCHUNG B))))))
Streng genommen steht hier das umbenannte DFT-Attribut
48
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel (16)
Endergebnisals Operatorbaum:
FLUG F FLUGZEUGTYP FT BUCHUNG B
F.FlugNr
F.FtypId = FT.FtypId FT.First+FT.Business+FT.Economy < count
F., FT., count
F., FT., count (TicketNr)
F., FT., Datum
B.FlugNr = F.FlugNr
F.FlugNr (F.FtypId = FT.FtypId FT.First+FT.Business+FT.Economy < count (F.,FT.,count (F., FT., count (TicketNr) ( F., FT., Datum (B.FlugNr = F.FlugNr (FLUG F FLUGZEUGTYP FT
BUCHUNG B))))))
49
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.3Kapitel 10.3
Logische AnfrageoptimierungLogische Anfrageoptimierung
50
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Stellung in der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Ergebnis
Standardisierung
Optimierung
Ausführung DBS-Laufzeitsystem
Planparametri-sierung
Code-Erzeugung
Anfrage in interner Form
algebraischer Ausdruck auf internen Dateien QEP
QEP
Code
Logische Optimierung
Physische Optimierung
Kostenbasier-te Auswahl
51
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Anordnung der Operatoren gemäß
Ziel: „Optimizing the average case“.
Hauptregel: „Halte die Zwischenergebnisse so klein wie möglich.“ Regel kann im Einzelfall auch nachteilig sein.
Umsetzung der Hauptregel
, vor ⋈, , ,… ausführen, denn und verringern den Umfang,
⋈, … “blähen“ oft die Zwischenrelationen auf.
Systematische Vorgehensweise:
Anwendung algebraischer Äquivalenzen.
Grundgedanke
52
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
1. 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 Attribute A1, …, An der Projektionsliste bezieht, können die beiden Operationen vertauscht werden
c(A1, …, An(R)) A1, …, An
(c(R))
Algebraische Äquivalenzen (1)
53
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
5. Die Operationen , ⋈, und sind kommutativ
6. 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 AB, mit A ein Attribut von R und B ein Attribut aus S.
c(R S) R ⋈c S
Algebraische Äquivalenzen (2)
54
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
7. Vertauschen von mit ⋈ oder
Falls das Selektionsprädikat c nur auf Attribute der Relation R zugreift, kann man die beiden Operationen vertauschen:
c(R ⋈p S) c(R) ⋈p S
c(R S) c(R) 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 ⋈p S) c1(R) ⋈p c2(S)
c(R S) c1(R) c2(S)
Algebraische Äquivalenzen (3)
55
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
8. Vertauschung von mit ⋈
Die 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 ⋈c S) (A1, …, An(R)) ⋈c (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 ⋈c S) A1', …, Ap', B1', …, Bq'((A1, …, An, A1', …, Ap'(R))
⋈c (B1, …, Bn, B1', …, Bq'(S)))
Für die -Operation gibt es kein Prädikat, so dass die Einschränkung entfällt.
Algebraische Äquivalenzen (4)
56
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
9. Die Operationen ⋈, , , sind jeweils assoziativ. Wenn also eine dieser Operationen bezeichnet, so gilt:
(R S) T R (S T)
10. Die Operation ist distributiv mit , , . Falls eine dieser Operationen bezeichnet, gilt:
c(R S) (c(R)) (c(S))
11. Die Operation ist distributiv mit mit , , . Falls eine dieser Operationen bezeichnet, gilt:
L(R S) (L(R)) (L(S))
12. Die Join- und Selektionsprädikate können mittels de Morgan's Regeln umgeformt werden:
(c1 c2) (c1) (c2)
(c1 c2) (c1) (c2)
Algebraische Äquivalenzen (5)
57
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
c1c2 ... cn (R) c1
(c2(…(cn
(R)) …))
c1(c2
((R)) c2(c1
((R))
L1(L2
(…(Ln(R)) …)) L1
(R)
c(A1, …, An(R)) A1, …, An
(c(R))
R S S R (⋈, , , )
c(R S) R ⋈c S
c(R S) c(R) S (⋈, )
c(R S) c1(R) c2
(S) (⋈, )
L(R ⋈c S) (A1, …, An(R)) ⋈c (B1, …, Bn
(S))
L(R ⋈c S) L((A1, …, An, A1', …, An'(R)) ⋈c (B1, …, Bn, B1', …, Bn'(S)))
(R S) T R (S T) (⋈, , , )
c(R S) (c(R)) (c(S)) (, , )
L(R S) (L(R)) (L(S)) (, , )
Anwendung als TransformationsregelnZerlegen/Zusammenfassen in Kaskaden von -Operationen
Beseitigen von (zu ⋈)
Projektionsoperationen soweit „nach unten“ wie möglich
Zerlegen/Zusammenfassen in Kaskaden von -Operationen
Blattknoten so vertauschen, dass der mit dem kleinsten Zwischenergebnis zuerst
ausgewertet wird
Selektionsoperationen soweit „nach unten“ (so früh) wie möglich
58
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispielanfrage (1)
EMPLOYEE(Fname, Lname, SSN, Bdate, Address, Sex, Salary, DNO)
PROJECT(Pname, Pnumber, Plocation, Dnum)
WORKSON(ESSN, PNO, Hours)
Finde den Nachnamen der Angestellten, die nach dem 16.4.58 geboren wurden und an einem Projekt namens „GOM“ arbeiten.
select Lnamefrom Employee, WorksOn, Projectwhere Pname = 'GOM'and Pnumber = PNOand ESSN = SSNand Bdate > 58.04.16
59
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Ergebnis der Übersetzung
Beispieloptimierung (1)select Lnamefrom Employee, WorksOn, Projectwhere Pname = 'GOM'and Pnumber = PNOand ESSN = SSNand Bdate > 58.04.16
Lname
Pname=‘GOM‘ Pnumber = PNO ESSN= SSN Bdate > 58.04.16
EMPLOYEE WORKS_ON
PROJECT
60
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Anwendung der Regeln c1c2 ... cn (R) c1
(c2(…(cn
(R)) …))
und c(R S) c1(R) c2
(S)
um Selektionen an die tiefste Stelle zu verschieben, an denen die für die Auswertung des Selektionsprädikats benötigten Attribute verfügbar sind.
Beispieloptimierung (1)
Pnumber = PNO
EMPLOYEE
WORKS_ON
PROJECT
Pname=‘GOM‘ESSN=SSN
Bdate>58.04.16
Lname
61
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Anwendung der Regeln R ⋈ S S ⋈ R
und (R ⋈ S) ⋈ T R (S ⋈ T)
um restriktivere Join-Operationen vor weniger restriktiven anwenden zu können.
Beispieloptimierung (1)
PROJECT
WORKS_ON
EMPLOYEE
Lname
Pnumber = PNO
ESSN=SSN
Pname=‘GOM‘
Bdate>58.04.16
62
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Anwendung der Regel c(R S) R ⋈c S
Beispieloptimierung (1)
PROJECT
WORKS_ONEMPLOYEE
Lname
⋈Pnumber = PNO
⋈ESSN=SSN
Pname=‘GOM‘
Bdate>58.04.16
63
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Anwendung der Regel
L(R ⋈c S) L((A1, …, An, A1', …, An'(R)) ⋈c (B1, …, Bn, B1', …, Bn'(S)))
um die Operanden frühzeitig auf die oberhalb noch benötigten Attribute einzuschränken.
Beispieloptimierung (1)
Lname
PROJECT
WORKS_ON
EMPLOYEE
⋈Pnumber = PNO
⋈ESSN=SSN
Pname=‘GOM‘
Bdate>58.04.16
Pnumber ESSN,PNO
SSN,LnameESSN
64
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispielanfrage (2)
STUDENTEN(MatrNr, Name, Semester)
VORLESUNGEN(VorlNr, Titel, SWS, gelesenVon)
PROFESSOREN(PersNr, Name, Rang, Raum)
HÖREN(MatrNr, VorlNr)
In welchen Semestern sind die Studenten, die Vorlesungen von Sokrates hören?
select distinct s.Semesterfrom Studenten s, hören h, Vorlesungen v, Professoren pwhere p.Name = 'Sokrates'and v.gelesenVon = p.PersNrand v.VorlNr = h.VorlNr and h.MatrNr = s.MatrNr
65
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Ergebnis der Übersetzung
Beispieloptimierung (2)
select distinct s.Semesterfrom Studenten s, hören h, Vorlesungen v, Professoren pwhere p.Name = 'Sokrates'and v.gelesenVon = p.PersNrand v.VorlNr = h.VorlNr and h.MatrNr = s.MatrNr
p.Name = ‘Sokrates‘ v.gelesenVon = p.PersNr v.VorlNr = h.VorlNr h.MatrNr = s.MatrNr
s.Semester
STUDENTEN
HÖRENVORLESUNGEN
PROFESSOREN
66
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Anwendung der Regel c1c2 ... cn (R) c1
(c2(…(cn
(R)) …))
Beispieloptimierung (2)
h.MatrNr = s.MatrNr
s.Semester
STUDENTEN
HÖRENVORLESUNGEN
PROFESSOREN
v.VorlNr = h.VorlNr
p.Name = ‘Sokrates‘
v.gelesenVon = p.PersNr
67
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispieloptimierung (2)Anwendung der Regeln c1
(c2((R)) c2
(c1((R))
und c(R S) c1(R) c2
(S)
um Selektionen an die tiefste Stelle zu verschieben, an denen die für die Auswertung des Selektionsprädikats benötigten Attribute verfügbar sind.
h.MatrNr = s.MatrNr
s.Semester
STUDENTEN
HÖREN
VORLESUNGEN
PROFESSOREN
v.VorlNr = h.VorlNr
p.Name = ‘Sokrates‘
v.gelesenVon = p.PersNr
68
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispieloptimierung (2)
⋈h.MatrNr = s.MatrNr
s.Semester
STUDENTEN HÖREN
VORLESUNGEN PROFESSOREN
⋈v.VorlNr = h.VorlNr
p.Name = ‘Sokrates‘
⋈v.gelesenVon = p.PersNr
Anwendung der Regel c(R S) R ⋈c S
69
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
STUDENTEN(MatrNr, Name, Semester)
VORLESUNGEN(VorlNr, Titel, SWS, gelesenVon)
PROFESSOREN(PersNr, Name, Rang, Raum)
HÖREN(MatrNr, VorlNr)
Beispieloptimierung (2)Anwendung der Regeln R ⋈ S S ⋈ Rund (R ⋈ S) ⋈ T R (S ⋈ T)
um restriktivere Join-Operationen vor weniger restriktiven anwenden zu können (Optimierung der Join-Reihenfolge).
⋈h.MatrNr = s.MatrNr
s.Semester
STUDENTEN
HÖREN
VORLESUNGEN
PROFESSOREN
⋈v.VorlNr = h.VorlNr
p.Name = ‘Sokrates‘
⋈v.gelesenVon = p.PersNr
70
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
STUDENTEN(MatrNr, Name, Semester)
VORLESUNGEN(VorlNr, Titel, SWS, gelesenVon)
PROFESSOREN(PersNr, Name, Rang, Raum)
HÖREN(MatrNr, VorlNr)
Beispieloptimierung (2)Anwendung der Regel
L(R ⋈c S) L((A1, …, An, A1', …, An'(R)) ⋈c (B1, …, Bn, B1', …, Bn'(S)))
um frühzeitig die Tupelgröße einzuschränken.
⋈h.MatrNr = s.MatrNr
s.Semester
STUDENTEN
HÖREN
VORLESUNGEN
PROFESSOREN
⋈v.VorlNr = h.VorlNr
p.Name =‘Sokrates‘
⋈v.gelesenVon = p.PersNr
h.MatrNr
71
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.4Kapitel 10.4
Physische AnfrageoptimierungPhysische Anfrageoptimierung
72
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Stellung in der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Ergebnis
Standardisierung
Optimierung
Ausführung DBS-Laufzeitsystem
Planparametri-sierung
Code-Erzeugung
Anfrage in interner Form
algebraischer Ausdruck auf internen Dateien QEP
QEP
Code
Logische Optimierung
Physische Optimierung
Kostenbasier-te Auswahl
73
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.4.1Kapitel 10.4.1
Einige GrundsätzeEinige Grundsätze
74
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Basisrelationen: 1. Beispielrelationen sind jeweils gemäss dem NSM in einer
Datei gespeichert, und 2. es sind zusätzlich Indexdateien eingerichtet (Primärindex:
satzschlüsselbasiert, Sekundärindex: Wert nicht satzidentifizierend, Clusterindex: zusätzlich Sätze in geballter Liste), oder
3. gelegentlich ist die Datei nach einem Hashverfahren abgelegt.
Zwischenergebnisse: Hier besteht im Grundsatz Wahlfreiheit bei der
Dateiorganisation. Daher kann es zum Einfügen weiterer Operatoren wie z.B.
Sortierung, Index-Generierung kommen. Somit kann sich der Operatorbaum gegenüber der logischen
Optimierung verändern.
Spielräume bei den Daten
75
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Zuordnen physischer Operatoren: Den Operatoren im Operatorbaum müssen
Implementierungen (konkrete Algorithmen) zugeordnet werden.
Die Zuordnung richtet sich bei den Operatoren auf den Blättern (den gespeicherten Relationen) nach deren statisch vorgegebener Dateiorganisation.
Die freie Wahl der Dateiorganisation bei den Zwischenrelationen spiegelt sich in einer entsprechenden Wahlfreiheit bei der Zuordnung der Algorithmen wider.
Spielräume bei den Operatoren
76
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Materialisierung: Jeder Knoten wird voll abgearbeitet bevor das Ergebnis
weitergereicht wird. Ergebnis muss daher auf Hintergrundspeicher aufgebaut
werden. Fließverarbeitung (Pipeline):
Ein Operator leitet jedes Ergebnistupel sofort an seinen übergeordneten Operator weiter. Vorteil: Reduktion des Speicherplatzes für die
Zwischenergebnisse, verzahnte Ausführung.
Probleme: Tupelstrom kann an blockierenden Operatoren (Pipeline
Breaker) aufgehalten werden. Das langsamste Glied in der Kette bestimmt die
Geschwindigkeit: Pufferung gelegentlich erforderlich. Daher u.U. Ausweichen auf Hintergrundspeicher notwendig.
Verarbeitungsvarianten (1)
77
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Fließverarbeitung schematisch
Verarbeitungsvarianten (2)
R S
...
...
...
T
...
...
...
78
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Pipeline-Breaker mit Materialisierung
Verarbeitungsvarianten (3)
R S
...
...
...
T
...
...
...
79
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Verarbeitungsvarianten (4)
Pipeline-Breaker: Unäre Operationen
sort Duplikatelimination (unique,distinct) Aggregatoperationen (min,max,sum,...)
Binäre Operationen Mengendifferenz
Je nach Implementierung Join Union
80
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Einheitliche Behandlung jedes Knotens:
Vereinheitlichung der Operatoren (1)
Initialisieren, Öffnen der benötigten Eingaben
Beschaffen des nächsten Eingabetupels
(nutzt scan-Operator)
Aufräumen, Schließen der Iteratoren der Eingaberelation, Freigabe von
Speicher, bei Blockieren: Weitergabe des kompletten Ergebnisses
Angaben zur Selektivität
Angaben zu den Kosten
Realisiert beispielsweise über Klassen
81
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel:Pull-basierte Fließverarbeitung
Vereinheitlichung der Operatoren (2)
opennext
ReturnErgebnis
82
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.4.2Kapitel 10.4.2
OperatorzuordnungOperatorzuordnung
83
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
P: Exact Match (Nicht-Schlüssel) oder Range. R mit entspr. Index
P: Exact Match (Schlüssel). R mit entspr. Index
P: Exact Match oder Range. R mit entspr. Index
immer verwendbar
Selektion
P
R
LinearSelect
R
PrimärIndexSelect
R
SekundärIndexSelect
R
ClusterIndexSelect
R
Falls R Zwischenrelation:Ggf. zusätzl. Indexerzeugung
84
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Duplikatelim., R unsortiert
Duplikatelim., R sortiert
Duplikatelim., R mit entspr. Index
immer verwendbar
Projektion
LinearProject
R
SortProj
R
IndexProj
R
Falls R Zwischenrelation: Ggf.zusätzl. Indexerzeugung oder Sortierung
L
RSort
R
85
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
immer verwendbar
Falls R und/oder S unsortiert, zunächst sortieren
S mit entspr. Index, sonst zunächst Aufbau
immer verwendbar
Verbindung
NestedLoop
R S
IndexJoin
R S
Zwischenrelationen müssen ggf. aufbereitet werden
HashJoin
R S
R S
⋈R.A=S.B
Index
R S
MergeJoin
[SortR.A] [SortS.B]
Simple|Grace|Hybrid
86
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Beispiel
⋈h.MatrNr = s.MatrNr
s.Semester
STUDENTEN
HÖREN
VORLESUNGEN
PROFESSOREN
⋈v.VorlNr = h.VorlNr
p.Name = ‘Sokrates‘
⋈v.gelesenVon = p.PersNr
87
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Primärindex auf MatrNr
Sekundärindex auf gelesenVon
Beispiel
STUDENTEN
HÖREN
VORLESUNGEN
PROFESSOREN
LinearSelect (p.Name = ‘Sokrates‘)
IndexJoin(v.gelesenVon =
p.PersNr)
Sort(v.VorlNr)
Sort(h.VorlNr)
MergeJoin(v.VorlNr = h.VorlNr)
IndexJoin(h.MatrNr = s.MatrNr)
LinearProject(s.Semester)
Sort(s.Semester)
SortProject(s.Semester)
88
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Gelegentlich lassen sich Materialisierungen auch durch Verschmelzen von Operatoren vermeiden.
Beispiele: Kombination von Selektion und Projektion. Kombination einer Selektion mit einer Verbindung, etwa
Integration einer Selektion in die äußere Schleife eines Nested-Loop-Join,
Integration von Selektionen in den Merge-Join.
Kombination von Gruppierung und Aggregierung.
Verschmelzen von Operatoren
89
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kapitel 10.5Kapitel 10.5
Kostenbasierte AuswahlKostenbasierte Auswahl
90
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Stellung in der Anfragebearbeitung
Scanner, Parser, Sichtauflösung
deklarative SQL-Anfrage
Auswertungsplan (Query Evaluation Plan, QEP) auf Satzzugriffsstrukturen
Ergebnis
Standardisierung
Optimierung
Ausführung DBS-Laufzeitsystem
Planparametri-sierung
Code-Erzeugung
Anfrage in interner Form
algebraischer Ausdruck auf internen Dateien QEP
QEP
Code
Logische Optimierung
Physische Optimierung
Kostenbasier-te Auswahl
91
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Stellung in der Optimierung
(evtl. schrittweises) Aufspannen des
Suchraums
deklarative SQL-Anfrage
Suche
Äquivalente Pläne
„Bester“ (guter) Plan
Logische Optimierung
Physische Optimierung
RevidierteAusgangssituation
Die Wahl des Auswertungsplans ist ein Optimierungsproblem!Lösungsraum: Mehrere Operatorbäume, um nicht günstige Lösungen vorzeitig auszuschließen.
Erweiterung des Lösungsraums: Diverse Zuordnungen von Algorithmen.
Kostenbasierte Auswahl: Aufwand richtet sich danach wie häufig die angestrebte Lösung wiederholt wird. Hoher Aufwand lohnt nur bei parametrisierten Standardanfragen.
92
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Optimierungskriterien: Für die Optimierung benötigt man eine Kostenfunktion. Sie berechnet die Gesamtkosten der Anfrage aus den
Kostenabschätzung für die Einzeloperationen. Grobe Abschätzungen wurden in Kapitel 9 gegeben.
In die Kostenabschätzung geht die Größe der Zwischenergebnisse zentral ein. Daher spielen die Selektivitätsabschätzungen (siehe Kapitel 9)
eine wichtige Rolle.
Optimierung: Für jeden Kandidat-Auswertungsplan müssen dessen Kosten
abgeschätzt werden. Gesucht sind daher Optimierungsverfahren, die den
Lösungsraum sehr rasch einschränken, ohne dabei allzu viel gute Lösungen zu verlieren.
Kostenbasierte Auswahl (1)
93
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Kostenbasierte Auswahl (2)
(evtl. schrittweises) Aufspannen des
Suchraums
deklarative SQL-Anfrage
Suche
Äquivalente Pläne
„Bester“ (guter) Plan
Logische Optimierung
Physische Optimierung
KostenmodellStatistiken/HistogrammePuffergrößeVerwendeter Rechner
Zielfunktion: Antwortzeit vs. Durchsatz
RevidierteAusgangssituation
94
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Schätzung Tupelzahl
Schätzung Aufwand
Schätzung Aufwand
Schätzung Aufwand
Schätzung Aufwand
Schätzung Aufwand Schätzung Aufwand
Schätzung Aufwand
Schätzung Aufwand
Schätzung Aufwand
Schätzung Tupelzahl
Schätzung Tupelzahl
Schätzung Tupelzahl
Schätzung Tupelzahl
Schätzung Tupelzahl
Schätzung Tupelzahl
Schätzung Tupelzahl
Größe(p)
Größe(v)
Größe(h)
Größe(s)
Kostenabschätzung (Beispiel)
STUDENTEN
HÖREN
VORLESUNGEN
PROFESSOREN
LinearSelect (p.Name = ‘Sokrates‘)
IndexJoin(v.gelesenVon =
p.PersNr)
Sort(v.VorlNr)
Sort(h.VorlNr)
MergeJoin(v.VorlNr = h.VorlNr)
IndexJoin(h.MatrNr = s.MatrNr)
LinearProject(s.Semester)
Sort(s.Semester)
SortProject(s.Semester)
95
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Join-Reihenfolge
Beobachtung: In allen praktischen Anfragen dominieren die Verbindungsoperationen
Optimierung der Reihenfolge dieser Operationen kritisch für die Anfrageoptimierung.
Join-Modell (Graphische Veranschaulichung):
⋈
R S
Äußere (Build-) Relation: Wenn immer möglich die
kleinere Relation
Innere (Probe-) Relation
96
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Join-Bäume (1)
⋈
R1⋈
⋈ R2
R3R4
⋈
R1⋈
⋈R2
R3 R4
⋈
R1
⋈ ⋈
R2 R3 R4
Links-orientierter Baum
Rechts-orientierter BaumBuschiger Baum
97
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Join-Bäume (2)
⋈
R1⋈
⋈ R2
R3R4
⋈
R1
⋈ ⋈
R2 R3 R4
Variantenzahl (n: Zahl der Relationen):
(2(n-1))!
(n-1)!n (2(n-1))!/(n-1)!
2 2
5 1680
10 1,761010
20 4,31027
Teilmenge der buschigen Bäume, daher geringere Variantenzahl.Beispiel n=6:Buschige Bäume: 30.240Links-orientierte Bäume: 720
98
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Join-Bäume (3)
⋈
R1⋈
⋈ R2
R3R4
Links-orientierte Bäume spiegeln das Join-Modell und damit die effizienten Algorithmen wider.
Besitzen besondere Tendenz zur Entwicklung effizienter Auswertungspläne!
Ausreichend zur Entwicklung des Suchraums!
99
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Primärindex auf MatrNr
Sekundärindex auf gelesenVon
Umformung des Beispiels
STUDENTEN
HÖREN
VORLESUNGEN
PROFESSOREN
LinearSelect (p.Name = ‘Sokrates‘)
IndexJoin(v.gelesenVon =
p.PersNr)
Sort(v.VorlNr)
Sort(h.VorlNr)
MergeJoin(v.VorlNr = h.VorlNr)
IndexJoin(h.MatrNr = s.MatrNr)
LinearProject(s.Semester)
Sort(s.Semester)
SortProject(s.Semester)
100
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Greedy-Suche (1)
Konstruiere die Lösung des vollständigen Plans schrittweise, indem mit jedem Schritt der bisher erzeugte Teilplan durch Hinzunahme einer Verbindung so erweitet wird, dass die geringsten Kosten entstehen. Keine Garantie dass der optimale Plan gefunden wird, aber
es wird ein guter Plan gefunden.
Großer Vorteil: Anzahl der zu betrachtenden Pläne ist gering.
101
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Greedy-Suche (2)
Beispiel:
Verbindung der 4 Relationen KUNDE, PRODUKT, LIEFERANT, BESTELLUNG.
Einfache Kostenfunktion: Ergebnisgröße.
102
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Greedy-Suche (3)
Schritt 1:
Plan Ergebnisgröße
KUNDE ⋈ PRODUKT 5.000.000
KUNDE ⋈ LIEFERANT 1.000.000
KUNDE ⋈ BESTELLUNG 20.000
PRODUKT ⋈ LIEFERANT 5.000
PRODUKT ⋈ BESTELLUNG 20.000
LIEFERANT ⋈ BESTELLUNG 2.000.000⋈
LIEFERANTPRODUKTSchritt 2:
Plan Ergebnisgröße
(PRODUKT ⋈ LIEFERANT) ⋈ BESTELLUNG
20.000
(PRODUKT ⋈ LIEFERANT) ⋈ KUNDE 5.000.000
⋈
BESTELLUNG
Schritt 3: KUNDE
⋈
KUNDE
103
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Dynamische Programmierung (1)
Prinzip: Zerlege Problem wiederholt in Teilprobleme. Löse jedes Teilproblem optimiert unter Verwendung
„kleinerer“ Teilprobleme. Dieselbe Lösung kann mehrfach verwendet werden, d.h.
Lösungen werden nur einmal entwickelt.
Anwendung auf R1 ⋈ R2 ... ⋈ ⋈ Rn:
Berechne Lösungen für alle Ri und alle Kombinationen Ri
⋈ Rj (da es jeweils nur eine gibt, sind sie definitionsgemäß optimal).
Erweitere schrittweise von optimierten (k-1)-Kombinationen auf k-Kombinationen (k=3,....n).
104
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Dynamische Programmierung (2)
Standardverfahren in heutigen relationalen Datenbanksystemen!
Jedoch mit effizienter Aufzählung: Anstatt zunächst alle 2-elem, 3-elem, ..., n-elem Pläne
sequentiell zu enumerieren: Effizientes Verschränken.
Frühzeitiges Abschneiden von Lösungswegen.
Beispiel:
Verbindung der 4 Relationen KUNDE (K), PRODUKT (P), LIEFERANT (L), BESTELLUNG (B).
Einfache Kostenfunktion: Ergebnisgröße.
105
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Dynamische Programmierung (3)
Basis:
Menge (k=1) Ergebnisgröße Opt. Plan
{K} 1.000 K
{P} 5.000 P
{L} 100 L
{B} 20.000 B
Menge (k=2) Ergebnisgröße Opt. Plan
{K,P} 5.000.000 K ⋈ P
{K,L} 1.000.000 L ⋈ K
{K,B} 20.000 K ⋈ B
{P,L} 5.000 L ⋈ P
{P,B} 20.000 P ⋈ B
{L,B} 2.000.000 L ⋈ B
106
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Dynamische Programmierung (4)
Menge (k=1) Ergebnisgröße Opt. Plan
{K} 1.000 K
{P} 5.000 P
{L} 100 L
{B} 20.000 B
Menge (k=2) Ergebnisgröße Opt. Plan
{K,P} 5.000.000 K ⋈ P
{K,L} 1.000.000 L ⋈ K
{K,B} 20.000 K ⋈ B
{P,L} 5.000 L ⋈ P
{P,B} 20.000 P ⋈ B
{L,B} 2.000.000 L ⋈ B
Induktion (links-orientiert):
In diesem Beispiel weiter verfolgt
107
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Dynamische Programmierung (5)
Induktion (links-orientiert):
Menge (k=3) Ergebnisgröße Opt. Plan
{K,B,L} 2.000.000 (K ⋈ B) ⋈ L
{K,B,P} 20.000 (K ⋈ B) ⋈ P
{P,L,K} 5.000.000 (L ⋈ P) ⋈ K
{P,L,B} 20.000 (L ⋈ P) ⋈ B
Summe der bisher in den Zwischenergebnissen aufgelaufenen Kosten.
Opt. Plan Kosten
(K ⋈ B) ⋈ L 2.020.000
(K ⋈ B) ⋈ P 40.000
(L ⋈ P) ⋈ K 5.005.000
(L ⋈ P) ⋈ B 25.000 ((L ⋈ P) ⋈ B) ⋈ K
Letzter Schritt: k=4 ({K,P,L,B}), also nur 1 Ergebnisgröße.
108
© 2009 Univ,Karlsruhe, IPD, Prof. Lockemann DBI 10
Dynamische Programmierung (6)
⋈
PRODUKTLIEFERANT
⋈
BESTELLUNG
⋈
KUNDE
((L ⋈ P) ⋈ B) ⋈ K