Tighten left-bound of MemoryAccountingBitsetCollectorManager.Result#bitSet
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
Follow up to #16452,which tightened the right bound of MemoryAccountingBitsetCollectorManager.Result#bitSet to highestMatchedDoc + 1.Left bound is still 0 so for selective queries whose matches sit deep in the index, the result bitset still allocates a leading zero run of (0, lowestMatchedDoc). On large indices this is dominant remaining source of overallocation
Suggested by @gaobinlong in (https://github.com/apache/lucene/pull/16452#discussion_r3793553053). Deferred from that PR because it involves a small API shape change to Result rather than a pure bug fix.
Proposed design:
Add int docBase to the Result record so bit index i of bitSet maps to absolute doc id i + docBase. Expose a helper iterator() that returns a fresh DocBaseBitSetIterator per call, so the result stays re iterable:
java
/** @lucene.experimental */
public record Result(FixedBitSet bitSet, int docBase, long totalBytesUsed) {
/** Fresh iterator over absolute doc ids; safe to call multiple times. */
public DocBaseBitSetIterator iterator() {
return new DocBaseBitSetIterator(bitSet, bitSet.cardinality(), docBase);
}
}
In reduce() compute lowestMatched across collectors (new getLowestSetBit() on the collector, mirror of getHighestSetBit()) set docBase = lowestMatched & ~63 (multiple-of-64 invariant), allocate FixedBitSet(highestMatched - docBase + 1) or range each collector's bits into it at the right offset.
Empty result case: length-1 bitset with docBase = 0 preserves the #16452 fix so nextSetBit(0) and iterator().nextDoc() return NO_MORE_DOCS safely.
I followed the existing [DocBaseBitSetIterator](https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/util/DocBaseBitSetIterator.java) precedent like BitSetIterator but has a doc base in order to avoid storing previous 0s, exactly this problem. Same (FixedBitSet, int docBase) shape same multiple-of-64 constraint, already used in production by BKD reads (bkd/DocIdsWriter.java#readBitSetIterator).
Contributor guide
Research direction
Start with MemoryAccountingBitsetCollectorManager.Result and reduce(), then read DocBaseBitSetIterator and the BKD precedent in bkd/DocIdsWriter.java#readBitSetIterator. Done means Result includes docBase and a reusable iterator over absolute document IDs, selective results avoid the leading zero allocation, and empty results retain the stated safe behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend, search
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 68/100