Introduction: limitations of brute-force search

A naive Vector DB uses approximate nearest neighbor (ANN) via brute-force: for every query, compute Euclidean distance to all N vectors, sort by top-k. Complexity: O(N × d) where d=number of dimensions. With N=100M and d=768:

• Float operations: 100M × 768 = 76.8 billion operations per query.
• Single query latency: ~250ms (CPU bound).
• Throughput 1000 queries/sec: impossible.
• RAM consumed: 100M × 768 × 4 bytes = 307 GB (float32).

The solution is to shift paradigm toward hierarchical indexing (HNSW — Hierarchical Navigable Small World) where search becomes O(log N) with smart graph traversal.

Indexing strategies for 100M+ vectors

1. HNSW (Hierarchical Navigable Small World) — The modern gold standard

HNSW is a probabilistic algorithm that builds a multi-layer graph where layer 0 contains all vectors, layer 1 contains 10%, layer 2 contains 1%, etc. Search starts from the top layer (few nodes) and descends, navigating locally toward approximate nearest neighbor. Query complexity: O(log N). Key properties:

• Memory-efficient: Approximately 3-5x the float dataset RAM (not infinite).
• Sublinear latency: 100M vectors ~40ms average (vs 250ms brute-force).
• Tunable accuracy: Parameters M (edges per node) and ef (search expansion factor).

Implementation parameters:

import hnswlib

# Create HNSW index for 100M vectors, dim=768
index = hnswlib.Index(space='cosine', dim=768)
index.init_index(max_elements=100_000_000,
                 ef_construction=200,  # accuracy construction (200-400 common)
                 M=16)                 # max connections per node (8-64 range)

# Load vectors in batch: each batch 10K vectors
for batch_idx in range(0, 100_000_000, 10_000):
    vectors = load_batch(batch_idx, batch_idx + 10_000)
    labels = range(batch_idx, batch_idx + 10_000)
    index.add_items(vectors, labels)

# Save index to disk (persistence)
index.save_index("vectors_100m.hnsw")

# Query: return top-10 neighbors
query_vector = [0.1, 0.2, ..., 0.8]  # 768 dim
index.set_ef(ef=100)  # ef search trade-off latency/accuracy
labels, distances = index.knn_query(query_vector, k=10)
        

2. IVF (Inverted File Index) — For extreme compression

IVF divides vector space into Voronoi cells (e.g., 1000 clusters). Each vector is assigned to its cluster and neighbor vectors within the cluster are encoded. Search: find query-nearest cluster and search only within top-5 clusters. Latency O(clusters_searched × cluster_size), not O(N).

import faiss

# IVF: create 1000 clusters (Voronoi)
quantizer = faiss.IndexFlatL2(768)  # quantizer for distance
index = faiss.IndexIVFFlat(quantizer, 768, 1000)
index.train(training_vectors)

# Add 100M vectors: each vector goes into one of 1000 clusters
index.add(all_vectors)

# Query search: only in top 5 clusters (probe=5)
index.nprobe = 5
distances, labels = index.search(query_vector, k=10)
        

3. DiskANN — For ultra-large scale (1B+ vectors)

Microsoft DiskANN stores graph on SSD, not RAM. Each node keeps only K nearest neighbors (not N). SSD access is ~100x slower than RAM but consumes 100x less memory. For 1B vectors: memory ~10GB, latency ~200ms (acceptable for some use cases).

Partitioning and sharding 100M vectors

Beyond a certain threshold (typically 50-200M per cluster), distributing vectors across multiple machines becomes necessary. Two strategies:

Range Partitioning: Shard by ID ranges

Assign vectors to shards based on ID modulo number of shards. Simple but risky for skewed distributions.

# 100M vectors distributed across 10 shards (10M per shard)
num_shards = 10

def get_shard(vector_id, num_shards):
    return vector_id % num_shards

# Shard 0: IDs 0, 10, 20, ..., 99999990
# Shard 1: IDs 1, 11, 21, ..., 99999991
# etc.

# Query: send to ALL shards, merge top-10 results
query_result = []
for shard_id in range(num_shards):
    partial_result = query_shard(shard_id, query_vector, k=100)
    query_result.extend(partial_result)

# Merge: take top-10 globally from merged results
final_result = sorted(query_result, key=lambda x: x.distance)[:10]
        

Semantic Partitioning: Shard by feature clustering

