Package org.apache.cassandra.index.sai.disk.v1.vector

Class BruteForceRowIdIterator

java.lang.Object

org.apache.cassandra.utils.AbstractIterator<RowIdWithScore>

org.apache.cassandra.index.sai.disk.v1.vector.BruteForceRowIdIterator

All Implemented Interfaces:

com.google.common.collect.PeekingIterator<RowIdWithScore>, AutoCloseable, Iterator<RowIdWithScore>, CloseableIterator<RowIdWithScore>

@NotThreadSafe
public class BruteForceRowIdIterator
extends AbstractIterator<RowIdWithScore>

An iterator over RowIdWithScore that lazily consumes from a NeighborQueue of approximate scores.

The idea is that we maintain the same level of accuracy as we would get from a graph search, by re-ranking the top `k` best approximate scores at a time with the full resolution vectors to return the top `limit`.

For example, suppose that limit=3 and k=5 and we have ten elements. After our first re-ranking batch, we have ABDEF????? We will return A, B, and D; if more elements are requested, we will re-rank another 5 (so three more, including the two remaining from the first batch). Here we uncover C, G, and H, and order them appropriately: CEFGH?? This illustrates that, also like a graph search, we only guarantee ordering of results within a re-ranking batch, not globally.

Note that we deliberately do not fetch new items from the approximate list until the first batch of `limit`-many is consumed. We do this because we expect that most often the first limit-many will pass the final verification and only query more if some didn't (e.g. because the vector was deleted in a newer sstable).

As an implementation detail, we use a heap to maintain state rather than a List and sorting.

Constructor Summary

Constructors

Constructor	Description
BruteForceRowIdIterator(io.github.jbellis.jvector.graph.NeighborQueue approximateScoreQueue, SegmentRowIdOrdinalPairs segmentOrdinalPairs, io.github.jbellis.jvector.graph.NeighborSimilarity.ExactScoreFunction reranker, int limit, int topK, io.github.jbellis.jvector.graph.GraphIndex.View<float[]> view)

Method Summary

Modifier and Type	Method	Description
void	close()
protected RowIdWithScore	computeNext()

Methods inherited from class org.apache.cassandra.utils.AbstractIterator

endOfData, hasNext, next, peek, remove

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Iterator

forEachRemaining

Constructor Details

BruteForceRowIdIterator

public BruteForceRowIdIterator(io.github.jbellis.jvector.graph.NeighborQueue approximateScoreQueue,
 SegmentRowIdOrdinalPairs segmentOrdinalPairs,
 io.github.jbellis.jvector.graph.NeighborSimilarity.ExactScoreFunction reranker,
 int limit,
 int topK,
 io.github.jbellis.jvector.graph.GraphIndex.View<float[]> view)

Parameters:

approximateScoreQueue - A heap of indexes ordered by their approximate similarity scores

segmentOrdinalPairs - A mapping from the index in the approximateScoreQueue to the node's rowId and ordinal

reranker - A function that takes a graph ordinal and returns the exact similarity score

limit - The query limit

topK - The number of vectors to resolve and score before returning results

view - The view of the graph, passed so we can close it when the iterator is closed

Method Details

computeNext

protected RowIdWithScore computeNext()

Specified by:

computeNext in class AbstractIterator<RowIdWithScore>

close

public void close()

Specified by:

close in interface AutoCloseable

Specified by:

close in interface CloseableIterator<RowIdWithScore>

Overrides:

close in class AbstractIterator<RowIdWithScore>