Vector Databases — pgvector, HNSW, IVF

Why this session exists

Nearest-neighbor search is an index capability, not a requirement to buy a separate database. For N vectors of dimension d, an exact dense scan computes O(Nd) arithmetic and reads the relevant vector bytes. Ten million 1024-dimensional float32 vectors occupy 40.96 GB decimal (about 38.15 GiB), before IDs or indexes. That is a footprint, not “40GB of dot products.” Exact search remains viable for small authorized subsets, batch workloads or suitable hardware; no universal 100K, 10M or 100M boundary chooses an index.

After this lesson you should explain graph traversal, inverted lists and quantization, tune their build/query parameters, compare databases under filtering and update requirements, and diagnose recall/latency regressions. Sessions 117–118 supply ingestion and retrieval context.

Exact geometry and the dimensionality caveat

Cosine is dot(x,y)/(norm(x)*norm(y)) for nonzero vectors; it does not require inputs already normalized. Normalizing makes it equal to a dot product. For two unit vectors, squared Euclidean distance is 2-2*dot(x,y), hence all three rankings agree. With variable norms, dot-product and cosine rankings can differ dramatically. A zero vector has undefined cosine and needs explicit rejection or a declared convention.

The neighborhood analogy is useful: IVF checks selected neighborhoods; HNSW follows coarse express routes before local streets. Neither guarantees the nearest shop was visited. In high-dimensional random data, distances often concentrate. For independent unit-variance Gaussian coordinates, squared distance has mean 2d and variance 8d, giving relative standard deviation sqrt(2/d). That explains why axis-aligned bounds can prune poorly. It does not prove that all exact algorithms must scan every point on all high-dimensional datasets: intrinsic dimension, structure, metric, preprocessing and query regime matter. Approximation is a tradeoff, not a logical requirement.

HNSW: graph construction and query budgets

HNSW's authors describe a hierarchy with exponentially decreasing layer populations. Every item is in the bottom layer; random upper-layer membership supplies longer-range navigation. Search greedily descends upper layers, then maintains a bounded exploratory frontier at the bottom rather than committing to one greedy neighbor.

M controls connection capacity and graph memory; ef_construction controls insertion-time search effort; ef_search controls query exploration. It is wrong to name only two parameters and omit construction effort. M is not simply the exact degree of every node. Graph construction searches for neighbors and applies selection heuristics; higher effort can improve the graph but costs work. Recall is empirical: “O(log N × ef)” is a useful intuition in favorable regimes, not a worst-case bound or an exact visit count. Deletes, graph aging, out-of-distribution queries and filtering warrant fresh measurements.

For pgvector 0.8.1, the documented defaults are m=16, ef_construction=64, hnsw.ef_search=40; do not transplant another library's 200 construction default. Start from versioned defaults, sweep budgets, and report recall with p50/p95, build time and memory on your distribution.

IVF-Flat and product quantization

IVF learns coarse centroids, assigns vectors to inverted lists and probes selected lists at query time. With reasonably balanced lists, candidate comparisons are about N*nprobe/nlist, plus coarse-centroid search and bookkeeping. Training requires a representative sample; k-means is iterative, not “one pass.” IVF-Flat stores full vectors; partitioning alone does not provide PQ's compression.

For an exact coarse assignment and uncompressed vectors, probing all lists recovers an exhaustive scan's results under consistent ties. Probing 200 of 316 lists scans about 63% of balanced data, not “almost all” by definition. pgvector recommends starting lists around N/1000 up to one million rows and sqrt(N) above that, then tuning probes starting around sqrt(lists). These are guidelines, not optimality laws.

PQ partitions a d-dimensional vector into m subvectors and learns K codewords for each subspace. With K=256, each code uses one byte. A 1024-float vector takes 4096 bytes; m=16 uses 16 code bytes, a 256× payload compression. Codebooks take m*K*(d/m)*4 = K*d*4 bytes (about 1MiB here), and IDs/list/graph metadata are additional. One hundred million such codes occupy 1.6GB decimal, versus 409.6GB for raw vectors; retaining originals for exact reranking adds that storage back somewhere.

Asymmetric distance computation leaves the query uncompressed and adds per-subspace lookup distances to the stored codewords. Reranking original vectors can fix quantized ordering within retrieved candidates, not rescue omitted candidates. No fixed 1–3-point recall loss is promised. Faiss IVFPQ's source identifies both inverted lists and PQ codes.

Historical context: HNSW's preprint dates to 2016; Faiss's GPU similarity-search paper is from 2017, not the original timeline's 2010 Faiss launch. pgvector added HNSW in 0.5.0; the later 0.8.0 iterative-scan change is separate. These are feature milestones, not proof that Pinecone was the first managed vector database or that all products share one index implementation.

Choosing storage and filtering semantics

