The OQL Physical Algebra

The following are the physical plan operators used by ODB:

• TABLE_SCAN( 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( extent_name, range_variable, predicate, index_name, sort_order ): Same as TABLE_SCAN, but it uses the index index_name to deliver the tuples ordered by sort_order.
• 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( 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=left, then it behaves like an left-outer join (it concatenates the left tuple with null values), if keep=right it behaves like a right-outer join, while if keep=none, it is a regular join.
• MERGE_JOIN( left_plan, right_plan, predicate, keep, 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.
• SORT( plan, sort_order ): Sorts a plan by the sort_order.
• UNNEST( 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=true, then the tuple is padded with a null value.
• NEST( monoid, plan, variable, head, groupby, nestvars, 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) and with the values of the nestvars variables.
• GROUP_BY( monoid, plan, range_variable, head, groupby, nestvars, predicate ): Same as NEST, but plan must be ordered by groupby (the monoid must be commutative).
• MERGE( monoid, left_plan, right_plan ): Merges the (union-compatible) streams of the input plans.
• MAP( plan, variable, function ): extends the input stream of the plan with the binding of the variable to the result of the function application to the input tuples.