Finding Neighbors Inside the Eligible Corpus

Two tenants each own one third of a corpus. For one tenant, the nearest documents sit beside the query. For the other, every eligible document lies farther away, beyond the first region the search inspects. A planner that sees only the fraction of matching documents treats these queries alike. Their access paths may need very different work.

The tenant-filter article already shows how truncating global candidates can starve a filtered answer. This chapter goes underneath that boundary: which vertices or clusters does an index let a query reach, what does a predicate change about that navigation, and when should the planner stop trying the approximate path?

Locate those access paths on the primer’s search-system map. Its answers and quality vocabulary separates the eligible population, inspected candidates and exact-neighbor fidelity used below.

We continue the synthetic engineering-document service from the identity chapter. The baseline remains 50,000 documents in one region, 10 queries/s and 20 updates/s; these are scenario inputs, not measured capacity. The new requirement is to serve equally selective filters with different geometric placement, then a conjunction of tenant and document kind. Reading time covers prose; reserve additional time for the exercises.

Evidence boundary: All coordinates, graph edges, budgets and thresholds below are stipulated teaching inputs. The walk is a single-level FIFO graph mechanism, not a simulation or benchmark of HNSW, ACORN or a production planner. The inspected primary sources explain their own mechanisms; no engine experiment or benchmark reproduction is claimed.

The population tells you the answer, not the access path

A predicate is a condition that a record either satisfies or fails. At search snapshot S, let N be the number of live documents in the selected corpus and E be those satisfying the full query predicate. Define selectivity here as the matching fraction s = |E| / N. A smaller s means fewer matches. Always name the denominator: a fraction of a service’s named collection, or namespace, differs from a fraction measured after tenant restriction. Neither scope is automatically one physical shard.

The tenant comes from trusted identity context, not an arbitrary request value. Snapshot eligibility combines that tenant with live state and additional filters. A dense query selects one named vector field, here body, with exactly one vector per document in that field. Rank distinct documents by squared Euclidean distance ascending, then doc ID ascending. Adding the stored title vector in the earlier chapter did not change this query’s score. Multi-field aggregation remains a separate contract.

The exact eligible oracle enumerates all of E at S, calculates every selected-field distance and takes the first min(k, |E|) documents under that total order. An approximate result R has eligible-neighbor recall |R ∩ oracle| / |oracle| when the oracle is nonempty. For an empty oracle, recall is N/A and the required result is empty. Every returned document must separately satisfy eligibility. Exact-neighbor fidelity measures agreement with distance ranking; judged relevance and freshness answer different questions.

For a tiny E, enumerating the eligible IDs with an attribute index and computing their distances can be a strong plan. An attribute index maps values to matching records; a bitmap represents membership with bits and can combine predicates with set operations. Enumeration is work too: reading and intersecting these structures can dominate a very small distance scan. The pgvector v0.8.6 filtering documentation recommends starting with a filter-column index and explicitly says small matching fractions can work well with exact search. That is a useful counterpoint to treating every prefiltered scan as too slow.

An approximate global path instead finds promising vectors in the whole corpus and filters those candidates. Its effort depends on where matches occur along that path. In ACORN §3, Patel and colleagues distinguish selectivity from query correlation: eligible vectors may cluster near or far from the query compared with a randomly selected set of the same size. This is a geometric property, not just a count. Below, “near” and “far” are descriptive toy placements; we do not estimate the paper’s formal workload correlation statistic.

Before reading the trace, predict this: if two masks each retain four of twelve documents, must a four-vertex walk find the same number of matches? If it later finds k matches, has it necessarily found the nearest eligible k?

Save a graph small enough to inspect completely

Replace the service’s large vectors with twelve two-dimensional body vectors for this exercise only. The query is (0,0), all rows are live at S, and distance is x² + y². IDs are new to this chapter. Cluster membership and directed outgoing edges are saved inputs, not inferred from geometry. incident = 1 marks the second predicate.

Run two alternative snapshots: Near assigns tenant A to [21,22,23,24]; Far assigns A to [29,30,31,32]. All other rows belong to B. Each snapshot has twelve live documents and four eligible A documents, so both selectivities are 4/12 = 1/3. Labels change between alternatives; the query, vectors and saved edges do not.

Our walk follows an explicit rule. Initialize a first-in, first-out queue with entry 21 and mark it discovered. Pop a vertex, calculate its distance, then enqueue its not-yet-discovered outgoing neighbors in the saved order. Keep walking through nonmatching vertices, but admit only eligible popped IDs to the result pool. Stop after B pops or when the queue is empty. Finally sort the eligible pool by (distance, doc_id) and take k. One pop costs one distance evaluation; adjacency and predicate work are additional counters.

