Unicode text normalization for search and sorting

[MA2153]

Unicode text normalization for search and sorting

Type: Feature — new packages/core/src/text/, then a migration and a change to how the FTS index is populated

Recording the design behind #2862 (approved privately, no public thread until now) and — more importantly — surfacing the five decisions the next PR can't be written without. #2862 is unit-tested infrastructure with no call sites; everything below is about what wiring it actually costs.

Problem

Sorting is wrong. SQLite, and therefore D1, compares TEXT with BINARY collation. ORDER BY display_name files Adam, Zoe, alice, Álvaro in that order. Raised in review on #2352 (discussion_r3765977657), which also flagged that ORDER BY and the keyset cursor predicates have to share one set of semantics or pagination skips and duplicates rows. D1 has no ICU collations and Intl.Collator yields a comparator, not a storable key, so the ordering has to be baked into a key computed in JS on the write path.

Search under-matches. FTS5's unicode61 does no Unicode normalization, so NFC and NFD spellings of a word tokenize differently, and its remove_diacritics 1 covers a Latin-1-ish subset. Arabic harakat, tatweel, Farsi ZWNJ and Arabic-Indic digits pass through untouched: ٢٨ never reaches 28, مُحَمَّد never matches محمد. unicode61 also swallows a whole Thai or Chinese sentence as a single token.

Both are fixed by normalizing in JS before text reaches SQLite, which also gives Postgres — where there is no FTS path at all today — the same behavior.

Goals

• One normalization that runs identically at FTS index time, FTS query time, and sort-key write time.
• Alphabetical ordering under a binary collation, tailorable per locale, storable in an indexed column.
• No new queries on the logged-out hot path.
• No ICU dependency; works on workerd.

Non-goals

