Vector Databases & ANN Indexes

A flat array of embeddings scales to about 50k–100k vectors before linear-scan latency becomes a real problem. Above that, an index structure is needed that trades a bounded amount of recall for O(log n) or better query time. That is what a vector database is: an ANN index wrapped in a storage and serving layer.

Why exact KNN does not scale

Brute-force k-nearest-neighbor computes cosine similarity between the query and every stored vector, sorts the scores, and returns top-k. It is exact and requires no preprocessing, but costs O(n·d). Ten million vectors at 1,536 dimensions require about 15 billion multiply-accumulate operations per query.

The trade-off ANN algorithms accept is “approximate”; they do not guarantee finding the exact nearest neighbor on every query. In practice, a well-tuned index returns 95–99% of the true top-k neighbors at 1/100th the compute cost. For retrieval in AI systems, that is almost always the right trade.

How ANN narrows the search

HNSW stores a layered proximity graph. Sparse upper layers connect distant landmark nodes, while the bottom layer contains a denser graph over the corpus. A query starts in an upper layer, follows edges toward progressively closer nodes, and descends until it reaches a small candidate region. Query-time search breadth controls how many candidates are explored before returning top-k.

IVF partitions vectors around trained centroids. Query processing finds the nearest centroids and scans only their inverted lists. The number of probed lists controls the recall and latency trade-off. Product quantization can compress list entries when raw vectors do not fit the memory budget.

Metadata filters complicate both structures. Post-filtering retrieves global neighbors and discards rows that fail the predicate, which can leave fewer than k results for selective filters. Pre-filtering can disconnect an HNSW graph or force a scan over a small subset. Databases that support filtered ANN integrate predicate checks into traversal or run iterative scans until enough qualifying candidates have been found.

HNSW

Hierarchical Navigable Small World (original paper) is the dominant algorithm in production vector databases. Its main parameters are:

• m; bidirectional edges per node in the proximity graph. Higher m → better recall, more memory, slower inserts. Typical range: 16–64.
• ef_construction; size of the dynamic candidate list during index build. Higher → better graph quality, slower build. Typical: 64–200.
• ef_search; candidate list size during query traversal. Higher → better recall, slower queries. It is tunable at query time without rebuilding the index.

HNSW inserts are O(log n) and updates are supported (though expensive). The index is memory-resident by default: 10M vectors at float32, 1536 dimensions, with m=16 requires roughly 60 GB for raw vectors plus ~20% overhead for graph edges. Most databases now offer on-disk variants (pgvector’s diskann extension, Qdrant’s on-disk segments) for corpora that do not fit in RAM.

IVF and IVF-PQ

Inverted File Index trains a k-means quantizer to partition the space into nlist Voronoi cells, then stores an inverted list of which vectors belong to each cell. At query time, find the nearest nprobe centroids and scan only those lists.

• nlist: a common starting heuristic is sqrt(n) for a corpus of n vectors.
• nprobe: nprobe=1 gives maximum speed but poor recall; nprobe=nlist degrades to a full scan. Typical production values: 10–50.

IVF is often combined with Product Quantization (IVF-PQ), which compresses each vector into a compact code by independently quantizing sub-vectors. A 1,536-dimensional float32 vector occupies about 6 KB; a 64–128 byte code reduces that footprint by roughly 50–100× at some recall cost.

The build process requires all vectors upfront for the k-means clustering step. IVF does not support incremental inserts well; HNSW does.

ScaNN

Google’s ScaNN uses anisotropic vector quantization. Instead of minimizing uniform reconstruction error, it optimizes inner-product preservation between query and document vectors. This can improve recall per compression ratio when query and document embeddings follow different distributions.

Implementations

pgvector

pgvector adds a vector type and HNSW/IVF indexes to Postgres. It adds ANN search without introducing another data service.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# pip install psycopg2-binary pgvector openai
import psycopg2
from pgvector.psycopg2 import register_vector
from openai import OpenAI

conn = psycopg2.connect("postgresql://localhost/mydb")
register_vector(conn)
cur = conn.cursor()

cur.execute("""
    CREATE TABLE IF NOT EXISTS documents (
        id        serial PRIMARY KEY,
        chunk     text,
        embedding vector(1536)
    )
""")
# Build HNSW with cosine distance — ef_search is tunable per-query without rebuilding
cur.execute("""
    CREATE INDEX IF NOT EXISTS docs_hnsw
    ON documents USING hnsw (embedding vector_cosine_ops)
    WITH (m = 16, ef_construction = 64)
""")
conn.commit()

openai_client = OpenAI()

def upsert(chunk: str) -> None:
    resp = openai_client.embeddings.create(model="text-embedding-3-small", input=chunk)
    vec = resp.data[0].embedding
    cur.execute(
        "INSERT INTO documents (chunk, embedding) VALUES (%s, %s)",
        (chunk, vec),
    )
    conn.commit()

def search(query: str, top_k: int = 5) -> list[tuple[str, float]]:
    resp = openai_client.embeddings.create(model="text-embedding-3-small", input=query)
    qvec = resp.data[0].embedding
    # ef_search > ef_construction is valid and improves recall at query time
    cur.execute("SET hnsw.ef_search = 100")
    cur.execute(
        """
        SELECT chunk, 1 - (embedding <=> %s::vector) AS score
        FROM documents
        ORDER BY embedding <=> %s::vector
        LIMIT %s
        """,
        (qvec, qvec, top_k),
    )
    return cur.fetchall()

