%
% Kapitel Implementierung
%
%

\chapter{Implementierung}\label{chp:Implementierung}
Die Beschreibung der Umsetzung der in Kapitel \ref{chp:Entwurf} vorgestellten Überlegungen folgt in diesem Kapitel der Reihenfolge der im Optimierer durchlaufenen Schritte bei der Optimierung einer Abfrage. Nach einem kurzen Exkurs zur Umsetzung des Full-Outer-Join-Operators im \textsc{Secondo}-Kernels werden die einzelnen Optimierungsschritte bei einer geschachtelten Abfrage beschrieben und anhand einiger Beispiele erläutert. Im ersten Schritt werden Umschreibungsalgorithmen auf die Abfrage angewandt, die die Abfrage in eine inhaltlich äquivalente Struktur überführen. Die umgeschriebene Abfrage erlaubt dabei eine effizientere Optimierung, z.B. durch Verwendung von Indizes, die durch zusätzlich eingefügte abgeleitete Prädikate benutzt werden können. Hierzu gehört auch die Entschachtelung geschachtelter Abfragen. Im nächsten Schritt wird die Abfrage analysiert und alle Metadaten zu den in der Abfrage verwendeten Objekten ermittelt. Hierzu gehören die verwendeten Attribute und Relationen ebenso wie konstante Objekte. Die um diese Informationen angereicherte Abfrage wird im nächsten Schritt mit dem zentralen Optimierungsalgorithmus (siehe \ref{sct:Beschreibung SECONDO}) in einen ausführbaren Plan übersetzt. Anschließend wird der Plan in die Syntax des \textsc{Secondo}-Kernels übersetzt. Die Optimierung geschachtelter Prädikate erfolgt integriert in den beschriebenen Schritten. Für die Übersetzung der Unterabfragen sind die vom Optimierer ermittelten Konstrukte der äußeren Abfrage notwendig. Abhängig davon, ob der Optimierer das Prädikat als Join-Prädikat oder als Selektions-Prädikat übersetzt, sind unterschiedliche Übersetzungen notwendig. Eine Übersetzung während der Optimierungsphase ist im Moment nicht möglich, da grundlegende Datenstrukturen zu Beginn der Übersetzung eines Abfrageblocks initialisiert werden. Die Übersetzung zu diesem Zeitpunkt würde die bereits aufgebauten Datenstrukturen des äußeren Abfrageblocks zurücksetzen. Daher erfolgt die Übersetzung der Unterabfragen, die nicht durch Entschachtelung aufgelöst werden können, um einen Schritt verschoben, d.h. es findet eine Verzahnung der Übersetzungsschritte zwischen äußerer Abfrage und Unterabfrage statt.


Die in diesem Kapitel dargestellten Beispiele beziehen sich auf die Relationen \secondo{Staedte} (alle deutschen Städte mit den Attributen Kennzeichen, Vorwahl, Postleitzahl, Bevölkerung und Bezeichnung), \secondo{PLZ} (alle deutschen Postleitzahlen) und \secondo{Orte} (alle deutschen Gemeinden mit den Attributen Bevölkerung in Tausend Einwohner, Vorwahl und Kennzeichen) der Datenbank \secondo{opt}. Diese ist standardmäßig in \textsc{Secondo} enthalten. Die Relationen haben folgende Schemata:

\begin{algorithmic}
\STATE Staedte(Kennzeichen, Vorwahl, PLZ, Bev, SName) 
\STATE PLZ(Ort, PLZ)
\STATE Orte(Bevt, Vorwahl, Ort, Kennzeichen)
\end{algorithmic}.

Um auch inhaltlich die Vorgänge während der Optimierung darstellen zu können, werden zusätzlich die Relationen 

\begin{algorithmic}
\STATE Supplier(sno, sname, status, city)
\STATE Part(pno, pname, color, weight, city)
\STATE Shipment(sno, pno, qty, origin)
\end{algorithmic}

verwendet. \emph{Supplier} ist eine Tabelle von Lieferanten, \emph{Part} enthält Werkstücke und \emph{Shipment} Daten zu Lieferungen. Der Inhalt dieser Relationen wird vor der Verwendung in einem Beispiel jeweils angegeben.

\section{Full-Outer-Join}\label{sct:Full-Outer-Join}

\subsection{Sort-Merge-Outer-Join}
Grundlage für die Implementierung des Operators \secondo{smouterjoin} ist der Operator \\ % Fixes Layout
\secondo{sortmergejoin} der \algebra{ExtRelation-C++}-Algebra. Type-Mapping-Funktion und die Grundstruktur des Algorithmus konnten übernommen werden. Aus Gründen der Wartbarkeit wurde auf eine gemeinsame Implementierung der Value"=Map\-ping"=Funk\-tion mit Hilfe von C++"=Temp\-lates für \secondo{sortmergejoin} und \secondo{smouterjoin} verzichtet. Eine prototypische Implementierung führte zu unübersichtlichem Quellcode und Leistungseinbußen beim \secondo{sortmergejoin}. Daher wurde auf der Basis der \secondo{sortmergejoin}-Implementierung eine eigenständige Implementierung des Operators \secondo{smouterjoin} erstellt. 

\subsection{Symm-Outer-Join}


\section{Umschreiben quantifizierter Prädikate}
Prädikate mit den quantifizierenden Operatoren \sql{exists, not exists, any} und \sql{all} werden in äquivalente Prädikate mit Aggregationen überführt. Damit sind sie den in Kapitel \ref{chp:Entwurf} beschriebenen Algorithmen zur Entschachtelung zugänglich. \sql{exists} und \sql{not exists} werden in eine Prüfung transformiert, ob das Ergebnis mehr als 0 Tupel bzw. genau 0 Tupel enthält. 

