Skip to content

Commit bb9e740

Browse files
viiryaclaude
andauthored
fix: apply the parent struct's null mask before hashing its fields (apache#5754)
Arrow keeps a `StructArray`'s children validity independent of the parent's, so at a row where the struct itself is null a child buffer can still hold a value. The struct branch of `create_hashes_internal!` recursed straight into `struct_array.columns()` without consulting the parent's null buffer, so a null struct hashed whatever happened to sit in the child slot instead of leaving the seed alone as Spark does. Two rows with the same logical key then hash differently. What the tests here demonstrate directly is a wrong answer from `hash` and `xxhash64` in a Spark query. The same hash decides shuffle partition assignment, so equal keys reaching different partitions follows from it, but that path is not exercised by these tests. The `List` and `Map` branches already guard on `is_null`; only `Struct` did not. Uses `StructArray::flatten`, which unions the parent's nulls into each child exactly the way apache#4432 fixed the same null-mask propagation problem in `GetStructField`, and does it without revalidating the child data buffers: the union only ever adds nulls, so the buffers are unchanged. Going through the checked `ArrayData` builder instead would rescan every child buffer on each call -- for a string child, the whole UTF-8 values buffer -- and this branch runs once per element when hashing a list of structs. `flatten` is called only when the parent actually has a null, because it also builds a fresh `Fields` with every non-nullable field re-marked nullable, which this call site discards. A struct carrying an all-valid null buffer, which is what slicing leaves behind, would otherwise pay a `Vec` and an `Arc<[FieldRef]>` for nothing. `NullBuffer` stores its null count, so the test itself is free. The branch is shared by murmur3 and xxhash64 through the macro, so both are fixed and both get a regression test. Each test fails without the change: the null row hashes 3319311472 rather than the 42 seed under murmur3. The unit tests hand-build the array, so they do not show that a query can reach this shape. It can: a nullable struct whose child field is REQUIRED is written as `optional group c { required int32 a; }`, and on read the child leaf has nowhere to record a null of its own, so its buffer holds a value at exactly the rows where the struct is null. Two end-to-end tests in `CometHashExpressionSuite` cover that, one with a scalar child and one where the child is itself a struct so the union has to recurse, and both disagree with Spark before the change. The per-element route through `hash_list_array!` gets an end-to-end test too. Using the struct as the list element directly does not reproduce, because a null element is rebuilt on the way into the array and the hidden child values go with it. Wrapping it does: `array(named_struct('tag', 1, 'b', c))` yields an element that is itself valid, so it is copied rather than rebuilt, and the null `c` inside keeps the values Parquet wrote under it. Covered with one element and with two, so the chaining between elements is exercised, and both disagree with Spark before the change. Co-authored-by: Claude Code <[email protected]>
1 parent 6368c4e commit bb9e740

4 files changed

Lines changed: 271 additions & 3 deletions

File tree

‎native/spark-expr/src/hash_funcs/murmur3.rs‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -302,6 +302,91 @@ mod tests {
302302
);
303303
}
304304

