@@ -5,89 +5,111 @@ use vortex_buffer::BufferMut;
55use vortex_dtype:: DType ;
66use vortex_dtype:: PType ;
77use vortex_error:: VortexResult ;
8+ use vortex_mask:: Mask ;
89
910use crate :: Array ;
1011use crate :: ArrayRef ;
12+ use crate :: Canonical ;
1113use crate :: IntoArray ;
12- use crate :: ToCanonical ;
1314use crate :: arrays:: ChunkedVTable ;
1415use crate :: arrays:: PrimitiveArray ;
1516use crate :: arrays:: TakeExecute ;
1617use crate :: arrays:: chunked:: ChunkedArray ;
1718use crate :: builtins:: ArrayBuiltins ;
19+ use crate :: canonical:: ToCanonical ;
1820use crate :: executor:: ExecutionCtx ;
1921use 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
84106impl 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 ( ) ;
0 commit comments