Aufgabe 1: Block Nested Loop Join (1 P.) Aufgabe 2: Grace Hash

Datenbanksysteme WS 2015/16
Prof. Dr.-Ing. Sebastian Michel
MSc. Manuel Hoffmann
TU Kaiserslautern, FB Informatik – Lehrgebiet Informationssysteme
Übungsblatt 3: Ausgabe 10.11.2015, Präsentation 18.11.2015
Aufgabe 1: Block Nested Loop Join
http://dbis.informatik.uni-kl.de
(1 P.)
Gegeben sind die Relationen User und Comment über die ein Block Nested Loop Join (ohne Hashtabelle)
durchgeführt wird, bei welchem ein größerer Chunk“ an Seiten auf einmal übertragen wird. Es gibt 2286
”
Benutzer und 13970 Einträge in der Kommentar-Tabelle. Die Tupel beider Relationen sind jeweils eine
Seite groß, der zur Verfügung stehende Join-Puffer fasst 256 Seiten.
(a) Welche Chunkgröße wird gewählt? Berechnen Sie die Anzahl der Seitenzugriffe auf die Festplatte für
beide Möglichkeiten der Wahl der äußeren Relation.
(b) Betrachten Sie außerdem eine alternative Implementierung, bei der der Join-Puffer gleichmäßig mit
Seiten der inneren und äußeren Join-Tabelle gefüllt wird. Wie müssen Sie das Kostenmodell anpassen?
Wie hoch sind die Kosten, die in ihrem Model beim Join zwischen User und Comment verursacht werden?
(c) Wandeln Sie die beiden Modelle aus (a) und (b) so um, dass nicht mehr einzelne Seitenzugriffe auf
die Festplatte gezählt werden, sondern konsekutive Seitenzugriffe. Das heißt, wenn Sie in einem Schritt
auf die Seiten A, B, C, D zugreifen, soll dies als 1 Zugriff gezählt werden und nicht als 4. Berechnen Sie
auch hier den Unterschied, den die Wahl der äußeren Relation hervorruft.
Aufgabe 2: Grace Hash Join
(1 P.)
Gegeben zwei Relationen R und S, die wie folgt verlustfrei gejoint werden sollen: R.a ./ S.b. R habe
100.000 Tupel mit unique Werten für a, S habe 500.000 Tupel mit gleichverteilten Werten für b. Die
Breite der Tupel sei so groß wie eine Seite. Der Join-Puffer habe Platz für 80 Seiten wobei beliebig
viel zusätzlicher Platz für eine Hashtabelle ist. Als Hashfunktion für die Partitionierung wird mod k
verwendet, gehen Sie davon aus, dass a ⊆ N, b ⊆ N.
Wie wird k am geschicktesten gewählt, um den Grace Hash Join möglichst effizient auszuführen? Für Ihr
k, wie viele lesende Seitenzugriffe sind nötig? Aus wie vielen sequentiellen Leseoperationen setzten sich
diese zusammen? Wie viele Seitenzugriffe sind das verglichen mit dem Block Nested Loop Join?
Aufgabe 3: Select Distinct
(1 P.)
Geben Sie die Implementierung eines Operators in Pseudocode an, der select distinct Anfragen auf genau einem Attribut (zum Beispiel: select distinct firstname from students) korrekt und möglichst
effizient beantwortet. Sie können folgende Parameter bei der Implementierung benutzen:
• Basisrelation: R
• Attributname: a
• Puffergröße: nB
• Größe von R in Seiten: nR
• Liste der verfügbaren (B+ -Baum-)Indexe I
Erläutern Sie, wie viele Seitenzugriffe dieser Algorithmus benötigt unter der Annahme, dass eine Seite
genau ein Tupel aus R fasst, und dass jedes Attribut eine viertel Seite groß ist. Anstelle von Worst- oder
Average-Case Analyse für den gesamten Algorithmus, beschreiben Sie, wie teuer dieser unter verschiedenen Voraussetzungen ist.
1
Datenbanksysteme WS 2015/16
Prof. Dr.-Ing. Sebastian Michel
MSc. Manuel Hoffmann
TU Kaiserslautern, FB Informatik – Lehrgebiet Informationssysteme
Übungsblatt 3: Ausgabe 10.11.2015, Präsentation 18.11.2015
http://dbis.informatik.uni-kl.de
Aufgabe 4: Abfragekosten
(1 P.)
Gegeben eine Relation R mit Primärattribut a. Vier Tupel dieser Relation passen in eine Seite, jedes
Tupel besteht aus vier gleichgroßen Attributen und select count(*) from R ergibt 200.000. Alle Indexe
sind B+ -Bäume mit Höhe h, deren Blattknoten acht Attribute zusammen mit Verweisen auf Datenseiten
fassen. Die Blattknoten sind komplett gefüllt. Gehen Sie von einem kleinen Puffer aus, sodass sie höchstens
ein paar aufeinanderfolgende Seitenzugriffe ohne Zugriff auf die Festplatte durchführen können.
(a) Geben Sie die Kosten in Seitenzugriffen für die Abfrage select * from R bei Verwendung des clustered
Primärindexes an.
(b) Was würde select * from R kosten, wenn der Optimierer sich für einen Sekundärindex entscheidet?
(c) Sei nun select b from R die Anfrage nach einem Nicht-Primärattribut b. Was kostet diese Anfrage bei
Verwendung eines Sekundärindex über b?
(d) Was kostet die selbe Anfrage, wenn die Tabelle zuvor nach b geclustert wurde?
2

Download Report