The OQL Physical Plan Operators

The following are the physical plan operators used by lambda-DB:

• TABLE_SCAN( monoid, extent_name, range_variable, predicate ): Implements the OQL query: select * from range_variable in extent_name where predicate. It creates a stream of tuples, where each tuple has only one component, range_variable, whose value is an object from the extent.

• INDEX_SCAN( monoid, extent_name, range_variable, predicate, index_name, low, high ): Same as TABLE_SCAN, but it uses the index index_name to deliver all the tuples between (and including) the keys low and high.

• REDUCE( monoid, plan, variable, head, predicate ): For each tuple of the input stream of plan that satisfies predicate, it evaluates the head. Then it reduces the entire stream to a value (a stream of one value bound to variable) or a collection (a stream of tuples, where each tuple binds variable to the value of head), depending on the output monoid.

• NESTED_LOOP( monoid, left_plan, right_plan, predicate, keep ): Implements the relational join operator. It concatenates the tuples in the input streams of the left and right plans if the satisfy the predicate. If keep=none, the join is a regular join. Otherwise, it is a generalization of the left outer join and keep specifies which variables to keep from the left stream. For example, if keep = pair(e,d), then if all the tuples from the left stream that have equal e and d values are not joined with any tuple from the right stream, then this operator delivers one of these tuples concatenated with null values. If keep contains all the variables of the left stream, then this outer join is the same as the left-outer join in relational databases.

• INDEXED_LOOP( monoid, left_plan, right_plan, predicate, keep, index_name, key ): Same as NESTED_LOOP but it uses indexing to retrieve tuples from the right (inner) stream. index_name is the name of the index while key contains the index attributes.

• MERGE_JOIN( monoid, left_plan, right_plan, predicate, keep, left_key, left_sort_order, right_sort_order ): Same as NESTED_LOOP, but it requires the left plan be sorted by left_sort_order and the right plan by right_sort_order. It merges the two streams using the sort orders. It requires that at least one of the streams has the sort order as a key (determined by the boolean value left_key).

• SORT( plan, sort_order ): Sorts a plan by the sort_order.

• UNNEST( monoid, plan, variable, path, predicate, keep ): For each tuple in the the input stream of plan, it concatenates the binding of variable to all possible values of path, filtering out those tuples that do not satisfy the predicate. If there are no values, or no value satisfies the predicate, and keep is note equal to none, then the tuple is padded with a null value.

• NEST( monoid, plan, variable, head, groupby, predicate ): It groups the input stream of plan by the variables in groupby. Then, it extents the input stream of plan with the binding of variable to the value REDUCE(monoid,plan,variable,head,predicate).

• MAP( monoid, plan, variable, pred, keep, path ): It maps the path to every tuple of the input stream and concatenates the result to the tuple. It is mostly used to dereference OIDs.

• MERGE( monoid, left_plan, right_plan ): Merges the (union-compatible) streams of the input plans.