Skip to content

Commit 287d1b4

Browse files
fix: map_from_arrays/map_from_entries pair wrong keys and values for sliced lists (apache#25419)
map_deduplicate_keys selected the output keys with a boolean mask built only over the entries processed for the current input rows, then applied that mask to the full (unsliced) flat keys array via `filter`. `filter` treats the mask as starting at index 0 of the array, so whenever the input list array was sliced (e.g. by an upstream ORDER BY + LIMIT/OFFSET) and its offsets did not start at 0, the wrong keys were selected while values (selected via `take` with absolute indices) remained correct. Fix by selecting keys the same way as values: track the absolute index of each kept key in `flat_keys` and materialize them with `take`, instead of filtering with a mask that implicitly assumes the array starts at offset 0.
1 parent 62f039f commit 287d1b4

3 files changed

Lines changed: 80 additions & 17 deletions

File tree

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

Lines changed: 48 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -19,11 +19,9 @@ use std::borrow::Cow;
1919
use std::collections::HashMap;
2020
use std::sync::Arc;
2121

22-
use arrow::array::{
23-
Array, ArrayRef, AsArray, BooleanBuilder, Int32Array, MapArray, StructArray,
24-
};
22+
use arrow::array::{Array, ArrayRef, AsArray, Int32Array, MapArray, StructArray};
2523
use arrow::buffer::{NullBuffer, OffsetBuffer};
26-
use arrow::compute::{filter, take};
24+
use arrow::compute::take;
2725
use arrow::datatypes::{DataType, Field, Fields};
2826
use datafusion_common::{Result, ScalarValue, exec_err};
2927

@@ -178,10 +176,13 @@ fn map_deduplicate_keys(
178176

179177
// Mirror Spark's `ArrayBasedMapBuilder`: the first occurrence of a key
180178
// 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).
184-
let mut keys_mask_builder = BooleanBuilder::new();
179+
// overwrites that slot's value. `key_indices`/`value_indices` record the
180+
// source index in `flat_keys`/`flat_values` to materialize for each
181+
// output slot (the value index is updated in place on overwrite). These
182+
// are absolute indices into the flattened arrays, which is required
183+
// because `flat_keys`/`flat_values` are not rebased to the start of the
184+
// (possibly sliced) input lists.
185+
let mut key_indices: Vec<i32> = Vec::new();
185186
let mut value_indices: Vec<i32> = Vec::new();
186187
let mut key_to_output_idx: HashMap<ScalarValue, usize> = HashMap::new();
187188
for (row_idx, (next_keys_offset, next_values_offset)) in keys_offsets
@@ -209,12 +210,12 @@ fn map_deduplicate_keys(
209210
cur_keys_offset + cur_entry_idx,
210211
)?
211212
.compacted();
213+
let abs_key_idx = (cur_keys_offset + cur_entry_idx) as i32;
212214
let abs_value_idx = (cur_values_offset + cur_entry_idx) as i32;
213215

214216
if let Some(&output_idx) = key_to_output_idx.get(&key) {
215217
if last_value_wins {
216218
value_indices[output_idx] = abs_value_idx;
217-
keys_mask_builder.append_value(false);
218219
continue;
219220
}
220221
return exec_err!(
@@ -224,22 +225,18 @@ fn map_deduplicate_keys(
224225
`datafusion.spark.map_key_dedup_policy` to `LAST_WIN`."
225226
);
226227
}
227-
keys_mask_builder.append_value(true);
228-
key_to_output_idx.insert(key, value_indices.len());
228+
key_to_output_idx.insert(key, key_indices.len());
229+
key_indices.push(abs_key_idx);
229230
value_indices.push(abs_value_idx);
230231
new_last_offset += 1;
231232
}
232-
} else {
233-
// The result entry is NULL — no keys/values emitted. Still pad the
234-
// mask so it stays aligned with `flat_keys`.
235-
keys_mask_builder.append_n(num_keys_entries, false);
236233
}
237234
new_offsets.push(new_last_offset);
238235
cur_keys_offset += num_keys_entries;
239236
cur_values_offset += num_values_entries;
240237
}
241-
let keys_mask = keys_mask_builder.finish();
242-
let needed_keys = filter(&flat_keys, &keys_mask)?;
238+
let key_indices_array = Int32Array::from(key_indices);
239+
let needed_keys = take(&flat_keys, &key_indices_array, None)?;
243240
let value_indices_array = Int32Array::from(value_indices);
244241
let needed_values = take(&flat_values, &value_indices_array, None)?;
245242
let offsets = OffsetBuffer::new(new_offsets.into());
@@ -343,6 +340,40 @@ mod tests {
343340
assert_eq!(map.value_offsets(), &[0, 0]);
344341
}
345342

