%
% Kapitel Leistungsbewertung
%
%

\chapter{Leistungsbewertung}\label{chp:Leistungsbewertung}
%\definecolor{ListingBackground}{rgb}{0.92,0.92,0.92}
Die geschachtelten Abfragen des TPC-D Benchmarks, die mit den in dieser Arbeit implementierten Algorithmen übersetzt werden können, dienen in diesem Kapitel als Beispiel, um die einzelnen Transformationsschritte bei der Entschachtelung darzustellen. Die Abfragen Q8, Q11, Q13 und Q18 lassen sich mit der vom Optimierer momentan erkannten Syntax nicht übersetzen. Sie verwenden in der \sql{select}-Klausel Ausdrücke über Aggregationsergebnissen (Q8), die \sql{having}-Klausel (Q11, Q18) oder benötigen einen Left-Outer-Join-Operator. Eine Erweiterung des Optimierers um diese Funktionalität war nicht Teil dieser Arbeit. 

Die Abfragen sind über folgenden Relationen definiert:

\begin{itemize}
	\item PART -- Teile
	\item SUPPLIER -- Lieferanten
	\item PARTSUPP -- Verknüpfungstabelle zwischen Teilen und Lieferant
	\item CUSTOMER -- Kunden
	\item ORDERS -- Bestellungen
	\item LINEITEM -- Bestellpositionen
	\item NATION -- Länder
	\item REGION -- Regionen
\end{itemize}.

Eine genaue Aufstellung der Schemata der Tabellen findet sich in \cite{TPC-D}.

Am Vergleich der Laufzeiten der einzelnen Phasen des Optimierers lässt sich erkennen, in welchen Fällen eine entschachtelte Ausführung der iterativ geschachtelten über- bzw. unterlegen ist. Die Abfragen werden auf einer Datenbank ausgeführt, die über ein Generierungsskript erzeugt werden kann. Um die Größe der Datenbank zu beeinflussen, existiert ein Skalierungsfaktor, der bei der Erzeugung der Datenbank angegeben werden muss. Jede Abfrage wurde auf Datenbanken mit verschiedenen Skalierungsfaktoren durchgeführt. Bei kleineren Skalierungsfaktoren kann es zu Fehlverhalten des Optimierers kommen, da die temporären Relationen unter Umständen leer sind. Die Berechnung der Selektivität von Join-Prädikaten, die auf leere Relationen verweisen, ist momentan fehlerhaft implementiert. 

Vor der Ausführung der Abfragen wurden alle vorhandenen Metainformationen zu Prädikaten und Relationen gelöscht. Die Laufzeit für die Ermittlung der Selektivitäten fließt also in die hier dargestellten Laufzeiten mit ein. Da der Optimierer über einen Query-Cache verfügt, in dem die entschachtelte Variante einer Abfrage abgespeichert wird, ist jede weitere Ausführung der gleichen Abfrage deutlich schneller. Der Query-Cache wird bei der ersten Ausführung als \enquote{kalt}, bei den darauf folgenden Ausführungen als \enquote{warm} bezeichnet. Ausführungszeiten, die bei der Entschachtelung ohne bzw. mit Ausnutzung des Query-Cache, d.h. \enquote{kalt} bzw. \enquote{warm} erzielt wurden, werden in den dargestellten Grafiken kurz mit \enquote{entschachtelt, kalt} bzw. \enquote{entschachtelt, warm} bezeichnet.

\section{Laufzeit- und Strukturvergleich}\label{sct:Laufzeit- und Strukturvergleich}
\subsection{TPC-D Q2}
Diese Abfrage dient der Ermittlung des günstigsten Lieferanten für ein gegebenes Bauteil in einer Region. Für ein Bauteil einer bestimmten Art und Größe wird der Lieferant ermittelt, der dieses zu den günstigsten Konditionen anbietet. Gibt es mehrere Lieferanten in der gewählten Region, die das gewünschte Teil zu den günstigsten Konditionen anbieten, so werden die 100 Lieferanten mit dem höchsten Kontostand angezeigt. Von jedem Lieferanten werden der Kontostand, der Name und das Land, die Teilenummer und der Hersteller, die Lieferantenadresse, Telefonnummer und eine Bemerkung angezeigt. Als Werte der Parameter SIZE, TYPE und REGION wurden die Werte aus der Abfrageüberprüfung des Benchmarks gewählt, d.h. SIZE = \enquote{15}, TYPE = \enquote{BRASS} und REGION = \enquote{EUROPE}.

\begin{lstlisting}[caption=Abfrage Q2,label=Q2:nested]
select
	[sacctbal, sname,
	 nname, ppartkey,
	 pmfgr, saddress,
	 sphone, scomment]
from
	[part, supplier,
	 partsupp, nation, region]
where
	[ppartkey = pspartkey,
	ssuppkey = pssuppkey,
	psize = 15,
	ptype contains "BRASS",
	snationkey = nnationkey,
	nregionkey = rregionkey,	
 rname = "EUROPE",
	pssupplycost = (
		select
			min(ps:pssupplycost)
		from
			[partsupp as ps, supplier as s,
			nation as n, region as r]
		where
			[ppartkey = ps:pspartkey,
		 	s:ssuppkey = ps:pssuppkey,
		 	s:snationkey = n:nnationkey,
		 	n:nregionkey = r:rregionkey,	
		 	r:rname = "EUROPE"]
	 )]
orderby
	[sacctbal desc,
	nname,
	sname,
	ppartkey] 
first 100
\end{lstlisting}

Die innere Abfrage ist vom Typ JA, da eine Aggregation (das Minimum) berechnet wird und sie ein Prädikat \sql{ppartkey = ps:ppartkey} enthält, das auf die Relation \sql{pssupplycost} des äußeren Abfrageblocks zugreift. Der Optimierer wendet also den in \ref{sct:Algorithmus NEST-JA2} beschriebenen Algorithmus an. Hierzu werden insgesamt drei temporäre Tabellen benötigt. Die erste temporäre Relation ist die Restriktion der im inneren Abfrageblock verwendeten Relationen des äußeren Blocks auf die benötigten Attribute.

\begin{lstlisting}[caption=Abfrage Q2{,} Definition trelxx1,label=Q2:trelxx1]
trelxx1 = 
select distinct [ppartkey, pspartkey] 
from [part, partsupp]
\end{lstlisting}

Die zweite temporäre Relation ist die Einschränkung der inneren Relation durch alle \emph{einfachen} Prädikate.

\begin{lstlisting}[caption=Abfrage Q2{,} Definition trelxx2,label=Q2:trelxx2]
trelxx2 =
select [ps:pspartkey, ps:pssupplycost]
from 
	[partsupp as ps, supplier as s, 
	nation as n, region as r]
where 
	[s:ssuppkey = ps:pssuppkey, 
	s:snationkey = n:nnationkey, 
	n:nregionkey = r:rregionkey, 
	r:rname = "EUROPE"]
\end{lstlisting}

Die dritte temporäre Relation wird aus dem Equi-Join der ersten und zweiten temporären Relation unter Berechnung der Aggregation gebildet. Man beachte die Attributnamen mit \enquote{\_ps}. Diese sind notwendig, da sich Optimierer und \textsc{Secondo} in der Syntax für umbenannte Tupel unterscheiden. Es muss hier auf die ausführbare Syntax der Spalten zurück gegriffen werden. 

\begin{lstlisting}[caption=Abfrage Q2{,} Definition trelxx3,label=Q2:trelxx3]
trelxx3 = 
select [pspartkey_ps, min(pssupplycost_ps) as var1] 
from [trelxx1, trelxx2] 
where [ppartkey = pspartkey_ps] 
groupby pspartkey_ps
\end{lstlisting}

Mit Algorithmus \textbf{NEST-G} ergibt sich 

\begin{lstlisting}[caption=Abfrage Q2 in SQL-Syntax{,} entschachtelt,label=Q2:unnested]
select 
	[sacctbal, sname, nname, 
	ppartkey, pmfgr, saddress, 
	sphone, scomment]
from 
	[part, supplier, partsupp, 
	nation, region, trelxx3 as alias1]
where 
	[ppartkey = pspartkey, 
	ssuppkey = pssuppkey, 
	psize = 15, 
	ptype contains["BRASS"], 
	snationkey = nnationkey, 
	nregionkey = rregionkey, 
	rname = ["EUROPE"], 
	ppartkey = alias1:pspartkey_ps, 
	pssupplycost = alias1:var1]
orderby 
	[sacctbal desc, nname, 
	sname, ppartkey]
first 100
\end{lstlisting}

als inhaltlich äquivalente Abfrage. Die beiden Prädikate \sql{pssupplycost = alias1:var1} und \sql{ppartkey = alias1:pspartkey\_ps} ersetzen das geschachtelte Prädikat 

\begin{lstlisting}[caption=Abfrage Q2{,} geschachteltes Prädikat,label=Q2:nested_predicate]
pssupplycost = (
		select min(ps:pssupplycost)
		from 
			[partsupp as ps, supplier as s,
			nation as n, region as r]
		where
			[ppartkey = ps:pspartkey,
		 	s:ssuppkey = ps:pssuppkey,
		 	s:snationkey = n:nnationkey,
		 	n:nregionkey = r:rregionkey,	
		 	r:rname = "EUROPE"]
	 )
\end{lstlisting}
.

Das erste der beiden Prädikate ergibt sich direkt aus dem geschachtelten Prädikat, während das zweite Prädikat die Übernahme des korrelierten Prädikats in die endgültige Abfrage darstellt. Zusätzlich wurde die neue Relation trelxx3 in die FROM-Klausel aufgenommen. Alle nicht korrelierten Prädikate der Unterabfrage wurden bereits bei der Erstellung der Relation trelxx3 berücksichtigt. Die Prädikate der entschachtelten Variante sind nur noch einfache und Join-Prädikate. 

Wird die Abfrage ohne die Anwendung von Entschachtelungsalgorithmen übersetzt, so ergibt sich in ausführbarer Syntax folgender Ausdruck:

\begin{lstlisting}[caption=Abfrage Q2 in ausführbarer Syntax{,} geschachtelt,label=Q2:executable]
PART feedproject[pMFGR, pPARTKEY, pSIZE, pTYPE] 
SUPPLIER feedproject[sACCTBAL, sADDRESS, sCOMMENT, sNAME, sNATIONKEY, sPHONE, sSUPPKEY] 
NATION feedproject[nNAME, nNATIONKEY, nREGIONKEY] 
REGION feedproject[rNAME, rREGIONKEY] 
sortmergejoin[nREGIONKEY , rREGIONKEY] {0.007992, 0.808} 
sortmergejoin[sNATIONKEY , nNATIONKEY] {0.004995, 0.5} 
PARTSUPP feedproject[psPARTKEY, psSUPPKEY, psSUPPLYCOST] 
symmjoin[(.sSUPPKEY = ..psSUPPKEY)] {0.00024975, 0.02525} 
symmjoin[(.pPARTKEY = ..psPARTKEY)] {1.24875e-05, 0.001275} 
filter[
	fun (alias3: TUPLE) 
	(
		attr(alias3, psSUPPLYCOST) 
		= 
		SUPPLIER feedproject[sNATIONKEY, sSUPPKEY] {s} 
		NATION feedproject[nNATIONKEY, nREGIONKEY] {n} 
		REGION feedproject[rNAME, rREGIONKEY] {r} 
		sortmergejoin[nREGIONKEY_n , rREGIONKEY_r] {0.007992, 0.8} 
		sortmergejoin[sNATIONKEY_s , nNATIONKEY_n] {0.004995, 0.505} 
		filter[(.rNAME_r = "EUROPE")] {0.1998, 19.4} 
		PARTSUPP feedproject[psPARTKEY, psSUPPKEY, psSUPPLYCOST] {ps} 
		symmjoin[(.sSUPPKEY_s = ..psSUPPKEY_ps)] {0.00024975, 0.026} 
		filter[(attr(alias3, pPARTKEY) = .psPARTKEY_ps)] 
		min[psSUPPLYCOST_ps] 
	)] {1.24875e-05, 0.001675} 
filter[(.pSIZE = 15)] {0.00624375, 0.60625} 
filter[(.pTYPE contains "BRASS")] {0.00624375, 0.625} 
filter[(.rNAME = "EUROPE")] {0.1998, 19.4} 
project[sACCTBAL, sNAME, nNAME, pPARTKEY, pMFGR, sADDRESS, sPHONE, sCOMMENT] 
sortby[sACCTBAL desc, nNAME asc, sNAME asc, pPARTKEY asc] 
head[100] 
consume
\end{lstlisting}

Das geschachtelte Prädikat (Listing \ref{Q2:nested_predicate}) ist mit einem komplexen \secondo{filter}-Ausdruck übersetzt worden. Die Unterabfrage wurde wie eine flache Abfrage übersetzt. Die einzige Besonderheit ist das Prädikat \secondo{filter[(attr(alias3, pPARTKEY) = .psPARTKEY\_ps)]} in dem das Attribut \secondo{pPARTKEY} der äußeren Relation \secondo{PART} referenziert wird.

Die Übersetzung der entschachtelten Abfrage entspricht der iterativ-geschachtelten Übersetzung, mit Ausnahme des geschachtelten \secondo{filter}-Ausdrucks. Dieser wird durch den Join mit der Relation \secondo{trelxx3} und die beiden Prädikate \secondo{symmjoin[(.psSUPPLYCOST = ..Var1\_alias1)]} und \secondo{filter[(.pPARTKEY = .psPARTKEY\_ps\_alias1)]} ersetzt. Dies entspricht gerade den durch den Algorithmus \textbf{NEST-G} vorgenommenen Änderungen an der Abfrage.

