Der Cost-Based Optimizer: wie Ausführungspläne wirklich entstehen

1. Das Grundproblem: viele mögliche Pläne für dieselbe Abfrage

SQL beschreibt, welches Ergebnis eine Abfrage liefern soll, nicht wie die Datenbank dieses Ergebnis technisch erzeugt. Für eine Abfrage mit mehreren Joins, Filtern und einer Sortierung existieren oft dutzende bis hunderte technisch gleichwertige Wege, das Ergebnis zu berechnen: unterschiedliche Join-Reihenfolgen, unterschiedliche Join-Algorithmen, unterschiedliche Entscheidungen, ob ein Index genutzt wird oder ein voller Tabellen-Scan günstiger ist.

Ein regelbasierter Optimizer, wie er in älteren Systemen verwendet wurde, trifft diese Entscheidungen anhand fester Prioritäten, etwa immer den selektivsten verfügbaren Index zu bevorzugen. Ein Cost-Based Optimizer geht einen anderen Weg: Er berechnet für mehrere Kandidaten-Pläne eine geschätzte Kostenzahl und wählt den Plan mit den niedrigsten geschätzten Kosten aus, unabhängig davon, welche allgemeine Regel dafür sprechen würde.

2. Statistiken als Grundlage jeder Kostenschätzung

Damit der Optimizer überhaupt Kosten schätzen kann, braucht er Informationen über die tatsächliche Datenverteilung: die Gesamtzahl der Zeilen einer Tabelle, die Anzahl unterschiedlicher Werte pro Spalte, sowie ein Histogramm, das die Verteilung der Werte innerhalb einer Spalte grob abbildet. Diese Statistiken werden nicht bei jeder Abfrage neu berechnet, sondern periodisch oder durch explizite Wartungsbefehle aktualisiert und dann zwischengespeichert.

Veraltete Statistiken sind eine der häufigsten Ursachen für schlechte Ausführungspläne: Wenn eine Tabelle seit der letzten Statistik-Aktualisierung stark gewachsen ist oder sich die Werteverteilung einer Spalte grundlegend geändert hat, arbeitet der Optimizer mit falschen Annahmen und trifft Entscheidungen, die zur tatsächlichen Datenlage nicht mehr passen, selbst wenn die Kostenberechnung an sich fehlerfrei ist.

-- Statistiken manuell aktualisieren (Syntax variiert je nach System)
ANALYZE TABLE orders;

-- Aktuelle Statistiken prüfen
SELECT table_name, table_rows, avg_row_length
FROM information_schema.tables
WHERE table_name = 'orders';

3. Kardinalitätsschätzung: wie viele Zeilen ein Zwischenschritt liefert

Die zentrale Größe in jedem Kostenmodell ist die Kardinalität, also die geschätzte Anzahl Zeilen, die ein Zwischenschritt des Plans liefert. Für einen einfachen Filter wie WHERE status = 'shipped' schätzt der Optimizer die Kardinalität anhand der Selektivität dieses Werts, abgeleitet aus dem Histogramm der Spalte status: Ist shipped ein häufiger Wert, wird die geschätzte Ergebnismenge groß, ist er selten, entsprechend klein.

Bei mehreren verknüpften Filtern oder Joins multipliziert der Optimizer typischerweise die Einzelselektivitäten miteinander, unter der Annahme statistischer Unabhängigkeit zwischen den beteiligten Spalten. Diese Annahme ist der zentrale Ausgangspunkt für viele später beobachtbare Fehleinschätzungen, weil reale Daten oft alles andere als unabhängig verteilt sind.

4. Vom geschätzten Zeilenaufkommen zur konkreten Kostenzahl

Aus der geschätzten Kardinalität berechnet der Optimizer für jeden Kandidaten-Plan eine Kostenzahl, die typischerweise I/O-Kosten, etwa für das Lesen von Datenseiten von der Platte oder aus dem Buffer Pool, sowie CPU-Kosten für Vergleiche, Sortierungen und Hash-Berechnungen kombiniert. Diese Kostenwerte sind meist abstrakte, systemspezifische Einheiten, keine direkten Zeitangaben, lassen sich aber innerhalb desselben Systems zuverlässig vergleichen.

Für jeden Join in der Abfrage bewertet der Optimizer zusätzlich mehrere Algorithmen, etwa Nested Loop Join, Hash Join und Merge Join, und wählt je nach geschätzter Größe der beteiligten Zwischenergebnisse den günstigsten aus. Ein Nested Loop Join ist bei kleinen Ergebnismengen oft am günstigsten, ein Hash Join dagegen bei großen, unsortierten Mengen, weshalb sich der gewählte Algorithmus mit der geschätzten Datenmenge ändern kann, selbst bei identischer Abfrage-Struktur.

5. Wie der Optimizer aus mehreren Kandidaten den finalen Plan wählt

Weil die Anzahl theoretisch möglicher Pläne mit der Zahl der Joins exponentiell wächst, durchsucht der Optimizer in der Praxis nicht alle Kombinationen vollständig, sondern nutzt Heuristiken und dynamische Programmierung, um den Suchraum einzugrenzen. Ab einer gewissen Anzahl von Tabellen in einem Join wechseln viele Systeme deshalb auf genetische oder greedy Algorithmen, die nicht mehr garantiert den global optimalen Plan finden, sondern einen ausreichend guten in vertretbarer Planungszeit.

