Vorlesung Datenbanksysteme vom 18.10.2004 Anfragebearbeitung Logische Optimierung Physische...

Vorlesung Datenbanksysteme vom 18.10.2004Anfragebearbeitung

Logische OptimierungPhysische Optimierung

Architektur eines DBMS

DML-Compiler DDL-Compiler

Abfrageoptimierung

Datenbankmanager

Schemaverwaltung

Dateiverwaltung

Logdateien Indexe Datenbasis Data Dictionary

Mehrbenutzersynchronisation

Fehlerbehandlung

Interactive Abfrage API/Präcompiler Verwaltungswerkzeug

Pull-based Query Evaluation

opennext

ReturnErgebnis

Pipelining vs. Pipeline-Breaker

Pipeline-Breaker

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

Binäre OperationenMengendifferenz

Je nach Implementierung JoinUnion

Beispiele:

Op6 Employee A DNO = Dnumber Department

Op7 Department A MgrSSN = SSN Employee

Zu betrachten allgemein:Implementierungs-Varianten für R AA=B S

JOIN - Implementierung

J1 nested (inner-outer) loop„brute force“-Algorithmus

foreach r Rforeach s S

if s.B = r.A then Res := Res (r s)

Nested Loop Join

Block-Nested Loop Join-Algorithmus

m-k m-k m-k m-k m-kR

kS k k k k k

J2 Zugriffsstruktur auf SIndex Nested Loop Join

in jedem Durchlauf von R werden nur die in S qualifizierenden Tupel gelesen

dazu ist ein Index auf B erforderlich

foreach r Rforeach s S[B=r.A]

Res := Res (r s)

Index Nested Loop Join

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 (wenn Duplikate eliminiert werden)

Sort-Merge-Join

A 5 5 5 6 6 6 7 7 7

R B 4 4 4 5 5 6 7 7 7 8

S A B5 55 55 55 55 55 56 66 66 67 7

Ergebnis:

Mengendurchschnitt mit einem Hash/Partitionierungs-Algorithmus

769013174288

S44179746

•Nested Loop: O(N2)

•Sortieren: O(N log N)

•Partitionieren und Hashing

769013174288

S44179746

90427613882

769013174288

S44179746

90427613882

1344172

769013174288

S44179746

90427613882

1344172

90427613882

1344172

Build-Phase

Hashtabelle

R S = {3, }R3

90427613882

1344172

Probe-Phase

R S = {3, }R3

90427613882

1344172

Build-Phase2. Partition

R S = {3, }R3

90427613882

1344172

Probe-Phase2. Partition

R S = {3, 13 }R3

90427613882

1344172

Probe-Phase2. Partition

769013174288

S44179746

90427613882

1344172

R S = {3, 13, 2, 44, 17 }

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 Bucket

Wird (nach praktischen Tests) nur vom Merge-Join „geschlagen“, wenn die Relationen schon vorsortiert sind

Hash-Join

Ar1 5r2 7r3 8r4 5

R SB 5 s1

h(A) h(B )

Bucket 3Bucket 2Bucket 1

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

receive

Partitionh(R.A)

Partitionh(S.A)

receive

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

Partitionh(R.A)

Hashtabelle

Lade Blöcke von P1

Nested-Loop Join Hash Join

Hybrid Hash-Join Fange so an, als wenn der Build-Input S vollständig in

den Hauptspeicher passen würde Sollte 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

Hybrid Hash-Join

Hashtabelle

Hybrid Hash-Join

Hashtabelle

Hybrid Hash-Join

Hashtabelle

Hybrid Hash-Join

Partitionh(R.A) P2

Hashtabelle

Wenn r zur ersten Partition

gehört

111100

111100 False

Join mit Hashfilter(Bloom-Filter)

Join mit Hashfilter(False Drop Abschätzung)

Wahrscheinlichkeit, dass ein bestimmtes Bit j gesetzt istW. 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..

Vergleich: Sort/Merge-Join versus Hash-Join

R run run S

merge m

R partition partition S

Illustration: Externes Sortieren

971735

317975

Mehrstufiges Mischen / Merge

Level 0

Level 1

Level 2

Replacement Selection während der Run-Generierung

971735

Ersetze Array durch Einen Heap

971735

1-97 1-3

971735

1-97 1-17

971735

1-97 1-17

971735

1-97 1-17

971735

1-97 1-17

971735

1-97 1-17

971735

1-97 1-17

971735

1-97 1-27

971735

1-97 1-27

971735

1-97 1-27

Nächster Run, kleiner

als 17

971735

1-97 1-27

