At high selectivity the exact scan beats the index outright

An approximate index exists to avoid comparing the query against everything. The saving is real when everything is ten million vectors and illusory when the predicate has already reduced everything to a few thousand, because at that size comparing against all of them is a short loop. This chapter is about the size at which the loop wins, how to compute that size rather than guess it, and what has to exist in the request path for a system to notice which regime a given query is in.

Two terms carry the argument. An exact scan — brute force — scores the query against every eligible vector and sorts, with no index involved and no approximation anywhere. Cardinality is the count of documents a predicate matches, the same quantity as selectivity but expressed as a number of documents rather than a fraction, and it is the number a system needs in order to choose between plans.

What a few thousand vectors actually costs#

Take a filter that leaves five thousand eligible documents in an index of 768-dimensional vectors. Three numbers describe the work, and each follows from the one before.

The bytes come first. A vector is 768 components, each a float32, which is four bytes, so one vector is 768 multiplied by 4 — a little over three kilobytes. Five thousand of them is five thousand times that, which is 15.4 MB. Nothing about this depends on the index; it is the size of the raw data the predicate selected.

The arithmetic comes second. Scoring one vector against the query is one multiply-accumulate per component, so 768 of them, and five thousand vectors is five thousand times 768, which is 3.84 million multiply-accumulate pairs. A single core running a BLAS sgemv — the standard single-precision matrix-times-vector routine that every numerical library ships — gets through that in a few hundred microseconds.

The third number is the one that governs, and it is why the second one barely matters. Reading 15.4 MB out of memory at a realistic 20 GB/s of single-thread bandwidth takes 15.4 MB divided by 20 GB/s, which lands around 0.8 ms. The arithmetic finishes in a few hundred microseconds and the memory read takes roughly twice that, so the operation is bound by moving the bytes rather than by multiplying them. Every later argument in this chapter is a bandwidth argument for that reason.

Set 0.8 ms beside the previous chapter's sweep, which spent 62 ms at comparable selectivity and returned 4.6 results out of 10 with recall 0.27. The loop returns 10 out of 10 with recall 1.0, seventy times faster.

import numpy as np

def exact_top_k(q: np.ndarray, ids: np.ndarray,
                mat: np.ndarray, k: int = 10):
    """mat: (n, 768) float32, L2-normalised. q: (768,) normalised."""
    scores = mat @ q                     # one BLAS call
    if k < len(scores):
        part = np.argpartition(-scores, k)[:k]      # O(n), no full sort
        part = part[np.argsort(-scores[part])]
    else:
        part = np.argsort(-scores)
    return ids[part], scores[part]

# eligible ids come from the metadata store, not the vector index
ids, mat = store.gather(tenant_id="acme", doc_type="msa",
                        jurisdiction="DE")   # (5_014, 768)
top_ids, top_scores = exact_top_k(q_vec, ids, mat)

Nothing in that function is approximate, which removes an entire category of problem. There is no ef_search to tune, no cliff to measure, no gap between what the index found and what exists, and the result count is min(k, n_eligible) by construction rather than by luck. The cost is linear in the number of eligible vectors, and linear is fine when the number is small.

Where the crossover sits#

Brute force stops winning at a point you can compute from two quantities: the bandwidth available to the scan and the latency of the approximate plan it is replacing. The reasoning is one substitution. An approximate query takes some fixed time regardless of how many documents are eligible, because its cost is set by its budget rather than by the predicate. A scan's time is the bytes it reads divided by the bandwidth. Set the two equal and solve for the bytes.

Put the usual numbers in. If an ANN query takes 10 ms and a scan reads at 20 GB/s, then the scan spends its 10 ms reading 10 ms multiplied by 20 GB/s, which is 200 MB of vectors. Convert that budget from bytes to documents by dividing by the bytes per vector computed above — the same three-kilobyte figure — and 200 MB comes to about 65,000 vectors. Below that the scan is faster and exact; above it the index wins.

That per-vector size is worth holding onto, because it turns up twice in this chapter doing two different jobs, and the fact that it is the same number both times is not a coincidence. Here it converts a byte budget into a document budget. It appears again below as the size of an individual random read, because a scattered gather fetches one vector at a time and a vector is what it is.

Changing the vector's size moves the crossover in exact proportion, because the crossover is a byte budget divided by bytes per vector. Halving the dimension halves the bytes per vector and therefore doubles the crossover. Storing int8 instead of float32 puts one byte where four were, which quarters the bytes per vector and quadruples the crossover, to roughly 260,000 vectors for 768-dimensional int8. Parallelise the scan across four cores and the bandwidth term moves instead, with the same effect.

