karterk

With brute-force you have no idea about what letters could follow a given letter, but with a Trie you already know the possible combinations so you avoid needless permutations.

There is another aspect of tries that make them really useful: you can do fast, fuzzy word searches on a trie.

In Typesense[1], I've implemented fuzzy search based on levenshtein damerau distance and it's incredibly fast. I've found this approach to be a much better (faster + more flexible) alternative to Peter Norvig's brute-force based spell-checker that is quite a popular post [2].

[1]: https://github.com/typesense/typesense [2]: https://norvig.com/spell-correct.html

Thank you for your kind words. We are just getting started :)

Yes, please see here: https://github.com/typesense/typesense/issues/122#issuecomme...

The latest RC build is `0.22.0.rcs18`.

Finally added support for indexing and/or separating on specific symbols in the ongoing pre-release builds. With that, I think Typesense should be able to handle code search, but I have never tried to index and search on code myself :)

A problem close to my heart. Good search is certainly still too difficult to pull off for small teams, and this was one of my motivations for building and open sourcing Typesense[1].

Most people think of search and immediately think of large data sets, but the problems that plague smaller datasets are equally interesting. It's less about performance and more about relevance. For e.g. searching across multiple fields for a compound query like "taylor swift style", requires breaking the query into segments (taylor swift | style) before searching for the appropriate fields. There are also a class of problems that traditional search engines that rely on BM25 or TF-IDF for ranking cannot reliably solve (e.g. searching on small texts like titles) where you have to consider distance between matching words (which TF-IDF and BM25 miss). Lastly, there is also personalization which is almost always left as an exercise to the reader :)

[1]: https://github.com/typesense/typesense

Happy to help with the transition to Typesense! Email and Calendly link in my HN profile.

Terms will be common across the group. The scoped API key helps you guarantee that you can never accidentally access another customer's search data since the filter condition will be baked into the query itself and you also use a separate key per customer.

Certainly that's possible but doing fast type ahead fuzzy search requires keeping large parts of the indexing data structure in-memory.

There are, of course, many use cases where one does not need that speed. Eventually, like Redis we will probably have an option to use SSD storage smartly for these non-latency sensitive use cases. That's not our immediate focus though.

The reason reason people overpay for large databases on RDS: RDS spend makes little difference to a lot of companies when the alternative is hosting it in-house. AWS provides multi-az failover and ability to add read-replicas with a click of a button. The support is also pretty good if you pay for the premium tier: I've had a RDS support member join major database migrations (might not happen for smaller companies, but we are talking about large spenders here).

> The caste system prevent a huge part of the population to contribute to the demographic dividends

Over the years India has implemented several affirmative action programs (locally called "reservations") that ensures a more level playing field.

India has actually done reasonably well economically since 1995. Unless you can point to specific studies that correlate India's less-than-spectacular economic performance to the caste system directly, this is a fairly baseless statement. You only have to take a quick look at the last 10 year average GDP.

Interested, email in profile.

I see. Perhaps, because we're using the native CPP client we faced no such crash issues with RocksDB. We have also handled transactions at a higher layer.

All the best with MeiliSearch!

LMDB and RockDB are both great projects, but how much performance you can get out of them would depend on the larger architecture of the system they are being integrated into. Both projects provide tens of flags to adjust read/write amplification to customize them for a particular use case. You will often see public benchmarks of these systems being updated with suggestions from both sides on less-than-optimal configurations being used!

In the case of Typesense, RocksDB is not even a top-10 contributor to the overall latency involved in serving the result. In any case, it would be good to clarify a few things:

> As we don’t use RocksDB but LMDB, we use a lot less real memory than key-value stores that uses a user-side cache system.

Typesense stores only the raw-data in RocksDB. All indexing data structures for filtering, faceting etc. are compact in-memory data structures stored outside. The only fixed memory cost from RocksDB is an in-memory table that is used to buffer writes (see the next point) before being flushed to disk. In practice, this is a trivial percentage of memory used when compared to other data structures.

