apache / apache/lucene

Should we use the new `expectedVisitedNodes` estimator to speed up filtered vector search?

Open
#14,845 8 comments 0 reactions 0 assignees View on GitHub
good first issue type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

@benwtrent 's PR at #14836 introduced an estimator for the number of visited nodes based on k and the number of vectors called `expectedVisitedNodes(int k, int size)`.

Currently, filtered vector search works roughly this way:
1. compute a per-leaf k value based on the global k value
2. if (filterCost <= perLeafK) do an exact search
3. else run an approximate search, stop after visiting filterCost+1 nodes
4. if the approximate search stopped early (and is thus incomplete), run an exact search

Could/should we update step 2 above to do an exact search if (filterCost <= expectedVisitedNodes(perLeafK, size))? This should help save approximate searches that are almost certainly going to be stopped early and ignored anyway?

Contributor guide

Open the contributing guide

Research direction

Start by reading PR #14836's expectedVisitedNodes(int k, int size) estimator and locate the filtered vector-search code implementing the four described steps. Compare the current per-leaf exact-search decision with the estimator, then verify that any change preserves filtered-search correctness and avoids approximate work when the estimate indicates it will be stopped early.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.