This FIFO rule is deliberately simple enough to reproduce by hand. Real graph search has its own candidate queues, levels, neighbor selection and stopping rules. The point is to identify what a finite traversal inspected, rather than hide an unexamined algorithm behind the name HNSW.

For B=4, the distance-evaluated IDs are [21,22,23,25]. Enqueuing 29 is not evaluating or returning 29: it is still waiting when the budget ends. Near returns [21,22], exactly its k=2 oracle. Far returns [], although its oracle is [29,30]. Both results obey the predicate. Only one achieves full eligible-neighbor recall.

The second Far lane exposes a more subtle stopping boundary. At B=10, the result is [29,31], with distances 25 and 36. Doc30 also has distance 25 and belongs before doc31; it is not popped until step 11. Having enough matches did not establish the nearest eligible answer. Increasing this toy budget to 11 repairs the result. No particular production budget follows from that calculation.

Bridges are navigation, not disclosure

In Far, entry 21 and intermediate 25 belong to B. Following their edges lets the walk reach A’s doc29. If a different rule rejected a nonmatching vertex before expanding its outgoing edges, it would stop at entry 21 even with a larger budget. Increasing a queue budget cannot restore edges that the traversal rule never follows.

A trusted search engine may use nonmatching adjacency or vector metadata internally under its declared isolation policy. That does not authorize disclosing the corresponding document contents. The application checks current-policy authorization at a defined decision point before returning content or forwarding it to an external reranker or generator. An old snapshot match is not proof of current permission. This model assumes a trusted policy lookup at that point and does not promise that a policy cannot change afterward. It also does not analyze timing side channels or design a tenant-isolation protocol.

Cooperate with the predicate while navigating

Two mechanisms can reduce travel through unhelpful regions. They pay for that information in different places.

Route to clusters that may contain matches

A cluster index groups vectors, then uses representatives such as centroids to select groups to inspect. For this toy, a centroid is the arithmetic mean of its cluster’s saved coordinates. Its distance helps rank clusters; it is not a lower bound on every member’s distance.

Suppose an exact, snapshot-consistent attribute summary says which clusters contain at least one match. An unfiltered one-cluster router chooses C0, yielding no Far matches. A predicate-aware router excludes C0 and C1 and chooses C2. Evaluating all four eligible members there yields Far’s exact [29,30] in four document-distance evaluations, plus summary reads and centroid work. Near similarly selects C0 and gets [21,22]. Exactness happens here because each eligible set is wholly contained in its one selected cluster. On another corpus, stopping after one matching cluster remains approximate unless a valid bound proves other clusters cannot improve the result.

turbopuffer’s January 2025 native-filtering account describes this cooperation: find nearby clusters containing matches, then evaluate matching candidates inside them. Its attribute structures include cluster-level summaries and exact within-cluster bitmaps. The described LSM keys use (attribute_value, cluster_id) with sets of local IDs; the attribute index reacts when an ANN address changes. That is evidence for the described older design, not a specification of the in-progress v3 layout.

Cluster summaries are useful but coarse. “Some row in C0 satisfies P” and “some row in C0 satisfies Q” do not imply that the same row satisfies P AND Q. Intersecting cluster-level bitmaps produces candidate clusters. Intersecting exact row membership, or checking the full predicate, resolves false positives. A missing true match in a supposedly safe summary can instead cause an incorrect exclusion, so maintenance and snapshot consistency matter.

Recover useful graph neighborhoods

ACORN §5 targets search over a predicate subgraph: vertices passing the predicate and the edges between them. Simply deleting nonmatching vertices from a graph can remove useful routes, as the bridge example shows. ACORN changes how useful neighborhoods are supplied, rather than assuming the surviving graph is always navigable.

ACORN-γ expands candidate neighbor lists during construction and uses predicate-agnostic pruning to control storage. During search it filters neighborhoods to matching vertices; its compression-compatible lookup can examine selected two-hop neighbors to recover pruned connections. ACORN-1 moves neighbor expansion to query time, considering one-hop and two-hop neighbors before predicate filtering and truncation. “Two-hop” means following a neighbor’s adjacency list; that internal lookup need not reveal its document contents. These are descriptions of the inspected paper’s mechanisms, not configuration instructions for every implementation.

