lambda-DB: An ODMG-Based Object-Oriented DBMS

One of the key factors for OODB systems to successfully compete with relational systems as well as to meet the performance requirements of many non-traditional applications is the development of an effective query optimizer and a high-performance query evaluation engine. There are many aspects to the OODB query optimization problem that can benefit from the already proven relational query-optimization technology. However many key features of OODB languages present new and difficult problems not adequately addressed by this technology. These features include object identity, methods, encapsulation, subtype hierarchy, user-defined type constructors, large multimedia objects, multiple collection types, arbitrary nesting of collections, and nesting of query expressions.

The lambda-DB project at the University of Texas at Arlington aims at developing frameworks and prototype systems that address the new query optimization challenges for OODBs. We have already developed a theoretical framework for query optimization based on an effective calculus [3]. The system reported here is a fully operational ODMG 2.0 [2] OODB based on this framework. Our system can handle most ODL declarations and can process most OQL queries. lambda-DB is not ODMG compliant. Instead it supports its own C++ binding that provides a seamless integration between OQL and C++ with low impedance mismatch. It allows C++ variables to be used in queries and results of queries to be passed back to C++ programs. To do so, programs expressed in our C++ binding are compiled by a C++ preprocessor that performs query optimization at preprocessing time, rather than run-time, as it is proposed by ODMG. Therefore, all type errors are caught at compile time. The disadvantage of our approach is that, since optimization is done at compile time, the execution strategies may become suboptimal at run time due to updates or, worse, they may even become invalid if indexes are dropped. The obvious advantage of course is that our system is very fast. In addition to compiled queries, lambda-DB also supports execution of ad-hoc OQL queries at run-time by an OQL interpreter.

The lambda-DB system architecture is shown below:

The back-end of our OODB is the SDL (the Shore Data Language) layer of the SHORE [1] object management system, developed at the University of Wisconsin. ODL schemas are translated into SDL schemas in a straightforward way and are stored in the system catalog. The lambda-DB OQL compiler is basically a C++ preprocessor that accepts a language called lambda-OQL, which is C++ source code with embedded DML commands to perform transactions, queries, updates, etc. The preprocessor generates C++ code that contains calls to the lambda-DB evaluation engine. This C++ code is compiled and linked to the appropriate ODL module and it is then executed against the database. An OQL interpreter is actually a lambda-OQL program and thus, it has to be linked to ODL modules (because the interpreter may need to call methods, which are compiled C++ programs). We also provide a visual query formulation interface, called VOODOO, which generates OQL text which in turn is interpreted by the OQL interpreter.

Even though the implementation of our system is simple enough for other database researchers to use and extend, it is quite sophisticated since it employs current state-of-the-art query optimization technologies as well as new advanced experimental optimization techniques which we have developed through the years, such as query unnesting. The lambda-DB OODBMS is available as an open source software through the web at

Query Optimization in lambda-DB

Our OQL optimizer is expressed in a very powerful optimizer specification language, called OPTL, and is implemented in a flexible optimization framework, called OPTGEN, which extends our earlier work on optimizer generators. OPTL is a language for specifying query optimizers that captures a large portion of the optimizer specification information in a declarative manner. It extends C++ with a number of term manipulation constructs and with a rule language for specifying query transformations. OPTGEN is a C++ preprocessor that maps OPTL specification into C++ code.

The lambda-DB OQL optimizer proceeds in eight phases: 1) parsing of OQL queries and translation from OQL into calculus, 2) type checking, 3) normalization, 4) translation into algebra and query unnesting, 5) join permutation, 6) physical plan generation, 7) generation of intermediate evaluation code, and 8) translation from intermediate code into C++ code, or interpretation of the intermediate code.

Our calculus is called the monoid comprehension calculus [4]. It captures most features of OQL and is a good basis for expressing various optimization algorithms concisely. It is based on monoids, a general template for a data type, which can capture most collection and aggregate operators currently in use for relational and object-oriented databases.

