Document 14 · Quick learnSelectivity first · Islands, not just bits · The dashboard shows the whale
One numberdecides every query
One number decides every filtered query, and the failure mode is silence. Multi-tenancy is the same problem with the filter always present and the values wildly unequal.
“A private room fixes what you find. Only a rule at the door fixes how long you wait.”
0.4 survivors
from 40 candidates at 1% selectivity
1.00 recall
brute force — the only guarantee here
10–20k rows
the promotion threshold, both vendors
1.8% of traffic
the tier that can be wrong forever
Selectivitythe one number that decides everything
The fraction of the table that passes the filter. Nothing else about filtered search matters until you know it — not the engine, not the parameters, not the index type. Two filters on the same table can need opposite strategies, and this is the only thing separating them.
A
tenant = A, the largest tenant4,000,000 rows · one in every 2.5 · 25 candidates for 10 results
40%
B
department = radiology1,000,000 · one in 10 · 100 candidates
10%
C
published in the last 30 days100,000 · one in 100 · 1,000 candidates
1%
D
published since yesterday5,000 · one in 2,000 · 20,000 candidates
0.05%
E
document = one specific file50 · one in 200,000 · 2,000,000 candidates
0.0005%
Read the last row
With fifty matching rows in ten million, one candidate in every two hundred thousand is a survivor — so you would need to walk to roughly two hundred thousand candidates before you expected to see one.
No sensible ef gets there. The graph is simply the wrong tool for that query
Two words that must stay apart
index
The ANN structure — the HNSW graph over the vectors.
Not the payload index
payload index
A secondary structure over one payload field, so a predicate can be answered without scanning ten million rows.
It does nothing to the graph
candidate
A row the graph walk reached and scored.
Not a survivor
survivor
A candidate that also passes the filter.
Not a candidate
Five ways to answer a filtered queryand the one where most production bugs live
1 · Post-filter
Walk as normal, then apply the predicate to the ef candidates you got.
Needs no engine support. And at 1% selectivity, 40 candidates × 0.01 = 0.4 survivors on average — the result set is one row and nothing reports the shortfall
2 · Brute force
Use the payload index to find the exact survivor set; score every one; sort; take k.
The graph is not consulted at all — so recall is exactly 1.00. The only technique here with a recall guarantee
3 · Stepping-stone
The walk visits non-matching neighbours to keep moving, but only matching ones may enter the result.
A batch is returned, filtered; if short of k the walk resumes from where it stopped.
pgvector iterative scan
5 · Route instead of filter
Make the filter key the shard key, so the filter becomes a routing decision.
Costs nothing, because selectivity inside the chosen shard is 100%
The bit check is free. The extra steps are not.
A bitmap is one bit per row — ten million rows is 1.25 MB, small enough to live in L2 cache. The walk tests one bit per neighbour visited: a fraction of a nanosecond, against the ~500 ns of the distance computation beside it.
So the answer to “does the filter live in the graph node?” is no. The payload lives with the row, the filter arrives with the query, and the bitmap is built per query from the payload index and thrown away
The precondition: no payload index, no brute-force plan
“Find the 50 survivors” means a payload index lookup. Without one it means reading ten million payloads — seconds — and in pgvector the planner will not even consider the plan.
Two rules in tension: index every field you filter on (Qdrant calls this the single biggest speed-up for filtered queries, larger than any HNSW tuning) and do not index fields you never filter on, because each is resident memory that could have been vectors
Workedcardinality picks the structure · 20 departments → 20 bitmaps of 1.25 MB, ANDed in microseconds · 200,000 doc_ids → a bitmap per value would be 250 GB, so it must be an inverted listMilvus makes it explicit: bitmap below ~500 distinct, inverted above
The connectivity problemwhat makes this genuinely hard rather than merely fiddly
The walk lands on a match
Three matching nodes exist, spread far apart — and the edges between them run through non-matching nodes.
The dilemma
A walk that only steps on matches gets stranded on one island. A walk that ignores the filter wastes almost every step.
Build-time answer
Qdrant’s filterable HNSW adds payload-aware edges when the graph is built — payload_m controls how many.
Query-time answer
ACORN evaluates neighbours-of-neighbours, so the walk can jump over a ring of non-matches.
Weaviate v1.27+, Qdrant 1.16+
Anatomy of one filtered query, inside the engine
1
The request carries the vector, the filter and k together. Nothing is pre-computed by the caller.
2
Each predicate answered by its own payload index: 4,000,000 ids for the tenant, 800,000 for the date range.
3
Both turned into bitmaps and ANDed. 320,000 bits set — 3.2% selectivity.
4
The planner reads the popcount. Above the brute-force threshold → a bitmap-guided walk.
5
The walk extends until ten matching candidates are found — ~310 candidates, eight times an unfiltered walk.
The rule Lucene implements that everyone else bakes into a constant
Per segment: if the matching document count is small, skip the graph and brute-force the matches. Otherwise walk with the bitset — but if the number of nodes explored exceeds the number of survivors, abandon the walk and brute-force them instead, because at that point brute force is provably cheaper.
A live version of the crossover, decided mid-query rather than by a threshold set at configuration time. It is also why Elastic warns that, unlike ordinary queries, a more restrictive kNN filter can be slower
What each engine actually doesand the gotcha in each
Qdrant
Filterable HNSW via payload_m; ACORN since 1.16.
Brute-force switch:full_scan_threshold, 10,000 KB — about 1,700 vectors at 1536-d Gotcha: a payload index declared after ingest needs a graph rebuild — it does not catch up on its own
Weaviate
Sweeping or ACORN over a Roaring allow-list.
Switch:flatSearchCutoff, 40,000 objects Gotcha: older clients still default to sweeping — check the collection config
Elasticsearch
Bitset pre-filter inside the kNN walk, per Lucene segment.
Switch: live — matches ≤ num_candidates, or nodes explored > matches Gotcha: a bool.filter wrapped around a knn query is a post-filter and can return fewer than k
Milvus
Bitset pre-filter, or iterative filtering for expensive expressions.
Declare: a scalar index per field — bitmap under ~500 distinct, inverted above Gotcha: iterative filtering processes one entity at a time
Pinecone
Single-stage; per-cluster metadata statistics skip clusters with no possible match.
Declare: store unordered numerics (ids) as strings, or the min/max statistics are defeated Gotcha: a very selective filter can leave the chosen clusters unable to fill top_k
pgvector
No vector planner at all. The ordinary Postgres planner chooses using ordinary row-count statistics.
And it has no idea what selectivity means for HNSW
The order of escalation in pgvector
1
Raise hnsw.ef_searchno schema change, roughly linear cost
free
2
Enable hnsw.iterative_scan0.8+, capped at 20,000 tuples
a setting
3
Add a B-tree on the filter columnthis is what unlocks the brute-force plan for tight filters
an index
4
ANALYZE after loadsso the planner actually picks it
a job
5
A partial HNSW index per big valuea graph in which everything qualifies
per value
6
Partition or shard by the keyat which point the filter has become routing
a redesign
Filtering meets shardingthe worst combination in this track
A filter’s selectivity is computed per shard, and hash sharding scatters every filter value evenly — so a 1% filter is 1% on each of four shards. Each shard walks its own graph under the same tight filter. The over-fetch and the connectivity problem are paid four times.
Hashed shards, tight filter
100,000 rows pass, spread evenly.
Per shard: 25,000 survivors of 2.5M — still 1%
Each shard: an iterative walk, ~1,000 candidates for 10 hits
Coordinator merges 4 × 10 → 10. Total walk work ~4×
You pay the slowest-shard tail and the extended walk, four times over
Filter key = shard key?
Tenant-keyed shards, filter = tenant
Routed to one shard.
Selectivity inside that shard is 100%
A plain walk, no filter cost at all
Three shards not touched
Filtering has become routing
Two cases where sharding helps, and one where it is the worst available
When the filter key is the shard key, filtering becomes routing and costs nothing — Qdrant shard keys, Weaviate multi-tenancy, Pinecone namespaces, Postgres partitions. When each shard can independently choose to brute-force its own survivors — Lucene’s per-segment rule — sharding parallelises the brute force.
Everything else, sharding makes worse. Fan-out plus a tight filter is the worst combination in this track
Tenant skewthe same query, the same index, four different outcomes
Twenty tenants own two thirds of the data, and nearly ten thousand share the remaining seventh. Nothing about multi-tenancy makes sense until you hold that in your head.
W
whale · 4,000,000 rows40% selectivity · 16 survivors in 40 candidates · 25 candidates for 10
plain walk
L
large · 150,000 rows1.5% · 0.6 survivors · 667 candidates for 10
iterative scan
M
medium · 10,000 rows0.1% · 0.04 survivors · 10,000 candidates
at the line
S
small · 138 rows0.0014% · 724,638 candidates — a walk is useless
brute force
The counter-intuitive result: the tail is not the hard part
A 138-row tenant is 138 × 1,536 = about 212,000 multiply-adds. That is microseconds, and it is exact. The tail is easy once the engine has a brute-force fallback.
The hard band is the middle — ten thousand to a couple of million rows, too big to brute-force cheaply and too small for a plain walk. On the reference stack that is 180 tenants carrying 18% of the data, and they are precisely the ones nobody notices
Recall is no longer one number, and the dashboard shows the whale’s
“Our recall@10 is 0.96” is a fine sentence for a single-tenant store. Here it hides everything: the tail is 1.00 because it is brute-forced, the whale is 0.96 because it gets a plain walk, and the middle tier sits between 0.85 and 0.97.
The dashboard number is the whale’s number, because the whale is 40% of the queries. The medium tier is 1.8% of traffic, so it can be measurably worse forever and never move the average. Measure per tenant and report p50 and p10 across tenants
The tiered designand the promotion threshold
Rooms for the few families with thousands of books; one shared hall with name tags for everyone else; a rule at the door about how many requests each family may make. Every major vendor has now built some version of exactly that.
Qdrant · tiered multitenancy, v1.16
A shared fallback shard holds small tenants; large tenants get a dedicated shard.
Promotion at ~20,000 points. Stay under ~1,000 dedicated shards per cluster
Weaviate · native MT + dynamic index
Every tenant is its own shard. A tenant starts flat — vectors on disk, brute force — and converts.
Default conversion at 10,000 objects. Requires async indexing
Milvus · partition key
Hash tenants into num_partitions (default 16); with isolation, a separate sub-index per key.
1,024 manual partitions per collection
Pinecone · namespaces
One namespace per tenant, physically separate storage.
No shared graph, so no size tiering. 100,000 namespaces per index
pgvector · hand-built
Shared table with a B-tree on tenant_id and iterative scan for the middle.
The threshold is yours. A partial index per tenant stops being sane past a few dozen
The tenant bitmap, and why the numbers work
Uncompressed, 1.25 MB per tenant regardless of size — ten thousand of those is 12.5 GB.
Roaring makes a 138-row tenant ~1 KB, a 10,000-row tenant ~20 KB, the whale under a megabyte. All ten thousand come to ~20 MB, resident
The sentence for the interview
“Promote a tenant to its own graph when it leaves the brute-force band — around ten to twenty thousand rows — because below that a shared table answers it exactly in microseconds, and above that a filtered walk starts costing recall. Both Qdrant and Weaviate default to that line.”
Note what that is not: it is not “when the tenant has more data than a graph’s overhead”. Overhead sets an upper bound on how many graphs you can afford; the crossover sets where each one earns its place
Isolation is two different thingsand an architect answer names both
Data isolation
Tenant Z never receives a row of tenant A.
Enforced: in the store — filter, route or collection — and in the read-time join
Failure mode: a leak — a security incident
Which model helps: collection > partition > filter
Who owns it: the platform team, and they must be able to prove it
People say “tenant isolation” and mean either of two unrelated guarantees.
Performance isolation
Tenant A’s traffic never slows tenant Z.
Enforced:above the store — API gateway, queue, quota
Failure mode: a slowdown — an SLA incident
Which model helps:none fully. Dedicated replicas help; rate limits are the real fix
Who owns it: the API team — it is a product policy, not a store property
The noisy neighbour, and what the stores actually offer
Every tenant’s query lands in the same queue and competes for the same CPU and page cache. A whale at high QPS with wide walks fills the queue, and a tail tenant’s microsecond query waits tens of milliseconds behind it. A private room fixes what you find; only a rule at the door fixes how long you wait.
None of the engines gives a per-tenant CPU share inside a shared collection. That is the statement to make — and then qualify, because the honest fix is a per-tenant rate limit and a fair scheduler at the API layer, plus physical separation for the whale
Never trust the filter alonefour layers, and only one is correct by construction
In the shared-table model the entire security boundary is one predicate that application code must remember to add to every query. Code paths multiply — admin tools, batch jobs, a new endpoint, a debugging script — and one of them will forget.
1 · Tenant-scoped credential
The store itself refuses other tenants.
Weaviate requires a tenant per call, Pinecone a namespace, Qdrant a JWT with a payload claim, Postgres a role
2 · Row-level security
The database adds the predicate, so forgetting it is impossible.
ENABLE then FORCE ROW LEVEL SECURITY — so the table owner is subject to it too
3 · Read-time join
The final SELECT against the system of record re-checks the tenant on the ids that came back.
The only layer that is correct by construction
4 · The filter in the query
Necessary for recall and cost.
And insufficient for security
RLS gives correctness, not recall
The policy is inlined into the plan as an ordinary Filter, so the nearest-neighbour query still walks the index broadly and filters afterwards — it is post-filtering with a predicate you cannot forget.
So pair it with an explicit filter for recall, and keep RLS for correctness
Why the read-time join fixes more than the leak
Whatever the vector store returns, the last step re-selects those ids from the relational source of truth with the tenant predicate applied. If the store leaked, the join drops the leak.
And it fixes the drift problem too: a document deleted in Postgres leaves its vectors behind, and a tenant reassignment leaves the old tenant in the payload. The vector store is a cache of candidate ids; the database is the source of truth for who may see them
Answer it out loudthe ninety-second version, then six questions
“Selectivity decides everything, and nothing else matters until you know it. Above about ten per cent, a plain walk with post-filtering is fine. Below about a thousand rows, brute-force the survivors — it is exact, it is microseconds, and it is the only technique here with a recall guarantee. In between you need the engine to filter during the walk, using a per-query bitmap built from a payload index — and the hard part is not the bit check, it is connectivity: the matching nodes may be islands joined by non-matching ones, which is what filterable HNSW and ACORN exist to solve. Multi-tenancy is that same problem with the filter always present and the values wildly unequal — so you tier it: shared table for the tail, dedicated graph above the brute-force band, around ten to twenty thousand rows.”
Six questions, and the spine of each answer
Architect
How do you handle a filtered vector search?
Ask for selectivity first — nothing else about the design is decidable without it
>10%: a plain walk, post-filter is fine
<~1,000 rows: brute-force the survivors — exact, microseconds, recall 1.00
In between: filter during the walk, from a per-query bitmap built from a payload index
And the precondition everyone forgets: no payload index, no brute-force plan. Index every field you filter on, and none that you do not.
Architect
Post-filtering returns fewer than k results. Why?
Because the walk had no knowledge of the filter — it returned the ef nearest, then the predicate was applied to those
Selectivity × candidates is the whole story: 40 candidates at 1% = 0.4 survivors
The result is one row, the application shows one row, and nothing reports the shortfall
Which is why this is where most production filtered-search bugs live: it needs no engine support, so it is what every prototype does, and it fails silently.
Architect
Why is a tight filter sometimes slower?
Connectivity. The matching nodes may be islands joined by non-matching ones
A walk that only steps on matches gets stranded; one that ignores the filter wastes almost every step
So the walk extends — roughly 1 ÷ selectivity longer than unfiltered
Elastic warns explicitly that a more restrictive kNN filter can be slower, unlike ordinary queries
The fixes: filterable HNSW (payload-aware edges at build time) or ACORN (neighbours-of-neighbours at query time) — or, past the crossover, stop walking and brute-force.
Architect
Design multi-tenancy for ten thousand tenants with one whale.
Tier it. Shared table for the tail, dedicated graph for the large ones
Promote when a tenant leaves the brute-force band — ten to twenty thousand rows. Both Qdrant and Weaviate default there
Below that a shared table answers exactly, in microseconds. Above it a filtered walk starts costing recall
And the whale gets its own shard, placed on its own node if performance isolation matters
Then name the two isolations separately: data isolation lives in the store and the read-time join; performance isolation lives above the store, and no engine gives a per-tenant CPU share.
Eng manager
Our recall@10 is 0.96. Are we fine?
In a multi-tenant store that is the whale’s number, because the whale is 40% of queries
The tail is 1.00 because it is brute-forced. The middle tier sits between 0.85 and 0.97
The medium tier is 1.8% of traffic, so it can be measurably worse forever and never move the average
So: measure per tenant and report the distribution — p50 and p10 across tenants, not one mean. And the hard band is the middle, not the tail: 180 tenants carrying 18% of the data, and they are precisely the ones nobody notices.
Eng manager
How do you prove a tenant cannot see another’s data?
Not with the query filter — that is necessary for recall and cost, and insufficient for security
Tenant-scoped credentials, so the store itself refuses
Row-level security, so forgetting the predicate is impossible — with FORCE, so the owner is subject too
A read-time join against the system of record, which is the only layer correct by construction
Plus canary documents in CI asserting synthetic tenants cannot retrieve them. The filter is one predicate that application code must remember on every path — and one path will forget.
Fast answersthe eight that come up most
QWhat is the single biggest speed-up for filtered queries?
A payload index on every field you filter on — Qdrant’s own FAQ says larger than any HNSW tuning. Without one, “find the survivors” means scanning ten million payloads, and in pgvector the planner will not even consider the brute-force plan.
QWhich payload index type?
Cardinality picks it. Twenty departments → twenty bitmaps of 1.25 MB, ANDed in microseconds. Two hundred thousand doc_ids → a bitmap per value would be 250 GB, so an inverted list or a tree. Milvus makes the rule explicit: bitmap below ~500 distinct, inverted above.
QDoes the filter live in the graph node?
No. The payload lives with the row, the filter arrives with the query, and the bitmap is built per query from the payload index and thrown away. The bit check is a fraction of a nanosecond against ~500 ns for the distance computation beside it.
QI declared a payload index after ingest and nothing improved.
In Qdrant, an index declared after ingest needs a graph rebuild — it does not catch up on its own. This is the single most common “we did that and it did not help” in this area.
QWhy can a more restrictive filter be slower?
Because of connectivity: the walk has to travel further to find k survivors, roughly 1 ÷ selectivity longer. Unlike ordinary database queries where a tighter predicate is cheaper, here it is often more expensive — until you cross the line where brute force wins.
QWhere does the promotion threshold come from?
The brute-force crossover, not graph overhead. Below ~10–20k rows a shared table answers exactly in microseconds; above it a filtered walk starts costing recall. Overhead sets an upper bound on how many graphs you can afford; the crossover sets where each one earns its place.
QDoes row-level security fix my filtered-search recall?
No. RLS gives correctness, not recall — the policy is inlined as an ordinary Filter, so the query still walks broadly and filters afterwards. Pair it with an explicit filter for recall.
QIs a namespace or collection per tenant always better?
For data isolation and lifecycle, yes — deletion is a DROP and is trivially provable. For performance isolation, not on its own: read and write unit limits often apply per index rather than per namespace, and none of the engines gives a per-tenant CPU share.
Selectivity decides everything, and the failure mode is silence. Post-filtering needs no engine support, so it is what every prototype does — and at one per cent selectivity forty candidates yield 0.4 survivors, the application shows one row, and nothing reports the shortfall. Below about a thousand survivors the right answer is to stop walking and brute-force them, which is exact and microseconds. Multi-tenancy is that same problem with the filter always present and the values wildly unequal — so tier it at the brute-force crossover, and measure recall per tenant, because the dashboard number is the whale’s.