apache/lucene

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

Open

#14.845 aperta il 25 giu 2025

Vedi su GitHub
 (6 commenti) (0 reazioni) (0 assegnatari)Java (879 fork)batch import
good first issuetype:enhancement

Metriche repository

Star
 (2179 star)
Metriche merge PR
 (Merge medio 7g 11h) (109 PR mergiate in 30 g)

Descrizione

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?

Guida contributor

Direzione di ricerca
Esamina l'estimatore expectedVisitedNodes e il percorso del codice di ricerca vettoriale filtrata per valutare il potenziale miglioramento.
Tech stack
java
Dominio
backend
Tipo issue
Funzionalità
DifficoltàQuanto dovrebbe essere impegnativa per un nuovo contributor.
3
Tempo stimatoTempo stimato per completare e verificare uno scope piccolo.
1-2 giorni
Stato attivitàQuanto è probabile che la issue sia ancora attiva e reviewable.
Attiva
ChiarezzaQuanto chiaramente la issue descrive problema, scope e risultato atteso.
Chiara
Prerequisiti
JavaLucene
Adatta ai principiantiQuanto la issue è adatta a contributor alla prima esperienza.
60