Based on your suggestion, I implemented BatchIterator and benchmarked it against several approaches, including the current implementation.
I compared six implementations under the same JMH environment, using a 5,000-row batch over the full 65,536-position chunk at each target density. I also ran the containers through serialize() / deserialize() to match the structure used in the actual read path. The results are in microseconds per batch; lower is better. implementation sparse 0.5% medium 5% dense 12% current (isDeleted per row) 64.99 80.22 19.76 forAllInRange + RelativeRangeConsumer 0.49 1.91 3.07 forEachInRange + gap fill (this PR) 0.45 1.87 4.16 BatchIterator 0.63 2.79 5.92 BatchIterator performed slightly worse than the current PR implementation. I haven't profiled the exact cause yet, but one possible factor is that nextBatch(int[]) returns deleted positions into a buffer, requiring a second pass to build the row-ID mapping. Another difference is that BatchIterator does not currently provide a bulk callback for contiguous ranges with no deletes. forAllInRange can handle these ranges with acceptAllAbsent(from, to), effectively skipping them in O(1). In the run-container case, this alone resulted in roughly a 2.7x difference. One approach I haven't tested yet is keeping a single iterator alive across batches instead of creating a new one for each batch. This could amortize container lookup and reduce per-batch allocation. I can benchmark this as well, although given the current 5,000-row batch size, I don't expect a significant difference. >From an API perspective, I also think a stateful iterator would be a larger change to PositionDeleteIndex, since it introduces a new API and lifecycle. The current PR instead adds a default method while keeping the existing loop as the default implementation. For now, I've chosen the approach that provides a *measured performance improvement while keeping the API change minimal*. If the community feels the iterator-based approach is a better fit, I'm happy to investigate the persistent-iterator variant further.
