A filter matches 0.1% of 100M vectors. Predict whether pre-filter brute force or post-filter ANN serves it faster.

Predict output·Medium·4.0 · 0·~2 min·Asked atLlamaIndex Observe Ai Razorpay

Attempt it

A query carries a metadata filter matching just 100,000 of 100M vectors (0.1% selectivity). Option A: pre-filter, then brute force exact search over only the matching vectors (1024-dim float32, SIMD distance kernels available). Option B: run HNSW over the whole index and post-filter the candidates, oversampling until k=20 filtered results survive. Predict which option wins and roughly what each costs per query.

The two strategies have wildly different costs at 0.1% selectivity. **Option B (post-filter ANN) is the bad choice.** HNSW returns candidates in score order without knowing the filter. Each candidate survives the metadata filter with probability 0.001. To get 20 survivors, you need on the order of 20 / 0.001 = 20,000 raw candidates. HNSW is not designed to return 20,000 ranked candidates; the search list (`ef_search`) is usually in the hundreds, and pushing it into the tens of thousands tanks latency and recall. **Option A (pre-filter brute force) is the good choice.** The metadata filter narrows the candidate set to 100,000 vectors. Brute force means computing the query-to-vector distance for every one of them. Each distance is a dot product over 1024 float32 values. With SIMD (AVX2 or AVX-512), modern CPUs do this at billions of operations per second. 100k distances is about 100 million floating-point operations; that finishes in a few milliseconds, with perfect recall. **Why selectivity matters.** Below roughly 1 to 5 percent selectivity, the crossover favours pre-filter exact scan. Above that, the ANN cost over the full corpus is small enough that post-filter wins. Production engines (Qdrant, Weaviate, pgvector planners) detect the crossover and switch strategies automatically based on estimated filter cardinality.

**Option A (pre-filter brute force) wins decisively at 0.1% selectivity.** The arithmetic on each side: **Option A cost.** 100k vectors at 1024 dims. Reading the vectors is about 100k x 1024 x 4 = 400 MB; SIMD distance computation processes 8 to 16 floats per cycle. On a modern CPU, 100 million floating-point ops finishes in single-digit milliseconds. Recall is exactly 1.0. The bottleneck is memory bandwidth for the vector reads; if the working set fits in cache, the scan is faster still. **Option B cost.** HNSW must return enough unranked candidates that 20 of them pass the metadata filter. Pass rate is 0.001, so the expected number of candidates needed is 20 / 0.001 = 20,000. The HNSW `ef_search` parameter governs how many candidates the search list holds; typical values are 64 to 512. Pushing `ef_search` to 20,000 means the search behaves more like a wide BFS than an HNSW graph walk, and the per-query cost grows roughly linearly with `ef_search` after a point. Worse, recall on the top 20 filtered results degrades because the candidates returned at high `ef_search` are not necessarily the true global nearest neighbours within the filtered set. **The crossover.** Selectivity matters more than absolute corpus size for this decision. The crossover is roughly: $$\text{pre-filter wins when} \quad N_{\text{filtered}} \cdot c_{\text{distance}} < N_{\text{ANN-candidates}} \cdot c_{\text{graph-step}}$$ At 0.1% selectivity the left side is small (100k cheap distance computations) and the right side is large (tens of thousands of graph walks). Pre-filter is the clear winner. The crossover moves around as selectivity rises; above 1 to 5 percent, post-filter ANN over the whole index becomes competitive again.

TL;DR

Pre-filter brute force wins at 0.1% selectivity: 100k SIMD dot products in milliseconds with perfect recall, versus post-filter ANN needing ~20,000 candidates that HNSW cannot deliver gracefully.

Memory aid

Easy to grasp

