mbutrovich commented on code in PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#discussion_r4326434048
##########
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:
What do you think about using a seeded `rand` generator here instead of the
hand-written xorshift? The same closure is repeated in
`test_ranges_skip_to_matches_model`, `test_advance_to_matches_model` and
`test_build_deletes_row_selection_matches_model`. `rand` is already a
dev-dependency of the crate
([`Cargo.toml`](https://github.com/apache/iceberg-rust/blob/0bc58a09bc21821e4e15e75593616d3597c4a22b/crates/iceberg/Cargo.toml#L94)),
so `StdRng::seed_from_u64(seed)` with `random_range` and `random_bool` would
replace the four copies. It would also make reads like `rand() % 2 == 0` say
what they mean.
##########
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:
Should the model also generate row groups with zero rows? Parquet allows
them, and they hit the arms that cut or carry a range at the row group
boundary. Removing `cuts.dedup()` lets repeated cuts produce empty row groups,
but with this seed that gives only 3 empty row groups across the 344 cases. A
hand-written case may be clearer: an empty row group inside a deleted run, once
selected and once skipped.
--
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]
