Support for DocIdSetBuilder with (min,max) docId

[jainankitk]

Description

Currently, we are using maxDoc >>> 7 as the default threshold before upgrading to BitSet. I am wondering if there is more optimal way of determining the right threshold.

The memory cost of FixedBitSet is always known, and we can get the selectivity from (# docs in buffer)/(maxDoc in buffer) so far. If the selectivity is high, consider upgrading to FixedBitSet earlier, else should delay the upgrade.

[jainankitk]

Thinking bit more, this selectivity approach won't work as the docId arrive out of order and only sorted during DocIdSetIterator#build. Although, with the introduction of LeafReaderContextPartition, passing context.reader().maxDoc() into the DocIdSetIterator is not correct. Should provide both minDocId & maxDocId for:

• Correctly computing the DocIdSetIterator#threshold
• Use minDocId as offset for reducing the memory consumed by DocIdSetIterator

[jainankitk]

I was wondering how do is the min/max docId partitioning managed by something like PointRangeQuery as it doesn't iterate over the documents in docId order. Realized that we do duplicate work today as every LeafReaderContextPartition builds complete docIdSet. Related to #13745.

[prudhvigodithi]

So from my understanding, Instead of creating one large BitSet for the entire segment (sized for maxDoc), the suggestion is to:

• Create a smaller BitSet that only covers the specific range of document IDs in a partition.
• Use the minDocId and maxDocId of the partition to define this range, something like as follows:

int rangeSize = maxDocId - minDocId + 1;
this.threshold = rangeSize >>> 7; 

So now the memory cost of the BitSet would be based on the range size, not maxDoc.

[jainankitk]

@prudhvigodithi - While from BitSet perspective that looks, I am not sure how this implementation of BitSet can be used by LeafReaderContextPartition for PointRangeQuery. Today, complete DocIdSet is created for every partition and only the scoring happens per doc range. Seems Luca already started looking into solving this problem per #13745 (comment). @javanna - Wondering if you were able to make progress, or have further insights?

[jainankitk]

Actually thinking more on this, even though we iterate over, we can skip adding documents to DocIdSetBuilder outside the range of LeafReaderContextPartition. There is still some duplicate work for building DocIdSetBuilder across threads for individual segment, this should reduce the memory requirements while still providing concurrency benefits of intra segment search. @prudhvigodithi - Let me know if you still interested in take a stab at this

[prudhvigodithi]

Yes let me take a stab at this. Thanks

[javanna]

Hey @jainankitk , I tried a few attempts, but did not get very far. I was not able to put in enough time to put a proposal together and submit a PR yet. I am happy to review changes if others manage to make progress before I get to it. I do have some context on what's needed for intra-segment concurrency based on my previous work on it. Cheers!

[jainankitk]

Thanks @javanna for getting back with the current status. Will wait for @prudhvigodithi to make progress on the proposal and PRs. Will loop you in for reviews given your intra-segment concurrency context. Looking forward to making more progress in this space, over next few months!

[prudhvigodithi]

Filtering out out of range docs prevents giant bit-sets, so we can only add the docs to the DocIdSetBuilder that are within the range of LeafReaderContextPartition this prevents each thread from storing doc IDs that belong to other partitions.

Adding to this should we also update the maxDoc (this.threshold = maxDoc >>> 7;) with LeafReaderContextPartition size so the so the threshold scales correctly, this way the resulting bit-set are sized to the partition itself.