You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by so...@apache.org on 2025/05/05 17:59:35 UTC
(lucene) branch main updated: OptimisticKnnVectorQuery (#14226)
This is an automated email from the ASF dual-hosted git repository.
sokolov pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new d279af1961f OptimisticKnnVectorQuery (#14226)
d279af1961f is described below
commit d279af1961f40465a3a9e8ab84848afe69fd8424
Author: Michael Sokolov <so...@falutin.net>
AuthorDate: Mon May 5 13:59:30 2025 -0400
OptimisticKnnVectorQuery (#14226)
* OptimisticKnnVectorQuery that re-enters search for segments with with strong results
* fix JDK23 lint
* simplify OptimisticKnnVectorQuery to 2 rounds only
* move OptimisticKnnVectorQuery into AbstractKnnVectorQuery
* tidy
* Use TopKnnCollector for second pass so we correctly collect total top K
---------
Co-authored-by: Michael Sokolov <so...@amazon.com>
---
.../lucene/search/AbstractKnnVectorQuery.java | 180 +++++++++++++++++++--
.../apache/lucene/search/SeededKnnVectorQuery.java | 8 +-
.../lucene/search/BaseKnnVectorQueryTestCase.java | 2 +-
.../lucene/search/TestKnnFloatVectorQuery.java | 10 +-
.../search/TestSeededKnnByteVectorQuery.java | 4 +-
5 files changed, 183 insertions(+), 21 deletions(-)
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..998495836ff 100644
--- a/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
@@ -22,12 +22,17 @@ import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
import java.util.List;
+import java.util.Map;
import java.util.Objects;
import java.util.concurrent.Callable;
import org.apache.lucene.codecs.KnnVectorsReader;
+import org.apache.lucene.codecs.lucene90.IndexedDISI;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.KnnVectorValues;
import org.apache.lucene.index.LeafReader;
import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.index.QueryTimeout;
@@ -53,6 +58,9 @@ import org.apache.lucene.util.Bits;
abstract class AbstractKnnVectorQuery extends Query {
private static final TopDocs NO_RESULTS = TopDocsCollector.EMPTY_TOPDOCS;
+ // Constant controlling the degree of additional result exploration done during
+ // pro-rata search of segments.
+ private static final int LAMBDA = 16;
protected final String field;
protected final int k;
@@ -93,22 +101,62 @@ abstract class AbstractKnnVectorQuery extends Query {
new TimeLimitingKnnCollectorManager(
getKnnCollectorManager(k, indexSearcher), indexSearcher.getTimeout());
TaskExecutor taskExecutor = indexSearcher.getTaskExecutor();
- List<LeafReaderContext> leafReaderContexts = reader.leaves();
+ List<LeafReaderContext> leafReaderContexts = new ArrayList<>(reader.leaves());
List<Callable<TopDocs>> tasks = new ArrayList<>(leafReaderContexts.size());
for (LeafReaderContext context : leafReaderContexts) {
tasks.add(() -> searchLeaf(context, filterWeight, knnCollectorManager));
}
- TopDocs[] perLeafResults = taskExecutor.invokeAll(tasks).toArray(TopDocs[]::new);
-
- // Merge sort the results
- TopDocs topK = mergeLeafResults(perLeafResults);
+ Map<Integer, TopDocs> perLeafResults = new HashMap<>();
+ TopDocs topK = runSearchTasks(tasks, taskExecutor, perLeafResults, leafReaderContexts);
+ int reentryCount = 0;
+ if (topK.scoreDocs.length > 0 && perLeafResults.size() > 1) {
+ float minTopKScore = topK.scoreDocs[topK.scoreDocs.length - 1].score;
+ TimeLimitingKnnCollectorManager knnCollectorManagerInner =
+ new TimeLimitingKnnCollectorManager(
+ new ReentrantKnnCollectorManager(
+ new TopKnnCollectorManager(k, indexSearcher), perLeafResults),
+ indexSearcher.getTimeout());
+ Iterator<LeafReaderContext> ctxIter = leafReaderContexts.iterator();
+ while (ctxIter.hasNext()) {
+ LeafReaderContext ctx = ctxIter.next();
+ TopDocs perLeaf = perLeafResults.get(ctx.ord);
+ if (perLeaf.scoreDocs.length > 0
+ && perLeaf.scoreDocs[perLeaf.scoreDocs.length - 1].score >= minTopKScore) {
+ // All this leaf's hits are at or above the global topK min score; explore it further
+ ++reentryCount;
+ tasks.add(() -> searchLeaf(ctx, filterWeight, knnCollectorManagerInner));
+ } else {
+ // This leaf is tapped out; discard the context from the active list so we maintain
+ // correspondence between tasks and leaves
+ ctxIter.remove();
+ }
+ }
+ assert leafReaderContexts.size() == tasks.size();
+ assert perLeafResults.size() == reader.leaves().size();
+ topK = runSearchTasks(tasks, taskExecutor, perLeafResults, leafReaderContexts);
+ }
if (topK.scoreDocs.length == 0) {
return new MatchNoDocsQuery();
}
- return createRewrittenQuery(reader, topK);
+ return createRewrittenQuery(reader, topK, reentryCount);
+ }
+
+ private TopDocs runSearchTasks(
+ List<Callable<TopDocs>> tasks,
+ TaskExecutor taskExecutor,
+ Map<Integer, TopDocs> perLeafResults,
+ List<LeafReaderContext> leafReaderContexts)
+ throws IOException {
+ List<TopDocs> taskResults = taskExecutor.invokeAll(tasks);
+ for (int i = 0; i < taskResults.size(); i++) {
+ perLeafResults.put(leafReaderContexts.get(i).ord, taskResults.get(i));
+ }
+ tasks.clear();
+ // Merge sort the results
+ return mergeLeafResults(perLeafResults.values().toArray(TopDocs[]::new));
}
- private TopDocs searchLeaf(
+ protected TopDocs searchLeaf(
LeafReaderContext ctx,
Weight filterWeight,
TimeLimitingKnnCollectorManager timeLimitingKnnCollectorManager)
@@ -184,7 +232,29 @@ abstract class AbstractKnnVectorQuery extends Query {
}
protected KnnCollectorManager getKnnCollectorManager(int k, IndexSearcher searcher) {
- return new TopKnnCollectorManager(k, searcher);
+ KnnCollectorManager manager =
+ (visitedLimit, strategy, context) -> {
+ @SuppressWarnings("resource")
+ float leafProportion =
+ context.reader().maxDoc() / (float) context.parent.reader().maxDoc();
+ int perLeafTopK = perLeafTopKCalculation(k, leafProportion);
+ // if we divided by zero above, leafProportion can be NaN and then this would be 0
+ assert perLeafTopK > 0;
+ return new TopKnnCollector(perLeafTopK, visitedLimit, strategy);
+ };
+ return manager;
+ }
+
+ /*
+ * Returns perLeafTopK, the expected number (K * leafProportion) of hits in a leaf with the given
+ * proportion of the entire index, plus three standard deviations of a binomial distribution. Math
+ * says there is a 95% probability that this segment's contribution to the global top K hits are
+ * <= perLeafTopK.
+ */
+ private static int perLeafTopKCalculation(int k, float leafProportion) {
+ return (int)
+ Math.max(
+ 1, k * leafProportion + LAMBDA * Math.sqrt(k * leafProportion * (1 - leafProportion)));
}
protected abstract TopDocs approximateSearch(
@@ -264,12 +334,56 @@ abstract class AbstractKnnVectorQuery extends Query {
return TopDocs.merge(k, perLeafResults);
}
- private Query createRewrittenQuery(IndexReader reader, TopDocs topK) {
- int len = topK.scoreDocs.length;
+ // forked from SeededKnnVectorQuery.SeededCollectorManager
+ private class ReentrantKnnCollectorManager implements KnnCollectorManager {
+ final KnnCollectorManager knnCollectorManager;
+ final Map<Integer, TopDocs> perLeafResults;
+
+ ReentrantKnnCollectorManager(
+ KnnCollectorManager knnCollectorManager, Map<Integer, TopDocs> perLeafResults) {
+ this.knnCollectorManager = knnCollectorManager;
+ this.perLeafResults = perLeafResults;
+ }
+ @Override
+ public KnnCollector newCollector(
+ int visitLimit, KnnSearchStrategy searchStrategy, LeafReaderContext ctx)
+ throws IOException {
+ KnnCollector delegateCollector =
+ knnCollectorManager.newCollector(visitLimit, searchStrategy, ctx);
+ TopDocs seedTopDocs = perLeafResults.get(ctx.ord);
+ VectorScorer scorer = createVectorScorer(ctx, ctx.reader().getFieldInfos().fieldInfo(field));
+ if (seedTopDocs.totalHits.value() == 0 || scorer == null) {
+ // shouldn't happen - we only come here when there are results
+ assert false;
+ // on the other hand, it should be safe to return no results?
+ return delegateCollector;
+ }
+ DocIdSetIterator vectorIterator = scorer.iterator();
+ // Handle sparse
+ if (vectorIterator instanceof IndexedDISI indexedDISI) {
+ vectorIterator = IndexedDISI.asDocIndexIterator(indexedDISI);
+ }
+ // Most underlying iterators are indexed, so we can map the seed docs to the vector docs
+ if (vectorIterator instanceof KnnVectorValues.DocIndexIterator indexIterator) {
+ DocIdSetIterator seedDocs =
+ new SeededKnnVectorQuery.MappedDISI(
+ indexIterator, new SeededKnnVectorQuery.TopDocsDISI(seedTopDocs, ctx));
+ return knnCollectorManager.newCollector(
+ visitLimit,
+ new KnnSearchStrategy.Seeded(seedDocs, seedTopDocs.scoreDocs.length, searchStrategy),
+ ctx);
+ }
+ // could lead to an infinite loop if this ever happens
+ assert false;
+ return delegateCollector;
+ }
+ }
+
+ protected Query createRewrittenQuery(IndexReader reader, TopDocs topK, int reentryCount) {
+ int len = topK.scoreDocs.length;
assert len > 0;
float maxScore = topK.scoreDocs[0].score;
-
Arrays.sort(topK.scoreDocs, Comparator.comparingInt(a -> a.doc));
int[] docs = new int[len];
float[] scores = new float[len];
@@ -278,7 +392,14 @@ abstract class AbstractKnnVectorQuery extends Query {
scores[i] = topK.scoreDocs[i].score;
}
int[] segmentStarts = findSegmentStarts(reader.leaves(), docs);
- return new DocAndScoreQuery(docs, scores, maxScore, segmentStarts, reader.getContext().id());
+ return new DocAndScoreQuery(
+ docs,
+ scores,
+ maxScore,
+ segmentStarts,
+ topK.totalHits.value(),
+ reader.getContext().id(),
+ reentryCount);
}
static int[] findSegmentStarts(List<LeafReaderContext> leaves, int[] docs) {
@@ -351,27 +472,56 @@ abstract class AbstractKnnVectorQuery extends Query {
private final float[] scores;
private final float maxScore;
private final int[] segmentStarts;
+ private final long visited;
private final Object contextIdentity;
+ private final int reentryCount;
/**
* Constructor
*
* @param docs the global docids of documents that match, in ascending order
* @param scores the scores of the matching documents
+ * @param maxScore the max of those scores? why do we need to pass in?
* @param segmentStarts the indexes in docs and scores corresponding to the first matching
* document in each segment. If a segment has no matching documents, it should be assigned
* the index of the next segment that does. There should be a final entry that is always
* docs.length-1.
+ * @param visited the number of graph nodes that were visited, and for which vector distance
+ * scores were evaluated.
* @param contextIdentity an object identifying the reader context that was used to build this
* query
*/
DocAndScoreQuery(
- int[] docs, float[] scores, float maxScore, int[] segmentStarts, Object contextIdentity) {
+ int[] docs,
+ float[] scores,
+ float maxScore,
+ int[] segmentStarts,
+ long visited,
+ Object contextIdentity,
+ int reentryCount) {
this.docs = docs;
this.scores = scores;
this.maxScore = maxScore;
this.segmentStarts = segmentStarts;
+ this.visited = visited;
this.contextIdentity = contextIdentity;
+ this.reentryCount = reentryCount;
+ }
+
+ /*
+ DocAndScoreQuery(DocAndScoreQuery other) {
+ this.docs = other.docs;
+ this.scores = other.scores;
+ this.maxScore = other.maxScore;
+ this.segmentStarts = other.segmentStarts;
+ this.visited = other.visited;
+ this.contextIdentity = other.contextIdentity;
+ this.reentryCount = other.reentryCount;
+ }
+ */
+
+ int reentryCount() {
+ return reentryCount;
}
@Override
@@ -487,6 +637,10 @@ abstract class AbstractKnnVectorQuery extends Query {
visitor.visitLeaf(this);
}
+ public long visited() {
+ return visited;
+ }
+
@Override
public boolean equals(Object obj) {
if (sameClassAs(obj) == false) {
diff --git a/lucene/core/src/java/org/apache/lucene/search/SeededKnnVectorQuery.java b/lucene/core/src/java/org/apache/lucene/search/SeededKnnVectorQuery.java
index 98d8599f116..9fcd34e3d99 100644
--- a/lucene/core/src/java/org/apache/lucene/search/SeededKnnVectorQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/SeededKnnVectorQuery.java
@@ -179,11 +179,11 @@ public class SeededKnnVectorQuery extends AbstractKnnVectorQuery {
return delegate.createVectorScorer(context, fi);
}
- private static class MappedDISI extends DocIdSetIterator {
+ static class MappedDISI extends DocIdSetIterator {
KnnVectorValues.DocIndexIterator indexedDISI;
DocIdSetIterator sourceDISI;
- private MappedDISI(KnnVectorValues.DocIndexIterator indexedDISI, DocIdSetIterator sourceDISI) {
+ MappedDISI(KnnVectorValues.DocIndexIterator indexedDISI, DocIdSetIterator sourceDISI) {
this.indexedDISI = indexedDISI;
this.sourceDISI = sourceDISI;
}
@@ -225,11 +225,11 @@ public class SeededKnnVectorQuery extends AbstractKnnVectorQuery {
}
}
- private static class TopDocsDISI extends DocIdSetIterator {
+ static class TopDocsDISI extends DocIdSetIterator {
private final int[] sortedDocIds;
private int idx = -1;
- private TopDocsDISI(TopDocs topDocs, LeafReaderContext ctx) {
+ TopDocsDISI(TopDocs topDocs, LeafReaderContext ctx) {
sortedDocIds = new int[topDocs.scoreDocs.length];
for (int i = 0; i < topDocs.scoreDocs.length; i++) {
// Remove the doc base as added by the collector
diff --git a/lucene/core/src/test/org/apache/lucene/search/BaseKnnVectorQueryTestCase.java b/lucene/core/src/test/org/apache/lucene/search/BaseKnnVectorQueryTestCase.java
index 5f925d98e57..6f3fa1b600d 100644
--- a/lucene/core/src/test/org/apache/lucene/search/BaseKnnVectorQueryTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/search/BaseKnnVectorQueryTestCase.java
@@ -496,7 +496,7 @@ abstract class BaseKnnVectorQueryTestCase extends LuceneTestCase {
assertRandomConsistency(false);
}
- @AwaitsFix(bugUrl = "https://github.com/apache/lucene/issues/14180")
+ // @AwaitsFix(bugUrl = "https://github.com/apache/lucene/issues/14180")
public void testRandomConsistencyMultiThreaded() throws IOException {
assertRandomConsistency(true);
}
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestKnnFloatVectorQuery.java b/lucene/core/src/test/org/apache/lucene/search/TestKnnFloatVectorQuery.java
index 96965b14fce..5278beb5d97 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestKnnFloatVectorQuery.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestKnnFloatVectorQuery.java
@@ -236,13 +236,21 @@ public class TestKnnFloatVectorQuery extends BaseKnnVectorQueryTestCase {
AbstractKnnVectorQuery.DocAndScoreQuery query =
new AbstractKnnVectorQuery.DocAndScoreQuery(
- docs, scores, maxScore, segments, indexReader.getContext().id());
+ docs,
+ scores,
+ maxScore,
+ segments,
+ scoreDocs.length,
+ indexReader.getContext().id(),
+ 0);
final Weight w = query.createWeight(searcher, ScoreMode.TOP_SCORES, 1.0f);
TopDocs topDocs = searcher.search(query, 100);
assertEquals(scoreDocs.length, topDocs.totalHits.value());
+ assertEquals(query.visited(), topDocs.totalHits.value());
assertEquals(TotalHits.Relation.EQUAL_TO, topDocs.totalHits.relation());
Arrays.sort(topDocs.scoreDocs, Comparator.comparingInt(scoreDoc -> scoreDoc.doc));
assertEquals(scoreDocs.length, topDocs.scoreDocs.length);
+ assertEquals(0, query.reentryCount());
for (int i = 0; i < scoreDocs.length; i++) {
assertEquals(scoreDocs[i].doc, topDocs.scoreDocs[i].doc);
assertEquals(scoreDocs[i].score, topDocs.scoreDocs[i].score, 0.0001f);
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestSeededKnnByteVectorQuery.java b/lucene/core/src/test/org/apache/lucene/search/TestSeededKnnByteVectorQuery.java
index c4a3aa23303..ba4ba46bf3e 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestSeededKnnByteVectorQuery.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestSeededKnnByteVectorQuery.java
@@ -275,10 +275,10 @@ public class TestSeededKnnByteVectorQuery extends BaseKnnVectorQueryTestCase {
@Override
public KnnCollector newCollector(
- int numVisisted, KnnSearchStrategy searchStrategy, LeafReaderContext context)
+ int numVisited, KnnSearchStrategy searchStrategy, LeafReaderContext context)
throws IOException {
KnnCollector knnCollector =
- knnCollectorManager.newCollector(numVisisted, searchStrategy, context);
+ knnCollectorManager.newCollector(numVisited, searchStrategy, context);
if (knnCollector.getSearchStrategy() instanceof KnnSearchStrategy.Seeded seeded) {
if (seedCalls == null && seeded.numberOfEntryPoints() > 0) {
fail("Expected non-seeded collector but received: " + knnCollector);