apache / apache/lucene

Explore partially decoding blocks (within-block skipping)

Open
#12,749 2 comments 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

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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.