JeonDaehong commented on code in PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#discussion_r4291508902
##########
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:
Added `test_build_deletes_row_selection_matches_model`: random row-group
cuts (half placed next to a deleted position so they land inside runs), a
random `selected_row_groups` subset or `None`, over every DV from
`mixed_delete_vectors` (now `pub(crate)` under `cfg(test)`), compared with a
selection built one deleted position at a time. Dropping the "range continues
into the next row group" break, or skipping one row too far in a skipped group,
makes it fail.
##########
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:
Agreed, reworded to say adjacent ranges may not be merged and callers should
not assume a range is maximal.
##########
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:
Ported it here, so this now closes #3400. `advance_to` uses the same
three-way check as `skip_to`, which also fixes the "before the first `next()`"
case from the issue. Removed the stale roaring-rs#314 and git-dependency notes.
Each #3400 case has its own `advance_to` test, plus a model test like the one
for `skip_to`.
##########
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:
Moved it into the doc comment, with the roaring version and the workloads.
##########
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:
Done, `buffered: Option<Buffered>` with `Pos(u32)` and `Range(u32, u32)`
(inclusive end, documented on the variant).
##########
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:
Fixed with `saturating_add`: a run ending at `u64::MAX` ends the range at
`u64::MAX`, and a range holding only `u64::MAX` ends the iterator, since that
position is past any row. `test_ranges_end_at_u64_max` covers both.
--
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]