Qdrant

Qdrant integrates payload filters directly into HNSW graph traversal, avoiding the post-filter recall degradation that plagues bolt-on approaches.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# pip install qdrant-client openai
import uuid
from qdrant_client import QdrantClient
from qdrant_client.models import (
    Distance, VectorParams, PointStruct,
    Filter, FieldCondition, MatchValue,
)
from openai import OpenAI

qdrant = QdrantClient(url="http://localhost:6333")
openai_client = OpenAI()
COLLECTION = "documents"

qdrant.create_collection(
    collection_name=COLLECTION,
    vectors_config=VectorParams(size=1536, distance=Distance.COSINE),
)

def upsert(chunk: str, user_id: str) -> None:
    resp = openai_client.embeddings.create(model="text-embedding-3-small", input=chunk)
    qdrant.upsert(
        collection_name=COLLECTION,
        points=[PointStruct(
            id=str(uuid.uuid4()),
            vector=resp.data[0].embedding,
            payload={"chunk": chunk, "user_id": user_id},
        )],
    )

def search(query: str, user_id: str, top_k: int = 5):
    resp = openai_client.embeddings.create(model="text-embedding-3-small", input=query)
    return qdrant.search(
        collection_name=COLLECTION,
        query_vector=resp.data[0].embedding,
        query_filter=Filter(
            must=[FieldCondition(key="user_id", match=MatchValue(value=user_id))]
        ),
        limit=top_k,
    )

Choosing a vector database

The decision is mostly an operational one. When Postgres already operates at the required corpus scale, pgvector keeps the operational surface minimal and transaction semantics simple. If filtered search across large multi-tenant corpora is a first-class requirement, Qdrant’s native filter integration pays for the added service. When index operations should remain outside the on-call scope, Pinecone is a fully managed API.

Index choice should be tested against the actual corpus and filters. A useful benchmark starts with exact KNN on a representative sample to establish the true top-k set. Each ANN configuration then runs the same queries while recording recall@k, p50 and p99 latency, index size, and build time. The result is a curve rather than one winning configuration: increasing ef_search or nprobe usually trades latency for recall, while compression changes memory use and reconstruction error.

Filtered queries need a separate workload. An index can perform well on unfiltered semantic search and fail when a tenant or document-type predicate leaves only a small fraction of the corpus eligible. The benchmark distribution should include common filters, highly selective filters, and queries with fewer than k valid results. This catches post-filter implementations that appear fast but return too few neighbors.

Ingestion behavior also affects the choice. HNSW supports incremental insertion, but sustained writes can change latency and graph quality. IVF depends on trained centroids, so a corpus whose distribution shifts may need retraining. Deletion semantics matter as well: some systems mark vectors deleted and compact later, causing temporary storage growth. Query benchmarks therefore run alongside insert, update, delete, and compaction tests under realistic concurrency.

Failure modes

Recall degrades silently. A misconfigured ef_search or nprobe can drop recall from 98% to 70% with no error and no warning; queries just start returning worse results. Measure recall@k against a held-out ground-truth set during index-parameter tuning, and re-run that measurement after changes to index configuration or corpus composition.

Index build cost for HNSW is significant. Building HNSW over 10M vectors with m=16, ef_construction=200 can take 30–60 minutes on a single machine. For streaming ingestion pipelines, this matters: the index cannot be rebuilt the index after every insert. Plan for background index builds and understand whether the database handles incremental HNSW inserts (most do, with per-insert cost proportional to m).

Filtered ANN is harder than it looks. Naive post-filtering: run ANN for top-500, then filter. If only 0.1% of the corpus belongs to the target user, top-500 may contain zero matching results. Pre-filtering restricts graph traversal to matching nodes; effective when the filter is selective, but requires the database to integrate filter logic into the traversal. pgvector 0.7+ supports iterative index scans that approximate this; Qdrant does it natively. Know which mode the database uses before designing a multi-tenant retrieval system.

Embedding drift invalidates every stored vector. Upgrading the embedding model, for example from text-embedding-3-small to text-embedding-3-large, makes all stored vectors incompatible with new query vectors. Cosine similarity across different model versions is meaningless. Treat a model change as a full corpus re-embed plus index rebuild: it is a breaking schema migration, not a rolling update. Version-lock the embedding model identifier in your application config.

Memory requirements are large and non-obvious. A 10M-vector HNSW index at float32, 1536 dims, m=16 requires ~60 GB for raw vectors plus ~10 GB for graph edges. Most teams underestimate this when sizing. Use dimension reduction (MRL truncation to 512 dims from text-embedding-3-small), IVF-PQ compression, or on-disk index variants when memory is constrained.

Small corpora often need no dedicated vector database. For corpora under 100k vectors, a flat numpy scan or SQLite with pgvector is fast enough at < 5ms query latency. The operational complexity of a dedicated vector database is not justified until you hit meaningful scale or require filtered ANN with selective predicates.

Further reading

• ANN Benchmarks; a benchmark of ANN algorithms: recall vs. queries-per-second across HNSW, IVF, ScaNN, Annoy, and others on standardized datasets. Useful for index selection and tuning.
• Pinecone’s vector database overview covers HNSW, IVF-PQ, and index trade-offs.
• Eugene Yan’s applied ML articles cover retrieval and two-stage ranking systems.
• Chip Huyen’s LLM engineering overview discusses latency and cost across a retrieval stack.