Skip to content

Commit 0576a0b

Browse files
authored
fix: compare ScalarValue maps using Arrow ordering (#25555)
## Which issue does this PR close? Close #25556 ## Rationale for this change `ScalarValue::partial_cmp` only compared Map keys and ignored their values. Maps with identical keys but different values were therefore considered equal. This could produce incorrect ordering when merging ordered aggregate states, such as `first_value`, `last_value`, and `nth_value`, and could incorrectly validate range partition split points. ## What changes are included in this PR? Use Arrow's Map comparator for `ScalarValue::Map` comparisons. This aligns scalar comparison with Arrow sorting and nested comparison semantics, including values, entry order, lengths, and nulls. Add unit tests covering these cases. ## What is the testing strategy for this PR? Added `test_map_partial_cmp` covering: - maps with identical keys and different values - lexicographic `(key, value)` entry ordering - maps of different lengths - null and empty maps ## Are there any user-facing changes? Map scalar comparisons now consider both keys and values and are consistent with Arrow ordering.
1 parent 31a4ca0 commit 0576a0b

1 file changed

Lines changed: 41 additions & 18 deletions

File tree

  • datafusion/common/src/scalar

‎datafusion/common/src/scalar/mod.rs‎

Lines changed: 41 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,7 @@ use arrow::array::{
7474
Time32SecondArray, Time64MicrosecondArray, Time64NanosecondArray,
7575
TimestampMicrosecondArray, TimestampMillisecondArray, TimestampNanosecondArray,
7676
TimestampSecondArray, UInt8Array, UInt16Array, UInt32Array, UInt64Array, UnionArray,
77-
downcast_run_array, new_empty_array, new_null_array,
77+
downcast_run_array, make_comparator, new_empty_array, new_null_array,
7878
};
7979
use arrow::buffer::{BooleanBuffer, ScalarBuffer};
8080
use arrow::compute::kernels::cast::{CastOptions, cast_with_options};
@@ -920,23 +920,11 @@ fn partial_cmp_map(m1: &Arc<MapArray>, m2: &Arc<MapArray>) -> Option<Ordering> {
920920
return None;
921921
}
922922

923-
for col_index in 0..m1.len() {
924-
let arr1 = m1.entries().column(col_index);
925-
let arr2 = m2.entries().column(col_index);
926-
927-
let lt_res = arrow::compute::kernels::cmp::lt(arr1, arr2).ok()?;
928-
let eq_res = arrow::compute::kernels::cmp::eq(arr1, arr2).ok()?;
929-
930-
for j in 0..lt_res.len() {
931-
if lt_res.is_valid(j) && lt_res.value(j) {
932-
return Some(Ordering::Less);
933-
}
934-
if eq_res.is_valid(j) && !eq_res.value(j) {
935-
return Some(Ordering::Greater);
936-
}
937-
}
938-
}
939-
Some(Ordering::Equal)
923+
// Keep ScalarValue ordering consistent with Arrow sorting and nested comparison.
924+
// Maps compare lexicographically by entry (key, value), including offsets and nulls.
925+
let comparator =
926+
make_comparator(m1.as_ref(), m2.as_ref(), Default::default()).ok()?;
927+
Some(comparator(0, 0))
940928
}
941929

942930
impl Eq for ScalarValue {}
@@ -7424,6 +7412,41 @@ mod tests {
74247412
assert_eq!(a.partial_cmp(&b), Some(Ordering::Greater));
74257413
}
74267414

7415+
#[test]
7416+
fn test_map_partial_cmp() {
7417+
fn map(entries: Option<Vec<(&str, Option<i32>)>>) -> ScalarValue {
7418+
ScalarValue::Map(Arc::new(MapArray::from_vec_of_maps::<
7419+
StringArray,
7420+
Int32Array,
7421+
_,
7422+
_,
7423+
>(vec![entries], false)))
7424+
}
7425+
7426+
let a1 = map(Some(vec![("a", Some(1))]));
7427+
let a2 = map(Some(vec![("a", Some(2))]));
7428+
assert_eq!(a1.partial_cmp(&a2), Some(Ordering::Less));
7429+
assert_eq!(a2.partial_cmp(&a1), Some(Ordering::Greater));
7430+
7431+
// Map entries compare as (key, value) pairs, rather than comparing all keys
7432+
// before all values. The first pair therefore determines this ordering.
7433+
let high_first_value = map(Some(vec![("a", Some(100)), ("b", Some(1))]));
7434+
let low_first_value = map(Some(vec![("a", Some(1)), ("c", Some(999))]));
7435+
assert_eq!(
7436+
high_first_value.partial_cmp(&low_first_value),
7437+
Some(Ordering::Greater)
7438+
);
7439+
7440+
let prefix = map(Some(vec![("a", Some(1))]));
7441+
let longer = map(Some(vec![("a", Some(1)), ("b", Some(2))]));
7442+
assert_eq!(prefix.partial_cmp(&longer), Some(Ordering::Less));
7443+
7444+
let null = map(None);
7445+
let empty = map(Some(vec![]));
7446+
assert_eq!(null.partial_cmp(&empty), Some(Ordering::Less));
7447+
assert_eq!(empty.partial_cmp(&empty), Some(Ordering::Equal));
7448+
}
7449+
74277450
#[test]
74287451
fn scalar_value_to_array_u64() -> Result<()> {
74297452
let value = ScalarValue::UInt64(Some(13u64));

0 commit comments

Comments
 (0)