You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by gu...@apache.org on 2025/05/26 15:45:04 UTC
(lucene) 03/03: Optimize AbstractKnnVectorQuery#createBitSet with intoBitset (#14674)
This is an automated email from the ASF dual-hosted git repository.
guofeng pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit e865d0076e435891fcd8c62647df7bc044908742
Author: Guo Feng <52...@users.noreply.github.com>
AuthorDate: Mon May 26 21:53:57 2025 +0800
Optimize AbstractKnnVectorQuery#createBitSet with intoBitset (#14674)
---
lucene/CHANGES.txt | 2 ++
.../lucene/search/AbstractKnnVectorQuery.java | 29 ++++++++++++++-------
.../search/AbstractVectorSimilarityQuery.java | 30 ++++++++++++++++------
3 files changed, 44 insertions(+), 17 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 82c4bf10555..51e83b7d730 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -65,6 +65,8 @@ Optimizations
* GITHUB#14709: Speed up TermQuery by Scorer#nextDocsAndScores. (Guo Feng)
+* GITHUB#14674: Optimize AbstractKnnVectorQuery#createBitSet with intoBitset. (Guo Feng)
+
Bug Fixes
---------------------
* GITHUB#14654: ValueSource.fromDoubleValuesSource(dvs).getSortField() would throw errors when
diff --git a/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java b/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
index bdedc23fb88..0f49e806844 100644
--- a/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
@@ -37,6 +37,7 @@ import org.apache.lucene.search.knn.TopKnnCollectorManager;
import org.apache.lucene.util.BitSet;
import org.apache.lucene.util.BitSetIterator;
import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
/**
* Uses {@link KnnVectorsReader#search} to perform nearest neighbour search.
@@ -171,15 +172,25 @@ abstract class AbstractKnnVectorQuery extends Query {
// 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);
+ int threshold = maxDoc >> 7; // same as BitSet#of
+ if (iterator.cost() >= threshold) {
+ // take advantage of Disi#intoBitset and Bits#applyMask
+ FixedBitSet bitSet = new FixedBitSet(maxDoc);
+ bitSet.or(iterator);
+ if (liveDocs != null) {
+ liveDocs.applyMask(bitSet, 0);
+ }
+ return bitSet;
+ } else {
+ FilteredDocIdSetIterator filterIterator =
+ new FilteredDocIdSetIterator(iterator) {
+ @Override
+ protected boolean match(int doc) {
+ return liveDocs == null || liveDocs.get(doc);
+ }
+ };
+ return BitSet.of(filterIterator, maxDoc); // create a sparse bitset
+ }
}
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java b/lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java
index df11ae04232..8bbac89ee1b 100644
--- a/lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/AbstractVectorSimilarityQuery.java
@@ -29,6 +29,7 @@ import org.apache.lucene.search.knn.KnnSearchStrategy;
import org.apache.lucene.util.BitSet;
import org.apache.lucene.util.BitSetIterator;
import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.FixedBitSet;
/**
* Search for all (approximate) vectors above a similarity threshold.
@@ -142,14 +143,27 @@ abstract class AbstractVectorSimilarityQuery extends Query {
acceptDocs = bitSetIterator.getBitSet();
} else {
// Else collect all matching docs
- FilteredDocIdSetIterator filtered =
- new FilteredDocIdSetIterator(scorer.iterator()) {
- @Override
- protected boolean match(int doc) {
- return liveDocs == null || liveDocs.get(doc);
- }
- };
- acceptDocs = BitSet.of(filtered, leafReader.maxDoc());
+ DocIdSetIterator iterator = scorer.iterator();
+ final int maxDoc = leafReader.maxDoc();
+ int threshold = maxDoc >> 7; // same as BitSet#of
+ if (iterator.cost() >= threshold) {
+ // take advantage of Disi#intoBitset and Bits#applyMask
+ FixedBitSet bitSet = new FixedBitSet(maxDoc);
+ bitSet.or(iterator);
+ if (liveDocs != null) {
+ liveDocs.applyMask(bitSet, 0);
+ }
+ acceptDocs = bitSet;
+ } else {
+ FilteredDocIdSetIterator filterIterator =
+ new FilteredDocIdSetIterator(iterator) {
+ @Override
+ protected boolean match(int doc) {
+ return liveDocs == null || liveDocs.get(doc);
+ }
+ };
+ acceptDocs = BitSet.of(filterIterator, maxDoc); // create a sparse bitset
+ }
}
int cardinality = acceptDocs.cardinality();