Autocomplete and Suggestion Systems

By Oleksandr Andrushchenko — Published on
0 Likes
0 Dislikes
Autocomplete and Suggestion Systems
Autocomplete and Suggestion Systems

Autocomplete looks simple because the interface is small: a user types a few characters and the system returns a short list of likely completions. In production, however, autocomplete is a latency-sensitive search problem with very different requirements from ordinary full-text search.

A good suggestion system must respond within tens of milliseconds, handle incomplete prefixes, rank popular and contextually useful candidates, avoid stale or low-quality suggestions, and remain efficient under extremely high request rates.

The core design principle is to treat autocomplete as a specialized retrieval system rather than as a normal search request executed on every keystroke.

Table of Contents

Why Autocomplete Is Different

Normal search begins after the user submits a complete query. Autocomplete runs while the query is still being constructed.

User types:

"p"
"po"
"pos"
"post"
"postg"
"postgr"
"postgres"

One short typing session can therefore generate many requests.

If every keystroke triggered a normal full-text search:

1 user
x 8 keystrokes
= 8 search requests

10,000 active users
x several keystrokes/sec
= very high request volume

Autocomplete also has a much tighter latency budget because users directly perceive delays between keystrokes and suggestions.

A useful target might look like:

p50: < 20 ms
p95: < 50 ms
p99: < 100 ms

The exact numbers depend on the product, but the general requirement is clear: autocomplete must be small, bounded, and extremely fast.

It should usually return only a handful of candidates:

input:
"postg"

results:
PostgreSQL
PostgreSQL replication
PostgreSQL indexing
PostgreSQL performance
PostgreSQL partitioning

This differs from a normal search result page, where dozens or hundreds of documents may be considered and ranked.

Generating Suggestion Candidates

The first problem is efficiently retrieving phrases or entities that begin with a partially typed prefix.

Several indexing strategies can support this.

Prefix Indexes

The simplest conceptual approach is to precompute prefixes.

For the term:

"postgresql"

the system could index:

p
po
pos
post
postg
postgr
postgre
postgres
postgresq
postgresql

The query:

"postg"

can then perform an exact lookup against the prefix structure instead of scanning all possible strings.

This produces very fast retrieval but can increase index size substantially because a single suggestion generates many prefix entries.

For a candidate of length n, the system may create approximately n prefix entries.

"database"
length = 8

prefixes:
d
da
dat
data
datab
databa
databas
database

Large suggestion vocabularies therefore require careful control over which prefixes are stored.

Edge N-Grams

Search engines commonly implement prefix matching using edge n-grams.

For:

"distributed"

an edge n-gram analyzer might generate:

dis
dist
distr
distri
distrib
distribu
distribut
distribute
distributed

The index may deliberately skip extremely short prefixes such as one-character inputs because they match too many candidates.

min_gram = 3
max_gram = 15

This provides an important trade-off:

smaller min_gram
    |
    +--> suggestions appear earlier
    +--> larger index
    +--> more candidate matches


larger min_gram
    |
    +--> smaller index
    +--> less query fan-out
    +--> suggestions appear later

The autocomplete index should therefore reflect actual user behavior rather than trying to support every theoretical prefix.

Trie-Based Retrieval

A trie stores strings according to shared prefixes.

For the words:

car
card
care
cat

a simplified trie looks like:

        c
        |
        a
       / \
      r   t
     / \
    d   e

Searching for the prefix ca navigates directly to the corresponding node and explores descendants from there.

Conceptually:

prefix = "ca"

find node("ca")
      |
      v
descendants
      |
      +--> car
      +--> card
      +--> care
      +--> cat

Trie-like structures can provide excellent prefix performance and are especially useful when the suggestion vocabulary is relatively stable and can be kept efficiently in memory.

The trade-off is memory usage. A naïve trie can consume substantial space, so production implementations often use compressed variants or specialized finite-state structures.

Ranking Suggestions

