How Vector Databases actually work?

Moving from a Retrieval-Augmented Generation (RAG) prototype to a production-scale system often reveals a “performance cliff.” While libraries like FAISS or Chroma handle thousands of vectors with ease, scaling to millions or billions requires moving beyond simple list-based comparisons. To maintain sub-second latency, vector databases must solve the “Curse of Dimensionality” by trading absolute precision for sub-linear search time. This is achieved through graph-based traversal, lossy bit-level compression (Quantization), and decoupled storage-compute architectures.

TL;DR

• ANN is the Core: Vector databases utilize Approximate Nearest Neighbor (ANN) algorithms to bypass $O(n)$ exhaustive searches, achieving sub-linear time complexity.
• Index Trade-offs: HNSW provides superior query latency and high recall but consumes 2–5x more memory than clustering methods like IVFFlat due to graph edge storage.
• Quantization Strategies: Scalar Quantization (SQ8) and Product Quantization (PQ) reduce memory footprints by 4x to 10x, though they introduce “rank reversal” risks.
• Hybrid Search Efficiency: Modern engines like Qdrant and Weaviate utilize “In-Graph Filtering” with bitmasks to apply metadata constraints during traversal, preventing the “empty result” problem inherent in post-filtering.

I. The Anatomy of an Embedding: From Float32 to Bitmask

In a standard RAG pipeline, a 1,536-dimension vector — standard for OpenAI’s text-embedding-3-small—is represented as 32-bit floats. The memory math for this is punishing: a single vector requires 6,144 bytes ($1,536 \times 4$). At a scale of 10 million vectors, raw storage alone consumes ~60GB of RAM, excluding indexing overhead.

To mitigate this, vector databases employ Scalar Quantization (SQ8). This process transforms 32-bit floats into 8-bit integers by mapping the floating-point values of each dimension to a 256-step scale based on the distribution of the dataset.

• The Impact: Benchmarks from pgvector demonstrate that SQ8 reduces the RAM footprint by approximately 75% (4x reduction) while maintaining high recall (often >98%).
• The Technical Risk: Precision loss in high-dimensional space can lead to Rank Reversal. Because the distance between vectors in quantized space is an approximation, the “true” nearest neighbor in Float32 space may be displaced by the second or third neighbor in SQ8 space.

II. Navigating the Multi-Dimensional Labyrinth: HNSW vs. IVF

The choice of indexing algorithm is the most significant factor in determining the latency-memory profile of a vector database.

Hierarchical Navigable Small World (HNSW) HNSW is the current industry standard for high-performance retrieval. It constructs a multi-layered graph where the top layers contain sparse, long-range connections (analogous to a Skip List) and the bottom layers contain dense, local connections.

• Performance: HNSW offers the best query-per-second (QPS) rates for high-recall requirements (95%+).
• Memory Overhead: HNSW is memory-intensive. It stores an adjacency list (pointers) for every node. The memory complexity is $O(n \cdot d + n \cdot m)$, where $n$ is the number of vectors, $d$ is the dimensionality, and $m$ is the number of bi-directional connections per node. This often results in a memory footprint 2–5x larger than the raw data.

Inverted File Indexing (IVF) IVF utilizes a clustering approach, dividing the vector space into Voronoi cells. Each cell is represented by a centroid. During a search, the engine identifies the $n$ closest centroids and searches only the vectors within those specific clusters.

• In AWS pgvector tests, creating an HNSW index for 58,000 records took 81 seconds, whereas IVFFlat (an IVF variant) took only 15 seconds.
• IVF is significantly more memory-efficient than HNSW but suffers from higher query latency and lower recall as the dataset grows, as it is prone to missing neighbors that fall just outside the searched Voronoi cells.

III. The Compression Engine: Product Quantization (PQ)

For billion-scale datasets, SQ8 is often insufficient. Product Quantization (PQ) provides a more aggressive compression by decomposing the original vector space into a Cartesian product of low-dimensional subspaces.

Get Navuluribalaji’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

PQ divides a vector into m sub-vectors and runs a clustering algorithm (like k-means) on each subspace to create a codebook. Each sub-vector is then replaced by the index of its nearest centroid.

