Vector Database Indexing, HNSW Graphs & Capacity Estimation

Vector Database Indexing & Capacity Estimation

As Large Language Models (LLMs) proliferate, the demand for fast, high-dimensional similarity search has skyrocketed. Vector databases (e.g., Pinecone, Milvus, Qdrant, pgvector) rely on Approximate Nearest Neighbor (ANN) algorithms to find semantic proximity in sub-linear time.

1. The High-Dimensional Bottleneck

In standard relational databases, indexing uses B-Trees (O(\log N) time complexity) because scalar values (integers, strings, timestamps) have a total order.

High-dimensional vectors have no total order. When vectors live in \mathbb{R}^{1536}, computing Euclidean Distance (L_2) or Cosine Similarity:

[ Layer 2: Sparse Highway ]    (Node 1) -------------> (Node 8)
                                  |                       |
                                  v                       v
[ Layer 1: Medium Density ]    (Node 1) -> (Node 4) -> (Node 8)
                                  |           |           |
                                  v           v           v
[ Layer 0: Full Dense HNSW ]   (Node 1)->(2)->(3)->(4)->(5)->(8)

Fig 1. HNSW multi-layer graph navigation: greedy routing at top layers, dense local search at base layer.

2. Hierarchical Navigable Small World (HNSW)

HNSW is currently the state-of-the-art graph-based indexing algorithm:

• Skip-List Analogy: HNSW constructs a multi-layer geometric graph inspired by probabilistic skip-lists. Top layers contain only a sparse subset of vectors connected across large distances.
• Greedy Traversal: A query enters at the top layer, greedily navigates to the nearest neighbor, drops down a level, and repeats until reaching Layer 0.
• Bounded In-Degree: Each node is connected to at most M neighbors (typically M=16 or M=64), capping graph growth to O(N \log N) construction time and O(\log N) search time.

3. Rigorous Memory & Capacity Calculation

When sizing vector database infrastructure (RAM, disk, compute), use the following formula:

Where:

• N = Number of vectors in the index (e.g., 10,000,000 chunks)
• D = Dimensionality of the embedding model (e.g., 1536 for OpenAI text-embedding-ada-002, 3072 for text-embedding-3-large, 768 for open-source bge-base)
• S_b = Bytes per scalar dimension (4\text{ bytes} for standard Float32, 2\text{ bytes} for Float16)

Example: 10 Million Vectors (D=1536)

1. Raw Vectors:
   10^7 \times 1536 \times 4\text{ bytes} = 61,440,000,000\text{ bytes} \approx 61.44\text{ GB}
2. HNSW Graph Overhead: Each vector maintains M bidirectional edges (M=32). Each edge pointer takes 8 bytes.
   10^7 \times 32 \times 8\text{ bytes} \approx 2.56\text{ GB}
   Plus vector metadata, ID mapping, and search buffers, HNSW overhead adds roughly 35\text{--}45\%:
   \text{Total RAM Required} = 61.44\text{ GB} \times 1.40 \approx 86.0\text{ GB RAM}

4. Vector Quantization Techniques

To avoid deploying 100+ GB RAM instances, production systems apply quantization:

• Scalar Quantization (SQ8): Maps each 32-bit float to an 8-bit integer using uniform bucketing between min and max dimensions.
  • Slashes raw vector memory by 4\times (61.44\text{ GB} → 15.36\text{ GB}).
  • Recall penalty: typically <1.5%.
• Product Quantization (PQ): Divides the 1536-dimensional vector into m=96 sub-vectors of 16 dimensions each. Clusters sub-vectors into 256 centroids using k-means, replacing 16 floats with a single 1-byte centroid index.
  • Slashes memory by 16\times (61.44\text{ GB} → 3.84\text{ GB}).
  • Allows the entire index to fit in consumer-grade L3 CPU caches for extreme QPS throughput.