\begin{lstlisting}[language=secondoscript,caption=Abfrage Q2 in ausführbarer Syntax{,} entschachtelt,label=Q2:executable_unnested]
PART feedproject[pMFGR, pPARTKEY, pSIZE, pTYPE] 
SUPPLIER feedproject[sACCTBAL, sADDRESS, sCOMMENT, sNAME, sNATIONKEY, sPHONE, sSUPPKEY] 
NATION feedproject[nNAME, nNATIONKEY, nREGIONKEY] 
REGION feedproject[rNAME, rREGIONKEY] 
sortmergejoin[nREGIONKEY , rREGIONKEY] {0.007992, 0.808} 
sortmergejoin[sNATIONKEY , nNATIONKEY] {0.004995, 0.5} 
PARTSUPP feedproject[psPARTKEY, psSUPPKEY, psSUPPLYCOST] 
symmjoin[(.sSUPPKEY = ..psSUPPKEY)] {0.00024975, 0.02525} 
symmjoin[(.pPARTKEY = ..psPARTKEY)] {1.24875e-05, 0.001275} 
trelxx3 feedproject[psPARTKEY_ps, Var1] {alias1}
symmjoin[(.psSUPPLYCOST = ..Var1_alias1)] {2.93824e-05, 0.00302941}
filter[(.pPARTKEY = .psPARTKEY_ps_alias1)] {9.18199e-05, 0.0102022} 
filter[(.pTYPE contains "BRASS")] {0.00624375, 0.625} 
filter[(.pSIZE = 15)] {0.00624375, 0.60625} 
filter[(.rNAME = "EUROPE")] {0.1998, 19.4} 
project[sACCTBAL, sNAME, nNAME, pPARTKEY, pMFGR, sADDRESS, sPHONE, sCOMMENT] 
sortby[sACCTBAL desc, nNAME asc, sNAME asc, pPARTKEY asc] 
head[100] 
consume
\end{lstlisting}

\begin{table}[h]
\centering
\begin{tabular}{@{}lrrrr@{}} \toprule
& \multicolumn{4}{c}{Laufzeit in ms} \\ \cmidrule(l){2-5}
& \multicolumn{2}{c}{iterativ} & \multicolumn{2}{c}{entschachtelt} \\ 
Phase & \multicolumn{1}{c}{kalt} & warm & \multicolumn{1}{c}{kalt} & warm\\ \midrule
Rewrite & 0 & 0 & 549 & 0 \\
Lookup & 92 & 44 & 3 & 3 \\
QueryToPlan & 236 & 275 & 678 & 508 \\
Execute & 7673 & 7658 & 298 & 307 \\
\cmidrule(l){1-5} 
Total & 8241 & 8213 & 1790 & 1063 \\
\bottomrule\end{tabular}
 \caption{Detaillierte Laufzeiten von Q2 bei Skalierungsfaktor = 0,0008 der DB}
 \label{tab:Q2 Laufzeit}
\end{table}

Der Optimierer berechnet für den Skalierungsfaktor 0,0008 Kosten von 411,18 für die entschachtelte und 377,18 für die iterative Ausführung. Dies widerspricht den tatsächlichen Laufzeiten, wie man Tabelle \ref{tab:Q2 Laufzeit} entnehmen kann. Auch für den Skalierungsfaktor 0,0032 sehen die berechneten Kosten (1657,95 für die entschachtelte Ausführung, 1610,28 für die iterative Ausführung) ähnlich aus. Der Optimierer würde also bei einem Vergleich der Ausführungsstrategien die iterative Ausführung wählen. Wie der Abbildung \ref{plot:Q2 line} zu entnehmen ist, wäre diese Auswahl ungünstig. Möglicherweise werden die Ausführungskosten für geschachtelte Prädikate noch falsch eingeschätzt.

%\pgfplotsset{every x tick label/.style={below, yshift=-0.25em, rotate=90, xshift=-1.5em}, every y tick label/.style={/pgf/number format/1000 sep={.}}}
\pgfplotsset{every x tick label/.style={below}, every y tick label/.style={/pgf/number format/1000 sep={.}}}

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=,font=\footnotesize},
%xtick=data,
%ylabel=Sekunden,
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%xticklabels={1,2,3},
%]
%\addplot coordinates {(0,	0. 549	)(1,	0	)(2, 	0	)};
%\addplot coordinates {(0,	0.003	)(1,	0.003	)(2,	0.092	)};
%\addplot coordinates {(0,	0.678	)(1,	0.508	)(2,	0.236	)};
%\addplot coordinates {(0,	0.298	)(1,	0.307	)(2,	7.673	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Abfrage Q2, detaillierte Laufzeit in Sekunden}
%\label{Q2:plot bars}
%\end{figure}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}

\begin{figure}[h]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
%axis y line=left,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={,0.0016,0.0032,0.0064,0.0128},%0.0001,0.0002,0.0004,0.0008,0.0016,0.0032,0.0064},
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
%area legend,
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
%ybar stacked,
sharp plot
]

\addplot coordinates {(0.0008,	1.79	)(0.0016,	2.975	)(0.0032,	7.381	)(0.0064,	15.645	)(0.0128,	57.756	)};
\addplot coordinates {(0.0008,	1.063	)(0.0016,	1.887	)(0.0032,	5.095	)(0.0064,	8.094	)(0.0128,	31.848	)};
\addplot coordinates {(0.0008,	8.241	)(0.0016,	4.882	)(0.0032,	33.689	)(0.0064,	302.276	)(0.0128,	2568.521	)};
%\addplot coordinates {(0.0008,	8.213	)(0.0016,	4.813	)(0.0032,	33.764	)(0.0064,	300.085	)(0.0128,	2525.131	)};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}% kalt, iterativ warm}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q2 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q2 line}
\end{figure}

\subsection{TPC-D Q4}
Diese Abfrage ermittelt, wie gut das Bestell-Prioritätssystem funktioniert. D.h. es wird die Anzahl der Bestellungen ermittelt, bei welchen mindestens ein Teil nach dem versprochenen Lieferdatum beim Kunden einging. Die Abfrage führt die Anzahl solcher Bestellungen in der Reihenfolge der Bestellprioritäten auf. 
Als Parameter DATE wurde der Wert \enquote{1993-07-01} aus der Abfrage-Überprüfung gewählt

\begin{lstlisting}[caption=Abfrage Q4]
select
	[oorderpriority, count(*) as ordercount]
from orders
where		
	[oorderdate >= instant("1993-07-01"),		
	oorderdate < theInstant(
		year_of(instant("1993-07-01")), 
	 	month_of(instant("1993-07-01")) + 3, 
	 	day_of(instant("1993-07-01"))
	),
	exists(
	 	select *
		from lineitem
		where
			[lorderkey = oorderkey, 
			lcommitdate < lreceiptdate]
	)]
groupby [oorderpriority]
orderby	[oorderpriority]
\end{lstlisting}

Die Abfrage ist vom Typ J, da das geschachtelte Prädikat keine Aggregation enthält, aber über das Prädikat \sql{lorderkey = oorderkey} mit dem äußeren Abfrageblock korreliert ist.

Die Projektion der äußeren Relation auf die Join-Spalte ergibt
\begin{lstlisting}[caption=Abfrage Q4{,} Definition trelxx1]
trelxx1 = select distinct[oorderkey] from orders
\end{lstlisting}

Einschränkung der inneren Relation mit allen \emph{einfachen} Prädikaten.
\begin{lstlisting}[caption=Abfrage Q4{,} Definition trelxx2]
trelxx2 = select [lorderkey] from [lineitem] where [lcommitdate < lreceiptdate]
\end{lstlisting}


Als dritte temporäre Relation muss daher der Full-Outer-Join zwischen den temporären Relationen trelxx1 und trelxx2 berechnet werden. Da hier der Full-Outer-Join berechnet wird, ist die Definition in ausführbarer Syntax angegeben. Auch der Optimierer erzeugt diese Definition \emph{direkt} in ausführbarer Syntax.
\begin{lstlisting}[caption=Abfrage Q4{,} Definition trelxx3]
trelxx3 = 
trelxx1 feed 
trelxx2 feed 
smouterjoin[oORDERKEY, lORDERKEY] 
sortby[oORDERKEY asc] 
groupby[oORDERKEY;Var1: group feed filter[not(isempty(.lORDERKEY))] count] 
projectextend[Var1; lORDERKEY: .oORDERKEY] 
consume
\end{lstlisting}

Die \sql{exists}-Konstruktion aus der Abfrage vereinfacht sich nach der Optimierung zu einem Join mit der neuen Tabelle \secondo{trelxx3} und einer Selektion von Einträgen dieser Tabelle, die der Bedingung \secondo{0 < var1} genügen. Aus Gründen der Eindeutigkeit der Attributnamen wird die neue Relation unter dem Namen \secondo{alias1} eingebunden.
\begin{lstlisting}[caption=Abfrage Q4 in SQL-Syntax{,} entschachtelt]
select [oorderpriority, count(*) as ordercount] 
from [orders, trelxx3 as alias1] 
where 
	[oorderdate>=instant("1993-07-01"), 
	oorderdate<theInstant(
		year_of(instant("1993-07-01")), 
		month_of(instant("1993-07-01")) + 3, 
		day_of(instant("1993-07-01"))
	), 
	oorderkey = alias1:lorderkey, 
	0 < alias1:var1] 
groupby [oorderpriority] 
orderby [oorderpriority]
\end{lstlisting}

Die Übersetzung der entschachtelten Form von Abfrage Q4 erzeugt folgenden Ausdruck in ausführbarer Syntax

\begin{lstlisting}[caption=Abfrage Q4 in ausführbarer Syntax{,} entschachtelt]
ORDERS feedproject[oORDERDATE, oORDERKEY, oORDERPRIORITY] 
filter[(.oORDERDATE < theInstant(
	year_of(instant("1993-07-01")), 
	(month_of(instant("1993-07-01")) + 3), 
	day_of(instant("1993-07-01")))
)] {0.001665, 0.0841667} 
filter[(.oORDERDATE >= instant("1993-07-01"))] {0.0058275, 0.0833333} 
trelxx3 feedproject[lORDERKEY, Var1] {alias1} 
symmjoin[(.oORDERKEY = ..lORDERKEY_alias1)] {0.000803196, 0.007608} 
filter[(0 < .Var1_alias1)] {0.373792, 0.0875} 
sortby[oORDERPRIORITY asc] 
groupby[oORDERPRIORITY; Ordercount: group feed count ]
project[oORDERPRIORITY, Ordercount] 
sortby[oORDERPRIORITY asc] 
consume
\end{lstlisting}.

Dieser unterscheidet sich von der Übersetzung der Abfrage ohne Entschachtelung lediglich in der Übersetzung des geschachtelten Prädikats. In der entschachtelten Abfrage wird dieses durch einen Join mit Relation \secondo{trelxx3} über die Attribute \secondo{oORDERKEY} und \secondo{lORDERKEY} sowie das Selektions-Prädikat \secondo{filter[(0 < .Var1\_alias1)]} übersetzt. Die iterative Variante enthält dagegen die triviale Übersetzung mit einem \secondo{filter}-Ausdruck.

\begin{lstlisting}[caption=Abfrage Q4 in ausführbarer Syntax{,} geschachtelt]
ORDERS feedproject[oORDERDATE, oORDERKEY, oORDERPRIORITY] 
filter[(.oORDERDATE < theInstant(
	year_of(instant("1993-07-01")), 
	(month_of(instant("1993-07-01")) + 3), 
	day_of(instant("1993-07-01"))))
] {0.001665, 0.0841667} 
filter[(.oORDERDATE >= instant("1993-07-01"))] {0.0058275, 0.0833333} 
filter[
	fun (alias2: TUPLE) (
		0 
		< 
		LINEITEM feedproject[lCOMMITDATE, lORDERKEY, lRECEIPTDATE] 
		filter[(.lCOMMITDATE < .lRECEIPTDATE)] {0.0034965, 0.059} 
		filter[(.lORDERKEY = attr(alias2, oORDERKEY))] 
		count 
	)] {0.0008325, 0.0925} 
sortby[oORDERPRIORITY asc] 
groupby[oORDERPRIORITY; Ordercount: group feed count ]
project[oORDERPRIORITY, Ordercount] 
sortby[oORDERPRIORITY asc] 
consume
\end{lstlisting}

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=},
%xtick=data,
%ylabel=Sekunden,
%scaled ticks=base 10:0,
%xticklabels={1,2,3,4},
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%%xticklabel style={rotate=-30, yshift=0.25em, xshift=1.5em},
%]
%\addplot coordinates {(0,	0.645	)(1,	0	)(2,	0	)};
%\addplot coordinates {(0,	0.002	)(1,	0.002	)(2,	0.026	)};
%\addplot coordinates {(0,	0.002	)(1,	0.002	)(2,	0.002	)};
%\addplot coordinates {(0,	5.986	)(1,	6.054	)(2,	3.093	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Abfrage Q4, detaillierte Laufzeit in Sekunden}
%\end{figure}
%\setcounter{footnote}{0}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}


\begin{figure}[h]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={,,,0.0016,0.0032,0.0064},
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
sharp plot
]
\addplot coordinates {(0.0002,	0.067	)(0.0004,	0.489	)(0.0008,	7.03	)(0.0016,	25.483	)(0.0032,	98.154	)(0.0064,	383.557	)};
\addplot coordinates {(0.0002,	0.058	)(0.0004,	0.076	)(0.0008,	6.277	)(0.0016,	24.222	)(0.0032,	95.008	)(0.0064,	382.824	)};
\addplot coordinates {(0.0002,	0.504	)(0.0004,	0.684	)(0.0008,	3.313	)(0.0016,	88.478	)(0.0032,	354.426	)(0.0064,	1442.454 )};
%\addplot coordinates {(0.0002,	0.434	)(0.0004,	0.643	)(0.0008,	3.297	)(0.0016,	88.188	)(0.0032,	353.111	)(0.0064,	1439.432 )};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q4 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q4 line}
\end{figure}

\subsection{TPC-D Q7}
Diese Abfrage listet für zwei gewählte Länder den Wert der versandten Waren. Es wird der Wert der Waren, die zwischen Lieferanten und Kunden länderübergreifend versandt wurden, ausgegeben und nach Land des Lieferanten, Land des Kunden und Jahr gruppiert. Als Werte für die Parameter NATION1 und NATION2 wurden die Werte aus der Abfrageüberprüfung, NATION1 = \enquote{FRANCE} und NATION2 = \enquote{GERMANY} ausgewählt.