One important component of our optimizer is a normalization system for reducing expressions to a canonical form. Normalization simplifies the subsequent optimization phases because it reduces the number of forms to be considered each time. In addition, normalization removes many forms of query nesting, a process also known as query decorrelation. All the other forms of query nesting are removed by a very powerful method [3], which generalizes many unnesting techniques proposed recently in the literature. In fact, our system is capable of removing any form of query nesting using a very simple and efficient algorithm. The simplicity of our method is due to the use of the monoid comprehension calculus as an intermediate form for OODB queries. The monoid comprehension calculus treats operations over multiple collection types, aggregates, and quantifiers in a similar way, resulting in a uniform way of unnesting queries, regardless of their type of nesting. Our unnesting algorithm is compositional, that is, the translation of an embedded query does not depend on the context in which it is embedded; instead, each subquery is translated independently, and all translations are composed to form the final unnested query. Our unnesting algorithm is efficient and easy to implement (it is only 160 lines of C++ code). In addition to query unnesting, lambda-DB converts path expressions into pointer joins between class extents (when is possible) and it uses information about 1:N class relationships to convert unnests into pointer joins between extents (by using the inverse relationship).

If the comprehension calculus was to be interpreted as is, the evaluation would proceed in a nested-loop fashion, resembling the semantics of the calculus, which gives an unacceptable performance for most non-trivial applications. Research in relational query optimization has already addressed the related problem of efficiently evaluating join queries by considering different join orders, different access paths to data, and different join algorithms. To effectively adapt this technology to handle our calculus, comprehensions must be expressed in terms of algebraic operators, which, eventually, will be mapped into physical execution algorithms, like those found in relational database systems. This translation is done in stages: queries in our framework are first translated into monoid comprehensions, which serve as an intermediate form, and then are translated into a version of the nested relational algebra that supports aggregation, quantification, outer-joins, and outer-unnests. At the end, the algebraic terms are translated into execution plans. We use both a calculus and an algebra as intermediate forms because the calculus closely resembles current OODB languages and is easy to normalize, while the algebra is lower-level and can be directly translated into the execution algorithms supported by DBMSs.

A very important task of any query optimizer is finding a good order to evaluate the query operations. In the context of relational databases, this is known as join ordering. lambda-DB uses a polynomial-time heuristic algorithm, called GOO, that generates a "good quality" order of the monoid algebra operators in the query algebraic form. GOO is a bottom-up greedy algorithm that always performs the most profitable operations first. The measure of profit is the size of the intermediate results, but it can be easily modified to use real cost functions. GOO is based on query graphs and takes into account both the output sizes of the results constructed in earlier steps and the predicate selectivities. It generates bushy join trees that have a very low total size of intermediate results.

After the best evaluation order of operators is derived, the algebraic form is mapped into an evaluation plan by a rule-based rewriting system. Our system considers the available access paths (indexes) and the available physical algorithms to generate different plans. During this phase, all alternative plans (for the derived order of operators) are generated and costed and the best plan is selected. Finally, each evaluation plan is translated into an intermediate evaluation code that reflects the signatures of the evaluation algorithms used in lambda-DB (described in the next section). This code can then be straightforwardly translated into C++ or interpreted by the lambda-DB interpreter.

The Evaluation Engine

The lambda-DB evaluation engine is built on top of SHORE [1]. The only layer of SHORE used in our implementation is SDL (the Shore Data Language) exclusively, because we believe it is more resilient to changes than the Shore Storage Manager and is easier to use. An alternative would have been to write our own value-added server on top of the storage manager. A lot of effort has been made to make the implementation of the evaluation engine as simple as possible without sacrificing performance. This required a very careful design. For example, one of our design requirements was to put all the evaluation algorithms in a library so that the query evaluation code would consist of calls to these algorithms. This sounds obvious enough and simple to implement, but it required some special techniques (described below) borrowed from the area of functional programming.

Algebraic operators, such as R |X|_{R.A=S.B} S, are intrinsically higher-order. That is, they are parameterized by pieces of code (ie. functions) that specify some of the operation details. For the previous join, the piece of code is the predicate R.A=S.B. If it was to be implemented in C++, the join operator could have been specified as:

