Introduction

ferrodb is a relational database written from scratch in Rust. It is a page-based storage engine, B+-tree indexes, write-ahead logging with crash recovery, MVCC transactions, a hand-written SQL frontend, a cost-based query optimizer, the PostgreSQL wire protocol, and a WebAssembly build — with no third-party SQL parser, storage engine, or B+-tree crate. The point is to build the machine, not to glue one together.

This book is an architecture tour. Each chapter takes one subsystem and explains what it does, how it works, and why it is built that way, following the same bottom-up order the database was built in: you cannot understand the executor until you understand the B+-tree, and you cannot understand the B+-tree until you understand the pager.

The milestone map

ferrodb was built as eight milestones, each an independently testable, demoable artifact:

The crate layout

crates/storage   disk · buffer pool · slotted pages · B+-tree · WAL + recovery
crates/sql       lexer · Pratt parser · AST
crates/engine    catalog · tuple codec · evaluator · MVCC · planner + optimizer · executor
crates/pgwire    PostgreSQL wire protocol server (ferrodb-pg)
crates/wasm      WebAssembly bindings (hand-written C ABI, no wasm-bindgen)
crates/cli       ferrodb-kv (raw KV) + ferrodb (SQL shell)
crates/bench     SQLite-comparison benchmark harness

A recurring theme worth watching for: each layer is an abstraction the layer above can rely on without knowing its internals. The B+-tree talks to the buffer pool, never to the file. The executor talks to the B+-tree, never to a page. This is what makes it possible to swap the file for a Vec<u8> and run the whole engine in a browser (Chapter 9) without touching the SQL layer.

Storage: the pager

Every database is ultimately a program that reads and writes a file in fixed-size blocks. ferrodb's storage layer is three components stacked on top of a single file: the disk manager, the buffer pool, and slotted pages.

The disk manager

The database is one file divided into fixed 4 KiB pages, addressed by a PageId (a u32 page number). The disk manager does three things: allocate a new page (extend the file), read a page by id, and write a page by id.

Every page carries a CRC32C checksum in its header. On every read the checksum is recomputed and compared; a mismatch means the page is torn or corrupt and the read fails loudly rather than returning garbage. This is the database's first line of defence against a half-written page.

Crucially, the disk manager does not talk to std::fs::File directly — it holds a Box<dyn Blob>, a small trait (read/write/seek/set_len/sync/len). The native implementation is a File; an in-memory Vec<u8> implementation (MemBlob) backs the WASM build. Everything above this line is oblivious to which one is in use.

The buffer pool

Reading a page from disk on every access would be ruinous, so the buffer pool is an in-memory cache of pages held in a fixed set of frames (256 by default). Callers fetch(page_id) to pin a page into a frame and get a mutable handle; they unpin it when done.

When every frame is occupied and a new page is needed, one must be evicted. The buffer pool uses clock-sweep eviction: frames are arranged in a ring with a reference bit; the "clock hand" sweeps forward, clearing set bits and evicting the first frame it finds with a clear bit and no pins. This approximates least-recently-used without the bookkeeping of true LRU.

Two rules make the pool safe for durability (Chapter 4):

• A pinned page is never evicted — someone is using it.
• A dirty page (modified since it was read) must be written back before its frame is reused, and under the no-steal policy an uncommitted dirty page is never written back at all.

Slotted pages

A 4 KiB page needs to hold a variable number of variable-length items — rows, or B+-tree entries. The standard layout for this is a slotted page: a header at the front, a slot directory growing downward from just after the header, and the cells (the actual bytes) growing upward from the end. Each slot is a (offset, length) pointer into the cell area.

+--------+------+------+-----      -----+--------+--------+
| header | slot | slot | ...  free  ... |  cell  |  cell  |
+--------+------+------+-----      -----+--------+--------+
          \----- directory ----->       <---- cells -----/

This layout has two properties the layers above depend on. First, an item can be found in O(1) by slot number without scanning the page. Second, an item can grow, shrink, or be deleted by rewriting only its cell and slot — the other items do not move, so their slot numbers stay stable. Free space is tracked so the page knows when it is full and must split.

With these three pieces — checksummed pages, a caching pinnable buffer pool, and a slotted page layout — we have everything the B+-tree needs.