Also 

\sql{exists(select $C_n$ from $R_m$ where P)} 

in 

\sql{0 < (select count(*) from $R_m$ where P)} 

und 

\sql{not exists(select $C_n$ from $R_m$ where P)} 

in 

\sql{0 = (select count(*) from $R_m$ where P)}. 

Prädikate mit \sql{all} und \sql{any} werden in die im vorigen Kapitel beschriebenen Prädikate vom Typ JA transformiert. Dieser Schritt erfolgt bei jedem geschachtelten Prädikat, unabhängig davon, ob eine weitere Entschachtelung möglich ist. Eine direkte Übersetzung der quantifizierenden Operatoren in die ausführbare Syntax des \textsc{Secondo}-Kernels wurde nicht implementiert. Die Verwendung des Operators \sql{count(*)} ist notwendig, um die richtige Behandlung nicht definierter Tupelwerte (\sql{null}-Werte) zu gewährleisten. Diese Umwandlung erfolgt durch das Prädikat preTransform/2. 

\section{Entschachtelung}
Nach der Vorabtransformation quantifizierter Prädikate wird durch die Anwendung des in \ref{chp:Entwurf} beschriebenen Algorithmus NEST-G versucht, die Abfrage in ihre kanonische Form, d.h. eine Form ohne geschachtelte Prädikate, zu überführen. Die Entschachtelung einer Abfrage erfolgt in mehreren Schritten. In jedem Schritt wird ein Entschachtelungsalgorithmus auf einen Teilausdruck der Abfrage angewandt. Bei Unterabfragen in der \sql{select}- und der \sql{from}-Klausel werden im Moment nur nicht-korrelierte Unterabfragen unterstützt. Die Reihenfolge der auf eine Abfrage angewandten Entschachtelungsalgorithmen ist: 
\begin{enumerate}
\item Entschachtelung von nicht korrelierten Unterabfragen in der \sql{select}-Klausel 
\item Entschachtelung von nicht korrelierten Unterabfragen in der \sql{from}-Klausel 
\item Entschachtelung von Unterabfragen in der \sql{where}-Klausel. 
\end{enumerate}.

Die Entschachtelung von Unterabfragen in der \sql{where}-Klausel erfolgt rekursiv mit dem allgemeinen Entschachtelungsalgorithmus nach Kim/Ganski/Wong \cite{319745,38723}. Dabei werden die oben beschriebenen Schachtelungstypen unterschieden. Je nach Schachtelungstyp wird der entsprechende Entschachtelungsalgorithmus angewendet. \enquote{Temporäre Relationen} werden für die Entschachtelung korrelierter Abfragen mit Aggregationsfunktion benötigt. Um die Geschwindigkeit bei wiederholtem Ausführen der Abfragen zu beschleunigen, werden die zum Entschachteln eines Prädikats notwendigen temporären Relationen zur Laufzeit in einem Prolog-Fakt gespeichert. Bei einer Datenbank werden alle eventuell noch vorhandenen temporären Relationen gelöscht, um in jeder neuen Sitzung eine saubere Datenbankumgebung bereitzustellen. Die Implementierung des allgemeinen Entschachtelungsalgorithmus nach Kim/Ganski/Wong wurde mit dem Prädikat \prolog{transformNestedPredicates/6} realisiert. Da SQL beliebig tief geschachtelte Abfragen zulässt, wird der Algorithmus rekursiv auf die Unterabfragen und das Ergebnis der Entschachtelung angewandt, bis das Ergebnis durch die implementierten Algorithmen nicht weiter entschachtelt werden kann. Unterabfragen, die in dieser Phase nicht aufgelöst werden können, werden als geschachtelte Ausdrücke übersetzt.

\subsection{Unterabfragen in der \sql{select}- und \sql{from}-Klausel}\label{ssct:from-Klausel}
Unterabfragen in der \sql{select}-Klausel werden ausgewertet und in der Abfrage durch ihr Ergebnis ersetzt. Da an dieser Stelle nur skalare Unterabfragen zulässig sind, schlägt die Übersetzung fehl, falls das Ergebnis der Unterabfrage keine skalare Konstante ist. Jede Unterabfrage in der \sql{select}-Klausel wird mit dem Prädikat \prolog{transformNestedAttribute/4} in einen Attributausdruck umgewandelt. Hierbei wird überprüft, ob die Abfrage keine korrelierten Prädikate enthält. Ist die Abfrage nicht frei von korrelierten Prädikaten, so kann keine Transformation der Unterabfrage vorgenommen werden.

Eine in der \sql{from}-Klausel definierte Unterabfrage wird in eine temporäre Relation übersetzt, d.h. das Ergebnis der Unterabfrage wird für die Auswertung materialisiert. In der Umschreibungsphase wird die Abfrage dann auf Basis dieser temporären Relation formuliert. Auch hier wird die Unterabfrage auf korrelierte Prädikate untersucht, da eine Übersetzung in eine temporäre Relation dann nicht möglich ist. Diese Übersetzung erfolgt mit dem Prädikat \prolog{transformNestedRelations/4}.

\subsection{Geschachtelte Prädikate}
Über die Erkennung des Schachtelungstyps wird der Algorithmus ausgewählt, der auf das Prädikat angewandt wird. Hierfür wird das SQL-Prädikat in Teilausdrücke zerlegt. Es wird dabei unterschieden zwischen geschachtelten Ausdrücken mit unärem Operator wie z.B. \sql{exists} und binären Operatoren. Binäre Operatoren sind z.B. die skalaren Vergleichsoperatoren, aber auch der Mengenoperator \sql{in}. Die Unterabfrage wird auf Aggregationsfunktionen untersucht; sind keine vorhanden, so kann der Typ der Abfrage nur noch J oder N sein. Im zweiten Schritt wird ein Schema-Lookup für die Unterabfrage durchgeführt. Dieser ist nur bei nicht-korrelierten Abfragen erfolgreich. Aus der Kombination dieser beiden Ergebnisse kann der Typ der Unterabfrage und damit des geschachtelten Prädikats ermittelt werden.

