Extending Iterators for Advanced Query Execution

Today's commercial relational database systems use tree-shaped execution plans. The evaluation techniques for these plan are well understood and have been refined over the last decade. However, for queries that contain disjunctive predicates, using the more general class of direct acyclic graphs and splitting data streams can be beneficial. Unfortunately, the iterator based evaluation techniques used for tree-shaped plans do not apply to this case. Iterators implement a breadth first search providing full encapsulation where operators communicate by answered requests in synchronous manner. In this paper we develop an extension of the conventional iterator based evaluation technique. We introduce request handles that add context information to the data requests which allows for arbitrary plan topologies including cycles. The original problem of evaluating plans with operators that split data streams can then be solved by mere rewriting of the execution plan.