The B+-tree

The B+-tree is the data structure that turns a heap of pages into an ordered map: keys stored in sorted order, with logarithmic point lookups and efficient ordered range scans. Every table in ferrodb is a B+-tree keyed by its primary key (or a hidden row id).

Shape

A B+-tree is a balanced tree of pages:

• Internal nodes hold separator keys and child page pointers. They exist only to route a search to the right leaf.
• Leaf nodes hold the actual (key, value) entries, in sorted order, and each leaf points to its right sibling — so once you find the first matching leaf, an ordered scan is just walking the sibling chain.

All leaves are at the same depth; the tree stays balanced by construction.

Point lookup

To find a key, start at the root and at each internal node binary-search the separators to pick the child to descend into, until you reach a leaf; then binary-search the leaf. The number of page fetches is the tree height — O(log n). This is the operation behind every PK IndexSeek.

Insert, split, and root growth

Insertion finds the target leaf and adds the entry. If the leaf overflows its 4 KiB, it splits: the entries are divided between the old leaf and a new one, and the split's separator key is pushed up into the parent. If the parent overflows, it splits too, and so on up the tree. If the root splits, a brand-new root is created one level up — this is the only way the tree grows taller, and it is what keeps every leaf at the same depth.

This split-on-overflow behaviour is exactly what the WASM visualizer (Chapter 9) animates: insert enough rows and you watch a single-leaf tree become a root over two leaves, then three, and so on.

Range scans

Because leaves are sorted and chained, an ordered range scan is: descend to the leaf containing the lower bound, then walk right along the sibling chain emitting entries until the upper bound is crossed. scan(lo, hi) treats lo as inclusive and hi as exclusive. The optimizer's IndexRange access path (Chapter 7) is a thin wrapper over exactly this call — it seeks straight to the starting leaf rather than scanning the whole table.

Overflow chains

A value larger than a page cannot fit in a leaf cell. ferrodb stores such values in a chain of overflow pages: the leaf holds a small stub pointing at the first overflow page, and each overflow page points to the next. A 20 KB value round-trips transparently through this chain.

Proving it correct

A B+-tree is fiddly enough that correctness must be demonstrated, not asserted. ferrodb's core test runs hundreds of randomized insert/delete sequences against a std::collections::BTreeMap model and asserts the two agree on every operation, alongside a 2 000-key split-stress test and the 20 KB overflow round-trip. If the tree ever diverges from the model, the property test shrinks the failing sequence to a minimal reproducer.

WAL & crash recovery

A database must survive a crash. If the machine loses power midway through a multi-page B+-tree split, the file must not be left in a state where the tree is half-updated and unreadable. ferrodb guarantees this with a write-ahead log (WAL) and a no-steal buffer policy.

The two policies

Recovery strategy is defined by two questions about when dirty pages reach the data file:

• Steal? May an uncommitted transaction's dirty pages be written to the data file? ferrodb says no (no-steal). Uncommitted changes never touch the data file, so recovery never has to undo anything.
• Force? Must a committing transaction's pages be flushed to the data file before commit returns? ferrodb says no (no-force) for the data file, but it does force the log. The pages are logged and the log is fsynced at commit; the data file catches up lazily.

No-steal + log-force gives the simplest correct recovery: redo-only. There is nothing to undo, and the only thing to redo is committed work that had not yet reached the data file.

The commit protocol

Every statement is an autocommit transaction (until M4 adds explicit BEGIN). On commit:

1. Write the after-images of every page the transaction modified into the WAL.
2. Append a commit record.
3. fsync the WAL — now the transaction is durable, even though the data file is stale.
4. Only then may the dirty pages be written back to the data file (and they may be deferred).

The critical window is between step 3 and the data-file write. A crash there has the change durably in the log but not in the data file — exactly the case recovery must repair.

Recovery

On startup, ferrodb scans the WAL. For every transaction that has a commit record, it replays the logged page after-images into the data file; transactions without a commit record are ignored, so their partial effects vanish. Because the after-image is the whole page, replay is idempotent — applying it twice is the same as once — which is what makes redo safe to run after any crash.

