Phase 5 — Capabilities: Vector Search

Overview

Phase 5 grows the platform by the Capabilities deciding rule (spec 12, roadmap §Phase 5): storage/execution capabilities go INTO the engine; interface/service capabilities are COMPOSED AROUND it. The one capability that is built in is vector search; the three that are composed around (better-auth, PostgREST, DuckDB) are adopted unmodified and demonstrated as glue, never welded into the core.

Everything is additive and the storage seam never moves: ENGINE_ABI_VERSION goes to 3 (the vector type, HNSW, distance operators, and the v… bind encoding — no C symbols added or removed), while STORAGE_TRAIT_VERSION stays 2. The vector index needs no new storage capability: it rides the existing append_wal/replay path exactly like the rows do.

Built IN — vector search (the headline)

Why it branches / scales-to-zero / S3-backs for free

The engine is WAL-centric: rows are not stored as pages, they are replayed from the durable WAL into the in-memory MVCC store on open (db.rs::replay). The vector index is built the same way — it is a derived structure over the column's vectors, not a side file. The only durable artifacts are the CreateIndex/DropIndex WAL ops (wal.rs) and the vector values themselves; the graph is rebuilt by Store::rebuild_indexes after replay (the index's cold-start "warm"). Three properties fall straight out, with no special-casing:

• Branching branches the index (spec 12's differentiator, gated by tests/vector.rs::branch_branches_the_vector_index and the Bun branching forks the vector index test). A branch is a BranchStorage whose replay includes the parent's CreateIndex + the in-window inserts, so the branch rebuilds its own graph; its diverged writes never touch the base.
• Scale-to-zero: idle compute drops, the next open replays the WAL and rebuilds the graph — the warm is the replay.
• S3-backing / PITR: the vectors and the index definition are LSN-versioned WAL records like everything else, so the object backend and point-in-time window cover them unchanged (s3:// works with no recompile, same as rows).

MVCC + index maintenance

The index maps vid -> vector for every row version that has one; visibility is resolved at query time against the row version the vid identifies, so the index stays MVCC-agnostic. Inserts/updates add the new vid (Store::index_row_inserted); deletes need no index change (the row version's delete_lsn filters it out); a rolled-back pending insert is tombstoned out (Store::rollback_pending). The KNN scan over-fetches (KNN_OVERFETCH) to absorb invisible/filtered hits, then takes the first k that pass WHERE and snapshot visibility.

SQL surface added

• embedding VECTOR(768) column type (dimension required, validated).
• Vector literals [1, 2, 3] and '[1,2,3]' text coercion (pgvector-style).
• CREATE INDEX name ON table USING hnsw (col [vector_cosine_ops]) [WITH (m=…, ef_construction=…, ef_search=…, metric='cosine'|'l2'|'inner_product')] and DROP INDEX [IF EXISTS] name (autocommit DDL, like CREATE TABLE).
• Distance operators usable in projection, WHERE, and ORDER BY. Without a matching index the query still works as a brute-force scan + sort (the operator evaluates per row); with one it is answered by the access method — same results, proven by tests/vector.rs::hnsw_index_answers_top_k_and_matches_brute_force.

Composed AROUND — placement, not core code

Per the rule, none of these enter the engine binary; the core stays "rows + vectors + the storage trait". They are demonstrated as the thin glue we own:

• better-auth (service, in-process). The real library runs in-process against a Twill database adapter (clients/bun/src/better-auth.ts) that stores users/sessions/accounts as ordinary rows — no external auth service, and because it is rows it branches and recovers with the database. The adapter maps better-auth's CRUD contract onto the SQL subset (OR-chain for IN, client-side OFFSET, literal LIMIT). Exercised end-to-end (sign-up/sign-in/session + branch isolation) in clients/bun/test/better-auth.test.ts; runnable demo clients/bun/examples/auth-app.ts. The conceptual shape also appears in compose.ts.
• PostgREST (interface, in front). Attaches over server mode (pgwire, Phase 3) with zero engine changes — wire-compatibility is the contract. Absent in embedded deployments; nothing to build here.
• DuckDB (OLAP, over shared storage). A second engine over the same floor. The only code we own is the materialization job (clients/bun/src/olap.ts): snapshot a table to an open columnar file (Parquet) on the shared store, atomically (temp + rename), on a configurable cadence (Materializer); DuckDB reads it directly. DuckDB is also the off-the-shelf Parquet writer the job shells out to, falling back to CSV (read_csv_auto) when it is absent. Verified end-to-end in clients/bun/test/olap.test.ts (CSV export + atomic publish always; the Parquet→DuckDB aggregation round-trip where the DuckDB CLI is installed, reported skipped otherwise); runnable demo clients/bun/examples/duckdb-olap.ts. The conceptual shape also appears in compose.ts.

Tests

• crates/engine/tests/vector.rs — type round-trip + dimension validation, the three distance operators (brute force), HNSW top-k vs brute-force parity, WHERE-filtered + MVCC-correct KNN, branch isolation of the index, rebuild from WAL on restart, rollback tombstoning, exact nearest over a larger set, and the CREATE INDEX guards.
• crates/engine/tests/ffi.rs::vector_search_via_c_abi — the vector type, an HNSW index, and a v…-bound query through the same C ABI bun:ffi binds.
• clients/bun/test/vector.test.ts — the embedded path end-to-end, including the branch-the-memory payoff. Examples: vector-memory.ts, compose.ts.

Deliberate scope boundaries (documented, not accidental)

• The index is derived, not a side file. Spec 12 says "store the graph as pages, not a side file"; the engine's rows are themselves WAL-derived in-memory state, so the consistent realization is a WAL-derived index — same durability path, same branch/scale-to-zero semantics, never a side file. The literal page layout is a cold-read optimization, now realized additively (see Vector hardening below), not a separate durable graph.
• Composed engines are adopted, not vendored. better-auth/PostgREST/DuckDB are external; Phase 5 builds only the glue (the vector capability and the materialization job), per spec 12's "build only thin glue".
• SQL subset unchanged otherwise. Joins, GROUP BY, subqueries, and DISTINCT remain out of scope; ORDER BY ranks by expressions, not output aliases.

Vector hardening (#89)

The three "MAY"/open-question items above are now implemented — additively, with the storage seam untouched (STORAGE_TRAIT_VERSION stays 3, ENGINE_ABI_VERSION stays 3). Branching and scale-to-zero still rebuild each branch's graph from its own WAL (the warm is the replay), gated by tests/vector.rs::branch_branches_the_vector_index.

• VH-3 — recall tuning surface (#99). ef_search is now a per-session knob: SET twill.vector_ef_search = N (and TO N / TO DEFAULT), RESET twill.vector_ef_search, and SHOW twill.vector_ef_search. The value threads through run_select → knn_select → VectorIndex::search as a pure parameter binding — no shared or durable state, so branching/scale-to-zero are unaffected. The recall/latency trade-off is documented with a measured curve in spec 12.
• VH-2 — incremental maintenance under delete churn (#98). A committed delete/supersede marks its index node head-deleted (still navigable, still returned so older snapshots stay correct; the executor re-checks MVCC visibility). Two levers then keep recall up: KNN over-fetch widens by the dead/live ratio, and once head-deleted density crosses ~20% of a graph of ≥64 nodes a compacting rebuild fires automatically (off the read path, on the single-writer commit path) dropping the dead nodes. The compaction records a floor LSN; a snapshot below it falls back to a brute-force scan, so snapshot isolation is preserved across compaction (tests/vector.rs::old_snapshot_survives_compaction).
• VH-1 — page-laid-out index (#97). A freshly built graph is checkpointed as fixed-size, LSN-versioned page images through the existing put_page/get_page contract (the trait never learns "index page vs row page"). A cold open adopts the checkpoint when it exactly reflects the replayed head, loading the graph in bounded page reads instead of replaying every vector through HNSW insertion; a missing, stale, or branch-private checkpoint simply takes the rebuild-from-rows path, so correctness never depends on the pages.

Related