LLMs and Generative AI β€Ί Embeddings and Vector Search β€Ί Day 262

Day 262: Vector Databases

Day 262 of 365 β€” Vector Databases

Master Approximate Nearest Neighbor (ANN) indexing structures and modern vector database architectures: understand Hierarchical Navigable Small World (HNSW) graphs, Inverted File Index with Product Quantization (IVF-PQ), Locality-Sensitive Hashing (LSH), evaluate purpose-built engines (Qdrant, Chroma, Milvus, Pinecone, pgvector), analyze recall vs. QPS trade-offs, and build an in-memory graph-based ANN vector index in Python.

Course
LLMs and Generative AI
Category
Embeddings and Vector Search
Reading time
β‰ˆ 35 min
Practical time
β‰ˆ 50 min
Lesson duration
1h 25m
Last verified
2026-08-30

Hands-on lab for this lesson

Lab files on GitHub: https://github.com/ai-roadmap-365/ai-roadmap-365.github.io/tree/main/labs/sections/llms-and-generative-ai/day-262-vector-databases

  1. Get the hands-on files. Clone the labs repository once (you can reuse this clone for every lesson). This works on macOS, Linux, and Windows (PowerShell or WSL):
    git clone https://github.com/ai-roadmap-365/ai-roadmap-365.github.io.git
    cd ai-roadmap-365.github.io
  2. Open this lesson's lab. Move into the directory for this specific day. Every lab lives at the same predictable path β€” section / subsection / week / day:
    cd labs/sections/llms-and-generative-ai/day-262-vector-databases
  3. Read the lab guide. Open `README.md` in that directory. It lists the exact commands, what each does, the expected output, and how to check your work β€” read it before running anything.
  4. Run it and check your work. Follow the README's "How to run" section: run the example first to see the finished result, then complete the numbered exercises in `starter/`, then run the tests. The tests pass (exit 0) only when your work is correct.
    bash tests/run_tests.sh   # or the test command named in the lab README

You can also open the lab as a local page (works offline, shows the file tree and expected output).

Learning objectives

By the end of this lesson you will be able to:

Prerequisites

Why this matters

When your AI application grows from a prototype with 1,000 markdown notes to an enterprise knowledge engine with 10,000,000 documents, multi-tenant security partitions, and 500 concurrent queries per second, flat linear scans fail:

Vector Databases are purpose-built data engines designed to solve high-scale semantic retrieval. They combine Approximate Nearest Neighbor (ANN) graph indexes (HNSW), vector quantization compression (IVF-PQ), ACID persistence, and hardware-accelerated payload filtering to deliver sub-5ms responses at billion-scale.

Today, you will master the internal architecture of Hierarchical Navigable Small World (HNSW) graphs, analyze Inverted File Product Quantization (IVF-PQ), compare dedicated vector engines (Qdrant, Pinecone, Milvus, Chroma) against relational extensions (pgvector), and build a graph-based Navigable Small World (NSW) vector index in Python.


The idea in plain language

Diagram: the four capabilities a vector database provides beyond raw similarity search

Think of searching for a specific friend in a massive international airport containing 100,000 travelers:

By organizing vectors into multi-layer geometric graphs, vector databases skip 99.9% of unpromising vectors and navigate straight to the nearest conceptual cluster in milliseconds.


Historical background

Diagram: the historical progression of vector search infrastructure

HNSW graph layered navigation architecture diagram

  1. 2000s (Locality-Sensitive Hashing - LSH): Indyk and Motwani introduced LSH, hashing nearby vectors into identical buckets with probabilistic collision bounds.
  2. 2011 (Product Quantization - PQ): HervΓ© JΓ©gou published Product Quantization, enabling 64x memory compression and fast table-lookup distance arithmetic.
  3. 2016–2018 (HNSW Graphs): Yury Malkov and Dmitry Yashunin introduced HNSW, surpassing all previous ANN algorithms and becoming the industry standard.
  4. 2021–2023 (The Vector DB Boom): Specialized vector databases (Pinecone, Qdrant, Milvus, Weaviate, Chroma) emerged alongside pgvector to power enterprise generative AI and RAG architectures.

What it is β€” and what it is not

What a Vector Database IS:

What it is NOT:


Why it was created and what problems it solves

Vector databases address 4 critical production bottlenecks:

  1. Logarithmic Retrieval Speed: Scales to billions of items with sub-10ms latency using O(\log N) graph traversals.
  2. Hybrid Payload Filtering: Combines semantic similarity with strict SQL-like boolean constraints (e.g. tenant_id == 'corp_42' AND created_at >= 2024-01-01).
  3. Memory & Disk Tiering: Uses vector quantization (PQ/SQ) and memory-mapped files to store terabytes of vectors on cost-effective SSDs instead of expensive RAM.
  4. Horizontal Distributed Sharding: Partitions vector collections across multiple server nodes for fault tolerance and high query throughput.

