apache / apache/lucene

reduce unnecessary loop matches in BKDReader [LUCENE-10516]

Open
#11,552 1 comment 0 reactions 0 assignees View on GitHub
affects-version:8.6.2 legacy-jira-priority:Major module:core/other type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

In **BKDReader.visitSparseRawDocValues()**, we will read a batch of docIds which have the same point value:**scratchPackedValue**, then call **visitor.visit(scratchIterator, scratchPackedValue)** to find which docIDs match the range.

```java
default void visit(DocIdSetIterator iterator, byte[] packedValue) throws IOException {
int docID;
while ((docID = iterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
visit(docID, packedValue);
}
}
```

We know that the packedValue are same for the batch of docIds, if the first doc match the range, the batch of other docIds will also match the range, so the loop seems useless.

We should call the method as follow:

```java
public void visit(DocIdSetIterator iterator, byte[] packedValue) throws IOException {
if (matches(packedValue)) {
int docID;
while ((docID = iterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
visit(docID);
}
}
}
```

https://github.com/apache/lucene/blob/2e941fcfed6cad3d9c8667ff5324cd04858ba547/lucene/core/src/java/org/apache/lucene/search/PointRangeQuery.java#L196

If we should override the **visit(DocIdSetIterator iterator, byte[] packedValue)** in **ExitableDirectoryReader$ExitableIntersectVisitor** to avoid calling the default implement:

```java
`@Override`
public void visit(DocIdSetIterator iterator, byte[] packedValue) throws IOException {
queryCancellation.checkCancelled();
in.visit(iterator, packedValue);
}
```

---
Migrated from [LUCENE-10516](https://issues.apache.org/jira/browse/LUCENE-10516) by kkewwei (@kkewwei), updated May 20 2022

Contributor guide

Open the contributing guide

Research direction

Start by reading BKDReader.visitSparseRawDocValues() and the visit methods discussed in PointRangeQuery, then inspect ExitableDirectoryReader$ExitableIntersectVisitor for the cancellation path. Confirm how batches sharing scratchPackedValue are handled and verify that range matching and cancellation behavior remain correct without unnecessary per-document checks.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Refactor
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.