18 Parallele Anfragebearbeitung

18.1 Allgemeine Vorgehensweise

Die Anfragebearbeitung in Parallelen DBS weist große Ähnlichkeiten mit der Anfrageverarbeitung in Verteilten DBS (Kap. 6) auf. Insbesondere fallen zur Erstellung eines Ausführungsplans die drei Phasen der Anfragetransformation, Daten-Lokalisierung und Optimierung an. Die Berücksichtigung unterschiedlicher Parallelisierungsarten betrifft vor allem die Phase der Optimierung. Dabei kann die in Verteilten DBS aufgrund der geforderten Knotenautonomie vorgenommene Trennung zwischen globaler und lokaler Optimierung entfallen. Dennoch ist die Erstellung eines guten parallelen Ausführungsplanes weitaus komplexer als die Bestimmung sequentieller Pläne. Denn dabei ist für jeden Operator die Parallelisierungsstrategie festzulegen, welche Entscheidungen über den Parallelitätsgrad, die Zuteilung von Betriebsmitteln (Prozessoren, Hauptspeicher) sowie der Implementierungsstrategie verlangt. Weiterhin wird die Festlegung der Ausführungsreihenfolge von der Parallelisierung stark beeinflußt, z.B. um ein möglichst hohes Maß an Inter-Operatorparallelität nutzen zu können.

Um die Komplexität der Query-Optimierung und damit die Optimierungsdauer zu reduzieren, wird häufig ein zweistufiger Ansatz verfolgt, bei dem für eine DB-Operation zunächst ein optimaler sequentieller Ausführungsplan (Operatorbaum) erstellt wird, für den dann in einem zweiten Schritt die Parallelisierung vorgenommen wird. Dieser Ansatz vereinfacht zwar die Optimierung, kann aber natürlich zu suboptimalen Lösungen führen [Pi90]. Andere Ansätze reduzieren die Komplexität durch strukturelle Beschränkungen des Suchraumes, z.B. in dem nur lineare Operatorbäume berücksichtigt werden, die jedoch auch den erreichbaren Grad an Inter-Operatorparallelität begrenzen. Ein anderer Ansatz zur Reduzierung des Optimierungsaufwandes besteht darin, die Suchstrategie einzuschränken. In kommerziellen DBS wird nämlich meist eine nahezu vollständige Bewertung aller möglichen Pläne (exhaustive search) vorgenommen, z.B. mit Verfahren der dynamischen Programmierung [Se79]. Der Aufwand solch enumerativer Methoden zur Optimierung paralleler Ausführungspläne ist jedoch für komplexere Operationen, die z.B. mehr als 10 Relationen betreffen, nicht mehr akzeptabel. Zur Reduzierung des Aufwandes wurden zahlreiche heuristische und zufallsgesteuerte Suchstrategien vorgeschlagen [LVZ93]. Wir werden einige dieser Ansätze im Zusammenhang mit Mehr-Wege-Joins diskutieren (Kap. 18.3.4).

Als Kostenfunktion zur Optimierung empfiehlt sich die Abschätzung der Antwort- bzw. Bearbeitungszeit, da deren Verkürzung Ziel von Intra-Transaktionsparallelität ist. Dazu sind die Kommunikationsanteile in Abhängigkeit der vorliegenden Datenverteilung (bei Shared-Nothing) sowie die CPU- und E/A-bezogenen Kosten zu bestimmen. Zur Übersetzungszeit lassen sich allerdings lediglich Antwortzeiten im Einbenutzerbetrieb abschätzen, die sich im Mehrbenutzerbetrieb aufgrund von Behinderungen durch parallel zu bearbeitende Transaktionen und Anfragen stark erhöhen können. Auch Entscheidungen wie Parallelitätsgrad und Prozessorallokation sollten im Mehrbenutzerfall idealerweise vom aktuellen Systemzustand abhängig gemacht werden, was dynamische Ansätze für Parallelisierung und Scheduling verlangt.