Nearest-neighbour search with filters

Deep dive

How it works

Parts:

• vector index — HNSW, IVF-PQ or a Vamana graph (DiskANN) over all items
• attribute index — inverted index, B-tree or roaring bitmap; yields the matching ids and their count
• planner — picks the strategy from the selectivity estimate (cf. query optimizer)
• filter-aware search — a traversal that tests each candidate against the predicate

Operations for one query (q, predicate P, k):

1. Estimate s = |{i : P(i)}| / n from the attribute index.
2. If s·n is below about the cost of one ANN query in distance computations (rule of thumb): pre-filter. Take the matching ids, compute exact distances, keep the top k (top-k selection).
3. Else if the index is filter-aware (extra edges per attribute, per-label start nodes, denser graph): filtered traversal with ef grown as s shrinks.
4. Else post-filter: ANN search for k' = k/s times a safety factor, drop non-matching, keep k. If fewer than k remain, enlarge k' (iterative scan) or fall back to step 2.
5. Merge segments or shards, top k again.

In-graph filtering (HNSW style): a candidate failing P stays in the beam as a route but never enters the result set. Routes through non-matching nodes keep the walk connected; the price is more distance computations as s falls, and at very low s the matches form islands the walk never reaches. IVF: apply P while scanning the probed lists and raise nprobe as s falls.

selectivity s:   0 ----- tiny ---------- moderate ---------- large ----- 1
strategy:        pre-filter (exact)      filter-aware ANN     post-filter / plain ANN
                 |matches| < ANN cost    ef grows as 1/s      k' = k/s is small
walk (q -> *, filter keeps o, drops x):  q > x > x > o > x > o > o   (x = route only)

Code

Exact pre-filter versus post-filtered and in-scan-filtered IVF; the pre-filter result is asserted equal to ground truth.

use std::time::Instant;

struct Rng(u64);
impl Rng {
    fn next(&mut self) -> u64 { self.0 ^= self.0 << 13; self.0 ^= self.0 >> 7; self.0 ^= self.0 << 17; self.0 }
    fn unit(&mut self) -> f32 { (self.next() >> 40) as f32 / (1u64 << 24) as f32 - 0.5 }
}
fn l2(a: &[f32], b: &[f32]) -> f32 { a.iter().zip(b).map(|(x, y)| (x - y) * (x - y)).sum() }

/// Exact k nearest among `ids`. Pre-filtering = call this with the matching ids only.
fn knn(data: &[f32], dim: usize, q: &[f32], ids: impl Iterator<Item = u32>, k: usize) -> Vec<u32> {
    let mut v: Vec<(f32, u32)> = ids.map(|i| (l2(q, &data[i as usize * dim..][..dim]), i)).collect();
    v.sort_by(|a, b| a.0.total_cmp(&b.0));
    v.into_iter().take(k).map(|x| x.1).collect()
}

struct Ivf { cent: Vec<f32>, lists: Vec<Vec<u32>>, dim: usize }
impl Ivf {
    fn nearest(&self, q: &[f32], p: usize) -> Vec<usize> { // the p closest centroids
        let mut v: Vec<(f32, usize)> = self.cent.chunks(self.dim).enumerate().map(|(c, x)| (l2(q, x), c)).collect();
        v.sort_by(|a, b| a.0.total_cmp(&b.0));
        v.into_iter().take(p).map(|x| x.1).collect()
    }
    fn build(data: &[f32], dim: usize, nlist: usize) -> Ivf {
        let n = data.len() / dim;
        let cent = (0..nlist).flat_map(|c| data[(c * n / nlist) * dim..][..dim].to_vec()).collect();
        let mut ivf = Ivf { cent, lists: vec![], dim };
        for _ in 0..6 { // a few Lloyd iterations
            ivf.lists = vec![Vec::new(); nlist];
            for i in 0..n { let c = ivf.nearest(&data[i * dim..][..dim], 1)[0]; ivf.lists[c].push(i as u32); }
            for (c, l) in ivf.lists.iter().enumerate().filter(|(_, l)| !l.is_empty()) {
                for d in 0..dim { ivf.cent[c * dim + d] = l.iter().map(|&i| data[i as usize * dim + d]).sum::<f32>() / l.len() as f32; }
            }
        }
        ivf
    }
    /// Scan the nprobe nearest lists, keeping only ids that pass `pred`.
    fn search(&self, data: &[f32], q: &[f32], k: usize, nprobe: usize, pred: &dyn Fn(u32) -> bool) -> Vec<u32> {
        let ids = self.nearest(q, nprobe).into_iter().flat_map(|c| self.lists[c].iter().copied());
        knn(data, self.dim, q, ids.filter(|&i| pred(i)), k)
    }
}

