LLMs and Generative AI › Embeddings and Vector Search › Day 262
Hands-on lab — Day 262: Vector Databases
- ← Back to the Day 262 lesson
- Open the hands-on files on GitHub — clone or download them from the public labs repository
- Local path in your clone:
labs/sections/llms-and-generative-ai/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
efSearchto 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
- Verify nodes establish bidirectional graph links.
- Confirm greedy search discovers top nearest neighbors.
- Validate higher efSearch improves candidate exploration.
- 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
- Implement a 2-layer HNSW graph with an upper sparse skip layer.
- Measure Recall@5 vs efSearch on 1,000 synthetic vectors.
Navigation
- 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-databaseswhen 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
- 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.