Vector Databases: Embeddings at Scale

When Brute-Force Search Collapses

Flipkart's catalog during a Big Billion Days sale holds on the order of 150 million listings. A shopper types "party wear kurti under 1000, cotton, not too glittery." No SKU field stores "not too glittery" — this is a meaning-match problem, not a keyword filter. The standard fix, since 2019 or so, is to run every listing description through a transformer encoder once, offline, producing a fixed-length vector — an embedding — and store it. At query time the shopper's text is embedded the same way, and the system returns the listings whose vectors sit closest to the query vector in that embedding space. This is nearest-neighbor search, and it is the entire reason vector databases exist.

Start with the naive version: compare the query vector against every stored vector, exactly, every time. Say each embedding has dimension d = 768 (the output size of a common sentence encoder such as all-mpnet-base-v2). Comparing two vectors by cosine similarity costs about 2d floating-point operations — d multiplications for the dot product, d additions to sum them, ignoring the norm terms which can be precomputed once at insert time. Across N = 150,000,000 listings, one query costs 2Nd = 2 × 1.5×10⁸ × 768 = 2.304×10¹¹ FLOPs — 230.4 GFLOP. A modern multi-core server sustaining 200 GFLOPS on this kind of dense linear algebra takes 230.4 / 200 = 1.152 seconds per query on compute alone.

But compute is not actually the bottleneck here, and this is the sharper, more useful diagnosis. Each comparison reads 4d bytes (one float32 per dimension) and performs only 2d FLOPs — an arithmetic intensity of 2d / 4d = 0.5 FLOP per byte, far below the several-FLOP-per-byte range where modern CPUs and GPUs become compute-bound. This workload is memory-bandwidth-bound. The real cost is reading all N × d × 4 = 150×10⁶ × 768 × 4 = 4.608×10¹¹ bytes = 460.8 GB from memory, once per query. At a realistic sustained server memory bandwidth of 200 GB/s, that's 460.8 / 200 = 2.304 seconds — worse than the compute estimate, and the one that actually governs latency. A shopper will not wait two seconds for a search box to respond, and Flipkart is not serving one query at a time during a sale.

Everything in this chapter is the engineering response to that one number: 460.8 GB and 2.3 seconds, per query, for a workload that needs to run thousands of times a second at under 100 milliseconds. Two independent levers exist — shrink the bytes read (quantization) and shrink the number of vectors actually examined (approximate indexing). Production vector databases stack both.

What an Embedding Actually Encodes

An embedding is the output of a trained encoder — commonly a transformer, as covered in this year's LLM-architecture unit — mapped to a fixed-dimension real vector such that semantic proximity in meaning corresponds to geometric proximity in the vector space. Sentence-embedding models like Sentence-BERT (Reimers & Gurevych, EMNLP 2019) are trained with a contrastive or Siamese objective specifically so that "cotton kurti, pastel" and "pastel-colored cotton kurti" land close together while "cotton kurti" and "cast iron skillet" land far apart, even though none of those pairs share exact substrings. This is the property that keyword indexing (inverted indexes, BM25) fundamentally cannot give you — BM25 matches tokens, embeddings match meaning.

Production embedding dimensions vary by model: open-source sentence-transformer models commonly emit 384 or 768 dimensions; OpenAI's text-embedding-3-small and text-embedding-3-large emit 1536 and 3072 by default (both also expose a `dimensions` parameter that truncates the vector, a technique called Matryoshka Representation Learning — Kusupati et al., NeurIPS 2022 — where the training objective front-loads the most important information into the earlier dimensions so truncation degrades gracefully rather than randomly). Every one of these vectors is dense — almost no zero entries — which is precisely what makes classical exact-match indexes (hash indexes, B-trees) useless here: there is no discrete key to index on, only continuous geometric position.

Distance Metrics You Can Prove, Not Just Assert

Three distance functions dominate vector search: Euclidean (L2) distance, dot product, and cosine similarity. They are not interchangeable in general, but there is one clean, provable relationship worth deriving rather than memorizing. For two vectors q and v with equal norm |q| = |v| = 1 (unit-normalized):