\begin{lstlisting}[caption=Abfrage Q7]
select [supp_nation, cust_nation, lyear, sum(volume) as revenue]
from ( 
	select 
		[n1:nname as supp_nation,
		 n2:nname as cust_nation,
		 year_of(lshipdate) as lyear,
		 lextendedprice * (1 - ldiscount) as volume]
	from
		[supplier, lineitem, orders, 
		customer,	nation as n1, nation as n2]
	where
		[ssuppkey = lsuppkey,
		oorderkey = lorderkey,
		ccustkey = ocustkey,
		snationkey = n1:nnationkey,
		cnationkey = n2:nnationkey,
		(n1:nname = "FRANCE" and n2:nname = "GERMANY")
		or 
		(n1:nname = "GERMANY" and n2:nname = "FRANCE"),
		between(instant2real(lshipdate), 
			instant2real(instant("1995-01-01")), 
			instant2real(instant("1996-12-31"))
		)]
	) as shipping
groupby	[supp_nation, cust_nation, lyear]
orderby	[supp_nation, cust_nation, lyear]
\end{lstlisting}

Da es sich um eine Abfrage mit einer geschachtelten \sql{from}-Klausel handelt, muss diese im ersten Schritt durch ihre Auswertung in Form einer temporären Relation ersetzt werden. Die definierende Abfrage der \sql{from}-Klausel ist eine flache Abfrage. Daher müssen keine weiteren Entschachtelungsalgorithmen angewandt werden.

\begin{lstlisting}[caption=Abfrage Q7{,} Definition trelxx1]
trelxx1 = select 
	[n1:nname as supp_nation, 
	n2:nname as cust_nation, 
	year_of(lshipdate)as lyear, 
	lextendedprice* (1-ldiscount)as volume]
from 
	[supplier, lineitem, orders, 
	customer, nation as n1, nation as n2]
where 
	[ssuppkey = lsuppkey, 
	oorderkey = lorderkey, 
	ccustkey = ocustkey, 
	snationkey = n1:nnationkey, 
	cnationkey = n2:, 
	(n1:nname = "FRANCE" and n2:nname = "GERMANY")
	or 
	(n1:nname = "GERMANY" and n2:nname = "FRANCE"), 
	between(instant2real(lshipdate), 
		instant2real(instant("1995-01-01")), 
		instant2real(instant("1996-12-31"))
	)]
\end{lstlisting}

Die entschachtelte Version von Abfrage Q7 stellt nur noch eine einfache Aggregationsberechnung über der neuen temporären Relation dar.
\begin{lstlisting}[caption=Abfrage Q7 in SQL-Syntax{,} entschachtelt]
select 
	[supp_nation, cust_nation, 
	lyear, sum(volume)as revenue]
from trelxx1 
groupby [supp_nation, cust_nation, lyear]
orderby [supp_nation, cust_nation, lyear]
\end{lstlisting}

Damit ist auch die Übersetzung der entschachtelten Version trivial.

\begin{lstlisting}[caption=Abfrage Q7 in ausführbarer Syntax{,} entschachtelt]
trelxx1 feed 
sortby[Supp_nation asc, Cust_nation asc, Lyear asc] 
groupby[Supp_nation, Cust_nation, Lyear; Revenue: group feed sum[Volume] ]
project[Supp_nation, Cust_nation, Lyear, Revenue] 
sortby[Supp_nation asc, Cust_nation asc, Lyear asc] 
consume
\end{lstlisting}

Die Übersetzung der Abfrage erfolgt wie in Abschnitt \ref{ssct:from-Klausel} beschrieben. Die innere Abfrage wird in einen Strom übersetzt, auf welchen dann Selektion und Projektion der äußeren Abfrage angewandt werden. Wie man sehen kann, stimmen die entschachtelte Variante und die iterative Übersetzung ab dem Ausdruck \secondo{sortby[Supp\_nation asc, Cust\_nation asc, Lyear asc]} vollkommen überein.

\begin{lstlisting}[caption=Abfrage Q7 in ausführbarer Syntax{,} geschachtelt]
CUSTOMER feedproject[cCUSTKEY, cNATIONKEY] 
SUPPLIER feedproject[sNATIONKEY, sSUPPKEY] 
NATION feedproject[nNAME, nNATIONKEY] {n1} 
sortmergejoin[sNATIONKEY , nNATIONKEY_n1] {0.004995, 0.505} 
NATION feedproject[nNAME, nNATIONKEY] {n2} 
symmjoin[(
	((.nNAME_n1 = "FRANCE") and (..nNAME_n2 = "GERMANY")) 
	or 
	((.nNAME_n1 = "GERMANY") and (..nNAME_n2 = "FRANCE"))
)] {0.0015984, 0.1696}
symmjoin[(.cNATIONKEY = ..nNATIONKEY_n2)] {0.001665, 0.0336667} 
ORDERS feedproject[oCUSTKEY, oORDERKEY] 
symmjoin[(.cCUSTKEY = ..oCUSTKEY)] {0.001998, 0.00526667} 
LINEITEM feedproject[lDISCOUNT, lEXTENDEDPRICE, lORDERKEY, lSHIPDATE, lSUPPKEY] 
symmjoin[(.oORDERKEY = ..lORDERKEY)] {3.996e-06, 0.00042} 
filter[(.sSUPPKEY = .lSUPPKEY)] {0.001998, 0.026} 
filter[
	instant2real(.lSHIPDATE) 
	between[instant2real(instant("1995-01-01")) , instant2real(instant("1996-12-31"))] 
] {0.0004995, 0.0505} 
extend[
	Supp_nation: .nNAME_n1, Cust_nation: .nNAME_n2, Lyear: year_of(.lSHIPDATE), 
	Volume: (.lEXTENDEDPRICE * (1 - .lDISCOUNT)
)]
project[Supp_nation, Cust_nation, Lyear, Volume] 
sortby[Supp_nation asc, Cust_nation asc, Lyear asc] 
groupby[Supp_nation, Cust_nation, Lyear; Revenue: group feed sum[Volume] ]
project[Supp_nation, Cust_nation, Lyear, Revenue] 
sortby[Supp_nation asc, Cust_nation asc, Lyear asc] 
consume
\end{lstlisting}

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=},
%xtick=data,
%ylabel=Sekunden,
%scaled ticks=base 10:0,
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%xticklabels={1,2,3,4},
%xticklabel style={rotate=-30, yshift=0.25em, xshift=1.5em},
%]
%\addplot coordinates {(0,	962	)(1,	1	)(2,	1	)};
%\addplot coordinates {(0,	0	)(1,	0	)(2,	7	)};
%\addplot coordinates {(0,	0	)(1,	0	)(2,	279	)};
%\addplot coordinates {(0,	103	)(1,	100	)(2,	495	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Laufzeit der einzelnen Phasen von Abfrage Q7}
%\end{figure}
%\setcounter{footnote}{0}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}

\begin{figure}[h]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={,,,,0.0016,0.0032,0.0064,0.0128},
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
sharp plot
]
\addplot coordinates {(0.0001,	0.608	)(0.0002,	0.101	)(0.0004,	2.292	)(0.0008,	0.622	)(0.0016,	6.499	)(0.0032,	1.826	)(0.0064,	134.078	)(0.0128,	1896.151	)};
\addplot coordinates {(0.0001,	0.225	)(0.0002,	0.08	)(0.0004,	1.79	)(0.0008,	0.204	)(0.0016,	0.245	)(0.0032,	0.257	)(0.0064,	0.285	)(0.0128,	0.445	)};
\addplot coordinates {(0.0001,	0.453	)(0.0002,	2.369	)(0.0004,	1.07	)(0.0008,	0.497	)(0.0016,	6.447	)(0.0032,	1.52	)(0.0064,	133.863	)(0.0128,	1894.486	)};
%\addplot coordinates {(0.0001,	0.445	)(0.0002,	2.269	)(0.0004,	1.064	)(0.0008,	0.508	)(0.0016,	6.364	)(0.0032,	1.543	)(0.0064,	133.109	)(0.0128,	1892.116	)};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}% kalt, iterativ warm}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q7 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q7 line}
\end{figure}

Wie man an der Entwicklung der Laufzeiten in Abbildung \ref{plot:Q7 line} sehen kann, ergeben sich durch die Entschachtelung bei einmaliger Ausführung weder Vor- noch Nachteile. Dies ist auch nicht anders zu erwarten, da sich die beiden Ausführungsstrategien nur hinsichtlich der Persistenz des Stroms der inneren Abfrage unterscheiden. Bei mehrfacher Ausführung ist die entschachtelte Ausführung klar überlegen, da hierbei die Auswertung der inneren Abfrage komplett entfallen kann.


\subsection{TPC-D Q9}
Ermittelt den Gewinn, der mit bestimmten Teilen gemacht wurde, gruppiert nach Land und Jahr. Gewinn ist hier definiert als rabattierter Verkaufspreis - Einkaufspreis * Anzahl. Für die Parameter COLOR, DATE und NATION wurden die Werte aus der Abfrageüberprüfung des Benchmarks, COLOR = forest, DATE = 01.01.1994 und NATION = \enquote{CANADA}, gewählt.

\begin{lstlisting}[caption=Abfrage Q9]
select [nation, oyear, sum(amount) as sumprofit]
from (
	select
		[nname as nation,
		 year_of(oorderdate) as oyear,
		 lextendedprice * (1 - ldiscount) - pssupplycost * lquantity as amount]
	from
		[part, supplier,
		 lineitem, partsupp,
		 orders, nation]
	where
		[ssuppkey = lsuppkey,
		 pssuppkey = lsuppkey,
		 pspartkey = lpartkey,
		 ppartkey = lpartkey,
		 oorderkey = lorderkey,
		 snationkey = nnationkey,
		 pname contains "green"]
	) as profit
groupby	[nation, oyear]
orderby [nation, oyear desc]
\end{lstlisting}

Die Abfrage enthält eine Unterabfrage in der \sql{from}-Klausel. Daher muss diese durch eine temporäre Relation ersetzt werden. Diese ergibt sich aus der Auswertung der Unterabfrage. Da die innere Abfrage flach ist, d.h. keine Unterabfragen enthält, müssen keine weiteren Entschachtelungsalgorithmen angewandt werden.

\begin{lstlisting}[caption=Abfrage Q9{,} Definition trelxx1]
select 
	[nname as nation, 
	year_of(oorderdate)as oyear, 
	lextendedprice * (1 - ldiscount) - pssupplycost * lquantity as amount]
from 
	[part, supplier, lineitem, 
	partsupp, orders, nation]
where 
	[ssuppkey = lsuppkey, 
	pssuppkey = lsuppkey, 
	pspartkey = lpartkey, 
	ppartkey = lpartkey, 
	oorderkey = lorderkey, 
	snationkey = nnationkey, 
	pname contains "green"]
\end{lstlisting}

Die entschachtelte Version ist eine einfache Abfrage, ohne weitere Prädikate.

\begin{lstlisting}[caption=Abfrage Q9 in SQL-Syntax{,} entschachtelt]
select [nation, oyear, sum(amount)as sumprofit]
from trelxx1 
groupby [nation, oyear]
orderby [nation, oyear desc]
\end{lstlisting}

Damit ist auch die Übersetzung in ausführbare Syntax trivial:

\begin{lstlisting}[caption=Abfrage Q9 in ausführbarer Syntax{,} entschachtelt]
trelxx1 feed 
sortby[Nation asc, Oyear asc] 
groupby[Nation, Oyear; Sumprofit: group feed sum[Amount] ]
project[Nation, Oyear, Sumprofit] 
sortby[Nation asc, Oyear desc] 
consume
\end{lstlisting}.

Die iterative Übersetzung der Abfrage ergibt folgenden Ausdruck in ausführbarer Syntax:

\begin{lstlisting}[caption=Abfrage Q9 in ausführbarer Syntax{,} geschachtelt]
ORDERS feedproject[oORDERDATE, oORDERKEY] 
PARTSUPP feedproject[psPARTKEY, psSUPPKEY, psSUPPLYCOST] 
PART feedproject[pNAME, pPARTKEY] 
SUPPLIER feedproject[sNATIONKEY, sSUPPKEY] 
NATION feedproject[nNAME, nNATIONKEY] 
sortmergejoin[sNATIONKEY , nNATIONKEY] {0.004995, 0.495} 
LINEITEM feedproject[lDISCOUNT,lEXTENDEDPRICE,lORDERKEY,lPARTKEY,lQUANTITY,lSUPPKEY] 
symmjoin[(.sSUPPKEY = ..lSUPPKEY)] {0.001998, 0.026} 
symmjoin[(.pPARTKEY = ..lPARTKEY)] {1.24875e-05, 0.0012875} 
symmjoin[(.psPARTKEY = ..lPARTKEY)] {3.996e-06, 0.000412} 
symmjoin[(.oORDERKEY = ..lORDERKEY)] {3.996e-06, 0.00042} 
filter[(.psSUPPKEY = .lSUPPKEY)] {2.3976e-05, 0.000416} 
filter[(.pNAME contains "green")] {0.00624375, 0.6375} 
extend[
	Nation: .nNAME, Oyear: year_of(.oORDERDATE), 
	Amount: ((.lEXTENDEDPRICE * (1 - .lDISCOUNT)) - (.psSUPPLYCOST * .lQUANTITY))
] 
project[Nation, Oyear, Amount] 
sortby[Nation asc, Oyear asc] 
groupby[Nation, Oyear; Sumprofit: group feed sum[Amount]]
project[Nation, Oyear, Sumprofit] 
sortby[Nation asc, Oyear desc] 
consume
\end{lstlisting}.

