R5.3 · LESSON 3 OF 6

Filtering

Design a retrieval record and explain filtering, indexing, partitioning, updates and consistency.

THE IDEA

Filtering

Real queries come with conditions: only English, only this customer, only documents updated this year. A prefilter restricts the candidates first and then ranks them. A postfilter ranks first and then discards ineligible hits, so it can return fewer than k results. If a filter accepts 20% of the corpus, ten global candidates leave about two survivors; to expect ten you would fetch about fifty.

Ten points on a line (ids 0–9 at x = id). Points 0 and 5 are English, the rest German. Query x = 0, want 2 English results.

postfilter: candidates fetched3

prefilter (restrict to English first, then nearest 2): ids 0, 5 postfilter (nearest 3 globally, then keep English): ids 0 ← only 1 of 2 wanted

share of the corpus the filter accepts0.2

fetching 10 candidates gives about 2 survivors to expect 10 survivors fetch about 50 candidates

Selective filters make postfiltering come up short, while prefiltering through an approximate index can leave the graph or clusters poorly connected. The best strategy depends on how selective the filter is.

Same data, two orders of operations.

Predict first. Can retrieving ten global candidates and then filtering yield fewer than ten eligible results?

Chapter context

A vector index solves similarity lookup; a retrieval application also needs durable records, metadata, permissions and updates. Database behavior determines which vectors are eligible and which version of a document an answer uses.

TRY IT YOURSELF

Part 1. Do it hands-on

Estimate survivors by hand, then write both filtering strategies and see one fall short.

Ten points on a line (ids 0–9 at x = id). Points 0 and 5 are English, the rest German. Query x = 0, want 2 English results.

postfilter: candidates fetched3

prefilter (restrict to English first, then nearest 2): ids 0, 5 postfilter (nearest 3 globally, then keep English): ids 0 ← only 1 of 2 wanted

share of the corpus the filter accepts0.2

fetching 10 candidates gives about 2 survivors to expect 10 survivors fetch about 50 candidates

expected survivors (10 × 20%) fetch for 10 survivors at 20% at 1% can postfiltering return fewer than 10? (yes/no)

To do: A postfilter fetches 10 global candidates and keeps those matching a filter that accepts 20% of the corpus (independence assumed). Expected survivors?
To do: To expect 10 survivors at 20% selectivity you must fetch about how many candidates?
To do: At 1% selectivity?
To do: Can retrieving ten global candidates and then filtering return fewer than ten eligible results? Type yes or no

Part 2. Do it in code

postfilter_search(q, vectors, meta, pred, k, fetch): take the `fetch` nearest ids globally (squared L2, ties: smaller id), then keep those whose metadata satisfies pred(meta[id]), and return the first k.
prefilter_search(q, vectors, meta, pred, k): restrict to ids that satisfy pred first, then return the k nearest.
expected_survivors(fetch, selectivity): fetch · selectivity.
fetch_needed(k, selectivity): ceil(k / selectivity); ValueError if selectivity is not in (0, 1].
shortfall(results, k): how many results are missing: max(0, k − len(results)).

import math

def postfilter_search(q, vectors, meta, pred, k, fetch):
    pass

def prefilter_search(q, vectors, meta, pred, k):
    pass

def expected_survivors(fetch, selectivity):
    pass

def fetch_needed(k, selectivity):
    pass

def shortfall(results, k):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can retrieving ten global candidates then filtering yield fewer than ten eligible results?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

Raw vector storage is $M=Ndb$ for N vectors of dimension d and b bytes per coordinate. If a postfilter independently accepts fraction f of an initial k candidates, the expected survivor count is kf; this is an expectation, not a guarantee.

Worked example

Ten million vectors of dimension 768 in float32 require 10,000,000×768×4=30,720,000,000 bytes, or 30.72 decimal GB, before IDs, text, indexes and replicas. If a postfilter accepts 20% of ten candidates under a simplifying independence assumption, the expected survivor count is only two.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
bytes_used=10_000_000*768*4
assert bytes_used == 30_720_000_000
assert isclose(bytes_used/1_000_000_000,30.72)
assert 10*.2 == 2

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Filter selectivity and ANN candidate recall interact. Replication adds storage. Matching vector dimension does not establish matching embedding space.