Diese Arbeit untersucht ausgewählte Problemstellungen der dynamischen Lastbalancierung
in parallelen Datenbanksystemen (PDBS). Betrachtet wird die möglichst gleichmäßige Verteilung von Arbeitslasten zur Laufzeit komplexer analytischer Anfragen. Das Hauptproblem besteht in der eingeschränkten Vorhersagbarkeit sogenannter Skew-Effekte, die verschiedene Arten von Lastungleichgewichten beschreiben und deren Bekämpfung der Schlüssel zur gleichmäßigen Verteilung und effizienten Abarbeitung von Arbeitslasten ist. In der Arbeit werden sowohl empirische als auch analytische Untersuchungsmethoden angewandt. Der Schwerpunkt der Untersuchung liegt dabei auf sogenannten Shared-Disk-Systemen, die sich durch eine gemeinsame Plattenspeicheranbindung auszeichnen; diese Architekturen haben in früheren Forschungen vergleichsweise wenig Beachtung gefunden. Über die eigentliche Lastverteilung hinaus betrachtet die Arbeit ausgewählte Aspekte der dynamischen Allokation von Zwischenergebnissen komplexer Anfragen.
Nach einer allgemeinen Einführung sowie der Positionsbestimmung der Arbeit innerhalb
des Sachgebiets wird zunächst eine theoretische Analyse der Begriffe Skew und
Lastbalancierung vorgenommen. Sowohl für die zahlreichen existierenden Lastbalancierungsverfahren als auch für die Vielfalt unterschiedlicher Skew-Effekte wird
jeweils eine Klassifikation entwickelt. Die Gegenüberstellung beider Begriffswelten
ermöglicht grundsätzliche Aussagen über die Eignung verschiedener Lastverteilungsansätze
zur Bekämpfung bestimmter Skew-Formen. Unter anderem wird festgestellt,
daß hochdynamische, laufzeitbasierte Balancierungsansätze nicht nur zu einer
gleichmäßigeren Lastverteilung führen, sondern dabei sogar eine geringere Komplexität
als typische statische Verfahren besitzen.

Auf dieser Grundlage wird für die empirischen Untersuchungen ein neuer Lastbalancierungsansatz entwickelt: Das sogenannte bedarfsorientierte Scheduling (On-demand Scheduling, ODS) weist eine wesentlich höhere Dynamik auf als die derzeit vorherrschenden prädiktiven Algorithmen. Es verzichtet auf eine umfassende Vorausplanung
von Anfragen und macht statt dessen die tatsächliche Verarbeitungsgeschwindigkeit
zur Grundlage der Lastverteilung. Zum Vergleich des neuen Ansatzes mit einem herkömmlichen Verfahren wird ein Simulationssystem für PDBS verwendet, in dem neue Datenallokations- und Lastbalancierungsmethoden implementiert, erprobt und bewertet werden können. Für die Anwendung von ODS zur parallelen Join-Verarbeitung belegt es signifikante Vorteile vor allem im Mehrbenutzerbetrieb. Hier eignen sich bedarfsorientierte Verfahren wesentlich besser zur Korrektur unerwarteter Lastungleichgewichte als prädiktive oder reaktive Ansätze. ODS wird daher zur Basis weiterer Entwicklungen gemacht.
Als Ergänzung der Join-Verarbeitung wird ein allgemeines Allokationsschema für
Zwischenergebnisse umfangreicher mehrstufiger Anfragen vorgeschlagen. Mittels
einer mathematischen Analyse wird dazu ein optimaler Verteilgrad bestimmt, mit
dem ein möglichst konfliktarmer Zugriff auf die Daten möglich wird. Wichtigstes
Ergebnis dieser Untersuchung ist die Feststellung, daß selbst solche Datenmengen,
die auf einem einzelnen Prozessorknoten weiterverarbeitet werden, über mehrere
Plattenspeicher verteilt werden sollten. Der Nutzen des parallelen Lesezugriffs übersteigt
in allen realistischen Fällen die Belastung durch vermehrte Plattenzugriffskonflikte.
Die letzte Studie überträgt das bedarfsorientierte Scheduling aus klassischen relationalen
DBS in eine Data-Warehouse-Umgebung. Aufbauend auf einer ebenfalls neuentwickelten
Allokationsmethode werden mehrere Varianten des ODS-Verfahrens an
verschiedenen Anfragetypen simulativ erprobt. Hierbei wird eine Strategie ermittelt,
die für alle Lastarten nahezu optimale Resultate liefert, indem sie die Balancierung
von Prozessor- und Plattenauslastungen gegeneinander abwägt. Damit erübrigt sich
eine aufwendige und fehleranfällige Analyse des Lastprofils zur Auswahl eines optimalen
Spezialverfahrens. Das Risiko extrem hoher Antwortzeiten für falsch klassifizierte
Anfragen wird ohne nennenswerte Leistungsverluste vermieden.
Die in der Arbeit präsentierten Lösungsansätze lassen sich auf zahlreiche unterschiedliche Systemarchitekturen, Datenmodelle und Arbeitslasten verallgemeinern.