andygrove opened a new issue, #218:
URL: https://github.com/apache/datafusion-spark/issues/218
Part of #178 and apache/datafusion-comet#7300.
### What the function does
`sort_array(array[, ascendingOrder])` sorts an array by the natural ordering
of its elements. `ascendingOrder`
defaults to `true`. The result type is the input type, with `containsNull`
unchanged. The element type must be
orderable (`RowOrdering.isOrderable`), so a map or VARIANT element, or a
struct holding one, fails with
`DATATYPE_MISMATCH.INVALID_ORDERING_TYPE`. A non-array first argument fails
with
`DATATYPE_MISMATCH.UNEXPECTED_INPUT_TYPE`.
Since Spark 4.0, `ascendingOrder` may be any foldable BOOLEAN expression. A
non-foldable value fails with
`DATATYPE_MISMATCH.NON_FOLDABLE_INPUT`, and a non-boolean value fails with
`UNEXPECTED_INPUT_TYPE`.
Null handling:
- The expression is null-intolerant: a NULL array, or a NULL
`ascendingOrder` (4.0+), gives NULL.
- NULL elements sort first in ascending order and last in descending order.
- For FLOAT/DOUBLE, NaN is greater than every non-NaN value, and all NaNs
are equal.
The function exists since Spark 1.5.0 and has no aliases. It is a different
function from Spark's `array_sort`,
which puts NULLs last and accepts a lambda.
### Examples
```sql
SELECT sort_array(array('b', 'd', null, 'c', 'a'), true);
-- [null,"a","b","c","d"]
SELECT sort_array(array('b', 'd', null, 'c', 'a'), false);
-- ["d","c","b","a",null]
SELECT sort_array(array(2, 1, 3));
-- [1,2,3]
SELECT sort_array(array(true, false, true, null, false));
-- [null,false,false,true,true]
SELECT sort_array(array(array(2), array(1), array(2, 4), null), true);
-- [null,[1],[2],[2,4]]
SELECT sort_array(array(array(2), array(1), array(2, 4), null), false);
-- [[2,4],[2],[1],null]
SELECT sort_array(array('b', 'd'), cast(NULL as boolean));
-- NULL (Spark 4.0+; 3.x fails analysis)
SELECT sort_array(array('b', 'd'), '1');
-- error DATATYPE_MISMATCH.UNEXPECTED_INPUT_TYPE (paramIndex "second",
requiredType "BOOLEAN")
```
### Edge cases to test
- NULL array, empty array, an array of only NULLs, and `array(NULL, NULL)`
(element type `VOID`, returned
unchanged).
- NULL placement in both directions, with NULLs at the start, middle and end
of the input.
- Floating point:
- NaN sorts after `+Infinity` ascending and first descending. Include NaNs
with different bit patterns.
- The general comparator
(`SQLOrderingUtil.compareDoubles`/`compareFloats`) treats `-0.0 == 0.0`, and the
sort is stable (`Arrays.parallelSort` of `Object[]`), so signed zeros
keep their input order.
- There is one exception. Whole-stage codegen takes a fast path for an
ascending sort of a primitive element
type (other than BOOLEAN) whose array type has `containsNull = false`.
That path calls
`Arrays.parallelSort(double[])` (`Arrays.sort` before 4.1), which puts
`-0.0` before `0.0`. Test
`[0.0, -0.0]` both with `containsNull = false` (for example from a
non-null column) and with
`containsNull = true`.
- Struct elements compare field by field, and array elements compare
lexicographically (shorter prefix first),
with NULL fields or elements first. Nested floats follow the rules above,
but without the fast path.
- Strings use binary (UTF-8 byte) order. Collated strings (4.0+) sort by
collation. Binary elements sort by
unsigned bytes.
- DECIMAL, DATE, TIMESTAMP, TIMESTAMP_NTZ, and ANSI interval (YEAR-MONTH /
DAY-TIME) element types.
- Map, VARIANT and legacy `CalendarInterval` elements are not orderable, so
they give an analysis error
(`INVALID_ORDERING_TYPE`).
- Stability: equal elements keep their relative input order. This is visible
for structs whose fields compare
equal, and for signed zeros.
- The array can be a literal or a column. `ascendingOrder` is a literal or a
foldable expression such as
`NOT false`, never a column.
### Differences across Spark versions
- 3.4 and 3.5: `ascendingOrder` must be a boolean `Literal`. `cast(NULL as
boolean)` fails analysis with
`DATATYPE_MISMATCH.UNEXPECTED_INPUT_TYPE` (paramIndex `"2"`), and a
foldable non-literal fails the same way.
- 4.0: any foldable boolean is accepted, a NULL order returns NULL, a
non-foldable order gets the new
`NON_FOLDABLE_INPUT` error, and `paramIndex` becomes ordinal ("second").
- 4.1 (present in 4.1.3) and 4.2: `Arrays.sort` is replaced by
`Arrays.parallelSort`. Results are the same, and the object sort stays
stable.
### Implementation notes
- Spark implements this in
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/collectionOperations.scala`
(`SortArray`). Float ordering is in
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/util/SQLOrderingUtil.scala`.
- DataFusion core has `array_sort(array, 'ASC'|'DESC', 'NULLS FIRST'|'NULLS
LAST')` in
`datafusion/functions-nested/src/sort.rs`. It differs from Spark as
follows:
- Its nulls default is `NULLS FIRST` even for `DESC`, whereas Spark puts
NULLs last when descending. So
`sort_array(a, false)` maps to `'DESC', 'NULLS LAST'`.
- It takes string order arguments, not a boolean.
- It uses `sort_unstable_by`, so equal elements are not kept in input
order.
- Floats use the total order (`total_cmp` for primitives, and the row
format for nested values). `-0.0` sorts
before `0.0` in every case, and negative-sign NaNs sort before every
number. Spark treats all NaNs as
largest and signed zeros as equal (except in the codegen fast path
described above).
- It returns a NULL list when the order argument is NULL, which matches
4.0+.
- An implementation can wrap `array_sort` for non-float element types, if
the stability difference is
acceptable for them. Float elements at any depth need a Spark-specific
comparator: NaN largest, all NaNs
equal, `-0.0 == 0.0`, and a stable sort.
- The float-normalization helpers in
`crates/spark/src/function/array/array_contains.rs` (see
apache/datafusion-spark#34) are related. Sharing one Spark float-ordering
helper would help here and in the
set functions.
- The function belongs in `crates/spark/src/function/array/`. Add
`crates/sqllogictest/test_files/array/sort_array.slt` and document it with
`#[user_doc]`.
---
_This issue was generated by an LLM (Claude) from the Apache Spark source
code and tests. Examples come from Spark's `ExpressionDescription` examples,
test suites and `.sql.out` golden files, but please verify them against Spark
before relying on them._
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]