Vector Databases and Indexes

Where embeddings live: exact (flat) search vs approximate nearest neighbour indexes (HNSW, IVF), Chroma and pgvector, and filtering by metadata.

What is it?

Once every chunk has an embedding, retrieval is a nearest neighbour search: given the query's vector, find the k stored vectors most similar to it (the top-k). A vector database (or vector store) is a system that stores vectors together with their text and metadata and answers that question quickly.

The naive way: flat (brute-force) search. Compare the query with every stored vector, compute cosine similarity (see embeddings), sort, return the best k. This is exact - it always finds the true nearest neighbours - and for up to tens of thousands of chunks it is perfectly fast. Its cost grows linearly: ten times more chunks means ten times more work per query. At millions of chunks with hundreds of dimensions each, scanning everything on every query becomes too slow.

Approximate nearest neighbour (ANN) indexes trade a tiny bit of accuracy for a huge speed-up. Instead of checking every vector, they use a data structure that leads them to the right neighbourhood and only check candidates there. They usually return the true top-k, but can occasionally miss one. The fraction of true neighbours an ANN search finds is called its recall; well-tuned indexes reach high recall while examining a small fraction of the data.

The two index families you will meet everywhere:

  • HNSW (Hierarchical Navigable Small World) - a multi-layer graph where each vector is linked to some of its near neighbours. A search starts at an entry point in the sparse top layer, greedily hops towards the query, then drops to denser layers to refine. Fast, high recall, supports inserts without rebuilding; uses extra memory for the links. The default choice in most vector databases.
  • IVF (Inverted File index) - cluster all vectors into nlist groups with k-means, each represented by a centre point (centroid). A query is compared with the centroids first, and then only the vectors in the closest nprobe clusters are scanned. Cheaper to build and lighter on memory; recall depends on how many clusters you probe, and clusters should be rebuilt when the data changes a lot.

Large-scale systems also compress vectors (for example product quantization, which stores a short code instead of full floating-point numbers) to fit more in memory, at some accuracy cost.

Metadata filtering restricts a search to chunks whose metadata matches a condition: dept = 'hr', year >= 2024, source in (...), or 'user is allowed to see this'. It is essential for multi-tenant apps and permissions (see rag-in-production). There are two basic approaches: pre-filtering (filter first, then find nearest neighbours among the survivors - always returns k results if they exist) and post-filtering (find the top-k nearest, then drop non-matching ones - may return fewer than k, or nothing). Good vector databases integrate filtering into the index search.

Choosing a store:

  • Chroma - an open-source embedded vector database you can pip install; stores vectors, documents and metadata on local disk. Great for learning, prototypes and small apps. Used throughout this subject.
  • pgvector - an extension that adds a vector column type and HNSW/IVFFlat indexes to PostgreSQL. If you already run Postgres, you get vector search plus SQL filters, joins, transactions, backups and permissions in one place.
  • Dedicated vector databases and search engines (many managed services exist, and general search engines have added vector support) - for very large scale, high query volume, or built-in hybrid search. Pick based on scale, operations and the features you need, not hype.

Whatever the store, you keep three things together per chunk: the id, the embedding, and the document text + metadata. And you must always use the same embedding model for stored chunks and queries - vectors from different models live in different spaces and cannot be compared.

Explain like I'm 10

Flat search is finding the closest café by measuring the distance to every café in the country. An IVF index is first asking 'which city is closest?', then only checking cafés in that city (and maybe the next-closest city too, that is nprobe). HNSW is asking a well-connected local: they point you to someone in the right region, who points you to someone in the right street, who points you to the café - a few hops instead of a national survey. Metadata filtering is saying 'only cafés open on Sunday'.

Examples

Brute-force vs bucketed (IVF-style) approximate search: speed vs recall

// Deterministic random numbers so the output is reproducible
function rng(seed) { let s = seed >>> 0; return () => { s = (s * 1664525 + 1013904223) >>> 0; return s / 4294967296; }; }
const rand = rng(42);
const DIM = 8, N = 3000, K = 10;
const normalize = (v) => { const n = Math.hypot(...v); return v.map((x) => x / n); };
const dot = (a, b) => { let s = 0; for (let i = 0; i < a.length; i++) s += a[i] * b[i]; return s; };

