Skip to content

Commit 70be73c

Browse files
authored
perf: trim zctl listview instead of full rebuild (#8164)
When exporting a `ListViewArray` to an Arrow list-view, the rebuild gate now branches on whether the array is already zero-copy-to-list: - **Zero-copy-to-list arrays** have no overlaps and no interior gaps, so their only waste is leading/trailing unreferenced elements. These are reclaimed with a cheap `trim_elements` rebuild (a lazy `elements` slice plus an `O(num_lists)` offset adjustment, no element data copy), gated on the unreferenced fraction exceeding `DEFAULT_TRIM_ELEMENTS_THRESHOLD`. - **Non-zero-copy arrays** keep the existing density-based `MakeZeroCopyToList` full rebuild, since they may contain overlaps, gaps, or garbage that only a full rebuild can reclaim. --------- Signed-off-by: Matt Katz <[email protected]> Signed-off-by: Matt Katz <[email protected]>
1 parent 3c5c151 commit 70be73c

6 files changed

Lines changed: 201 additions & 58 deletions

File tree

‎vortex-array/src/arrays/listview/array.rs‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ use crate::LEGACY_SESSION;
2222
#[expect(deprecated)]
2323
use crate::ToCanonical as _;
2424
use crate::VortexSessionExecute;
25+
use crate::aggregate_fn::fns::min_max::min_max;
2526
use crate::array::Array;
2627
use crate::array::ArrayParts;
2728
use crate::array::TypedArrayRef;
@@ -32,11 +33,14 @@ use crate::arrays::Primitive;
3233
use crate::arrays::PrimitiveArray;
3334
use crate::arrays::bool;
3435
use crate::arrays::primitive::PrimitiveArrayExt;
36+
use crate::builtins::ArrayBuiltins;
3537
use crate::dtype::DType;
3638
use crate::dtype::IntegerPType;
39+
use crate::dtype::PType;
3740
use crate::expr::stats::Stat;
3841
use crate::match_each_integer_ptype;
3942
use crate::match_each_unsigned_integer_ptype;
43+
use crate::scalar_fn::fns::operators::Operator;
4044
use crate::validity::Validity;
4145

4246
/// The `elements` data array, where each list scalar is a _slice_ of the `elements` array, and
@@ -522,6 +526,56 @@ pub trait ListViewArrayExt: TypedArrayRef<ListView> {
522526

523527
Ok(estimate)
524528
}
529+
530+
/// Returns the half-open range `[start, end)` of `elements` indices referenced by any view:
531+
/// the minimum offset and the maximum `offset + size`. Elements outside this range are
532+
/// unreferenced leading or trailing slack that a
533+
/// [`TrimElements`](super::ListViewRebuildMode::TrimElements) rebuild would reclaim.
534+
///
535+
/// For **zero-copy-to-list** arrays this is `O(1)`: views are sorted and non-overlapping with
536+
/// no interior gaps, so the bounds are exactly `[first_offset, last_offset + last_size)`.
537+
/// Otherwise it computes min/max statistics over `offsets` and `offsets + sizes`.
538+
///
539+
/// # Preconditions
540+
///
541+
/// The array must contain at least one list (`len() > 0`).
542+
fn referenced_element_bounds(&self, ctx: &mut ExecutionCtx) -> VortexResult<(usize, usize)> {
543+
let n_lists = self.as_ref().len();
544+
vortex_ensure!(
545+
n_lists > 0,
546+
"referenced_element_bounds requires a non-empty array"
547+
);
548+
549+
if self.is_zero_copy_to_list() {
550+
let start = self.offset_at(0);
551+
let end = self.offset_at(n_lists - 1) + self.size_at(n_lists - 1);
552+
return Ok((start, end));
553+
}
554+
555+
let start = self
556+
.offsets()
557+
.statistics()
558+
.compute_min::<usize>(ctx)
559+
.vortex_expect("offsets must report a usize min statistic");
560+
561+
// Cast offsets and sizes to the widest integer type so that `offset + size` cannot overflow
562+
// the narrower input width.
563+
let wide_dtype = DType::from(if self.offsets().dtype().as_ptype().is_unsigned_int() {
564+
PType::U64
565+
} else {
566+
PType::I64
567+
});
568+
let offsets = self.offsets().cast(wide_dtype.clone())?;
569+
let sizes = self.sizes().cast(wide_dtype)?;
570+
let end = min_max(&offsets.binary(sizes, Operator::Add)?, ctx)?
571+
.vortex_expect("non-empty array must report a min/max")
572+
.max
573+
.as_primitive()
574+
.as_::<usize>()
575+
.vortex_expect("max `offset + size` must fit in a usize");
576+
577+
Ok((start, end))
578+
}
525579
}
526580
impl<T: TypedArrayRef<ListView>> ListViewArrayExt for T {}
527581

