6 ms·

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

116 points by pc 17y ago

crux_ 17y ago
Something like this? - Regular expression searching on compressed text, http://portal.acm.org/citation.cfm?id=967612 http://portal.acm.org/citation.cfm?id=967612
- mbrubeck 17y ago
  The cost of that algorithm still grows linearly with respect to the length of the compressed text. It's possible Google is doing something like this (searching over the entire corpus until they find a match), but is there any work on precomputing an actual "index" to speed up this type of search?
  - crux_ 17y ago
    I'm certain there are many approaches to be found via citation-following. 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.)
    - crux_ 17y ago
      Replying to myself, since editing was getting out of control. A neat property of the 2nd approach is that if you ever reach a node R where R < S you're done: all children will be matched. A less neat property is that it won't allow multi-line matches, but I'm not sure those are allowed anyway.
deleted 17y ago
[deleted]
drcode 17y ago
Is your question "How do you create an index that allows regexes?" In that case, I'd like to know the answer to the question, as well.
- thwarted 17y ago
  perl has a "study" function that examines a string in anticipation of doing many pattern matches on it. I'm not sure what it does exactly, but the kind of structures it creates could be serialized and stored along with an input file (or perhaps replace it), and used as kind of regular expression optimized index. This isn't necessarily an "index" in the normal sense, but then, neither is the likes of a full-text index either. But really, any data structures that are optimized for a specific kind of processing are indexes.
  - jrockway 17y ago
    study does not do anything really interesting. It looks up substrings in a table of substring -> average frequency. It then scans for the rarest character first, so that it can fail quickly for most input. 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.
    - thwarted 17y ago
      Study doesn't do anything really interesting, but neither is creating a keyword index for a keyword based search all that interesting either. Considering that Google code search is not intended to search English (for which their regular search technology would most likely suffice for that) using regular expressions, then I agree that the naive study implementation you've quoted is, basically, not what Google is using for code search. However, there's no reason that the frequency tables need to be static nor need to be constructed solely from from C programs and English text. Frequency tables can be continuously updated based on the input corpus and the input corpus should be the code that is being searched. Part of search is being able to rule out significant portions of the search space in the name of getting positive results as fast as possible, so being able to fail quickly for most inputs (considering the example regular expression only returns three hits, it seems a wide majority don't match), a study-like implementation would appear to be a possibility.
wooster 17y ago
AFAIK, Google Code Search was written by Russ Cox, who also wrote this: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html 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. :)
- nostrademons 17y ago
  If anyone knows any differently, I doubt they'd be able to tell you. ;-)
- Retric 17y ago
  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.
- deleted 17y ago
  [deleted]
- fizx 17y ago
  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.
- bravura 17y ago
  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.
simonw 17y ago
I've always wanted to know that.
mtrimpe 17y ago
It might be possible to adapt a regex state machine to use an AVL TDAWG ( http://www.ssp.isee.kyushu-u.ac.jp/~inenaga/papers/tcs-ternary.pdf http://www.ssp.isee.kyushu-u.ac.jp/~inenaga/papers/tcs-terna... )
johngunderman 17y ago
I am 100% postulating here, but this is what seems most likely to me: Google is known for MapReduce. It seems like it would make regex searches manageable when put in such an algorithm. All Google would have to do would be to take whatever key system they use for their big-tables and use MapReduce to expand the regex over the keys. Then they just have to return the data associated with those keys.
- tumult 17y ago
  ..what? I would love to see you try to explain how you think this works :)
  - johngunderman 17y ago
    to quote http://infolab.stanford.edu/~backrub/google.html http://infolab.stanford.edu/~backrub/google.html 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 :-) )
    - tumult 17y ago
      Quote is unrelated to what you are saying! use MapReduce to expand the regex over the keys 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. ... Looking forward to further explanations!
miracle 17y ago
Easynews also has a global search where you can search through all the newsgroup posts with a regular expression (> 150 days). You might ask them? They are certainly not as secrective as google is ;)
- jrockway 17y ago
  Is the global search really a regex? I thought it was just substrings.
  - s3graham 17y ago
    The labels are links to regularexpressions.info so I'd guess yes. I'm pretty sure EN just greps subject + output of something like 'strings' though, it chugs pretty hard on broad searches.
tlrobinson 17y ago
This is off-topic, but I just realized Google Code Search is great for seeing where code you open source ends up. Came across a few things I had no idea were using my code. Kinda cool.
- mc 17y ago
  Tom, did you know there are extra filters you can use to search Github.com? Try "tlrobinson package:github.com lang:javascript"
robk 17y ago
IIRC, this was a rather high-compute-cost project inside of Google, far more so than other search projects. Obviously it was a favorite though of the eng decision makers, so was well cared for resource-wise.
pmorici 17y ago
This presentation talks about using N-grams to make an regex searchable index http://www.informatik.hu-berlin.de/forschung/gebiete/wbi/teaching/archive/sose08/pr_text/vortraege/ngram_indexing.pdf http://www.informatik.hu-berlin.de/forschung/gebiete/wbi/tea...
- fizx 17y ago
  No complexity analysis. Random student results. It's viable to build an index with n-grams, but I don't think you'd get any benefit over suffix-tree search. There might be a way to select n-grams cleverly some of the time, but you can also easily run into pathological cases.
