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.