Abfrageoptimierer

Der Abfrageoptimierer ist Teil eines Datenbankmanagementsystems (DBMS), der versucht, für eine Datenbankabfrage einen optimalen Auswertungsplan zu berechnen. Die Entwicklung von Abfrageoptimierern ist eng mit der Entwicklung der relationalen DBMS verbunden. Bei den bis dahin existierenden („vor-relationalen“) DBMS auf Basis des hierarchischen Datenbankmodells (wie z. B. IMS) oder dem Netzwerk-Datenbankmodell hat sich das Anwendungsprogramm die Daten mittels Folgen von „navigierenden“ Aufrufe an das DBMS die benötigten Daten „stückweise“ beschafft. D.h. die Anwendungsprogrammierer haben im Detail festgelegt, in welcher Reihenfolge auf welche Daten zugegriffen wird. (Ausführliche Beispiele hierzu finden sich z. B. in und .)

Mit der Vorstellung der Relationenalgebra hat E.F. Codd im Jahr 1970 einen Weg aufgezeigt, wie man mit dieser Abfragesprache in einem Anfrageausdruck die gewünschte Ergebnismenge der Daten beschreiben kann. In Anlehnung an die Mengenlehre hat er diese Abfragesprache als Menge von Operatoren konstruiert; und zwar so, dass jeder dieser Operatoren entweder einen oder zwei Eingabeparameter vom Typ „Menge von Tupeln“ aufweist und als Ergebnis stets eine „Menge von Tupeln“ zurückliefert. Hierdurch kann man diese Aufrufe schachteln und somit eine ganze Folge von Anweisungen in einem Anfrageausdruck formulieren.

Und – damit verbunden - gibt noch eine weitere wichtige Eigenschaft der Relationenalgebra: Man kann – analog zu den Rechenregeln in der Mathematik – Regeln formulieren, ob und ggf. unterwelchen Bedingungen Operanden vertauscht [ a + b ⇔ b + a ], deren Reihenfolge verändert werden kann [ a – b + c ⇔ a + c – b ] oder Operationen zusammengefasst werden können [ (a * b + a * c) ⇔ a * (b + c) ]. Bei der Relationenalgebra können diese Regeln dann z. B. wie folgt aussehen:

Äquivalenz-Transformationen der Relationenalgebra (Auszug) - Quelle:

Wenn man Regeln dieser Art im DBMS hinterlegt, kann nun das DBMS selbstständig alternative Ausführungsmöglichkeiten für einen gegebenen Anfrageausdruck ermitteln und eine möglichst effiziente Ausführungsreihenfolge auswählen.

Trotz dieser Eigenschaften ist die Relationenalgebra für den direkten Einsatz als Anfragesprache zur Nutzung durch Anwendungsprogrammierer nicht geeignet, da geschachtelte Ausdrücke recht komplex werden können. Deshalb wurde im Kontext des Projekts System R vom Forschungslabor der IBM in San Jose (dem späteren Almaden Research Lab) die Sprache SEQUEL entwickelt, die unter dem Namen SQL zum ISO-Standard wurde. In den DBMS, die Abfrageoptimierung betreiben (wie z. B Oracle und DB2), werden SQL-Abfragen auf einen äquivalenten Anfrageausdruck der (herstellerspezifisch erweiterten) Relationenalgebra abgebildet. Die folgenden beiden Abbildungen illustrieren dies am Beispiel von IBM DB2 V9.

Operatorbaum für SQL-Anfrage - Beispiel 1 (Quelle: )

Operatorbaum für SQL-Anfrage - Beispiel 2 (Quelle: )

Es lassen sich zwei Typen von Abfrageoptimierern unterscheiden: regelbasierte und kostenbasierte Abfrageoptimierer.

Aufgaben eines Abfrageoptimierers

Der Abfrageoptimierer hat die Aufgabe, die Antwortzeit eines Datenzugriffs zu minimieren. Da vor allem bei komplexen SQL-Abfragen oft mehrere Zugriffswege möglich sind, die oft sehr unterschiedliche Antwortzeit haben, besteht die Aufgabe darin, einen Zugriffsweg mit einer möglichst kurzen Antwortzeit auszuwählen.

