6.5 Bearbeitung von Join-Anfragen

6.5.1 Einfache Strategien

Zu berechnen sei der natürliche Verbund zwischen Relation R an Knoten KR und Relation S an Knoten KS. Die einfachen Join-Strategien sind dadurch gekennzeichnet, daß der Join vollständig an einem Knoten ausgeführt wird. Damit sind im wesentlichen noch zwei Punkte zu klären: a) an welchem Knoten erfolgt die Join-Berechnung und b) wie wird der Datenaustausch zwischen den Knoten durchgeführt. Für den Ausführungsort des Joins kommen drei Möglichkeiten in Betracht, nämlich Knoten KR, Knoten KS oder ein sonstiger Knoten, an dem z.B. eine Weiterverarbeitung des Ergebnisses vorzunehmen ist. Bezüglich des Datenaustauschs bestehen zwei Alternativen, die z.B. im Prototyp R* unterstützt werden [ML86]:

  1. Transfer ganzer Relationen ("Ship Whole")
    Hierbei werden Relationen vollständig an den Join-Knoten übertragen, wo sie in temporären Relationen gespeichert werden, bevor die Join-Ausführung erfolgt. Soll die Join-Berechnung an einem der beiden datenhaltenden Knoten erfolgen, wird der Transfer natürlich für die kleinere Relation durchgeführt.

  2. Satzweises Anfordern von Verbundpartnern ("Fetch As Needed")
    In diesem Fall erfolgt die Join-Berechnung an einem der datenhaltenden Knoten KR bzw. KS. Für jedes Tupel der lokal vorliegenden Relation wird der Wert des Join-Attributs an den anderen Rechner geschickt. Dieser bestimmt daraufhin die Tupel mit übereinstimmenden Werten im Verbundattribut und überträgt sie an den anfordernden Rechner.

Der Vorteil der ersten Methode (Ship Whole) liegt darin, daß sie mit einer minimalen Nachrichtenanzahl auskommt. Dafür ist jedoch ein hohes Datenvolumen zu übertragen. Außerdem ist im Join-Rechner ggf. eine hohe Anzahl von E/A-Vorgängen für die zu erzeugenden temporären Relationen vorzunehmen. Der Ansatz scheint daher vor allem für kleinere Relationen von Interesse zu sein. Die Alternative (Fetch As Needed) verursacht dagegen eine sehr hohe Nachrichtenanzahl, da für jedes Tupel der ersten Relation eine Anforderung der Verbundpartner stattfindet. Dafür läßt sich ggf. der Übertragungsumfang kleiner halten, da nur die relevanten Tupel der zweiten Relation übertragen werden. Dies ist vor allem bei hoher Join-Selektivität vorteilhaft. Die Menge zu berücksichtigender Verbundpartner kann daneben aufgrund zusätzlicher Selektionsbedingungen reduziert werden. In diesem Fall läßt sich jedoch auch beim Ship-Whole-Ansatz der Kommunikationsumfang reduzieren, indem vor dem Transfer die anwendbaren Selektionen (und Projektionen) durchgeführt werden.

