Kostenbasierte Abfrageoptimierung

Die kostenbasierte Abfrageoptimierung durchsucht den Raum äquivalenter Ausführungspläne für eine Abfrage und wählt denjenigen mit den niedrigsten geschätzten Kosten aus, wobei Statistiken über die Daten und ein Modell der Ausführungskosten verwendet werden.

Definition

Kostenbasierte Abfrageoptimierung ist der Prozess der Schätzung der Ausführungskosten alternativer äquivalenter Pläne für eine Abfrage anhand von Datenstatistiken und eines Kostenmodells sowie der Auswahl des Plans mit den geringsten geschätzten Kosten, typischerweise mit einer durch dynamische Programmierung gewählten Join-Reihenfolge.

Scope

Dieses Thema behandelt, wie ein Optimierer einen Plan auswählt: den Plan-Suchraum, der durch Äquivalenzen der relationalen Algebra und alternative physische Operatoren erzeugt wird, das Kostenmodell, das Pläne bewertet (hauptsächlich in Bezug auf I/O und CPU), die Kardinalitäts- und Selektivitätsschätzung aus Statistiken und Histogrammen sowie den Dynamic-Programming-Ansatz zur Join-Reihenfolgen-Enumeration, der von System R eingeführt wurde. Ausgenommen sind die Implementierung der Operatoren selbst und die regelbasierte logische Umschreibung, die über das hinausgeht, was die Plangenerierung speist.

Core questions

• Wie wird der Raum äquivalenter Ausführungspläne generiert und beschnitten?
• Wie schätzt der Optimierer die Kardinalität und Selektivität von Operationen?
• Wie enumeriert die dynamische Programmierung Join-Reihenfolgen effizient?
• Was berücksichtigt das Kostenmodell, und wie werden I/O- und CPU-Kosten kombiniert?
• Warum führen Kardinalitätsschätzungsfehler zu schlechten Planauswahlen?

Key concepts

• Plan-Suchraum
• Kostenmodell (I/O und CPU)
• Selektivitäts- und Kardinalitätsschätzung
• Histogramme und Statistiken
• Join-Reihenfolgen-Enumeration
• Dynamische Programmierung
• interessante Sortierreihenfolgen
• transformationsbasierte Optimierung

Key theories

System R dynamische Programmierungsoptimierung

Selinger's Optimierer enumeriert Join-Reihenfolgen Bottom-up mit dynamischer Programmierung, wobei der günstigste Plan für jede Teilmenge von Relationen (und jede interessante Sortierreihenfolge) beibehalten wird, was die Suche im großen Join-Reihenfolgen-Raum handhabbar macht.

Kardinalitäts- und Selektivitätsschätzung

Der Optimierer schätzt die Anzahl der Tupel, die jede Operation erzeugt, unter Verwendung von Tabellenstatistiken, Histogrammen und Selektivitätsformeln; diese Schätzungen steuern das Kostenmodell und sind die Hauptquelle für Optimierungsfehler.

Kostenmodelle und Suchstrategien

Pläne werden durch ein Kostenmodell bewertet, das I/O-, CPU- und Speichereffekte kombiniert; über die dynamische Programmierung von System R hinaus untersuchen transformationsbasierte Optimierer Pläne mittels Umschreibungsregeln, um die Optimierung auf reichhaltigere Operatoren und verteilte Umgebungen auszudehnen.

Clinical relevance

Der Optimierer ist die Komponente, die es Benutzern ermöglicht, deklaratives SQL zu schreiben, ohne die Ausführung spezifizieren zu müssen; die Qualität seiner Kostenschätzungen und seiner Suche bestimmt direkt, ob Abfragen auf großen Datenbanken schnell sind, weshalb die kostenbasierte Optimierung zu den am meisten untersuchten und kommerziell wichtigsten Teilen von Datenbanksystemen gehört.

History

Der System R-Optimierer von Selinger und Kollegen aus dem Jahr 1979 führte die kostenbasierte Optimierung mit dynamischer Programmierung für die Join-Reihenfolge und selektivitätsbasierter Kostenschätzung ein und definierte damit das Feld. Spätere transformationsbasierte Optimierer wie Volcano und Cascades verallgemeinerten die Suche, und laufende Arbeiten zur Kardinalitätsschätzung, einschließlich gelernter Modelle, adressieren die zentrale Schwäche des Frameworks.

Debates

Kardinalitätsschätzung versus adaptive Ausführung

Da die kostenbasierte Optimierung nur so gut ist wie ihre Größenschätzungen, die bei korrelierten Daten oft falsch sind, diskutieren Forscher, ob man in bessere Statistiken und maschinell gelernte Schätzer investieren oder sich stärker auf adaptive, zur Laufzeit erfolgende Re-Optimierung verlassen sollte, die schlechte Pläne während der Ausführung korrigiert.

Key figures

• Patricia Selinger
• Goetz Graefe
• Surajit Chaudhuri

Seminal works

• selinger1979
• graefe1993

Frequently asked questions

Warum wählt ein Optimierer manchmal einen schlechten Plan?

Kostenbasierte Optimierer verlassen sich auf Schätzungen, wie viele Zeilen jede Operation erzeugen wird. Wenn Daten schief verteilt oder Spalten korreliert sind, können diese Schätzungen weit daneben liegen, und der Fehler summiert sich über Joins hinweg. Eine falsche Schätzung kann den Optimierer dazu verleiten, eine schlechte Join-Reihenfolge oder einen ungünstigen Zugriffspfad zu wählen, obwohl der Plan auf dem Papier günstig aussah.

Warum wird dynamische Programmierung für die Join-Reihenfolge verwendet?

Die Anzahl der möglichen Join-Reihenfolgen wächst kombinatorisch mit der Anzahl der Tabellen, sodass eine erschöpfende Suche undurchführbar ist. Die dynamische Programmierung erstellt optimale Pläne für größere Mengen von Relationen aus optimalen Plänen für kleinere Teilmengen, wodurch der Aufwand drastisch reduziert wird, während dennoch eine gute (oft optimale) Join-Reihenfolge für typische Abfragegrößen gefunden wird.