Auto Complete with Redis (2010) | Hacker News Reader

Auto Complete with Redis (2010)

oldblog.antirez.com

178 pointssetra24 comments

Hello! This article is serverely stale info. Modern versions of Redis with lexicographic ranges can do much better. Please check the following: https://redis.io/topics/indexes

Also you may want to check the RediSearch module from Redis Labs. It's AGPL and not part of the Redis project itself but it's very powerful. http://redisearch.io

BTW using vanilla Redis with lexicographic ranges some time ago I published a demo where I indexed the whole Linux kernel code using a small amount of memory and performing many tens of thousands ranges per second. There are other systems out there that are designed just for search but in certain low latency cases Redis can be hard to beat, also if you want to change the index in real time.

>This article is serverely stale info. Modern versions of Redis with lexicographic ranges can do much better. Please check the following: https://redis.io/topics/indexes

Are you able to put a similar warning at the top of the article? Maybe something like, "[The following info is deprecated but is left for historical purposes. ... Please check the following: https://redis.io/topics/indexes]"

You are right, I usually always do that but this time I totally missed this. Thanks I'll do.

While i deeply love redis and have used this exact article in the past to build an autocomplete— I’d really not recommend it to anyone. Using something like elastic search provides much better and robust results.

Yes it’s more work to setup but the maintenance and tweaking will be waaaay easier and more timely in the long run.

Even if you are doing this with redis, there are two far better methods of doing it - with lexical ranges, or with RediSearch's autocomplete, which is way more powerful - uses a compact trie, has fuzzy matching with a Levenshtein automaton, scoring, payloads, etc. See http://redisearch.io/Commands/#ftsugget (Full disclosure: I'm the author of that project)

IDK, having survived many ... MANY ES outages, I’d take REDIS in a heartbeat if it gives me the functionality I need.

it's amazing how every single person i know that used ES has had a freakton of bad experiences with ES. and it's still the only ok solution in this area.

What about Solr?

Also, SQLite Full Text Search with a prefix query (you could also use `:memory:` as the address to simulate in-memory redis life):

https://sqlite.org/fts3.html (and also https://sqlite.org/fts5.html) -- make sure to use the a stemming tokenizer as well.

Why SQLite might be a good idea for your project/small service: https://www.sqlite.org/whentouse.html

Actually, at that point you’d want to use PostgreSQL’s Full Text Search.

SQLite’s is a lot more limited in performance, and a lot less usable.

SQLite wins in one area that can be crucial -- simplicity. PostgreSQL is a fantastic and robust database, and it's FTS capabilities are almost certainly good-enough (especially if you consider SQLite's to be good-enough), but it is necessarily complex to support the amount of robustness it offers.

SQLite offers a fraction of the robustness of Postgres, but that difference is not necessarily reflected in the correctness/speed of a simple full text search capability meant to support auto-complete (as in the article). Unfortunately I don't have number to back up this assertion, but I'd be very surprised if SQLite FTS was even 10x slower, maybe someone should do that comparison, I'll put it down and make a humble attempt at comparing these two approaches someday.

Make sure to also run a test with multiple threads concurrently interacting with SQLite.

Due to SQLite's exclusive locking mechanism, this causes actual issues with concurrent writes and reads.

Good point - but reads never blocked except during a (concurrent) write, which wouldn't likely be much of a problem with the presumably read-heavy autocomplete scenario described here.

Incidentally, even that's not even an issue anymore, if you enable SQLite's write-ahead logging support:

https://www.sqlite.org/wal.html

Came here to say something similar, except s/elastic search/solr/. I like redis, and use it for various things, but autocomplete is something I'd rather use a different tech to achieve.

That all said, the comments above on redisearch and and lexicographic ranges are worth having a look at. If you already have redis in your stack and can't/don't want to add another tech and you don't need anything particularly advanced, that could be a better option than grabbing a lucene backed sledgehammer.

Is this not a perfect use case for a trie? Can you make a trie in Redis?

I have not implemented a trie myself, but apparently the problem is they take up a lot of space: http://www.drdobbs.com/database/ternary-search-trees/1844105...

A trie and a ternary search tree are two very different beasts. Tries can are very memory efficient, as common prefixes in terms are bunched together, and nodes are not split on every letter.

I think so, specifically a ternary search tree. While you can implement one on top of redis, I’m pretty sure it would be significantly slower than an in memory TST.

The good news, it more popular now than before... sigh. https://hn.algolia.com/?query=Auto%20Complete%20with%20Redis...

Can we please put [2010] in the title?

I’m glad to learn of this, but note that it’s from 2010.

OP should put 2010 in the title.

We've updated the title, thanks. Sorry for the delay!

actually good idea

Reply on news.ycombinator.com