• Full UCA/CLDR conformance. Chinese sorts by code point not pinyin; Japanese by kana not reading (which can't be derived from the text); Thai skips leading-vowel reordering; French skips backwards accent comparison.
• Stemming. FTS5's porter unicode61 stems inside SQLite. What's often called "Arabic stemming" — harakat removal, alef/yeh unification, digit folding — is normalization and belongs in the shared layer.
• Changing the public search API's query syntax.

What #2862 already contains

normalize.ts holds the shared folds. The two pipelines diverge after it, because one function for both would be wrong:

	Search	Sorting
Case folding	always locale-invariant, so İSTANBUL matches istanbul	Turkish keeps ı and i distinct
Collisions	harmless, a near miss returns one extra row	need a unique tiebreaker; ties break cursor pagination
Durability	derived index; a change costs rebuildIndex	persisted key; a change costs a backfill migration
Ta marbuta ة→ه	applied, for recall	not applied, it merges distinct names
Locale order	one invariant fold	tailored (å after z in Swedish, ch after h in Czech)

Mark removal is an allowlist, not \p{M} — stripping every combining mark deletes Devanagari matras and Thai vowel signs, which are letters, not accents. Sort keys are fixed-width two-character collation elements (a→a0, Polish ą→a1, Swedish å→{0) so a plain BINARY comparison reproduces alphabetical order.

---

Decisions needed

1. Where does index-time normalization run?

This is the blocker. The FTS index is populated by SQL triggers (fts-manager.ts), which insert NEW.<col> straight into the FTS table — the file says so: "Extraction must live in SQL because the sync triggers cannot call into JS." A JS searchIndexText() has nowhere to run at index time as the system is built today.

	Cost
A. Drop triggers, populate FTS from the repository layer in JS	Every direct-SQL writer — migrations, seed, CLI import, snapshot restore — silently stops maintaining the index unless it routes through the repo
B. Normalized shadow column per searchable field on ec_*; triggers copy it into FTS	Keeps triggers authoritative and bm25 per-column weights intact. Roughly doubles stored bytes for searchable fields
C. One _search_text column per content table, all searchable fields concatenated	Cheapest schema. Loses per-column bm25 weighting and per-column snippet() targeting
D. Normalize at query time only	No migration, and actively worse: the query gets folded, the index doesn't, so recall drops

Leaning B. It's the only one that leaves the trigger architecture — and migration 039's hard-won corruption fixes — alone.

2. What does snippet() show?

query.ts:323 returns snippet(fts, 2, '<mark>', '</mark>', '...', 32) to the API, and the FTS table deliberately stores its own copy so snippets read as prose. Index normalized text and snippets become lowercase and unaccented; for CJK/Thai they become bigram soup:

searchIndexText("東京都は日本の首都です")
→ "東京 京都 都は は日 日本 本の の首 首都 都で です"

snippet() highlights by token offset in the indexed column, so pointing it at a raw UNINDEXED copy gives correct prose with no <mark>. Three ways out: accept degraded snippets, return raw text unhighlighted, or reconstruct highlights client-side from the matched terms. I don't have a confident recommendation here and would like one before B is built.

3. Sort keys assume BINARY collation. Postgres doesn't use it.

The scheme's separator element is two spaces. Under a typical en_US.UTF-8 Postgres collation, spaces and punctuation are ignored at the primary level, so "a0 b0" vs "a0a0" orders one way under BINARY and the other under glibc — silently, with no error. The sort-key column needs COLLATE "C" in the migration and a dialect test that asserts it. Cheap to do, easy to forget, impossible to fix after keys are stored and paginated against.

4. Non-BMP characters break the fixed-width invariant and JS/SQLite agreement

defaultElements emits ${ch}0, which is three UTF-16 units for a supplementary-plane character, so every element after it misaligns. Worse, JS compares UTF-16 code units while SQLite compares UTF-8 bytes, and they disagree whenever a key mixes surrogates with U+E000..U+FFFF. Against real node:sqlite:

keys:   sortKey("z"), sortKey("\uE000"), sortKey("\u{2000B}")
sqlite: "z0"  <  "\uE0000"  <  "\u{2000B}0"      (UTF-8 bytes, i.e. code point order)
js:     "z0"  <  "\u{2000B}0"  <  "\uE0000"      (UTF-16 units, surrogates sort low)

That lands directly on the cursor obligation from #2352: a keyset cursor compared in JS will not agree with the database's ORDER BY. Options: bucket all supplementary-plane characters under one BMP sentinel primary (restores both invariants, collapses ordering within the bucket to the id tiebreaker — affects rare CJK extensions and historic scripts), or accept the divergence and document that cursor comparison must happen in SQL. Either way the tests should run ORDER BY through a real SQLite and a COLLATE "C" Postgres instead of Array.toSorted, which is what would have caught this.

5. Bigrams for scripts without word boundaries

Indexing CJK/Thai runs as overlapping bigrams is deterministic and needs no ICU or custom tokenizer, and index and query go through the same function so both sides segment identically. It costs roughly 1.8× the tokens and stored bytes for those scripts, and a 3-character query becomes an implicit AND of two bigrams, so it can match documents where the bigrams aren't adjacent. Fine by me for recall-oriented search; worth an explicit yes.

---

Also worth knowing

• Query-time normalization can't wrap escapeQuery wholesale. It deliberately passes FTS5 operators through, and FTS5 requires AND/OR/NOT/NEAR uppercase. Normalize terms, not the query string.
• Persian ZWNJ → space matches Lucene's PersianCharFilter, but it's asymmetric: می‌رود indexes as two tokens, میرود as one, and neither query finds the other.
• sr-Latn is tailored, bare sr is not, so Serbian Cyrillic (the default script) gets code-point order, which misplaces ђ ј љ њ ћ џ. Tailor it or document it.
• NFKC runs before the digit-run scan, so 10² sorts as the number 102 and ½ as 12.
• Three tailoring bugs found in review are already fixed on the branch: Ukrainian й folding onto и, Turkish î filing under dotless ı, and Greek final sigma splitting from medial sigma in both pipelines.

Rollout sketch

Sort keys land as an additive nullable column plus a forward-only backfill, SORT_KEY_VERSION stored alongside so stale keys are detectable; old code tolerates the new column and new code tolerates an incomplete backfill, so ORDER BY has to fall back to the raw column while sort_key IS NULL. Search needs no migration beyond decision 1's schema — the index is derived, so a change to the folds costs a rebuildIndex, not a migration.

Happy to split any of the five out into its own thread if that's easier to decide.