The upshot: a crash between the WAL commit and the data flush — the exact window that would otherwise corrupt a multi-page split — is repaired on restart, and a statement that never committed leaves no trace.

Proving it without racing the OS

You cannot reliably test crash recovery by launching a process and kill-ing it at the right microsecond. ferrodb instead uses deterministic crash injection: the test drives the engine to the precise point between log-commit and data-flush, drops the in-memory state, reopens from the file, and asserts the committed data is present and the uncommitted data is gone. The dangerous window is reproduced on purpose, every run.

MVCC transactions

Multiple transactions must run concurrently without corrupting each other's view of the data, and a long read must not block a write. ferrodb achieves this with multi-version concurrency control (MVCC) and snapshot isolation: writers create new versions instead of overwriting, and each transaction reads from a consistent snapshot taken when it began.

Version chains

Nothing is ever overwritten in place. Each key in the B+-tree maps not to a single row but to a version chain — a list of versions, each stamped with:

• xmin: the transaction that created this version.
• xmax: the transaction that deleted it (or none).
• hint bits: whether xmin / xmax are known-committed.

The three write operations become:

• INSERT appends a new version with xmin = my transaction.
• UPDATE stamps the old version's xmax and appends a new version — delete-old + insert-new.
• DELETE stamps the visible version's xmax with a tombstone.

Snapshots and visibility

At BEGIN, a transaction captures a snapshot: the set of transactions committed as of that instant. To read a key, the engine walks its version chain and picks the one version visible to the snapshot — created by a transaction the snapshot considers committed, and not yet deleted by one it does. Because a reader only ever consults versions and its own fixed snapshot, readers never block writers and writers never block readers.

Commit truth without a separate log

How does a version know whether the transaction that wrote it committed? Many systems keep a separate commit log (CLOG). ferrodb instead makes the hint bits the persisted source of truth: when a transaction commits, its versions' hint bits are set to committed and written out. After a restart, a committed version is simply visible; a version whose writer crashed or rolled back has no committed hint bit and is invisible — there is no undo pass and no external log to consult.

Write conflicts

If two concurrent transactions both try to update the same row, the second to arrive finds the version already stamped with a live xmax from the other transaction and fails with a write conflict — first-updater-wins. This is what keeps snapshot isolation from silently losing an update.

VACUUM

Version chains grow without bound as rows are updated. VACUUM walks the tables and reclaims versions that are dead to every live snapshot — no current or future transaction could ever need them — compacting the chains. It is the garbage collector that keeps MVCC from leaking space forever.

Correctness here cannot be shown by a single-threaded test. ferrodb drives interleaved transactions — begin A, begin B, write in A, read in B, commit, re-read — and asserts each sees exactly the snapshot it should.

SQL frontend & executor

Above the storage and transaction layers sits the part users actually touch: SQL. ferrodb parses and executes SQL with no sqlparser crate — a hand-written lexer and a Pratt parser feed an AST that a volcano-style executor runs over the B+-trees.

Lexer

The lexer turns the raw SQL string into a stream of tokens — keywords, identifiers, string and number literals, operators, punctuation. It is a straightforward character scanner; the only subtleties are case-insensitive keywords and distinguishing - the operator from a negative number.

Pratt parser

Expressions are parsed with a Pratt parser (top-down operator precedence). Each operator has a binding power; the parser reads a prefix (a literal, a column, a parenthesized group, a function call) and then, while the next operator binds tighter than the current context, folds it in. This handles a + b * c, NOT x AND y, comparison chains, and qualified column references (t.col) cleanly, without a precedence-climbing table of special cases. Statements (SELECT, INSERT, CREATE, UPDATE, DELETE) are parsed by recursive descent around the expression parser.

The catalog

The database is self-describing: table definitions live in a catalog stored in the same file, in its own B+-tree keyed by table name. A TableSchema records the columns and their types, the root page of the table's data tree, the next row id, and (as of M8) a row_count statistic for the optimizer. CREATE TABLE writes a catalog entry; every query reads the schema back out of it.

Types and three-valued logic

ferrodb has four types — INTEGER, REAL, TEXT, BOOLEAN — and, like SQL, a first-class NULL. Comparisons and boolean operators follow three-valued logic: NULL = NULL is not true but NULL, NULL AND false is false, NULL AND true is NULL. The evaluator implements these tables so WHERE filters and expressions behave as SQL requires rather than treating NULL as a sentinel value.