Prefix matching only determines which candidates are possible. The system still needs to decide which suggestions should appear first.

For the prefix:

"java"

possible suggestions might include:

java
javascript
java hashmap
java virtual machine
java spring boot
javascript array
java interview questions

A ranking function may combine several signals:

score =
    prefix_match_quality +
    popularity +
    recent_trend +
    query_success +
    contextual_relevance

Popularity is often an important baseline.

Suppose historical query frequency is:

"javascript"            4,800,000
"java"                  3,900,000
"java spring boot"        850,000
"java hashmap"            620,000
"java virtual machine"    310,000

A frequency-based system might return:

ja
 |
 +--> javascript
 +--> java
 +--> java spring boot
 +--> java hashmap

However, raw popularity should not be the only ranking signal. Historical popularity can preserve outdated or low-quality queries indefinitely.

A more robust score might use:

score =
    0.50 * popularity +
    0.20 * recent_frequency +
    0.15 * click_success +
    0.10 * conversion +
    0.05 * freshness

Ranking should also consider prefix quality. A suggestion beginning exactly with the typed query generally deserves stronger treatment than one matching only after aggressive normalization.

The broader ranking concepts are covered in Search Relevance and Ranking Strategies.

Query Suggestions from Search Logs

Autocomplete candidates do not have to come directly from indexed products or documents. Many systems build suggestions from historical queries.

Suppose the search logs contain:

"postgresql replication"       18,420 searches
"postgresql indexing"          15,930 searches
"postgresql performance"       12,100 searches
"postgresql partitioning"       8,240 searches
"postgresql vacuum"             6,820 searches

The system can periodically aggregate these queries:

Search Logs
    |
    v
Aggregation Job
    |
    +--> frequency
    +--> recency
    +--> clicks
    +--> conversions
    |
    v
Suggestion Dataset
    |
    v
Autocomplete Index

This approach can produce suggestions that reflect real user language instead of only document titles.

However, raw search logs should not automatically become public suggestions.

They may contain:

  • personally identifying information;
  • spam;
  • offensive queries;
  • random identifiers;
  • URLs;
  • low-frequency noise;
  • sensitive terms.

A production pipeline should filter and normalize candidates before publication.

Raw Queries
    |
    v
Normalization
    |
    v
Frequency Threshold
    |
    v
Safety / Quality Filtering
    |
    v
Scoring
    |
    v
Published Suggestions

Low-frequency queries can be excluded:

if query_count < MIN_OCCURRENCES:
    exclude()

This improves quality while reducing the size of the suggestion index.

Context and Personalization

Global popularity is a good default, but the most useful completion may depend on context.

Consider the prefix:

"app"

Possible suggestions could include:

apple
application architecture
application load balancer
app store
apple watch

A backend engineer and an online shopper may reasonably expect different ranking.

Contextual signals may include:

language
country
category
current page
recent searches
product type
organization
device
session behavior

For an e-commerce category page:

category = "laptops"
prefix = "mac"

global suggestions:
mac
macbook
mac address
mac cosmetics

category-aware suggestions:
macbook
macbook air
macbook pro

Context can improve relevance without requiring deep user personalization.

Personalized autocomplete may incorporate recent history:

global:
"postgresql"
"postgresql tutorial"
"postgresql download"

recent user searches:
"postgresql replication"
"postgresql failover"

personalized:
"postgresql replication"
"postgresql failover"
"postgresql tutorial"

However, personalization reduces cache reuse because responses are no longer identical for all users.

A practical design often combines a cached global result with a small personalized layer:

Global top suggestions
        |
        +--> cached
        |
        v
Merge
        ^
        |
Recent user suggestions
        |
        +--> small personalized set

This keeps most of the retrieval path highly cacheable while still providing useful personalization.

Designing for Very Low Latency

Autocomplete is one of the highest-frequency search endpoints, so small inefficiencies multiply quickly.

The client should avoid sending a request for every raw keyboard event.