The practical crossover is lower than the arithmetic suggests, because gathering the eligible vectors is not free. If they are scattered across a memory-mapped file, the scan is doing random reads of 3 KB each rather than a sequential sweep, and effective bandwidth drops by an order of magnitude. Engines that support this plan well keep vectors clustered by the attributes people filter on — the same idea as a clustered index in a relational store — so that a tenant's or a document type's vectors are contiguous. Where they are not clustered, measure the gather separately from the scan, because it usually dominates.

The scan column does not scale linearly with the document count, and that is the most instructive thing in the table. Five thousand vectors take 0.8 ms; a hundred times as many take not eighty milliseconds but 1.6 s, and eight hundred times as many take 10 s rather than the six hundred milliseconds bandwidth alone would predict. The scan arithmetic is linear, so the departure is the gather, and the shape of the departure is the point: the penalty is worst in the middle of the range. At five thousand documents the eligible vectors were handed over as one contiguous block, which is what the (5_014, 768) matrix in the code above is. At a hundred thousand they are scattered thinly across the whole store and every read is a separate three-kilobyte fetch. At four million they are dense enough that touching them again resembles a sequential sweep. Whether a scan is cheap is therefore a question about memory layout and not only about n, which is why the paragraph above says to measure the gather separately.

Work the canonical case through that table. A filter matching 0.05% of a 10M-document index leaves 5,000 eligible documents. Post-filtering returns nothing, because a top-10 draws ten multiplied by that selectivity, which is 0.005 expected matches — one page in two hundred contains anything at all. Filtered ANN sits at the bottom of the cliff and returns a handful of results with recall under 0.3 while taking sixty-odd milliseconds. The exact scan reads 15 MB, returns ten results with recall 1.0, and finishes in under a millisecond. The plan that looks least sophisticated is the only one that is both fast and correct, and it wins by a margin large enough that no amount of index tuning closes it. That is the answer worth having ready: pre-filtering does not beat post-filtering as a general rule, and at extreme selectivity neither of them is the plan you want.

Each plan owns a band of the selectivity axis and is disastrous somewhere else. The scan row is the clearest illustration: unbeatable at 5,000 eligible documents, unshippable at 102,000, catastrophic at 4.1 million. There is no plan that is correct everywhere, which means the choice cannot be made once at design time and written into the retrieval service.

The decision belongs to the query, not the codebase#

Selectivity is a property of a specific predicate against a specific set of documents at a specific moment. The same filter expression — tenant_id = ? AND doc_type = 'contract' — matches 12 documents for a customer who signed up last week and 380,000 for the anchor tenant that migrated eleven years of archives. A retrieval service that hardcodes one plan is right for one of those customers.

The shape of the fix has been standard in relational databases since Selinger's 1979 System R paper introduced cost-based optimisation: estimate the cardinality of each predicate from statistics, assign a cost to each available plan given that estimate, and execute the cheapest. Postgres does exactly this when it chooses between a sequential scan, an index scan and a bitmap heap scan, and the thing it is deciding is recognisably the same decision — an index is worth its overhead when it eliminates most of the table, and a sequential scan wins when the predicate is either very selective on a small relation or not selective at all. The instinct to write SET enable_seqscan = off because sequential scans feel primitive is the same instinct as "we should pre-filter everywhere for correctness", and it fails for the same reason.

Vector search needs less machinery than a relational optimiser, because there is one predicate and three plans rather than an exponential space of join orders. What it needs is a cardinality estimate, and there are several ways to get one at a cost far below the query itself:

PLAN_SCAN_MAX      = 20_000    # eligible docs; measured, not guessed
PLAN_POSTFILTER_MIN = 0.25     # selectivity above which over-fetch is fine

def choose_plan(predicate, k=10):
    n = cardinality.estimate(predicate)      # sub-millisecond
    s = n / CORPUS_SIZE

    if n <= PLAN_SCAN_MAX:
        return ExactScan(predicate)
    if s >= PLAN_POSTFILTER_MIN:
        overfetch = min(int(k / s * 1.5), 200)
        return PostFilter(predicate, top_k=overfetch)
    return FilteredAnn(predicate, ef_search=ef_for_selectivity(s))

Three constants in that function are decisions rather than derivations, and it is worth being clear which is which. PLAN_SCAN_MAX = 20_000 sits well below the 65,000 the crossover arithmetic gave, and the comment says why: the arithmetic assumed sequential bandwidth, the gather is often scattered, and the honest response to an uncertainty of that size is to leave headroom rather than to model it. The 1.5 in the over-fetch is the same kind of headroom applied to the previous chapter's k/s, which fills the page on average and therefore leaves it short about half the time; multiplying by half again buys margin against the draw. And the 200 cap never actually binds here, because post-filtering is only reached when selectivity is at least PLAN_POSTFILTER_MIN, at which point k/s multiplied by 1.5 cannot reach 200. It is there so that a later change to the threshold cannot silently produce an enormous fetch.

