laskoviymishka commented on code in PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#discussion_r4286596035
##########
crates/iceberg/src/arrow/reader/positional_deletes.rs:
##########
@@ -211,6 +184,73 @@ 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() {
Review Comment:
I'd add a randomized test for `build_deletes_row_selection` next to this
one: random row-group sizes, a random `selected_row_groups` subset and the DVs
from `mixed_delete_vectors`, compared against a per-row oracle that
run-length-encodes the selected groups.
The iterator gets a model test, but this loop was rewritten wholesale and
only has hand-picked cases. The branch I'd least trust to stay correct is a
range carried from a selected row group into a skipped one.
`mixed_delete_vectors` would need to be `pub(crate)` under `cfg(test)` for this.
##########
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,
Review Comment:
This `+ 1` overflows when the last deleted position is `u64::MAX`. In debug
that's a panic; in release it wraps to `(start, 0)`, which breaks the `start <
end` contract the reader relies on.
It isn't a realistic row position, but the treemap can hold it and DVs come
from external blobs, so this shouldn't be able to panic. Either use
`checked_add` here and end the iterator at the edge, or reject positions above
Java's `MAX_POSITION` at decode time and keep a `debug_assert!` here.
##########
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;
Review Comment:
I'd move the 4 vs 8/16/32 comparison from the PR description into this doc
comment, so whoever bumps `roaring` later knows the value was tuned, and on
which workload.
##########
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:
Because `target` only ever moves forward, the `high_bits > hi` early return
and the "already past `lo`" path are only hit by the hand-written test below.
I'd let the model sometimes pick a backward target, and add a treemap with gaps
between bitmaps (high bits `{0, 3, 7}`) to `mixed_delete_vectors` so the loop
that skips empty bitmaps gets exercised. Both paths also assume
`Iter::advance_to` never rewinds, which is better checked by the randomized
test than by reading the code.
##########
crates/iceberg/src/delete_vector.rs:
##########
@@ -227,7 +241,7 @@ fn decode_roaring_directory(mut reader: &[u8]) ->
Result<RoaringTreemap> {
// Ideally, we'd just wrap `roaring::RoaringTreemap`'s iterator,
`roaring::treemap::Iter` here.
// But right now, it does not have a corresponding implementation of
`roaring::bitmap::Iter::advance_to`,
-// which is very handy in ArrowReader::build_deletes_row_selection.
+// which `advance_to` below needs.
Review Comment:
This block is still stale after the edit: roaring-rs#314 has since merged
(April 2025). After this PR, `advance_to` also has no caller inside the crate.
The bigger issue is that `advance_to` went public in #3461 with both #3400
bugs still in it. `skip_to` here already has the three-way `high_bits` vs `hi`
handling that fixes them. We could port that into `advance_to` here so #3400
can close, or do it as an immediate follow-up and reword this comment to say
`advance_to` is only kept for the public API. Which would you rather?
##########
crates/iceberg/src/delete_vector.rs:
##########
@@ -92,6 +92,20 @@ impl DeleteVector {
self.inner.is_empty()
}
+ /// Returns the deleted positions as ascending, non-overlapping half-open
ranges.
+ ///
+ /// Adjacent ranges are not always merged: a run that crosses a 2^32
boundary comes out as
Review Comment:
I don't think 2^32 is the only split. The probe calls `next_range` once, so
if that stops at a 2^16 container boundary, the rest of the run comes back as a
separate range right next to it. I'd just say adjacent ranges may not be merged
and callers shouldn't assume they're maximal. The reader is fine either way
because `RowSelection` merges them.
##########
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:
I'd split this into two tests, e.g. `..._to_missing_later_bitmap` and
`..._below_current_bitmap`, so a failure says which case broke. Since #3400
stays open, I'd also say these are the cases for `skip_to`; as written it reads
as if the issue is fixed.
##########
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)>,
Review Comment:
`pending` and `pending_range` are never both set, because each exit path in
`next()` sets only one. But `skip_to` trims them separately and nothing
enforces that. I'd fold them into one field so the type carries the invariant:
```rust
enum Buffered {
/// Start of the next range.
Pos(u32),
/// A complete range, inclusive end.
Range(u32, u32),
}
```
That also documents the inclusive `u32` end. The `end < lo` check in
`skip_to` depends on it, and the current field doc doesn't say so.
##########
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:
The doc should say this only applies to ranges still buffered in the
iterator. A range already returned by `next()` is the caller's to cut, which
the reader does in its `start < next_row_group_base_idx` arm.
--
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]
