SS 2004B. König-Ries: KuD6-1 Kapitel 6: Anfragebearbeitung physische Datenstrukturen: B-Bäume Anfragebearbeitung Folien: © Prof. Lockemann, IPD, Uni Karlsruhe

SS 2004 B. König-Ries: KuD 6-1

Kapitel 6: Anfragebearbeitung

physische Datenstrukturen: B-Bäume

AnfragebearbeitungFolien: © Prof. Lockemann, IPD, Uni Karlsruhe

© Prof. Kemper, TU München (Begleitmaterial zu Kapitel 7 des Lehrbuchs)


Referenzarchitektur

Externes Datenmodell

Anfragebearbeitung

Internes Datenmodell

Satz- u. Satzmengenverwaltung

Physische Datenstrukturen

Zugriffsschicht

Hauptspeicherseiten u. Segmente

Dateien

Dateiverwaltung

Geräteschnittstelle

Scheduler

Recovery-Verwalter

Segment- u. Pufferverwaltung


betrachtete Aspekte


Anfragebearbeitung




Zugriffsschicht


Dateien

Dateiverwaltung


Scheduler

Recovery-Verwalter




physische Datenstrukturen: B-Bäume



Referenzarchitektur


Anfragebearbeitung




Zugriffsschicht


Dateien

Dateiverwaltung


Scheduler

Recovery-Verwalter



S.. SuchschlüsselD..

Weitere Daten

V.. Verweise (SeitenNr)




Einfügen eines neuen Objekts (Datensatz) in einen B-Baum


Sukzessiver Aufbau eines B-Baums vom Grad k=2

10 13 19

7



7 10 13 19

3



7 10 13 19

3

?



7 10

3

13 19

?



3 7

3

13 19

?10



3 7 13 19

?10



3 7 13 19

?10

1



3 7 13 19

?10

1



3 7 13 19

?10

1



1 3 7 13 19

?10

1



1 3 7 13 19

?10

2



1 3 7 13 19

?10

2

2



1 2 3 7 13 19

?10

2

2



1 2 3 7 13 19

?10

4



1 2 3 7 13 19

?10

4

4



1 2 3 7 13 19

?10

4

4



1 2 3 7 13 19

?10

4

4



1 2 3 7 13 19

?3 10

4

4



1 2 13 19

?3 10

4 7



1 2 13 19

?3 10

11

4 7



1 2 11 13 19

?3 10

4 7



1 2 11 13 19

?3 10

21

4 7



1 2 11 13 19

?3 10

21

4 7



1 2 11 13 19 21

?3 10

12

4 7



1 2 11 13 19 21

?3 10

12

4 7 12



1 2 11 13 19 21

?3 10

12

4 7 12



1 2 11 13 19 21

?3 10

12

4 7 12



1 2 11 13 19 21

?3 10 13

12

4 7 12



1 2 11 19 21

?3 10 13

12

4 7 11 12



1 2 19 21

?3 10 13

12

4 7 11 12



1 2 19 21

?3 10 13

14

4 7 11 12



1 2 14 19 21

?3 10 13

14

4 7 11 12



1 2 14 19 21

?3 10 13

15

4 7 11 12



1 2 14 15 19 21

?3 10 13

20

4 7 11 12



1 2 14 15 19 21

?3 10 13

20

4 7 11 12

20



1 2 14 15 19 21

?3 10 13

20

4 7 11 12

20



1 2 14 15 19 21

?3 10 13 19

20

4 7 11 12

20



1 2 14 15

?3 10 13 19

20

4 7 11 12

20 21



1 2 14 15

?3 10 13 19

5

4 7 11 12

20 21



1 2 14 15

?3 10 13 19

5

4 7 11 12

20 21



1 2 14 15

?3 10 13 19

5

4 5 7 11 12

20 21



1 2 14 15

?3 10 13 19

6

4 5 7 11 12

20 21



1 2 14 15

?3 10 13 19

6

4 5 6 7 11 12

20 21



1 2

14 15

?3 10 13 19

4 5 6 7 11 12

20 21

8



1 2

14 15

?3 10 13 19

4 5 6 7 11 12

20 21

8

8



1 2

14 15

?3 10 13 19

4 5 6 7 11 12

20 21

8

8



1 2

14 15

?3 10 13 19

