Skip to main content

vortex_array/arrays/chunked/
array.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! First-class chunked arrays.
5//!
6//! Vortex is a chunked array library that's able to
7
8use std::fmt::Debug;
9use std::fmt::Display;
10use std::fmt::Formatter;
11
12use futures::stream;
13use vortex_buffer::BufferMut;
14use vortex_error::VortexExpect;
15use vortex_error::VortexResult;
16use vortex_error::vortex_bail;
17
18use crate::ArrayRef;
19use crate::ArraySlots;
20use crate::Canonical;
21use crate::ExecutionCtx;
22use crate::IntoArray;
23use crate::array::Array;
24use crate::array::ArrayParts;
25use crate::array::TypedArrayRef;
26use crate::array_slots;
27use crate::arrays::Chunked;
28use crate::arrays::PrimitiveArray;
29use crate::dtype::DType;
30use crate::iter::ArrayIterator;
31use crate::iter::ArrayIteratorAdapter;
32use crate::search_sorted::SearchSorted;
33use crate::search_sorted::SearchSortedSide;
34use crate::stream::ArrayStream;
35use crate::stream::ArrayStreamAdapter;
36use crate::validity::Validity;
37
38/// Slot layout of a [`Chunked`] array: `[chunk_offsets, chunks...]`.
39#[array_slots(Chunked)]
40pub struct ChunkedSlots {
41    /// The non-nullable `u64` array of cumulative chunk offsets.
42    #[slot(0)]
43    pub chunk_offsets: ArrayRef,
44    /// The chunk arrays, each sharing the outer dtype.
45    #[slot(1..)]
46    pub chunks: Vec<ArrayRef>,
47}
48
49#[derive(Clone, Debug)]
50pub struct ChunkedData {
51    pub(super) chunk_offsets: Vec<usize>,
52    /// This is used to find the next child to execute when in executing into a builder.
53    pub(super) next_builder_slot: usize,
54}
55
56impl Display for ChunkedData {
57    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
58        write!(f, "nchunks: {}", self.chunk_offsets.len().saturating_sub(1))
59    }
60}
61
62pub trait ChunkedArrayExt: TypedArrayRef<Chunked> {
63    fn chunk_offsets_array(&self) -> &ArrayRef {
64        self.slots()[ChunkedSlots::CHUNK_OFFSETS]
65            .as_ref()
66            .vortex_expect("validated chunk offsets slot")
67    }
68
69    fn nchunks(&self) -> usize {
70        self.slots()
71            .len()
72            .saturating_sub(ChunkedSlots::CHUNKS_OFFSET)
73    }
74
75    fn chunk(&self, idx: usize) -> &ArrayRef {
76        self.slots()[ChunkedSlots::CHUNKS_OFFSET + idx]
77            .as_ref()
78            .vortex_expect("validated chunk slot")
79    }
80
81    fn iter_chunks(&self) -> impl Iterator<Item = &ArrayRef> {
82        self.slots()[ChunkedSlots::CHUNKS_OFFSET..]
83            .iter()
84            .map(|slot| slot.as_ref().vortex_expect("validated chunk slot"))
85    }
86
87    fn chunks(&self) -> Vec<ArrayRef> {
88        self.iter_chunks().cloned().collect()
89    }
90
91    fn non_empty_chunks(&self) -> impl Iterator<Item = &ArrayRef> {
92        self.iter_chunks().filter(|chunk| !chunk.is_empty())
93    }
94
95    /// Returns the cached chunk boundary offsets.
96    fn chunk_offset_values(&self) -> &[usize] {
97        &self.chunk_offsets
98    }
99
100    fn find_chunk_idx(&self, index: usize) -> VortexResult<(usize, usize)> {
101        assert!(index <= self.len(), "Index out of bounds of the array");
102        let chunk_offset_values = self.chunk_offset_values();
103        let index_chunk = chunk_offset_values
104            .search_sorted(&index, SearchSortedSide::Right)?
105            .to_ends_index(self.nchunks() + 1)
106            .saturating_sub(1);
107        let chunk_start = chunk_offset_values[index_chunk];
108        let index_in_chunk = index - chunk_start;
109        Ok((index_chunk, index_in_chunk))
110    }
111
112    fn array_iterator(&self) -> impl ArrayIterator + '_ {
113        ArrayIteratorAdapter::new(
114            self.dtype().clone(),
115            self.iter_chunks().map(|chunk| Ok(chunk.clone())),
116        )
117    }
118
119    fn array_stream(&self) -> impl ArrayStream + '_ {
120        ArrayStreamAdapter::new(
121            self.dtype().clone(),
122            stream::iter(self.iter_chunks().map(|chunk| Ok(chunk.clone()))),
123        )
124    }
125}
126impl<T: TypedArrayRef<Chunked>> ChunkedArrayExt for T {}
127
128impl ChunkedData {
129    pub(super) fn new(chunk_offsets: Vec<usize>) -> Self {
130        Self {
131            chunk_offsets,
132            next_builder_slot: ChunkedSlots::CHUNKS_OFFSET,
133        }
134    }
135
136    pub(super) fn make_chunk_offsets_array(chunk_offsets: &[usize]) -> ArrayRef {
137        let mut chunk_offsets_buf = BufferMut::<u64>::with_capacity(chunk_offsets.len());
138        for &offset in chunk_offsets {
139            let offset = u64::try_from(offset)
140                .vortex_expect("chunk offset must fit in u64 for serialization");
141            unsafe { chunk_offsets_buf.push_unchecked(offset) }
142        }
143        PrimitiveArray::new(chunk_offsets_buf.freeze(), Validity::NonNullable).into_array()
144    }
145
146    /// Validates the components that would be used to create a `ChunkedArray`.
147    ///
148    /// This function checks all the invariants required by `ChunkedArray::new_unchecked`.
149    pub fn validate(chunks: &[ArrayRef], dtype: &DType) -> VortexResult<()> {
150        for chunk in chunks {
151            if chunk.dtype() != dtype {
152                vortex_bail!("expected type: {} but instead got {}", dtype, chunk.dtype());
153            }
154        }
155
156        Ok(())
157    }
158}
159
160impl Array<Chunked> {
161    fn parts_from_chunks<const VALIDATE: bool>(
162        chunks: impl IntoIterator<Item = ArrayRef>,
163        dtype: DType,
164    ) -> VortexResult<ArrayParts<Chunked>> {
165        let chunks = chunks.into_iter();
166        let (lower, _) = chunks.size_hint();
167        Self::parts_from_chunks_with_capacity::<VALIDATE>(chunks, dtype, lower)
168    }
169
170    fn parts_from_chunks_with_capacity<const VALIDATE: bool>(
171        chunks: impl IntoIterator<Item = ArrayRef>,
172        dtype: DType,
173        capacity: usize,
174    ) -> VortexResult<ArrayParts<Chunked>> {
175        let mut slots = ArraySlots::with_capacity(ChunkedSlots::CHUNKS_OFFSET + capacity);
176        slots.push(None);
177        let mut chunk_offsets = Vec::with_capacity(capacity + 1);
178        chunk_offsets.push(0);
179        let mut len = 0usize;
180
181        for chunk in chunks {
182            if VALIDATE {
183                Self::validate_chunk_dtype(&chunk, &dtype)?;
184            }
185            len += chunk.len();
186            chunk_offsets.push(len);
187            slots.push(Some(chunk));
188        }
189
190        Ok(Self::parts_from_slots(dtype, len, chunk_offsets, slots))
191    }
192
193    /// Checks that the chunk has the dtype of the array.
194    ///
195    /// This function is not generic, so each iterator type does not compile its own copy of the
196    /// error message.
197    fn validate_chunk_dtype(chunk: &ArrayRef, dtype: &DType) -> VortexResult<()> {
198        if chunk.dtype() != dtype {
199            vortex_bail!("expected type: {} but instead got {}", dtype, chunk.dtype());
200        }
201        Ok(())
202    }
203
204    /// Creates the parts from the collected chunk slots and offsets.
205    ///
206    /// This function is not generic, so each iterator type that `parts_from_chunks_with_capacity`
207    /// gets compiled for does not compile its own copy.
208    fn parts_from_slots(
209        dtype: DType,
210        len: usize,
211        chunk_offsets: Vec<usize>,
212        mut slots: ArraySlots,
213    ) -> ArrayParts<Chunked> {
214        slots[ChunkedSlots::CHUNK_OFFSETS] =
215            Some(ChunkedData::make_chunk_offsets_array(&chunk_offsets));
216        ArrayParts::new(Chunked, dtype, len, ChunkedData::new(chunk_offsets), slots)
217    }
218
219    pub(super) fn with_next_builder_slot(mut self, next_builder_slot: usize) -> Self {
220        if let Some(data) = self.data_mut() {
221            data.next_builder_slot = next_builder_slot;
222            return self;
223        }
224        // This is the slow path that will be hit at most once per execution since the second one
225        // *MUST* have execlusive access due to this copy.
226        let stats = self.statistics().to_owned();
227        let mut data = self.data().clone();
228        data.next_builder_slot = next_builder_slot;
229        // SAFETY: we only modified next_builder_slot which doesn't affect array invariants.
230        unsafe {
231            Array::from_parts_unchecked(ArrayParts::new(
232                Chunked,
233                self.dtype().clone(),
234                self.len(),
235                data,
236                self.slots().iter().cloned().collect::<ArraySlots>(),
237            ))
238        }
239        .with_stats_set(stats)
240    }
241
242    /// Constructs a new `ChunkedArray`.
243    pub fn try_new(chunks: impl IntoIterator<Item = ArrayRef>, dtype: DType) -> VortexResult<Self> {
244        Self::try_from_chunked_parts(Self::parts_from_chunks::<true>(chunks, dtype)?)
245    }
246
247    pub fn rechunk(
248        &self,
249        target_bytesize: u64,
250        target_rowsize: usize,
251        ctx: &mut ExecutionCtx,
252    ) -> VortexResult<Self> {
253        let mut new_chunks = Vec::new();
254        let mut chunks_to_combine = Vec::new();
255        let mut new_chunk_n_bytes = 0;
256        let mut new_chunk_n_elements = 0;
257        for chunk in self.iter_chunks() {
258            let n_bytes = chunk.nbytes();
259            let n_elements = chunk.len();
260
261            if (new_chunk_n_bytes + n_bytes > target_bytesize
262                || new_chunk_n_elements + n_elements > target_rowsize)
263                && !chunks_to_combine.is_empty()
264            {
265                let canonical = unsafe {
266                    Array::<Chunked>::new_unchecked(
267                        chunks_to_combine.drain(..),
268                        self.dtype().clone(),
269                    )
270                }
271                .into_array()
272                .execute::<Canonical>(ctx)?
273                .into_array();
274                new_chunks.push(canonical);
275
276                new_chunk_n_bytes = 0;
277                new_chunk_n_elements = 0;
278            }
279
280            if n_bytes > target_bytesize || n_elements > target_rowsize {
281                new_chunks.push(chunk.clone());
282            } else {
283                new_chunk_n_bytes += n_bytes;
284                new_chunk_n_elements += n_elements;
285                chunks_to_combine.push(chunk.clone());
286            }
287        }
288
289        if !chunks_to_combine.is_empty() {
290            let canonical =
291                unsafe { Array::<Chunked>::new_unchecked(chunks_to_combine, self.dtype().clone()) }
292                    .into_array()
293                    .execute::<Canonical>(ctx)?
294                    .into_array();
295            new_chunks.push(canonical);
296        }
297
298        unsafe { Ok(Self::new_unchecked(new_chunks, self.dtype().clone())) }
299    }
300
301    /// Creates a new `ChunkedArray` without validation.
302    ///
303    /// # Safety
304    ///
305    /// All chunks must have exactly the same [`DType`] as the provided `dtype`.
306    pub unsafe fn new_unchecked(chunks: impl IntoIterator<Item = ArrayRef>, dtype: DType) -> Self {
307        let chunks = chunks.into_iter();
308        let (expected_nchunks, _) = chunks.size_hint();
309        // SAFETY: the caller guarantees the dtype of every chunk.
310        unsafe { Self::new_unchecked_sized(chunks, dtype, expected_nchunks) }
311    }
312
313    /// Creates a chunked array without validation, reserving space for `expected_nchunks` chunks.
314    ///
315    /// The expected count is only an allocation hint: fewer or more chunks are allowed.
316    /// This is useful when iterator adapters such as `process_results` lose the source size hint.
317    ///
318    /// # Safety
319    ///
320    /// All chunks must have exactly the same [`DType`] as the provided `dtype`.
321    pub unsafe fn new_unchecked_sized(
322        chunks: impl IntoIterator<Item = ArrayRef>,
323        dtype: DType,
324        expected_nchunks: usize,
325    ) -> Self {
326        let parts = Self::parts_from_chunks_with_capacity::<false>(chunks, dtype, expected_nchunks)
327            .vortex_expect("unchecked chunked construction cannot fail");
328        // SAFETY: the caller guarantees the dtype of every chunk.
329        unsafe { Self::from_chunked_parts_unchecked(parts) }
330    }
331
332    /// Creates the array from parts after validation.
333    ///
334    /// The generic constructors call this function. It is not generic, so crates that call those
335    /// constructors do not each compile the `Chunked` array vtable.
336    fn try_from_chunked_parts(parts: ArrayParts<Chunked>) -> VortexResult<Self> {
337        Array::try_from_parts(parts)
338    }
339
340    /// Creates the array from parts without validation.
341    ///
342    /// The generic constructors call this function. It is not generic, so crates that call those
343    /// constructors do not each compile the `Chunked` array vtable.
344    ///
345    /// # Safety
346    ///
347    /// The parts must be logically consistent.
348    unsafe fn from_chunked_parts_unchecked(parts: ArrayParts<Chunked>) -> Self {
349        unsafe { Array::from_parts_unchecked(parts) }
350    }
351}
352
353impl FromIterator<ArrayRef> for Array<Chunked> {
354    fn from_iter<T: IntoIterator<Item = ArrayRef>>(iter: T) -> Self {
355        let mut chunks = iter.into_iter().peekable();
356        let dtype = chunks
357            .peek()
358            .map(|c| c.dtype().clone())
359            .vortex_expect("Cannot infer DType from an empty iterator");
360        Array::<Chunked>::try_new(chunks, dtype)
361            .vortex_expect("Failed to create chunked array from iterator")
362    }
363}
364
365#[cfg(test)]
366mod test {
367    use std::sync::LazyLock;
368
369    use itertools::Itertools;
370    use rstest::rstest;
371    use vortex_buffer::buffer;
372    use vortex_error::VortexResult;
373    use vortex_error::vortex_err;
374    use vortex_session::VortexSession;
375
376    use crate::IntoArray;
377    use crate::VortexSessionExecute;
378    use crate::arrays::ChunkedArray;
379    use crate::arrays::PrimitiveArray;
380    use crate::arrays::chunked::ChunkedArrayExt;
381    use crate::assert_arrays_eq;
382    use crate::dtype::DType;
383    use crate::dtype::Nullability;
384    use crate::dtype::PType;
385    use crate::validity::Validity;
386
387    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
388
389    #[rstest]
390    fn sized_chunks(
391        #[values(0, 1, 17)] nchunks: usize,
392        #[values(0, 1, 17)] expected_nchunks: usize,
393    ) -> VortexResult<()> {
394        let dtype = DType::from(PType::U64);
395        let chunks = (0..nchunks as u64).map(|i| buffer![i].into_array());
396        // SAFETY: every chunk contains non-nullable u64 values.
397        let array =
398            unsafe { ChunkedArray::new_unchecked_sized(chunks, dtype.clone(), expected_nchunks) };
399
400        assert_eq!(array.dtype(), &dtype);
401        assert_eq!(array.nchunks(), nchunks);
402        assert_eq!(
403            array.chunk_offset_values(),
404            (0..=nchunks).collect::<Vec<_>>()
405        );
406        let mut ctx = SESSION.create_execution_ctx();
407        assert_arrays_eq!(
408            array,
409            PrimitiveArray::from_iter(0..nchunks as u64),
410            &mut ctx
411        );
412        Ok(())
413    }
414
415    #[rstest]
416    fn sized_chunks_with_process_results(#[values(0, 1)] error_at: usize) {
417        let mut visited = 0;
418        let chunks = (0..3).map(|i| {
419            visited += 1;
420            if i == error_at {
421                Err(vortex_err!("chunk source failed"))
422            } else {
423                Ok(buffer![1u64].into_array())
424            }
425        });
426        let dtype = DType::from(PType::U64);
427        let result = chunks.process_results(|chunks| {
428            // SAFETY: every successfully yielded chunk contains non-nullable u64 values.
429            unsafe { ChunkedArray::new_unchecked_sized(chunks, dtype, 3) }
430        });
431
432        assert!(
433            result
434                .unwrap_err()
435                .to_string()
436                .contains("chunk source failed")
437        );
438        assert_eq!(visited, error_at + 1);
439    }
440
441    #[test]
442    fn test_rechunk_one_chunk() {
443        let mut ctx = SESSION.create_execution_ctx();
444        let chunked = ChunkedArray::try_new(
445            vec![buffer![0u64].into_array()],
446            DType::Primitive(PType::U64, Nullability::NonNullable),
447        )
448        .unwrap();
449
450        let rechunked = chunked.rechunk(1 << 16, 1 << 16, &mut ctx).unwrap();
451
452        assert_arrays_eq!(chunked, rechunked, &mut ctx);
453    }
454
455    #[test]
456    fn test_rechunk_two_chunks() {
457        let mut ctx = SESSION.create_execution_ctx();
458        let chunked = ChunkedArray::try_new(
459            vec![buffer![0u64].into_array(), buffer![5u64].into_array()],
460            DType::Primitive(PType::U64, Nullability::NonNullable),
461        )
462        .unwrap();
463
464        let rechunked = chunked.rechunk(1 << 16, 1 << 16, &mut ctx).unwrap();
465
466        assert_eq!(rechunked.nchunks(), 1);
467        assert_arrays_eq!(chunked, rechunked, &mut ctx);
468    }
469
470    #[test]
471    fn test_rechunk_tiny_target_chunks() {
472        let mut ctx = SESSION.create_execution_ctx();
473        let chunked = ChunkedArray::try_new(
474            vec![
475                buffer![0u64, 1, 2, 3].into_array(),
476                buffer![4u64, 5].into_array(),
477            ],
478            DType::Primitive(PType::U64, Nullability::NonNullable),
479        )
480        .unwrap();
481
482        let rechunked = chunked.rechunk(1 << 16, 5, &mut ctx).unwrap();
483
484        assert_eq!(rechunked.nchunks(), 2);
485        assert!(rechunked.iter_chunks().all(|c| c.len() < 5));
486        assert_arrays_eq!(chunked, rechunked, &mut ctx);
487    }
488
489    #[test]
490    fn test_rechunk_with_too_big_chunk() {
491        let mut ctx = SESSION.create_execution_ctx();
492        let chunked = ChunkedArray::try_new(
493            vec![
494                buffer![0u64, 1, 2].into_array(),
495                buffer![42_u64; 6].into_array(),
496                buffer![4u64, 5].into_array(),
497                buffer![6u64, 7].into_array(),
498                buffer![8u64, 9].into_array(),
499            ],
500            DType::Primitive(PType::U64, Nullability::NonNullable),
501        )
502        .unwrap();
503
504        let rechunked = chunked.rechunk(1 << 16, 5, &mut ctx).unwrap();
505        // greedy so should be: [0, 1, 2] [42, 42, 42, 42, 42, 42] [4, 5, 6, 7] [8, 9]
506
507        assert_eq!(rechunked.nchunks(), 4);
508        assert_arrays_eq!(chunked, rechunked, &mut ctx);
509    }
510
511    #[test]
512    fn test_empty_chunks_all_valid() -> VortexResult<()> {
513        let mut ctx = SESSION.create_execution_ctx();
514        // Create chunks where some are empty but all non-empty chunks have all valid values
515        let chunks = vec![
516            PrimitiveArray::new(buffer![1u64, 2, 3], Validity::AllValid).into_array(),
517            PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), // empty chunk
518            PrimitiveArray::new(buffer![4u64, 5], Validity::AllValid).into_array(),
519            PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), // empty chunk
520        ];
521
522        let chunked =
523            ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
524
525        // Should be all_valid since all non-empty chunks are all_valid
526        assert!(chunked.all_valid(&mut ctx)?);
527        assert!(!chunked.into_array().all_invalid(&mut ctx)?);
528
529        Ok(())
530    }
531
532    #[test]
533    fn test_empty_chunks_all_invalid() -> VortexResult<()> {
534        let mut ctx = SESSION.create_execution_ctx();
535        // Create chunks where some are empty but all non-empty chunks have all invalid values
536        let chunks = vec![
537            PrimitiveArray::new(buffer![1u64, 2], Validity::AllInvalid).into_array(),
538            PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(), /* empty chunk */
539            PrimitiveArray::new(buffer![3u64, 4, 5], Validity::AllInvalid).into_array(),
540            PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(), /* empty chunk */
541        ];
542
543        let chunked =
544            ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
545
546        // Should be all_invalid since all non-empty chunks are all_invalid
547        assert!(!chunked.all_valid(&mut ctx)?);
548        assert!(chunked.into_array().all_invalid(&mut ctx)?);
549
550        Ok(())
551    }
552
553    #[test]
554    fn test_empty_chunks_mixed_validity() -> VortexResult<()> {
555        let mut ctx = SESSION.create_execution_ctx();
556        // Create chunks with mixed validity including empty chunks
557        let chunks = vec![
558            PrimitiveArray::new(buffer![1u64, 2], Validity::AllValid).into_array(),
559            PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), // empty chunk
560            PrimitiveArray::new(buffer![3u64, 4], Validity::AllInvalid).into_array(),
561            PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(), /* empty chunk */
562        ];
563
564        let chunked =
565            ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
566
567        // Should be neither all_valid nor all_invalid
568        assert!(!chunked.all_valid(&mut ctx)?);
569        assert!(!chunked.into_array().all_invalid(&mut ctx)?);
570
571        Ok(())
572    }
573}