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]"
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)
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.
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.
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:
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.
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.
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.