4 5 6 7 11 12

20 21

8

8



1 2

14 15

?3 10 13 19

6 7 11 12

20 21

8

84 5



1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

64 5



1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

4 5



1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

4 5



1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

4 5



1 2

14 15

?3 10 13 19

7 8 11 12

20 21

6

4 5

3 6



1 2

14 15

?13 19

7 8 11 12

20 21

10

4 5

3 6



1 2

14 15

?13 19

7 8 11 12

20 21

4 5

3 6

10



1 2

14 15

?13 19

7 8 11 12

20 21

4 5

3 6

10

10


eigentlich…

.. geht es jetzt noch weiter. Man kann in einen Baum nämlich nicht nur einfügen, sondern auch

daraus löschen. Das ist aber nicht ganz einfach, lassen wir hier mal weg. Bei Interesse können Sie das Verfahren in jedem Datenbanklehrbuch

(z.B. dem von Kemper/Eickler) nachlesen.


Verwendung eines B-Baums

1 2

14 15

?13 19

7 8 11 12

20 21

4 5

3 6

10

10



physische Datenstrukturen



Implementierung der relationalen Operatoren

Relationale Operatoren können durch Satzmengenverwaltung nicht direkt ausgeführt werden, da diese nur navigierende Such- und Zugriffsoperationen für individuelle Kollektionen anbietet.

Anfragebearbeitung muss deshalb geeignete Operator-Implementierung auswählen, die die Funktionalität des Operators möglichst effizient erbringt.

Kritisch ist vor allem Implementierung der binären Operatoren (Verbindung, Vereinigung, Durchschnitt, Differenz), da potenziell quadratische Laufzeit.


Selektion (1)

Sequenzielle Selektion Schleife über alle Tupel der Relation. Ergebnis-Satzmenge kann vollständige Datensätze oder nur

Verweise (Satz-Identifikatoren) auf qualifizierende Ausgangs-Datensätze enthalten.

Aufwand O(|R|), wobei R Eingaberelation. Bei vertikaler Fragmentierung und Einbezug mehrerer Attribute in

die Selektionsbedingung sind ggf. zusätzliche Verbindungen mit entsprechend höherer Laufzeit erforderlich.


Selektion (2)

Indexbasierte Selektion Bei einfacher Selektionsbedingung der Form Attributi Konstante

kann Direktzugriff erfolgen, sofern unterliegende Datenstruktur wertbasierten Zugriff über Attributi unterstützt.

Aufwand O(log|R|) + Anzahl der Ergebnistupel, bei Selektion auf Gleichheit und Einsatz einer Hashtabelle als Indexstruktur sogar O(|1|) + Anzahl der Ergebnistupel.

Bei booleschen Kombinationen von Vergleichen getrennte Auswertung der einzelnen Vergleiche und anschließend Bildung des Durchschnitts bzw. der Vereinigung der Ergebnisse.


Projektion

Sequenzieller Durchlauf, Aufwand O(|R|). Bei Duplikat-Elimination (select distinct) ist anschließender

Sortierlauf und weiterer sequenzieller Durchlauf zur Duplikatentfernung notwendig, Aufwand in diesem Fall O(R log|R|).


Geschachtelte Verbindung (1)

Geschachtelte Schleife, in der jeder Datensatz in Datei R (hier: BUCHUNG) mit jedem Datensatz in S (hier: FLUG) verglichen wird:

Iterator bu = BUCHUNG.createIterator();Tupel tb, tf;while bu.hasNext() {

tb = bu.get();bu.next();Iterator fl = FLUG.createIterator();while fl.hasNext() {

tf = fl.get();fl.next();if tb.flugNr = tf.flugNr then ERG.insert(tbtf);

}}


Geschachtelte Verbindung (2)

Aufwand: Zahl der Satzzugriffe: |R|+(|R||S|) = |R|(1+|S|). Seien auf einer Seite nR bzw. nS Sätze untergebracht. Dann Zahl

der Hintergrundspeicherzugriffe |R|/nR (1+|S|/nS).

R sollte daher die kleinere Relation sein. Erfordert gebündelte Satzspeicherung.


Geschachtelte Verbindung mit Direktzugriff

Geschachtelte Schleife, in der für jeden Datensatz in R der oder die passenden Datensätze in S anhand eines Index aufgefunden werden:

