apache / apache/lucene

Move index of numbers from BKD into DocValuesSkipper?

Open
#14,850 3 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

Immature idea, for discussion purpose :)

Today our range query on numbers have two approaches: BKD or DocValue Skipper.

The drawback of BKD:
* Allocating too much memory (big bitset)
* can not respect small lead clause lazily (now eased by IndexOrDocValue)
* can not respect intra-segment concurrency.
* doc ids are usually stored 3 bytes.

The drawback of DocValue Skipper:
* Slow if we can not skip on one block.

I wonder if we can have a doc id list stored in value order in DocValue Skipper to replace BKD totally. These docs should be split into smaller blocks (128 or 512) and can be vectorized decoded. This idea sounds really like we have a small BKD in each block.

```
For example:

Today we have:
doc 1, 2, 3, 5, 6
value 3, 5, 2, 4, 1

we store another doc list 6, 3, 1, 5, 2
whose values are in order.
```

Advantages:
1. solve drawbacks of BKDs.
2. ease slow problem of DocValue Skipper

Disadvantages:
1. Comparing to BKD: this can not gather all docs needed on segment level. If docs are evenly distributed, there may be just a few docs required in a block, then we can not append whole doc block without caring values (addAll). Maybe we should not build this on level0 block but higher, like 65536-docs block?

Contributor guide

Open the contributing guide

Research direction

Start by tracing the existing BKD, DocValue Skipper, and IndexOrDocValue range-query paths, then compare how their doc IDs and block behavior are represented. The issue provides no named files, tests, or acceptance criteria; a contribution would first need a settled design and measurable definition of replacing BKD.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend, search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.