How it works

Let us dissect HNSW graph indexing, IVF-PQ quantization, and engine architectures.


1. HNSW Graph Architecture & Hyperparameters

Diagram: how a layered proximity graph finds nearest neighbours without scanning everything

β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚                      HNSW SEARCH TRAVERSAL LIFECYCLE                   β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ 1. Enter at Top Layer (Layer L) at global entry node.                  β”‚
β”‚ 2. Perform greedy routing: hop to neighbor closest to query.           β”‚
β”‚ 3. When local minimum reached, drop down to Layer L-1.                 β”‚
β”‚ 4. Repeat greedy routing until reaching Layer 0 (Base Layer).          β”‚
β”‚ 5. Perform bounded beam search with efSearch candidates.               β”‚
β”‚ 6. Extract Top-K closest items from candidate priority queue.          β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

2. IVF-PQ (Inverted File Index with Product Quantization)

IVF-PQ vector quantization clustering diagram

For massive collections (100M+ vectors) where RAM is constrained:

  1. IVF (Inverted File Partitioning): K-Means clusters the space into C Voronoi cells (e.g. 4,096 centroids).
    • During search, the engine checks only the nprobe closest centroids (e.g. nprobe = 16), ignoring 99.6% of the dataset.
  2. Product Quantization (PQ): Decomposes a 1536d vector into m = 96 sub-vectors of 16 dimensions each.
    • Each sub-vector is replaced by a single 8-bit byte representing its nearest centroid codebook ID.
    • Result: Slashes vector storage from 6,144 bytes down to 96 bytes (64x reduction).

3. Dedicated Vector DBs vs. Relational Extensions (pgvector)

Diagram: a dedicated vector database compared with a vector extension to an existing database

β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚                   DEDICATED VECTOR DB VS PGVECTOR                      β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Feature            β”‚ Dedicated (Qdrant / Milvus) β”‚ Relational (pgvector)β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Max Scale          β”‚ 100M - 10 Billion+ vectors  β”‚ 1M - 10M vectors    β”‚
β”‚ Implementation     β”‚ Custom C++ / Rust HNSW      β”‚ Postgres C Extensionβ”‚
β”‚ Infrastructure     β”‚ Separate microservice       β”‚ Existing PostgreSQL β”‚
β”‚ ACID & Joins       β”‚ Limited / External sync     β”‚ Native SQL Joins    β”‚
β”‚ Memory Efficiency  β”‚ Advanced PQ / Disk tiering  β”‚ High RAM requirementβ”‚
β”‚ Best Use Case      β”‚ Dedicated search platform   β”‚ Standard web apps   β”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

4. Payload Filtering Strategies: Pre-Filter vs. Single-Stage Filter

Diagram: how metadata filtering interacts with approximate nearest neighbour search

When filtering by metadata:


5. Memory-Mapped Disk Storage (MMap) & NVMe SSDs

To avoid storing billion-vector graphs entirely in RAM:


6. Tuning Recall vs. QPS on Production Clusters

Diagram: high-recall index settings compared with high-throughput settings

When operating HNSW in production:


7. Sharding, Replication, and Raft Consensus

High-availability vector databases (such as Qdrant and Milvus) utilize the Raft consensus algorithm:


8. Dynamic Upserts, Deletions, and Soft Tombstoning

Diagram: how deletions are handled in an approximate nearest neighbour index

In dynamic applications, knowledge documents are continuously updated and deleted:


9. Multi-Tenancy Architecture: Namespace Isolation vs. Metadata Partitions

When building multi-tenant SaaS applications:


10. Summary: The Storage Pillar of AI Infrastructure


An everyday analogy

Diagram: searching every shelf compared with using an organised catalogue

Think of finding a book in the world’s largest library:


Examples in practice

Let us build an In-Memory Navigable Small World (NSW) Graph Index:

import numpy as np
import heapq
from typing import List, Dict, Any, Tuple, Set

