JeonDaehong opened a new pull request, #18027: URL: https://github.com/apache/iceberg/pull/18027
`ColumnarBatchUtil.buildRowIdMapping` and `buildIsDeleted` call `PositionDeleteIndex.isDeleted(pos)` once for every row in a batch. Because positions within a batch form a contiguous ascending range, each call repeats redundant work: extracting high/low keys, checking bitmap array bounds, and performing binary searches on the container array. None of this is amortized across the batch, even though consecutive calls target the same one or two containers. This PR introduces `PositionDeleteIndex.forEachInRange(posStart, length, consumer)`, which efficiently traverses deleted positions within a given range in ascending order. The default implementation falls back to the existing per-position loop, while `BitmapPositionDeleteIndex` overrides it to resolve the range to at most two underlying 32-bit bitmaps and walk each once. `ColumnarBatchUtil` now leverages this path when no equality deletes are present; tables with equality deletes retain the previous behavior. ### Performance Measured on 8M rows across 4 files (single-column projection, 3 runs per configuration in separate JVMs, sampled via async-profiler `ctimer` for delete-check CPU usage): | delete 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 largest speedup occurs just below the array/bitmap threshold, where eliminating per-row binary searches provides the biggest relief. Notably, `buildIsDeleted` sees a **14.9x–18.9x** improvement since it avoids filling gaps between deleted positions. ### Correctness & Scope - **Correctness verified:** `count(*)`, `sum(id)`, and `min/max(id)` results across 7 test tables match the baseline identically. Tables with equality deletes show zero performance regression. - **Scope:** This PR targets `spark/v4.2` first to keep the diff concise and reviewable. Since `ColumnarBatchUtil` is byte-identical in `v3.5`, `v4.0`, and `v4.1`, I will follow up with backports once the overall design is approved. For additional benchmarks—including cross-microarchitecture validation, local vs. S3 performance, cold/warm cache behavior, scaling from 1–16 parallel tasks, cluster runs, and hardware counters—along with edge-case performance bounds, please refer to #18026. Closes #18026 -- 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]