In einem ersten Schritt werden die verschiedenen Zugriffswege analysiert. In einem zweiten Schritt werden die verschiedenen Alternativen bewertet und schließlich wird ein Zugriffsweg ausgewählt.

Zur Ermittlung der verschiedenen Zugriffswege wird auch untersucht, ob andere Formulierungen der SQL-Abfrage mit identischer Ergebnismenge möglich sind. Beispiel: Transformation eines Subselects in einen Join oder Transformation eines OR-Prädikats in einen Union.

Falls zwei oder mehrere Tabellen verknüpft werden (join), gibt es mehrere Wege, dies zu tun.

Beispiel mit 3 Tabellen A, B und C

(A * B) * C
(A * C) * B
(B * C) * A
(B * A) * C
(C * A) * B
(C * B) * A

Bei 3 Tabellen ergeben sich $3!=3*2*1=6$ Varianten. Wenn 10 Tabellen miteinander gejoint werden, dann ergeben sich 3,6 Mio. theoretisch mögliche Varianten.

Die meisten DBMS haben mehrere Joinalgorithmen mit denen ein Join ausgeführt werden kann. Wenn z. B. 4 Joinalgorithmen zur Auswahl stehen, dann gibt es alleine für die Variante (A * B) * C genau ${\text{4 Joinalgorithmen}}^{{\text{3 Tabellen}}-1}=16$ Möglichkeiten, um die beiden Joins auszuführen. So ergeben sich schon ${\text{6 Varianten}}*{\text{16 Joinmöglichkeiten}}=96$ verschiedene kombinierte Varianten, um die drei Tabellen miteinander zu joinen.

Wenn Indizes zu den Tabellen existieren, dann ergeben sich weitere Möglichkeiten, den Datenzugriff zu gestalten.

Einige DBMS haben die Möglichkeit, eine Abfrage durch Parallelverarbeitung von mehreren Prozessoren ausführen zu lassen, falls eine geeignete Hardware zur Verfügung steht.

So kann die Anzahl der möglichen Zugriffsvarianten schnell sehr hoch werden. Die einzelnen Zugriffsvarianten unterscheiden sich meistens erheblich in ihrer Ausführungszeit:

• Je nach den Mengenverhältnissen der in einem Join beteiligten Tabellen führen bestimmte Joinalgorithmen schnell zum Ergebnis, während andere sehr zeitaufwändig in ihrer Ausführung sind.
• Die Verwendung eines Index lohnt sich meistens nur dann, wenn das betreffende Prädikat (z. B. ID = 1234) eine starke Selektivität aufweist, andernfalls führt ein Lesen der kompletten Tabelle schneller zum Ziel.
• Parallelverarbeitung erfordert auch einen gewissen Koordinationsaufwand. Daher ist Parallelverarbeitung nur in bestimmten Fällen von Vorteil.

Der Abfrageoptimierer hat nun die Aufgabe, von den verschiedenen Zugriffsvarianten die mit der besten Ausführungszeit zu ermitteln.

Regelbasierte Abfrageoptimierer

Ein regelbasierter Abfrageoptimierer verwendet zur Ermittlung des Auswertungsplans nur die vorhandenen Datenstrukturen (Tabellen, Indizes). Dabei kommt ein festgelegtes Set von Regeln zum Einsatz. Eine Regel kann z. B. lauten: Wenn ein vorhandener Index genutzt werden kann, dann tue das. Nur wenn kein geeigneter Index vorhanden ist, führe einen Full Table Scan aus.

Regelbasierte Abfrageoptimierer verwenden für die Entscheidungen keine Informationen über die in den Tabellen gespeicherten Daten. So werden insbesondere die Anzahl der Datensätze in den beteiligten Tabellen, Werte, die besonders häufig vorkommen, der Sortierzustand der Sätze nicht berücksichtigt.