||q - v||² = (q - v)·(q - v)
           = q·q - 2(q·v) + v·v
           = |q|² + |v|² - 2(q·v)
           = 1 + 1 - 2(q·v)
           = 2 - 2·cos(q, v)          [since cos(q,v) = (q·v)/(|q||v|) = q·v when both norms are 1]

So for normalized vectors, squared L2 distance is a strictly decreasing linear function of cosine similarity. Minimizing L2 distance and maximizing cosine similarity produce the identical ranking. This is why production systems normalize embeddings once at insert time and then run plain dot-product or L2 search — it's algebraically cheaper (no norm computation per comparison) and mathematically equivalent to cosine, provided normalization actually happened.

That "provided" is where things break, and it motivates a fully worked example.

A Fully Worked Nearest-Neighbor Query

Take six toy 4-dimensional vectors — small enough to compute by hand, large enough to show a real ranking — representing document topics and a query about "matrix multiplication for backpropagation," q = (1, 0, 1, 0):

A = (2, 0, 1, 0)   "Linear Algebra: Matrix Multiplication"
B = (1, 1, 1, 0)   "Neural Network Backpropagation"
C = (0, 2, 0, 1)   "Cricket Analytics: Net Run Rate"
D = (0, 0, 0, 2)   "Thermodynamics: Entropy"
E = (1, 0, 0, 1)   "Probability: Bayes Theorem"
H = (1, 2, 1, 1)   "Cricket Analytics, extended chapter"

|q| = √(1²+0²+1²+0²) = √2. Cosine similarity = (q·v) / (|q||v|):

A: q·A = 1·2+0·0+1·1+0·0 = 3.  |A| = √5.  cos = 3/√10 = 0.9487
B: q·B = 1·1+0·1+1·1+0·0 = 2.  |B| = √3.  cos = 2/√6  = 0.8165
E: q·E = 1·1+0·0+1·0+0·1 = 1.  |E| = √2.  cos = 1/2   = 0.5000
C: q·C = 0.                    cos = 0
D: q·D = 0.                    cos = 0
H: q·H = 1·1+0·2+1·1+0·1 = 2.  |H| = √7.  cos = 2/√14 = 0.5345

Ranked by cosine: A (0.9487) > B (0.8165) > H (0.5345) > E (0.5000) > C = D (0). That is exactly the ranking a good retrieval system should produce — the linear-algebra chapter first, the closely related backprop chapter second, the orthogonal cricket and thermodynamics chapters last.

Now look at raw dot product instead of cosine: B and H both score 2, tying for second place, even though H (norm √7 ≈ 2.65) is far less concentrated in the query's direction than B (norm √3 ≈ 1.73) — cosine ranks B clearly above H (0.8165 vs 0.5345) while unnormalized dot product cannot tell them apart. A longer or more repetitive document, which tends to accumulate a larger embedding norm, would out-rank a shorter, more precisely on-topic one under raw dot product. This is exactly why the equivalence proved above requires normalization — drop that step and dot-product ranking silently diverges from cosine ranking.

Verify all of it numerically:

import numpy as np

q = np.array([1, 0, 1, 0])
docs = {
    "A_linear_algebra": np.array([2, 0, 1, 0]),
    "B_backprop":       np.array([1, 1, 1, 0]),
    "C_cricket":        np.array([0, 2, 0, 1]),
    "D_thermo":         np.array([0, 0, 0, 2]),
    "E_bayes":          np.array([1, 0, 0, 1]),
    "H_cricket_long":   np.array([1, 2, 1, 1]),
}

def cosine(u, v):
    return np.dot(u, v) / (np.linalg.norm(u) * np.linalg.norm(v))

for name, v in docs.items():
    print(name, "dot=", np.dot(q, v), "cos=", round(cosine(q, v), 4))

# Output:
# A_linear_algebra dot= 3 cos= 0.9487
# B_backprop       dot= 2 cos= 0.8165
# C_cricket        dot= 0 cos= 0.0
# D_thermo         dot= 0 cos= 0.0
# E_bayes          dot= 1 cos= 0.5
# H_cricket_long   dot= 2 cos= 0.5345

The Curse of Dimensionality Kills Exact Trees