The volcano executor

Execution is a tree of operators, each of which produces rows. In M2 this is a simple pipeline: scan a table, filter rows by WHERE, sort by ORDER BY, project the selected columns, apply LIMIT/OFFSET. Each operator pulls from its child — the classic volcano model. INSERT encodes a tuple and puts it into the table's B+-tree; UPDATE and DELETE scan, match, and rewrite version chains (Chapter 5).

This clean operator model is what M5 builds on: the optimizer's job is to choose which operators to assemble and in what order, without changing how any single operator works.

The cost-based optimizer

M5 turns the straight-line executor into a real query engine over a physical plan tree, with a cost-based optimizer that chooses access paths and join order. EXPLAIN prints the plan it picks.

The plan tree

A query compiles to a tree of physical operators: Scan (with an access path), Join (hash or nested-loop), Filter, Aggregate, Sort, Project, Limit. Each node carries an estimated output cardinality (est) used to compare alternatives. run_plan walks this tree to produce rows.

Access paths

How a base table is read is its access path:

• SeqScan — read every visible row.
• IndexSeek — a B+-tree point lookup for a pk = const predicate. One fetch chain instead of a full scan.
• IndexRange — a B+-tree bounded scan for pk >/>=/< predicates (added in M8). It seeks straight to the starting leaf and walks the sibling chain, with lo inclusive and hi exclusive.

Single-table predicates are pushed down onto the scan rather than run as a separate Filter node, so the scan emits fewer rows. For the index paths the original predicate is also kept as a residual filter, so a conservative index bound (for example, > widening to an inclusive lower bound) is always narrowed back to exact SQL semantics.

Cardinality from a statistic, not a scan

