LLMs and Generative AI › Embeddings and Vector Search › Day 262

Hands-on lab — Day 262: Vector Databases

Commands

Setup

pip install -r requirements/requirements.txt

Run

python3 examples/vector_databases_lib.py

Test

./tests/run_tests.sh

File tree

conftest.py
examples/test_vector_databases_lib.py
examples/vector_databases_lib.py
expected-output/examples-run.txt
expected-output/FIELDS.md
expected-output/measured-values.txt
expected-output/starter-run.txt
expected-output/test-run.txt
metadata.yml
README.md
requirements/requirements.txt
security.md
starter/test_vector_databases_lib.py
starter/vector_databases_lib.py
tests/run_tests.sh
tests/test_vector_databases_lib.py
troubleshooting.md

Lab README

Lab: Day 262 -- Vector Databases

Lesson

Day number: 262 of 365. Course: Course06-SS02 (LLMs and Generative AI - Retrieval and Customization). Topic: Vector Databases, Approximate Nearest Neighbors, HNSW, and IVF-PQ.

Purpose

Build and test an In-Memory Navigable Small World (NSW) Vector Index in Python. Implement graph-based vector insertion, bidirectional neighbor linking, greedy beam search traversal, and analyze efSearch recall tuning.

Learning objectives

  • Implement graph-based vector index insertion with bounded neighborhood connectivity.
  • Execute greedy logarithmic search traversal with priority candidate queues.
  • Tune efSearch to observe trade-offs between graph recall and traversal steps.
  • Compare NSW graph retrieval against flat linear scans.

Prerequisites

  • Day 261 (Semantic Similarity Search).
  • Python 3.11+ with NumPy and Pytest.

Supported operating systems

  • macOS (Apple Silicon / Intel)
  • Linux (Ubuntu, Debian, Fedora, Arch)
  • Windows 11 / WSL2

Hardware requirements

  • 1+ CPU cores.
  • 1 GB RAM.
  • 100 MB disk space.

Required software

  • Python 3.11 or newer.
  • pip package manager.
  • virtualenv or venv module.

Free and open-source options

NumPy and Python standard libraries are open source.

Installation

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements/requirements.txt

File structure

  • starter/vector_databases_lib.py: Student scaffold file.
  • examples/vector_databases_lib.py: Complete reference implementation.
  • tests/test_vector_databases_lib.py: Pytest automated validation suite.
  • expected-output/: Verified output logs and baseline values.

How to run

Execute the reference demonstration script:

python3 examples/vector_databases_lib.py

What the commands do

  • Builds in-memory NSW graph index.
  • Links vectors with bidirectional edges.
  • Executes greedy graph traversal search.
  • Runs unit test assertions.

Expected output

NSW Demo Executed. Top Match: Doc 0 with score 1.0000

Validation steps

  1. Verify nodes establish bidirectional graph links.
  2. Confirm greedy search discovers top nearest neighbors.
  3. Validate higher efSearch improves candidate exploration.
  4. Ensure all unit test assertions pass.

Tests

Run the test runner script:

./tests/run_tests.sh

Cleanup

find . -type d -name "__pycache__" -exec rm -rf {} +
find . -type d -name ".pytest_cache" -exec rm -rf {} +

Troubleshooting

  • Disconnected graph components: Ensure the entry node has valid outgoing connections to subsequent nodes.

Security notes

All computations execute locally in memory.

Extension exercises

  1. Implement a 2-layer HNSW graph with an upper sparse skip layer.
  2. Measure Recall@5 vs efSearch on 1,000 synthetic vectors.
  • Lesson title: Vector Databases
  • Day number: 262 of 365
  • Lesson article: https://ai-roadmap-365.github.io/day-262-vector-databases
  • Lab files: everything you need is in this directory — follow “How to run” below.
  • Browse the course locally: from the repository root, this lab also appears in the course website at /labs/day-262-vector-databases when the site is running.

Expected output

FIELDS.md

# Expected Output Fields: Day 262

- `NSW Demo`: Status of NSW graph search execution.

examples-run.txt

NSW Demo Executed. Top Match: Doc 0 with score 1.0000

measured-values.txt

NSW Demo: Success
Top Match: Doc 0
Score: 1.0000

starter-run.txt

Starter scaffold executed. Ready for student implementation.

test-run.txt

============================= test session starts ==============================
collected 4 items

tests/test_vector_databases_lib.py::test_nsw_index_basic_retrieval PASSED       [ 25%]
tests/test_vector_databases_lib.py::test_nsw_graph_connectivity PASSED          [ 50%]
tests/test_vector_databases_lib.py::test_empty_nsw_index PASSED                 [ 75%]
tests/test_vector_databases_lib.py::test_ef_search_recall_scaling PASSED        [100%]

