Skip to content

Commit 77aa7f3

Browse files
authored
fix: match Spark's float ordering for sort and window keys nested in arrays and structs (apache#6475)
* fix: match Spark's float ordering for sort and window keys nested in arrays and structs Spark orders floats with SQLOrderingUtil.compareDoubles at every depth of an array or struct. Comet normalized scalar float sort and window keys so that Arrow's total order agrees with Spark's, but compared nested keys raw, so -0.0 sorted below 0.0 and a NaN with the sign bit set below -Infinity. Wrap array and struct keys with a float leaf in NormalizeNestedFloats in create_normalized_key_expr, which builds the keys of Sort, TopK, Window and WindowGroupLimit. Only the comparison key is normalized, so returned values keep their bits. CometSortOrder is compatible for every key type, so strict floating-point mode no longer falls back for these keys. Closes apache#5507. * test: link the nested-null issues from the nested float key fixture * fix: decline nullable nested float keys in strict mode and drop the nested float rank-limit guard Strict floating-point mode fell back for every float nested in a sort or window key, before those keys were normalized. Removing that fallback also admitted keys that can hold a null element or field, which the native sort and RANGE window frames order differently from Spark (apache#6476, apache#6477). CometSortOrder now keeps the fallback for a key that has a float and whose type can hold a nested null, and every other key stays native. apache#6468 made RANK and DENSE_RANK limits fall back for nested float order keys, because the native operator compared them raw. The native planner now normalizes those keys, so drop that guard and make its test expect native execution. Split the nested float order key fixture: the existing one runs with the default settings, and a new one runs in strict mode and pins both halves of the policy. * test: drop the sweep suite's known gap for nested float sort keys With floats nested in array and struct sort keys normalized, the nested ORDER BY cases match Spark (apache#5507), so the suite now requires them to. * fix: fall back for RANGE frames over ORDER BY keys DataFusion cannot compare DataFusion finds a RANGE frame's CURRENT ROW bound by comparing ORDER BY values with ScalarValue::partial_cmp, which cannot order an array of arrays or structs, or a struct holding an array (apache/datafusion#24937), so the query fails with "Uncomparable values". Strict floating-point mode declined these keys while nested float keys were compared raw, and once null-free nested float keys became compatible they reached this failure in strict mode too. The same shapes fail with the default settings whatever their element type. CometWindowExec now falls back for a RANGE frame bounded by CURRENT ROW over such a key. Ranking functions, CUME_DIST, ROWS frames and an unbounded RANGE frame never compare values this way and stay native.
1 parent 03cb6bd commit 77aa7f3

16 files changed

Lines changed: 562 additions & 142 deletions

File tree

‎.ai/skills/review-comet-shuffle-pr/SKILL.md‎

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -55,12 +55,14 @@ keys**, and it is not the same rule for the two partitionings:
5555
and rejects collated strings, because Comet compares raw bytes. That is the whole rule. Scalar
5656
float and double are accepted, under `spark.comet.exec.strictFloatingPoint` as well: since
5757
[#5981](https://github.com/apache/datafusion-comet/pull/5981) the native range partitioner
58-
normalizes its comparison keys and its sampled boundary rows the same way the native sort does,
59-
and `CometSortOrder.getSupportLevel` returns `Compatible()` for them regardless of strict mode.
60-
What strict mode still governs is floating point _nested_ in an array, struct, or map
61-
([#5507](https://github.com/apache/datafusion-comet/issues/5507)), which is already out as a
62-
range key for being nested. `CometNativeShuffleSuite` runs "range partitioning on floating-point
63-
uses native shuffle" under both settings of the config.
58+
normalizes its comparison keys and its sampled boundary rows the same way the native sort does.
59+
`CometSortOrder` is `Compatible()` for scalar floats regardless of strict mode. It is for floats
60+
nested in arrays and structs too, because the native sort normalizes them, unless the key's type
61+
can hold a null element or field
62+
([#6476](https://github.com/apache/datafusion-comet/issues/6476),
63+
[#6477](https://github.com/apache/datafusion-comet/issues/6477)), which strict mode declines.
64+
A nested key is already out as a range key for being nested. `CometNativeShuffleSuite` runs
65+
"range partitioning on floating-point uses native shuffle" under both settings of the config.
6466
- **`HashPartitioning` is primitive-only by default only.** With
6567
`spark.comet.shuffle.native.partitioning.hash.nested.enabled=true` (default `false`),
6668
`supportedHashPartitioningDataType` admits structs and arrays recursively, and maps on Spark

‎docs/source/contributor-guide/native_shuffle.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -63,8 +63,8 @@ Native shuffle (`CometExchange`) is selected when all of the following condition
6363
compares raw bytes. Scalar float and double are supported, including when
6464
`spark.comet.exec.strictFloatingPoint` is enabled, because the native range partitioner
6565
normalizes its comparison keys and its sampled boundary rows the same way the native sort
66-
does. Strict floating point only affects floating-point values nested in arrays, structs, or
67-
maps, which are rejected as range keys for being nested anyway.
66+
does. The native sort normalizes floating-point values nested in arrays and structs as well,
67+
but those keys are rejected as range keys for being nested.
6868
- `HashPartitioning` keys must be primitive **by default**. Setting
6969
`spark.comet.shuffle.native.partitioning.hash.nested.enabled` to `true` admits structs and
7070
arrays as keys, checked recursively to their leaves, and maps on Spark 4.0 and later, where

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

Lines changed: 19 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -48,20 +48,25 @@ Spark's `ORDER BY`, `RANK`, `DENSE_RANK`, and window frame comparisons route thr
4848
`SQLOrderingUtil.compareDoubles` / `compareFloats`, which equate all NaN representations and
4949
define `-0.0 == 0.0`. NaN sorts above every non-NaN value.
5050

51-
For scalar `FLOAT` and `DOUBLE` keys, Comet normalizes NaNs and signed zeros before native
52-
sorting, window peer comparisons, and `WindowGroupLimitExec` rank comparisons. Native range
53-
partitioning normalizes its keys and sampled boundaries in the same way. Only comparison keys
54-
are normalized; returned values retain their original NaN representations and zero signs.
55-
56-
Native sorting of floating-point values nested in arrays or structs still uses Arrow's raw total
57-
ordering. Nested keys can therefore produce different ordering or rank results from Spark; see
58-
[#5507](https://github.com/apache/datafusion-comet/issues/5507).
59-
60-
Because those scalar comparison keys match Spark, `spark.comet.exec.strictFloatingPoint=true` no
61-
longer forces a fallback for them: scalar `FLOAT` and `DOUBLE` sort keys, window and rank order
62-
keys, and range partitioning keys all stay native under strict mode. Floating-point values nested
63-
in arrays, structs, or maps still fall back under strict mode, because their ordering is the raw
64-
total ordering described above.
51+
For `FLOAT` and `DOUBLE` keys, and for keys that nest them in arrays and structs at any depth,
52+
Comet normalizes NaNs and signed zeros before native sorting, window peer comparisons, and
53+
`WindowGroupLimitExec` rank comparisons. Native range partitioning normalizes its keys and
54+
sampled boundaries in the same way; it only accepts scalar keys. Only comparison keys are
55+
normalized; returned values retain their original NaN representations and zero signs.
56+
57+
Because those comparison keys match Spark, `spark.comet.exec.strictFloatingPoint=true` does not
58+
force a fallback for them: sort keys, window and rank order keys, and range partitioning keys all
59+
stay native under strict mode, whether the floats in them are scalar or nested.
60+
61+
The exception is a key that nests floats in an array or struct whose type can hold a null element
62+
or field. Spark orders such a null below every other value, whatever the key's `NULLS FIRST` or
63+
`NULLS LAST`. The native sort places it by that null order, so `ASC NULLS LAST` and
64+
`DESC NULLS FIRST` can differ from Spark, and a `RANGE` window frame orders it above every other
65+
value, so a running aggregate can span the whole partition
66+
([#6476](https://github.com/apache/datafusion-comet/issues/6476),
67+
[#6477](https://github.com/apache/datafusion-comet/issues/6477)). Strict mode makes those keys fall
68+
back to Spark. A key whose type cannot hold a null, such as `array(coalesce(x, 0.0D))`, stays
69+
native.
6570

6671
`array_min` and `array_max` use Spark-compatible native comparisons in both strict and non-strict
6772
floating-point modes. Signed zeros compare equal, and all NaN representations compare equal and

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

Lines changed: 8 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,10 @@ incorrect result. When any single window expression in a `WindowExec` falls back
8888
overflow instead of returning Spark's `NULL`.
8989
- `RANGE` frame with an explicit offset when the `ORDER BY` column is `DATE` or `DECIMAL`
9090
([#4834](https://github.com/apache/datafusion-comet/issues/4834)).
91+
- `RANGE` frame bounded by `CURRENT ROW` when an `ORDER BY` key is an array of arrays or structs, or a struct
92+
holding an array, such as `array(named_struct('x', x))`. DataFusion cannot compare those values to find the
93+
frame's bounds ([apache/datafusion#24937](https://github.com/apache/datafusion/issues/24937)). Ranking functions
94+
and `ROWS` frames over the same keys run natively.
9195
- `first_value` / `last_value` on a `RANGE` frame with a literal offset
9296
([#4835](https://github.com/apache/datafusion-comet/issues/4835)).
9397
- `lag` / `lead` with a non-literal default value ([#4268](https://github.com/apache/datafusion-comet/issues/4268)).
@@ -102,20 +106,10 @@ runs natively; it is controlled by `spark.comet.exec.windowGroupLimit.enabled` (
102106
- Any `PARTITION BY` or `ORDER BY` key whose type carries a non-default `StringType` collation
103107
(e.g. `UTF8_LCASE`). The native operator detects partitions and order-key peer groups by
104108
comparing Arrow row-encoded keys for byte equality, which splits peers that Spark ties.
105-
- `RANK` and `DENSE_RANK` whose `ORDER BY` key has a `FLOAT` or `DOUBLE` nested in an array or
106-
struct. The same byte equality decides their ties, and nested floating-point values aren't
107-
normalized, so `-0.0` and `+0.0`, or two NaN representations, would get different ranks and the
108-
cutoff would drop rows that Spark keeps
109-
([#5507](https://github.com/apache/datafusion-comet/issues/5507)).
110-
111-
**Known incompatibilities:**
112-
113-
- `ROW_NUMBER` over such a key still runs natively and follows the native sort, which compares
114-
nested floating-point values with Arrow's raw total ordering. Which of two rows that differ only
115-
in `-0.0` and `+0.0`, or in their NaN representation, gets the lower row number can therefore
116-
differ from Spark ([#5507](https://github.com/apache/datafusion-comet/issues/5507)). Scalar
117-
`FLOAT` and `DOUBLE` keys are normalized and match Spark; see
118-
[floating-point ordering](./floating-point.md).
109+
110+
Floating-point `ORDER BY` keys, including floats nested in arrays and structs, are normalized
111+
and match Spark's ranks; see [floating-point ordering](./floating-point.md), which also covers
112+
strict floating-point mode.
119113

120114
## Round-Robin Partitioning
121115

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

Lines changed: 11 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -149,16 +149,17 @@ See [TopK metrics](../metrics.md#local-topk).
149149

150150
## Optimizing Sorting on Floating-Point Values
151151

152-
Comet normalizes NaN payloads and signed zeros in scalar `FLOAT` and `DOUBLE` ordering keys, so `ORDER BY`, window
153-
ordering and range partitioning on them match Spark and stay native even with
154-
`spark.comet.exec.strictFloatingPoint=true`. Only the comparison key is normalized; returned values keep their original
155-
NaN representation and zero sign.
156-
157-
Floating-point values nested in arrays, structs, or maps are compared with Arrow's raw total ordering instead, which can
158-
differ from Spark when the data contains both zero and negative zero, or more than one NaN representation. This is likely
159-
an edge case that is not of concern for many users. Setting `spark.comet.exec.strictFloatingPoint=true` makes those
160-
nested cases fall back to Spark, and they can be forced back onto the native path with
161-
`spark.comet.expression.SortOrder.allowIncompatible=true`.
152+
Comet normalizes NaN payloads and signed zeros in `FLOAT` and `DOUBLE` ordering keys, including floating-point values
153+
nested in arrays and structs, so `ORDER BY`, window ordering and range partitioning on them match Spark and stay native
154+
even with `spark.comet.exec.strictFloatingPoint=true`. Only the comparison key is normalized; returned values keep their
155+
original NaN representation and zero sign.
156+
157+
The exception is a key that nests floating-point values in an array or struct whose type can hold a null element or
158+
field. Spark orders such a null below every other value, and the native sort and `RANGE` window frames do not
159+
([#6476](https://github.com/apache/datafusion-comet/issues/6476),
160+
[#6477](https://github.com/apache/datafusion-comet/issues/6477)), so
161+
`spark.comet.exec.strictFloatingPoint=true` makes those keys fall back to Spark. They can be forced back onto the
162+
native path with `spark.comet.expression.SortOrder.allowIncompatible=true`.
162163

163164
`sort_array` sorts array elements rather than ordering rows. It follows Spark's floating-point ordering as well, so it
164165
also stays native with `spark.comet.exec.strictFloatingPoint=true`.

‎native/core/src/execution/planner.rs‎

Lines changed: 50 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -142,9 +142,9 @@ use datafusion_comet_spark_expr::{
142142
create_case_when, create_if_expr, jvm_udf::JvmScalarUdfExpr, spark_in_list, ApproxPercentile,
143143
ArrayInsert, Avg, AvgDecimal, Cast, CheckOverflow, Correlation, Covariance, CreateNamedStruct,
144144
DecimalRescaleCheckOverflow, GetArrayStructFields, GetStructField, HllPlusPlus, HllSketchAgg,
145-
HllUnionAgg, IfExpr, ListExtract, MaxMinBy, Mode, NormalizeNaNAndZero, Regr, RegrType,
146-
SparkCastOptions, Stddev, SumDecimal, ToJson, UnboundColumn, Variance, WideDecimalBinaryExpr,
147-
WideDecimalOp,
145+
HllUnionAgg, IfExpr, ListExtract, MaxMinBy, Mode, NormalizeNaNAndZero, NormalizeNestedFloats,
146+
Regr, RegrType, SparkCastOptions, Stddev, SumDecimal, ToJson, UnboundColumn, Variance,
147+
WideDecimalBinaryExpr, WideDecimalOp,
148148
};
149149
use itertools::Itertools;
150150
use jni::objects::{Global, JObject};
@@ -997,16 +997,18 @@ impl PhysicalPlanner {
997997
}
998998
}
999999

1000-
/// Normalize scalar floating-point comparison keys without changing output values.
1001-
/// Sort, Window, and WindowGroupLimit must use identical expressions so DataFusion
1002-
/// can recognize the ordering of window partition keys.
1000+
/// Normalize floating-point comparison keys without changing output values: a `FLOAT` or
1001+
/// `DOUBLE` key, and an array or struct key with a float at any depth, whose order Arrow
1002+
/// otherwise takes from the raw bits. Sort, Window, and WindowGroupLimit must use identical
1003+
/// expressions so DataFusion can recognize the ordering of window partition keys.
10031004
fn create_normalized_key_expr(
10041005
&self,
10051006
spark_expr: &Expr,
10061007
input_schema: SchemaRef,
10071008
) -> Result<Arc<dyn PhysicalExpr>, ExecutionError> {
10081009
let child = self.create_expr(spark_expr, Arc::clone(&input_schema))?;
1009-
Ok(NormalizeNaNAndZero::wrap_if_needed(
1010+
let child = NormalizeNaNAndZero::wrap_if_needed(child, input_schema.as_ref())?;
1011+
Ok(NormalizeNestedFloats::wrap_if_needed(
10101012
child,
10111013
input_schema.as_ref(),
10121014
)?)
@@ -4967,6 +4969,38 @@ mod tests {
49674969
.collect()
49684970
}
49694971

4972+
/// `floating_sort_batches` with each key wrapped in a one-element list and in a one-field
4973+
/// struct, which have to order and tie exactly as the bare key does. A null key becomes a
4974+
/// null list or struct.
4975+
fn nested_floating_sort_batches() -> Vec<(i32, RecordBatch)> {
4976+
use arrow::array::StructArray;
4977+
use arrow::buffer::OffsetBuffer;
4978+
floating_sort_batches()
4979+
.into_iter()
4980+
.flat_map(|(type_id, batch)| {
4981+
let values = Arc::clone(batch.column(0));
4982+
let nulls = values.nulls().cloned();
4983+
let element = Field::new("item", values.data_type().clone(), true);
4984+
let list: ArrayRef = Arc::new(ListArray::new(
4985+
Arc::new(element),
4986+
OffsetBuffer::from_lengths(vec![1; values.len()]),
4987+
Arc::clone(&values),
4988+
nulls.clone(),
4989+
));
4990+
let fields = Fields::from(vec![Field::new("v", values.data_type().clone(), true)]);
4991+
let record: ArrayRef = Arc::new(StructArray::new(fields, vec![values], nulls));
4992+
[list, record].into_iter().map(move |key| {
4993+
let mut fields: Vec<FieldRef> = batch.schema().fields().to_vec();
4994+
fields[0] = Arc::new(Field::new("ord", key.data_type().clone(), true));
4995+
let mut columns = batch.columns().to_vec();
4996+
columns[0] = key;
4997+
let batch = RecordBatch::try_new(Arc::new(Schema::new(fields)), columns);
4998+
(type_id, batch.unwrap())
4999+
})
5000+
})
5001+
.collect()
5002+
}
5003+
49705004
#[test]
49715005
fn floating_window_partition_keys_preserve_ordering() {
49725006
let planner = PhysicalPlanner::default();
@@ -5034,7 +5068,11 @@ mod tests {
50345068
async fn floating_sort_keys_preserve_window_group_limit_peers() {
50355069
let planner = PhysicalPlanner::default();
50365070
let context = SessionContext::new_with_config(SessionConfig::new().with_batch_size(3));
5037-
for (type_id, batch) in floating_sort_batches() {
5071+
// Floats nested in a list or a struct must rank exactly as the bare floats do.
5072+
let batches = floating_sort_batches()
5073+
.into_iter()
5074+
.chain(nested_floating_sort_batches());
5075+
for (type_id, batch) in batches {
50385076
for (descending, kind, fetch, expected) in [
50395077
(true, WindowFnKind::Rank, 3, vec![0, 1, 2, 8, 9]),
50405078
(true, WindowFnKind::DenseRank, 2, vec![0, 1, 2, 8, 9]),
@@ -5086,8 +5124,10 @@ mod tests {
50865124
}
50875125
ids.sort_unstable();
50885126
assert_eq!(
5089-
ids, expected,
5090-
"type={type_id}, descending={descending}, {kind:?}"
5127+
ids,
5128+
expected,
5129+
"type={type_id}, key={}, descending={descending}, {kind:?}",
5130+
batch.schema().field(0).data_type()
50915131
);
50925132
// The zero peer group and the second NaN peer group straddle size-3
50935133
// sort output batches. Tie state must survive those boundaries.

‎spark/src/main/scala/org/apache/comet/CometConf.scala‎

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1097,10 +1097,12 @@ object CometConf extends ShimCometConf {
10971097
.category(CATEGORY_EXEC)
10981098
.doc(
10991099
"When enabled, fall back to Spark for floating-point operations that may differ from " +
1100-
"Spark, such as comparing -0.0 and 0.0, or sorting floating-point values nested in " +
1101-
"arrays, structs, or maps. Scalar `ORDER BY`, window ordering and range partitioning " +
1102-
"keys are unaffected, because Comet normalizes those comparison keys to match Spark, " +
1103-
"and so is `sort_array`, which follows Spark's ordering. " +
1100+
"Spark, such as comparing -0.0 and 0.0. `ORDER BY`, window ordering and range " +
1101+
"partitioning keys are unaffected, including floating-point values nested in arrays " +
1102+
"and structs, because Comet normalizes those comparison keys to match Spark. The " +
1103+
"exception is a nested key whose type can hold a null element or field, which falls " +
1104+
"back until the native sort and window frames order those nulls as Spark does. " +
1105+
"`sort_array` is unaffected too, because it follows Spark's ordering. " +
11041106
s"$COMPAT_GUIDE.")
11051107
.booleanConf
11061108
.createWithDefault(false)

0 commit comments

Comments
 (0)