Hi all, Eduard suggested on Slack that I bring this to the list for broader review, so here it is.
Spark's vectorized reader calls PositionDeleteIndex.isDeleted(pos) once per row while building the row-id mapping for a batch, in ColumnarBatchUtil.buildRowIdMapping and buildIsDeleted. Positions within a batch are a contiguous ascending range, so every one of those calls repeats the same work: extracting the high and low keys, bounds-checking the bitmap array, and binary searching the container array. None of it is amortized across the batch, even though the whole batch lands in the same one or two containers. PR: https://github.com/apache/iceberg/pull/18027 Issue: https://github.com/apache/iceberg/issues/18026 This change adds one method to PositionDeleteIndex: default void forEachInRange(long posStart, int length, LongConsumer c) The default implementation is the current per-position loop, so this is source- and binary-compatible, and any external implementation keeps working untouched. BitmapPositionDeleteIndex overrides it to resolve the range to at most two underlying 32-bit bitmaps and walk each once. ColumnarBatchUtil uses this path only when the scan has no equality deletes; tables with equality deletes keep the existing loop. The interface addition is the part I would most like opinions on. The alternative I considered was keeping the traversal internal to core, but every approach I considered either exposed RoaringPositionBitmap or gave up the clean fallback for other implementations. PositionDeleteIndex already grows through default methods (merge, forEach, cardinality, serialize), so this seemed like the established pattern rather than a new one -- but I would rather hear that from people who maintain it. I measured this on 8M rows across 4 files, with one column projected and 3 repetitions per configuration in separate JVMs (delete-check CPU samples, async-profiler ctimer): density container current patched reduction 0.5% array 674 79 8.6x 6.1% array 873 94 9.3x 7.0% bitmap 420 113 3.7x 8.0% bitmap 499 142 3.5x 50% bitmap 584 225 2.6x The gain is largest just below the array/bitmap container boundary, which is where the removed work -- a binary search per row -- was most expensive. buildIsDeleted improves more (14.9x-18.9x) because it does not need to fill the gaps between deleted positions. Correctness was checked before performance: count(*), sum(id), and min/max(id) over 7 tables are identical for both jars, equality-delete tables show no regression, and the existing delete tests pass. CI on the PR is green. Two caveats I would rather call out up front: - These are delete-check CPU samples, not end-to-end wall clock. The delete check is 43-54% of scan CPU in my setup, but its share of total query CPU falls to 6.8% and then 2.4% once a GROUP BY is added. The absolute CPU saved does not change; the fraction does. - The run-to-run spread of an identical configuration is 9.7% median on my primary machine, so I do not claim any difference inside that band. The issue lists the rest of the caveats, including the two numbers I withdrew after re-measuring on quieter hardware. The issue has the fuller picture: three CPU microarchitectures, local disk and S3, warm and dropped page cache, task parallelism 1 through 16, a small distributed cluster, and hardware counters used to check the mechanism rather than infer it from timings -- which is how I found out that my first explanation for the cost was wrong. It currently touches spark/v4.2 only, to keep the diff reviewable. ColumnarBatchUtil is byte-identical in v3.5, v4.0, and v4.1, so I will backfill those in a follow-up if the direction looks right. I am happy to change the approach if there is a better one, and I still have the raw profiles, flame graphs, and per-axis charts if any of it would help the review. Thanks, Daehong Jeon
