Embeddings and Vector Search.

MegaMart Assist has been live for a week. Its answers sound fluent, but the search behind them keeps missing. (An illustrative scene: the customers, articles and times are made up; each failure is a classic one.)

None of these is a model bug. They're retrieval decisions: how text becomes vectors, how to find the nearest without scanning millions, how filters meet an approximate index, and how keyword and vector results combine.

Day 1 treated the model as a slow, metered dependency and sized its tokens. Today we build the search that decides which tokens it sees: semantic search over MegaMart's help articles and past resolved tickets. Tomorrow, Day 3 turns these results into a grounded answer.

01Chapter 1: What Is an Embedding?#

1.1 The Simple Definition#

An embedding is a fixed-length list of numbers that a model produces from a piece of text (or an image), trained so that inputs with similar meaning get vectors that are close together. "My parcel arrived broken" and "item damaged in delivery" share no words, but their vectors are neighbours.

A vector search takes a query vector and returns the stored vectors nearest to it: the k nearest neighbours (kNN).

Week 7, Day 1 built the inverted index and Week 7, Day 3 scored it with BM25. We don't replace them today. Chapter 9 combines both.

1.2 What the Model Gives You#

Embedding models differ in dimensions, input length and price. As of October 2026:

MegaMart Assist uses voyage-4 at 1,024 dimensions, because its customers write in English, Hindi and Hinglish (Day 3's pipeline embeds with it). Three facts from these docs shape the design:

• Dimensions are a cost knob. OpenAI says embeddings can be shortened "without the embedding losing its concept-representing properties": text-embedding-3-large cut to 256 still beats the older text-embedding-ada-002 at 1,536 (OpenAI docs). Fewer dimensions, less memory, faster maths.
• Queries and documents may need different treatment. Voyage's input_type "prepends a prompt to your inputs before vectorizing them": "Represent the query for retrieving supporting documents:" for queries, "Represent the document for retrieval:" for documents (Voyage docs). Cohere's v3+ models require an input_type: search_query or search_document for search (Cohere API reference). Swap them and recall drops.
• Vectors from different models aren't comparable. Chapter 13 handles the migration this forces.

1.3 Measuring "Close"#

OpenAI's embeddings "are normalized to length 1", so "cosine similarity can be computed slightly faster using just a dot product" and "cosine similarity and Euclidean distance will result in the identical rankings" (OpenAI docs). The rule: use the metric the model was trained for, normalise if the store's fast path needs it (Elasticsearch's dot_product similarity "requires vectors to be normalized", Elastic docs), and use the same metric at index and query time.

1.4 Bi-Encoders: Why Documents Can Be Embedded Ahead of Time#

An embedding model is a bi-encoder: it encodes query and document separately, so documents are embedded once at write time and a query costs one embedding call plus a lookup. Airbnb's search uses the same split: a listing tower that "could be computed offline on a daily basis" and a query tower run in real time (Airbnb Engineering). Cross-encoders, which read the pair together, rerank the shortlist in Day 3.

%% title: MegaMart Assist retrieval: write path and read path
flowchart TD
  CMS@{ icon: "sd:file", label: "Help articles, policies,<br/>playbooks (CMS)" }
  TK@{ icon: "sd:database", label: "Ticket store<br/>resolved tickets" }
  ING["Ingest worker<br/>split (Day 3), embed, upsert"]:::service
  EMB@{ icon: "sd:ml", label: "Embedding model<br/>voyage-4, 1,024 dims" }
  PG@{ icon: "tech:postgresql", label: "PostgreSQL + pgvector<br/>~171K document chunks<br/>HNSW + full text" }
  VX@{ icon: "sd:index", label: "Ticket summaries<br/>~3M vectors, HNSW<br/>(same Postgres today)" }
  U@{ icon: "sd:users", label: "Customers<br/>English, Hindi, Hinglish" }
  AS["MegaMart Assist<br/>(Day 1 gateway)"]:::core
  RS["Retrieval service<br/>embed query, filter,<br/>keyword + vector, fuse"]:::core
  D3["Day 3: rerank,<br/>assemble context"]:::service
  CMS --> ING
  TK --> ING
  ING --> EMB
  ING --> PG
  ING --> VX
  U --> AS
  AS --> RS
  RS --> EMB
  RS --> PG
  RS --> VX
  RS --> D3
  class CMS,TK,PG,VX store
  class EMB external
  class U client

1.5 Key Terms#

02Chapter 2: Exact Search and What It Costs#

The simplest vector search is a loop: compute the distance from the query to every stored vector, keep the best k.

# search/exact.py: exact top-k by cosine similarity (illustrative)
import numpy as np

def normalise(m: np.ndarray) -> np.ndarray:
    return m / np.linalg.norm(m, axis=-1, keepdims=True)

def exact_top_k(query: np.ndarray, docs: np.ndarray, k: int = 10):
    """docs: (N, d) float32, already normalised. One pass over every vector."""
    scores = docs @ normalise(query)            # N dot products = cosine similarities
    top = np.argpartition(-scores, k)[:k]       # O(N), no full sort
    return top[np.argsort(-scores[top])], scores

It's correct by construction, and for small corpora it's the right answer. The question is when it stops being one.

Exact search stays useful at scale in two places: ground truth (Chapter 7 measures every index against it) and highly selective filters (Chapter 8): if only 2,000 tickets match "this customer's orders", scanning those 2,000 beats any index.

Every ANN index makes the same bargain: look at a small fraction of the vectors and sometimes miss a true neighbour. They differ in how they pick the fraction, and what that costs.

03Chapter 3: HNSW, a Graph You Can Descend#

3.1 The Idea#

Hierarchical Navigable Small World graphs (Malkov and Yashunin, arXiv 2016, revised 2018) link each vector to some of its near neighbours, then stack sparser copies of the graph on top, like a skip list's "express lanes" (the paper notes the "similarity of the algorithm to the skip list structure"):

• Every vector lives in layer 0. Its top layer is drawn at random "with an exponentially decaying probability distribution"; with M = 16 and the paper's suggested mL = 1/ln(M), each layer keeps about 1 in 16 of the vectors below it.
• A search starts at a fixed entry point in the top layer, walks greedily to the neighbour closest to the query, drops a layer when it can't get closer, and repeats.
• In layer 0 it keeps a candidate list of size ef and explores neighbours of the best candidates until the list stops improving. The best k in that list are the answer.

Top layers make long jumps; the bottom layer does the fine search. That's how the paper gets "a logarithmic complexity scaling".

%% title: An HNSW search: long jumps on top, fine search at the bottom
flowchart TD
  Q(["Query vector<br/>#quot;parcel arrived broken#quot;"]):::core
  L2["Layer 2: 1 in 256 vectors<br/>(~12,500 of 3.2M), greedy hops"]:::service
  L1["Layer 1: 1 in 16<br/>(~200,000), closer region"]:::service
  L0["Layer 0: all 3.2M vectors<br/>best-first search, list of size ef"]:::service
  R(["Top k from the ef candidates"]):::ok
  Q -->|"enter at the top layer"| L2
  L2 -->|"no closer neighbour: drop a layer"| L1
  L1 -->|"drop a layer"| L0
  L0 --> R

3.2 The Three Knobs#

The paper's guidance: "A reasonable range of M is from 5 to 48", with bigger M "better for high recall and/or high dimensional data"; "2∙M is a good choice" for layer-0 links; and efConstruction should be large enough to reach construction recall near 1, "0.95 is enough for the most use-cases". FAISS's wiki gives 4 ≤ M ≤ 64 and says the speed-accuracy trade-off "is set via the efSearch parameter".

# search/hnsw_layer0.py: the best-first search inside one layer (illustrative)
import heapq

def search_layer(query, entry, ef, neighbours, dist):
    """neighbours(v) -> linked vertices; dist(q, v) -> distance. Returns the ef closest found."""
    visited = {entry}
    d0 = dist(query, entry)
    candidates = [(d0, entry)]                 # min-heap: closest unexplored first
    best = [(-d0, entry)]                      # max-heap of size ef: current results
    while candidates:
        d, v = heapq.heappop(candidates)
        if d > -best[0][0]:                    # closest candidate is worse than our worst result
            break                              # nothing left can improve the list
        for n in neighbours(v):
            if n in visited:
                continue
            visited.add(n)
            dn = dist(query, n)
            if len(best) < ef or dn < -best[0][0]:
                heapq.heappush(candidates, (dn, n))
                heapq.heappush(best, (-dn, n))
                if len(best) > ef:
                    heapq.heappop(best)        # drop the worst
    return sorted((-d, v) for d, v in best)

A larger ef keeps more candidates alive, visits more vectors, and finds more true neighbours. That's the whole recall-latency dial.

3.3 What HNSW Costs#

• Memory. FAISS puts HNSW at "(d * 4 + M * 2 * 4) bytes per vector": with d = 1,024 and M = 16, 4,096 bytes of vector plus 128 of links (the paper: "about 60-450 bytes per object" for the graph). Vectors dominate, and both must be in RAM.
• Build time. Each insert is a search plus link updates. Elastic calls building these structures "compute-intensive"; pgvector says "indexes build significantly faster when the graph fits into maintenance_work_mem". Give bulk builds memory and parallel workers.
• Updates and deletes. Inserts work incrementally (pgvector: an HNSW index "can be created without any data in the table since there isn't a training step"). Deletes are harder: FAISS says "HNSW does not support removing vectors from the index. This would destroy the graph structure". Databases mark deleted rows and clean up later, so a delete-heavy index degrades until it's vacuumed or rebuilt.

04Chapter 4: IVF, Clusters You Can Skip#

4.1 The Idea#

An inverted file (IVF) index runs k-means over a sample of vectors to find nlist centroids, then files every vector under its nearest centroid. It's Week 7's inverted index with clusters instead of terms. A query finds its nprobe nearest centroids and scans only those lists.

• With 65,536 lists and nprobe = 64, a query scans about 0.1% of the vectors.
• A true neighbour that fell into a list you didn't probe is missed. Raising nprobe trades latency for recall.

4.2 Sizing the Lists#

Two published rules of thumb:

pgvector says to create the index "after the table has some data", because the centroids come from it. That's IVF's weakness: centroids are fixed at training time. When new tickets drift (a new product line, a festival sale), lists grow unevenly and recall at the same nprobe falls. Watch list sizes and retrain.

Its strength is cheap updates: adding a vector appends it to one list. Airbnb chose IVF over HNSW because "the high volume of real-time updates per second for Airbnb home listings... caused the memory footprint of the HNSW index to grow too large", and "parallel retrieval with HNSW alongside filters resulted in poor latency performance". IVF cluster assignments became "a standard search filter" in their existing search system, and Euclidean distance "produced much more balanced clusters" than dot product (Airbnb Engineering).

05Chapter 5: Product Quantisation, Compressing the Vectors Themselves#

5.1 The Problem It Solves#

HNSW and IVF reduce how many vectors a query touches. Neither shrinks the vectors. MegaMart's 3.2M × 4 KB is 13 GB, which fits in RAM. But if it kept every conversation for four years, ~100M vectors, the raw floats alone would be 410 GB. Quantisation stores each vector in fewer bytes.

5.2 How PQ Works#

Product quantisation (Jégou, Douze and Schmid, IEEE TPAMI 2011) "decomposes the space into a Cartesian product of low dimensional subspaces and [quantizes] each subspace separately":

1. Split each 1,024-dim vector into m sub-vectors (say m = 64 sub-vectors of 16 dims).
2. For each sub-space, learn 256 centroids with k-means. A sub-vector is replaced by the id of its nearest centroid: one byte.
3. The vector becomes m bytes: 64 bytes instead of 4,096, 64× smaller.

The paper, working on 128-dim SIFT descriptors, goes smaller still: "Using k* = 256 and m = 8 is often a reasonable choice", 64-bit codes, and it validates the approach "on a dataset of two billion vectors".

Distances are estimated without decompressing. With asymmetric distance computation (ADC), the query stays exact: build a table of distances from each query sub-vector to all 256 centroids of its sub-space (64 × 256 numbers), then a stored vector's distance is 64 table lookups and additions.

# search/pq.py: product quantisation encode and ADC (illustrative, no training code)
import numpy as np

def pq_encode(x: np.ndarray, codebooks: np.ndarray) -> np.ndarray:
    """x: (d,), codebooks: (m, 256, d/m). Returns m uint8 codes."""
    m, _, sub = codebooks.shape
    parts = x.reshape(m, sub)
    return np.array([np.argmin(((codebooks[j] - parts[j]) ** 2).sum(1)) for j in range(m)], np.uint8)

def adc_distances(q: np.ndarray, codes: np.ndarray, codebooks: np.ndarray) -> np.ndarray:
    """codes: (N, m). Exact query, compressed database: one table, then lookups."""
    m, _, sub = codebooks.shape
    table = ((codebooks - q.reshape(m, 1, sub)) ** 2).sum(-1)    # (m, 256)
    return table[np.arange(m), codes].sum(1)                     # (N,) approximate squared L2

5.3 IVF-PQ and Rescoring#

PQ is usually combined with IVF: the paper's IVFADC uses a coarse quantiser (the IVF centroids) and PQ-encodes each vector's residual from its centroid. FAISS lists IVFx,PQy at "ceil(M * nbits/8)+8" bytes per vector: the code plus an 8-byte id.

Compressed distances are approximate, so close candidates come back in a noisy order. The fix is rescoring: take the top 100–200 by PQ distance, fetch their full vectors from SSD, recompute exact distances, return the top k. FAISS's RFlat "re-orders search results with exact distance computations"; Elastic recovers quantisation's lost recall "by oversampling and rescoring more vectors".

%% title: An IVF-PQ query with rescoring
flowchart TD
  Q(["Query vector"]):::core
  C["Compare with 65,536 centroids<br/>pick nprobe = 64 lists"]:::service
  T["Build ADC table<br/>64 sub-spaces × 256 centroids"]:::service
  S["Scan codes in 64 lists<br/>~0.1% of vectors, 72 B each"]:::service
  TOP["Top 200 by approximate distance"]:::service
  F@{ icon: "sd:database", label: "Full float32 vectors<br/>on SSD" }
  R(["Exact rescoring<br/>return top 10"]):::ok
  Q --> C --> T --> S --> TOP
  TOP -->|"fetch 200 × 4 KB"| F
  F --> R
  class F store

5.4 Simpler Quantisation#

PQ isn't the only option. Elastic's documentation, as of October 2026:

Elastic now quantises by default: "float and bfloat16 vectors are quantized automatically, using BBQ where available and int8_hnsw for low-dimensional vectors". pgvector offers halfvec (2 bytes per dimension) and binary quantisation via expression indexes.

06Chapter 6: Choosing an Index#

pgvector's README sums up the main pair: HNSW "has better query performance than IVFFlat (in terms of speed-recall tradeoff), but has slower build times and uses more memory". A newer family keeps the graph on SSD: Microsoft's DiskANN (NeurIPS 2019) can "index, store, and search a billion point database on a single workstation with just 64GB RAM and an inexpensive solid-state drive", serving "> 5000 queries a second with < 3ms mean latency and 95%+ 1-recall@1" on SIFT1B.

07Chapter 7: Recall vs Latency#

7.1 recall@k#

An ANN index can't tell you what it missed. You find out by comparing it with exact search:

recall@k = |ANN top-k ∩ exact top-k| ÷ k

Recall@10 of 0.95 means that, on average, 9.5 of the true 10 nearest neighbours came back. It measures the index, not the answer: if the embedding model puts the wrong article nearest, exact search returns it too. Answer quality is Day 4's evaluation problem; index recall is today's.

7.2 Measure on Your Data#

ann-benchmarks popularised the method: plot recall against queries per second per library and setting, on datasets such as SIFT (128 dims, 1M vectors) and GloVe (25–200 dims). Its latest results are "as of April 2025", and the project is "no longer actively maintained". Use it to learn the shape of the trade-off. Your vectors (1,024 dims, Hinglish, your filters) behave differently, so build the curve yourself:

# eval/recall.py: recall@k vs ef_search, against exact ground truth (illustrative)
import random, time

def recall_at_k(ann_ids, exact_ids, k=10):
    return len(set(ann_ids[:k]) & set(exact_ids[:k])) / k

def sweep(index, exact, queries, efs=(20, 40, 80, 160, 320), k=10, sample=500):
    qs = random.sample(queries, sample)                 # real logged queries, not synthetic
    truth = {q.id: exact.search(q.vec, k) for q in qs}  # exact scan: slow, run offline
    for ef in efs:
        index.set_ef(ef)
        t0 = time.perf_counter()
        hits = [recall_at_k(index.search(q.vec, k, filters=q.filters), truth[q.id], k) for q in qs]
        ms = (time.perf_counter() - t0) * 1000 / len(qs)
        print(f"ef={ef:>4}  recall@{k}={sum(hits)/len(hits):.3f}  {ms:.1f} ms/query")

Use real queries with their filters (filtered recall is often much worse, Chapter 8), slice by language and selectivity (an average of 0.96 can hide Hindi at 0.80), and re-run after every model, parameter or data change.

08Chapter 8: Metadata Filtering#

Real queries come with conditions: only published articles, only the customer's language, only tickets from the last two years, only articles for the customer's region. Filtering is easy in a database and surprisingly hard in an ANN index.

8.1 Three Strategies#

Vendors name these differently. Weaviate calls its approach pre-filtering: "an inverted index... is used to create an allow-list of eligible candidates" for the graph search. Since v1.34 its default is ACORN, "especially useful when the filter has low correlation with the query vector", and it switches to a flat (brute-force) search "when a filter becomes too restrictive", below a configurable flatSearchCutoff (40,000 objects by default) (Weaviate docs). Ask any store: where does the filter run, what happens when it's selective, and can it return fewer than k?

8.2 Choosing by Selectivity#

%% title: Choosing a filter strategy for one query
flowchart TD
  S{"How many vectors<br/>pass the filter?"}:::core
  S -->|"a few thousand<br/>(one customer's tickets)"| EX["Pre-filter + exact scan<br/>B-tree on the column"]:::ok
  S -->|"a few known values<br/>(language, region)"| PI["Partial index or partition<br/>per value"]:::ok
  S -->|"anything from 1% to 100%<br/>(date ranges, tags)"| FT["In-filter traversal<br/>or iterative scan"]:::ok
  FT --> CK{"Recall still low<br/>at this selectivity?"}:::core
  CK -->|"yes"| MORE["Raise ef or candidates,<br/>or fall back to exact"]:::service
  CK -->|"no"| DONE(["Ship it, keep measuring"]):::ok

pgvector's README gives the same ladder: an index on the filter column for conditions "that match a low percentage of rows", partial indexes when "filtering by only a few distinct values", partitioning when "filtering by many different values", and iterative scans for the rest, bounded by hnsw.max_scan_tuples (20,000 by default).

Instacart shows what filtering inside the search is worth: with pgvector, "real-time inventory availability information is used as a pre-filter to reduce the search space", and "we saw a 6% drop in the number of searches with zero results due to better recall" (Instacart Engineering, 2025; more in Chapter 14).

09Chapter 9: Hybrid Search#

9.1 Why Both#

Rohit's "RTN-4471" is a token: BM25 finds it, an embedding blurs it. Kavya's "paisa wapas" is a meaning: an embedding finds it, BM25 needs a synonym list. Hybrid search runs both retrievers and fuses their rankings; Pinecone's docs: "combine a keyword signal (BM25 or sparse) with a dense signal at query time, often with reranking".

9.2 Don't Add the Scores#

The tempting fusion, 0.5 × bm25 + 0.5 × cosine, breaks because the scales differ: BM25 is unbounded and depends on the query's terms (Week 7, Day 3), while cosine sits in a narrow band. One retriever dominates, differently per query.

Reciprocal rank fusion (RRF) ignores scores and uses only ranks (Cormack, Clarke and Büttcher, SIGIR 2009):

RRFscore(d) = Σ over rankings r of 1 ÷ (k + r(d))

The paper fixed k = 60 "during a pilot investigation", found it "near-optimal, but that the choice was not critical", and reported that RRF "consistently yields better results than any individual system". Elasticsearch's rrf retriever uses the same formula with rank_constant defaulting to 60 (Elastic docs).

# search/fuse.py: reciprocal rank fusion (illustrative)
from collections import defaultdict

def rrf(rankings: list[list[str]], k: int = 60, weights: list[float] | None = None, top: int = 150):
    """rankings: one list of doc ids per retriever, best first."""
    weights = weights or [1.0] * len(rankings)
    scores = defaultdict(float)
    for w, ranking in zip(weights, rankings):
        for rank, doc_id in enumerate(ranking, start=1):
            scores[doc_id] += w / (k + rank)
    return sorted(scores, key=scores.get, reverse=True)[:top]

# lexical = bm25.search(q, 100); semantic = ann.search(embed(q), 100, filters=f)
# candidates = rrf([lexical, semantic])      # Day 3 reranks these

Tune weights later, and narrowly: if evals show exact tokens matter for queries containing an order code, weight the lexical list up for those queries only.

9.3 The Query Path#

%% title: One hybrid query: Rohit's return code
sequenceDiagram
  autonumber
  participant A as MegaMart Assist
  participant R as Retrieval service
  participant E as Embedding API
  participant K as Keyword index
  participant V as Vector index
  A->>R: RTN-4471 still not picked up, lang hi-en, region IN
  par lexical
    R->>K: BM25 top 100, filter published and region
    K-->>R: ticket T-55120 ranks 1st on RTN-4471
  and semantic
    R->>E: embed query, input_type query
    E-->>R: 1,024 floats
    R->>V: kNN top 100, same filter in the search
    V-->>R: pickup articles and similar tickets
  end
  R->>R: RRF with k = 60, keep top 150
  R-->>A: 150 candidates for Day 3 to rerank

In PostgreSQL both retrievers can run in one database, which is what Instacart moved to:

-- MegaMart help articles: hybrid retrieval in one query (illustrative)
SET hnsw.ef_search = 100;                           -- HNSW returns at most ef_search rows (default 40)
SET hnsw.iterative_scan = relaxed_order;            -- keep filtered kNN from coming back short
WITH nearest AS MATERIALIZED (                      -- filters stay inside the CTE
  SELECT id, embedding <=> $1 AS dist
  FROM articles
  WHERE status = 'published' AND region = $3
  ORDER BY dist LIMIT 100
), semantic AS (
  SELECT id, row_number() OVER (ORDER BY dist + 0) AS r FROM nearest
), lexical AS (
  SELECT id, row_number() OVER (ORDER BY ts_rank_cd(tsv, q) DESC) AS r
  FROM articles, websearch_to_tsquery('simple', $2) q
  WHERE tsv @@ q AND status = 'published' AND region = $3
  ORDER BY ts_rank_cd(tsv, q) DESC LIMIT 100
)
SELECT id, COALESCE(1.0 / (60 + s.r), 0) + COALESCE(1.0 / (60 + l.r), 0) AS rrf
FROM semantic s FULL OUTER JOIN lexical l USING (id)
ORDER BY rrf DESC LIMIT 150;

<=> is pgvector's cosine distance operator. A relaxed_order scan can return rows slightly out of order, so, as pgvector's README advises, the nearest rows go into a materialized CTE and are re-sorted by exact distance before fusion (the + 0 "is needed for Postgres 17+", so the planner doesn't assume they're already sorted).

10Chapter 10: Choosing a Store#

As of October 2026: pgvector (v0.8.7) stores "4 * dimensions + 8 bytes" per vector and indexes vector "up to 2,000 dimensions", so 3,072-dim embeddings need halfvec or fewer dimensions. Elasticsearch's dense_vector takes up to 4,096 dims. Pinecone allows "40 KB of metadata per record" and suggests "one namespace per customer".

The default for MegaMart: start where the data already is. Documents, tickets and their metadata are already in Postgres, and Chapter 11 shows the whole index is ~13.5 GB, so pgvector holds both corpora today. A search engine or a dedicated store earns its place when the index outgrows a node or the team needs features Postgres lacks.

11Chapter 11: Sizing and Sharding#

Week 0 taught us to estimate memory before buying it. For vectors the question is simple: what must be in RAM for a query to be fast?

Build time belongs in the same estimate, but measure it: build an index of 1M of your own vectors, time it, and scale up. HNSW inserts slow down as the graph grows and once it outgrows build memory; IVF-PQ trains once on a sample, then encodes in one pass. If a rebuild takes a day, every model change (Chapter 13) costs a day.

11.1 Sharding a Vector Index#

Past one node's RAM, split the index (Week 1, Day 1 · Partitioning), in one of two ways:

• Shard by id (hash). Each shard indexes a random slice. Every query goes to every shard and a coordinator merges their local results. Elasticsearch works this way: num_candidates is "the number of nearest neighbor candidates to consider per shard", and Elasticsearch "collects k... results from each shard, then merges them to find the global top k results" (Elastic docs). Latency is set by the slowest shard.
• Shard by attribute (tenant, region, language). A query carrying it hits one shard, but shards are uneven (Week 1, Day 4 · Hot Keys and Skew) and other queries still fan out.

The HNSW paper flags the cost: partitioning the data across nodes works, but "the total parallel throughput of the system does not scale well with the number of computer nodes". So shard for memory, and add replicas for throughput and availability (Week 1, Day 2 · Replication).

%% title: Scatter-gather over four hash-sharded shards (the 100M growth case)
flowchart TD
  RS["Retrieval service<br/>k = 10, candidates = 50 per shard"]:::core
  S1@{ icon: "sd:index", label: "Shard 1<br/>25M vectors + replica" }
  S2@{ icon: "sd:index", label: "Shard 2<br/>25M vectors + replica" }
  S3@{ icon: "sd:index", label: "Shard 3<br/>25M vectors + replica" }
  S4@{ icon: "sd:index", label: "Shard 4<br/>25M vectors + replica" }
  M["Merge 200 candidates<br/>by distance, keep top 10"]:::service
  RS --> S1 & S2 & S3 & S4
  S1 & S2 & S3 & S4 --> M
  M --> OUT(["Top 10, slowest shard sets latency"]):::ok
  class S1,S2,S3,S4 store

11.2 Caching#

Results for an identical (query text, filters, model version, index version) can be cached (Week 4), and so can query embeddings, saving an API call per repeat. Caching answers by meaning, a semantic cache, is Day 5's topic.

12Chapter 12: When the Index Lies Quietly#

Vector search fails without errors: every query returns k results, relevant or not.

13Chapter 13: Changing the Embedding Model#

Sooner or later a better model arrives: better at Hinglish, cheaper, or shorter vectors.

Treat a model change like a schema migration, with the alias pattern of Week 7's zero-downtime reindex. From the index's side: version every vector (a model_id column; pgvector can keep an expression index per model, WHERE (model_id = 123)); build the new index beside the old one (twice the memory for the overlap, ~27 GB today, plus the build time from Chapter 11); and flip the alias only after recall and relevance pass, keeping v1 for rollback. Voyage says "all embeddings created with the 4 series are compatible with each other", which avoids a rebuild only inside that family. Day 3 runs the whole migration through its ingestion pipeline.

14Chapter 14: How Real Companies Do It#

Spotify: a library, chosen for speed and memory. Spotify built Voyager, "based on hnswlib" and "intended to succeed Annoy" (its own earlier library): "more than 10 times the speed of Annoy (at the same recall)" and "up to 4 times less memory usage than Annoy (thanks to E4M3 8-bit floating point)", serving production traffic "since 2022" (Spotify Engineering, 2023). A library fits when the team owns the serving system around it.

Instacart: retrieval moved into the database. Instacart moved search from Elasticsearch to PostgreSQL ("a 10x reduction in write workload"). Its semantic retrieval had run on FAISS, where "an excess number of documents had to be fetched first (overfetching) before being filtered". With pgvector, inventory became a pre-filter and zero-result searches fell 6%; "while pgvector was marginally slower than FAISS for larger retailers, it had better recall performance" (Instacart Engineering, 2025). Filtering, not raw ANN speed, decided it.

Airbnb: IVF because of updates and filters. Chapter 4's case: real-time listing updates bloated HNSW's memory and filters hurt its latency, so IVF clusters became one more filter in an existing search stack (Airbnb Engineering).

15Chapter 15: Common Mistakes#

1. Vector search alone. Order codes, SKUs and error strings need exact tokens. Run BM25 alongside and fuse with RRF.
2. Filtering after the index. A selective filter on a post-filtered index returns short, silently. Know where your store filters, and alert on result counts.
3. Never measuring recall. Defaults are a starting point. Build the recall-vs-latency curve on real, filtered queries, sliced by language.
4. Sizing for RAM last, or quantising first. Full-precision HNSW at 100M × 1,024 dims is ~420 GB per replica; at MegaMart's 3.2M it's 13.5 GB. Do the arithmetic before choosing the store, and quantise (with rescoring) only when the index outgrows a node.
5. Mixing embedding models. Vectors from different models or versions can't be compared. Version every vector and migrate with dual indexes and an alias.

16Chapter 16: Interview Tips and Phrases#

16.1 When to Bring It Up#

Any "search by meaning" prompt: support assistants, semantic product search, similar items, RAG. Raise hybrid search when the data has IDs, codes or names, and filtering when there are tenants, permissions or languages.

16.3 Questions to Ask the Interviewer#

• How many documents, how fast do they grow, and how often are they updated or deleted?
• Which filters are mandatory (tenant, permissions, language), and how selective are they?
• Do users search with exact identifiers as well as natural language?
• What recall or relevance bar must we meet, and how will we measure it?

16.4 Common Follow-Up Questions#

17Chapter 17: Practice Problems#

Summary#

Further Reading#

Papers#

• Paper

  Malkov and Yashunin — Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv 1603.09320, v4 2018): https://arxiv.org/abs/1603.09320

• Read

  Jégou, Douze and Schmid — Product Quantization for Nearest Neighbor Search (IEEE TPAMI 2011): https://inria.hal.science/inria-00514462

• Paper

  Cormack, Clarke and Büttcher — Reciprocal Rank Fusion outperforms Condorcet and individual Rank Learning Methods (SIGIR 2009): https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf

• Paper

  Subramanya et al. — DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node (NeurIPS 2019): https://papers.nips.cc/paper/2019/hash/09853c7fb1d3f8ee67a61b6bf4a7f8e6-Abstract.html

Documentation#

• Wiki

  FAISS wiki — Guidelines to choose an index · Faiss indexes · The index factory: https://github.com/facebookresearch/faiss/wiki

• Read

  pgvector README (v0.8.7): https://github.com/pgvector/pgvector

• Docs

  Elastic — Tune approximate kNN search · Filtered kNN search · dense_vector · Reciprocal rank fusion: https://www.elastic.co/docs/deploy-manage/production-guidance/optimize-performance/approximate-knn-search · https://www.elastic.co/docs/solutions/search/vector/knn/filtered-knn-search · https://www.elastic.co/docs/reference/elasticsearch/mapping-reference/dense-vector · https://www.elastic.co/docs/reference/elasticsearch/rest-apis/reciprocal-rank-fusion

• Docs

  Weaviate — Filtering: https://docs.weaviate.io/weaviate/concepts/filtering

• Docs

  Pinecone — Indexing overview: https://docs.pinecone.io/guides/index-data/indexing-overview

• Docs

  OpenAI — Vector embeddings: https://developers.openai.com/api/docs/guides/embeddings

• Docs

  Voyage — Text embeddings · Pricing: https://docs.voyageai.com/docs/embeddings · https://docs.voyageai.com/docs/pricing

• Docs

  Cohere — Embed API reference: https://docs.cohere.com/reference/embed

• Read

  ann-benchmarks: https://github.com/erikbern/ann-benchmarks

Engineering Posts#

• Blog

  Spotify — Introducing Voyager (25 October 2023): https://engineering.atspotify.com/2023/10/introducing-voyager-spotifys-new-nearest-neighbor-search-library

• Blog

  Instacart — How Instacart Built a Modern Search Infrastructure on Postgres (29 May 2025): https://company.instacart.com/tech-innovation/how-instacart-built-a-modern-search-infrastructure-on-postgres

• Read

  Airbnb — Embedding-Based Retrieval for Airbnb Search: https://airbnb.tech/ai-ml/embedding-based-retrieval-for-airbnb-search/