% File:     tml.tex
% Date:     24-Feb-1995
% Author:   Andreas Gawecki, Florian Matthes
%
\documentstyle[epsf,tml]{clmult01}

\pagestyle{myheadings}

\def\descriptionlabel#1{\hspace\labelsep \bf #1\hfil}

\title{Chapter 2.3.5\\Integrating Query and Program Optimization\\Using Persistent CPS Representations}

\author{Andreas Gawecki \and Florian Matthes}

\institute{Technical University Hamburg-Harburg\\Harburger Schlo{\ss}stra{\ss}e 20\\D-21071 Hamburg, Germany}


\begin{document}

\authorrunning{Andreas~Gawecki \and Florian~Matthes}
\titlerunning{Integrating Query and Program Optimization}

\maketitle

\abstract{This is a synopsis of \cite{GaMa96a}}


\section{Introduction and Motivation}

The traditional focus of database language research has been on high-level languages for data access and manipulation (query languages, trigger definition languages, 4th generation languages, script languages) or on implementation-oriented languages which capture the characteristic operations of a specific target system at hand (relational algebra, object algebra, structural recursion, \dots).

A closer look at tools working on such code representations like query and program optimizers reveals a large number of common tasks which at present are addressed with often icompatible technologies:

\begin{description} 
\item[Binding analysis:] Which entity (table, index, view, 
function, method, variable, etc.) is denoted by an identifier? Are there multiple references to the same entity?

\item[Identifier substitution] by a bound value or expression: View 
expansion, procedure or method inlining, constant folding, substitution of 
host programming language parameters, etc.

\item [Free variable analysis:] Does a variable appear in a query predicate? 
Does a procedure depend on global variables? Does a query contain 
programming language variables? Are there independent subexpressions? Which 
base relations do appear inside an integrity constraint?
\end{description}
%
After a decade of experience in our group with building integrated database 
programming languages \cite{Schm77a,MRS84,ScMa94} (see also synopsis in Chapter 2.1.2) and optimizers for their 
query languages \cite{JaSc82b,JKMS82,JaKo84,BJS86,ERMS91}, we made the radical decision to replace special-purpose representations for queries, programs and scripts with a single, expressive {\em intermediate\/} language. We thereby avoid incompatibilities and redundancies arising from the repeated implementation of the above functionality.

This intermediate language of the Tycoon System (see Chapter 2.1.4), the Tycoon Machine Language (TML), is presented in more detail in \cite{GaMa96a,GaMa94,Kira94}. Here, we only demonstrate its use for integrated program and query optimization in a persistent programming environment.


%-----------------------------------------------------------------------------


\section{Continuation Passing Style}

Continuation Passing Style (CPS) \cite{Appe92,KKRHPA86,Kels89,Tedo91,Gawe92a} is a powerful yet simple program 
representation technique.  The main advantage of CPS 
over other intermediate representations lies in the drastic reduction of the number of program constructs which have 
to be handled by the compile-time and run-time optimizer while preserving 
much of the structural information of the source language input. CPS has simple and clean semantics based on the $\lambda$-calculus.  TML 
is a CPS representation based on a call-by-value $\lambda$-calculus with store semantics.  A 
number of predefined {\em primitive procedures} operate on an implicit, hidden store.

TML supports higher-order languages, i.e.  languages where functions may 
take other functions as arguments (see Chapter 1.1.1 which describes the Tycoon Language).  For example, the selection operation 
$\sigma_p(R)$ in relational algebra takes two arguments, a range relation 
$R$ and a selection predicate $p$ where $p$ can be understood as a boolean 
function on the element type of $R$. 

Like terms in the $\lambda$-calculus, CPS terms provide an integrated 
representation of code fragments and their associated data bindings.  To 
meet the specific requirements of persistent languages and database 
languages, TML terms may contain simple literal values and object 
identifiers that denote arbitrarily complex objects (tables, indices, ADT 
values) in the persistent Tycoon object store (see Chapter 2.2.4).

By representing programs in CPS, many well-known program and algebraic 
query optimization techniques become special cases of a few simple and 
general $\lambda$-calculus transformations.  These transformations can be applied freely even in the presence of nonterminatating computations and/or
side-effecting calls to primitive procedures. This is due to the syntactical restrictions on TML terms which require actual parameters to function calls to be be constants, variables or abstractions. The complete abstract syntax of TML is defined by only four productions (literals, identifiers, abstractions and applications). Although the semantics of TML is based on the general $\lambda$-calculus, well-formed TML programs must satisfy a number of additional constraints which are preserved by the TML rewrite rules. These constraints and rewrite rules are given in the full paper.

In TML, most of the ``real work'' needed to implement source language 
semantics (e.g.  integer arithmetic, query evaluation) is factored out 
into primitive procedures which are not considered part of the intermediate 
language itself. By definition, each primitive calls 
exactly one of its continuation arguments tail-recursively, passing the 
result of its computation, if any.  For example, some arithmetic primitives 
take two continuations: the {\em normal} continuation which receives the 
calculated result, and an {\em exception} continuation which is invoked if 
the primitive fails due to overflow or division by zero. The set of primitive procedures used for the compilation of TL (see Chapter 1.1.1) and the information needed by the generic TML rewriting tools for additional (possibly language -specific) primitive procedures is described in the full paper).

%-----------------------------------------------------------------------------

\section{Analysis and Rewriting}

