Implementing Autocomplete with MySQL, Redis, and Elasticsearch

Autocomplete is a user‑friendly feature for mobile devices that lets users finish searches with fewer keystrokes. According to Google, it can reduce typing by about 25%, saving more than 200 years of typing time per day across users.

The article explains what autocomplete is, why it is useful, and presents three common implementation approaches: MySQL, Redis, and Elasticsearch.

1. What is Autocomplete

Search engines suggest possible completions based on the characters a user has typed, allowing the user to select a suggestion instead of typing the full query.

2. Common Autocomplete Methods

Most commercial systems (Taobao, JD, Pinduoduo, Baidu) use prefix matching. The three typical backend solutions are:

MySQL implementation

Redis implementation

Elasticsearch implementation

3. MySQL Implementation

The simplest way is to use a LIKE query.

SELECT * FROM table WHERE keyword LIKE "ssss%" LIMIT 10

This works for small data sets but suffers from poor performance and limited scalability when the dataset grows or when hot‑word ranking is required.

4. Redis Implementation

Redis can store suggestions in a sorted set (zset) with a score of 0, allowing lexical ordering. By inserting sentinel members (e.g., aa{ and ab{ ) you can locate the range of members that share a prefix.

Typical steps:

Use ASCII ordering: characters before a are `` and after z is { .

Insert sentinel keys to define the range.

Query the range with ZRANGE .

For Chinese characters, store them as hexadecimal strings.

Redis also allows a separate zset to store hot‑word scores, which can be intersected with the suggestion set to produce popularity‑sorted results. However, adding typo‑correction is not straightforward.

5. Elasticsearch (ES) Implementation

ES provides a Completion Suggester via the Suggesters API, which is designed specifically for autocomplete and supports weight‑based ranking.

Because autocomplete requires extremely low latency, ES stores the analyzed terms in a Finite State Transducer (FST) rather than a traditional inverted index. The FST is loaded into memory for fast prefix lookup, but it only supports prefix matching.

PUT /ulink_dict/
{
"mappings": {
"dict": {
"properties": {
"suggest": {
"type": "completion"
}
}
}
}
}

PUT ulink_dict/dict/1
{
"suggest": {
"input": ["关键词"],
"weight": 80
}
}

POST /ulink_dict/_search
{
"suggest": {
"song-suggest": {
"prefix": "关键词",
"completion": {
"field": "suggest"
}
}
}
}

The FST data structure compresses common prefixes, resulting in low memory usage and O(len(str)) query time. The article demonstrates building an FST for the words “cat”, “deep”, and “do” with step‑by‑step diagrams.

6. Conclusion

The article covered the concept of autocomplete, its use cases, and three backend implementations. Choosing the right solution depends on data size, latency requirements, and whether additional features such as typo‑correction or hot‑word ranking are needed.

References:

https://www.elastic.co/guide/en/elasticsearch/reference/current/search-suggesters.html

https://blog.burntsushi.net/transducers/