============================== 4 passed in 0.38s ===============================

Source files

conftest.py (585 bytes)
"""Make this lab importable when the suite runs.

pytest puts the test file's own directory on sys.path, not the lab root, so a
test that does `from examples.<module> import ...` -- or imports a module that
lives in examples/ directly -- fails without this. Putting it here rather than
in run_tests.sh means a bare `pytest` from the lab root works too.
"""

import os
import sys

LAB = os.path.dirname(os.path.abspath(__file__))
for candidate in (LAB, os.path.join(LAB, "examples")):
    if os.path.isdir(candidate) and candidate not in sys.path:
        sys.path.insert(0, candidate)
examples/test_vector_databases_lib.py (1536 bytes)
import pytest
import numpy as np
from examples.vector_databases_lib import (
    SimpleNSWIndex
)

def test_nsw_index_basic_retrieval():
    index = SimpleNSWIndex(dimension=3, max_neighbors=3)
    v0 = np.array([1.0, 0.0, 0.0])
    v1 = np.array([0.95, 0.05, 0.0])
    v2 = np.array([0.0, 1.0, 0.0])
    index.add_document(v0, {"id": 0})
    index.add_document(v1, {"id": 1})
    index.add_document(v2, {"id": 2})

    query = np.array([1.0, 0.0, 0.0])
    results = index.search(query, top_k=2, ef_search=5)
    
    assert len(results) == 2
    assert results[0][0]["id"] == 0
    assert results[1][0]["id"] == 1

def test_nsw_graph_connectivity():
    index = SimpleNSWIndex(dimension=4, max_neighbors=3)
    for i in range(10):
        vec = np.random.randn(4)
        index.add_document(vec, {"id": i})

    # Assert all nodes are in graph
    for i in range(10):
        assert i in index.graph
        assert len(index.graph[i]) > 0 or i == 0

def test_empty_nsw_index():
    index = SimpleNSWIndex(dimension=4)
    query = np.array([1.0, 0.0, 0.0, 0.0])
    results = index.search(query, top_k=3)
    assert results == []

def test_ef_search_recall_scaling():
    index = SimpleNSWIndex(dimension=4, max_neighbors=4)
    for i in range(20):
        vec = np.random.randn(4)
        index.add_document(vec, {"id": i})

    query = np.random.randn(4)
    res_low = index.search(query, top_k=3, ef_search=3)
    res_high = index.search(query, top_k=3, ef_search=15)
    
    assert len(res_low) <= 3
    assert len(res_high) == 3
examples/vector_databases_lib.py (3373 bytes)
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, ef_search=max(self.max_neighbors, 8))
        for target_meta, _ in closest:
            target_id = target_meta["id"]
            if target_id not in self.graph[node_id]:
                self.graph[node_id].append(target_id)
            if len(self.graph[target_id]) < self.max_neighbors * 2 and node_id not in self.graph[target_id]:
                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)

        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)]

        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]]

def run_nsw_demo():
    index = SimpleNSWIndex(dimension=3, max_neighbors=2)
    v0 = np.array([1.0, 0.0, 0.0])
    v1 = np.array([0.9, 0.1, 0.0])
    v2 = np.array([0.0, 1.0, 0.0])
    index.add_document(v0, {"id": 0, "title": "Doc 0"})
    index.add_document(v1, {"id": 1, "title": "Doc 1"})
    index.add_document(v2, {"id": 2, "title": "Doc 2"})

    query = np.array([1.0, 0.0, 0.0])
    results = index.search(query, top_k=2)
    print(f"NSW Demo Executed. Top Match: {results[0][0]['title']} with score {results[0][1]:.4f}")
    return results

if __name__ == "__main__":
    run_nsw_demo()
metadata.yml (429 bytes)
lesson_id: D262
day: 262
kind: lab
languages:
  - python
setup_commands:
  - 'pip install -r requirements/requirements.txt'
run_commands:
  - 'python3 examples/vector_databases_lib.py'
test_commands:
  - './tests/run_tests.sh'
cleanup_commands:
  - 'find . -type d -name "__pycache__" -exec rm -rf {} +'
requires_network: false
requires_api_key: false
estimated_minutes: 45
last_executed: '2026-08-30'
executed_on: 'macos-arm64'
requirements/requirements.txt (41 bytes)
torch>=2.2.0
numpy>=1.26.0
pytest>=8.0.0
starter/test_vector_databases_lib.py (1536 bytes)
import pytest
import numpy as np
from examples.vector_databases_lib import (
    SimpleNSWIndex
)

