1use 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#[array_slots(Chunked)]
40pub struct ChunkedSlots {
41 #[slot(0)]
43 pub chunk_offsets: ArrayRef,
44 #[slot(1..)]
46 pub chunks: Vec<ArrayRef>,
47}
48
49#[derive(Clone, Debug)]
50pub struct ChunkedData {
51 pub(super) chunk_offsets: Vec<usize>,
52 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 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 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 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 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 let stats = self.statistics().to_owned();
227 let mut data = self.data().clone();
228 data.next_builder_slot = next_builder_slot;
229 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 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 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 unsafe { Self::new_unchecked_sized(chunks, dtype, expected_nchunks) }
311 }
312
313 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 unsafe { Self::from_chunked_parts_unchecked(parts) }
330 }
331
332 fn try_from_chunked_parts(parts: ArrayParts<Chunked>) -> VortexResult<Self> {
337 Array::try_from_parts(parts)
338 }
339
340 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 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 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 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 let chunks = vec![
516 PrimitiveArray::new(buffer![1u64, 2, 3], Validity::AllValid).into_array(),
517 PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), PrimitiveArray::new(buffer![4u64, 5], Validity::AllValid).into_array(),
519 PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), ];
521
522 let chunked =
523 ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
524
525 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 let chunks = vec![
537 PrimitiveArray::new(buffer![1u64, 2], Validity::AllInvalid).into_array(),
538 PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(), PrimitiveArray::new(buffer![3u64, 4, 5], Validity::AllInvalid).into_array(),
540 PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(), ];
542
543 let chunked =
544 ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
545
546 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 let chunks = vec![
558 PrimitiveArray::new(buffer![1u64, 2], Validity::AllValid).into_array(),
559 PrimitiveArray::new(buffer![0u64; 0], Validity::AllValid).into_array(), PrimitiveArray::new(buffer![3u64, 4], Validity::AllInvalid).into_array(),
561 PrimitiveArray::new(buffer![0u64; 0], Validity::AllInvalid).into_array(), ];
563
564 let chunked =
565 ChunkedArray::try_new(chunks, DType::Primitive(PType::U64, Nullability::Nullable))?;
566
567 assert!(!chunked.all_valid(&mut ctx)?);
569 assert!(!chunked.into_array().all_invalid(&mut ctx)?);
570
571 Ok(())
572 }
573}