Diese Übersetzung entspricht ab dem Term \secondo{sortby[Nation asc, Oyear asc]} der entschachtelten Abfrage. Der erste Teil entspricht hierbei genau der Übersetzung, die für die temporäre Abfrage erzeugt wurde.

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=},
%xtick=data,
%ylabel=Millisekunden,
%scaled ticks=base 10:0,
%xticklabels={1,2,3,4},
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%xticklabels={1,2,3,4},
%xticklabel style={rotate=-30, yshift=0.25em, xshift=1.5em},
%]
%\addplot coordinates {(0,	6154	)(1,	1	)(2,	1	)};
%\addplot coordinates {(0,	0	)(1,	0	)(2,	3	)};
%\addplot coordinates {(0,	0	)(1,	1	)(2,	231	)};
%\addplot coordinates {(0,	112	)(1,	114	)(2,	5515	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Laufzeit der einzelnen Phasen von Abfrage Q9}
%\end{figure}
%\setcounter{footnote}{0}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}

\begin{figure}[h]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={0{,}0008,0{,}0016,0{,}0032,0{,}0064},
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
sharp plot
]
\addplot coordinates {(0.0008,	0.856	)(0.0016,	445.54	)(0.0032,	1776.867	)(0.0064,	7127.544	)};
\addplot coordinates {(0.0008,	0.227	)(0.0016,	0.237	)(0.0032,	0.284	)(0.0064,	0.313	)};
\addplot coordinates {(0.0008,	111.962	)(0.0016,	443.399	)(0.0032,	1773.326	)(0.0064,	7148.13	)};
%\addplot coordinates {(0.0008,	111.574	)(0.0016,	446.848	)(0.0032,	1777.87	)(0.0064,	7055.378	)};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}% kalt, iterativ warm}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q9 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q9 line}
\end{figure}

Auch bei dieser Abfrage zeigt sich der Vorteil der Entschachtelung erst bei mehrmaliger Ausführung. Wie man Abbildung \ref{plot:Q9 line} entnehmen kann, unterscheidet sich die Laufzeit für die entschachtelte Variante im ersten Durchlauf nicht von der iterativen Ausführung.

\subsection{TPC-D Q15}
Diese Abfrage ermittelt den Top-Lieferanten. Es wird der Lieferant ermittelt, der das meiste zum Umsatz im gewählten Quartal beigetragen hat, gibt es mehrere, so werden sie nach Lieferantennummer geordnet angezeigt. 

\begin{lstlisting}[caption=Abfrage Q15] 
select
	[ssuppkey, sname, saddress, 
	sphone, total_revenue]
from [supplier, revenue]
where
	[ssuppkey = supplier_no,
	total_revenue = (select max(total_revenue) from revenue)]
orderby [ssuppkey]
\end{lstlisting}


Die Abfrage ist im Benchmark über einem View definiert. Da \textsc{Secondo} keine Views unterstützt, wird hierfür eine temporäre Tabelle angelegt.

\begin{lstlisting}[caption=Abfrage Q15{,} Definition von revenue]
select
	[lsuppkey as supplier_no, 
	sum(lextendedprice* (1-ldiscount))as total_revenue]
from 
	lineitem 
where
	[lshipdate>=instant("1996-01-01"), 
	lshipdate<theInstant(
		year_of(instant("1996-01-01")), 
		month_of(instant("1996-01-01"))+3, 
		day_of(instant("1996-01-01"))
	)]
groupby	[lsuppkey]
\end{lstlisting}

Die Abfrage ist vom Typ A, da es sich bei der Unterabfrage um eine Aggregationsberechnung handelt. Es sind keine korrelierten Prädikate vorhanden, die Transformation erfolgt daher durch Auswertung der Unterabfrage. 

\begin{lstlisting}[caption=Abfrage Q15 in SQL-Syntax{,} entschachtelt]
select
	[ssuppkey, 
	sname, 
	saddress, 
	sphone, 
	total_revenue]
from [supplier, revenue]
where
	[ssuppkey=supplier_no, 
	total_revenue=645989.2892999999]
orderby	[ssuppkey]
\end{lstlisting}

Die Übersetzung der entschachtelten Abfrage in ausführbare Syntax ist daher trivial.

\begin{lstlisting}[caption=Abfrage Q15 in ausführbarer Syntax{,} entschachtelt]
SUPPLIER feedproject[sADDRESS, sNAME, sPHONE, sSUPPKEY] 
revenue feedproject[Supplier_no, Total_revenue] 
filter[(.Total_revenue = 645989.2892999999)] {0.124875, 12.125} 
sortmergejoin[sSUPPKEY , Supplier_no] {0.124875, 1.57812} 
project[sSUPPKEY, sNAME, sADDRESS, sPHONE, Total_revenue] 
sortby[sSUPPKEY asc] 
consume
\end{lstlisting}

Bei der iterativen Übersetzung wird die Unterabfrage für jedes Tupel des Stroms erneut ausgewertet.

\begin{lstlisting}[caption=Abfrage Q15 in ausführbarer Syntax{,} geschachtelt]
SUPPLIER feedproject[sADDRESS, sNAME, sPHONE, sSUPPKEY] 
revenue feedproject[Supplier_no, Total_revenue] 
filter[
	fun (alias5: TUPLE) (
		attr(alias5, Total_revenue) 
		= 
		revenue feed {r} 
		max[Total_revenue_r] 
	)] {0.124875, 13} 
sortmergejoin[sSUPPKEY , Supplier_no] {0.124875, 1.57812} 
project[sSUPPKEY, sNAME, sADDRESS, sPHONE, Total_revenue] 
sortby[sSUPPKEY asc] 
consume
\end{lstlisting}

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=},
%xtick=data,
%ylabel=Millisekunden,
%scaled ticks=base 10:0,
%xticklabels={1,2,3,4},
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%xticklabels={1,2,3,4},
%xticklabel style={rotate=-30, yshift=0.25em, xshift=1.5em},
%]
%\addplot coordinates {(0,	62	)(1,	1	)(2,	1	)};
%\addplot coordinates {(0,	0	)(1,	0	)(2,	378	)};
%\addplot coordinates {(0,	721	)(1,	347	)(2,	3	)};
%\addplot coordinates {(0,	107	)(1,	86	)(2,	98	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Laufzeit der einzelnen Phasen von Abfrage Q15}
%\end{figure}
%\setcounter{footnote}{0}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}

\begin{figure}[h]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={,,,,0.0016,0.0032,0.0064,0.0128},
enlargelimits=0.10,
ymin=0,
legend style={at={(1.65,0.5)},
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
sharp plot
]
\addplot coordinates {(0.0008,	0.744	)(0.0016,	0.919	)(0.0032,	1.056	)(0.0064,	2.038	)(0.0128,	5.391	)(0.0256,	9.232	)(0.0512,	9.372	)(0.1024,	23.601	)};
\addplot coordinates {(0.0008,	0.566	)(0.0016,	0.722	)(0.0032,	0.924	)(0.0064,	1.247	)(0.0128,	2.302	)(0.0256,	5.901	)(0.0512,	9.223	)(0.1024,	18.387	)};
\addplot coordinates {(0.0008,	0.601	)(0.0016,	0.68	)(0.0032,	0.918	)(0.0064,	1.262	)(0.0128,	2.238	)(0.0256,	5.875	)(0.0512,	9.868	)(0.1024,	20.801	)};
%\addplot coordinates {(0.0008,	0.613	)(0.0016,	0.687	)(0.0032,	0.896	)(0.0064,	1.279	)(0.0128,	2.354	)(0.0256,	5.901	)(0.0512,	9.901	)(0.1024,	20.885	)};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}% kalt, iterativ warm}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q15 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q15 line}
\end{figure}

Die Laufzeiten der Ausführungsstrategien unterscheiden sich auch bei steigendem Skalierungsfaktor nur gering. Den größten Teil der Laufzeit nimmt die Erzeugung des Views ein. Da diese Laufzeitkosten bei beiden Ausführungsstrategien zu Buche schlagen, wurden sie hier nicht gesondert gemessen. Auch bei einer Steigerung des Skalierungsfaktors um mehrere Größenordnungen bewegen sich die Laufzeiten immer noch im zweistelligen Sekundenbereich. Die Beschränkung des Skalierungsfaktors war bei dieser Abfrage durch die Laufzeit der View-Erzeugung gegeben.

\subsection{TPC-D Q16}
Mit dieser Abfrage wird die Anzahl der Lieferanten für bestimmte Teile ermittelt. Die Teile dürfen nicht von einem bestimmten Typ sein, nicht von einer bestimmten Marke und es darf keine Kundenbeschwerden über den Lieferanten geben. Als Werte für die Parameter BRAND, TYPE, SIZE{1-8} wurden die Werte der Abfrageüberprüfung ausgewählt. (BRAND = \enquote{Brand\#45}, TYPE = \enquote{MEDIUM POLISHED}, SIZE1 = \enquote{49}, SIZE2 = \enquote{14}, SIZE3 = \enquote{23}, SIZE4 = \enquote{45}, SIZE5 = \enquote{19}, SIZE6 = \enquote{3}, SIZE7 = \enquote{36} und SIZE8 = \enquote{9})

\begin{lstlisting}[caption=Abfrage Q16]
select
	[pbrand, 
	ptype, 
	psize,
	count(distinct pssuppkey) as suppliercnt]
from [partsupp, part]
where
	[ppartkey = pspartkey,
	not(pbrand = "Brand#45"),
	not(ptype starts "MEDIUM POLISHED"),
	psize in (49, 14, 23, 45, 19, 3, 36, 9),
	pssuppkey not in(
		select 
			ssuppkey
		from 
			supplier
		where
  	[scomment contains "Customer",
			 scomment contains "Complaints"]
		)]
groupby [pbrand, ptype, psize]
orderby	
	[suppliercnt desc, 
	pbrand, ptype, psize]
\end{lstlisting}

Abfrage Q16 ist vom Typ J, da kein korreliertes Prädikat in der Unterabfrage auftritt. Da es sich bei dem Operator des geschachtelten Prädikats um den Operator \sql{not in} handelt, ist momentan keine Entschachtelung möglich. Ein Vergleich der Ausführungsstrategien für diese Abfrage ist daher nicht machbar.

\begin{lstlisting}[caption=Abfrage Q16 in ausführbarer Syntax]
PART feedproject[pBRAND, pPARTKEY, pSIZE, pTYPE] 
PARTSUPP feedproject[psPARTKEY, psSUPPKEY] 
symmjoin[(.pPARTKEY = ..psPARTKEY)] {2.4975e-05, 0.0012875} 
filter[
	fun (alias7: TUPLE) not((
		attr(alias7, psSUPPKEY) 
		in 
		SUPPLIER feedproject[sCOMMENT, sSUPPKEY] 
		filter[(.sCOMMENT contains "Complaints")] {0.124875, 12.25} 
		filter[(.sCOMMENT contains "Customer")] {0.124875, 12.75} 
		projecttransformstream[sSUPPKEY] 
		collect_set 
	))] {0.0124875, 0.175} 
filter[.pSIZE in [const set(int) value (49 14 23 45 19 3 36 9)]] {0.00624375, 0.61875} 
filter[not((.pBRAND = "Brand#45"))] {0.04995, 0.61875} 
filter[not((.pTYPE starts "MEDIUM POLISHED"))] {0.04995, 0.6625} 
sortby[pBRAND asc, pTYPE asc, pSIZE asc] 
groupby[pBRAND, pTYPE, pSIZE; 
	Suppliercnt: group feed 
	filter[not(isempty(.psSUPPKEY))] 
	project[psSUPPKEY] 
	sort 
	rdup 
	count 
]
project[pBRAND, pTYPE, pSIZE, Suppliercnt] 
sortby[Suppliercnt desc, pBRAND asc, pTYPE asc, pSIZE asc] 
consume
\end{lstlisting}

Die Übersetzung erfolgt mit einem geschachtelten \secondo{filter}-Ausdruck und den Operatoren \secondo{in} und \secondo{transformstream}. 

\subsection{TPC-D Q17}
Diese Abfrage beantwortet, wieviel Umsatz verloren ginge, falls Bestellungen über kleine Mengen bestimmter Teile nicht mehr ausgeführt würden. Als Werte für die Parameter BRAND und CONTAINER wurden die Werte der Abfrageüberprüfung, BRAND = \enquote{Brand\#23} und CONTAINER = \enquote{MED BOX}, ausgewählt.
\begin{lstlisting}[caption=Abfrage Q17]
select
	[sum(lextendedprice / 7.0) as avg_yearly]		
from
	[lineitem, part]
where
	[ppartkey = lpartkey,
	 pbrand = "Brand#23",
	 pcontainer = "MED BOX",
	 lquantity < (
		select
			avg(0.2 * l1:lquantity)
		from
			[lineitem as l1]
		where
			[l1:lpartkey = ppartkey]
	)]
groupby	[]
\end{lstlisting}

Es handelt sich um eine Abfrage vom Typ JA, da die Unterabfrage eine Aggregation berechnet. Über das Prädikate \sql{l1:lpartkey = ppartkey} wird das Attribut \sql{ppartkey} der äußeren Relation \sql{part} referenziert. Die Entschachtelung erfolgt daher mit Algorithmus \textbf{NEST-JA2} (siehe Abschnitt \ref{sct:Algorithmus NEST-JA2}).


Der erste Schritt besteht in der Projektion der äußeren Relation \sql{part} auf das im geschachtelten Prädikat verwendete Attribut \sql{ppartkey}.

\begin{lstlisting}[caption=Abfrage Q17{,} Definition von trelxx1]
trelxx1 = select distinct ppartkey from part
\end{lstlisting}

Die zweite temporäre Relation ist die Projektion der inneren Relation auf alle benötigten Attribute.

\begin{lstlisting}[caption=Abfrage Q17{,} Definition von trelxx2]
trelxx2 = 
select [l1:lpartkey, l1:lquantity] from [lineitem as l1]
\end{lstlisting}

Die Berechnung der Aggregation über den beiden temporären Relationen \sql{trelxx1} und \sql{trelxx2} erfolgt über die Ausführung des folgenden SQL-Ausdrucks.

\begin{lstlisting}[caption=Abfrage Q17{,} Definition von trelxx3]
trelxx3 =
select
	[lpartkey_l1, 
	avg(0.2*lquantity_l1)as var1]
from
	[trelxx1, 
	trelxx2]
where
	[lpartkey_l1 = ppartkey]
groupby 
	lpartkey_l1
\end{lstlisting}

Damit ergibt sich als flache Variante von Abfrage Q17 die einfache Aggregationsabfrage
\begin{lstlisting}[caption=Abfrage Q17 in SQL-Syntax{,} entschachtelt]
select
	[sum(lextendedprice/7.0)as avg_yearly]
from
	[lineitem, 
	part, 
	trelxx3 as alias1]
where
	[ppartkey = lpartkey, 
	pbrand = "Brand#23", 
	pcontainerv = "MED BOX", 
	ppartkey = alias1:lpartkey_l1, 
	lquantity < alias1:var1]
groupby []
\end{lstlisting}.

Die Übersetzung in ausführbare Syntax liefert folgenden \textsc{Secodo}-Ausdruck

\begin{lstlisting}[caption=Abfrage Q17 in ausführbarer Syntax{,} entschachtelt]
PART feedproject[pBRAND, pCONTAINER, pPARTKEY] 
trelxx3 feedproject[lPARTKEY_l1, Var1] {alias1} 
symmjoin[(.pPARTKEY = ..lPARTKEY_l1_alias1)] {3.90234e-05, 0.00453125} 
filter[(.pBRAND = "Brand#23")] {0.00624375, 0.6125} 
filter[(.pCONTAINER = "MED BOX")] {0.00624375, 0.64375} 
LINEITEM feedproject[lEXTENDEDPRICE, lPARTKEY, lQUANTITY] 
symmjoin[(.pPARTKEY = ..lPARTKEY)] {1.24875e-05, 0.0012875} 
filter[(.lQUANTITY < .Var1_alias1)] {0.00014985, 0.0013} 
groupby[; Avg_yearly: group feed 
	extend[Var1: (.lEXTENDEDPRICE / 7.0000000000)] 
	sum[Var1]
]
project[Avg_yearly] 
consume
\end{lstlisting}.

Dieser unterscheidet sich von der iterativen Übersetzung 

\begin{lstlisting}[caption=Abfrage Q17 in ausführbarer Syntax{,} geschachtelt]
PART feedproject[pBRAND, pCONTAINER, pPARTKEY] 
filter[(.pBRAND = "Brand#23")] {0.00624375, 0.6125} 
filter[(.pCONTAINER = "MED BOX")] {0.00624375, 0.64375} 
LINEITEM feedproject[lEXTENDEDPRICE, lPARTKEY, lQUANTITY] 
symmjoin[(.pPARTKEY = ..lPARTKEY)] {1.24875e-05, 0.0012875} 
filter[
	fun (alias1: TUPLE) (
		attr(alias1, lQUANTITY) 
		< 
		LINEITEM feed {l1} 
		filter[(.lPARTKEY_l1 = attr(alias1, pPARTKEY))] 
		extend[var1: (0.2000000000 * .lQUANTITY_l1)] 
		avg[var1] 
	)] {1.24875e-05, 0.00185} 
groupby[; Avg_yearly: group feed 
	extend[Var1: (.lEXTENDEDPRICE / 7.0000000000)] 
	sum[Var1] 
]
project[Avg_yearly] 
consume
\end{lstlisting}

durch den Join mit der Relation \secondo{trelxx3} über \secondo{symmjoin[(.pPARTKEY = ..lPARTKEY\_l1\_alias1)]} und die Selektion mit dem Prädikat \secondo{filter[(.lQUANTITY < .Var1\_alias1)]}. Diese ersetzen den komplexen \secondo{filter}-Ausdruck, der die triviale Übersetzung der Unterabfrage darstellt.

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=},
%xtick=data,
%ylabel=Millisekunden,
%scaled ticks=base 10:0,
%xticklabels={1,2,3,4},
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%xticklabels={1,2,3,4},
%xticklabel style={rotate=-30, yshift=0.25em, xshift=1.5em},
%]
%\addplot coordinates {(0,	5943	)(1,	1	)(2,	1	)};
%\addplot coordinates {(0,	2	)(1,	2	)(2,	190	)};
%\addplot coordinates {(0,	1085	)(1,	22	)(2,	8	)};
%\addplot coordinates {(0,	266	)(1,	264	)(2,	283	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Laufzeit der einzelnen Phasen von Abfrage Q17}
%\end{figure}
%\setcounter{footnote}{0}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}

\begin{figure}[h]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={0.0008,0.0016,0.0032,0.0064,0.0128},
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
sharp plot
]
\addplot coordinates {(0.0008,	10.945	)(0.0016,	20.15	)(0.0032,	54.489	)(0.0064,	218.186	)(0.0128,	842.648	)};
\addplot coordinates {(0.0008,	1.182	)(0.0016,	1.169	)(0.0032,	2.197	)(0.0064,	7.384	)(0.0128,	28.798	)};
\addplot coordinates {(0.0008,	1.387	)(0.0016,	1.2	)(0.0032,	0.572	)(0.0064,	0.85	)(0.0128,	68.046	)};
%\addplot coordinates {(0.0008,	1.199	)(0.0016,	1.167	)(0.0032,	0.467	)(0.0064,	0.657	)(0.0128,	67.591	)};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}% kalt, iterativ warm}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q17 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q17 line}
\end{figure}

