Chapter 2.3.5 Integrating Query and Program Optimization Using Persistent CPS Representations

Andreas Gawecki and Florian Matthes

Technical University Hamburg-Harburg Harburger Schloßstraße 20 D-21071 Hamburg, Germany

Summary This is a synopsis of [6]

1. 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, …).

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: Binding analysis: Which entity (table, index, view, function, method, variable,

etc.) is denoted by an identifier? Are there multiple references to the same entity?

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

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?

After a decade of experience in our group with building integrated database programming languages [15, 13, 16] (see also synopsis in Chapter 2.1.2) and optimizers for their query languages [9, 8, 7, 2, 3], we made the radical decision to replace special-purpose representations for queries, programs and scripts with a single, expressive 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 [6, 5, 11]. Here, we only demonstrate its use for integrated program and query optimization in a persistent programming environment.

2. Continuation Passing Style

Andreas Gawecki, Florian Matthes

Continuation Passing Style (CPS) [1, 12, 10, 17, 4] 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 λ-calculus. TML is a CPS representation based on a call-by-value λ-calculus with store semantics. A number of predefined 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 σ_{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 λ-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 λ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 λ-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 normal continuation which receives the calculated result, and an 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).

3. Analysis and Rewriting

The TML optimizer is organized into two separate passes, namely a 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 expansion pass tries to substitute bound λ-abstractions (procedures or continuations) at the positions where they are applied. Effectively, this CPS transformation performs 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 [1].

Integrating Query and Program Optimization

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 [6] in detail using the notation

(precondition) :
A \underline{rule name}▷ B

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

3.1 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.

Fig. 3.1. Compilation, optimization and evaluation in the Tycoon system

For each exported source code function f in a compilation unit, the compiler back end augments the generated code for f with a reference to a compact persistent representation of the TML tree (Persistent TML, PTML) for 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. 3.1).

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.

4. 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 select and where clauses of SQL statements. Furthermore, the body of element-at-a-time iterators (for 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.

Fig. 4.1. Embedded Query Optimization

Given an integrated database language where user-defined code and query expressions are fully integrated [14], query and program optimization have to interact closely (see Fig. 4.1): 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 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 not lead to repeated traversals of TML terms.

Acknowledgement This research was supported by ESPRIT Basic Research, Project FIDE, #6309.

References

1. A. Appel. Compiling with Continuations. Cambridge University Press, 1992.

2. S. Böttcher, M. Jarke, and J.W. Schmidt. Adaptive predicate managers in database systems. In Proceedings of the Twelfth International Conference on Very Large Databases, Kyoto, Japan, 1986.

3. J. Eder, A. Rudloff, F. Matthes, and J.W. Schmidt. Data construction with recursive set expressions in DBPL. In Proceedings of the Kiev East/West Workshop on Next Generation Database Technology, volume 504 of Lecture Notes in Computer Science, April 1991.

4. A. Gawecki. An optimizing compiler for Smalltalk. Bericht FBI-HH-B-152/92, Fachbereich Informatik, Universität Hamburg, Germany, September 1992. (In German).

5. A. Gawecki and F. Matthes. The Tycoon machine language TML: An optimizable persistent program representation. FIDE Technical Report FIDE/94/100, Fachbereich Informatik, Universität Hamburg, Germany, August 1994.

6. A. Gawecki and F. Matthes. Exploiting persistent intermediate code representations in open database environments. In Proceedings of the Fifth Conference on Extending Database Technology, EDBT’96, volume 1057 of Lecture Notes in Computer Science, Avignon, France, March 1996. Springer-Verlag.

7. M. Jarke and J. Koch. Query optimization in database systems. ACM Computing Surveys, 16(2):111–152, 1984.

8. M. Jarke, J. Koch, M. Mall, and J.W. Schmidt. Query optimization research in the database programming languages (DBPL) project. IEEE – Data Engineering, pages 11–14, September 1982.

9. M. Jarke and J.W. Schmidt. Query processing strategies in the Pascal/R relational database management system. In Proceedings of the ACM-SIGMOD International Conference on Management of Data, Orlando, Florida, 1982.

10. R.A. Kelsey. Compilation by program transformation. Technical report, Yale University, Department of Computer Science, May 1989.

11. P. Kiradjiev. Dynamic optimization in CPS-based intermediate languages. Master’s thesis, Fachbereich Informatik, Universität Hamburg, Germany, December 1994. (In German).

12. D. Kranz, R. Kelsey, J. Rees, P. Hudak, J. Philbin, and N. Adams. ORBIT: An optimizing compiler for Scheme. ACM SIGPLAN Notices, 21(7):219–233, July 1986.

13. M. Mall, M. Reimer, and J.W. Schmidt. Data selection, sharing and access control in a relational scenario. In M.L. Brodie, J.L. Myopoulos, and J.W. Schmidt, editors, On Conceptual Modelling. Springer-Verlag, 1984.

14. F. Matthes and J.W. Schmidt. Bulk types: Built-in or add-on? In Database Programming Languages: Bulk Types and Persistent Data. Morgan Kaufmann Publishers, September 1991.

15. J.W. Schmidt. Some high level language constructs for data of type relation. In Proceedings of the ACM-SIGMOD International Conference on Management of Data, Toronto, Canada, August 1977.

16. J.W. Schmidt and F. Matthes. The DBPL project: Advances in modular database programming. Information Systems, 19(2):121–140, 1994.

17. D. Teodosiu. HARE: An optimizing portable compiler for Scheme. ACM SIG-PLAN Notices, 26(1):109–120, January 1991.