Skip to content

Vector Databases#

Problem statement (interviewer prompt)

A system must search across millions of documents by semantic similarity, not keyword. Each document is encoded as a 768- or 1536-dimensional embedding. Design the storage and index layer that returns the top-K most similar vectors with sub-100ms p99 latency.

A vector database stores high-dimensional embeddings and supports approximate nearest neighbour (ANN) queries. The index trades a small amount of recall for orders-of-magnitude faster search than brute-force O(N×d) cosine similarity.

flowchart LR
  Q([Query text]) --> Enc[Encoder model] --> Vec[1536-d query vector]
  Vec --> Idx[ANN index<br/>HNSW / IVF / ScaNN]
  Idx --> TopK[Top-K candidate ids]
  TopK --> Meta[(Doc store<br/>id → text + metadata)]
  Meta --> R([Ranked results])

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    class Q,R client;
    class Enc,Idx service;
    class Meta datastore;

Powers semantic search, RAG (retrieval-augmented generation), recommendation, deduplication, and visual similarity. Pinecone, Weaviate, Milvus, Qdrant, and pgvector are common implementations.

A vector database is a specialized store for dense embeddings generated by encoder models (text, image, audio). Its main job: given a query vector, return the K most similar vectors fast.

Why not just SQL?#

Brute-force similarity over N vectors of dimension d is O(N·d). For 10M vectors at d=1536 with cosine distance, a single query is ~15B float ops. ANN indexes drop that to O(log N) or O(sqrt(N)) at >95% recall.

Index families#

HNSW (Hierarchical Navigable Small World)#

flowchart TB
  subgraph L2[Layer 2: long-range]
    A((A)) --- B((B))
  end
  subgraph L1[Layer 1]
    A1((A)) --- C((C)) --- B1((B)) --- D((D))
  end
  subgraph L0[Layer 0: all nodes, dense graph]
    direction LR
    a1((A)) --- c1((C)) --- d1((D)) --- e1((E)) --- f1((F))
    a1 --- e1
    c1 --- f1
    b1((B)) --- d1
  end
  L2 --> L1 --> L0

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
  • Multilayer graph; greedy traversal from top to bottom.
  • High recall (>95%), low latency, supports incremental insert.
  • Memory-heavy: ~1.5x raw vector size.
  • Used in Weaviate, Qdrant, Milvus, pgvector (recently).

IVF (Inverted File)#

  1. Cluster all vectors into K Voronoi cells via k-means.
  2. At query time, probe nprobe nearest cells.

  3. Compare query to vectors in those cells only.

  4. Trade nprobe for recall vs latency.

  5. Lower memory than HNSW; better for billions of vectors.
  6. Often combined with product quantization (PQ) for compression: IVF-PQ.

Others#

  • ScaNN (Google): asymmetric quantization, optimized for TPU/GPU inference.
  • Annoy (Spotify): trees of random projections; build once, query forever.
  • DiskANN (Microsoft): NVMe-backed for billion-scale at modest RAM cost.

Distance metrics#

Metric Use
Cosine similarity Text embeddings (OpenAI, BERT); normalized vectors
Inner product (dot) Models that bake magnitude into similarity
L2 / Euclidean Image embeddings, visual search
Hamming Binary embeddings (compact, fast on bitwise CPU)

Filtered ANN#

Real queries combine vector similarity with structured filters: "top-10 most similar docs where tenant_id=X and date>2024-01-01".

Implementations: - Pre-filter (filter then ANN): cheap when selectivity is high. - Post-filter (ANN then filter): cheap when selectivity is low. - Hybrid: build per-shard indexes by tenant; query only matching shards.

Hybrid search (BM25 + vectors)#

flowchart TB
  Q([Query]) --> Spl[Split]
  Spl --> BM25[BM25 keyword]
  Spl --> Vec[Vector ANN]
  BM25 --> Merge[Reciprocal rank fusion]
  Vec --> Merge
  Merge --> Out([Top-K])

    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    class Spl,BM25,Vec,Merge service;

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;

Keyword search handles exact matches (acronyms, codes); vector search handles paraphrases. RRF (reciprocal rank fusion) blends the two scores.

Architecture at scale#

