Index Memory Footprint

In a Hierarchical Navigable Small World (HNSW) graph, memory is dominated by the storage of edges connecting nodes (vectors). Each node maintains connections to its nearest neighbors across multiple hierarchical layers.

• Memory Cost: Scales with M * num_vectors * num_layers, where M is the maximum number of connections per layer.
• Example: For 10 million vectors with M=16 and 3 layers, storing 32-bit integer IDs for edges can consume several gigabytes of RAM.
• Trade-off: Higher M improves recall and search speed but linearly increases memory usage.

An Inverted File (IVF) index uses a coarse quantizer—typically built via k-means clustering—to partition vectors into Voronoi cells. The memory stores the list of centroid vectors and an inverted index mapping each centroid to its list of vector IDs.

• Memory Cost: Primarily num_centroids * vector_dimension * bytes_per_value. For 10,000 centroids of 768-dimension float32 vectors, this is ~30 MB.
• The Inverted Index: Adds overhead for storing dynamic lists of postings (vector IDs) for each cell. Memory scales with dataset size and distribution.

Quantization compresses vectors to reduce memory. This requires storing learned codebooks.

• Product Quantization (PQ): Splits a vector into m subvectors. Each subvector cluster has a codebook of k centroids. Memory is m * k * (dimension/m) * bytes_per_value.
• Scalar Quantization (SQ): Uses a global codebook of quantization levels (e.g., 256 levels for 8-bit). Memory is minimal, often just storing per-dimension min/max values for range normalization.
• Residual Storage: In IVFPQ, only the quantized codes (integers) for residuals are stored, not the full vectors, offering massive compression.

The raw or compressed representation of the vectors themselves is the foundational memory component.

• Full-Precision (e.g., float32): Most expensive. Memory = num_vectors * dimension * 4 bytes.
• Quantized Storage: Vectors are represented by compact codes.
  • PQ Codes: Each vector is m bytes (one byte per subvector code).
  • SQ Codes: Each vector is dimension bytes (e.g., uint8).
• Hybrid Approaches: Systems like DiskANN store full-precision vectors on disk and keep only a compressed cache or graph structure in RAM.

Additional in-memory data structures are required to enable efficient search operations.

• Priority Queues (Heaps): Used during beam search in graph traversal. Size is controlled by the search beam width hyperparameter.
• Distance Lookup Tables: For Product Quantization, pre-computed distances between query subvectors and codebook centroids are stored in tables to accelerate Asymmetric Distance Computation (ADC).
• Visited Bitmaps: To avoid revisiting nodes during graph search, a bitmap marking visited nodes is allocated. Size is num_vectors / 8 bytes.

Production vector databases support hybrid search, combining vector similarity with metadata filtering. This requires auxiliary indices.

• Filtering Indices: In-memory structures like Roaring Bitmaps or B-Trees to index scalar metadata (e.g., user_id, timestamp). Memory scales with the cardinality and number of filterable fields.
• Vector ID Mapping: Systems need a mapping from internal vector IDs to external primary keys and metadata records.
• Statistics: Per-partition or per-segment statistics for query planning and optimization.

A lossy compression technique that dramatically reduces memory footprint by splitting vectors into subvectors and quantizing each using a learned codebook. Instead of storing full-precision vectors (e.g., 32-bit floats), PQ stores only the indices to codebook entries.

• Key Mechanism: Divides a D-dimensional vector into m subvectors of D/m dimensions. Each subvector is replaced by the ID of its nearest centroid in a small, pre-trained codebook (e.g., 256 centroids, requiring an 8-bit index).
• Memory Impact: Can reduce storage from 4 bytes per dimension (float32) to less than 1 byte per dimension, enabling billion-scale datasets to fit in RAM.
• Trade-off: Introduces quantization error, as distances are approximated using lookup tables rather than exact calculations.

A composite indexing algorithm that combines an Inverted File (IVF) for coarse partitioning with Product Quantization (PQ) for fine compression. It is the industry standard for high-performance, memory-efficient search.

• Two-Stage Design: First, an IVF index uses k-means clustering to partition the dataset into Voronoi cells. The search probes only the nearest cells. Second, vectors within those cells are compressed using PQ.
• Memory Footprint: Achieves a multiplicative reduction. The IVF component stores centroids (minimal overhead), while the PQ component compresses the residual vectors (original vector minus centroid).
• Performance: Enables fast search by restricting distance computations to a small subset of compressed vectors, using Asymmetric Distance Computation (ADC) for accuracy.

A simpler compression method that reduces the precision of each vector component independently, directly shrinking memory footprint and accelerating distance calculations.

• Process: Maps each 32-bit floating-point value in a vector to an 8-bit (or 4-bit) integer by dividing the value range into discrete levels. For example, float32 values between -1.0 and 1.0 can be linearly mapped to integers 0-255.
• Memory Impact: Provides a predictable 4x reduction (32-bit to 8-bit) or 8x reduction (32-bit to 4-bit).
• Use Case: Often used as a pre-filtering step or in conjunction with other indexes. It is less effective than PQ for very high-dimensional vectors but is computationally cheaper to apply.

A graph-based index specifically engineered for billion-scale datasets with a minimal in-memory footprint by leveraging solid-state drive storage.

• Core Principle: Stores the primary graph index on SSD and caches only a small, frequently accessed working set in RAM. Search traverses the on-disk graph with high IO efficiency.
• Memory Footprint: Can be orders of magnitude smaller than fully in-memory indexes for the same dataset size, as only graph adjacency lists for the cached frontier are resident.
• Trade-off: Achieves high recall and throughput but with higher search latency (milliseconds) compared to purely in-memory indexes (microseconds). Ideal for cost-effective, large-scale archival search.

The two-stage architecture used in composite indexes to balance memory and accuracy. The coarse quantizer narrows the search scope; the fine quantizer compresses within that scope.

• Coarse Quantizer (e.g., IVF): A clustering algorithm (like k-means) that partitions the dataset. It stores a list of centroids and an inverted index mapping each centroid to its list of vectors. Memory overhead is low (just the centroids).
• Fine Quantizer (e.g., PQ): Operates on the residual vectors (the difference between a vector and its coarse centroid). By compressing these residuals, it achieves high compression ratios with controlled error.
• System Impact: This separation allows independent tuning—adding more coarse centroids increases search speed but not memory, while adding more PQ codebooks increases memory and accuracy.

The inevitable distortion or information loss introduced when compressing continuous-valued vectors into discrete representations, directly impacting search accuracy.

• Definition: The difference between the distance calculated using the original full-precision vectors and the distance approximated using their quantized representations.
• Impact on Recall: Higher quantization error generally lowers Recall@k, as the approximate distances may misorder the true nearest neighbors. This is the fundamental trade-off for reduced memory footprint.
• Mitigation Strategies:
  • Asymmetric Distance Computation (ADC): Uses the full-precision query against quantized database vectors.
  • Multi-Codebook Quantization: Using more codebooks in PQ reduces error at the cost of memory.
  • Exact Re-ranking: A second-stage pass that re-scores top candidates using full-precision vectors.