Optimize IndexedDISI by implementing binary search for sparseDocs in advance methods
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
If we look at below line of code, we are doing linear search if `NumDocs < 4096`.
https://github.com/apache/lucene/blob/9b68f633fdd606074e1808474f2baa23ff21df91/lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java#L583
This would be slow if there are repeated searches within the same Block.
I'm attaching a PR where I am trying to optimize it via BinarySearch.
Contributor guide
Research direction
Start by reading lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java around line 583 and trace the advance methods that search sparseDocs. Compare the current linear lookup with the surrounding IndexedDISI behavior, then verify that repeated searches preserve existing results while using binary search for sparse blocks.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Refactor
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 68/100