343+
#[test]
344+
fn offsets_not_starting_at_zero_use_absolute_indices() {
345+
// Simulates a sliced list array: `flat_keys`/`flat_values` still hold
346+
// all rows' data, but `keys_offsets`/`values_offsets` only describe a
347+
// single row whose entries start partway through the flat arrays
348+
// (as happens after an upstream operator like LIMIT/OFFSET slices
349+
// the input). The keys must still be paired with the values from
350+
// that same row, not with whatever happens to sit at the start of
351+
// the flat arrays.
352+
let (keys, values) = int32_utf8_inputs(
353+
vec![99, 98, 1, 2],
354+
vec![Some("dummy1"), Some("dummy2"), Some("a"), Some("b")],
355+
);
356+
let offsets = [2i32, 4];
357+
358+
let result = map_from_keys_values_offsets_nulls(
359+
&keys, &values, &offsets, &offsets, None, None, false,
360+
)
361+
.unwrap();
362+
363+
let map = result.as_map();
364+
assert_eq!(map.len(), 1);
365+
let entries = map.value(0);
366+
let keys_col = entries
367+
.column(0)
368+
.as_primitive::<arrow::datatypes::Int32Type>();
369+
let values_col = entries.column(1).as_string::<i32>();
370+
assert_eq!(keys_col.values(), &[1, 2]);
371+
assert_eq!(
372+
values_col.iter().collect::<Vec<_>>(),
373+
vec![Some("a"), Some("b")]
374+
);
375+
}
376+
346377
#[test]
347378
fn null_row_is_skipped_and_not_checked() {
348379
// Row 0 is NULL (keys null). Its duplicate keys should be ignored;

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

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

186186
statement ok
187187
set datafusion.spark.map_key_dedup_policy = 'EXCEPTION';
188+
189+
# Regression test for https://github.com/apache/datafusion/issues/25419
190+
# ORDER BY + LIMIT/OFFSET produces sliced list arrays whose offsets do not
191+
# start at 0; the keys must still be paired with the values from the same row.
192+
statement ok
193+
CREATE TABLE sliced_arrays AS VALUES ([99, 98], [990, 980]), ([1, 2], [10, 20]);
194+
195+
query ?
196+
SELECT map_from_arrays(column1, column2)
197+
FROM (SELECT * FROM sliced_arrays ORDER BY column2 DESC LIMIT 1 OFFSET 1) s;
198+
----
199+
{1: 10, 2: 20}
200+
201+
statement ok
202+
DROP TABLE sliced_arrays;

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

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

216216
statement ok
217217
set datafusion.spark.map_key_dedup_policy = 'EXCEPTION';
218+
219+
# Regression test for https://github.com/apache/datafusion/issues/25419
220+
# ORDER BY + LIMIT/OFFSET produces sliced list arrays whose offsets do not
221+
# start at 0; the keys must still be paired with the values from the same row.
222+
statement ok
223+
CREATE TABLE sliced_entries AS VALUES
224+
([struct(99, 990), struct(98, 980)], 1),
225+
([struct(1, 10), struct(2, 20)], 2);
226+
227+
query ?
228+
SELECT map_from_entries(column1)
229+
FROM (SELECT * FROM sliced_entries ORDER BY column2 LIMIT 1 OFFSET 1) s;
230+
----
231+
{1: 10, 2: 20}
232+
233+
statement ok
234+
DROP TABLE sliced_entries;

0 commit comments

Comments
 (0)