Am Ende dieses Prozesses steht der Plan mit der niedrigsten Gesamtkostenzahl unter allen betrachteten Kandidaten. Dieser Plan wird kompiliert oder interpretiert ausgeführt und häufig für wiederholte Ausführungen derselben oder ähnlicher Abfragen in einem Plan-Cache zwischengespeichert, um die Optimierungszeit bei erneuter Ausführung einzusparen.

6. Warum identische Abfragen auf unterschiedlichen Datenbeständen unterschiedliche Pläne bekommen

Weil der gesamte Entscheidungsprozess auf Statistiken basiert, die die tatsächliche Datenverteilung widerspiegeln, führt dieselbe Abfrage auf einer kleinen Testdatenbank mit wenigen tausend Zeilen oft zu einem vollkommen anderen Plan als auf der Produktionsdatenbank mit Millionen Zeilen. Ein Index, der auf der kleinen Tabelle noch als zu teuer eingeschätzt wird, weil ein voller Scan bei wenigen Datenseiten kaum ins Gewicht fällt, kann auf der großen Tabelle plötzlich zur klar besseren Wahl werden.

Ebenso kann sich der Plan für dieselbe Abfrage auf demselben System verändern, sobald sich die Werteverteilung durch neue Daten verschiebt, etwa wenn eine Statusspalte durch einen Batch-Import plötzlich viele neue, seltene Werte erhält. Das erklärt, warum ein Plan, der über Monate stabil und performant lief, ohne Code-Änderung plötzlich langsam werden kann, sobald sich die zugrunde liegenden Statistiken durch Datenwachstum oder eine neue Statistik-Aktualisierung verändern.

7. Die zentrale Grenze: Korrelationen zwischen Spalten bleiben meist unsichtbar

Die Annahme statistischer Unabhängigkeit zwischen Spalten ist der bekannteste blinde Fleck jedes Cost-Based Optimizers. Filtert eine Abfrage etwa gleichzeitig nach country = 'DE' und city = 'Berlin', schätzt der Optimizer die kombinierte Selektivität als Produkt beider Einzelselektivitäten, obwohl beide Werte in Wirklichkeit stark korreliert sind: Fast jede Zeile mit city = 'Berlin' hat automatisch auch country = 'DE'. Die tatsächliche Ergebnismenge ist damit oft um ein Vielfaches größer als vom Optimizer geschätzt.

Solche Fehleinschätzungen führen dazu, dass der Optimizer einen Plan wählt, der für die geschätzte, viel zu kleine Ergebnismenge sinnvoll wäre, in der Praxis aber deutlich zu viele Zeilen verarbeiten muss, etwa einen Nested Loop Join, der bei der tatsächlichen Datenmenge einem Hash Join klar unterlegen ist. Moderne Systeme bieten dafür teils mehrspaltige Statistiken oder Extended Statistics an, die genau diese Art von Korrelation gezielt erfassen, müssen dafür aber explizit angelegt werden und werden in der Praxis selten flächendeckend genutzt.

-- Mehrspaltige Statistik anlegen, um Korrelation zwischen
-- country und city für den Optimizer sichtbar zu machen
-- (Syntax exemplarisch, variiert je nach Datenbanksystem)
CREATE STATISTICS stat_country_city
ON country, city
FROM customers;

8. Fehlerhafte Kardinalitätsschätzungen im Ausführungsplan erkennen

Die meisten Datenbanksysteme geben im ausführlichen Ausführungsplan sowohl die geschätzte als auch, nach tatsächlicher Ausführung, die real beobachtete Zeilenzahl pro Schritt aus. Eine große Abweichung zwischen geschätzter und tatsächlicher Zeilenzahl an einem bestimmten Punkt im Plan ist das zuverlässigste Anzeichen dafür, dass der Optimizer an dieser Stelle eine falsche Annahme getroffen hat, meist wegen genau der oben beschriebenen Korrelationsproblematik oder veralteter Statistiken.

Diese Diagnose ist der entscheidende erste Schritt, bevor überhaupt über Optimierungsmaßnahmen wie zusätzliche Indizes, umgeschriebene Abfragen oder explizite Statistik-Hinweise nachgedacht wird. Ohne den tatsächlichen Ausführungsplan mit den real beobachteten Zeilenzahlen zu betrachten, bleibt jede Optimierung an dieser Stelle reine Spekulation über ein Problem, dessen Ursache man noch gar nicht kennt.

9. Wie sich der Optimizer gezielt beeinflussen lässt, ohne ihn zu umgehen

Statt den Optimizer per Hint komplett zu einer bestimmten Zugriffsstrategie zu zwingen, was bei zukünftigem Datenwachstum schnell wieder zur schlechteren Wahl werden kann, ist es meist nachhaltiger, dem Optimizer bessere Eingabedaten zu liefern: aktuellere Statistiken, feiner aufgelöste Histogramme für stark ungleichmäßig verteilte Spalten, oder mehrspaltige Statistiken für bekannt korrelierte Spaltenkombinationen.

Erst wenn diese Maßnahmen ausgeschöpft sind und der Optimizer trotz korrekter Statistiken systematisch falsch entscheidet, etwa weil das Kostenmodell eine bestimmte Konstellation grundsätzlich nicht gut abbilden kann, ist ein gezielter Plan-Hint gerechtfertigt. Auch dann sollte ein solcher Hint dokumentiert und regelmäßig überprüft werden, weil er bei verändertem Datenwachstum leicht selbst zur Ursache eines suboptimalen Plans wird.

10. Zusammenfassung

11. FAQ: Cost-Based Optimizer: Das Wichtigste auf einen Blick