6.5 Bearbeitung von Join-Anfragen

6.5.4 Mehr-Wege-Joins

Mehr-Wege-Joins lassen sich generell als Folge von Zwei-Wege-Joins realisieren. Es gilt somit neben der Festlegung der Join-Strategie pro Verbund (Ship Whole, Semi-Join, Bitvektor-Join) vor allem die Reihenfolge der einzelnen Join-Berechnungen zu bestimmen. Die Bestimmung der günstigsten Reihenfolge ist jedoch sehr aufwendig, da die Anzahl möglicher Ausführungsstrategien exponentiell mit der Relationenanzahl zunimmt. In R*, wo keine Semi-Join-Methoden unterstützt wurden, erfolgte dennoch eine solch vollständige Bewertung aller Join-Reihenfolgen (exhaustive search). Im SDD-1-Prototyp dagegen wurde die Ausführungsreihenfolge für Semi-Join-Operationen durch einen heuristischen Ansatz bestimmt [Be81]. Dabei wird zunächst eine mögliche Reihenfolge als Initiallösung festgelegt, die iterativ verbessert wird. Hierzu werden in jedem Schritt die Kommunikationskosten für die möglichen Semi-Joins bewertet. Die bis zu diesem Zeitpunkt festgelegte Ausführungsfolge wird dann um denjenigen Semi-Join erweitert, der bei dieser Bewertung die geringsten Kommunikationskosten verursacht.

Für zentralisierte DBS erfolgt die Bestimmung von Join-Reihenfolgen vor allem im Hinblick auf die Reduzierung von Zwischenergebnissen. Obwohl in Verteilten DBS die Größe der Zwischenrelationen die Kommunikationskosten beeinflußt, reicht es zu deren Minimierung i.a. nicht aus, diejenige Join-Reihenfolge zu finden, bei der die Vereinigung der Zwischenergebnisse den geringsten Umfang hat. Dies gilt selbst für die einfachen Ship-Whole-Strategien. Denn anstatt der Zwischenrelationen können auch die Basisrelationen übertragen werden, falls diese kleiner sind.

Beispiel 6-12

