Out-of-Core Vector Database

A C++17 vector database for approximate nearest-neighbor (ANN) search over datasets that exceed available RAM. Target: 100GB dataset, ≤8GB RAM, recall@10 ≥ 0.95, competitive QPS with DiskANN.

Status

Stage	Module	Status
1	Storage Engine - DiskManager + BufferPool (Clock eviction, CRC32 pages)	done
2	Core Algorithms - distance kernels (scalar + AVX2/FMA), k-means, flat index	done
3	HNSW (in-memory) - multi-layer graph, beam search, heuristic neighbor selection	done
4	Out-of-Core HNSW (layer-0 records on paged storage, beam search via BufferPool)	done
5	Product Quantization - codec + ADC + PQFlatIndex with rerank	done
6	IVF and IVF-PQ - coarse k-means partitioning + residual PQ compression	done
7	Query Engine - unified SearchEngine, QueryPlanner, extern "C" FFI	done
8	Python Eval Harness - vs. FAISS, hnswlib, DiskANN	planned

Current build: 82 / 82 tests pass in ~15s. Highlights:

• AVX2 L2² is 9.16× scalar on the hot path (target was 4×).
• HNSW Recall@10 = 0.972 at ef=200, 0.994 at ef=400 on 10k Gaussian vectors (dim=128) — measured against the brute-force FlatIndex oracle.
• OocHNSW recall = 0.952 at ef=100 holds identically across buffer-pool sizes from 5% to 200% of the index — the buffer pool affects speed, not correctness. Full-cache QPS is 3246; 5%-cache QPS is 22 (≈148× I/O penalty under heavy eviction).
• PQ codec: 32× compression (128-dim float32 → 16 bytes); ADC distance is 1.85× faster than AVX2 L2 in the memory-bandwidth-bound (cold) regime because it touches 32× less data per record.
• IVF-PQ on 100k×128 vectors: 17.3× faster than brute force at recall@10 = 0.896, with a 2.3 MB index vs 48.8 MB of raw vectors (21× smaller).
• Unified SearchEngine API drives Flat / HNSW / IVF-PQ through one Search(query, k); QueryPlanner picks the right backend from (n, dim, ram_budget); rerank closes the IVF-PQ recall gap vs exact L2 to <2%. Embeddable via a C99 FFI (oocvdb_* handles).

Quick Start

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel $(nproc)
cd build && ctest --output-on-failure

Run the AVX2 microbench:

./build/bench_distance

Architecture

Four layers, top to bottom. Each layer depends only on the layers beneath it.

Query Engine    ANN search · beam search · re-ranking
Index Layer     HNSW · IVF · PQ · IVF-PQ
Buffer Pool     page cache · Clock eviction · async prefetch
Disk Manager    4KB pages · pread/pwrite · CRC32 · io_uring (Stage 4+)

The thesis: HNSW's upper layers are logarithmically small and stay resident; layer-0 (99% of nodes) is paged through the buffer pool. During beam search, the buffer pool prefetches neighbor pages one hop ahead, overlapping I/O with distance computation.

See docs/ARCHITECTURE.md for page layouts, file formats, and data flow.

Why C++

Direct memory control for the buffer pool, SIMD intrinsics for distance kernels, and parity with industry baselines (FAISS, hnswlib, DiskANN are all C++) so head-to-head benchmarks are apples-to-apples.

Build Requirements

• CMake ≥ 3.20
• GCC ≥ 9 or Clang ≥ 13 (C++17)
• x86-64 with AVX2 + FMA (most CPUs since 2014)
• Optional: libasan / libubsan for -DOOCVDB_SANITIZE=ON builds

GoogleTest is fetched automatically via CMake FetchContent on first configure.

Repository Layout

include/oocvdb/        public C++ headers
  storage/             page.h, disk_manager.h, buffer_pool.h
  utils/               distance.h, kmeans.h
  index/               flat.h
src/                   implementations (mirrors include/)
tests/                 GoogleTest suites
benchmarks/            microbenchmarks
docs/                  IMPLEMENTATION.md · ARCHITECTURE.md · stages/

Documentation

• docs/IMPLEMENTATION.md - eight-stage master plan with acceptance criteria
• docs/ARCHITECTURE.md - system design, on-disk formats, query flow, memory budget
• CLAUDE.md - guidance for Claude Code when working in this repo

References

• Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using HNSW graphs, TPAMI 2020
• Subramanya et al., DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, NeurIPS 2019
• FAISS - Meta's vector similarity library
• hnswlib - reference HNSW implementation
• ANN Benchmarks - standardized evaluation methodology

License

TBD.