Das DBMS Oracle hatte bis zur Version 7 nur einen regelbasierten Abfrageoptimierer. Eine der Regeln besagte, dass die Reihenfolge, mit der bei einem Join auf die einzelnen Tabellen zugegriffen wird, davon abhängig ist, in welcher Reihenfolge die Tabellen in SQL-Statement angegeben sind. Das hatte den Vorteil, dass der Programmierer durch die Formulierung des SQL-Statements darauf Einfluss nehmen konnte, welcher Auswertungsplan zum Einsatz kommt.

Regelbasierte Abfrageoptimierer haben den Vorteil, dass die ermittelten Auswertungspläne statisch sind. Wenn ein Programm in einer Testumgebung mit einem kleinen Datenbestand entwickelt und getestet wurde, dann kann man sicher sein, dass in einer größeren, produktiven Umgebung dieselben Auswertungspläne verwendet werden. Ein periodisches Analysieren des Datenbestands zur Ermittlung von Statistiken ist nicht erforderlich.

Der entscheidende Nachteil des regelbasierten Abfrageoptimierers ist, dass die starren Regeln sich nicht an dem tatsächlich vorhandenen Datenvolumen orientieren. Es ist wie die Auswahl einer Route durch die Innenstadt nur anhand eines Stadtplans ohne Kenntnisse von vorhandenen Staus und Baustellen. Ein kostenbasierter Abfrageoptimierer liefert meistens bessere Ergebnisse, als ein regelbasierter Abfrageoptimierer.

Kostenbasierte Abfrageoptimierer

Der kostenbasierte Optimierer verwendet für seine Entscheidungen statistische Auswertungen über die gespeicherten Daten. Diese Statistiken müssen von Zeit zu Zeit aktualisiert werden. Es empfiehlt sich, nach jeder umfangreichen Änderung am Datenvolumen die Statistiken zu erneuern.

Dabei werden je nach DBMS unterschiedliche statistische Werte ermittelt:

• die Anzahl der Sätze und der belegte Speicherplatz pro Tabelle und Index
• die Anzahl unterschiedlicher Werte pro Spalte (diese Information ist vor allem bei Spalten sinnvoll, die auch in einem Index vorkommen)
• der größte und der kleinste Wert pro Spalte
• der Sortierzustand einer Tabelle im Vergleich zur Sortierreihenfolge eines Index (Clustering Order)
• Einige DBMS (z. B. Oracle) können Histogramme für jede Spalte ermitteln. Andere DBMS (z. B. DB2) können Häufigkeitsverteilungen für am häufigsten vorkommende Werte für jede Tabellenspalte ermitteln.
• Kennzahlen über die vorhandene Hardware wie z. B. die Zugriffsgeschwindigkeit der Festplatten, die Größe des Arbeitsspeichers, die Anzahl der zur Verfügung stehenden Prozessoren

Der kostenbasierte Optimierer ermittelt in einem ersten Schritt alle theoretisch möglichen Zugriffspläne. In einem zweiten Schritt wird für jeden Zugriffsplan abgeschätzt, welche Kosten die Ausführung dieses Zugriffsplans verursachen wird. Mit dem Begriff „Kosten“ ist in erster Linie die Rechenzeit gemeint. Es kann auch die Nutzung der Systemkomponenten (z. B. der Speicherbedarf) mit einfließen.

Eine exakte Berechnung der Kosten ist in der Praxis meist zu aufwändig bzw. nicht möglich. Daher werden Heuristiken verwendet zur Abschätzung der Kosten. Der Zugriffsplan, der die beste Bewertung erhält, wird schließlich ausgeführt, um die angeforderten Daten zu ermitteln.

Die nachstehenden Beispiele zeigen, wie stark sich ein rein regelbasierter von einem kostenbasierten Ausführüngsplan unterscheiden können:

IBM DB2 V9: SQL-Abfrage mit regelbasierter Optimierung (Optimierungsklasse 0) - Quelle:

IBM DB2 V9: Dieselbe SQL-Abfrage, jetzt mit kostenbasierter Optimierung (Opt.-Klasse 5) - Quelle:

