6 Verteilte Anfragebearbeitung

6.5 Bearbeitung von Join-Anfragen

Wir verdeutlichen die Ansätze zur globalen Optimierung beispielhaft für die (natürliche) Join-Berechnung, da diese Aufgabe häufig anfällt und oft hohe Ausführungskosten verursacht, so daß sich ein entsprechend großes Optimierungspotential ergibt. Dies gilt bereits für einfache Joins zwischen zwei Relationen. Für Join-Berechnungen zwischen mehr als zwei Relationen ist zusätzlich eine günstige Ausführungsreihenfolge zu bestimmen. In unseren Diskussionen nehmen wir vereinfachend an, daß die beteiligten Relationen jeweils vollständig an einem Knoten gespeichert sind. Die Algorithmen lassen sich jedoch auch für die Join-Berechnung zwischen einzelnen Fragmenten verwenden. Alternativ dazu können die einzelnen Relationen vor der Join-Bildung aus den Fragmenten rekonstruiert werden (Kap. 6.3.1).

Wir stellen zunächst einfache Strategien zur Join-Berechnung vor, bei denen ganze Relationen zwischen den Rechnern verschickt werden bzw. bei denen die zur Join-Berechnung benötigten Sätze der anderen Relation einzeln angefordert werden. Danach wird untersucht, wie durch Einsatz von Semi-Joins der Kommunikationsumfang reduziert werden kann. Anschließend (Kap. 6.5.3) wird noch auf eine Variante dieser Methode eingegangen, bei der Bitvektoren (Hash-Filter) zur Bestimmung von Verbundpartnern verwendet werden. Abschließend diskutieren wir die Berechnung von Mehr-Wege-Joins.

6.5.1 - Einfache Strategien
6.5.2 - Semi-Join-Strategien
6.5.3 - Bitvektor-Join
6.5.4 - Mehr-Wege-Joins