arch-dev.sgml

关系型数据库 Postgresql 6.5.2

    <para>
     Note that every <literal>Sort</literal> and <literal>SeqScan</literal> node appearing in figure
     \ref{plan} has got a <literal>targetlist</literal> but because there was not enough space
     only the one for the <literal>MergeJoin</literal> node could be drawn.
    </para>

    <para>
     Another task performed by the planner/optimizer is fixing the
     <firstterm>operator ids</firstterm> in the <literal>Expr</literal>
     and <literal>Oper</literal> nodes. As
     mentioned earlier, <productname>Postgres</productname> supports a variety of different data
     types and even user defined types can be used. To be able to maintain
     the huge amount of functions and operators it is necessary to store
     them in a system table. Each function and operator gets a unique
     operator id. According to the types of the attributes used
     within the qualifications etc., the appropriate operator ids
     have to be used.
    </para>
   </sect2>
  </sect1>

  <sect1>
   <title>Executor</title>

   <para>
    The <firstterm>executor</firstterm> takes the plan handed back by the
    planner/optimizer and starts processing the top node. In the case of
    our example (the query given in example \ref{simple_select}) the top
    node is a <literal>MergeJoin</literal> node. 
   </para>

   <para>
    Before any merge can be done two tuples have to be fetched (one from
    each subplan). So the executor recursively calls itself to
    process the subplans (it starts with the subplan attached to
    <literal>lefttree</literal>). The new top node (the top node of the left subplan) is a
    <literal>SeqScan</literal> node and again a tuple has to be fetched before the node
    itself can be processed. The executor calls itself recursively
    another time for the subplan attached to <literal>lefttree</literal> of the
    <literal>SeqScan</literal> node.
   </para>

   <para>
    Now the new top node is a <literal>Sort</literal> node. As a sort has to be done on
    the whole relation, the executor starts fetching tuples
    from the <literal>Sort</literal> node's subplan and sorts them into a temporary
    relation (in memory or a file) when the <literal>Sort</literal> node is visited for
    the first time. (Further examinations of the <literal>Sort</literal> node will
    always return just one tuple from the sorted temporary
    relation.)
   </para>

   <para>
    Every time the processing of the <literal>Sort</literal> node needs a new tuple the
    executor is recursively called for the <literal>SeqScan</literal> node
    attached as subplan. The relation (internally referenced by the
    value given in the <literal>scanrelid</literal> field) is scanned for the next
    tuple. If the tuple satisfies the qualification given by the tree
    attached to <literal>qpqual</literal> it is handed back, otherwise the next tuple
    is fetched until the qualification is satisfied. If the last tuple of
    the relation has been processed a <literal>NULL</literal> pointer is
    returned.
   </para>

   <para>
    After a tuple has been handed back by the <literal>lefttree</literal> of the
    <literal>MergeJoin</literal> the <literal>righttree</literal> is processed in the same way. If both
    tuples are present the executor processes the <literal>MergeJoin</literal>
    node. Whenever a new tuple from one of the subplans is needed a
    recursive call to the executor is performed to obtain it. If a
    joined tuple could be created it is handed back and one complete
    processing of the plan tree has finished. 
   </para>

   <para>
    Now the described steps are performed once for every tuple, until a
    <literal>NULL</literal> pointer is returned for the processing of the
    <literal>MergeJoin</literal> node, indicating that we are finished.
   </para>

  </sect1>

<!--
**********************************************************
**********************************************************
**********************************************************
**********************************************************
**********************************************************

\pagebreak
\clearpage

\section{The Realization of the Having Clause}
\label{having_impl}

The {\it having clause} has been designed in SQL to be able to use the
results of {\it aggregate functions} within a query qualification. The
handling of the {\it having clause} is very similar to the handling of
the {\it where clause}. Both are formulas in first order logic (FOL)
that have to evaluate to true for a certain object to be handed back:
%
\begin{itemize}
<step> The formula given in the {\it where clause} is evaluated for
every tuple. If the evaluation returns {\tt true} the tuple is
returned, every tuple not satisfying the qualification is ignored.
%
<step> In the case of {\it groups} the {\it having clause} is evaluated
for every group. If the evaluation returns {\tt true} the group is
taken into account otherwise it is ignored.
\end{itemize}
%
\subsection{How Aggregate Functions are Implemented}
\label{aggregates}