Iterator bu = BUCHUNG.createIterator();Tupel tb, tf;while bu.hasNext() {

tb = bu.get ();tf := FLUG.getKey(flugNr,tb.flugNr);if erfolgreich then ERG.insert(tbtf);bu.next();

}


Geschachtelte Verbindung mit Direktzugriff

Aufwand: Unterliegende Datenstruktur für S muss wertbasierten Zugriff für

die in die Verbindung eingehenden Attribute unterstützen. Aufwand O (|R|) (Hash) oder O(|R| log|S|) (B*-Baum). R (äußere Schleife) sollte daher die kleinere Relation sein. Hash-Join: Zwischenrelation nach einem Hashverfahren erstellen.


Abb. externes internes Datenmodell

Wesentliche Abbildungsaufgaben: Abbildung von Relationen auf Satzmengen, Übersetzung von SQL-Anfragen in interne Operator-Ausdrücke.

Anfrage-Übersetzung erledigt intern: Behandlung von Sichten (Definition wird in Anfrage eingearbeitet), Überwachung von Konsistenzbedingungen (ggf. zusätzliche

Operatoraufrufe), Durchsetzung der Schutzmechanismen (Rechte-Überprüfung bei

Übersetzung der Anfrage). Im Folgenden zunächst Betrachtung der Abbildung von Relationen auf

Satzmengen.


Übersetzung von SQL-Anfragen (1)

Grundsätzliches Problem: SQL ist deklarative Sprache und gibt keinen Algorithmus vor. Intern wird aber ausführbares Programm benötigt.

Prinzipielles Vorgehen zur Umsetzung deklarativ imperativ: Definiere Algebra von Operatoren, die einzelne Algorithmen

kapseln und als Basis-Bausteine eines imperativen Programms dienen.

Imperative Programme sind dann Bäume solcher Operatoren. Ordne jeder Grammatikregel der deklarativen Sprache

Übersetzungsregel zu, die besagt, wie äquivalenter Operatorbaum zu konstruieren ist.

Optimiere aus Übersetzung resultierenden Operatorbaum durch Ausnutzung von Äquivalenz-Beziehungen, die in der Algebra gelten.


Übersetzung von SQL-Anfragen (2)

Konkretes Vorgehen zur Übersetzung von SQL: Als Operator-Algebra dient (zunächst) die relationale Algebra. Da Grammatik von SQL ziemlich komplex ist, werden Ausdrücke

zunächst standardisiert (in bestimmte Standardformen überführt). Für Standardformen erfolgt Übersetzung anhand von Syntaxbaum.

Im folgenden einige Beispiele für einfache Umformungsregeln.


Grundmuster der SQL-Übersetzung

Select-Ausdruck

select A1, A2,..., Anfrom R1, R2,..., Rmwhere B

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.


Grundmuster der SQL-Übersetzung

Select-Ausdruck

select A1, A2,..., Anfrom R1, R2,..., Rmwhere B

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.

ignorieren wir mal…


Einfache Anfragen (2)

Einfache Anfragen können rekursiv in relationale Algebra übersetzt werden: Basistabellen werden durch Referenzen auf die entsprechenden

internen Dateien ersetzt. Eine Folge einfacher Anfragen in einer from-Klausel wird in das

Kartesische Produkt überführt. select-Ausdruck (evt. mit Gruppierung) wird in Kombination aus

Selektions- und Projektionsoperator übersetzt, die auf die übersetzte from-Klausel angewendet werden.

Gruppierung wird dabei als zusätzlicher Operator übersetzt, da in der relationalen Algebra nicht direkt abbildbar.

Relationale Verknüpfung (union, intersect, except, join) einfacher Anfragen wird in entsprechende relationale Operatoren übersetzt.


Übersetzung einfacher Anfragen: Beispiel

Beispiel: Interne Datei FRA_FLÜGE entspricht dem SQL-Ausdruck:select flugNr, nach, abflugszeit, ankunftszeit, ticketNr, datum

from FLUG, BUCHUNG

where von = "FRA"

and FLUG.flugNr = BUCHUNG.flugNr;

Die Anfrage ist bereits einfach und kann geradewegs in den algebraischen Ausdruck

flugNr,nach,abflugszeit,ankunftszeit,ticketNr,datum

