Should Morel's collection types indicate that a collection is sorted, unique, or has repeatable iteration order?

[julianhyde]

Should Morel's collection types indicate that a collection is sorted, unique, or has repeatable iteration order? The relational model and functional programming languages both have collection types, but there is a mismatch. Relations are unordered (unless a query has an ORDER BY clause), programming language lists are ordered. Uniqueness is complicated (relations are unique in Datalog but not in SQL, and if you choose a unique collection such as Java's HashSet or TreeSet it has implications for iteration order).

We propose to add a multiset type to Morel, a new clause unordered. We do not propose to deal with uniqueness or sort order at this time.

Specifically:

1. Add a new collection type, multiset, an unordered equivalent of list.
2. A from expression and a join clause can iterate over both list and multiset collections.
3. The result of a from expression is a list if it ends with order followed by zero or more yield or where clauses, or if it reads from a list followed by by zero or more yield or where clauses; multiset otherwise.
4. Add a clause, unordered.

Remarks:

• Like list, multiset has a length method that returns the number of elements. You should not assume that its running time is O(1).
• multiset does not have the nth (l, i), take (l, i) or drop (l, i) methods of list because the ith element is not defined
• Tables in external databases are modeled as multiset. (Nullable columns become optional, since Morel has no null value.)
• An order clause returns an ordered collection even if the sort-keys are not exhaustive. In particular, order with no arguments returns a list whose order is undefined but whose order will be the same each time the list is read.
• We have not specified whether order is stable. We will probably declare that it is not stable.
• Assigning a nondeterministic query to a list does not make it deterministic. If you run it several times, the order of items in the list may change.
• We do not propose types for unique or sorted collections. (Contrast with Java interfaces Set and SortedSet, which do precisely that.) It is important to know if a collection's elements are unique or sorted, the key(s) or sort key of a collection, and if there are functional or referential dependencies, but this should be done using constraints rather than by the type system.
• Should there be a function or clause that returns the elements of a list with ordinal? (Compare SQL UNNEST WITH ORDINAL.)
• Should there be a 'zip join'?

Examples of ordered and unordered queries.

(*) Ordered
from e in scott.emp order by empno;

(*) Ordered (not exhaustively, because salary is not unique).
from e in scott.emp order e.sal;

(*) Ordered (not exhaustively, because there are no sort keys).
from e in scott.emp order;

(*) Ordered (because 'order' creates ordering and 'yield' does not destroy it)
from e in scott.emp order e.empno yield {e.ename};

(*) Unordered (because 'group')
from e in scott.emp group e.deptno compute avg of e.sal;

(*) Not ordered (because `scott.emp` is a multiset)
from e in scott.emp;

(*) Ordered (because `emps` is a list)
val emps = [{empno: 10, ename: "Shaggy"}, {empno: 20, ename: "Scooby"}];
from e in emps;

(*) Unordered (because 'unorder')
from e in emps unorder;

(*) empnos will have type 'int multiset'
val empnos = from e in emps yield e.empno unorder;

Rationale

Let's review collection types in various languages.

Standard ML

Standard ML's main collection type is list. A list's iteration order is defined and is deterministic. If you add elements in a certain order, iterations will always appear in the same order. It's as if each item had a zero-based ordinal; it doesn't, but there is more information in a list than an unsorted collection containing the same elements.

A list can contain duplicate elements.

Like all collections we will be discussing, lists are finite and immutable. Size can be determined in constant time.

There is also vector, which is similar to list but whose sub (v, i) function allows constant time access to the ith element.

Java

Java has the following collection types. All are finite and have a constant-time size operation. Each has mutable and immutable implementations.

• List has a defined order and may contain duplicates.
• Set does not have a defined order and may not contain duplicates.
• SortedSet has a deterministic order (determined by its comparator) but the creator of the SortedSet cannot dictate the order.

Relational

In the academic relational model (and Datalog), relations do not contain duplicates, are finite and immutable, have no deterministic iteration order.