// Fake "embeddings": points scattered around 12 topic centres
const topics = Array.from({ length: 12 }, () => Array.from({ length: DIM }, () => rand() * 2 - 1));
const noisyNear = (c) => normalize(c.map((x) => x + (rand() - 0.5) * 0.8));
const data = Array.from({ length: N }, (_, i) => ({ id: i, v: noisyNear(topics[i % 12]) }));

function bruteForce(q) {
  const scored = data.map((d) => ({ id: d.id, score: dot(q, d.v) }));
  return { hits: scored.sort((a, b) => b.score - a.score).slice(0, K), compared: data.length };
}

// Build the IVF index: k-means into NLIST buckets
const NLIST = 30;
let centroids = data.slice(0, NLIST).map((d) => d.v.slice());
let assign = new Array(N).fill(0);
for (let iter = 0; iter < 6; iter++) {
  const sums = centroids.map(() => new Array(DIM).fill(0));
  const counts = new Array(NLIST).fill(0);
  data.forEach((d, i) => {
    let best = 0;
    for (let c = 1; c < NLIST; c++) if (dot(d.v, centroids[c]) > dot(d.v, centroids[best])) best = c;
    assign[i] = best; counts[best]++;
    d.v.forEach((x, j) => { sums[best][j] += x; });
  });
  centroids = sums.map((s, c) => (counts[c] ? normalize(s) : centroids[c]));
}
const buckets = centroids.map(() => []);
data.forEach((d, i) => buckets[assign[i]].push(d));

function ivfSearch(q, nprobe) {
  const nearest = centroids.map((c, i) => ({ i, s: dot(q, c) })).sort((a, b) => b.s - a.s).slice(0, nprobe);
  const candidates = nearest.flatMap((b) => buckets[b.i]);
  const hits = candidates.map((d) => ({ id: d.id, score: dot(q, d.v) })).sort((a, b) => b.score - a.score).slice(0, K);
  return { hits, compared: candidates.length + NLIST };
}

const queries = Array.from({ length: 20 }, (_, i) => noisyNear(topics[i % 12]));
for (const nprobe of [1, 2, 4, 30]) {
  let recall = 0, compared = 0;
  for (const q of queries) {
    const truth = new Set(bruteForce(q).hits.map((h) => h.id));
    const approx = ivfSearch(q, nprobe);
    recall += approx.hits.filter((h) => truth.has(h.id)).length / K;
    compared += approx.compared;
  }
  console.log("nprobe=" + nprobe + "  recall@10=" + (recall / queries.length).toFixed(2) +
    "  vectors compared per query=" + Math.round(compared / queries.length) + " (brute force: " + N + ")");
}

Probing only the closest bucket compares a small fraction of the vectors but can miss true neighbours that landed in a neighbouring bucket. Probing more buckets raises recall towards 1.0 at the cost of more comparisons; probing all of them is just brute force plus overhead. HNSW makes the same speed/recall trade-off with a graph instead of buckets, tuned by ef_search.

Pre-filtering vs post-filtering with metadata

const chunks = [
  { id: "a", v: [0.95, 0.31], meta: { dept: "eng", year: 2025 }, text: "Eng on-call leave rules" },
  { id: "b", v: [0.93, 0.37], meta: { dept: "eng", year: 2024 }, text: "Eng leave calendar" },
  { id: "c", v: [0.90, 0.44], meta: { dept: "sales", year: 2025 }, text: "Sales leave blackout dates" },
  { id: "d", v: [0.80, 0.60], meta: { dept: "hr", year: 2025 }, text: "HR annual leave policy: 25 days" },
  { id: "e", v: [0.70, 0.71], meta: { dept: "hr", year: 2023 }, text: "HR old leave policy: 22 days" },
  { id: "f", v: [0.10, 0.99], meta: { dept: "hr", year: 2025 }, text: "HR parking rules" },
];
const query = [0.97, 0.24];   // "how many days of leave do I get?"
const cos = (a, b) => (a[0] * b[0] + a[1] * b[1]) / (Math.hypot(...a) * Math.hypot(...b));
const top = (items, k) => items.map((c) => ({ id: c.id, text: c.text, score: +cos(query, c.v).toFixed(3) }))
  .sort((x, y) => y.score - x.score).slice(0, k);
