Abstract: In an extensible database system, evaluation of a query plan is done in cooperation between a collection of operator implementation functions and a component of the DBMS that we call the query processor. Basically, the query processor constructs an operator tree for the query plan and then calls an evaluator function which traverses the tree, calling the operator functions in each node. This seemingly simple strategy is complicated by the fact that operator functions must be able to call for the evaluation of parameter expressions (e.g. predicates), and must be able to process streams of objects in a pipelined manner.
Although query processing along these lines is implemented in most database systems, and certainly in all extensible database systems, the details of programming the parameter passing, organizing the interaction between stream operators, etc. are tricky, and seem to be buried in the code of the respective systems. We are not aware of any simple, crisp, clear published exposition of how one could implement such a query processor. This is what the paper offers.
Moreover, we feel the solution presented here is particularly simple, elegant, and general. For example, it is entirely independent from the data model being implemented, admits arbitrary parameter functions, and allows one to mix freely stream operators and other operators. The construction of the operator tree, shown in the paper, includes complete type checking and resolution of overloading. The query processor has been implemented within the Secondo system; the source code is available.
Keywords: Extensible database systems, query processor, operator tree, streams, second-order signature, type checking, Secondo
Published: 10th Int. Conf. on Database and Expert System Applications (DEXA'99), LNCS 1677, Springer Verlag, 66-87, 1999.