Five indexes, five different answers: what a two-character search query costs in SQLite and D1

A shop directory I look after has a search box in its header. At three thousand rows it was instant, and the code that made it instant is one line:

SELECT id, name, price FROM shops WHERE name LIKE '%' || ? || '%' LIMIT 20; 

At two hundred thousand rows the same line takes 21.9 ms locally for a term with six thousand matches, and the LIMIT does not save it: the scan runs until it has visited enough rows, so a common word stops early at 0.17 ms while a rare one pays the entire 21.9 ms. And that is not mainly a latency problem. The application sits on a database that answers one query at a time, so 22 ms per search is a ceiling of about 45 searches per second for the entire database — every page view, every write, every admin lookup standing in the same queue behind a header search box.

I spent a morning measuring what that line actually costs, and what the three obvious replacements cost instead. The measurements below are from SQLite 3.46.1 in Python 3.12, on 200,000 to 1,000,000 synthetic Korean shop rows, on the same engine that backs D1. The numbers are specific to that machine; the ratios were stable across every run, and the shapes are what you should carry to yours.

The finding that changed the design was not a speed number. It was this table, where seven search strings are answered five different ways by five indexes over the same 200,000 rows:

Seven queries, five indexes, and only one of them agrees with LIKE on every row. Two of the five return zero rows and no error for a query that has thousands of matches. That is the part worth an article: the failure is silent, it is invisible in development, and it is specific to languages whose words are short enough that "three characters" is more than the user types.

How I measured

Two things you cannot get from a stopwatch on a warm cache: how much work a query did, and whether the work depended on the rows it happened to find. SQLite exposes the first through the progress handler, which fires every N virtual-machine instructions:

def vm_steps(conn, sql, params, every=100): n = [0] conn.set_progress_handler(lambda: (n.__setitem__(0, n[0] + 1), 0)[1], every) try: rows = conn.execute(sql, params).fetchall() finally: conn.set_progress_handler(None, 0) return n[0] * every, len(rows) 

The instruction count is the honest cost: it does not depend on whether the page cache was warm or whether the CPU was busy. Wall time I report as the minimum of five runs, because I care about the floor, not the average of a shared machine.

The corpus is 200,000 rows of (id, name, name_en, category, price), where name is a Korean surname + given name + 식당/분식/카페 plus a dish such as 김치찌개, so substring frequencies resemble a real directory. The schema has one index, idx_name ON shops(name).

A B-tree cannot find a substring, and the numbers are boringly linear

LIKE '%김치%' is a scan, and there is no schema change that makes it not a scan. A B-tree is ordered by prefix, so it can answer "starts with" and "between". It cannot answer "contains" without visiting every entry, because a match may begin at any offset.

The measured cost per row is almost exactly constant: 4.1 VM instructions per row, across four orders of magnitude of table size, for a query with a 600-row result set:

Linear is the good news. Linear means you can predict it, and my rule of thumb is now about 10 ms per 100,000 rows per LIKE '%…%' column on a laptop-class core, which on a hosted database with a slower core and a network hop in front of it you should triple before quoting to anyone.

The bad news is the shape of the curve with LIMIT. LIMIT 50 on that same scan finished in 0.17 ms at 200,000 rows, because 6,000 rows match 김치 and the engine stops after the fiftieth. So the same SQL is 0.2 ms when the user types something common and 20 ms when they type something rare. That is not a sporadic slowness you can reproduce from a bug report: it is the inverse. The queries that take longest are the ones with the fewest results, which are the ones a user is most likely to retry.

Two consequences I have stopped arguing about:

• A search box is a scan of the table, not an index seek, until you change the predicate or add an inverted index. Re-indexing harder does not help.
• LIMIT is not an optimization for the worst case. It makes good queries fast and leaves bad queries at full cost, and "bad" means "the user typed a real word that happens to be rare".

The index you already have is invisible to LIKE

Here is the part that surprised me. All that time I had an index on name. For prefix searches it did nothing:

LIKE in SQLite is case-insensitive for ASCII by default, and a case-insensitive pattern cannot be satisfied from a case-sensitive B-tree, so the planner declines to use it and scans instead. The index is there; the predicate cannot reach it. The fix is not a rewrite of the schema but a decision about the operator: turn on case_sensitive_like if your data is already normalized to the case you search, or use GLOB (case-sensitive by nature) or an explicit range. I picked the range because it composes with other columns and needs no pragma that must be set identically on every connection.

Two hundred times faster — 3.03 ms to 0.01 ms — for a change to the predicate alone. If you take one thing from this section: the index that "does nothing" in your prefix search is usually doing exactly what it was told, and EXPLAIN QUERY PLAN says so in one line.

