Datenbankoperator

Ein Datenbankoperator ist Teil einer Datenbankanfrage, der für die Ausführung eines einzelnen Teilschrittes der Anfrage zuständig ist. Für eine Anfrage erstellt eine Datenbank einen Auswertungsplan, dessen Ausführung das angeforderte Ergebnis liefert.

Schematisch ist ein Auswertungsplan dabei ein Baum, der die Datenbankoperatoren als Knoten beinhaltet. An den Blättern des Baumes befinden sich die gespeicherten Datentabellen. Von dort werden sie von Operator zu Operator nach oben weitergereicht, bis an der Wurzel das Anfrageergebnis bereitsteht. Der Baum wird auch als Operatorbaum bezeichnet.

Bearbeiten einer Anfrage

Eine Anfrage an eine Datenbank wird bei Relationalen Datenbanken typischerweise als SQL-Anfrage an das Datenbankmanagementsystem gesendet. Hier wird die Anfrage von einem Parser in die relationalen Operationen zerlegt, die nötig sind um die Anfrage zu beantworten.

Logische und physische Operatoren

Man unterscheidet dabei die

• Logischen Operatoren
• Physischen Operatoren

Während die logischen Operatoren die mathematischen Operationen der relationalen Algebra repräsentieren, befinden sich hinter den physischen Operatoren ausführbare Algorithmen, die den logischen Operator implementieren.

Die relationale Algebra definiert die folgenden logischen Operatoren, mit denen alle weiteren Operatoren gebildet werden können:

• Projektion
• Selektion
• Kreuzprodukt
• Umbenennung
• Vereinigung
• Differenz

Jeder logische Operator kann dabei durch sehr unterschiedliche physische Operatoren ausgeführt werden. Das Datenbankmanagementsystem kann zur Laufzeit entscheiden, welche Implementierung in einem speziellen Fall die beste ist. Außerdem gibt es abgeleitete Operatoren, die sich aus den logischen Operatoren durch Verschachtelung ableiten lassen. Ein spezialisierter, abgeleiteter Operatoren ist der Join-Operator, der Selektion und Kreuzprodukt hintereinander durchführt, um diese wichtige Operation so effizient wie möglich umzusetzen. Außerdem sind der Differenz-Operator und der Divisions-Operator weitere abgeleitete Operatoren.

Optimierung

In der Regel kann dieselbe Anfrage auf sehr unterschiedliche Weisen berechnet werden, die abhängig von der Anfrage und den vorhandenen Daten sehr unterschiedlich schnell sein können. Das heißt, beide Ausführungspläne haben mengenmäßig das gleiche Ergebnis und sind daher mathematisch gesehen äquivalent. Moderne Datenbankmanagementsysteme haben daher komplexe Anfrageoptimierer, die aus der Menge aller möglichen Ausführungspläne den effizientesten auswählen.

Logische Optimierung

Zunächst wird hier eine logische Optimierung vorgenommen. Es wird untersucht, ob sich eine Anfrage mathematisch vereinfachen lässt, ohne das Ergebnis zu beeinflussen. Das heißt, der Operatorbaum wird in einen äquivalenten Baum transformiert. Typischerweise werden hier mehrfache Selektionsoperatoren auf der gleichen Datenquelle eliminiert oder Selektionsoperatoren, die immer zu einer Reduktion des Aufwands führen, so weit wie möglich im Baum nach unten bewegt.

Physische Optimierung

Im nächsten Schritt findet die physische Optimierung statt. Nun wählt der Optimierer den bestmöglichen Algorithmus für eine Operation aus. Dabei berücksichtigt er die Kardinalität einer Datenquelle, also die Anzahl der Elemente, die verarbeitet werden müssen, sowie vorhandene Indizes auf einer Relation. So gibt es Algorithmen, die nur dann sehr schnell sind, wenn ein Index vorhanden ist, wie beispielsweise der Index-Join.

ONC

Jeder Operator ist ein Knoten in einem Operatorbaum. Daher hat er ein oder zwei Datenquellen und genau eine Datenausgabe, mit dem Daten an einen anderen Operator weitergegeben werden kann. Die Operatoren sind typischerweise als Iteratoren mit einer ONC-Schnittstelle implementiert. ONC steht hier für Open, Next, Close. Der Operator wird also mit Open initial geöffnet. Dann kann mit Next über die Elemente, die der Operator liefert, iteriert werden. Bei jedem Iterationsschritt fordert der Operator so viele Elemente von seinen Datenquellen an, die er benötigt, um ein neues Ergebniselement der Ergebnisrelation zu berechnen. Abschließend kann zur Freigabe von Systemressourcen der Operator mittels Close geschlossen werden.

Beispiel

Operatorbaum der Beispielanfrage

Angenommen, es sind zwei Relationen person und anschrift mit den folgenden Attributen gegeben:

person.id

person.vorname

person.name

person.geburtsdatum

anschrift.id

anschrift.personen_id

anschrift.strasse

anschrift.ort

Dann würde die Anfrage nach allen Personen aus Marburg wie folgt aussehen:

select p.name from person p , anschrift a  where a.ort = ’Marburg’ AND  p.id = a.personen_id;

Das Bild rechts zeigt, wie die Anfrage als ein Operatorbaum dargestellt wird. Das Tool SELECT2OBaum bietet die Möglichkeit, SELECT-Abfragen interaktiv in Operatorbäume umzuwandeln.

Sonstiges

Bemerkenswert ist, dass die Umsetzung der Datenbankoperatoren, bis heute erklärbar durch die großen Geschwindigkeitsunterschiede bei Zugriffen auf Hauptspeicherplatz beziehungsweise Festplattenplatz, selbst wieder durch Operationen auf baumartigen Datenstrukturen, in der Regel B-Bäume oder B*-Bäume, implementiert wurden. In dem Maße, wie solche Geschwindigkeitsflaschenhälse beseitigt werden, können auch weniger performante oder problemähnliche Datenstrukturen benutzt werden. Die Geschwindigkeitsflaschenhälse in der Speicherorganisation ähneln den Flaschenhälsen nach von Neumann, siehe auch Speicherhierarchie.

Literatur

• Alfons Kemper, André Eickler: Datenbanksysteme – Eine Einführung. ISBN 3-486-27392-2

Weblinks

• XXL in Java – Datenbankbibliothek zu Lehr- und Forschungszwecken