KEYS command performance

[max_iv]

We're thinking on moving some parts of our web app (mysql based) to
redis
currently the question is if autocomplete search would benefit from it
- we have a sql query to user table with a few joins returning users
with matching usernames.
so the idea is to move the data to redis with keys being username
(which will be used to compare against autocomplete query) and value
being hash of needed user fields (which will be shown in autocomplete
results)

Wiki says that KEYS command can scan a 1 million keys database in 40
milliseconds which seems to be a good result,
but anyway, it would nice to hear if someone solved (or decided to not
to) similar task before with redis.

[Salvatore Sanfilippo]

On Thu, Jan 14, 2010 at 4:41 PM, max_iv <max...@gmail.com> wrote:
>
> Wiki says that KEYS command can scan a 1 million keys database in 40
> milliseconds which seems to be a good result,
> but anyway, it would nice to hear if someone solved (or decided to not
> to) similar task before with redis.

Hello Max,

KEYS is not the way to go, the best thing you can do is to use instead
a sorted set.
What you want is to turn the first 4 or 5 characters of the strings
into an integer (you can
imagine every char as a digit of a radix 256 number for instance, but
there are better
representation) and add all your usernames into a sorted set.

Then using ZRANGEBYSCORE you can get all the elements between a given range.

This method is much more scalable as it's an O(log(N)) thing.

I'm covering this stuff in my very slowly evolving Redis book...

Cheers,
Salvatore

--
Salvatore 'antirez' Sanfilippo
http://invece.org

"Once you have something that grows faster than education grows,
you’re always going to get a pop culture.", Alan Kay