(lucene) branch main updated: Fix knn vector visit limit fence post error (#13058)

[be...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

benwtrent 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 681fa216656 Fix knn vector visit limit fence post error (#13058)
681fa216656 is described below

commit 681fa216656efd1bef1ea206c8884b1d32008941
Author: Benjamin Trent <be...@gmail.com>
AuthorDate: Tue Feb 6 12:37:12 2024 -0500

    Fix knn vector visit limit fence post error (#13058)
    
    I noticed while experimenting with brute-force search that our visitation limit is EXACTLY the number of filtered docs to hit. Consequently, if we happen to do brute force search and visit that exact number of vectors, we will fall back again to do brute-force a second time. This struck me as weird.
    
    This commit adjusts the visit limit threshold for approximate search to account for this.
---
 .../src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java    | 5 +++--
 1 file changed, 3 insertions(+), 2 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 6c2c50a03e4..be69f800ba2 100644
--- a/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
+++ b/lucene/core/src/java/org/apache/lucene/search/AbstractKnnVectorQuery.java
@@ -126,7 +126,7 @@ abstract class AbstractKnnVectorQuery extends Query {
     }
 
     BitSet acceptDocs = createBitSet(scorer.iterator(), liveDocs, maxDoc);
-    int cost = acceptDocs.cardinality();
+    final int cost = acceptDocs.cardinality();
 
     if (cost <= k) {
       // If there are <= k possible matches, short-circuit and perform exact search, since HNSW
@@ -135,7 +135,8 @@ abstract class AbstractKnnVectorQuery extends Query {
     }
 
     // Perform the approximate kNN search
-    TopDocs results = approximateSearch(ctx, acceptDocs, cost, knnCollectorManager);
+    // We pass cost + 1 here to account for the edge case when we explore exactly cost vectors
+    TopDocs results = approximateSearch(ctx, acceptDocs, cost + 1, knnCollectorManager);
     if (results.totalHits.relation == TotalHits.Relation.EQUAL_TO) {
       return results;
     } else {