6.5 Bearbeitung von Join-Anfragen

6.5.3 Bitvektor-Join

Der Kommunikationsaufwand der Semi-Join-Strategien läßt sich reduzieren, indem die Verbundattributwerte auf einen kompakten Bitvektor abgebildet werden und nur dieser übertragen wird. Da die Abbildung i.a. über eine Hash-Funktion erfolgt, spricht man gelegentlich auch von einem Hash-Filter-Join.

Der Bitvektor B sei folgendermaßen definiert:

B: Array [1:n] of BIT.

Zur Abbildung der Verbundattributwerte wird eine Hash-Funktion h verwendet, die jeden Attributwert eindeutig auf eine ganze Zahl zwischen 1 und n abbildet. Für jeden Verbundattributwert wird das derart zugeordnete Bit im Bitvektor gesetzt. Als Verbundpartner werden alle Tupel ermittelt, für deren Verbundattributwert das Bit gesetzt ist. Die Join-Berechnung R S läuft demnach in folgenden Schritten ab (im Bitvektor B seien anfangs alle Bits zurückgesetzt):

  1. In KR: Für jeden Attributwert v in V (R) setze zugehöriges Bit B (h(v));
    Übertragung des Bitvektors B an KS

  2. In KS: Bestimmung von Z = { s S | B ( h(s.v)) gesetzt} und Übertragung an KR

  3. In KR: Bestimmung von R Z = R S.

Die Einsparungen im Übertragungsvolumen durch Verwendung eines Bitvektors sind natürlich um so höher, je länger die Verbundattributwerte sind oder je mehr unterschiedliche Werte ansonsten zu übertragen wären. Ein weiterer Vorteil liegt darin, daß die Bestimmung der Verbundpartner in Schritt 2 sehr einfach wird. Hierzu ist kein Join durchzuführen, sondern es genügt das Lesen der Relation (Scan) in einer beliebigen Reihenfolge. Insbesondere dieser Aspekt ergab in Performance-Abschätzungen signifikant bessere Resultate für Bitvektor-Joins verglichen mit allgemeinen Semi-Join-Methoden [ML86].

Auf der anderen Seite ist die Hash-Abbildung i.a. nicht injektiv, so daß mit dem Bitvektor nur potentielle Verbundpartner bestimmt werden. Es qualifizieren sich dabei jedoch auch Tupel, die im Verbundergebnis nicht beteiligt sind. Die Übertragung solcher Tupel führt dazu, daß die durch den Bitvektor erreichten Einsparungen zumindest teilweise wieder zunichte gemacht werden. Das Ausmaß dieser Effekte hängt neben der Verteilung der Verbundattributwerte v.a. von der Länge des Bitvektors n und der Hash-Funktion h ab. Durch Wahl eines ausreichend großen n und geeigneter Hash-Funktionen kann die Filterwirkung jedoch meist sehr gut gehalten werden. Diese Problematik wurde bereits in anderen Kontexten untersucht, wo solche Hash-Filter (auch Bloom-Filter genannt) anwendbar sind [Bl70, SL76].

Beispiel 6-11

Der Bitvektor-Join soll auf die in Abb. 6-12 gezeigten Beispielrelationen angewendet werden. Wir betrachten die Join-Berechnung am Knoten KS, da hiermit bei den Semi-Join-Methoden (Beispiel 6-10) der geringste Kommunikationsaufwand verbunden war (#AW=8).Wir verwenden n=5 und h(v) = (v MOD n) + 1.

Die Berechnung des Bitvektors am Knoten KS liefert den Wert B = 11001. In KR wird damit neben (1,1) und (4,5) als dritter potentieller Verbundpartner das Tupel (4,6) ermittelt, da h(6)=2 und B(2) gesetzt ist. Dieses Tupel ist daher ebenfalls an KS zu übertragen, wo es jedoch nicht ins Join-Ergebnis eingeht. Setzt man die Länge des Bitvektors einem Attributwert gleich, so ergibt sich für den Bitvektor-Join als Übertragungsvolumen #AW=7.