fn main() {
    let (n, dim, nq, k, nprobe, kp) = (20_000usize, 32usize, 200usize, 10usize, 8usize, 50usize);
    let mut r = Rng(0x9E3779B97F4A7C15);
    let centers: Vec<f32> = (0..64 * dim).map(|_| 4.0 * r.unit()).collect(); // 64 clusters
    let point = |r: &mut Rng| -> Vec<f32> { let c = (r.next() % 64) as usize; (0..dim).map(|d| centers[c * dim + d] + 0.5 * r.unit()).collect() };
    let data: Vec<f32> = (0..n).flat_map(|_| point(&mut r)).collect();
    let attr: Vec<u32> = (0..n).map(|_| (r.next() % 1000) as u32).collect(); // independent of the vector
    let queries: Vec<Vec<f32>> = (0..nq).map(|_| point(&mut r)).collect();
    let ivf = Ivf::build(&data, dim, 128);
    println!("sel  | pre-filter | post-filter k'={kp} | in-scan filter | (recall@{k}, us/query)");
    for sel in [0.5f32, 0.1, 0.01] {
        let limit = (sel * 1000.0) as u32;
        let pred = |i: u32| attr[i as usize] < limit;
        let (mut rec, mut us) = ([0.0f64; 3], [0.0f64; 3]);
        for q in &queries {
            let truth: Vec<u32> = knn(&data, dim, q, 0..n as u32, n).into_iter().filter(|&i| pred(i)).take(k).collect();
            let t = Instant::now();
            let pre = knn(&data, dim, q, (0..n as u32).filter(|&i| pred(i)), k);
            us[0] += t.elapsed().as_secs_f64() * 1e6;
            assert_eq!(pre, truth); // pre-filtering is exact
            let t = Instant::now();
            let post: Vec<u32> = ivf.search(&data, q, kp, nprobe, &|_| true).into_iter().filter(|&i| pred(i)).take(k).collect();
            us[1] += t.elapsed().as_secs_f64() * 1e6;
            let t = Instant::now();
            let scan = ivf.search(&data, q, k, nprobe, &pred);
            us[2] += t.elapsed().as_secs_f64() * 1e6;
            for (j, res) in [&pre, &post, &scan].iter().enumerate() {
                rec[j] += res.iter().filter(|i| truth.contains(i)).count() as f64 / truth.len().max(1) as f64;
            }
        }
        let f = |j: usize| format!("{:.3}, {:>4.0}", rec[j] / nq as f64, us[j] / nq as f64);
        println!("{:>3.0}% | {} | {} | {}", sel * 100.0, f(0), f(1), f(2));
    }
}

Complexity and constants

Measured on this Mac (Apple M4 Pro), one core, release build, the code above: 20,000 vectors, 32 dimensions, 64 clusters, an attribute independent of the vector, 128 IVF lists with nprobe = 8, k = 10, 200 queries, recall against the exact filtered top 10; times are the mean of several runs, order of ±10 %.

• Post-filter recall tracks s·k'/k: 0.5 at 10 % (about 5 hits expected from 50), about 0.05 at 1 %. A predicate correlated with the query shifts this.
• Pre-filter time is linear in s·n; the code sorts all matches (a heap is cheaper at large s).
• The predicate per candidate is a bitmap probe or column read: order of one cache miss on large data.

Efficiency

• Cost: measured above (20k × 32-dim): 15-185 µs per pre-filter query, 28 µs per post-filtered IVF query, 3-19 µs per in-scan-filtered one. At scale the bound is memory latency per visited vector plus a predicate test per candidate.
• Levers:
  • selectivity-based planner — avoids post-filter collapse and big brute-force scans (Qdrant: cardinality estimate vs full_scan_threshold; Lucene: exact fallback; per their docs) — any engine with an attribute index
  • extra graph edges per indexed attribute — keeps the filtered subgraph connected (Qdrant docs) — few, strict, frequent filters
  • denser graph with predicate-subgraph traversal (ACORN) — 2-1,000× higher throughput at fixed recall than prior methods in the paper's tests (Patel et al.) — arbitrary predicates, low selectivity
  • partition by tenant or service — each query touches one small index — isolation keys known in advance
• Naive → standard → state of the art:
  • post-filter a fixed top-k · recall collapses as s falls
  • estimate s, then pre-filter, filtered ANN or iterative post-filter · near unfiltered recall
  • label-aware or predicate-agnostic graph (Filtered-DiskANN, ACORN) · an order of magnitude or more over earlier methods in the papers' tests

Implementation notes

• Estimate s from per-value counts or histograms, not from ANN results; multiply predicates only if independent.
• Post-filter: grow k' geometrically, cap total work, then fall back to pre-filter.
• Graph filtering: start from matching entry points (Filtered-DiskANN: one start node per label).
• Segmented indexes: plan per segment, since s differs between segments.

Pitfalls

• Unfiltered recall says nothing; build ground truth with the same predicate.
• A fixed k' after a restrictive predicate silently returns fewer than k results.
• A filter correlated with the query region (language filter on a multilingual embedding) behaves unlike the independent table.
• Many soft-deleted points break connectivity of filtered walks (Qdrant docs).
• An attribute index created after the graph may leave it without filter-aware edges (Qdrant: rebuild).

Variants and alternatives

In production

• Lucene filtered kNN, FAISS IDSelector, Qdrant, Weaviate, Milvus, pgvector (details in the table).
• Fields: e-commerce search, multi-tenant RAG, media libraries, recommenders, log analytics.

Implementations

Sources

• S. Gollapudi, N. Karia, V. Sivashankar, R. Krishnaswamy, N. Begwani, S. Raz, Y. Lin, Y. Zhang, N. Mahapatro, P. Srinivasan, A. Singh, H. V. Simhadri, Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters, The Web Conference (WWW), 2023. paper · PDF
• L. Patel, P. Kraft, C. Guestrin, M. Zaharia, ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data, SIGMOD / Proc. ACM Manag. Data, 2024. paper · arXiv · code
• Qdrant, Indexing, docs. docs
• pgvector README, Filtering. docs
• Weaviate, Filtering, docs. docs
• Apache Lucene, AbstractKnnVectorQuery source. source