Skip to content

Commit c9a3fbe

Browse files
authored
Drop null patch elements when sparse lists share their elements (#11182)
## Summary Since #11173, sparse lists with a null or empty fill reuse the patch lists' elements in their output. When the patch lists are already zero-copy to a list, `MakeExact` only trims the ends, so null patch lists keep their elements. Those elements are exported and written. This PR uses `MakeExactWithEmptyNulls` on the null or empty fill path so that null patches are lists of length 0. ## Changes - The shared-elements path rebuilds the patch lists with `MakeExactWithEmptyNulls`. - If null lists hold nothing, the rebuild returns the array as is; otherwise the elements become a lazy filter over the ranges valid lists use. - `empty_fill_reuses_elements` test now uses a null patch with no elements. Signed-off-by: Matt Katz <[email protected]>
1 parent fdd96d0 commit c9a3fbe

2 files changed

Lines changed: 43 additions & 11 deletions

File tree

‎encodings/sparse/src/canonical.rs‎

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -378,25 +378,25 @@ fn execute_sparse_lists(
378378
let indices = indices.reinterpret_cast(indices.ptype().to_unsigned());
379379
let fill_list = fill_value.as_list();
380380

381-
// Make the patch views contiguous and trim unused elements once. Empty-fill decoding can
382-
// share those elements directly; the nonempty-fill builder below can append contiguous
383-
// patch runs and use the exact element count when choosing an offset width.
384-
let values = resolved
385-
.values()
386-
.clone()
387-
.downcast::<ListView>()
388-
.rebuild(ListViewRebuildMode::MakeExact, ctx)?;
381+
let values = resolved.values().clone().downcast::<ListView>();
389382

390383
// Keep the builder for at most one valid list: there is no repeated element gather to
391384
// avoid, and constructing run-end offsets would add setup work.
392385
let patch_validity = values.listview_validity().execute_mask(values.len(), ctx)?;
393386
let use_shared_elements = patch_validity.true_count() > 1;
394387

395-
// Null lists also have no elements, so null and empty fills take the same path.
388+
// Null lists also have no elements, so null and empty fills take the same path. Its output
389+
// shares the patch elements, so drop the ones only null lists hold: exports and element-wise
390+
// functions would otherwise read elements that no valid row shows.
396391
if fill_list.is_empty() && use_shared_elements {
392+
let values = values.rebuild(ListViewRebuildMode::MakeExactWithEmptyNulls, ctx)?;
397393
return lists::empty_fill(resolved, values, fill_value, len, nullability, ctx);
398394
}
399395

396+
// Trim the patch elements to those the views reference, so the element count below is what
397+
// the builder will hold rather than an over-estimate.
398+
let values = values.rebuild(ListViewRebuildMode::MakeExact, ctx)?;
399+
400400
// Each gap between patches is appended as one constant array, whose canonical form points
401401
// every view at a single copy of the fill value, so a gap costs the fill value's elements once
402402
// however many rows it covers. Bound the number of gaps: there is at most one on either side of

‎encodings/sparse/src/canonical/lists/tests.rs‎

Lines changed: 34 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -27,10 +27,10 @@ fn empty_fill_reuses_elements(#[values(false, true)] null_fill: bool) -> VortexR
2727
crate::initialize(&session);
2828
let mut ctx = session.create_execution_ctx();
2929

30-
let elements = buffer![1i32, 2, 8, 9, 3].into_array();
30+
let elements = buffer![1i32, 2, 3].into_array();
3131
let lists = ListArray::try_new(
3232
elements.clone(),
33-
buffer![0u32, 2, 4, 5].into_array(),
33+
buffer![0u32, 2, 2, 3].into_array(),
3434
Validity::from_iter([true, false, true]),
3535
&mut ctx,
3636
)?;
@@ -69,6 +69,38 @@ fn empty_fill_reuses_elements(#[values(false, true)] null_fill: bool) -> VortexR
6969
Ok(())
7070
}
7171

72+
#[test]
73+
fn empty_fill_drops_null_patch_elements() -> VortexResult<()> {
74+
let session = VortexSession::empty();
75+
crate::initialize(&session);
76+
let mut ctx = session.create_execution_ctx();
77+
78+
// The null patch still holds [8, 9], as a masked list does.
79+
let lists = ListArray::try_new(
80+
buffer![1i32, 2, 8, 9, 3].into_array(),
81+
buffer![0u32, 2, 4, 5].into_array(),
82+
Validity::from_iter([true, false, true]),
83+
&mut ctx,
84+
)?;
85+
let fill = Scalar::null(lists.dtype().clone());
86+
let actual = Sparse::try_new(
87+
buffer![1u32, 4, 7].into_array(),
88+
lists.into_array(),
89+
10,
90+
fill,
91+
&mut ctx,
92+
)?
93+
.into_array()
94+
.execute_until::<List>(&mut ctx)?;
95+
96+
assert_arrays_eq!(
97+
actual.as_::<List>().elements().clone(),
98+
buffer![1i32, 2, 3].into_array(),
99+
&mut ctx
100+
);
101+
Ok(())
102+
}
103+
72104
#[test]
73105
fn terminal_offset_wider_than_view_offsets() -> VortexResult<()> {
74106
let session = VortexSession::empty();

0 commit comments

Comments
 (0)