Before we can describe how the {\it having clause} is implemented we
will have a look at the implementation of {\it aggregate functions} as
long as they just appear in the {\it targetlist}. Note that {\it aggregate
functions} are applied to groups so the query must contain a {\it
group clause}.
%
\begin{example} 
\label{having}
Here is an example of the usage of the {\it aggregate
function} {\tt count} which counts the number of part numbers ({\tt
pno}) of every group. (The table {\tt sells} is defined in example
\ref{supplier}.)
%
\begin{verbatim}
  select sno, count(pno)
  from sells
  group by sno;
\end{verbatim}
%
\end{example}
%
A query like the one in example \ref{having} is processed by the usual
stages:
%
\begin{itemize}
<step> the parser stage
<step> the rewrite system
<step> the planner/optimizer 
<step> the executor
\end{itemize}
%
and in the following sections we will describe what every stage does
to the query in order to obtain the appropriate result.

\subsubsection{The Parser Stage}

\begin{figure}[ht]
\begin{center}
\epsfig{figure=figures/parse_having.ps}
\caption{{\it Querytree} built up for the query of example \ref{having}}
\label{parse_having}
\end{center}
\end{figure}

The parser stage builds up a {\it querytree} containing the {\it
where} qualification and information about the {\it grouping} that has
to be done (i.e. a list of all attributes to group for is attached to
the field {\tt groupClause}). The main difference to {\it querytrees}
built up for queries without {\it aggregate functions} is given in the
field {\tt hasAggs} which is set to {\tt true} and in the {\it
targetlist}. The {\tt expr} field of the second {\tt TLE} node of the
{\it targetlist} shown in figure \ref{parse_having} does not point
directly to a {\tt VAR} node but to an {\tt Aggreg} node representing
the {\it aggregate function} used in the query.

A check is made that every attribute grouped for appears only without
an {\it aggregate function} in the {\it targetlist} and that every
attribute which appears without an {\it aggregate function} in the
{\it targetlist} is grouped for.
%

\pagebreak 

\subsubsection{The Rewrite System}

The rewriting system does not make any changes to the {\it querytree}
as long as the query involves just {\it base tables}. If any {\it
views} are present the query is rewritten to access the tables
specified in the {\it view definition}.
%
\subsubsection{Planner/Optimizer}
Whenever an {\it aggregate function} is involved in a query (which is
indicated by the {\tt hasAggs} flag set to {\tt true}) the planner
creates a {\it plantree} whose top node is an {\tt AGG} node. The {\it
targetlist} is searched for {\it aggregate functions} and for every
function that is found, a pointer to the corresponding {\tt Aggreg}
node is added to a list which is finally attached to the field {\tt aggs} of
the {\tt AGG} node. This list is needed by the {\it executor} to know which
{\it aggregate functions} are present and have to be
handled.

The {\tt AGG} node is followed by a {\tt GRP} node. The implementation
of the {\it grouping} logic needs a sorted table for its operation so
the {\tt GRP} node is followed by a {\tt SORT} node. The {\tt SORT}
operation gets its tuples from a kind of {\tt Scan} node (if no
indices are present this will be a simple {\tt SeqScan} node). Any
qualifications present are attached to the {\tt Scan} node. Figure
\ref{plan_having} shows the {\it plan} created for the query given in
example \ref{having}.

\begin{figure}[ht]
\begin{center}
\epsfig{figure=figures/plan_having.ps}
\caption{{\it Plantree} for the query of example \ref{having}}
\label{plan_having}
\end{center}
\end{figure}

Note that every node has its own {\it targetlist} which may differ from the
one of the node above or below.  The field {\tt varattno} of every
{\tt VAR} node included in a {\it targetlist} contains a number representing
the position of the attribute's value in the tuple of the current node.

\pagebreak
\clearpage

\subsubsection{Executor}

