19 ms·
How Google Code Search Worked: Regex Matching with a Trigram Index (2012)
- softwaredoug 8y agoVery cool! - Most search problems are solved this way - interesting index data modeling to the needed use cases, not magic machine learning neural network unicorns. Many want to sell you the latter. The thing that gets the job done is usually the former. One big reasons for this is the need for really good training data to do supervised learning on search problems. If you’re Google or Wikipedia, you can get this data. But many struggle to understand what a good result was for a query based on clicks and other user data due to low volumes of traffic.
- kierenj 8y agoI'm gonna be that guy and ask you not to refer to OCD in a flippant/casual sense please
- softwaredoug 8y agoAh thanks for catching that. Changed to “obsessed”
- gauravphoenix 8y ago>Most search problems are solved this way - interesting index data modeling to the needed use cases, not magic machin learning neural network unicorns. Many want to sell you the latter. The thing that gets the job done is usually the former. occam's razor
- atdt 8y agoAs an aside: most of the Wikimedia Foundation's analytics data is available for anyone to download (https://wikitech.wikimedia.org/wiki/Analytics#Datasets https://wikitech.wikimedia.org/wiki/Analytics#Datasets). There is some link-rot to wade through, but try asking on #wikimedia-analytics on freenode if you can't find something.
- kqr 8y agoThen you're using magic machine learning wrong. I'm part of a small team who uses it exactly for the purpose of giving intelligent search to non-Googles and non-Wikipedias, and we have a very good track record. The key is to use machine learning to generalize user behavior across multiple items in roughly the same category, rather than individual items. In fact, with tiny amounts of data you should pretty much never deal in individual items -- always in groups of related items.
- softwaredoug 8y agoUndoubtedly I’m doing a lot wrong :) Yup that’s one method I teach people in Learning to Rank training. In addition to reducing dimensionality on queries, you can also do so by geo and user depending on the domain. But do you want to do this much munging of training data? Even still the basis for how you group similar information needs isn’t always obvious, and most teams prefer a simpler solution they can understand and manage that’s not ML based. A lot depends on the team that’s ultimately going to maintain the solution.
- softwaredoug 8y agoI’d also be curious who your team is exactly and what are their results? Be very interested in learning more
- chudi 8y agoWhen you said that you work in groups, the groups are discovered with a clustering technique and then you apply the learning to rank algos ?
- softwaredoug 8y agoIn most learning to rank data sets, the only notion of a "query" is a numerical identifier that groups a set of features and a grade. Your goal is to optimize the ordering in that group. That group can really be a user, a query pattern, a location, or a bazillion other groupings likely to share similar rankings. For example, a common training data storage format looks like grade(0-4) queryId list of feature values... Such as: 4 qid:1 1:0.5 2:0.24 # a doc with these features is 'good' for this query 0 qid:1 1:-0.5 2:0.24 # a bad doc for query id 1 is described by these features Features in an LTR context are some relationship between the query and doc (such as scores computed from Solr/Elasticsearch queries) Of course turning clicks/session info into grades isn't easy. One way to go about it is with click models (https://pdfs.semanticscholar.org/0b19/b37da5e438e6355418c726469f6a00473dc3.pdf https://pdfs.semanticscholar.org/0b19/b37da5e438e6355418c726...). Another way is to equate conversions in a session with one of the grades (a purchase is a 4). Needless to say, such usage data is sparse for long tail queries (queries that rarely happen - 'fuscha shoes'). Luckily it's not sparse for head queries (common queries - 'shoes'). So those head queries can provide some benefit, helping to generalize to the rare long tail queries. You'll see a lot of patterns that are modifiers on head queries. Like 'shoes' is a head query. But 'blue shoes' and 'purple shoes' and other 'color shoes' are tail queries. You can do a lot with that insight - Supervised grouping of queries into one 'query id' by watching how users refine queries. For example users type "shoes" then in the same session add one color adjective "red shoes". Using that to group '<color> shoes' queries - Unsupervised clustering of similar sessions or searches where users seem to expect ranking to perform similarly based on user behavior The downside/tradeoff is you lose a lot of nuance that you're getting with per-query training data. But it's a technique people use. It also substitutes one ML problem for another, which may or may not be harder than the original one
- rurban 8y agoThis was posted here at least 10x before. The last time someone posted a link to a hopeful successor at github: https://news.ycombinator.com/item?id=18022357 https://news.ycombinator.com/item?id=18022357
- petters 8y agoI wish GitHub had decent search functionality.
- enriquto 8y agoyou mean, searching the past history of all codes?
- petters 8y agoMostly searching for regexes in code and in filenames. But yes, history would sometimes be useful too. And this is really the bare minimum. An even better search would e.g. allow searching for identifiers (comments and strings disregarded).
- enriquto 8y agoyeah, that would be wonderful indeed! The current search functionality of github is nearly useless, which is a shame.
- rpedela 8y agoI believe GitHub uses ES, and currently allowing users to perform regex can bog down the entire cluster if the regex is malformed. This is a problem with Solr too. I believe there was some effort to resolve this at the Lucene level, but I am not sure the status. In other words, I agree with you but I also know it is an extremely hard problem to solve at Github's scale.
- btown 8y agoAre there any good writeups on how to implement the trigram index side of this? For instance, the code alludes to the idea that you could store each trigram as a bitmap over documents, then the Boolean combinations become bitwise operations. I suppose you could keep the bitmaps in compressed (or even probabilistic sketch) form, then decompress only those required for a query, but is this the right intuition? Are there lower-level libraries or databases that do this kind of thing well, rather than rolling your own on a KV store or using something monstrous like ElasticSearch?
- shabble 8y agohttps://wiki.postgresql.org/images/6/6c/Index_support_for_regular_expression_search.pdf https://wiki.postgresql.org/images/6/6c/Index_support_for_re... is I think the slides for a conference talk on implementing within Postgres
- JaggedNZ 8y agoPostgres FTS with trigrams (pg_trigram extension) works really well for many search applications. Most of the effort would be tuning the FTS dictionary.
- dreamer_soul 8y agoMy issue with it is that a small term such as one word doesn't event match to a record which is weird, I'm using it with rails. Thinking of using elastic search to help with that
- deleted 8y ago[deleted]
- user5994461 8y agoThe project was released by the original author here. https://github.com/google/codesearch https://github.com/google/codesearch There is no information on the subject besides the 3 blog posts and the proof of concept.
- 8y ago
- was_boring 8y agoHonestly, this comment is garbage. The author doesn't go into machine learning vs not. The comment appears to be grasping at straws to be controversial and drive clicks to the link at the bottom. I understand that replying to it and pointing it out may result in the wrath of mods, but it truly is so transparent that it's disgusting.
- softwaredoug 8y agoDeleted the link I did write a book on the topic, developed the Elasticsearch learning to rank plugin, and have helped several Alexa top 50 sites deliver more accurate search I’m only pointing out that search is oversold industry, but when you read about what Google actually does it’s more normal stuff that we would all probably do to solve a similar problem. (for those curious it was a link to content at a community conference i help run - pointing out how hard ML can be for search. I admit a bit tangential perhaps)
- isoos 8y agoCould you please re-share the link? I have seen the original text of your post, thought that this is an interesting topic and I'd like to find time to watch them.
- softwaredoug 8y agoSure here it is sadly no videos, just slides https://haystackconf.com/europe2018/ https://haystackconf.com/europe2018/
- sctb 8y agoWe detached this subthread from https://news.ycombinator.com/item?id=18582578 https://news.ycombinator.com/item?id=18582578 and marked it off-topic.
- sn41 8y agoFor a reasonable code base, say the linux kernel source code, how large is the trigram index? Is it necessary that the index be kept in memory?
- nestorD 8y ago77MB for the Linux 3.1.3 kernel sources according to the "Implementation" section of the article.
- PunchTornado 8y agoBe an inter with Jeff Dean as a mentor...
- rasmi 8y agoThe search features discussed in the article are now available through Google Cloud Source Repositories: https://cloud.google.com/source-repositories/docs/searching-code https://cloud.google.com/source-repositories/docs/searching-...
- secure 8y agoShameless plug: This is what I based Debian Code Search on: https://codesearch.debian.net/ https://codesearch.debian.net/ See also https://codesearch.debian.net/research/bsc-thesis.pdf https://codesearch.debian.net/research/bsc-thesis.pdf if you’re interested in details.
- blattimwind 8y agoA bit of a funny full circle, isn't it?
- devoply 8y agoIs your code open source?
- LukeShu 8y agohttps://github.com/Debian/dcs https://github.com/Debian/dcs
- techbio 8y agoTrigrams are of three characters, not tokens. This is not the obvious search strategy for code, lacking semantic structure, though apparently it suits regex searchable indexes.
- karmakaze 8y agoHow fitting. I've been working on making Etsy houndd [0] available as SaaS. Houndd uses a trigram index with regexp and can search all the repos I care about in ms. The demo page works. The signup just send me a confirmation email and the setup is still manual, so expect hours/day delay. Aiming to have this all automated by tomorrow. Appreciate any/all feedback. [0] https://github.com/etsy/hound https://github.com/etsy/hound [1] https://gitgrep.com https://gitgrep.com
- deleted 8y ago[deleted]
- xooms 8y agoHave you made sure that Git people are OK with the name GitGrep? See https://git-scm.com/about/trademark https://git-scm.com/about/trademark for details.
- mslot 8y agoIf you want to build something like this yourself, Postgres has a Trigram index: https://www.postgresql.org/docs/current/pgtrgm.html https://www.postgresql.org/docs/current/pgtrgm.html
- ta1234567890 8y agoThat's great. It seems like it only supports character-level trigrams though. Do you know of any tools that can create word-level trigrams from Postgres?
- ravenstine 8y agoThis reminds me of a browser-side search I once wrote using a combination of regex, Soundex, and Damerau-Levenshtein. The reason I made this browser-side is because the app doesn't have that many records that it needed to be on the server; the records were in the hundreds to thousands, not millions. https://github.com/SCPR/fire-tracker/blob/master/app/lib/search-index.js https://github.com/SCPR/fire-tracker/blob/master/app/lib/sea... Not the best code I've ever written by far, but it was a neat little experiment. Basically, indexing each record with Soundex(phonetics) makes the search semi-tolerant to misspellings and also brings up similar-sounding results, while Damerau-Levenshtein is used to sort the results by closeness. I also had it index timestamps with Here it is in action: https://firetracker.scpr.org/archive https://firetracker.scpr.org/archive As you can see, you can misspell search terms and it will usually get it right. Granted, a lot of unrelated records usually come up in a search, but the important thing is the user should get what they're looking for in the first few results, usually the first. Regex is a powerful thing.
- sqs 8y agoAnother shameless plug: Sourcegraph uses this for indexed search via Zoekt (it also has index-less live search). Check out the cmd/indexed-search code at https://github.com/sourcegraph/sourcegraph https://github.com/sourcegraph/sourcegraph.
- z3t4 8y agoModern servers have a lot of compute resources and memory compared to 15 years back, before doing any optimizations I would start out with a naive full text search, which will most likely be fast enough. A full code search using regex is also more powerful for users. Imagine if you could use Regex when searching on Github or Google!? Source code use relative little space, If you strip out the markup/JS from web sites, they also take up relative little space. The only problem however is to educate users on how to do effective searches.
- humbledrone 8y agoI think you might be underestimating the size of the document corpus that you'd be running over.
- z3t4 8y agoLets say there are 5 billion url's with an average of 10 KiB of data (if you take out JS/CSS/images etc), and one server has 50 GB or ram you would need 1000 servers, which is very small considered Google probably have one million servers deployed. I just tried to text search your comment on Google and it found your post! So Google is already doing full text search, and does it in less then one second (0.69 to be precise). There are probably many reasons why they don't allow Regex, probably because it would be very easy to "scrape" resources such as e-mail addresses, credit card numbers, etc. It would however be cool if Google would allow you to search structured data, for example find 100 recipes that has eggs in it :P Silly example, but the possibilities are endless!
- mcbits 8y agoMaybe you should clarify what you meant by "naive full text search" because that usually means scanning all documents character-by-character to match the characters in the query, which is definitely not what Google does.
- humbledrone 8y agoBut that's exactly my point -- when you get to the stage where you have 1,000 servers with 50G of RAM each, you have gotten to the point where an optimization like an inverted index is completely sensible. The design you propose has to do a full regex scan over 50 TB of RAM for every. single. user. query. For Pete's sake! This is definitely the realm where the computational costs make it worthwhile to spend engineering resources to optimize, especially if you are going to serve lots of users.
- joatmon-snoo 8y agoFWIW kythe.io is the modern successor that does this internally at Google. Haven't worked on it, but have written some code that's a client. Unfortunately I think the indexing pipelines aren't publically available.
- Thorrez 8y agoYou can still use Google Code Search on the Chrome codebase. https://cs.chromium.org https://cs.chromium.org For example here's a hacky regex that finds lambdas: https://cs.chromium.org/search/?q=%5CW%5C%5B%5B%5E%5C%5D%5D*%5C%5D%5Cs*%5C(%5B%5E)%5D*%5C)%5Cs*%7B+lang:c%2B%2B&sq=package:chromium&type=cs https://cs.chromium.org/search/?q=%5CW%5C%5B%5B%5E%5C%5D%5D*...
- ngnear 8y agoYou can store a local search index of your code using https://github.com/google/codesearch https://github.com/google/codesearch, which uses this algorithm in the background.