andygrove opened a new pull request, #6518:
URL: https://github.com/apache/datafusion-comet/pull/6518
## Which issue does this PR close?
Part of #6385: the `array_remove` and `sort_array` parts of the "fix
`min`/`max`, `greatest`/`least`, `array_remove`, NaN handling in
`array_distinct`/`array_union`, and `sort_array`" step.
## Rationale for this change
Spark compares floats in `array_remove` with `genEqual`, in which `-0.0`
equals `0.0` and all NaNs are equal, and sorts them in `sort_array` with
`SQLOrderingUtil.compareDoubles`, in which NaN sorts above every other value.
Comet ran DataFusion's `array_remove_all` and `array_sort`, which compare by
IEEE 754 total order, where `-0.0` sorts below `0.0` and a NaN with the sign
bit set sorts below `-Infinity`. Negating a NaN sets that bit on any platform,
and on x86-64 every NaN that arithmetic produces has it.
With `d` holding `0.0`, `-0.0`, NaN and `1.0`, on `main`:
| Query | Spark | Comet before |
| --- | --- | --- |
| `array_remove(array(d, -d, 1.0D, NULL), 0.0D)` for `d = 0.0` | `[1.0,
null]` | `[-0.0, 1.0, null]` |
| `array_remove(array(d, -d, 1.0D), d)` for `d = NaN` | `[1.0]` | `[NaN,
1.0]` |
| `sort_array(array(d, -d, 1.0D))` for `d = 0.0` | `[0.0, -0.0, 1.0]` |
`[-0.0, 0.0, 1.0]` |
| `sort_array(array(d, -d, 1.0D))` for `d = NaN` | `[1.0, NaN, NaN]` |
`[NaN, 1.0, NaN]` |
`sort_array` has one more rule. Spark's comparator sort is stable, so in the
third row the two zeros keep their order. But when an ascending sort's elements
cannot be null, Spark's generated code calls `java.util.Arrays.sort` on the
primitive array, whose order puts `-0.0` before `0.0` (`canPerformFastSort` in
`SortArray`, in every version from 3.4 to 4.2; 4.1 switched to
`Arrays.parallelSort`, which orders the same way). In strict floating-point
mode, float `sort_array` went through the codegen dispatcher.
## What changes are included in this PR?
- `SparkArrayRemove` replaces DataFusion's `array_remove_all` in Comet's
registry, as `SparkArrayExtrema` replaces `array_min` and `array_max`. For
elements with a `FLOAT` or `DOUBLE` at any depth it compares as `genEqual` does
(nested elements through `float_semantics::spark_equality`) and keeps the
elements it does not remove as they are, bits included. Other element types
still use DataFusion's version. Null elements stay, and a null array or value
gives null, as before.
- `SparkSortArray` (`spark_sort_array`) sorts arrays whose elements hold a
float as Spark's stable sort does, in Spark's ordering (nested elements through
`spark_comparator`), with null elements first when ascending and last when
descending, or, for an ascending sort of `FLOAT` or `DOUBLE` elements that
cannot be null, in `java.util.Arrays.sort` order. `CometSortArray` sends float
element types to it with Spark's `containsNull`, which the native list type
does not carry, since Comet's `array(...)` always builds nullable elements.
Other element types still use DataFusion's `array_sort`.
- For `FLOAT` and `DOUBLE` elements, both are faster than DataFusion's
versions in the benchmark below:
- `array_remove` of a constant value tests every element in one pass over
all the rows, as DataFusion's version does, and keeps the null elements with
one bitwise OR of the validity.
- `sort_array` copies all the values once and sorts each row where it
lands, after its nulls when ascending or before them when descending. Rust's
stable sort was up to 1.8 times slower than DataFusion's unstable sort for rows
of 33 to 63 elements, so a row longer than 20 elements gets an unstable sort,
after which the NaNs, and the zeros unless in `java.util.Arrays.sort` order,
are put back in their original order. Those are the only tied elements whose
bits can differ, so the result is the stable sort's. A shorter row gets the
stable sort, which is an insertion sort either way.
- `CometSortArray` no longer reports float elements as incompatible in
strict floating-point mode, so they run natively instead of through the codegen
dispatcher. The routing fixtures expect that.
- The floating-point compatibility guide gains a section on both functions,
and the tuning guide, the expression table, the
`spark.comet.exec.strictFloatingPoint` description and the array expression
audit are updated.
- A `float_arrays` benchmark compares both with DataFusion's versions.
## How are these changes tested?
- `array_remove_floating_point.sql` (new, run with strict floating-point
mode off and on): removing a zero or a NaN of either sign from `DOUBLE` and
`FLOAT` arrays holding both zeros and both kinds of NaN, null elements, a null
value, nested arrays, and calls with only literals.
- `sort_array_floating_point.sql` (new, off and on, with
`SortArray.allowIncompatible=false` so strict mode applies the shipped policy):
both zeros and both NaNs in both orders, ascending and descending, `DOUBLE` and
`FLOAT`, arrays whose elements can be null and arrays whose elements cannot
(`coalesce` and literals), and nested arrays and structs.
- Both fail on `main` with strict floating-point mode off,
`array_remove_floating_point.sql` with it on as well.
- Unit tests compare both functions, by bits, with Spark's rules:
`array_remove` of every edge value from an array of all of them, nulls,
`FLOAT`, constants (including a sliced array), struct elements, and other types
passing through to DataFusion; `sort_array` over pseudo-random sequences of up
to 82 edge values (long enough for the unstable sort to reorder ties) in both
directions, with and without null elements, sliced, the `java.util.Arrays.sort`
case against a `Double.compare` model, `FLOAT`, and struct elements. Without
the step that restores the order of ties, the sequence tests fail.
- Results on macOS aarch64 with the default Spark 4.1 profile:
`CometSqlFileTestSuite` with every fixture, 595 passed;
`CometArrayExpressionSuite`, 67 passed; the `datafusion-comet-spark-expr` unit
tests, 1078 passed.
The `float_arrays` benchmark times 8192 rows of `DOUBLE` arrays without
zeros or NaNs, where both versions must return the same arrays, which it checks
first. "With nulls" makes every tenth row and every seventh element null. One
run on macOS aarch64:
| Function | Elements per row | Nulls | Comet | DataFusion |
| --- | --- | --- | --- | --- |
| `sort_array` | 8 | no | 118 µs | 129 µs |
| `sort_array` | 8 | yes | 212 µs | 231 µs |
| `sort_array` | 50 | no | 1.73 ms | 1.90 ms |
| `sort_array` | 50 | yes | 1.76 ms | 1.82 ms |
| `array_remove` | 8 | no | 77 µs | 110 µs |
| `array_remove` | 8 | yes | 88 µs | 150 µs |
| `array_remove` | 50 | no | 168 µs | 239 µs |
| `array_remove` | 50 | yes | 235 µs | 339 µs |
--
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]
