1#[cfg(feature = "arrow")]
6use crate::column::writer::LevelDataRef;
7use crate::errors::{ParquetError, Result};
8use crate::file::properties::CdcOptions;
9use crate::schema::types::ColumnDescriptor;
10
11use super::CdcChunk;
12use super::cdc_generated::{GEARHASH_TABLE, NUM_GEARHASH_TABLES};
13
14#[derive(Debug)]
75pub(crate) struct ContentDefinedChunker {
76 max_def_level: i16,
78 max_rep_level: i16,
80 repeated_ancestor_def_level: i16,
82
83 min_chunk_size: i64,
88 max_chunk_size: i64,
96 rolling_hash_mask: u64,
98
99 rolling_hash: u64,
101 has_matched: bool,
103 nth_run: usize,
105 chunk_size: i64,
107}
108
109impl ContentDefinedChunker {
110 pub fn new(desc: &ColumnDescriptor, options: &CdcOptions) -> Result<Self> {
111 let rolling_hash_mask = Self::calculate_mask(
112 options.min_chunk_size as i64,
113 options.max_chunk_size as i64,
114 options.norm_level,
115 )?;
116 Ok(Self {
117 max_def_level: desc.max_def_level(),
118 max_rep_level: desc.max_rep_level(),
119 repeated_ancestor_def_level: desc.repeated_ancestor_def_level(),
120 min_chunk_size: options.min_chunk_size as i64,
121 max_chunk_size: options.max_chunk_size as i64,
122 rolling_hash_mask,
123 rolling_hash: 0,
124 has_matched: false,
125 nth_run: 0,
126 chunk_size: 0,
127 })
128 }
129
130 fn calculate_mask(min_chunk_size: i64, max_chunk_size: i64, norm_level: i32) -> Result<u64> {
135 if min_chunk_size < 0 {
136 return Err(ParquetError::General(
137 "min_chunk_size must be non-negative".to_string(),
138 ));
139 }
140 if max_chunk_size <= min_chunk_size {
141 return Err(ParquetError::General(
142 "max_chunk_size must be greater than min_chunk_size".to_string(),
143 ));
144 }
145
146 let avg_chunk_size = min_chunk_size.midpoint(max_chunk_size);
147 let target_size = (avg_chunk_size - min_chunk_size) / NUM_GEARHASH_TABLES as i64;
150
151 let mask_bits = if target_size > 0 {
153 63 - target_size.leading_zeros() as i32
154 } else {
155 0
156 };
157
158 let effective_bits = mask_bits - norm_level;
159
160 if !(1..=63).contains(&effective_bits) {
161 return Err(ParquetError::General(format!(
162 "The number of bits in the CDC mask must be between 1 and 63, got {effective_bits}"
163 )));
164 }
165
166 Ok(u64::MAX << (64 - effective_bits))
168 }
169
170 #[inline]
177 fn roll(&mut self, bytes: &[u8]) {
178 self.chunk_size += bytes.len() as i64;
179 if self.chunk_size < self.min_chunk_size {
180 return;
181 }
182 for &b in bytes {
183 self.rolling_hash = self
184 .rolling_hash
185 .wrapping_shl(1)
186 .wrapping_add(GEARHASH_TABLE[self.nth_run][b as usize]);
187 self.has_matched =
188 self.has_matched || ((self.rolling_hash & self.rolling_hash_mask) == 0);
189 }
190 }
191
192 #[inline(always)]
197 fn roll_fixed<const N: usize>(&mut self, bytes: &[u8; N]) {
198 self.chunk_size += N as i64;
199 if self.chunk_size < self.min_chunk_size {
200 return;
201 }
202 for j in 0..N {
203 self.rolling_hash = self
204 .rolling_hash
205 .wrapping_shl(1)
206 .wrapping_add(GEARHASH_TABLE[self.nth_run][bytes[j] as usize]);
207 self.has_matched =
208 self.has_matched || ((self.rolling_hash & self.rolling_hash_mask) == 0);
209 }
210 }
211
212 #[inline]
214 fn roll_level(&mut self, level: i16) {
215 self.roll_fixed(&level.to_le_bytes());
216 }
217
218 #[inline]
236 fn need_new_chunk(&mut self) -> bool {
237 if self.has_matched {
238 self.has_matched = false;
239 self.nth_run += 1;
240 if self.nth_run >= NUM_GEARHASH_TABLES {
241 self.nth_run = 0;
242 self.chunk_size = 0;
243 return true;
244 }
245 }
246 if self.chunk_size >= self.max_chunk_size {
247 self.chunk_size = 0;
248 return true;
249 }
250 false
251 }
252
253 fn calculate<F>(
266 &mut self,
267 def_levels: LevelDataRef<'_>,
268 rep_levels: LevelDataRef<'_>,
269 num_levels: usize,
270 mut roll_value: F,
271 ) -> Vec<CdcChunk>
272 where
273 F: FnMut(&mut Self, usize),
274 {
275 let has_def_levels = self.max_def_level > 0;
276 let has_rep_levels = self.max_rep_level > 0;
277
278 let mut chunks = Vec::new();
279 let mut prev_offset: usize = 0;
280 let mut prev_value_offset: usize = 0;
281 let mut value_offset: usize = 0;
282
283 if !has_rep_levels && !has_def_levels {
284 for offset in 0..num_levels {
292 roll_value(self, offset);
293 if self.need_new_chunk() {
294 chunks.push(CdcChunk {
295 level_offset: prev_offset,
296 num_levels: offset - prev_offset,
297 value_offset: prev_offset,
298 num_values: offset - prev_offset,
299 });
300 prev_offset = offset;
301 }
302 }
303 prev_value_offset = prev_offset;
304 value_offset = num_levels;
305 } else if !has_rep_levels {
306 for offset in 0..num_levels {
315 let def_level = def_levels
316 .value_at(offset)
317 .expect("def_levels required when max_def_level > 0");
318 self.roll_level(def_level);
319 if def_level == self.max_def_level {
320 roll_value(self, offset);
324 }
325 if self.need_new_chunk() {
328 chunks.push(CdcChunk {
329 level_offset: prev_offset,
330 num_levels: offset - prev_offset,
331 value_offset: prev_value_offset,
332 num_values: value_offset - prev_value_offset,
333 });
334 prev_offset = offset;
335 prev_value_offset = value_offset;
336 }
337 if def_level == self.max_def_level {
338 value_offset += 1;
339 }
340 }
341 } else {
342 let mut leaf_offset: usize = 0;
373
374 for offset in 0..num_levels {
375 let def_level = def_levels
376 .value_at(offset)
377 .expect("def_levels required for nested data");
378 let rep_level = rep_levels
379 .value_at(offset)
380 .expect("rep_levels required for nested data");
381
382 self.roll_level(def_level);
383 self.roll_level(rep_level);
384 if def_level == self.max_def_level {
385 roll_value(self, leaf_offset);
386 }
387
388 if rep_level == 0 && self.need_new_chunk() {
391 let levels_to_write = offset - prev_offset;
392 if levels_to_write > 0 {
393 chunks.push(CdcChunk {
394 level_offset: prev_offset,
395 num_levels: levels_to_write,
396 value_offset: prev_value_offset,
397 num_values: value_offset - prev_value_offset,
398 });
399 prev_offset = offset;
400 prev_value_offset = value_offset;
401 }
402 }
403 if def_level == self.max_def_level {
404 value_offset += 1;
405 }
406 if def_level >= self.repeated_ancestor_def_level {
407 leaf_offset += 1;
408 }
409 }
410 }
411
412 if prev_offset < num_levels {
414 chunks.push(CdcChunk {
415 level_offset: prev_offset,
416 num_levels: num_levels - prev_offset,
417 value_offset: prev_value_offset,
418 num_values: value_offset - prev_value_offset,
419 });
420 }
421
422 #[cfg(debug_assertions)]
423 self.validate_chunks(&chunks, num_levels, value_offset);
424
425 chunks
426 }
427
428 #[cfg(feature = "arrow")]
431 pub(crate) fn get_arrow_chunks(
432 &mut self,
433 def_levels: LevelDataRef<'_>,
434 rep_levels: LevelDataRef<'_>,
435 array: &dyn arrow_array::Array,
436 ) -> Result<Vec<CdcChunk>> {
437 use arrow_array::cast::AsArray;
438 use arrow_schema::DataType;
439
440 let num_levels = match (def_levels.len(), rep_levels.len()) {
445 (0, 0) => array.len(),
446 (d, r) => d.max(r),
447 };
448
449 macro_rules! fixed_width {
450 ($N:literal) => {{
451 let data = array.to_data();
452 let buffer = data.buffers()[0].as_slice();
453 let values = &buffer[data.offset() * $N..];
454 self.calculate(def_levels, rep_levels, num_levels, |c, i| {
455 let offset = i * $N;
456 let slice = &values[offset..offset + $N];
457 c.roll_fixed::<$N>(slice.try_into().unwrap());
458 })
459 }};
460 }
461
462 macro_rules! binary_like {
463 ($a:expr) => {{
464 let a = $a;
465 self.calculate(def_levels, rep_levels, num_levels, |c, i| {
466 c.roll(a.value(i).as_ref());
467 })
468 }};
469 }
470
471 let dtype = array.data_type();
472 let chunks = match dtype {
473 DataType::Null => self.calculate(def_levels, rep_levels, num_levels, |_, _| {}),
474 DataType::Boolean => {
475 let a = array.as_boolean();
476 self.calculate(def_levels, rep_levels, num_levels, |c, i| {
477 c.roll_fixed(&[a.value(i) as u8]);
478 })
479 }
480 DataType::Int8 | DataType::UInt8 => fixed_width!(1),
481 DataType::Int16 | DataType::UInt16 | DataType::Float16 => fixed_width!(2),
482 DataType::Int32
483 | DataType::UInt32
484 | DataType::Float32
485 | DataType::Date32
486 | DataType::Time32(_)
487 | DataType::Interval(arrow_schema::IntervalUnit::YearMonth)
488 | DataType::Decimal32(_, _) => fixed_width!(4),
489 DataType::Int64
490 | DataType::UInt64
491 | DataType::Float64
492 | DataType::Date64
493 | DataType::Time64(_)
494 | DataType::Timestamp(_, _)
495 | DataType::Duration(_)
496 | DataType::Interval(arrow_schema::IntervalUnit::DayTime)
497 | DataType::Decimal64(_, _) => fixed_width!(8),
498 DataType::Interval(arrow_schema::IntervalUnit::MonthDayNano)
499 | DataType::Decimal128(_, _) => fixed_width!(16),
500 DataType::Decimal256(_, _) => fixed_width!(32),
501 DataType::FixedSizeBinary(_) => binary_like!(array.as_fixed_size_binary()),
502 DataType::Binary => binary_like!(array.as_binary::<i32>()),
503 DataType::LargeBinary => binary_like!(array.as_binary::<i64>()),
504 DataType::Utf8 => binary_like!(array.as_string::<i32>()),
505 DataType::LargeUtf8 => binary_like!(array.as_string::<i64>()),
506 DataType::BinaryView => binary_like!(array.as_binary_view()),
507 DataType::Utf8View => binary_like!(array.as_string_view()),
508 DataType::Dictionary(_, _) => {
509 let dict = array.as_any_dictionary();
510 self.get_arrow_chunks(def_levels, rep_levels, dict.keys())?
511 }
512 _ => {
513 return Err(ParquetError::General(format!(
514 "content-defined chunking is not supported for data type {dtype:?}",
515 )));
516 }
517 };
518 Ok(chunks)
519 }
520
521 #[cfg(debug_assertions)]
522 fn validate_chunks(&self, chunks: &[CdcChunk], num_levels: usize, total_values: usize) {
523 assert!(!chunks.is_empty(), "chunks must be non-empty");
524
525 let first = &chunks[0];
526 assert_eq!(first.level_offset, 0, "first chunk must start at level 0");
527 assert_eq!(first.value_offset, 0, "first chunk must start at value 0");
528
529 let mut sum_levels = first.num_levels;
530 let mut sum_values = first.num_values;
531 for i in 1..chunks.len() {
532 let chunk = &chunks[i];
533 let prev = &chunks[i - 1];
534 assert!(chunk.num_levels > 0, "chunk must have levels");
535 assert_eq!(
536 chunk.level_offset,
537 prev.level_offset + prev.num_levels,
538 "level offsets must be contiguous"
539 );
540 assert_eq!(
541 chunk.value_offset,
542 prev.value_offset + prev.num_values,
543 "value offsets must be contiguous"
544 );
545 sum_levels += chunk.num_levels;
546 sum_values += chunk.num_values;
547 }
548 assert_eq!(sum_levels, num_levels, "chunks must cover all levels");
549 assert_eq!(sum_values, total_values, "chunks must cover all values");
550
551 let last = chunks.last().unwrap();
552 assert_eq!(
553 last.level_offset + last.num_levels,
554 num_levels,
555 "last chunk must end at num_levels"
556 );
557 }
558}
559
560#[cfg(test)]
561mod tests {
562 use super::*;
563 use crate::basic::Type as PhysicalType;
564 #[cfg(feature = "arrow")]
565 use crate::column::writer::LevelDataRef;
566 use crate::schema::types::{ColumnPath, Type};
567 use std::sync::Arc;
568
569 fn make_desc(max_def_level: i16, max_rep_level: i16) -> ColumnDescriptor {
570 let tp = Type::primitive_type_builder("col", PhysicalType::INT32)
571 .build()
572 .unwrap();
573 ColumnDescriptor::new(
574 Arc::new(tp),
575 max_def_level,
576 max_rep_level,
577 ColumnPath::new(vec![]),
578 )
579 }
580
581 #[test]
582 fn test_calculate_mask_defaults() {
583 let mask = ContentDefinedChunker::calculate_mask(256 * 1024, 1024 * 1024, 0).unwrap();
584 let expected = u64::MAX << (64 - 15);
587 assert_eq!(mask, expected);
588 }
589
590 #[test]
591 fn test_calculate_mask_with_norm_level() {
592 let mask = ContentDefinedChunker::calculate_mask(256 * 1024, 1024 * 1024, 1).unwrap();
593 let expected = u64::MAX << (64 - 14);
594 assert_eq!(mask, expected);
595 }
596
597 #[test]
598 fn test_calculate_mask_invalid() {
599 assert!(ContentDefinedChunker::calculate_mask(-1, 100, 0).is_err());
600 assert!(ContentDefinedChunker::calculate_mask(100, 50, 0).is_err());
601 assert!(ContentDefinedChunker::calculate_mask(100, 100, 0).is_err());
602 }
603
604 #[test]
605 fn test_non_nested_non_null_single_chunk() {
606 let options = CdcOptions {
607 min_chunk_size: 8,
608 max_chunk_size: 1024,
609 norm_level: 0,
610 };
611 let mut chunker = ContentDefinedChunker::new(&make_desc(0, 0), &options).unwrap();
612
613 let num_values = 4;
615 let chunks = chunker.calculate(
616 LevelDataRef::Absent,
617 LevelDataRef::Absent,
618 num_values,
619 |c, i| {
620 c.roll_fixed::<4>(&(i as i32).to_le_bytes());
621 },
622 );
623 assert_eq!(chunks.len(), 1);
624 assert_eq!(chunks[0].level_offset, 0);
625 assert_eq!(chunks[0].value_offset, 0);
626 assert_eq!(chunks[0].num_levels, 4);
627 }
628
629 #[test]
630 fn test_max_chunk_size_forces_boundary() {
631 let options = CdcOptions {
632 min_chunk_size: 256,
633 max_chunk_size: 1024,
634 norm_level: 0,
635 };
636 let mut chunker = ContentDefinedChunker::new(&make_desc(0, 0), &options).unwrap();
637
638 let num_values = 2000;
641 let chunks = chunker.calculate(
642 LevelDataRef::Absent,
643 LevelDataRef::Absent,
644 num_values,
645 |c, i| {
646 c.roll_fixed::<4>(&(i as i32).to_le_bytes());
647 },
648 );
649
650 assert!(chunks.len() > 1);
652
653 let mut total_levels = 0;
655 for (i, chunk) in chunks.iter().enumerate() {
656 assert_eq!(chunk.level_offset, total_levels);
657 if i < chunks.len() - 1 {
658 assert!(chunk.num_levels > 0);
659 }
660 total_levels += chunk.num_levels;
661 }
662 assert_eq!(total_levels, num_values);
663 }
664
665 #[test]
666 fn test_deterministic_chunks() {
667 let options = CdcOptions {
668 min_chunk_size: 4,
669 max_chunk_size: 64,
670 norm_level: 0,
671 };
672
673 let roll = |c: &mut ContentDefinedChunker, i: usize| {
674 c.roll_fixed::<8>(&(i as i64).to_le_bytes());
675 };
676
677 let mut chunker1 = ContentDefinedChunker::new(&make_desc(0, 0), &options).unwrap();
678 let chunks1 = chunker1.calculate(LevelDataRef::Absent, LevelDataRef::Absent, 200, roll);
679
680 let mut chunker2 = ContentDefinedChunker::new(&make_desc(0, 0), &options).unwrap();
681 let chunks2 = chunker2.calculate(LevelDataRef::Absent, LevelDataRef::Absent, 200, roll);
682
683 assert_eq!(chunks1.len(), chunks2.len());
684 for (a, b) in chunks1.iter().zip(chunks2.iter()) {
685 assert_eq!(a.level_offset, b.level_offset);
686 assert_eq!(a.num_levels, b.num_levels);
687 assert_eq!(a.value_offset, b.value_offset);
688 assert_eq!(a.num_values, b.num_values);
689 }
690 }
691
692 #[test]
693 fn test_nullable_non_nested() {
694 let options = CdcOptions {
695 min_chunk_size: 4,
696 max_chunk_size: 64,
697 norm_level: 0,
698 };
699 let mut chunker = ContentDefinedChunker::new(&make_desc(1, 0), &options).unwrap();
700
701 let num_levels = 20;
702 let def_levels: Vec<i16> = (0..num_levels).map(|i| i16::from(i % 3 != 0)).collect();
705 let expected_non_null: usize = def_levels.iter().filter(|&&d| d == 1).count();
706
707 let chunks = chunker.calculate(
708 LevelDataRef::Materialized(&def_levels),
709 LevelDataRef::Absent,
710 num_levels,
711 |c, i| {
712 c.roll_fixed::<4>(&(i as i32).to_le_bytes());
713 },
714 );
715
716 assert!(!chunks.is_empty());
717 let total_levels: usize = chunks.iter().map(|c| c.num_levels).sum();
718 let total_values: usize = chunks.iter().map(|c| c.num_values).sum();
719 assert_eq!(total_levels, num_levels);
720 assert_eq!(total_values, expected_non_null);
721 assert!(total_values < total_levels);
723 }
724}
725
726#[cfg(all(test, feature = "arrow"))]
729mod arrow_tests {
730 use std::borrow::Borrow;
731 use std::cmp::Ordering;
732 use std::sync::Arc;
733
734 use arrow::util::data_gen::create_random_batch;
735 use arrow_array::cast::AsArray;
736 use arrow_array::{Array, ArrayRef, BooleanArray, Int32Array, RecordBatch};
737 use arrow_buffer::Buffer;
738 use arrow_data::ArrayData;
739 use arrow_schema::{DataType, Field, Fields, Schema};
740
741 use crate::arrow::arrow_reader::ParquetRecordBatchReaderBuilder;
742 use crate::arrow::arrow_writer::ArrowWriter;
743 use crate::column::writer::LevelDataRef;
744 use crate::file::properties::{
745 CdcOptions, WriterProperties, WriterPropertiesBuilder, WriterVersion,
746 };
747 use crate::file::reader::{FileReader, SerializedFileReader};
748
749 const CDC_MIN_CHUNK_SIZE: usize = 4 * 1024;
752 const CDC_MAX_CHUNK_SIZE: usize = 16 * 1024;
753 const CDC_PART_SIZE: usize = 128 * 1024;
754 const CDC_EDIT_SIZE: usize = 128;
755 const CDC_ROW_GROUP_LENGTH: usize = 1024 * 1024;
756
757 fn test_hash(seed: u64, index: u64) -> u64 {
761 let mut h = (index.wrapping_add(seed)).wrapping_mul(0xc4ceb9fe1a85ec53u64);
762 h ^= h >> 33;
763 h = h.wrapping_mul(0xff51afd7ed558ccdu64);
764 h ^= h >> 33;
765 h = h.wrapping_mul(0xc4ceb9fe1a85ec53u64);
766 h ^= h >> 33;
767 h
768 }
769
770 fn generate_array(dtype: &DataType, nullable: bool, length: usize, seed: u64) -> ArrayRef {
772 macro_rules! gen_primitive {
773 ($array_type:ty, $cast:expr) => {{
774 if nullable {
775 let arr: $array_type = (0..length)
776 .map(|i| {
777 let val = test_hash(seed, i as u64);
778 if val % 10 == 0 {
779 None
780 } else {
781 Some($cast(val))
782 }
783 })
784 .collect();
785 Arc::new(arr) as ArrayRef
786 } else {
787 let arr: $array_type = (0..length)
788 .map(|i| Some($cast(test_hash(seed, i as u64))))
789 .collect();
790 Arc::new(arr) as ArrayRef
791 }
792 }};
793 }
794
795 match dtype {
796 DataType::Boolean => {
797 if nullable {
798 let arr: BooleanArray = (0..length)
799 .map(|i| {
800 let val = test_hash(seed, i as u64);
801 if val.is_multiple_of(10) {
802 None
803 } else {
804 Some(val.is_multiple_of(2))
805 }
806 })
807 .collect();
808 Arc::new(arr)
809 } else {
810 let arr: BooleanArray = (0..length)
811 .map(|i| Some(test_hash(seed, i as u64).is_multiple_of(2)))
812 .collect();
813 Arc::new(arr)
814 }
815 }
816 DataType::Int32 => gen_primitive!(Int32Array, |v: u64| v as i32),
817 DataType::Int64 => {
818 gen_primitive!(arrow_array::Int64Array, |v: u64| v as i64)
819 }
820 DataType::Float64 => {
821 gen_primitive!(arrow_array::Float64Array, |v: u64| (v % 100000) as f64
822 / 1000.0)
823 }
824 DataType::Utf8 => {
825 let arr: arrow_array::StringArray = if nullable {
826 (0..length)
827 .map(|i| {
828 let val = test_hash(seed, i as u64);
829 if val.is_multiple_of(10) {
830 None
831 } else {
832 Some(format!("str_{val}"))
833 }
834 })
835 .collect()
836 } else {
837 (0..length)
838 .map(|i| Some(format!("str_{}", test_hash(seed, i as u64))))
839 .collect()
840 };
841 Arc::new(arr)
842 }
843 DataType::Binary => {
844 let arr: arrow_array::BinaryArray = if nullable {
845 (0..length)
846 .map(|i| {
847 let val = test_hash(seed, i as u64);
848 if val.is_multiple_of(10) {
849 None
850 } else {
851 Some(format!("bin_{val}").into_bytes())
852 }
853 })
854 .collect()
855 } else {
856 (0..length)
857 .map(|i| Some(format!("bin_{}", test_hash(seed, i as u64)).into_bytes()))
858 .collect()
859 };
860 Arc::new(arr)
861 }
862 DataType::FixedSizeBinary(size) => {
863 let size = *size;
864 let mut builder = arrow_array::builder::FixedSizeBinaryBuilder::new(size);
865 for i in 0..length {
866 let val = test_hash(seed, i as u64);
867 if nullable && val.is_multiple_of(10) {
868 builder.append_null();
869 } else {
870 let s = format!("bin_{val}");
871 let bytes = s.as_bytes();
872 let mut buf = vec![0u8; size as usize];
873 let copy_len = bytes.len().min(size as usize);
874 buf[..copy_len].copy_from_slice(&bytes[..copy_len]);
875 builder.append_value(&buf).unwrap();
876 }
877 }
878 Arc::new(builder.finish())
879 }
880 DataType::Date32 => {
881 gen_primitive!(arrow_array::Date32Array, |v: u64| v as i32)
882 }
883 DataType::Timestamp(arrow_schema::TimeUnit::Nanosecond, _) => {
884 gen_primitive!(arrow_array::TimestampNanosecondArray, |v: u64| v as i64)
885 }
886 _ => panic!("Unsupported test data type: {dtype:?}"),
887 }
888 }
889
890 fn generate_table(schema: &Arc<Schema>, length: usize, seed: u64) -> RecordBatch {
892 let arrays: Vec<ArrayRef> = schema
893 .fields()
894 .iter()
895 .enumerate()
896 .map(|(i, field)| {
897 generate_array(
898 field.data_type(),
899 field.is_nullable(),
900 length,
901 seed + i as u64 * 10,
902 )
903 })
904 .collect();
905 RecordBatch::try_new(schema.clone(), arrays).unwrap()
906 }
907
908 fn cdc_byte_width(dtype: &DataType) -> usize {
911 match dtype {
912 DataType::Boolean => 1,
913 DataType::Int8 | DataType::UInt8 => 1,
914 DataType::Int16 | DataType::UInt16 | DataType::Float16 => 2,
915 DataType::Int32
916 | DataType::UInt32
917 | DataType::Float32
918 | DataType::Date32
919 | DataType::Time32(_) => 4,
920 DataType::Int64
921 | DataType::UInt64
922 | DataType::Float64
923 | DataType::Date64
924 | DataType::Time64(_)
925 | DataType::Timestamp(_, _)
926 | DataType::Duration(_) => 8,
927 DataType::Decimal128(_, _) => 16,
928 DataType::Decimal256(_, _) => 32,
929 DataType::FixedSizeBinary(n) => *n as usize,
930 _ => 0, }
932 }
933
934 fn bytes_per_record(dtype: &DataType, nullable: bool) -> usize {
936 let bw = cdc_byte_width(dtype);
937 if bw > 0 {
938 if nullable { bw + 2 } else { bw }
939 } else {
940 16 }
942 }
943
944 fn calculate_cdc_size(array: &dyn Array, nullable: bool) -> i64 {
946 let dtype = array.data_type();
947 let bw = cdc_byte_width(dtype);
948 let result = if bw > 0 {
949 let valid_count = array.len() - array.null_count();
951 (valid_count * bw) as i64
952 } else {
953 match dtype {
955 DataType::Utf8 => {
956 let a = array.as_string::<i32>();
957 (0..a.len())
958 .filter(|&i| a.is_valid(i))
959 .map(|i| a.value(i).len() as i64)
960 .sum()
961 }
962 DataType::Binary => {
963 let a = array.as_binary::<i32>();
964 (0..a.len())
965 .filter(|&i| a.is_valid(i))
966 .map(|i| a.value(i).len() as i64)
967 .sum()
968 }
969 DataType::LargeBinary => {
970 let a = array.as_binary::<i64>();
971 (0..a.len())
972 .filter(|&i| a.is_valid(i))
973 .map(|i| a.value(i).len() as i64)
974 .sum()
975 }
976 _ => panic!("CDC size calculation not implemented for {dtype:?}"),
977 }
978 };
979
980 if nullable {
981 result + array.len() as i64 * 2
983 } else {
984 result
985 }
986 }
987
988 struct ColumnInfo {
990 page_lengths: Vec<i64>,
991 has_dictionary_page: bool,
992 }
993
994 fn get_column_info(data: &[u8], column_index: usize) -> Vec<ColumnInfo> {
996 let reader = SerializedFileReader::new(bytes::Bytes::from(data.to_vec())).unwrap();
997 let metadata = reader.metadata();
998 let mut result = Vec::new();
999 for rg in 0..metadata.num_row_groups() {
1000 let rg_reader = reader.get_row_group(rg).unwrap();
1001 let col_reader = rg_reader.get_column_page_reader(column_index).unwrap();
1002 let mut info = ColumnInfo {
1003 page_lengths: Vec::new(),
1004 has_dictionary_page: false,
1005 };
1006 for page in col_reader {
1007 let page = page.unwrap();
1008 match page.page_type() {
1009 crate::basic::PageType::DATA_PAGE | crate::basic::PageType::DATA_PAGE_V2 => {
1010 info.page_lengths.push(page.num_values() as i64);
1011 }
1012 crate::basic::PageType::DICTIONARY_PAGE => {
1013 info.has_dictionary_page = true;
1014 }
1015 crate::basic::PageType::INDEX_PAGE => {}
1016 }
1017 }
1018 result.push(info);
1019 }
1020 result
1021 }
1022
1023 fn assert_cdc_chunk_sizes(
1026 array: &ArrayRef,
1027 info: &ColumnInfo,
1028 nullable: bool,
1029 min_chunk_size: usize,
1030 max_chunk_size: usize,
1031 expect_dictionary_page: bool,
1032 ) {
1033 let expect_dict = match array.data_type() {
1035 DataType::Boolean => false,
1036 _ => expect_dictionary_page,
1037 };
1038 assert_eq!(
1039 info.has_dictionary_page,
1040 expect_dict,
1041 "dictionary page mismatch for {:?}",
1042 array.data_type()
1043 );
1044
1045 let page_lengths = &info.page_lengths;
1046 assert!(
1047 page_lengths.len() > 1,
1048 "CDC should produce multiple pages, got {page_lengths:?}"
1049 );
1050
1051 let bw = cdc_byte_width(array.data_type());
1052 if bw > 0
1054 || matches!(
1055 array.data_type(),
1056 DataType::Utf8 | DataType::Binary | DataType::LargeBinary
1057 )
1058 {
1059 let mut offset = 0i64;
1060 for (i, &page_len) in page_lengths.iter().enumerate() {
1061 let slice = array.slice(offset as usize, page_len as usize);
1062 let cdc_size = calculate_cdc_size(slice.as_ref(), nullable);
1063 if i < page_lengths.len() - 1 {
1064 assert!(
1065 cdc_size >= min_chunk_size as i64,
1066 "Page {i}: CDC size {cdc_size} < min {min_chunk_size}, pages={page_lengths:?}"
1067 );
1068 }
1069 assert!(
1070 cdc_size <= max_chunk_size as i64,
1071 "Page {i}: CDC size {cdc_size} > max {max_chunk_size}, pages={page_lengths:?}"
1072 );
1073 offset += page_len;
1074 }
1075 assert_eq!(
1076 offset,
1077 array.len() as i64,
1078 "page lengths must sum to array length"
1079 );
1080 }
1081 }
1082
1083 fn write_with_cdc_options(
1086 batches: &[&RecordBatch],
1087 min_chunk_size: usize,
1088 max_chunk_size: usize,
1089 max_row_group_rows: Option<usize>,
1090 enable_dictionary: bool,
1091 ) -> Vec<u8> {
1092 assert!(!batches.is_empty());
1093 let schema = batches[0].schema();
1094 let mut builder = WriterProperties::builder()
1095 .set_dictionary_enabled(enable_dictionary)
1096 .set_content_defined_chunking(Some(CdcOptions {
1097 min_chunk_size,
1098 max_chunk_size,
1099 norm_level: 0,
1100 }));
1101 if let Some(max_rows) = max_row_group_rows {
1102 builder = builder.set_max_row_group_row_count(Some(max_rows));
1103 }
1104 let props = builder.build();
1105 let mut buf = Vec::new();
1106 let mut writer = ArrowWriter::try_new(&mut buf, schema.clone(), Some(props)).unwrap();
1107 for batch in batches {
1108 writer.write(batch).unwrap();
1109 }
1110 writer.close().unwrap();
1111
1112 let readback = read_batches(&buf);
1114 let original_rows: usize = batches.iter().map(|b| b.num_rows()).sum();
1115 let readback_rows: usize = readback.iter().map(|b| b.num_rows()).sum();
1116 assert_eq!(original_rows, readback_rows, "Roundtrip row count mismatch");
1117 if original_rows > 0 {
1118 let original = concat_batches(batches.iter().copied());
1119 let roundtrip = concat_batches(&readback);
1120 assert_eq!(original, roundtrip, "Roundtrip validation failed");
1121 }
1122
1123 buf
1124 }
1125
1126 fn write_cdc_batch(batch: &RecordBatch, builder: WriterPropertiesBuilder) -> Vec<u8> {
1128 let props = builder
1129 .set_writer_version(WriterVersion::PARQUET_2_0)
1130 .set_content_defined_chunking(Some(CdcOptions {
1131 min_chunk_size: 8 * 1024,
1132 max_chunk_size: 16 * 1024,
1133 norm_level: 0,
1134 }))
1135 .build();
1136
1137 let mut buf = Vec::new();
1138 let mut writer = ArrowWriter::try_new(&mut buf, batch.schema(), Some(props)).unwrap();
1139 writer.write(batch).unwrap();
1140 writer.close().unwrap();
1141 buf
1142 }
1143
1144 fn assert_multiple_nonempty_data_pages(data: &[u8]) {
1145 let info = get_column_info(data, 0);
1146 let total: usize = info.iter().map(|c| c.page_lengths.len()).sum();
1147 let empty = info
1148 .iter()
1149 .flat_map(|c| c.page_lengths.iter())
1150 .filter(|&&n| n == 0)
1151 .count();
1152
1153 assert!(
1154 total > 1,
1155 "CDC should produce multiple data pages, got {total}"
1156 );
1157 assert_eq!(empty, 0, "forced CDC page breaks must not emit empty pages");
1158 }
1159
1160 #[test]
1161 #[cfg_attr(miri, ignore)] fn cdc_boolean_small_pages_does_not_panic() {
1163 let num_rows = 32_768;
1164 let values: Vec<bool> = (0..num_rows).map(|i| i % 7 == 0).collect();
1165 let col = Arc::new(BooleanArray::from(values)) as ArrayRef;
1166 let batch = RecordBatch::try_from_iter([("flag", col)]).unwrap();
1167
1168 let props = WriterProperties::builder().set_data_page_size_limit(1024);
1169 let data = write_cdc_batch(&batch, props);
1170 assert_multiple_nonempty_data_pages(&data);
1171
1172 let readback = read_batches(&data);
1173 let rows: usize = readback.iter().map(|b| b.num_rows()).sum();
1174 assert_eq!(rows, num_rows);
1175 }
1176
1177 #[test]
1178 #[cfg_attr(miri, ignore)] fn cdc_int32_row_count_limit_does_not_emit_empty_pages() {
1180 let values: Vec<i32> = (0..8_192).map(|i| i % 97).collect();
1181 let col = Arc::new(Int32Array::from(values)) as ArrayRef;
1182 let batch = RecordBatch::try_from_iter([("a", col)]).unwrap();
1183
1184 let props = WriterProperties::builder()
1185 .set_dictionary_enabled(false)
1186 .set_data_page_row_count_limit(128);
1187 let data = write_cdc_batch(&batch, props);
1188 assert_multiple_nonempty_data_pages(&data);
1189 }
1190
1191 #[test]
1192 fn cdc_all_null_arrow_column_writes_data_pages() {
1193 let array = Arc::new(Int32Array::from(vec![None::<i32>; 4096])) as ArrayRef;
1194 let schema = Arc::new(Schema::new(vec![Field::new("f0", DataType::Int32, true)]));
1195 let batch = RecordBatch::try_new(schema, vec![array.clone()]).unwrap();
1196
1197 let data = write_with_cdc_options(&[&batch], 64, 256, Some(4096), false);
1198 let info = get_column_info(&data, 0);
1199
1200 assert_eq!(info.len(), 1);
1201 assert!(
1202 !info[0].page_lengths.is_empty(),
1203 "all-null CDC write should still emit data pages"
1204 );
1205 assert_eq!(
1206 info[0].page_lengths.iter().sum::<i64>(),
1207 array.len() as i64,
1208 "all-null CDC pages should account for every input row"
1209 );
1210 }
1211
1212 fn read_batches(data: &[u8]) -> Vec<RecordBatch> {
1213 let reader = ParquetRecordBatchReaderBuilder::try_new(bytes::Bytes::from(data.to_vec()))
1214 .unwrap()
1215 .build()
1216 .unwrap();
1217 reader.collect::<std::result::Result<Vec<_>, _>>().unwrap()
1218 }
1219
1220 fn concat_batches(batches: impl IntoIterator<Item = impl Borrow<RecordBatch>>) -> RecordBatch {
1221 let batches: Vec<_> = batches.into_iter().collect();
1222 let schema = batches[0].borrow().schema();
1223 let batches = batches.iter().map(|b| b.borrow());
1224 arrow_select::concat::concat_batches(&schema, batches).unwrap()
1225 }
1226
1227 fn find_differences(first: &[i64], second: &[i64]) -> Vec<(Vec<i64>, Vec<i64>)> {
1230 let n = first.len();
1231 let m = second.len();
1232 let mut dp = vec![vec![0usize; m + 1]; n + 1];
1233 for i in 0..n {
1234 for j in 0..m {
1235 if first[i] == second[j] {
1236 dp[i + 1][j + 1] = dp[i][j] + 1;
1237 } else {
1238 dp[i + 1][j + 1] = dp[i + 1][j].max(dp[i][j + 1]);
1239 }
1240 }
1241 }
1242 let mut common = Vec::new();
1243 let (mut i, mut j) = (n, m);
1244 while i > 0 && j > 0 {
1245 if first[i - 1] == second[j - 1] {
1246 common.push((i - 1, j - 1));
1247 i -= 1;
1248 j -= 1;
1249 } else if dp[i - 1][j] >= dp[i][j - 1] {
1250 i -= 1;
1251 } else {
1252 j -= 1;
1253 }
1254 }
1255 common.reverse();
1256
1257 let mut result = Vec::new();
1258 let (mut last_i, mut last_j) = (0usize, 0usize);
1259 for (ci, cj) in &common {
1260 if *ci > last_i || *cj > last_j {
1261 result.push((first[last_i..*ci].to_vec(), second[last_j..*cj].to_vec()));
1262 }
1263 last_i = ci + 1;
1264 last_j = cj + 1;
1265 }
1266 if last_i < n || last_j < m {
1267 result.push((first[last_i..].to_vec(), second[last_j..].to_vec()));
1268 }
1269
1270 let mut merged: Vec<(Vec<i64>, Vec<i64>)> = Vec::new();
1272 for diff in result {
1273 if let Some(prev) = merged.last_mut() {
1274 if prev.0.is_empty() && diff.1.is_empty() {
1275 prev.0 = diff.0;
1276 continue;
1277 } else if prev.1.is_empty() && diff.0.is_empty() {
1278 prev.1 = diff.1;
1279 continue;
1280 }
1281 }
1282 merged.push(diff);
1283 }
1284 merged
1285 }
1286
1287 fn assert_page_length_differences(
1290 original: &ColumnInfo,
1291 modified: &ColumnInfo,
1292 exact_equal_diffs: usize,
1293 exact_larger_diffs: usize,
1294 exact_smaller_diffs: usize,
1295 edit_length: i64,
1296 ) {
1297 let diffs = find_differences(&original.page_lengths, &modified.page_lengths);
1298 let expected = exact_equal_diffs + exact_larger_diffs + exact_smaller_diffs;
1299
1300 if diffs.len() != expected {
1301 eprintln!("Original: {:?}", original.page_lengths);
1302 eprintln!("Modified: {:?}", modified.page_lengths);
1303 for d in &diffs {
1304 eprintln!(" Diff: {:?} vs {:?}", d.0, d.1);
1305 }
1306 }
1307 assert_eq!(
1308 diffs.len(),
1309 expected,
1310 "Expected {expected} diffs, got {}",
1311 diffs.len()
1312 );
1313
1314 let (mut eq, mut larger, mut smaller) = (0usize, 0usize, 0usize);
1315 for (left, right) in &diffs {
1316 let left_sum: i64 = left.iter().sum();
1317 let right_sum: i64 = right.iter().sum();
1318 match left_sum.cmp(&right_sum) {
1319 Ordering::Equal => eq += 1,
1320 Ordering::Less => {
1321 larger += 1;
1322 assert_eq!(
1323 left_sum + edit_length,
1324 right_sum,
1325 "Larger diff mismatch: {left_sum} + {edit_length} != {right_sum}"
1326 );
1327 }
1328 Ordering::Greater => {
1329 smaller += 1;
1330 assert_eq!(
1331 left_sum,
1332 right_sum + edit_length,
1333 "Smaller diff mismatch: {left_sum} != {right_sum} + {edit_length}"
1334 );
1335 }
1336 }
1337 }
1338
1339 assert_eq!(eq, exact_equal_diffs, "equal diffs count");
1340 assert_eq!(larger, exact_larger_diffs, "larger diffs count");
1341 assert_eq!(smaller, exact_smaller_diffs, "smaller diffs count");
1342 }
1343
1344 fn assert_page_length_differences_update(
1347 original: &ColumnInfo,
1348 modified: &ColumnInfo,
1349 max_equal_diffs: usize,
1350 ) {
1351 let diffs = find_differences(&original.page_lengths, &modified.page_lengths);
1352 assert!(
1353 diffs.len() <= max_equal_diffs,
1354 "Expected at most {max_equal_diffs} diffs, got {}",
1355 diffs.len()
1356 );
1357 for (left, right) in &diffs {
1358 let left_sum: i64 = left.iter().sum();
1359 let right_sum: i64 = right.iter().sum();
1360 assert_eq!(
1361 left_sum, right_sum,
1362 "Update diff should not change total row count"
1363 );
1364 }
1365 }
1366
1367 #[test]
1370 fn test_find_differences_basic() {
1371 let diffs = find_differences(&[1, 2, 3, 4, 5], &[1, 7, 8, 4, 5]);
1372 assert_eq!(diffs.len(), 1);
1373 assert_eq!(diffs[0].0, vec![2, 3]);
1374 assert_eq!(diffs[0].1, vec![7, 8]);
1375 }
1376
1377 #[test]
1378 fn test_find_differences_multiple() {
1379 let diffs = find_differences(&[1, 2, 3, 4, 5, 6, 7], &[1, 8, 9, 4, 10, 6, 11]);
1380 assert_eq!(diffs.len(), 3);
1381 assert_eq!(diffs[0].0, vec![2, 3]);
1382 assert_eq!(diffs[0].1, vec![8, 9]);
1383 assert_eq!(diffs[1].0, vec![5]);
1384 assert_eq!(diffs[1].1, vec![10]);
1385 assert_eq!(diffs[2].0, vec![7]);
1386 assert_eq!(diffs[2].1, vec![11]);
1387 }
1388
1389 #[test]
1390 fn test_find_differences_different_lengths() {
1391 let diffs = find_differences(&[1, 2, 3], &[1, 2, 3, 4, 5]);
1392 assert_eq!(diffs.len(), 1);
1393 assert!(diffs[0].0.is_empty());
1394 assert_eq!(diffs[0].1, vec![4, 5]);
1395 }
1396
1397 #[test]
1398 fn test_find_differences_empty() {
1399 let diffs = find_differences(&[], &[]);
1400 assert!(diffs.is_empty());
1401 }
1402
1403 #[test]
1404 fn test_find_differences_changes_at_both_ends() {
1405 let diffs = find_differences(&[1, 2, 3, 4, 5, 6, 7, 8, 9], &[0, 0, 2, 3, 4, 5, 7, 7, 8]);
1406 assert_eq!(diffs.len(), 3);
1407 assert_eq!(diffs[0].0, vec![1]);
1408 assert_eq!(diffs[0].1, vec![0, 0]);
1409 assert_eq!(diffs[1].0, vec![6]);
1410 assert_eq!(diffs[1].1, vec![7]);
1411 assert_eq!(diffs[2].0, vec![9]);
1412 assert!(diffs[2].1.is_empty());
1413 }
1414
1415 #[test]
1416 fn test_find_differences_additional() {
1417 let diffs = find_differences(
1418 &[445, 312, 393, 401, 410, 138, 558, 457],
1419 &[445, 312, 393, 393, 410, 138, 558, 457],
1420 );
1421 assert_eq!(diffs.len(), 1);
1422 assert_eq!(diffs[0].0, vec![401]);
1423 assert_eq!(diffs[0].1, vec![393]);
1424 }
1425
1426 macro_rules! cdc_single_rg_tests {
1429 ($mod_name:ident, $dtype:expr, $nullable:expr) => {
1430 mod $mod_name {
1431 use super::*;
1432
1433 fn config() -> (DataType, bool, usize, usize) {
1434 let dtype: DataType = $dtype;
1435 let nullable: bool = $nullable;
1436 let bpr = bytes_per_record(&dtype, nullable);
1437 let part_length = CDC_PART_SIZE / bpr;
1438 let edit_length = CDC_EDIT_SIZE / bpr;
1439 (dtype, nullable, part_length, edit_length)
1440 }
1441
1442 fn make_schema(dtype: &DataType, nullable: bool) -> Arc<Schema> {
1443 Arc::new(Schema::new(vec![Field::new("f0", dtype.clone(), nullable)]))
1444 }
1445
1446 #[test]
1447 #[cfg_attr(miri, ignore)] fn delete_once() {
1449 let (dtype, nullable, part_length, edit_length) = config();
1450 let schema = make_schema(&dtype, nullable);
1451
1452 let part1 = generate_table(&schema, part_length, 0);
1453 let part2 = generate_table(&schema, edit_length, 1);
1454 let part3 = generate_table(&schema, part_length, part_length as u64);
1455
1456 let base = concat_batches([&part1, &part2, &part3]);
1457 let modified = concat_batches([&part1, &part3]);
1458
1459 for enable_dictionary in [false, true] {
1460 let base_data = write_with_cdc_options(
1461 &[&base],
1462 CDC_MIN_CHUNK_SIZE,
1463 CDC_MAX_CHUNK_SIZE,
1464 Some(CDC_ROW_GROUP_LENGTH),
1465 enable_dictionary,
1466 );
1467 let mod_data = write_with_cdc_options(
1468 &[&modified],
1469 CDC_MIN_CHUNK_SIZE,
1470 CDC_MAX_CHUNK_SIZE,
1471 Some(CDC_ROW_GROUP_LENGTH),
1472 enable_dictionary,
1473 );
1474
1475 let base_info = get_column_info(&base_data, 0);
1476 let mod_info = get_column_info(&mod_data, 0);
1477 assert_eq!(base_info.len(), 1);
1478 assert_eq!(mod_info.len(), 1);
1479
1480 assert_cdc_chunk_sizes(
1481 &base.column(0).clone(),
1482 &base_info[0],
1483 nullable,
1484 CDC_MIN_CHUNK_SIZE,
1485 CDC_MAX_CHUNK_SIZE,
1486 enable_dictionary,
1487 );
1488 assert_cdc_chunk_sizes(
1489 &modified.column(0).clone(),
1490 &mod_info[0],
1491 nullable,
1492 CDC_MIN_CHUNK_SIZE,
1493 CDC_MAX_CHUNK_SIZE,
1494 enable_dictionary,
1495 );
1496
1497 assert_page_length_differences(
1498 &base_info[0],
1499 &mod_info[0],
1500 0,
1501 0,
1502 1,
1503 edit_length as i64,
1504 );
1505 }
1506 }
1507
1508 #[test]
1509 #[cfg_attr(miri, ignore)] fn delete_twice() {
1511 let (dtype, nullable, part_length, edit_length) = config();
1512 let schema = make_schema(&dtype, nullable);
1513
1514 let part1 = generate_table(&schema, part_length, 0);
1515 let part2 = generate_table(&schema, edit_length, 1);
1516 let part3 = generate_table(&schema, part_length, part_length as u64);
1517 let part4 = generate_table(&schema, edit_length, 2);
1518 let part5 = generate_table(&schema, part_length, 2 * part_length as u64);
1519
1520 let base = concat_batches([&part1, &part2, &part3, &part4, &part5]);
1521 let modified = concat_batches([&part1, &part3, &part5]);
1522
1523 for enable_dictionary in [false, true] {
1524 let base_data = write_with_cdc_options(
1525 &[&base],
1526 CDC_MIN_CHUNK_SIZE,
1527 CDC_MAX_CHUNK_SIZE,
1528 Some(CDC_ROW_GROUP_LENGTH),
1529 enable_dictionary,
1530 );
1531 let mod_data = write_with_cdc_options(
1532 &[&modified],
1533 CDC_MIN_CHUNK_SIZE,
1534 CDC_MAX_CHUNK_SIZE,
1535 Some(CDC_ROW_GROUP_LENGTH),
1536 enable_dictionary,
1537 );
1538
1539 let base_info = get_column_info(&base_data, 0);
1540 let mod_info = get_column_info(&mod_data, 0);
1541 assert_eq!(base_info.len(), 1);
1542 assert_eq!(mod_info.len(), 1);
1543
1544 assert_cdc_chunk_sizes(
1545 &base.column(0).clone(),
1546 &base_info[0],
1547 nullable,
1548 CDC_MIN_CHUNK_SIZE,
1549 CDC_MAX_CHUNK_SIZE,
1550 enable_dictionary,
1551 );
1552 assert_cdc_chunk_sizes(
1553 &modified.column(0).clone(),
1554 &mod_info[0],
1555 nullable,
1556 CDC_MIN_CHUNK_SIZE,
1557 CDC_MAX_CHUNK_SIZE,
1558 enable_dictionary,
1559 );
1560
1561 assert_page_length_differences(
1562 &base_info[0],
1563 &mod_info[0],
1564 0,
1565 0,
1566 2,
1567 edit_length as i64,
1568 );
1569 }
1570 }
1571
1572 #[test]
1573 #[cfg_attr(miri, ignore)] fn insert_once() {
1575 let (dtype, nullable, part_length, edit_length) = config();
1576 let schema = make_schema(&dtype, nullable);
1577
1578 let part1 = generate_table(&schema, part_length, 0);
1579 let part2 = generate_table(&schema, edit_length, 1);
1580 let part3 = generate_table(&schema, part_length, part_length as u64);
1581
1582 let base = concat_batches([&part1, &part3]);
1583 let modified = concat_batches([&part1, &part2, &part3]);
1584
1585 for enable_dictionary in [false, true] {
1586 let base_data = write_with_cdc_options(
1587 &[&base],
1588 CDC_MIN_CHUNK_SIZE,
1589 CDC_MAX_CHUNK_SIZE,
1590 Some(CDC_ROW_GROUP_LENGTH),
1591 enable_dictionary,
1592 );
1593 let mod_data = write_with_cdc_options(
1594 &[&modified],
1595 CDC_MIN_CHUNK_SIZE,
1596 CDC_MAX_CHUNK_SIZE,
1597 Some(CDC_ROW_GROUP_LENGTH),
1598 enable_dictionary,
1599 );
1600
1601 let base_info = get_column_info(&base_data, 0);
1602 let mod_info = get_column_info(&mod_data, 0);
1603 assert_eq!(base_info.len(), 1);
1604 assert_eq!(mod_info.len(), 1);
1605
1606 assert_cdc_chunk_sizes(
1607 &base.column(0).clone(),
1608 &base_info[0],
1609 nullable,
1610 CDC_MIN_CHUNK_SIZE,
1611 CDC_MAX_CHUNK_SIZE,
1612 enable_dictionary,
1613 );
1614 assert_cdc_chunk_sizes(
1615 &modified.column(0).clone(),
1616 &mod_info[0],
1617 nullable,
1618 CDC_MIN_CHUNK_SIZE,
1619 CDC_MAX_CHUNK_SIZE,
1620 enable_dictionary,
1621 );
1622
1623 assert_page_length_differences(
1624 &base_info[0],
1625 &mod_info[0],
1626 0,
1627 1,
1628 0,
1629 edit_length as i64,
1630 );
1631 }
1632 }
1633
1634 #[test]
1635 #[cfg_attr(miri, ignore)] fn insert_twice() {
1637 let (dtype, nullable, part_length, edit_length) = config();
1638 let schema = make_schema(&dtype, nullable);
1639
1640 let part1 = generate_table(&schema, part_length, 0);
1641 let part2 = generate_table(&schema, edit_length, 1);
1642 let part3 = generate_table(&schema, part_length, part_length as u64);
1643 let part4 = generate_table(&schema, edit_length, 2);
1644 let part5 = generate_table(&schema, part_length, 2 * part_length as u64);
1645
1646 let base = concat_batches([&part1, &part3, &part5]);
1647 let modified = concat_batches([&part1, &part2, &part3, &part4, &part5]);
1648
1649 for enable_dictionary in [false, true] {
1650 let base_data = write_with_cdc_options(
1651 &[&base],
1652 CDC_MIN_CHUNK_SIZE,
1653 CDC_MAX_CHUNK_SIZE,
1654 Some(CDC_ROW_GROUP_LENGTH),
1655 enable_dictionary,
1656 );
1657 let mod_data = write_with_cdc_options(
1658 &[&modified],
1659 CDC_MIN_CHUNK_SIZE,
1660 CDC_MAX_CHUNK_SIZE,
1661 Some(CDC_ROW_GROUP_LENGTH),
1662 enable_dictionary,
1663 );
1664
1665 let base_info = get_column_info(&base_data, 0);
1666 let mod_info = get_column_info(&mod_data, 0);
1667 assert_eq!(base_info.len(), 1);
1668 assert_eq!(mod_info.len(), 1);
1669
1670 assert_cdc_chunk_sizes(
1671 &base.column(0).clone(),
1672 &base_info[0],
1673 nullable,
1674 CDC_MIN_CHUNK_SIZE,
1675 CDC_MAX_CHUNK_SIZE,
1676 enable_dictionary,
1677 );
1678 assert_cdc_chunk_sizes(
1679 &modified.column(0).clone(),
1680 &mod_info[0],
1681 nullable,
1682 CDC_MIN_CHUNK_SIZE,
1683 CDC_MAX_CHUNK_SIZE,
1684 enable_dictionary,
1685 );
1686
1687 assert_page_length_differences(
1688 &base_info[0],
1689 &mod_info[0],
1690 0,
1691 2,
1692 0,
1693 edit_length as i64,
1694 );
1695 }
1696 }
1697
1698 #[test]
1699 #[cfg_attr(miri, ignore)] fn update_once() {
1701 let (dtype, nullable, part_length, edit_length) = config();
1702 let schema = make_schema(&dtype, nullable);
1703
1704 let part1 = generate_table(&schema, part_length, 0);
1705 let part2 = generate_table(&schema, edit_length, 1);
1706 let part3 = generate_table(&schema, part_length, part_length as u64);
1707 let part4 = generate_table(&schema, edit_length, 2);
1708
1709 let base = concat_batches([&part1, &part2, &part3]);
1710 let modified = concat_batches([&part1, &part4, &part3]);
1711
1712 for enable_dictionary in [false, true] {
1713 let base_data = write_with_cdc_options(
1714 &[&base],
1715 CDC_MIN_CHUNK_SIZE,
1716 CDC_MAX_CHUNK_SIZE,
1717 Some(CDC_ROW_GROUP_LENGTH),
1718 enable_dictionary,
1719 );
1720 let mod_data = write_with_cdc_options(
1721 &[&modified],
1722 CDC_MIN_CHUNK_SIZE,
1723 CDC_MAX_CHUNK_SIZE,
1724 Some(CDC_ROW_GROUP_LENGTH),
1725 enable_dictionary,
1726 );
1727
1728 let base_info = get_column_info(&base_data, 0);
1729 let mod_info = get_column_info(&mod_data, 0);
1730 assert_eq!(base_info.len(), 1);
1731 assert_eq!(mod_info.len(), 1);
1732
1733 assert_cdc_chunk_sizes(
1734 &base.column(0).clone(),
1735 &base_info[0],
1736 nullable,
1737 CDC_MIN_CHUNK_SIZE,
1738 CDC_MAX_CHUNK_SIZE,
1739 enable_dictionary,
1740 );
1741 assert_cdc_chunk_sizes(
1742 &modified.column(0).clone(),
1743 &mod_info[0],
1744 nullable,
1745 CDC_MIN_CHUNK_SIZE,
1746 CDC_MAX_CHUNK_SIZE,
1747 enable_dictionary,
1748 );
1749
1750 assert_page_length_differences_update(&base_info[0], &mod_info[0], 1);
1751 }
1752 }
1753
1754 #[test]
1755 #[cfg_attr(miri, ignore)] fn update_twice() {
1757 let (dtype, nullable, part_length, edit_length) = config();
1758 let schema = make_schema(&dtype, nullable);
1759
1760 let part1 = generate_table(&schema, part_length, 0);
1761 let part2 = generate_table(&schema, edit_length, 1);
1762 let part3 = generate_table(&schema, part_length, part_length as u64);
1763 let part4 = generate_table(&schema, edit_length, 2);
1764 let part5 = generate_table(&schema, part_length, 2 * part_length as u64);
1765 let part6 = generate_table(&schema, edit_length, 3);
1766 let part7 = generate_table(&schema, edit_length, 4);
1767
1768 let base = concat_batches([&part1, &part2, &part3, &part4, &part5]);
1769 let modified = concat_batches([&part1, &part6, &part3, &part7, &part5]);
1770
1771 for enable_dictionary in [false, true] {
1772 let base_data = write_with_cdc_options(
1773 &[&base],
1774 CDC_MIN_CHUNK_SIZE,
1775 CDC_MAX_CHUNK_SIZE,
1776 Some(CDC_ROW_GROUP_LENGTH),
1777 enable_dictionary,
1778 );
1779 let mod_data = write_with_cdc_options(
1780 &[&modified],
1781 CDC_MIN_CHUNK_SIZE,
1782 CDC_MAX_CHUNK_SIZE,
1783 Some(CDC_ROW_GROUP_LENGTH),
1784 enable_dictionary,
1785 );
1786
1787 let base_info = get_column_info(&base_data, 0);
1788 let mod_info = get_column_info(&mod_data, 0);
1789 assert_eq!(base_info.len(), 1);
1790 assert_eq!(mod_info.len(), 1);
1791
1792 assert_cdc_chunk_sizes(
1793 &base.column(0).clone(),
1794 &base_info[0],
1795 nullable,
1796 CDC_MIN_CHUNK_SIZE,
1797 CDC_MAX_CHUNK_SIZE,
1798 enable_dictionary,
1799 );
1800 assert_cdc_chunk_sizes(
1801 &modified.column(0).clone(),
1802 &mod_info[0],
1803 nullable,
1804 CDC_MIN_CHUNK_SIZE,
1805 CDC_MAX_CHUNK_SIZE,
1806 enable_dictionary,
1807 );
1808
1809 assert_page_length_differences_update(&base_info[0], &mod_info[0], 2);
1810 }
1811 }
1812
1813 #[test]
1814 #[cfg_attr(miri, ignore)] fn prepend() {
1816 let (dtype, nullable, part_length, edit_length) = config();
1817 let schema = make_schema(&dtype, nullable);
1818
1819 let part1 = generate_table(&schema, part_length, 0);
1820 let part2 = generate_table(&schema, edit_length, 1);
1821 let part3 = generate_table(&schema, part_length, part_length as u64);
1822 let part4 = generate_table(&schema, edit_length, 2);
1823
1824 let base = concat_batches([&part1, &part2, &part3]);
1825 let modified = concat_batches([&part4, &part1, &part2, &part3]);
1826
1827 for enable_dictionary in [false, true] {
1828 let base_data = write_with_cdc_options(
1829 &[&base],
1830 CDC_MIN_CHUNK_SIZE,
1831 CDC_MAX_CHUNK_SIZE,
1832 Some(CDC_ROW_GROUP_LENGTH),
1833 enable_dictionary,
1834 );
1835 let mod_data = write_with_cdc_options(
1836 &[&modified],
1837 CDC_MIN_CHUNK_SIZE,
1838 CDC_MAX_CHUNK_SIZE,
1839 Some(CDC_ROW_GROUP_LENGTH),
1840 enable_dictionary,
1841 );
1842
1843 let base_info = get_column_info(&base_data, 0);
1844 let mod_info = get_column_info(&mod_data, 0);
1845 assert_eq!(base_info.len(), 1);
1846 assert_eq!(mod_info.len(), 1);
1847
1848 assert_cdc_chunk_sizes(
1849 &base.column(0).clone(),
1850 &base_info[0],
1851 nullable,
1852 CDC_MIN_CHUNK_SIZE,
1853 CDC_MAX_CHUNK_SIZE,
1854 enable_dictionary,
1855 );
1856 assert_cdc_chunk_sizes(
1857 &modified.column(0).clone(),
1858 &mod_info[0],
1859 nullable,
1860 CDC_MIN_CHUNK_SIZE,
1861 CDC_MAX_CHUNK_SIZE,
1862 enable_dictionary,
1863 );
1864
1865 assert!(
1866 mod_info[0].page_lengths.len() >= base_info[0].page_lengths.len(),
1867 "Modified should have same or more pages"
1868 );
1869
1870 assert_page_length_differences(
1871 &base_info[0],
1872 &mod_info[0],
1873 0,
1874 1,
1875 0,
1876 edit_length as i64,
1877 );
1878 }
1879 }
1880
1881 #[test]
1882 #[cfg_attr(miri, ignore)] fn append() {
1884 let (dtype, nullable, part_length, edit_length) = config();
1885 let schema = make_schema(&dtype, nullable);
1886
1887 let part1 = generate_table(&schema, part_length, 0);
1888 let part2 = generate_table(&schema, edit_length, 1);
1889 let part3 = generate_table(&schema, part_length, part_length as u64);
1890 let part4 = generate_table(&schema, edit_length, 2);
1891
1892 let base = concat_batches([&part1, &part2, &part3]);
1893 let modified = concat_batches([&part1, &part2, &part3, &part4]);
1894
1895 for enable_dictionary in [false, true] {
1896 let base_data = write_with_cdc_options(
1897 &[&base],
1898 CDC_MIN_CHUNK_SIZE,
1899 CDC_MAX_CHUNK_SIZE,
1900 Some(CDC_ROW_GROUP_LENGTH),
1901 enable_dictionary,
1902 );
1903 let mod_data = write_with_cdc_options(
1904 &[&modified],
1905 CDC_MIN_CHUNK_SIZE,
1906 CDC_MAX_CHUNK_SIZE,
1907 Some(CDC_ROW_GROUP_LENGTH),
1908 enable_dictionary,
1909 );
1910
1911 let base_info = get_column_info(&base_data, 0);
1912 let mod_info = get_column_info(&mod_data, 0);
1913 assert_eq!(base_info.len(), 1);
1914 assert_eq!(mod_info.len(), 1);
1915
1916 assert_cdc_chunk_sizes(
1917 &base.column(0).clone(),
1918 &base_info[0],
1919 nullable,
1920 CDC_MIN_CHUNK_SIZE,
1921 CDC_MAX_CHUNK_SIZE,
1922 enable_dictionary,
1923 );
1924 assert_cdc_chunk_sizes(
1925 &modified.column(0).clone(),
1926 &mod_info[0],
1927 nullable,
1928 CDC_MIN_CHUNK_SIZE,
1929 CDC_MAX_CHUNK_SIZE,
1930 enable_dictionary,
1931 );
1932
1933 let bp = &base_info[0].page_lengths;
1934 let mp = &mod_info[0].page_lengths;
1935 assert!(mp.len() >= bp.len());
1936 for i in 0..bp.len() - 1 {
1937 assert_eq!(bp[i], mp[i], "Page {i} should be identical");
1938 }
1939 assert!(mp[bp.len() - 1] >= bp[bp.len() - 1]);
1940 }
1941 }
1942
1943 #[test]
1944 fn empty_table() {
1945 let (dtype, nullable, _, _) = config();
1946 let schema = make_schema(&dtype, nullable);
1947
1948 let empty = RecordBatch::new_empty(schema);
1949 for enable_dictionary in [false, true] {
1950 let data = write_with_cdc_options(
1951 &[&empty],
1952 CDC_MIN_CHUNK_SIZE,
1953 CDC_MAX_CHUNK_SIZE,
1954 Some(CDC_ROW_GROUP_LENGTH),
1955 enable_dictionary,
1956 );
1957 let info = get_column_info(&data, 0);
1958 if !info.is_empty() {
1960 assert!(info[0].page_lengths.is_empty());
1961 }
1962 }
1963 }
1964
1965 #[test]
1966 #[cfg_attr(miri, ignore)] fn array_offsets() {
1968 let (dtype, nullable, part_length, edit_length) = config();
1969 let schema = make_schema(&dtype, nullable);
1970
1971 let table = concat_batches([
1972 &generate_table(&schema, part_length, 0),
1973 &generate_table(&schema, edit_length, 1),
1974 &generate_table(&schema, part_length, part_length as u64),
1975 ]);
1976
1977 for offset in [0usize, 512, 1024] {
1978 if offset >= table.num_rows() {
1979 continue;
1980 }
1981 let sliced = table.slice(offset, table.num_rows() - offset);
1982 let data = write_with_cdc_options(
1983 &[&sliced],
1984 CDC_MIN_CHUNK_SIZE,
1985 CDC_MAX_CHUNK_SIZE,
1986 Some(CDC_ROW_GROUP_LENGTH),
1987 true,
1988 );
1989 let info = get_column_info(&data, 0);
1990 assert_eq!(info.len(), 1);
1991
1992 assert_cdc_chunk_sizes(
1994 &sliced.column(0).clone(),
1995 &info[0],
1996 nullable,
1997 CDC_MIN_CHUNK_SIZE,
1998 CDC_MAX_CHUNK_SIZE,
1999 true,
2000 );
2001 }
2002 }
2003 }
2004 };
2005 }
2006
2007 cdc_single_rg_tests!(cdc_bool_non_null, DataType::Boolean, false);
2009 cdc_single_rg_tests!(cdc_i32_non_null, DataType::Int32, false);
2010 cdc_single_rg_tests!(cdc_i64_nullable, DataType::Int64, true);
2011 cdc_single_rg_tests!(cdc_f64_nullable, DataType::Float64, true);
2012 cdc_single_rg_tests!(cdc_utf8_non_null, DataType::Utf8, false);
2013 cdc_single_rg_tests!(cdc_binary_nullable, DataType::Binary, true);
2014 cdc_single_rg_tests!(cdc_fsb16_nullable, DataType::FixedSizeBinary(16), true);
2015 cdc_single_rg_tests!(cdc_date32_non_null, DataType::Date32, false);
2016 cdc_single_rg_tests!(
2017 cdc_timestamp_nullable,
2018 DataType::Timestamp(arrow_schema::TimeUnit::Nanosecond, None),
2019 true
2020 );
2021
2022 mod cdc_multiple_row_groups {
2025 use super::*;
2026
2027 const PART_LENGTH: usize = 128 * 1024;
2028 const EDIT_LENGTH: usize = 128;
2029 const ROW_GROUP_LENGTH: usize = 64 * 1024;
2030
2031 fn schema() -> Arc<Schema> {
2032 Arc::new(Schema::new(vec![
2033 Field::new("int32", DataType::Int32, true),
2034 Field::new("float64", DataType::Float64, true),
2035 Field::new("bool", DataType::Boolean, false),
2036 ]))
2037 }
2038
2039 #[test]
2040 #[cfg_attr(miri, ignore)] fn insert_once() {
2042 let s = schema();
2043 let part1 = generate_table(&s, PART_LENGTH, 0);
2044 let part2 = generate_table(&s, PART_LENGTH, 2);
2045 let part3 = generate_table(&s, PART_LENGTH, 4);
2046 let edit1 = generate_table(&s, EDIT_LENGTH, 1);
2047 let edit2 = generate_table(&s, EDIT_LENGTH, 3);
2048
2049 let base = concat_batches([&part1, &edit1, &part2, &part3]);
2050 let modified = concat_batches([&part1, &edit1, &edit2, &part2, &part3]);
2051 assert_eq!(modified.num_rows(), base.num_rows() + EDIT_LENGTH);
2052
2053 let base_data = write_with_cdc_options(
2054 &[&base],
2055 CDC_MIN_CHUNK_SIZE,
2056 CDC_MAX_CHUNK_SIZE,
2057 Some(ROW_GROUP_LENGTH),
2058 false,
2059 );
2060 let mod_data = write_with_cdc_options(
2061 &[&modified],
2062 CDC_MIN_CHUNK_SIZE,
2063 CDC_MAX_CHUNK_SIZE,
2064 Some(ROW_GROUP_LENGTH),
2065 false,
2066 );
2067
2068 for col in 0..s.fields().len() {
2069 let base_info = get_column_info(&base_data, col);
2070 let mod_info = get_column_info(&mod_data, col);
2071
2072 assert_eq!(base_info.len(), 7, "expected 7 row groups for col {col}");
2073 assert_eq!(mod_info.len(), 7);
2074
2075 assert_eq!(base_info[0].page_lengths, mod_info[0].page_lengths);
2077 assert_eq!(base_info[1].page_lengths, mod_info[1].page_lengths);
2078
2079 for i in 2..mod_info.len() - 1 {
2081 assert_page_length_differences(
2082 &base_info[i],
2083 &mod_info[i],
2084 0,
2085 1,
2086 1,
2087 EDIT_LENGTH as i64,
2088 );
2089 }
2090 assert_page_length_differences(
2092 base_info.last().unwrap(),
2093 mod_info.last().unwrap(),
2094 0,
2095 1,
2096 0,
2097 EDIT_LENGTH as i64,
2098 );
2099 }
2100 }
2101
2102 #[test]
2103 #[cfg_attr(miri, ignore)] fn delete_once() {
2105 let s = schema();
2106 let part1 = generate_table(&s, PART_LENGTH, 0);
2107 let part2 = generate_table(&s, PART_LENGTH, 2);
2108 let part3 = generate_table(&s, PART_LENGTH, 4);
2109 let edit1 = generate_table(&s, EDIT_LENGTH, 1);
2110 let edit2 = generate_table(&s, EDIT_LENGTH, 3);
2111
2112 let base = concat_batches([&part1, &edit1, &part2, &part3, &edit2]);
2113 let modified = concat_batches([&part1, &part2, &part3, &edit2]);
2114
2115 let base_data = write_with_cdc_options(
2116 &[&base],
2117 CDC_MIN_CHUNK_SIZE,
2118 CDC_MAX_CHUNK_SIZE,
2119 Some(ROW_GROUP_LENGTH),
2120 false,
2121 );
2122 let mod_data = write_with_cdc_options(
2123 &[&modified],
2124 CDC_MIN_CHUNK_SIZE,
2125 CDC_MAX_CHUNK_SIZE,
2126 Some(ROW_GROUP_LENGTH),
2127 false,
2128 );
2129
2130 for col in 0..s.fields().len() {
2131 let base_info = get_column_info(&base_data, col);
2132 let mod_info = get_column_info(&mod_data, col);
2133
2134 assert_eq!(base_info.len(), 7);
2135 assert_eq!(mod_info.len(), 7);
2136
2137 assert_eq!(base_info[0].page_lengths, mod_info[0].page_lengths);
2138 assert_eq!(base_info[1].page_lengths, mod_info[1].page_lengths);
2139
2140 for i in 2..mod_info.len() - 1 {
2141 assert_page_length_differences(
2142 &base_info[i],
2143 &mod_info[i],
2144 0,
2145 1,
2146 1,
2147 EDIT_LENGTH as i64,
2148 );
2149 }
2150 assert_page_length_differences(
2151 base_info.last().unwrap(),
2152 mod_info.last().unwrap(),
2153 0,
2154 0,
2155 1,
2156 EDIT_LENGTH as i64,
2157 );
2158 }
2159 }
2160
2161 #[test]
2162 #[cfg_attr(miri, ignore)] fn update_once() {
2164 let s = schema();
2165 let part1 = generate_table(&s, PART_LENGTH, 0);
2166 let part2 = generate_table(&s, PART_LENGTH, 2);
2167 let part3 = generate_table(&s, PART_LENGTH, 4);
2168 let edit1 = generate_table(&s, EDIT_LENGTH, 1);
2169 let edit2 = generate_table(&s, EDIT_LENGTH, 3);
2170 let edit3 = generate_table(&s, EDIT_LENGTH, 5);
2171
2172 let base = concat_batches([&part1, &edit1, &part2, &part3, &edit2]);
2173 let modified = concat_batches([&part1, &edit3, &part2, &part3, &edit2]);
2174
2175 let base_data = write_with_cdc_options(
2176 &[&base],
2177 CDC_MIN_CHUNK_SIZE,
2178 CDC_MAX_CHUNK_SIZE,
2179 Some(ROW_GROUP_LENGTH),
2180 false,
2181 );
2182 let mod_data = write_with_cdc_options(
2183 &[&modified],
2184 CDC_MIN_CHUNK_SIZE,
2185 CDC_MAX_CHUNK_SIZE,
2186 Some(ROW_GROUP_LENGTH),
2187 false,
2188 );
2189
2190 for col in 0..s.fields().len() {
2191 let nullable = s.field(col).is_nullable();
2192 let base_info = get_column_info(&base_data, col);
2193 let mod_info = get_column_info(&mod_data, col);
2194
2195 assert_eq!(base_info.len(), 7);
2196 assert_eq!(mod_info.len(), 7);
2197
2198 assert_cdc_chunk_sizes(
2200 &base.column(col).slice(0, ROW_GROUP_LENGTH),
2201 &base_info[0],
2202 nullable,
2203 CDC_MIN_CHUNK_SIZE,
2204 CDC_MAX_CHUNK_SIZE,
2205 false,
2206 );
2207
2208 assert_eq!(base_info[0].page_lengths, mod_info[0].page_lengths);
2209 assert_eq!(base_info[1].page_lengths, mod_info[1].page_lengths);
2210
2211 assert_page_length_differences_update(&base_info[2], &mod_info[2], 1);
2213
2214 for i in 3..mod_info.len() {
2216 assert_eq!(base_info[i].page_lengths, mod_info[i].page_lengths);
2217 }
2218 }
2219 }
2220
2221 #[test]
2222 #[cfg_attr(miri, ignore)] fn append() {
2224 let s = schema();
2225 let part1 = generate_table(&s, PART_LENGTH, 0);
2226 let part2 = generate_table(&s, PART_LENGTH, 2);
2227 let part3 = generate_table(&s, PART_LENGTH, 4);
2228 let edit1 = generate_table(&s, EDIT_LENGTH, 1);
2229 let edit2 = generate_table(&s, EDIT_LENGTH, 3);
2230
2231 let base = concat_batches([&part1, &edit1, &part2, &part3]);
2232 let modified = concat_batches([&part1, &edit1, &part2, &part3, &edit2]);
2233
2234 let base_data = write_with_cdc_options(
2235 &[&base],
2236 CDC_MIN_CHUNK_SIZE,
2237 CDC_MAX_CHUNK_SIZE,
2238 Some(ROW_GROUP_LENGTH),
2239 false,
2240 );
2241 let mod_data = write_with_cdc_options(
2242 &[&modified],
2243 CDC_MIN_CHUNK_SIZE,
2244 CDC_MAX_CHUNK_SIZE,
2245 Some(ROW_GROUP_LENGTH),
2246 false,
2247 );
2248
2249 for col in 0..s.fields().len() {
2250 let nullable = s.field(col).is_nullable();
2251 let base_info = get_column_info(&base_data, col);
2252 let mod_info = get_column_info(&mod_data, col);
2253
2254 assert_eq!(base_info.len(), 7);
2255 assert_eq!(mod_info.len(), 7);
2256
2257 assert_cdc_chunk_sizes(
2259 &base.column(col).slice(0, ROW_GROUP_LENGTH),
2260 &base_info[0],
2261 nullable,
2262 CDC_MIN_CHUNK_SIZE,
2263 CDC_MAX_CHUNK_SIZE,
2264 false,
2265 );
2266
2267 for i in 0..base_info.len() - 1 {
2269 assert_eq!(base_info[i].page_lengths, mod_info[i].page_lengths);
2270 }
2271
2272 let bp = &base_info.last().unwrap().page_lengths;
2274 let mp = &mod_info.last().unwrap().page_lengths;
2275 assert!(mp.len() >= bp.len());
2276 for i in 0..bp.len() - 1 {
2277 assert_eq!(bp[i], mp[i]);
2278 }
2279 }
2280 }
2281 }
2282
2283 #[test]
2286 #[cfg_attr(miri, ignore)] fn test_cdc_array_offsets_direct() {
2288 use crate::basic::Type as PhysicalType;
2289 use crate::schema::types::{ColumnDescriptor, ColumnPath, Type};
2290
2291 let options = CdcOptions {
2292 min_chunk_size: CDC_MIN_CHUNK_SIZE,
2293 max_chunk_size: CDC_MAX_CHUNK_SIZE,
2294 norm_level: 0,
2295 };
2296 let desc = {
2297 let tp = Type::primitive_type_builder("col", PhysicalType::INT32)
2298 .build()
2299 .unwrap();
2300 ColumnDescriptor::new(Arc::new(tp), 0, 0, ColumnPath::new(vec![]))
2301 };
2302
2303 let bpr = bytes_per_record(&DataType::Int32, false);
2304 let n = CDC_PART_SIZE / bpr;
2305 let offset = 10usize;
2306
2307 let array: Int32Array = (0..n).map(|i| test_hash(0, i as u64) as i32).collect();
2308 let mut chunker = super::ContentDefinedChunker::new(&desc, &options).unwrap();
2309 let chunks = chunker
2310 .get_arrow_chunks(LevelDataRef::Absent, LevelDataRef::Absent, &array)
2311 .unwrap();
2312
2313 let sliced = array.slice(offset, n - offset);
2314 let mut chunker2 = super::ContentDefinedChunker::new(&desc, &options).unwrap();
2315 let chunks2 = chunker2
2316 .get_arrow_chunks(LevelDataRef::Absent, LevelDataRef::Absent, &sliced)
2317 .unwrap();
2318
2319 let values: Vec<usize> = chunks.iter().map(|c| c.num_values).collect();
2320 let values2: Vec<usize> = chunks2.iter().map(|c| c.num_values).collect();
2321
2322 assert!(values.len() > 1, "expected multiple chunks, got {values:?}");
2323 assert_eq!(values.len(), values2.len(), "chunk count must match");
2324
2325 assert_eq!(
2326 values[0] - values2[0],
2327 offset,
2328 "offsetted first chunk should be {offset} values shorter"
2329 );
2330 assert_eq!(
2331 &values[1..],
2332 &values2[1..],
2333 "all chunks after the first must be identical"
2334 );
2335 }
2336
2337 #[test]
2342 #[cfg_attr(miri, ignore)] fn test_cdc_list_roundtrip() {
2344 let schema = Arc::new(Schema::new(vec![
2345 Field::new(
2346 "_1",
2347 DataType::List(Arc::new(Field::new_list_field(DataType::Int32, true))),
2348 true,
2349 ),
2350 Field::new(
2351 "_2",
2352 DataType::List(Arc::new(Field::new_list_field(DataType::Boolean, true))),
2353 true,
2354 ),
2355 Field::new(
2356 "_3",
2357 DataType::LargeList(Arc::new(Field::new_list_field(DataType::Utf8, true))),
2358 true,
2359 ),
2360 ]));
2361 let batch = create_random_batch(schema, 10_000, 0.25, 0.75).unwrap();
2362 write_with_cdc_options(
2363 &[&batch],
2364 CDC_MIN_CHUNK_SIZE,
2365 CDC_MAX_CHUNK_SIZE,
2366 None,
2367 true,
2368 );
2369 }
2370
2371 #[test]
2373 #[cfg_attr(miri, ignore)] fn test_cdc_deeply_nested_roundtrip() {
2375 let inner_field = Field::new_list_field(DataType::Int32, true);
2376 let inner_type = DataType::List(Arc::new(inner_field));
2377 let outer_field = Field::new_list_field(inner_type.clone(), true);
2378 let list_list_type = DataType::List(Arc::new(outer_field));
2379
2380 let struct_inner_field = Field::new_list_field(DataType::Int32, true);
2381 let struct_inner_type = DataType::List(Arc::new(struct_inner_field));
2382 let struct_fields = Fields::from(vec![Field::new("a", struct_inner_type, true)]);
2383 let struct_type = DataType::Struct(struct_fields);
2384 let struct_list_field = Field::new_list_field(struct_type, true);
2385 let list_struct_type = DataType::List(Arc::new(struct_list_field));
2386
2387 let schema = Arc::new(Schema::new(vec![
2388 Field::new("list_list", list_list_type, true),
2389 Field::new("list_struct_list", list_struct_type, true),
2390 ]));
2391 let batch = create_random_batch(schema, 10_000, 0.25, 0.75).unwrap();
2392 write_with_cdc_options(
2393 &[&batch],
2394 CDC_MIN_CHUNK_SIZE,
2395 CDC_MAX_CHUNK_SIZE,
2396 None,
2397 true,
2398 );
2399 }
2400
2401 #[test]
2407 fn test_cdc_list_non_empty_null_segments() {
2408 let values = Int32Array::from(vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
2415 let offsets = Buffer::from_iter([0_i32, 2, 5, 7, 9, 10]);
2416 let null_bitmap = Buffer::from([0b00010101]); let list_type = DataType::List(Arc::new(Field::new_list_field(DataType::Int32, false)));
2419 let list_data = unsafe {
2420 ArrayData::new_unchecked(
2421 list_type.clone(),
2422 5,
2423 None,
2424 Some(null_bitmap),
2425 0,
2426 vec![offsets],
2427 vec![values.to_data()],
2428 )
2429 };
2430 let list_array = arrow_array::make_array(list_data);
2431
2432 let schema = Arc::new(Schema::new(vec![Field::new("col", list_type, true)]));
2433 let batch = RecordBatch::try_new(schema, vec![list_array]).unwrap();
2434
2435 let buf = write_with_cdc_options(
2436 &[&batch],
2437 CDC_MIN_CHUNK_SIZE,
2438 CDC_MAX_CHUNK_SIZE,
2439 None,
2440 true,
2441 );
2442 let read = concat_batches(read_batches(&buf));
2443 let read_list = read.column(0).as_list::<i32>();
2444 assert_eq!(read_list.len(), 5);
2445 assert!(read_list.is_valid(0));
2446 assert!(read_list.is_null(1));
2447 assert!(read_list.is_valid(2));
2448 assert!(read_list.is_null(3));
2449 assert!(read_list.is_valid(4));
2450
2451 let get_vals = |i: usize| -> Vec<i32> {
2452 read_list
2453 .value(i)
2454 .as_primitive::<arrow_array::types::Int32Type>()
2455 .values()
2456 .iter()
2457 .copied()
2458 .collect()
2459 };
2460 assert_eq!(get_vals(0), vec![1, 2]);
2461 assert_eq!(get_vals(2), vec![6, 7]);
2462 assert_eq!(get_vals(4), vec![10]);
2463 }
2464}