The estimator is the interesting component. For equality predicates on indexed attributes, a roaring bitmap gives an exact cardinality in constant time from the container headers, so tenant_id = 'acme' AND doc_type = 'msa' costs an intersection over compressed bitmaps rather than a count of documents. For range predicates on numeric or date attributes, an equi-depth histogram — a hundred buckets whose boundaries are chosen so that each holds the same number of documents — gets within a few percent.

For anything unindexed, a reservoir sample of 100,000 document ids, drawn uniformly as the documents stream past and filtered in memory, gives a proportion. How good that proportion is follows from counting. The standard error of an estimated proportion is the square root of the proportion times its complement, divided by the sample size, and that expression is largest when the proportion is one half — which puts a worst-case standard error around 0.15 percentage points on a sample of a hundred thousand. That is precise enough to distinguish 0.05% from 40% by an enormous margin. It is not precise enough to distinguish 0.04% from 0.06%, and the cleanest way to see why is to count hits rather than percentages: a predicate matching one document in two thousand shows up about fifty times in a hundred-thousand-document sample, the noise on a count of fifty is about its square root, which is roughly seven, and fifty give or take seven spans exactly the interval in question. The plan boundaries are chosen so the imprecision does not matter. Many teams also keep a maintained counter table for the one attribute they filter on constantly, usually the tenant, updated on ingest.

Several engines now do some version of this internally, which changes the build-versus-configure question rather than removing it. Qdrant's filterable HNSW estimates the cardinality of the payload filter from its payload indexes and switches to an exact scan of the matching points when the estimate falls below a configurable threshold, and its Combining Vector Search and Filtering write-up documents both the mechanism and the threshold. Elasticsearch decides between a filtered graph search and a brute-force scan on a similar basis. Where the engine routes for you, the work is verifying that its threshold matches your latency budget and your vector dimension rather than the vendor's defaults, and confirming that the estimate it uses is exact rather than sampled for the predicates you care about. Where it does not route, the router lives in your retrieval service and the estimates come from whatever metadata store you already run.

Where the router misjudges#

Cardinality estimation inherits every failure mode it has in relational databases, and the dominant one is correlation. Estimators multiply per-attribute selectivities on the assumption that attributes are independent, which is the same independence assumption the first chapter used to derive k × s and it is wrong for the same reason: attributes in real data are not drawn separately.

Follow it through on a concrete pair. country = 'DE' AND language = 'de' gets estimated as 4% multiplied by 3%, which is 0.12%, when the true figure is close to 3%, because almost every German-language document is German — the second predicate eliminates almost nothing once the first has run. Convert both to document counts against the 10.2 million indexed and the size of the error becomes visible: the estimate is 12,000 documents and the truth is 306,000. The router sees a number below PLAN_SCAN_MAX and picks the exact scan, so it gathers 306,000 vectors instead of 12,000, and by the scan row of the table above that is a query that should have taken 20 ms taking six seconds. Multi-column statistics fix the correlations you anticipate; a hard cap on the number of vectors the scan will gather, after which it falls back to the ANN plan, handles the ones you did not.

The router is also not a substitute for measuring the filtered ANN path. It reduces how often that path runs at bad selectivity, which shrinks the blast radius of the recall cliff without removing it, because the middle band — a filter matching 40,000 documents out of 10 million — is served by filtered ANN and is exactly where recall sits somewhere between 0.6 and 0.9 without announcing itself.

A subtler consequence is that the same query can now take different plans on different days, which makes latency graphs harder to read. That is the situation above, and the general form of the fix is the one that scenario reached: the chosen plan and the estimated cardinality belong on every retrieval span, because a plan flip is invisible in every other signal the system emits.

And routing adds cost of its own that has to stay small. An estimate that takes 3 ms in front of a 7 ms query has added most of half again to the latency of the common case in order to protect the rare one, which is nowhere near the order of magnitude cheaper than the cheapest plan that an estimator needs to be. Bitmap cardinality and histogram lookups clear that bar comfortably; a SELECT count(*) against the metadata store does not, and a service that issues one per query has traded a retrieval problem for a database load problem.

The three plans and the router between them make filtered retrieval correct across the whole selectivity axis, and they do it by making the system's behaviour depend on a quantity that varies per query and per day. That dependence is the price. A single recall figure averaged over traffic now blends queries answered exactly, queries answered approximately at healthy selectivity, and queries answered approximately near the cliff, and it moves when the traffic mix moves rather than when quality moves.

Which means the measurement has to be cut the way the system is built. Separating filtered queries from unfiltered ones, and then breaking the filtered figure down by the selectivity bands and the filter values that actually appear in traffic, is not a reporting nicety once a router exists. It is the only way the number means anything.