SQL-Anfragen: Optimierung für parallele Bearbeitung: FZI-Berichte Informatik

1 Einleitung.- 1.1 Einführung des Optimierungsproblems.- 1.2 Techniken der Anfrageoptimierung.- 1.3 Kernprobleme der Arbeit.- 1.4 Vorgehensweise.- 1.5 Abgrenzung gegenüber anderen Problemstellungen.- 2 Grundlagen und Literaturüberblick.- 2.1 Relationale Anfragesprachen.- 2.2 Parallele Anfragebearbeitung.- 2.3 Anfragetransformation.- 2.4 Parallelisierung.- 3 Grundkonzept des Optimierers.- 3.1 Lösungsansatz.- 3.2 Anfragerepräsentation.- 3.3 Anfragetransformation und Generierung algebraischer Ausdrücke.- 3.4 Generierung paralleler Bearbeitungspläne.- 4 Erweiterte relationale Algebra und SQL.- 4.1 Spezifikation der erweiterten relationalen Algebra.- 4.2 Die Anfragesprache SQL.- 4.3 Beispiele für die Übersetzung von SQL-Anfragen.- 5 Grundlagen der Anfragetransformation.- 5.1 Überblick.- 5.2 Prädikat-Transformation.- 5.3 Gruppierende Abbildungen.- 5.4 Ersetzung nicht geschlossener Ausdrücke.- 5.5 Algebraische Transformationsregeln.- 5.6 Zusammenfassung.- 6 Anfragetransformation und Generierung algebraischer Ausdrücke.- 6.1 Überblick.- 6.2 Standardisierung.- 6.3 Verbesserung algebraischer Ausdrücke.- 6.4 Beispiele für Standardisierung und Verbesserung.- 6.5 Aufzählung algebraischer Ausdrücke.- 7 Implementierung relationaler Operatoren.- 7.1 Grundlagen.- 7.2 Zugriffspfade.- 7.3 Sequentielle Bearbeitung relationaler Operatoren.- 7.4 Einsatz von Indizes.- 7.5 Ausnutzung einer Sortierung.- 7.6 Verwendung von Hashing.- 7.7 Zerlegung von Operationen in Phasen.- 7.8 Zusammenfassung.- 8 Grundlagen der Parallelisierung.- 8.1 Überblick.- 8.2 Datenflußprogramm.- 8.3 Meta-Datenflußprogramm.- 8.4 Transformationen auf dem Meta-Datenflußprogramm.- 8.5 Abbildung des Meta-Datenflußprogramms auf ein Datenflußprogramm.- 8.6 Generierung eines parallelen Bearbeitungsplans.-8.7 Zusammenfassung.- 9 Kostenmodell.- 9.1 Zielsetzung und Vorgehensweise.- 9.2 Kostenarten.- 9.3 Kostenanteile.- 9.4 Kostenfaktoren.- 9.5 Kostenfunktionen.- 9.6 Bewertung eines parallelen Bearbeitungsplans.- 9.7 Bewertung eines Meta-Datenflußprogramms.- 10 Parallelisierungsstrategien.- 10.1 Aufgaben einer Parallelisierungsstrategie.- 10.2 Heuristiken zur Erzeugung eines Meta-Datenflußprogramms.- 10.3 Heuristiken auf der Basis des Parallelitätsprofils.- 10.4 Heuristiken für die Zuordnung.- 10.5 Zusammenfassung.- 11 Zusammenfassung und Ausblick.- 11.1 Hauptergebnisse der Arbeit.- 11.2 Weiterführende Arbeiten.