The natural next question: why not just use a KD-tree or a B-tree over the 768 coordinates, the way G11's DBMS unit indexed relational columns? Trees prune by recursively halving a search space, and that works beautifully up to perhaps 10–20 dimensions. Past that, a well-documented phenomenon (Weber, Schek & Blott, VLDB 1998, among others) sets in: in high-dimensional space, the distance from a query point to its nearest neighbor and to its farthest neighbor converge — the ratio approaches 1. When almost every point is "about as far" as every other point, a tree's pruning rule ("this whole subtree is farther than the current best candidate, skip it") almost never fires, and the tree degenerates into an exhaustive scan with extra bookkeeping overhead on top. At d = 768, exact tree indexes are strictly worse than the brute-force scan they were meant to replace. This is the real reason the field abandoned exact indexing for embeddings and moved to approximate methods.

Approximate Nearest Neighbor: IVF and Product Quantization

Inverted File Index (IVF) attacks the "how many vectors do I compare against" side. Run k-means once over the dataset to produce nlist cluster centroids (FAISS's documentation suggests nlist on the order of 4√N to 16√N as a starting heuristic — for N = 150 million, √N ≈ 12,247, so that's roughly 50,000 to 200,000 cells). Every stored vector is assigned to its nearest centroid. At query time, instead of scanning all N vectors, find the nprobe closest centroids to the query and scan only the vectors inside those cells. If nlist ≈ 50,000 and nprobe = 8, a query touches roughly (8/50,000) × N vectors instead of N — several orders of magnitude fewer comparisons. The cost: if the true nearest neighbor happens to sit in a cluster whose centroid isn't among the nprobe closest (it can, near cluster boundaries), it's missed entirely. IVF is approximate by construction — recall trades directly against nprobe.

Product Quantization (PQ), from Jégou, Douze & Schmid (IEEE TPAMI, 2011), attacks the "how many bytes per vector" side, independent of IVF. Split each d-dimensional vector into m equal sub-vectors, and separately k-means-cluster each sub-vector's space into k* = 256 centroids (256 fits in 8 bits, one byte). Store each vector not as its d raw floats but as m byte-indices into those per-segment codebooks. For d = 768 with sub-vector width 8 (a common FAISS default), m = 768/8 = 96 bytes replace 768 × 4 = 3072 bytes — a 3072/96 = 32× compression ratio, with distances at query time approximated via precomputed lookup tables against the codebooks rather than reconstructing the original floats.

N = 150_000_000
d = 768

flops_per_query = 2 * N * d
print(flops_per_query / 1e9, "GFLOP")            # 230.4 GFLOP

compute_latency = flops_per_query / 200e9         # 200 GFLOPS assumed sustained
print(compute_latency, "s")                        # 1.152 s

bytes_per_query = N * d * 4
print(bytes_per_query / 1e9, "GB")                 # 460.8 GB

memory_latency = bytes_per_query / 200e9            # 200 GB/s assumed bandwidth
print(memory_latency, "s")                          # 2.304 s  <- dominates; memory-bound

m = 96
compressed_bytes = N * m
print(compressed_bytes / 1e9, "GB")                 # 14.4 GB
print((d * 4) / m, "x compression")                 # 32.0x

compressed_latency = compressed_bytes / 200e9
print(compressed_latency, "s")                       # 0.072 s = 72 ms

Quantization alone — before adding any cluster-pruning — takes the memory-bound scan from 2.304 s to 72 ms, a 32× improvement that exactly tracks the compression ratio, because the workload was memory-bound and 32× fewer bytes means 32× less time reading them. Stack IVF's cluster pruning on top (examining only a small fraction of cells) and a full production index (IVF-PQ, as shipped in FAISS) reaches low-millisecond query latency over the full 150-million-vector catalog. This is also why the 460.8 GB uncompressed footprint matters beyond speed: it simply will not fit in the RAM of a single machine, whereas the 14.4 GB compressed footprint comfortably does.

HNSW: Graphs That Skip Across Scale

The dominant index inside most current production vector databases — Pinecone, Weaviate, Qdrant, Milvus, and pgvector's HNSW mode — is not IVF-PQ but Hierarchical Navigable Small World graphs (HNSW), introduced by Malkov and Yashunin in a 2016 preprint and formally published in IEEE TPAMI in 2020. HNSW builds a multi-layer proximity graph: every stored vector is a node in the base layer (Layer 0), where it holds edges to a bounded number of its approximate nearest neighbors (parameter M, commonly 16–64). A random subset of nodes is also promoted to Layer 1, a smaller subset of those to Layer 2, and so on — each layer roughly geometrically sparser than the one below it, the same way a skip list's upper rungs are sparser than its base linked list.

