How Vector Databases Work: HNSW Indexes, Similarity Search, and the Storage Engine Behind AI-Native Retrieval

Most engineers first encounter a vector database the same way: drop a few embeddings in, do a similarity query, be surprised it works. Then they try to scale it, or add filters, or tune for sub-10ms latency, and the abstraction stops holding. The underlying system is doing something specific and constrained, and understanding what it is doing turns debugging from guesswork into engineering.

This article covers the full internals: how embeddings are stored and indexed, how HNSW traversal works at the graph level, where IVF and product quantization fit in, how the query path goes from a vector to top-K results, what happens when you combine ANN search with metadata filters, and what the write path looks like from ingestion to persistence. The tradeoffs section compares the major systems across the dimensions that actually matter in production, and the production section covers the decisions that separate a prototype from a reliable retrieval system.

Embeddings: What Is Actually Stored

A vector database stores high-dimensional floating-point arrays alongside metadata. A text embedding from a model like text-embedding-3-small produces a 1536-dimensional float32 vector. An image embedding might be 768 or 2048 dimensions. Each dimension encodes some learned feature of the input, though the individual dimensions are not semantically interpretable.

The database associates each vector with an ID and an optional metadata payload (a JSON object). The core invariant is that vectors close in the embedding space represent semantically similar inputs, by whatever geometry the embedding model was trained on.

// What a vector record looks like structurally
interface VectorRecord {
  id: string;
  vector: number[]; // e.g., 1536 floats for text-embedding-3-small
  metadata: Record<string, string | number | boolean | string[]>;
}

// Inserting a document embedding into Qdrant (illustrative)
async function upsertEmbedding(
  client: QdrantClient,
  collectionName: string,
  record: VectorRecord
): Promise<void> {
  await client.upsert(collectionName, {
    wait: true,
    points: [
      {
        id: record.id,
        vector: record.vector,
        payload: record.metadata,
      },
    ],
  });
}

The naive retrieval approach is exact nearest neighbor search: compute the distance from the query vector to every stored vector, sort, return the top K. At 10M vectors with 1536 dimensions, that is 10M dot products per query, each involving 1536 multiply-accumulate operations. Even with AVX-512, this takes hundreds of milliseconds. This is why approximate nearest neighbor (ANN) algorithms exist, and why HNSW became the dominant index structure.

HNSW: The Index Structure That Makes ANN Practical

HNSW stands for Hierarchical Navigable Small World. It is a graph-based index where nodes represent vectors and edges connect similar vectors. The key insight is the hierarchical structure: a multi-layer graph where upper layers are sparse long-range graphs and lower layers are dense short-range graphs. This structure allows search to start at the top (navigating quickly across large distances) and progressively descend to the bottom layer (refining toward the nearest neighbors).

Building the Graph

When a vector is inserted, HNSW assigns it a random maximum layer level using an exponential decay probability distribution. Most vectors land on layer 0 (the dense base layer). A small fraction reach layer 1, fewer reach layer 2, and so on. This mirrors the structure of skip lists.

For each layer from the assigned maximum down to layer 0, the algorithm:

1. Enters the graph at the current entry point.
2. Performs a greedy search, moving to whichever neighbor is closest to the new vector.
3. Collects the ef_construction nearest candidates found during traversal.
4. Selects M neighbors from those candidates using a heuristic that prefers diverse connections over purely closest ones.
5. Creates bidirectional edges between the new node and the selected neighbors.

The parameter M controls the maximum number of edges per node per layer. Higher M means better recall but more memory and slower inserts. Typical values range from 8 to 48. The parameter ef_construction controls candidate pool size during build: higher values improve graph quality (and thus recall at query time) at the cost of longer index build time.

// Conceptual HNSW insert — illustrates what the algorithm is doing
// Real implementations are in C++ with SIMD distance computation

interface HNSWNode {
  id: string;
  vector: number[];
  maxLayer: number;
  // connections[layer] = list of neighbor node IDs at that layer
  connections: Map<number, string[]>;
}

function assignMaxLayer(mL: number): number {
  // mL = 1 / ln(M), controls layer distribution
  // Result follows exponential distribution — most nodes land at layer 0
  return Math.floor(-Math.log(Math.random()) * mL);
}

Searching the Graph

At query time, the search starts from the entry point at the topmost layer and greedily descends. At each layer, the algorithm maintains a dynamic candidate list of size ef (the ef_search parameter), moving toward closer nodes until no neighbor is closer than the worst candidate in the current set.