const isHr2025 = (c) => c.meta.dept === "hr" && c.meta.year >= 2025;

const post = top(chunks, 3).filter((h) => isHr2025(chunks.find((c) => c.id === h.id)));
const pre = top(chunks.filter(isHr2025), 3);
console.log("post-filter (search top-3, then filter):", post);
console.log("pre-filter (filter, then search top-3):", pre);

Post-filtering threw away all three nearest hits because they belonged to other departments, returning nothing even though a perfect HR answer exists. Pre-filtering (or a database that filters during the index search) returns the right chunk. When you post-filter, over-fetch (for example top-50) to reduce this risk.

Chroma: store with metadata, query with filters (Python)

# pip install chromadb sentence-transformers
import chromadb
from sentence_transformers import SentenceTransformer

model = SentenceTransformer("all-MiniLM-L6-v2")          # 384-dimensional vectors
client = chromadb.PersistentClient(path="./db")           # data persists on disk
col = client.get_or_create_collection("docs")

docs = [
    "Employees get 25 days of annual leave per year.",
    "Up to 5 unused leave days carry over to next year.",
    "Engineers on call receive one extra day off per week on call.",
    "Expense receipts must be submitted within 30 days.",
]
metas = [
    {"source": "handbook.pdf", "page": 4, "dept": "hr", "year": 2025},
    {"source": "handbook.pdf", "page": 4, "dept": "hr", "year": 2025},
    {"source": "eng-wiki.md", "page": 1, "dept": "eng", "year": 2024},
    {"source": "finance.pdf", "page": 2, "dept": "finance", "year": 2025},
]
col.add(
    ids=[f"chunk-{i}" for i in range(len(docs))],
    documents=docs,
    embeddings=model.encode(docs, normalize_embeddings=True).tolist(),
    metadatas=metas,
)

q = model.encode(["How much holiday do I get?"], normalize_embeddings=True).tolist()

def show(res):
    for doc, meta, dist in zip(res["documents"][0], res["metadatas"][0], res["distances"][0]):
        print(f"  {dist:.3f}  {meta['source']} p{meta['page']}: {doc}")

print("no filter:");             show(col.query(query_embeddings=q, n_results=3))
print("only HR:");               show(col.query(query_embeddings=q, n_results=3, where={"dept": "hr"}))
print("HR or eng, 2025+:");      show(col.query(query_embeddings=q, n_results=3,
                                     where={"$and": [{"dept": {"$in": ["hr", "eng"]}}, {"year": {"$gte": 2025}}]}))
print("text must contain 'carry':"); show(col.query(query_embeddings=q, n_results=3,
                                     where_document={"$contains": "carry"}))

Chroma keeps ids, embeddings, documents and metadata together and indexes vectors with HNSW. 'distances' are lower-is-better. Chroma's default distance is L2; because we normalise the embeddings, L2 distance ranks results in exactly the same order as cosine similarity (squared L2 = 2 - 2 x cosine). 'where' filters on metadata with operators such as $eq, $ne, $gt, $gte, $lt, $lte, $in, $nin, $and and $or; 'where_document' filters on the text itself.

pgvector: a vector column, an HNSW index and a filtered top-k query (SQL)

-- Enable the extension (once per database)
CREATE EXTENSION IF NOT EXISTS vector;

CREATE TABLE chunks (
  id         bigserial PRIMARY KEY,
  source     text NOT NULL,
  page       int,
  dept       text NOT NULL,
  content    text NOT NULL,
  embedding  vector(384) NOT NULL          -- must match the embedding model's dimensions
);

