A vector database written from scratch in Python + Numba: hand-implemented HNSW
and product quantization, attribute-filtered search behind a cost-based query
planner, write-ahead-log durability that survives kill -9, a gRPC API, and a
learned early-termination model. Benchmarked against FAISS on SIFT1M (1M
vectors) and 300k MiniLM-embedded MS MARCO passages.
The engine contains no C/C++/Rust/Cython and no ANN libraries. Every hot path —
graph traversal, distance kernels, PQ scanning, tree-ensemble inference — is an
@njit Numba kernel over preallocated NumPy arrays. FAISS appears only in
bench/ as the baseline.
Measured on one machine (i5-13500HX, 14C/20T, 32 GB, Windows 11). Every number
is regenerated by one command from a config in configs/bench/ and rendered
into these tables by python -m bench.report.
| area | outcome |
|---|---|
| HNSW vs FAISS (SIFT1M) | 44.1k vs 56.6k QPS at recall@10 = 0.95 (16 threads); equal single-thread latency at matched ef; 1M-vector build in 46 s vs 55 s |
| Product quantization | vectors resident in RAM cut 488 → 15.4 MiB (31.7×) at ~95 % of full-precision throughput; recall up to 0.995 after exact re-rank |
| Filtered search | planner: 0.84 ms mean at recall 0.968 on a mixed-selectivity workload, where every fixed strategy either loses a third of the true results or costs 10× more |
| Durability | 100/100 kill -9 crash-recovery runs; 132,553 acknowledged records verified bit-for-bit |
| Learned early termination | negative result: 5–10 % faster on MS MARCO at high recall, slower on SIFT1M; the 25 % target was not met and the model ships disabled |
| engine | build (16 threads) | index RAM | QPS @ recall 0.95 | ef for 0.95 | 1-thread p50 / p99 @ ef=64 |
|---|---|---|---|---|---|
| vectra-hnsw | 46 s | 619 MiB | 44.1k | 96 | 134 / 165 µs |
| faiss-hnsw | 55 s | 626 MiB | 56.6k | 64 | 139 / 171 µs |
Search speed at equal ef matches FAISS; the gap at equal recall comes from
graph quality. FAISS grants each new node up to 2M layer-0 links at insert
time where Vectra grants M (the hnswlib convention), and Vectra's parallel
build does not link nodes inserted in the same batch.
| engine | index RAM | vectors held in RAM | QPS @ 0.90 | QPS @ 0.95 | best recall |
|---|---|---|---|---|---|
| vectra-hnsw | 619 MiB | float32 (488 MiB) | 68.4k | 43.9k | 0.994 |
| vectra-hnsw-pq | 146 MiB | 16-byte codes (15.4 MiB) | 65.3k | 40.9k | 0.995 |
| faiss-ivfpq | 25 MiB | 16-byte codes | n/a | n/a | 0.582 |
| faiss-ivfpq-refine | 513 MiB | float32 (488 MiB) | 26.4k | n/a | 0.910 |
The graph is traversed on compressed distances; the best 2·ef candidates are
re-ranked exactly from the memory-mapped full vectors, which stay on disk.
"n/a" marks recall the engine never reaches. The graph itself (131 MiB) is not
compressed, so the whole resident index shrinks 4.2×, not 31.7×.
| strategy | mean latency | p99 | recall@10 |
|---|---|---|---|
| post_filter | 0.79 ms | 1.7 ms | 0.655 |
| bitmap | 53.60 ms | 430.4 ms | 0.988 |
| brute_force | 8.88 ms | 29.5 ms | 1.000 |
| planner | 0.84 ms | 2.9 ms | 0.968 |
No fixed strategy wins across selectivities: bitmap-constrained traversal
collapses on rare filters, brute force grows with the match count, and
post-filtering loses recall once matches thin out. The planner picks per query
from selectivity estimates (quantile sketches and value frequencies kept in
SQLite). Its thresholds were tuned on the learn split only
(configs/bench/sift1m_filters_tune.yaml); the per-selectivity breakdown is in
bench/results/sift1m_filters.json.
A LightGBM model predicts a per-query search budget from features observed
during the search, replacing the fixed ef. Both variants (one up-front
prediction; re-prediction at checkpoints) were trained on learn-split queries
and evaluated single-threaded at matched recall:
| dataset | recall | fixed ef | upfront (Δ) | checkpoint (Δ) |
|---|---|---|---|---|
| SIFT1M | 0.95 | 150 µs | 163 µs (+8.7 %) | 168 µs (+12.3 %) |
| SIFT1M | 0.99 | 316 µs | 332 µs (+5.2 %) | 360 µs (+14.2 %) |
| MS MARCO 300k | 0.95 | 397 µs | 376 µs (−5.4 %) | 392 µs (−1.3 %) |
| MS MARCO 300k | 0.97 | 665 µs | 598 µs (−10.1 %) | 640 µs (−3.7 %) |
The target of a 25 % latency reduction on both datasets was not met. An oracle
with each query's exact budget would cut SIFT1M work about 4×, but the model
explains only ~39 % of the variance in required budget, which bounds the
achievable saving near 10 % of distance computations; the measured numbers sit
where that bound predicts once the model's own cost is paid. Full curves are
in bench/results/*_early_stop.json, and the model ships disabled
(early_stop.model: null).
bench/crash.py starts a writer subprocess, hard-kills it at a random moment
(TerminateProcess / SIGKILL), reopens the collection, and verifies that
every acknowledged upsert is present bit-for-bit, every acknowledged delete is
absent, nothing recovered is corrupt, and the index is consistent and
searchable. 100/100 runs pass across three snapshot cadences; a short version
runs in pytest on every test run.
gRPC API (api/) ─► query planner (engine/planner.py)
│ filter strategy from estimated selectivity
│ search budget: explicit ef │ learned model │ config default
▼
index layer: HNSW (index/hnsw.py) · PQ (index/pq.py) · early stop (ml/)
▼
storage: memmap vectors · SQLite metadata · WAL + snapshots (storage/)
Insert: validate → append to WAL + fsync → write vector (memmap) and attributes (SQLite + NumPy columns) → PQ-encode → HNSW insert → ack.
Query: parse filter → estimate selectivity → brute force over matching ids, or HNSW (full-precision or PQ codes, optionally bitmap-constrained) → exact re-rank → attribute join → response.
HNSW on flat arrays (index/hnsw.py). Layer 0 is an (N, 2M) int32
neighbour table with −1 for empty slots; upper layers share one compact
(rows, M) table addressed by per-node row offsets, since only ~N/M nodes
exist above layer 0. Kernels: greedy descent, best-first search over parallel
(dist, id) array heaps, and Malkov's neighbour-selection heuristic. Visited
sets are per-thread uint32 tag arrays that never need clearing. The build is
parallel and deterministic: batches search the pre-batch graph in prange and
write only their own rows, then reverse edges are grouped by (layer, target)
and each target row is re-pruned by exactly one thread. Node levels are hashed
from ids, so any thread count reproduces the same graph. Deletes are
tombstones. Every kernel has a pure-Python twin checked by the tests.
Product quantization (index/pq.py). 16 subvectors × 256-centroid
codebooks (k-means in NumPy, optionally PyTorch on GPU for training only);
512 bytes → 16. Queries build one 16×256 ADC table, then score codes by table
lookups. In PQ mode the traversal keeps a bounded pool of the best 2·ef
candidates for exact re-ranking; the depth was chosen on the learn split.
Filters and planner (engine/filters.py, engine/planner.py). A small
expression language (comparisons, IN, AND/OR/NOT, parentheses) parses to an
AST evaluated as vectorised masks over per-attribute NumPy columns; SQLite
holds the durable copy and the statistics. Strategy by estimated selectivity:
≥ 0.1 post-filter (with bitmap fallback if too few survive), 0.02–0.1
bitmap-constrained traversal, ≤ 0.02 brute force over the matching ids.
Bitmaps are cached per (predicate, write-version).
Durability (storage/wal.py). Every write is appended to a CRC-framed log
and fsynced before it is applied or acknowledged. Snapshots are written to a
temp directory, fsynced, renamed, and published by atomically replacing a
CURRENT pointer; recovery loads the newest snapshot and replays the log tail
through the same code path as live writes. A torn tail record fails its CRC,
was never acknowledged, and is truncated.
Concurrency (engine/collection.py). Lock-free reads, single-writer
writes. Growable state grows by copy-and-swap and vectors are written before
any edge references them, so readers capture a consistent view without locks;
Numba kernels release the GIL, so reads scale with the server's thread pool.
The trade-off: a search concurrent with a write may miss the newest points.
Early-termination model (ml/). Features are O(1) signals from the
running search (entry distance, best/k-th gap, candidate frontier, expansion
counts, selectivity). Labels come from generous searches on learn queries.
The trained trees are flattened to five arrays and evaluated by a small Numba
function inside the search loop (~1 µs), matching LightGBM's predictions to
1e-9 in tests.
uv sync
uv run python -m api.server --root data/collections --port 50051import numpy as np
from api.client import Client
db = Client("127.0.0.1:50051")
db.create_collection("products", dim=128) # options: index="hnsw_pq", metric="cosine", hnsw__M=32
vecs = np.random.rand(1000, 128).astype("float32")
attrs = [{"price": float(i), "category": "shoes" if i % 2 else "hats"} for i in range(1000)]
db.upsert("products", [f"p{i}" for i in range(1000)], vecs, attrs)
db.search("products", vecs[0], k=5, filter='price < 500 AND category == "shoes"',
include_attributes=True)Errors surface as gRPC status codes (INVALID_ARGUMENT, NOT_FOUND,
ALREADY_EXISTS). The engine also embeds directly
(engine.collection.Collection), and an optional REST gateway is available via
uv sync --extra rest and uvicorn api.rest:create_app --factory.
For a guided demo — 50k real passages, semantic and filtered search over gRPC,
deletes, error handling, and a live kill -9 recovery — run
uv run python -m examples.demo (requires the data extra and the MS MARCO
dataset step below).
uv sync --extra bench # engine + FAISS baseline + matplotlib
uv run pytest # 110 tests, ~15 s with a warm Numba cache
uv run python -m bench.datasets.sift1m # download SIFT1M, verify its ground truth
uv run python -m bench.run configs/bench/sift1m_hnsw.yaml
uv run python -m bench.run configs/bench/sift1m_pq.yaml
uv run python -m bench.run configs/bench/sift1m_filters_tune.yaml # learn split only
uv run python -m bench.run configs/bench/sift1m_filters.yaml
uv run python -m bench.run configs/bench/sift1m_early_stop.yaml
uv run python -m bench.run configs/bench/crash.yaml
uv sync --extra bench --extra data # + torch (CUDA) and sentence-transformers
uv run python -m bench.datasets.msmarco
uv run python -m bench.run configs/bench/msmarco_early_stop.yaml
uv run python -m bench.report # the tables aboveEach run writes bench/results/<config>.json — including CPU, RAM, OS,
library versions, thread count and the full config — plus an SVG plot
(--plot-only redraws from the JSON).
Protocol: 3 warmup runs, 5 timed runs, median reported; p99 over per-query times; JIT compilation happens in warmup and is never timed. Batch QPS uses 16 threads for both engines; single-thread latency is pinned to one P-core (the CPU is hybrid, and unpinned runs drift ~20 %). Seeds are fixed everywhere, and nothing is tuned on test queries — early-stop models, PQ re-rank depth and planner thresholds all come from the separate learn split.
- Single node: no replication or sharding.
- PQ compresses vectors, not the graph, which caps whole-index savings at 4.2× on SIFT1M.
- Deletes are tombstones; no compaction or rebuild command yet.
- Attributes are scalar (number, string, bool);
ANDselectivity assumes independence. - The crash test covers process kills; fsync-before-ack is the protection against OS crashes and power loss, which a live-machine test cannot simulate.
- Absolute numbers are from one hybrid-CPU Windows laptop; the same-machine, same-session comparisons are what transfer.
proto/ service definition + generated stubs
api/ gRPC server, Python client, optional REST gateway
engine/ collection, filter language, planner, config
index/ flat.py (brute force), hnsw.py, pq.py, distance kernels
ml/ early-stop features, labels, training, in-kernel tree inference
storage/ memmap vectors, SQLite metadata, WAL + snapshots
bench/ datasets, benchmark runners, micro-benchmarks, results/
tests/ unit, property-based and crash-recovery tests
configs/ index defaults and one YAML per benchmark