(von="FRA" BUCHUNG.flugNr =FLUG.flugNr (BUCHUNG FLUG) )

übersetzt werden.


Anfrageoptimierung (1)

Konkretes Vorgehen nach der Übersetzung von SQL: Erhaltener Operatorbaum wird in algebraischer

Optimierungsphase gemäß Regeln der relationalen Algebra optimiert.

In anschließender nicht-algebraischer Optimierungsphase werden spezifische Operator-Implementierungen ausgewählt und weitere Operatoren wie z.B. Sortierung, Index-Generierung etc. eingefügt.


Algebraische Optimierung (1)

Ziel: Transformation des Operatorbaums in äquivalenten Baum, der effizienter auszuführen ist.

Anwendbare Gesetze der relationalen Algebra (Auszug): Verbindung ist kommutativ und assoziativ. Selektionen und Projektionen können zerlegt und

zusammengefasst werden. Projektion kommutiert mit Selektion, Verbindung und Vereinigung,

solange benötigte Attribute nicht herausprojiziert werden. Selektion kommutiert mit Verbindung, Vereinigung, Differenz und

Gruppierung (solange die Selektionsbedingung sich nur auf die Gruppierungsattribute bezieht).

Kartesisches Produkt gefolgt von Selektion ergibt -Verbindung.



Problem bei der Optimierung: Ausführungskosten eines bestimmten Operatorbaums lassen sich nur schwer schätzen.

Benötigt werden u.a. Informationen über: Größe der Ausgangstabellen, Größe der verbleibenden Tabellen nach Selektion oder Projektion, Treffer-Rate bei einer Verbindung, Ausführungskosten von Operationen (hängen stark von Algorithmus

ab, der aber in dieser Optimierungsphase noch nicht betrachtet wird).

Pragmatisches Vorgehen: Verwende „Kochrezepte“, die mit hoher Wahrscheinlichkeit die Größe der Zwischenergebnisse reduzieren.



Faustformeln für sinnvolle Transformationen: Führe Selektionen so früh wie möglich durch. Spalte Selektionen, die auf Attribute mehrerer Relationen Bezug

nehmen, in eine Folge von Selektionen auf, die jeweils nur auf Attribute einer Relation Bezug nehmen. (Dann lässt sich nämlich die erste Regel besser anwenden.)

Fasse kartesische Produkte und Selektionen möglichst zu -Verbindungen zusammen.

Führe Projektionen so früh wie möglich (aber nach eventuellen Selektionen) aus.

Füge ggf. zusätzliche Projektionen ein, um nicht mehr benötigte Attribute so früh wie möglich zu entfernen.


Algebraische Optimierung: Beispiel

FLUG


von = "FRA" FLUG.flugNr = BUCHUNG.flugNr

BUCHUNG

⋈

von = "FRA"

flugNr, nach, abflugszeit,ankunftszeit

FLUG BUCHUNG

flugNr,ticketNr,datum


Nicht-algebraische Optimierung

Aufgabe: Auswahl geeigneter Operator-Implementierungen sowie weitere Optimierung des Operatorbaums.

Handlungsmöglichkeiten (Auswahl): Einfügen von Sortierläufen, um Mischverbindung zu ermöglichen, Erzeugen eines temporären Index, um Verbindung mit Direktzugriff

zu ermöglichen, Änderung der Reihenfolge von komplexen Selektionsbedingungen, Änderung der Reihenfolge von Verbindungen,

Wesentliches Entscheidungskriterium: Größe der erzeugten Zwischenergebnisse.


Nicht-algebraische Optimierung: Beispiel

FLUG



BUCHUNG

von = "FRA"

INDEX(BUCHUNG)

INDEX(FLUG)


FLUG BUCHUNG

⋈


Nicht-algebraische Optimierung: Beispiel

FLUG



BUCHUNG

von = "FRA"

flugNr, nach, abflugszeit,ankunftszeit

flugNr flugNr

flugNr, ticketNr,datum

FLUG BUCHUNG

⋈

sort sort

Documents

SS 2004B. König-Ries: KuD6-1 Kapitel 6: Anfragebearbeitung physische Datenstrukturen: B-Bäume Anfragebearbeitung Folien: © Prof. Lockemann, IPD, Uni Karlsruhe