1. Einleitung

Problemstellung: Die Wahl der optimalen Join-Reihenfolge ist entscheidend für die Query-Performance.
Klassische Architektur von Query-Optimierern: Vorstellung der traditionellen Architektur mit Kardinalitätsschätzung, Kostenmodell und Planaufzählung.
Forschungsfragen:
- Wie gut sind Kardinalitätsschätzungen und wann führen schlechte Schätzungen zu langsamen Queries?
- Wie wichtig ist ein genaues Kostenmodell für den gesamten Query-Optimierungsprozess?
- Wie groß muss der enumerierte Planraum sein?
Methodik:
- "Join Order Benchmark" (JOB): Ein neuer Benchmark basierend auf dem IMDB-Datensatz mit realistischen Queries und Korrelationen.
- PostgreSQL als Testsystem: Ein Open-Source DBMS mit traditioneller Architektur.
- Kardinalitätsextraktion und -injektion: Ermöglicht die Isolierung des Einflusses der Kardinalitätsschätzung.

2. Hintergrund und Methodik

Detaillierte Beschreibung des IMDB-Datensatzes und dessen Eignung für den Benchmark (reale Korrelationen, ungleichmäßige Datenverteilungen).
JOB-Queries:
- 33 Query-Strukturen mit 2-6 Varianten (unterschiedliche Selektionen).
- 3 bis 16 Joins pro Query (durchschnittlich 8).
- Fokus auf Join-Reihenfolge als wichtigstes Optimierungsproblem.
PostgreSQL:
- Traditionelle Architektur mit dynamischer Programmierung für die Join-Reihenfolge.
- Kardinalitätsschätzung basierend auf Histogrammen, häufigsten Werten und Domänenkardinalitäten.
- Vereinfachende Annahmen: Gleichverteilung, Unabhängigkeit, Inklusionsprinzip.
- Query-Engine mit verschiedenen Join-Algorithmen (Nested-Loop, Hash-Join, Sort-Merge).
Kardinalitätsextraktion und -injektion:
- Gewinnung von Kardinalitätsschätzungen aus verschiedenen DBMS.
- Injektion der Schätzungen in PostgreSQL zur isolierten Untersuchung der Kardinalitätsschätzung.
Experimentelles Setup:
- Hardware- und Software-Spezifikation des Testsystems.
- Konfigurationsparameter von PostgreSQL.

3. Kardinalitätsschätzung

Bedeutung der Kardinalitätsschätzung: Wichtigste Grundlage für die Wahl des optimalen Query-Plans.
Schätzungen für Basisrelationen:
- Q-Fehler-Analyse (Faktor, um den eine Schätzung von der tatsächlichen Kardinalität abweicht).
- Vergleich verschiedener DBMS: PostgreSQL, HyPer und drei kommerzielle Systeme.
- Feststellung:
  - Die meisten Basisrelationen werden korrekt geschätzt.
  - Es gibt jedoch Ausreißer mit großen Fehlern.
  - DBMS A und HyPer zeigen die besten Ergebnisse (vermutlich durch Sampling).
Schätzungen für Joins:
- Feststellung:
  - Große Fehler: Oftmals um Faktor 1000 oder mehr.
  - Exponentielles Fehlerwachstum: Mit zunehmender Anzahl der Joins.
  - Systematische Unterschätzung: Besonders ausgeprägt bei DBMS B.
- Ursache:
  - Unabhängigkeitsannahme bei der Join-Schätzung.
  - Keine Erkennung von Join-übergreifenden Korrelationen.
  - Abbildung 3: Visualisiert die Q-Fehler für verschiedene DBMS und Join-Größen.
Schätzungen für TPC-H:
- Feststellung:
  - TPC-H stellt keine große Herausforderung für Kardinalitätsschätzer dar.
  - Abbildung 4: Vergleich der Schätzfehler von PostgreSQL für JOB- und TPC-H-Queries.
Verbesserte Statistiken für PostgreSQL:
- Feststellung:
  - Die Verwendung der tatsächlichen Anzahl unterschiedlicher Werte verbessert die Varianz der Fehler.
  - Die Unterschätzung der Kardinalitäten wird jedoch verstärkt.
- Abbildung 5: Vergleich der Schätzungen mit geschätzten und tatsächlichen Anzahlen unterschiedlicher Werte.

4. Wann führen schlechte Kardinalitätsschätzungen zu langsamen Queries?

Einfluss des physischen Datenbankdesigns: Die Art und Anzahl der Indizes beeinflusst den Suchraum für Pläne und die Sensitivität gegenüber Schätzfehlern.
Risiko der Abhängigkeit von Schätzungen:
- Feststellung:
  - Die Verwendung von Schätzungen führt oft zu langsameren Queries im Vergleich zu den tatsächlichen Kardinalitäten.
  - Schlechte Schätzungen können zu Timeouts führen.
- Ursachen:
  - Wahl von Nested-Loop-Joins aufgrund von Unterschätzungen: Diese haben eine hohe Komplexität und sollten vermieden werden.
  - Falsch dimensionierte Hash-Tabellen aufgrund von Unterschätzungen: Führt zu langen Kollisionsketten.
- Lösung:
  - Deaktivierung von Nested-Loop-Joins (ohne Index-Lookup).
  - Dynamische Größenanpassung der Hash-Tabellen zur Laufzeit.