Size is not assumed to be constant-time (but that's an implementation concern, and there may be a materialized view or other data structure that computes size quickly).

Because iteration is not deterministic, there is no operation to get the ith element.

The industrial relational model (used by SQL) is the same as the academic relational model, except that relations may contain duplicates.

Comparing the approaches

In the relational model, not everything we know about the data is encoded as part of the type. For example, given the relation employees (empno, ename, deptno, dname) we may know that empno is primary key, and that deptno functionally determines dname. We know that this relation is unique (because of the primary key) but iteration order is still nondeterministic.

In the relational model (including in the SQL standard), sorting is generally performed last, just before outputting to a screen. Iteration order remains unknown until that point. (There is one important exception: the ARRAY column type has a determined order.)

In our proposal, a Morel query returns an ordered collection in similar circumstances to a relational query. A SQL query with an ORDER BY clause is sorted, and a Morel query ending with order returns a list.

Relational systems make much use of constraints, and constraints are separate from schema (type system). Likewise, we intend to add constraints to Morel, and these will be used to represent sort-order, uniqueness and functional dependencies, and intra-row constraints (e.g. job = 'SALES' orelse commission = 0). We intend to allow constraints to be explicitly declared, but will also be deduced (e.g. uniqueness following a group clause, or intra-row constraints following a where clause), may be checked at run time (using something like assert), and the programmer can check that they can be deduced (using a prove keyword that is analogous to assert but works at compile time).

[julianhyde]

Let's extend the proposal to address the remarks:

Should there be a function or clause that returns the elements of a list with ordinal? (Compare SQL UNNEST WITH ORDINAL.)
Should there be a 'zip join'?

We propose that there is an ordinal value available in a yield clause of a list but not a multiset. (It is available in some other clauses, including where and order but not including join.)

ordinal is declared in the Relational struct:

val ordinal: int

but its value is not constant. Its value changes from one row to the next, and you will get a compilation error if you access it from an invalid location (such as the yield clause of a multiset).

ordinal is not a keyword, and therefore it is overridden by the usual scoping rules. For example,

let
  val ordinal = 5
in
  ordinal + 1
end

returns 6 as you would expect. And a record can have an ordinal field:

let
  val r = {ordinal = 5, offset = 1}
in
  r.ordinal + r.offset
end

To implement ordinal in yield, we would use a function similar to Vector.mapi. (There is no List.mapi in the Standard Basis Library, apparently for no good reason.)

To implement ordinal in clauses such as where, order, group, we would insert an upstream yield {_ordinal = ordinal, <all fields}}. Examples:

from i in [3,1,4,1,5,9,2,6,5,3];
> val it = [3,1,4,1,5,9,2,6,5,3] : int list
from i in [3,1,4,1,5,9,2,6,5,3] yield {i,ordinal};
> val it =
>   [{i=3,ordinal=0},{i=1,ordinal=1},{i=4,ordinal=2},{i=1,ordinal=3},
>    {i=5,ordinal=4},{i=9,ordinal=5},{i=2,ordinal=6},{i=6,ordinal=7},
>    {i=5,ordinal=8},{i=3,ordinal=9}] : {i:int, ordinal:int} list
from i in [3,1,4,1,5,9,2,6,5,3] where i > ordinal;
> val it = [3,4,5,9];

If ordinal is used in different clauses, its value is computed in each clause separately:

from i in [3,1,4,1,5,9,2,6,5,3] where i > ordinal yield {i,ordinal};
> val it =
>   [{i=3,ordinal=0},{i=4,ordinal=1},{i=5,ordinal=2},{i=9,ordinal=3}]
>   : {i:int, ordinal:int} list

Queries on unordered lists (multiset) are sometimes more efficient than queries on ordered lists (list). For example, they can be executed in parallel streams. Use of ordinal forces serial execution. Notes on serial/parallel execution:

• If the compiler can safely push ordinal upstream, and assign it to a field, then downstream can be parallelized. ordinal cannot be pushed upstream through certain clauses such as where.
• If the result of the query is a list, the compiler may parallelize the computation using multiset but it must use a merge-sort to convert the parallel streams into a list. A pipeline 'step1 step2 step3' becomes 'yield {_ordinal=ordinal, } step1 step2 step 3 order _ordinal yield {}`.

Zip join can be expressed by assigning ordinal to a field and joining on that:

val names = ["shaggy", "scooby", "velma"];
val ages = [28, 5, 22];
from n in (from name in names yield {name, ordinal})
    join a in (from age in ages yield {age, ordinal})
    on n.ordinal = a.ordinal
 yield {n.name, a.age};

The compiler should be smart enough to use an O(n) join algorithm, similar to ListPair.zip.

[julianhyde]

Most of the ideas in this discussion have been implemented in Morel 0.7:

• ordinal was added in Add unorder step and ordinal expression #276
• unorder step was added in Add unorder step #277
• Ordered queries were added in Ordered and unordered queries #273
• The bag type and Bag structure were added in Add a bag type, and Bag structure, to represent unordered collections with duplicates allowed #235

I also wrote an article Ordered and unordered data.