Skip to content

Commit 924d571

Browse files
AdamGSthorrester
authored andcommitted
fix: Handle nulls correctly when extracting nested arrays from nullable struct/map (apache#25122)
## Which issue does this PR close? - Closes apache#25120. ## Rationale for this change Fixes null handling when accessing nested map/struct arrays by AND-ing the null buffers as we go down into the array tree. Running the `get_field` benchmarks on my M3 macbook, one micro benchmark has a small repeatable regression: ``` get_field_map_1024_entries_4_first time: [18.811 µs 18.881 µs 18.954 µs] change: [+6.4039% +6.8632% +7.3094%] (p = 0.00 < 0.05) Performance has regressed. ``` ## What changes are included in this PR? Taking parent nulls into account when extracting nested arrays from map/struct arrays. ## What is the testing strategy for this PR? Additional unit tests and SLT tests. ## Are there any user-facing changes? Correct behavior. --------- Signed-off-by: Adam Gutglick <[email protected]> (cherry picked from commit 140c7c5)
1 parent 505af5f commit 924d571

5 files changed

Lines changed: 307 additions & 40 deletions

File tree

‎datafusion/functions/src/core/getfield.rs‎

Lines changed: 268 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -18,10 +18,12 @@
1818
use std::sync::{Arc, OnceLock};
1919

2020
use arrow::array::{
21-
Array, Capacities, MutableArrayData, Scalar, cast::AsArray, make_array,
21+
Array, ArrayRef, Capacities, MutableArrayData, Scalar, cast::AsArray, make_array,
2222
make_comparator,
2323
};
24-
use arrow::compute::SortOptions;
24+
use arrow::array::{BooleanArray, layout};
25+
use arrow::buffer::NullBuffer;
26+
use arrow::compute::{SortOptions, nullif};
2527
use arrow::datatypes::{DataType, Field, FieldRef};
2628

2729
use datafusion_common::cast::{as_map_array, as_struct_array};
@@ -125,6 +127,10 @@ fn process_map_array(
125127
let matches = keys.values();
126128

127129
for entry in 0..map_array.len() {
130+
if map_array.is_null(entry) {
131+
mutable.try_extend_nulls(1)?;
132+
continue;
133+
}
128134
let start = offsets[entry] as usize;
129135
let end = offsets[entry + 1] as usize;
130136

@@ -160,6 +166,10 @@ fn process_map_with_nested_key(
160166
MutableArrayData::with_capacities(vec![&original_data], true, capacity);
161167

162168
for entry in 0..map_array.len() {
169+
if map_array.is_null(entry) {
170+
mutable.try_extend_nulls(1)?;
171+
continue;
172+
}
163173
let start = map_array.value_offsets()[entry] as usize;
164174
let end = map_array.value_offsets()[entry + 1] as usize;
165175

@@ -182,6 +192,46 @@ fn process_map_with_nested_key(
182192
Ok(ColumnarValue::Array(data))
183193
}
184194

195+
/// Apply a struct's nulls to one of its fields.
196+
fn apply_parent_nulls(
197+
col: &ArrayRef,
198+
parent_nulls: Option<&NullBuffer>,
199+
) -> Result<ArrayRef> {
200+
let Some(parent_nulls) = parent_nulls else {
201+
// If there are no parent nulls to apply, we can just return
202+
return Ok(Arc::clone(col));
203+
};
204+
205+
// NullArray is already entirely null and cannot have a validity bitmap.
206+
// If we have 0 parent nulls, we can also avoid extra work.
207+
if col.data_type().is_null() || parent_nulls.null_count() == 0 {
208+
return Ok(Arc::clone(col));
209+
}
210+
211+
if layout(col.data_type()).can_contain_null_mask {
212+
// `nullif` marks a row null where the mask is true and keeps the
213+
// field's own nulls. Only the validity bitmap is rebuilt; the value
214+
// buffers and child arrays are shared with `col`.
215+
let null_parents = BooleanArray::new(!parent_nulls.inner(), None);
216+
return Ok(nullif(col.as_ref(), &null_parents)?);
217+
}
218+
219+
// Unions and run-end encoded arrays have no validity bitmap of their own
220+
// and represent nulls in their children. Rebuild the array so null parents
221+
// become null values in those children.
222+
let data = col.to_data();
223+
let mut mutable = MutableArrayData::new(vec![&data], true, data.len());
224+
let mut end = 0;
225+
for (start, valid_end) in parent_nulls.valid_slices() {
226+
mutable.try_extend_nulls(start - end)?;
227+
mutable.try_extend(0, start, valid_end)?;
228+
end = valid_end;
229+
}
230+
mutable.try_extend_nulls(data.len() - end)?;
231+
232+
Ok(make_array(mutable.freeze()))
233+
}
234+
185235
/// Extract a single field from a struct or map array
186236
fn extract_single_field(base: ColumnarValue, name: ScalarValue) -> Result<ColumnarValue> {
187237
let arrays = ColumnarValue::values_to_arrays(&[base])?;
@@ -204,9 +254,8 @@ fn extract_single_field(base: ColumnarValue, name: ScalarValue) -> Result<Column
204254
"Field {field_name} not found in dictionary struct"
205255
)
206256
})?;
207-
Ok(ColumnarValue::Array(
208-
dict.with_values(Arc::clone(field_col)),
209-
))
257+
let field_col = apply_parent_nulls(field_col, values_struct.nulls())?;
258+
Ok(ColumnarValue::Array(dict.with_values(field_col)))
210259
}
211260
(DataType::Map(_, _), key, _) => {
212261
// The lookup key is a single scalar. `eq` does not support nested
@@ -222,7 +271,10 @@ fn extract_single_field(base: ColumnarValue, name: ScalarValue) -> Result<Column
222271
let as_struct_array = as_struct_array(&array)?;
223272
match as_struct_array.column_by_name(&k) {
224273
None => exec_err!("Field {k} not found in struct"),
225-
Some(col) => Ok(ColumnarValue::Array(Arc::clone(col))),
274+
Some(col) => Ok(ColumnarValue::Array(apply_parent_nulls(
275+
col,
276+
as_struct_array.nulls(),
277+
)?)),
226278
}
227279
}
228280
(DataType::Struct(_), name, _) => exec_err!(
@@ -695,10 +747,10 @@ impl ScalarUDFImpl for GetFieldFunc {
695747
mod tests {
696748
use super::*;
697749
use arrow::array::{
698-
ArrayRef, Int32Array, Int32Builder, ListArray, ListBuilder, MapBuilder,
699-
StructArray,
750+
ArrayRef, Int32Array, Int32Builder, ListArray, ListBuilder, MapBuilder, RunArray,
751+
StructArray, UnionArray,
700752
};
701-
use arrow::datatypes::{Fields, Int32Type};
753+
use arrow::datatypes::{Fields, Int32Type, UnionFields};
702754

703755
#[test]
704756
fn test_get_field_utf8view_key() -> Result<()> {
@@ -771,6 +823,213 @@ mod tests {
771823
Ok(())
772824
}
773825

826+
#[test]
827+
fn test_get_field_nested_struct_outer_nulls() -> Result<()> {
828+
let inner_array = StructArray::new(
829+
vec![Field::new("value", DataType::Int32, false)].into(),
830+
vec![Arc::new(Int32Array::from(vec![1, 2, 3]))],
831+
None,
832+
);
833+
834+
// Only the outer struct marks row 1 as null; its children are all valid.
835+
let outer_array = StructArray::new(
836+
vec![Field::new("inner", inner_array.data_type().clone(), false)].into(),
837+
vec![Arc::new(inner_array)],
838+
Some(NullBuffer::from(vec![true, false, true])),
839+
);
840+
841+
for (input, expected) in [
842+
(outer_array.clone(), vec![Some(1), None, Some(3)]),
843+
(outer_array.slice(1, 2), vec![None, Some(3)]),
844+
] {
845+
let inner = extract_single_field(
846+
ColumnarValue::Array(Arc::new(input)),
847+
ScalarValue::Utf8(Some("inner".to_string())),
848+
)?;
849+
let result = extract_single_field(
850+
inner,
851+
ScalarValue::Utf8(Some("value".to_string())),
852+
)?
853+
.into_array(expected.len())?;
854+
855+
let expected = Int32Array::from(expected);
856+
assert_eq!(result.as_ref(), &expected as &dyn Array);
857+
}
858+
859+
Ok(())
860+
}
861+
862+
#[test]
863+
fn test_get_field_map_parent_nulls() -> Result<()> {
864+
use arrow::array::{FixedSizeListArray, MapArray};
865+
use arrow_buffer::OffsetBuffer;
866+
867+
let keys = Arc::new(Int32Array::from(vec![7; 3])) as ArrayRef;
868+
let nested_keys = Arc::new(FixedSizeListArray::new(
869+
Arc::new(Field::new("item", DataType::Int32, false)),
870+
1,
871+
Arc::clone(&keys),
872+
None,
873+
)) as ArrayRef;
874+
875+
// Exercise both map lookup paths. The null map has a valid matching entry.
876+
for keys in [keys, nested_keys] {
877+
let key = ScalarValue::try_from_array(keys.as_ref(), 0)?;
878+
let entries = StructArray::new(
879+
vec![
880+
Field::new("key", keys.data_type().clone(), false),
881+
Field::new("value", DataType::Int32, false),
882+
]
883+
.into(),
884+
vec![keys, Arc::new(Int32Array::from(vec![1, 2, 3]))],
885+
None,
886+
);
887+
let map = MapArray::new(
888+
Arc::new(Field::new("entries", entries.data_type().clone(), false)),
889+
OffsetBuffer::new(vec![0, 1, 2, 3].into()),
890+
entries,
891+
Some(NullBuffer::from(vec![true, false, true])),
892+
false,
893+
);
894+
let result = extract_single_field(ColumnarValue::Array(Arc::new(map)), key)?
895+
.into_array(3)?;
896+
let expected = Int32Array::from(vec![Some(1), None, Some(3)]);
897+
assert_eq!(result.as_ref(), &expected as &dyn Array);
898+
}
899+
Ok(())
900+
}
901+
902+
#[test]
903+
fn test_get_field_null_typed_child() -> Result<()> {
904+
use arrow::array::{DictionaryArray, NullArray, UInt32Array};
905+
use arrow::datatypes::UInt32Type;
906+
907+
let values = Arc::new(StructArray::new(
908+
vec![Field::new("value", DataType::Null, true)].into(),
909+
vec![Arc::new(NullArray::new(2))],
910+
Some(NullBuffer::from(vec![true, false])),
911+
)) as ArrayRef;
912+
let dictionary = Arc::new(DictionaryArray::<UInt32Type>::try_new(
913+
UInt32Array::from(vec![0, 1]),
914+
Arc::clone(&values),
915+
)?) as ArrayRef;
916+
917+
for input in [values, dictionary] {
918+
let result = extract_single_field(
919+
ColumnarValue::Array(input),
920+
ScalarValue::Utf8(Some("value".to_string())),
921+
)?
922+
.into_array(2)?;
923+
assert_eq!(result.logical_null_count(), 2);
924+
}
925+
Ok(())
926+
}
927+
928+
#[test]
929+
fn test_get_field_union_parent_nulls() -> Result<()> {
930+
use arrow::array::{DictionaryArray, StringArray, UInt32Array};
931+
use arrow::datatypes::UInt32Type;
932+
933+
let fields = UnionFields::try_new(
934+
[3, 7],
935+
[
936+
Field::new("int", DataType::Int32, true),
937+
Field::new("string", DataType::Utf8, true),
938+
],
939+
)?;
940+
let ints = Int32Array::from(vec![Some(9), Some(1), Some(2), None, Some(4)]);
941+
let strings = StringArray::from(vec!["x"; 5]);
942+
943+
// Dense rows 1 and 2 share a value, but only row 2 has a null parent.
944+
for offsets in [None, Some(vec![0, 1, 1, 3, 0].into())] {
945+
let child = UnionArray::try_new(
946+
fields.clone(),
947+
vec![7, 3, 3, 3, 7].into(),
948+
offsets,
949+
vec![Arc::new(ints.clone()), Arc::new(strings.clone())],
950+
)?;
951+
let union_type = child.data_type().clone();
952+
let parent = StructArray::new(
953+
vec![Field::new("u", union_type.clone(), true)].into(),
954+
vec![Arc::new(child)],
955+
Some(NullBuffer::from(vec![true, true, false, true, true])),
956+
);
957+
let values = Arc::new(parent.slice(1, 4)) as ArrayRef;
958+
let dictionary = Arc::new(DictionaryArray::<UInt32Type>::try_new(
959+
UInt32Array::from(vec![0, 1, 2, 3]),
960+
Arc::clone(&values),
961+
)?) as ArrayRef;
962+
963+
for input in [values, dictionary] {
964+
let result = extract_single_field(
965+
ColumnarValue::Array(input),
966+
ScalarValue::Utf8(Some("u".to_string())),
967+
)?
968+
.into_array(4)?;
969+
assert_eq!(
970+
result.logical_nulls(),
971+
Some(NullBuffer::from(vec![true, false, false, true]))
972+
);
973+
let result = match result.data_type() {
974+
DataType::Dictionary(_, _) => result.as_any_dictionary().values(),
975+
_ => &result,
976+
};
977+
assert_eq!(result.data_type(), &union_type);
978+
result.to_data().validate_full()?;
979+
let result = result.as_union();
980+
assert_eq!(result.value(0).as_ref(), &Int32Array::from(vec![1]));
981+
assert_eq!(result.value(3).as_ref(), &StringArray::from(vec!["x"]));
982+
}
983+
}
984+
Ok(())
985+
}
986+
987+
#[test]
988+
fn test_get_field_run_encoded_parent_nulls() -> Result<()> {
989+
// Logical values: [10, 10, 20, NULL, NULL]
990+
let run_ends = Int32Array::from(vec![2, 3, 5]);
991+
let values = Int32Array::from(vec![Some(10), Some(20), None]);
992+
let child = RunArray::<Int32Type>::try_new(&run_ends, &values)?;
993+
let run_type = child.data_type().clone();
994+
let parent = StructArray::new(
995+
vec![Field::new("r", run_type.clone(), true)].into(),
996+
vec![Arc::new(child)],
997+
Some(NullBuffer::from(vec![true, false, true, true, true])),
998+
);
999+
1000+
for (input, expected) in [
1001+
(
1002+
Arc::new(parent.clone()) as ArrayRef,
1003+
vec![Some(10), None, Some(20), None, None],
1004+
),
1005+
(
1006+
Arc::new(parent.slice(1, 4)) as ArrayRef,
1007+
vec![None, Some(20), None, None],
1008+
),
1009+
] {
1010+
let result = extract_single_field(
1011+
ColumnarValue::Array(input),
1012+
ScalarValue::Utf8(Some("r".to_string())),
1013+
)?
1014+
.into_array(expected.len())?;
1015+
assert_eq!(result.data_type(), &run_type);
1016+
result.to_data().validate_full()?;
1017+
1018+
let run_array = result.as_run::<Int32Type>();
1019+
let run_values = run_array.values().as_primitive::<Int32Type>();
1020+
let logical: Vec<Option<i32>> = (0..run_array.len())
1021+
.map(|i| {
1022+
let physical = run_array.get_physical_index(i);
1023+
run_values
1024+
.is_valid(physical)
1025+
.then(|| run_values.value(physical))
1026+
})
1027+
.collect();
1028+
assert_eq!(logical, expected);
1029+
}
1030+
Ok(())
1031+
}
1032+
7741033
#[test]
7751034
fn test_get_field_dict_encoded_struct() -> Result<()> {
7761035
use arrow::array::{DictionaryArray, StringArray, UInt32Array};

‎datafusion/sqllogictest/src/test_context.rs‎

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -693,23 +693,25 @@ fn register_dictionary_struct_table(ctx: &SessionContext) {
693693

694694
ctx.register_batch("dict_struct_table", batch).unwrap();
695695

696-
// Second table: dictionary-encoded struct with nullable entries
697-
let names_nullable = Arc::new(StringArray::from(vec!["X", "Y"])) as ArrayRef;
698-
let ids_nullable = Arc::new(Int32Array::from(vec![10, 20])) as ArrayRef;
696+
// Second table: null keys, null structs with valid children, and null children.
697+
let names_nullable =
698+
Arc::new(StringArray::from(vec!["X", "Y", "hidden"])) as ArrayRef;
699+
let ids_nullable =
700+
Arc::new(Int32Array::from(vec![Some(10), None, Some(30)])) as ArrayRef;
699701
let struct_fields_nullable: Fields = vec![
700702
Field::new("name", DataType::Utf8, false),
701-
Field::new("id", DataType::Int32, false),
703+
Field::new("id", DataType::Int32, true),
702704
]
703705
.into();
704706
let values_struct_nullable = Arc::new(
705707
StructArray::try_new(
706708
struct_fields_nullable.clone(),
707709
vec![names_nullable, ids_nullable],
708-
None,
710+
Some(vec![true, true, false].into()),
709711
)
710712
.unwrap(),
711713
) as ArrayRef;
712-
let keys_nullable = UInt32Array::from(vec![Some(0), None, Some(1), None]);
714+
let keys_nullable = UInt32Array::from(vec![Some(0), None, Some(1), Some(2), Some(2)]);
713715
let dict_nullable =
714716
DictionaryArray::<UInt32Type>::try_new(keys_nullable, values_struct_nullable)
715717
.unwrap();

0 commit comments

Comments
 (0)