Nächster Run, kleiner

als 17

971735

1-97 2-16

971735

1-97 2-16

971735

1-97 2-16

971735

1-97 2-16

971735

172797

2-2 2-16

971735

172797

2-2 2-16

971735

17279799

2-2 2-16

971735

17279799

2-2 2-16

971735

17279799

2-13 2-16

971735

172797992

2-13 2-16

Implementierungs-Details Natürlich darf man nicht einzelne Datensätze zwischen

Hauptspeicher und Hintergrundspeicher transferieren Jeder „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) ??

Übersetzung der logischen Algebra

AR.A=S.B

HashJoinR.A=S.B

MergeJoinR.A=S.B

[SortR.A] [SortS.B]

IndexJoinR.A=S.B

[HashS.B | TreeS.B]

NestedLoopR.A=S.B

[Bucket]

SelectP

IndexSelectP

[NestedDup]

Projectl

[SortDup]

Projectl

[IndexDup]

[Hash | Tree]

Projectl

Ein AuswertungsplanEin Auswer-tungsplan

Wiederholung der Optimierungsphasenselect 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

p.Name = ´Sokrates´ and ...

s.Semester

As.MatrNr=h.MatrNr

Ap.PersNr=v.gelesenVon

s.Semester

p.Name = ´Sokrates´

Av.VorlNr=h.VorlNr

Vorlesung Datenbanksysteme vom 18.10.2004 Anfragebearbeitung Logische Optimierung Physische...

Documents

Informationsintegration Containment und Local-as-View Anfragebearbeitung 12.1.2006 Felix Naumann

Datenbanksysteme 1 - fj-strube.de

Kapitel 8 Anfragebearbeitung Logische Optimierung Physische Optimierung Kostenmodelle „Tuning“

SQL - Zusammenfassung DATENBANKSYSTEME FÜR HÖRER ANDERER FACHRICHTUNGEN

Kapitel 8 Anfragebearbeitung · 2015. 11. 23. · Kapitel 8 Anfragebearbeitung Logische Optimierung Physische Optimierung Kostenmodelle ... Mittels Regel 8 werden die Blattknoten

Optimierung von Anfragen an verteilte Datenbanksysteme

Vorlesung Datenbanksysteme vom 18.11.2015 Anfragebearbeitung 2 Architektur eines DBMS Logische Optimierung Physische Optimierung Kostenmodelle

02.11.2013FB Info - H. Härtl1 Datenbanksysteme Einführung

Übung Datenbanksysteme II Index- strukturen Thorsten Papenbrock

Kapitel 8 Anfragebearbeitung Logische Optimierung Physische Optimierung Kostenmodelle Tuning

Kapitel 3: Datenbanksysteme - uni-muenchen.de...DATABASE SYSTEMS GROUP Einführung in die Informatik: Systeme und Anwendungen – SoSe 2009 Kapitel 3: Datenbanksysteme 3 • Arbeiten

Grundlagen der Datenbanksystem I - Konzeptuelles Datenbank ... · Logische Optimierung Grundlagen der Datenbanksysteme I VIII-4 Grundlegende Aspekte Zu betrachten sind für eine Optimierung

WS 2014/15 Datenbanksysteme Do 17:00 – 18:30 R 0.005 Vorlesung #10 Anfragebearbeitung

SS 2004B. König-Ries: Datenbanksysteme2-1 Kapitel 2: Referenzarchitektur für Datenbanksysteme Methodischer Architekturentwurf Architekturentwurf für Datenbanksysteme

5. Schema-Architekturen verteilter Datenbanksysteme · P. Dadam, 1999 - Verteilte Datenbanken und Client/Server-Systeme 5. Schema-Architekturen verteilter Datenbanksysteme 5-1 5

Vorlesung Datenbanksysteme Gliederung

Kapitel 8 Anfragebearbeitung - uni-due.de · 2016. 2. 4. · Kapitel 8 Anfragebearbeitung Logische Optimierung ... Mittels Regel 8 werden die Blattknoten so vertauscht, dass derjenige,

5. SQL: Erstellen von Tabellen Erzeugen und Löschen von ...home.edvsz.hs-osnabrueck.de/skleuker/WS12_DB/Datenbanksysteme… · Datenbanksysteme Prof. Dr. Stephan Kleuker 108 Anmerkungen

Datenbanksysteme I Anfragebearbeitung und -optimierung · PDF fileSQL Anfrage. Überblick Parsen der Anfrage Transformationsregeln der RA Optimierung Kostenmodelle ... Gilt jeweils

Übung Datenbanksysteme II Index- strukturen