apache / apache/lucene

Enhance ContinuousIds optimisation to store the diff between docIds as a Vint

Open
#13,228 0 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

One of the optimisations introduced by [LUCENE-10233](https://issues.apache.org/jira/browse/LUCENE-10233) was to compress continuous doc Ids (strictly sorted) by only storing the start docId [here](https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/util/bkd/DocIdsWriter.java#L61-L65) with a flag to indicate the same.

This works well when the difference between continuous docIds is `1`

I was testing datasets where only few points ( Enums ) are present in multiple docs and are inserted in a cyclic fashion.

Consider the following insertion order :

=================================
- Insert Doc Id 1 with 1d Point Value as 1
- Insert Doc Id 2 with 1d Point Value as 2
- Insert Doc Id 3 with 1d Point Value as 3

=================================

- Insert Doc Id 4 with 1d Point Value as 1
- Insert Doc Id 5 with 1d Point Value as 2
- Insert Doc Id 6 with 1d Point Value as 3

=================================

- Insert Doc Id 7 with 1d Point Value as 1
- Insert Doc Id 8 with 1d Point Value as 2
- Insert Doc Id 9 with 1d Point Value as 3

=================================

and so on.

In such scenario's, although the docIds for every point follow an arithmetic progression, the difference between them is 3.

I tested with changing the implementation to also store the diff along with starting docId and observed high compression for such cases. My test involved indexing 1 million docs with one numeric field containing only 2 unique points that are inserted in a cyclic fashion.

Without storing the diff, the KDD File took 276kb whereas with the diff it took around 34 kb.

My proposal is to store the diff along with the starting docId to ensure all arithmetic progressions of docIds can use this optimisation.

Contributor guide

Open the contributing guide

Research direction

Start in lucene/core/src/main/java/org/apache/lucene/util/bkd/DocIdsWriter.java at the ContinuousIds optimization described in LUCENE-10233. Examine how the start docId is stored, then validate the proposal against the cyclic arithmetic-progression example. Done means progressions with a constant difference can use the optimization and achieve the reported compression improvement.

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
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.