Array functions and order preservation

[zeen]

Arrays are an ordered data structure. For array functions that generate new arrays based on existing ones, the documentation isn't clear on whether there's any order that can be assumed for the result.

Functions of interest:

• array_intersect
• array_except
• array_union
• array_distinct

Based on my testing, order seems to be preserved. For the one or more input arrays being operated on, output ordering is based on the input arrays' order, with the first array's order having priority over the second's, etc.

e.g., for array_intersect(array['a', 'b', 'c'], array['d', 'c', 'b']) the result is consistently ['b', 'c'], and not ['c', 'b']. Can this behavior be relied upon?

The following also lack any explicit statement in the docs, but it would be highly surprising if we couldn't assume the order of the returned array is based on the input array(s):

• array_remove
• concat
• combinations
• filter

[zeen]

This somewhat also boils down to whether the API contract for intersect, except, union, etc is that of sets (unordered) or arrays. These functions return without duplicates (which is more along the lines of sets), but are array functions.

The tests currently seem to assume a specific output order, e.g.:

presto/presto-main/src/test/java/com/facebook/presto/operator/scalar/TestArrayIntersectFunction.java

Line 65 in 2ad67dc

assertFunction("array_intersect(ARRAY[CAST('x' as VARCHAR), 'x', 'y', 'z'], ARRAY['x', 'y', 'x'])", new ArrayType(VARCHAR), ImmutableList.of("x", "y"));

[rongrong]

Conceptually these are actually set functions implemented on an array. So yes, order will be somewhat preserved depending on the underlying implementation. But I'd say this is more of a side effect on implementation details rather than a contract.

[zeen]

The Apache Spark project also added the array_intersect function based on Presto.

Jira: https://issues.apache.org/jira/browse/SPARK-23913
PR: apache/spark#21102

They do test for order in the specific implementation:

https://github.com/apache/spark/blob/0494dc90af48ce7da0625485a4dc6917a244d580/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/CollectionExpressionsSuite.scala#L1785-L1786

But the PR and commit message include Note: The order of elements in the result is not defined.

[zeen]

It'd be great if the docs explicitly stated that order is undefined.

If order is undefined, but we needed to preserve it in a query, then:

-- undefined order without dups:
array_intersect(a, b)
array_except(a, b)
array_union(a, b)

-- defined order with dups:
filter(a, x -> contains(array_intersect(a, b), x)
filter(concat(a, b), x -> contains(array_union(a, b), x)
concat(a, b)

To distinct results in an ordered manner, something like this would work:

reduce(
    a,
    null,
    (s, x) -> IF(
        s IS null,
        array[x],
        if(contains(s, x), s, s || x)
    ),
    (s) -> s
)

Unless the optimizer is sufficiently smart so as to not create a brand new array on every iteration of the reduce, the above might be O(N^2)...

The following might be more efficient for large arrays, but gets pretty verbose:

transform(
    array_sort(
        transform(
            map_entries(multimap_from_entries(
                zip(a, sequence(1, cardinality(a))) -- get (value, index) pairs
            )), -- group indices by value into (value, array[index1, index2, ...]) pairs
            x -> (array_min(x.field1), x.field0) -- turn into (lowest_index, value) pairs
        )
    ), -- sort by lowest_index
    x -> x.field1 -- extract value from tuple
)

[rongrong]

We'd appreciate it if you would like to contribute to a documentation clarification! Thanks!