mc 17y ago
I'd (probably) consider building and searching an index of ASTs (http://en.wikipedia.org/wiki/Abstract_syntax_tree http://en.wikipedia.org/wiki/Abstract_syntax_tree). Not only would it allow searching with regexp, but it could allow more sophisticated search queries like "Search all my Ruby code for blocks that rescue StandardError and are not followed by an ensure clause"
- gruseom 17y ago
  But you'd have to do that separately for every language. Edit: the OP is such a great question. I've been saving up the joke of commenting "How is this Hacker News?" on the most literally appropriate HN post I run across... and almost used it on this one. Sadly, I probably never will.
  - mc 17y ago
    > But you'd have to do that separately for every language. That's correct. It's one of the challenging parts.
    - gruseom 17y ago
      It's one of those ideas that would be best tried out on one instance first. It's not obvious that the ASTs of programs in different languages would be "A" enough for a generalized querying system to be useful. Still, I don't mean to shoot the idea down - it would make for an interesting experiment.
fizx 17y ago
Reverse Aho-Corasick matching. Basically, you store all of your searchable text in a suffix tree. You then do a depth-first search of the tree for matching strings. http://www.cs.brandeis.edu/~mfc/cs120/papers/ptrees.pdf http://www.cs.brandeis.edu/~mfc/cs120/papers/ptrees.pdf http://en.wikipedia.org/wiki/Aho-Corasick_algorithm http://en.wikipedia.org/wiki/Aho-Corasick_algorithm http://en.wikipedia.org/wiki/Suffix_tree http://en.wikipedia.org/wiki/Suffix_tree
- pc 17y ago
  How does that help here? My query doesn't contain any directly-searchable strings, unless you start abstracting things by treating all alpha chars as the same, etc.
  - deleted 17y ago
    [deleted]
  - jaydub 17y ago
    If I understand correctly (a big if) and the underlying structure is something along the lines of a giant suffix tree then searching for any particular string takes time asymtomtically equivalent to the length of the query string. What if there were another corresponding "meta-data" suffix-tree perhaps this would allow the fast abstract search. what if the nodes contained meta-data such as length/type etc instead of merely containing the data itself.
  - fizx 17y ago
    A nice thing about regular expressions is that you always know where you are in the expression (no backtracking, at least in theory). 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)".

116 points by pc 17y ago

crux_ 17y ago

Something like this? - Regular expression searching on compressed text, http://portal.acm.org/citation.cfm?id=967612 http://portal.acm.org/citation.cfm?id=967612

mbrubeck 17y ago
The cost of that algorithm still grows linearly with respect to the length of the compressed text. It's possible Google is doing something like this (searching over the entire corpus until they find a match), but is there any work on precomputing an actual "index" to speed up this type of search?
- crux_ 17y ago
  I'm certain there are many approaches to be found via citation-following. 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.)
  - crux_ 17y ago
    Replying to myself, since editing was getting out of control. A neat property of the 2nd approach is that if you ever reach a node R where R < S you're done: all children will be matched. A less neat property is that it won't allow multi-line matches, but I'm not sure those are allowed anyway.

deleted 17y ago

[deleted]

drcode 17y ago

Is your question "How do you create an index that allows regexes?" In that case, I'd like to know the answer to the question, as well.

thwarted 17y ago
perl has a "study" function that examines a string in anticipation of doing many pattern matches on it. I'm not sure what it does exactly, but the kind of structures it creates could be serialized and stored along with an input file (or perhaps replace it), and used as kind of regular expression optimized index. This isn't necessarily an "index" in the normal sense, but then, neither is the likes of a full-text index either. But really, any data structures that are optimized for a specific kind of processing are indexes.
- jrockway 17y ago
  study does not do anything really interesting. It looks up substrings in a table of substring -> average frequency. It then scans for the rarest character first, so that it can fail quickly for most input. 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.
  - thwarted 17y ago
    Study doesn't do anything really interesting, but neither is creating a keyword index for a keyword based search all that interesting either. Considering that Google code search is not intended to search English (for which their regular search technology would most likely suffice for that) using regular expressions, then I agree that the naive study implementation you've quoted is, basically, not what Google is using for code search. However, there's no reason that the frequency tables need to be static nor need to be constructed solely from from C programs and English text. Frequency tables can be continuously updated based on the input corpus and the input corpus should be the code that is being searched. Part of search is being able to rule out significant portions of the search space in the name of getting positive results as fast as possible, so being able to fail quickly for most inputs (considering the example regular expression only returns three hits, it seems a wide majority don't match), a study-like implementation would appear to be a possibility.

wooster 17y ago

AFAIK, Google Code Search was written by Russ Cox, who also wrote this: http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html 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. :)