\begin{table}[h]
\centering
\begin{tabular}{@{}lcc@{}} \toprule
& nicht-korreliert & korreliert\\ \midrule
ohne Aggregationsfunktion & N & J \\
mit Aggregationsfunktion & A & JA \\
\bottomrule\end{tabular} 
	\caption{Typ Ermittlung}
  \label{tab_Type}
\end{table}

Die Transformation geschachtelter Prädikate wird über eine Depth-First-Suche rekursiv durchgeführt, d.h. es wird bei den Blättern des Abfragegraphen mit der Optimierung begonnen. Da die Entschachtelungsalgorithmen eine Abfrage der Schachtelungstiefe n in eine Abfrage der Schachtelungstiefe n-1 überführen, entspricht dies genau der Vorgehensweise in \cite{38723}. Geschachtelte Prädikate, die nicht den Klassen A,J,N oder JA entsprechen, werden wie \enquote{einfache} Prädikate behandelt. Ihre Übersetzung erfolgt über die triviale geschachtelte Ausführung und wird erst bei der Übersetzung des Plans in ausführbare Syntax vorgenommen. 

Für Typ-A Abfragen wird die Abfrage ausgewertet und das Ergebnis der Abfrage an ihrer Stelle eingefügt. Hierbei kann es bei Gleitkommazahlen zu numerischen Fehlern kommen, da die Werte zwischen dem Optimierer und \textsc{Secondo} nur mit einer begrenzten Genauigkeit ausgetauscht werden. Die Genauigkeit, mit der \textsc{Secondo} Gleitkommazahlen behandelt, lässt sich beim Kompilieren festlegen.

So wird für die Abfrage 
 
\begin{lstlisting}
select ort 
from plz
where
	plz = (select max(p:plz) from plz as p)
\end{lstlisting}

im ersten Schritt die Unterabfrage \lstinline{select max(p:plz) from plz as p} ausgewertet. Das Ergebnis (99998) wird nun anstelle der Unterabfrage in die ursprüngliche Abfrage übernommen. Diese wird in ihrer entschachtelten Form zu 

\begin{lstlisting}
select ort from plz where [plz = 99998]
\end{lstlisting}.

Das Ergebnis ist eine Abfrage ohne geschachteltes Prädikat, die mit den Standardverfahren des Optimierers übersetzt werden kann. 

Die Umsetzung von Algorithmus NEST-N-J (siehe Abschnitt \ref{sct:Algorithmus NEST-N-J}) ist trivial. Die Anwendung erfolgt auf Prädikate, die als Typ J oder N erkannt werden, d.h. sie haben keine Aggregationsfunktion in der Unterabfrage. Da die Relationen der \sql{from}-Klausel bereits als Liste vorliegen, müssen nur die Listen der Unterabfrage und der äußeren Abfrage vereinigt werden. Ist der verwendete Operator \sql{in}, so muss eine temporäre Relation erzeugt werden, die die Projektion der inneren Relation auf die Join-Spalten ist. Hierdurch werden unerwünschte Duplikate entfernt und die Mengensemantik des Operators \sql{in} wird auch für das Join-Prädikat erhalten. Auch die Prädikate liegen als Liste von Konjunktionstermen vor und können über das Prädikat \prolog{append} zu einer Liste zusammengeführt werden. Im letzten Schritt des Algorithmus wird das zusätzliche Join-Prädikat erzeugt. Der Operator des neuen Prädikats ist \enquote{=}, falls das geschachtelte Prädikat den Operator \sql{in} beinhaltete, andernfalls wird der ursprüngliche Operator beibehalten. Die Entschachtelung von Abfragen vom Typ N oder J mit dem \sql{not in}-Operator erfolgt hier nicht. Eine Erweiterung des Algorithmus nach der Implementierung eines Anti-Join Operators ist aber ohne weiteres möglich. 

Die Typ-N Abfrage 

\begin{lstlisting}
select sname 
from staedte
where sname in (select ort from plz where plz > 5000)
\end{lstlisting}

wird transformiert in 

\begin{lstlisting}
select sname 
from [staedte, plz] 
where [sname = ort, plz > 5000]
\end{lstlisting}.

Die Bedingungen aus dem geschachtelten Prädikat und dem Prädikat der Unterabfrage werden in Form der zwei Prädikate \lstinline{sname = ort} und \lstinline{plz > 5000} in die entschachtelte Variante übernommen.

Eine Typ-J Abfrage unterscheidet sich von einer Typ-N nur durch ein korreliertes Prädikat. In der entschachtelten Abfrage wird das korrelierte Prädikat der Unterabfrage zu einem Join-Prädikat der entschachtelten Abfrage, wie man an der Transformation von 

\begin{lstlisting}
select sname
from staedte
where sname in (select ort from plz where plz < bev)
\end{lstlisting}

zu

\begin{lstlisting}
select sname 
from [staedte, plz] 
where [sname = ort, plz < bev]
\end{lstlisting}

sehen kann. Hier wird das Prädikat \lstinline{plz < bev}, das sich in der ursprünglichen Abfrage auf Relation \lstinline{staedte} des äußeren und Relation \lstinline{plz} des inneren Abfrageblocks bezieht, zu einem Join-Prädikat der entschachtelten Abfrage.