The descent from layer to layer is fast because upper layers have long-range edges: a few hops cover large distances. By layer 0, the algorithm is in the right neighborhood and explores locally with high density. The key property of small-world graphs is that the average path length between any two nodes grows logarithmically with the number of nodes, which is what makes HNSW’s O(log N) search complexity hold empirically.

ef_search is the primary recall/latency knob at query time. Higher ef_search explores more candidates before returning, increasing recall but increasing latency. Setting ef_search = K (where K is the number of results requested) gives minimum latency but degraded recall. Setting ef_search = 200 for K = 10 is a common production starting point.

IVF and Product Quantization: Memory Efficiency at Scale

HNSW stores the full float32 vectors in memory alongside the graph structure. At 1536 dimensions per vector, that is 6KB per vector. One million vectors requires roughly 6GB of RAM before graph overhead. For 100M vectors, this is impractical on a single node without quantization.

Inverted File Index (IVF)

IVF partitions the vector space into nlist Voronoi cells using k-means clustering. Each cell has a centroid. At index build time, every vector is assigned to its nearest centroid and stored in that cell’s inverted list. At query time, the algorithm identifies the nprobe cells whose centroids are closest to the query vector and performs exact search within only those cells.

This dramatically reduces the search space: instead of scanning all N vectors, you scan only (nprobe / nlist) * N vectors on average. The recall/speed tradeoff is controlled by nprobe. IVF trades some recall for scalability: vectors near cell boundaries may get assigned to the wrong cell, and their true nearest neighbors may live in an adjacent cell that does not get probed.

Product Quantization (PQ)

PQ compresses vectors from float32 down to a compact code, typically 8-64 bytes regardless of original dimensionality. The approach: divide the vector into M sub-vectors of equal dimension. Train a separate codebook of k centroids for each sub-vector using k-means. Encode each sub-vector as the index of its nearest centroid in that codebook.

A 1536-dim float32 vector (6KB) can be compressed to 64 bytes with M=64, k=256 PQ, achieving 96x compression. The distance between a query vector and a PQ-encoded database vector can be computed using precomputed lookup tables without decompressing: this is called Asymmetric Distance Computation (ADC).

The combination of IVF and PQ (IVF-PQ) is what systems like Faiss use to run billion-scale similarity search on a single machine. The recall is lower than HNSW at comparable memory, but the memory footprint is orders of magnitude smaller.

Distance Metrics: Cosine, Euclidean, and Dot Product

The choice of distance metric matters and must match how the embedding model was trained.

Dot product is the raw similarity measure: the sum of element-wise products. It is fast to compute (a single BLAS SDOT call) and is the natural metric for models trained with contrastive learning. The problem: magnitude encodes information. Two vectors pointing in the same direction but with different magnitudes have different dot products.

Cosine similarity normalizes by magnitude first. It is equivalent to dot product on unit-normalized vectors. Most text embedding models produce unit vectors or expect cosine comparison. If your vectors are already L2-normalized (as they are from OpenAI’s embedding API), cosine and dot product are identical.

Euclidean distance (L2) measures geometric distance. It is the appropriate metric for dense retrieval scenarios where magnitude carries meaning, or when using models trained with L2 loss. L2 is sensitive to dimensionality: high-dimensional spaces suffer from the curse of dimensionality where L2 distances become increasingly uniform.

// Distance metrics implemented in TypeScript — useful for understanding,
// not for production (use native SIMD implementations in actual systems)

function dotProduct(a: number[], b: number[]): number {
  return a.reduce((sum, val, i) => sum + val * b[i], 0);
}

function cosineSimilarity(a: number[], b: number[]): number {
  const dot = dotProduct(a, b);
  const magA = Math.sqrt(dotProduct(a, a));
  const magB = Math.sqrt(dotProduct(b, b));
  return dot / (magA * magB);
}

function euclideanDistance(a: number[], b: number[]): number {
  return Math.sqrt(a.reduce((sum, val, i) => sum + (val - b[i]) ** 2, 0));
}

Metadata Filtering: Pre-filter vs Post-filter

In production, you rarely want the top K most similar vectors across all data. You want the top K most similar vectors that belong to a specific user, have a specific tag, or fall within a date range. This is where ANN search meets structured filtering, and the interaction is non-trivial.

Post-filter

