18.3 Parallele Joins

18.3.4 Mehr-Wege-Joins

Zur Parallelisierung komplexer Anfragen, deren Operatorbäume zahlreiche Knoten umfassen, fand vor allem die Optimierung von Mehr- bzw. N-Wege-Joins große Beachtung in der Literatur [Ze89, SD90, LST91,CYW92, CLYY92, ZZB93]. Auf die Optimierung solcher Anfragen in Verteilten DBS wurde bereits in Kap. 6.5.4 eingegangen. Ein besonderes Optimierungsproblem besteht darin, eine äquivalente und möglichst günstige Reihenfolge von Zwei-Wege-Joins zu finden. Das Optimierungsproblem verschärft sich bei paralleler Join-Berechnung noch erheblich. Denn hierzu sind Festlegungen sowohl für Intra- als auch Inter-Operatorparallelität zu treffen, insbesondere auf welchen Prozessoren die Join-Bearbeitung zu welchen Zeitpunkten erfolgen soll. Weiterhin soll sowohl Daten- als auch Pipeline-Parallelität genutzt werden.

Zur Reduzierung des Optimierungsproblems betrachten die meisten Implementierungen und Verfahrensvorschläge lediglich lineare Operatorbäume, bei denen ein Mehr-Wege-Join durch eine lineare Folge von Zwei-Wege-Joins realisiert wird. Hierbei kann unterschieden werden zwischen den in Abb. 18-7 gezeigten links-tiefen (left deep) und rechts-tiefen (right deep) Operatorbäumen [Ze89, SD90][85]. Unbeschränkte Operatorbäume (bushy trees, Abb. 18-7c) bieten dagegen offensichtlich ein größeres Optimierungspotential als lineare Bäume. Insbesondere kann mit ihnen Datenparallelität weitgehender genutzt werden, da auf unterschiedlichen Relationen arbeitende Teilbäume vollständig parallel ausführbar sind (z.B. R1R2 und R3R4 in Abb. 18-7c). Allerdings ist der Optimierungsaufwand für unbeschränkte Operatorbäume komplexer Anfragen vielfach prohibitiv.

Abb. 18-7: Berechnungsfolgen für N-Wege-Joins (N=5)

Die Unterschiede zwischen links- und rechts-tiefen Bäumen treten vor allem bei der Verwendung von Hash-Joins zu Tage. Beim links-tiefen Baum (Abb. 18-7a) ist die zum Probing benutzte, rechte Eingabe jeder Join-Operation eine Basisrelation. Die Join-Berechnung erfolgt in N Schritten, wobei im ersten Schritt die Hash-Tabelle für die erste Relation ("linker" Operand) aufgebaut wird und in den N-1 folgenden Schritten das Probing mit den restlichen Basisrelationen erfolgt. Die Ergebnistupel einer Join-Berechnung werden schubweise an den jeweils nächsten Join-Knoten gesendet, der damit die Hash-Tabelle im Hauptspeicher aufbaut. Dort kann die eigentliche Join-Berechnung (Probing-Phase) erst gestartet werden, wenn das komplette Ergebnis des vorausgehenden Joins vorliegt. Der Einsatz von Pipeline-Parallelität zwischen Join-Operatoren ist somit auf jeweils zwei Knoten beschränkt. Von Nachteil ist ferner, daß die Größe der Hash-Tabellen von der Selektivität der einzelnen Join-Operationen abhängt, so daß der Hauptspeicherbedarf oft nur ungenau bekannt ist.

Beim rechts-tiefen Baum (Abb. 18-7b) wird durch verstärkte Nutzung von Parallelität eine Join-Bearbeitung in zwei Schritten erreicht. Dabei werden im ersten Schritt N-1 der N Basisrelationen ("linke" Operanden) parallel in die Hauptspeicher der Join-Rechner geladen. Im zweiten Schritt wird dann sukzessive die Join-Berechnung mit der N-ten Relation unter Nutzung von Pipeline-Parallelität durchgeführt. Dieser Ansatz hat jedoch den Nachteil eines sehr hohen Speicherbedarfs. Gestattet jedoch die Hauptspeicherkapazität das vollständige Laden der N-1 Relationen ergeben sich deutliche Vorteile gegenüber links-tiefen Bäumen [SD90]. Der geringere Speicherbedarf links-tiefer Bäume ist dagegen vor allem bei hoher Join-Selektivität sehr ausgeprägt.