flowchart TB
  Client --> R[Router]
  R --> S1[Shard 1<br/>HNSW index<br/>tenants A-F]
  R --> S2[Shard 2<br/>tenants G-M]
  R --> S3[Shard 3<br/>tenants N-Z]
  S1 --> D1[(Vector + metadata)]
  S2 --> D2[(Vector + metadata)]
  S3 --> D3[(Vector + metadata)]
  Upload --> Enc[Embedding service<br/>OpenAI / cohere / local] --> S1

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    class Client,Upload client;
    class R edge;
    class S1,S2,S3,Enc service;
    class D1,D2,D3 datastore;
  • Shard by tenant or topic: filtered ANN stays cheap.
  • Replicate read paths: graph indexes are read-optimized.
  • Async upserts: insert into write-ahead log; rebuild index segment.

RAG retrieval pattern#

  1. User asks question → encode to vector.
  2. ANN top-K most relevant chunks.
  3. Optional re-rank with cross-encoder (slower, more accurate on small set).
  4. Prompt LLM with context: "Given these chunks, answer ...".

Trade-offs#

Pros Cons
Semantic understanding Index build is expensive
Sub-100ms queries at millions of vectors Recall < 100% (approximate)
Drop-in for recommendation, search Embedding model = part of contract

How vector DBs compose#

flowchart TB
  VEC((Vector DB))
  SRCH[Search internals<br/>BM25 keyword half of hybrid]
  RAG[Vector search / RAG<br/>top consumer]
  REC[Recommendation system<br/>embedding ANN lookup]
  GEO[Geo indexing<br/>spatial cousin of ANN]
  VEC --> RAG
  VEC --> REC
  SRCH -. hybrid fusion .-> VEC
  GEO -. analogue .- VEC

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class VEC service;
    class SRCH,RAG,REC,GEO datastore;

Glossary & fundamentals#

Tag Concept What it is Page
HLD Search internals inverted-index keyword sibling search-internals
HLD Database sharding shard vectors by tenant database-sharding
HLD Recommendation system top consumer of vector search recommendation-system
HLD Geo indexing spatial sibling of ANN geo-indexing

Quick reference#

Why#

Brute-force similarity is O(N·d); ANN indexes give sub-100ms recall>95%.

Index families#

Index Memory Recall Use
HNSW High (1.5×) 95-99% Millions of vectors, low latency
IVF Medium 90-95% Billions; tune nprobe
IVF-PQ Low 80-90% Cost-sensitive at scale
DiskANN Very low RAM, NVMe 90%+ Billion-scale on a box
ScaNN Medium 95% Google-scale, TPU-friendly

Distance metrics#

  • Cosine - text (normalized)
  • Inner product - magnitude-aware
  • L2 - image, visual
  • Hamming - binary embeddings

Filtered ANN#

  • Pre-filter (high selectivity)
  • Post-filter (low selectivity)
  • Per-tenant index shards (best)

Hybrid search (BM25 + vector)#

  1. Run both
  2. Merge via Reciprocal Rank Fusion (RRF)

RAG pattern#

  1. Encode question
  2. ANN top-K chunks
  3. (Optional) re-rank with cross-encoder
  4. Stuff into LLM prompt

Common DBs#

Pinecone, Weaviate, Milvus, Qdrant, pgvector, Vespa, Elastic dense_vector.

Watch-outs#

  • Embedding model is part of the contract; switching requires reindex
  • Re-rankers improve top-10 dramatically over raw ANN
  • Cosine vs dot must match how the model was trained

Refs#

  • Malkov & Yashunin - HNSW (2016)
  • Pinecone learn series
  • pgvector docs

FAQ#

What is a vector database?#

A database optimized for storing high-dimensional embeddings and answering nearest-neighbor queries quickly, used for semantic search, recommendations, and retrieval-augmented generation.

What is the difference between HNSW and IVF?#

HNSW builds a navigable graph of vectors and gives high recall with low query latency. IVF clusters vectors and searches only nearby clusters; it scales to huge corpora but uses more memory per query.

When should I use approximate vs exact nearest neighbor?#

Exact search is fine up to a few hundred thousand vectors. Beyond that, approximate algorithms like HNSW, IVF, or ScaNN trade a small recall loss for orders-of-magnitude speedup.

Do I need a dedicated vector database?#

Not always. Postgres pgvector or Elasticsearch knn handle moderate sizes. Dedicated systems like Pinecone, Milvus, or Weaviate help when you need horizontal scale, isolation, and richer filtering.

How are vector databases used in RAG?#

Documents are chunked and embedded into vectors. At query time, the user question is embedded and the top-K nearest chunks are retrieved and stuffed into the LLM prompt as context.

Further reading#