• pgvector/Postgres: transactional vectors and relational rows, SQL joins and existing backup/auth practices can reduce integration work. Index memory competes with OLTP; vacuum, build locks, replicas and filtered-query plans still cost operations. “Already running Postgres” is not “free.”
• Pinecone: evaluate the managed service's current filter, freshness, isolation, availability and billing contracts. Do not infer its private implementation is universally HNSW or quote old per-vector pricing as a current fact.
• Qdrant or Weaviate: evaluate payload/filter indexes, hybrid retrieval, update/delete behavior and operational ownership on your workload; neither is universally faster or restricted to a fixed size band.
• Milvus/Zilliz: consider index choices, storage tiers and deployment complexity when independent scaling is justified; do not assume every Faiss index/kernel is exposed in every release.
• Faiss in process: useful for offline/static or embedded search. You own persistence, replication, IDs, permissions and lifecycle. Update support depends on index type; a full rebuild is not universally required.

This is a decision framework, not an independently benchmarked vendor ranking. Define a measurable exit criterion from the existing store: refresh window, recall at latency SLO, memory pressure or interference with transactions. Separate storage introduces synchronization/deletion/permission-drift risks; same-store transactions help only if updates are actually performed atomically and application authorization is correct.

pgvector's approximate search may apply a filter after an index scan; SQL WHERE does not itself prove ANN prefiltering. At 1% selectivity, a fixed candidate budget can yield very few eligible rows. Version 0.8.0 introduced iterative scans that search more until enough results or a bound is reached; this was not a 0.7 guarantee. Other options are exact search over a selective subset, partial indexes, partitioning, larger budgets or an engine with a suitable filtered ANN algorithm. Measure gold neighbors within the eligible subset, not against unfiltered gold. Unauthorized results must never reach the generator even when recall is sacrificed.

Hands-on: exact oracle, IVF failure and PQ arithmetic

The CPU program uses supplied centroids to expose list selection. It is not a trained HNSW/pgvector benchmark. It tests a missed neighbor, exhaustive-probe recovery, filtering, and quantized distance against independent reconstruction.

import numpy as np
 
X = np.array([[0., 0.], [1., 0.], [1.1, 0.], [9., 0.], [10., 0.]])
centers = np.array([[0., 0.], [10., 0.]])
assignment = np.argmin(((X[:, None]-centers)**2).sum(2), axis=1)
 
def exact(q, eligible=None, k=2):
    ids = list(range(len(X))) if eligible is None else list(eligible)
    return sorted(ids, key=lambda i: (float(((X[i]-q)**2).sum()), i))[:k]
 
def ivf(q, probes, k=2, eligible=None):
    if not 1 <= probes <= len(centers):
        raise ValueError("probe range")
    lists = np.argsort(((centers-q)**2).sum(1), kind="stable")[:probes]
    allowed = set(range(len(X))) if eligible is None else set(eligible)
    candidates = [i for i in allowed if assignment[i] in lists]
    return exact(q, candidates, k)
 
q = np.array([5.2, 0.])
assert exact(q) == [3, 2]
assert ivf(q, 1) == [3, 4]  # misses id 2 across the partition boundary
assert ivf(q, 2) == exact(q)
assert exact(q, [0, 1, 2]) == [2, 1]
assert ivf(q, 1, eligible=[0, 1, 2]) == []
assert ivf(q, 2, eligible=[0, 1, 2]) == [2, 1]
# Tiny PQ: two one-dimensional codebooks, 2 bits per vector here.
books = [np.array([0., 2.]), np.array([0., 4.])]
x, query = np.array([1.8, 3.7]), np.array([1., 1.])
code = [int(np.argmin((book-x[j])**2)) for j, book in enumerate(books)]
reconstructed = np.array([books[j][c] for j, c in enumerate(code)])
adc = sum((books[j][c]-query[j])**2 for j, c in enumerate(code))
assert np.isclose(adc, ((reconstructed-query)**2).sum())
assert not np.isclose(adc, ((x-query)**2).sum())  # quantization is lossy
assert 1024*4/16 == 256
assert 100_000_000*1024*4 == 409_600_000_000
# Cosine and raw dot rankings need not agree.
a, b, query = np.array([1., 0.]), np.array([100., 100.]), np.array([1., 0.])
assert query@b > query@a
assert query@a/np.linalg.norm(a) > query@b/np.linalg.norm(b)
print("exact/IVF/PQ contracts pass; no ANN service benchmark")

A controlled pgvector benchmark recipe

Retain the original database exercise as an unexecuted, isolated-test-database procedure. Pin PostgreSQL and pgvector 0.8.1 and use a unique benchmark table, never DROP TABLE items in an existing application. Register the pgvector psycopg adapter for NumPy arrays or send vector text with an explicit ::vector cast; an arbitrary Python list can adapt as a PostgreSQL array rather than the required vector type.

