Move index of numbers from BKD into DocValuesSkipper?
- 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
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