Skip to content

Commit 1820b84

Browse files
committed
Address review: fix advance_to (#3400), randomized reader test
- DeleteVectorIterator::advance_to now handles a target in a missing later bitmap, a target below the current bitmap, and a call before the first next (the cases in #3400), with the same three-way check as skip_to. Dropped the stale comments about roaring-rs#314 and the git dependency. - Randomized test for build_deletes_row_selection: random row group layouts and selections over mixed_delete_vectors, against a selection built one deleted position at a time. - full_range no longer overflows at u64::MAX. - One Buffered enum instead of pending/pending_range. - Model tests also skip backwards, mixed_delete_vectors has gaps between bitmaps, a model test for advance_to, the #3400 cases split per test, and doc updates for ranges, skip_to and RUN_PROBE_LEN.
1 parent 46ff84f commit 1820b84

2 files changed

Lines changed: 347 additions & 122 deletions

File tree

‎crates/iceberg/src/arrow/reader/positional_deletes.rs‎

Lines changed: 91 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -141,7 +141,7 @@ mod tests {
141141

142142
use crate::Runtime;
143143
use crate::arrow::{ArrowReader, ArrowReaderBuilder};
144-
use crate::delete_vector::DeleteVector;
144+
use crate::delete_vector::{DeleteVector, mixed_delete_vectors};
145145
use crate::io::FileIO;
146146
use crate::scan::{FileScanTask, FileScanTaskDeleteFile, FileScanTaskStream};
147147
use crate::spec::{DataContentType, DataFileFormat, NestedField, PrimitiveType, Schema, Type};
@@ -251,6 +251,96 @@ mod tests {
251251
);
252252
}
253253

254+
/// The selection for `deleted` built one deleted position at a time.
255+
fn expected_deletes_row_selection(
256+
row_group_sizes: &[u64],
257+
selected_row_groups: &Option<Vec<usize>>,
258+
deleted: &[u64],
259+
) -> RowSelection {
260+
let mut selectors = Vec::new();
261+
let mut base = 0;
262+
for (idx, &num_rows) in row_group_sizes.iter().enumerate() {
263+
let end = base + num_rows;
264+
if selected_row_groups
265+
.as_ref()
266+
.is_none_or(|selected| selected.contains(&idx))
267+
{
268+
let mut row = base;
269+
let first = deleted.partition_point(|&p| p < base);
270+
for &pos in deleted[first..].iter().take_while(|&&p| p < end) {
271+
selectors.push(RowSelector::select((pos - row) as usize));
272+
selectors.push(RowSelector::skip(1));
273+
row = pos + 1;
274+
}
275+
selectors.push(RowSelector::select((end - row) as usize));
276+
}
277+
base = end;
278+
}
279+
selectors.into()
280+
}
281+
282+
/// Random row group layouts and selections over the delete vectors the iterator tests use,
283+
/// compared with a selection built one deleted position at a time.
284+
#[test]
285+
fn test_build_deletes_row_selection_matches_model() {
286+
let mut state = 3u64;
287+
let mut rand = move || {
288+
state ^= state << 13;
289+
state ^= state >> 7;
290+
state ^= state << 17;
291+
state
292+
};
293+
let schema_descr = get_test_schema_descr();
294+
let columns: Vec<_> = schema_descr
295+
.columns()
296+
.iter()
297+
.map(|ptr| ColumnChunkMetaData::builder(ptr.clone()).build().unwrap())
298+
.collect();
299+
300+
for deletes in mixed_delete_vectors() {
301+
let deleted: Vec<u64> = deletes.iter().collect();
302+
let num_rows = deleted.last().map_or(0, |&last| last + 1) + rand() % 100 + 1;
303+
for _ in 0..8 {
304+
// Row group boundaries, half of them next to a deleted position so that they
305+
// fall inside runs.
306+
let mut cuts: Vec<u64> = (0..rand() % 8)
307+
.map(|_| match deleted.len() {
308+
n if n > 0 && rand() % 2 == 0 => {
309+
(deleted[(rand() % n as u64) as usize] + rand() % 3).saturating_sub(1)
310+
}
311+
_ => rand() % num_rows,
312+
})
313+
.filter(|&cut| cut > 0 && cut < num_rows)
314+
.collect();
315+
cuts.extend([0, num_rows]);
316+
cuts.sort_unstable();
317+
cuts.dedup();
318+
let sizes: Vec<u64> = cuts.windows(2).map(|w| w[1] - w[0]).collect();
319+
let row_groups: Vec<RowGroupMetaData> = sizes
320+
.iter()
321+
.enumerate()
322+
.map(|(i, &n)| {
323+
build_test_row_group_meta(
324+
schema_descr.clone(),
325+
columns.clone(),
326+
n as i64,
327+
i as i16,
328+
)
329+
})
330+
.collect();
331+
let selected = (rand() % 4 != 0)
332+
.then(|| (0..sizes.len()).filter(|_| rand() % 2 == 0).collect());
333+
334+
assert_eq!(
335+
ArrowReader::build_deletes_row_selection(&row_groups, &selected, &deletes)
336+
.unwrap(),
337+
expected_deletes_row_selection(&sizes, &selected, &deleted),
338+
"row groups {sizes:?}, selected {selected:?}"
339+
);
340+
}
341+
}
342+
}
343+
254344
#[test]
255345
fn test_build_deletes_row_selection() {
256346
let schema_descr = get_test_schema_descr();

0 commit comments

Comments
 (0)