secondo/Optimizer/Subqueries/kapitel/implementierung.tex

%
% Kapitel Implementierung
%
%

\chapter{Implementierung}\label{chp:Implementierung}
Die Beschreibung der Umsetzung der in Kapitel \ref{chp:Entwurf} vorgestellten <20>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<72>utert. Im ersten Schritt werden Umschreibungsalgorithmen auf die Abfrage angewandt, die die Abfrage in eine inhaltlich <20>quivalente Struktur <20>berf<72>hren. Die umgeschriebene Abfrage erlaubt dabei eine effizientere Optimierung, z.B. durch Verwendung von Indizes, die durch zus<75>tzlich eingef<65>gte abgeleitete Pr<50>dikate benutzt werden k<>nnen. Hierzu geh<65>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<65>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<73>hrbaren Plan <20>bersetzt. Anschlie<69>end wird der Plan in die Syntax des \textsc{Secondo}-Kernels <20>bersetzt. Die Optimierung geschachtelter Pr<50>dikate erfolgt integriert in den beschriebenen Schritten. F<>r die <20>bersetzung der Unterabfragen sind die vom Optimierer ermittelten Konstrukte der <20>u<EFBFBD>eren Abfrage notwendig. Abh<62>ngig davon, ob der Optimierer das Pr<50>dikat als Join-Pr<50>dikat oder als Selektions-Pr<50>dikat <20>bersetzt, sind unterschiedliche <20>bersetzungen notwendig. Eine <20>bersetzung w<>hrend der Optimierungsphase ist im Moment nicht m<>glich, da grundlegende Datenstrukturen zu Beginn der <20>bersetzung eines Abfrageblocks initialisiert werden. Die <20>bersetzung zu diesem Zeitpunkt w<>rde die bereits aufgebauten Datenstrukturen des <20>u<EFBFBD>eren Abfrageblocks zur<75>cksetzen. Daher erfolgt die <20>bersetzung der Unterabfragen, die nicht durch Entschachtelung aufgel<65>st werden k<>nnen, um einen Schritt verschoben, d.h. es findet eine Verzahnung der <20>bersetzungsschritte zwischen <20>u<EFBFBD>erer Abfrage und Unterabfrage statt.


Die in diesem Kapitel dargestellten Beispiele beziehen sich auf die Relationen \secondo{Staedte} (alle deutschen St<53>dte mit den Attributen Kennzeichen, Vorwahl, Postleitzahl, Bev<65>lkerung und Bezeichnung), \secondo{PLZ} (alle deutschen Postleitzahlen) und \secondo{Orte} (alle deutschen Gemeinden mit den Attributen Bev<65>lkerung in Tausend Einwohner, Vorwahl und Kennzeichen) der Datenbank \secondo{opt}. Diese ist standardm<64><6D>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<72>nge w<>hrend der Optimierung darstellen zu k<>nnen, werden zus<75>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<74>lt Werkst<73>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 <20>bernommen werden. Aus Gr<47>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<75>bersichtlichem Quellcode und Leistungseinbu<62>en beim \secondo{sortmergejoin}. Daher wurde auf der Basis der \secondo{sortmergejoin}-Implementierung eine eigenst<73>ndige Implementierung des Operators \secondo{smouterjoin} erstellt. 

\subsection{Symm-Outer-Join}


\section{Umschreiben quantifizierter Pr<50>dikate}
Pr<EFBFBD>dikate mit den quantifizierenden Operatoren \sql{exists, not exists, any} und \sql{all} werden in <20>quivalente Pr<50>dikate mit Aggregationen <20>berf<72>hrt. Damit sind sie den in Kapitel \ref{chp:Entwurf} beschriebenen Algorithmen zur Entschachtelung zug<75>nglich. \sql{exists} und \sql{not exists} werden in eine Pr<50>fung transformiert, ob das Ergebnis mehr als 0 Tupel bzw. genau 0 Tupel enth<74>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<EFBFBD>dikate mit \sql{all} und \sql{any} werden in die im vorigen Kapitel beschriebenen Pr<50>dikate vom Typ JA transformiert. Dieser Schritt erfolgt bei jedem geschachtelten Pr<50>dikat, unabh<62>ngig davon, ob eine weitere Entschachtelung m<>glich ist. Eine direkte <20>bersetzung der quantifizierenden Operatoren in die ausf<73>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<65>hrleisten. Diese Umwandlung erfolgt durch das Pr<50>dikat preTransform/2. 

