If you were asked to design Qdrant's filtered-HNSW search from scratch, what core problem would you need to solve, and what naive approach would you reject first?

The core problem is: given a filter that matches a subset of points, find the top-k nearest neighbors among the matching points, without scanning the entire collection and without missing relevant results. The naive approaches are two. The first is post-filtering: run the ANN search without the filter, retrieve the top-k, then discard the ones that do not match. This fails because the top-k may contain few or no matching points, especially for selective filters, so the result set is incomplete or empty. It also wastes work on non-matching candidates. The second is pre-filtering with brute force: find all the points that match the filter (via the payload index), then compute the exact distances to all of them, then take the top-k. This is correct but expensive: if the filter matches a large fraction of the collection, the brute-force scan is a full scan. The correct solution is a filter-aware traversal: modify the HNSW search so that the filter is evaluated during the graph traversal, and the traversal continues until it has found enough matching points to return the top-k. This is what Qdrant does, and it is the core problem that the design must solve.

The mechanism that makes filter-aware traversal work is that the traversal maintains a candidate list and a result list, and the result list is populated only with points that pass the filter. The traversal continues until the candidate list is exhausted (no unexplored neighbor is closer than the worst result) or the result list has k matching points. If the filter is selective, the traversal has to explore more of the graph to find enough matching points, so the effective search breadth increases. The payload index helps by identifying the matching set and by pruning segments that cannot match. The naive approaches fail because they do not integrate the filter into the traversal: post-filtering decouples the filter from the search, so it can miss matching points that are not in the top-k; pre-filtering with brute force decouples the search from the graph, so it loses the sub-linear property. The filter-aware traversal is the only approach that preserves both correctness and sub-linear search. The design must also handle the case where the filter matches a very large fraction of the collection: in that case, the filter-aware traversal behaves like an unfiltered search, and the payload index may not help. And the case where the filter matches a very small fraction: in that case, the traversal must explore a large portion of the graph, and the cost can approach a full scan, which is why the planner may choose a pre-filtering strategy in that case.