A query starts at a single fixed entry point in the topmost, sparsest layer and greedily walks to whichever neighbor is closest to the query vector, repeating until no neighbor improves on the current node — a local optimum for that layer. The search then drops one layer at that same node and repeats the greedy walk there, now with more neighbors to consider since the layer is denser. This continues down to Layer 0, where the search expands a candidate list of size ef_search (rather than stopping at the very first local optimum) to guard against getting stuck in a spurious optimum, and returns the best candidates found. Because the upper layers let a query cross large distances in the graph in very few hops — the same principle that makes six-degrees-of-separation social graphs "small world" — Malkov and Yashunin argue, and benchmarks broadly support, that search cost grows roughly logarithmically with N rather than linearly. For N = 150,000,000, log₂N ≈ 27.16 — meaning the graph search touches on the order of a few dozen hops' worth of candidates rather than 150 million comparisons, which is the entire point.

Common Misconception: "Vector Search Finds the True Nearest Neighbors"

The name "nearest neighbor search" misleads students into assuming a vector database always returns the mathematically closest vectors, the way a SQL `ORDER BY distance LIMIT 10` would over an exact scan. It does not, by design. Every index covered here — IVF, PQ, HNSW — is approximate: IVF can miss a neighbor whose true cluster wasn't among the probed cells; PQ replaces exact distances with lookup-table approximations from compressed codebooks; HNSW's greedy walk can settle into a node that looks locally optimal but isn't the global nearest neighbor, especially with a small ef_search. The standard way production teams quantify this gap is recall@k — the fraction of the true top-k nearest neighbors (found by a separate, offline exact brute-force pass) that the approximate index actually returns.

The two parameters students conflate are M and ef_search. M (roughly 16–64) is fixed at index-build time — it controls how many edges each node keeps, trading index memory and build time for how well-connected, and therefore how navigable, the graph is. ef_search is set per query — it controls how large a candidate list the base-layer expansion considers before returning results. Raising ef_search increases recall (closer to exhaustive) at the direct cost of latency, and it is the knob an engineer actually tunes at serve time, not M, which would require rebuilding the whole index. A team serving Flipkart's search box under 100 ms will deliberately accept a small, known recall loss (returning the 9th- or 10th-best match instead of guaranteed-exact) in exchange for a large latency win over anything close to exhaustive search — that tradeoff, not a shortcut around correctness, is the actual engineering decision a vector database exists to make.

The Production Stack

None of this runs in isolation from the rest of the pipeline students built in G11's backend and DBMS units. A typical retrieval-augmented generation (RAG) system — the pattern behind most production LLM applications — chunks source documents into passages (too large a chunk dilutes the embedding's specificity; too small loses context the language model needs), embeds each chunk with a model like the ones above, and stores the vectors alongside the original text and metadata for filtering (price range, category, date). FAISS (Johnson, Douze & Jégou, IEEE Transactions on Big Data, 2019), originally built at Meta, is the library most of these systems build their ANN core on — it implements IVF, PQ, and HNSW directly and adds GPU-accelerated variants for billion-scale corpora. On top of that core sit full database systems: Milvus and Weaviate as dedicated vector databases with sharding and replication; Qdrant, similar, written in Rust for latency-sensitive deployments; Pinecone as a fully managed service; and pgvector, which adds HNSW and IVF-Flat index types directly inside PostgreSQL, letting a team keep vectors in the same transactional database as the rest of their relational data instead of running a separate system. Most serious production search stacks also run a keyword index (BM25) alongside the vector index and merge the two result sets — hybrid search — because embeddings, trained to capture semantic similarity, are often weaker than exact keyword match at precise entity names, part numbers, or rare terms that never appeared often enough in training data to earn a distinctive vector direction.

Active Recall

Attempt each question before reading its answer.

Q1. Why does a KD-tree, which works well indexing a database's numeric columns at low dimension, fail to speed up nearest-neighbor search once embeddings reach 768 dimensions?

