mfellner opened a new issue, #3400:
URL: https://github.com/apache/iceberg-rust/issues/3400
Related to #2411 (v3 tracking).
Related to #1806, which fixes the stale cached delete in
`build_deletes_row_selection`. The cases below are not covered by that fix.
## Apache Iceberg Rust version
main at a76678363. The `advance_to` body is identical in v0.10.1 (compared
the two tagged sources).
## Describe the bug
`DeleteVectorIterator::advance_to` (`crates/iceberg/src/delete_vector.rs`,
lines 256-276) splits the target into a high 32-bit bucket and a low 32-bit
offset. It mishandles two cases that become reachable once positions reach 2^32:
1. The target is in a later bucket, but the outer bitmap iterator is
exhausted (lines 264-267). The function returns without clearing the current
bucket, so positions below the target are still yielded.
2. The target's bucket is lower than the current bucket. The low 32 bits of
the target are applied to the current, higher bucket (line 275), so valid
positions in that bucket are dropped.
A latent third case: calling `advance_to` before the first `next()` does
nothing (lines 260-262), so positions below the target are yielded.
`build_deletes_row_selection` always calls `next()` first
(`crates/iceberg/src/arrow/reader/positional_deletes.rs`, line 44), so it does
not hit this today.
Effects through `ArrowReader::build_deletes_row_selection`:
- Case 1, with a skipped row group crossing 2^32 followed by a selected row
group: the call does not return. The hang is reproduced (see below). The
mechanism is from code reading only: the stale cached delete stays below the
selected row group's base, and the `'chunks` loop neither selects nor skips, so
it does not advance.
- Case 2: the returned `RowSelection` omits a delete (reproduced below).
Both need positions of at least 2^32, which requires a data file with at
least 2^32 rows. The spec's deletion vector section states that deletion
vectors support positive 64-bit positions.
## To Reproduce
On a checkout of main at a76678363, append the two test modules below to
`crates/iceberg/src/delete_vector.rs` and
`crates/iceberg/src/arrow/reader/positional_deletes.rs` (no other source
changes), then run:
```
cargo test --offline -p iceberg --lib repro_advance_to
```
Result on main: `0 passed; 5 failed`, finished in 10.01s. The row-selection
tests run on a worker thread with a 10 second receive timeout, so the hang
fails the test instead of blocking the run. In the failures below, "left" is
the actual result.
Failures:
-
`delete_vector::repro_advance_to::advance_to_past_last_bucket_leaves_no_stale_positions`:
left `[7]`, right `[]`
-
`delete_vector::repro_advance_to::advance_to_lower_target_keeps_later_positions_in_current_bucket`:
left `[]`, right `[4294967316]`
-
`delete_vector::repro_advance_to::advance_to_on_fresh_iterator_skips_positions_below_target`:
left `[5, 200]`, right `[200]`
-
`arrow::reader::positional_deletes::repro_advance_to::skipped_row_group_crossing_2_32_then_selected_row_group_terminates`:
`build_deletes_row_selection did not terminate within 10s`
-
`arrow::reader::positional_deletes::repro_advance_to::skipped_row_group_ending_at_50_keeps_delete_in_bucket_1`:
left `[select(4294967256), skip(1), select(89)]`, right `[select(4294967256),
skip(1), select(9), skip(1), select(79)]`
As a control, a skipped row group followed by a selected row group with
deletes below 2^32 (positions 3, 7 and 60, row groups of 50 and 50 rows,
selected `[1]`) returns the expected selection on main.
The test bodies:
<details>
<summary>Test code (crates/iceberg/src/delete_vector.rs)</summary>
```rust
#[cfg(test)]
mod repro_advance_to {
use super::*;
const BUCKET_1: u64 = 1 << 32;
#[test]
fn advance_to_past_last_bucket_leaves_no_stale_positions() {
let mut dv = DeleteVector::default();
dv.insert(5);
dv.insert(7);
let mut it = dv.iter();
assert_eq!(it.next(), Some(5));
it.advance_to(BUCKET_1 + 10);
assert_eq!(it.collect::<Vec<u64>>(), Vec::<u64>::new());
}
#[test]
fn advance_to_lower_target_keeps_later_positions_in_current_bucket() {
let mut dv = DeleteVector::default();
dv.insert(BUCKET_1 + 10);
dv.insert(BUCKET_1 + 20);
let mut it = dv.iter();
assert_eq!(it.next(), Some(BUCKET_1 + 10));
it.advance_to(50);
assert_eq!(it.collect::<Vec<u64>>(), vec![BUCKET_1 + 20]);
}
#[test]
fn advance_to_on_fresh_iterator_skips_positions_below_target() {
let mut dv = DeleteVector::default();
dv.insert(5);
dv.insert(200);
let mut it = dv.iter();
it.advance_to(100);
assert_eq!(it.collect::<Vec<u64>>(), vec![200]);
}
}
```
</details>
<details>
<summary>Test code
(crates/iceberg/src/arrow/reader/positional_deletes.rs)</summary>
```rust
#[cfg(test)]
mod repro_advance_to {
use std::sync::Arc;
use std::sync::mpsc;
use std::time::Duration;
use parquet::arrow::arrow_reader::{RowSelection, RowSelector};
use parquet::file::metadata::{ColumnChunkMetaData, RowGroupMetaData};
use parquet::schema::types::{SchemaDescPtr, SchemaDescriptor, Type as
SchemaType};
use super::ArrowReader;
use crate::delete_vector::DeleteVector;
const BUCKET_1: i64 = 1 << 32;
fn schema_descr() -> SchemaDescPtr {
let field = SchemaType::primitive_type_builder("a",
parquet::basic::Type::INT32)
.build()
.unwrap();
let schema = SchemaType::group_type_builder("schema")
.with_fields(vec![Arc::new(field)])
.build()
.unwrap();
Arc::new(SchemaDescriptor::new(Arc::new(schema)))
}
fn row_group(schema: &SchemaDescPtr, num_rows: i64, ordinal: i16) ->
RowGroupMetaData {
let columns: Vec<ColumnChunkMetaData> = schema
.columns()
.iter()
.map(|c|
ColumnChunkMetaData::builder(c.clone()).build().unwrap())
.collect();
RowGroupMetaData::builder(schema.clone())
.set_num_rows(num_rows)
.set_column_metadata(columns)
.set_ordinal(ordinal)
.build()
.unwrap()
}
// Runs `build_deletes_row_selection` on a worker thread so a
non-terminating loop fails the test
// instead of hanging the test binary.
fn build_selection_bounded(
row_groups: Vec<RowGroupMetaData>,
selected_row_groups: Option<Vec<usize>>,
deletes: DeleteVector,
) -> Option<RowSelection> {
let (tx, rx) = mpsc::channel();
std::thread::spawn(move || {
let selection = ArrowReader::build_deletes_row_selection(
&row_groups,
&selected_row_groups,
&deletes,
)
.unwrap();
let _ = tx.send(selection);
});
rx.recv_timeout(Duration::from_secs(10)).ok()
}
fn deletes_of(positions: &[i64]) -> DeleteVector {
let mut dv = DeleteVector::default();
for &pos in positions {
dv.insert(pos as u64);
}
dv
}
#[test]
fn skipped_row_group_crossing_2_32_then_selected_row_group_terminates() {
let schema = schema_descr();
let row_groups = vec![
row_group(&schema, BUCKET_1 + 10, 0),
row_group(&schema, 10, 1),
];
let selection = build_selection_bounded(
row_groups,
Some(vec![1]),
deletes_of(&[3, 7]),
)
.expect("build_deletes_row_selection did not terminate within 10s");
assert_eq!(
selection,
RowSelection::from(vec![RowSelector::select(10)])
);
}
#[test]
fn skipped_row_group_ending_at_50_keeps_delete_in_bucket_1() {
let schema = schema_descr();
let row_groups = vec![
row_group(&schema, 50, 0),
row_group(&schema, BUCKET_1 + 50, 1),
];
let selection = build_selection_bounded(
row_groups,
Some(vec![1]),
deletes_of(&[BUCKET_1 + 10, BUCKET_1 + 20]),
)
.expect("build_deletes_row_selection did not terminate within 10s");
assert_eq!(
selection,
RowSelection::from(vec![
RowSelector::select((BUCKET_1 - 40) as usize),
RowSelector::skip(1),
RowSelector::select(9),
RowSelector::skip(1),
RowSelector::select(79),
])
);
}
}
```
</details>
## Upstream roaring
The comment at `delete_vector.rs` lines 213-218 says the roaring treemap
iterator has no `advance_to`, and that roaring-rs PR #314 is open. PR #314 was
merged on 2025-04-03, and roaring 0.11.4 (the version in `Cargo.lock`) provides
`treemap::Iter::advance_to`. The note at lines 220-222 about a temporary git
reference is also out of date: `Cargo.toml` depends on `roaring = "0.11"` from
crates.io.
Using `RoaringTreemap::iter()` from roaring 0.11.4 with the same inputs, the
case 1 input gives the expected result. For the case 2 input (after `next()`
returns 4294967306, `advance_to(50)` yields `[]` instead of `[4294967316]`).
Replacing the hand-written method with the upstream one would therefore not by
itself fix case 2.
## Expected behavior
After `advance_to(target)`, the iterator yields only positions at or above
`target`, including when the target is in a later 2^32 bucket.
`build_deletes_row_selection` returns a `RowSelection` that matches the deletes
for any row-group layout, including row groups that cross 2^32, and returns in
all cases.
## Willingness to contribute
I would be willing to contribute a fix with guidance from the Iceberg
community (any contribution would be agent-assisted and I would disclose that).
Found during an agent-assisted audit of v3 support (see #2411). The
reproduction above was run against main at a76678363.
--
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]
