You Asked for 40 Rows and Got 4: What a Filter Does to an HNSW Vector Search

Mostafa Dhouib·8 min read

You Asked for 40 Rows and Got 4: What a Filter Does to an HNSW Vector Search

The short answer. An approximate vector index explores a fixed-size neighbourhood of candidates and returns the best ones it found. When you add a filter, the usual implementation finds those candidates first and applies your filter afterwards, so whatever fails the filter is simply gone. At a filter that passes one row in ten, a reproduction on PostgreSQL 16.15 with pgvector 0.8.6 returned 3.93 rows on average against a request for 40, at the default ef_search. Nothing errors. You get a short list, and a short list looks exactly like a corpus that did not have much to say.

This one is responsible for a particular kind of wasted week, because the symptom points away from the cause.

Somebody builds retrieval over a corpus, scopes queries by tenant or document type or date, and the answers come back thin. Not wrong, thin. The model says it does not have enough information, or it answers from two chunks when it should have had twenty. The investigation goes to chunking, to the embedding model, to the prompt. None of those is it.

How the index actually answers a query

An HNSW index is a navigable graph. A search enters at an entry point and walks toward the query vector, keeping a working list of the best candidates it has seen. The size of that list is the ef_search parameter, and it is the thing that decides how much of the graph gets explored. When the walk stops improving, the index returns the best items from its list.

The important property is that ef_search bounds the exploration regardless of what you do with the results afterwards. The index does not know your filter exists. It finds its neighbourhood, and then the filter runs.

That is post-filtering, and it is the default behaviour.

Why the arithmetic is brutal

Suppose ef_search is 40 and your filter passes one row in ten.

The index explores and ends up with roughly 40 candidates. The filter then removes about nine out of every ten. You are left with about 4.

In the reproduction, the average was 3.93 rows returned against a request for 40, which is almost exactly what the back-of-the-envelope predicts. The number is not mysterious once you see the mechanism: you are sampling a filtered population through a window sized for an unfiltered one.

And it gets worse as the filter gets more selective, which is the opposite of what people expect. A tighter scope feels safer. A per-tenant filter in a system with a hundred tenants passes one row in a hundred, and the same window returns a fraction of a row on average, which in practice means frequently zero.

Why it is silent

Three reasons it survives.

The query succeeds. There is no error condition. Fewer rows than requested is a completely ordinary result from a LIMIT, because a corpus might genuinely not contain more matches.

The rows you do get are good. They are the nearest neighbours that passed the filter, so they are relevant. Nothing about the output looks degraded, it just looks sparse.

And the obvious explanation is wrong but plausible. A thin result set from a scoped query reads as "this tenant does not have much content", which is sometimes true and is the first thing anyone will believe.

How to tell in one measurement

Run the same query twice, once with the filter and once without, and compare the row counts against what you asked for.

Unfiltered returns 40, filtered returns 4: this is post-filtering, not a thin corpus.

Then confirm by raising ef_search substantially and re-running the filtered query. If the row count rises roughly in proportion, the index was the constraint. If it does not move, you genuinely do not have the content.

That second step matters because it distinguishes the two explanations, and they lead to completely different work.

The three fixes, and what each costs

Raise ef_search. Set it high enough that the post-filter survivors still fill your limit: roughly your desired row count divided by the filter's selectivity. For a one-in-ten filter wanting 40 rows, that is in the region of 400. This is the quickest fix and it costs latency, because the index explores proportionally more of the graph. It is the right answer when the filter is mildly selective.

Partition by the filter. If the filter is a tenant, a document type, or anything else with a small set of stable values, give each one its own index. The filter then becomes index selection rather than post-filtering, and inside each index there is nothing to filter out. This is the right answer for per-tenant scoping and is usually what multi-tenant retrieval should have been doing anyway, for isolation reasons that have nothing to do with recall.

Use iterative or filtered scanning where available. Newer pgvector versions can continue scanning until the limit is satisfied rather than stopping at a fixed neighbourhood. This changes the cost model, because the work now depends on selectivity rather than being fixed, and a very selective filter can scan a large fraction of the index. It is the right answer when selectivity varies unpredictably.

The choice is a trade between predictable latency and predictable recall, and it is worth making deliberately rather than inheriting the default.

The general lesson

An approximate index gives you an approximate answer within a budget you set. Every parameter that bounds the search is a recall decision disguised as a performance setting, and ef_search is the clearest example: it reads like a tuning knob and it determines whether your filtered query returns a usable result set at all.

The broader habit this argues for is measuring candidate counts at every stage of a retrieval pipeline rather than only evaluating the final answer. A stage that silently returns fewer candidates than the next stage needs is invisible in the output and obvious in a count.

The honest limit

The 3.93 figure is from my own reproduction on PostgreSQL 16.15 with pgvector 0.8.6, at the default ef_search, with a filter constructed to pass about 10 percent of rows. It is one configuration, and the exact number will move with your data distribution, how your filter correlates with vector position, and your index build parameters.

What generalises is the mechanism and its direction, not the number. If your filter correlates with the embedding space, say a tenant whose documents are topically distinct, the effect can be milder because the surviving neighbours cluster. If it is orthogonal to the embedding space, it behaves like the random case above.

Measure it on your own index. The two-query comparison above takes a minute.

FAQ

Why does my vector search return fewer rows when I add a WHERE clause? Because the index explores a fixed-size neighbourhood set by ef_search and your filter is applied to those candidates afterwards. Whatever fails the filter is gone, and nothing goes back to find replacements. A filter passing one row in ten against an ef_search of 40 leaves roughly 4 rows, which matches the 3.93 average measured in reproduction.

Is a thin filtered result set a sign of a small corpus? That is the plausible explanation and often the wrong one. Run the query with and without the filter and compare row counts, then raise ef_search and re-run the filtered query. If the count rises roughly in proportion, the index was the constraint rather than the content.

What should I set ef_search to when filtering? Roughly the number of rows you want divided by the filter's selectivity, so for 40 rows through a one-in-ten filter, in the region of 400. This costs latency in proportion, since the index explores more of the graph, and it is the right trade when the filter is mildly selective rather than extremely so.

Should I use one index per tenant for multi-tenant vector search? Usually yes, if the tenant set is reasonably stable. The filter becomes index selection rather than post-filtering, so there is nothing inside the index to filter away and recall is unaffected. It also gives you isolation at the storage layer, which is worth having for reasons unrelated to recall.

Does the problem get worse with a more selective filter? Yes, which is the counterintuitive part, because a tighter scope feels safer. A one-in-a-hundred filter against the same neighbourhood leaves a fraction of a row on average, which in practice means frequently returning nothing at all from a corpus that contains plenty of matches.

Why doesn't the database warn me about this? Because nothing has gone wrong by the database's rules. The index returned its best candidates within the budget it was given, the filter removed rows that did not match, and a result set smaller than the limit is an ordinary outcome of any query. There is no error condition to raise.