|
|
|
|
|
|
by derefr
2824 days ago
|
|
|
On your local machine, you can get away with a linear scan (as "git grep" does), because nothing else is contending for time with your search. "git grep" is actually very costly in terms of CPU and disk IO, but you don't notice, because you're only running one "git grep" at once, and so nothing is contending for those resources. On GitHub, tens of thousands of searches will be happening at once on the same search cluster. If they were all literally doing a "git grep" (a linear scan of the associated repo data), the disk caches would thrash back and forth between queries, and nothing could be answered in less than 30 seconds. The only way for GitHub to respond to code searches at scale in a reasonable time, is to have a pre-built index. If the index was per repo, that'd be a kind of partitioned index; and there's no DBMS that I know of that can handle a partitioned object having 58 million partitions. It makes much more sense to have an unpartitioned index... which effectively implies "cross-repo search" (because, once you have an unpartitioned index built up over all your repos, it costs nothing to enable someone to search that entire index at once.) |
|
|
With ever-cheaper RAM, ever-faster SSDs, and cloud computing, it could actually make sense, now or soon, to scan through an entire repo, either on "disk" or in RAM. I started building an app that would suck down any GitHub repo by simulating a git clone in the back-end, in the time it took you to type in your query, and hold it in RAM across queries. As a user, I'm sure I would gladly pay however many cents it costs to take up this much RAM when I'm on the search page over the course of a month.
Even if a linear scan isn't feasible, regex search at scale is not an unsolved problem, and GitHub has access to world-class engineers. Google Code used trigrams to do regex search with an index (https://swtch.com/~rsc/regexp/regexp4.html). Sourcegraph offers regex search.