My guess, back when I was doing code search at Apple, was that he was actually scanning all the docs with his fast regexp, which would be do-able with the number of machines at his disposal + the expected traffic.
If Russell Cox wrote it, it must be good. I programmed competitively with him at USACO and in college (we got to 8th best college team in the world), and he was a consistent ass-kicker. Hardcore and disciplined and fast.
That does searching of text, without generating an index. While this is fast, you are still have search time linear in the size of your searchable text.
If you used a suffix tree as an index, you'd get time complexity strongly sublinear in text length.
In summary, if the regex matching complexity dwarfs the corpus size, you want Thompson NFA. If your corpus size dwarfs the regex complexity, you want suffix tree indexes. It's not clear to me if the two approaches can be combined, but if they are, I'd like to know.
I agree that Google probably just throws HW at the problem, but you could also build something custom if it really needed to scale. Just record what people look for and keep an index for the common chunks of logic.
So, if people often search for someones name or date you keep a list of what satisfies that so you can quickly eliminate large numbers of documents without doing a full text search. You could also reduce the document to a list of tokens and search that list before the file etc.
My guess, back when I was doing code search at Apple, was that he was actually scanning all the docs with his fast regexp, which would be do-able with the number of machines at his disposal + the expected traffic.
If anyone knows any differently, I'm all ears. :)