FM-Index Full-Text Search in a Transactional Engine

Inverted indexes and transactional writes do not coexist easily, and that seam is what pushes most database vendors toward eventually-consistent search sidecars, search daemons, or CDC pipelines that resync the index out of band. We wanted to skip the seam entirely, which meant picking a full-text index structure that the same WAL could cover at the same fsync as the rows it covered, and the FM-index (Ferragina-Manzini, 2000) was the data structure that made the cut.

What an FM-index is, briefly

A Burrows-Wheeler transform turns text into something that compresses as well as the same text runs through gzip, because the BWT groups repeated substrings the same way. The FM-index adds enough suffix-sampling metadata on top of the BWT that you can test whether a pattern is a substring by walking the BWT’s first-column matrix one character at a time, without scanning the original text at all. The asymptotic shape is O(|pattern|) per query against a corpus that is highly compressed on disk.

Inverted indexes, by contrast, store the original tokens uncompressed, hash each token to a postings list, and answer a query by intersecting those postings lists in constant time per term. They are the right choice when your data is largely read-only, your queries are repeated, and you can afford to rebuild the index out of band after writes. They are not the right choice for a transactional engine that wants the index to participate in the same commit as the rows.

What the FM-index bought us at the storage layer

Two things specifically.

The first is write-path simplicity. An inverted index wants to be immutable between commits, which is why transactional inverted indexes need separate WAL coordination, deferred rebuilds, or row-level deltas stitched onto an immutable postings structure. An FM-index in MongrelDB is materialized as a column-level rewrite, batched with the rows it covers, fsync’d through the same WAL, and rolled back by not rewriting it; the index has no separate consistency model because there is no separate index state to coordinate.

The second is the readability of the data on disk. The same BWT that makes the FM-index queryable is the same representation that compresses text well, and MongrelDB’s storage layer already pays for compressed column layouts in the rest of the engine; the search side gets that compression benefit alongside the rest of the engine’s columnar storage without a separate index cost.

That is the trade we wanted: one source of truth, one consistency model, one wire format. The FM-index was the data structure that gave us all three; the inverted index would have given us one and a half and required a separate subsystem for the half.

What we had to give up to get there

Build cost. Inverted indexes get built incrementally as documents are inserted, and the index is correct after every INSERT. The FM-index is meaningful only over a corpus; rebuilding it across a single row is wasteful. MongrelDB batches FM-index rewrites across table-rewrite checkpoints, with the same IndexBuildPolicy::Deferred default the SQL indexes use; this means write amplification on full-text-heavy workloads is higher than on inverted-index engines, and first-query-after-batch latency can spike when a checkpoint has not been built yet. The benchmark numbers are honest about this; the architecture is honest about why.

Pure-pattern ranking. The FM-index gives you containment (does the pattern appear?), not relevance (how much does it matter?). BM25 ranking is available via the mongreldb_fts_rank(text, query) UDF, which computes simplified BM25 from per-row term frequency and approximated corpus statistics at query time; accurate BM25-with-IDF lives in the separate fts_docs virtual table, which is the inverted-index path. That is a hybrid shape, not pure FM-index purity, and we note it because a search-engine purist would.

Where it shows up in the wire format

WHERE body LIKE '%phrase%' in raw SQL, ->whereFts(...) in the Kit query builder, and where('fm', ...) in the PHP fluent builder all dispatch to the same FM-index path through /kit/query. There is no separate search endpoint to point your app at, no separate consistency model to reason about, and no eventual-index lag to defend against in application code. A search query joined against the same WHERE clauses you would write for a regular typed column looks like:

SELECT id, title
FROM articles
WHERE body LIKE '%rust bwt fts%'
  AND published_at > '2026-01-01'
ORDER BY mongreldb_fts_rank(body, 'rust bwt fts') DESC
LIMIT 20;

Same transactional commit at the end of the statement, same WAL coverage for the index update on any INSERT to articles, and the same single-engine consistency model for both the row and the search result.

When this is the wrong tradeoff

If you are running a pure search-engine workload with no transactional semantics on the indexed data, with hot-write patterns the FM-index chokes on, and with strict sub-millisecond p99 on very short queries, an inverted-index engine tuned for that workload is still faster than what an FM-index on a transactional engine gives you; we did not pretend otherwise when we built it. What we wanted was transactional full-text search on the same engine as the rest of your data, on the same wire format, and the FM-index was the right way to spend the storage budget to get it.