Exact vs approximate search

When to scan exactly and when to use ANN — accuracy, latency, memory, and build-cost trade-offs.

Version
Latest
v0.1.0 · latest 2 min read
On this page
  1. The trade-off
  2. Decision guide
  3. Exactness guarantees worth knowing
diagram
flowchart TB
    Q["ORDER BY distance LIMIT k"] --> S{"table size\n+ settings?"}
    S -->|"small table, or\nann_enabled=off,\nor filtered,\nor repeatable-read"| EX["EXACT scan\n100% recall\ncost grows with rows"]
    S -->|"large table\n+ usable index\n+ unfiltered"| ANN["ANN (HNSW/IVF)\ncandidate retrieval\n+ exact re-rank\n~recall, fast"]
    EX --> R["top-k rows"]
    ANN --> R
Diagram source · mermaidcopy included
mermaidsource
flowchart TB
    Q["ORDER BY distance LIMIT k"] --> S{"table size\n+ settings?"}
    S -->|"small table, or\nann_enabled=off,\nor filtered,\nor repeatable-read"| EX["EXACT scan\n100% recall\ncost grows with rows"]
    S -->|"large table\n+ usable index\n+ unfiltered"| ANN["ANN (HNSW/IVF)\ncandidate retrieval\n+ exact re-rank\n~recall, fast"]
    EX --> R["top-k rows"]
    ANN --> R

The trade-off#

Exact scan Approximate (HNSW)
Recall 100% by construction High but < 100%; tunable via ef_search / oversampling
Latency Grows linearly with rows Grows slowly (graph traversal + re-rank)
Memory No index structure Graph + vectors resident (bounded by vector.max_memory_bytes)
Build cost None Paid at index build; rebuilt from rows after restore
Correctness risk None None for returned ordering — candidates are re-ranked with exact distances

Only publish recall/latency numbers you measured yourself on your data, model dimension, and hardware. This documentation makes no performance claims — see Performance.

Decision guide#

  1. Start exact. No index, ORDER BY distance LIMIT k, measure latency at your target row count.
  2. Fast enough? Stop. Indexes add build time, memory, and operational surface for no benefit on small tables.
  3. Too slow past ~tens of thousands of rows? Add USING hnsw, re-measure latency and recall against an exact baseline (SET vector.ann_enabled = off gives you the baseline on demand).
  4. Tune only with evidence. Raise ef_search until recall meets your bar; stop when latency exceeds budget. Record the setting alongside the measurement.

Exactness guarantees worth knowing#

  • Unfiltered, unindexed queries are always exact.
  • Filtered queries run exact even when an index exists.
  • Repeatable-read snapshots run exact to preserve snapshot semantics.
  • ANN candidates are always re-ranked with exact distances before LIMIT is applied — approximation affects which candidates are considered, never the arithmetic.
Was this page helpful?