This is an interesting idea. Ideally we would figure out up-front whether it's best to use the graph or not, but I can also imagine that we can't always make the right decision there, so we need the ability to fall back. I wonder if we could make it look a bit nicer API-wise, e.g. could we more generally move the responsibility of tracking which doc IDs have already been collected from the codec to the collector, so that it wouldn't even need changes to the API? I guess that the downside is that it would force us to track this information in the doc ID space, while the codec can do this more efficiently right now by tracking a bit set of vector ordinals.

Thanks @jpountz! I realised something from your comment:

My current implementation has a flaw, because it cannot handle the OrdinalTranslatedKnnCollector correctly: The setVisited call has the BitSet visited as packed ordinals, but the getVisited call receives a docId (and not a vectorId) so we would need a reverse IntToIntFunction docIdToVectorOrdinal to map it back to an ordinal

This is straightforward for DenseOffHeapVectorValues or EmptyOffHeapVectorValues (because there is a 1-1 mapping between a doc and ordinal) but becomes a problem for SparseOffHeapVectorValues which has the vectorOrdinaltoDocId implemented as a DirectMonotonicReader - which I think is docIds stored one after another - so getting the docId for an ordinal is as simple as a lookup at that offset. However, getting an inverse of this can become costly (binary search -> returning the index) as opposed to the current constant time lookup

I wonder how costly it would be to maintain the set of visited docs at the KnnCollector like you mentioned (perhaps using a SparseFixedBitSet)? We already create a BitSet of maxDoc length to hold the filtered docs..

In the worst case, we would need another BitSet of the same length to store which docs are visited from graph search, then skip over those from #exactSearch. However, there may be a better opportunity here: since we want to go over docs that are "prefiltered but not visited", can we simply #clear the bits whenever we visit a node - we just need to find a way to do this cleanly?

The gains may be beneficial only when topK is large and the filter is restrictive

Is this because a large topK will cause approximate search to fan out more and have potentially more nodes to visit. While the restrictive filter increases the odds of neighbors with high similarity getting rejected, causing us to visit >cost(filter) and fallback to exact search.

So we see a 5-10% improvement in latency b/w baseline and candidate?

Yes, the restrictive filter will cause more fallbacks to #exactSearch, and the high topK will mean more visitation = saving more on duplicate work

So we see a 5-10% improvement in latency b/w baseline and candidate?

The benchmark is sort of a happy case (high topK), but yes, we see a 5-10% improvement in latency there. I'm not sure what's the general topK - selectivity combinations seen by users, may be helpful if someone else can replicate the benchmark with values close to their use-case

like working in ordinal v/s docId space that @jpountz pointed out

I took a shot at moving the tracking of visited nodes to the docId space (delegated to KnnCollector), and the benchmark results are similar to the posted one (but the flaw mentioned above is addressed)

This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!

I have done some more benchmarking and there isn't really a significant improvement. This is over 500k, 1024 vectors. Getting the nearest 500 neighbors.

Baseline

latency	nDoc	filter
3.11	500000	0.0060	pre-filter
3.11	500000	0.0059	pre-filter
2.94	500000	0.0058	pre-filter
2.90	500000	0.0057	pre-filter
2.81	500000	0.0056	pre-filter
2.77	500000	0.0055	pre-filter
2.65	500000	0.0054	pre-filter
2.80	500000	0.0053	pre-filter

Candidate (this using a FixedBitSet to keep track of visited in a collector)

latency	nDoc    filter
2.94	500000	0.0060	pre-filter
2.90	500000	0.0059	pre-filter
2.87	500000	0.0058	pre-filter
2.94	500000	0.0057	pre-filter
2.70	500000	0.0056	pre-filter
2.60	500000	0.0055	pre-filter
2.63	500000	0.0054	pre-filter
2.59	500000	0.0053	pre-filter

Note, this is with a FixedBitSet that allocates enough space to track every vector. This can get very expensive on large segments. I tried a SparseBitSet but at my scale of only 500k docs, it was actually slower than baseline.

It just shows that the margins of the gain here may be very slim :/

Thanks for checking @benwtrent!

We primarily improve cases of using a high topK + a selective filter (good rate of fallback, large number of duplicate computations). I notice ~5% gains in those cases from your numbers, which may not be high enough for the extra memory consumption

I'll wait for a couple of days in case someone feels this is still worth pursuing, or else I'll close this PR..