apache / apache/lucene

Tighten left-bound of MemoryAccountingBitsetCollectorManager.Result#bitSet

Open
#16,649 1 comment 0 reactions 0 assignees View on GitHub
type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.