DirectPostingsFormat can minimize binary searching in seek's [LUCENE-4932]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
I was looking at the DirectPostingsFormat to see exactly what it's doing when you I seekExact(). It does a plain binary search every time, even if I've positioned the state well into size of the array. A comment (probably left by @mikemccand) shows that he too knows this could be done smarter:
```Java
// TODO: we should use the skip pointers; should be
// faster than bin search; we should also hold
// & reuse current state so seeking forwards is
// faster
```
This issue represents resolving that TODO so it's isn't forgotten.
For inspiration about solving this in a smarter way, see Solr's SortedIntDocSet which avoids binary search using an approach that could be borrowed for this codec.
---
Migrated from [LUCENE-4932](https://issues.apache.org/jira/browse/LUCENE-4932) by David Smiley (@dsmiley)
Contributor guide
Research direction
Start by locating DirectPostingsFormat and the seekExact implementation, then read the TODO about skip pointers and reusing current state. Compare the approach with Solr's SortedIntDocSet; done means resolving that TODO so repeated or forward seeks avoid an unnecessary plain binary search while preserving seek behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100