Q2. Using the six-vector worked example, compute the cosine similarity between q = (1, 0, 1, 0) and a new vector I = (3, 0, 3, 0) by hand.

Q3. A startup has 32 GB of RAM budgeted for its vector index and must store 20 million vectors at d = 1536. Will uncompressed float32 storage fit? If not, will PQ with 8-bit codes at sub-vector width 8 fit, and with how much headroom?

Q4. Which HNSW parameter — M or ef_search — should an engineer raise to improve recall for a single slow, high-stakes query without rebuilding the index, and why?

Q5. AICI's catalog example scales from N = 150,000,000 to 600,000,000 vectors (4×) at the same time the embedding model is upgraded from d = 768 to d = 1536 (2×). Trace the full ripple: (a) raw brute-force FLOPs per query, (b) uncompressed memory footprint, (c) PQ-compressed memory footprint (keeping sub-vector width fixed at 8, so m scales with d), and (d) the approximate HNSW hop-count order, log₂N.

Q6. True or false: if two embeddings are unit-normalized, ranking by ascending L2 distance from a query gives the same order as ranking by descending cosine similarity. Justify from the identity derived earlier in this chapter.

A1. Trees prune subtrees only when they can prove every point inside is farther than the current best candidate. In high dimensions, the ratio between nearest- and farthest-neighbor distance converges toward 1 (Weber, Schek & Blott, VLDB 1998) — nearly every point is "about equally far," so that pruning test almost never succeeds, and the tree degrades to an exhaustive scan with extra overhead on top, strictly worse than brute force.

A2. I = 3q exactly (each coordinate scaled by 3), so I points in the identical direction as q. Cosine similarity depends only on direction, not magnitude: cos(q, I) = (q·I)/(|q||I|) = (3+0+3+0)/(√2 · √18) = 6/(√2·3√2) = 6/6 = 1.0 — perfect similarity, confirming cosine ignores scale entirely.

A3. Uncompressed: 20×10⁶ × 1536 × 4 bytes = 1.2288×10¹¹ bytes = 122.88 GB — does not fit in 32 GB (needs about 3.8× the budget). With PQ, sub-vector width 8 gives m = 1536/8 = 192 bytes per vector: 20×10⁶ × 192 = 3.84×10⁹ bytes = 3.84 GB — fits comfortably, using only about 12% of the 32 GB budget, with roughly 28 GB to spare for graph edges, metadata, and OS cache.

A4. ef_search. M is baked into the graph at build time and changing it means re-indexing the whole dataset; ef_search is a per-query parameter that widens the candidate list examined during the base-layer expansion, directly trading latency for recall on that one query without touching the stored index.

A5. (a) FLOPs scale with N·d, so 4× × 2× = 8×: 230.4 GFLOP → 1,843.2 GFLOP (1.8432 TFLOP). (b) Uncompressed memory also scales with N·d: 8× → 460.8 GB → 3,686.4 GB (3.69 TB). (c) Compressed memory: m doubles from 96 to 192 (since d doubled while sub-vector width stayed fixed at 8), and total compressed bytes = N·m, so it scales by 4× (from N) × 2× (from m) = 8× as well: 14.4 GB → 115.2 GB. Note that PQ's 32× compression ratio itself stays constant — quantization does not change how storage scales with N and d, it only rescales the constant. (d) log₂(600,000,000) = log₂(4 × 150,000,000) = log₂4 + log₂(150,000,000) = 2 + 27.16 = 29.16 — a 4× data increase adds only about 2 extra hops. This is the entire argument for graph-based ANN over brute force: linear quantities (FLOPs, memory) scale proportionally with the 8× growth, while the graph's search depth barely moves.

A6. True. For unit vectors, ||q − v||² = |q|² + |v|² − 2(q·v) = 2 − 2·cos(q, v). Squared L2 distance is a decreasing linear function of cosine similarity, so the vector with the smallest L2 distance is always the vector with the largest cosine similarity — the two rankings are identical whenever both vectors are normalized to length 1.

Think About It

Think about this: How would you explain vector databases: embeddings at scale to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where vector databases: embeddings at scale is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting vector databases: embeddings at scale to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind vector databases: embeddings at scale, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.