def test_nsw_index_basic_retrieval():
    index = SimpleNSWIndex(dimension=3, max_neighbors=3)
    v0 = np.array([1.0, 0.0, 0.0])
    v1 = np.array([0.95, 0.05, 0.0])
    v2 = np.array([0.0, 1.0, 0.0])
    index.add_document(v0, {"id": 0})
    index.add_document(v1, {"id": 1})
    index.add_document(v2, {"id": 2})

    query = np.array([1.0, 0.0, 0.0])
    results = index.search(query, top_k=2, ef_search=5)
    
    assert len(results) == 2
    assert results[0][0]["id"] == 0
    assert results[1][0]["id"] == 1

def test_nsw_graph_connectivity():
    index = SimpleNSWIndex(dimension=4, max_neighbors=3)
    for i in range(10):
        vec = np.random.randn(4)
        index.add_document(vec, {"id": i})

    # Assert all nodes are in graph
    for i in range(10):
        assert i in index.graph
        assert len(index.graph[i]) > 0 or i == 0

def test_empty_nsw_index():
    index = SimpleNSWIndex(dimension=4)
    query = np.array([1.0, 0.0, 0.0, 0.0])
    results = index.search(query, top_k=3)
    assert results == []

def test_ef_search_recall_scaling():
    index = SimpleNSWIndex(dimension=4, max_neighbors=4)
    for i in range(20):
        vec = np.random.randn(4)
        index.add_document(vec, {"id": i})

    query = np.random.randn(4)
    res_low = index.search(query, top_k=3, ef_search=3)
    res_high = index.search(query, top_k=3, ef_search=15)
    
    assert len(res_low) <= 3
    assert len(res_high) == 3
starter/vector_databases_lib.py (569 bytes)
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):
        # TODO: Initialize NSW index
        pass

    def add_document(self, vector: np.ndarray, meta: Dict[str, Any]) -> int:
        # TODO: Add vector and connect to closest existing neighbors
        pass

    def search(self, query_vec: np.ndarray, top_k: int = 3, ef_search: int = 10) -> List[Tuple[Dict[str, Any], float]]:
        # TODO: Greedy graph traversal with priority queue
        pass
tests/run_tests.sh (227 bytes)
#!/usr/bin/env bash
set -euo pipefail
echo "========================================"
echo "Running Day 262 Lab Test Suite"
echo "========================================"
pytest tests/ -v
echo "All tests passed successfully."
tests/test_vector_databases_lib.py (1536 bytes)
import pytest
import numpy as np
from examples.vector_databases_lib import (
    SimpleNSWIndex
)

def test_nsw_index_basic_retrieval():
    index = SimpleNSWIndex(dimension=3, max_neighbors=3)
    v0 = np.array([1.0, 0.0, 0.0])
    v1 = np.array([0.95, 0.05, 0.0])
    v2 = np.array([0.0, 1.0, 0.0])
    index.add_document(v0, {"id": 0})
    index.add_document(v1, {"id": 1})
    index.add_document(v2, {"id": 2})

    query = np.array([1.0, 0.0, 0.0])
    results = index.search(query, top_k=2, ef_search=5)
    
    assert len(results) == 2
    assert results[0][0]["id"] == 0
    assert results[1][0]["id"] == 1

def test_nsw_graph_connectivity():
    index = SimpleNSWIndex(dimension=4, max_neighbors=3)
    for i in range(10):
        vec = np.random.randn(4)
        index.add_document(vec, {"id": i})

    # Assert all nodes are in graph
    for i in range(10):
        assert i in index.graph
        assert len(index.graph[i]) > 0 or i == 0

def test_empty_nsw_index():
    index = SimpleNSWIndex(dimension=4)
    query = np.array([1.0, 0.0, 0.0, 0.0])
    results = index.search(query, top_k=3)
    assert results == []

def test_ef_search_recall_scaling():
    index = SimpleNSWIndex(dimension=4, max_neighbors=4)
    for i in range(20):
        vec = np.random.randn(4)
        index.add_document(vec, {"id": i})

    query = np.random.randn(4)
    res_low = index.search(query, top_k=3, ef_search=3)
    res_high = index.search(query, top_k=3, ef_search=15)
    
    assert len(res_low) <= 3
    assert len(res_high) == 3

Troubleshooting

Troubleshooting: Day 262 - Vector Databases

Common Issues

  1. Empty search results:
    • Cause: Index has zero documents added before search.
    • Fix: Check len(self.vectors) > 0 before starting graph traversal.

Security notes

Security & Privacy: Day 262 - Vector Databases

Security Guidance

  • Isolate tenant data partitions to prevent cross-tenant vector extraction.