LSM_VECTOR: a query with an allow-list narrower than k costs a full index scan, every time #5748

Found while measuring the brute-force fallback for #5558 (PR #5739). Pre-existing on main, not introduced by that PR - measured both ways, see below.

What happens

findNeighborsFromVector(query, k, efSearch, allowedRIDs) decides whether to fall back to a brute-force scan by comparing the result count against min(k, availableVectors). allowedRIDs does not enter that expectation, so a query restricted to fewer RIDs than k can never meet it: it looks permanently short, and the fallback walks every ordinal in the index on every query.

Measured

50,000 vectors, 128 dimensions, INT8, k=10, allow-list of 3 RIDs, best of 3 rounds of 300 queries:

276x, and it is not a tail: the scan fires on literally every query.

Confirmed pre-existing by restoring the pre-#5739 guard (availableVectors = ordinalMap.length plus the results.size() < availableVectors * 8 / 10 term) and re-measuring: 26,602 us/query, 900/900 scans. The old 80% term was true here too, so it never suppressed anything - the two are the same within noise.

Why the obvious fix is not obviously right

Capping the expectation at allowedRIDs.size() removes the scan, and I tried exactly that while working on #5739 - then reverted it, because a test showed what it costs. With a 3-RID allow-list on a tombstoned index the graph walk returns 2 of the 3: a restrictive Bits filter makes JVector's local-maximum heuristic stop expanding early, and the fallback is what completes the answer. Cap the expectation and that query returns 2 instead of 3.

So this is a real trade, not an oversight to patch:

• cap by allowedRIDs.size() - fast, silently lossy when graph recall under-fills the allow-list;
• cap by the number of live allowed RIDs - accurate, costs a location lookup per allow-list entry, which for a large allow-list is worse than the scan it saves;
• scan only the allow-list rather than every ordinal - the fallback walks ordinalMap and tests membership; walking the allow-list and resolving each RID to its ordinal instead would make the fallback O(allow-list) rather than O(index), which for a narrow allow-list is the interesting direction. Needs a RID -> vectorId lookup, which VectorLocationIndex already maintains as a reverse index (ridToVectorIds, added in LSMVectorIndex.remove() scans all vector ids per call: any record update on a vector-indexed type is O(index size), bulk edge-connect degrades quadratically #5318).
• raise efSearch when the filter is restrictive so the graph walk finds them all and the fallback never triggers.

The third looks most promising: it keeps the completeness the fallback provides and removes the part that scales with the index rather than with the query.

Observability

getStats() gained a bruteForceScans counter in #5739, so this is now measurable on a live index rather than only visible as a WARNING log line. Anyone seeing filtered vector queries run slow should check it first.