Relation join ( Relation x, Relation y, bool (pred) (tuple,tuple) )
where pred is the address of the predicate function. The same holds for any evaluation plan operator, such as the nested-loop join operator. If a query is to be compiled into execution code with no run-time interpretation of predicates, it should make use of higher-order evaluation algorithms. The alternative (which is adopted by commercial systems) is to define the evaluation algorithms as kind of macros to be macroexpanded and individually tailored for each different instance of the evaluation operator in the query plan. For example, the nested-loop join would have to be a function with a `hole' in its body, to be filled with the predicate code. Then the entire code, the evaluation function and the predicate, is generated and inserted inside the query code. This is very clumsy and makes the development and extension of the evaluation algorithms very tedious and error-prone.

One very important issue to consider when writing evaluation algorithms is stream-based processing of data (sometimes called iterator-based processing or pipelining). We would like to avoid materializing the intermediate data on disk whenever it is possible. lambda-DB pipelines all evaluation algorithms. Instead of using threads to implement pipelining, as it is traditionally done in most systems, we developed a special technique borrowed from the area of lazy functional languages. Each of our evaluation algorithms is written in such a way that it returns a piece of data (one tuple) as soon as it constructs one. To retrieve all the tuples, the algorithm must be called multiple times. For example, the pipeline version of the nested-loop join will have the signature:

tuple nested_loop ( Stream sx, Stream sy, bool (pred) (tuple,tuple) )
where Stream is a stream of tuples equipped with standard operations, such as first and next. In contrast to the regular nested-loop algorithm, this algorithm exits when it finds the first qualified tuple (that satisfies pred). To pipeline an algorithm, we construct a suspended stream, which is a structure with just one component: an embedded function, which, when invoked, it calls the evaluation algorithm to construct one tuple. For example, to pipeline our nested-loop algorithm, we construct a suspended stream whose embedded function, F, is defined as:
tuple F () { return nested_loop(s1,s2,pred); }
where s1 and s2 are the streams that correspond to the join inputs and pred is the address of the predicate function. When a tuple is needed from a suspended stream, its embedded function is called with no arguments to return the next tuple. This is a clean and efficient way of implementing pipelining. This type of evaluation resembles lazy evaluation in functional programming languages. Here though we provide an explicit control over the lazy execution, which gives a better handle of controlling the data materialization on disk.

Currently, the lambda-DB evaluation engine supports table scan of a class extent, index scan, sorting, block nested-loop join, indexed nested-loop join, sort-merge join, pointer join, unnesting, nesting (group-by), and reduction (to evaluate aggregation and quantifications). We are planning to support hybrid hash join in the near future.

The intermediate evaluation code, which is generated from a query evaluation plan, is a purely functional program that consists of calls to the evaluation algorithms. The functional parameters of the calls (such as the predicate function of the nested-loop join), are represented as anonymous functions (lambda abstractions). If the intermediate code is compiled into C++, the lambda abstractions are translated into named C++ functions by a simple defunctionalization process. If the intermediate code is interpreted, each call to an evaluation algorithm is executed without much overhead because function addresses are stored into a vector and calls to functions are dispatched in constant time by retrieving the function directly from the vector. Lambda abstractions are interpreted by using the address of the interpreter itself as a parameter and by pushing the body of the lambda abstraction into a special stack. This form of dispatching makes the interpreter very compact (it is 400 lines of C++ code only) and very fast.

[1] M. Carey et al. Shoring Up Persistent Applications. In SIGMOD'94, pp 383-394.
[2] R. Cattell et al. The Object Database Standard: ODMG 2.0. Morgan Kaufmann, 1997.
[3] L. Fegaras. Query Unnesting in Object-Oriented Databases. In SIGMOD'98, pp 49-60.
[4] L. Fegaras and D. Maier. Towards an Effective Calculus for Object Query Languages. In SIGMOD'95, pp 47-58.

Last modified: 1/8/00 by Leonidas Fegaras