vector-db

Vector Database Engine

A search engine that finds things by meaning rather than exact words, the way a librarian can hand you the right book from a vague description. It was built from the original research paper rather than a ready-made library, then tested on 17,000 pieces of text: its matches were at least as accurate as FAISS, the library professionals use, though FAISS answers each search 10 to 13 times faster.

HNSW Descent: how a search by meaning finds its match. It starts on a sparse top layer where a few long hops cover huge ground, then drops a level onto a denser map and hops again, closing in on the nearest matches instead of checking every item. Live and interactive: drag it to orbit, scroll or pinch to zoom. Open full screen

Recall vs queries-per-second tradeoff curve from a real HNSW benchmark sweep of vector-db, compared to brute-force search. — 17K vectors, 768-dim: recall climbs toward 1.0 as ef_search increases, trading off throughput.

0.9997recall@10 at efSearch 320

matches FAISSrecall at matched params

17,000vectors indexed (768-dim)

View code on GitHub All projects

Overview

A vector database engine written from scratch in Python, built around an HNSW index implemented directly from the paper rather than wrapping a library. Approximate nearest-neighbor search with configurable recall, exact brute-force ground truth, metadata-filtered kNN, crash-safe WAL persistence, and a small HTTP server.

The point is understanding, not beating C. The graph construction, greedy search, neighbor-selection heuristic, and level generation are all hand-written; numpy is used only for vectorized distance math, and FAISS appears in one place, the benchmark, purely as a reference.

HNSW is the interesting part: a layered small-world graph you navigate greedily in roughly O(log n) hops. Getting recall above 0.95 on real embeddings, making deletes and persistence correct, and measuring honestly against a C library is where the understanding lands.

Key features

An HNSW index from scratch: a multi-layer graph, probabilistic level assignment, greedy per-layer search, the Algorithm-4 neighbor-selection heuristic with keep_pruned_connections, and configurable M, efConstruction, and efSearch across L2, cosine, and inner-product metrics.
A flat brute-force index for exact recall ground truth.
Soft delete with tombstones and a compact() rebuild.
Crash-safe persistence: a binary snapshot plus an fsync'd write-ahead log, verified by a test that kills a real subprocess mid-batch.
Metadata and filtered kNN with both pre-filter (exact) and post-filter (approximate) strategies, both tested.
A FastAPI server with a Python client.

Benchmark

18,000 real 20-Newsgroups embeddings (text-embedding-005, 768-dim), 17,000 indexed and 1,000 held out. M = 16, efConstruction = 200, k = 10, efSearch swept.

Recall vs FAISS

efSearch	ours recall@10	ours p50 ms	FAISS recall@10
10	0.9473	1.67	0.9038
40	0.9938	3.73	0.9886
80	0.9980	5.38	0.9970
160	0.9994	10.73	0.9987
320	0.9997	17.97	0.9991

What the numbers say

At every matched efSearch our recall is at least as high as FAISS, which confirms the graph and search are implemented correctly. FAISS is roughly 10 to 13x faster per query and builds the index in seconds rather than about 20 minutes, because it is optimized C with SIMD and this is CPython with per-node numpy calls. That gap is expected and is the whole reason libraries like FAISS exist.

Tech stack

Python 3.12
numpy
FastAPI
HNSW from the paper
faiss-cpu (benchmark only)
pytest

Challenges

Neighbor heuristic vs plain top-M: the first graph kept the M nearest candidates and recall stalled around 0.7; implementing Algorithm 4 (keep a candidate only if it is closer to the base than to any already-selected neighbor) pushed recall past 0.95.
Crash recovery needed config separate from the snapshot: a WAL-only directory could not reconstruct the index, so config.json is persisted durably at collection creation.
Vertex token limits on real text blew the 20,000-token cap on one 36,610-token batch; token-budgeted batching kept every request under the cap.
Python insert speed is dominated by many tiny numpy calls; batching helped, but a from-scratch Python HNSW is still far slower to build than FAISS, and that is reported rather than hidden.

What I learned

The layer stack is a skip-list for geometry: sparse top layers give long-range hops, the dense bottom layer does local search, and the neighbor heuristic keeps links diverse enough to navigate.
Squared L2 and normalized-vector cosine share one distance code path, removing a sqrt and a division from the hot loop.
efSearch is a pure recall/latency dial you can turn after the index is built; efConstruction is a build-time quality dial you cannot.
Durability is about ordering: fsync the WAL record before applying the operation, and frame each record with a length and a CRC so a torn tail fails its check.