The naive approach: run ANN search to get the top ef results, then apply the metadata filter. Fast index traversal, simple implementation. The problem: if only 1% of your vectors match the filter, you may need to retrieve 100x more ANN results than requested to find K that pass the filter. At low selectivity, this degrades to full scan or returns fewer than K results.

Pre-filter

Build a filtered candidate set first (from an inverted index on the metadata), then run the similarity comparison only within those candidates. Recall is exact within the filtered set, but HNSW traversal cannot be used directly on an arbitrary subset of the graph. Some systems reindex on the fly or maintain per-attribute subgraphs, which adds complexity and memory.

Hybrid Approaches

Qdrant and Weaviate both implement adaptive filtering: they estimate selectivity at query time and switch strategies based on the size of the filtered set. If the filter matches a large fraction of the corpus (high selectivity, meaning many matches), post-filtering is efficient. If the filter is highly restrictive, the system falls back to exact search within the filtered IDs. The threshold and strategy are implementation-specific.

// Query that requires filtering — how this looks from the application layer
interface FilteredQuery {
  vector: number[];
  topK: number;
  filter: {
    must: Array<{
      key: string;
      match?: { value: string | number | boolean };
      range?: { gte?: number; lte?: number };
    }>;
  };
}

// Qdrant-style query with payload filter
async function searchWithFilter(
  client: QdrantClient,
  collectionName: string,
  query: FilteredQuery
): Promise<ScoredPoint[]> {
  return client.search(collectionName, {
    vector: query.vector,
    limit: query.topK,
    filter: {
      must: query.filter.must.map((condition) => ({
        key: condition.key,
        ...(condition.match ? { match: condition.match } : {}),
        ...(condition.range ? { range: condition.range } : {}),
      })),
    },
    with_payload: true,
  });
}

The Write Path: Ingestion to Persistence

Understanding the write path matters when you are dealing with index build time, write throughput, and freshness guarantees.

Ingestion: The client submits a vector upsert. The server validates the dimensionality (must match the collection’s configured dimension), assigns or validates the ID, and writes to a write-ahead log (WAL) for durability.

Buffering: New vectors go into an in-memory buffer or a mutable “growing” segment. They are searchable immediately but are not yet part of the optimized HNSW index. Searches during this window combine an exact scan of the buffer with HNSW traversal of the indexed segments.

Index build (optimization): When the buffer reaches a threshold (configurable), the system triggers an optimization pass: builds or extends the HNSW index on disk, potentially compacts multiple small segments into a larger indexed segment. This process runs asynchronously and is CPU and memory intensive.

Persistence: The final indexed segment is memory-mapped from disk. The HNSW graph and the raw vectors are stored together in the segment file. Memory mapping lets the OS page in only the portions needed for a query, which is important when the index is larger than RAM.

The implication for applications: inserts are low-latency (WAL write + buffer), but index optimization is async. Under heavy write load, optimization can fall behind, increasing the fraction of vectors in un-indexed buffers and degrading query latency.

The Query Path: Vector to Top-K Results

A query arrives as a vector and a set of parameters (topK, ef_search, filter, score threshold). The execution path:

1. Decode and validate the query vector.
2. Identify segments to search: all active indexed segments plus any un-indexed buffers.
3. Execute HNSW search on each indexed segment in parallel: traverse the graph using the entry point for that segment, maintaining a candidate heap of size ef_search.
4. Execute exact scan on un-indexed buffers.
5. Apply metadata filter either during traversal (pre-filter) or after (post-filter), per the system’s strategy.
6. Merge and rank results across all segments: take the top K by score from the combined candidate sets.
7. Fetch payloads if requested and return.

The query path is read-optimized: HNSW traversal is embarrassingly parallel across segments, and the graph is memory-mapped, so the OS cache does the heavy lifting for frequently accessed subgraphs.

System Comparison