Debouncing can reduce request volume:

Typing:
p
po
pos
post
postg

Without debounce:
5 requests

With short debounce:
1-2 requests

The client can also wait until a minimum prefix length is reached:

if len(query) < 2:
    return []

On the server side, the query path should remain minimal:

Client
  |
  v
Autocomplete API
  |
  v
Cache
  |
  v
Suggestion Index
  |
  v
Top 8

Avoid downstream service fan-out:

Bad:

Autocomplete
   |
   +--> Search
   +--> Product Service
   +--> User Service
   +--> Analytics
   +--> Inventory


Better:

Autocomplete
   |
   +--> dedicated suggestion index

The suggestion index should normally contain everything required to render the result:

{
    "text": "postgresql replication",
    "type": "query",
    "score": 0.94
}

or for entity suggestions:

{
    "text": "PostgreSQL",
    "type": "technology",
    "id": 284,
    "slug": "postgresql"
}

This avoids expensive enrichment during the typing path.

Caching is especially effective for popular prefixes because many users generate the same requests:

"iph"
"ipho"
"iphone"

"post"
"postg"
"postgr"

A cache key can remain simple:

autocomplete:{locale}:{prefix}

Cache effectiveness, request coalescing, and hot-key behavior should be considered using the same principles described in Designing Multi-Level Caching Architectures.

Keeping Suggestions Fresh

Autocomplete data often needs different freshness guarantees from the main search index.

Some candidates change slowly:

countries
brands
product categories
technology names

Others change quickly:

trending queries
breaking news topics
new products
popular searches
events

A common architecture combines offline and near-real-time updates:

Historical Search Logs
        |
        v
Batch Aggregation
        |
        v
Base Suggestion Index
        |
        +------------------+
                           |
Recent Query Stream        |
        |                  |
        v                  |
Real-Time Aggregation      |
        |                  |
        +---------> Merge -+
                      |
                      v
               Autocomplete API

The base dataset provides stable popularity signals, while a smaller real-time layer captures emerging trends.

A ranking formula can combine both:

score =
    0.70 * historical_score +
    0.30 * recent_score

Time decay prevents old popularity from dominating indefinitely:

trend_score =
    frequency * exp(-lambda * age)

For products, updates may come from the same event pipeline that maintains the main search index:

Product Database
      |
      v
Change Stream
      |
      +--> Main Search Indexer
      |
      +--> Suggestion Indexer

This allows the two read models to evolve independently while sharing the same authoritative source.

Production Design Example

Consider an e-commerce platform with 80 million products and several million searches per day.

The main search system is optimized for full queries, while autocomplete uses a separate suggestion index.

                         DATA PIPELINE

Product Catalog
      |
      v
Change Stream
      |
      +---------------------+
      |                     |
      v                     v
Search Indexer        Suggestion Builder
      |                     |
      v                     v
Main Search Index     Product Suggestions


Search Logs
      |
      v
Query Aggregation
      |
      v
Query Suggestions
      |
      +-----------+
                  |
                  v
          Suggestion Index

The read path is intentionally short:

Browser
   |
   | prefix = "wirel"
   v
Autocomplete API
   |
   v
Cache
   |
   | miss
   v
Suggestion Index
   |
   v
Top 8 suggestions

The index might contain both queries and entities:

{
    "text": "wireless headphones",
    "type": "query",
    "popularity": 0.96,
    "recent_score": 0.82
}

{
    "text": "Wireless Noise Cancelling Headphones",
    "type": "product",
    "product_id": 1042,
    "popularity": 0.91,
    "available": true
}

The prefix wirel may produce 300 candidates.

Prefix lookup
    |
    v
300 candidates
    |
    v
Availability / quality filters
    |
    v
120 candidates
    |
    v
Fast ranking
    |
    v
Top 8

A ranking function might look like:

score =
    0.45 * popularity +
    0.25 * prefix_quality +
    0.15 * recent_score +
    0.10 * conversion_score +
    0.05 * contextual_score

