Übungsaufgaben

18 Parallele Anfragebearbeitung

Übungsaufgaben

Aufgabe 18-1: Parallele Join-Berechnung

: Relation R (1 Million Tupel) sei an 4 Rechnern (n=4), Relation S (100.000 Tupel) an 2 Rechnern (m=2) gespeichert. Wie hoch ist der Kommunikationsumfang (in MB) für die Datenumverteilung zur parallelen Join-Berechnung

für dynamische Replikation
für dynamische Partitionierung und 5 Join-Rechner (p=5)
für dynamische Partitionierung, wenn für S das Verteil- mit dem Join-Attribut übereinstimmt, nicht jedoch für R ?

: Die Tupelgröße betrage 100 B.
: (Lösung Aufgabe 18-1:)

Aufgabe 18-2: Mindest-Hauptspeichergröße für partitionierten Hash-Join

Der GRACE-Hash-Join partitioniert S und R in q Partitionen, falls die kleinere Relation S nicht in den Hauptspeicher paßt. Zeigen Sie, daß bei einer Größe der S-Relation von b Seiten, eine Hauptspeichergröße von wenigstens

+ 1 Seiten erforderlich ist.

(Lösung Aufgabe 18-2:)

Aufgabe 18-3: TID-Hash-Join

: Eine Reduzierung des Speicherbedarfs von Hash-Joins ergibt sich, wenn in der Hash-Tabelle anstelle der vollständigen Sätze nur die Schlüsselwerte für das Join-Attribut sowie die Verweise (tuple identifiers, TID) auf die Sätze gespeichert werden. Diskutieren Sie Vor- und Nachteile eines solchen Ansatzes. Welche Auswirkungen ergeben sich für die parallele Join-Bearbeitung in Shared-Nothing-Systemen ?
: (Lösung Aufgabe 18-3:)

Aufgabe 18-4: Paralleler Hash-Join mit Überlaufbehandlung an Datenknoten

: Geben Sie analog zu Kap. 18.3.3 einen Algorithmus für einen parallelen Hash-Join in Shared-Nothing-Systemen an, bei dem die Überlaufbehandlung gemäß dem GRACE-Ansatz an den Datenknoten erfolgt.
: (Lösung Aufgabe 18-4:)

Aufgabe 18-5: Paralleler Hash-Join bei Shared-Everything

: Wie können die Algorithmen zur parallelen Hash-Join-Berechnung für Shared-Everything abgewandelt werden?
: (Lösung Aufgabe 18-5:)

Aufgabe 18-6: Daten-Skew

: Der Join zwischen R und S soll parallel auf 5 Join-Prozessoren berechnet werden. R umfasse 500, S 1000 Tupel, der Wertebereich für das Join-Attribut liege zwischen 1 und 1000. Der Wert 1 soll in R und S je 200-mal auftreten, der Wert 2 100-mal in R und 600-mal in S; alle übrigen Werte sollen höchstens einmal pro Relation vorkommen.
: Welche Skew-Effekte sind zu erwarten, wenn eine Hash-Funktion zur Umverteilung der Tupel verwendet wird ? Welche Bereichspartitionierung vermeidet diese ?
: (Lösung Aufgabe 18-6:)

Aufgabe 18-7: Parallele Änderungstransaktionen bei Shared-Disk

: Intra-Query-Parallelität wird in derzeitigen Shared-Disk-Implementierungen nur für lesende DB-Operationen geboten. Welche Probleme bestehen bei der Parallelisierung von Update-Transaktionen bzw. -Operationen ? (Hinweis: Welche Auswirkungen ergeben sich für die Transaktionsverwaltung und Kohärenzkontrolle ?)
: (Lösung Aufgabe 18-7:)