summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/utthesis/ICDE-11/p2v.tex
blob: d8c344e3024d987403752bd9acb7e89c3a191255 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
\section{The P2V pre-processor}
\label{sec:ptov}

In Section~\ref{sec:intro}, we enumerated the four primary goals of
Prairie, viz., uniformity in operator and algorithms; uniformity in
properties; uniformity in property-transformations; and efficient
generation of Prairie optimizers.  The first three goals are driven by
the need for conceptual simplicity; however, they alone do not
necessarily generate efficient optimizers.  The P2V pre-processor
ensures that efficient optimizers can be realized from Prairie
specifications, by translating them to the Volcano framework and then
generating an optimizer by compiling with the Volcano search engine.
This Prairie optimizer-generator paradigm is shown schematically in
Figure~\ref{fig:ptovmodel}.  The pre-processor itself is 4500 lines of
\texttt{flex} and \texttt{bison} code.  In this section, we briefly
describe the pre-processor steps and explain why the Prairie-to-Volcano
transformation is non-trivial.  A more detailed description of the
pre-processor is given in \cite{Das94}.

\begin{centeredfigure}
\myshadowbox
{
\scriptsize
\begin{centeredinfullminipage}
\begin{center}
\psset{unit=6mm}
\psset{nodesep=3pt}
%\begin{pspicture}(-1.0,-0.5)(10,9.0)
\begin{pspicture}(-1.0,-0.5)(8,9.0)
\pspolygon[doubleline=true](1,1.5)(7,1.5)(7,7.5)(1,7.5)
\pspolygon[fillcolor=white,fillstyle=solid](2,8)(6,8)(6,9)(2,9)
\rput(4,8.5){\psframebox*{Prairie Rule Set}}
\psline[border=2pt]{->}(4,8)(4,7)
\pspolygon[doubleline=true](2,6)(6,6)(6,7)(2,7)
\rput(4,6.5){P2V Pre-processor}
\psline[border=2pt]{->}(4,6)(4,5)
\pspolygon[fillcolor=gray,fillstyle=solid](2,4)(6,4)(6,5)(2,5)
\rput(4,4.5){\psframebox*{Volcano Rule Set}}
\psline[border=2pt]{->}(4,4)(4,3)
\pspolygon[doubleline=true](2,2)(6,2)(6,3)(2,3)
\rput(4,2.5){\begin{tabular}{c} Volcano \\ Optimizer-Generator \end{tabular}}
\psline[border=2pt]{->}(4,2)(4,1)
\pspolygon[fillcolor=gray,fillstyle=solid](2,0)(6,0)(6,1)(2,1)
\rput(4,0.5){\psframebox*{Query Optimizer}}
\rput[r](1,0.5){Operator Tree}
\psline[border=2pt]{->}(1,0.5)(2,0.5)
\psline[border=2pt]{->}(6,0.5)(7,0.5)
\rput[l](7,0.5){Access Plan}
\end{pspicture}
\end{center}
\end{centeredinfullminipage}
}
\caption{The Prairie optimizer-generator paradigm.  Double-boxed modules
         represent software generators, shaded boxes represent
         generated programs.  The outermost double-boxed portion
         denotes the Prairie optimizer generator.}
\label{fig:ptovmodel}
\end{centeredfigure}

The specification of an optimizer in Volcano consists of a set of
transformation rules (called ``trans\_rules'') and implementation rules
(called ``impl\_rules''), a set of properties, and some support
functions.  The join associativity trans\_rule
(cf.\ Figure~\ref{fig:associativity}) in Volcano is as follows\footnote{There
are conditions and actions associated with Volcano rules that are not
shown here.}:
\begin{eqnarray*}
\scriptscriptstyle
& &
{\scriptstyle
(\text{JOIN} \ \text{?op\_arg5}
  \ ((\text{JOIN} \ \text{?op\_arg4} \ (?1 \ ?2)) \ 
     ?3))} \\
& &
\rulespace
{\scriptstyle -\!\!>}
{\scriptstyle
(\text{JOIN} \ \text{?op\_arg7}
  \ (?1 \ 
     (\text{JOIN} \ \text{?op\_arg6} \ (?2 \ ?3))))}
\end{eqnarray*}
The important point to note is the use of \emph{operator arguments}
(denoted by ``op\_arg'' in rules); these arguments contain properties
used in the rule's actions, but unlike Prairie, they do not contain
\emph{all} the properties of an operator tree node.  There are other
property classes, like algorithm argument, logical property, system
property, physical property, and cost.  Thus, while Prairie uses a
uniform descriptor to encode properties, Volcano partitions the
properties into different classes.  The P2V pre-processor partitions a
Prairie descriptor into the different property classes required by
Volcano.  This is a non-trivial task, since it requires parsing the
Prairie rules and their actions.

Impl\_rules in Volcano defer most of the actions associated with the
rules to support functions.  Each algorithm has four support functions
associated with it.  A Prairie specification, on the other hand,
contains all the actions in the corresponding rule.  The P2V
pre-processor parses a Prairie I-rule, and automatically generates all
the Volcano support functions from the rule.  This is also a complex
process, since it depends partly on the partitioning of properties
mentioned in the last paragraph, and also because it requires
relocating pieces of code from Prairie rules to Volcano support
functions.

The third salient feature of a Volcano specification is the presence of
implicit, or hidden, algorithms, called \emph{enforcers}.  In Prairie,
all algorithms are explicit.  Consider, for example, the Merge\_sort
algorithm in Figure~\ref{fig:msort}.  In a Volcano specification, this
algorithm would be classified as an enforcer, since it enforces the
sortedness property.  The P2V pre-processor determines the Prairie
algorithms that are functionally Volcano enforcers, and deletes the
corresponding Prairie rules to generate the Volcano specification.
This requires the pre-processor to migrate the (deleted) rule's actions
to Volcano support functions.

The P2V pre-processor also generates a set of compact Volcano rules by
merging Prairie rules whenever possible.  Consider, for example, the
following set of rules in Prairie:
\begin{eqnarray*}
{\scriptstyle \text{JOIN}(S_1, S_2):\mathbf{D_3}}
  & \Longrightarrow &
{\scriptstyle \text{JOPR}(\text{SORT}(S_1):\mathbf{D_4},
        \text{SORT}(S_2):\mathbf{D_5}):\mathbf{D_6}} \\
{\scriptstyle \text{SORT}(S_1):\mathbf{D_2}}
  & \Longrightarrow &
{\scriptstyle \text{Null}(S_1:\mathbf{D_3}):\mathbf{D_4}} \\
{\scriptstyle \text{JOPR}(S_1, S_2):\mathbf{D_3}}
  & \Longrightarrow &
{\scriptstyle \text{Nested\_loops}(S_1:\mathbf{D_4}, S_2):\mathbf{D_5}}
\end{eqnarray*}
The first rule is a T-rule, and the next two are I-rules.  The P2V
pre-processor combines the above set of Prairie rules into a single
I-rule,
\begin{eqnarray*}
{\scriptstyle \text{JOIN}(S_1, S_2):\mathbf{D_3}}
 & \Longrightarrow &
{\scriptstyle \text{Nested\_loops}(S_1:\mathbf{D_4}, S_2):\mathbf{D_5}}
\end{eqnarray*}
and then translates it into a single Volcano impl\_rule.