Full-text search

Full-text search in Arkeion is native: MATCH, BM25 ranking and snippet() / highlight() are built into the engine, and the inverted index lives inside the same encrypted, versioned file as your rows. There is no second service to run and no separate index to keep in sync. Because the index sits in the same copy-on-write history as everything else, MATCH … AS OF searches the past, and the index survives vacuum — both for free.

Native, not a second index

The usual way to add search is to stand up a separate index — SQLite’s FTS5, or a search engine alongside your database. That forces two stores to stay in sync: every write has to update both, and a crash in between leaves them disagreeing. Worse, for private data you now hold the content twice, and the second copy is often a plaintext index sitting outside your encrypted store.

Native search removes that whole class of problem. The inverted index is written in the same transaction as the row, with the one fdatasync every Arkeion commit already pays, so it can never diverge from the data. It inherits encryption, backups, time-travel and the audit chain at no extra cost — one encrypted file, no second copy of your content.

The inverted index

Underneath, full-text search is an inverted index. A normal index maps a row to its values; an inverted index maps each term to the list of documents that contain it (a “document” is a row; each indexed column is tokenised independently). Text comes in, is broken into terms, and every term points at the rows where it appears.

Rows become terms; the dictionary stores each term once as a short id; posting lists point each term id at the rows that hold it.

The tokeniser

The tokeniser turns text into terms. It is deterministic and model-free (not an LLM tokeniser): the same row always produces the same terms, which is what makes the index auditable. It is dependency-free and contains no unsafe code — everything comes from the standard library.

Two built-ins ship today:

unicode (default): a term is a maximal run of alphanumeric characters, lower-cased, with hand-written diacritic folding (café → cafe, ñ → n, ß → ss, œ → oe, …) across the common European ranges.
ascii: ASCII alphanumerics only, lower-cased, no folding — faster when you don’t need it.

The tokeniser is a trait, so language-specific stemmers or an address-aware tokeniser (splitting bob@example.com into bob, example.com and the whole address) can be added later without changing the default. Each token records its byte offsets into the original text, so snippet() and highlight() can underline the exact match without storing offsets in the index.

How it’s stored

An FTS index is a special kind of secondary index: the same versioned b-tree and the same maintenance on every insert, update and delete — but with a finer grain, one entry per token instead of one per column value. To keep it from interfering with ordinary indexes, full-text data lives in its own key range, split into a dictionary, the postings, and the statistics BM25 needs.

Three parts in one key range: a dictionary so terms aren't repeated, term-major postings, and the counts BM25 needs.

The pieces:

Term dictionary. Each term is stored once and mapped to a 4-byte id. Postings are keyed by that id, so the word itself never repeats in a posting. A term* prefix search becomes a range scan of the dictionary that returns the matching set of ids.
Postings. One cell per (term, row), keyed by (term id, row id). The value holds, for each field, the token’s positions as delta-varints (field, count, pos0, Δpos…). A prefix scan over one term id yields every (row, positions) for that term. Keeping one cell per (term, row) — rather than one packed blob per term — is what keeps updates and deletes clean single-cell operations, which is exactly what copy-on-write and snapshot isolation want.
Statistics. BM25 needs three counts: each document’s length, the average length across the index, and the document frequency (df) of each term. These are maintained incrementally as rows change, so they never have to be recomputed at query time.

The index definition (name, columns, tokeniser) is stored inside the table schema, so maintenance sees the index without an extra lookup on every write.

Prefix compression

The lever that made the index small is b-tree prefix compression at the leaf level. Every posting cell for a given term begins with the same key prefix — the full-text tag plus the term id, about nine bytes. Instead of repeating that prefix in every cell, the leaf stores it once per page and each cell keeps only what differs (the row id). Row ids and term ids are stored variable-length and order-preserving rather than in fixed 8- and 4-byte fields.

Prefix compression is what brought the index below FTS5 — pure storage encoding that leaves the logical model, the incremental writes and versioning untouched, and helps every index, not just full-text.

Ranking with BM25

MATCH finds the rows; BM25 orders them. It is the standard relevance score, and it balances three ideas: a term that appears more often in a row counts for more (term frequency), a term that is rare across the corpus counts for more (inverse document frequency), and a hit in a short field counts for more than the same hit in a very long one (length normalisation). All three inputs — term frequency, document length, average length and df — come straight from the posting value and the statistics keys.

SELECT id, snippet(body, 'index'), bm25(body, 'index') AS rank
FROM docs
WHERE body MATCH 'index'
ORDER BY rank DESC
LIMIT 10;

When a query is a MATCH ordered by bm25(...) with a LIMIT, the ranking is computed straight from the index and only a short list of top rows is fetched and re-scored exactly — so most matching rows are never read or re-tokenised. The same BM25 formula backs both this fast path and the per-row bm25() function, so they can’t drift apart. snippet() and highlight() re-tokenise just the rows you’re showing to place the markers, using the byte offsets the tokeniser recorded.

The query language

The string on the right of MATCH has its own small grammar, close to FTS5’s:

terms — index
boolean — index AND rust, index OR search, index NOT stale
phrase — "inverted index"
prefix — index*
proximity — NEAR(index rust, 5)
per-column — title:index

Time travel, and surviving vacuum

Because the index is an ordinary citizen of the copy-on-write history, two useful things come for free. MATCH … AS OF VERSION n searches the index as it was at an earlier version — full-text search over the past, not just the data. And vacuum, which reclaims superseded versions, keeps the current index intact with no special handling, because there is no separate store to rebuild.

Performance

Measured on 50k MS MARCO passages, embedded and in-process, against SQLite FTS5 on the same machine:

	earlier format	Arkeion	SQLite FTS5
Index size	146 MB	26.2 MB	27.2 MB
Build	63 s	11 s	0.6 s
Common-term query	25.6 ms	2.5 ms	1.1 ms
Prefix / phrase query	9.3 / 9.1 ms	1.4 / 2.6 ms	0.5 / 0.6 ms

Read it honestly. The index ended up smaller than FTS5’s (26.2 vs 27.2 MB) — a versioned, encrypted, time-travelling store beating a specialised C engine on compactness. Where FTS5 still wins is build speed and query latency: its packed segments build and scan faster than one b-tree cell per posting. The trade buys something FTS5 can’t offer — search that is provable, encrypted, and addressable in the past — with none of the two-store synchronisation risk.