The optimizer needs to know roughly how many rows each table has. The obvious-but-wrong way is to count them at plan time — which is what an early version did, walking the whole B+-tree on every query and making a point lookup secretly O(n). The fix is the one every real database uses: keep a statistic. TableSchema.row_count is maintained incrementally on INSERT/DELETE and persisted in the catalog (analogous to PostgreSQL's reltuples), so the planner reads a cardinality estimate in O(1). This single change took 20k-row point lookups from milliseconds to microseconds (see Benchmarks).

Join algorithms and order

An equijoin (a.x = b.y) runs as a hash join: build a hash table on the smaller side, probe with the larger. Without an equality condition it falls back to a nested-loop join.

Join order matters enormously: joining the two smallest relations first keeps intermediate results small. For all-INNER queries of up to eight relations, ferrodb runs a System-R-style dynamic program over subsets of relations, choosing the left-deep order that minimizes the summed intermediate cardinality — so it never leads with the biggest table. A query containing a LEFT join falls back to written order, because reordering an outer join is not generally valid.

EXPLAIN

EXPLAIN renders the chosen plan as an indented tree, most-parent first, with each node's estimated row count and the pushed-down filters. It is how you see the optimizer's decisions:

Project [u.name AS name]  (rows≈1)
  HashJoin [Inner] on u.id = o.user_id  (rows≈1)
    SeqScan orders o  (rows≈3)
    IndexSeek users u (pk = 1)  (rows≈1)

Here the optimizer recognized u.id = 1 as an index seek, made that one-row relation the build side of the hash join, and pushed the predicate down onto the users scan.

PostgreSQL wire protocol

A database that only its own CLI can talk to is a toy. M6 makes ferrodb speak enough of the PostgreSQL v3 wire protocol that the real psql client — or any Postgres driver — can connect over TCP and run SQL. It is implemented by hand: no async runtime, no protocol crate.

Why the Postgres protocol

Implementing an existing, documented protocol means ferrodb inherits a whole ecosystem of clients for free. The v3 protocol is also refreshingly simple to speak at the "simple query" level: it is a sequence of length-prefixed, type-tagged messages over a plain socket.

The startup handshake

Every Postgres client opens with an SSL request before anything else; ferrodb replies with a single byte declining TLS, and the client proceeds in cleartext. The client then sends a startup packet with the user and database name, and the server replies AuthenticationOk, a few ParameterStatus messages, and ReadyForQuery. Now the connection is live.

The simple query cycle

For each Query message (a SQL string), the server runs the statement and replies with:

• RowDescription — the result columns and their types, for a SELECT.
• DataRow — one message per row, each field encoded per its type.
• CommandComplete — a tag like SELECT 3 or INSERT 0 1.
• ReadyForQuery — the server is ready for the next query.

BEGIN / COMMIT / ROLLBACK map straight onto the engine's MVCC transactions (Chapter 5). Any engine error becomes an ErrorResponse message, which psql prints as a normal SQL error.

Concurrency model

The server is deliberately simple: blocking IO, one thread per connection, with the database behind a shared Arc<Mutex<Database>>. This is not how a high-throughput server would be built, but it is correct and easy to reason about, and it is enough to serve concurrent psql sessions. (The Blob trait carrying a Send bound — see Chapter 2 — is what lets the Database cross thread boundaries safely.)

Verifying the framing

The byte-level framing is validated by in-process wire tests that drive the protocol over a loopback socket — open a connection, perform the handshake, send a query, and assert the exact sequence of reply messages — so the protocol is tested without depending on an external psql binary.

WebAssembly playground

The most visual proof that the engine is real: the whole of ferrodb — storage, SQL, MVCC, the optimizer — compiles to WebAssembly and runs entirely in the browser, next to a live B+-tree visualizer that shows the tree split as you insert rows.

The prerequisite: no filesystem

A browser has no File. This is why the storage layer was built on the Blob trait from the start (Chapter 2): the native build backs it with a real File, and the WASM build backs it with a Vec<u8> (MemBlob). Database::open_in_memory() assembles a fully in-memory engine that needs no files at all — and nothing above the storage layer had to change to make the browser build work.

A hand-written C ABI — no wasm-bindgen

crates/wasm is a cdylib targeting wasm32-unknown-unknown with no wasm-bindgen and no dependencies. It exports a tiny C ABI:

• alloc / dealloc — so JavaScript can write an input string into wasm linear memory.
• db_new / db_free — lifecycle of a Database handle.
• db_exec — run a SQL string, return results as JSON.
• db_tree — export a table's B+-tree as JSON.
• free_string — release a returned buffer.

Strings cross the boundary as length-prefixed byte buffers ([u32 len][bytes...]) that the JS reads straight out of wasm memory — the same trick in both directions. The Output → JSON formatting is a pure function, unit-tested on the host. The resulting module (~383 KB) instantiates with zero imports.

The visualizer

web/index.html is a SQL editor with a results table and, beside it, an SVG rendering of the live B+-tree. Database::table_tree walks the physical tree through the buffer pool into a TreeNode { leaf, keys, children }, decoding keys per the primary-key type; to_json serializes it by hand. A small tidy-tree layout (measure subtree widths, place children, center parents) draws it, color-coding internal and leaf nodes. The tree refreshes after every statement — insert rows and you watch a single leaf grow into a root over multiple leaves in real time, the split behaviour from Chapter 3 made visible.

A prebuilt .wasm is committed so the web/ directory can be served as-is; web/build.sh rebuilds it.

Vector search: the HNSW index

ferrodb M9 adds approximate nearest-neighbor search over embedding vectors — the workload behind semantic search and RAG — as a secondary index, integrated the way pgvector integrates with Postgres:

CREATE TABLE items (id INTEGER PRIMARY KEY, category TEXT, embedding VECTOR(768));
INSERT INTO items VALUES (1, 'docs', '[0.011, -0.322, ...]');
CREATE INDEX items_emb ON items USING HNSW (embedding);

SELECT id, category
FROM items
WHERE category = 'docs'
ORDER BY distance(embedding, '[0.02, -0.31, ...]')
LIMIT 10;

EXPLAIN shows the access path the optimizer chose:

Limit 10
  Project [id, category]
    Sort [distance(embedding, [0.02, -0.31, ... (768 dims)]) asc]
      HnswTopK items (distance(embedding, ...) LIMIT 10)

The design splits cleanly in two: crates/vector is a standalone, dependency-free HNSW library (distance kernels → graph → persistence → recall harness), and the engine wires it in as an index — new VECTOR(dim) type, catalog entries, DML hooks, and a planner rule.

The division of labor (the pgvector parallel)

The index maps vectors to row keys — the same order-preserving key bytes the primary B+-tree is keyed by. A search returns candidate keys; the engine fetches each through the B+-tree and applies MVCC visibility. The index never learns about transactions:

• An aborted insert leaves a ghost node in the graph. Search may return its key; mvcc::visible_index sees xmin aborted and drops the row. This is exactly how Postgres treats dead TIDs returned by any index.
• A delete tombstones the graph node: it keeps routing traversals (its links remain load-bearing) but is never returned. Rebuild reclaims it.
• The plan keeps a Sort + Limit above the index scan. The index only proposes candidates; the sort re-orders them exactly and the limit truncates. Approximation can lose a candidate, never misorder one.

The algorithm

HNSW (Malkov & Yashunin, 2016/2018) is a stack of proximity graphs — a skip list generalized to metric space. Every element gets a random top layer floor(-ln(unif(0,1)) · mL) with mL = 1/ln(M): layer 0 holds everything, each higher layer keeps ~1/M of the one below. Search descends the sparse "express lanes" greedily (beam of 1), then runs an ef-wide beam search on layer 0. ef_search is the single recall/latency knob.

The subtle part is neighbor selection (Algorithm 4). Linking each node to its M nearest neighbors fails on clustered data: all links point inside the cluster and greedy search can't cross between clusters. The heuristic keeps a candidate only if it's closer to the new node than to any neighbor already kept — a "does this link cover a new direction?" test that yields long-range bridges. Rejected candidates back-fill unused slots (keepPrunedConnections).

Deviations from the paper, all deliberate: extendCandidates off (paper's own recommendation), tombstones added (the paper has no delete; a database needs one), and layer-0 reachability is asserted by a BFS diagnostic in the harness rather than assumed.

The hot loop: SIMD distance kernels

One search evaluates hundreds to thousands of distances, so the kernel is the whole ballgame. Three metrics (L2 squared — sqrt is monotone, so we skip it; cosine; negated dot so that smaller = closer uniformly), each with a scalar reference implementation and a hand-written AVX2+FMA implementation, selected once per process by CPU feature detection into plain function pointers. unsafe is confined to the kernel bodies with documented obligations; property tests hold SIMD to the scalar reference within a relative epsilon across every len % 8 remainder class (the sums associate differently — bit-exact agreement would actually indicate the SIMD path silently fell back).

Measured on this machine (cargo run -p vector --example distbench --release):

Cosine gains less: three FMA accumulator chains compete for the same ports — which is why normalize-on-insert (store unit vectors, use dot at query time) is the optimization pgvector also performs.

Filtered search: the hero feature

WHERE category = 'X' ORDER BY distance(...) LIMIT k is where a relational engine earns its keep against a bolted-on vector library. The naive approach — run top-k, then filter — has a well-known recall cliff: with a 1% selective predicate, the unfiltered top-10 almost surely contains zero matches.

ferrodb threads the predicate into the traversal: non-matching nodes still route the beam (dropping them from traversal is what strands the search), but cannot enter the result set. The admission test resolves each candidate's row key through the B+-tree and evaluates the predicate under the query's snapshot — so filtering, visibility, and search share one pass. If the beam still comes back short (ultra-selective predicate), ef escalates ×4 until it covers the graph, at which point the "approximate" search has degenerated into an exhaustive filtered scan — exactly the right fallback, and the end-to-end test proves a single matching needle in 300 rows is found.

Persistence: sidecar + mmap, and why not the pager

The B+-tree pages beautifully; an HNSW graph does not — traversal hops between arbitrary nodes, so paging it means WAL-logging every adjacency mutation (pgvector's approach, a milestone of its own). Instead the index is derived data: serialized to a sidecar file (db.hnsw-<table>-<col>) with a checksummed graph section and the vector arena at a 4096-aligned offset, mmap'd on load (raw mmap/munmap declared by hand — no libc crate, per repo ethos). The checksum deliberately excludes the arena: verifying it would fault in every page and defeat lazy loading.

Crash story: the WAL never logs graph mutations because the WAL-protected base table can always regenerate the index. On open, a sidecar that is missing, torn, or stale (its node count disagrees with the table's key count) is discarded and the index rebuilds — REINDEX semantics, proven by tests that corrupt, truncate, and stale-ify the file.

Measured recall (the correctness proof)

HNSW is approximate; without a recall number the implementation is unverified. The harness (cargo run -p vector --bin recall --release) builds over labeled data, computes exact ground truth by brute force, and counts hits by distance (ties in the dataset shouldn't count against the index — the first id-based counter mis-scored duplicate points, a diagnosis the harness now documents). Dataset: clustered synthetic Gaussians, deliberately labeled synthetic, deliberately clustered — uniform random vectors are a misleadingly easy benchmark and clusters are what stress the neighbor heuristic.

n=20,000, dim=64, 50 clusters, M=16, ef_construction=200, k=10, single thread:

Brute force on the same data: 0.7 ms/query (1,386 QPS) — the index is 3–27× faster depending on where you sit on the recall curve. Memory: 8.3 MB (vectors 5.1 MB + graph). On an easy regime (dim=8) the index reaches recall@10 = 1.000 at ef ≥ 40, which is the implementation-correctness signal; the clustered numbers above are the honest hard-mode curve. Build: ~5,000 inserts/s single-threaded.

Limits, honestly

The graph must be resident (vectors can lazily page via mmap; adjacency can't). At 10M × 768-dim that's ~31 GB of vectors — the point where pgvector's paged, WAL-integrated design or quantization (PQ/SQ) becomes the right answer, and the natural next milestone. Writer concurrency is single-threaded behind the engine's existing session model; the index itself supports parallel readers (RwLock, no unsafe). VACUUM does not yet rebuild vector indexes to reclaim tombstones.

Benchmarks

The final milestone measures ferrodb against a mature C database — bundled SQLite — on the same in-memory workloads. The goal is not to win (it does not) but to be honest and reproducible, and to use scale as a forcing function that exposes performance bugs the correctness tests never would.

The harness

crates/bench drives five workloads over a 20 000-row dataset, fully in memory, sending the same SQL strings to both engines with no statement caching — so every number covers the whole parse → plan → execute path. SQLite sits behind an optional sqlite Cargo feature (via rusqlite with the bundled build), so the default workspace build and CI stay dependency-light.

$ cargo run -p ferrodb-bench --release --features sqlite

Two fairness rules matter. Inserts are batched multi-row statements on both sides — ferrodb's no-steal buffer pool bounds a single transaction's dirty set, so a 20k-row load is committed in batches rather than one giant transaction. The aggregate uses WHERE v >= 0 (which matches every row) to force a genuine full scan on both engines, rather than measuring SQLite's special-cased bare-COUNT(*) shortcut.

Representative results

One machine, release build, ferrodb vs bundled SQLite. ratio = ferrodb ÷ sqlite (1.0× = parity, higher = ferrodb slower):

Numbers vary run to run and machine to machine; treat them as orders of magnitude, not lab results.

What the numbers say

The index-driven workloads — point lookup and range scan, the entire reason the M5 optimizer exists — land within a small constant factor of SQLite. That is the headline result: a from-scratch B+-tree with a cost-based optimizer is genuinely competitive on the operations indexes are for.

The full-scan and join workloads are slower, and honestly so. They expose the cost of a row-at-a-time interpreter that materializes each operator's output into a RowSet before the next operator runs. A streaming (iterator/volcano-pull) executor that never materializes intermediate results is the single largest remaining performance lever, and the obvious next step beyond this milestone.

The bugs the benchmark caught

Running the harness at scale immediately exposed two optimizer defects that every correctness test had passed straight over:

1. Cardinality estimation scanned the table. The planner counted rows by walking the whole B+-tree on every query, so a point lookup was secretly O(n). Replacing the live count with a persisted row_count statistic (see The optimizer) took 20k-row point lookups from ~5 ms to ~7 µs each — a ~700× improvement.
2. Range predicates fell back to full scans. There was no index range access path, so WHERE id >= a AND id < b scanned all 20k rows. Adding IndexRange over the existing B+-tree bounded scan cut range queries ~90×.

This is the real argument for benchmarking: not the final table, but the two bugs that only appeared under load.