> LSM-Tree key-value store like RocksDB that needs to merge/compact pages of key-values pairs before being able to return it too you

This happens in-memory and is flushed to the disk in batches. Merging of on-disk SST files happens in the background with no real impact on reads. The advantage of this approach though is that it gets you really good batched write throughput [0] (the above caveat on the difficulty of benchmarking applies).

In summary, like all systems, choosing a storage system involves many trade-offs and what really matters is what works best for your architecture.

[0]: https://dgraph.io/blog/post/badger-lmdb-boltdb/

Thank you for your kind words. Made my day. Typesense is 100% bootstrapped, and a labor of love[0]. We will certainly do our best to keep making it better.

[0]: https://typesense.org/blog/the-unreasonable-effectiveness-of...

Typesense offers fast, in-memory geosearch: https://github.com/typesense/typesense

Making the client work only with only a specific ES version seems like an oversight[1], but it is really difficult to say given the back and forth between AWS and Elastic here. I hope it is not intentional.

[1]: https://twitter.com/xeraa/status/1423071203753869313

I certainly agree. However, many people don't have that dedicated focused time. I wanted to give an alternative perspective on what one can do when you can't find such long stretches of time.

I used to code for an hour every week day and maybe 3-4 hours on weekend. But there was also a lot of "background processing" of what I plan to work on next and how to implement it. The more background processing I did, the faster I was in the actual implementation. So those hours I actually spent on the keyboard were really productive.

I don't disagree with you, and which is why I qualified my thoughts with a filter of a "large and growing market". Impossible to fail in such a market if your goal is not to be a billion dollar company.

True, but when we started we bet on certain trends that are just getting mainstream now. Having said that, large markets tend to have a lot of niches. You can certainly carve your own. It might not be a billion dollar niche, but that was never the point :)

1. Typesense is pretty stable and we are really careful about retaining backward compatibility. Our release cycles are slow (we give RC builds for people wanting a feature urgently) and we test a lot. The version number is just a number: Terraform just hit 1.0 last month :)

2. We've a hosted cloud version: https://cloud.typesense.org/ -- and we also added a Sponsor button on Github because so many people have been asking us for it.

As a maintainer of another open-source search project (https://github.com/typesense/typesense), this whole saga has left a pretty sour taste.

At the end of the day, being truly committed to open source is difficult once you start feeling the revenue pressure. The very openness of the license that drives the growth of the project and the community in the early days becomes an albatross around your neck. Once you have raised a lot of money, there is tremendous pressure sooner or later to own the market and to justify the insane revenue multiples at which many companies are raising. It's a delicate path.

If you set the expectations right, I think the Cloud market is large enough to accommodate several companies in most verticals. However, "growth at all costs" requires walking back on your ideals and promises.

Important to note that it's only Twitter which seems to have a problem here complying with the regulations. The other social networks have complied.

InfluxDB could have become Grafana if they had focussed better. It was a breathe of fresh in a space where existing solutions were horrendously complicated. I suspect that they were under a lot of pressure to monetize and lost some way in attempting to do that.

Agree, it's fixed now.

I did benchmark extensively 4-5 years ago, but I don't have those numbers with me. Tries are quite expensive memory-wise by design, but I found that ART gave the best balance between speed (by exploiting cache locality) and memory. State of art might have improved by now.

As far as Typesense goes though, I found that the actual posting lists, document listings, and other faceting/sorting related indexing data structures is where the bigger overhead is, especially for larger datasets.

Good catch :) We're testing a new feature on a RC build that the demo is using. It has some quirks that we are working on: thanks for the feedback!

Sorry about that. We've a RC build that we are testing a new feature with at the moment on that cluster, and unfortunately this demo is hosted on that :-/

Exact word queries are on our near-term todo list. We've already added support for exclusion via "-" operator in the last release.

Dynamic synonyms will require more thought given the machine learning aspects involved. May require domain specific models. And I also wonder how "off-the-shelf" it will really be in practice.