• Databases like Milvus use PQ to enable “Billion-scale” search, where a 1,536-dimension vector is compressed into a compact string of codes. This allows indices to fit entirely within L3 cache or RAM, drastically reducing I/O operations.
• PQ is a “lossy” compression. Unlike SQ8, which simply lowers precision, PQ fundamentally replaces values with cluster representatives. Once compressed, the original float values cannot be recovered, making re-ranking — where the top results are re-calculated using exact distance — difficult without original data persistence.

IV. The Hybrid Search Paradox: Pre-filtering vs. Post-filtering

Production queries rarely rely solely on semantic similarity. A common query might be: “Find ‘Legal’ documents (Metadata) similar to ‘Contract A’ (Vector).”

1. Post-filtering: The engine retrieves the top-K nearest neighbors and then discards those that do not match the metadata filter. This leads to the “empty result” problem: if the top 100 neighbors are not “Legal” documents, the user receives zero results, even if the 101st neighbor was a perfect match.
2. Pre-filtering (Bitmasking): Modern engines like Qdrant and Weaviate utilize In-Graph Filtering. They maintain a bitmask of all documents that satisfy the metadata criteria. During the HNSW graph traversal, the algorithm only considers nodes where the bitmask is “active.” This ensures that the search returns the most similar vectors that also meet the metadata constraints.

V. Distributed Topology: Decoupling Storage from Compute

To achieve horizontal scalability, architectural design has shifted from monolithic instances to tiered, cloud-native models. Milvus 2.0 exemplifies this with a four-layer architecture:

• Access Layer (Proxy): Handles request parsing and result aggregation.
• Coordinator Service: Manages cluster topology and task assignment.
• Worker Nodes (Query/Data/Index): These nodes are specialized. Query nodes are optimized for memory-intensive ANN searches, often utilizing local NVMe for caching.
• Storage Layer: Employs object storage (e.g., S3) for long-term persistence, using a “log-as-data” approach where all mutations are recorded as a sequence of log events.

This decoupling allows engineers to scale Query Nodes (compute/RAM) independently of Data Nodes (storage), a critical feature for managing the high costs of memory-intensive vector indices.

VI. The “Failure Modes” Engineering Reality Check

Engineering for vector databases requires accounting for physical constraints that traditional relational databases do not face.

• Cold Start Latency: In serverless architectures, the index is often stored in S3. The first query after a period of inactivity may trigger a “cold start,” where the index must be loaded into the Query Node’s RAM. This can result in latencies of 10 seconds or more.
• The Memory Trap: Because HNSW performance relies on keeping the graph adjacency list in memory, query speed drops exponentially once the index exceeds the available L3 cache or RAM. If the system is forced to swap to disk, a 5ms query can instantly degrade to 500ms.
• Build-Time vs. Query-Time: As demonstrated in AWS RDS benchmarks, HNSW provides superior query speed but is roughly 5.4x slower to build than IVF. For high-velocity data where the index must be updated in real-time, the build-time overhead of HNSW can create significant ingestion bottlenecks.

Conclusion

Optimizing a vector database is a balancing act between three competing variables: Recall, Latency, and Cost. Choosing HNSW over IVF is a commitment to latency at the expense of RAM. Choosing PQ over SQ8 is a commitment to scale at the expense of precision. For the Senior Engineer, the objective is not to find a “perfect” database, but to select an indexing and quantization strategy that maintains the required recall within the physical constraints of the hardware.

Key Takeaways

1. HNSW is the Latency Leader: Use it for production environments where query speed is the priority and memory budget is secondary.
2. Quantization is Mandatory at Scale: Implement SQ8 as a baseline optimization to reduce RAM requirements by 4x without significant recall loss.
3. Favor In-Graph Filtering: Ensure your database provider supports metadata filtering during the search traversal (bitmasking) to avoid the pitfalls of post-filtering.
4. Monitor the Index-RAM Ratio: Always keep your HNSW index within the available RAM. Falling off the “memory cliff” into disk-swapping is the most common cause of production performance failure.

Sources

• AWS Database Blog: Vector Engine for Amazon OpenSearch Serverless.
• Milvus Documentation: Distributed Architecture and Log-as-Data.
• ANN-Benchmarks (ann-benchmarks.com): Comparative analysis of HNSW vs. IVFFlat.