# 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.