When Two-Character Queries Silently Return Nothing: Measuring Japanese Search Indexes in an Expo App

The bigram inverted index cost more in luggage than it saved in speed

Next, the textbook approach: split each normalized key into two-character grams and map each gram to a set of document IDs.

function buildBigram(items) {
  const idx = Object.create(null);
  for (let i = 0; i < items.length; i++) {
    const k = norm(items[i].title + items[i].tags.join(""));
    for (let j = 0; j + 2 <= k.length; j++) {
      (idx[k.slice(j, j + 2)] ||= []).push(i);
    }
  }
  for (const g in idx) idx[g] = [...new Set(idx[g])];
  return idx;
}
 
function queryBigram(idx, keys, q) {
  const nq = norm(q);
  if (nq.length < 2) return null; // ← this line becomes the problem
  const grams = [];
  for (let j = 0; j + 2 <= nq.length; j++) grams.push(nq.slice(j, j + 2));
 
  let cand = null;
  for (const g of grams) {
    const posting = idx[g];
    if (!posting) return [];
    if (cand === null) cand = posting;
    else {
      const s = new Set(posting);
      cand = cand.filter((x) => s.has(x));
    }
    if (cand.length === 0) return [];
  }
  // Gram order isn't guaranteed by intersection alone, so verify against the real string
  return cand.filter((i) => keys[i].includes(nq));
}

Search did get faster: 0.093 ms at 20,000 items, roughly an eighth of the linear scan. The trouble was everywhere else.

The index is nearly the same size as the catalog it indexes — 97% of it at 50,000 items. Making search faster means roughly doubling what you ship. With download size visible on the App Store listing, that isn't a free trade.

Then my correctness check against the linear scan disagreed:

MISMATCH 20000 滝  linear=708 hits  bigram=0 hits

That is the nq.length < 2 early return. A single character produces no bigrams, so the index cannot represent the query at all. In Japanese, single-character queries are ordinary — 猫 (cat), 桜 (cherry blossom), 月 (moon), 海 (sea). The moment I added the index, that entire class of query disappeared.

So far this is my own implementation's flaw. The next part was not.

FTS5 trigram drops anything shorter than three characters, without complaint

Assuming my hand-rolled index was simply sloppy, I moved to SQLite FTS5. It's available through expo-sqlite, and it ships a trigram tokenizer specifically for CJK text. Delegating to a well-tested implementation felt like the safer path.

# Load 20,000 rows into a trigram table and compare against a plain table
c.execute("CREATE VIRTUAL TABLE s USING fts5(id UNINDEXED, k, tokenize='trigram')")
c.executemany("INSERT INTO s VALUES (?,?)", rows)
 
c.execute("CREATE TABLE plain(id TEXT, k TEXT)")
c.executemany("INSERT INTO plain VALUES (?,?)", rows)
 
for q in ["夜景", "猫", "桜", "星空の", "高解像度"]:
    m = c.execute("SELECT count(*) FROM s WHERE k MATCH ?", ('"' + q + '"',)).fetchone()[0]
    l = c.execute("SELECT count(*) FROM plain WHERE k LIKE ?", ('%' + q + '%',)).fetchone()[0]
    print(q, len(q), m, l)

The output:

No exception. No warning. A query under three characters cannot form a single trigram, so it quietly resolves to the empty set. That is a reasonable consequence of the design, but on screen it is indistinguishable from a genuine miss. To the user, the app simply has no cats.

The name trigram tells you it indexes in units of three characters. It does not tell you that fewer than three cannot be queried — that's the implication on the other side. In English, cat is three characters, so the issue never surfaces. In Japanese it's one. That asymmetry is the whole trap.

One more thing needs correcting. The first version of this article said that LIKE against the virtual table returns 0. I re-ran it on SQLite 3.53.1 and that was wrong: on a trigram table, LIKE does substring matching and returns the right count.

-- LIKE on the FTS5 virtual table (trigram)
SELECT count(*) FROM s WHERE k LIKE '%猫%';   -- returns a count, even for one character
SELECT count(*) FROM s WHERE k MATCH '"猫"';  -- returns 0

I noticed only when I went to rebuild the hybrid table and pointed LIKE straight at the virtual table. The original run used SQLite 3.37.2, and I have not checked that version again, so I am only vouching for what I re-ran.

I then measured short queries two ways: LIKE on the virtual table, and LIKE on an ordinary table holding the same rows. The catalog is a fresh synthetic one (20,000 items), so the hit counts differ from the table above. Compare columns within this table, not across the two.

Below three characters the index cannot help, so LIKE on the virtual table becomes a full scan — about twice the plain table's time in this environment. A separate plain table for short queries therefore buys speed, not correctness. If roughly 3 ms is acceptable, you can skip storing the data twice.

Going hybrid meant the slow path set the pace

The obvious fix is to branch on query length: FTS5 for three characters and up, plain-table LIKE below that. I wrote it and measured it.