- Abbildung 6: Zeigt den Einfluss der Optimierungen auf die Query-Laufzeiten.
Gute Pläne trotz schlechter Kardinalitäten:
- Feststellung:
  - Mit nur Primärschlüsselindizes und den genannten Optimierungen ist die Performance oft nahe am Optimum.
- Ursachen:
  - Full-Table-Scans bei großen Tabellen dämpfen den Einfluss der Join-Reihenfolge.
  - Im Hauptspeicher ist die Wahl eines suboptimalen Join-Algorithmus nicht katastrophal.
Komplexe Zugriffspfade:
- Feststellung:
  - Zusätzliche Fremdschlüsselindizes führen zu größeren Performanceunterschieden.
- Ursache:
  - Der Suchraum für Pläne wird komplexer.
- Abbildung 7: Vergleich der Laufzeiten mit und ohne Fremdschlüsselindizes.
Join-übergreifende Korrelationen:
- Herausforderung: Schätzung von Kardinalitäten bei korrelierten Prädikaten über mehrere Tabellen.
- Beispiel DBLP-Datensatz: Partitionierung von Indizes kann Join-übergreifende Korrelationen ausnutzen.
- Feststellung:
  - Der Einfluss von Join-übergreifenden Korrelationen hängt von den verfügbaren Zugriffspfaden ab.
  - Neue physische Designs und Zugriffspfade könnten notwendig sein.

5. Kostenmodelle

Zweck des Kostenmodells: Auswahl des besten Plans aus dem Suchraum basierend auf den Kardinalitätsschätzungen.
Das PostgreSQL-Kostenmodell:
- Komplexes Modell mit über 4000 Zeilen C-Code.
- Berücksichtigt CPU- und I/O-Kosten.
- Schwierige Konfiguration der Parameter.
Kosten und Laufzeit:
- Feststellung:
  - Das Kostenmodell korreliert mit der Laufzeit, aber schlechte Schätzungen führen zu Ausreißern.
  - Die Verwendung der tatsächlichen Kardinalitäten macht das Kostenmodell zuverlässiger.
- Abbildung 8: Vergleich von Kosten und Laufzeiten für verschiedene Kostenmodelle.
Optimierung des Kostenmodells für Hauptspeicher:
- Feststellung:
  - Anpassung der Parameter für geringere I/O-Kosten verbessert die Korrelation.
  - Die Verbesserung ist jedoch geringer als der Einfluss der Kardinalitätsschätzung.
Sind komplexe Kostenmodelle notwendig?
- Einfaches Kostenmodell (Cmm): Zählt nur die Anzahl der verarbeiteten Tupel.
- Feststellung:
  - Selbst das einfache Modell kann die Laufzeit im Hauptspeicher gut vorhersagen.
  - Die Verbesserung durch das Kostenmodell ist geringer als der Einfluss der Kardinalitätsschätzung.
- Abbildung 8: Vergleich von Kosten und Laufzeiten für verschiedene Kostenmodelle.

6. Planraum

Planaufzählungsalgorithmen: Untersuchen den Raum der möglichen Join-Reihenfolgen (exhaustiv oder heuristisch).
Wie wichtig ist die Join-Reihenfolge?
- Quickpick-Algorithmus: Erzeugt zufällige Pläne, um die Kostenverteilung zu visualisieren.
- Feststellung:
  - Die Kosten verschiedener Join-Reihenfolgen können sich um Größenordnungen unterscheiden.
  - Die Form der Verteilungen variiert je nach Query und Indexkonfiguration.
  - Fremdschlüsselindizes führen zu größeren Performanceunterschieden.
- Abbildung 9: Visualisiert die Kostenverteilungen für verschiedene Queries und Indexkonfigurationen.
Sind Bushy Trees notwendig?
- Vergleich verschiedener Baumstrukturen: Left-Deep, Right-Deep, Zig-Zag, Bushy.
- Feststellung:
  - Zig-Zag-Bäume bieten in den meisten Fällen eine gute Performance.
  - Left-Deep-Bäume sind akzeptabel, Right-Deep-Bäume hingegen schlecht.
- Tabelle 2: Zeigt die Performanceeinbußen für eingeschränkte Baumstrukturen.
Sind Heuristiken ausreichend?
- Vergleich von dynamischer Programmierung mit Heuristiken: Quickpick-1000, Greedy Operator Ordering (GOO).
- Feststellung:
  - Die vollständige Aufzählung mit dynamischer Programmierung liefert die besten Ergebnisse.
  - Heuristiken sind jedoch weniger anfällig für Schätzfehler.
- Tabelle 3: Vergleich der Performance verschiedener Algorithmen.

7. Schlussfolgerungen und zukünftige Arbeiten

Zusammenfassung der wichtigsten Erkenntnisse:
- Query-Optimierung ist essentiell für effiziente Query-Verarbeitung.
- Kardinalitätsschätzung ist die wichtigste Komponente und stellt die größte Herausforderung dar.
- Kostenmodelle spielen eine untergeordnete Rolle.
- Exhausive Planaufzählung ist vorzuziehen, aber der Einfluss von Schätzfehlern ist groß.
Ausblick auf zukünftige Forschung:
- Integration fortschrittlicherer Schätzalgorithmen.
- Stärkere Interaktion zwischen Laufzeit und Query-Optimierer.
- Untersuchung von datenbankresidenten und verteilten Datenbanken.