483 lines
44 KiB
TeX
483 lines
44 KiB
TeX
|
%
|
|||
|
|
% Kapitel Entwurf
|
|||
|
|
%
|
|||
|
|
%
|
|||
|
|
|
|||
|
|
\chapter{Entwurf}\label{chp:Entwurf}
|
|||
|
|
In diesem Kapitel werden die Kriterien f<>r die Auswahl der in Kapitel \ref{chp:Implementierung} implementierten Algorithmen dargestellt. Anschlie<69>end werden die theoretischen Grundlagen der einzelnen Algorithmen ausf<73>hrlich beleuchtet.
|
|||
|
|
|
|||
|
|
\section{<EFBFBD>berblick}\label{sct:<3A>berblick2}
|
|||
|
|
Die von Kim bzw. Ganski/Wong vorgestellten Algorithmen (siehe \cite{319745,38723}) zur Optimierung geschachtelter Abfragen haben f<>r die Implementierung in \textsc{Secondo} den Vorteil, dass sie sich mit der Einf<6E>hrung weniger weiterer Operatoren in die bestehende \textsc{Secondo}"=Im\-ple\-men\-tie\-rung integrieren lassen. Zur Umsetzung der Algorithmen sind die vorhandenen Stan\-dard-Ope\-ra\-ti\-on\-en Projektion und Selektion sowie die Operationen Anti-Join und Full-Outer-Join notwendig. Im Rahmen dieser Arbeit wurde ein Full-Outer-Join-Operator f<>r den Fall der Attribut-Gleichheit implementiert.
|
|||
|
|
|
|||
|
|
Da sich keiner der vorhandenen Join-Algorithmen zur Umsetzung eines effizienten Anti-Join-Algorithmus eignet, wurde auf die Implementierung eines entsprechenden Algorithmus verzichtet. Abfragen mit dem Operator \sql{not in} k<>nnen mit den ausgew<65>hlten Algorithmen nur mit einem Anti-Join-Operator entschachtelt werden. Diese werden daher zwar <20>bersetzt, die entsprechenden Pr<50>dikate sind aber keiner weiteren Optimierung zug<75>nglich. D.h. eine Optimierung <20>ber Entschachtelung ist in diesem Spezialfall nicht m<>glich. Nach der Implementierung eines Anti-Join-Operators sollte die Implementierung eines Pr<50>dikats zur Entschachtelung mit dem in \cite{319745} vorgestellten Algorithmus m<>glich sein. Zus<75>tzlich ist die Erweiterung des Optimierers um die Verarbeitung von allgemeinen Join-Pr<50>dikaten notwendig, die nicht der Kombination von Kreuzprodukt und Selektion entsprechen. Hierbei sind vor allem der Outer-Join und der Anti-Join f<>r die Optimierung von geschachtelten Abfragen von Bedeutung. Da eine beliebige Vertauschung der Reihenfolge von Outer-Join- und Join-Pr<50>dikaten nicht zul<75>ssig ist, m<>ssen die f<>r die Vertauschung hinreichenden Bedingungen beim Aufbau des Predicate-Order-Graphen ber<65>cksichtigt werden \cite{244812}.
|
|||
|
|
|
|||
|
|
Bei der Analyse des Problems wurde klar, dass eine echte Optimierung, d.h. ein Vergleich der geschachtelten und der nicht geschachtelten Ausf<73>hrungsvariante einer Abfrage, umfangreiche Berechnungen und Simulationen erfordern w<>rde. Um die Kosten der entschachtelten Abfrage ermitteln zu k<>nnen, m<>ssen die Selektivit<69>ten der Pr<50>dikate ermittelt werden. Dies erfolgt durch Auswertung jedes einzelnen Pr<50>dikats <20>ber Stichproben-Relationen, die aus den eigentlichen Relationen abgeleitet werden. Bei Selektions-Pr<50>\-di\-ka\-ten wird hier nur eine Stichprobenrelation ben<65>tigt, bei Join-Pr<50>dikaten dementsprechend zwei. Die Stichprobenrelationen werden automatisch erzeugt, sobald sie das erste Mal ben<65>tigt werden. Um die Stichprobenrelationen f<>r tempor<6F>re Relationen zu erzeugen, m<>ssen die tempor<6F>ren Relationen materialisiert werden. D.h. das Ergebnis der ihnen zugrundeliegenden Abfrage muss vollst<73>ndig ermittelt werden. Die Erzeugung der tempor<6F>ren Relationen zu diesem Zeitpunkt w<>rde die Laufzeitkosten hierf<72>r aber bei beiden Ausf<73>hrungsstrategien erh<72>hen. Ein sinnvoller Vergleich w<>re nicht mehr gegeben, da gerade die Erzeugung der tempor<6F>ren Relationen zu einer l<>ngeren Laufzeit bei entschachtelter Ausf<73>hrung f<>hren kann. Da die Pr<50>dikate der entschachtelten Abfrage m<>glicherweise auf tempor<6F>re Relationen bezugnehmen, m<>sste hier die entsprechende Selektivit<69>t simuliert werden. Eine Simulation der Selektivit<69>tsbestimmung setzt komplexe statistische Berechnungen voraus, um Selektivit<69>t und Kardinalit<69>t abzusch<63>tzen. Um an dieser Stelle verl<72>ssliche Daten zu erhalten, w<>re der Nachbau eines gro<72>en Teils der Metadaten-Ermittlung des Optimierers notwendig gewesen. So ist zwar die Absch<63>tzung der Kardinalit<69>t einer Ergebnisrelation mit Hilfe der Kardinalit<69>ten der verwendeten Relationen und den Selektivit<69>ten der Pr<50>dikate m<>glich. Aussagen <20>ber die Selektivit<69>t eines Pr<50>dikats <20>ber dieser Relation lassen sich jedoch nicht ohne weiteres treffen. Da diese Simulationen den Rahmen dieser Diplomarbeit sprengen w<>rde, wurde auf die Implementierung verzichtet.
|
|||
|
|
|
|||
|
|
Zur Veranschaulichung der Algorithmen wird in \cite{319745} eine graphische Repr<70>sentation geschachtelter Abfragen eingef<65>hrt. Abfragen werden in Form von Abfragegraphen dargestellt. Jeder Abfrageblock stellt einen Knoten dar. Jeder Knoten wird mit den zur Auswertung notwendigen Relationen markiert. Es gibt zwei Arten von Kanten, die den f<>r die Auswertung notwendigen Informationsfluss darstellen. Gerade Kanten stellen einen Informationsfluss von der Unterabfrage zur <20>u<EFBFBD>eren Abfrage dar. D.h. f<>r die Auswertung des <20>u<EFBFBD>eren Abfrageblocks sind Informationen aus der Unterabfrage notwendig. Geschwungene Kanten stellen einen Informationsfluss von der <20>u<EFBFBD>eren zur inneren Abfrage dar, sie treten somit bei korrelierten geschachtelten Abfragen auf. Die Kanten werden abh<62>ngig von der Klassifikation der Schachtelung mit verschiedenen Markierungen versehen. Ein Pr<50>dikat vom Typ-A erzeugt eine gerade Kante, die mit \sql{$A(C_k)$} versehen wird. \sql{$C_k$} ist die Projektionsspalte der Unterabfrage.
|
|||
|
|
|
|||
|
|
\tikzstyle{place}=[circle,draw=black,thick,inner sep=0pt,minimum size=6mm]
|
|||
|
|
\tikzstyle{mylabel}=[above,font=\footnotesize]
|
|||
|
|
|
|||
|
|
\begin{tikzpicture}[grow=right]
|
|||
|
|
\path
|
|||
|
|
(0,0) node[place] (Ri) {$R_i$}
|
|||
|
|
(2.5,0) node[place,draw](Rj) {$R_j$};
|
|||
|
|
\draw[-] (Ri) -- node[mylabel] {$A(C_k)$} (Rj);
|
|||
|
|
\end{tikzpicture}
|
|||
|
|
|
|||
|
|
Pr<EFBFBD>dikate vom Typ-N erzeugen eine gerade Kante mit der Markierung \sql{$N(C_k)$}. Da der Operator \sql{not in} einen Sonderfall darstellt, wird bei diesem Operator die Markierung \sql{$Nx(C_k$)} erzeugt.
|
|||
|
|
|
|||
|
|
\begin{tikzpicture}[grow=right]
|
|||
|
|
\path
|
|||
|
|
(0,0) node[place] (Ri) {$R_i$}
|
|||
|
|
(2.5,0) node[place,draw](Rj) {$R_j$};
|
|||
|
|
\draw[-] (Ri) -- node[mylabel] {$N(C_k)$} (Rj);
|
|||
|
|
\path
|
|||
|
|
(6,0) node[place] (Ri) {$R_i$}
|
|||
|
|
(8.5,0) node[place,draw](Rj) {$R_j$};
|
|||
|
|
\draw[-] (Ri) -- node[mylabel] {$Nx(C_k)$} (Rj);
|
|||
|
|
\end{tikzpicture}
|
|||
|
|
|
|||
|
|
Pr<EFBFBD>dikate vom Typ-J erzeugen zwei Kanten. Eine gerade Kante mit Markierung \sql{$N(C_k)$} bzw. \sql{$Nx(C_k$)} und eine geschwungene Kante, die mit dem korrelierten Pr<50>dikat der Unterabfrage markiert wird, also allgemein mit der Markierung \sql{$R_i.C_n \theta R_j.C_m$}. Analog dazu werden bei Pr<50>dikaten vom Typ-JA zwei Kanten erzeugt. Die erste Kante ist mit der Markierung \sql{$A(C_k)$} versehen, die zweite, geschwungene Kante wird ebenfalls mit dem korrelierten Pr<50>dikat markiert.
|
|||
|
|
|
|||
|
|
\begin{tikzpicture}[grow=right]
|
|||
|
|
\path
|
|||
|
|
(0,0) node[place] (Ri) {$R_i$}
|
|||
|
|
(2.5,0) node[place,draw](Rj) {$R_j$};
|
|||
|
|
\draw[-] (Ri) -- node[mylabel] {$N(C_k)$} (Rj);
|
|||
|
|
\draw[-]
|
|||
|
|
(Ri.south east) .. controls (1,-0.5) and (1.5,-0.5) ..
|
|||
|
|
node[mylabel,below,sloped] {$R_i.C_n \theta R_j.C_m$} (Rj.south west);
|
|||
|
|
\path
|
|||
|
|
(6,0) node[place] (Ri) {$R_i$}
|
|||
|
|
(8.5,0) node[place,draw](Rj) {$R_j$};
|
|||
|
|
\draw[-] (Ri) -- node[mylabel] {$A(C_k)$} (Rj);
|
|||
|
|
\draw[-]
|
|||
|
|
(Ri.south east) .. controls (7,-0.5) and (7.5,-0.5) ..
|
|||
|
|
node[mylabel,below,sloped] {$R_i.C_n \theta R_j.C_m$} (Rj.south west);
|
|||
|
|
\end{tikzpicture}
|
|||
|
|
|
|||
|
|
Ein Schritt im Optimierungsalgorithmus entspricht immer der Entfernung einer Kante des Abfragegraphen. Das Ergebnis der Abfrage muss dabei erhalten bleiben. Bei Abfragen mit einer Schachtelungstiefe gr<67><72>er 1 kann eine gebogene Kante auch Abfragebl<62>cke verbinden, die mehr als eine Schachtelungsebene auseinander liegen.
|
|||
|
|
|
|||
|
|
\begin{tikzpicture}[grow=right]
|
|||
|
|
\path
|
|||
|
|
(0,0) node[place] (R1) {$R_1$}
|
|||
|
|
(2.5,0) node[place](R2) {$R_2$}
|
|||
|
|
(5,0) node[place] (R3) {$R_3$};
|
|||
|
|
\draw[-] (R1) -- node[mylabel] {$N(C_k)$} (R2);
|
|||
|
|
\draw[-] (R2) -- node[mylabel] {$N(C_l)$} (R3);
|
|||
|
|
\draw[-]
|
|||
|
|
(R1.south east) .. controls (2,-0.75) and (3,-0.75) ..
|
|||
|
|
node[mylabel,below,sloped] {$R_1.C_n \theta R_3.C_m$} (R3.south west);
|
|||
|
|
\end{tikzpicture}
|
|||
|
|
|
|||
|
|
%Da der Operator \sql{in} f<>r Tupel noch nicht implementiert ist, wurde die triviale Umsetzung von \sql{in} in die Disjunktion der angegebenen Konstanten als <20>bersetzung integriert. Eine Implementierung des \sql{in}-Operators f<>r Tupelstr<74>me auf Basis des \secondo{in}- und \secondo{collect\_set}-Operators der \algebra{Collection}-Algebra w<>re eine m<>gliche Vorgehensweise zur performanten Implementierung dieses Operators. Ein Ausdruck \sql{$A_i$ in $(b_1,\dots,b_n)$} wird also in die inhaltlich <20>quivalente Darstellung \sql{($A_i = b_1\ or\ ( \dots\ or\ (A_i = b_n) \dots ))$} <20>berf<72>hrt
|
|||
|
|
|
|||
|
|
%\begin{itemize}
|
|||
|
|
% \item keine automatische Entscheidung entschachteln oder nicht
|
|||
|
|
% \subitem alle Metadaten <20>ber temp. Relationen w<>ren notwendig
|
|||
|
|
% \subitem inkl. Selektivit<69>ten
|
|||
|
|
% \item \textbf{IN} ohne Subquery -> <20>bersetzung in geschachtelte \textbf{OR} Pr<50>dikate
|
|||
|
|
%\end{itemize}
|
|||
|
|
Die Optimierungen von geschachtelten Abfragen, die in dieser Arbeit implementiert wurden, unterliegen aufgrund der verwendeten Algorithmen einigen Einschr<68>nkungen. Geschachtelte Abfragen d<>rfen im inneren Abfrageblock keine \sql{group by/having}-Klausel aufweisen (vgl. \cite{671658}). In korrelierten Abfragen d<>rfen nur Attribute der Relationen des den Abfrageblock direkt umgebenden Abfrageblocks verwendet werden. D.h. auf Schachtelungsebene n d<>rfen nur Relationen des inneren Abfrageblocks und Relationen der Schachtelungsebene n-1 verwendet werden. Tritt ein geschachteltes Pr<50>dikat in einem Disjunktionsterm auf, so ist es einer Optimierung mit den hier implementierten Algorithmen ebenfalls nicht zug<75>nglich. Algorithmen zur Optimierung geschachtelter Abfragen in Disjunktionen wurden aber z.B. in \cite{Brantner2007} vorgestellt. Bei einer Erweiterung des Optimierers um die Optimierung disjunktiver Terme kann eine entsprechende Optimierung f<>r geschachtelte Abfragen vorgesehen werden. Korrelierte Abfragen in der \sql{select}- und \sql{from}-Klausel k<>nnen nicht mit einfachen tempor<6F>ren Relationen ersetzt werden. In dieser Arbeit wurde daher nur die Behandlung nicht korrelierter Abfragen in der \sql{select}- und \sql{from}-Klausel implementiert. Geschachtelte Abfragen, die nicht durch Entschachtelungs- und Transformationsalgorithmen optimiert werden k<>nnen, werden in geschachtelte, iterative Ausdr<64>cke <20>bersetzt.
|
|||
|
|
|
|||
|
|
\section{Full-Outer-Join-Operatoren f<>r SECONDO}
|
|||
|
|
Um die korrekte Umsetzung der Korrekturen zu gew<65>hrleisten, die Ganski/Wong an den Algorithmen aus \cite{319745} vorgenommen haben, ist die Full-Outer-Join-Operation notwendig. \textsc{Secondo} kann diese Operation bereits ausf<73>hren, da sich der Full-Outer-Join durch andere, bereits implementierte Operatoren darstellen l<>sst. Die effiziente Berechnung des Full-Outer-Join ist hiermit jedoch nicht m<>glich, der Full-Outer-Join wird hierbei durch komplexe Verkn<6B>pfung von Join, Kreuzprodukt und Mengendifferenz bzw. Mengenvereinigung berechnet. Daher war es notwendig, eine effiziente Implementierung zu erstellen. \textsc{Secondo} enth<74>lt bereits mehrere Join-Operatoren. Als Vorlage f<>r die Implementierung der Full-Outer-Join-Operatoren wurden die Operatoren \secondo{sortmergejoin} und \secondo{symmjoin} ausgew<65>hlt, da sich die zugrunde liegenden Algorithmen mit wenigen <20>nderungen in einen Full-Outer-Join umbauen lassen.
|
|||
|
|
|
|||
|
|
\subsection{Sort-Merge-Outer-Join}
|
|||
|
|
Sort-Merge-Join ist ein Algorithmus zur Berechnung von Equi-Joins. Daher wird auch nur der Full-Outer-Join f<>r Equi-Join berechnet. Voraussetzung ist die Sortierung der Relationen bzw. Str<74>me bez<65>glich der Join-Attribute. Diese Anforderung kann durch das vorhergehende Sortieren der Relationen erf<72>llt werden. In \textsc{Secondo} erfolgt diese Sortierung innerhalb des Operators \secondo{sortmergejoin}.
|
|||
|
|
|
|||
|
|
Mithilfe zweier Zeiger und eines Puffers werden die sortiert vorliegenden Str<74>me durchlaufen.
|
|||
|
|
Zu Beginn des Algorithmus zeigen die beiden Zeiger auf das erste Tupel der jeweiligen Relation und der Puffer ist leer.
|
|||
|
|
\begin{enumerate}
|
|||
|
|
\item Jetzt werden alle Tupel der zweiten Relation mit <20>bereinstimmendem Wert im Join-Attribut in den Puffer gelesen und der Zeiger jeweils auf das aktuell gelesene Tupel gesetzt.
|
|||
|
|
\item Im n<>chsten Schritt wird das aktuelle Tupel der ersten Relation mit dem aktuellen Tupel der zweiten Relation verglichen.
|
|||
|
|
\subitem Solange der Wert des Join-Attributs des Tupels der ersten Relation kleiner ist, als der Wert des Join-Attributs des Tupels im Puffer, wird der Zeiger in der ersten Relation um eine Position erh<72>ht.
|
|||
|
|
\subitem Besteht Gleichheit im Wert des Join-Attributs, so wird ein Tupel der Ergebnisrelation erzeugt, das aus der Aneinanderreihung des Tupels der ersten Relation und des ersten Tupels des Puffers besteht. Anschlie<69>end wird das Tupel aus dem Puffer gel<65>scht. Ist der Puffer ersch<63>pft, wird der Zeiger in der ersten Relation erh<72>ht und mit dem ersten Schritt fortgefahren. Enth<74>lt der Puffer noch Tupel, so wird die Erzeugung eines Ergebnistupels mit dem neuen ersten Tupel des Puffers wie gerade beschrieben durchgef<65>hrt.
|
|||
|
|
\subitem Ist der Wert des Join-Attributs des aktuellen Tupels der ersten Relation gr<67><72>er, als der entsprechende Wert des aktuellen Tupels der zweiten Relation, so werden alle Tupel aus dem Puffer gel<65>scht, der Zeiger in der zweiten Relation erh<72>ht und mit dem ersten Schritt fortgefahren.
|
|||
|
|
\item Ist eine der beiden Relationen ersch<63>pft, ist der Algorithmus beendet. Verbrauchte Tupel werden aus dem Puffer gel<65>scht.
|
|||
|
|
\end{enumerate}
|
|||
|
|
|
|||
|
|
Dieser Algorithmus l<>sst sich auf folgende Art und Weise zum Full-Outer-Join ausbauen. Bei jedem Vergleichsschritt wird jetzt ein Tupel der Ausgaberelation erzeugt. Ist der Wert im ersten Puffer gr<67><72>er als im zweiten, so besteht das Tupel der Ergebnismenge aus einer Verkettung des Tupels aus dem Puffer und einem mit \sql{null}-Werten gef<65>llten Tupel der zweiten Relation. Auf die gleiche Art wird mit jedem Tupel des Puffers verfahren. Ist der Attribut-Wert gleich, so wird wie beim Sort-Merge-Join verfahren. Ist der Wert kleiner, so wird f<>r jedes Tupel im zweiten Puffer ein Ausgabe-Tupel erzeugt, das aus einer Aneinanderreihung eines NULL-Tupels der ersten Relation und dem Tupel aus dem Puffer besteht. Damit wird f<>r jedes Tupel, das nicht im Join-Ergebnis enthalten w<>re, ein Ausgabetupel erzeugt, dessen Attributwerte f<>r die Attribute der jeweils anderen Relation mit \sql{null}-Werten gef<65>llt sind.
|
|||
|
|
|
|||
|
|
\subsection{Symm-Outer-Join}
|
|||
|
|
Der Algorithmus des Operators \secondo{symmjoin} erlaubt die Berechnung der Join-Operation mit beliebigen Bedingungen. Er ist aufgrund der Verzahnung der Selektions- und Kreuz\-pro\-dukt-Ope\-ra\-ti\-on effizienter als die Verkn<6B>pfung dieser beiden Operationen. Die Bedingung wird wie in \textsc{Secondo} <20>blich durch eine Funktion dargestellt, die zwei Tupel auf einen booleschen Wert abbildet.
|
|||
|
|
|
|||
|
|
Die Relationen werden bei diesem Algorithmus mithilfe mehrerer Zeiger, zweier Puffer und eines Flags durchlaufen. Zwei der Zeiger zeigen immer auf das n<>chste Tupel einer Relation. Der dritte Zeiger zeigt auf das aktuell betrachtete Tupel. Mit dem Flag wird angezeigt, welche Relation als Quelle f<>r das n<>chste Tupel dient.
|
|||
|
|
Zu Beginn des Algorithmus sind beide Puffer leer und die Zeiger zeigen auf das jeweils erste Tupel der Relationen. Der Zeiger auf das aktuell betrachtete Tupel zeigt auf das erste Tupel der ersten Relation.
|
|||
|
|
\begin{enumerate}
|
|||
|
|
\item Sind beide Relationen ersch<63>pft, so ist der Algorithmus beendet.
|
|||
|
|
\item Ist das Flag f<>r die erste Relation gesetzt:
|
|||
|
|
\subitem Zeigt der Zeiger f<>r das aktuelle Tupel auf 0, so wird der Zeiger auf das n<>chste Tupel der ersten Relation gesetzt und der Zeiger in der ersten Relation erh<72>ht. Ist die erste Relation ersch<63>pft, wird das Flag auf die zweite Relation gesetzt.
|
|||
|
|
\subitem Wenn der zweite Puffer ersch<63>pft ist, wird das aktuelle Tupel in den ersten Puffer eingef<65>gt. Der Zeiger auf das aktuelle Tupel zeigt auf 0. Das Flag wird auf die zweite Relation ge<67>ndert. Es wird mit dem ersten Schritt fortgefahren.
|
|||
|
|
\subitem Ist der zweite Puffer noch nicht ersch<63>pft, so wird die Bedingung <20>ber dem aktuellen Tupel und dem ersten Tupel des zweiten Puffers ausgewertet. Wertet die Bedingung zu \sql{true} aus, so wird ein Ergebnistupel erzeugt, das eine Verkettung des aktuellen Tupels und des ersten Tupels des zweiten Puffers ist. Das verwendete Tupel des zweiten Puffers wird unabh<62>ngig vom Ergebnis der Auswertung aus dem Puffer gel<65>scht. Es wird mit Schritt 1 fortgefahren.
|
|||
|
|
\item Ist das Flag f<>r die zweite Relation gesetzt.
|
|||
|
|
\subitem Zeigt der Zeiger f<>r das aktuelle Tupel auf 0, so wird der Zeiger auf das n<>chste Tupel der zweiten Relation gesetzt und der Zeiger in der zweiten Relation erh<72>ht. Ist die zweite Relation ersch<63>pft, wird das Flag auf die erste Relation gesetzt.
|
|||
|
|
\subitem Ist der erste Puffer ersch<63>pft, wird das aktuelle Tupel in den zweiten Puffer eingef<65>gt. Das aktuelle Tupel wird gel<65>scht und der Zeiger hierauf wird auf 0 gesetzt. Das Flag wird auf die erste Relation ge<67>ndert. Es wird mit dem ersten Schritt fortgefahren.
|
|||
|
|
\subitem Ist der erste Puffer noch nicht ersch<63>pft, so wird die Bedingung <20>ber dem ersten Tupel des zweiten Puffers und dem aktuellen Tupel ausgewertet. Wertet die Bedingung zu \sql{true} aus, so wird ein Ergebnistupel erzeugt, das eine Verkettung des ersten Tupels des ersten Puffers des aktuellen Tupels ist. Das verwendete Tupel des ersten Puffers wird unabh<62>ngig vom Ergebnis der Auswertung aus dem Puffer gel<65>scht. Es wird mit Schritt 1 fortgefahren.
|
|||
|
|
\end{enumerate}
|
|||
|
|
|
|||
|
|
Um diesen Algorithmus in einen Full-Outer-Join zu <20>berf<72>hren, sind einige <20>nderungen notwendig. Um <20>ber die Tupel Buch zu f<>hren, die bereits im Equi-Join enthalten sind, werden zwei Hashtabellen benutzt, eine Hashtabelle f<>r Tupel der ersten Relation und eine f<>r Tupel der zweiten Relation. Um hier den Speicherbedarf klein zu halten, wird nur die Tupel-Id in der Hashtabelle gespeichert. Die Tupel-Id ist eine eindeutige Identifikation eines Tupels bezogen auf einen Strom von Tupeln. Bei jeder Erzeugung eines Ausgabetupels des \secondo{symmjoin}-Algorithmus werden die Tupel-Ids der beiden f<>r die Ausgabe verwendeten Tupel in die jeweilige Hashtabelle eingetragen. Jedesmal, wenn der Zeiger in einer der beiden Relationen erh<72>ht wird, wird das Tupel in einen Puffer eingetragen. Hierbei gibt es jeweils einen Puffer f<>r die erste und einen f<>r die zweite Relation. Da die Tupel beim Einf<6E>gen in einen Puffer nicht kopiert, sondern nur ein Zeiger auf die bestehende Tupeldarstellung erzeugt wird, ist diese Vorgehensweise durchaus effizient. Nachdem der \secondo{symmjoin}-Algorithmus beendet ist, werden die beiden Puffer, die jetzt alle Tupel der jeweiligen Relation beinhalten, mit einem Iterator durchlaufen. F<>r jedes Tupel wird <20>ber die Tupel-Id in der entsprechenden Hashtabelle nachgeschlagen, ob das Tupel bereits f<>r die Ausgabe verwendet wurde. Ist dies nicht der Fall, wird ein Ausgabetupel erzeugt, das aus den Attributwerten des betrachteten Tupels und \sql{null}-Werten f<>r die Attribute der jeweils anderen Relation besteht. Nach dieser <20>berpr<70>fung wird das Tupel aus dem Puffer gel<65>scht.
|
|||
|
|
|
|||
|
|
%\begin{itemize}
|
|||
|
|
% \item Beschreibung Sortmergejoin
|
|||
|
|
% \subitem Zwei Tupelbuffer
|
|||
|
|
% \subitem sortieren
|
|||
|
|
% \subitem immer mit dem kleineren Tupel arbeiten und vergleichen
|
|||
|
|
% \subitem falls Treffer, merge Schritt
|
|||
|
|
% \subitem sonst Tupel verwerfen und mit n<>chstem Tupel weiterarbeiten
|
|||
|
|
%\end{itemize}
|
|||
|
|
%Basis ist sortmergejoin, nicht \enquote{matchende} Tupel wird mit \sql{null}-Werten aufgef<65>llt, nur Equi-Outerjoin\\
|
|||
|
|
%Ausblick: Full-Outer-Join auf Basis von Symmjoin. Die Tupel der beiden Str<74>me werden um ein Attribut TupelID erweitert. Zu jedem Tupel, das <20>ber den Symmjoin-Algorithmus einen Partner gefunden hat, wird die TupelID in einer Hash-Tabelle gespeichert. Dabei werden die TupelIDs f<>r jeden Strom in einer eigenen Hash-Tabelle abgelegt. Nach Beendigung des Symmjoin-Algorithmus wird jeder Tupelpuffer ein zweites Mal durchlaufen. Ist die TupelID eines Tupels nicht in der entsprechenden Hash-Tabelle enthalten, so wird ein Ergebnistupel erzeugt, das die Werte aus dem betrachteten Tupel <20>bernimmt und f<>r die zus<75>tzlichen Spalten mit \sql{null}-Werten aufgef<65>llt wird. zwei Hash-Tabelle mit TupelIds f<>r alle gefundenen Tupel, Tupelbuffer durchlaufen und ein mit \sql{null}-Werten aufgef<65>lltes Tupel erzeugen f<>r alle nicht gematchten Tupel
|
|||
|
|
|
|||
|
|
\section{Behandlung quantifizierter Pr<50>dikate}\label{sct:Behandlung quantifizierter Pr<50>dikate}
|
|||
|
|
Pr<EFBFBD>dikate mit den Operatoren \sql{exists}, \sql{all} oder \sql{any} k<>nnen in ein inhaltlich <20>quivalentes Pr<50>dikat mit Aggregationsfunktion transformiert werden, sofern keine \sql{null}-Werte in den Unterabfragen enthalten sind.
|
|||
|
|
|
|||
|
|
Das Pr<50>dikat \sql{exists(Q)} ist genau dann wahr, wenn die Ergebnisrelation des Abfrageblocks Q mindestens ein Tupel enth<74>lt. Ist \lstinline[mathescape=true]{Q = select $C_n$ from $R_m$ where P}, so l<>sst sich dies aber auch als \lstinline[mathescape=true]{0 < (select count(*) $\ $from $R_m$ where P)} ausdr<64>cken. Analog dazu kann \lstinline[mathescape=true]{not exists(select $C_n$ from $R_m$ where P)} in \lstinline[mathescape=true]{0 = (select count(*) $\ $from $R_m$ where P)} <20>berf<72>hrt werden. Da die Aggregation <20>ber die urspr<70>ngliche Ergebnisspalte $C_n$ bei \sql{null}-Werten zu falschen Ergebnissen f<>hrt, m<>ssen hier alle Tupel gez<65>hlt werden. Um die Berechnung der Aggregation zu beschleunigen, kann die Abfrage mit dem Ausdruck \secondo{first 1} noch auf das erste Tupel der Unterabfrage beschr<68>nkt werden. Dies verhindert, dass teure Operatoren auf allen Tupeln der Unterabfrage ausgef<65>hrt werden m<>ssen.
|
|||
|
|
|
|||
|
|
Das Ergebnis von Abfragen mit den Operatoren \sql{all} und \sql{any} bleibt ebenfalls erhalten, wenn man Pr<50>dikate mit den beiden Operatoren in Pr<50>dikate umwandelt, die einen Vergleich mit dem Maximum bzw. Minimum der Unterabfrage darstellen.
|
|||
|
|
|
|||
|
|
\lstinline[mathescape=true]{$C_n$ $\theta$ any(select $C_m$ from $R_i$ where P)} wird f<>r $\theta \in {<,<=,>,>=}$ transformiert in
|
|||
|
|
|
|||
|
|
\lstinline[mathescape=true]{$C_n$ $\theta$ (select AGGR($C_m$) from $R_i$ where P)}.
|
|||
|
|
|
|||
|
|
Wobei hier gilt
|
|||
|
|
\begin{math}
|
|||
|
|
AGGR =
|
|||
|
|
\begin{cases}
|
|||
|
|
max&\quad\text{falls}\ \theta \in {<, \leq}, \\
|
|||
|
|
min&\quad\text{falls}\ \theta \in {>, \geq}.
|
|||
|
|
\end{cases}
|
|||
|
|
\end{math}
|
|||
|
|
|
|||
|
|
So wird
|
|||
|
|
|
|||
|
|
\lstinline[mathescape=true]{select * from $R_i$ where $C_n$ $\leq$ any(select $C_m$ from $R_j$ where P)}
|
|||
|
|
|
|||
|
|
in
|
|||
|
|
|
|||
|
|
\lstinline[mathescape=true]{select * from $R_i$ where $C_n$ $\leq$ (select $max(C_m)$ from $R_j$ where P)}
|
|||
|
|
|
|||
|
|
transformiert.
|
|||
|
|
|
|||
|
|
Im Spezialfall \lstinline[mathescape=true]{$C_n$ = any(select $C_m$ from $R_i$ where P)} wird das Pr<50>dikat durch das semantisch <20>quivalente Pr<50>dikat \lstinline[mathescape=true]{$C_n$ in (select $C_m$ from $R_i$ where P)} ersetzt.
|
|||
|
|
|
|||
|
|
\lstinline[mathescape=true]{$C_n$ $\theta$ all(select $C_m$ from $R_i$ where P)} wird f<>r $\theta \in {<,<=,>,>=}$ transformiert in
|
|||
|
|
|
|||
|
|
\lstinline[mathescape=true]{$C_n$ $\theta$ (select AGGR($C_m$) from $R_i$ where P)}.
|
|||
|
|
|
|||
|
|
Wobei hier gilt
|
|||
|
|
\begin{math}
|
|||
|
|
AGGR =
|
|||
|
|
\begin{cases}
|
|||
|
|
min&\quad\text{falls}\ \theta \in {<, \leq}, \\
|
|||
|
|
max&\quad\text{falls}\ \theta \in {>, \geq}.
|
|||
|
|
\end{cases}
|
|||
|
|
\end{math}
|
|||
|
|
|
|||
|
|
Mit dem Operator \sql{all} wird analog verfahren. Eine Abfrage mit \sql{all}
|
|||
|
|
|
|||
|
|
\lstinline[mathescape=true]{select * from $R_i$ where $C_n$ $\leq$ all(select $C_m$ from $R_j$ where P)}
|
|||
|
|
|
|||
|
|
wird in
|
|||
|
|
|
|||
|
|
\lstinline[mathescape=true]{select * from $R_i$ where $C_n$ $\leq$ (select $min(C_m)$ from $R_j$ where P)}
|
|||
|
|
|
|||
|
|
transformiert.
|
|||
|
|
|
|||
|
|
Ein Pr<50>dikat \lstinline[mathescape=true]{$C_n$ = all(select $C_m$ from $R_i$ where P)} hat keine sinnvolle Semantik, mehr, sobald die geschachtelte Abfrage mehr als einen Wert f<>r $C_m$ liefert. Die Verwendung von \sql{Epxr = all(Q)} wird in diesem Fall nicht unterst<73>tzt.
|
|||
|
|
|
|||
|
|
Mit diesen Transformationen lassen sich auch quantifizierte Pr<50>dikate als Pr<50>dikate der Typen J oder JA betrachten. Dies hat zur Folge, dass sich die im Folgenden beschriebenen Optimierungsalgorithmen auch auf diese Pr<50>dikate anwenden lassen. Au<41>erdem sind die Pr<50>dikate einer <20>bersetzung in ausf<73>hrbare \textsc{Secondo}-Syntax besser zug<75>nglich, da die Aggregation bereits durch Standard-Operatoren implementiert ist. Eine Einf<6E>hrung weiterer Operatoren zur <20>bersetzung quantifizierter Pr<50>dikate ist hierdurch nicht notwendig.
|
|||
|
|
|
|||
|
|
|
|||
|
|
\section{Entschachtelungsalgorithmen}\label{sct:Entschachtelungsalgorithmen}
|
|||
|
|
\subsection{Algorithmus \textbf{NEST-N-J}}\label{sct:Algorithmus NEST-N-J}
|
|||
|
|
In \cite{319745} wird gezeigt, dass eine Abfrage der Form
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
SELECT <20>$R_i.C_k$<EFBFBD>
|
|||
|
|
FROM <20>$R_i$<EFBFBD>
|
|||
|
|
WHERE <20>$R_i.C_h$<EFBFBD> IN (SELECT <20>$R_j.C_m$<EFBFBD> FROM <20>$R_j$<EFBFBD> WHERE P)
|
|||
|
|
\end{lstlisting}
|
|||
|
|
|
|||
|
|
\begin{tikzpicture}[grow=right]
|
|||
|
|
\path
|
|||
|
|
(0,0) node[place] (Ri) {$R_i$}
|
|||
|
|
(2.5,0) node[place,draw](Rj) {$R_j$};
|
|||
|
|
\draw[-] (Ri) -- node[mylabel] {$N(C_m)$} (Rj);
|
|||
|
|
\end{tikzpicture}
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
inhaltlich <20>quivalent zu einer Abfrage
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
SELECT <20>$R_i.C_k$<EFBFBD>
|
|||
|
|
FROM <20>$R_i, R_j$<EFBFBD>
|
|||
|
|
WHERE <20>$R_i.C_h = R_j.C_m$<EFBFBD> AND P
|
|||
|
|
\end{lstlisting}
|
|||
|
|
|
|||
|
|
ist.
|
|||
|
|
|
|||
|
|
Dabei wird die mengenbasierte Semantik des IN-Operators nur dann erhalten, wenn $R_j$ bez<65>glich der Spalte $C_m$ duplikatfrei ist. Dies kann aber jederzeit erreicht werden, indem $R_j$ durch eine tempor<6F>re Relation $R_{j}^{'}$ ersetzt wird. $R_{j}^{'}$ erh<72>lt man, indem $R_j$ auf die Spalte $C_m$ eingeschr<68>nkt und projiziert wird. F<>r skalare Vergleichsoperatoren gilt die <20>quivalenz ohne diese Einschr<68>nkung.
|
|||
|
|
|
|||
|
|
%Skalare Vergleichsoperatoren sind nicht \enquote{duplikats-entfernend}.
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
SELECT <20>$R_i.C_k$<EFBFBD>
|
|||
|
|
FROM <20>$R_i$<EFBFBD>
|
|||
|
|
WHERE <20>$R_i.C_h$<EFBFBD> NOT IN (SELECT <20>$R_j.C_m$<EFBFBD>
|
|||
|
|
FROM <20>$R_j$<EFBFBD>);
|
|||
|
|
\end{lstlisting}
|
|||
|
|
|
|||
|
|
l<EFBFBD>sst sich dagegen nicht mit
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
SELECT <20>$R_i.C_k$<EFBFBD>
|
|||
|
|
FROM <20>$R_i, R_j$<EFBFBD>
|
|||
|
|
WHERE <20>$R_i.C_h <> R_j.C_m$<EFBFBD>
|
|||
|
|
\end{lstlisting}
|
|||
|
|
|
|||
|
|
<EFBFBD>bersetzen, da die Semantik und das Ergebnis der beiden Abfragen nicht <20>bereinstimmen. In der geschachtelten Abfrage werden als Ergebnis alle Tupel der <20>u<EFBFBD>eren Relation erwartet, zu denen es keine Entsprechung in der inneren Relation gibt. Das Ergebnis der zweiten Abfrage ist die Teilmenge des Kreuzprodukts der beiden Relationen, die in den Werten $C_h$ und $C_m$ nicht <20>bereinstimmen. Die ben<65>tigte Operation der Relationenalgebra ist der Anti-Join. In den f<>r \textsc{Secondo} implementierten Algebramodulen f<>r die Relationenalgebra, \algebra{Relation-C++}- und \algebra{ExtRelation-C++}-Algebra ist kein entsprechender Operator enthalten. Eine Implementierung im Rahmen dieser Diplomarbeit erfolgte aus den oben genannten Gr<47>nden nicht.
|
|||
|
|
|
|||
|
|
Ziel des Algorithmus ist es, ein geschachteltes Pr<50>dikat in eine inhaltlich identische entschachtelte Form zu <20>berf<72>hren. Basis der Transformation ist die Beobachtung, dass das Ergebnis einer geschachtelten Abfrage vom Typ N oder J und einer Abfrage <20>ber allen verwendeten Relationen mit einem zus<75>tzlichen Join-Pr<50>dikat identisch ist. Die Entschachtelung entspricht dabei der Verschmelzung der Abfragebl<62>cke, jede Relation des <20>u<EFBFBD>eren und des inneren Abfrageblocks wird erhalten. Die entschachtelte Abfrage enth<74>lt alle Pr<50>dikate der beiden Abfragebl<62>cke. Das neue Join-Pr<50>dikat h<>lt die Vergleichsbedingung zwischen Attributausdruck des <20>u<EFBFBD>eren Abfrageblocks mit den Spalten des inneren Abfrageblocks fest. Da die Join-Operation in SQL Multimengen-Semantik hat, m<>ssen bei Operatoren mit strenger Mengensemantik, z.B. \sql{in}, die inneren Relationen vor der Verwendung in der entschachtelten Variante auf ihre Join-Spalten projiziert und durch die Pr<50>dikate der Unterabfrage eingeschr<68>nkt werden. Andernfalls liefert das neue Join-Pr<50>dikat durch Duplikate m<>glicherweise falsche Ergebnisse. Da das Ergebnis der Projektion und Selektion maximal die gleiche M<>chtigkeit hat, wie die Ursprungsrelationen, wirkt sich diese zus<75>tzliche Operation in den meisten F<>llen eher positiv auf die Anzahl der I/O-Operationen aus (siehe auch \cite{319745}). Die Durchf<68>hrung des Algorithmus entspricht im Abfragegraphen der Entfernung einer geraden Kante mit der Markierung $N(C_k)$. Grunds<64>tzlich kann mit dem hier beschriebenen Algorithmus auch eine gerade Kante mit der Markierung $Nx(C_k)$, d.h. ein geschachteltes Pr<50>dikat mit dem \sql{not in}-Operator aufgel<65>st werden. Der hierf<72>r notwendige Anti-Join-Operator und die f<>r diesen Operator notwendige Sonderbehandlung im Optimierer bleiben aber einer zuk<75>nftigen Erweiterung des Optimierers vorbehalten.
|
|||
|
|
|
|||
|
|
\begin{algorithm}
|
|||
|
|
Algorithmus NEST-N-J
|
|||
|
|
\begin{algorithmic}
|
|||
|
|
\STATE \textbf{procedure} $nest\_n\_j(Q)$
|
|||
|
|
\STATE $combine\_from\_clauses(outer\_query\_block, inner\_query\_block)$
|
|||
|
|
\STATE $combine\_where\_clauses(outer\_query\_block, inner\_query\_block)$
|
|||
|
|
\STATE $insert\_new\_join\_predicate(Q)$
|
|||
|
|
\end{algorithmic}
|
|||
|
|
\end{algorithm}
|
|||
|
|
|
|||
|
|
Die \sql{from}-Klausel der entschachtelten Abfrage setzt sich aus der Vereinigung der \sql{from}-Klauseln des <20>u<EFBFBD>eren und inneren Abfrageblocks zusammen. F<>r die neue \sql{where}-Klausel wird die Konjunktion der Pr<50>dikate der beiden \sql{where}-Klauseln gebildet. Zus<75>tzlich wird diese um ein Join-Pr<50>dikat erg<72>nzt, das aus dem urspr<70>nglich geschachtelten Pr<50>dikat abgeleitet ist. Das Pr<50>dikat ist der Vergleich des im geschachtelten Pr<50>dikat auf der linken Seite auftretenden Attributs mit dem Attribut der \sql{select}-Klausel des inneren Abfrageblocks. Der Vergleichsoperator des neuen Pr<50>dikats ist nur f<>r die Operatoren \sql{in} und \sql{not in} abweichend von dem im geschachtelten Pr<50>dikat verwendeten Operator. Ist \sql{in} der Operator des geschachtelten Pr<50>dikats, so wird der Equi-Join ben<65>tigt; der Operator des neuen Join-Pr<50>dikats ist dann \enquote{=}. Beim Operator \sql{not in} ist ein Anti-Join notwendig. Eine entsprechende Syntax existiert im SQL-Standard nicht. Die \sql{select}-Klausel der urspr<70>nglichen Abfrage bleibt unver<65>ndert.
|
|||
|
|
|
|||
|
|
%Alle FROM-Klausel kombinieren. Die resultierende FROM-Klausel umfasst alle Relationen des inneren und des <20>u<EFBFBD>eren Abfrageblocks\\
|
|||
|
|
%Die Konjunktion der \sql{where}-Klauseln bilden.\\
|
|||
|
|
%Das geschachtelte Pr<50>dikat \begin{math}[R_i.C_h \operatorname{op}\ (\texttt{SELECT} R_j.C_m \dots)]\end{math} ersetzen durch ein neues Join-Pr<50>dikat \begin{math}[R_i.C_h \operatorname{\emph{new-op}} R_j.C_m]\end{math}, das mit der restlichen \sql{where}-Klausel per Konjunktion verbunden ist\\
|
|||
|
|
%Die SELECT-Klausel des <20>u<EFBFBD>ersten Abfrageblocks behalten\\
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
select <20>$A_1 ,\dots,A_n$<EFBFBD>
|
|||
|
|
from <20>$R_1 ,\dots,R_m$<EFBFBD>
|
|||
|
|
where <20>$P_1,\dots,P_l,$<EFBFBD>
|
|||
|
|
<09>$X\operatorname{\theta}\ ($<EFBFBD>
|
|||
|
|
select <20>$T_i.B$<EFBFBD>
|
|||
|
|
from <20>$T_1 ,\dots,T_s$<EFBFBD>
|
|||
|
|
where <20>$Q_1,\dots,Q_r$<EFBFBD>
|
|||
|
|
<09>$)$<EFBFBD>
|
|||
|
|
\end{lstlisting}
|
|||
|
|
|
|||
|
|
wird transformiert in
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
select <20>$A_1,\dots,A_n$<EFBFBD>
|
|||
|
|
from <20>$R_1,\dots,R_m,T_1,\dots,T_s$<EFBFBD>
|
|||
|
|
where <20>$P_1,\dots,P_l$<EFBFBD>,
|
|||
|
|
<09>$Q_1,\dots,Q_r$<EFBFBD>
|
|||
|
|
<09>$X\operatorname{\theta^'}T_i.B$<EFBFBD>
|
|||
|
|
\end{lstlisting}
|
|||
|
|
|
|||
|
|
wobei gelten muss
|
|||
|
|
|
|||
|
|
\begin{math}
|
|||
|
|
X \subset\{A_1,\ldots,A_n\} \\[1em]
|
|||
|
|
\theta \in \{\operatorname{IN},\operatorname{NOT\ IN},=,\not=,>,\geq,<,\leq\} \\[1em]
|
|||
|
|
\theta^{'} =
|
|||
|
|
\begin{cases}
|
|||
|
|
=&\quad\text{falls}\ \theta = \operatorname{IN}, \\
|
|||
|
|
\triangleright&\quad\text{falls}\ \theta = \operatorname{NOT\ IN}, \\
|
|||
|
|
\theta&\quad\text{sonst}.
|
|||
|
|
\end{cases}
|
|||
|
|
\end{math}
|
|||
|
|
|
|||
|
|
$\triangleright$ entspricht hier dem Anti-Join-Operator
|
|||
|
|
|
|||
|
|
Der Beweis f<>r die Korrektheit wird in \cite{319745} gef<65>hrt. Aus der im SQL Standard definierten Semantik f<>r geschachtelte Abfragen, ergibt sich, dass f<>r jedes betrachtete Tupel der <20>u<EFBFBD>eren Abfrage die innere Abfrage ausgewertet werden kann. F<>r den Operator \sql{in} bedeutet dies, dass das geschachtelte Pr<50>dikat \sql{true} ist, wenn der Wert $X$ im Ergebnis der inneren Abfrage enthalten ist. Das Join-Pr<50>dikat der entschachtelten Abfrage ist genau dann \sql{true}, wenn das geschachtelte Pr<50>dikat wahr ist.
|
|||
|
|
|
|||
|
|
\subsection{Algorithmus \textbf{NEST-JA2}}\label{sct:Algorithmus NEST-JA2}
|
|||
|
|
Der Algorithmus basiert auf der Idee, die ben<65>tigten Aggregationswerte f<>r jede Auspr<70>gung der Selektion, d.h. f<>r jede Belegung der Attribute der \sql{where}-Klausel, nur einmal zu berechnen. Um die Auswertung der Aggregation nicht bei jedem Tupel der <20>u<EFBFBD>eren Relation durchf<68>hren zu m<>ssen, wird mit tempor<6F>ren Tabellen gearbeitet. Es wird die Aggregation <20>ber die inneren Relationen, gruppiert nach Werten des Join-Attributs der <20>u<EFBFBD>eren Spalte, vorausberechnet. Da die tempor<6F>ren Relationen persistent abgelegt werden, f<>llt der Aufwand f<>r ihr Anlegen nur einmal an. Wird die Abfrage w<>hrend einer Sitzung erneut aufgerufen, so kann auf die bestehenden tempor<6F>ren Relationen zugegriffen werden, d.h. die Laufzeitkosten f<>r die Erstellung der tempor<6F>ren Relationen fallen w<>hrend einer Sitzung nur einmal an.
|
|||
|
|
|
|||
|
|
\begin{algorithm}
|
|||
|
|
Algorithmus NEST-JA2
|
|||
|
|
\begin{algorithmic}
|
|||
|
|
\STATE \textbf{procedure} $nest\_ja2(Q)$
|
|||
|
|
\STATE $Rt_1 = project\_outer\_relations(Q)$
|
|||
|
|
\STATE $Rt_2 = project\_and\_restrict\_inner\_relations(Q)$
|
|||
|
|
\IF{Aggregationsfunktion ist COUNT}
|
|||
|
|
\IF{COUNT(*)}
|
|||
|
|
\STATE \textit{Ersetze * durch Join-Attribut}
|
|||
|
|
\ENDIF
|
|||
|
|
\STATE $Rt_3 = outerjoin\_and\_aggregate(Rt_1, Rt_2)$
|
|||
|
|
\ELSE
|
|||
|
|
\STATE $Rt_3 = join\_and\_aggregate(Rt_1, Rt_2)$
|
|||
|
|
\ENDIF
|
|||
|
|
\STATE $equi\_join(outer\_relations, Rt_3)$
|
|||
|
|
\end{algorithmic}
|
|||
|
|
\end{algorithm}
|
|||
|
|
|
|||
|
|
Im ersten Schritt werden die ben<65>tigten <20>u<EFBFBD>eren Relationen auf die in der Unterabfrage verwendeten Attributspalten projiziert und durch den Zusatz \sql{distinct} um Duplikate bereinigt. Hiermit erh<72>lt man die erste tempor<6F>re Relation $Rt_1$. Die zweite tempor<6F>re Relation $Rt_2$ ist die Projektion der inneren Relationen auf die Attribute der korrelierten Pr<50>dikate und Restriktion durch alle einfachen Pr<50>dikate der Unterabfrage. Die dritte tempor<6F>re Relation $Rt_3$ ist ein Join aus den beiden vorhergehenden tempor<6F>ren Relationen. Hierbei wird die Aggregation vorausberechnet und nach den Join-Attributen der <20>u<EFBFBD>eren Relationen gruppiert. Handelt es sich bei der Aggregationsfunktion um \sql{count}, so muss ein Full-Outer-Join ausgef<65>hrt werden, da hier \sql{null}-Werte das Ergebnis der Aggregation beeinflussen.
|
|||
|
|
|
|||
|
|
Wird \sql{count} in der urspr<70>nglichen Abfrage auf Tupelebene ausgef<65>hrt (\sql{select count(*)}), so muss die Aggregation bei der Erstellung der tempor<6F>ren Relation auf eine der Join-Spalten ge<67>ndert werden, um das Ergebnis nicht zu verf<72>lschen. Es d<>rfen nur die Tupel gez<65>hlt werden, die f<>r Spalten, die aus den inneren Relationen stammen, keine \sql{null}-Werte annehmen. Die Projektion der Relation $Rt_3$ erfolgt auf die entsprechenden Attribute der <20>u<EFBFBD>eren Relationen, gegebenenfalls m<>ssen die Attribute in der \sql{select}-Klausel umgesetzt werden. Die entschachtelte Version der Abfrage wird gebildet, indem die urspr<70>ngliche \sql{from}-Klausel um die tempor<6F>re Relation $Rt_3$ erweitert wird. Das geschachtelte Pr<50>dikat der \sql{where}-Klausel wird durch ein neues Join-Pr<50>dikat ersetzt, welches auf <20>bereinstimmung der urspr<70>nglichen linken Seite des geschachtelten Pr<50>dikats mit der Aggregationsspalte von $Rt_3$ pr<70>ft. Der Algorithmus entspricht der Entfernung einer gebogenen Kante und einer geraden Kante zwischen zwei Knoten im Abfragegraphen.
|
|||
|
|
|
|||
|
|
|
|||
|
|
%1. tempor<6F>re Relation = Projektion der <20>u<EFBFBD>eren Relation(en) auf die Join-Spalten und Restriktion durch \emph{simple} Pr<50>dikate, die in der <20>u<EFBFBD>eren \sql{where}-Klausel enthalten sind\\
|
|||
|
|
%2. tempor<6F>re Relation = Join aus 1. tempor<6F>rer und innerer/en Relationen, falls Aggregationsfunktion = \sql{count}, dann m<>ssen die simplen Pr<50>dikate auf die innere Relation vor dem Join angewandt werden. Ist die Aggregationsfunktion \sql{count}(*), dann muss \sql{count} <20>ber die/eine Join-Spalte ausgef<65>hrt werden. Das Join-Pr<50>dikat muss den selben Operator enthalten, wie die urspr<70>ngliche geschachtelte Abfrage. Der Join-Operator in der urspr<70>nglichen Abfrage muss in \emph{=} ge<67>ndert werden. In der \sql{select}-Klausel muss die Join-Spalte der <20>u<EFBFBD>eren Relation anstelle der Inneren Relation verwendet werden\\
|
|||
|
|
|
|||
|
|
Der Algorithmus und die einzelnen Zwischenschritte werden hier in SQL-Syntax dargestellt. Die urspr<70>ngliche Abfrage hat die allgemeine Form:
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
select <20>$A_1, \dots, A_n$<EFBFBD>
|
|||
|
|
from <20>$R_1, \dots, R_m$<EFBFBD>
|
|||
|
|
where <20>$P_1 (R_1 ), \dots, P_k (R_1 )$<EFBFBD>,
|
|||
|
|
<09>$P_1 , \ldots, P_l,$<EFBFBD>,
|
|||
|
|
<09>$R_i.X \operatorname{\theta}\ ($<EFBFBD>
|
|||
|
|
select <20>$\operatorname{AGGR}(T_j.A)$<EFBFBD>
|
|||
|
|
from <20>$T_1 , \dots, T_s$<EFBFBD>
|
|||
|
|
where <20>$Q_1, \dots, Q_r$<EFBFBD>,
|
|||
|
|
<09>$R_1.Y \operatorname{op} T_1.Z$<EFBFBD>
|
|||
|
|
<09>$)$<EFBFBD>
|
|||
|
|
\end{lstlisting}.
|
|||
|
|
|
|||
|
|
Die $A_1, \dots, A_n$ sind Attributausdr<64>cke <20>ber den Schemata der Relationen $R_1, \dots, R_m$. Die Pr<50>dikate $P_1(R_1), \dots, P_k(R_1)$ sind ausschlie<69>lich <20>ber Attributen der Relation $R_1$ formuliert, sind also \emph{einfache} Pr<50>dikate <20>ber $R_1$. Die Pr<50>dikate $P_1, \dots, P_l$ sind allgemeine Pr<50>dikate <20>ber Attributen einer oder mehrerer beliebiger Relationen aus $R_1, \dots, R_m$.
|
|||
|
|
|
|||
|
|
Die erste tempor<6F>re Relation ist die Projektion der <20>u<EFBFBD>eren Relation auf die Join-Spalte des korrelierten Pr<50>dikats. Es werden bereits alle \emph{einfachen} Pr<50>dikate angewandt, da diese auschlie<69>lich <20>ber Attributen von $R_1$ definiert sind. Die Anwendung der Pr<50>dikate bereits zu diesem Zeitpunkt f<>hrt zu einer garantiert nicht gr<67><72>eren tempor<6F>ren Relation, da die Selektions-Operation das Ergebnis eines relationalen Ausdrucks nur verkleinern kann. Die tempor<6F>re Relation ergibt sich aus der Abfrage als
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
<EFBFBD>$Rt_1$<EFBFBD> =
|
|||
|
|
select distinct <20>$R_1.Y$<EFBFBD>
|
|||
|
|
from <20>$R_1$<EFBFBD>
|
|||
|
|
where <09>$P_1(R_1), \dots, P_k(R_1)$<EFBFBD>
|
|||
|
|
\end{lstlisting}.
|
|||
|
|
|
|||
|
|
F<EFBFBD>r die zweite tempor<6F>re Relation werden die inneren Relationen auf die Join-Spalten projiziert und durch die \emph{einfachen} Pr<50>dikate eingeschr<68>nkt. Es ergibt sich aus der obigen Abfrage folgender Ausdruck:
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
<EFBFBD>$Rt_2$<EFBFBD> =
|
|||
|
|
select <20>$T_j.A, T_1.Z$<EFBFBD>
|
|||
|
|
from <20>$T_1, \dots, T_s$<EFBFBD>
|
|||
|
|
where <20>$Q_1, \dots, Q_r$<EFBFBD>
|
|||
|
|
\end{lstlisting}.
|
|||
|
|
|
|||
|
|
F<EFBFBD>r Aggregationsfunktionen ungleich \sql{count} ergibt sich folgender Ausdruck f<>r die dritte tempor<6F>re Relation:
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
<EFBFBD>$Rt_3$<EFBFBD> =
|
|||
|
|
select <20>$Rt_1.Y,\operatorname{AGGR}(Rt_2.A)$<EFBFBD> as AggrResult
|
|||
|
|
from $Rt_1, Rt_2$
|
|||
|
|
where <20>$Rt_1.Y \operatorname{op} Rt_2.Z$<EFBFBD>
|
|||
|
|
group by
|
|||
|
|
<09>$Rt_2.Y$<EFBFBD>
|
|||
|
|
\end{lstlisting}.
|
|||
|
|
|
|||
|
|
Die Aggregation wird also f<>r jeden unterschiedlichen Wert von $Rt_2.Y$ genau einmal berechnet.
|
|||
|
|
|
|||
|
|
Ist die Aggregationsfunktion \sql{count}, so muss abweichend hiervon der Full-Outer-Join berechnet werden. Die hier angegebene Syntax f<>r den Outer-Join entspricht der Syntax des SQL-Standards. Die momentan im Optimierer implementierte Struktur von SQL-Abfragen l<>sst eine einfache Erweiterung um diese Outer-Join-Syntax nicht zu. Erschwerend kommt hinzu, dass Join- und Outer-Join-Operationen nur unter eingeschr<68>nkten Bedingungen in ihrer Reihenfolge vertauscht werden k<>nnen \cite{244812}. Die Integration in den zentralen Optimierungsalgorithmus w<>rde daher umfangreiche Ver<65>nderungen voraussetzen, um diese Randbedingungen w<>hrend der Optimierung <20>berpr<70>fen zu k<>nnen. Daher wurde auf die Integration des Outer-Join-Operators in die SQL-Syntax des Optimierers verzichtet. Die Erzeugung der entsprechenden tempor<6F>ren Relation erfolgt direkt in ausf<73>hrbarer Syntax.
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
<EFBFBD>$Rt_3$<EFBFBD> = (
|
|||
|
|
select <20>$Rt_1.Y,\operatorname{AGGR}(Rt_2.A)$<EFBFBD> as AggrResult
|
|||
|
|
from <20>$Rt_1$<EFBFBD> full outer join <20>$Rt_2$<EFBFBD>
|
|||
|
|
on <20>$Rt_1.Y \operatorname{op} Rt_2.Z$<EFBFBD>
|
|||
|
|
group by
|
|||
|
|
<09>$Rt_1.Y$<EFBFBD>
|
|||
|
|
<20>$)$<EFBFBD>
|
|||
|
|
\end{lstlisting}
|
|||
|
|
|
|||
|
|
F<EFBFBD>r den in dieser Arbeit umgesetzten Operator \secondo{smouterjoin} ergibt sich damit in ausf<73>hrbarer Syntax
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
<EFBFBD>$Rt_3$<EFBFBD> =
|
|||
|
|
query
|
|||
|
|
<09>$Rt_1$<EFBFBD> feed
|
|||
|
|
<09>$Rt_2$<EFBFBD> feed
|
|||
|
|
smouterjoin[Rt_1.Y, Rt_2.Z]
|
|||
|
|
groupby[AggrResult: group feed <20>$\operatorname{AGGR}(Rt_2.A)$<EFBFBD>]
|
|||
|
|
project[<5B>$Rt_1.Y$<EFBFBD>, AggrResult]
|
|||
|
|
consume
|
|||
|
|
\end{lstlisting}.
|
|||
|
|
|
|||
|
|
Hierbei gilt allerdings die oben beschriebene Einschr<68>nkung, dass das Pr<50>dikat \\pred$[Rt_1.Y \operatorname{op} Rt_2.Z]$ die Form $Rt_1.Y = Rt_2.Z$ haben muss.
|
|||
|
|
|
|||
|
|
Nach der Berechnung der tempor<6F>ren Tabellen vereinfacht sich die urspr<70>ngliche Abfrage zu
|
|||
|
|
|
|||
|
|
\begin{lstlisting}
|
|||
|
|
select <20>$A_1, \dots, A_n$<EFBFBD>
|
|||
|
|
from <20>$R_1, \dots, R_m, Rt_3$<EFBFBD>,
|
|||
|
|
where <20>$P_1, \dots, P_l,$<EFBFBD>
|
|||
|
|
<09>$R_i.X \operatorname{\theta} Rt_3$<EFBFBD>.AggrResult,
|
|||
|
|
<09>$R_1.Y = Rt_3.Z$<EFBFBD>
|
|||
|
|
\end{lstlisting}
|
|||
|
|
|
|||
|
|
wobei f<>r den Operator $\theta$ gelten muss
|
|||
|
|
|
|||
|
|
\begin{math}\theta \in\{=,\not=,>,\geq,<,\leq\}\end{math}.
|
|||
|
|
|
|||
|
|
\subsection{Algorithmus NEST-G}\label{sct:Algorithmus NEST-G}
|
|||
|
|
Ganski/Wong stellen in \cite{38723} ihren allgemeinen Algorithmus zur Optimierung geschachtelter Abfragen vor. Dieser wendet rekursiv je nach Schachtelungstyp die oben vorgestellten Algorithmen auf geschachtelte Pr<50>dikate an. Geschachtelte Pr<50>dikate, die keiner der vier Klassen entsprechen, werden wie gew<65>hnliche Join- oder Selektions-Pr<50>dikate behandelt.
|
|||
|
|
|
|||
|
|
\begin{algorithm}
|
|||
|
|
\caption{Algorithmus NEST-G}
|
|||
|
|
\begin{algorithmic}
|
|||
|
|
\STATE \textbf{procedure} $nest\_g(Q)$
|
|||
|
|
\FORALL{Pr<EFBFBD>dikate p in Q}
|
|||
|
|
\IF{p ist ein geschachteltes Pr<50>dikat mit Unterabfrage $Q_u$}
|
|||
|
|
\STATE $nest\_g(Q_u)$
|
|||
|
|
\IF{$Q_u$ ist vom Typ A}
|
|||
|
|
\STATE $nest\_a(Q_u)$
|
|||
|
|
\ELSIF{$Q_u$ ist vom Typ JA}
|
|||
|
|
\STATE $nest\_ja2(Q_u)$
|
|||
|
|
\STATE $nest\_n\_j(Q, Q_u)$
|
|||
|
|
\ENDIF
|
|||
|
|
\ENDIF
|
|||
|
|
\STATE $nest\_n\_j(Q_u)$
|
|||
|
|
\ENDFOR
|
|||
|
|
\end{algorithmic}
|
|||
|
|
\end{algorithm}
|
|||
|
|
|
|||
|
|
|
|||
|
|
Der Algorithmus NEST-A wandelt ein geschachteltes Pr<50>dikat einer Abfrage in ein einfaches Pr<50>dikat um. Mit Algorithmus NEST-JA2 wird ein geschachteltes Pr<50>dikat vom Typ-JA in ein geschachteltes Pr<50>dikat vom Typ-J umgewandelt. Durch die Anwendung von Algorithmus NEST-N-J nach NEST-JA2 wird dieses Pr<50>dikat in ein einfaches Join-Pr<50>dikat transformiert.
|
|||
|
|
|
|||
|
|
Damit entfernen die beiden Algorithmen NEST-A und NEST-N-J eine Schachtelungsebene aus einem Pr<50>dikat. Da NEST-G rekursiv auf die Unterabfragen angewandt wird wird in jedem Schleifendurchlauf des Algorithmus die Schachtelungstiefe eines Pr<50>dikats um eins erniedrigt. Da geschachtelte Pr<50>dikate eine Schachtelungstiefe $>= 1$ haben, ist sichergestellt, dass der Algorithmus terminiert. Nach Beendigung des Algorithmus enth<74>lt die transformierte Version von Q keine geschachtelten Pr<50>dikate der Typen A, N-J oder JA.
|
|||
|
|
|
|||
|
|
|
|||
|
|
%allgemeiner Algorithmus zur Entschachtelung mit tempor<6F>ren Tabellen, auf der Basis von Join- und Outerjoin-Operatoren und tempor<6F>ren Tabellen,
|
|||
|
|
%
|
|||
|
|
%
|
|||
|
|
%Begriffserkl<6B>rung Schachtelunsgtiefe
|
|||
|
|
%
|
|||
|
|
%Schritte des Optimierers
|
|||
|
|
%\begin{itemize}
|
|||
|
|
% \item Query-Rewriting
|
|||
|
|
% \item Schema-Lookup
|
|||
|
|
% \item Abfrageplan-Ermittlung
|
|||
|
|
% \item <20>bersetzung Plan in ausf<73>hrbare Syntax
|
|||
|
|
%\end{itemize}
|
|||
|
|
%
|
|||
|
|
%
|
|||
|
|
%durch vorhanden Operatoren in \textsc{Secondo} fast vollst<73>ndig umsetzbar, nur Erweiterung um Full-Outerjoin-Operator notwendig\\
|
|||
|
|
%Vergleich nested-iteration/dekorrelierter Plan wird \underline{nicht} implementiert:\\
|
|||
|
|
%F<>r den Vergleich der Kosten m<>sste die komplette Selektivit<69>ts- und Kostenbestimmung f<>r die notwendigen tempor<6F>ren Relationen simuliert werden (**ausf<73>hrlicher beschreiben**)\\
|
|||
|
|
%kann nicht f<>r alle Formen von Subqueries genutzt werden (Beispiele)\\
|
|||
|
|
%Ergebnis sollte eine Abfrage der Schachtelungstiefe 0 sein. Der Optimierer
|
|||
|
|
%
|
|||
|
|
%\begin{enumerate}
|
|||
|
|
% \item Jedes Typ-A Pr<50>dikat wird in ein einfaches Pr<50>dikat umgewandelt, indem es vollst<73>ndig ausgewertet wird. Falls das Pr<50>dikat ebenfalls geschachtelt ist, wird Algorithmus NEST-G rekursiv angewandt, bis das Pr<50>dikat nicht weiter entschachtelt werden kann.
|
|||
|
|
% \item Jedes Typ-JA Pr<50>dikat wird mit dem Algorithmus NEST-JA(G) in eine semantisch <20>quivalente Abfrage vom Typ-N oder -J umgewandelt.
|
|||
|
|
% \item \emph{In dieser Arbeit nicht implementiert}: Pr<50>dikate vom Typ-D werden in ihre kanonische Form transformiert.
|
|||
|
|
% \item Die aus den bisherigen Schritten des Algorithmus resultierende Abfrage hat nur noch Pr<50>dikate vom Typ-N oder Typ-J. Diese wird mit dem Algorithmus NEST-N-J in ihre kanonische Form <20>berf<72>hrt.
|
|||
|
|
%\end{enumerate}
|
|||
|
|
|
|||
|
|
\section{<EFBFBD>bersetzung in ausf<73>hrbare Syntax}
|
|||
|
|
\subsection{IN Operator}
|
|||
|
|
Die \algebra{Collection}-Algebra stellt mit dem Operator \algebra{in} einen mengenbasierten Operator bereit, der die Semantik des SQL-Operators \sql{in} implementiert. Da der Typ-Konstruktor f<>r \algebra{set} (entspricht einer Menge) <20>ber beliebigen Datentypen aus der \emph{Kind} \algebra{DATA} definiert ist, steht die \sql{in}-Operation f<>r beliebige Attributausdr<64>cke zur Verf<72>gung, denn Attribute ebenfalls <20>ber \algebra{DATA} definiert sind. Daher wurde dieser Operator f<>r die <20>bersetzung von Pr<50>dikaten mit dem \sql{in}-Operator ausgew<65>hlt.
|
|||
|
|
|
|||
|
|
\subsection{Geschachtelte Iteration}
|
|||
|
|
Geschachtelte Pr<50>dikate, die nicht durch die oben beschriebenen Algorithmen in flache Abfragen <20>berf<72>hrt werden k<>nnen, sollen dennoch vom Optimierer ausgef<65>hrt werden k<>nnen. Die geschachtelte Iteration ist die triviale Umsetzung der Semantik geschachtelter Pr<50>dikate. Die <20>bersetzung der Unterabfragen soll hierbei soweit wie m<>glich mit den bereits vorhandenen Verfahren des Optimierers erfolgen, um eine effiziente <20>bersetzung zu gew<65>hrleisten. Korrelierte Pr<50>dikate k<>nnen nicht direkt in die <20>bersetzung der Unterabfrage einbezogen werden. Daher werden die korrelierten Pr<50>dikate f<>r die <20>bersetzung von der Unterabfrage entfernt. Die so entstandene, einfache Abfrage wird mit dem Optimierungsalgorithmus in einen Plan <20>bersetzt. Die korrelierten Pr<50>dikate werden dann auf diesen Plan als Selektionspr<70>dikate angewandt, d.h. es werden erst alle einfachen und alle Join-Pr<50>dikate ausgef<65>hrt und auf deren Ergebnis die korrelierten Pr<50>dikate als Selektion ausgef<65>hrt. Ist mehr als ein korreliertes Pr<50>dikat vorhanden, so werden die Pr<50>dikate in der Reihenfolge ihrer Selektivit<69>t ausgef<65>hrt. Pr<50>dikate mit hoher Selektivit<69>t werden zuerst ausgef<65>hrt, um das noch weiter zu verarbeitende Ergebnis zu minimieren.
|
|||
|
|
|
|||
|
|
|
|||
|
|
%
|
|||
|
|
% EOF
|
|||
|
|
%
|
|||
|
|
%
|