Run K-means on a sample of vectors, assign cluster membership to each vector. Semantically similar vectors end up in the same shard. Query: calculate affinity with cluster centroids, interrogate only top-3 shards. Lower latency.

from sklearn.cluster import KMeans

# Sample 1M vectors for clustering
sample_vectors = random_sample(all_vectors, 1_000_000)
kmeans = KMeans(n_clusters=10)
kmeans.fit(sample_vectors)

# Assign each vector to cluster
def assign_to_shard(vector):
    distances_to_centroids = np.linalg.norm(
        kmeans.cluster_centers_ - vector, axis=1)
    shard_id = np.argmin(distances_to_centroids)
    return shard_id

# Query: find top-3 cluster-nearest
query_centroid_dist = np.linalg.norm(
    kmeans.cluster_centers_ - query_vector, axis=1)
top_shards = np.argsort(query_centroid_dist)[:3]

result = []
for shard_id in top_shards:
    partial = query_shard(shard_id, query_vector, k=50)
    result.extend(partial)

final = sorted(result, key=lambda x: x.distance)[:10]
        

Quantization: reduce memory by 75%

You're storing float32 (4 bytes per component). With d=768 and 100M vectors: 307 GB RAM. uint8 quantization reduces to 77 GB (75% savings). Trade-off: accuracy decreases ~2-3% but latency improves significantly.

Uniform uint8 quantization

Map the [min_val, max_val] range of each dimension to [0, 255].

import numpy as np

def quantize_vector(vector, min_val=None, max_val=None):
    """Quantize float32 to uint8"""
    if min_val is None:
        min_val = np.percentile(vector, 0.1)
    if max_val is None:
        max_val = np.percentile(vector, 99.9)

    # Normalize to [0, 1]
    normalized = (vector - min_val) / (max_val - min_val + 1e-8)
    normalized = np.clip(normalized, 0, 1)

    # Scale to [0, 255]
    quantized = (normalized * 255).astype(np.uint8)
    return quantized, min_val, max_val

def dequantize_vector(quantized, min_val, max_val):
    """Dequantize uint8 to float32"""
    normalized = quantized.astype(np.float32) / 255.0
    vector = normalized * (max_val - min_val) + min_val
    return vector

# Apply to all 100M vectors
quantized_vectors = []
scales = {}

for i in range(0, 100_000_000, 100_000):
    batch = all_vectors[i:i+100_000]
    batch_quantized, min_val, max_val = quantize_vector(batch)
    quantized_vectors.append(batch_quantized)
    scales[i] = (min_val, max_val)

# HNSW index on uint8 (memory: 25% of original)
quantized_index = hnswlib.Index(space='l2', dim=768)
quantized_index.add_items(np.vstack(quantized_vectors))
        

Query optimization and batch processing

Batch queries: reduce latency for thousand queries

Sending queries one at a time is inefficient. Batch processing leverages SIMD parallelization:

# BAD: serial queries
latency_total = 0
for query_vec in query_batch:
    start = time.time()
    result = index.search(query_vec, k=10)
    latency_total += time.time() - start
# 1000 queries × 40ms = 40 seconds

# GOOD: batch queries with vectorization
start = time.time()
query_matrix = np.vstack(query_batch)  # [1000, 768]
results = index.batch_search(query_matrix, k=10)
elapsed = time.time() - start
# 1000 queries × 0.8ms = 0.8 seconds (50x improvement!)
        

Query result caching

Repeated queries often hit the same vectors. LRU cache on Redis:

import redis
import hashlib

redis_cache = redis.Redis(host='localhost', port=6379)

def search_with_cache(query_vector, k=10):
    # Hash of query
    query_hash = hashlib.md5(query_vector.tobytes()).hexdigest()
    cache_key = f"vector_search:{query_hash}:k{k}"

    # Try cache
    cached_result = redis_cache.get(cache_key)
    if cached_result:
        return json.loads(cached_result)

    # Cache miss: query the index
    result = index.search(query_vector, k=k)

    # Cache for 1 hour
    redis_cache.setex(cache_key, 3600, json.dumps(result))
    return result
        

Memory management for 100M+ vectors

Real-time RAM monitoring

import psutil

