Usually, when we implement suggestions in autocomplete input fields, we query directly to our database. Relatively, LIKE queries in MySQL are slower. So why not autocomplete using Redis?
Disclaimer: This is a basic Redis solution for “just-trying-it-out” purposes only.
As I’ve mentioned, I got annoyed by the slow autocomplete results of an app that I have been playing with so I browsed the internet for some NoSQL solutions, specifically Redis. Usually, apps have Redis set up already so it would be nice to just leverage it for a basic autocomplete solution.
One of the strategies that I tried to implement is based on the idea that I need to store each partially typed character as a sorted set in Redis.
Assuming that I have DB data, the populate method above will insert Redis keys that would help implement autocomplete.
For example I have the following data in my database:
Generally, the number of Redis keys that will be created will be the number of characters each string has. So in tomato’s case, it’s 6.
The method populate will insert tomato’s 🍅 keys as:
Uhm, get it?
On tomato’s initial iteration, the key would be set to the string “t” since we’re extracting the characters from 0 to n+1 (n will start from 0 so, just +1). Then, the data to be set will be formatted to JSON so we can store not just one value. This is necessary if you need to access more than one attribute from your ActiveRecord model when in using the JS for autocomplete.
Then, the Redis
ZADD command is used to create a sorted set called
kupsearch:t since the variable
key is set to “t”. It will be inserted into the sorted set
kupsearch:t having the formatted to JSON data.
This process will continue until the whole word is inserted as a key-
kupsearch:tomato. And then, it will move on to the next data which is “toaster”.
Note: Ideally, namespaces must be meaningful so don’t use
kupsearch in real life.
Data retrieval is easy. The sample method that I created below shows a rough implementation of it. Note that I parsed the results first because I saved the data in JSON format.
So, the basic idea is to use Redis’ ZREVRANGE command. This will return the result set in reversed order which is descending– values with higher scores will be returned first.
As you may have noticed in the populate method, I was just inserting 1 as the score. Ideally, if you want to keep track of users’ hits as they enter the search key, you would increment the score of that key. When you do this, you will be able to return the results that are usually searched first before the unpopular ones. To increment, you can use the ZINCRBY command.
I benchmarked the LIKE query method against the Redis solution and for obvious reasons, Redis won. It’s an almost 100% improvement at least on 1000 rows of data.
#<Benchmark::Tms:0x007fc385731ce8 @label="", @real=14.029786, @cstime=0.0, @cutime=0.0, @stime=0.3000000000000007, @utime=12.299999999999983, @total=12.599999999999984>
#<Benchmark::Tms:0x007fc383e04158 @label="", @real=0.000284, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.0, @total=0.0>
Percentage Increase: 99.99797573533908
Code I used is something like:
It’s probably a small sample so don’t count on my performance testing ability. 😂
Caveats & Limitations
- Searching by ActiveRecord scopes is not handled. This means that if you only want to search and return products starts with “t” and that are fresh, Product.fresh, Redis does not know that so it will still return all that starts with “t”. There is probably a decent prefixing strategy for that but I haven’t explored it yet.
- Redis insertions must be maintained when inserting, updating and deleting AR objects.