Explore partially decoding blocks (within-block skipping)
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
Idea from @mikemccand 's comment in https://github.com/apache/lucene/issues/12696#issuecomment-1770461719
```
Another exciting optimization such a "patch-less" encoding could implement is within-block skipping (I believe Tantivy does this).
Today, our skipper is forced to align to block boundaries, so when we skip to a given docid, we go to the block that may contain this docid, decode all 128 int[], then linearly scan within those 128 ints. This is quite a bit of overhead for each skip request!
If we could lower that linear scan cost to maybe 16 or 8 or something, the conjunctive queries should get even faster. But perhaps it becomes trickier to take advantage of SIMD optimizations if we are decoding a subset of ints, not sure.
```
After the change in https://github.com/apache/lucene/pull/12741 , we will no longer use patching when encoding doc blocks.
This may allow us to partially decode blocks? This would mean skipping could jump to the middle of a block, instead of having to be at block boundaries as they are today.
Contributor guide
Research direction
Start by reading the linked discussion in issue 12696 and the changes in pull request 12741, then trace Lucene's current block skipper and doc-block decoding behavior. The work is complete when a concrete partial-decoding approach is defined and validated for within-block skipping without the former patching requirement.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100