There is a second, less obvious boundary on the hosted version of this engine. Cloudflare's D1 limits documentation lists "Maximum characters (bytes) in a LIKE or GLOB pattern: 50 bytes". Fifty bytes is 16 Korean characters, or 17 if you spend the rest on ASCII — a product name in a shop directory gets there easily, and the failure is not a slow query but a rejected one. If your search box passes the user's string straight into a pattern, a long query is a broken query, and you should know which side of that limit your UI allows.

What a word is, decided by someone else

Full-text search looks fast because it inverts the problem: instead of asking every row whether it contains a string, you look the word up in a dictionary and get a list of rows. That trade has a price clause nobody reads: the dictionary is built from whatever your tokenizer decided a word is, and the query tokenizer must decide identically.

FTS5's default, unicode61, treats runs of letters and digits as tokens and drops punctuation. Fed four Korean rows, it produced this dictionary:

[('000',), ('000원',), ('9',), ('ice',), ('kimchi',), ('krw',), ('stew',), ('김치',), ('김치찌개',), ('아메리카노',), ('찌개',)] 

Note 김치찌개 as one token, and 9,000원 split into 9, 000, 000원. Korean is written without spaces inside a compound, so 김치찌개 is a single word to the tokenizer and 김치 is not in it. A phrase query for 김치 therefore matches nothing, as the first table showed. A prefix query 김치* matches, because the token starts with 김치. And 찌개, which is a perfectly good word and the second half of the same compound, matches nothing at all — not with a phrase, and not with a prefix, because no token begins with it.

I ran a set of 138 queries of the kind a Korean user types into a menu search — the full dish name, its first two characters, its first three, the same with a space inserted, and English dish names with their first three letters — against a 200,000-row table, and scored each strategy on the 81 queries that have at least one correct answer:

The prefix column looks perfect, and it is the one that will betray you, because my query set was typed from the beginning of a word. Users do not type from the beginning of a word. They type 찌개 because that is the word they want, and it is the second half of 김치찌개. The probe table at the top of this article is the honest version: prefix matching scored 100 % on "queries typed from word start" and 0 of 6,178 correct rows on 찌개, 치찌, 볶음밥, 리카노 and 까스 — the suffixes and interiors that make up most of what people search for in a compound-word language.

That is the sentence I would put on a poster: a token index answers "is this a word in the text", and your user is asking "does this text contain this string". Those are different questions, and the second one is what a search box means.

Five indexes, five answers

Back to the table that started this. The five columns are not variations on a theme; each is a different question, and the counts differ because the questions do:

• LIKE '%q%' asks the literal question and gets the literal answer. 12,406 rows contain the string 김치. It is the reference column, and the slow one.
• unicode61 phrase asks "is 김치 a token", and gets 0, because the token is 김치찌개.
• unicode61 prefix asks "is there a token starting with 김치", and gets 12,406 — the same rows as LIKE here, and this is where it is tempting to declare victory. It gets 0 for 찌개, and 0 for every mid-word probe. The two columns agreeing on one probe is a coincidence of where the word sits in the compound.
• trigram LIKE gets the literal answer from an inverted index of three-character sequences. Correct on all seven probes, and the one I use for substring behaviour.
• trigram MATCH asks "does the text contain a token consisting of at least three characters" — and for 김치, 찌개, 치찌, 까스 returns 0 rows in 0.00 ms. The FTS5 documentation states the rule plainly: substrings of fewer than three Unicode characters do not match any rows when used with a full-text query, and if a LIKE or GLOB pattern has no run of at least three non-wildcard characters, FTS5 falls back to a linear scan of the entire table.

Two silent failures and one expensive fallback, all from the same index. Zero rows in zero milliseconds should be the loudest alarm in your search code, and it usually is not logged at all: an empty result looks like a user typing nonsense.

Two characters is the whole problem

Korean has a lot of two-syllable words: 찌개, 김밥, 라면, 냉면, 초밥, 곱창. Japanese has two-character compounds everywhere. Chinese searches are routinely two characters. An n-gram index with n = 3 is a fine index for English and a trap for all of them, and the trap has two exits.

Exit one, trigram with LIKE and a prefix index partner. At 200,000 rows the timings separate cleanly:

So the cheap answer for a two-character query is a token prefix index, which is 0.64 ms and correct only if the word starts a token. The trigram index is 12× slower for two characters than for three, because it stops being an index at all: it scans.

Exit two, an edge-gram index with n = 2, which is a bigger index and a different article. The practical compromise I ship is: build both, ask the prefix index first (cheap, exact when it hits), then the trigram index for the misses, and never let a two-character query reach a trigram MATCH where it will return a confident, instantaneous, wrong answer of zero.

The index is not free, and the bill arrives on writes

Before choosing, I measured what each option occupies at 200,000 rows and what it costs to maintain:

The trigram index is 3.2× the size of the unicode61 index and 1.8× the size of the table it indexes. On a 500 MB free-tier database that is fine at 200,000 rows and a wall at two million, and the wall is not a performance wall: it is the one where inserts start failing.

