[antirez]

At the end of the original link of this post, I tried to hint a bit about a simple way to overcome this, which is by discrete splitting of different rates different search strings are typed.

Basically you have a sorted set that counts the occurrences of a given search string, using top-k stream algorithm consisting of just taking a set of size N2 if you are interested in the top-N, and always trimming a random element from the top N - N2 interval when a new element is added.

At this point what happens is that you take M autocompletion keys. complete_10, complete_100, complete_1000, ..., complete_max, that go up to order of magnitudes, so what happens is that when an user types you query complete_max, and check if it has enough entries, otherwise you also query the lower-rank sorted set and so forth.

This way you are able to show users top-searches while they are typing, but still populate the autocompletion with lower-frequency entries if needed.

Of course when the "counting" sorted set is updated, if an element goes from an order of magnitude to the other, you update the sorted sets accordingly.

[dvirsky]

Yep, that's a solid approach, although it might be limiting to some people. Also, maybe having something like ZRANGEBYLEXSTORE would also allow caching and sorting of the results by allowing quick ZINTER etc.

[antirez]

Agreed on both, the algorithm proposed is not perfect as it is discrete in nature, and storing results makes a lot of sense for top-queries since this is the kind of application where 5 minutes old is "good enough" for most users.