def monitor_memory():
    process = psutil.Process()
    memory_info = process.memory_info()

    rss_mb = memory_info.rss / 1024 / 1024  # Resident set size
    vms_mb = memory_info.vms / 1024 / 1024  # Virtual memory size

    print(f"RSS: {rss_mb:.0f} MB | VMS: {vms_mb:.0f} MB")

    # Alert if RSS > 80GB
    if rss_mb > 80_000:
        trigger_scale_out()  # Spinup new shard

# Call every 5 minutes
schedule.every(5).minutes.do(monitor_memory)
        

Eviction policy for cache overflow

When RAM fills up, implement LRU eviction: remove least-accessed vectors from RAM, keep as warm cache on SSD.

Monitoring and alerting in production

Critical KPIs for 100M+ setup

• Query latency (p50, p95, p99): Target p95 < 100ms, alert if > 200ms for 5 min.
• RAM usage: Alert if > 85% to prevent OOM.
• Index freshness: Time between insert and queryable. Target < 10 seconds.
• Recall accuracy: Top-10 returned match top-10 brute-force. Target > 95%.

from prometheus_client import Histogram, Gauge

# Prometheus metrics
query_latency = Histogram('vector_search_latency_ms', 'Query latency')
ram_usage = Gauge('ram_usage_gb', 'RAM usage')
index_freshness = Gauge('index_freshness_seconds', 'Time to index')

def record_query_latency(duration_ms):
    query_latency.observe(duration_ms)

def record_ram():
    usage_gb = psutil.virtual_memory().used / 1024**3
    ram_usage.set(usage_gb)

# Setup alerts in Grafana
# p95 latency > 200ms for 5 min → page oncall
# ram > 85% → scale out shard
        

Case study: scaling to 200M vectors in production

Enterprise RAG system, 200M internal article vectors (d=768). Challenge: 5000 queries/sec, p95 latency budget 100ms.

Implemented solution

• Sharding: 4 geographic shards (EU-West, EU-Central, US-East, Asia-Pacific), 50M vectors each.
• Indexing: HNSW + uint8 quantization (reduced from 307GB to 77GB globally).
• Query routing: Load balancer sends queries to geographically closest shard + hot-standby.
• Batch processing: Application batch-accumulates queries, sends every 50ms in batch of 100.
• Cache: Redis cluster (3 nodes) caches top-100 queries (80% hit rate).

Result: 100ms p95 consistently. Infrastructure cost: €2K/month on Hetzner (vs €50K cloud managed service).

FAQ: common questions on Vector DB scaling

Q1: When should I migrate from single-instance to cluster?

Answer: Recommended threshold: 50-100M vectors. At 100M+ the single-instance cost (RAM + CPU) becomes unsustainable and latency degrades. A cluster of 4-8 nodes is the cost/performance sweet-spot.

Q2: Does uint8 quantization reduce accuracy too much?

Answer: Depends on use case. For information retrieval (top-10 neighbors) accuracy decreases ~1-2%. For clustering/anomaly detection it may decrease more. Best practice: test on your dataset with recall metric (compare top-10 quantized vs float32).

Q3: When to use HNSW vs IVF?

Answer: HNSW is the modern default (sub-100ms, 95%+ recall). Use IVF if you need extreme compression (1B+ vectors) and can tolerate 150-300ms latency. Use DiskANN if infrastructure budget is very limited.

Q4: How to avoid hotspots in sharding?

Answer: Range partitioning causes skew if ID distribution is unbalanced. Use semantic partitioning (K-means clustering) or consistent hashing to distribute query load uniformly. Monitor queries/sec per shard and automatically rebalance every 24h.

Q5: Infrastructure cost for 100M vector cluster?

Answer: Estimate: 4 r7i.2xlarge nodes (768 GB total RAM), NVMe SSD for durability. AWS: ~€8K/month. Hetzner: ~€2K/month. Self-hosted datacenter: €300/month (hardware) + ops (€3K/month). Pinecone managed: €12K/month.

Conclusions and next steps

Scaling Vector Database beyond 100 million vectors does not require new innovation, but rather careful selection of 4 proven techniques: HNSW hierarchical indexing, semantic sharding, quantization, and batch processing. When implemented disciplined, modern production systems maintain sub-100ms latency and sustainable costs even at massive scale.

Action items: (1) Benchmark HNSW vs IVF on your dataset with recall metric. (2) Plan sharding strategy (semantic or range) based on query distribution. (3) Setup latency/recall monitoring in staging before production. (4) Quantize and test accuracy impact.