apache / apache/lucene

A little optimization about BKDReader

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

**1.Reduce the match times for BKD node whose relation=`CELL_CROSSES_QUERY`.**

When performing range query, if the Relation is `CELL_CROSSES_QUERY`, we need to traverse each value in this leaf node and `matches`. A segment query typically involves two leaf nodes with Relation set to `CELL_CROSSES_QUERY`, leading to 512×2 `matches`.

In reality, the 512 values on each BKD leaf node are stored in a compressed format, such as "30 consecutive 1, 30 consecutive 2, 30 consecutive 3.....". Notably, `matching` for `30 consecutive 1` only requires 1 times, instead of 30. With this optimization, the BKD tree only needs a few `matching` rather than 512 per leaf.

For a shard with 25 segments, the original approach would involve 25×512×2 = 25,600 `matching` operations. Through the above optimization, however, a lot of reduction in `matching` can be achieved.

https://github.com/apache/lucene/blob/3c118d74d0bc1bc194272774605c1c1e57232925/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java#L911
```
......
scratchIterator.reset(i, length);
if (visitor.compare(scratchPackedValue, scratchPackedValue) == PointValues.Relation.CELL_INSIDE_QUERY) {
visitor.visit(new IntsRef(scratchIterator.docIDs, i, length));
}
......
```

**2.When calling `PointValues.intersect()`, if there is no matching node left, we should exit promptly.**

For example, in the following case, only leaf node 7 matches. In reality, we would visit nodes from 1 to 13.

- When visiting leaf node 7: relation = CELL_CROSSES_QUERY
- When visiting leaf node 8: relation = CELL_OUTSIDE_QUERY

Once the relation changes to CELL_OUTSIDE_QUERY in node 8, we should exit immediately instead of continuing to visit nodes 9 to 13.
![Image](https://github.com/user-attachments/assets/fa33e09a-957a-4406-b495-925bc40f1f4b)

Contributor guide

Open the contributing guide

Research direction

Start in lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java around the referenced scratchIterator and visitor.compare logic, then trace PointValues.intersect() and the CELL_CROSSES_QUERY/CELL_OUTSIDE_QUERY cases. Done means reducing redundant matches for repeated values in a leaf and exiting promptly when no matching nodes remain, with relevant tests covering both behaviors.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
performance, search
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.