305+
/// Arrow lets a `StructArray`'s children carry their own validity, so at a row where the struct
306+
/// itself is null the child buffer can still hold a value. Spark hashes a null struct as the
307+
/// seed, so those hidden child values must not reach the hash. This is the same null-mask
308+
/// propagation problem that #4432 fixed for `GetStructField`.
309+
#[test]
310+
fn test_null_struct_ignores_hidden_child_values() {
311+
use arrow::array::{Int32Array, StructArray};
312+
use arrow::buffer::NullBuffer;
313+
use arrow::datatypes::{DataType, Field, Fields};
314+
315+
let fields: Fields = vec![Arc::new(Field::new("a", DataType::Int32, true))].into();
316+
// Row 1 is a null struct whose child still holds 999.
317+
let child: ArrayRef = Arc::new(Int32Array::from(vec![Some(1), Some(999)]));
318+
let nulls = NullBuffer::from(vec![true, false]);
319+
let with_hidden: ArrayRef = Arc::new(StructArray::new(
320+
fields.clone(),
321+
vec![Arc::clone(&child)],
322+
Some(nulls.clone()),
323+
));
324+
// Same shape, but the hidden slot is null too.
325+
let child_null: ArrayRef = Arc::new(Int32Array::from(vec![Some(1), None]));
326+
let without_hidden: ArrayRef =
327+
Arc::new(StructArray::new(fields, vec![child_null], Some(nulls)));
328+
329+
let mut a = vec![42u32; 2];
330+
create_murmur3_hashes(&[with_hidden], &mut a).unwrap();
331+
let mut b = vec![42u32; 2];
332+
create_murmur3_hashes(&[without_hidden], &mut b).unwrap();
333+
334+
assert_eq!(
335+
a, b,
336+
"a null struct must hash the same regardless of what its child buffer holds"
337+
);
338+
assert_eq!(a[1], 42, "a null struct must leave the seed untouched");
339+
}
340+
341+
/// The struct branch is also reached once per element when hashing `array<struct<..>>`, which
342+
/// is the path #5567 made usable as a shuffle partitioning key. The test above hashes a struct
343+
/// directly, so it does not cover that route.
344+
///
345+
/// Here the null is the list *element* itself, with valid elements either side so the chaining
346+
/// is exercised. The end-to-end test in `CometHashExpressionSuite` covers the other shape, a
347+
/// valid element wrapping a null struct, which is the one a query can produce.
348+
#[test]
349+
fn test_null_struct_element_of_list_ignores_hidden_child_values() {
350+
use arrow::array::{Int32Array, ListArray, StructArray};
351+
use arrow::buffer::{NullBuffer, OffsetBuffer};
352+
use arrow::datatypes::{DataType, Field, Fields};
353+
354+
let fields: Fields = vec![Arc::new(Field::new("a", DataType::Int32, true))].into();
355+
// Element 1 is a null struct whose child still holds 999; elements 0 and 2 are valid.
356+
let element_nulls = NullBuffer::from(vec![true, false, true]);
357+
let with_hidden: ArrayRef = Arc::new(StructArray::new(
358+
fields.clone(),
359+
vec![Arc::new(Int32Array::from(vec![Some(1), Some(999), Some(3)])) as ArrayRef],
360+
Some(element_nulls.clone()),
361+
));
362+
// The same shape with the hidden slot null as well.
363+
let without_hidden: ArrayRef = Arc::new(StructArray::new(
364+
fields,
365+
vec![Arc::new(Int32Array::from(vec![Some(1), None, Some(3)])) as ArrayRef],
366+
Some(element_nulls),
367+
));
368+
369+
// One row holding all three elements, so element hashes chain in order.
370+
let as_list = |elements: ArrayRef| -> ArrayRef {
371+
Arc::new(ListArray::new(
372+
Arc::new(Field::new("item", elements.data_type().clone(), true)),
373+
OffsetBuffer::new(vec![0i32, 3].into()),
374+
elements,
375+
None,
376+
))
377+
};
378+
379+
let mut from_hidden = vec![42u32; 1];
380+
create_murmur3_hashes(&[as_list(with_hidden)], &mut from_hidden).unwrap();
381+
let mut from_null = vec![42u32; 1];
382+
create_murmur3_hashes(&[as_list(without_hidden)], &mut from_null).unwrap();
383+
384+
assert_eq!(
385+
from_hidden, from_null,
386+
"a null struct element must hash the same regardless of its child buffer"
387+
);
388+
}
389+
305390
#[test]
306391
fn test_i8() {
307392
test_murmur3_hash::<i8, Int8Array>(

‎native/spark-expr/src/hash_funcs/utils.rs‎

Lines changed: 24 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -828,8 +828,30 @@ macro_rules! create_hashes_internal {
828828
}
829829
DataType::Struct(_) => {
830830
let struct_array = col.as_any().downcast_ref::<StructArray>().unwrap();
831-
// Hash each field of the struct - Spark hashes all fields recursively
832-
let columns: Vec<ArrayRef> = struct_array.columns().to_vec();
831+
// Hash each field of the struct - Spark hashes all fields recursively.
832+
//
833+
// Arrow keeps a struct's children validity independent of the parent's, so at a
834+
// row where the struct is null a child buffer can still hold a value. Spark
835+
// hashes a null struct as the seed, so the parent's nulls have to be pushed
836+
// into each child before recursing, the same way #4432 fixed `GetStructField`.
837+
// Without it a null struct hashes whatever happens to sit in the child slot.
838+
// `flatten` does exactly this union, and skips revalidating the child data
839+
// buffers: it only ever adds nulls, so the buffers themselves are unchanged.
840+
// Rebuilding them through the checked builder would rescan every child buffer
841+
// (for a string child, the whole UTF-8 values buffer) on each call, and this
842+
// branch is reached once per element when hashing a list of structs.
843+
//
844+
// Only call it when there is actually a null to push down. `flatten` returns
845+
// early when there is no null buffer at all, but with a buffer present it
846+
// builds a fresh `Fields` with every non-nullable field re-marked nullable,
847+
// which this call site discards. So the case worth skipping is a buffer that
848+
// is present and all-valid -- what slicing leaves behind -- which would
849+
// otherwise pay a `Vec` and an `Arc<[FieldRef]>` for nothing. `NullBuffer`
850+
// caches its null count, so the test itself is O(1).
851+
let columns: Vec<ArrayRef> = match struct_array.nulls() {
852+
Some(nulls) if nulls.null_count() > 0 => struct_array.flatten().1,
853+
_ => struct_array.columns().to_vec(),
854+
};
833855
if !columns.is_empty() {
834856
$recursive_hash_method(&columns, $hashes_buffer)?;
835857
}

‎native/spark-expr/src/hash_funcs/xxhash64.rs‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -208,6 +208,72 @@ mod tests {
208208
assert_eq!(from_dict, from_decoded);
209209
}
210210

211+
/// The struct branch is shared with murmur3 through `create_hashes_internal!`, so the parent
212+
/// null mask has to reach xxhash64's children too. See #4432 for the same problem in
213+
/// `GetStructField`.
214+
#[test]
215+
fn test_null_struct_ignores_hidden_child_values() {
216+
use arrow::array::StructArray;
217+
use arrow::buffer::NullBuffer;
218+
use arrow::datatypes::{DataType, Field, Fields};
219+
220+
let fields: Fields = vec![Arc::new(Field::new("a", DataType::Int32, true))].into();
221+
let nulls = NullBuffer::from(vec![true, false]);
222+
let hidden: ArrayRef = Arc::new(StructArray::new(
223+
fields.clone(),
224+
vec![Arc::new(Int32Array::from(vec![Some(1), Some(999)])) as ArrayRef],
225+
Some(nulls.clone()),
226+
));
227+
let plain: ArrayRef = Arc::new(StructArray::new(
228+
fields,
229+
vec![Arc::new(Int32Array::from(vec![Some(1), None])) as ArrayRef],
230+
Some(nulls),
231+
));
232+
233+
let mut a = vec![42u64; 2];
234+
create_xxhash64_hashes(&[hidden], &mut a).unwrap();
235+
let mut b = vec![42u64; 2];
236+
create_xxhash64_hashes(&[plain], &mut b).unwrap();
237+
assert_eq!(a, b, "a null struct must hash the same either way");
238+
assert_eq!(a[1], 42, "a null struct must leave the seed untouched");
239+
}
240+
241+
/// Companion to the murmur3 case: the struct branch is shared through the macro, so the
242+
/// per-element route needs covering here too.
243+
#[test]
244+
fn test_null_struct_element_of_list_ignores_hidden_child_values() {
245+
use arrow::array::{ListArray, StructArray};
246+
use arrow::buffer::{NullBuffer, OffsetBuffer};
247+
use arrow::datatypes::{DataType, Field, Fields};
248+
249+
let fields: Fields = vec![Arc::new(Field::new("a", DataType::Int32, true))].into();
250+
let element_nulls = NullBuffer::from(vec![true, false, true]);
251+
let with_hidden: ArrayRef = Arc::new(StructArray::new(
252+
fields.clone(),
253+
vec![Arc::new(Int32Array::from(vec![Some(1), Some(999), Some(3)])) as ArrayRef],
254+
Some(element_nulls.clone()),
255+
));
256+
let without_hidden: ArrayRef = Arc::new(StructArray::new(
257+
fields,
258+
vec![Arc::new(Int32Array::from(vec![Some(1), None, Some(3)])) as ArrayRef],
259+
Some(element_nulls),
260+
));
261+
let as_list = |elements: ArrayRef| -> ArrayRef {
262+
Arc::new(ListArray::new(
263+
Arc::new(Field::new("item", elements.data_type().clone(), true)),
264+
OffsetBuffer::new(vec![0i32, 3].into()),
265+
elements,
266+
None,
267+
))
268+
};
269+
270+
let mut from_hidden = vec![42u64; 1];
271+
create_xxhash64_hashes(&[as_list(with_hidden)], &mut from_hidden).unwrap();
272+
let mut from_null = vec![42u64; 1];
273+
create_xxhash64_hashes(&[as_list(without_hidden)], &mut from_null).unwrap();
274+
assert_eq!(from_hidden, from_null);
275+
}
276+
211277
#[test]
212278
fn test_i8() {
213279
test_xxhash64_hash::<i8, Int8Array>(

‎spark/src/test/scala/org/apache/comet/CometHashExpressionSuite.scala‎

Lines changed: 96 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,9 @@ package org.apache.comet
2121

2222
import scala.util.Random
2323

24-
import org.apache.spark.sql.CometTestBase
24+
import org.apache.spark.sql.{CometTestBase, Row}
2525
import org.apache.spark.sql.execution.adaptive.AdaptiveSparkPlanHelper
26+
import org.apache.spark.sql.types.{IntegerType, StructField, StructType}
2627

2728
import org.apache.comet.testing.{DataGenOptions, FuzzDataGenerator, ParquetGenerator, SchemaGenOptions}
2829

@@ -256,6 +257,100 @@ class CometHashExpressionSuite extends CometTestBase with AdaptiveSparkPlanHelpe
256257
}
257258
}
258259

260+
test("hash - null struct with a required child field") {
261+
// `c` is nullable but its child is REQUIRED, so Spark writes
262+
// `optional group c { required int32 a; }`. On read the child leaf has nowhere to record a
263+
// null of its own, so its buffer holds a value at exactly the rows where the struct is null.
264+
// That is the shape where the parent's null mask has to reach the children; a struct built in
265+
// the plan, or one whose child is also nullable, has null children there and hides the bug.
266+
withTempPath { dir =>
267+
val schema = StructType(
268+
Seq(
269+
StructField(
270+
"c",
271+
StructType(Seq(StructField("a", IntegerType, nullable = false))),
272+
nullable = true)))
273+
withSQLConf(CometConf.COMET_ENABLED.key -> "false") {
274+
val rows = Seq(Row(Row(1)), Row(null), Row(Row(3)), Row(null))
275+
spark
276+
.createDataFrame(spark.sparkContext.parallelize(rows), schema)
277+
.coalesce(1)
278+
.write
279+
.parquet(dir.toString)
280+
}
281+
spark.read.parquet(dir.toString).createOrReplaceTempView("null_struct_t")
282+
checkSparkAnswerAndOperator("SELECT hash(c), xxhash64(c) FROM null_struct_t ORDER BY 1, 2")
283+
}
284+
}
285+
286+
test("hash - null struct whose child is itself a struct") {
287+
// The union has to recurse: the outer struct's nulls reach the inner struct, whose own
288+
// children are required and so carry values under the null.
289+
withTempPath { dir =>
290+
val inner = StructType(Seq(StructField("x", IntegerType, nullable = false)))
291+
val schema = StructType(
292+
Seq(
293+
StructField(
294+
"c",
295+
StructType(Seq(StructField("b", inner, nullable = false))),
296+
nullable = true)))
297+
withSQLConf(CometConf.COMET_ENABLED.key -> "false") {
298+
val rows = Seq(Row(Row(Row(1))), Row(null), Row(Row(Row(3))), Row(null))
299+
spark
300+
.createDataFrame(spark.sparkContext.parallelize(rows), schema)
301+
.coalesce(1)
302+
.write
303+
.parquet(dir.toString)
304+
}
305+
spark.read.parquet(dir.toString).createOrReplaceTempView("null_nested_struct_t")
306+
checkSparkAnswerAndOperator(
307+
"SELECT hash(c), xxhash64(c) FROM null_nested_struct_t ORDER BY 1, 2")
308+
}
309+
}
310+
311+
test("hash - list element wrapping a null struct with a required child field") {
312+
// The per-element path in `hash_list_array!`, which #5567 made usable as a shuffle key.
313+
//
314+
// Wrapping the struct rather than using it as the element directly is what makes this
315+
// reachable: `array(named_struct('tag', 1, 'b', c))` produces an element that is itself
316+
// valid, so it is copied rather than rebuilt, and the null `c` inside it keeps the child
317+
// values Parquet wrote under it. Using `c` as the element directly does not reproduce,
318+
// because a null element is rebuilt on the way in and the hidden values go with it.
319+
//
320+
// So this covers a null struct nested inside a valid element. The unit test in murmur3.rs
321+
// covers the complementary shape, where the element itself is the null struct.
322+
withTempPath { dir =>
323+
val schema = StructType(
324+
Seq(
325+
StructField(
326+
"c",
327+
StructType(Seq(StructField("a", IntegerType, nullable = false))),
328+
nullable = true)))
329+
withSQLConf(CometConf.COMET_ENABLED.key -> "false") {
330+
val rows = Seq(Row(Row(1)), Row(null), Row(Row(3)), Row(null))
331+
spark
332+
.createDataFrame(spark.sparkContext.parallelize(rows), schema)
333+
.coalesce(1)
334+
.write
335+
.parquet(dir.toString)
336+
}
337+
spark.read.parquet(dir.toString).createOrReplaceTempView("wrapped_null_struct_t")
338+
339+
checkSparkAnswerAndOperator("""
340+
SELECT
341+
hash(array(named_struct('tag', 1, 'b', c))),
342+
xxhash64(array(named_struct('tag', 1, 'b', c)))
343+
FROM wrapped_null_struct_t ORDER BY 1, 2""")
344+
345+
// Two elements, so the hash of the second chains onto the first.
346+
checkSparkAnswerAndOperator("""
347+
SELECT
348+
hash(array(named_struct('tag', 1, 'b', c), named_struct('tag', 2, 'b', c))),
349+
xxhash64(array(named_struct('tag', 1, 'b', c), named_struct('tag', 2, 'b', c)))
350+
FROM wrapped_null_struct_t ORDER BY 1, 2""")
351+
}
352+
}
353+
259354
test("hash - struct with array field") {
260355
withTable("t") {
261356
sql("CREATE TABLE t(c STRUCT<a: INT, b: ARRAY<STRING>>) USING parquet")

0 commit comments

Comments
 (0)