Correctness came back. But looking at the table, I stopped.

The JavaScript linear scan over the same 20,000 items runs in 0.80 ms. The slow path here (4.7–5.3 ms) is roughly six times that. Even the fast path degrades to 4.46 ms once the hit count grows.

At this scale, every path through SQLite lost to the naive scan. The theoretical advantage of an index simply doesn't materialize at 20,000 items — the fixed costs of serialization and crossing the bridge dominate instead.

The FTS5 database file was 3.3 MB at 20,000 items and 9.4 MB at 50,000. Insertion took 252 ms and 628 ms respectively. What that expense bought me was search that was slower than the scan it replaced.

The decision rule I now use:

Decide on an index only after measuring short queries and startup cost, not search speed. I reread that line before every design now.

The real bottleneck was startup normalization, not search

I had been measuring query latency the whole time, which in hindsight was the comfortable thing to measure. What actually governed the feel of the app was elsewhere: the pass that normalizes every record at load.

39.5 ms at 20,000 items — forty-nine times a single 0.80 ms query. I had spent a weekend shaving 0.8 ms down to 0.09 ms while ignoring the 39.5 ms sitting directly in front of it.

It also occupies the JavaScript thread. Apply the device correction and you are past 100 ms; at a hundred thousand items, startup becomes visibly heavy.

The fix was simple: normalize at build time and ship only the result.

// scripts/build-search-keys.mjs — runs once, at build time
import fs from "node:fs";
 
const norm = (s) =>
  s
    .normalize("NFKC")
    .toLowerCase()
    .replace(/[ァ-ヶ]/g, (c) => String.fromCharCode(c.charCodeAt(0) - 0x60))
    .replace(/\s+/g, "");
 
const items = JSON.parse(fs.readFileSync("assets/catalog.json", "utf8"));
 
// Emit one newline-delimited string; line number maps to catalog index
const keys = items.map((it) => norm(it.title + it.tags.join("")));
if (keys.some((k) => k.includes("\n"))) {
  throw new Error("A normalized key contains a newline — pick a different delimiter");
}
fs.writeFileSync("assets/search-keys.txt", keys.join("\n"));
console.log(`wrote ${keys.length} keys / ${Buffer.byteLength(keys.join("\n"))} bytes`);

The app just reads and splits.

import { Asset } from "expo-asset";
import * as FileSystem from "expo-file-system";
 
let KEYS = null;
 
export async function loadSearchKeys() {
  if (KEYS) return KEYS;
  const asset = Asset.fromModule(require("../assets/search-keys.txt"));
  await asset.downloadAsync();
  const raw = await FileSystem.readAsStringAsync(asset.localUri);
  KEYS = raw.split("\n");
  return KEYS;
}
 
export function searchByKeys(nq) {
  const hits = [];
  for (let i = 0; i < KEYS.length; i++) {
    if (KEYS[i].indexOf(nq) >= 0) hits.push(i);
  }
  return hits;
}

I chose newline-joined text over a JSON array because it measured faster and smaller: at 20,000 items, JSON.parse took 1.6 ms over 1,118 KB while split took 1.1 ms over 1,078 KB. At 100,000 items the gap widens to 7.5 ms versus 3.9 ms. Dropping the quotes and commas earns exactly what you'd expect.

Since newlines are the delimiter, a newline inside a key shifts everything after it. Guard for that in the build script. I skipped the check once, a single tag contained a newline, and every index after that record was off by one. Search results showed the neighboring wallpaper for every hit — an unsettling bug until the cause surfaced.

What I settled on

The wallpaper app I maintain as an indie developer holds roughly 24,000 items today. Its current shape:

FTS5 is gone. I'll revisit it when the catalog is four times larger and measurements actually breach the frame budget — and I'll build the short-query table on day one.

The branch points, laid out. Please re-measure in your own environment before adopting any row.

If you generate this part with Rork or Expo tooling, "add search" alone will import English-language assumptions. I now hand over the specification instead:

Implement in-app search with these requirements.

- Search over a precomputed key array (read assets/search-keys.txt, newline-delimited)
- Normalization: NFKC → lowercase → katakana to hiragana → strip whitespace. Apply the same function to the query
- Single-character queries must work. Do not use n-gram indexes or the FTS5 trigram tokenizer
- Debounce input at 200ms; cancel the previous search via AbortController or equivalent
- On zero results, show three suggested tags rather than a bare "no matches" message

That third line is there because of this incident. I now check whether a single Japanese character returns anything before I check whether the generated code is fast.

Where to start

If your app has search, type one single-character query. Pick a subject your users actually look for. Either results come back or they don't — and that alone tells you whether the index was designed with Japanese in mind.

Then measure startup preparation rather than query latency. In my case there were 0.7 ms available on the search side and 38 ms on the startup side. Where the time actually hides isn't knowable until you measure.

Every number here came from running the code myself. The ratios should transfer; the absolute values deserve a check on your own device. Thank you for reading.