along/secondo
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
secondo/Optimizer/Subqueries/kapitel/review.tex
along dfd1e74548 firs commit
2026-01-23 17:03:45 +08:00

390 lines
39 KiB
TeX
Raw Permalink Blame History

%
% Review
%
%
\chapter{Review}\label{chp:Review}
Dieses Kapitel gibt einen Überblick über die für die Umsetzung dieser Arbeit verwendeten Technologien und deren theoretische Grundlagen. Anschließend werden die in der Literatur bekannten Ansätze zur Optimierung geschachtelter Abfragen dargestellt.
\section{Überblick}\label{sct:Überblick}
Ein Datenbanksystem ist eine Sammlung zusammenhängender Dateien und Programme, die es einem Benutzer erlauben auf diese Dateien zuzugreifen und diese zu ändern. Eine Hauptaufgabe eines Datenbanksystems ist es, dem Benutzer eine abstrakte Sicht auf die Daten zu ermöglichen. Die physikalische Ablage und der eigentliche Zugriff auf die Daten werden dabei vor dem Benutzer verborgen. Dabei können drei Abstraktionsebenen unterschieden werden.
Die interne Ebene beschreibt, wie die Daten physikalisch abgelegt werden. Mit Hilfe von systemnahen komplexen Datenstrukturen wird die physische Ablage der Daten beschrieben.
Die konzeptuelle Ebene umfasst die Beschreibung der Art der Daten und der Beziehungen zwischen den Daten. In ihr wird die gesamte Datenbank auf der Basis von vergleichsweise einfachen Strukturen beschrieben. Bei der Realisierung der Strukturen auf der konzeptuellen Ebene kann auf die Strukturen der physischen Ebene zurückgegriffen werden. Für einen Benutzer der logischen Ebene, z.B. einen Datenbankadministrator, muss dies jedoch nicht sichtbar sein.
Auf der höchsten Abstraktionsebene, der externen Ebene, wird nur ein Teil der Datenbank beschrieben. Obwohl die konzeptuelle Ebene mit einfacheren Strukturen arbeitet, bleibt eine gewisse Komplexität wegen der Unterschiedlichkeit der in einer großen Datenbank gespeicherten Informationen. Viele Benutzer eines Datenbanksystems benötigen nicht alle Informationen; stattdessen brauchen sie nur einen Teil der Datenbank. Die externe Ebene dient der Vereinfachung beim Zugriff auf das System. Es können beliebig viele Sichten auf eine Datenbank existieren.
Jedem Datenbanksystem liegt ein Datenmodell zugrunde. Das Datenmodell beschreibt die konzeptuellen Einheiten und Werkzeuge, um Daten, Beziehungen zwischen den Daten, die Semantik der Daten und Konsistenzeinschränkungen zu beschreiben. Verbreitete Datenmodelle für Datenbanken sind das relationale und das objektorientierte Datenbankmodell.
Die Grundelemente des relationalen Datenmodells sind Attribute, Tupel und Relationen. Eine Relation wird durch ihr Relationenschema eindeutig beschrieben. Ein Relationenschema ist eine Menge von Attributen. Durch einen zugeordneten Datentyp und einen Namen bestimmt ein Attribut die möglichen Werte, die die Ausprägungen des Attributs annehmen können. Ein Tupel ist eine konkrete Ausprägung, d.h. eine Zeile einer Relation (Tabelle). Damit ist eine Relation eine Menge von Tupeln.
Die Relationenalgebra lässt sich durch folgende Konstruktionsvorschriften eindeutig beschreiben.
Es seien $E_1$ und $E_2$ Ausdrücke über der Relationenalgebra, dann lassen sich alle Ausdrücke der Relationenalgebra mit den folgenden Operationen bilden:
\begin{itemize}
\item $E_1 \cup E_2$
\item $E_1 - E_2$
\item $E_1 \times E_2$
\item $\sigma_P(E_1)$, wobei P ein Prädikat über Attributen von $E_1$ ist.
\item $\pi_S(E_1)$, wobei S eine Teilmenge der Attribute von $E_1$ ist.
\item $\rho_x(E_1)$, wobei $x$ ein neuer Name für das Ergebnis von $E_1$ ist.
\end{itemize}
(\cite{DBLP:books/mg/SilberschatzKS01})
Die Vereinigung ($\cup$) hat als Ergebnis die Vereinigung der Ergebnisse der beiden Ausdrücke $E_1$ und $E_2$. Voraussetzung für die Vereinigung ist die Übereinstimmung der beiden Ausdrücke in ihrem Relationenschema.
Die Mengendifferenz (-) ermittelt alle Tupel, die im ersten Ausdruck enthalten sind, nicht aber im zweiten.
Das Kreuzprodukt zweier relationaler Ausdrücke, bezeichnet mit ($\times$), liefert die Verkettung jedes Tupels des ersten Ausdrucks mit jedem Tupel des zweiten Ausdrucks. Hat $E_1$ $n_1$ Tupel und $E_2$ $n_2$ Tupel, so hat das Kreuzprodukt $n_1 * n_2$ Tupel.
Mit der Selektionsoperation ($\sigma$) werden nur die Tupel ermittelt, die das angegebene Prädikat erfüllen.
Die Projektion ($\pi$) schränkt das Ergebnisschema auf die angegebenen Attribute ein.
Während Relationen und Attribute über einen Namen spezifiziert sind, sind die Ergebnisse relationaler Ausdrücke ohne Bezeichnung. Mit der Umbenennungsoperation ($\rho$) wird dem Ergebnis eines relationalen Ausdrucks eine Bezeichnung zugeordnet. Dies kann auf Relationenebene geschehen, d.h. das Ergebnis bekommt einen Namen zugeordnet. Es ist aber auch möglich, die Attribute des Ergebnisses umzubenennen.
\subsection{SQL}
Relationale Datenbanken beruhen auf der von E.F. Codd vorgeschlagenen Relationenalgebra und dem ebenfalls von Codd vorgestellten Relationenkalkül \cite{DBLP:books/mg/SilberschatzKS01}. Ein grundsätzlicher Vorteil des relationalen Datenbankmodells ist die Möglichkeit, die gewünschten Ergebnisse einer Abfrage auf einem hohen Abstraktionsniveau formulieren zu können. Die Zugriffspfade auf die Daten müssen hier nicht mit angegeben werden. Die Relationenalgebra ist abgeschlossen, d.h. das Ergebnis jedes Ausdrucks ist ebenfalls wieder eine Relation. Da die mathematischen Grundlagen der Relationenalgebra und des Relationenkalküls für nicht-technische Benutzer einer Datenbank nicht einfach zu verstehen sind, wurde viel Arbeit in die Entwicklung einer Datenbanksprache gesteckt, die genauso mächtig ist wie das Relationenkalkül und die Relationenalgebra, sich aber leichter erlernen lässt. Eines der interessantesten Merkmale von SQL ist die Möglichkeit, Abfrageblöcke beliebig zu schachteln. Eine geschachtelte Abfrage enthält einen weiteren Abfrageblock als Teilausdruck. Die Syntax für geschachtelte Abfragen wird weiter unten dargestellt. Die Begriffe innerer Abfrageblock und Unterabfrage werden im Folgenden synonym verwendet.
Eine Abfrage ohne geschachtelte Prädikate hat die Schachtelungstiefe 1. Enthält eine Abfrage mindestens einen weiteren Abfrageblock der maximalen Schachtelungstiefe n, so hat sie die Schachtelungstiefe n + 1. Die Schachtelungstiefe gibt also an, auf wie vielen Ebenen die Abfrageblöcke geschachtelt sind.
SQL ist eine auf dem relationalen Datenbankmodell beruhende Datenbanksprache. Mit ihr können in relationalen Datenbanken die Metadaten der Relationen angelegt und geändert werden. Außerdem erlaubt sie die Manipulation der Daten. Auch die granulare Vergabe von Berechtigungen wurde in SQL standardisiert.
%\begin{itemize}
% \item Datenbanksprache
% \subitem Datendefinition (DDL)
% \subitem Datenmanipulation (DML)
% \subitem Rechtevergabe (DCL)
Ein typischer Abfrageblock hat die Form
\begin{lstlisting}
select §$A_1,A_2,\cdots,A_n$§
from §$r_1,r_2,\cdots,r_m$§
where P
\end{lstlisting}
Grundsätzlich besteht eine SQL-Abfrage aus den drei Klauseln \sql{select}, \sql{from} und \sql{where}. Diese bilden einen sogenannten Abfrageblock. In der \sql{select}-Klausel werden die Attribute der Ergebnisrelation angegeben. Die \sql{from}-Klausel gibt die Quellrelationen an, aus denen das Ergebnis ermittelt wird. Die optionale \sql{where}-Klausel gibt schließlich Einschränkungen an, denen die Ergebnistupel genügen müssen.
Die \sql{select}-Klausel entspricht der Projektions-Operation der Relationenalgebra. In ihr werden alle Attribute der Ergebnisrelation angegeben. Um alle Attribute der beteiligten Relationen zu erhalten gibt es die spezielle Notation \enquote{*}. Mit Ihr wird also das Schema der Ergebnisrelation festgelegt.
Die \sql{from}-Klausel entspricht dem kartesischen Produkt in der Relationenalgebra. Hier werden alle in der Abfrage verwendeten Relationen aufgeführt.
Die \sql{where}-Klausel entspricht der Selektions-Operation der Relationenalgebra. Das Prädikat P ist ein boolescher Ausdruck über den Attributen der in der \sql{from}-Klausel angegebenen Relationen. Ist der Ausdruck die Konjunktion mehrerer Terme, so spricht man auch bei den einzelnen Termen von einem Prädikat der Abfrage.
Es gibt in SQL zwei Konstrukte, die sich nicht mit der Relationenalgebra ausdrücken lassen. D.h. SQL ist echt mächtiger als die Relationenalgebra. Die Konstrukte sind \sql{null}-Werte und Aggregationsfunktionen.
\sql{null}-Werte sind spezielle Attributwerte, die die Abwesenheit eines Werts anzeigen. Boolesche-Ausdrücke mit \sql{null}-Werten entsprechen einer dreiwertigen Logik, da als Ergebnis die Werte \sql{true}, \sql{false} und \sql{null} auftreten können.
Aggregationsfunktionen berechnen Werte über allen Tupeln einer Relation. Die im SQL-Standard definierten Aggregationsfunktionen sind
\begin{itemize}
\item \sql{count} -- Anzahl der Tupel
\item \sql{sum} -- Summe eines Attributwerts
\item \sql{avg} -- Durchschnitt eines Attributwerts
\item \sql{min} -- Minimum eines Attributwerts
\item \sql{max} -- Maximum eines Attributwerts
\end{itemize}.
Als Parameter wird ein Attribut angegeben, über dessen Werten die Aggregation berechnet wird. Dabei kann jede der Aggregationsfunktionen in einer mengenbasierten und einer multimengenbasierten Variante aufgerufen werden. Mit dem Zusatz \sql{distinct} wird die strikt mengenbasierte Variante gewählt, mit dem impliziten Parameter \sql{all} die multimengenbasierte. Implizit bedeutet in diesem Fall, ein Aggregationsausdruck ohne Zusatz wird berechnet wie ein Ausdruck, bei dem \sql{all} explizit angegeben wurde. Ein \sql{count}-Ausdruck hat z.B. die Form \sql{count(distinct $C$)} bzw. \sql{count($C$)} für die multimengenbasierte Semantik. Der Operator \sql{count} existiert auch noch in einer tupelbasierten Variante: \sql{count(*)}. Diese unterscheidet sich nur in Bezug auf die Behandlung von \sql{null}-Werten vom spaltenbasierten Operator.
\sql{group by\dots having}-Klausel. Die Eingabemenge der Aggregationsfunktion wird in Gruppen mit gleichen Attributwerten in den angegebenen Attributen partitioniert; die Aggregationsfunktion wird dann jeweils separat für jede Gruppe berechnet. Die optionale \sql{having}-Klausel erlaubt die Selektions-Operation auf den Ergebnissen der Aggregationsfunktion(en). Hierzu wird ein Prädikat angegeben, das auf das Ergebnis der Aggregation angewandt wird. Nur Ergebnistupel, für die dieses Prädikat zu \sql{true} auswertet, werden in die Ergebnisrelation übernommen.
In der \sql{order by}-Klausel werden die Ergebnisattribute angegeben, nach welchen das Ergebnis sortiert werden soll. Mit dem Zusatz \sql{asc} bzw. \sql{desc} hinter dem Attributnamen kann zwischen auf- und absteigender Sortierung für das entsprechende Attribut gewählt werden. Die Reihenfolge der Attribute in der \sql{order by}-Klausel gibt die Rangfolge bei der Sortierung an.
% \item geschachtelte Abfragen
%
% \subitem in der \sql{select}-Klausel.
% \subitem in der \sql{from}-Klausel
% \subitem in der WHERE Klausel
% \subitem in der \sql{group by}\dots \sql{having}-Klausel (nicht implementiert) Die \sql{group by}\dots \sql{having}-Klausel erlaubt die Angabe eines Prädikats, das auf das Ergebnis einer Aggregation angewandt wird.
Der SQL-Standard unterscheidet in
\begin{enumerate}
\item scalar subqueries -- Ergebnis der Abfrage ist ein einzelner Wert. Diese Form der Unterabfrage darf an jeder Stelle in einem Abfrageblock verwendet werden, an dem auch eine skalare Konstante zulässig wäre.
\item row subqueries -- Ergebnis der Abfrage ist eine Liste bzw. Menge von Werten.
\item table subqueries -- Ergebnis der Abfrage ist eine Relation.
\end{enumerate}.
Zusätzlich kann man die Unterabfrage nach dem Ort ihres Auftretens unterscheiden.
%\begin{itemize}
% \item SQL-Standard unterscheidet in
% \subitem \enquote{scalar subqueries} (Ergebnis der Abfrage ist ein einzelner Wert). Diese Form der Unterabfrage darf an jeder Stelle in einem Abfrageblock verwendet werden, an dem auch eine skalare Konstante zulässig wäre.
% \subitem \enquote{row subqueries} (Ergebnis der Abfrage ist eine Liste/Menge von Werten)
% \subitem \enquote{table subqueries} (Ergebnis der Abfrage ist eine Relation)
% \item nach Korrelation
% \subitem nicht-korreliert (trivial, Ergebnis ist Konstante/Liste von Konstanten)
% \subitem korrelierte geschachtelte Abfrage
% \subsubitem ohne Aggregation
% \subsubitem mit Aggregation
% \item Ort des Auftretens
%\end{itemize}
\begin{enumerate}
\item In der \sql{select}-Klausel -- Das Ergebnis der Auswertung der geschachtelten Abfrage wird in die Ergebnisrelation aufgenommen. In der \sql{select}-Klausel sind nur skalare Unterabfragen zulässig.
\item In der \sql{from}-Klausel -- Komplexe Abfragen über mehrere Relationen lassen sich oft verständlicher formulieren, wenn in einem ersten Schritt die notwendigen Daten zu einer Relation zusammengefasst werden. Im darauf folgenden Schritt wird dann die eigentliche Abfrage über dieser neuen Relation formuliert. Diese Form der Strukturierung lässt sich durch Unterabfragen in der \sql{from}-Klausel bewerkstelligen. Die Unterabfrage liefert die Zusammenfassung der Daten, auf deren Basis die Abfrage formuliert wird.
\item In der \sql{where}-Klausel -- Geschachtelte Abfragen in der \sql{where}-Klausel bieten die Möglichkeit, das Ergebnis einer Abfrage in einer Bedingung zu verwenden. Hierzu können die Operatoren \sql{in}, \sql{exists}, \sql{all}, \sql{any} und skalare Vergleichsoperatoren benutzt werden. Die Semantik dieser Operatoren wird in den nachfolgenden Absätzen kurz skizziert.
\item In der \sql{group by}\dots \sql{having}-Klausel -- Auch in den Prädikaten der \sql{having}"=Klau"-sel kann auf Unterabfragen zurückgegriffen werden. Allerdings kann nur auf die Attribute der Ergebnisrelation der zuvorstehenden Abfrage zugegriffen werden. D.h. die Ausdrücke in einem Prädikat beziehen sich auf ein \sql{group by}-Attribut oder ein Aggregationsergebnis.
\begin{lstlisting}
select §$A_i$§, §$avg(A_j)$§
from §$R_n$§ as R
group by §$A_i$§
having §$avg(A_j)$§ >
(select §$avg(A_j)$§
from §$R_n$§
where §$R.A_i$§ = §$A_i$§)
\end{lstlisting}
\end{enumerate}
Der \sql{in}-Operator prüft das Enthaltensein eines Werts in einer Menge. Die Menge kann durch Auflistung oder durch eine Abfrage spezifiziert werden. Ein geschachteltes Prädikat mit dem \sql{in}-Operator ist genau dann wahr, wenn der Wert auf der linken Seite (Attribut oder Zeile) im Ergebnis der Unterabfrage enthalten ist.
\begin{lstlisting}
§$A_i$§ in (select §$A_j$§ from §$R_n$§ where P)
\end{lstlisting}
Mit dem \sql{exists}-Operator wird die Ergebnisrelation darauf überprüft, ob sie mindestens ein Ergebnistupel enthält. In nicht-korrelierten Prädikaten ist die Verwendung von \sql{exists} meist nicht relevant, da das Prädikat in diesem Fall zu der Konstant \sql{TRUE} bzw. \sql{FALSE} auswertet. Bei korrelierten Prädikaten lassen sich mit \sql{exists} komplexe Bedingungen prüfen.
\begin{lstlisting}
exists(select §$A_j$§ from §$R_n$§ where P)
\end{lstlisting}
Die Operatoren \sql{any} und \sql{all} entsprechen den Quantoren $\exists$ und $\forall$ der Prädikatenlogik erster Stufe. Das Ergebnis eines Prädikats mit dem \sql{any}-Operator ist genau dann wahr, wenn mindestens ein Tupel der Ergebnisrelation den Vergleich $\theta$ erfüllt. Als Vergleichsoperator sind die skalaren Operatoren $<, <=, =, >, >=$ mit ihrer üblichen Semantik und der Operator <> mit der Bedeutung \enquote{ungleich} zulässig. Um den semantischen Unterschied des Operators \sql{any} zu der Verwendung des Wortes \enquote{any} in der englischen Sprache zu betonen und Missverständnisse zu vermeiden, wurde mit SQL92 der Operator \sql{some} mit identischer Semantik eingeführt.
\begin{lstlisting}
§$A_i$§ §$\theta$§ any(select §$A_j$§ from §$R_n$§ where P)
\end{lstlisting}
Der \sql{all}-Operator wertet zu \sql{TRUE} aus, wenn der Vergleich für alle Ergebnistupel positiv ausfällt. Die zulässigen Vergleichsoperatoren sind dieselben wie beim Operator \sql{any}.
\begin{lstlisting}
§$A_i$§ §$\theta$§ all(select §$A_j$§ from §$R_n$§ where P)
\end{lstlisting}
\subsection{TPC-D Benchmark}
TPC \footnote{TPC = Transaction Processing Performance Council} ist eine Vereinigung von IT-Unternehmen. Ziel des TPC ist es, standardisierte Benchmarks zur Bewertung von Transaktionssystemen zur Verfügung zu stellen. Mit diesen Benchmarks können herstellerunabhängig Datenbanksysteme verglichen werden. Je nach Anwendungsgebiet werden verschiedene Metriken zum Vergleich von real verfügbaren Systemen bereitgestellt. Der in dieser Arbeit für den Vergleich herangezogene Benchmark TPC-D ist ein Entscheidungshilfe-Benchmark. In dem Benchmark sind 22 Abfragen zusammengefasst, die Antworten auf betriebswirtschaftliche Fragestellungen geben. Insgesamt 14 dieser Abfragen haben geschachtelte Abfrageblöcke und eignen sich daher als Anschauungsobjekt für die Optimierung geschachtelter Anfragen. In Kapitel \ref{chp:Leistungsbewertung} findet sich eine Gegenüberstellung der geschachtelten und der optimierten Ausführung dieser Abfragen. Ziel des Benchmarks ist der Vergleich von Datenbanksystemen über Metriken, die sowohl die Performance, gemessen über die Antwortzeiten der Abfragen, als auch die Kosten für die verwendete Hardware mit einbeziehen. Die Ergebnisse eines solchen Benchmarks können nach einer Überprüfung durch den TPC auf der Website \url{http://www.tpc.org/} veröffentlicht werden.
\subsection{Beschreibung SECONDO}\label{sct:Beschreibung SECONDO}
\textsc{Secondo} ist ein modular aufgebautes, erweiterbares Datenbanksystem. Es können sowohl das zugrundeliegende Datenmodell, als auch die verfügbaren Datentypen und Operatoren beliebig erweitert und ausgebaut werden.
Über den Formalismus der Signaturen zweiter Ordnung (\textbf{SECOND} \textbf{O}rder Signatures) lassen sich die Datentypen und Operationen auf den Datentypen beschreiben. Signaturen zweiter Ordnung sind zwei gekoppelte Signaturen. Die Sorten der ersten Signatur werden \secondo{KIND} genannt, die Operationen Typ-Konstruktoren. Die im System verfügbaren Datentypen sind genau die Ausdrücke dieser Signatur. Die zweite Signatur beschreibt Operationen auf diesen Datentypen. Über die Implementierung von Algebramodulen lässt sich \textsc{Secondo} um beliebige Datentypen und Operationen auf diesen Datentypen erweitern. Zu den bereits verfügbaren Datentypen gehören neben den üblichen Basisdatentypen, wie z.B. \secondo{integer}, unter anderem auch räumliche (spatiale) und raum-zeitliche (spatio-temporale) Datentypen, die z.B. in Geoinformationssystemen verwendet werden können.
\textsc{Secondo} besteht aus den drei Komponenten Kernel, Optimierer und grafischer Benutzeroberfläche (GUI). Diese drei Komponenten können getrennt, aber auch im Zusammenspiel genutzt werden.
Der Kernel ist in C++ geschrieben und bietet die Möglichkeit Ausdrücke in der \textsc{Secondo}-eigenen Syntax auszuführen. Hierzu gibt es eine Kommandozeilen-Schnittstelle, über die mit dem Kernel kommuniziert werden kann. Zusätzlich kann der Kernel auch im Client/Server-Betriebsmodus gestartet werden. Er bietet dann anderen Komponenten die Möglichkeit, auf den Kernel zuzugreifen. Abfragen über Relationen werden mit Tupelströmen realisiert, d.h. zur Ausführungszeit wird einem Operator auf Anforderung das nächste Tupel bereitgestellt oder das Ende des Stroms signalisiert. Dadurch ist es nicht notwendig die beteiligten Relationen vollständig im Speicher vorhalten zu müssen bzw. über Paging-Mechanismen bereitzustellen.
Mit dem Optimierer können SQL-ähnliche Ausdrücke in ausführbare Pläne übersetzt werden. Dies kann losgelöst von den anderen Komponenten über die Kommandozeile erfolgen. Zusätzlich gibt es auch beim Optimierer die Möglichkeit, ihn im Client/Server-Modus zu starten.
Der Optimierer bietet die Möglichkeit, conjunctive query optimization durchzuführen. D.h. es werden für die Optimierung alle Konjunktionsterme des Prädikats betrachtet. Basis des Optimierers ist ein in \cite{Güting02,DBLP:conf/ideas/DiekerG00} vorgestellter Optimierungsalgorithmus der auf kürzesten Pfaden in einem predicate order graph (pog) beruht. Ein pog zu einer Liste von n Prädikaten ist ein n-dimensionaler Hyperwürfel mit zwei ausgezeichneten Knoten maximaler Entfernung, die mit 0 bzw. $2^n$ bezeichnet werden. Hierbei stellen die Pfade die Permutationen der Konjunktionsterme des Prädikats dar. Jeder Knoten gibt durch seine Nummer die ausgewerteten Prädikate an. Die ausgewerteten Prädikate werden in Bits kodiert. Beim Knoten mit der Nummer 5 (binär 101) sind also die Prädikate 1 und 3 bereits ausgewertet. Jede Kante steht für einen booleschen Ausdruck. Für jede Übersetzungsmöglichkeit dieses Ausdrucks wird eine \enquote{ausführbare Kante} erzeugt. Durch die Bewertung der Kanten mit Kosten (die sich aus der Selektivität und den Ausführungskosten des Ausdrucks zusammensetzen) entspricht ein bezüglich der Kosten kürzester Pfad einer optimalen Reihenfolge der Prädikatsauswertung.
Die Implementierung des Optimierers ist in Prolog geschrieben. Da die vom Optimierer erkannte SQL-ähnliche Sprache aus gültigen Prolog-Ausdrücken besteht, werden das Parsen und Übersetzen in entsprechende Datenstrukturen von der Prolog-Laufzeitumgebung übernommen. Die Übersetzung der SQL-ähnlichen Ausdrücke in die ausführbare \textsc{Secondo}-Syntax besteht aus den im Folgenden beschriebenen Phasen. In der ersten Phase wird der Ausdruck umgeschrieben. Abhängig von den gewählten Optionen des Optimierers werden z.B. enthaltene Makros ausgewertet, redundante Prädikate entfernt oder der Ausdruck so umstrukturiert, dass an mehreren Stellen verwendete Teilausdrücke nur einmal ausgeführt werden müssen (CSE -- common subexpression elimination). In diese Phase integrieren sich die Ent\-schach\-te\-lungs\-al\-go\-rith\-men, die im Rahmen dieser Arbeit implementiert wurden. Im zweiten Schritt werden die Schema-Daten der an der Abfrage beteiligten Datenbankobjekte (Attribute, Relationen und konstante Objekte) ermittelt und als Prolog-Fakten gespeichert. Sie werden zum Aufbau des predicate order graphs benötigt. Im nächsten Schritt wird der optimale Plan mit dem oben beschriebenen Optimierungsalgorithmus ermittelt. Im letzten Schritt wird aus dem Plan, der immer noch ein gültiger Prolog-Term ist, ein Ausdruck in der ausführbaren Syntax des \textsc{Secondo}-Kernels generiert. Falls vom Benutzer gewünscht, kann die Abfrage direkt aus dem Optimierer heraus an den \textsc{Secondo}-Kernel gestellt werden. Das Ergebnis wird dann ebenfalls im Optimierer ausgegeben.
Die vom Optimierer unterstützte SQL-Syntax ist in Anhang \ref{apd:Secondo SQL-Dialekt} angegeben, inklusive der in dieser Arbeit implementierten Erweiterungen. Grundsätzlich wird eine SQL-Abfrage durch folgende Struktur abgebildet, wobei kursiv dargestellte Knoten optionale Teile einer Abfrage sind.
% Set the overall layout of the tree
\tikzstyle{level 1}=[level distance=2cm, sibling distance=4cm]
\tikzstyle{level 4}=[level distance=2cm, sibling distance=2cm]
% Define styles for bags and leafs
\tikzstyle{bag} = [text width=4em, text centered]
%\tikzstyle{end} = [circle, minimum width=3pt,fill, inner sep=0pt]
\tikzstyle{end} = [text width=4em, text centered]
\begin{tikzpicture}[grow=down]
\node[bag] {\optional{first/last}}
child {
node[end, label=below:
{}]{\optional{Limit}}
edge from parent
node[above] {}
node[below] {}
}
child {
node[bag] {\optional{groupby}}
child {
node[end, label=below:
{}]{\optional{grouping Attribute}}
edge from parent
node[above] {}
node[below] {}
}
child {
node[bag] {\optional{sortby}}
child {
node[end, label=below:
{}]{\optional{Sortierungs Attribute}}
edge from parent
node[above] {}
node[below] {}
}
child {
node[bag] {from}
child{
node[bag] {select}
child {
node[end, label=below:
{}] {\optional{Selektions Attribute}}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
}
child{
node[end, label=below:
{}] {Relationen}
edge from parent
node[above] {}
node[below] {}
}
child {
node[bag] {\optional{where}}
child {
node[end, label=below:
{}] {\optional{Prädikate}}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
}
edge from parent
node[above] {}
node[below] {}
};
\end{tikzpicture}
Die grafische Benutzeroberfläche ist in Java implementiert. Mit ihr können Abfragen sowohl an den Optimierer als auch an den Kernel gestellt werden. Zusätzlich ist sie in der Lage z.B. raum-zeitliche Datentypen darzustellen. Es wird eine zweidimensionale Projektion der Daten dargestellt, die über die Zeitachse abgespielt werden kann. Hierbei kann die Geschwindigkeit variiert werden. Durch Erweiterungen kann die GUI um die Darstellung beliebiger Datentypen ergänzt werden. Da die GUI die Möglichkeit bietet, das Ergebnis einer Abfrage in einem eigenen Format zu speichern, kann man ihre Darstellungsmöglichkeiten auch ohne Kernel und Optimierer benutzen.
%\begin{itemize}
% \item Erweiterbares Datenbanksystem
% \item Second-Order-Signatures
% \item Kernel/Algebren
% \item Optimierer
% \item GUI
% \item Client/Server Betrieb
%\end{itemize}
\section{Ausführungsstrategien}
\subsection{Geschachtelte Iteration}
%\cite{375748,1247598,ISO:1992:IITa}
Die Semantik der Auswertung von geschachtelten Abfragen wird im SQL-Standard \cite{ISO:1992:IITa} definiert. Das Ergebnis einer geschachtelten Abfrage erhält man, indem der innere Abfrageblock für jedes Tupel des äußeren Abfrageblocks ausgewertet wird. Enthält die Unterabfrage korrelierte Prädikate, d.h. Prädikate, die sich auf Attribute der Relationen des äußeren Abfrageblocks beziehen, so werden die entsprechenden Werte aus dem Tupel des äußeren Abfrageblocks als Konstanten in die Prädikate der Unterabfrage übernommen. Diese Form der Auswertung ist für große äußere Relationen nicht sehr performant. Bei Unterabfragen mit Aggregationsfunktion muss die Aggregation für jedes Tupel der äußeren Relation neu berechnet werden. In \cite{319745, 38723} werden Kostenberechnungen für Beispiele durchgeführt, die eine Verbesserung der notwendigen I/O-Operationen für eine Abfrage um ein bis zwei Größenordnungen zeigen.
\subsection{Entschachtelung}
Es wurde schon früh beobachtet, dass es zu bestimmten geschachtelten Abfragen inhaltlich äquivalente Abfragen gibt, die ohne Schachtelung auskommen. In \cite{319745} wurde erstmals die Formalisierung dieser Äquivalenz untersucht, um geschachtelte Abfragen durch Optimierung der Ausführungspläne beschleunigen zu können. Ebd. wird ein Verfahren vorgestellt, eine geschachtelte Abfrage durch Transformation in eine inhaltlich äquivalente, nicht geschachtelte Abfrage zu optimieren. Die dort vorgestellten Algorithmen benötigen nur die erweiterten Standard-Operationen der Relationenalgebra. Ziel der Entschachtelungen ist die Überführung geschachtelter Abfrageblöcke in eine inhaltlich äquivalente Form. Zwei Abfrageblöcke sind inhaltlich äquivalent, wenn für jede beliebige Interpretation (Belegung mit Werten) der Variablen (in diesem Fall Relationen, Attribute und Konstanten), das Ergebnis der Abfrage übereinstimmt. Grundsätzlich haben die Entschachtelungsansätze gemeinsam, dass Äquivalenzen aufgestellt werden, die die Transformation einer Abfrage in eine strukturell anders aufgebaute Abfrage erlauben. Dabei unterscheiden sich die verschiedenen Ansätze in der für die Optimierung genutzten Notation der Abfrage. Die Relationenalgebra wird je nach Ansatz um verschiedene Operatoren erweitert. Dabei wird die Relationenalgebra zwar funktional erweitert, es findet jedoch keine Erweiterung der Ausdrucksstärke statt. D.h. die eingeführten Operatoren lassen sich grundsätzlich durch komplexe Ausdrücke über den Standardoperatoren darstellen. Vorteil der Einführung der neuen Operatoren ist die Möglichkeit, mit Hilfe dieser Operatoren Transformationen zu formulieren, die eine optimierte Formulierung einer geschachtelten Abfrage zulassen. Dienen die Operatoren nur der algebraischen Optimierung und können sie durch algebraische Transformationen immer aus einem Ausdruck entfernt werden, so ist keine Implementierung notwendig. Andernfalls ist eine effiziente Implementierung erforderlich. Während in \cite{319745,38723,671634} die Abfrage in SQL-Notation transformiert wird, wird die Abfrage in \cite{375748,756653} in Ausdrücke einer erweiterten Relationenalgebra übersetzt und algebraisch transformiert.
In \cite{375748} wird die SQL-Abfrage erst einmal in eine algebraische Darstellung übersetzt. Um die Transformationen leisten zu können, wird die relationale Algebra um einige Operatoren erweitert, mit deren Hilfe sich der Term, der durch die Übersetzung entsteht, in eine entschachtelte Variante überführen lässt. Die Ansätze zur Entschachtelung korrelierter Unterabfragen mit Aggregationsfunktion werden in die Vorgehensweisen Nested-Iteration, erst Outer-Join, dann Aggregation, erst Aggregation, dann Outer-Join und in orthogonale Optimierung unterschieden. Die orthogonale Optimierung geht in folgenden Schritten vor: Zerlegung der Abfrage in einen Operatorbaum auf der Basis des \sql{apply}-Operators. \sql{Apply} ist ein relationaler Operator zweiter Ordnung, der die parametrierte Ausführung von Teilausdrücken abstrahiert. Im zweiten Schritt wird \sql{apply} in andere Operatoren umgeschrieben, wie z.B. \sql{outer join}. Die Vorgehensweise zur Entfernung der Korrelation beruht auf den gleichen Mechanismen wie in \cite{671634}. Anschließend wird, sofern möglich, der Outer-Join noch vereinfacht. So lässt sich Outer-Join in Gegenwart von \sql{null}-verwerfenden Prädikaten in Join umwandeln. Zusätzlich werden \sql{group-by}-Ausdrücke möglichst spät ausgewertet. Nachteil dieser Vorgehensweise ist die mögliche Einführung gemeinsamer Teilausdrücke (CSEs) bei der Entschachtelung.
Apply ist eine Ausprägung des Generalized-Projection Operators wie er z.B. in \cite{DBLP:books/mg/SilberschatzKS01} für die erweiterte Relationenalgebra vorgestellt wird. Der Generalized-Projection-Operator erlaubt nicht nur die Projektion auf Attribute der Ursprungsrelation, sondern auch auf Funktionsergebnisse, die über den Attributen dieser Relation formuliert werden. SegmentApply ist eine Variante des Apply-Operators, die nicht auf einzelne Zeilen sondern auf Gruppen von Zeilen angewandt wird. \sql{null}-rejecting Outer-Join: Ein Outer-Join heißt \sql{null}-verwerfend, wenn das Join-Prädikat \sql{null}-verwerfend ist und die Menge A der Attribute Teilmenge des Schemas der zweiten Relation. Ist ein Outer-Join-Prädikat \sql{null}-verwerfend, so ist es äquivalent zu einem Join-Prädikat mit der gleichen Join-Bedingung. Diese Äquivalenz ermöglicht, die Ausführungsreihenfolge zumindest für gewisse Outer-Joins und Joins zu vertauschen. \sql{null}-verwerfend heißt, dass das Prädikat \sql{null} auf den Wert \sql{false} abbildet.
In \cite{1066180} wird ein Algorithmus zur Optimierung geschachtelter Abfragen auf der Basis einer geschachtelten Relationenalgebra vorgestellt. Der vorgestellte Algorithmus ist jedoch nur für geschachtelte Abfragen ohne Aggregationsfunktion zulässig. Eine geschachtelte Relationenalgebra ist die konsequente Erweiterung der Relationenalgebra um die Zulässigkeit von Relationen als Attributwerte, d.h. eine Relation kann ihrerseits bereits geschachtelt sein. Die Grundoperationen der relationalen Algebra werden um zwei Operatoren erweitert. Die Operatoren nest und unnest überführen eine Menge von Relationen in eine geschachtelte Relation respektive entfernen die Schachtelung aus einer geschachtelten Relation. Prädikate, die in der geschachtelten Relationenalgebra Schachtelungsebenen verbinden, werden \emph{linking} (verbindende) Prädikate genannt. Es wird ein Operator \emph{linking selection} eingeführt, dieser erweitert die Selektionsoperation der Relationenalgebra, die ja nur auf flachen Relationen definiert ist. Die Selektion mit einem \emph{linking} Prädikat entspricht daher der \emph{linking selection}. Der Algorithmus zur Entschachtelung baut in einer depth-first Vorgehensweise eine flache Relation aus der geschachtelten Abfrage mit Hilfe von Join und Outer-Join auf. In einer optimierten Variante wird die Entschachtelung durch Pipelining, d.h. die Verzahnung der Rechenschritte der einzelnen Entschachtelungen noch einmal beschleunigt. Bei einer prototypischen Implementierung in einem kommerziellen DBMS\footnote{Database Management System = Datenbankverwaltungssystem} mit gespeicherten Prozeduren wurden zum Teil Beschleunigungen um mehrere Größenordnungen erreicht.
%\begin{itemize}
% \item G-Aggregation (Generalized-Aggregation)
% \item G-Join (Generalized-Join)
% \item G-Restriction (Generalized-Restriction)
% \item G-Outerjoin (Generalized-Outer-Join)
%\end{itemize}
\section{Klassifikation geschachtelter Abfragen}
SQL Prädikate lassen sich in verschiedene Klassen einteilen. Abhängig von der Semantik der Operation, kann man in \emph{einfache} Prädikate, \emph{Join}-Prädikate und \emph{geschachtelte} Prädikate unterscheiden.
\emph{Einfache} Prädikate sind solche Prädikate, die zu ihrer Berechnung nur auf Konstanten und Attribute einer Relation zugreifen. Ein Beispiel für ein solches Prädikat ist \textbf{$C_m = 10$}. Die entsprechende Operation der Relationenalgebra ist die Selektion.
\emph{Join}-Prädikate benötigen zu ihrer Berechnung Attribute aus zwei oder mehr Relationen. Sie \emph{verbinden} (to join -- engl. verbinden) die verwendeten Relationen. In der Relationenalgebra entspricht diese Operation der Kombination von Kreuzprodukt und Selektion.
\begin{lstlisting}
select * from §$R_i, R_j$§ where §$R_i.C_n=R_j.C_m$§
\end{lstlisting}
entspricht in der Relationenalgebra dem Ausdruck
\begin{math}
\sigma_{R_i.C_n=R_j.C_m}(R_i \times R_j)
\end{math}
\emph{Geschachtelte} Prädikate enthalten eine Unterabfrage in ihrem Ausdruck. Abhängig von der Ergebnismächtigkeit der Unterabfrage spricht der SQL-Standard von skalaren Unterabfragen, deren Ergebnis genau ein Wert ist; Zeilen-Unterabfragen (row subqueries), Ergebnis dieser Abfragen ist ein Tupel, das aus mehreren Attributen bestehen kann, sowie von Tabellen-Unterabfragen, deren Ergebnis eine Relation ist. Je nach Ergebnistyp ist die Verwendung von Unterabfragen an verschiedenen Stellen eines Abfrageblocks zulässig. Skalare Unterabfragen sind an jeder Stelle zulässig, an der auch Literale erlaubt sind. Zeilen- und Tabellen-Abfragen unterliegen einigen Einschränkungen, was ihre Verwendung in Views betrifft (siehe \cite{ISO:1992:IITa}), können aber an fast jeder Stelle eingesetzt werden, an der ihr Ergebnistyp zulässig ist. Der SQL-Standard erlaubt die Schachtelung von Abfrageblöcken in beliebiger Tiefe. Tabellen-Unterabfragen können z.B. in der \sql{from}-Klausel eingesetzt werden.
%Klassifikation von Prädikaten in
%einfache(Vergleich mit Konstante(n)),
%Nested,
%Join und
%Divisionsprädikat,\\
%Einschränkung bei Join-Prädikaten auf =-Operator, \\
%nur eine Spalte in der Select-Klausel erlaubt in Subquery, \\
%keine \sql{group by}\dots \sql{having}-Klausel in Subquery \cite{671658}, \\
%Innerer und und äußerer Abfrageblock, \\
%Klassifikation in
%N =(kein Join-Prädikat, dass auf Relationen im äußeren Abfrageblock verweist, keine Aggregationsfunktion in Select-Klausel, ergibt eine Liste von Konstanten),
%A =(kein Join-Prädikat, dass auf Relationen im äußeren Abfrageblock verweist, Aggregationsfunktion in Select-Klausel, kann vollkommen unabhängig vom äußeren Abfrageblock ausgewertet werden, Ergebnis ist immer eine Konstante,
%J =(hat Join-Prädikat das die/eine Relation aus dem äußeren Abfrageblock referenziert, keine Aggregationsfunktion in Select-Klausel),
%JA =(hat Join-Prädikat mit Verweis auf Relation im äußeren Abfrageblock, Aggregationsfunktion),
%D =(ein Divisions-Prädikat, dass in einer der beiden Abfrageblöcke ein Join-Prädikat mit Verweis auf eine Relation im äußeren Abfrageblock, drückt die relationale Divisionsoperation aus), \\
%\emph{nested-iteration method}, vollständige Auswertung des inneren Abfrageblocks für jedes Tupel des äußeren Blocks
Grundsätzlich lassen sich geschachtelte Abfragen in unabhängige Abfragen und korrelierte Abfragen unterscheiden. Unabhängige Abfragen lassen sich ohne den äußeren Abfrageblock auswerten. Ist eine unabhängige Auswertung nicht möglich, spricht man von korrelierten Abfragen, da das Ergebnis der inneren Abfrage vom Wert des Tupels des äußeren Abfrageblocks abhängt. Kim stellt in \cite{319745} eine Klassifikation geschachtelter Abfragen auf, auf deren Basis seine ebendort vorgestellten Entschachtelungsalgorithmen arbeiten.
\subsection{Typ A}
Eine geschachtelte Abfrage mit Aggregationsfunktion, die keine Attribute aus den äußeren Relationen referenziert, heißt vom Typ A. Solche Abfragen können unabhängig vom äußeren Abfrageblock ausgewertet werden. Ihr Ergebnis ist ein skalarer Wert, z.B. der Ort mit der höchsten Postleitzahl aus der Relation PLZ.
\begin{lstlisting}
select ort
from plz
where
plz = (select max(p:plz) from plz as p)
\end{lstlisting}
\subsection{Typ N}
Eine geschachtelte Abfrage ist vom Typ N, genau dann wenn die innere Abfrage keine Aggregationsfunktion enthält und alle Prädikate entweder simple Prädikate oder Join-Prädikate über Attributen der Relationen des inneren Abfrageblocks sind. Prädikate vom Typ N können unabhängig vom äußeren Abfrageblock ausgewertet werden; ihr Ergebnis ist eine Liste von Konstanten. Beispiel: Alle Städte mit einer Postleitzahl > 5000
\begin{lstlisting}
select sname
from staedte
where sname in (select ort from plz where plz > 5000)
\end{lstlisting}
\subsection{Typ J}
Eine Abfrage hat den Typ J, wenn mindestens ein Attribut der äußeren Relation im Prädikat verwendet wird, aber keine Aggregationsfunktion in der \sql{select}-Klausel vorkommt. Beispiel: Finde alle Städte, deren Bevölkerung größer als die Postleitzahl ist.
\begin{lstlisting}
select sname
from staedte
where sname in (select ort from plz where plz < bev)
\end{lstlisting}
\subsection{Typ JA}
Korrelierte Abfragen mit Aggregationsfunktion in der \sql{select}-Klausel heißen vom Typ JA. Das Ergebnis der Unterabfrage hängt vom Wert eines Attributs der äußeren Relationen ab. Beispiel: Alle Orte mit ihrer maximalen Postleitzahl. Der Wert des Maximums ist vom gerade betrachteten Ort abhängig.
\begin{lstlisting}
select ort
from plz
where plz = (select max(p:plz) from plz as p where ort = p:ort)
\end{lstlisting}
%
% EOF
%
%
Reference in New Issue View Git Blame Copy Permalink