Load a seeded synthetic fixture plus representative permitted data, normalize only if the metric contract calls for it, record actual row IDs, and ANALYZE. Establish exact gold first. Build only one candidate ANN index at a time, or explicitly verify the selected plan using EXPLAIN; leaving HNSW and IVF indexes together does not prove the second benchmark used IVF. Match vector_cosine_ops and ORDER BY embedding <=> query LIMIT k. Use SET LOCAL hnsw.ef_search or SET LOCAL ivfflat.probes within a transaction to avoid leaking settings through a pool. Record warm versus cold cache, repeated queries, concurrency, build time and memory. No 1–5ms or 0.99 recall result follows merely from N=100K.

For each setting, compute |ANN_k ∩ exact_k|/k with consistent ties and enough eligible rows. np.argpartition is unordered and takes a zero-based kth index; a stable sorted oracle is easier to inspect. Run the category-filter experiment at several selectivities with filtered gold and query plans. Iterative scans have limits, so record both insufficient-result rate and recall; do not declare a filter “fixed” from latency alone.

Production cases, memory and DiskANN

The original Notion migration and Spotify IVFPQ anecdotes were not established by their citations. They are replaced by explicit design cases: (1) co-locate transactional embeddings to reduce drift, measuring OLTP interference; (2) use compressed codes when raw vector memory dominates, validating recall; (3) tune search budgets and filters before blaming the model. These preserve the operational lessons without invented company incidents.

For five million 768-dimensional float32 vectors, raw payload is 15.36GB. A rough bottom-layer adjacency estimate with 64 four-byte neighbor IDs per node is 1.28GB; upper layers, allocator overhead, labels, deletions and workspaces are extra. The 16.64GB subtotal is not a complete RAM budget or proof that sharding is unnecessary. int8 payload is 3.84GB before scales and metadata, with empirical quality consequences.

DiskANN changes the storage tier: the disk-resident graph/full-vector structures are searched using compact in-memory representations and caching. The original claim that the whole graph necessarily fits in RAM was wrong. SSD reads, cache hit rate and beam/search policy matter; a published billion-point result is not a blanket guarantee for any 32GB machine, nor a proof of pgvectorscale performance.

Recall and stretch: complete answers

1. HNSW: a hierarchical proximity graph navigated coarse-to-fine with bounded bottom-layer exploration; favorable empirical speed is not a universal logarithmic guarantee.
2. IVF: centroid-selected inverted lists reduce scanned candidates. IVF-Flat is not intrinsically a compressed-vector scheme; add PQ for that tradeoff.
3. Knobs: M and construction effort affect the graph; ef_search affects queries. nlist affects partitioning; nprobe affects query coverage.
4. 5M vectors plus Postgres? Benchmark pgvector first if transactional integration helps; decide from RAM, filters, updates and SLOs, not count alone.
5. 500M vectors and 32GB? A 16-byte PQ code payload is 8GB plus IDs/codebooks/index/runtime. IVFPQ or SSD-backed search may fit; full-vector reranking storage and measured recall remain constraints.
6. Recall tuning: parameters change searched candidates; measure quality and cost on a declared query set. Larger budgets need not improve every query monotonically in every approximate implementation.
7. PQ: learn subspace codebooks and store code indices. Compression reduces payload, with non-universal distortion/recall impact.
8. Filter cliff: try exact search over selective eligible rows or appropriate partial/partitioned/iterative/filtered ANN plans; verify the plan and eligible-gold denominator.
9. Build cost: HNSW repeatedly searches/selects/connects neighbors; IVF trains centroids and assigns points. Relative time depends on sample, iterations, parameters and implementation, not a universal theorem.
10. DiskANN stretch: SSD storage plus compact RAM representations/caching changes the RAM ceiling at the cost of I/O and search-policy complexity; the graph need not all be in RAM.

Explain an HNSW traversal, show why one-probe IVF misses the worked neighbor, and defend a database choice with a capacity and lifecycle budget. The same index can support agent memory and CLIP retrieval; not every dense search needs a database, and pgvector queries use SQL operators rather than a fictional MATCH ... USING hnsw command.

Optional resources and onward navigation

The original optional pre-read links are retained as navigation, not fact-check evidence or promises about video length, quality or API stability. Use the versioned primary sources in the teaching for consequential claims. Original pacing was a suggested 90-minute session, not a completion guarantee.

• What is a Vector Database?
• HNSW · Hierarchical Navigable Small World graphs
• pgvector in Postgres — hands-on
• Hierarchical Navigable Small Worlds (HNSW)
• pgvector · Postgres vector similarity search
• ANN Benchmarks · recall vs QPS across libraries

Next in the original sequence: S120 · LLM Agents — Function Calling, Tools, Planning. Publication and release navigation are adjudicated by the parent.

Hub: The 6-Month Learning Plan. The original 130-session scaffold is retained as navigation, not evidence that every destination has been reviewed.

Review and execution boundary

Reviewed against complete original and pre-edit current teaching with claim-specific primary evidence and independently replayed coverage. The executable CPU program is a bounded teaching test, not a pretrained model, serving, RAG or training benchmark. External model/service recipes remain source-supported and unexecuted. No weights, datasets, GPU, paid API or new service were used. Source publication is not end-to-end application acceptance.