6 ms·
Given the shoutouts to Burntsushi and Lemire this is almost certainly a bitmap trigram index based engine similar to https://github.com/google/zoekt https://git
by jpgvm 5y ago
Given the shoutouts to Burntsushi and Lemire this is almost certainly a bitmap trigram index based engine similar to https://github.com/google/zoekt https://github.com/google/zoekt
The index is likely based on Roaring bitmaps, presumably https://github.com/RoaringBitmap/roaring-rs https://github.com/RoaringBitmap/roaring-rs in this case.
Nice architecture, exactly how I would have done it also.
- rurban 5y agoNope, 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.
- preseinger 5y agoCode search typically does not need many (most?) full-text search features like TF-IDF, stopwords, stemming, tagging, etc. It's a categorically different domain.
- tanoku 5y agoOh 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.
- rurban 5y agoSure, 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
- yencabulator 5y ago> Trigrams dont help for regex. https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html
- jpgvm 5y agoEverything 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.
- jeltz 5y agoPostgreSQL uses trigrams to optimize regex searches.
- v1g1l4nt3 5y agoRelated: https://srcgr.ph/zoekt-memory-optimizations https://srcgr.ph/zoekt-memory-optimizations