Skip to content

Commit 6e4d9ba

Browse files
authored
fix: Spark map_from_arrays, map_from_entries for sliced lists (apache#25431)
## Which issue does this PR close? - Closes apache#25419. ## Rationale for this change In `datafusion-spark`, `map_from_arrays` and `map_from_entries` return wrong results when their input list array is sliced. The values are correct, but the keys come from rows outside the slice. ## What changes are included in this PR? * Fix the shared helper `map_deduplicate_keys` to behave correctly by slicing the input key range down to only the currently visible keys * Add `debug_assert` to check a useful invariant * Update various comments * Add unit tests * Add SLTs ## What is the testing strategy for this PR? Existing tests pass, new tests added. ## Are there any user-facing changes? No, aside from bugfix.
1 parent d967e68 commit 6e4d9ba

3 files changed

Lines changed: 153 additions & 6 deletions

File tree

‎datafusion/spark/src/function/map/utils.rs‎

Lines changed: 125 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -164,10 +164,14 @@ fn map_deduplicate_keys(
164164
let offsets_len = keys_offsets.len();
165165
let mut new_offsets = Vec::with_capacity(offsets_len);
166166

167-
let mut cur_keys_offset = keys_offsets
167+
// For a sliced list the offsets do not start at 0: `flat_keys` and
168+
// `flat_values` are the full child arrays, and only the elements in
169+
// `offsets[0]..offsets[len]` belong to the input rows.
170+
let first_keys_offset = keys_offsets
168171
.first()
169172
.map(|offset| *offset as usize)
170173
.unwrap_or(0);
174+
let mut cur_keys_offset = first_keys_offset;
171175
let mut cur_values_offset = values_offsets
172176
.first()
173177
.map(|offset| *offset as usize)
@@ -178,9 +182,11 @@ fn map_deduplicate_keys(
178182

179183
// Mirror Spark's `ArrayBasedMapBuilder`: the first occurrence of a key
180184
// fixes its position in the output; under LAST_WIN a later duplicate
181-
// overwrites that slot's value. `keys_mask` selects the first-seen keys,
182-
// `value_indices` records the source index in `flat_values` to materialize
183-
// for each output slot (updated in place on overwrite).
185+
// overwrites that slot's value. `keys_mask` selects the first-seen keys
186+
// and has one bit per key entry of the input rows, so bit 0 corresponds to
187+
// `flat_keys[first_keys_offset]`. `value_indices` records the source index
188+
// in `flat_values` to materialize for each output slot (updated in place
189+
// on overwrite).
184190
let mut keys_mask_builder = BooleanBuilder::new();
185191
let mut value_indices: Vec<i32> = Vec::new();
186192
let mut key_to_output_idx: HashMap<ScalarValue, usize> = HashMap::new();
@@ -231,15 +237,19 @@ fn map_deduplicate_keys(
231237
}
232238
} else {
233239
// The result entry is NULL — no keys/values emitted. Still pad the
234-
// mask so it stays aligned with `flat_keys`.
240+
// mask so it stays aligned with the key entries of later rows.
235241
keys_mask_builder.append_n(num_keys_entries, false);
236242
}
237243
new_offsets.push(new_last_offset);
238244
cur_keys_offset += num_keys_entries;
239245
cur_values_offset += num_values_entries;
240246
}
241247
let keys_mask = keys_mask_builder.finish();
242-
let needed_keys = filter(&flat_keys, &keys_mask)?;
248+
// Every key entry of the input rows must have exactly one mask bit;
249+
// otherwise the mask selects the wrong keys for all later rows.
250+
debug_assert_eq!(keys_mask.len(), cur_keys_offset - first_keys_offset);
251+
let input_keys = flat_keys.slice(first_keys_offset, keys_mask.len());
252+
let needed_keys = filter(&input_keys, &keys_mask)?;
243253
let value_indices_array = Int32Array::from(value_indices);
244254
let needed_values = take(&flat_values, &value_indices_array, None)?;
245255
let offsets = OffsetBuffer::new(new_offsets.into());
@@ -250,6 +260,7 @@ fn map_deduplicate_keys(
250260
mod tests {
251261
use super::*;
252262
use arrow::array::{Int32Array, StringArray};
263+
use arrow::datatypes::Int32Type;
253264

254265
fn int32_utf8_inputs(
255266
keys: Vec<i32>,
@@ -372,4 +383,112 @@ mod tests {
372383
assert!(map.is_null(0));
373384
assert!(!map.is_null(1));
374385
}
386+
387+
/// Returns the flattened `(key, value)` entries of an Int32 -> Utf8 map.
388+
fn int32_utf8_entries(map: &MapArray) -> Vec<(i32, Option<String>)> {
389+
let keys = map.keys().as_primitive::<Int32Type>();
390+
let values = map.values().as_string::<i32>();
391+
keys.values()
392+
.iter()
393+
.zip(values.iter())
394+
.map(|(k, v)| (*k, v.map(str::to_string)))
395+
.collect()
396+
}
397+
398+
#[test]
399+
fn sliced_input_reads_keys_and_values_from_offset_range() {
400+
let (keys, values) = int32_utf8_inputs(
401+
vec![99, 98, 97, 1, 2, 3, 96],
402+
vec![Some("z"), Some("a"), Some("b"), Some("c"), Some("y")],
403+
);
404+
let keys_offsets = [3i32, 5, 6];
405+
let values_offsets = [1i32, 3, 4];
406+
407+
let result = map_from_keys_values_offsets_nulls(
408+
&keys,
409+
&values,
410+
&keys_offsets,
411+
&values_offsets,
412+
None,
413+
None,
414+
false,
415+
)
416+
.unwrap();
417+
418+
let map = result.as_map();
419+
assert_eq!(map.value_offsets(), &[0, 2, 3]);
420+
assert_eq!(
421+
int32_utf8_entries(map),
422+
vec![
423+
(1, Some("a".to_string())),
424+
(2, Some("b".to_string())),
425+
(3, Some("c".to_string())),
426+
]
427+
);
428+
}
429+
430+
#[test]
431+
fn sliced_input_last_win() {
432+
let (keys, values) = int32_utf8_inputs(
433+
vec![99, 1, 2, 1, 96],
434+
vec![Some("z"), Some("y"), Some("a"), Some("b"), Some("c")],
435+
);
436+
let keys_offsets = [1i32, 4];
437+
let values_offsets = [2i32, 5];
438+
439+
let result = map_from_keys_values_offsets_nulls(
440+
&keys,
441+
&values,
442+
&keys_offsets,
443+
&values_offsets,
444+
None,
445+
None,
446+
true,
447+
)
448+
.unwrap();
449+
450+
let map = result.as_map();
451+
assert_eq!(map.value_offsets(), &[0, 2]);
452+
assert_eq!(
453+
int32_utf8_entries(map),
454+
vec![(1, Some("c".to_string())), (2, Some("b".to_string()))]
455+
);
456+
}
457+
458+
#[test]
459+
fn sliced_input_null_row() {
460+
// Row 0 is NULL; its (duplicate) keys are skipped but still occupy
461+
// positions in the child array ahead of row 1's keys.
462+
let (keys, values) = int32_utf8_inputs(
463+
vec![99, 1, 1, 2, 3],
464+
vec![
465+
Some("z"),
466+
Some("dup-a"),
467+
Some("dup-b"),
468+
Some("x"),
469+
Some("y"),
470+
],
471+
);
472+
let offsets = [1i32, 3, 5];
473+
let keys_nulls = NullBuffer::from(vec![false, true]);
474+
475+
let result = map_from_keys_values_offsets_nulls(
476+
&keys,
477+
&values,
478+
&offsets,
479+
&offsets,
480+
Some(&keys_nulls),
481+
None,
482+
false,
483+
)
484+
.unwrap();
485+
486+
let map = result.as_map();
487+
assert_eq!(map.value_offsets(), &[0, 0, 2]);
488+
assert!(map.is_null(0));
489+
assert_eq!(
490+
int32_utf8_entries(map),
491+
vec![(2, Some("x".to_string())), (3, Some("y".to_string()))]
492+
);
493+
}
375494
}

‎datafusion/sqllogictest/test_files/spark/map/map_from_arrays.slt‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -185,3 +185,17 @@ NULL
185185

186186
statement ok
187187
set datafusion.spark.map_key_dedup_policy = 'EXCEPTION';
188+
189+
# Sliced input: OFFSET makes the function see list arrays whose first offset is
190+
# non-zero, so the child arrays still contain the skipped row's elements.
191+
query ?
192+
SELECT map_from_arrays(a, b)
193+
FROM (
194+
SELECT * FROM values
195+
(array[99, 98], array['x', 'y'], 1),
196+
(array[1, 2], array['a', 'b'], 2)
197+
AS tab(a, b, id)
198+
ORDER BY id LIMIT 1 OFFSET 1
199+
);
200+
----
201+
{1: a, 2: b}

‎datafusion/sqllogictest/test_files/spark/map/map_from_entries.slt‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -215,3 +215,17 @@ AS tab(data);
215215

216216
statement ok
217217
set datafusion.spark.map_key_dedup_policy = 'EXCEPTION';
218+
219+
# Sliced input: OFFSET makes the function see a list array whose first offset is
220+
# non-zero, so the child array still contains the skipped row's entries.
221+
query ?
222+
SELECT map_from_entries(data)
223+
FROM (
224+
SELECT * FROM values
225+
(array[struct(99, 'x'), struct(98, 'y')], 1),
226+
(array[struct(1, 'a'), struct(2, 'b')], 2)
227+
AS tab(data, id)
228+
ORDER BY id LIMIT 1 OFFSET 1
229+
);
230+
----
231+
{1: a, 2: b}

0 commit comments

Comments
 (0)