HNSW AnnIterator has no brute-force fallback at high filter ratios

[rere950303]

Description

HNSW AnnIterator has no brute-force fallback at high filter ratios. When the bitset filters out ≥93% of the points (kHnswSearchKnnBFFilterThreshold), FaissHnswIterator only sets accumulated_alpha = max and keeps traversing the graph. It visits almost every node while looking for the few unfiltered ones.

kNN Search already switches to brute force at the same threshold (WhetherPerformBruteForceSearch). #1534 / #1535 fixed the same gap for RangeSearch. As #1534 notes, operations that use the iterator directly are still affected ("This broader optimization will be addressed separately in a follow-up"). The existing unit test also says so: // Iterator doesn't have a fallback to bruteforce mechanism at high filter rate. (tests/ut/test_iterator.cc).

The main caller is Milvus search iterator V2. CachedSearchIterator calls index.VectorIterators() → AnnIterator on every page RPC (SearchOnIndex.cpp), and pymilvus 2.6 MilvusClient.search_iterator does one extra probe search when the iterator is created. So every page of a filtered search iterator pays the full-graph traversal.

Impact in production

This showed up after we upgraded Milvus 2.4.23 → 2.6.22 together with pymilvus 2.4 → 2.6:

• pymilvus 2.4 used the V1 iterator, which issues RangeSearch calls. pymilvus 2.4 also clamps ef to the batch size (16 in our case), so each call was a short, ef-bounded search. Brute force only applied at 97% (knowhere 2.3.14 hnswlib searchRange).
• pymilvus 2.6 uses the V2 iterator. It goes through AnnIterator, which has no brute-force fallback, keeps walking until the batch is filled, and passes the configured ef through (750 in our case).

(Corrected after review: an earlier version of this text attributed the old speed to a 93% brute-force switch.)

Our scalar filters are highly selective (well above 93% of each segment is filtered out). After the upgrade, the p99 latency of the HNSW collections searched with search_iterator rose by roughly an order of magnitude. Collections searched with plain Search were unaffected. Most of the slow requests were the topk=1 probe issued when the iterator is created.

Proposal

When the filter ratio reaches an iterator brute-force threshold (97%, per review in #1863; the kNN threshold of 93% was too early at typical ef), have FaissHnswIterator scan the unfiltered points once with the same storage distance computer (or the refine index when present, as the brute-force kNN Search does) and hand them to IndexIterator in a single batch, instead of traversing the graph. IndexIterator already keeps the results in a heap, and refine / label mapping / result id mapping are unchanged.

Benchmark

Synthetic, 200k × 768 fp32, COSINE, HNSW M=16 / efConstruction=200, ef=750, random bitset, 20 queries, time to get the first 16 results from AnnIterator (best of 3), aarch64 10 cores. "graph" = current main, "brute force" = proposed.

filter ratio	iterator graph (ms/q)	iterator brute force (ms/q)	speedup	recall@16 graph	recall@16 brute force
90.0%	21.48	22.66	— (unchanged path)	0.847	0.847
95.0%	28.05	unchanged	— (below the 97% threshold)	0.872	unchanged
99.0%	56.01	1.33	42.2x	0.931	1.000
99.9%	97.75	1.08	90.9x	0.969	1.000