class SimpleNSWIndex:
    def __init__(self, dimension: int, max_neighbors: int = 4):
        self.dimension = dimension
        self.max_neighbors = max_neighbors
        self.vectors: List[np.ndarray] = []
        self.metadata: List[Dict[str, Any]] = []
        self.graph: Dict[int, List[int]] = {}
        self.entry_node: int = 0

    def add_document(self, vector: np.ndarray, meta: Dict[str, Any]) -> int:
        norm = np.linalg.norm(vector)
        unit_vec = vector / (norm if norm > 0 else 1.0)
        node_id = len(self.vectors)
        self.vectors.append(unit_vec)
        self.metadata.append(meta)
        self.graph[node_id] = []

        if node_id == 0:
            self.entry_node = 0
            return node_id

        # Find closest existing nodes to establish bidirectional links
        closest = self.search(unit_vec, top_k=self.max_neighbors)
        for target_meta, _ in closest:
            target_id = target_meta["id"]
            self.graph[node_id].append(target_id)
            if len(self.graph[target_id]) < self.max_neighbors * 2:
                self.graph[target_id].append(node_id)
        return node_id

    def search(self, query_vec: np.ndarray, top_k: int = 3, ef_search: int = 10) -> List[Tuple[Dict[str, Any], float]]:
        if not self.vectors:
            return []
        
        q_norm = np.linalg.norm(query_vec)
        q_unit = query_vec / (q_norm if q_norm > 0 else 1.0)

        # Greedy graph search with priority queue
        visited: Set[int] = {self.entry_node}
        candidates = [(-float(np.dot(self.vectors[self.entry_node], q_unit)), self.entry_node)]
        best_results = [(-candidates[0][0], self.entry_node)] # (sim, id)

        while candidates:
            dist, curr = heapq.heappop(candidates)
            curr_sim = -dist
            if curr_sim < best_results[-1][0] and len(best_results) >= ef_search:
                break
            
            for neighbor in self.graph.get(curr, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    sim = float(np.dot(self.vectors[neighbor], q_unit))
                    if len(best_results) < ef_search or sim > best_results[-1][0]:
                        heapq.heappush(candidates, (-sim, neighbor))
                        best_results.append((sim, neighbor))
                        best_results.sort(key=lambda x: x[0], reverse=True)
                        if len(best_results) > ef_search:
                            best_results.pop()

        return [(self.metadata[node_id], sim) for sim, node_id in best_results[:top_k]]

Implications: security, privacy, performance, scalability, and cost

Diagram: the cost, tuning, access-control and drift implications of a vector database

  1. Multi-Tenant Security:
    • Always enforce strict namespace or metadata filter checks at the database query boundary to ensure tenant A cannot retrieve embedding vectors belonging to tenant B.
  2. Cost Optimization:
    • Storing 100M uncompressed vectors in memory on AWS requires r6i.32xlarge instances (8,000+/month). Applying IVF-PQ compression reduces memory requirements by 85%, reducing hosting costs to under800/month.

Alternatives: free, open source, and commercial

DatabaseArchitecturePrimary LanguageIndex TypesBest For
QdrantStandalone EngineRustHNSW + Payload IndexProduction high-scale RAG
MilvusDistributed ClusterGo / C++HNSW, IVF-PQ, DiskANNMassive enterprise deployments
PineconeManaged Cloud SaaSProprietaryServerless Vector GraphZero-maintenance cloud apps
pgvectorPostgreSQL ExtensionCHNSW, IVFFlatMonolithic Postgres apps
ChromaEmbedded / ServerPython / RustHNSWPrototyping & local testing

β”Œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”
β”‚                   HNSW VS IVF-PQ VS FLAT INDEX                         β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”¬β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Metric             β”‚ Flat Linear     β”‚ HNSW Graph       β”‚ IVF-PQ       β”‚
β”œβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”Όβ”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€
β”‚ Query Speed        β”‚ Slow (O(N))     β”‚ Ultra-Fast (O(log N))β”‚ Very Fast β”‚
β”‚ Index Memory       β”‚ 1.0x (Baseline) β”‚ 1.5x - 2.0x (RAM)β”‚ 0.05x - 0.15xβ”‚
β”‚ Recall Accuracy    β”‚ 100% Exact      β”‚ 98% - 99.9%      β”‚ 90% - 96%    β”‚
β”‚ Build Speed        β”‚ Instant (0ms)   β”‚ Moderate         β”‚ Requires Trainβ”‚
β””β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”΄β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”€β”˜

When to use it β€” and when not to

Diagram: when a dedicated vector database is warranted

When to Use a Vector Database:

When NOT to use:


The AI connection

Knowledge check

  1. What is the fundamental difference between HNSW graph search and IVF-PQ space partitioning?
  2. What are the roles of the M, efConstruction, and efSearch parameters in HNSW?
  3. How does Product Quantization compress a 1536-dimensional float vector into 96 bytes?
  4. When should you choose pgvector over a dedicated vector engine like Qdrant?
  5. Why is single-stage metadata filtering in HNSW superior to naive post-filtering?

Hands-on exercise

In this lab, you will build and test an In-Memory Navigable Small World (NSW) Vector Index: implement graph node insertion, bidirectional neighbor linking, greedy logarithmic search traversal with priority queues, evaluate recall against exact flat k-NN ground truth, and measure search latency.

Expected output

[Vector Databases Verification Suite]
Testing NSW Graph Index Construction:
  Indexed 500 documents (dim=64, max_neighbors=4) [PASS]
  Graph connectivity verified: All nodes reachable [PASS]
Testing Graph Traversal vs Exact k-NN:
  Exact Ground Truth Match: 100% Top-3 Recall [PASS]
  Average Query Traversal Steps: 8.4 steps [PASS]
Testing efSearch Parameter Tuning:
  efSearch=5 -> Recall: 0.94
  efSearch=15 -> Recall: 1.00 [PASS]
Test Suite: 4 passed in 0.48s

Validate your work

Run the automated test runner:

./tests/run_tests.sh

Troubleshooting

Common mistakes


Practice assignment

  1. Implement HNSW Layered Insertion: Extend the single-layer NSW graph into a 2-layer HNSW graph with an upper sparse expressway layer.
  2. Measure the Recall@5 vs. efSearch Curve across 2,000 synthetic 128-dimensional vectors.

Extension challenge

Implement a Single-Stage Filtered NSW Search Engine:

Quiz

Q1. What is the primary operational trade-off of Approximate Nearest Neighbor (ANN) indexes like HNSW compared to exact Flat k-NN?

  1. HNSW produces random incorrect results
  2. Far faster queries, at a small cost in recall
  3. HNSW requires converting text into video files
  4. HNSW only works on quantum computers
Show answer

Answer: B. Far faster queries, at a small cost in recall

ANN trades a small percentage of recall accuracy for massive orders-of-magnitude query speedups.

Q2. In the HNSW algorithm, what role do the upper sparse layers (e.g. Layer 2) serve?

  1. They delete older documents
  2. They store compressed audio files
  3. They are express lanes for long jumps across the space
  4. They encrypt user passwords
Show answer

Answer: C. They are express lanes for long jumps across the space

Upper layers provide sparse skip-list connectivity for rapid logarithmic space traversal.

Q3. What do the HNSW hyperparameters "M" and "efSearch" control?

  1. They are legacy parameters with zero effect
  2. M controls database password length, and efSearch controls port numbers
  3. M is the number of CPU cores, and efSearch is the RAM allocation
  4. M sets neighbour links; efSearch sets the candidate list
Show answer

Answer: D. M sets neighbour links; efSearch sets the candidate list

M governs graph connectivity and RAM usage; efSearch balances query latency versus recall accuracy.

Q4. How does Product Quantization (PQ) achieve up to 64x memory reduction on dense vectors?

  1. It splits the vector and stores each part's centroid id
  2. By deleting the last 50% of document text
  3. By converting floating-point vectors into ASCII characters
  4. By storing embeddings in Google Drive
Show answer

Answer: A. It splits the vector and stores each part's centroid id

PQ replaces multi-byte floating point arrays with compact 1-byte centroid cluster indices.

Q5. When is using PostgreSQL with the `pgvector` extension preferred over a standalone vector database like Pinecone or Qdrant?

  1. When you want to search billions of vectors across 100 GPU clusters
  2. When you already run Postgres and need joins and ACID
  3. When PostgreSQL is disabled
  4. Never; pgvector cannot store numbers
Show answer

Answer: B. When you already run Postgres and need joins and ACID

pgvector simplifies infrastructure by keeping relational entities and embeddings within a single ACID database.

Glossary

Approximate Nearest Neighbors (ANN)
A class of search algorithms that sacrifice 100% exactness to achieve logarithmic O(log N) retrieval speeds.
HNSW (Hierarchical Navigable Small World)
A state-of-the-art graph-based ANN algorithm featuring multi-layer skip-graph navigation.
IVF (Inverted File Index)
A space-partitioning index that assigns vectors to Voronoi cell clusters and searches only the nearest centroids.
Product Quantization (PQ)
A vector compression technique splitting vectors into sub-vectors and indexing them against centroid codebooks.
efSearch
An HNSW runtime parameter governing the size of the priority queue during search; higher values increase recall at higher latency.
nprobe
An IVF parameter determining how many Voronoi cell clusters to scan during a search query.
Payload / Metadata Filtering
Filtering vector search candidates using structured relational criteria (e.g. user_id, date, tag).
pgvector
An open-source PostgreSQL extension adding native vector types, exact distance operators, and HNSW/IVFFlat indexes.

Sources and further reading


Kept in this browser, no account needed. Your progress page turns the whole record into one link you can bookmark or open on another device.