The Zone-Map That Didn't Skip
An earlier post in this series recorded how a filtered vector search stopped scaling with the size of the match set and started scaling with the query’s neighbourhood instead. The mechanism was a coarse IVF partition: bucket the matching set into its cells, rank the cells that actually hold matches by their distance to the query, and score only a short list. It shipped, and the cost curve flattened.
It left one thing on the table, and this post is about the attempt to pick it up, which mostly failed, and about the smaller thing that worked in its place. The lesson is narrow and I think worth writing down precisely because the failing part is the intuitive one, the kind that looks obviously right until it is measured.
The shape that was left
The routed filter still begins by materialising the match set . The predicate is evaluated over the corpus into a sorted list of matching ids, and that list is bucketed into cells with a pass that is . For a broad filter this list is large: a 25% predicate over a million vectors is a quarter of a million ids built, sorted, and handed across a boundary before any distance is computed. The scoring afterwards is cheap and bounded; the id set is the part that still grows with the predicate.
For an arbitrary predicate there is no way around building : you have to know which vectors match. But a large class of real filters is not arbitrary. It is a range on a numeric attribute: a time axis, an importance score, a recency stamp, any monotone key attached per vector. “The vectors valid in this window.” “The vectors above this importance.” For a range, the question is whether has to be materialised at all, or whether the structure of the index can answer “which cells contain matches” without first enumerating every match.
The tool for that question is old and comes from columnar databases: the zone
map. Keep, per block, the minimum and maximum of a column. A range query then
skips any block whose [min, max] does not overlap the query range, without
reading the block. It is the idea behind Small Materialized Aggregates
[1] and, in a shipping system, PostgreSQL’s block-range index
[2]. The blocks here are the IVF cells. Attach to each cell the min
and max of the attribute over the vectors it holds, and a range filter should be
able to drop whole cells unread, and gather the survivors’ members without ever
building the global match set.
That was the hypothesis. It is wrong in an interesting way.
What I expected, and what the geometry actually does
The expected win has two parts. First, cell skipping: cells whose attribute range misses the query are never touched. Second, no id set: the surviving cells are gathered directly from a per-cell membership list, so the materialisation disappears.
I built both. Each vector gets an opaque u64 attribute; each cell gets the
min, the max, and its member list; a range probe walks the cells, skips those the
zone map excludes, takes fully-covered cells wholesale and filters straddling
cells per-member. Then I measured it on the mxbai 1024-dimension corpus with a
synthetic uniform attribute standing in for a time axis, the conservative
choice, because a uniform attribute is the worst case for skipping.
The cell skipping did essentially nothing.
The reason is a fact about the two structures that I should have seen before
writing the code. The IVF cells [3] partition the corpus by
embedding geometry: -means over the vectors. The attribute is a time axis, or an importance
score, a quantity with no relationship to where a vector sits in embedding
space. So the attribute values scatter uniformly across every cell. Each cell of
a few hundred vectors, drawn from across the whole attribute domain, has a
[min, max] that spans almost the entire domain. A range that selects a fifth of
the corpus overlaps almost every cell, because almost every cell contains values
from across the whole range. There is nothing to skip.
I checked this the way you check a suspicion you do not trust: I ran the same benchmark with the attribute correlated to insertion order instead of uniform, expecting the correlated case to skip more. It skipped exactly as little. The numbers were identical to two significant figures. Correlation with insertion order is not correlation with cell membership, and cell membership is assigned by the vector, not by when it arrived. For the zone map to skip, the attribute would have to correlate with embedding-space clustering (recent facts would have to sit near each other in the model’s geometry), and for a time axis or an importance score they do not. The zone map’s headline trick is inert on exactly the attributes you would want to range over.
The part that did work
The other half survived: not materialising the id set. Skipping cells is worth nothing, but gathering a bounded shortlist directly from the cell members, ranked by the query and stopped at a budget, sidesteps building and sorting entirely. And that cost is real. The routed baseline’s per-query time grows with the match set; the range probe’s does not, because it stops at the candidate budget regardless of how many vectors match.
The router-level microbench, mxbai at 100k, one hundred queries per point, the
budget at 4096 candidates, uniform attribute:
| selectivity | id set built | baseline (build + probe) | range probe | speedup |
|---|---|---|---|---|
| 1% | ~1,000 | 0.08 ms | 0.16 ms | 0.49× |
| 2% | ~2,000 | 0.09 ms | 0.18 ms | 0.49× |
| 5% | ~5,000 | 0.30 ms | 0.18 ms | 1.71× |
| 10% | ~10,000 | 0.38 ms | 0.13 ms | 2.99× |
| 25% | ~25,000 | 0.61 ms | 0.09 ms | 6.59× |
| 50% | ~50,000 | 1.00 ms | 0.09 ms | 11.65× |
The crossover is not the selectivity; it is the size of the match set relative to the budget. Below roughly the budget, the id set is small, the baseline’s scan of it is nearly free, and the range probe only adds fixed overhead; it loses, at half the speed. Above the budget the range probe holds a flat floor around 0.09 ms while the baseline climbs linearly with , and by a 50% filter it is eleven times faster. The recall is identical at every point: the two paths score the same candidates and return the same top ten. This is not an approximation that trades quality for speed. It is the same answer, reached without building the list.
So the honest picture at the router level is a knee, not a uniform win: the range probe is worse for narrow filters and better for broad ones, and the boundary is the candidate budget. Which means the mechanism cannot be turned on unconditionally.
The router that picks the side
The zone map turned out to earn its place not by skipping cells but by making the match count cheap to estimate. The per-cell min, max, and member count are enough to project for a range without scanning the attribute column: sum the members of fully-covered cells, add a proportional share of the straddling ones. It is , a few hundred additions, and on this corpus it lands within a few percent of the true count (an estimate of ~900 against a true 998; ~2,400 against 2,503).
That estimate is exactly the input the knee needs. If the projected match set is above the budget, take the range probe; if below, materialise the small set and take the existing routed path, whose small-set scan is already cheap. The planner is the same shape the filtered search already uses to choose between an exact scan and the IVF route; this adds a third case for numeric ranges, chosen by a count that costs nothing to compute.
With the router deciding, the same microbench, comparing the auto-routed path against the always-materialise baseline:
| selectivity | chose range path | auto vs baseline |
|---|---|---|
| 1% | 0/200 | 1.00× |
| 2% | 0/200 | 1.01× |
| 5% | 200/200 | 2.04× |
| 10% | 200/200 | 3.58× |
| 25% | 200/200 | 7.15× |
| 50% | 200/200 | 13.34× |
Never slower than the baseline, up to thirteen times faster, recall unchanged. For the narrow filters it declines to use the new path and there is nothing lost; for the broad ones it takes it and the id set is never built.
The reality check on disk
The router numbers are the cost of choosing and gathering candidates in isolation.
A real query does more: after the shortlist it runs the quantized proxy scan and
the bounded full-precision re-rank from disk, and that work is the same whichever
path produced the shortlist. It is a shared constant, and it dominates. Measured
end to end against a real on-disk index, mxbai at 50k, k=10, 80-read re-rank,
the same warm cache for both paths:
| selectivity | old (materialise + route) | new (auto range) | speedup |
|---|---|---|---|
| 2% | 0.40 ms | 0.39 ms | 1.02× |
| 5% | 0.69 ms | 0.66 ms | 1.04× |
| 10% | 1.13 ms | 1.09 ms | 1.04× |
| 25% | 1.40 ms | 0.97 ms | 1.45× |
| 50% | 1.44 ms | 0.97 ms | 1.49× |
Neutral on narrow ranges, up to about one and a half times on broad ones, identical results throughout. The eleven-times figure from the router bench is real, but it is eleven times on a component that is a small fraction of the whole query once the disk re-rank is included. The end-to-end win is modest and lives entirely at high selectivity, where the id set the old path materialises is largest.
I will note the artefact that nearly fooled me, because it is the kind that survives a careless bench. My first end-to-end run showed a clean 2× even on narrow filters, where the two paths do identical work. It was cache order: the old path ran first every iteration and paid the cold reads the new path then reused. Running each path in its own loop, new first so any warm-cache advantage falls to the old one, collapsed the phantom 2× to the honest ~1× it should have been. A speedup that appears where the two code paths are provably the same is not a speedup.
What this supports, and what it does not
The range filter is worth having, as a third planner case gated on an estimated match count, for the specific shape it serves: a broad numeric-range predicate over a large corpus, where the old path’s id-set materialisation is the cost. It is never worse than what it replaces, and on the case it targets it removes a term that grew with the predicate. The estimate that routes it is the one piece of the zone map that pays for itself.
What it does not support is the intuition I started with. The min/max zone map, as a device for skipping cells in a vector index, is close to useless, because the attribute you want to range over does not correlate with the geometry the cells are cut along. It would help only for an attribute that clusters in embedding space, and the attributes that motivate range filters (time, recency, importance) do not. I kept the per-cell bounds only because they make the count cheap to estimate, not because they skip anything.
Two things I did not measure, in the manner of the earlier records. The synthetic attribute is uniform, chosen as the conservative case for skipping; I did not construct an attribute deliberately aligned with the cell geometry, because it does not correspond to a real filter and would only flatter a mechanism I have already reported as inert. And the whole comparison is a single run on the development machine, reproducible to within its run-to-run noise; the ratios hold, the absolute microseconds are the hardware’s. At the scales a personal deployment actually reaches, a match set in the low thousands, the small-set path the router falls back to is already fast, and the range path stays out of the way. So this closes a term in the cost that only bites when the corpus and the predicate are both large, and the part of the design that reads best on a whiteboard is the part that did nothing.
The general shape
The specific lesson has a general one under it, about what an index makes cheap. skeg’s index is cut along embedding geometry: the cells are -means over the vectors, and the graph they refine is a proximity graph [4]. Any metadata you bolt onto it (a time, a score, a tenant) is orthogonal to that partition. It does not move a vector between cells, so a min/max over a cell tells you almost nothing about which cells to skip. This is the same reason a filter-aware graph build [5] has to be validated against the walk that actually runs and not the exact distances that flatter a prototype, a point the earlier record in this series [6] paid for more than once. A structure attached to a vector index is fighting the geometry the index is organised around, and usually loses to it.
What the geometry does not fight is counting. A per-cell aggregate cannot say where the matches are, but it can say roughly how many there are, cheaply and without touching the data, which is precisely a selectivity estimate, the oldest routing input a query planner has [7]. That is the whole of what the zone map earned here: not a pruning structure but a histogram. Pruning was the idea I came in with; estimation was the idea I left with, and it is the one that decides the query. When the next metadata structure suggests itself for the vector path, that is the question I will ask first. Does it skip work, or does it only help me guess how much there is? Because on this index only the second kind has paid.
References
[1] Moerkotte, Guido. “Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing.” Proceedings of the 24th International Conference on Very Large Data Bases (VLDB ‘98), 1998. The origin of the min/max zone map as a block-pruning structure.
[2] The PostgreSQL Global Development Group. “BRIN Indexes.” PostgreSQL Documentation, postgresql.org/docs/current/brin.html. The block-range index is the min/max zone map in a shipping relational engine.
[3] Jégou, Hervé; Douze, Matthijs; Schmid, Cordelia. “Product Quantization for Nearest Neighbor Search.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 1, 2011. The inverted-file (IVF) partition whose cells the zone map annotates.
[4] Subramanya, Suhas Jayaram; Devvrit; Kadekodi, Rohan; Krishaswamy, Ravishankar; Simhadri, Harsha Vardhan. “DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node.” Advances in Neural Information Processing Systems 32 (NeurIPS 2019), 2019. The Vamana graph skeg walks and re-ranks against.
[5] Gollapudi, Siddharth; Karia, Neel; Sivashankar, Varun; Krishnaswamy, Ravishankar; Begwani, Nikit; Raz, Swapnil; Lin, Yiyong; Zhang, Yin; Mahapatro, Neelam; Srinivasan, Premkumar; Singh, Amit; Simhadri, Harsha Vardhan. “Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters.” Proceedings of the ACM Web Conference 2023 (WWW ‘23), 2023. The filter-aware graph build that a vector index’s geometry resists.
[6] “A Ceiling That Moved: skeg 0.6.0.” This series, 2026, /posts/2026-07-05-a-ceiling-that-moved. The earlier record of the filtered-search route this post extends, and of the proxy-path lesson it echoes.
[7] Ioannidis, Yannis. “The History of Histograms (abridged).” Proceedings of the 29th International Conference on Very Large Data Bases (VLDB ‘03), 2003. Selectivity estimation as the query planner’s routing input.