lambda-DB: System Overview

A lot of effort has been made to make the implementation as simple as possible without sacrificing performance. This required a very careful design. The language chosen for the implementation was C++ enhanced with automatic garbage collection (GC), even though a functional language, such as SML, would have been a better choice. The only part of Shore used in this implementation was 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. Unfortunately, the SDL code is currently integrated into the lambda-DB code, which makes it difficult to switch to a different back-end.

The following is a tour over the lambda-DB source code. The *.gen files contain OPTL code, which is processed by OPTGEN (an OPTimizer GENerator). OPTGEN is a tool for writing query optimizers for both object-relational and object-oriented databases. It is based on a highly declarative language, OPTL, in which you can specify query transformation rules as rules in an attribute grammar. You can find more information in the following manuals:

• Overview of OPTGEN and OPTL
• OPTL Reference Guide
• Optimizer Specification in OPTL
• OPTL Rule Syntax

• The monoid comprehension calculus
• The monoid algebra
• The physical plan operators
• Examples of query translation

The optimizer consists of the following stages:

1. parsing OQL queries (files oql.y and oql.lex).
2. translation of OQL queries into monoid comprehensions (file translator.gen).
3. checking the calculus for type correctness (file typecheck.gen).
4. algebraic rewriting, including normalization of comprehensions and materialization of path expressions into pointer joins (file optimizer.gen).
5. query unnesting and translation of the monoid comprehension calculus into the monoid algebra (file optimizer.gen).
6. join permutation using a cost-based heuristic (file cost_optimizer.gen).
7. physical plan generation using a rule-based cost-driven system (file rule_based_opt.gen).
8. generation of intermediate code (file code_generator.gen).
9. translation of intermediate code into C++ code (file C++_generator.gen).
10. interpretation of the intermediate code (file interpreter.gen).

The physical plans generated by the query optimizer are translated into C++ code (last stage of the optimizer). The C++ code consists of calls to a library of evaluation functions. Since the physical plan operators are higher-order in nature, most evaluation functions are higher-order too (ie. they are C++ functions that take functions as parameters). The query evaluation is done in a pipelined fashion (i.e. streams are materialized in the secondary storage only when necessary). Components:

1. the interface to the evaluation library (file eval.h).
2. the SDL specification of streams and other runtime data (file runtime.sdl).
3. the implementation of the evaluation functions (file eval.cc).

This part is very sketchy. Eventually, we will use the standard ODMG meta classes. Components:

1. parsing ODL specifications (files odl.y and odl.lex).
2. SDL specification of the ODL catalog (files type.sdl).
3. manipulation of ODL specifications: mapping ODL to SDL and updating the system catalog (files odl.gen).