(lucene) branch main updated: Use per-segment K in filtered KNN fallback logic (fixes 14671) (#14680)

[so...@apache.org]

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 24f2c4b429a Use per-segment K in filtered KNN fallback logic (fixes 14671) (#14680)
24f2c4b429a is described below

commit 24f2c4b429ab83c7f8057d1a9689cd4d1b8c5ebc
Author: Michael Sokolov <so...@falutin.net>
AuthorDate: Fri May 16 17:06:29 2025 -0400

    Use per-segment K in filtered KNN fallback logic (fixes 14671) (#14680)
---
 .../org/apache/lucene/search/AbstractKnnVectorQuery.java | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 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 5d203ca1a39..1ad62257f61 100644
--- a/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
@@ -194,19 +194,23 @@ abstract class AbstractKnnVectorQuery extends Query {
     final int cost = acceptDocs.cardinality();
     QueryTimeout queryTimeout = timeLimitingKnnCollectorManager.getQueryTimeout();
 
-    if (cost <= k) {
-      // If there are <= k possible matches, short-circuit and perform exact search, since HNSW
-      // must always visit at least k documents
+    float leafProportion = ctx.reader().maxDoc() / (float) ctx.parent.reader().maxDoc();
+    int perLeafTopK = perLeafTopKCalculation(k, leafProportion);
+
+    if (cost <= perLeafTopK) {
+      // If there are <= perLeafTopK possible matches, short-circuit and perform exact search, since
+      // HNSW must always visit at least perLeafTopK documents
       return exactSearch(ctx, new BitSetIterator(acceptDocs, cost), queryTimeout);
     }
 
     // Perform the approximate kNN search
     // We pass cost + 1 here to account for the edge case when we explore exactly cost vectors
     TopDocs results = approximateSearch(ctx, acceptDocs, cost + 1, timeLimitingKnnCollectorManager);
+
     if ((results.totalHits.relation() == TotalHits.Relation.EQUAL_TO
-            // We know that there are more than `k` available docs, if we didn't even get `k`
-            // something weird happened, and we need to drop to exact search
-            && results.scoreDocs.length >= k)
+            // We know that there are more than `perLeafTopK` available docs, if we didn't even get
+            // `perLeafTopK` something weird happened, and we need to drop to exact search
+            && results.scoreDocs.length >= perLeafTopK)
         // Return partial results only when timeout is met
         || (queryTimeout != null && queryTimeout.shouldExit())) {
       return results;