Details
-
Bug
-
Status: Resolved
-
Minor
-
Resolution: Won't Fix
-
None
-
None
-
None
-
None
-
New
Description
Performing a kNN search with very large k (where k is close to the total number of live docs) can return fewer than k documents. This occurs because searches aren't guaranteed to be able to visit every node in the graph. Specifically, when choosing entry points for the search, we make k random draws with replacement, and sometimes end up with fewer than k entry points. These entry points may not provide a connection to all other nodes in the graph.
This is an unusual case, but I think it'd be nice if we could always return k docs when they are available (or at least document the behavior?) We're currently working on adding graph layers (LUCENE-10054), which will change how entry points are selected. Maybe we can revisit this issue once that work is further along to see if a fix is still needed.
Here's an example test failure showing the problem. We happen to select numDocs=101 and k=100.
./gradlew test --tests TestKnnVectorQuery.testRandom -Dtests.seed=3B6CE0E105431E18
Attachments
Issue Links
- links to