Die komplexeste Behandlung erfordert Algorithmus NEST-JA2 (siehe Abschnitt \ref{sct:Algorithmus NEST-JA2}). Im ersten Schritt werden die Prädikate der Unterabfrage in einfache Prädikate, Join-Prädikate der inneren Abfrage und korrelierte Prädikate partitioniert. Danach werden die drei oben beschriebenen temporären Relationen erzeugt. Für die Projektion der äußeren Relationen auf die Join-Attribute müssen diese aus den korrelierten Prädikaten der Unterabfrage ermittelt werden. Hierzu werden die in den korrelierten Prädikaten verwendeten Attribute gegen die Metadaten der Relationen der Unterabfrage geprüft. Die Attribute, die nicht in den Relationen definiert sind, sind Attribute des äußeren Abfrageblocks. Die Restriktion der inneren Relationen erfolgt nur, falls die Unterabfrage einfache Prädikate enthält. Andernfalls werden die Relationen der Unterabfrage direkt weiterverwendet. Die Aggregation über den beiden temporären Relationen wird abhängig von der Aggregationsfunktion mit einem Outer-Join bzw. mit einem einfachen Join berechnet. Tritt bei der Erstellung einer dieser Relationen ein Fehler auf wird die Verarbeitung mit einer Exception abgebrochen. Aus der dritten temporären Relation und der ursprünglichen Abfrage wird im nächsten Schritt die entschachtelte Variante aufgebaut. Die Syntax für die Umbenennung von Relationen und Attributen im Optimierer deckt sich nicht mit der entsprechenden Syntax im \textsc{Secondo}-Kernel. Daher muss bei der Erstellung der entschachtelten Variante eine Umsetzung dieser Syntax erfolgen, um korrekt auf die Attribute der dritten temporären Relation zugreifen zu können. Die Syntax im Optimierer ist Name:Attribut, während im \textsc{Secondo}-Kernel Attribut\_Name verwendet wird. Jede Verwendung von Name:Attribut muss nun in Attribut\_Name geändert werden, sofern sie sich auf ein Attribut der dritten temporären Relation bezieht. Um sicherzustellen, dass es keine Namenskonflikte durch die neu erstellte Relation gibt, wird diese mit einer Umbenennung in die entschachtelte Abfrage aufgenommen. Dafür müssen alle Attributausdrücke, die Attribute der temporären Relation verwenden, an die Umbenennung angepasst werden.

Mit den Inhalten (siehe Tabellen \ref{tab_Supplier} und \ref{tab_Parts})

\begin{table}[th]
\centering
\begin{tabular}{@{}rrc@{}} 
\multicolumn{3}{c}{Supplier} \\ 
\toprule
pnum & quan & shipdate\\ \midrule
3 & 4 & 03.07.79 \\
3 & 2 & 01.10.78 \\
10 & 1 & 08.06.78 \\
10 & 2 & 10.08.81 \\
8 & 5 & 07.05.83 \\
\bottomrule\end{tabular} 
	\caption{Relation Supplier}
  \label{tab_Supplier}
\end{table}

\begin{table}[th]{
\centering
\begin{tabular}{@{}rr@{}}
\multicolumn{2}{c}{Parts} \\ 
 \toprule
pnum & qoh \\ \midrule
3 & 6 \\
10 & 1 \\
8 & 0 \\
\bottomrule\end{tabular}}
	\caption{Relation Parts}
  \label{tab_Parts}
\end{table}

ergibt die Abfrage 

\begin{lstlisting}
select pnum
from p:parts as p
where p:qoh = (select count(shipdate) 
				     from supply
				     where pnum = p:pnum and
				           shipdate < 01.01.80)
\end{lstlisting}

folgende Transformationen:

\begin{lstlisting}
trelxx1 = select distinct[p:pnum] from parts as p
\end{lstlisting}

Die erste temporäre Relation hat damit den Inhalt (Tabelle \ref{tab_trelxx1}).

\begin{table}[ht]
%\centering
\begin{tabular}{@{}r@{}}
\multicolumn{1}{c}{trelxx1} \\ 
 \toprule
pnum\_p \\ \midrule
3 \\
10 \\
8 \\
\bottomrule\end{tabular} 
	\caption{Relation trelxx1}
  \label{tab_trelxx1}
\end{table}.

Die Einschränkung und Projektion der inneren Relation \sql{supply} hat die Form

\begin{lstlisting}
trelxx2 = select [pnum, shipdate] from supply where shipdate < 01.01.80
\end{lstlisting}.

Dabei ergeben sich folgende Inhalte:
\begin{table}[ht]
%\centering
\begin{tabular}{@{}rc@{}} 
\multicolumn{2}{c}{trelxx2} \\ 
\toprule
pnum & shipdate\\ \midrule
3 & 03.07.79 \\
3 & 01.10.78 \\
10 & 08.06.78 \\
\bottomrule\end{tabular} 
	\caption{Relation trelxx2}
  \label{tab_trelxx2}
\end{table}

Da die Aggregationsfunktion \sql{count} ist, wird für die Aggregation der Outer-Join benutzt.
\begin{lstlisting}
trelxx3 = trelxx1 feed 
					trelxx2 feed
					smouterjoin[pnum\_p, pnum]
					groupby[var1: group feed count(shipdate)]
					project[pnum_p, var1]
					consume					
\end{lstlisting}

\begin{table}[ht]
%\centering
\begin{tabular}{@{}rc@{}} 
\multicolumn{2}{c}{trelxx3} \\ 
\toprule
pnum\_p & var1\\ \midrule
3 & 2 \\
10 & 1 \\
8 & 0 \\
\bottomrule\end{tabular} 
	\caption{Relation trelxx3}
  \label{tab_trelxx3}
