Anfrageoptimierer

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Anfrageoptimierer ist Teil eines Datenbankmanagementsystems, der versucht, für eine Datenbankanfrage einen optimalen Auswertungsplan zu berechnen.

Nicht alle DBMS haben einen Anfrageoptimierer. Das DBMS IMS z. B. braucht keinen Anfrageoptimierer, da es sich um ein hierarchisches DBMS handelt und die Zugriffe auf die Daten nicht in SQL-Syntax formuliert werden, sondern der Auswertungsplan bei jeder Abfrage mit angegeben werden muss.

Anfrageoptimierer kommen in der Regel bei relationalen DBMS zum Einsatz. Denn die SQL-Syntax spezifiziert nur, welche Daten ermittelt werden sollen, nicht aber wie es geschehen soll.

Es lassen sich zwei Typen von Anfrageoptimierern unterscheiden: regelbasierte und kostenbasierte Anfrageoptimierer.

Aufgaben eines Anfrageoptimierers[Bearbeiten]

Der Anfrageoptimierer hat die Aufgabe, die Antwortzeit eines Datenzugriffs zu minimieren. Da vor allem bei komplexen SQL-Anfragen 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-Anfrage 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 6 Varianten (3! = 3 * 2 * 1 = 6). 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 16 Möglichkeiten (4 hoch 2 = 16), um die beiden Joins auszuführen. So ergeben sich schon 96 verschiedene Varianten, um die drei Tabellen miteinander zu joinen.

Wenn Indices 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 Anfrageoptimierer[Bearbeiten]

Ein regelbasierter Anfrageoptimierer verwendet zur Ermittlung des Auswertungsplans keine Informationen über das tatsächlich vorhandene Datenvolumen. Es werden nur die vorhandenen Datenstrukturen (Tabellen, Indices) analysiert und mit der Abfrage abgeglichen. 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.

Das DBMS Oracle hatte bis zur Version 7 nur einen regelbasierten Anfrageoptimierer. 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.

Der entscheidende Nachteile des regelbasierten Anfrageoptimierers sind die starren Regeln, die 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 Anfrageoptimierer liefert meistens bessere Ergebnisse, als ein regelbasierter Anfrageoptimierer.

Kostenbasierte Anfrageoptimierer[Bearbeiten]

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.

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 (Rechenzeit und Speicherbedarf) die Ausführung dieses Zugriffsplans verursachen wird. Diese Kosten können nur bei ganz einfachen Zugriffen im Voraus exakt berechnet werden. Bei allen komplexeren Zugriffen müssen sie durch Verwendung von Heuristiken abgeschätzt werden. Der Zugriffsplan, der die beste Bewertung erhält, wird schließlich ausgeführt, um die angeforderten Daten zu ermitteln.

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 erfüllt der Optimierer nicht die an ihn gestellten Erwartungen.

Wenn ein kostenbasierter Optimierer verwendet wird, dann ist die kontinuierliche Aktualisierung der Statistiken 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 viel 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 unterliegt auch einer zeitlichen Restriktion. Damit diese Optimierung nicht zu lange dauert, werden bei vielen DBMS nicht alle theoretisch möglichen Zugriffspläne untersucht sondern z. B. nur maximal 2000. Alle weiteren Zugriffspläne werden nicht untersucht. Wenn bei einem komplexen Zugriff z. B. 200000 theoretisch mögliche Zugriffspläne existieren, dann wird nur 1% aller möglichen Zugriffswege genauer untersucht. Die Wahrscheinlichkeit, dass damit ein guter Zugriffsplan gefunden wird, ist sehr gering. Tatsächlich kommt es oft vor, dass für SQL-Statements, in denen viele Tabellen miteinander gejoint werden, ein Ausführungsplan zum Einsatz kommt, der deutlich schlechter ist, als der eigentlich optimale Ausführungsplan.

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. [1]

Einzelnachweise[Bearbeiten]

  1. Jonathan Lewis: Cost-Based Oracle Fundamentals. Apress, New York 2006, ISBN 1-59059-636-6, Kapitel 10