apache/lucene

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

Open

#14.845 geöffnet am 25. Juni 2025

Auf GitHub ansehen
 (6 Kommentare) (0 Reaktionen) (0 zugewiesene Personen)Java (2.179 Stars) (879 Forks)batch import
good first issuetype:enhancement

Beschreibung

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

Tech Stack
java
Domain
searchperformance
Issue Type
feature
SchwierigkeitGeschätzte Implementierungsschwierigkeit für neue Contributors, von 1 für sehr kleine Änderungen bis 5 für Expertenarbeit.
3
Geschätzte ZeitEin grober Zeitrahmen, um zu recherchieren, zu implementieren, zu testen und einen Pull Request vorzubereiten.
1-2 days
AktivitätsstatusWie verfügbar das Issue gerade wirkt: frisch, aktiv, stale, blockiert oder wartet auf Maintainer-Input.
active
KlarheitWie klar das Issue die erwartete Änderung, Akzeptanzkriterien und den nächsten Schritt erklärt.
clear
Voraussetzungen
JavaLucene vector search conceptsfamiliarity with PR #14836
EinsteigerfreundlichkeitEin Score von 1 bis 100, der schätzt, wie zugänglich dieses Issue für First-Time Contributors ist.
25
Research-Richtung
Examine the implementation of `expectedVisitedNodes` in PR #14836. Investigate the current filtered search logic in the codebase, likely in classes related to `KnnVectorQuery` or similar. Determine the impact of changing the condition in step 2 to use `expectedVisitedNodes` and validate with benchmark tests.