% % 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= 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 ( 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 % %