The TML optimizer is organized into two separate passes, namely a \e{reduction} pass and an 
expansion pass.  During the reduction pass, a number of generic rewrite 
rules are applied to the TML tree until no more rules are applicable.  
Termination is guaranteed because each of the rewrite rules reduces the 
size of the TML tree if it is applied.

The subsequent \e{expansion} pass tries to substitute bound 
$\lambda$-abstractions (procedures or continuations) at the positions where 
they are applied.  Effectively, this CPS transformation performs {\em 
procedure inlining} in terms of traditional compiler optimization or view 
expansion in database terminology.  The decision whether a given use of a 
bound abstraction is to be substituted is based on a heuristic cost model 
similar to the one described by \cite{Appe92}.

When one or more abstractions are substituted during the expansion pass, 
there usually is the opportunity to perform more reductions on the TML tree.  
Likewise, the reduction pass may reveal new opportunities to perform 
expansions, so the two passes are applied repeatedly until no more changes 
are made to the TML tree.  To guarantee the termination of this process 
even in obscure cases, a penalty is accumulated at each round of the 
reduction/expansion phases. 

The optimization rules are described in \cite{GaMa96a} in detail using the notation

\tmlrewritep{rule name}{(precondition)}{A}{B}

indicating that the TML expression $A$ may be rewritten to the TML 
expression $B$ if $precondition$ evaluates to true.

% ------------------------------------------------------------------------

\subsection{Optimization across Abstraction Barriers}

Effective optimization of highly modular 
languages and of database languages requires the analysis and rewriting of 
CPS terms that have been declared and compiled in separate scopes (logical 
schema, physical schema, query modules, embedded query, application 
program), at different times and most often by different users.

The Tycoon approach to overcome these abstraction barriers is (1) to wait until link or execution 
time, when all the bindings between the contributing parts of a persistent 
application are established, and (2) to keep sufficiently 
abstract code and binding information until that point in time.  Based on 
this approach it is rather straightforward to collect (via transitive 
reachability) all declarations that contribute to a given TML term (for 
example an embedded query) into a single scope (represented again as a TML 
term) and to invoke the TML optimizer to generate a globally optimized TML 
term.

\begin{figure}[htbp]
\epsfbild{TycoonPhases.epsf}{\epsfxsize=\columnwidth}
\caption{Compilation, optimization and evaluation in the Tycoon system}
\label{Fig:TycoonPhases}
\end{figure}

\noindent For each exported source code function \p{f} in a compilation unit, the 
compiler back end augments the generated code for \p{f} with a reference to 
a compact persistent representation of the TML tree (Persistent TML, 
PTML) for \p{f}.  At run-time, it is possible to map PTML back into TML, 
re-invoke the optimizer and code-generator, link the newly-generated code 
into the running program, and execute it (Fig.~\ref{Fig:TycoonPhases}).

The mapping from PTML back to TML also returns the set of R-value bindings 
([identifier, OID] pairs) established at runtime.  These bindings 
correspond to free variables (module names, database names, table names, 
function names, constant names, etc.) in the source text and they 
naturally give rise to context-dependent, inter-procedure and inter-module 
optimizations. The full paper describes this process in more detail.
     

%-----------------------------------------------------------------------------

\section{Towards Integrated Program and Query Optimization}

The syntax of many modern query languages
allows programming language variables, function and method calls to
appear in the \k{select} and \k{where} clauses of SQL statements.
Furthermore, the body of element-at-a-time iterators (\k{for} \k{each}
statements) and of database triggers may refer to programming language
statements.  User-defined data types lead to further interaction between
query expressions and programming language expressions.

Since traditional query optimizers do not have access to an abstract
representation of these program fragments, they have to work under
worst-case assumptions (dependencies between subexpressions,
side-effects), or they have to rely on programmer-supplied information
(commutativity, idempotence, side-effects) which is difficult to keep
consistent in large, long-lived systems.  In particular, current query
representations do not cover any form of control flow (conditionals, case
analysis, loops, exceptions) which is ``inherited'' through embedded
programming language expressions.

\begin{figure}[htbp]
\epsfbild{EmbeddedQueryOpt.epsf}{\epsfxsize=\columnwidth}
\caption{Embedded Query Optimization}
\label{Fig:EmbeddedQueryOpt}
\end{figure}

\noindent 
Given an integrated database language where user-defined code and query
expressions are fully integrated \cite{MaSc91b}, query and program
optimization have to interact closely (see Fig.~\ref{Fig:EmbeddedQueryOpt}):
Whenever the program optimizer encounters an embedded query construct
like a set-at-a-time (bulk) query or update, an element-at-a-time
iterator, or a view definition, it invokes the query optimizer on the
respective TML subtree with a TML environment which describes the global
bindings (free variables) for that expression.  Similarly, the query
optimizer invokes the program optimizer to analyze and optimize nested
programming language expressions which appear in query constructs (target
list, selection predicate, iterator body).  Again, binding information
for free variables (e.g., range variables in queries or loop control
variables in \k{for each} iterators) is passed along with the respective
TML subtree.  Recursive declarations of functions, values, or queries are
represented uniformly through applications of the fixpoint combinator $Y$
and do \e{not} lead to repeated traversals of TML terms.

\begin{acknowledgement}
This research was supported by ESPRIT Basic Research, Project FIDE,
\#6309.
\end{acknowledgement}

\small

\small
\bibliographystyle{plain}
\bibliography{../dbis-macros,../florian}

\end{document}
