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 _^[1] und _^[2].)

Mit der Vorstellung der Relationenalgebra hat E.F. Codd^[3] 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:

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^[6] 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.

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

1. ↑ Peter Dadam: Datenbanksysteme - Konzepte und Modell (Vorlesung Universität Ulm). Kapitel 3: Hierarchisches Datenmodell, 2013, S. 57–87 (researchgate.net). 
2. ↑ Peter Dadam: Datenbanksysteme - Konzepte und Modelle (Vorlesung Universität Ulm). Kapitel 4: Netzwerk-Datenmodell, 2013, S. 90–137 (researchgate.net). 
3. ↑ E. F. Codd: A relational model of data for large shared data banks. In: Communications of the ACM. Band 13, Nr. 6, Juni 1970, ISSN 0001-0782, S. 377–387, doi:10.1145/362384.362685 (acm.org [abgerufen am 20. Februar 2023]). 
4. ↑ Peter Dadam: Verteilte Datenbanken und Client/Server-Systeme. Springer, Berlin / Heidelberg / New York 1996, ISBN 3-540-61399-4, S. 130. 
5. ↑ ^{a b c} Peter Dadam: Datenbanksysteme - Konzepte und Modelle (Vorlesung, Universität Ulm). Kapitel 6: Relationales Datenmodell II: "Klassisches SQL", Abschnitt 6.8: Anfragebearbeitung. Ulm 2013, S. 234–261 (researchgate.net). 
6. ↑ Donald D. Chamberlin, Raymond F. Boyce: SEQUEL: A structured English query language. In: Proceedings of the 1976 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control - FIDET '76. ACM Press, Not Known 1976, S. 249–264, doi:10.1145/800296.811515 (acm.org [abgerufen am 20. Februar 2023]).