\subsection{TPC-D Q20}
Dies Abfrage identifiziert Lieferanten, die einen Überschuss an bestimmten Teilen haben. Als Überschuss gilt ein Anteil von mehr als 50\% der von einem Lieferanten versandten Teile über ein Jahr. Nur Teile mit einem vorgegebenen Namensbestandteil werden betrachtet. Als Werte für die Parameter COLOR, DATE und NATION wurden die Werte COLOR = \enquote{forest}, DATE = 01.01.1994 und NATION = \enquote{CANADA} der Abfrageüberprüfung ausgewählt.
\begin{lstlisting}[caption=Abfrage Q20]
select [sname, saddress]
from [supplier, nation]
where
	[ssuppkey in (
		select [pssuppkey]
		from [partsupp]
		where
			[pspartkey in (
				select ppartkey
				from part
				where tostring(pname) starts "forest"
			),
			psavailqty > (
				select sum(lquantity * 0.5)
				from lineitem
				where
					[lpartkey = pspartkey,
					lsuppkey = pssuppkey,
					lshipdate >= instant("1994-01-01"),
					lshipdate < theInstant(
						year_of(instant("1994-01-01")) + 1, 
					 	month_of(instant("1994-01-01")), 
					 	day_of(instant("1994-01-01"))
					 )]
			)]
		),
	 snationkey = nnationkey,
	 nname = "CANADA"]
orderby	[sname]
\end{lstlisting}

Abfrage Q20 ist mehrfach geschachtelt, die Schachtelungstiefe beträgt 2. Das geschachtelte Prädikate ist vom Typ N, da es sich um eine Unterabfrage ohne Aggregation und ohne Referenzierung äußerer Relationen handelt. Beim ersten inneren geschachtelten Prädikat (siehe Listing \ref{lst:Q20 inner nested 1}) handelt es sich sich ebenfalls um ein Prädikat vom Typ N, es werden ebenfalls keine äußeren Relationen referenziert und die \sql{select}-Klausel enthält keine Aggregationsfunktion. Das zweite innere geschachtelte Prädikat (siehe Listing \ref{lst:Q20 inner nested 2}) ist vom Type JA, da in der Unterabfrage eine Summe berechnet wird und die Relation \sql{partsupp} des direkt umschließenden Abfrageblocks referenziert wird.

\begin{lstlisting}[caption=Abfrage Q20{,} erstes inneres geschachteltes Prädikat,label=lst:Q20 inner nested 1]
pspartkey in (
	select ppartkey
	from part
	where tostring(pname) starts "forest"
)
\end{lstlisting}

Im ersten Schritt wird also Algorithmus \textbf{NEST-N-J} auf das innere Prädikat mit dem \sql{in}-Operator angewandt. Das Ergebnis ist 

\begin{lstlisting}[caption=Abfrage Q20{,} nach Algorithmus NEST-N-J]
select [sname, saddress]
from [supplier, nation]
where
	[ssuppkey in (
		select [pssuppkey]
		from [partsupp,part]
		where
			[pspartkey = ppartkey,
			tostring(pname) starts "forest",
			psavailqty > (
				select sum(lquantity * 0.5)
				from lineitem
				where
					[lpartkey = pspartkey,
					lsuppkey = pssuppkey,
					lshipdate >= instant("1994-01-01"),
					lshipdate < theInstant(
						year_of(instant("1994-01-01")) + 1, 
					 	month_of(instant("1994-01-01")), 
					 	day_of(instant("1994-01-01"))
					 )]
			)]
		),
	 snationkey = nnationkey,
	 nname = "CANADA"]
orderby	[sname]
\end{lstlisting}.

Im nächsten Schritt wird das verbleibende innere geschachtelte Prädikat mit Algorithmus \textbf{NEST-JA2} in eine kanonische Form überführt. Hierfür wird im ersten Schritt die temporäre Relation \sql{trelxx1} erzeugt, die die Einschränkung der äußeren Relation \sql{partsupp} auf alle benötigten Attribute darstellt (Listing \ref{lst:Q20 trelxx1}).

\begin{lstlisting}[caption=Abfrage Q20{,} zweites inneres geschachteltes Prädikat,label=lst:Q20 inner nested 2]
psavailqty > (
select sum(lquantity * 0.5)
from lineitem
where
	[lpartkey = pspartkey,
	lsuppkey = pssuppkey,
	lshipdate >= instant("1994-01-01"),
	lshipdate < theInstant(
		year_of(instant("1994-01-01")) + 1, 
	 	month_of(instant("1994-01-01")), 
	 	day_of(instant("1994-01-01"))
	 )]
)
\end{lstlisting}

\begin{lstlisting}[caption=Abfrage Q20{,} Definition trelxx1,label=lst:Q20 trelxx1]
trelxx1 = select distinct [pspartkey, pssuppkey] from partsupp
\end{lstlisting}

Zusammen mit Relation \sql{trelxx2}, die die Projektion der inneren Relation auf alle benötigten Attribute ist, bildet sie die Grundlage für Relation \sql{trelxx3}.

\begin{lstlisting}[caption=Abfrage Q20{,} Definition trelxx2]
trelxx2 = select [lpartkey, lquantity, lshipdate, lsuppkey] from lineitem
\end{lstlisting}

\begin{lstlisting}[caption=Abfrage Q20{,} Definition trelxx3]
trelxx3 =
select
	[lpartkey, 
	sum(lquantity*0.5)as var2]
from [trelxx1, trelxx2]
where [lpartkey = pspartkey]
groupby lpartkey
\end{lstlisting}

Mit der Einführung von Relation \sql{trelxx3} unter dem Namen \sql{alias1} und den ensprechenden Prädikaten \sql{pspartkey = alias1:lpartkey} und \sql{psavailqty > alias1:var1} ,vereinfacht sich Abfrage Q20 zu

\begin{lstlisting}[caption=Abfrage Q20{,} nach Algorithmus NEST-JA2]
select [sname, saddress]
from [supplier, nation]
where
	[ssuppkey in (
		select [pssuppkey]
		from [
			partsupp,part,
			trelxx3 as alias1]
		where
			[pspartkey = ppartkey,
			tostring(pname) starts "forest",
			psavailqty > alias1:var1,
			pspartkey = alias1:lpartkey]
			)]
		),
	 snationkey = nnationkey,
	 nname = "CANADA"]
orderby	[sname]
\end{lstlisting}.

Diese Abfrage ist vom Typ N und wird mit Algorithmus \textbf{NEST-N-J} in die entschachtelte Form

\begin{lstlisting}[caption=Abfrage Q20 in SQL-Syntax{,} entschachtelt]
select [sname, saddress]
from
	[supplier, nation, 
	partsupp, part, 
	trelxx3 as alias1]
where
	[ssuppkey = pssuppkey, 
	pspartkey = ppartkey, 
	tostring(pname) starts "forest", 
	pspartkey = alias1:lpartkey, 
	psavailqty > alias1:var1, 
	snationkey = nnationkey, 
	nname = "CANADA"]
orderby [sname]
\end{lstlisting}

überführt.

Wie man an der Übersetzung der entschachtelten Variante in ausführbare Syntax sehen kann,

\begin{lstlisting}[caption=Abfrage Q20 in ausführbarer Syntax{,} entschachtelt]
SUPPLIER feedproject[sADDRESS, sNAME, sNATIONKEY, sSUPPKEY] 
NATION feedproject[nNAME, nNATIONKEY] 
sortmergejoin[sNATIONKEY , nNATIONKEY] {0.004995, 0.495} 
filter[(.nNAME = "CANADA")] {0.03996, 4.04} 
PARTSUPP feedproject[psAVAILQTY, psPARTKEY, psSUPPKEY] 
symmjoin[(.sSUPPKEY = ..psSUPPKEY)] {0.001998, 0.02875} 
PART feedproject[pNAME, pPARTKEY] 
symmjoin[(.psPARTKEY = ..pPARTKEY)] {1.24875e-05, 0.0013125} 
trelxx3 feedproject[lPARTKEY, Var1] {alias1} 
symmjoin[(.psPARTKEY = ..lPARTKEY_alias1)] {1.24875e-05, 0.001325} 
filter[(.psAVAILQTY > .Var1_alias13)] {0.000786713, 0.0014125} 
filter[(tostring(.pNAME) starts "forest")] {0.00624375, 0.68125} 
project[sNAME, sADDRESS] 
sortby[sNAME asc] 
consume
\end{lstlisting}

unterscheidet sich diese von der iterativen Übersetzung durch das Wegfallen des komplexen, mehrfach geschachtelten \secondo{filter}-Ausdrucks.

