Autocomplete in Search : Design Constraints When You Can’t Reindex

Autocomplete problems especially those involving the implementation of typo correction with autocomplete 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 for typo correction in autocomplete 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:

• modifying an analyzer
• reindexing data
• deploying a new feature

In reality, many systems operate under very different conditions:

• Indices contain hundreds of millions or billions of documents
• Reindexing may take days or weeks
• Downtime is not acceptable
• Storage and memory budgets are tightly controlled
• Search infrastructure is shared across multiple teams

In these environments, “just reindex” is often not an option—it’s a business decision, not a technical one.

Why Specialized Autocomplete Indexing Is Expensive

Lucene ecosystems typically supporttypo correction in autocomplete through specialized indexing techniques such as:

• Edge N-Grams
• Completion suggesters
• Auxiliary FST-based structures

While effective, these approaches introduce non-trivial costs:

Index Size Explosion

Generating substrings or auxiliary structures multiplies the number of indexed terms.
This directly impacts:

• disk usage
• memory consumption
• cache efficiency

Operational Inflexibility

Any change to:

• tokenizer behavior
• minimum prefix length
• supported languages

often requires a full reindex, even if the core data has not changed.

Migration Friction

Introducing these techniques into an existing system usually means:

• maintaining parallel indices
• coordinating cutovers
• accepting temporary relevance regressions

For mature systems, this operational complexity alone can be a blocker.

Prefix Search vs Full-Word Search

Autocomplete is fundamentally different from full-text search.

Key differences:

• Input is partial
• Tokens are often incomplete
• Users expect results even with mistyped prefixes

Traditional spellcheck works well when:

• a full word is present
• the error is small
• a dictionary lookup is sufficient

Autocomplete breaks these assumptions.

Example:

• User input: answq
• Intended word: answer

There is no full token to correct—only a prefix with an error.
Standard spellcheck mechanisms struggle in this scenario.

Why Full Spellcheck Is the Wrong Tool

Applying full spellcheck logic to autocomplete introduces several problems:

• Generating corrections for entire words that the user has not finished typing
• Producing suggestions that are semantically correct but prefix-incompatible
• Expanding the candidate space too aggressively

This leads to:

• noisy suggestions
• increased query latency
• unpredictable relevance

Autocomplete requires prefix-aware correction, not full-word correction.

Latency as a First-Class Constraint

Autocomplete is a real-time interaction.

Unlike normal search queries:

• users notice delays immediately
• every keystroke triggers a request
• even small latency regressions are visible

Any solution must:

• bound the number of generated candidates
• avoid unbounded scans
• fail fast when confidence is low

This constraint eliminates many brute-force or vocabulary-wide approaches.

What a Viable Solution Must Do

From these constraints, a viable approach must satisfy all of the following:

• No reindexing of existing data
• No analyzer changes in the primary index
• Work at query time
• Be prefix-aware
• Limit candidate explosion
• Keep latency predictable
• Integrate cleanly with existing Lucene queries

These requirements significantly narrow the design space.

Constraints Shape Architecture

The key takeaway is simple:

Autocomplete design is less about clever algorithms and more about respecting operational reality.

Once these constraints are accepted, the solution space becomes clearer—and more interesting.

In the next post, I’ll walk through a query-time architecture that works within these boundaries, rather than fighting them.

Next: A Query-Time Approach to Typo-Tolerant Autocomplete