Search that finds the middle of a word, and the migration that broke production

A Freesbe user searched for “voice” and didn’t find the message about the invoice. Another searched in Hebrew, where “the” is a letter glued to the front of the word, and found nothing because every message said “the meeting” and they typed “meeting”.

Both had the same cause. Our search was a classic full-text index: it splits text into words and matches whole words or the start of a word. That’s how most search works, and it’s fine for English most of the time. It fails for words inside other words, for languages that attach prefixes, and for compound-word languages like German and Dutch.

The decision: a trigram index next to the word index

Messages live in SQLite, and SQLite’s full-text engine (FTS5) has a trigram tokenizer. Instead of indexing words, it indexes every run of three characters. “invoice” becomes inv, nvo, voi, oic, ice. A search for “voice” looks for voi, oic, ice next to each other, and finds the invoice.

We kept the word index and added the trigram index beside it:

• Terms of three letters or more search the trigram index, so they match anywhere in a word.
• One- and two-letter terms can’t be looked up by trigram, so they still use the word index and match the start of a word.
• Both ignore accents (remove_diacritics), so “cafe” finds “café”.

File names went into the same search text, so searching “budget” finds Q4-budget-final.xlsx.

What we turned down

• An external search cluster. Elasticsearch or OpenSearch would do this and more, but it’s a second system to keep in sync with every message edit and delete, in every data region.
• LIKE '%voice%'. Correct, but it reads every message. Fine for a demo, slow for a real workspace.
• Language-specific stemmers. Great for one language, wrong for a product that ships in 25. Trigrams don’t care what language they’re looking at.

The cost is size: a trigram index is bigger than a word index. For chat messages, which are short, it was a price worth paying.

The migration that broke production

The change itself was one migration. Our first version of it did three things in this order:

1. Create the trigram index and the triggers that keep it in sync with the messages table.
2. Fill the index from the existing messages.
3. Update existing messages to add file names to their search text.

Step 3 broke production deploys with SQLITE_CORRUPT_VTAB.

Here’s why. The trigram index is an “external content” index: it doesn’t keep its own copy of the text, it reads from the messages table. When a message’s text changes, the update trigger tells the index “remove the old text for this row, add the new text”. To remove the old text, the index needs to have held it in the first place.

In our order, the update ran against rows where the old text in the index and the old text in the table could disagree. Telling an external content FTS index to delete something it doesn’t hold corrupts it. And our CI didn’t catch it, because CI runs migrations on an empty database, where there’s nothing to update.

The fix, and the rule

We reordered the migration:

1. Rebuild the existing word index first, so it matches the table exactly.
2. Update the messages (add file names) before the trigram index or its triggers exist.
3. Create the trigram index and fill it from the table in one rebuild.
4. Only then create the triggers.

The rule we now follow for any migration that touches full-text search: never update indexed columns while an out-of-sync FTS trigger exists. Backfill, create, rebuild, then triggers.

And a broader one: if a migration changes existing rows, test it on a database that has rows. An empty database will happily pass a migration that can’t survive real data.

The result

Search now finds the invoice, the meeting with “the” glued to it, the German compound word and the spreadsheet by name. See Search and shortcuts in the help center for exactly what counts as a match.