\begin{lstlisting}[caption=Abfrage Q20 ausführbare Syntax geschachtelt]
SUPPLIER feedproject[sADDRESS, sNAME, sNATIONKEY, sSUPPKEY] 
NATION feedproject[nNAME, nNATIONKEY] 
sortmergejoin[sNATIONKEY , nNATIONKEY] {0.004995, 0.495} 
filter[(.nNAME = "CANADA")] {0.03996, 4.04} 
filter[
	fun (alias1: TUPLE) (
		attr(alias1, sSUPPKEY) 
		in 
		PARTSUPP feedproject[psAVAILQTY, psPARTKEY, psSUPPKEY] 
		filter[
			fun (alias2: TUPLE) (
				attr(alias2, psPARTKEY) 
				in 
				PART feedproject[pNAME, pPARTKEY] 
				filter[(tostring(.pNAME) starts "forest")] {0.00624375, 0.68125} 
				projecttransformstream[pPARTKEY] 
				collect_set 
			)] {0.00156094, 0.173437} 
		filter[
			fun (alias3: TUPLE) (
				attr(alias3, psAVAILQTY) 
				> 
				LINEITEM feedproject[lPARTKEY, lQUANTITY, lSHIPDATE, lSUPPKEY] 
				filter[(.lSHIPDATE >= instant("1994-01-01"))] {0.002997, 0.0525} 
				filter[(.lSHIPDATE < theInstant((
					year_of(instant("1994-01-01")) + 1), 
					month_of(instant("1994-01-01")), 
					day_of(instant("1994-01-01")))
				)] {0.0024975, 0.0555} 
				filter[(.lPARTKEY = attr(alias3, psPARTKEY))] 
				filter[(.lSUPPKEY = attr(alias3, psSUPPKEY))] 
				extend[var1: (.lQUANTITY * 0.5000000000)] 
				sum[var1] 
			)] {0.0124875, 0.184375} 
		projecttransformstream[psSUPPKEY] 
		collect_set 
	)] {0.124875, 19.5} 
project[sNAME, sADDRESS] 
sortby[sNAME asc] 
consume
\end{lstlisting}

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=},
%xtick=data,
%ylabel=Millisekunden,
%scaled ticks=base 10:0,
%xticklabels={1,2,3,4},
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%xticklabels={1,2,3,4},
%xticklabel style={rotate=-30, yshift=0.25em, xshift=1.5em},
%]
%\addplot coordinates {(0,	19534	)(1,	1	)(2,	4	)};
%\addplot coordinates {(0,	2	)(1,	0	)(2,	1784	)};
%\addplot coordinates {(0,	1297	)(1,	150	)(2,	8	)};
%\addplot coordinates {(0,	228	)(1,	216	)(2,	366	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Laufzeit der einzelnen Phasen von Abfrage Q20}
%\end{figure}
%\setcounter{footnote}{0}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}


\begin{figure}[h]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={,,,,0.0016,0.0032,0.0064,0.0128},
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
sharp plot
]
\addplot coordinates {(0.0008,	12.294	)(0.0016,	50.163	)(0.0032,	200.383	)(0.0064,	811.211	)(0.0128,	3239.196	)};
\addplot coordinates {(0.0008,	0.348	)(0.0016,	0.594	)(0.0032,	1.289	)(0.0064,	1.433	)(0.0128,	5.977	)};
\addplot coordinates {(0.0008,	0.326	)(0.0016,	8.267	)(0.0032,	59.713	)(0.0064,	266.071	)(0.0128,	1665.556	)};
%\addplot coordinates {(0.0008,	0.283	)(0.0016,	8.329	)(0.0032,	60.031	)(0.0064,	263.667	)(0.0128,	1684.976	)};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}% kalt, iterativ warm}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q20 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q20 line}
\end{figure}

Wie man Abbildung \ref{plot:Q20 line} entnehmen kann, ist die Entschachtelung über mehrere Ebenen jedoch so laufzeitaufwändig, dass die iterative Ausführungsstrategie bei allen verwendeten Skalierungsfaktoren der Datenbanken vorteilhafter ist. Lediglich die einfache Ausführung der entschachtelten Variante auf vorhandenen temporären Tabellen ist hier deutlich schneller.

\subsection{TPC-D Q21}
Diese Abfrage ermittelt Lieferanten die bei einer Mehr-Lieferanten-Bestellung nicht pünktlich geliefert haben. Als Wert für den Parameter NATION wurde der Wert NATION = \enquote{SAUDI ARABIA} der Abfrageüberprüfung gewählt.
\begin{lstlisting}[caption=Abfrage Q21]
select [sname, count(*) as numwait]
from 
	[supplier, lineitem as l1,
	 orders, nation]
where
	[ssuppkey = l1:lsuppkey,
	oorderkey = l1:lorderkey,
	oorderstatus = "F",
	l1:lreceiptdate > l1:lcommitdate,
	exists(
		select *
		from lineitem as l2
		where
			[l2:lorderkey = l1:lorderkey,
			not(l2:lsuppkey = l1:lsuppkey)]
	),
	not(exists(
		select *
		from lineitem as l3
		where
			[l3:lorderkey = l1:lorderkey,
			not(l3:lsuppkey = l1:lsuppkey),
			l3:lreceiptdate > l3:lcommitdate]
	)),
	snationkey = nnationkey,
	nname = "SAUDI ARABIA"]
groupby	[sname]
orderby	[numwait desc, sname] 
first 100
\end{lstlisting}

Abfrage Q21 beinhaltet zwei geschachtelte Prädikate mit \sql{exists}- bzw. \sql{not exists}-Operator. Diese werden im ersten Schritt durch ihre Darstellung mit Aggregationsabfragen ersetzt (siehe \ref{sct:Behandlung quantifizierter Prädikate}). Damit ergibt sich als erstes Zwischenergebnis

\begin{lstlisting}[caption=Abfrage Q21{,} ohne quantifizierte Prädikate]
select [sname, count(*) as numwait]
from 
	[supplier, lineitem as l1,
	 orders, nation]
where
	[ssuppkey = l1:lsuppkey,
	oorderkey = l1:lorderkey,
	oorderstatus = "F",
	l1:lreceiptdate > l1:lcommitdate,
	0 < (
		select count(*)
		from lineitem as l2
		where
			[l2:lorderkey = l1:lorderkey,
			not(l2:lsuppkey = l1:lsuppkey)]
	),
	0 = (
		select count(*)
		from lineitem as l3
		where
			[l3:lorderkey = l1:lorderkey,
			not(l3:lsuppkey = l1:lsuppkey),
			l3:lreceiptdate > l3:lcommitdate]
	)),
	snationkey = nnationkey,
	nname = "SAUDI ARABIA"]
groupby	[sname]
orderby	[numwait desc, sname] 
first 100
\end{lstlisting}

Die beiden geschachtelten Prädikate sind vom Typ JA, sie berechnen eine Aggregation und nehmen Bezug auf die Attribute \sql{l1:lorderkey} und \sql{l1:lsuppkey}. Durch die erste Ausführung wird das erste geschachtelte Prädikat mit Hilfe der Relationen \sql{trelxx1, trelxx2} und \sql{trelxx3} entschachtelt.

Relation \sql{trelxx1} ist die Einschränkung der äußeren Relation auf alle benötigten Attribute.
\begin{lstlisting}[caption=Abfrage Q21{,} Definition trelxx1]
trelxx1 = select distinct [l1:lorderkey, l1:lsuppkey] from lineitem as l1
\end{lstlisting}

Mit Relation \sql{trelxx2} wird die innere Relation auf alle benötigten Attribute eingeschränkt. Da in der inneren Abfrage keine \emph{einfachen} Prädikate vorkommen, findet hier keine weitere Restriktion statt.
\begin{lstlisting}[caption=Abfrage Q21{,} Definition trelxx2]
select [l2:lorderkey, l2:lsuppkey] from lineitem as l2
\end{lstlisting}

Der Full-Outer-Join über den Relationen \sql{trelxx1} und \sql{trelxx2} ergibt Relation \sql{trelxx3}.
\begin{lstlisting}[caption=Abfrage Q21{,} Definition trelxx3]
trelxx3 =
trelxx1 feed 
trelxx2 feed 
smouterjoin[lORDERKEY_l1,lORDERKEY_l2] 
extend[var1: ifthenelse(isempty(.lORDERKEY_l2), 0, 1)] 
sortby[lORDERKEY_l1 asc] 
groupby[lORDERKEY_l1;Var1: group feed sum[var1]] 
projectextend[Var1; lORDERKEY_l2: .lORDERKEY_l1] 
consume
\end{lstlisting}

Damit kann das erste geschachtelte Prädikat entschachtelt werden und es ergibt sich folgendes Zwischenergebnis
\begin{lstlisting}[caption=Abfrage Q21 in SQL-Syntax{,} entschachtelt]
select [sname, count(*)as numwait]
from
	[supplier, lineitem as l1, 
	orders, nation, 
	trelxx3 as alias1]
where
	[ssuppkey = l1:lsuppkey, 
	oorderkey = l1:lorderkey, 
	oorderstatus="F", 
	l1:lreceiptdate > l1:lcommitdate, 
	l1:lorderkey = alias1:lorderkey_l2, 
	0 < alias1:var1, 
	0 = (
		select count(*)
		from lineitem as l3
		where
			[l3:lorderkey = l1:lorderkey,
			not(l3:lsuppkey = l1:lsuppkey),
			l3:lreceiptdate > l3:lcommitdate]
	)),	snationkey = nnationkey, 
	nname = "SAUDI ARABIA"]
groupby	[sname]
orderby [numwait desc, sname]
first 100
\end{lstlisting}.

Diese Abfrage besitzt nur noch ein geschachteltes Prädikat und kann durch Algorithmus \textbf{NEST-JA2} vollständig entschachtelt werden. Da die verwendeten Attribute der Relation \sql{lineitem as l1} mit den verwendeten Attributen des bereits entschachtelten Prädikats übereinstimmen, kann die temporäre Relation \sql{trelxx1} hier wiederverwendet werden.

Lediglich die Selektion und Projektion der inneren Relation des Prädikats ist neu zu erstellen.
\begin{lstlisting}[caption=Abfrage Q21{,} Definition trelxx4]
select [l3:lorderkey, l3:lsuppkey]
from [lineitem as l3]
where [l3:lreceiptdate > l3:lcommitdate]
\end{lstlisting}

Die Auflösung des geschachtelten Prädikats erfolgt mit Relation \sql{trelxx5}. Diese ist der Full-Outer-Join über den Relationen \sql{trelxx1} und \sql{trelxx4}.
\begin{lstlisting}[caption=Abfrage Q21{,} Definition trelxx5]
trelxx5 = 
trelxx1 feed 
trelxx4 feed 
smouterjoin[lORDERKEY_l1,lORDERKEY_l3] 
extend[var1: ifthenelse(isempty(.lORDERKEY_l3), 0, 1)] 
sortby[lORDERKEY_l1 asc] 
groupby[lORDERKEY_l1;Var1: group feed sum[var1]] 
projectextend[Var1; lORDERKEY_l3: .lORDERKEY_l1] 
consume
\end{lstlisting}

Damit ergibt sich die entschachtelte Variante von Q21 als

\begin{lstlisting}[caption=Abfrage Q21 in SQL-Syntax{,} entschachtelt]
select [sname, count(*)as numwait]
from
	[supplier, lineitem as l1, 
	orders, nation, 
	trelxx3 as alias1, 
	trelxx5 as alias2]
where
	[ssuppkey = l1:lsuppkey, 
	oorderkey = l1:lorderkey, 
	oorderstatus="F", 
	l1:lreceiptdate > l1:lcommitdate, 
	l1:lorderkey = alias1:lorderkey_l2, 
	0 < alias1:var1, 
	l1:lorderkey = alias2:lorderkey_l3, 
	0 = alias2:var2, 
	snationkey = nnationkey, 
	nname = "SAUDI ARABIA"]
groupby	[sname]
orderby [numwait desc, sname]
first 100
\end{lstlisting}.

Die Übersetzung in ausführbare Syntax 

\begin{lstlisting}[caption=Abfrage Q21 in ausführbarer Syntax{,} entschachtelt]
ORDERS feedproject[oORDERKEY, oORDERSTATUS] 
SUPPLIER feedproject[sNAME, sNATIONKEY, sSUPPKEY] 
NATION feedproject[nNAME, nNATIONKEY] 
sortmergejoin[sNATIONKEY , nNATIONKEY] {0.004995, 0.495} 
filter[(.nNAME = "SAUDI ARABIA")] {0.03996, 4.2} 
LINEITEM feedproject[lCOMMITDATE, lORDERKEY, lRECEIPTDATE, lSUPPKEY] {l1} 
symmjoin[(.sSUPPKEY = ..lSUPPKEY_l1)] {0.001998, 0.04175} 
trelxx3 feedproject[lORDERKEY_l3, Var1] {alias1} 
symmjoin[(.lORDERKEY_l1 = ..lORDERKEY_l3_alias1)] {3.996e-06, 0.000448} 
symmjoin[(.oORDERKEY = ..lORDERKEY_l1)] {3.996e-06, 0.00048} 
trelxx5 feedproject[lORDERKEY_l2, Var2] {alias2} 
symmjoin[(.lORDERKEY_l1 = ..lORDERKEY_l2_alias2)] {3.996e-06, 0.000496} 
filter[(.lRECEIPTDATE_l1 > .lCOMMITDATE_l1)] {0.0034965, 0.059} 
filter[(.oORDERSTATUS = "F")] {0.00333, 0.0833333} 
filter[(0 = .Var1_alias1)] {0.000835983, 0.0878661} 
filter[(0 < .Var2_alias2)] {0.00668787, 0.0979079} 
sortby[sNAME asc] 
groupby[sNAME; Numwait: group feed count ]
project[sNAME, Numwait] 
sortby[Numwait desc, sNAME asc] 
head[100] 
consume
\end{lstlisting}

