Skip to content

Commit a2d7370

Browse files
authored
fix: match Spark's float semantics in array_remove and sort_array (apache#6518)
* fix: match Spark's float semantics in array_remove and sort_array Spark compares floats in array_remove with genEqual, where -0.0 equals 0.0 and all NaNs are equal, and sorts them in sort_array with a stable sort in its SQL ordering, where NaN is the largest value. DataFusion's array_remove_all and array_sort compare by IEEE 754 total order instead. Replace array_remove_all in Comet's registry with SparkArrayRemove, which handles elements holding a float at any depth and delegates other types to DataFusion. Send float sort_array to a new spark_sort_array, which takes Spark's containsNull so that an ascending sort of non-null FLOAT or DOUBLE elements follows java.util.Arrays.sort, as Spark's generated code does. Float sort_array no longer needs the codegen dispatcher in strict floating-point mode. Part of apache#6385. * fix: return errors for mismatched types and cover more array shapes Dispatch the float fast paths of array_remove on the element and value types together, so a value of another type fails in spark_equality instead of panicking, and return an error from sort_array for input that is not a list. Add SQL cases for a literal array with a column value and for null arrays, and benchmark array_remove with a value per row. * refactor: route array_remove in Scala and resolve the fast-sort rule there Send float array_remove to a new spark_array_remove from the serde, as sort_array already chooses its function there, which removes the wrapper around DataFusion's array_remove_all. Resolve Spark's canPerformFastSort rule in CometSortArray and pass whether -0.0 sorts first, and move that ordering into float_semantics as compare_floats_java. Count kept elements with one running popcount instead of a bit count per row, which cuts array_remove of a constant from 77 to 26 us for 8192 rows of 8 doubles, and compact sort_array's valid values toward the end of an ascending row so their count needs no separate pass. The nested sort relies on spark_comparator's null ordering, and both functions share their list and test helpers. The new fixtures no longer run twice under a strict floating-point matrix that no query reads. * test: drop the sweep suite's known gap for array_remove and sort_array array_remove and sort_array now compare floats as Spark does, so the suite requires those cases to match.
1 parent 351facd commit a2d7370

19 files changed

Lines changed: 1470 additions & 54 deletions

File tree

‎docs/source/contributor-guide/expression-audits/array_funcs.md‎

Lines changed: 7 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -122,9 +122,11 @@
122122
## array_remove
123123

