Anfrageoptimierer

Anfrageoptimierer

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 mitangegeben 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.

Inhaltsverzeichnis

Aufgaben eines Anfrageoptimierers

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

Ein regelbasierter Anfrageoptimierer verwendet zur Ermittlung des Auswertungsplans keine Informationen über das tatsächlich vorhandene Datenvolumen. Es werden nur die vorhanden 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 vorhandenen 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 nehnem 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 regelbasierte Anfrageoptimierer.

Kostenbasierte Anfrageoptimierer

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
  • der größte und der kleinste Wert pro Spalte
  • der Sortierzustand einer Tabelle im Vergleich zur Sortierreihenfolge eines Index (Clusteingorder)
  • 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 vorkommenden 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.

Wichtig bei dem kostenbasierten Optimierer ist die kontinuierliche Aktualisierung der Statistiken. 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 komplexen Zugriffen mit vielen möglichen Zugriffswegen nur ein kleiner Anteil davon genauer untersucht wird, dann ist das Risiko groß, dass der ausgewählte Zugriffsweg viel schlechter ist, als der eigentlich optimale Zugriffsweg.

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 die Möglichkeit, dass danach ein anderer Ausführungsplan zum Einsatz kommt, der zwar rechnerisch besser ist, aber tatsächlich deutlich schlechter ist, 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, dass schon monatelang mit einer guten Performance im Einsatz war, auf einmal eine deutlich schlechtere Performance bekommt. Man ist nie vor bösen Überraschungen sicher. [1]

Einzelnachweise

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

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Auswertungsplan — Bei einem Auswertungsplan (engl.: query evaluation plan (QEP), kurz: query plan), auch Ausführungsplan genannt, handelt es sich um eine Beschreibung, in welchen Einzelschritten ein relationales Datenbankmanagementsystem eine Datenbankabfrage… …   Deutsch Wikipedia

  • Selektivität (Informatik) — Selektivität ist ein Maß, das in der Informatik bei Datenbankabfragen auf Datenbanktabellen in relationalen Datenbankensystemen gebraucht wird; sie bestimmt den Anteil der Datensätze, die bei einer Abfrage nicht durch eine Selektivitätsbedingung… …   Deutsch Wikipedia

  • DBMS — Ein Datenbanksystem (DBS) ist ein System zur elektronischen Datenverwaltung. Die wesentliche Aufgabe eines DBS ist es, große Datenmengen effizient, widerspruchsfrei und dauerhaft zu speichern und benötigte Teilmengen in unterschiedlichen,… …   Deutsch Wikipedia

  • DBVS — Ein Datenbanksystem (DBS) ist ein System zur elektronischen Datenverwaltung. Die wesentliche Aufgabe eines DBS ist es, große Datenmengen effizient, widerspruchsfrei und dauerhaft zu speichern und benötigte Teilmengen in unterschiedlichen,… …   Deutsch Wikipedia

  • Data base management system — Ein Datenbanksystem (DBS) ist ein System zur elektronischen Datenverwaltung. Die wesentliche Aufgabe eines DBS ist es, große Datenmengen effizient, widerspruchsfrei und dauerhaft zu speichern und benötigte Teilmengen in unterschiedlichen,… …   Deutsch Wikipedia

  • Database management system — Ein Datenbanksystem (DBS) ist ein System zur elektronischen Datenverwaltung. Die wesentliche Aufgabe eines DBS ist es, große Datenmengen effizient, widerspruchsfrei und dauerhaft zu speichern und benötigte Teilmengen in unterschiedlichen,… …   Deutsch Wikipedia

  • Datenbankanwendung — Ein Datenbanksystem (DBS) ist ein System zur elektronischen Datenverwaltung. Die wesentliche Aufgabe eines DBS ist es, große Datenmengen effizient, widerspruchsfrei und dauerhaft zu speichern und benötigte Teilmengen in unterschiedlichen,… …   Deutsch Wikipedia

  • Datenbanken — Ein Datenbanksystem (DBS) ist ein System zur elektronischen Datenverwaltung. Die wesentliche Aufgabe eines DBS ist es, große Datenmengen effizient, widerspruchsfrei und dauerhaft zu speichern und benötigte Teilmengen in unterschiedlichen,… …   Deutsch Wikipedia

  • Datenbankmanagementsystem — Ein Datenbanksystem (DBS) ist ein System zur elektronischen Datenverwaltung. Die wesentliche Aufgabe eines DBS ist es, große Datenmengen effizient, widerspruchsfrei und dauerhaft zu speichern und benötigte Teilmengen in unterschiedlichen,… …   Deutsch Wikipedia

  • Datenbankprogramm — Ein Datenbanksystem (DBS) ist ein System zur elektronischen Datenverwaltung. Die wesentliche Aufgabe eines DBS ist es, große Datenmengen effizient, widerspruchsfrei und dauerhaft zu speichern und benötigte Teilmengen in unterschiedlichen,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”