Could we encode postings the way we encode monotonic long doc values?
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
Lucene has an efficient (storage and CPU) compressor for monotonic long values, that simply makes "best fit" (ish?) linear model to the N monotonic values, and then encodes the precise error signal (positive and negative) of each value. I think we use it for doc values in certain cases? Or maybe only for in-memory data structures?
Lucene's block postings is different: it encodes the docid delta between each document. But because postings are encoded this way, we have a linear/chained data dependency and must sequentially add up all the docid deltas to get the true docid of each of the 128 postings in the block.
Could we change postings to instead encode with the linear fit? We'd maybe lose some compression (having to store negative and positive -- `ZInt`), but then decoding could be done concurrently with simple SIMD math, and then skipping might be able to do a binary search within the block?
I know this (efficient block `int[]` encoding for SIMD decode) is a well/heavily studied area in the literature :) I'm sure there is already a good option on [Daniel Lemire's blog](https://lemire.me/blog/) somewhere!
It's not so simple, though, because we also accumulate the `freq` of each posting so we can know where we are in the positions/payloads block space.
Contributor guide
Research direction
Start by tracing Lucene's block postings and monotonic long doc-values paths, then examine how doc IDs, frequencies, positions, and payloads are accumulated. A complete proposal would need benchmarks or tests comparing compression, SIMD decoding, and within-block skipping, with an agreed encoding design.
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
- 25/100