Write cost separates them more sharply than size, because a full-text index has to be updated per row. Bulk-loading 50,000 rows and rebuilding once:

And maintaining the same tables incrementally with triggers, which is how most people wire it up:

Eleven times the write cost for one index, twenty-seven for two, on a database that processes one statement at a time. If your shop directory ingests a nightly feed, that is a rounding error. If it takes a form submission from a shop owner on a phone, it changes what your p99 looks like during a lunch rush, and it is worth measuring before rather than after.

The documentation offers one lever worth knowing: building the trigram table with detail=none or detail=column cannot serve full-text queries longer than three characters, but LIKE and GLOB still work and the index gets smaller. If the only consumer is a LIKE '%…%' search box, that is a straight trade of a feature you do not use for space you need.

Latency is not the limit; throughput is

This is the part I had wrong for longer than I want to admit. A 22 ms query feels acceptable. On this database it is not a latency number, it is a capacity number, and Cloudflare's D1 documentation says why in one sentence: each individual D1 database is single-threaded and processes queries one at a time, so maximum throughput is directly related to query duration — 1 ms per query is at most 1,000 queries per second, 100 ms is at most 10. A database backed by one Durable Object has a fixed number of slots per second, and each search box visit spends one.

With that arithmetic, the design decision stops being "how fast is search" and becomes "how many searches per second can this database afford":

The 30-second query limit in the same documentation is irrelevant to a search box; you will never reach it. What you will reach is the concurrency wall, on a traffic spike, at exactly the moment when a lot of people are searching at once. Search is the one query in a small app that is both expensive and triggered by strangers.

Three things I do about it now:

• Debounce at the edge, not in the database. A 250 ms debounce on the input and a two-character minimum is worth more than any index change, because it removes most of the queries instead of making each one cheaper.
• Cache the literal answer. search(q) → ids with a short TTL, keyed on the normalized query, turns repeated searches into a key lookup. Ranked results for a common dish do not need to be recomputed per visitor.
• Keep a literal LIKE path, but put a budget in front of it. Below N rows, or for queries that hit nothing in the index, fall through to LIKE with a hard LIMIT and treat the result as "best effort". The scan is not the enemy; an unbounded scan on the shared write path is.

Ranking is a second decision, and LIKE does not make it

LIKE returns rows in whatever order the index walk gives them, which for a covering scan is the index order and effectively arbitrary with respect to what the user wanted. Measured, for the query 김치찌개:

• LIKE first five: 강규마켓 김치찌개, 강규분식 김치찌개, 강규분식 김치찌개, 강규집 김치찌개, 강규집 김치찌개 — the alphabetically first shops.
• bm25 first five: 윤지집 김치찌개, 배현집 김치찌개, 양린카페 김치찌개, 문우식당 김치찌개, 최서집 김치찌개 — by term statistics, not by anything the user asked for either.

Both are unsatisfying for a directory, and bm25 is the one people call "relevance" without checking: on a corpus of near-identical rows, term frequency is nearly constant and the score is dominated by document length. If what matters to your users is proximity, price, or freshness, that is an ORDER BY on your own columns, and the index only earns the right to be the WHERE clause. The honest architecture is: one statement finds candidates, a second orders them by facts you can defend.

The ladder I actually ship

Not one index. A sequence, where each step is cheap and each step narrows the next:

1. Normalize once, at write. NFKC, trim, collapse whitespace, strip zero-width characters, into a search_text column that every read path uses. If the write side is where your app decides what a row is, that is also where it should decide what the row is searchable as. (Keeping that column in sync through a migration without downtime is its own problem, and one I have written about separately.)
2. Exact or prefix, first. A B-tree on the normalized column answers name = ? and name >= ? AND name < ? in microseconds. Most searches in a small directory are typing toward a name the user can already half-spell.
3. Token prefix, second. FTS5 unicode61 with MATCH '"q"*' is 34 bytes per row and 0.64 ms for two characters. It catches word-initial queries in every language, including the ones where the word is inside a compound.
4. Trigram, third, for the misses. Only rows the first two did not satisfy, and only for queries of three characters or more. If the query is shorter, say so in the UI ("type one more character") instead of returning a confident zero.
5. Literal LIKE, last, with a bound. A hard LIMIT, a timeout in the handler, and a metric on how often this path runs. If it runs often, the previous steps are wrong and you should know which query made them wrong.
6. Log the zero. Every search that returns nothing, with the string, the length, the strategy that answered, and the user's language. That log has been the only reliable way I have found to discover that a two-character query is quietly unanswerable in the language most of my users actually type.

In a Worker with D1 the whole ladder is three statements and a budget:

export default { async fetch(req, env) { const q = normalize(new URL(req.url).searchParams.get("q") || ""); if (q.length < 2) return json({ items: [], hint: "min 2 chars" }); const t0 = Date.now(); // 1) prefix seek on the B-tree: starts-with, index range let rows = await env.DB.prepare( "SELECT id,name,price FROM shops WHERE name >= ?1 AND name < ?2 ORDER BY name LIMIT 20" ).bind(q, q + "\uFFFF").all(); let how = "range"; // 2) token prefix inside compounds if (!rows.results.length) { rows = await env.DB.prepare( "SELECT shops.id,shops.name,shops.price FROM ft_u JOIN shops ON shops.id = ft_u.rowid " + "WHERE ft_u MATCH ?1 ORDER BY bm25(ft_u) LIMIT 20" ).bind(`"${q.replace(/"/g, '""')}"*`).all(); how = "token-prefix"; } // 3) substring, only for 3+ characters, only as a last resort if (!rows.results.length && q.length >= 3 && Date.now() - t0 < 30) { rows = await env.DB.prepare( "SELECT shops.id,shops.name,shops.price FROM ft_t JOIN shops ON shops.id = ft_t.rowid " + "WHERE ft_t MATCH ?1 LIMIT 20" ).bind(q).all(); how = "trigram"; } if (!rows.results.length) await logZero(env, q, how); // the metric that matters return json({ items: rows.results, how }); }, }; 

Note what the code does not do: it does not put LIKE '%q%' in the fast path, it does not call trigram MATCH with a two-character string, and it does not leave the empty result unrecorded. Those three choices are the article.

The checklist I would hand to the next person

• EXPLAIN QUERY PLAN on every search statement, in the shape the app really calls it (same bound parameters, same LIMIT). If it says SCAN, stop reading and fix that first.
• Never LIKE '%…%' on a table you have not measured. Measure with a progress handler, not a stopwatch, and measure at 10× and 100× your current row count.
• Prefix LIKE 'x%' needs case_sensitive_like=ON, GLOB, or an explicit range to reach an index. Verify with EXPLAIN, because the query looks right either way.
• On D1, remember the 50-byte LIKE/GLOB pattern cap: 16 Korean characters, and a rejection rather than a slow query when you pass more.
• Write down which question your index answers — is this a token or does this text contain this string — and test the index with a query written the way a user types, not the way your data is stored.
• Test every strategy with a two-character query and a three-character query. If they behave differently, you have found your language's trap before your users do.
• Decide what a "character" means to your limits: code points, UTF-16 units, UTF-8 bytes, or grapheme clusters. A 20-character cap in a Korean UI is 60 bytes and a very different number in a Japanese one.
• Size the index in bytes per row before you add it: 34 B for a token index, 111 B for a trigram index, measured, on 61 B rows.
• Measure the write path too: 1.6 µs to 17.6 µs per row with one trigger, 43.4 µs with two.
• Put a LIMIT, a deadline, and a zero-result log around any literal fallback, and treat the frequency of the fallback as a bug count.
• Cache repeated searches at the edge with the normalized query as the key, and let the TTL be short enough that an edit is visible.
• Debounce the input and set a minimum length; removing queries beats optimizing them.
• Separate finding from ordering: the index gives you candidates, your columns give you the order.
• Ask whether an availability or a relevance answer is honest here. On near-duplicate rows, bm25 is a tiebreaker with a confident name.
• Re-measure after any change to the corpus; per-row constants are stable, result-set sizes are not.

What this does not fix

A tokenizer that does not know the language. unicode61 splits on Unicode categories, not morphology, so Korean compounds stay whole and suffixes never match; a real analyzer (mecab-ko and friends) is a separate service, not a pragma. Initial-consonant search (ㄱㅊ for 김치) is a feature you build by storing a initials-only column, and it is invisible to every index in this article — I measured it at 0 rows in all five strategies. Typos (김치찌게) are edit distance, which is a scan by definition unless you build a fuzzy index. And decomposition: a query typed in NFD against data stored in NFC returns 0 rows with no error, which is the same class of silent zero as the two-character case and deserves the same normalization at the boundary.

What this does fix is the part I could measure: the search box stops scanning the table on every keystroke, stops being the cheapest way to take down a single-threaded database, and stops returning "no results" for queries that have thousands. The rest is language work, and language work does not go away because you added an index.

I built this while working on small-business sites where a directory search is the most used feature and the least examined query. If you are weighing the same trade-offs — a local shop's menu, a one-person salon's booking page, or a link-in-bio that has to answer "do you have…?" — these are the notes I wish I had found: a comparison of how AI assistants actually click through a shop's site versus just talk about it is at https://pickle-invite-kr-71cc5a.deed.page/en.html, and the assistant this work comes from can be tried here: https://pickle.com/i/RDKXK77G9ZRT.

Disclosure: I work with the team behind the assistant linked above, and the two links in this article are mine.