-- Approximate index for cosine distance. m = links per node, ef_construction = build effort
CREATE INDEX chunks_embedding_hnsw ON chunks
  USING hnsw (embedding vector_cosine_ops) WITH (m = 16, ef_construction = 64);
CREATE INDEX chunks_dept ON chunks (dept);

-- Insert (the app sends the vector as a literal like '[0.01, -0.2, ...]' or via a driver)
-- INSERT INTO chunks (source, page, dept, content, embedding) VALUES ($1, $2, $3, $4, $5);

-- Query: higher ef_search = better recall, slower
SET hnsw.ef_search = 100;
SELECT id, source, page, content,
       1 - (embedding <=> $1) AS cosine_similarity     -- <=> is cosine DISTANCE
FROM chunks
WHERE dept = 'hr'
ORDER BY embedding <=> $1
LIMIT 5;

-- Alternative: IVFFlat (build AFTER loading data; lists = number of clusters)
-- CREATE INDEX ON chunks USING ivfflat (embedding vector_cosine_ops) WITH (lists = 100);
-- SET ivfflat.probes = 10;

The operator <=> is cosine distance (<-> is L2 distance, <#> is negative inner product), and the index operator class must match the operator you sort by or the index is not used. With an approximate index, a WHERE filter is applied to the candidates the index returns, so a very selective filter can yield fewer than LIMIT rows; raise ef_search, add a regular index on the filter column, or use the iterative index scans available in newer pgvector versions. From Python, the pgvector package's register_vector(conn) lets you pass NumPy arrays directly as query parameters.

How it works

Flat index. Store vectors in an array; for a query compute all N similarities and keep the k best (with a small heap). Cost is proportional to N x dimensions per query. Exact, simple, no build time. Libraries make this very fast with vectorised maths, so it is a good choice up to a surprisingly large N.

IVF. Build: run k-means to get nlist centroids, assign every vector to its nearest centroid (an inverted list per centroid). Search: rank the centroids by similarity to the query, scan the vectors in the top nprobe lists. Work per query is roughly nlist + N x nprobe / nlist comparisons. Increasing nprobe raises recall and latency.

HNSW. Each vector is a node in a graph and is linked to up to M close neighbours. Nodes are also randomly promoted to higher layers, each sparser than the one below, like an express lane. Search starts at the top layer, greedily moves to whichever neighbour is closest to the query until no neighbour is closer, then descends a layer and repeats. On the bottom layer it keeps a candidate list of size ef_search and returns the best k. Bigger M and ef_construction build a better graph (more memory, slower build); bigger ef_search explores more at query time (higher recall, slower).

Distance metrics. Cosine distance (1 - cosine similarity), dot product and L2 (Euclidean) distance. For normalised vectors all three give the same ranking, which is why normalising embeddings is a good habit. Use the metric your embedding model was trained for, and make the index metric match the query operator.

Updates and deletes. HNSW supports inserts incrementally; deletes are often handled by marking entries as deleted and cleaning up later. IVF centroids drift as data changes, so large changes call for a rebuild. Any change of embedding model means re-embedding everything into a new index.

Flat: compare with ALL vectors        O(N)
 q -> [v1][v2][v3][v4] ... [vN]

IVF: compare with centroids, scan nprobe buckets
 q -> c1  c2  c3  c4  c5        (centroids)
          |       |
        [....]  [....]          (only these)

HNSW: greedy hops, layer by layer
 L2:  o-----------o--------o
                  |
 L1:  o----o------o----o---o
                       |
 L0:  o-o-o-o-o-o-o-o-[o]-o-o   -> top-k

Why does it exist?

Semantic search needs 'find the most similar vectors' to be fast at scale and combined with ordinary filters, persistence and updates. Traditional databases were built for exact matches and ranges, not for nearest neighbours in hundreds of dimensions. Vector indexes and databases fill that gap, and extensions like pgvector bring the capability into databases teams already run.

When to use it

Use a vector store whenever you do semantic retrieval over more than a handful of chunks. Start with flat search or Chroma for prototypes; use pgvector if you already run Postgres and want SQL filters, joins and one system to operate; consider a dedicated or managed vector search service for very large collections, high query rates or advanced features like built-in hybrid search and multi-tenancy.

When not to use it

For a few hundred or thousand chunks, an in-memory NumPy array with brute-force cosine is simpler and exact. For exact lookups (an order by id, a customer by email) use normal database queries, not vector search. Do not add a separate vector database to your architecture if pgvector in your existing Postgres meets your scale.

Common mistakes

  • Embedding queries with a different model (or different normalisation) than the stored chunks, which makes similarities meaningless.

  • Mismatched metrics: building a cosine index but querying with L2 (or vice versa), so the index is ignored or results are wrong.

  • Post-filtering a small top-k and getting zero results for selective filters.

  • Storing vectors without the chunk text and metadata, so results cannot be shown, cited or filtered.

  • Assuming ANN results are exact; not measuring recall against brute force when tuning parameters.

  • Building an IVF index on an empty or tiny table, so the clusters do not represent the real data.

  • Changing the embedding model without re-embedding and rebuilding the whole index.

Practice exercises

  1. Easy:

    In the IVF demo, change NLIST to 12 and to 60. How do recall and 'vectors compared' change for nprobe=1? Explain why.

  2. Easy:

    In the filtering demo, change post-filtering to over-fetch: search top-6, filter, then keep 3. Does it now find the HR chunks?

  3. Medium:

    Run the Chroma example and add a 'visibility' metadata field ('public' or 'internal'). Write a query that only returns public HR chunks from 2025 onwards.

  4. Medium:

    Write a Python function that compares Chroma's results with a brute-force NumPy cosine search over the same vectors for 50 random queries and reports recall@5.

  5. Hard:

    Set up Postgres with pgvector (for example via Docker), load 10,000 chunks with 384-dimensional embeddings, and measure query latency and recall@10 (against an exact query without the index) for hnsw.ef_search = 10, 40 and 200.

Interview questions

What is approximate nearest neighbour search and why use it?

Finding vectors that are very likely the nearest to a query without comparing against every vector, using an index such as HNSW or IVF. It trades a small loss in recall for large gains in speed, which matters once collections reach millions of vectors and queries must return in milliseconds.

Explain HNSW in a few sentences.

A layered proximity graph: every vector links to M near neighbours, and a random subset also appears in sparser upper layers. Search enters at the top, greedily walks towards the query, descends layer by layer, and on the bottom layer explores a candidate list of size ef_search to return the top-k. M and ef_construction control build quality and memory; ef_search controls query-time recall versus latency.

How does IVF work and what are nlist and nprobe?

IVF clusters vectors with k-means into nlist clusters. At query time it compares the query to all centroids, then exhaustively scans only the vectors in the nprobe nearest clusters. More probes means higher recall but more work; nlist trades build cost and bucket size.

What is the difference between pre-filtering and post-filtering?

Pre-filtering restricts the candidate set by metadata before (or during) the nearest neighbour search, so you get the best k among matching items. Post-filtering searches first and filters the top-k afterwards, which can return fewer than k or no results when the filter is selective. Over-fetching or filter-aware indexes mitigate this.

When would you choose pgvector over a dedicated vector database?

When you already run Postgres and your scale fits: you get vector search alongside relational data, SQL filters and joins, transactions, existing backups, permissions and monitoring, with one less system to operate. Dedicated systems make sense for very large scale, very high query throughput, or features you would otherwise build yourself.

Why must queries and documents use the same embedding model?

Each model defines its own vector space; dimensions and directions mean different things across models. Comparing a vector from model A with one from model B is meaningless, even if the dimensions happen to match. Changing models requires re-embedding the entire corpus.

Which distance metric should you use?

The one the embedding model was trained for, usually cosine similarity or dot product. If vectors are normalised to length 1, cosine, dot product and L2 produce identical rankings. The index's metric must match the query operator.