Dimension	Pinecone	Weaviate	Qdrant	pgvector	Milvus
Deployment	Managed only	Self-hosted or managed	Self-hosted or managed (cloud beta)	Self-hosted (RDS, Supabase)	Self-hosted or managed
Index types	HNSW (proprietary)	HNSW	HNSW + IVF variants	HNSW, IVF-Flat, IVF-PQ	HNSW, IVF-Flat, IVF-PQ, DiskANN
Filtering	Good, pre-filter on namespace	Strong, native hybrid	Strong, adaptive pre/post	Good via SQL WHERE	Good, growing
Hybrid search	Not native (BM25 separate)	Native (BM25 + vector)	Native (sparse + dense)	Via pg_trgm or manual	Native (sparse + dense)
Scalability	Horizontal, opaque	Horizontal, complex config	Horizontal, explicit sharding	Limited (Postgres limits)	Built for billion-scale
Latency (p99, 1M vectors)	~10-30ms	~15-40ms	~5-20ms	~5-50ms (depends on ef)	~10-30ms
Memory model	Opaque	Loads index into RAM	Memory-mapped, configurable	Shared buffers + OS cache	Tiered (hot/warm/cold)
Cost (managed)	High ($0.096/hr per pod)	Moderate	Low (early-stage)	Lowest (if already on Postgres)	Moderate
Operational complexity	Low (fully managed)	Medium	Medium	Low (familiar Postgres ops)	High
Ecosystem	OpenAI, LangChain tight	LangChain, LlamaIndex	LangChain, LlamaIndex	Any Postgres client	LangChain, LlamaIndex

pgvector is the right choice when your dataset fits in Postgres (under ~5M vectors at 1536 dims without quantization), your team already operates Postgres, and you need strong transactional guarantees alongside vector search. The HNSW index type added in pgvector 0.5 significantly improved query latency, but Postgres’s MVCC overhead and lack of native quantization limit scalability.

Qdrant is the pragmatic self-hosted choice for teams that need control, predictable performance, and a well-documented API. Written in Rust, it has good memory efficiency and low operational overhead compared to Milvus.

Milvus targets billion-scale deployments where you need tiered storage (S3 for cold data, local NVMe for hot), multiple index types per collection, and cloud-native horizontal scaling. The operational complexity is real: Milvus has separate components for coordination, data nodes, query nodes, and index nodes.

Production Considerations

Recall vs. latency tuning. HNSW recall is not fixed at index creation. ef_search controls the recall/latency tradeoff at query time without rebuilding the index. Start with ef_search = max(ef_search_minimum, 2 * K) and measure recall against a ground-truth nearest-neighbor set computed offline. Raise ef_search until recall meets your requirement. For RAG applications, 95% recall is usually sufficient. For ranked retrieval where position matters, 98%+ is more appropriate.

Index build time and cost. Building an HNSW index over 10M vectors at 1536 dimensions takes 30-90 minutes on a 16-core machine, depending on M and ef_construction. This is a one-time cost for static datasets but a continuous cost under heavy write load (re-optimization of growing segments). If your dataset has a clear offline-batch component (nightly ingest of new documents), batch the inserts and trigger optimization after the batch rather than during continuous ingestion.

Quantization for memory reduction. Scalar quantization (SQ8) reduces each float32 to an int8, cutting memory to 25% of the original with minimal recall loss (typically 1-2% at comparable ef_search). Product quantization compresses further but with higher recall cost. Most production deployments of large corpora should start with SQ8: the memory savings often mean the entire index fits on a single node rather than requiring sharding, which eliminates network overhead on multi-segment merges.

Dimension reduction. Matryoshka Representation Learning (MRL) models (like OpenAI’s text-embedding-3 series) allow truncating embeddings to lower dimensions with a graceful recall degradation. Dropping from 1536 to 512 dimensions reduces memory and compute by 3x. Run an offline recall benchmark on your actual queries before committing to a reduced dimension in production, since the optimal truncation point is dataset-dependent.

Hybrid search (dense + sparse). Pure vector similarity misses keyword-critical queries. A search for a specific error code, a proper noun, or a version number performs poorly with dense embeddings because these tokens are not well-captured in learned semantic space. BM25-style sparse vectors capture exact term frequency information. Hybrid search combines both: the final score is a weighted sum of dense similarity and sparse BM25 score. Weaviate and Qdrant both support this natively. The weight parameter (often called alpha) controls the blend: alpha=1.0 is pure vector, alpha=0.0 is pure BM25, alpha=0.75 is a common starting point for RAG pipelines. Tune this against a query evaluation set, not intuitively.

Monitoring. Track p50/p95/p99 query latency, ANN recall (via sampled ground-truth comparisons), segment count (high segment count indicates optimization is falling behind writes), and index memory usage. Latency spikes that correlate with high segment counts usually indicate a need to tune write throughput or trigger optimization more aggressively.

A vector database is not a black box that “does similarity search.” It is a system with specific knobs that control a recall/latency/memory triangle. The defaults ship your prototype. Understanding HNSW graph structure, quantization tradeoffs, and filter execution strategies is what ships your production system.