Popular prefixes are cached:

autocomplete:en-US:wirel
autocomplete:en-US:iph
autocomplete:en-US:lap

The client applies a short debounce and ignores responses belonging to older requests.

request 1: "post"
request 2: "postg"
request 3: "postgr"

response 1 arrives last

discard response 1
because current input = "postgr"

This prevents slow earlier requests from replacing newer suggestions in the interface.

The architecture scales well because the most frequent interaction uses a compact read model, small responses, bounded candidate sets, and highly reusable cache entries.

Common Mistakes

Reusing the normal search endpoint for autocomplete may appear simpler, but it often performs unnecessary work.

Autocomplete needs:
8 short suggestions

Full search performs:
large candidate retrieval
facets
aggregations
advanced ranking
result enrichment

That cost is multiplied across every keystroke.

A dedicated suggestion path is usually smaller, faster, and easier to scale independently.

Ranking Only by Popularity

Popularity can produce good initial rankings, but it can also create stale feedback loops.

popular query
    |
    v
shown more often
    |
    v
clicked more often
    |
    v
becomes even more popular

Without freshness and quality controls, outdated suggestions can remain permanently dominant.

Popularity should be balanced with recency, match quality, success metrics, and domain-specific signals.

Searching Very Short Prefixes Aggressively

A one-character prefix can match an enormous percentage of the suggestion vocabulary.

"a"
    |
    v
hundreds of thousands
or millions of candidates

It also provides very little information about user intent.

Waiting until two or three characters are available can significantly reduce load while usually having little impact on usability.

Indexing Unbounded Suggestion Candidates

Building suggestions from every historical query can create a huge index dominated by low-value data.

200 million raw queries

after normalization:
80 million unique strings

after frequency threshold:
3 million useful candidates

Frequency thresholds, normalization, expiration, and quality filtering can dramatically reduce index size while improving result quality.

Production Checklist

  • Use a dedicated autocomplete path when suggestion traffic becomes significant.
  • Choose prefix, edge n-gram, trie, or specialized completion structures based on workload.
  • Avoid indexing unnecessarily short prefixes.
  • Keep suggestion payloads small and self-contained.
  • Return only a small bounded number of suggestions.
  • Use client-side debouncing to reduce request volume.
  • Discard stale responses when newer input has already been submitted.
  • Cache popular prefixes when response personalization allows it.
  • Combine popularity with freshness and quality signals.
  • Filter low-frequency and low-quality historical queries before indexing them.
  • Keep authorization-sensitive information out of public suggestion indexes.
  • Use contextual ranking only where it produces measurable value.
  • Monitor p95 and p99 autocomplete latency separately from normal search.
  • Track suggestion click-through, acceptance rate, and zero-suggestion rate.

Conclusion

Autocomplete is a specialized search workload built around incomplete prefixes, extremely high request frequency, and very small latency budgets. Efficient systems avoid running the full search stack for every keystroke and instead maintain compact data structures optimized specifically for prefix retrieval.

Candidate generation may use edge n-grams, prefix indexes, tries, or dedicated completion structures. Ranking then combines match quality with popularity, recent trends, successful historical queries, and limited contextual signals.

The best production designs keep the request path short, aggressively bound candidate counts, cache common prefixes, filter noisy historical queries, and update suggestions independently from the main search experience when necessary.

Key Takeaway: Autocomplete should be optimized as its own read path. Precompute useful candidates, retrieve them through prefix-oriented indexes, rank only a small set, and keep the entire interaction fast enough to run repeatedly while the user is still typing.

Author

Oleksandr Andrushchenko

Oleksandr Andrushchenko

Software Engineer & Solution Architect
Nov 03, 2025 4 167
Enjoyed this article?

Support Oleksandr Andrushchenko

Buy me a coffee

This helps Oleksandr Andrushchenko continue creating useful content

Related articles

Comments (0)