[core] Build deletion-vector row ranges from roaring runs #1146

Search before asking

• I searched in the issues and found nothing similar.

Motivation

dv_to_non_deleted_ranges (data_file_reader.rs) and non_deleted_local_ranges (data_evolution_reader.rs) walk the deletion vector one deleted row at a time, and DeletionVector::iter() first copies every position into a Vec<u64>. So a DV that deletes one contiguous block costs as much as one that deletes the same number of scattered rows.

Reading a 4M-row parquet file (one int column) with a DV, c7i.4xlarge, median of 9 reads, 3 rounds alternating main and the change:

The every-10th-row gap went away when I switched old/new inside one binary with an env var (35.1 vs 35.4 ms over 4 rounds, ranges overlap), so I think it's code layout between the two builds, not this change.

Solution

roaring 0.11 has Iter::next_range, so a run can be taken one container at a time. Using only next_range made scattered deletes about 6x slower in the range-building step, so short runs are still walked with next and only runs longer than 4 switch to next_range. iceberg-rust does the same in apache/iceberg-rust#3454.

The output ranges are the same as before (checked against the current code on 2000 random bitmaps).

Anything else?

The comment on DeletionVector::iter() says roaring has no advance_to, but 0.11 has it. Nothing calls advance_to on DeletionVectorIterator today, so the Vec copy could go too, but that changes a public type, so I'd leave it out of this one.

Willingness to contribute

• I'm willing to submit a PR!