# Pre-Filtered ANN in Feather DB: How Exact Post-Filter Beats Approximate

> Most vector DBs do approximate pre-filter — filter candidates first, then run ANN on the subset, missing true neighbors outside the initial candidate pool. Feather DB does ANN first, then exact post-filter, avoiding both the miss problem and O(n) full scans.

- **Category**: Architecture
- **Read time**: 6 min read
- **Date**: June 16, 2026
- **Author**: Feather DB (Engineering)
- **URL**: https://getfeather.store/theory/feather-db-prefiltered-ann-search

---

## The filtered ANN problem

Filtered vector search — "find the 10 most semantically similar memories that also have `type=goal`" — is deceptively hard. The filter and the ANN are in tension: the ANN wants to explore the full graph, but the filter wants to restrict the result set. How you resolve that tension determines whether your filtered search is accurate, fast, or both.

There are three common strategies in the industry, and they have very different accuracy-performance profiles.

## Strategy 1: Approximate pre-filter (the naive approach)

Build a sub-index containing only the filtered nodes, then run ANN on that sub-index. This is what many vector databases do by default when you pass a metadata filter.

The problem: HNSW graph connectivity depends on all nodes being present during construction. A sub-index built from the filtered subset has degraded graph structure — the navigable small-world property breaks down when you remove most of the graph nodes. The result is meaningfully lower recall on the filtered search compared to unfiltered search, especially when the filter selectivity is high (e.g., only 1% of memories match the filter).

In the worst case, with highly selective filters, the pre-filter approach degrades to a near-linear scan because the HNSW graph has no useful long-range connections within the tiny filtered subset.

## Strategy 2: O(n) brute-force on filtered candidates

Load all matching candidates from disk, compute brute-force distance to the query vector, and return the top k. This is perfectly accurate but O(n_matched) — if 50,000 memories match the filter, you compute 50,000 dot products. At low filter selectivity (many matches), this is slow. At high selectivity (few matches), it's fast, but you've already fallen back to brute force.

## Strategy 3: Feather DB's ANN-first exact post-filter

Feather DB takes a different approach: run the full HNSW ANN search on the complete graph (or namespace subgraph) first, retrieve a larger candidate set, then apply the filter as an exact post-filter over those candidates. The graph quality is preserved because no nodes are removed from the HNSW structure. The filter operates on the ANN output, not on the input.

```python
import feather_db as fdb

db = fdb.DB.open("agent.feather", dim=768)

# Namespace filter: ANN traversal limited to this namespace's subgraph
results = db.search(query_vec, k=5, namespace="user-alice")

# Entity filter: ANN traversal within namespace, limited to entity subgraph
results = db.search(query_vec, k=5,
                    namespace="user-alice",
                    entity="work-context")

# Attribute filter: full ANN, then exact post-filter on attribute match
results = db.search(query_vec, k=5,
                    namespace="user-alice",
                    filter={"type": "goal"})

# Combined: namespace/entity scope ANN, attribute post-filter narrows results
results = db.search(query_vec, k=5,
                    namespace="user-alice",
                    entity="work-context",
                    filter={"type": "goal", "status": "active"})

```

## How namespace and entity filters work differently

It's important to distinguish between the three filter types in Feather DB — they operate at different stages of the retrieval pipeline:

Filter typeWhere appliedMechanismGraph impact

namespaceANN traversalPer-namespace HNSW subgraphOnly this namespace's nodes traversed
entityANN traversalPer-entity subgraph within namespaceOnly entity's nodes traversed
attribute filterPost-ANNExact key-value match over candidatesFull namespace/entity graph traversed

Namespace and entity filters are pre-filters, but they're not approximate: the HNSW subgraph for a namespace or entity is built with all the relevant nodes already in place. When you add a memory to `namespace="user-alice", entity="work-context"`, it is inserted into that entity's HNSW subgraph during write time — not filtered out from a global graph at read time. This preserves graph quality while still providing O(matches) traversal cost rather than O(total).

Attribute filters are post-filters because key-value attributes are arbitrary and not known at index build time. They apply over the top-k ANN candidates. To ensure the post-filter returns k results even with a selective filter, Feather DB automatically expands the ANN candidate set when a filter is present:

```python
# Internally, Feather DB oversamples candidates when a filter is present
# If k=5 and filter selectivity is low, it may retrieve 50 ANN candidates
# then apply the exact post-filter to return the top 5 matching results
# This is transparent to the caller — you always get up to k results back
results = db.search(query_vec, k=5, filter={"type": "goal"})
print(len(results))  # up to 5, may be fewer if fewer than 5 goals exist

```

## When to use each filter type

**Use namespace filter** when you need hard tenant isolation. Multi-user SaaS, multi-agent systems, per-document indexes. Namespace is the strongest boundary and the most efficient — it is always the first filter to apply.

**Use entity filter** when you want to search within a logical topic group. "Search only the user's language preferences," "Search only the memories from the current project." Entity gives you sub-namespace isolation with the same graph quality guarantees as namespace.

**Use attribute filter** when you have dynamic, arbitrary criteria that can't be known at schema design time. Status fields, date ranges, confidence levels, source URLs. These are the most flexible but have the most overhead — use them for secondary narrowing after namespace/entity have already scoped the search.

## Performance characteristics

The practical performance impact of each filter type at 100K total memories:

ScenarioTraversal costp50 latencyRecall@10

No filter (100K vectors)O(log 100K)~0.15ms97.2%
Namespace: 1K memoriesO(log 1K)~0.04ms97.1%
Entity: 200 memoriesO(log 200)~0.02ms96.8%
Attribute filter (10% selectivity)O(log 100K) + exact match~0.17ms96.5%
Attribute filter (1% selectivity)O(log 100K) + exact match~0.19ms95.1%

Namespace and entity filters are faster than unfiltered search because the subgraph is smaller. Attribute filters have minimal latency overhead (the HNSW traversal dominates) but can see small recall drops at very high selectivity because the fixed candidate set may not contain enough matching results. In practice, for typical agent memory workloads, attribute filter selectivity is rarely below 5% — and at 5%+ selectivity, the oversampling heuristic maintains recall above 95%.

The key insight: Feather DB's filter strategy is optimized for the statistical distribution of AI agent memory workloads, where namespace and entity filters handle the vast majority of isolation needs, and attribute filters handle secondary dynamic criteria. This avoids the approximate pre-filter trap that degrades recall in general-purpose vector databases.

**Install:** `pip install feather-db` · **GitHub:** [github.com/feather-store/feather](https://github.com/feather-store/feather)

---

*This is the machine-readable mirror of the theory post at [getfeather.store/theory/feather-db-prefiltered-ann-search](https://getfeather.store/theory/feather-db-prefiltered-ann-search). For the full Feather DB documentation, see [getfeather.store/llms-full.txt](https://getfeather.store/llms-full.txt).*