Autocomplete

The problem: a suggestion per keystroke

Snip's dashboard search box should suggest as the owner types: after su, show "summer sale", "summer shoes", "sunglasses". To feel instant, suggestions must appear within about 100 ms of each keystroke, network included, so the server has a few milliseconds. And a ten-letter query is ten requests, so autocomplete traffic is several times search traffic.

What to suggest matters as much as how fast: the most useful completions first. Snip ranks an owner's link titles and tags by how often they've been searched for and clicked.

Option 1: a prefix query

A prefix is the one thing a B-tree is good at for strings: title LIKE 'su%' can use an index (in Postgres, one built with text_pattern_ops), because all strings starting with su sit together in sorted order (04.02 Indexes and B-trees). For one owner's few thousand titles, that plus ORDER BY popularity LIMIT 5 is fine.

It breaks down at scale: a short prefix like s matches a huge range, which must then be sorted by popularity to find the top five. The top five are what's wanted, not all matches.

Option 2: a trie with the answers precomputed

A trie is a tree where each edge is a character, so each node represents a prefix. The trick for autocomplete is to store, at every node, the top k completions for that prefix, computed when phrases are added. A lookup walks down the prefix's characters and returns that node's list: no searching or sorting below it.

type TrieNode = { children: Map<string, TrieNode>; top: [string, number][] };
const node = (): TrieNode => ({ children: new Map(), top: [] });

export class Autocomplete {
  private root = node();
  constructor(private readonly k = 5) {}

  /** Add a phrase with a weight (say, how often it's searched). Every prefix node keeps its own top k. */
  add(phrase: string, weight: number) {
    let n = this.root;
    for (const ch of phrase.toLowerCase()) {
      if (!n.children.has(ch)) n.children.set(ch, node());
      n = n.children.get(ch)!;
      const top = n.top.filter(([p]) => p !== phrase);
      top.push([phrase, weight]);
      top.sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1));
      n.top = top.slice(0, this.k);
    }
  }

  /** Walk down the prefix, then answer from that node's precomputed list: no search below it. */
  suggest(prefix: string): string[] {
    let n: TrieNode | undefined = this.root;
    for (const ch of prefix.toLowerCase()) {
      n = n.children.get(ch);
      if (!n) return [];
    }
    return n.top.map(([p]) => p);
  }
}

Tested with k = 3 and six weighted phrases: s suggested "shoes", "summer sale", "summer shoes"; su suggested "summer sale", "summer shoes", "sunglasses"; an unknown prefix returned nothing; and raising "summer camp"'s weight moved it to the top of summer. Lookups cost the length of the prefix, whatever the number of phrases.

The costs: memory (every node stores k entries) and updates (a new phrase touches every node along its path). A weight that drops is awkward, because the node no longer knows the next-best phrase; real systems rebuild the trie periodically (hourly, say) from search logs, and serve it read-only from memory.

Option 3: let the search engine do it

Search engines have prefix features built in:

• Edge n-grams: at index time, store every prefix of each word as a term ("s", "su", "sum", "summ" …), so a prefix query becomes a normal term lookup in the inverted index (10.01 Inverted indexes). Flexible, but the index grows.
• Completion suggesters: Elasticsearch's completion suggester keeps its suggestions in data structures built for fast prefix lookups, held entirely in memory. The documentation is clear about the trade-off: fast to query, costly to build, and best kept in a single-shard index.

Snip uses the completion suggester for owner-scoped suggestions, with each owner's ID as a filter (a "context"), and rebuilds weights nightly from search logs.

The client does half the work

• Debounce: wait until the user pauses for about 100 ms before requesting. Fast typists send far fewer requests.
• Cancel stale requests: if the user typed sum after su, drop the su response if it arrives late, or the box shows suggestions for the wrong prefix.
• Cache by prefix: in the browser, and for global suggestions at the CDN (06.01 Where caches live): popular prefixes are requested constantly and change slowly.
• Filter locally: once you have suggestions for su, typing m can often be answered by filtering them, without asking the server.

Recap

Interview questions