\end{table}

Mit den Ergebnissen Tabelle \ref{tab_trelxx1}, Tabelle \ref{tab_trelxx2} und Tabelle \ref{tab_trelxx3}.

Die entschachtelte Abfrage lautet dann

\begin{lstlisting}
select p:pnum
from [parts as p, trelxx3 as alias1]
where [p:qoh = alias1:var1, 
		   p:pnum = alias1:pnum_p]
\end{lstlisting}

Wie sich leicht überprüfen lässt ist das Ergebnis (Tabelle \ref{tab_Q2}) übereinstimmend mit dem Ergebnis der geschachtelten Iteration. (Siehe auch die Ausführungen in \cite{38723})

\begin{table}[th]
%\centering
\begin{tabular}{@{}r@{}} 
\toprule
pnum\_p \\ \midrule
10 \\
8 \\
\bottomrule\end{tabular} 
	\caption{Ergebnis Abfrage Q2 von Kiessling}
  \label{tab_Q2}
\end{table}

Dabei wird

\begin{lstlisting}
select ort 
from plz
where plz = (select max(p:plz) from plz as p where ort = p:ort)
\end{lstlisting}

in die inhaltliche äquivalente Abfrage 

\begin{lstlisting}
select ort 
from [plz, trelxx3 as alias1] 
where [ort = alias1:ort_p, plz = alias1:var1]
\end{lstlisting}

umgeschrieben und die temporären Relationen trelxx1 und trelxx3 werden erzeugt. 

\begin{lstlisting}
trelxx1 = select distinct[ort] from orte
\end{lstlisting}

\begin{lstlisting}
trelxx3 = select [ort_p, max(plz_p) as var1] 
					 from [trelxx1, plz as p] 
					 where [ort = p:ort] 
					 groupby p:ort
\end{lstlisting}

Da die Unterabfrage keine einfachen Prädikate beinhaltet, wird in der Berechnung der Aggregation mit der Relation der Unterabfrage gearbeitet.

\section{Schema-Lookup}
Zum Zeitpunkt der Metadaten-Ermittlung sind nur noch geschachtelte Prädikate enthalten, die nicht durch die Entschachtelungsalgorithmen in ihre kanonische Form überführt werden können. Um auch für diese Prädikate eine Übersetzung in die ausführbare Syntax von \textsc{Secondo} zu gewährleisten, müssen alle für die Optimierung benötigten Metadaten zu den verwendeten Attributen und Relationen ermittelt werden.
Die Metadaten zu Prädikaten werden im Optimierer in einem Fakt \secondo{pr(P, R)} für einfache (Selektions)-Prädikate und \secondo{pr(P, R1, R2)} bei Join-Prädikaten für die weitere Verarbeitung ermittelt (siehe auch \cite{DBLP:conf/ideas/DiekerG00}). P bezeichnet hier einen Prä\-di\-kat\-aus\-druck, d.h. einem booleschen Ausdruck über Attributen von bis zu zwei Relationen. R bzw. R1 und R2 sind die Relationen, deren Attribute im Prädikat verwendet werden. Attribute, die im Prädikatausdruck verwendet werden, werden in einem Fakt \secondo{attr(Attributname, No, Case)} gespeichert. Hierbei bezieht sich \prolog{No} bei Join-Prädikaten auf die Reihenfolge der Relation aus der das Attribut stammt. Ist das Attribut in der ersten aufgeführten Relation enthalten, so hat No den Wert 1, andernfalls den Wert 2. Bei Selektionsprädikaten ist dieser Wert immer 0, da die Relation des Attributs eindeutig ist. Bei geschachtelten Prädikaten ist die erste Relation immer die Relation des Attributausdrucks auf der linken Seite des Vergleichsoperators. Steht links vom Vergleichsoperator eine Konstante, so bezieht sich die erste Relation auf die erste in der Unterabfrage verwandte Relation. Um die Stellung der Relationen des geschachtelten Prädikats auch bei der Übersetzung der Unterabfrage zur Verfügung zu haben, wird jede korrelierte Unterabfrage als Fakt subquery(Abfrage, Relation) bzw. subquery(Abfrage, erste Relation, zweite Relation) gespeichert. Hierdurch kann bei der Übersetzung in einen Plan auf die Reihenfolge der verwendeten äußeren Relationen zugegriffen werden, was unter anderem bei der Umbenennung der Relationen zur Verwendung in einem \secondo{filter}-Ausdruck notwendig ist.