\section{Entschachtelung}
Nach der Vorabtransformation quantifizierter Pr<50>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<50>dikate, zu <20>berf<72>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<73>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<EFBFBD>re Relationen} werden f<>r die Entschachtelung korrelierter Abfragen mit Aggregationsfunktion ben<65>tigt. Um die Geschwindigkeit bei wiederholtem Ausf<73>hren der Abfragen zu beschleunigen, werden die zum Entschachteln eines Pr<50>dikats notwendigen tempor<6F>ren Relationen zur Laufzeit in einem Prolog-Fakt gespeichert. Bei einer Datenbank werden alle eventuell noch vorhandenen tempor<6F>ren Relationen gel<65>scht, um in jeder neuen Sitzung eine saubere Datenbankumgebung bereitzustellen. Die Implementierung des allgemeinen Entschachtelungsalgorithmus nach Kim/Ganski/Wong wurde mit dem Pr<50>dikat \prolog{transformNestedPredicates/6} realisiert. Da SQL beliebig tief geschachtelte Abfragen zul<75>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<65>st werden k<>nnen, werden als geschachtelte Ausdr<64>cke <20>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<75>ssig sind, schl<68>gt die <20>bersetzung fehl, falls das Ergebnis der Unterabfrage keine skalare Konstante ist. Jede Unterabfrage in der \sql{select}-Klausel wird mit dem Pr<50>dikat \prolog{transformNestedAttribute/4} in einen Attributausdruck umgewandelt. Hierbei wird <20>berpr<70>ft, ob die Abfrage keine korrelierten Pr<50>dikate enth<74>lt. Ist die Abfrage nicht frei von korrelierten Pr<50>dikaten, so kann keine Transformation der Unterabfrage vorgenommen werden.

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

\subsection{Geschachtelte Pr<50>dikate}
<EFBFBD>ber die Erkennung des Schachtelungstyps wird der Algorithmus ausgew<65>hlt, der auf das Pr<50>dikat angewandt wird. Hierf<72>r wird das SQL-Pr<50>dikat in Teilausdr<64>cke zerlegt. Es wird dabei unterschieden zwischen geschachtelten Ausdr<64>cken mit un<75>rem Operator wie z.B. \sql{exists} und bin<69>ren Operatoren. Bin<69>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<65>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<50>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<50>dikate wird <20>ber eine Depth-First-Suche rekursiv durchgef<65>hrt, d.h. es wird bei den Bl<42>ttern des Abfragegraphen mit der Optimierung begonnen. Da die Entschachtelungsalgorithmen eine Abfrage der Schachtelungstiefe n in eine Abfrage der Schachtelungstiefe n-1 <20>berf<72>hren, entspricht dies genau der Vorgehensweise in \cite{38723}. Geschachtelte Pr<50>dikate, die nicht den Klassen A,J,N oder JA entsprechen, werden wie \enquote{einfache} Pr<50>dikate behandelt. Ihre <20>bersetzung erfolgt <20>ber die triviale geschachtelte Ausf<73>hrung und wird erst bei der <20>bersetzung des Plans in ausf<73>hrbare Syntax vorgenommen. 

