You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@iceberg.apache.org by "JeonDaehong (via GitHub)" <gi...@apache.org> on 2026/10/14 14:29:30 UTC
[PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
JeonDaehong opened a new pull request, #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454
## Which issue does this PR close?
- Related to #3400.
## What changes are included in this PR?
`build_deletes_row_selection` walks the delete vector one position at a time, so a run of deleted rows costs one iteration per row. On files with many contiguous deletes this is a large part of the read.
This builds the selection from deleted ranges instead (`DeleteVector::ranges`):
- Short runs are still walked with `next`. A run switches to roaring's `next_range` after 4 consecutive positions, because `next_range` binary-searches the rest of an array container on each call and is slower than `next` when most runs are single rows.
- Row groups that are not selected are skipped with `skip_to` instead of walking their deletes.
- `DeleteVectorIterator` and its `advance_to` are no longer used and are removed. That is the function #3400 is about; the new skip logic is tested for both cases there (I left a note on the issue).
Results are identical to `main` (checked in the benchmark below and in the tests).
<details>
<summary>Benchmark (c7i.2xlarge, release, 7 runs alternating old/new, median)</summary>
Reading a 20M-row Parquet file (4 numeric columns, 20 row groups, local disk), selection build + read:
| deletes | main | this PR |
|---|---|---|
| 1000 large runs, 50% | 190 ms | 125 ms |
| runs of 100, 50% | 223 ms | 159 ms |
| runs of 20, 50% | 279 ms | 224 ms |
| 99% deleted | 260 ms | 135 ms |
| 5% scattered single rows | 270 ms | 271 ms |
| pairs, 10% | 270 ms | 269 ms |
| 0.01% | 163 ms | 163 ms |
The last three are within run-to-run noise. Selection build alone on 100M rows: 329 ms β 0.05 ms (large runs), 689 ms β 59 ms (99%), 172 ms β 174 ms (5% scattered, ranges overlap). The share of the build in a read is smaller with more or wider columns or remote storage.
I also tried switching after 8, 16 and 32 positions; 4 was best for runs and showed no slowdown on scattered deletes.
</details>
I did the same kind of change for Java's DV iteration in apache/iceberg#18027.
## Are these changes tested?
Yes. New tests in `delete_vector.rs` compare `ranges()` and `skip_to` against a reference model on mixed sets (single rows, pairs, runs around the switch point, runs across 2^16 and 2^32), plus the two cases from #3400. A new row selection test crosses 2^32 with and without row group selection. Existing positional delete tests pass unchanged. Breaking `skip_to` or dropping a buffered run in four different ways makes the new tests fail. `cargo test -p iceberg --lib`, clippy and fmt are clean.
## AI Disclosure
I used Claude Code to write the change, the tests and the benchmark, and to run them. I reviewed it before opening the PR.
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6293515137
I'm taking a quick pass this morning.
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "laskoviymishka (via GitHub)" <gi...@apache.org>.
laskoviymishka commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6302170569
@JeonDaehong - agree with @mbutrovich , let's close those test changes and ready to merge
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6232920352
Thanks @akshat-lakhera for checking this against the roaring source. Addressed in 0bc58a09b:
1. Added `test_ranges_join_runs_across_2_16`, which checks that a run across 2^16 comes back as one range, both when `next_range` picks it up and when the run starts within the positions walked first. I also changed the `ranges()` doc to say a run is split at each 2^32 boundary.
2. The randomized reader test now ends the file at or just after a deleted position half the time, so deletes past the end of the file are covered with the last row group both selected and skipped.
3. Moved the `u64::MAX` note to `ranges()`.
4. Agreed. I'll add the benchmark as a follow-up.
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
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:
Could we use a seeded `StdRng` here instead of a hand-written xorshift? `rand` is already a dev-dependency of the crate ([`Cargo.toml`](https://github.com/apache/iceberg-rust/blob/0bc58a09bc21821e4e15e75593616d3597c4a22b/crates/iceberg/Cargo.toml#L94)). It would replace this closure and its copies in `test_ranges_skip_to_matches_model`, `test_advance_to_matches_model` and `test_build_deletes_row_selection_matches_model`. The modulo arithmetic at the call sites would also become ranges that say what they mean:
```rust
let mut rng = StdRng::seed_from_u64(7);
let run = match rng.random_range(0..5) {
0 => 1,
1 => 2,
// one past the probe length: the rest comes from `next_range`
2 => u64::from(RUN_PROBE_LEN) + 1,
3 => rng.random_range(1..=40),
_ => rng.random_range(1..=70_000),
};
```
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "laskoviymishka (via GitHub)" <gi...@apache.org>.
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6209425148
Thanks @laskoviymishka. Addressed everything in 1820b8454, including the `advance_to` fix, so this now closes #3400. `delete_vector` and `positional_deletes` tests, clippy, fmt and `cargo doc` with `-D warnings` pass.
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6195259898
Rebased on #3461, which made `delete_vector` public. This PR now keeps `DeleteVector::iter`, `DeleteVectorIterator` and `advance_to` as they are and adds the range iterator as crate-private, so `public-api.txt` is unchanged. `delete_vector` and `positional_deletes` tests, clippy, fmt and `cargo doc` with `-D warnings` pass.
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6170936070
@laskoviymishka @mbutrovich could you take a look when you have time? This builds the delete row selection from deleted ranges instead of per position: reads with contiguous deletes get 20-48% faster, scattered deletes are unchanged (numbers in the description). cc @Baunsgaard, since #2292 looked at range handling for delete vectors.
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6293206424
@laskoviymishka gentle ping. Since your approval I pushed 1820b8454 (your review items) and 0bc58a09b (akshat-lakhera's extra tests and docs). CI is green and it's mergeable. Could you take another look and merge if it still looks good?
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "laskoviymishka (via GitHub)" <gi...@apache.org>.
laskoviymishka merged PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "JeonDaehong (via GitHub)" <gi...@apache.org>.
JeonDaehong commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6314155572
@mbutrovich @laskoviymishka addressed both in 743ae5389. Thanks for the review.
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] perf(arrow): build the delete row selection from deleted ranges [iceberg-rust]
Posted by "laskoviymishka (via GitHub)" <gi...@apache.org>.
laskoviymishka commented on PR #3454:
URL: https://github.com/apache/iceberg-rust/pull/3454#issuecomment-6373384686
it's time toπ¬οΈ β΅ !
--
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: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org