The {\it executor} uses the function {\tt execAgg()} to execute {\tt AGG}
nodes. As described earlier it uses one main function {\tt
ExecProcNode} which is called recursively to execute subtrees. The
following steps are performed by {\tt execAgg()}:
%
\begin{itemize}
%
<step> The list attached to the field {\tt aggs} of the {\tt AGG} node is
examined and for every {\it aggregate function} included the {\it transition
functions} are fetched from a {\it function table}. Calculating the
value of an {\it aggregate function} is done using three functions:
%
\begin{itemize}
<step> The {\it first transition function} {\tt xfn1} is called with the
current value of the attribute the {\it aggregate function} is applied
to and changes its internal state using the attribute's value given as
an argument.
%
<step> The {\it second transition function} {\tt xfn2} is called without any
arguments and changes its internal state only according to internal rules.
%
<step> The {\it final function} {\tt finalfn} takes the final states of {\tt
xfn1} and {\tt xfn2} as arguments and finishes the {\it aggregation}.
\end{itemize}
%
\begin{example} Recall the functions necessary to implement the
{\it aggregate function} {\tt avg} building the average over all
values of an attribute in a group (see section \ref{ext_agg} {\it
Extending Aggregates}):
%
\begin{itemize}
%
<step> The first transition function {\tt xfn1} has to be a function that
takes the actual value of the attribute {\tt avg} is applied to as an
argument and adds it to the internally stored sum of previous
calls.
%
<step> The second transition function {\tt xfn2} only increases an internal
counter every time it is called. 
%
<step> The final function {\tt finalfn} divides the result of {\tt xfn1} by
the counter of {\tt xfn2} to calculate the average.
%
\end{itemize}
%
\end{example}
%
Note that {\tt xfn2} and {\tt finalfn} may be absent (e.g. for the
{\it aggregate function} {\tt sum} which simply sums up all values of
the given attribute within a group. \\
\\
{\tt execAgg()} creates an array containing one entry for every {\it
aggregate function} found in the list attached to the field {\tt
aggs}. The array will hold information needed for the execution of
every {\it aggregate function} (including the {\it transition functions}
described above).
%
<step> The following steps are executed in a loop as long as there are
still tuples returned by the subplan (i.e. as long as there are still
tuples left in the current group). When there are no tuples left
in the group a {\tt NULL} pointer is returned indicating the end of the
group.
%
\begin{itemize}
<step> A new tuple from the subplan (i.e. the {\it plan} attached to the
field {\tt lefttree}) is fetched by recursively calling {\tt
ExecProcNode()} with the subplan as argument.
%
<step> For every {\it aggregate function} (contained in the array created
before) apply the transition functions {\tt xfn1} and {\tt xfn2} to
the values of the appropriate attributes of the current tuple.
\end{itemize}
%
<step> When we get here, all tuples of the current group have been
processed and the {\it transition functions} of all {\it aggregate
functions} have been applied to the values of the attributes. We are
now ready to complete the {\it aggregation} by applying the {\it final
function} ({\tt finalfn}) for every {\it aggregate function}.
%
<step> Store the tuple containing the new values (the results of the
{\it aggregate functions}) and hand it back.
\end{itemize}
%
Note that the procedure described above only returns one tuple
(i.e. it processes just one group and when the end of the group is
detected it processes the {\it aggregate functions} and hands back one
tuple). To retrieve all tuples (i.e. to process all groups) the
function {\tt execAgg()} has to be called (returning a new tuple every
time) until it returns a {\tt NULL} pointer indicating that there are
no groups left to process.

\subsection{How the Having Clause is Implemented}

The basic idea of the implementation is to attach the {\it operator tree}
built for the {\it having clause} to the field {\tt qpqual} of
node {\tt AGG} (which is the top node of the query tree). Now the executor
has to evaluate the new {\it operator tree} attached to {\tt qpqual} for
every group processed. If the evaluation returns {\tt true} the group
is taken into account otherwise it is ignored and the next group will
be examined. \\
\\
In order to implement the {\it having clause} a variety of changes
have been made to the following stages:
%
\begin{itemize}
<step> The {\it parser stage} has been modified slightly to build up and
transform an {\it operator tree} for the {\it having clause}.
%
<step> The {\it rewrite system} has been adapted to be able to use {\it
views} with the {\it having logic}.
%
<step> The {\it planner/optimizer}  now takes the {\it operator tree} of
the {\it having clause} and attaches it to the {\tt AGG} node (which
is the top node of the {\it queryplan}).
%
<step> The {\it executor} has been modified to evaluate the {\it operator tree}
(i.e. the internal representation of the {\it having
qualification}) attached to the {\tt AGG} node and the results of the
{\it aggregation} are only considered if the evaluation returns {\tt true}.
\end{itemize}
%
In the following sections we will describe the changes made to every