Picture searching for the tallest person at a stadium of 100,000 spectators. Two strategies. One: ask everyone wearing a red hat (you know there are only 100 of them) to line up and pick the tallest. Two: scan the whole stadium roughly, write down anyone tall-looking, then check which ones happen to have red hats, repeating until 20 of your tall candidates also wear red. If red hats are rare (one in a thousand), the first strategy finishes in seconds with the right answer. The second strategy spends ages scanning and most of the candidates fail the red-hat test, so you keep going. Vector databases face the same choice every time a filter is very selective.

Key concepts

Vector Databases

Concept explanation~2 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

The brute-force versus ANN crossover for filtered queries is one of the most consequential and most overlooked decisions in production vector search. Teams pick one strategy at architecture time, ship it, and pay for it in tail latency on every query whose selectivity sits on the wrong side of the crossover. The right framing is to recognize that no single strategy is best; the strategy depends on per-query filter cardinality, and serious engines plan per query.

This section walks through the cost models for the three candidate strategies (pre-filter exact, post-filter ANN, filtered ANN), shows where each one wins, and discusses how real engines make the choice. The arithmetic is straightforward once the variables are named; the operational discipline is to never commit to one strategy globally.

Cost model: pre-filter exact scan

Pre-filter exact means apply the metadata filter first, then compute exact distances against the surviving vectors.

Filter application. A metadata index (B-tree on a scalar column, inverted index on a tag column, partition map on a partition key) identifies the matching vector IDs. At 0.1% selectivity, this returns 100,000 IDs out of 100M.

Distance computation. For each surviving vector, compute the query-to-vector distance. At 1024 dims float32, each distance is a 1024-element dot product. SIMD instructions (AVX2, AVX-512, NEON) process 8 to 16 floats per cycle; at modern clock speeds, a single CPU core can do roughly 10 billion floating-point operations per second on inner-product workloads.

Per-query cost.

c = N_{\text{filtered}} \cdot d \cdot \text{(flops per dim)} = 100{,}000 \cdot 1024 \cdot 2 \approx 2 \times 10^8 \text{ flops}

Divided by 10 billion flops per second: roughly 20 milliseconds on a single core, single-digit milliseconds when SIMD and parallelism kick in.

Memory bandwidth. Reading the vectors is 100k x 4 KB = 400 MB. Modern memory bandwidth is tens of GB per second, so the read finishes in 10 to 30 milliseconds if the data is cold. If the filtered vectors are hot in cache, the read is free.

Recall. Exactly 1.0. Brute force is exact by construction.

Caveats. Storage layout matters. If the filtered vectors are packed contiguously (clustered, partitioned, or sorted by the filter column), the scan is sequential and bandwidth-friendly. If they are scattered, the scan is random I/O and pays a much higher per-byte cost. Cluster by frequently-filtered columns when possible.

Cost model: post-filter ANN with oversampling

Cost model: filtered ANN with in-graph pruning

Production planner discipline

Low-selectivity routing rules and the 2026 cost tradeoff

Situations where this technique stops working.

2–4 min · Everything important, quickly.

Real products, models, and research that use this idea.

Qdrant has an explicit query planner that estimates filter cardinality and switches between pre-filter exact scan and filtered HNSW traversal automatically
pgvector with HNSW now supports iterative scans that traverse the index while applying filters, with planner hints when statistics are wrong

What an interviewer would ask next. Try answering before peeking at the approach.

QWhat changes if the 100k filtered vectors are scattered across disk rather than packed together?

The scan turns into random reads, which are 100 to 1000x slower than sequential reads on disk. The arithmetic still says milliseconds, but the wall-clock time can be hundreds of milliseconds. The fix is storage layout: cluster or partition by the filter column.

1 more follow-up an interviewer would ask next. Sign in to reveal them.

Red flags & common mistakes

The phrases that signal junior thinking. Click to expand.

Most common mistake

Defaulting to ANN regardless of selectivity, then watching latency explode as oversampling factors balloon past what HNSW search lists can deliver.

60 second bullets to scan on the way to the call.

Why selectivity determines the right filter strategy, not absolute corpus size
How to compute the post-filter oversampling factor from k and selectivity

Primary sources. Browse if you want the original framing.