F<EFBFBD>r Typ-A Abfragen wird die Abfrage ausgewertet und das Ergebnis der Abfrage an ihrer Stelle eingef<65>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<70>ngliche Abfrage <20>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<50>dikat, die mit den Standardverfahren des Optimierers <20>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<50>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 <20>u<EFBFBD>eren Abfrage vereinigt werden. Ist der verwendete Operator \sql{in}, so muss eine tempor<6F>re Relation erzeugt werden, die die Projektion der inneren Relation auf die Join-Spalten ist. Hierdurch werden unerw<72>nschte Duplikate entfernt und die Mengensemantik des Operators \sql{in} wird auch f<>r das Join-Pr<50>dikat erhalten. Auch die Pr<50>dikate liegen als Liste von Konjunktionstermen vor und k<>nnen <20>ber das Pr<50>dikat \prolog{append} zu einer Liste zusammengef<65>hrt werden. Im letzten Schritt des Algorithmus wird das zus<75>tzliche Join-Pr<50>dikat erzeugt. Der Operator des neuen Pr<50>dikats ist \enquote{=}, falls das geschachtelte Pr<50>dikat den Operator \sql{in} beinhaltete, andernfalls wird der urspr<70>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<50>dikat und dem Pr<50>dikat der Unterabfrage werden in Form der zwei Pr<50>dikate \lstinline{sname = ort} und \lstinline{plz > 5000} in die entschachtelte Variante <20>bernommen.

Eine Typ-J Abfrage unterscheidet sich von einer Typ-N nur durch ein korreliertes Pr<50>dikat. In der entschachtelten Abfrage wird das korrelierte Pr<50>dikat der Unterabfrage zu einem Join-Pr<50>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<50>dikat \lstinline{plz < bev}, das sich in der urspr<70>nglichen Abfrage auf Relation \lstinline{staedte} des <20>u<EFBFBD>eren und Relation \lstinline{plz} des inneren Abfrageblocks bezieht, zu einem Join-Pr<50>dikat der entschachtelten Abfrage.