unterscheidet sich von der iterativen Übersetzung durch die fehlenden, komplexen \secondo{filter}-Ausdrücke. An ihrer Stelle finden sich der Join mit den Relationen \secondo{trelxx3} und \secondo{trelxx5} sowie die zugehörigen \secondo{filter}-Ausdrücke.

\begin{lstlisting}[caption=Abfrage Q21 in ausführbarer Syntax{,} geschachtelt]
ORDERS feedproject[oORDERKEY, oORDERSTATUS] 
SUPPLIER feedproject[sNAME, sNATIONKEY, sSUPPKEY] 
NATION feedproject[nNAME, nNATIONKEY] 
sortmergejoin[sNATIONKEY , nNATIONKEY] {0.004995, 0.495} 
filter[(.nNAME = "SAUDI ARABIA")] {0.03996, 4.2} 
LINEITEM feedproject[lCOMMITDATE, lORDERKEY, lRECEIPTDATE, lSUPPKEY] {l1} 
symmjoin[(.sSUPPKEY = ..lSUPPKEY_l1)] {0.001998, 0.04175} 
symmjoin[(.oORDERKEY = ..lORDERKEY_l1)] {3.996e-06, 0.00048} 
filter[(.lRECEIPTDATE_l1 > .lCOMMITDATE_l1)] {0.0034965, 0.059} 
filter[
	fun (alias1: TUPLE) (
		0 
		< 
		LINEITEM feed {l2} 
		filter[(.lORDERKEY_l2 = attr(alias1, lORDERKEY_l1))] 
		filter[not((.lSUPPKEY_l2 = attr(alias1, lSUPPKEY_l1)))] 
		count 
	)] {0.0004995, 0.0645} 
filter[
	fun (alias2: TUPLE) (
		0 
		= 
		LINEITEM feedproject[lCOMMITDATE, lORDERKEY, lRECEIPTDATE, lSUPPKEY] {l3} 
		filter[(.lRECEIPTDATE_l3 > .lCOMMITDATE_l3)] {0.0034965, 0.059} 
		filter[(.lORDERKEY_l3 = attr(alias2, lORDERKEY_l1))] 
		filter[not((.lSUPPKEY_l3 = attr(alias2, lSUPPKEY_l1)))] 
		count 
	)] {0.003996, 0.061} 
filter[(.oORDERSTATUS = "F")] {0.00333, 0.0833333} 
sortby[sNAME asc] 
groupby[sNAME; Numwait: group feed count ]
project[sNAME, Numwait] 
sortby[Numwait desc, sNAME asc] 
head[100] 
consume
\end{lstlisting}

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=},
%xtick=data,
%ylabel=Millisekunden,
%scaled ticks=base 10:0,
%xticklabels={A kalt,A warm,B kalt,B warm},
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%]
%\addplot coordinates {(0,	2662	)(1,	1	)(2,	2	)};
%\addplot coordinates {(0,	2	)(1,	2	)(2,	358	)};
%\addplot coordinates {(0,	3858	)(1,	1730	)(2,	421	)};
%\addplot coordinates {(0,	478	)(1,	475	)(2,	451	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Laufzeit der einzelnen Phasen von Abfrage Q21}
%\end{figure}
%\setcounter{footnote}{0}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}

\begin{figure}
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={,,,,0.0016,0.0032,0.0064,0.0128},
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
sharp plot
]
\addplot coordinates {(0.0008,	3.752	)(0.0016,	5.822	)(0.0032,	7.092	)(0.0064,	11.843	)(0.0128,	81.745	)};
\addplot coordinates {(0.0008,	1.601	)(0.0016,	1.594	)(0.0032,	1.882	)(0.0064,	2.142	)(0.0128,	62.853	)};
\addplot coordinates {(0.0008,	0.747	)(0.0016,	0.926	)(0.0032,	0.952	)(0.0064,	1.393	)(0.0128,	957.265	)};
%\addplot coordinates {(0.0008,	0.686	)(0.0016,	0.8	)(0.0032,	0.996	)(0.0064,	1.32	)(0.0128,	960.547	)};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}% kalt, iterativ warm}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q21 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q21 line}
\end{figure}

Die Ausführungszeiten lassen nur begrenzt Rückschlüsse auf die Vorteilhaftigkeit einer Ausführungstrategie zu. Zwar ist die entschachtelte Ausführung bei Skalierungsfaktor 0,0128 sowohl bei der ersten Ausführung als auch bei weiteren Ausführungen um eine Größenordnung schneller. Da sich die Ausführungszeiten bei kleineren Skalierungsfaktoren umgekehrt verhalten, lässt sich daraus noch keine Aussage über Vorteilhaftigkeit der entschachtelten Ausführung bei steigenden Skalierungsfaktoren ableiten.

\subsection{TPC-D Q22}
Diese Abfrage ermittelt, wieviele Kunden in den letzten 7 Jahren keine Bestellung getätigt haben, aber dennoch einen überdurchschnittlichen Umsatz auf ihrem Konto haben. Gruppiert wird nach \enquote{Länderschlüssel}, wobei Länderschlüssel als die ersten zwei Ziffern der Telefonnummer definiert ist. Als Werte für die Parameter I1, I2, I3, I4, I5, I6, I7 und I8 wurden wieder die Werte aus der Abfrageüberprüfung des Benchmark ausgewählt. (I1 = 13,
I2 = 35, I3 = 31, I4 = 23, I5 = 29, I6 = 30, I7 = 18, I8 = 17).
\begin{lstlisting}[caption=Abfrage Q22]
select
	[cntrycode,
	 count(*) as numcust,
	 sum(cacctbal) as totacctbal]
from (
	select
		[substr(cphone, 1, 2) as cntrycode, 
		cacctbal]
	from customer 
	where
		[substr(cphone, 1, 2) in ("13","35","31","23","29","30","18"),
		cacctbal > (
			select avg(c1:cacctbal)
			from customer as c1
			where
				[c1:cacctbal > 0.00,
				substr(c1:cphone, 1, 2) in ("13","35","31","23","29","30","18")]
		),
		not( exists(
			select *
			from orders
			where	ocustkey = ccustkey
		))]
	) as custsale
groupby	[cntrycode]
orderby	[cntrycode]
\end{lstlisting}

Die Abfrage hat eine geschachtelte \sql{from}-Klausel, die wiederum geschachtelte Prädikate enthält. Um die \sql{from}-Klausel in eine temporäre Relation zu übersetzen, wird ihre definierende Abfrage mit Algorithmus \textbf{NEST-G} in eine flache Form überführt. Da es sich bei dem zweiten geschachtelten Prädikat um ein quantifiziertes Prädikat handelt, wird dieses im ersten Schritt durch eine äquivalente Formulierung als Aggregationsabfrage ersetzt.

\begin{lstlisting}[caption=Abfrage Q22{,} nach Verarbeitung des quantifizierten Prädikats]
select
	[cntrycode,
	 count(*) as numcust,
	 sum(cacctbal) as totacctbal]
from (
	select
		[substr(cphone, 1, 2) as cntrycode, 
		cacctbal]
	from customer 
	where
		[substr(cphone, 1, 2) in ("13","35","31","23","29","30","18"),
		cacctbal > (
			select avg(c1:cacctbal)
			from customer as c1
			where
				[c1:cacctbal > 0.00,
				substr(c1:cphone, 1, 2) in ("13","35","31","23","29","30","18")]
		),
		0 = (
			select count(*)
			from orders
			where	ocustkey = ccustkey
		)]
	) as custsale
groupby	[cntrycode]
orderby	[cntrycode]
\end{lstlisting}

Im nächsten Schritt wird das erste geschachtelte Prädikat, welches vom Typ A ist, aufgelöst, d.h. die Unterabfrage wird durch ihr Ergebnis ersetzt.

\begin{lstlisting}[caption=Abfrage Q22{,} nach Auswertung der ersten Unterabfrage]
select
	[cntrycode,
	 count(*) as numcust,
	 sum(cacctbal) as totacctbal]
from (
	select
		[substr(cphone, 1, 2) as cntrycode, 
		cacctbal]
	from customer 
	where
		[substr(cphone, 1, 2) in ("13","35","31","23","29","30","18"),
		cacctbal > 4022.0983333333]
		),
		not( exists(
			select *
			from orders
			where	ocustkey = ccustkey
		))]
	) as custsale
groupby	[cntrycode]
orderby	[cntrycode]
\end{lstlisting}

Das verbleibende geschachtelte Prädikat ist vom Typ JA und kann mit Algorithmus \textbf{NEST-JA2} entschachtelt werden. Hierfür wird die Projektion der äußeren Abfrage auf alle in der Unterabfrage verwendeten Attribute als temporäre Relation erzeugt.

\begin{lstlisting}[caption=Abfrage Q22{,} Definition trelxx1]
trelxx1 = select distinct [ccustkey] from customer
\end{lstlisting}

Da die Unterabfrage nur das korrelierte Prädikat enthält, ist die zweite temporäre Relation die Projektion der inneren Relation \sql{orders} auf das verwendete Attribut \sql{ocustkey}.

\begin{lstlisting}[caption=Abfrage Q22{,} Definition trelxx2]
trelxx2 = select [ocustkey] from orders
\end{lstlisting}

Da die Aggregationsfunktion \sql{count} ist, wird die dritte temporäre Relation als Full-Outer-Join über den temporären Relationen \sql{trelxx1} und \sql{trelxx2} berechnet.

\begin{lstlisting}[caption=Abfrage Q22{,} Definition trelxx3]
trelxx3 = 
trelxx1 feed 
trelxx2 feed 
smouterjoin[cCUSTKEY,oCUSTKEY] 
extend[var1: ifthenelse(isempty(.oCUSTKEY), 0, 1)] 
sortby[cCUSTKEY asc] 
groupby[cCUSTKEY;Var1: group feed sum[var1]] 
projectextend[Var1; oCUSTKEY: .cCUSTKEY] 
consume
\end{lstlisting}

Als Ergebnis der Entschachtelung ergibt sich für die definierende Abfrage der \sql{from}-Klausel folgender Ausdruck:

\begin{lstlisting}[caption=Abfrage Q22{,} Definition trelxx4]
trelxx4 =
select
	[substr(cphone, 1, 2)as cntrycode, 
	cacctbal]
from [customer, trelxx3 as alias1]
where
	[substr(cphone, 1, 2) in ("13","35","31","23","29","30","18"), 
	cacctbal > 4022.0983333333, 
	ccustkey = alias1:ocustkey, 
	0 = alias1:var1]
\end{lstlisting}

Damit vereinfacht sich Abfrage Q22 zu

\begin{lstlisting}[caption=Abfrage Q22 in SQL-Syntax{,} entschachtelt]
select
	[cntrycode, 
	count(*)as numcust, 
	sum(cacctbal)as totacctbal]
from trelxx4 
groupby	[cntrycode]
orderby	[cntrycode]
\end{lstlisting}.

Die Übersetzung in ausführbare Syntax ist trivial.

\begin{lstlisting}[caption=Abfrage Q22 in ausführbarer Syntax{,} entschachtelt]
trelxx4 feed 
sortby[Cntrycode asc] 
groupby[Cntrycode; Numcust: group feed count , Totacctbal: group feed sum[cACCTBAL] ]
project[Cntrycode, Numcust, Totacctbal] 
sortby[Cntrycode asc] 
consume
\end{lstlisting}

Die iterative Übersetzung enthält an Stelle von Relation \sql{trelxx4} die Übersetzung der definierenden Abfrage. Ab dem Ausdruck \secondo{sortby[Cntrycode asc]} stimmen beide Übersetzungen wieder überein.

\begin{lstlisting}[caption=Abfrage Q22 in ausführbarer Syntax{,} geschachtelt]
CUSTOMER feed 
filter[
	substr(.cPHONE, 1, 2) 
	in 
	[const set(string) value ("13" "35" "31" "23" "29" "30" "18")]
] {0.01665, 0.883333} 
filter[
	fun (alias1: TUPLE) (
		attr(alias1, cACCTBAL) 
		> 
		CUSTOMER feed {c1} 
		filter[
			substr(.cPHONE_c1, 1, 2) 
			in 
			[const set(string) value ("13" "35" "31" "23" "29" "30" "18")]
		] {0.01665, 0.883333} 
		filter[(.cACCTBAL_c1 > 0.0000000000)] {0.04995, 0.875} 
		avg[cACCTBAL_c1] 
	)] {0.0333, 0.941667} 
filter[
	fun (alias2: TUPLE) 
	not((
		ORDERS feed 
		filter[(.oCUSTKEY = attr(alias2, cCUSTKEY))] 
		head[1] 
		count = 1)
	)] {0.058275, 0.958333} 
extend[Cntrycode: substr(.cPHONE, 1, 2)] 
project[Cntrycode, cACCTBAL] 
sortby[Cntrycode asc] 
groupby[Cntrycode; Numcust: group feed count , Totacctbal: group feed sum[cACCTBAL] ]
project[Cntrycode, Numcust, Totacctbal] 
sortby[Cntrycode asc] 
consume
\end{lstlisting}

%\begin{figure}[h]
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%/pgf/number format/1000 sep=},
%xtick=data,
%ylabel=Millisekunden,
%scaled ticks=base 10:0,
%xticklabels={A kalt,A warm,B kalt,B warm},
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar stacked,
%]
%\addplot coordinates {(0,	2556	)(1,	1	)(2,	1	)};
%\addplot coordinates {(0,	0	)(1,	0	)(2,	320	)};
%\addplot coordinates {(0,	0	)(1,	0	)(2,	5	)};
%\addplot coordinates {(0,	106	)(1,	106	)(2,	588	)};
%\legend{Rewrite,Lookup,QueryToPlan,Execute}
%\end{axis}
%\end{tikzpicture}
%\caption{Laufzeit der einzelnen Phasen von Abfrage Q22}
%\end{figure}
%\setcounter{footnote}{0}
%\stepcounter{footnote}\footnotetext{entschachtelt, kalt}
%\stepcounter{footnote}\footnotetext{entschachtelt, warm}
%\stepcounter{footnote}\footnotetext{iterativ}
%%\stepcounter{footnote}\footnotetext{iterativ, warm}

