Hacker News Reader

Comment by jpgvm | Hacker News Reader

Given the shoutouts to Burntsushi and Lemire this is almost certainly a bitmap trigram index based engine similar to https://github.com/google/zoekt

The index is likely based on Roaring bitmaps, presumably https://github.com/RoaringBitmap/roaring-rs in this case.

Nice architecture, exactly how I would have done it also.

View on HN

Nope, I would have used an existing search solution, like xapian. It does so much more, and much faster.

You need to support a proper query syntax, with tags, rankings, stopwords, stemming. Then you need to have a proper db backend (reverse indices). Trigrams dont help for regex. Then a templated representation. Google codesearch would do only the 2nd of 3. ElasticSearch is commercial, and only java.

Doing that from scratch is a bit silly.

Code search typically does not need many (most?) full-text search features like TF-IDF, stopwords, stemming, tagging, etc. It's a categorically different domain.

Oh OK, you have clearly spent more time thinking about this problem than the team of engineers at GitHub who've been researching code search at scale for more than four years. I bet they feel real silly right now knowing they could have shipped this search engine in a couple weeks taping together off-the-shelf libraries if they only had your talent for software architecture.

Sure, I did. I've implemented a proper search for a very big companies document and knowledge base. Similar to gmane, which also used xapian. Much better than what I see there. Or with the old google code search

> Trigrams dont help for regex.

https://swtch.com/~rsc/regexp/regexp4.html

Everything you are talking about is useful for full-text search. It's practically pointless for code search. Trigrams definitely help for regex, you can make use of a trigram index for a quick false positive index lookup.

Code and log search are two specialized use-cases of search that definitely warrant a non-full-text approach and as far as I am aware the trigram bitmap index would be considered state of the art for both.

That isn't to say you can't solve the problem with a full-text search engine, many people do with the solutions you alluded to. However they are drastically less efficient and probably out of the question at Githubs scale.

PostgreSQL uses trigrams to optimize regex searches.

Reply on news.ycombinator.com