Backend & Search Engineering

In the previous post, we looked at the constraints that make autocomplete difficult in real Lucene-based systems: large indices, high reindexing costs, tight latency budgets, and partial user input. Given those constraints, the most important design decision is where correction logic should live. This post describes a query-time architecture for typo-tolerant autocomplete that works around existing indices rather than modifying them. Why Query-Time Instead of Index-Time Index-time solutions optimize query execution by pushing complexity into preprocessing. That trade-off only works when reindexing is cheap. ...

Prefix-aware traversal narrows the search space, but it does not solve the entire problem. Even with a trie, allowing unrestricted deviations from user input would quickly lead to: excessive candidate generation unpredictable latency irrelevant suggestions This post explains how edit distance is used as a bounding mechanism, not as a full spellcheck solution. Why Bounding Matters in Autocomplete Autocomplete operates under tight constraints: every keystroke triggers a query users expect immediate feedback small delays are noticeable Any correction strategy that does not explicitly limit its search space will eventually fail under load. ...

Autocomplete problems are rarely algorithmic in isolation. They are almost always constraint-driven. Before discussing any solution, it’s important to understand why many commonly recommended approaches are simply not feasible in real production systems—especially those built on top of Lucene-based search engines. This post outlines the constraints that shaped the design decisions discussed later in this series. The Reality of Legacy and Large Indices In an ideal world, changing how autocomplete works would be as simple as: ...

In the previous post, we looked at a query-time architecture for typo-tolerant autocomplete. That architecture depends on one core capability: efficiently reasoning about prefixes. This post focuses on a data structure well-suited for that task—the trie—and explains why it fits prefix-aware correction better than many alternatives. Why Prefix Awareness Changes the Problem Autocomplete input is incomplete by nature. When a user types:

This blog documents how I think about backend systems, search infrastructure, and engineering trade-offs in real-world production environments. The focus is not tutorials, but decisions.