JeonDaehong commented on code in PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#discussion_r4335907979
##########
crates/iceberg/src/delete_vector.rs:
##########
@@ -316,10 +460,284 @@ pub(crate) fn frame_dv_blob(vector: &[u8]) -> Vec<u8> {
blob
}
+/// Deterministic pseudo-random sets mixing single positions, short and long
runs, runs across
+/// 2^16 and 2^32 boundaries, and empty bitmaps between used ones.
+#[cfg(test)]
+pub(crate) fn mixed_delete_vectors() -> Vec<DeleteVector> {
+ let mut state = 0x9E37_79B9_7F4A_7C15u64;
+ let mut rand = move || {
+ state ^= state << 13;
+ state ^= state >> 7;
+ state ^= state << 17;
+ state
+ };
Review Comment:
Done in 743ae5389. `mixed_delete_vectors` and the three model tests use
`StdRng::seed_from_u64` now, with ranges instead of the modulo arithmetic.
##########
crates/iceberg/src/arrow/reader/positional_deletes.rs:
##########
@@ -211,6 +184,171 @@ mod tests {
Arc::new(SchemaDescriptor::new(Arc::new(schema)))
}
+ /// Row groups and deleted runs that cross the 2^32 position boundary,
with and without row
+ /// group selection.
+ #[test]
+ fn test_build_deletes_row_selection_across_2_pow_32() {
+ let schema_descr = get_test_schema_descr();
+ let columns: Vec<_> = schema_descr
+ .columns()
+ .iter()
+ .map(|ptr|
ColumnChunkMetaData::builder(ptr.clone()).build().unwrap())
+ .collect();
+ let row_groups = |sizes: &[i64]| -> Vec<RowGroupMetaData> {
+ sizes
+ .iter()
+ .enumerate()
+ .map(|(i, &n)| {
+ build_test_row_group_meta(schema_descr.clone(),
columns.clone(), n, i as i16)
+ })
+ .collect()
+ };
+ let select = RowSelector::select;
+ let skip = RowSelector::skip;
+ let high = 1u64 << 32;
+ let big = high as usize;
+
+ // Row group 1 starts at 2^32 - 2. The run 2^32 - 3 ..= 2^32 crosses
both boundaries.
+ let meta = row_groups(&[(1 << 32) - 2, 8]);
+ let deletes = DeleteVector::new(RoaringTreemap::from_iter([
+ 1,
+ high - 3,
+ high - 2,
+ high - 1,
+ high,
+ high + 3,
+ ]));
+ let build = |selected: Option<Vec<usize>>| {
+ ArrowReader::build_deletes_row_selection(&meta, &selected,
&deletes).unwrap()
+ };
+ assert_eq!(
+ build(None),
+ RowSelection::from(vec![
+ select(1),
+ skip(1),
+ select(big - 5),
+ skip(4),
+ select(2),
+ skip(1),
+ select(2),
+ ])
+ );
+ assert_eq!(
+ build(Some(vec![0])),
+ RowSelection::from(vec![select(1), skip(1), select(big - 5),
skip(1)])
+ );
+ assert_eq!(
+ build(Some(vec![1])),
+ RowSelection::from(vec![skip(3), select(2), skip(1), select(2)])
+ );
+
+ // Skipping row group 0 lands past 2^32, in the next bitmap.
+ let meta = row_groups(&[(1 << 32) + 1, 4]);
+ let deletes = DeleteVector::new(RoaringTreemap::from_iter([5, high -
1, high, high + 2]));
+ assert_eq!(
+ ArrowReader::build_deletes_row_selection(&meta, &Some(vec![1]),
&deletes).unwrap(),
+ RowSelection::from(vec![select(1), skip(1), select(2)])
+ );
+ }
+
+ /// The selection for `deleted` built one deleted position at a time.
+ fn expected_deletes_row_selection(
+ row_group_sizes: &[u64],
+ selected_row_groups: &Option<Vec<usize>>,
+ deleted: &[u64],
+ ) -> RowSelection {
+ let mut selectors = Vec::new();
+ let mut base = 0;
+ for (idx, &num_rows) in row_group_sizes.iter().enumerate() {
+ let end = base + num_rows;
+ if selected_row_groups
+ .as_ref()
+ .is_none_or(|selected| selected.contains(&idx))
+ {
+ let mut row = base;
+ let first = deleted.partition_point(|&p| p < base);
+ for &pos in deleted[first..].iter().take_while(|&&p| p < end) {
+ selectors.push(RowSelector::select((pos - row) as usize));
+ selectors.push(RowSelector::skip(1));
+ row = pos + 1;
+ }
+ selectors.push(RowSelector::select((end - row) as usize));
+ }
+ base = end;
+ }
+ selectors.into()
+ }
+
+ /// Random row group layouts and selections over the delete vectors the
iterator tests use,
+ /// compared with a selection built one deleted position at a time.
+ #[test]
+ fn test_build_deletes_row_selection_matches_model() {
+ let mut state = 3u64;
+ let mut rand = move || {
+ state ^= state << 13;
+ state ^= state >> 7;
+ state ^= state << 17;
+ state
+ };
+ let schema_descr = get_test_schema_descr();
+ let columns: Vec<_> = schema_descr
+ .columns()
+ .iter()
+ .map(|ptr|
ColumnChunkMetaData::builder(ptr.clone()).build().unwrap())
+ .collect();
+
+ for deletes in mixed_delete_vectors() {
+ let deleted: Vec<u64> = deletes.iter().collect();
+ for _ in 0..8 {
+ // Half the time the file ends at or before a deleted
position, so the deletes
+ // past its end must be ignored.
+ let num_rows = match deleted.len() {
+ n if n > 0 && rand() % 2 == 0 => {
+ deleted[(rand() % n as u64) as
usize].saturating_add(rand() % 2)
+ }
+ _ => deleted.last().map_or(0, |&last| last + 1) + rand() %
100,
+ }
+ .max(1);
+ // Row group boundaries, half of them next to a deleted
position so that they
+ // fall inside runs.
+ let mut cuts: Vec<u64> = (0..rand() % 8)
+ .map(|_| match deleted.len() {
+ n if n > 0 && rand() % 2 == 0 => {
+ (deleted[(rand() % n as u64) as usize] + rand() %
3).saturating_sub(1)
+ }
+ _ => rand() % num_rows,
+ })
+ .filter(|&cut| cut > 0 && cut < num_rows)
+ .collect();
+ cuts.extend([0, num_rows]);
+ cuts.sort_unstable();
+ cuts.dedup();
Review Comment:
Did both in 743ae5389. I dropped `cuts.dedup()` so repeated cuts leave empty
row groups, and added
`test_build_deletes_row_selection_empty_row_group_inside_run`. It has rows 1..5
deleted across `[3, 0, 3]`, with the empty group selected, skipped, and as the
first selected group.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
