Ask HN: What kind of index is Google using here?

* Plan 9 from User Space - http://plan9.us

* vx32/9vx - http://pdos.csail.mit.edu/~baford/vm/

* libtask - http://swtch.com/libtask/

(Plus quite a few bits of Plan 9 itself, obviously.)

Edit: forgot this really cool storage system: http://doc.cat-v.org/plan_9/misc/foundation/

Say your query is \d+(th|nd|rd), and your searchable text is "The 3rd planet from the sun is 20000000 miles away." Your tree search will hit 2, then fail on 20, then 3, then 3r, then 3rd, and then terminate successfully. So we followed 5 pointers, and tested another 20 or so for nullity.

This was independent of the length of the searchable text (but not the number of found matches). It would have performed equally well on "The 3rd planet from the sun is 20000000 miles away. Lorem ipsum (insert 10mb of random Latin here)".

From the docs:

(The way "study" works is this: a linked list of every character in the string to be searched is made, so we know, for example, where all the 'k' characters are. From each search string, the rarest character is selected, based on some static frequency tables constructed from some C programs and English text. Only those places that contain this "rarest" character are examined.)

Basically, this is not what Google is doing for code search.

That's correct. It's one of the challenging parts.

But consider that you can use the linked algorithm, and a bit of trickiness, to create an index already:

- Step (a): prepare another version of the document where every digit is replaced with 0, every word char with 'a', etc.

- Step (b): note how much better it compresses. :)

- Step (c): Perform a similar 'weakening' on the search regex.

- Step (d): Done! Not an exact index, but it will allow you to quickly eliminate a large number of documents.

You can also combine this approach with text-based ones for the cases where there are parts of the search regex that contain literal text. (This is almost certainly the most common use case).

Or you could make it hierarchical if you need to by creating several watered-down texts for each input with different levels of substitution.

---------------------------------------------------

Since this is the sort of thing that's fun to think about, here's a whole different approach:

- Break each document apart into code lines.

- Create a hierarchical tree: leaves are the code snippets (with a pointer back to source doc), each node represents a clustering-by-text-similarity of all its children. (Appropriate distance measure left as an exercise for the reader. :) )

- Let's say that for two regular expressions, RA & RB, RA < RB iff any text matched by RA will also be matched by RB.

- At each node, create a regular expression R so that for each child regex C, C < R. (The leaves become a regex that simply matches the source line literally.) Along the way, make a best effort to restrict the length of R by introducing generalizations (R can't simply be Ca|Cb|Cc...) without making it so loose that it matches everything.

- Then, searching for a regex S can be done recursively: For each child regex R of the current node, if you can construct a new regex T such that T < S and T < R, descend into that node.

n.b. I typed that out in a hurry and without being rigorous... so it's probably not quite right, but an interesting path to think about exploring. Also: testing if one regex is less than another (as defined above) is actually fairly straightforward, even though it seems hard.

(And a quick edit to add: the last step is definitely wrong. Unfortunately I need to hop onto a conference call, so it'll have to wait until the indefinite future.)

(Edit to that: I think I fixed it for now. Shorter version: if the intersection of S and R is nonempty, descend.)

Indexing Documents into Barrels -- After each document is parsed, it is encoded into a number of barrels. Every word is converted into a wordID by using an in-memory hash table -- the lexicon. New additions to the lexicon hash table are logged to a file. Once the words are converted into wordID's, their occurrences in the current document are translated into hit lists and are written into the forward barrels. The main difficulty with parallelization of the indexing phase is that the lexicon needs to be shared. Instead of sharing the lexicon, we took the approach of writing a log of all the extra words that were not in a base lexicon, which we fixed at 14 million words. That way multiple indexers can run in parallel and then the small log file of extra words can be processed by one final indexer.

So we have a hash table of words/searches -> results

Because we have this, we can regex search the keys, and end up with the result pages.

we do have other options though. It could be:

a) magic b) a trade secret (think PidgeonRank :-) )

I'm pretty sure EN just greps subject + output of something like 'strings' though, it chugs pretty hard on broad searches.