What do you trade away by indexing edge n-grams to power prefix autocomplete?

## N-grams and edge n-grams An **n-gram** filter emits every contiguous substring of a token within a length range: `shoe` with a range of 2–3 yields `sh`, `ho`, `oe`, `sho`, `hoe`. An **edge n-gram** filter emits only the substrings anchored at the start: `shoe` with range 1–4 yields `s`, `sh`, `sho`, `shoe`. Edge grams exist to serve prefix matching; full grams exist to serve infix/substring matching and to give unspaced scripts something to index when a proper segmenter is unavailable. ## Why index prefixes instead of matching them at query time A prefix query can be answered without any n-grams, by walking the sorted term dictionary from the prefix and expanding to every term that starts with it. This works, but the expansion is unbounded: a one- or two-character prefix on a large vocabulary can expand into a huge disjunction of terms, and that expansion cost is paid on every keystroke, per shard, while the user is waiting. Turning prefixes into ordinary indexed terms moves that cost from query time to index time, where it is paid once per document and amortised. A keystroke then costs exactly one dictionary lookup, and it composes cleanly with filters and with the rest of the query. ## What it costs **Index size and write throughput.** With an edge-gram range of *min* to *max*, each token of sufficient length becomes up to *max − min + 1* terms, each with its own postings entry. Index size grows several-fold on that field, the term dictionary grows, segment merges have more to do, and indexing throughput drops. On a large corpus this is the dominant objection, and it is why the field is usually a dedicated copy used only for the suggest path rather than the main searchable field. **Distorted term statistics.** A one-character gram like `s` appears in an enormous share of documents, so its IDF is near zero, while longer grams behave more normally. Worse, a single document contributes multiple grams from the same token, inflating term frequency in ways that have nothing to do with topical relevance. The practical consequence is that ranking on an edge-gram field is close to meaningless, and teams usually score on the real analyzed field and use the gram field only for matching — or disable length normalisation and frequency contributions on it. **Query-side asymmetry is mandatory.** If the user's input is n-grammed too, a query for `shoes` emits `s`, `sh`, `sho`, `shoe`, `shoes`, and the `s` clause alone matches nearly every document. Precision collapses and the result list looks random. The query must be analyzed as a plain token and matched against the indexed grams. This is the canonical example of *deliberate* index/query analyzer asymmetry. **Rigidity.** The gram range is materialised into the postings. Extending it — say from a maximum of 10 to 20 characters so longer prefixes still match — requires reindexing the corpus. Likewise, prefixes longer than the maximum simply stop matching unless the query is truncated to the maximum length, a subtle bug where autocomplete works until the user types the eleventh character. **Full n-grams are far worse.** Substring grams over a length range produce on the order of token-length times range terms per token, so index inflation is dramatic and statistics are even noisier. Reserve them for genuinely infix use cases. ## Alternatives and when to prefer them - **Term-dictionary prefix scan.** Fine when the field's vocabulary is small, prefixes are reasonably long, or query volume is low. Zero index cost, no reindex to change behaviour. - **A dedicated suggester structure.** Search engines can build a finite-state automaton over a suggestion vocabulary that returns completions in near-constant time with optional weights. It is compact and purpose-built, but it lives beside the index, needs its own build, and does not compose with arbitrary filters as naturally. - **A separate suggestion index built from query logs.** Often the best product answer: complete to *what people actually search*, weighted by popularity and freshness, rather than to every token that happens to appear in the corpus. It is smaller, more relevant, and decoupled from the document index entirely. - **Matching whole-word prefixes only on the last token.** A cheap middle ground: analyze the query normally, treat all but the final token as complete words, and only prefix-match the token the user is still typing. ## How to decide Ask three questions: how large is the field's vocabulary, how short are the prefixes you must serve, and does the suggestion need to be ranked by anything other than lexical match? Small vocabulary and long prefixes favour a dictionary scan; keystroke-latency requirements on a big corpus favour indexed edge grams on a dedicated field; a product where suggestions should reflect demand favours a query-log-driven suggestion index. And whichever you choose, budget for the reindex, because every one of these choices is materialised at index time.