‎vortex-array/src/arrays/listview/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@ pub use conversion::recursive_list_from_list_view;
1919

2020
mod rebuild;
2121
pub use rebuild::DEFAULT_REBUILD_DENSITY_THRESHOLD;
22+
pub use rebuild::DEFAULT_TRIM_ELEMENTS_THRESHOLD;
2223
pub use rebuild::ListViewRebuildMode;
2324

2425
#[cfg(test)]

‎vortex-array/src/arrays/listview/rebuild.rs‎

Lines changed: 28 additions & 51 deletions
Original file line numberDiff line numberDiff line change
@@ -11,15 +11,13 @@ use crate::LEGACY_SESSION;
1111
#[expect(deprecated)]
1212
use crate::ToCanonical as _;
1313
use crate::VortexSessionExecute;
14-
use crate::aggregate_fn::fns::min_max::min_max;
1514
use crate::arrays::ConstantArray;
1615
use crate::arrays::ListViewArray;
1716
use crate::arrays::PrimitiveArray;
1817
use crate::arrays::listview::ListViewArrayExt;
1918
use crate::arrays::primitive::PrimitiveArrayExt;
2019
use crate::builders::builder_with_capacity;
2120
use crate::builtins::ArrayBuiltins;
22-
use crate::dtype::DType;
2321
use crate::dtype::IntegerPType;
2422
use crate::dtype::Nullability;
2523
use crate::dtype::PType;
@@ -54,6 +52,16 @@ fn rebuilt_offset_ptype(offsets_ptype: PType) -> PType {
5452
/// list element dtypes.
5553
pub const DEFAULT_REBUILD_DENSITY_THRESHOLD: f32 = 0.1;
5654

55+
/// Waste threshold to decide whether to trim a zero-copy-to-list `ListViewArray`.
56+
///
57+
/// A zero-copy-to-list array has no overlaps and no interior gaps, so its only unreferenced bytes
58+
/// are leading and trailing elements. Trimming those is much cheaper than a full rebuild (a lazy
59+
/// `elements` slice plus an `O(num_lists)` offset adjustment, with no element data copy), so we use
60+
/// a more aggressive threshold than [`DEFAULT_REBUILD_DENSITY_THRESHOLD`].
61+
///
62+
/// When the unreferenced (leading + trailing) fraction of `elements` exceeds this threshold, we trim.
63+
pub const DEFAULT_TRIM_ELEMENTS_THRESHOLD: f32 = 0.05;
64+
5765
/// Modes for rebuilding a [`ListViewArray`].
5866
pub enum ListViewRebuildMode {
5967
/// Removes all unused data and flattens out all list data, such that the array is zero-copyable
@@ -67,6 +75,9 @@ pub enum ListViewRebuildMode {
6775

6876
/// Removes any leading or trailing elements that are unused / not referenced by any views in
6977
/// the [`ListViewArray`].
78+
///
79+
/// If the referenced `[start, end)` bounds are already known, prefer calling
80+
/// [`trim_elements`](ListViewArray::trim_elements) directly to avoid recomputing them.
7081
TrimElements,
7182

7283
/// Equivalent to `MakeZeroCopyToList` plus `TrimElements`.
@@ -335,58 +346,24 @@ impl ListViewArray {
335346

336347
/// Rebuilds a [`ListViewArray`] by trimming any unused / unreferenced leading and trailing
337348
/// elements, which is defined as a contiguous run of values in the `elements` array that are
338-
/// not referecened by any views in the corresponding [`ListViewArray`].
349+
/// not referenced by any views in the corresponding [`ListViewArray`].
339350
fn rebuild_trim_elements(&self) -> VortexResult<ListViewArray> {
340-
let start = if self.is_zero_copy_to_list() {
341-
// If offsets are sorted, then the minimum offset is the first offset.
342-
// Note that even if the first view is null, offsets must always be valid, so it is
343-
// completely fine for us to use this as a lower-bounded start of the `elements`.
344-
self.offset_at(0)
345-
} else {
346-
let mut ctx = LEGACY_SESSION.create_execution_ctx();
347-
self.offsets()
348-
.statistics()
349-
.compute_min(&mut ctx)
350-
.vortex_expect(
351-
"[ListViewArray::rebuild]: `offsets` must report min statistic that is a `usize`",
352-
)
353-
};
354-
355-
let end = if self.is_zero_copy_to_list() {
356-
// If offsets are sorted and there are no overlaps (views are always "increasing"), we
357-
// can just grab the last offset and last size.
358-
let last_offset = self.offset_at(self.len() - 1);
359-
let last_size = self.size_at(self.len() - 1);
360-
last_offset + last_size
361-
} else {
362-
// Cast offsets and sizes to the widest integer type to prevent
363-
// overflow when computing offsets + sizes. The end offset may not
364-
// fit in the integer width otherwise.
365-
let wide_dtype = DType::from(if self.offsets().dtype().as_ptype().is_unsigned_int() {
366-
PType::U64
367-
} else {
368-
PType::I64
369-
});
370-
let offsets = self.offsets().cast(wide_dtype.clone())?;
371-
let sizes = self.sizes().cast(wide_dtype)?;
372-
373-
let mut ctx = LEGACY_SESSION.create_execution_ctx();
374-
let min_max = min_max(
375-
&offsets
376-
.binary(sizes, Operator::Add)
377-
.vortex_expect("`offsets + sizes` somehow overflowed"),
378-
&mut ctx,
379-
)
380-
.vortex_expect("Something went wrong while computing min and max")
381-
.vortex_expect("We checked that the array was not empty in the top-level `rebuild`");
351+
let mut ctx = LEGACY_SESSION.create_execution_ctx();
352+
let (start, end) = self.referenced_element_bounds(&mut ctx)?;
382353

383-
min_max
384-
.max
385-
.as_primitive()
386-
.as_::<usize>()
387-
.vortex_expect("unable to interpret the max `offset + size` as a `usize`")
388-
};
354+
// SAFETY: we calculated valid start and end bounds
355+
unsafe { self.trim_elements(start, end) }
356+
}
389357

358+
/// Unsafely trims `elements` to the referenced half-open range `[start, end)`, adjusting every offset
359+
/// down by `start`. The result preserves the original `is_zero_copy_to_list` flag.
360+
///
361+
/// # SAFETY
362+
///
363+
/// `start` must be the minimum value of `offsets`, and end should be the maximum value of `offsets[i] + size[i]`
364+
/// over all indices `i` of offsets. Otherwise, `offsets` and `sizes` may hold references to elements that no longer exist
365+
/// and the array will be corrupted.
366+
pub unsafe fn trim_elements(&self, start: usize, end: usize) -> VortexResult<ListViewArray> {
390367
let adjusted_offsets = match_each_integer_ptype!(self.offsets().dtype().as_ptype(), |O| {
391368
let offset = <O as FromPrimitive>::from_usize(start)
392369
.vortex_expect("unable to convert the min offset `start` into a `usize`");

‎vortex-array/src/arrays/listview/tests/density.rs‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
//! Tests for `compute_referenced_elements_mask`, `compute_density`, and
55
//! `estimate_density` on `ListViewArray`.
66
7+
use vortex_buffer::buffer;
78
use vortex_error::VortexResult;
89
use vortex_mask::Mask;
910
use vortex_session::VortexSession;
@@ -14,13 +15,16 @@ use super::common::create_large_listview;
1415
use super::common::create_overlapping_listview;
1516
use super::common::create_sparse_overlapping_listview;
1617
use crate::ExecutionCtx;
18+
use crate::IntoArray;
1719
use crate::VortexSessionExecute;
20+
use crate::arrays::ListViewArray;
1821
use crate::arrays::listview::ListViewArrayExt;
1922
use crate::arrays::listview::tests::common::create_empty_elements_listview;
2023
use crate::expr::stats::Precision;
2124
use crate::expr::stats::Stat;
2225
use crate::scalar::ScalarValue;
2326
use crate::session::ArraySession;
27+
use crate::validity::Validity;
2428

2529
const EPS: f32 = 1e-6;
2630

@@ -137,3 +141,39 @@ fn referenced_mask_set_bits_match_views() -> VortexResult<()> {
137141
assert!(bb.value(19));
138142
Ok(())
139143
}
144+
145+
#[test]
146+
fn referenced_bounds_zero_copy_full_coverage() -> VortexResult<()> {
147+
let mut ctx = test_execution_ctx();
148+
// create_basic_listview references all 10 elements with no leading/trailing slack.
149+
let lv = create_basic_listview();
150+
assert_eq!(lv.referenced_element_bounds(&mut ctx)?, (0, 10));
151+
Ok(())
152+
}
153+
154+
#[test]
155+
fn referenced_bounds_zero_copy_with_slack() -> VortexResult<()> {
156+
let mut ctx = test_execution_ctx();
157+
// 10 elements, views cover [2, 6): 2 leading + 4 trailing unreferenced.
158+
let elements = buffer![0i32, 1, 2, 3, 4, 5, 6, 7, 8, 9].into_array();
159+
let offsets = buffer![2u32, 4].into_array();
160+
let sizes = buffer![2u32, 2].into_array();
161+
let lv = unsafe {
162+
ListViewArray::new_unchecked(elements, offsets, sizes, Validity::NonNullable)
163+
.with_zero_copy_to_list(true)
164+
};
165+
assert_eq!(lv.referenced_element_bounds(&mut ctx)?, (2, 6));
166+
Ok(())
167+
}
168+
169+
#[test]
170+
fn referenced_bounds_non_zero_copy() -> VortexResult<()> {
171+
let mut ctx = test_execution_ctx();
172+
let elements = buffer![0i32, 1, 2, 3, 4, 5, 6, 7, 8, 9].into_array();
173+
let offsets = buffer![5u32, 2].into_array();
174+
let sizes = buffer![2u32, 2].into_array();
175+
let lv = ListViewArray::new(elements, offsets, sizes, Validity::NonNullable);
176+
assert!(!lv.is_zero_copy_to_list());
177+
assert_eq!(lv.referenced_element_bounds(&mut ctx)?, (2, 7));
178+
Ok(())
179+
}

‎vortex-array/src/arrow/executor/list_view.rs‎

Lines changed: 58 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ use crate::ExecutionCtx;
1414
use crate::arrays::ListViewArray;
1515
use crate::arrays::PrimitiveArray;
1616
use crate::arrays::listview::DEFAULT_REBUILD_DENSITY_THRESHOLD;
17+
use crate::arrays::listview::DEFAULT_TRIM_ELEMENTS_THRESHOLD;
1718
use crate::arrays::listview::ListViewArrayExt;
1819
use crate::arrays::listview::ListViewDataParts;
1920
use crate::arrays::listview::ListViewRebuildMode;
@@ -31,11 +32,28 @@ pub(super) fn to_arrow_list_view<O: OffsetSizeTrait + IntegerPType>(
3132
) -> VortexResult<arrow_array::ArrayRef> {
3233
let array = array.execute::<ListViewArray>(ctx)?;
3334

34-
// If the array is sufficiently sparse, rebuild before handing it to Arrow. Otherwise downstream
35-
// consumers hold an elements buffer containing unreferenced data in memory indefinitely,
36-
// and any compute pass over that buffer wastes work on data nothing references.
37-
let density = array.upper_bound_density(ctx)?;
38-
let array = if density < DEFAULT_REBUILD_DENSITY_THRESHOLD {
35+
// Reclaim unreferenced elements before handing the array to Arrow. Otherwise downstream
36+
// consumers hold an elements buffer containing unreferenced data in memory indefinitely, and
37+
// any compute pass over that buffer wastes work on data nothing references.
38+
let array = if array.is_zero_copy_to_list() {
39+
// A zctl array has no overlaps and no interior gaps, so the only unreferenced
40+
// elements are leading and trailing. Trimming them is much cheaper than a full rebuild.
41+
// Compute the referenced bounds once and reuse them for both the decision and the trim.
42+
let n_elts = array.elements().len();
43+
if n_elts == 0 || array.is_empty() {
44+
array
45+
} else {
46+
let (start, end) = array.referenced_element_bounds(ctx)?;
47+
let waste = (n_elts - (end - start)) as f32 / n_elts as f32;
48+
if waste > DEFAULT_TRIM_ELEMENTS_THRESHOLD {
49+
// SAFETY: we calculated valid start and end bounds
50+
unsafe { array.trim_elements(start, end)? }
51+
} else {
52+
array
53+
}
54+
}
55+
} else if array.upper_bound_density(ctx)? < DEFAULT_REBUILD_DENSITY_THRESHOLD {
56+
// Overlaps, gaps, or garbage may be present, so a full rebuild is needed to reclaim waste.
3957
array.rebuild(ListViewRebuildMode::MakeZeroCopyToList)?
4058
} else {
4159
array
@@ -106,6 +124,41 @@ mod tests {
106124
use crate::arrow::executor::list_view::PrimitiveArray;
107125
use crate::validity::Validity;
108126

127+
#[test]
128+
fn trims_zero_copy_with_significant_trailing_waste() -> VortexResult<()> {
129+
let mut ctx = LEGACY_SESSION.create_execution_ctx();
130+
// Zero-copy-to-list array with 10 elements but only [0, 4) referenced -> 60% waste.
131+
// The conversion should trim the elements buffer down to the referenced range.
132+
let elements = PrimitiveArray::new(
133+
buffer![0i32, 1, 2, 3, 4, 5, 6, 7, 8, 9],
134+
Validity::NonNullable,
135+
);
136+
let offsets = PrimitiveArray::new(buffer![0i32, 2], Validity::NonNullable);
137+
let sizes = PrimitiveArray::new(buffer![2i32, 2], Validity::NonNullable);
138+
let list_array = unsafe {
139+
ListViewArray::new_unchecked(
140+
elements.into_array(),
141+
offsets.into_array(),
142+
sizes.into_array(),
143+
Validity::NonNullable,
144+
)
145+
.with_zero_copy_to_list(true)
146+
};
147+
148+
let field = Field::new("item", DataType::Int32, false);
149+
let arrow_dt = DataType::ListView(field.into());
150+
let arrow_array = list_array
151+
.into_array()
152+
.execute_arrow(Some(&arrow_dt), &mut ctx)?;
153+
154+
let listview = arrow_array
155+
.as_any()
156+
.downcast_ref::<GenericListViewArray<i32>>()
157+
.unwrap();
158+
assert_eq!(listview.values().len(), 4);
159+
Ok(())
160+
}
161+
109162
#[test]
110163
fn test_to_arrow_listview_i32() -> VortexResult<()> {
111164
let mut ctx = LEGACY_SESSION.create_execution_ctx();

‎vortex-duckdb/src/exporter/list_view.rs‎

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@ use vortex::array::ExecutionCtx;
1111
use vortex::array::arrays::ListViewArray;
1212
use vortex::array::arrays::PrimitiveArray;
1313
use vortex::array::arrays::listview::DEFAULT_REBUILD_DENSITY_THRESHOLD;
14+
use vortex::array::arrays::listview::DEFAULT_TRIM_ELEMENTS_THRESHOLD;
1415
use vortex::array::arrays::listview::ListViewArrayExt;
1516
use vortex::array::arrays::listview::ListViewDataParts;
1617
use vortex::array::arrays::listview::ListViewRebuildMode;
@@ -55,8 +56,25 @@ pub(crate) fn new_exporter(
5556
// If the array is sufficiently sparse, rebuild. Otherwise the DuckDB vector will
5657
// hold an elements buffer containing unreferenced data in memory indefinitely,
5758
// and any compute pass over that buffer wastes work on data nothing references.
58-
let density = array.upper_bound_density(ctx)?;
59-
let array = if density < DEFAULT_REBUILD_DENSITY_THRESHOLD {
59+
let array = if array.is_zero_copy_to_list() {
60+
// A zctl array has no overlaps and no interior gaps, so the only unreferenced
61+
// elements are leading and trailing. Trimming them is much cheaper than a full rebuild.
62+
// Compute the referenced bounds once and reuse them for both the decision and the trim.
63+
let n_elts = array.elements().len();
64+
if n_elts == 0 || array.is_empty() {
65+
array
66+
} else {
67+
let (start, end) = array.referenced_element_bounds(ctx)?;
68+
let waste = (n_elts - (end - start)) as f32 / n_elts as f32;
69+
if waste > DEFAULT_TRIM_ELEMENTS_THRESHOLD {
70+
// SAFETY: we calculated valid start and end bounds
71+
unsafe { array.trim_elements(start, end)? }
72+
} else {
73+
array
74+
}
75+
}
76+
} else if array.upper_bound_density(ctx)? < DEFAULT_REBUILD_DENSITY_THRESHOLD {
77+
// Overlaps, gaps, or garbage may be present, so a full rebuild is needed to reclaim waste.
6078
array.rebuild(ListViewRebuildMode::MakeZeroCopyToList)?
6179
} else {
6280
array

0 commit comments

Comments
 (0)