The paper also includes a prefilter fallback below a configured minimum selectivity. Its §7.2 compares optimized exact prefiltering, an over-searching postfilter baseline, and separately configured ACORN variants. Those choices matter when interpreting the results: a comparison against a postfilter baseline that asks for only k global candidates is a different experiment. No universal runtime or connectivity guarantee follows from the tiny walk or from a paper’s evaluated datasets.

The August 2026 Qdrant study gives a concrete planner counterpoint. In its tested implementation, filterable graph edges are built per payload field, while query-time ACORN-1 expansion helps with gaps including AND predicates. The planner can choose a payload-index path for small eligible sets. In the described default configuration ACORN is opt-in; this is not a default inferred from the original paper. The study uses Qdrant 1.18.2, one million 96-dimensional image vectors, 500 queries per filter and serial execution on one machine. It reports mean server-side latency, not production p99. Its own-strategy results are vendor-authored and unreplicated here. Their teaching value is the separation of build work, query repair and fallback, not a database ranking.

A conjunction changes both the count and the geometry

The saved incident predicate matches [21,25,29,31]: four of twelve documents. Near’s tenant predicate also matches four, but their intersection is only [21]. Far’s intersection is [29,31]. You cannot multiply 1/3 × 1/3 without an independence assumption; the actual matching fractions are 1/12 and 2/12 = 1/6. The incident labels are associated with document placement, and the conjunction selects its own population.

Use these scenario inputs for the worked cases and exercises. “A IDs” defines the trusted tenant’s snapshot membership; none leaves it unchanged, while incident intersects it with the saved incident mask. Other documents belong to B.

Guided prediction: one eligible record

Use Guided. Enumerate the conjunction before computing distances. Compare a complete eligible exact scan with the B=4 walk; choose a first plan hypothesis. Include k=3 in the answer rather than silently changing it to one. Then answer Empty under its saved inputs.

Independent problem: scatter the tenant, then restrict the kind

Use Independent: move A’s labels to [22,26,29,31], still four of twelve documents, add incident, raise k to 3 and give the walk B=8. First predict its result without looking at the answer. Derive the exact oracle, then explain what a cluster-level AND intersection can and cannot establish.

Choose a plan and rejected alternative. Stipulate a cumulative cap of ten document-distance evaluations for the initial path plus fallback, with separate implementation limits for memory and deadline. If you start with the walk, can a complete eligible scan fit afterward? Decide what response is allowed if the exact fallback cannot finish. Name one measurement and threshold that would change your plan choice.

Defend the plan with more than a matching fraction

The planner needs estimates it can act on: eligible count for the whole conjunction, geometry under the actual query distribution, accessible cluster/graph neighborhoods, vector dimension, index availability and costs under current cache and concurrency conditions. Partial indexes or tenant partitions may help stable query shapes, but they add storage, build work and update responsibilities; arbitrary predicate combinations can be too numerous to index separately. The pinned pgvector iterative-scan section documents continuation until enough results or configured scan limits. Its strict ordering governs returned candidates’ distance order; it does not prove the global eligible oracle was found.

Keep at least these work categories separate when comparing plans:

Compare an approximate plan with exact eligible results at the same snapshot, field, predicate and total order; pgvector’s monitoring section explicitly recommends exact comparisons. Sample Near, Far, scattered and conjunction shapes separately. Report result count, eligible-neighbor recall, work, capped-query frequency and end-to-end latency distributions. Include updates and warm/cold conditions. Aggregating every filter into one recall or latency mean can hide the failing intersection.

For our tiny conjunction, the chosen first hypothesis is complete eligible enumeration followed by exact distance scoring. The rejected fixed-budget graph path has a concrete missing neighbor. For larger E, predicate-aware routing or graph expansion earns consideration; neither gets a free proof from selectivity. A production decision needs controlled measurements and declared approximation semantics.

Your exit artifact is a short plan note containing the chosen path, rejected alternative, exact eligible baseline, termination/fallback limits and a measurement threshold that would change the choice. Preserve that note when the workload changes. Doing less work and working faster explains why skipped work and CPU efficiency are separate. From durable write to searchable snapshot asks which versions the indexes and their summaries are allowed to represent together.

For selected reading, use pgvector v0.8.6 Filtering, Iterative Index Scans and Monitoring to resolve exact-small-set and finite-budget behavior; ACORN v1 §§3, 5 and 7.2 for correlation, neighborhood mechanisms and baseline configuration; the native-filtering account for cluster/row summaries and their maintenance; and Qdrant’s scoped August 2026 study for per-field edges, AND predicates and planner fallback. These selections answer different mechanism questions. Their performance figures have not been reproduced for our service.