Die komplexeste Behandlung erfordert Algorithmus NEST-JA2 (siehe Abschnitt \ref{sct:Algorithmus NEST-JA2}). Im ersten Schritt werden die Pr<50>dikate der Unterabfrage in einfache Pr<50>dikate, Join-Pr<50>dikate der inneren Abfrage und korrelierte Pr<50>dikate partitioniert. Danach werden die drei oben beschriebenen tempor<6F>ren Relationen erzeugt. F<>r die Projektion der <20>u<EFBFBD>eren Relationen auf die Join-Attribute m<>ssen diese aus den korrelierten Pr<50>dikaten der Unterabfrage ermittelt werden. Hierzu werden die in den korrelierten Pr<50>dikaten verwendeten Attribute gegen die Metadaten der Relationen der Unterabfrage gepr<70>ft. Die Attribute, die nicht in den Relationen definiert sind, sind Attribute des <20>u<EFBFBD>eren Abfrageblocks. Die Restriktion der inneren Relationen erfolgt nur, falls die Unterabfrage einfache Pr<50>dikate enth<74>lt. Andernfalls werden die Relationen der Unterabfrage direkt weiterverwendet. Die Aggregation <20>ber den beiden tempor<6F>ren Relationen wird abh<62>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<6F>ren Relation und der urspr<70>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<6F>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<67>ndert werden, sofern sie sich auf ein Attribut der dritten tempor<6F>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<61>r m<>ssen alle Attributausdr<64>cke, die Attribute der tempor<6F>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<6F>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<68>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 <20>berpr<70>fen l<>sst ist das Ergebnis (Tabelle \ref{tab_Q2}) <20>bereinstimmend mit dem Ergebnis der geschachtelten Iteration. (Siehe auch die Ausf<73>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 <20>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<6F>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<50>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<50>dikate enthalten, die nicht durch die Entschachtelungsalgorithmen in ihre kanonische Form <20>berf<72>hrt werden k<>nnen. Um auch f<>r diese Pr<50>dikate eine <20>bersetzung in die ausf<73>hrbare Syntax von \textsc{Secondo} zu gew<65>hrleisten, m<>ssen alle f<>r die Optimierung ben<65>tigten Metadaten zu den verwendeten Attributen und Relationen ermittelt werden.
Die Metadaten zu Pr<50>dikaten werden im Optimierer in einem Fakt \secondo{pr(P, R)} f<>r einfache (Selektions)-Pr<50>dikate und \secondo{pr(P, R1, R2)} bei Join-Pr<50>dikaten f<>r die weitere Verarbeitung ermittelt (siehe auch \cite{DBLP:conf/ideas/DiekerG00}). P bezeichnet hier einen Pr<50>\-di\-kat\-aus\-druck, d.h. einem booleschen Ausdruck <20>ber Attributen von bis zu zwei Relationen. R bzw. R1 und R2 sind die Relationen, deren Attribute im Pr<50>dikat verwendet werden. Attribute, die im Pr<50>dikatausdruck verwendet werden, werden in einem Fakt \secondo{attr(Attributname, No, Case)} gespeichert. Hierbei bezieht sich \prolog{No} bei Join-Pr<50>dikaten auf die Reihenfolge der Relation aus der das Attribut stammt. Ist das Attribut in der ersten aufgef<65>hrten Relation enthalten, so hat No den Wert 1, andernfalls den Wert 2. Bei Selektionspr<70>dikaten ist dieser Wert immer 0, da die Relation des Attributs eindeutig ist. Bei geschachtelten Pr<50>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<50>dikats auch bei der <20>bersetzung der Unterabfrage zur Verf<72>gung zu haben, wird jede korrelierte Unterabfrage als Fakt subquery(Abfrage, Relation) bzw. subquery(Abfrage, erste Relation, zweite Relation) gespeichert. Hierdurch kann bei der <20>bersetzung in einen Plan auf die Reihenfolge der verwendeten <20>u<EFBFBD>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<72>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 <20>u<EFBFBD>eren Abfrageblocks ermittelt. Beim Nachschlagen der Relationen wird auf die Eindeutigkeit der Attributnamen <20>ber alle Abfragebl<62>cke hinweg geachtet. D.h. enth<74>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<74>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 <20>u<EFBFBD>eren und inneren Abfrageblock, dass eine der beiden Relationen umbenannt werden muss. Auch die Metadaten der in einem Pr<50>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<75>ckgesetzt werden, m<>ssen bereits an dieser Stelle die notwendigen Abfragen auf den Stichproben-Relationen f<>r die Pr<50>dikate der Unterabfrage erfolgen. Die Ermittlung der Selektivit<69>ten erfolgt also ebenso wie die Entschachtelung Bottom-Up. Ein geschachteltes Pr<50>dikat, das zwei Relationen der <20>u<EFBFBD>eren Abfrage referenziert, wird bei der Ermittlung der Selektivit<69>t wie ein einfaches Join-Pr<50>dikat behandelt. Die Abfrage <20>ber den Stichprobenrelationen f<>r ein Join-Pr<50>dikat wird immer mit einem \secondo{loopjoin} ausgef<65>hrt. Daher wird auch hier, wie unten beschrieben, das geschachtelte Pr<50>dikat mit Hilfe einer Mapping Funktion <20>bersetzt. Die Relationen der Unterabfrage werden auf entsprechenden Stichprobenrelationen ge<67>ndert. Die Gr<47><72>e des Ergebnisses der Stichprobenabfrage wird auf insgesamt maximal 250.000 Tupel eingeschr<68>nkt. Hierzu wird die Anzahl der in der Stichprobenabfrage verwendeten Relationen gez<65>hlt. Bei n Relationen werden nur auf die ersten $\sqrt[n]{250.000}$ Tupel jeder Stichprobenrelation zugegriffen. Die maximal in einer Selektivit<69>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<50>dikaten \prolog{setMaxSampleCard/1} und \prolog{setMaxSelCard/1} angepasst werden.

Die Ermittlung der Selektivit<69>t erfolgt f<>r Join-Pr<50>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<50>dikat m<>ssen ebenfalls entsprechend umbenannt werden. Die Umbenennung bei nicht geschachtelten Pr<50>dikaten erfolgt <20>ber die Angabe der Position der umbenannten Relation innerhalb des Pr<50>dikats. Durch Zerlegung und rekursive Anwendung des Umbenennungspr<70>dikats erfolgt diese Umbenennung auf beliebigen Ausdr<64>cken. Da die im Fakt \secondo{attr(Attributname, No, Case)} angegebene Position bei Attributen in korrelierten Pr<50>dikaten nicht zwingend deckungsgleich ist mit der Position der Relation im geschachtelten Pr<50>dikat, wird diese Zuordnung <20>ber alle Anwendungen des Umbenennungspr<70>dikats in einem Kellerspeicher festgehalten. <20>ber diesen Kellerspeicher kann dann auf den Namen eines Stroms zugegriffen werden, um die Umbenennung eines Pr<50>dikats der geschachtelten Abfrage durchzuf<75>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<50>dikate
%	\subitem nach dem Lookup eines Pr<50>dikats immer die Selektivit<69>t ermitteln, um die globalen Datenstrukturen (pog etc.) nicht w<>hrend der Plan-Ermittlung durch Subqueries zerst<73>ren
%\end{itemize}

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

\subsection{Ausf<EFBFBD>hrungsplan f<>r geschachtelte Pr<50>dikate}
Der Ausf<73>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 <20>ber den Optimierer erfolgen, da die Abfrage keine korrelierten Pr<50>dikate enth<74>lt. Hierzu wird das Optimierungpr<70>dikat \prolog{optimize/3} aufgerufen. Das Ergebnis ist ein Ausf<73>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<50>dikaten befreit werden. Die nicht-korrelierte Abfrage kann dann wieder vom Optimierer bearbeitet werden. Der daraus resultierende Plan wird nun um die korrelierten Pr<50>dikate erweitert. Hierbei werden diese in Form von \secondo{filter}-Ausdr<64>cken an den Plan angef<65>gt. Der \textsc{Secondo}-Operator \secondo{filter} erwartet als Argumente einen Tupelstrom (gegeben durch den Teilplan) und ein Pr<50>dikat, das auf eben diesem Strom angewandt wird. Dabei werden Pr<50>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<65>ber der wahlfreien Ausf<73>hrung dieser Selektionen haben. Die Implementierung in Prolog, die die Pr<50>dikate in der entsprechenden Reihenfolge ermittelt, erlaubt auch die Erweiterung um die Einbeziehung der Ausf<73>hrungskosten der Pr<50>dikate, um eine bessere Absch<63>tzung der minimalen Laufzeit zu erhalten. Grunds<64>tzlich w<>re auch eine Erweiterung des Optimierungsalgorithmus denkbar, bei der die korrelierten Pr<50>dikate mit in die Optimierung einbezogen werden. Damit w<>re es m<>glich, eine optimale Reihenfolge f<>r die Ausf<73>hrung der Pr<50>dikate zu ermitteln. Die <20>bersetzung geschachtelter Abfragen erfolgt Top-Down, damit zum <20>bersetzungszeitpunkt die Entscheidungen des Optimierers bekannt sind, mit welchen Konstrukten das geschachtelte Pr<50>dikat <20>bersetzt wird. Dies ist notwendig, um das Pr<50>dikat in einen passenden Ausdruck zu <20>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}

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

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

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

