JeonDaehong commented on code in PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#discussion_r4291509929
##########
crates/iceberg/src/delete_vector.rs:
##########
@@ -294,6 +308,128 @@ impl DeleteVectorIterator<'_> {
}
}
+/// Number of consecutive positions [`DeleteVectorRanges`] walks one by one
before it asks the
+/// bitmap for the rest of the run.
+///
+/// `roaring`'s `next_range` binary-searches the rest of an array container on
every call, which
+/// costs more than `next` when most runs are a single position, so it only
pays off for long
+/// runs.
+const RUN_PROBE_LEN: u32 = 4;
+
+/// Iterator over a [`DeleteVector`]'s deleted positions as half-open ranges,
see
+/// [`DeleteVector::ranges`].
+pub(crate) struct DeleteVectorRanges<'a> {
+ bitmaps: BitmapIter<'a>,
+ /// High 32 bits of the positions in `bitmap_iter`.
+ high_bits: u32,
+ bitmap_iter: Option<Iter<'a>>,
+ /// A position already taken from `bitmap_iter` that starts the next range.
+ pending: Option<u32>,
+ /// A complete range already taken from `bitmap_iter`, returned next.
+ pending_range: Option<(u32, u32)>,
+}
+
+impl DeleteVectorRanges<'_> {
+ fn full_range(&self, start: u32, end_inclusive: u32) -> (u64, u64) {
+ let base = u64::from(self.high_bits) << 32;
+ (
+ base | u64::from(start),
+ (base | u64::from(end_inclusive)) + 1,
+ )
+ }
+
+ /// Skips every deleted position below `pos`. A range that starts below
`pos` and ends after
Review Comment:
Added that to the doc.
##########
crates/iceberg/src/delete_vector.rs:
##########
@@ -320,6 +456,139 @@ pub(crate) fn frame_dv_blob(vector: &[u8]) -> Vec<u8> {
mod tests {
use super::*;
+ /// Deterministic pseudo-random sets mixing single positions, short and
long runs, and runs
+ /// across 2^16 and 2^32 boundaries.
+ 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
+ };
+
+ let mut vectors = vec![DeleteVector::default()];
+ for case in 0..40u64 {
+ let mut dv = DeleteVector::default();
+ let base = if case % 4 == 0 { (1u64 << 32) - 40 } else { 0 };
+ let mut pos = base + rand() % 50;
+ for _ in 0..(rand() % 60) {
+ let run = match rand() % 5 {
+ 0 => 1,
+ 1 => 2,
+ // one past the probe length: the rest comes from
`next_range`
+ 2 => u64::from(RUN_PROBE_LEN) + 1,
+ 3 => 1 + rand() % 40,
+ _ => 1 + rand() % 70_000,
+ };
+ dv.inner.insert_range(pos..pos + run);
+ pos += run + 1 + rand() % 30;
+ }
+ vectors.push(dv);
+ }
+ let mut boundaries = DeleteVector::default();
+ boundaries.inner.insert_range((1 << 16) - 3..(1 << 16) + 3);
+ boundaries
+ .inner
+ .insert_range((1 << 32) - 20..(1 << 32) + 20);
+ boundaries.inner.insert((2 << 32) + 7);
+ vectors.push(boundaries);
+ vectors
+ }
+
+ #[test]
+ fn test_ranges_cover_exactly_the_deleted_positions() {
+ for dv in mixed_delete_vectors() {
+ let positions: Vec<u64> = dv.iter().collect();
+ let mut expanded = Vec::new();
+ let mut last_end = None;
+ for (start, end) in dv.ranges() {
+ assert!(start < end, "empty range {start}..{end}");
+ assert!(
+ last_end.is_none_or(|last| last <= start),
+ "ranges out of order"
+ );
+ last_end = Some(end);
+ expanded.extend(start..end);
+ }
+ assert_eq!(expanded, positions);
+ }
+ }
+
+ #[test]
+ fn test_ranges_skip_to_matches_model() {
+ let mut state = 7u64;
+ let mut rand = move || {
+ state ^= state << 13;
+ state ^= state >> 7;
+ state ^= state << 17;
+ state
+ };
+
+ for dv in mixed_delete_vectors() {
+ let mut remaining: std::collections::BTreeSet<u64> =
dv.iter().collect();
+ let max = remaining.last().copied().unwrap_or(0) + 10;
+ let mut ranges = dv.ranges();
+ let mut target = 0u64;
+ loop {
+ if rand() % 3 == 0 {
+ target =
target.max(remaining.first().copied().unwrap_or(max));
Review Comment:
The model now also skips backwards (near the current position and anywhere
below it), and `mixed_delete_vectors` has a DV with high bits {0, 3, 7}.
Removing the `Buffered::Pos` trim in `skip_to` fails the model test.
##########
crates/iceberg/src/delete_vector.rs:
##########
@@ -320,6 +456,139 @@ pub(crate) fn frame_dv_blob(vector: &[u8]) -> Vec<u8> {
mod tests {
use super::*;
+ /// Deterministic pseudo-random sets mixing single positions, short and
long runs, and runs
+ /// across 2^16 and 2^32 boundaries.
+ 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
+ };
+
+ let mut vectors = vec![DeleteVector::default()];
+ for case in 0..40u64 {
+ let mut dv = DeleteVector::default();
+ let base = if case % 4 == 0 { (1u64 << 32) - 40 } else { 0 };
+ let mut pos = base + rand() % 50;
+ for _ in 0..(rand() % 60) {
+ let run = match rand() % 5 {
+ 0 => 1,
+ 1 => 2,
+ // one past the probe length: the rest comes from
`next_range`
+ 2 => u64::from(RUN_PROBE_LEN) + 1,
+ 3 => 1 + rand() % 40,
+ _ => 1 + rand() % 70_000,
+ };
+ dv.inner.insert_range(pos..pos + run);
+ pos += run + 1 + rand() % 30;
+ }
+ vectors.push(dv);
+ }
+ let mut boundaries = DeleteVector::default();
+ boundaries.inner.insert_range((1 << 16) - 3..(1 << 16) + 3);
+ boundaries
+ .inner
+ .insert_range((1 << 32) - 20..(1 << 32) + 20);
+ boundaries.inner.insert((2 << 32) + 7);
+ vectors.push(boundaries);
+ vectors
+ }
+
+ #[test]
+ fn test_ranges_cover_exactly_the_deleted_positions() {
+ for dv in mixed_delete_vectors() {
+ let positions: Vec<u64> = dv.iter().collect();
+ let mut expanded = Vec::new();
+ let mut last_end = None;
+ for (start, end) in dv.ranges() {
+ assert!(start < end, "empty range {start}..{end}");
+ assert!(
+ last_end.is_none_or(|last| last <= start),
+ "ranges out of order"
+ );
+ last_end = Some(end);
+ expanded.extend(start..end);
+ }
+ assert_eq!(expanded, positions);
+ }
+ }
+
+ #[test]
+ fn test_ranges_skip_to_matches_model() {
+ let mut state = 7u64;
+ let mut rand = move || {
+ state ^= state << 13;
+ state ^= state >> 7;
+ state ^= state << 17;
+ state
+ };
+
+ for dv in mixed_delete_vectors() {
+ let mut remaining: std::collections::BTreeSet<u64> =
dv.iter().collect();
+ let max = remaining.last().copied().unwrap_or(0) + 10;
+ let mut ranges = dv.ranges();
+ let mut target = 0u64;
+ loop {
+ if rand() % 3 == 0 {
+ target =
target.max(remaining.first().copied().unwrap_or(max));
+ target += rand() % 200;
+ ranges.skip_to(target);
+ remaining.retain(|&p| p >= target);
+ continue;
+ }
+ match ranges.next() {
+ Some((start, end)) => {
+ assert_eq!(Some(start), remaining.first().copied());
+ for p in start..end {
+ assert!(remaining.remove(&p), "{p} returned but
not deleted");
+ }
+ target = target.max(end);
+ }
+ None => {
+ assert!(remaining.is_empty(), "missed {remaining:?}");
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ #[test]
+ fn test_ranges_skip_to_inside_buffered_run() {
+ // After a run of exactly RUN_PROBE_LEN + 1, the following run is
already buffered.
+ let probe = u64::from(RUN_PROBE_LEN);
+ let mut dv = DeleteVector::default();
+ dv.inner.insert_range(0..probe + 1);
+ dv.inner.insert_range(probe + 3..probe + 13);
+ let mut ranges = dv.ranges();
+ assert_eq!(ranges.next(), Some((0, probe + 1)));
+ ranges.skip_to(probe + 8);
+ assert_eq!(ranges.next(), Some((probe + 8, probe + 13)));
+ assert_eq!(ranges.next(), None);
+ }
+
+ // The two cases from https://github.com/apache/iceberg-rust/issues/3400.
Review Comment:
Split into `test_ranges_skip_to_missing_later_bitmap` and
`test_ranges_skip_to_below_current_bitmap`, with the matching `advance_to`
tests next to them.
--
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]
