Skip to content

Commit 8fd8b8d

Browse files
perf[array]: chunked take with bounded compute graph (#6589)
Currently take on a chunked array will create dict arrays for each contiguous indices over a chunk. Instead sort the indices to a filter on each chunk and then materalize and take the whole array closes: #6407 --------- Signed-off-by: Joe Isaacs <[email protected]>
1 parent 6bc2c13 commit 8fd8b8d

4 files changed

Lines changed: 177 additions & 55 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎vortex-array/public-api.lock‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -622,7 +622,7 @@ pub fn vortex_array::arrays::ChunkedVTable::slice(array: &Self::Array, range: co
622622

623623
impl vortex_array::arrays::TakeExecute for vortex_array::arrays::ChunkedVTable
624624

625-
pub fn vortex_array::arrays::ChunkedVTable::take(array: &vortex_array::arrays::ChunkedArray, indices: &dyn vortex_array::Array, _ctx: &mut vortex_array::ExecutionCtx) -> vortex_error::VortexResult<core::option::Option<vortex_array::ArrayRef>>
625+
pub fn vortex_array::arrays::ChunkedVTable::take(array: &vortex_array::arrays::ChunkedArray, indices: &dyn vortex_array::Array, ctx: &mut vortex_array::ExecutionCtx) -> vortex_error::VortexResult<core::option::Option<vortex_array::ArrayRef>>
626626

627627
impl vortex_array::compute::IsConstantKernel for vortex_array::arrays::ChunkedVTable
628628

@@ -4056,7 +4056,7 @@ pub fn vortex_array::arrays::BoolVTable::take(array: &vortex_array::arrays::Bool
40564056

40574057
impl vortex_array::arrays::TakeExecute for vortex_array::arrays::ChunkedVTable
40584058

4059-
pub fn vortex_array::arrays::ChunkedVTable::take(array: &vortex_array::arrays::ChunkedArray, indices: &dyn vortex_array::Array, _ctx: &mut vortex_array::ExecutionCtx) -> vortex_error::VortexResult<core::option::Option<vortex_array::ArrayRef>>
4059+
pub fn vortex_array::arrays::ChunkedVTable::take(array: &vortex_array::arrays::ChunkedArray, indices: &dyn vortex_array::Array, ctx: &mut vortex_array::ExecutionCtx) -> vortex_error::VortexResult<core::option::Option<vortex_array::ArrayRef>>
40604060

40614061
impl vortex_array::arrays::TakeExecute for vortex_array::arrays::DecimalVTable
40624062

‎vortex-array/src/arrays/chunked/compute/take.rs‎

Lines changed: 173 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -5,89 +5,111 @@ use vortex_buffer::BufferMut;
55
use vortex_dtype::DType;
66
use vortex_dtype::PType;
77
use vortex_error::VortexResult;
8+
use vortex_mask::Mask;
89

910
use crate::Array;
1011
use crate::ArrayRef;
12+
use crate::Canonical;
1113
use crate::IntoArray;
12-
use crate::ToCanonical;
1314
use crate::arrays::ChunkedVTable;
1415
use crate::arrays::PrimitiveArray;
1516
use crate::arrays::TakeExecute;
1617
use crate::arrays::chunked::ChunkedArray;
1718
use crate::builtins::ArrayBuiltins;
19+
use crate::canonical::ToCanonical;
1820
use crate::executor::ExecutionCtx;
1921
use crate::validity::Validity;
2022

21-
fn take_chunked(array: &ChunkedArray, indices: &dyn Array) -> VortexResult<ArrayRef> {
23+
// TODO(joe): this is pretty unoptimized but better than before. We want canonical using a builder
24+
// we also want to return a chunked array ideally.
25+
fn take_chunked(
26+
array: &ChunkedArray,
27+
indices: &dyn Array,
28+
ctx: &mut ExecutionCtx,
29+
) -> VortexResult<ArrayRef> {
2230
let indices = indices
2331
.to_array()
2432
.cast(DType::Primitive(PType::U64, indices.dtype().nullability()))?
2533
.to_primitive();
2634

27-
// TODO(joe): Should we split this implementation based on indices nullability?
28-
let nullability = indices.dtype().nullability();
2935
let indices_mask = indices.validity_mask()?;
30-
let indices = indices.as_slice::<u64>();
31-
32-
let mut chunks = Vec::new();
33-
let mut indices_in_chunk = BufferMut::<u64>::empty();
34-
let mut start = 0;
35-
let mut stop = 0;
36-
// We assume indices are non-empty as it's handled in the top-level `take` function
37-
let mut prev_chunk_idx = array.find_chunk_idx(indices[0].try_into()?)?.0;
38-
for idx in indices {
39-
let idx = usize::try_from(*idx)?;
40-
let (chunk_idx, idx_in_chunk) = array.find_chunk_idx(idx)?;
41-
42-
if chunk_idx != prev_chunk_idx {
43-
// Start a new chunk
44-
let indices_in_chunk_array = PrimitiveArray::new(
45-
indices_in_chunk.clone().freeze(),
46-
Validity::from_mask(indices_mask.slice(start..stop), nullability),
47-
);
48-
chunks.push(
49-
array
50-
.chunk(prev_chunk_idx)
51-
.take(indices_in_chunk_array.into_array())?,
52-
);
53-
indices_in_chunk.clear();
54-
start = stop;
36+
let indices_values = indices.as_slice::<u64>();
37+
let n = indices_values.len();
38+
39+
// 1. Sort (value, orig_pos) pairs so indices for the same chunk are contiguous.
40+
// Skip null indices — their final_take slots stay 0 and are masked null by validity.
41+
let mut pairs: Vec<(u64, usize)> = indices_values
42+
.iter()
43+
.enumerate()
44+
.filter(|&(i, _)| indices_mask.value(i))
45+
.map(|(i, &v)| (v, i))
46+
.collect();
47+
pairs.sort_unstable();
48+
49+
// 2. Fused pass: walk sorted pairs against chunk boundaries.
50+
// - Dedup inline → build per-chunk filter masks
51+
// - Scatter final_take[orig_pos] = dedup_idx for every pair
52+
let chunk_offsets = array.chunk_offsets();
53+
let nchunks = array.nchunks();
54+
let mut chunks = Vec::with_capacity(nchunks);
55+
let mut final_take = BufferMut::<u64>::with_capacity(n);
56+
final_take.push_n(0u64, n);
57+
58+
let mut cursor = 0usize;
59+
let mut dedup_idx = 0u64;
60+
61+
for chunk_idx in 0..nchunks {
62+
let chunk_start = chunk_offsets[chunk_idx];
63+
let chunk_end = chunk_offsets[chunk_idx + 1];
64+
let chunk_len = usize::try_from(chunk_end - chunk_start)?;
65+
66+
let range_end = cursor + pairs[cursor..].partition_point(|&(v, _)| v < chunk_end);
67+
let chunk_pairs = &pairs[cursor..range_end];
68+
69+
if !chunk_pairs.is_empty() {
70+
let mut local_indices: Vec<usize> = Vec::new();
71+
for (i, &(val, orig_pos)) in chunk_pairs.iter().enumerate() {
72+
if cursor + i > 0 && val != pairs[cursor + i - 1].0 {
73+
dedup_idx += 1;
74+
}
75+
let local = usize::try_from(val - chunk_start)?;
76+
if local_indices.last() != Some(&local) {
77+
local_indices.push(local);
78+
}
79+
final_take[orig_pos] = dedup_idx;
80+
}
81+
82+
let filter_mask = Mask::from_indices(chunk_len, local_indices);
83+
chunks.push(array.chunk(chunk_idx).filter(filter_mask)?);
5584
}
5685

57-
indices_in_chunk.push(idx_in_chunk as u64);
58-
stop += 1;
59-
prev_chunk_idx = chunk_idx;
86+
cursor = range_end;
6087
}
6188

62-
if !indices_in_chunk.is_empty() {
63-
let indices_in_chunk_array = PrimitiveArray::new(
64-
indices_in_chunk.freeze(),
65-
Validity::from_mask(indices_mask.slice(start..stop), nullability),
66-
);
67-
chunks.push(
68-
array
69-
.chunk(prev_chunk_idx)
70-
.take(indices_in_chunk_array.into_array())?,
71-
);
72-
}
89+
let nullability = indices.dtype().nullability();
7390

74-
// SAFETY: take on chunks that all have same DType retains same DType
75-
unsafe {
76-
Ok(ChunkedArray::new_unchecked(
77-
chunks,
78-
array.dtype().clone().union_nullability(nullability),
79-
)
80-
.into_array())
81-
}
91+
let result_dtype = array.dtype().clone().union_nullability(nullability);
92+
// SAFETY: every chunk came from a filter on a chunk with the same base dtype,
93+
// unioned with the index nullability.
94+
let flat = unsafe { ChunkedArray::new_unchecked(chunks, result_dtype) }
95+
.into_array()
96+
// TODO(joe): can we relax this.
97+
.execute::<Canonical>(ctx)?
98+
.into_array();
99+
100+
// 4. Single take to restore original order and expand duplicates.
101+
// Carry the original index validity so null indices produce null outputs.
102+
let take_validity = Validity::from_mask(indices_mask, nullability);
103+
flat.take(PrimitiveArray::new(final_take.freeze(), take_validity).into_array())
82104
}
83105

84106
impl TakeExecute for ChunkedVTable {
85107
fn take(
86108
array: &ChunkedArray,
87109
indices: &dyn Array,
88-
_ctx: &mut ExecutionCtx,
110+
ctx: &mut ExecutionCtx,
89111
) -> VortexResult<Option<ArrayRef>> {
90-
take_chunked(array, indices).map(Some)
112+
take_chunked(array, indices, ctx).map(Some)
91113
}
92114
}
93115

@@ -96,8 +118,10 @@ mod test {
96118
use vortex_buffer::buffer;
97119
use vortex_dtype::FieldNames;
98120
use vortex_dtype::Nullability;
121+
use vortex_error::VortexResult;
99122

100123
use crate::IntoArray;
124+
use crate::ToCanonical;
101125
use crate::array::Array;
102126
use crate::arrays::BoolArray;
103127
use crate::arrays::PrimitiveArray;
@@ -161,6 +185,102 @@ mod test {
161185
);
162186
}
163187

188+
#[test]
189+
fn test_take_shuffled_indices() -> VortexResult<()> {
190+
let c0 = buffer![0i32, 1, 2].into_array();
191+
let c1 = buffer![3i32, 4, 5].into_array();
192+
let c2 = buffer![6i32, 7, 8].into_array();
193+
let arr = ChunkedArray::try_new(
194+
vec![c0, c1, c2],
195+
PrimitiveArray::empty::<i32>(Nullability::NonNullable)
196+
.dtype()
197+
.clone(),
198+
)?;
199+
200+
// Fully shuffled indices that cross every chunk boundary.
201+
let indices = buffer![8u64, 0, 5, 3, 2, 7, 1, 6, 4].into_array();
202+
let result = arr.take(indices.to_array())?;
203+
204+
assert_arrays_eq!(
205+
result,
206+
PrimitiveArray::from_iter([8i32, 0, 5, 3, 2, 7, 1, 6, 4])
207+
);
208+
Ok(())
209+
}
210+
211+
#[test]
212+
fn test_take_shuffled_large() -> VortexResult<()> {
213+
let nchunks: i32 = 100;
214+
let chunk_len: i32 = 1_000;
215+
let total = nchunks * chunk_len;
216+
217+
let chunks: Vec<_> = (0..nchunks)
218+
.map(|c| {
219+
let start = c * chunk_len;
220+
PrimitiveArray::from_iter(start..start + chunk_len).into_array()
221+
})
222+
.collect();
223+
let dtype = chunks[0].dtype().clone();
224+
let arr = ChunkedArray::try_new(chunks, dtype)?;
225+
226+
// Fisher-Yates shuffle with a fixed seed for determinism.
227+
let mut indices: Vec<u64> = (0..u64::try_from(total)?).collect();
228+
let mut seed: u64 = 0xdeadbeef;
229+
for i in (1..indices.len()).rev() {
230+
seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
231+
let j = (seed >> 33) as usize % (i + 1);
232+
indices.swap(i, j);
233+
}
234+
235+
let indices_arr = PrimitiveArray::new(
236+
vortex_buffer::Buffer::from(indices.clone()),
237+
Validity::NonNullable,
238+
);
239+
let result = arr.take(indices_arr.to_array())?;
240+
241+
// Verify every element.
242+
let result = result.to_primitive();
243+
let result_vals = result.as_slice::<i32>();
244+
for (pos, &idx) in indices.iter().enumerate() {
245+
assert_eq!(
246+
result_vals[pos],
247+
i32::try_from(idx)?,
248+
"mismatch at position {pos}"
249+
);
250+
}
251+
Ok(())
252+
}
253+
254+
#[test]
255+
fn test_take_null_indices() -> VortexResult<()> {
256+
let c0 = buffer![10i32, 20, 30].into_array();
257+
let c1 = buffer![40i32, 50, 60].into_array();
258+
let arr = ChunkedArray::try_new(
259+
vec![c0, c1],
260+
PrimitiveArray::empty::<i32>(Nullability::NonNullable)
261+
.dtype()
262+
.clone(),
263+
)?;
264+
265+
// Indices with nulls scattered across chunk boundaries.
266+
let indices =
267+
PrimitiveArray::from_option_iter([Some(5u64), None, Some(0), Some(3), None, Some(2)]);
268+
let result = arr.take(indices.to_array())?;
269+
270+
assert_arrays_eq!(
271+
result,
272+
PrimitiveArray::from_option_iter([
273+
Some(60i32),
274+
None,
275+
Some(10),
276+
Some(40),
277+
None,
278+
Some(30)
279+
])
280+
);
281+
Ok(())
282+
}
283+
164284
#[test]
165285
fn test_take_chunked_conformance() {
166286
let a = buffer![1i32, 2, 3].into_array();

‎vortex/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,7 @@ vortex-zstd = { workspace = true, optional = true }
5252
[dev-dependencies]
5353
anyhow = { workspace = true }
5454
arrow-array = { workspace = true }
55+
arrow-ipc = { workspace = true }
5556
divan = { workspace = true }
5657
fastlanes = { workspace = true }
5758
itertools = { workspace = true }

0 commit comments

Comments
 (0)