Um die weitere Verarbeitung geschachtelter Abfragen zu ermöglichen, müssen in der Phase des Schema-Lookups auch die Metadaten der Objekte der Unterabfragen nachgeschlagen werden. Hierzu werden die Daten zu den Selektionsattributen der Unterabfrage entsprechend den Attributen des äußeren Abfrageblocks ermittelt. Beim Nachschlagen der Relationen wird auf die Eindeutigkeit der Attributnamen über alle Abfrageblöcke hinweg geachtet. D.h. enthält eine Relation ein Attribut \emph{A}, so darf keine weitere Relation ohne Umbenennung in der Abfrage verwendet werden, die ein Attribut namens \emph{A} enthält. Wird dies vom Benutzer nicht beachtet, so wird er durch eine Fehlermeldung darauf hingewiesen. Dies bedeutet bei der Verwendung ein und derselben Relation im äußeren und inneren Abfrageblock, dass eine der beiden Relationen umbenannt werden muss. Auch die Metadaten der in einem Prädikat verwendeten Relationen werden für die Unterabfrage bestimmt. Da die für die Optimierung notwendigen Datenstrukturen, wie z.B. die Kanten des pog, zu Beginn der Optimierung einer Abfrage zurückgesetzt werden, müssen bereits an dieser Stelle die notwendigen Abfragen auf den Stichproben-Relationen für die Prädikate der Unterabfrage erfolgen. Die Ermittlung der Selektivitäten erfolgt also ebenso wie die Entschachtelung Bottom-Up. Ein geschachteltes Prädikat, das zwei Relationen der äußeren Abfrage referenziert, wird bei der Ermittlung der Selektivität wie ein einfaches Join-Prädikat behandelt. Die Abfrage über den Stichprobenrelationen für ein Join-Prädikat wird immer mit einem \secondo{loopjoin} ausgeführt. Daher wird auch hier, wie unten beschrieben, das geschachtelte Prädikat mit Hilfe einer Mapping Funktion übersetzt. Die Relationen der Unterabfrage werden auf entsprechenden Stichprobenrelationen geändert. Die Größe des Ergebnisses der Stichprobenabfrage wird auf insgesamt maximal 250.000 Tupel eingeschränkt. Hierzu wird die Anzahl der in der Stichprobenabfrage verwendeten Relationen gezählt. Bei n Relationen werden nur auf die ersten $\sqrt[n]{250.000}$ Tupel jeder Stichprobenrelation zugegriffen. Die maximal in einer Selektivitätsabfrage verwendete Anzahl von Tupeln pro Relation und insgesamt sind als Prolog-Fakten \prolog{maxSampleCard} und \prolog{maxSelCard} hinterlegt. Diese können vom Benutzer zur Laufzeit mit den Prädikaten \prolog{setMaxSampleCard/1} und \prolog{setMaxSelCard/1} angepasst werden.

Die Ermittlung der Selektivität erfolgt für Join-Prädikate mit einem Nested-Loop-Join. Um die Eindeutigkeit der Attributnamen sicherzustellen, wird automatisch eine Umbenennung der inneren Relation des Nested-Loop-Join vorgenommen. Alle Verweise im geschachtelten Prädikat müssen ebenfalls entsprechend umbenannt werden. Die Umbenennung bei nicht geschachtelten Prädikaten erfolgt über die Angabe der Position der umbenannten Relation innerhalb des Prädikats. Durch Zerlegung und rekursive Anwendung des Umbenennungsprädikats erfolgt diese Umbenennung auf beliebigen Ausdrücken. Da die im Fakt \secondo{attr(Attributname, No, Case)} angegebene Position bei Attributen in korrelierten Prädikaten nicht zwingend deckungsgleich ist mit der Position der Relation im geschachtelten Prädikat, wird diese Zuordnung über alle Anwendungen des Umbenennungsprädikats in einem Kellerspeicher festgehalten. Über diesen Kellerspeicher kann dann auf den Namen eines Stroms zugegriffen werden, um die Umbenennung eines Prädikats der geschachtelten Abfrage durchzuführen.

\begin{lstlisting}[caption=Abfrage mit Metadaten]
select attr(ort, 0, u) 
from [rel(plz, *)] 
where 
	[pr(attr(pLZ, 1, u)= subquery(select max(attr(p:pLZ, 0, u))from rel(plz, p), [rel(plz, *)]), rel(plz, *))]
\end{lstlisting}

%\begin{itemize}
%	\item Selektionsattribute der Subquery
%	\item Innere Tabellen
%	\item Prädikate
%	\subitem nach dem Lookup eines Prädikats immer die Selektivität ermitteln, um die globalen Datenstrukturen (pog etc.) nicht während der Plan-Ermittlung durch Subqueries zerstören
%\end{itemize}

\section{Ermittlung des Ausführungsplans}
\subsection{\sql{from}-Klausel}
Geschachtelte Abfragen mit einer Unterabfrage in der \sql{from}-Klausel werden folgendermaßen transformiert. Die Unterabfrage wird in einen Ausführungsplan übersetzt. Die Projektion und Selektion des äußeren Abfrageblocks werden dann auf diesen Plan angewandt. Dabei wird die Übersetzung der Selektion und Projektion mit dem bereits im Optimierer implementierten Prädikat \prolog{finish2/6} vorgenommen.

\subsection{Ausführungsplan für geschachtelte Prädikate}
Der Ausführungsplan für eine geschachtelte Abfrage wird in folgenden Schritten ermittelt. Handelt es sich um eine Abfrage vom Typ N/J oder vom Typ A so kann die Ermittlung direkt über den Optimierer erfolgen, da die Abfrage keine korrelierten Prädikate enthält. Hierzu wird das Optimierungprädikat \prolog{optimize/3} aufgerufen. Das Ergebnis ist ein Ausführungsplan, der aber immer noch einen Prolog-Term darstellt. Für die Planermittlung bei korrelierten Unterabfragen muss die Abfrage erst einmal von den korrelierten Prädikaten befreit werden. Die nicht-korrelierte Abfrage kann dann wieder vom Optimierer bearbeitet werden. Der daraus resultierende Plan wird nun um die korrelierten Prädikate erweitert. Hierbei werden diese in Form von \secondo{filter}-Ausdrücken an den Plan angefügt. Der \textsc{Secondo}-Operator \secondo{filter} erwartet als Argumente einen Tupelstrom (gegeben durch den Teilplan) und ein Prädikat, das auf eben diesem Strom angewandt wird. Dabei werden Prädikate mit niedrigen Kosten zuerst angewandt, um die Anzahl der zu verarbeitenden Ergebnistupel und den Laufzeitaufwand zu minimieren. Da der Optimierer nach dem gleichen Prinzip arbeitet, sollte diese Vorgehensweise eine positive Auswirkung auf die Laufzeit geschachtelter Abfragen gegenüber der wahlfreien Ausführung dieser Selektionen haben. Die Implementierung in Prolog, die die Prädikate in der entsprechenden Reihenfolge ermittelt, erlaubt auch die Erweiterung um die Einbeziehung der Ausführungskosten der Prädikate, um eine bessere Abschätzung der minimalen Laufzeit zu erhalten. Grundsätzlich wäre auch eine Erweiterung des Optimierungsalgorithmus denkbar, bei der die korrelierten Prädikate mit in die Optimierung einbezogen werden. Damit wäre es möglich, eine optimale Reihenfolge für die Ausführung der Prädikate zu ermitteln. Die Übersetzung geschachtelter Abfragen erfolgt Top-Down, damit zum Übersetzungszeitpunkt die Entscheidungen des Optimierers bekannt sind, mit welchen Konstrukten das geschachtelte Prädikat übersetzt wird. Dies ist notwendig, um das Prädikat in einen passenden Ausdruck zu übersetzen und die Mapping-Funktionen richtig zu gestalten.