nostrademons 17y ago
If anyone knows any differently, I doubt they'd be able to tell you. ;-)
Retric 17y ago
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.
deleted 17y ago
[deleted]
fizx 17y ago
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.
bravura 17y ago
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.

simonw 17y ago

I've always wanted to know that.

mtrimpe 17y ago

It might be possible to adapt a regex state machine to use an AVL TDAWG ( http://www.ssp.isee.kyushu-u.ac.jp/~inenaga/papers/tcs-ternary.pdf http://www.ssp.isee.kyushu-u.ac.jp/~inenaga/papers/tcs-terna... )

johngunderman 17y ago

I am 100% postulating here, but this is what seems most likely to me: Google is known for MapReduce. It seems like it would make regex searches manageable when put in such an algorithm. All Google would have to do would be to take whatever key system they use for their big-tables and use MapReduce to expand the regex over the keys. Then they just have to return the data associated with those keys.

tumult 17y ago
..what? I would love to see you try to explain how you think this works :)
- johngunderman 17y ago
  to quote http://infolab.stanford.edu/~backrub/google.html http://infolab.stanford.edu/~backrub/google.html 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 :-) )
  - tumult 17y ago
    Quote is unrelated to what you are saying! use MapReduce to expand the regex over the keys 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. ... Looking forward to further explanations!

miracle 17y ago

Easynews also has a global search where you can search through all the newsgroup posts with a regular expression (> 150 days). You might ask them? They are certainly not as secrective as google is ;)

jrockway 17y ago
Is the global search really a regex? I thought it was just substrings.
- s3graham 17y ago
  The labels are links to regularexpressions.info so I'd guess yes. I'm pretty sure EN just greps subject + output of something like 'strings' though, it chugs pretty hard on broad searches.

tlrobinson 17y ago

This is off-topic, but I just realized Google Code Search is great for seeing where code you open source ends up. Came across a few things I had no idea were using my code. Kinda cool.

mc 17y ago
Tom, did you know there are extra filters you can use to search Github.com? Try "tlrobinson package:github.com lang:javascript"

robk 17y ago

IIRC, this was a rather high-compute-cost project inside of Google, far more so than other search projects. Obviously it was a favorite though of the eng decision makers, so was well cared for resource-wise.

pmorici 17y ago

This presentation talks about using N-grams to make an regex searchable index http://www.informatik.hu-berlin.de/forschung/gebiete/wbi/teaching/archive/sose08/pr_text/vortraege/ngram_indexing.pdf http://www.informatik.hu-berlin.de/forschung/gebiete/wbi/tea...

fizx 17y ago
No complexity analysis. Random student results. It's viable to build an index with n-grams, but I don't think you'd get any benefit over suffix-tree search. There might be a way to select n-grams cleverly some of the time, but you can also easily run into pathological cases.

mc 17y ago

I'd (probably) consider building and searching an index of ASTs (http://en.wikipedia.org/wiki/Abstract_syntax_tree http://en.wikipedia.org/wiki/Abstract_syntax_tree). Not only would it allow searching with regexp, but it could allow more sophisticated search queries like "Search all my Ruby code for blocks that rescue StandardError and are not followed by an ensure clause"

gruseom 17y ago
But you'd have to do that separately for every language. Edit: the OP is such a great question. I've been saving up the joke of commenting "How is this Hacker News?" on the most literally appropriate HN post I run across... and almost used it on this one. Sadly, I probably never will.
- mc 17y ago
  > But you'd have to do that separately for every language. That's correct. It's one of the challenging parts.
  - gruseom 17y ago
    It's one of those ideas that would be best tried out on one instance first. It's not obvious that the ASTs of programs in different languages would be "A" enough for a generalized querying system to be useful. Still, I don't mean to shoot the idea down - it would make for an interesting experiment.

fizx 17y ago

Reverse Aho-Corasick matching. Basically, you store all of your searchable text in a suffix tree. You then do a depth-first search of the tree for matching strings. http://www.cs.brandeis.edu/~mfc/cs120/papers/ptrees.pdf http://www.cs.brandeis.edu/~mfc/cs120/papers/ptrees.pdf http://en.wikipedia.org/wiki/Aho-Corasick_algorithm http://en.wikipedia.org/wiki/Aho-Corasick_algorithm http://en.wikipedia.org/wiki/Suffix_tree http://en.wikipedia.org/wiki/Suffix_tree

pc 17y ago
How does that help here? My query doesn't contain any directly-searchable strings, unless you start abstracting things by treating all alpha chars as the same, etc.
- deleted 17y ago
  [deleted]
- jaydub 17y ago
  If I understand correctly (a big if) and the underlying structure is something along the lines of a giant suffix tree then searching for any particular string takes time asymtomtically equivalent to the length of the query string. What if there were another corresponding "meta-data" suffix-tree perhaps this would allow the fast abstract search. what if the nodes contained meta-data such as length/type etc instead of merely containing the data itself.
- fizx 17y ago
  A nice thing about regular expressions is that you always know where you are in the expression (no backtracking, at least in theory). 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)".