P03 — Small Vector Database

Run it first. There is a companion page that builds this project's machinery as numbered, independently runnable blocks and then assembles them into one measured system: P03 hands-on — block by block (handson/h*.py). Every number on it was produced by running the code. Read it alongside the milestones below.

Medium · 88 hours · Weeks 27–34 · Stage 2 · Python with a Rust storage layer

Table of Contents

• The Loop, Instantiated
• Why This Project Matters
• Prerequisites
• Duration and Size
• Central Technical Questions
• Architecture
• Showcase — The Query Planner, In Three Lines
• Implementation Milestones
• Concepts To Study
• Primary-Source Readings
• Experiments
• Benchmarks and Metrics
• Correctness Tests
• Failure Tests
• Expected Difficulties
• Scope Boundaries
• Deliverables
• Exit Criteria
• Extension Ideas
• Connections
• References

The Loop, Instantiated

Why This Project Matters

The gap between "I have an HNSW index" and "I have a vector database" is where every real engineering problem lives, and it is a gap most people never cross because the index is the interesting part.

This project's real job in the journey is to make you want Project 4. You will build the naive persistence layer — append-only file, full index rebuild on start — and measure its recovery time at one million vectors. It will be minutes. That number is what makes sparse indexes, Bloom filters, and compaction feel like solutions to a problem you have rather than features in a paper you read. This is the roadmap's most deliberate application of "naive design first", and it costs about six hours of rework on purpose.

The second reason: filtering is where vector search actually breaks in production, and you already ship filtered vector search on OpenSearch. After this project you will know exactly why your p99 spikes when a filter is narrow.

Prerequisites

• P02 complete — this is a hard dependency; the index is the core of the database
• File I/O: read/write/fsync, what the page cache is, what mmap actually does
• Basic concurrency: mutexes, reader-writer locks, and why a graph index is hostile to both

Duration and Size

Medium, 88 hours, 8 weeks.

Central Technical Questions

1. What does "durable" mean, precisely? After which system call is a write recoverable, and what exactly does fsync guarantee on your filesystem?
2. Why can't you update a graph index in place? Deletion in HNSW is not a matter of removing a node — trace why.
3. Pre-filter or post-filter? There is a selectivity threshold. Derive it, then measure where the derivation is wrong.
4. What does the filter do to graph connectivity? A filtered graph walk is a walk on a subgraph you did not build, and that subgraph may be disconnected.
5. What is your consistency model? Can a search see a half-inserted vector? Write it down as a sentence before you write the code.
6. What is your storage amplification, and where did it go — tombstones, alignment, the graph, or the metadata?

Architecture

Write your naive design first.

                    ┌──────────────── write path ────────────────┐
  insert(id,vec,md) ─► WAL (append + fsync policy) ─► memtable ──┼─► flush ─► segment N
                                                     (vectors +  │            ├ vectors.bin  (mmap, fixed stride)
                                                      metadata)  │            ├ meta.bin     (id → offset, attrs)
                                                                 │            ├ graph.bin    (HNSW adjacency)
                                                                 │            └ tomb.bin     (deleted ids)
                    ┌──────────────── read path ─────────────────┘
  search(q,k,filter) ─► planner ─┬─ pre-filter:  build allowed-set, walk graph restricted to it
                                 └─ post-filter: search top-K, filter, K = k/selectivity
                                        │
                                 merge across segments ─► apply tombstones ─► top-k

The filtering problem, derived

This is the section worth the most.

Post-filtering runs an unfiltered ANN search for the top \(K\), then discards non-matching results. If the filter is independent of similarity and selects a fraction \(s\) of the corpus, the expected number of surviving results is \(Ks\). To return \(k\) results you need

\[ K \ge k/s \]

Computed for \(k = 10\) over a 1M-vector corpus:

At \(s = 10^{-4}\) you are searching with efSearch ≥ 100,000, which is not a graph walk any more — it is brute force with a worse constant factor. This is the p99 cliff you have seen in production. And the table understates it: the independence assumption fails badly when the filter correlates with similarity (e.g. filtering to one publisher when that publisher's articles cluster in embedding space), and in the adversarial case no \(K\) suffices because all matching items lie outside the unfiltered top-\(K\) entirely.

Pre-filtering restricts the graph walk to matching nodes. It has no over-fetch problem, but it introduces a worse one: the induced subgraph may be disconnected. Your carefully built navigable graph guaranteed connectivity over all \(n\) nodes; it guarantees nothing about the subgraph induced by an arbitrary predicate. Greedy search on a disconnected subgraph reaches one component and stops — the same failure mode you diagnosed in P02's clustered-data ceiling, now caused by a query rather than by the data.

Brute force over the filtered set costs \(O(sn)\) and is exact. At \(s = 10^{-4}\) on 1M vectors that is 100 distance computations — faster than either alternative and perfectly accurate.

So the planner has three strategies and the crossovers are empirical. Deriving the crossover and then measuring where the derivation is wrong is the central experiment of this project.

Why deletion is hard

An HNSW node is referenced by the adjacency lists of its neighbours. Removing it requires either patching every in-edge (you do not have a reverse index, and building one doubles memory) or leaving a dangling reference. So every practical implementation uses tombstones: mark deleted, keep the node in the graph as a routing waypoint, filter at result time.

The consequences you must measure:

• Recall drifts down with churn, because tombstoned nodes occupy beam slots without producing results. Effective efSearch falls to roughly \(ef \cdot (1 - \text{tombstone fraction})\).
• Space amplification grows monotonically until compaction.
• Compaction means rebuilding the graph for that segment, which is the most expensive operation in the system. Its cost is why segment size is a real design decision and not an arbitrary constant.

Showcase — The Query Planner, In Three Lines

Before eight weeks of vector database, spend ten minutes on the decision the planner exists to make. Costs are the measured ones from numbers: 13.3 ns per BLAS distance, 899 ns per interpreted graph hop.

# P03 -- the filtering planner, decided by arithmetic rather than by taste.
import math
N, k = 1_000_000, 10
COST_PER_DIST_NS, GRAPH_HOP_NS = 13.3, 899.0   # measured, numbers.md
for s in (0.5, 0.1, 0.01, 0.001, 0.0001):
    post_K = math.ceil(k/s)                    # over-fetch, then discard
    post   = post_K * GRAPH_HOP_NS             # graph walk cost ~ ef
    brute  = s*N * COST_PER_DIST_NS            # exact scan of the matching set
    winner = "post-filter" if post < brute else "BRUTE FORCE (exact!)"
    print(f"s={s:<8} post-filter needs K={post_K:>7,} ({post/1e6:>7.2f} ms)   "
          f"brute over {s*N:>8,.0f} items ({brute/1e6:>6.2f} ms)   -> {winner}")
# solve for the crossover: (k/s)*HOP == s*N*DIST  =>  s = sqrt(k*HOP/(N*DIST))
xover = math.sqrt(k*GRAPH_HOP_NS/(N*COST_PER_DIST_NS))
print(f"\\nCrossover, solved: s = sqrt(k*HOP/(N*DIST)) = {xover:.4f}")
print("Below ~2.6% selectivity, EXACT brute force over the filtered set beats the")
print("approximate index. The planner is three lines of arithmetic, and a system")
print("without one falls off a cliff exactly here.")

s=0.5      post-filter needs K=     20 (   0.02 ms)   brute over  500,000 items (  6.65 ms)   -> post-filter
s=0.1      post-filter needs K=    100 (   0.09 ms)   brute over  100,000 items (  1.33 ms)   -> post-filter
s=0.01     post-filter needs K=  1,000 (   0.90 ms)   brute over   10,000 items (  0.13 ms)   -> BRUTE FORCE (exact!)
s=0.001    post-filter needs K= 10,000 (   8.99 ms)   brute over    1,000 items (  0.01 ms)   -> BRUTE FORCE (exact!)
s=0.0001   post-filter needs K=100,000 (  89.90 ms)   brute over      100 items (  0.00 ms)   -> BRUTE FORCE (exact!)
\nCrossover, solved: s = sqrt(k*HOP/(N*DIST)) = 0.0260
Below ~2.6% selectivity, EXACT brute force over the filtered set beats the
approximate index. The planner is three lines of arithmetic, and a system
without one falls off a cliff exactly here.

The third strategy is the one people forget. Below ~2.6% selectivity, an exact scan of the filtered set beats the approximate index — faster and correct. A planner that only knows pre- and post-filtering is missing the option that wins the hardest case. This is E3 in miniature.

Implementation Milestones

Concepts To Study

• Durability primitives: write vs fsync vs fdatasync; the page cache; write barriers; why a successful write() guarantees nothing
• Write-ahead logging: the log-before-data rule and why it is sufficient for crash-atomicity
• mmap: page faults as the loading mechanism, the OS as your buffer pool, and the reasons mmap is a contested choice for databases
• Append-only and immutability: why immutable segments make concurrency easy and space accounting hard
• Tombstones and compaction: logical vs physical deletion
• Segment/LSM-adjacent layout: why databases split into many immutable files
• Snapshot isolation: readers see a consistent version; how versioning implements it
• Query planning: cardinality estimation, and why a wrong estimate is worse than no plan
• Storage amplification: bytes on disk / bytes of live data, and every place it hides
• Checksums: CRC32C vs xxHash; per-block vs per-file

Primary-Source Readings

Budget: 11 hours.

Experiments

E3 is the project's centrepiece. You have a derivation predicting the post-filter over-fetch; you have a mechanism predicting pre-filter degradation; the crossovers are where derivation meets reality.

E12 is the most production-relevant. Steady-state p99 with no compaction running is a number that does not exist in production.

Benchmarks and Metrics

Correctness Tests

1. Crash consistency. kill -9 at ≥20 randomised points during a write workload; after recovery, every acknowledged write is present and no unacknowledged write appears. Automate this — it is the most valuable test in the project.
2. Read-your-writes within a session, at the stated consistency level.
3. Deleted vectors never returned, at any efSearch, before or after compaction.
4. Filter correctness: results satisfy the predicate, 100%, all three strategies.
5. Brute-force agreement: for small n, filtered search matches filtered brute force exactly at high efSearch.
6. Snapshot isolation: a reader holding a snapshot sees a stable view while a writer inserts and deletes underneath it.
7. Checksum detection: flip a bit in every file type; each is detected, not silently served.
8. Idempotent recovery: recover twice, get identical state.
9. Format versioning: an old-version file is rejected with a clear error, not misparsed.
10. Compaction preserves semantics: full query-result equality before and after, modulo tombstoned ids.

Failure Tests

Expected Difficulties

1. You will underestimate crash testing. Randomised kill -9 harnesses take a day to build and find bugs nothing else finds. Build it at milestone 2, not milestone 11.
2. Pre-filtering is much harder than it sounds. A filter-aware walk needs a cheap membership test inside the innermost loop, and a bitmap over segment-local ordinals is usually the only thing fast enough.
3. mmap makes memory accounting confusing. RSS is not your memory usage; the page cache is shared and evictable. Report both, and know which one the OOM killer looks at.
4. Concurrency with a mutable graph is genuinely hard. Mitigation: immutable segments plus a small mutable head. That is the design; do not fight it.
5. The query planner will be wrong and each misprediction will look like a performance bug. Log the estimated vs actual selectivity on every query from day one.

Scope Boundaries

In scope: single node, one collection, equality and range predicates on scalar metadata, crash recovery, compaction, snapshot-isolated readers.

Out of scope: distribution and replication (P05); SQL or any query language; transactions across multiple keys; authentication; a network protocol beyond a thin local RPC; multiple collections or schema evolution; hybrid dense+sparse retrieval; re-implementing HNSW — it is imported from P02 unchanged.

Deliverables

1. vectordb/ — embeddable library plus a CLI
2. STORAGE-FORMAT.md — byte-level layout, written before the code and updated when it drifts. This is a portfolio artifact on its own
3. REPORT.md with the E3 filtering study as its centrepiece
4. crashtest/ — the randomised kill harness, reusable in P04 and P05
5. Notebook entries for E1, E3, E10, E12
6. A recovery-time table that explicitly motivates P04

Exit Criteria

• Crash test passes at ≥20 randomised kill points with zero data loss of acknowledged writes
• E3 complete: all three strategies across six selectivities, with both crossovers identified
• Filtered recall measured and the pre-filter degradation explained by a mechanism
• Recovery time at 10⁶ vectors measured for both naive and snapshot+WAL, with the speedup stated
• Storage amplification measured and decomposed by cause
• p99 during compaction reported alongside steady-state p99
• The consistency model written as a paragraph a reviewer could attack
• REPORT.md written with a falsified prediction

Extension Ideas

• DiskANN-style disk-resident graph: index larger than RAM, with a measured RAM/recall/latency frontier. The strongest extension here.
• Filter-aware graph construction: add edges that preserve connectivity under the most common predicates (this is the Filtered-DiskANN idea). Real research territory.
• Learned selectivity estimation to improve the planner, measured against the logged mispredictions.
• Vector compression (scalar or product quantization) with a storage/recall frontier.

Connections

Backward: P02 supplies the index. P01 supplies realistic embeddings and metadata (token counts, timestamps) to filter on.

Forward:

• → P04 (LSM): your recovery-time measurement is P04's motivation. Your crash-test harness is reused directly.
• → P05 (Distributed KV): segments and snapshots become the unit of replication and rebalancing.
• → P08 (Recommender): filtered retrieval — "exclude already-seen", "last 48 hours" — is exactly the selectivity regime E3 studies, and freshness filters are narrow.
• → P15: storage and indexing choices affecting recommendation freshness is one of the candidate research questions, and this project supplies both sides of it.

References

• Subramanya, S. J., Devvrit, F., Kadekodi, R., Krishnaswamy, R., Simhadri, H. V. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS 2019.
• Gollapudi, S. et al. Filtered-DiskANN: Graph Algorithms for Approximate Nearest Neighbor Search with Filters. WWW 2023.
• Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., Schwarz, P. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM TODS 17(1), 1992.
• Crotty, A., Leis, V., Pavlo, A. Are You Sure You Want to Use MMAP in Your Database Management System? CIDR 2022.
• Wang, J. et al. Milvus: A Purpose-Built Vector Data Management System. SIGMOD 2021.
• Guo, R. et al. Manu: A Cloud Native Vector Database Management System. VLDB 2022.
• Kleppmann, M. Designing Data-Intensive Applications. O'Reilly, 2017. Chapter 3.
• Hellerstein, J. M., Stonebraker, M., Hamilton, J. Architecture of a Database System. Foundations and Trends in Databases 1(2), 2007.
• Pillai, T. S. et al. All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications. OSDI 2014. Read this before you trust your fsync discipline.