\subsection{IN Operator}
Der Operator \sql{in} erlaubt die <20>berpr<70>fung auf Enthaltensein in einer Menge (siehe \ref{sct:<3A>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<72>gung stellt. Mengen, die als Liste von Konstanten spezifiziert sind, werden in der <20>bersetzungsphase in ein entsprechendes \textsc{Secondo}-Objekt <20>bersetzt. 


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

wird in 

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

<EFBFBD>bersetzt. Der \sql{in}-Operator wird mit dem \textsc{Secondo} Operator \secondo{in} der \algebra{Collection}-Algebra <20>bersetzt. Bei Mengen die durch Auflistung definiert werden ist keine zus<75>tzliche Operation erforderlich. Mengen, deren Definition als Ergebnis von Unterabfragen erfolgt werden unter Zuhilfenahme der Operatoren \secondo{collect\_set} und \secondo{projecttransformstream} <20>bersetzt. Da der \secondo{in}-Operator nur auf einer Menge definiert ist, muss der Tupelstrom in eine Menge <20>berf<72>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 <20>u<EFBFBD>eren Stroms wird mit \secondo{in} gepr<70>ft, ob der entsprechende Attributwert enthalten ist. D.h. es wird genau die mengenbasierte Semantik des \sql{in}-Operators erreicht.

Ein Pr<50>dikat 

\begin{lstlisting}
<EFBFBD>$A_i$<EFBFBD> in (select <20>$A_j$<EFBFBD> from <20>$R_n$<EFBFBD>)
\end{lstlisting}

wird in den \textsc{Secondo}-Ausdruck 

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

<EFBFBD>bersetzt. 

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

Die hier behandelten Ausdr<64>cke haben die Form 

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

Je nach Anzahl der verwendeten <20>u<EFBFBD>eren Relationen wird die geschachtelte Abfrage <20>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 <20>bersetzt. Auf die Attribute der <20>u<EFBFBD>eren Relation kann dann <20>ber die Parameter der Mapping-Funktion zugegriffen werden. F<>r den Zugriff auf die Paramter der Mapping-Funktion m<>ssen noch zus<75>tzliche Operatoren eingef<65>gt werden. Diese ben<65>tigen die Parameternamen, um den Zugriff zu erm<72>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 <20>bersetzenden Pr<50>dikat um ein geschachteltes Pr<50>dikat mit einem skalaren Vergleichsoperator, so hat die Funktion die Form $A_i~\theta$~\secondo{query}"~Ausdruck. Der \textsc{Secondo}-Parser pr<70>ft Attribut und Ergebnis des \secondo{query}-Ausdrucks auf Typ-Kompatibilit<69>t mit dem Attribut-Ausdruck auf der linken Seite. 

Geschachtelte Pr<50>dikate, die zwei Relationen des <20>u<EFBFBD>eren Abfrageblocks referenzieren, werden mit dem \secondo{symmjoin}-Operator <20>bersetzt. Dieser Operator erlaubt die Formulierung beliebiger Join-Bedingungen, die nicht auf skalare Operatoren beschr<68>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 <20>bersetzt. Auch hier m<>ssen die Parameternamen den Relationen zugeordnet werden, um den Zugriff auf die Attribute in der geschachtelten Abfrage entsprechend <20>bersetzen zu k<>nnen. 

Bei unserem Beispiel wird das geschachtelte Pr<50>dikat in einen \secondo{filter}-Ausdruck <20>bersetzt. Der Parameter bekommt den Namen \secondo{alias4}. Der Zugriff auf das Attribut \secondo{PLZ} muss innerhalb des \secondo{filter}-Ausdrucks <20>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<50>dikat auf zwei Relationen des <20>u<EFBFBD>eren Abfrageblocks verwiesen, so handelt es sich semantisch um ein Join-Pr<50>dikat. Symmjoin ist der einzige Algorithmus, der die Join-Operation auch f<>r andere F<>lle als den Equi-Join ausf<73>hren kann. Der Operator akzeptiert zwei Tupelstr<74>me und eine Mapping-Funktion mit zwei Parameter als Argumente. Die Mapping-Funktion hat die Signatur $(streamelem1, streamelem2) \rightarrow bool$. <20>ber die Parameter streamelem1 und streamelem2 kann innerhalb der Unterabfrage auf die gerade betrachteten Tupel der <20>u<EFBFBD>eren Relationen zugegriffen werden. 
%\end{itemize}



%
% EOF
%