Die Qualität des kostenbasierten Optimierers ist davon abhängig, wie ausgefeilt die Berechnungsmodelle sind. Da die SQL-Syntax sehr umfangreich ist, müssen viele Sonderformen und Ausnahmen berücksichtigt werden. Es besteht die Gefahr, dass der rechnerisch günstigste Ausführungsplan tatsächlich nicht optimal ist oder sogar deutlich schlechter ist. Der tatsächlich günstigste Ausführungsplan hat in solchen Fällen durch die verwendete Heuristik ein schlechteres Rating erhalten und wurde daher verworfen. Das Ziel ist nicht unbedingt, aus den vielen möglichen Ausführungsplänen den absolut besten herauszufinden. Wenn der zweitbeste Ausführungsplan in seinen tatsächlichen Kosten nur geringfügig schlechter ist, dann ist es nicht schlimm, wenn dieser ausgewählt wird. Wenn die Heuristik jedoch die Realität so schlecht abschätzt, dass ein tatsächlich viel schlechterer Ausführungsplan zum Einsatz kommt, dann hat der Optimierer eine schlechte Wahl getroffen.

Wenn ein kostenbasierter Optimierer verwendet wird, dann ist eine periodische Erhebung von Statistiken über die gespeicherten Daten wichtig. Wenn sich das Datenvolumen ändert und die Statistiken danach nicht aktualisiert werden, dann werden die Abfragen anhand der veralteten Statistiken optimiert. Das erhöht das Risiko, dass der rechnerisch optimale Zugriffsweg tatsächlich nicht der optimale ist.

Ein weiteres Problem ist die grundsätzliche Unvollständigkeit der statistischen Daten. Es können nur bestimmte Kenngrößen ermittelt werden, doch in der Realität gibt es noch viel mehr Faktoren, die die Kosten eines Datenzugriffs beeinflussen. Oft gibt es Wechselwirkungen zwischen den einzelnen Prädikaten, die im Modell der statistischen Zahlen nicht berücksichtigt sind.

Die Ermittlung von Histogrammen oder Häufigkeitsverteilungen – falls das DBMS dazu die Möglichkeit bietet – ist sehr zeitaufwändig, und es erfordert zusätzlichen Speicherplatz, um diese Daten abzulegen.

Es kommt nicht nur darauf an, dass die Ausführung einer Abfrage optimiert wird, sondern die Ermittlung des optimalen Ausführungsplans selber darf auch nicht zu lange dauern. Damit die Suche bei komplexen Zugriffen nicht zu lange dauert, werden bei vielen DBMS nur ein Teil der theoretisch möglichen Zugriffspläne untersucht z. B. nur maximal 2000. Alle weiteren Zugriffspläne werden erst gar nicht analysiert. Das hat zur Folge, dass bei einem komplexen Zugriff, bei dem z. B. 200.000 theoretisch mögliche Zugriffspläne existieren, nur 1 % aller Zugriffspläne genauer untersucht wird. Die Wahrscheinlichkeit, dass bei diesem Vorgehen ein guter und schneller Zugriffsplan gefunden wird, ist eher gering. Tatsächlich kommt es oft vor, dass für SQL-Statements, in denen viele Tabellen (z. B. mehr als 10) miteinander gejoint werden, Ausführungspläne mit einer unbefriedigenden Laufzeit zum Einsatz kommen, obwohl es andere Ausführungspläne gibt, die hundert Mal schneller die gewünschten Daten liefern würden.

Ein weiterer Nachteil des kostenbasierten Optimierers ist der unerwartete Wechsel eines Ausführungsplans. Da der Ausführungsplan eben nicht einmal festgelegt wird, sondern jedes Mal neu ermittelt wird, besteht nach jedem Aktualisieren der Statistiken und erst Recht nach jedem Release-Wechsel der DBMS-Software die Möglichkeit, dass danach ein ungünstigerer Ausführungsplan zum Einsatz kommt. Dieser ist dann zwar rechnerisch besser, aber tatsächlich schlechter, als der bisher verwendete. So ein Wechsel eines Ausführungsplans kann eine Erhöhung der Ausführungszeit um den Faktor 10 oder 100 zur Folge haben. Das kann der Grund dafür sein, dass ein Programm, das schon monatelang mit einer guten Performance im Einsatz war, auf einmal eine deutlich schlechtere Performance bekommt.