How vector databases work: HNSW graphs, embeddings, and approximate nearest neighbors

Traditional relational databases use B-Tree indexes to sort and find structured data (like numbers, strings, and foreign keys) in logarithmic O(log N) time.

However, when building Retrieval-Augmented Generation (RAG) pipelines or multimodal search systems, modern AI applications work with high-dimensional dense vectors (e.g. 1,536-dimensional embedding vectors generated by models like OpenAI text-embedding-3).

Because B-Trees and standard indexes cannot order multidimensional vector space, traditional databases must perform an O(N) sequential table scan—calculating exact dot product distances across every single row.

BRUTE FORCE SCAN (Exact KNN):
Query Vector ➔ Calculate Distance to Row 1, Row 2, ... Row 1,000,000
Complexity: O(N * D) ➔ 1.5 Billion calculations ➔ 2,000ms+ latency (Unusable)

HNSW GRAPH INDEX (Approximate Nearest Neighbors - ANN):
Query Vector ➔ High-speed expressway jumps ➔ Zoom in on local neighborhood
Complexity: O(log N) ➔ Evaluates only ~100 candidate vectors ➔ Sub-10ms latency

---

1. What is an Embedding Vector?

An embedding model maps unstructured concepts (sentences, code snippets, user profiles, or images) into a continuous geometric coordinate space where semantic similarity corresponds to geometric proximity:

• vector("How do I fix memory leaks in Node.js?")
• vector("Debugging V8 garbage collector heap dumps")

Even though these two sentences share zero identical keywords, their 1,536-dimensional coordinates will point in almost the exact same angular direction (high cosine similarity).

---

2. The HNSW Graph Architecture

Hierarchical Navigable Small World (HNSW) is the gold standard indexing algorithm used by modern vector databases (including Pinecone, Qdrant, Milvus, and PostgreSQL’s pgvector).

Inspired by multi-layer skip lists and “six degrees of separation” social networks, HNSW constructs a multi-layered graph:

Layer 2 (Expressway - Top):
[Node A] ──────────────────────────────────────────▶ [Node Z]
   │                                                    │
Layer 1 (Arterial Roads - Mid):                         │
[Node A] ─────────────▶ [Node M] ──────────────────▶ [Node Z]
   │                       │                            │
Layer 0 (Local Streets - Bottom):                       │
[Node A] ──▶ [B] ──▶ [C] ─▶ [M] ──▶ [P] ──▶ [Q] ──▶ [Node Z]
(Contains 100% of all indexed vectors)

Search Execution Flow:

1. Top-Layer Entry: The query vector enters the top layer (Layer 2) at a pre-defined entry point.
2. Greedy Traversal: The algorithm jumps between nodes that have the highest cosine similarity to the query until it finds the local minimum for that layer.
3. Layer Dropdown: It drops to the next layer below (Layer 1) using the nearest node as the new starting point.
4. Bottom Layer Refinement: In Layer 0, it explores the immediate dense neighborhood to return the top-K nearest neighbors.

---

3. Production Trade-offs: Exact KNN vs. ANN

Dimension	Exact k-Nearest Neighbors (KNN)	HNSW Approximate (ANN)
Search Time	O(N) (Scales linearly with database size)	O(log N) (Sub-10ms for 10M+ vectors)
Recall Accuracy	100% exact mathematical match	95% – 99% recall (tuneable via ef_search)
Memory Footprint	Low (only stores raw vectors)	Higher (stores graph edges in RAM)
Build Index Time	Zero (no index required)	Moderate (indexes on background write)

---

4. Production Architectural Guidance

1. When to use pgvector: If your application already uses PostgreSQL and holds fewer than 500,000 vectors, using pgvector with an hnsw index (CREATE INDEX ON items USING hnsw (embedding vector_cosine_ops)) eliminates the operational complexity of managing a separate database.
2. When to use Dedicated Vector DBs: When scaling beyond 10 million vectors, requiring real-time sub-second filtering with high-concurrency QPS, use dedicated distributed vector engines like Qdrant or Pinecone.
3. Tune ef_search: In production, increase hnsw.ef_search during query execution to balance latency (lower values) vs. recall accuracy (higher values).