Zur Kostenabschätzung der einzelnen Join-Alternativen beschränken wir uns auf die Kommunikationsanteile. Dazu berücksichtigen wir zwei Komponenten, die Nachrichtenanzahl (#Nachrichten) sowie den Übertragungsumfang. Bezüglich des Übertragungsvolumens unterscheiden wir nicht zwischen unterschiedlichen Attributgrößen, sondern bestimmen lediglich die Anzahl zu übertragender Attributwerte (#AW).

Beispiel 6-8

Die Join-Strategien sollen zunächst für die in Abb. 6-12 gezeigten Beispielrelationen betrachtet werden. Das Join-Ergebnis (über Attribut B) enthält lediglich 2 Tupel; es liegt also eine hohe Join-Selektivität vor. Insbesondere ist nicht jedes R- bzw. S-Tupel im Join-Ergebnis repräsentiert. Zur Bestimmung der Kommunikationskosten berücksichtigen wir nur die Join-Berechnung selbst, nicht also die Nachrichten zum Starten des Verbundes oder der Weiterleitung des Ergebnisses. Für die einzelnen Strategien ergeben sich folgende Kosten:

S1 (Ship Whole, Join-Berechnung am R-Knoten):
#Nachrichten = 2; #AW = 18.

S2 (Ship Whole, Join-Berechnung am S-Knoten):
#Nachrichten = 2; #AW = 14.

S3 (Ship Whole, Join-Berechnung an drittem Knoten):
#Nachrichten = 4; #AW = 32.

F1 (Fetch As Needed; Join-Berechnung am R-Knoten):
#Nachrichten = 7 * 2 = 14; #AW = 2 * 3 = 6.

F2 (Fetch As Needed; Join-Berechnung am S-Knoten):
#Nachrichten = 6 * 2 = 12; #AW = 2 * 2 = 4.

Man erkennt, daß die Fetch-As-Needed-Strategien aufgrund der hohen Join-Selektivität den geringsten Nachrichtenumfang verursachen, jedoch eine deutlich höhere Nachrichtenanzahl.

Abb. 6-12: Beispielrelationen zur Join-Berechnung

Beispiel 6-9

Zwischen den Relationen KONTO (10000 Tupel) und KUNDE (5000 Tupel) soll folgende (hierarchische) Join-Anfrage bestimmt werden:

SELECT * FROM KUNDE, KONTO
WHERE KUNDE.KNR=KONTO.KNR AND KONTO.KTOSTAND > 20000

Beide Relationen sollen je 10 Attribute umfassen. Falls 5% der Konten mehr als 20000 DM aufweisen (SF = 0.05), ergeben sich folgende Ausführungskosten für die Join-Strategien:

S1 (Ship Whole, Join-Berechnung am KONTO-Knoten):
#Nachrichten = 2; #AW = 5 000 * 10 = 50 000.

S2 (Ship Whole, Join-Berechnung am KUNDE-Knoten):
#Nachrichten = 2; #AW = 500 * 10 = 5 000.

Es wird nicht die gesamte KONTO-Relation übertragen, sondern zunächst die Selektion
auf KTOSTAND ausgewertet (ansonsten wäre #AW = 100 000).

S3 (Ship Whole, Join-Berechnung an drittem Knoten):
#Nachrichten = 4; #AW = 55 000.

F1 (Fetch As Needed; Join-Berechnung am KONTO-Knoten):
#Nachrichten = 500 * 2 = 1000; #AW = 500 + 500 * 10 = 5 500.

Für jeden KONTO-Satz sind 1 Attributwert (Join-Attribut KNR) an KKUNDE
 sowie 10 Attributwerte von KKUNDE an KKONTO zu übertragen

F2 (Fetch As Needed; Join-Berechnung am KUNDE-Knoten):
#Nachrichten = 5 000 * 2 = 10000; #AW = 5000 + 500 * 10 = 10 000.

In diesem Beispiel ist Strategie S2 die beste, da sie auch die Selektionsbedingung zur Reduzierung des Kommunikationsumfangs nutzen kann. Von den Strategien S1 und F1, die beide eine Join-Berechnung am KONTO-Knoten vornehmen, schneidet F1 vom Nachrichtenumfang deutlich besser ab. Die Einzelanforderungen von Verbundpartnern (F1 und F2) verursachen wiederum eine sehr hohe Nachrichtenanzahl.

Die Leistungsanalyse in [ML86] zeigte, daß der Transfer ganzer Relationen in den meisten Fällen günstiger abschneidet als der Fetch-As-Needed-Ansatz, und zwar auch bei geographischer Verteilung, wo der Nachrichtenumfang stärker als bei lokaler Verteilung ins Gewicht fällt. Der Grund liegt in der exzessiv hohen Nachrichtenanzahl der Fetch-As-Needed-Strategie, die für jedes Tupel die Verbundpartner anfordert.