\begin{figure}[h]
\begin{tikzpicture}
\begin{axis}[
x tick label style={
/pgf/number format/1000 sep=},
xtick=data,
ylabel=Sekunden,
xlabel=Skalierungsfaktor,
xlabel style={yshift=-2.5em},
%xticklabels={0.0008,0.0016,0.0032,0.0064,0.0128},
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
anchor=east,legend columns=1},
scaled x ticks=base 10:4,
sharp plot
]
\addplot coordinates {(0.0008,	1.171	)(0.0016,	1.859	)(0.0032,	2.663	)(0.0064,	5.788	)(0.0128,	18.018	)};
\addplot coordinates {(0.0008,	0.204	)(0.0016,	0.221	)(0.0032,	0.27	)(0.0064,	0.266	)(0.0128,	0.353	)};
\addplot coordinates {(0.0008,	0.476	)(0.0016,	1.001	)(0.0032,	3.803	)(0.0064,	11.423	)(0.0128,	49.657	)};
%\addplot coordinates {(0.0008,	0.435	)(0.0016,	0.981	)(0.0032,	3.71	)(0.0064,	10.525	)(0.0128,	49.663	)};
\legend{entschachtelt kalt, entschachtelt warm, iterativ}% kalt, iterativ warm}
\end{axis}
\end{tikzpicture}
\caption{Laufzeit von Q22 für die beiden Ausführungsstrategien nach Skalierungsfaktor}
\label{plot:Q22 line}
\end{figure}

Ab einem Skalierungsfaktor von 0,0032 für die Datenbank ist die Laufzeit der entschachtelten Übersetzung auch ohne Ausnutzung des Query-Caches deutlich kürzer als die iterative Ausführung. Dieser Vorteil tritt mit steigendem Skalierungsfaktor immer deutlicher zu Tage.

\subsection{Laufzeit Übersicht}
Wie man Abbildung \ref{plot:Alle Laufzeit} und Tabelle \ref{tab:Alle Laufzeit kalt} entnehmen kann, ist die entschachtelte Ausführung bei gefülltem Query-Cache mindestens genauso performant, wie die iterative Ausführung. Nur die Abfragen Q17 und Q21 verhalten sich hier anders. Eindeutige Vorteile hat die entschachtelte Ausführung auch ohne Query-Cache nur bei den Abfragen Q2, Q4 und Q22. Bei den Abfragen Q7 und Q9 unterscheiden sich bei leerem Query-Cache die Laufzeiten für die entschachtelte und die iterative Ausführung nur unwesentlich.
\begin{figure}[h]
\begin{tikzpicture}
%\begin{semilogyaxis}[
\begin{axis}[
ybar=0.05em,
x tick label style={
%xshift=1.4em, 
font=\footnotesize},
xtick=data,
ylabel=Sekunden,
xticklabels={Q2,Q4,Q7,
Q9,
Q15,Q16,Q17,Q20,Q21,Q22},
scaled ticks=base 10:0,
enlargelimits=0.10,
legend style={at={(1.65,0.5)},
area legend,
anchor=east,legend columns=1},
%ybar interval=0.1,
bar width=0.45em,
xmode=normal,ymode=log,
ymin=0.1,
]
\addplot coordinates { 
(1, 0.0 )(2,	15.645 )(3,	383.557	)(4,	134.078	)(5,	7127.544	)(6,	2.038	)(7,	0.001	)(8,	218.186	)(9,	811.211	)(10,	11.843 )(11,	5.788	)(12, 0.0 ) 
};
\addplot coordinates { 
(1, 0.0 )(2,	8.094	)(3,	382.824	)(4,	0.285	)(5,	0.313	)(6,	1.247	)(7,	0.001	)(8,	7.384	)(9,	1.433	)(10,	2.142	)(11,	0.266	)(12, 0.0) 
};
\addplot coordinates { 
(1, 0.0)(2,	302.276	)(3,	1442.454	)(4,	133.863	)(5,	7148.13	)(6,	1.262	)(7,	28.144	)(8,	0.85	)(9,	266.071	)(10,	1.393	)(11,	11.423	)(12, 0.0) 
};
%\addplot coordinates { 
%(1, 0.0)(2,	300.085	)(3,	1439.432	)(4,	133.109	)(5,	7055.378	)(6,	1.279	)(7,	27.917	)(8,	0.657	)(9,	263.667	)(10,	1.32	)(11,	10.525	)(12, 0.0) 
%};
\legend{entschachtelt kalt,entschachtelt warm,iterativ}
%\end{semilogyaxis}
\end{axis}
\end{tikzpicture}
\caption{Gesamtlaufzeit bei Skalierungsfaktor 0,0064 mit logarithmischer Zeitachse}
\label{plot:Alle Laufzeit}
\end{figure}

Bei allen anderen Abfragen ist bei einmaliger Ausführung die iterative Ausführung schneller.

%\begin{figure}
%\begin{tikzpicture}
%\begin{axis}[
%x tick label style={
%xshift=1.4em, font=\footnotesize},
%xtick=data,
%ylabel=Sekunden,
%xticklabels={Q9},
%scaled ticks=base 10:0,
%enlargelimits=0.10,
%legend style={at={(1.65,0.5)},
%area legend,
%anchor=east,legend columns=1},
%ybar,
%%ybar interval=0.7,
%x tick label style={rotate=-30},
%]
%\addplot coordinates {(1,	112.071	)};
%\addplot coordinates {(1,	0.227	)};
%\addplot coordinates {(1,	111.962	)};
%\addplot coordinates {(1,	111.574	)};
%\legend{entschachtelt kalt,entschachtelt warm,iterativ kalt,iterativ warm}
%\end{axis}
%\end{tikzpicture}
%\caption{Abfrage Q9, Laufzeit bei Skalierungsfaktor 0,0008}
%\label{plot:Q9 Gesamtlaufzeit}
%\end{figure}

\begin{table}[h]
\centering
\begin{tabular}{@{}lrrr@{}} \toprule
& \multicolumn{3}{c}{Laufzeit in s} \\ \cmidrule(l){2-4}
Abfrage Nr. & iterativ & entschachtelt & entschachtelt, warm\\ \midrule
Q2	&	302,276	&	15,645	&	8,094	\\
Q4	&	1442,454	&	383,557	&	382,824	\\
Q7	&	133,863	&	134,078	&	0,285	\\
Q9	&	7148,130	&	7127,544	&	0,313	\\
Q15	&	1,262	&	2,038	&	1,247	\\
Q16	&	28,144	&	---	&	---	\\
Q17	&	0,850	&	218,186	&	7,384	\\
Q20	&	266,071	&	811,211	&	1,433	\\
Q21	&	1,393	&	11,843	&	2,142	\\
Q22	&	11,423	&	5,788	&	0,266	\\
\bottomrule\end{tabular}
 \caption{Laufzeiten bei Skalierungsfaktor 0,0064}
 \label{tab:Alle Laufzeit kalt}
\end{table}

%\begin{table}[h]
%\centering
%\begin{tabular}{@{}lrr@{}} \toprule
%& \multicolumn{2}{c}{Laufzeit in s} \\ \cmidrule(l){2-3}
%Abfrage Nr. & iterativ & entschachtelt\\ \midrule
%Q2	&	8,094	&	300,085	\\
%Q4	&	382,824	&	1439,432	\\
%Q7	&	0,285	&	133,109	\\
%Q9	&	0,313	&	7055,378	\\
%Q15	&	1,247	&	1,279	\\
%Q16	&	28,099	&	27,917	\\
%Q17	&	7,384	&	0,657	\\
%Q20	&	1,433	&	263,667	\\
%Q21	&	2,142	&	1,320	\\
%Q22	&	0,266	&	10,525	\\
%\bottomrule\end{tabular} 
%	\caption{Laufzeit bei Skalierungsfaktor 0,0064, \enquote{warm}}
% \label{tab:Alle Laufzeit warm}
%\end{table}

\section{Fazit}\label{sct:Fazit}
%Wie Abbildung \ref{Q2:plot bars} zu entnehmen ist, verkürzt sich die Laufzeit für die entschachtelte Ausführung bei mehrfacher Ausführung um die Laufzeit der Umschreibungsphase.  
%
%Während die Laufzeit für die entschachtelte Ausführung nur langsam ansteigt, wächst die Laufzeit für die iterative Ausführung exponentiell. Schon bei einem Skalierungsfaktor von 0.0064 verringert sich die Laufzeit der Abfrage durch Entschachtelung um eine Größenordnung. Eine entschachtelte Ausfürhung ist bei Abfrage Q2 also vorteilhaft. 
%
%Die Laufzeiten der Abfragen ergeben ein uneinheitliches Bild. Die Abfragen Q2 und Q4 erfahren durch die Entschachtelung eine deutliche Beschleunigung der Laufzeit. Sogar dann, wenn die temporären Relationen neu erzeugt werden müssen. Die Laufzeit der entschachtelten Abfrage ist im zweiten Durchlauf bis auf Abfrage Q21 vergleichbar oder besser der Ausführung mit geschachtelter Iteration. Bei den Abfragen Q17, Q20, Q21 und Q22 ist der Aufwand für die Erzeugung der temporären Relationen ein vielfaches der Ausführungszeit der geschachtelten Ausführung. Durch die Implementierung der beschriebenen Erweiterungen ist der Optimierer in der Lage, die oben beschriebenen Abfragen ausführen zu können. Um den Benchmark vollständig ausführen zu können, muss der Optimierer noch um einige Konstrukte erweitert werden. Die Abfragen Q18 und Q11 des Benchmarks benötigen die Unterstützung der \sql{having}-Klausel. Diese entspricht einer Selektionsoperation auf dem Ergebnis einer Aggregation. Für die Abfragen Q8 und Q14 ist die Übersetzung von Ausdrücken über Aggregationsergebnissen erforderlich. 
Der Optimierer ist jetzt in der Lage, geschachtelte Abfragen auszuführen. Für eine Teilmenge geschachtelter Abfragen wurden sogar zwei Ausführungsstrategien implementiert, zwischen welchen der Benutzer über Einstellungen im Optimierer wählen kann. Die iterativ-geschachtelte Ausführung ist für Unterabfragen in der \sql{where}-Klausel ohne weitere Einschränkungen verfügbar. Für die Entschachtelung von Unterabfragen gelten lediglich die in Kapitel \ref{chp:Entwurf} Einschränkungen für die Anwendung der Entschachtelungsalgorithmen. Die Übersetzung von Unterabfragen in der \sql{select}- und der \sql{from}-Klausel wurde für den einfachen Fall nicht-korrelierter Abfragen implementiert. 

Aus den ausgeführten Laufzeitvergleichen kann man schließen, dass die grundsätzliche Auswahl der Entschachtelungsstrategie wohl nur in wenigen Fällen zu einer deutlichen Verschlechterung der Laufzeit gegenüber der iterativen Übersetzung führen wird. Die automatische Auswahl der Ausführungsstrategie durch den Optimierer konnte in dieser Arbeit aus Platz- und Zeitgründen (siehe Abschnitt \ref{sct:Überblick2}) nicht mit umgesetzt werden. Dies stellt aber aufgrund des beobachteten Laufzeitverhalten wohl keine große Einschränkung dar. 

Zehn der 14 geschachtelten Abfragen aus dem TPC-D Benchmark lassen sich jetzt mit dem Optimierer ausführen. Um eine vollständige Ausführung des Benchmarks zu ermöglichen, muss \textsc{Secondo} nur noch um wenige Konstrukte erweitert werden. Hierzu gehören die \sql{having}-Klausel, die die Selektionsoperation auf Aggregationsergebnissen erlaubt, und ein Left-Outer-Join-Operator.

\section{Ausblick}
Der \textsc{Secondo}-Optimierer unterstützt bereits einen Großteil der im SQL-Standard definierten Syntax. Zu den wenigen fehlenden Elementen gehören die \sql{having}-Klausel und Left- sowie Right-Outer-Join-Operatoren. Eine Implementierung dieser Syntaxelemente wäre wünschenswert, da diese Konstrukte in den meisten relationalen Datenbanksystemen verfügbar sind und die Formulierung bestimmter Abfragen erleichtern.

Um die Entschachtelung zu vervollständigen, sollte über die Implementierung eines Anti-Join-Operators nachgedacht werden, da dieser für die Entschachtelung von Ausdrücken mit dem \sql{not in}-Operator notwendig ist. Hierbei muss jedoch beachtet werden, dass mit der Einführung von Anti-Join in die Optimierung beim Aufbau des Predicate-Order-Graphen nicht mehr alle Vertauschungen zulässig sind. Da auch bei den Outer-Join-Operatoren Bedingungen bezüglich der Vertauschung zu prüfen sind, könnte die Umsetzung dieser Maßnahmen möglicherweise gemeinsam erfolgen.

Weitere Formen von geschachtelten Abfragen, die noch nicht optimiert werden können sind: 
\begin{itemize}
\item korrelierte Abfragen in der \sql{select}-Klausel und der \sql{from}-Klausel
\item geschachtelte Abfragen in Disjunktionen
\item geschachtelte Abfragen, die mehrere Schachtelungsebenen überspringen
\item geschachtelte Abfragen in der \sql{having}-Klausel
\end{itemize}.
 
Eine Ergänzung des Optimierers, die diese Formen geschachtelter Abfragen einer Optimierung zugänglich macht, wäre zu überlegen.

Die Erweiterung der Optimierung um den Kostenvergleich zwischen geschachtelter und entschachtelter Ausführung auf der Basis statistisch modellierter Daten stellt mit Sicherheit eine Herausforderung dar. Die Kosten- und Selektivitätsberechnung für geschachtelte Prädikate könnte in einer folgenden Arbeit erweitert werden, um bei der Optimierung geschachtelter Abfragen beide Ausführungsstrategien zu vergleichen. 


%
% EOF
%
%