Die oben angegebene Abfrage wird in diesem Schritt in den Term

\begin{lstlisting}
consume(
	project(
		predinfo(
			0.0004995, 
			0.046, 
			filter(
				feedproject(
					rel(plz, *), 
					[attrname(attr(ort, 0, u)), 
					attrname(attr(pLZ, 0, u))]
				), 
				attr(pLZ, 1, u) 
				= 
				subquery(
					select max(attr(p:pLZ, 0, u))	from rel(plz, p), 
				  [rel(plz, *)]
				)
			)
		), 
		[attrname(attr(ort, 0, u))]
	)
)
\end{lstlisting}

übersetzt. Hierbei ist die Abfrage bereits in einen Plan übersetzt. Nur der Term Q in \lstinline{subquery(Q)} ist noch in SQL-Syntax und wird erst bei der Übersetzung in die ausführbare Syntax umgewandelt. Eine Übersetzung der Unterabfrage in dieser Phase kann wie oben beschrieben noch nicht erfolgen.

%\begin{itemize}
%	\item korrelierte Prädikate der Subquery entfernen. Hierzu werden die Prädikate untersucht, ob sie Attribute aus Relationen des äußeren Abfrageblocks verwenden.
%	\item Plan für Subquery ohne korrelierte Prädikate ermitteln. Unterabfragen ohne korrelierten Prädikate werden durch die Standardmechanismen des \textsc{Secondo}-Op\-ti\-mie\-rers übersetzt, um einen möglichst effizienten Ausführungsplan zu ermitteln. 
%	\item korrelierte Prädikate mit aufsteigender Selektivität an Plan \enquote{anflanschen}. 
%\end{itemize}

\section{Übersetzung des Plans in ausführbare Syntax}
Bis zu diesem Schritt ist bereits die äußerste Abfrage in einen Ausführungsplan übersetzt. Geschachtelte Prädikate werden in diesem Schritt übersetzt und durchlaufen dabei rekursiv die Phasen \enquote{Planermittlung} und \enquote{Übersetzung in ausführbare Syntax}. Da die Übersetzung geschachtelter Prädikate abhängig ist von den vom Optimierer gewählten Konstrukten zur äußeren Abfrage, kann die Übersetzung erst zu diesem Zeitpunkt erfolgen.

\subsection{IN Operator}
Der Operator \sql{in} erlaubt die Überprüfung auf Enthaltensein in einer Menge (siehe \ref{sct:Überblick}). Die Semantik des Operators erlaubt die Verwendung in einem Ausdruck mit einer Menge. Die Menge kann durch Auflistung von Konstanten angegeben werden, oder durch eine Unterabfrage spezifiziert werden. Mit der \algebra{Collection}-Algebra besitzt \textsc{Secondo} eine Algebra, die die entsprechenden Operationen auf Mengen zur Verfügung stellt. Mengen, die als Liste von Konstanten spezifiziert sind, werden in der Übersetzungsphase in ein entsprechendes \textsc{Secondo}-Objekt übersetzt. 


\begin{lstlisting}
(1,2,3,4)
\end{lstlisting}

wird in 

\secondo{[const set(int) value(1 2 3 4)]}

übersetzt. Der \sql{in}-Operator wird mit dem \textsc{Secondo} Operator \secondo{in} der \algebra{Collection}-Algebra übersetzt. Bei Mengen die durch Auflistung definiert werden ist keine zusätzliche Operation erforderlich. Mengen, deren Definition als Ergebnis von Unterabfragen erfolgt werden unter Zuhilfenahme der Operatoren \secondo{collect\_set} und \secondo{projecttransformstream} übersetzt. Da der \secondo{in}-Operator nur auf einer Menge definiert ist, muss der Tupelstrom in eine Menge überführt werden. Der Operator \secondo{projecttransformstream} hat die Signatur 

\secondo{$stream(tuple((a_1 t_1)\cdots(a_n t_n)))\times a_n$ $\rightarrow$ $(stream\; t_n)$} 

und wandelt einen Tupel-Strom in einen Strom von Werten um. Hierbei wird das Se\-lek\-tions\-at\-tri\-but der geschachtelten Abfrage als zu wählender Parameter mitgegeben. Der Strom wird dann mit dem Operator \secondo{collect\_set} in eine Menge umgewandelt und für jedes Tupel des äußeren Stroms wird mit \secondo{in} geprüft, ob der entsprechende Attributwert enthalten ist. D.h. es wird genau die mengenbasierte Semantik des \sql{in}-Operators erreicht.

Ein Prädikat 

