Datenbankoperator
aus Wikipedia, der freien Enzyklopädie
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 Ausführungsplan, 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 bereit steht. Der Baum wird auch als Operatorbaum bezeichnet.
Inhaltsverzeichnis |
[Bearbeiten] 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.
[Bearbeiten] 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 spezialisierte Operatoren, wie zum Beispiel den Join-Operator, der Selektion und Kreuzprodukt gleichzeitig durchführt, um diese wichtige Operation so effizient wie möglich umzusetzen.
[Bearbeiten] Optimierung
In der Regel kann die selbe 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 sind mathematisch gesehen äquivalent. Moderne Datenbankmangementsysteme haben daher komplexe Anfrageoptimierer, die aus der Menge aller möglichen Ausführungspläne den effizientesten auswählen.
[Bearbeiten] 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, soweit wie möglich im Baum nach unten bewegt.
[Bearbeiten] 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.
[Bearbeiten] 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 soviele Elemente von seinen Datenquellen an, die er benötigt um ein neues Ergebniselement der Ergebnisrelation zu berechnen. Abschließend kann zum Freigeben von Systemressourcen der Operator mittels Close geschlossen werden.
[Bearbeiten] Beispiel
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 join anschrift a on p.id = a.personen_id where a.ort = "Marburg"
Das Bild rechts zeigt, wie die Anfrage als ein Operatorbaum dargestellt wird.
[Bearbeiten] Trivia
Bemerkenswert ist, dass die Umsetzung der Datenbankoperatoren, historisch erklärbar durch die großen Geschwindigkeitsunterschiede bei Zugriffen auf Hauptspeicherplatz beziehungsweise Festplattenplatz, selbst wieder durch Operationen auf baumartigen Datenstrukturen, in der Regel Bayerbäumen oder B*-Baum, 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.
[Bearbeiten] Referenzen
- Datenbankbibliothek zu Lehr- und Forschungszwecken XXL in Java.
[Bearbeiten] Literatur
- Alfons Kemper, André Eickler: Datenbanksysteme - Eine Einführung, ISBN 3486273922
