apache / apache/lucene

Re-explore the logic around when Vector search should be Exact

Open
#12,505 3 comments 1 reaction 0 assignees View on GitHub
type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

Lucene always does an approximate nearest neighbors search when no filter is provided.

This seems like unnecessary work. Some benchmarks would have to be done, but some ideas I had around options to explore:

- Why not always do exact when `maxDoc < k`?
- Should the "when to do exact" calculation consider `byte` vs `float` vectors?
- EDIT: We should also revisit this calculation for when things are quantized or not. Increasingly, this seems like the format itself should track when it must bypass the graph at search time or not.

It seems weird to go through all the work of going to the graph if there are only 10 documents in a segment.

Contributor guide

Open the contributing guide

Research direction

No specific file or test is named. Start by locating the vector-search exactness decision and compare benchmark results for segments where maxDoc is below k, then examine byte versus float vectors and quantized versus unquantized formats. Done means the conditions for bypassing the graph are measured and clearly defined.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.