Links- und rechts-tiefe Bäume stellen Extremansätze hinsichtlich des Ressourcenbedarfs sowie der Anzahl benötigter Verarbeitungsschritte dar. Als Alternative dazu wurden in [ZZB93] sogenannte Zick-Zack-Bäume vorgeschlagen, welche lineare (tiefe) Operatorbäume darstellen, bei denen jedoch für Teilbäume zwischen links-tiefer und rechts-tiefer Vorgehensweise gewechselt werden kann. So kommt im Beispiel von Abb. 18-8a zunächst ein links-tiefer Teilbaum zur Auswertung, um den Join zwischen R1 und R2 zu berechnen. Das Ergebnis dieser Join-Operation bildet die "linke" Eingabe zu einem rechts-tiefen Teilbaum, ebenso wie die Relationen R3 und R4, die parallel in die Hauptspeicher der betreffenden Rechner gebracht werden. Die abschließende Probing-Phase mit R5 kann erst beginnen, nachdem das Join-Ergebnis von R1R2 vollständig vorliegt. Eine solche Kompromißlösung ermöglicht einen reduzierten Ressourcenbedarf gegenüber rechts-tiefen sowie einen höheren Parallelitätsgrad gegenüber links-tiefen Bäumen. Der Suchraum zur Optimierung erhöht sich dafür, da rechts- bzw. links-tiefe Bäume als Spezialfälle weiterhin möglich sind.

Abb. 18-8: Alternative Baumstrukturen für N-Wege-Joins (N=5)

Eine ähnliche Zielstellung wie mit Zick-Zack-Bäumen wird mit segmentierten rechts-tiefen Bäumen [CLYY92, STY93] verfolgt. Diese teilen den Operatorbaum in eine Menge rechts-tiefer Teilbäume (Segmente) auf, für welche die "linken" Eingaberelationen jeweils hauptspeicherresident gehalten und die daher parallel eingelesen werden können. Es handelt sich dabei im Prinzip um eine Verallgemeinerung von Zick-Zack-Bäumen, wobei nicht nur "tiefe", sondern beliebige Baumstrukturen (bushy trees) zugelassen werden, wie das Beispiel in Abb. 18-8b auch zeigt. Zur Vereinfachung von Optimierung und Scheduling-Entscheidungen wird jedoch zu einem Zeitpunkt jeweils nur ein Segment bearbeitet, also die Parallelität gegenüber unbeschränkten Operatorbäumen reduziert. Im Beispiel von Abb. 18-8b wird die Berechnung von R4R5 somit erst begonnen, wenn die Join-Berechnung des linken Segmentes beendet ist.

Die Eingrenzung des Suchraumes durch strukturelle Beschränkungen der Operatorbäume stellt nur einen Ansatz zur Reduzierung des Optimierungsaufwandes für komplexe Anfragen (z.B. Mehr-Wege-Joins) dar. Eine Alternative besteht in der Wahl einer effizienten Suchstrategie, die den hohen Aufwand für eine enumerative Bewertung nahezu aller Pläne umgeht, wie er mit dem klassischen Ansatz der dynamischen Programmierung [Se79] entsteht. Dies kann u.a. mit zufallsgesteuerten Suchstrategien wie Simulated Annealing oder iterativer Verbesserung erreicht werden, die eine bestimmte Ausgangslösung bis zum Erreichen eines lokalen Optimums verbessern. Auch wenn damit nicht immer das globale Optimum erreicht wird, findet sich mit geringem Aufwand meist eine gute Lösung. In [LVZ93] wurde gezeigt, daß die Anwendung solcher Suchstrategien auf einem unbeschränkten Suchraum (bushy trees) vielfach wirkungsvoller ist als der Einsatz enumerativer Suchstrategien auf einem beschränkten Suchraum.

[85] Von "tiefen" Operatorbäumen spricht man generell, wenn alle inneren Knoten des Baumes wenigstens einen Blattknoten (Basisrelation) als Eingabe besitzen [IK91].