\begin{lstlisting}
§$A_i$§ in (select §$A_j$§ from §$R_n$§)
\end{lstlisting}

wird in den \textsc{Secondo}-Ausdruck 

\secondo{filter[.$A_i$ in $R_n$ feed projecttransformstream[$A_j$] collect\_set]} 

übersetzt. 

\subsection{Allgemeine Prädikate mit Vergleichsoperatoren}
Der Optimierer unterstützt im Moment Prädikate, die als Ausdrücke über Attributen von bis zu zwei Relationen aufgebaut sind. Da diese Beschränkung nur durch Erweiterungen am zentralen Optimierungs-Algorithmus aufgehoben werden kann, gilt diese auch für Prädikate mit geschachtelten Abfragen, d.h. in einer Unterabfrage können maximal Attribute aus zwei äußeren Relationen verwendet werden. Da durch die Entschachtelung neue, temporäre Tabellen eingeführt werden können, kann es zu der Situation kommen, dass ein Prädikat in seiner geschachtelten Form ein Ausdruck über den Attributen zweier Relationen ist, aber bei der Entschachtelung zu einem Ausdruck über drei oder mehr Relationen wird. Um in diesem Fall eine Ausführung zu ermöglichen, wird die entsprechende Fehlermeldung abgefangen. Die Abfrage wird dann in der nicht entschachtelten Variante optimiert bzw. ausgeführt. Da die Fehlermeldung erst nach der Entschachtelung beim Schema-Lookup auftritt, wird der Schema-Lookup bereits einmal nach der Entschachtelung ausgeführt.

Die hier behandelten Ausdrücke haben die Form 

\begin{lstlisting}
attr(Attributname, No, Case) §$\theta$§ subquery(Query, Relation [, Relation2])
\end{lstlisting}.

Je nach Anzahl der verwendeten äußeren Relationen wird die geschachtelte Abfrage übersetzt mit einer allgemeinen Mapping-Funktion, die eine entsprechende Anzahl Parameter besitzt. Die innere Abfrage wird wie eine einfache Abfrage in einen \enquote{ungeschachtelten} \textsc{Secondo}-Ausdruck übersetzt. Auf die Attribute der äußeren Relation kann dann über die Parameter der Mapping-Funktion zugegriffen werden. Für den Zugriff auf die Paramter der Mapping-Funktion müssen noch zusätzliche Operatoren eingefügt werden. Diese benötigen die Parameternamen, um den Zugriff zu ermöglichen.

Der \secondo{filter} Operator erwartet neben einem Tupelstrom eine Mapping-Funktion, die vom Datentyp \secondo{tuple} nach \secondo{bool} abbildet. Eine Mapping-Funktion ist eine mit dem Operator \secondo{map} definierbare Funktionsvorschrift.  Handelt es sich bei dem zu übersetzenden Prädikat um ein geschachteltes Prädikat mit einem skalaren Vergleichsoperator, so hat die Funktion die Form $A_i~\theta$~\secondo{query}"~Ausdruck. Der \textsc{Secondo}-Parser prüft Attribut und Ergebnis des \secondo{query}-Ausdrucks auf Typ-Kompatibilität mit dem Attribut-Ausdruck auf der linken Seite. 

Geschachtelte Prädikate, die zwei Relationen des äußeren Abfrageblocks referenzieren, werden mit dem \secondo{symmjoin}-Operator übersetzt. Dieser Operator erlaubt die Formulierung beliebiger Join-Bedingungen, die nicht auf skalare Operatoren beschränkt sein müssen. Die Signatur des Operators ist \secondo{$stream1 \times stream2 \times map \rightarrow stream$}, wobei die Mapping-Funktion die Signatur \secondo{$streamelem1 \times streamelem2 \rightarrow bool$} haben muss. 

Die Mapping-Funktion wird hier ebenfalls als Vergleich eines Attribut-Ausdrucks mit einem Abfrageergebnis übersetzt. Auch hier müssen die Parameternamen den Relationen zugeordnet werden, um den Zugriff auf die Attribute in der geschachtelten Abfrage entsprechend übersetzen zu können. 

Bei unserem Beispiel wird das geschachtelte Prädikat in einen \secondo{filter}-Ausdruck übersetzt. Der Parameter bekommt den Namen \secondo{alias4}. Der Zugriff auf das Attribut \secondo{PLZ} muss innerhalb des \secondo{filter}-Ausdrucks über die entsprechende Umbenennung erfolgen.

\begin{lstlisting}
plz feedproject[Ort, PLZ]  
filter[
	fun (alias4: TUPLE) 
	(attr(alias4, PLZ) = 	plz  feed {p} max[PLZ_p])
] {0.0004995, 0.046} 
project[Ort]  
consume
\end{lstlisting}

%\begin{itemize}
%	\item Mit einem Parameter (normalerweise Filter)
%	
%	\item mit zwei Parametern für symmjoin (akzeptiert allgemeine Funktion) Wird in einem geschachtelten Prädikat auf zwei Relationen des äußeren Abfrageblocks verwiesen, so handelt es sich semantisch um ein Join-Prädikat. Symmjoin ist der einzige Algorithmus, der die Join-Operation auch für andere Fälle als den Equi-Join ausführen kann. Der Operator akzeptiert zwei Tupelströme und eine Mapping-Funktion mit zwei Parameter als Argumente. Die Mapping-Funktion hat die Signatur $(streamelem1, streamelem2) \rightarrow bool$. Über die Parameter streamelem1 und streamelem2 kann innerhalb der Unterabfrage auf die gerade betrachteten Tupel der äußeren Relationen zugegriffen werden. 
%\end{itemize}



%
% EOF
%