apache / apache/lucene

Wrap MatchedDocs and LiveDocs in a single Bits instance in createBitSet function of AbstractKnnVectorQuery

Open
#12,414 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

**Context**

In KNN Prefiltering we require a ```BitSet``` of docs which matched with prefilter query. This BitSet is used during HNSW Graph Search to check whether a node is accepted for matching or not. To create this BitSet we call [createBitSet](https://github.com/apache/lucene/blob/9ffc625b2ec43481e2cfba29828efbddf12e6852/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java#L161) function which creates a BitSet with following conditions:

1. When there are **no deletions** in the index and ```DocIdSetIterator``` is of ```BitSetIterator``` instance, then directly return the BitSet.

2. For other cases create a ```FilteredDocIdSetIterator``` first then create ```BitSet``` by iterating over docs from the ```FilteredDocIdSetIterator```.

```
private BitSet createBitSet(DocIdSetIterator iterator, Bits liveDocs, int maxDoc)
throws IOException {
if (liveDocs == null && iterator instanceof BitSetIterator bitSetIterator) {
// If we already have a BitSet and no deletions, reuse the BitSet
return bitSetIterator.getBitSet();
} else {
// Create a new BitSet from matching and live docs
FilteredDocIdSetIterator filterIterator =
new FilteredDocIdSetIterator(iterator) {
@Override
protected boolean match(int doc) {
return liveDocs == null || liveDocs.get(doc);
}
};
return BitSet.of(filterIterator, maxDoc);
}
}

```
**Problem**

When the ```DocIdSetIterator``` is of ```BitSetIterator``` instance and there are **deletions** in the index, we create a FilteredDocIdSetIterator which is later used to create a BitSet. This is a time consuming process because to create the BitSet we iterate over all matching docs from the iterator.

**Proposed Optimisation**

For the above case, we can wrap matchedDocs and liveDocs under single Bits instance something like below which can be directly passed for HNSW search. So, now during HNSW Search when a node is explored, we will check if the doc is accepted or not by checking bits of both matchedDocs and liveDocs which is constant time operation.

```
public class KNNBitSet implements Bits{

Bits liveDocs;
Bits matchedDocs;
public KNNBitSet(Bits matchedDocs, Bits liveDocs) {
this.matchedDocs = matchedDocs;
this.liveDocs = liveDocs;

}
@Override
public boolean get(int index) {
if (liveDocs ==null) {
return matchedDocs.get(index);
}
return matchedDocs.get(index) & liveDocs.get(index);
}

@Override
public int length() {
return 0;
}
}
```

**Advantage**

This will reduce BitSet creation time for some cases (when there are deleted documents) because now we are not iterating over each docs to create the BitSet.

**Drawback**

There is one drawback in this approach, that we will not be able to give the exact cardinality of acceptedDocs and the number will be higher than exact number of acceptedDocs because now we are not considering liveDocs into the final BitSet.

*Original*:
Number of Matched Docs = 10, Number of Deleted Docs = 2
Cardinality of Accepted Docs = 10-2 = 8

*With Proposed Optimisation*:
Number of Matched Docs = 10, Number of Deleted Docs = 2
Cardinality of Accepted Docs = 10 (This is an overestimation as we are not considering deleted docs in BitSet)

Contributor guide

Open the contributing guide

Research direction

Start in lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java at createBitSet, then trace how the resulting BitSet is used during HNSW Graph Search. Evaluate the proposed combined matchedDocs/liveDocs Bits behavior, including its length and cardinality implications. Done means the optimization is integrated without materializing all matching documents and remains compatible with the search path.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.