Zu berechnen sei der Join RS T mit Card (R) = Card (T) = 10000, Card (S) = 1000, JSF (RS) = 0.01, JSF (S T) =0.1. Jede der Relationen habe 10 Attribute. Bei den Kommunikationskosten beschränken wir uns auf den Umfang (#AW), da nur hierbei Unterschiede anfallen. Es bestehen u.a. folgende Ship-Whole Strategien (R -> K bedeutet Transfer von Relation R an Knoten K, Z bezeichne eine Zwischenrelation):

S1. R -> KS. Z := RS. Z -> KT. Berechnung des Ergebnisses ZT.
#AW = 10000 * 10 + 0.01 * 10000 * 1000 * 19 = 2 000 000

(bei einem einfachen Join-Attribut befinden sich in der Zwischenrelation 19 Attribute)

S2. S -> KR. Z := RS. Z -> KT. Berechnung des Ergebnisses ZT.
#AW = 1000 * 10 + 0.01 * 1000 * 10000 * 19 = 1 910 000

S3. S -> KT. Z := ST. Z -> KR. Berechnung des Ergebnisses ZR.
#AW = 1000 * 10 + 0.1 * 1000 * 10000 * 19 = 19 010 000

S4. T -> KS. Z := ST. Z -> KR. Berechnung des Ergebnisses ZR.
#AW = 10000 * 10 + 0.1 * 10000 * 1000 * 19 = 19 100 000

S5. R -> KS; T -> KS. Berechnung des Ergebnisses RS T.
#AW = 10000 * 10 + 10000 * 10 = 200 000

S6. S -> KR; T -> KR. Berechnung des Ergebnisses RS T.
#AW = 1000 * 10 + 10000 * 10 = 110 000.

Die Kommmunikationskosten liegen teilweise um mehr als zwei Größenordnungen auseinander (Faktor 175). Aufgrund der geringen Join-Selektivitäten schneiden diejenigen Strategien am besten ab, die nicht die Zwischenergebnisse, sondern die Basisrelationen zwischen den Knoten verschicken (S5 und S6).

Die Reduzierung des Kommunikationsaufwandes durch Semi-Join-Ansätze kommt für Mehr-Wege-Joins noch stärker zur Geltung. Denn ein Tupel wird nur dann im Ergebnis eines Mehr-Wege-Joins berücksichtigt, wenn es Verbundpartner in allen anderen Relationen findet. Die Wahrscheinlichkeit dafür sinkt jedoch mit wachsender Relationenzahl. Das Optimierungsproblem besteht darin, eine Abfolge von Semi-Join-Operationen zu finden, die eine möglichst weitgehende Reduzierung beteiligter Relationen ermöglicht, so daß das Übertragungsvolumen entsprechend gering gehalten werden kann. Diejenige Lösung, welche jede der beteiligten Relationen auf diejenigen Tupel reduzieren kann, welche auch im Endergebnis repräsentiert sind, wird als "vollständige Reduzierung" (full reducer) bezeichnet. Leider bestehen nicht für alle Typen von Join-Anfragen solche vollständigen Reduzierungen, sondern nur für azyklische Join-Anfragen [BG81].

Beispiel 6-13

Zu berechnen sei für die in Abb. 6-13 gezeigten Beispielrelationen der Join RS T. Eine mögliche Folge von Semi-Joins hierfür sieht folgendermaßen aus:

R' := R S
S' := S T
T' := T S.

In jedem der drei Schritte wird eine der Relationen durch Semi-Join-Bildung reduziert. So wird Relation R im ersten Schritt um fünf Tupel reduziert, S und T im zweiten und dritten Schritt um jeweils zwei Tupel. Das Gesamtergebnis erhält man, indem man den Join der reduzierten Relationen berechnet (z.B. an einem weiteren Knoten). Es liegt jedoch keine vollständige Reduzierung vor, da von jeder der Relationen nur jeweils ein Tupel im Endergebnis repräsentiert ist; die angegebenen Semi-Joins bewirkten jedoch lediglich eine Reduzierung auf zwei bis vier Tupel.

Abb. 6-13: Beispielrelationen zur Mehr-Wege-Join-Berechnung

Die vollständige Reduzierung sieht folgendermaßen aus:
S' := S R
T' := T S'
S'' := S' T'
R' := R S''.

Im Gegensatz zur ersten Lösung erfolgt hier eine geschachtelte Semi-Join-Bildung, um den Reduzierungseffekt über mehrere Stufen fortzuführen. Die angegebene Abarbeitungsreihenfolge ist in Abb. 6-13 zusätzlich durch die Pfeile verdeutlicht, wobei die zur Semi-Join-Berechnung übertragenen Verbundattributwerte ebenfalls angegeben sind. Zunächst wird Relation S mit den Verbundattributwerten von R um vier Tupel auf die zwei Tupel (1,5) und (5,7) reduziert (Relation S'). Im zweiten Schritt werden die beiden verbleibenden Verbundattributwerte 5 und 7 zur Semi-Join-Berechnung mit T verwendet, wobei diese Relation auf ein einziges Tupel reduziert wird, nämlich (7,3). Damit erfolgt in Schritt 3 eine weitergehende Reduzierung von S auf ebenfalls ein Tupel (5,7). Im letzten Schritt erfolgt dann die Reduzierung von R auf Tupel (4,5). Es handelt sich um eine vollständige Reduzierung, da jede der beteiligten Relationen auf die Tupel reduziert werden konnte (hier: jeweils 1 Tupel), die im Endergebnis enthalten sind.

Die vollständige Reduzierung benötigte einen Schritt mehr als die erste Lösung, dafür reduziert sie das Übertragungsvolumen. Für den Transfer der Verbundattributwerte fallen bei der ersten Lösung 4+6+6=16 AW an, bei der vollständigen Reduzierung lediglich 5+2+1+1=9 AW. Die Haupteinsparung ergibt sich jedoch beim anschließenden Transfer der reduzierten Relationen zur Join-Berechnung. Wenn diese an einem separaten Knoten erfolgt, fallen bei der vollständigen Reduzierung lediglich 2+2+2=6 AW Übertragungskosten an, bei der ersten Lösung dagegen 4+8+8=20 AW.

Die vollständige Reduzierung einer Anfrage ist unabhängig von den in den beteiligten Relationen vorliegenden Attributwerten [Ul88]; die im Beispiel genannte Lösung gilt somit für beliebige Ausprägungen der Relationen R, S und T. Leider ist die Bestimmung einer vollständigen Reduzierung auch für azyklische Join-Anfragen meist nicht mit polynomialem Aufwand möglich, so daß man häufig auf heuristische Lösungen zurückgreift. Eine Ausnahme besteht jedoch für die Teilklasse geketteter Join-Anfragen (chained queries), zu der auch die in Beispiel 6-13 verwendete Anfrage gehört. Eine gekettete Join-Anfrage hat allgemein die Form
R1 (A, A1) R2 (A1, A2) . . . Rn (An-1, B),

wobei die Ai die Join-Attribute kennzeichnen. Es liegt also eine Ordnung unter den zu verknüpfenden Relationen vor, da jede Relation nur mit ihren jeweiligen "Nachbarn" in der Kette verknüpft werden kann. Zur Bestimmung der vollständigen Reduzierung genügen 2n-2 Semi-Joins, die innerhalb von zwei Phasen ausgeführt werden. Dabei erfolgt zunächst in einer Vorwärts-Reduzierung ausgehend von R1 die Semi-Join-Bildung zwischen den jeweils benachbarten Relationen bis Rn:
R2' := R2R1
R3' := R3R2'

Rn' := RnRn-1'.

Danach erfolgt in der zweiten Phase eine Rückwärts-Reduzierung durch Semi-Join-Bildung in der umgekehrten Reihenfolge

Rn-1'' := Rn-1Rn'
Rn-2'' := Rn-2R2''

R1' := R1R2''.

Diese Vorgehensweise wurde auch in Beispiel 6-13 angewendet.