Suppose an e-commerce platform operating at Flipkart's scale wants to let a shopper photograph a kurta and instantly see visually similar products across the catalog. The pipeline is familiar by now: pass the image through a vision encoder, get back a 768-dimensional embedding, and find the catalog embeddings closest to it in cosine or Euclidean distance. The embedding model is not the hard part. The hard part shows up the moment you ask: closest to it among how many?
Say the catalog holds 500 million SKUs, each represented by a 768-dimensional float32 vector. Raw storage alone costs 500,000,000 × 768 × 4 bytes = 1,536,000,000,000 bytes — 1.5 TB, just to hold the vectors, before any index structure sits on top of them. A brute-force query compares the incoming vector against all 500 million rows: 500,000,000 × 768 multiply-adds per query, repeated for every search request, every second, across the platform. Neither number is exotic engineering — they are what happens when you multiply an embedding dimension by a catalog size and refuse to think about it further. A vector database is, at its core, the set of engineering decisions that make both numbers small again without throwing away the semantics the embedding captured. This chapter works through one specific, production-grade way to do that: product quantization combined with an inverted file index (IVF-PQ), the scheme underlying FAISS's billion-scale indexes and, in close variants, Milvus and Vespa's compressed indexes.
Two independent levers: pruning and compression
Every approximate nearest-neighbor (ANN) system pulls on some combination of two independent levers. The first is pruning: avoid comparing the query against most of the database at all. Graph-based indexes like HNSW (Malkov & Yashunin, 2018, IEEE TPAMI) prune by walking a navigable small-world graph toward the query, touching only a small, well-chosen neighborhood of nodes. Partition-based indexes prune by clustering the database once, offline, and at query time visiting only the clusters nearest the query — this is the IVF half of IVF-PQ. The second lever is compression: shrink what a single vector costs to store and compare, so that even the vectors you do touch are cheap. This is where product quantization operates, and it is the part of this design this chapter goes deep on, because it is where the memory arithmetic above actually gets solved.
The two levers are independent and composable — IVF-PQ literally is IVF pruning stacked on top of PQ compression, which is precisely why it scales the way it does. It is worth being explicit that pruning alone does not fix the 1.5 TB problem: even if a query only touches 0.02% of the database, storing the full 1.5 TB still requires 1.5 TB of RAM (or a slow disk round-trip) if every vector is kept at full float32 precision. Compression is the lever that shrinks the resident footprint; pruning is the lever that shrinks the work done per query. You need both.
Product quantization: compressing without projecting
Product quantization (Jégou, Douze & Schmid, 2011, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1), 117–128) compresses a D-dimensional vector by splitting it into m contiguous subvectors of D/m dimensions each, and quantizing each subspace independently against its own small codebook of centroids, trained offline with k-means. Concretely: split the 768 dimensions into, say, 96 chunks of 8 dimensions each. Run k-means separately on each of the 96 chunks (across the training set) to learn 256 centroids per chunk. Now any database vector can be replaced by 96 small integers — one per chunk, each simply the index of the nearest centroid in that chunk's codebook. Since 256 = 28, each index fits in exactly one byte, so the whole vector collapses to 96 bytes regardless of how spread out the original 3,072 bytes (768 × 4) were.
Two things about this deserve emphasis because they are the mechanism, not incidental detail. First, quantization happens independently per subspace — the codebook for dimensions 1–8 has nothing to do with the codebook for dimensions 9–16. Second, at query time you never have to decompress a database vector to compare it against the query. You compute, once per query, the squared distance from each query subvector to each of the 256 centroids in the matching codebook — a small distance table — and then approximate the distance to any encoded database vector by summing the table entries its code indices point to. This is asymmetric distance computation (ADC): the query stays at full precision, only the database side is quantized, and distance computation becomes a handful of table lookups and additions instead of 768 multiply-subtract-square operations.
Worked example: encoding and asymmetric distance, traced by hand
Real PQ setups use 8–16 dimensional subspaces and 256 centroids, which is not hand-traceable. The mechanism is identical at any scale, so trace it on a toy case: D = 4, split into m = 2 subspaces of 2 dimensions each, with k* = 2 centroids per subspace (so each subspace code is a single bit).
Fix the two codebooks, each already trained (imagine k-means converged to these):
Subspace 1 codebook: C1[0] = (1, 1) C1[1] = (4, 4)
Subspace 2 codebook: C2[0] = (0, 2) C2[1] = (3, 5)Take a database vector x = (1.2, 0.8, 3.5, 4.5). Encode subspace 1, x[0:2] = (1.2, 0.8):
- Squared distance to C1[0]=(1,1): (1.2−1)² + (0.8−1)² = 0.04 + 0.04 = 0.08
- Squared distance to C1[1]=(4,4): (1.2−4)² + (0.8−4)² = 7.84 + 10.24 = 18.08
Nearest is C1[0], so subspace-1 code = 0. Encode subspace 2, x[2:4] = (3.5, 4.5):
- Squared distance to C2[0]=(0,2): (3.5)² + (2.5)² = 12.25 + 6.25 = 18.5
- Squared distance to C2[1]=(3,5): (0.5)² + (0.5)² = 0.25 + 0.25 = 0.5
Nearest is C2[1], so subspace-2 code = 1. The full PQ code for x is (0, 1) — two bits total, versus 4 × 32 = 128 bits (16 bytes) for the raw float32 vector. That is a 64× compression ratio, at this toy scale, from discretization alone.
Now bring in a query q = (2.0, 1.5, 3.0, 4.0) and compute the approximate distance to x without ever reconstructing x. Build the distance table: for each subspace, the squared distance from q's subvector to every centroid in that subspace's codebook.
import numpy as np
C1 = np.array([[1.0, 1.0], [4.0, 4.0]]) # subspace 1 codebook
C2 = np.array([[0.0, 2.0], [3.0, 5.0]]) # subspace 2 codebook
codebooks = [C1, C2]
x = np.array([1.2, 0.8, 3.5, 4.5]) # database vector
q = np.array([2.0, 1.5, 3.0, 4.0]) # query vector
def encode(vec, codebooks, sub_dim=2):
codes = []
for C in codebooks:
i = len(codes)
sub = vec[i * sub_dim:(i + 1) * sub_dim]
dists = np.sum((C - sub) ** 2, axis=1)
codes.append(int(np.argmin(dists)))
return codes
def distance_table(query, codebooks, sub_dim=2):
table = []
for C in codebooks:
i = len(table)
sub = query[i * sub_dim:(i + 1) * sub_dim]
table.append(np.sum((C - sub) ** 2, axis=1))
return table
def adc_distance(codes, table):
return sum(table[i][c] for i, c in enumerate(codes))
x_codes = encode(x, codebooks)
table = distance_table(q, codebooks)
approx_dist = adc_distance(x_codes, table)
exact_dist = np.sum((q - x) ** 2)Tracing this by hand confirms every value: encode(x, codebooks) reproduces the 0.08/18.08 and 18.5/0.5 comparisons above and returns x_codes = [0, 1]. For distance_table(q, codebooks), subspace 1 gives distances from q[0:2]=(2.0,1.5) to C1[0] and C1[1]: (1)²+(0.5)²=1.25 and (2)²+(2.5)²=10.25, so table[0] = [1.25, 10.25]. Subspace 2 gives distances from q[2:4]=(3.0,4.0) to C2[0] and C2[1]: (3)²+(2)²=13 and (0)²+(1)²=1, so table[1] = [13, 1]. The ADC distance reads off the entries the code selects: table[0][0] + table[1][1] = 1.25 + 1 = 2.25. The true squared Euclidean distance, computed directly on the uncompressed vectors, is (0.8)²+(0.7)²+(−0.5)²+(−0.5)² = 0.64+0.49+0.25+0.25 = 1.63. The approximation overshoots by 0.62 — that gap is the quantization error, the price paid for replacing (1.2, 0.8, 3.5, 4.5) with the coarser (1, 1, 3, 5) that its code points to. It is not free, but it was computed with two table lookups and one addition rather than four subtractions, four squarings, and three additions on the full vector — and at 96 subspaces instead of 2, that gap in work becomes the difference between a query that finishes and one that doesn't.
The same arithmetic at production scale
Return to the 768-dimensional, 500-million-vector catalog. With m = 96 subspaces of 8 dimensions each and k* = 256 centroids per subspace (the standard FAISS default, chosen precisely because 256 = 28 packs one code into one byte), each vector compresses from 3,072 bytes to 96 bytes — a 32× compression ratio. Across 500 million vectors, resident memory drops from 1.5 TB to 500,000,000 × 96 bytes = 48,000,000,000 bytes, or 48 GB: a size that fits in the RAM of a single well-specified server instead of demanding a sharded cluster just to hold the index.
IVF-PQ: pruning the compressed index
Compression alone still leaves every query scanning 500 million 96-byte codes. That is where IVF layers on top. During index construction, a coarse quantizer — itself just k-means, run once on a sample of the data — partitions the database into nlist clusters, each represented by a centroid. FAISS's own guidance places nlist between 4√N and 16√N; for N = 5×108, √N ≈ 22,361, putting nlist in the range of roughly 89,000 to 358,000. Take nlist = 100,000 as a concrete choice inside that band. Each database vector is assigned to its nearest coarse centroid, and — this is the refinement Jégou et al.'s 2011 paper also introduces, called IVFADC — instead of PQ-encoding the raw vector, the index encodes the residual: vector minus its assigned coarse centroid. Residuals are small, zero-centered, and share far less variance than the raw dataset, so the same k* = 256 centroids per subspace quantize them more precisely than they would the raw vectors, for the same 96-byte cost.
At query time, the query is first compared against only the 100,000 coarse centroids (cheap: a single flat comparison against 100,000 vectors, not 500 million) to find the nprobe nearest clusters. With nprobe = 16, the search then visits only 16 of the 100,000 inverted lists. Assuming roughly balanced clusters, each holds about 500,000,000 / 100,000 = 5,000 vectors, so the scan touches approximately 16 × 5,000 = 80,000 PQ-encoded vectors — 0.016% of the catalog — using the same ADC table-lookup arithmetic traced above. That is the whole point of stacking the two levers: pruning cuts the 500 million candidates to 80,000, and compression makes each of those 80,000 comparisons cost table lookups instead of 768-dimensional float arithmetic.
The rerank step production systems don't skip
The 2.25-versus-1.63 gap in the worked example is not a rounding curiosity; it is systematic quantization error, and at 96 subspaces it can reorder close candidates in ways that hurt recall. Production IVF-PQ systems handle this with a final rerank (FAISS calls it a "refine" step): keep the original float32 vectors for the top-few-hundred shortlist candidates — either cached, or fetched from a secondary disk-backed store keyed by vector id — and recompute exact distances on just that shortlist before returning the final top-k. This is affordable precisely because ADC already did the expensive part cheaply: computing exact distance on 200 candidates costs nothing next to computing exact distance on 500 million, but it removes almost all of the quantization error from the final ranking. This two-stage "approximate then exact" pattern, not any single index structure, is usually what a production semantic search team means when they say their system is "IVF-PQ with reranking."
Common misconception: PQ is not dimensionality reduction
Students who have just studied PCA in the "Advanced AI & Mathematics" strand often assume product quantization is a variant of it — both "compress" vectors, so the instinct is to treat them as the same tool. They are not. PCA projects a D-dimensional vector onto a lower-dimensional basis by discarding directions of low variance; the output is a shorter real-valued vector, and information is lost by dropping dimensions. PQ never changes the number of dimensions or projects onto a new basis at all — every subspace still spans its original D/m real-valued dimensions during training and encoding. What PQ discards is not a set of directions but precision within each existing subspace: it replaces each real-valued subvector with the index of its nearest of k* centroids, a discretization (vector quantization) rather than a projection. That is why PQ code size is governed by m and k* (how finely each subspace is discretized), not by how many dimensions are "dropped" — none are. The two techniques are in fact complementary rather than competing: Optimized Product Quantization (Ge, He, Ke & Sun, CVPR 2013) applies a learned rotation, PCA-adjacent in spirit, before PQ encoding specifically to rebalance variance across subspaces and reduce quantization error — it uses a PCA-like transform to make PQ work better, which only makes sense once you see that PQ alone was never doing PCA's job in the first place.
Active recall
Attempt each question before reading its answer.
- For D = 768, m = 64 subspaces, k* = 256 centroids per subspace, what is the PQ code size per vector in bytes, and the compression ratio against float32 storage?
- In the production example (D=768, m=96, k*=256, N=500,000,000), suppose k* is increased from 256 to 65,536 centroids per subspace, with m and D unchanged. Recompute the code size per vector, the compression ratio, and total compressed memory for the 500M-vector catalog. Then trace the ripple effects on the per-query distance table and on codebook training.
- With nlist = 100,000 and N = 500,000,000, nprobe is raised from 16 to 32. Roughly how many vectors are scanned per query, and what happens to recall and latency, qualitatively?
- Why does IVFADC apply PQ to the residual (vector minus assigned coarse centroid) rather than to the raw vector?
- A classmate argues PQ and PCA are "basically the same compression trick." Explain precisely why this is wrong.
- Why must D be evenly divisible by m in the basic PQ scheme, and what does an implementation have to do if it isn't?
Answers
1. 768/64 = 12 dimensions per subspace, which divides evenly, so no padding is needed. Each subspace needs 256 = 28 centroid indices, i.e. 8 bits = 1 byte per subspace. Code size = 64 × 1 byte = 64 bytes/vector. Uncompressed size = 768 × 4 = 3,072 bytes. Compression ratio = 3,072 / 64 = 48×.
2. k* = 65,536 = 216 needs 16 bits = 2 bytes per subspace instead of 1. New code size = 96 × 2 = 192 bytes/vector (versus 96 bytes before). Compression ratio drops from 3,072/96 = 32× to 3,072/192 = 16×. Total compressed memory for 500M vectors doubles, from 48 GB to 500,000,000 × 192 = 96,000,000,000 bytes = 96 GB — still a 16× win over the 1.5 TB baseline, but half as good as before. The ripple does not stop at memory: the per-query distance table grows from 96 × 256 = 24,576 entries to 96 × 65,536 = 6,291,456 entries — a 256× increase in the distance computations needed just to build the table before any database scan starts. In bytes, the table itself grows from 24,576 × 4 = 98,304 bytes (≈96 KB, comfortably inside a typical L2 cache) to 6,291,456 × 4 ≈ 24 MB, which no longer fits in cache and turns each table lookup during the scan into a slower memory access. Offline, training 65,536 centroids per subspace instead of 256 needs a proportionally much larger and more diverse training sample to avoid empty or unstable clusters, and many more k-means iterations to converge — the index-build step, not just the query step, gets substantially slower.
3. Doubling nprobe to 32 roughly doubles the clusters visited, so the scan touches about 32 × 5,000 = 160,000 vectors (0.032% of the catalog, versus 0.016% before) — twice the work of the nprobe=16 case. Recall generally improves, because coarse clustering creates hard boundaries and a query's true nearest neighbor sometimes sits just across one, in a cluster that would have been skipped at nprobe=16; visiting more clusters catches more of those boundary cases. Query latency for the scan phase increases roughly in proportion to nprobe, since it is dominated by scanning that many more inverted-list entries.
4. After coarse assignment, a vector's residual (vector − its cluster's centroid) is small and centered near zero, sharing much less variance than the raw dataset, which itself spans the full spread of the catalog. Training PQ codebooks on residuals lets the same fixed budget of k* centroids per subspace cover a much smaller range of values, so each centroid sits closer to the vectors it represents — lower quantization error for identical code size, compared to quantizing raw vectors directly.
5. PCA reduces dimensionality: it projects a D-dimensional vector onto a lower-dimensional subspace by discarding low-variance directions, producing a shorter real-valued vector, with information lost along the dropped directions. PQ keeps every original dimension conceptually intact — it never changes basis or drops directions. Instead, within each of m contiguous subspaces (which retain their full original dimensionality), PQ replaces the real-valued subvector with the index of its nearest centroid from a small trained codebook: this is discretization (vector quantization), not projection. The two are complementary, not equivalent — OPQ (Ge et al., 2013) applies a rotation before PQ precisely to make PQ's discretization more effective, which would be meaningless if PQ were already doing PCA's job.
6. The basic scheme slices a vector into m contiguous, equal-length chunks of D/m dimensions each; if D is not evenly divisible by m, some chunks would need a different length than others, breaking the assumption that every subspace shares one fixed-size codebook structure. Implementations either choose m to divide D exactly (as with D=768, m=96 or m=64 above, both of which divide evenly), or pad the vector with zero-valued dimensions until it reaches a length divisible by m before splitting, accepting a small amount of wasted codebook capacity on the padded dimensions.
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: building semantic search infrastructure 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: building semantic search infrastructure 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: building semantic search infrastructure, 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.