124124
- Spark 3.4.3 (audited 2026-05-27): identical to 3.5.8.
125-
- Spark 3.5.8 (audited 2026-05-27): baseline. `ArrayRemove(left, right)`; removes all occurrences equal to `right`. Wired as `CometScalarFunction("array_remove")`. Falls back via `ArraysBase.isTypeSupported` for binary/struct/map/null child types.
125+
- Spark 3.5.8 (audited 2026-05-27): baseline. `ArrayRemove(left, right)`; removes all occurrences equal to `right`. Falls back via `ArraysBase.isTypeSupported` for binary/struct/map/null child types.
126126
- Spark 4.0.1 (audited 2026-05-27): `NullIntolerant` -> `nullIntolerant` field refactor.
127127
- Spark 4.1.1 (audited 2026-05-27): identical to 4.0.1.
128+
- Current status: `CometArrayRemove` sends arrays whose elements hold a `FLOAT` or `DOUBLE` at any depth to the native `spark_array_remove`, which compares as Spark's `genEqual` does (`-0.0` equals `0.0`, all NaNs are equal, nested elements through `spark_equality`) and keeps the bits of the elements it keeps. Other element types use DataFusion's `array_remove_all`. Null elements stay, and a null array or value gives null.
129+
- Performance (tuned 2026-10-01, PR [#6518](https://github.com/apache/datafusion-comet/pull/6518)): with a constant value, `FLOAT` and `DOUBLE` elements get one keep mask over all the values from `BooleanBuffer::collect_bool`, with the inverted validity ORed in, one running popcount over the mask's words for each row's kept count, and one `filter`. 41-76% less time than DataFusion's `array_remove_all` with a constant value, and 47-95% less with a value per row. Benchmark: `benches/float_arrays.rs`.
128130

129131
## array_repeat
130132

@@ -196,8 +198,10 @@
196198
## sort_array
197199

198200
- Spark 3.4.3 (audited 2026-05-27): identical to 3.5.8.
199-
- Spark 3.5.8 (audited 2026-05-27): baseline. `SortArray(base, ascendingOrder) extends BinaryExpression with ArraySortLike`; the second arg must be a `Literal(_: Boolean, BooleanType)`. Comet `CometSortArray` flags `Incompatible` under strict floating-point and falls back for nested arrays whose innermost element is `Struct` or `Null`.
200-
- Spark 4.0.1 (audited 2026-05-27): trait set changes substantively: `ArraySortLike` and `NullIntolerant` are removed, `nullIntolerant = true` becomes an override, and `ascendingOrder` is widened to accept any foldable boolean (not just `Literal`). Comet's `CometSortArray` still requires a `Literal`, so the new foldable form falls back at convert time.
201+
- Spark 3.5.8 (audited 2026-05-27): baseline. `SortArray(base, ascendingOrder) extends BinaryExpression with ArraySortLike`; the second arg must be a `Literal(_: Boolean, BooleanType)`.
202+
- Spark 4.0.1 (audited 2026-05-27): trait set changes substantively: `ArraySortLike` and `NullIntolerant` are removed, `nullIntolerant = true` becomes an override, and `ascendingOrder` is widened to accept any foldable boolean (not just `Literal`).
201203
- Spark 4.1.1 (audited 2026-05-27): identical to 4.0.1.
204+
- Current status: elements with a `FLOAT` or `DOUBLE` at any depth go to the native `spark_sort_array`, which sorts as Spark's generated code does: a stable sort in Spark's SQL ordering, except that for an ascending sort of `FLOAT` or `DOUBLE` elements that cannot be null, the serde has it put `-0.0` before `0.0`, as `java.util.Arrays.sort` does. This holds in strict floating-point mode too. Other supported element types use DataFusion's `array_sort`, and unsupported ones route through the codegen dispatcher. `ascendingOrder` may be any foldable boolean, which the serde evaluates.
205+
- Performance (tuned 2026-10-01, PR [#6518](https://github.com/apache/datafusion-comet/pull/6518)): `FLOAT` and `DOUBLE` rows sort within one copy of all the values, each row's valid values copied without branching next to its nulls. Rows of up to 20 elements use the stable `sort_by`. Longer rows use `sort_unstable_by` and then put the zero and NaN runs back in their original order, because Rust's stable sort is up to 1.8 times slower between 33 and 63 elements. From 2% more to 21% less time than DataFusion's `array_sort`. Benchmark: `benches/float_arrays.rs`.
202206

203207
[Spark Expression Support]: ../../user-guide/latest/expressions.md

‎docs/source/user-guide/latest/compatibility/floating-point.md‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,3 +69,15 @@ greater than non-NaN values. The original first equal element is retained: for e
6969
`array_min(array(0.0D, -0.0D))` returns `0.0`, while reversing those elements returns `-0.0`.
7070
The same ordering applies recursively to floating-point fields in arrays and structs. These
7171
expressions do not require Spark's codegen dispatcher for floating-point compatibility.
72+
73+
## `array_remove` and `sort_array`
74+
75+
`array_remove` compares `FLOAT` and `DOUBLE` elements as Spark does: `-0.0` equals `0.0`, and all
76+
NaN representations are equal, inside nested arrays too. The elements it keeps retain their
77+
original NaN representations and zero signs.
78+
79+
`sort_array` sorts in Spark's order, in which NaN sorts above every other value and all NaN
80+
representations tie, and keeps equal elements in their original order. In an array whose elements
81+
can be null, such as one built from nullable columns, `-0.0` and `0.0` therefore tie. Sorting an
82+
array whose elements cannot be null in ascending order, Spark's generated code puts `-0.0` before
83+
`0.0`, and so does Comet. Both expressions run natively in strict floating-point mode.

‎docs/source/user-guide/latest/expressions.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -176,7 +176,7 @@ The tables below list every Spark built-in expression with its current status.
176176
| `sequence` | ✅ | Hybrid | Integral types run natively; date/timestamp sequences use codegen dispatch |
177177
| `shuffle` | ✅ | Native | Binary/struct/map elements fall back |
178178
| `slice` | ✅ | Native | Native ([#4149](https://github.com/apache/datafusion-comet/pull/4149)) |
179-
| `sort_array` | ✅ | Hybrid | Struct, nested-array, and null elements run natively; other element types (for example intervals), and floating-point elements when `spark.comet.exec.strictFloatingPoint=true`, route through the JVM codegen dispatcher |
179+
| `sort_array` | ✅ | Hybrid | Struct, nested-array, floating-point, and null elements run natively; other element types (for example intervals) route through the JVM codegen dispatcher |
180180

181181
---
182182

‎docs/source/user-guide/latest/tuning/operators.md‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -160,6 +160,5 @@ an edge case that is not of concern for many users. Setting `spark.comet.exec.st
160160
nested cases fall back to Spark, and they can be forced back onto the native path with
161161
`spark.comet.expression.SortOrder.allowIncompatible=true`.
162162

163-
`sort_array` is separate. It sorts array elements rather than ordering rows, and its elements are compared with Arrow's
164-
raw total ordering, so `spark.comet.exec.strictFloatingPoint=true` makes it fall back even for a scalar floating-point
165-
element type. Use `spark.comet.expression.SortArray.allowIncompatible=true` to keep it native.
163+
`sort_array` sorts array elements rather than ordering rows. It follows Spark's floating-point ordering as well, so it
164+
also stays native with `spark.comet.exec.strictFloatingPoint=true`.

‎native/spark-expr/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -453,3 +453,7 @@ harness = false
453453
[[bench]]
454454
name = "nested_comparison"
455455
harness = false
456+
457+
[[bench]]
458+
name = "float_arrays"
459+
harness = false
Lines changed: 165 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,165 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Compare Comet's float `sort_array` and `array_remove` with DataFusion's `array_sort` and
19+
//! `array_remove_all` on doubles without zeros or NaNs, where both return the same arrays, which
20+
//! is checked before timing; special-value semantics belong in tests.
21+
22+
use arrow::array::{Array, ArrayRef, Float64Array, ListArray};
23+
use arrow::buffer::{NullBuffer, OffsetBuffer};
24+
use arrow::datatypes::{DataType, Field};
25+
use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
26+
use datafusion::common::config::ConfigOptions;
27+
use datafusion::common::ScalarValue;
28+
use datafusion::functions_nested::remove::array_remove_all_udf;
29+
use datafusion::functions_nested::sort::array_sort_udf;
30+
use datafusion::logical_expr::{ColumnarValue, ScalarFunctionArgs, ScalarUDF};
31+
use datafusion_comet_spark_expr::{SparkArrayRemove, SparkSortArray};
32+
use std::hint::black_box;
33+
use std::sync::Arc;
34+
use std::time::Duration;
35+
36+
const ROWS: usize = 8192;
37+
38+
/// The value of element `i`. Values repeat so that `array_remove` finds something to remove.
39+
fn value(i: usize) -> f64 {
40+
((i * 7919) % 101) as f64 * 0.5 + 1.0
41+
}
42+
43+
/// `ROWS` lists of `len` doubles, with every tenth list and every seventh element null if
44+
/// `nulls`.
45+
fn lists(len: usize, nulls: bool) -> ArrayRef {
46+
let values = if nulls {
47+
Float64Array::from_iter((0..ROWS * len).map(|i| (i % 7 != 0).then(|| value(i))))
48+
} else {
49+
Float64Array::from_iter_values((0..ROWS * len).map(value))
50+
};
51+
Arc::new(ListArray::new(
52+
Arc::new(Field::new_list_field(DataType::Float64, true)),
53+
OffsetBuffer::from_lengths(std::iter::repeat_n(len, ROWS)),
54+
Arc::new(values),
55+
nulls.then(|| NullBuffer::from_iter((0..ROWS).map(|row| row % 10 != 0))),
56+
))
57+
}
58+
59+
fn args(args: Vec<ColumnarValue>, list: &ArrayRef) -> ScalarFunctionArgs {
60+
ScalarFunctionArgs {
61+
arg_fields: args
62+
.iter()
63+
.map(|arg| Arc::new(Field::new("arg", arg.data_type(), true)))
64+
.collect(),
65+
args,
66+
number_rows: ROWS,
67+
return_field: Arc::new(Field::new("result", list.data_type().clone(), true)),
68+
config_options: Arc::new(ConfigOptions::default()),
69+
}
70+
}
71+
72+
fn criterion_benchmark(c: &mut Criterion) {
73+
let mut group = c.benchmark_group("float_arrays");
74+
group.sample_size(20);
75+
group.warm_up_time(Duration::from_millis(250));
76+
group.measurement_time(Duration::from_secs(1));
77+
let comet_sort = ScalarUDF::new_from_impl(SparkSortArray::default());
78+
let comet_remove = ScalarUDF::new_from_impl(SparkArrayRemove::default());
79+
let (datafusion_sort, datafusion_remove) = (array_sort_udf(), array_remove_all_udf());
80+
for len in [8, 50] {
81+
for nulls in [false, true] {
82+
let list = lists(len, nulls);
83+
let data = format!("len={len}_null={nulls}");
84+
let column = ColumnarValue::Array(Arc::clone(&list));
85+
let scalar = |value: ScalarValue| ColumnarValue::Scalar(value);
86+
let comet_sort_args = args(
87+
vec![
88+
column.clone(),
89+
scalar(ScalarValue::Boolean(Some(true))),
90+
scalar(ScalarValue::Boolean(Some(false))),
91+
],
92+
&list,
93+
);
94+
let datafusion_sort_args = args(
95+
vec![
96+
column.clone(),
97+
scalar(ScalarValue::from("ASC")),
98+
scalar(ScalarValue::from("NULLS FIRST")),
99+
],
100+
&list,
101+
);
102+
let remove_args = args(
103+
vec![column.clone(), scalar(ScalarValue::Float64(Some(26.0)))],
104+
&list,
105+
);
106+
// A value per row: the row's second element.
107+
let row_values =
108+
Float64Array::from_iter_values((0..ROWS).map(|row| value(row * len + 1)));
109+
let remove_column_args = args(
110+
vec![column, ColumnarValue::Array(Arc::new(row_values))],
111+
&list,
112+
);
113+
let cases = [
114+
(
115+
"sort_array",
116+
&comet_sort,
117+
&datafusion_sort,
118+
&comet_sort_args,
119+
&datafusion_sort_args,
120+
),
121+
(
122+
"array_remove",
123+
&comet_remove,
124+
&datafusion_remove,
125+
&remove_args,
126+
&remove_args,
127+
),
128+
(
129+
"array_remove_column",
130+
&comet_remove,
131+
&datafusion_remove,
132+
&remove_column_args,
133+
&remove_column_args,
134+
),
135+
];
136+
for (op, comet, datafusion, comet_args, datafusion_args) in cases {
137+
let evaluate = |udf: &ScalarUDF, args: &ScalarFunctionArgs| {
138+
udf.invoke_with_args(args.clone())
139+
.unwrap()
140+
.into_array(ROWS)
141+
.unwrap()
142+
};
143+
assert_eq!(
144+
evaluate(comet, comet_args).to_data(),
145+
evaluate(datafusion, datafusion_args).to_data(),
146+
"{op} {data}"
147+
);
148+
for (engine, udf, udf_args) in [
149+
("comet", comet, comet_args),
150+
("datafusion", datafusion.as_ref(), datafusion_args),
151+
] {
152+
group.bench_function(BenchmarkId::new(format!("{op}_{engine}"), &data), |b| {
153+
b.iter(|| {
154+
black_box(udf.invoke_with_args(black_box(udf_args.clone())).unwrap())
155+
})
156+
});
157+
}
158+
}
159+
}
160+
}
161+
group.finish();
162+
}
163+
164+
criterion_group!(benches, criterion_benchmark);
165+
criterion_main!(benches);

0 commit comments

Comments
 (0)