5 ms·

I have that beat, as I once made Google perform a 30-second query. I know exactly how I did it, too. I wasn't sure whether or not it would find it... So how

I have that beat, as I once made Google perform a 30-second query. I know exactly how I did it, too. I wasn't sure whether or not it would find it... So how does Google do a query? Well fundamentally it has lists of sites that have a keyword, so it gets the list for each of your keywords, then finds the intersection of those lists, then sorts it by the pagerank of the resulting URL's. That's how it used to work anyway. So back in the day I decided to try to do a test. I got the Gutenberg list of all of Shakespeare's words, and I wrote a program to go through it to find the longest string of all "stop" words (which you could still force Google to include - normally it ignores them, since there are just too many sites that include words like "the" and so on). Stop words are super common words like "the" which would be on millions or billions of pages. A huge list of URL's. So I coded up my little algorithm that goes word by word through the text, keeping track of what the longest string it found so far is, that consisted entirely of stop words. The longest string it found was: "from what it is to a". Just now I again did that query, and on the whole Internet it just found 4 matches (soon it will find this comment too and any archives of this comment), all being the exact phrase from Shakespeare: https://imgur.com/a/lvU1QSs https://imgur.com/a/lvU1QSs Impressively, that query now takes 0.84 seconds (I haven't done that query in several years, it's possibly cached but I doubt it.) However, when I first performed it, it took 30+ seconds. I didn't take a screenshot but I was super impressed. I brought Google to a crawl for 30 seconds, in the exact way I was intending. Moohahahahaha. "Holy cow. I just made Google's databases join six lists each with millions of pages on them, find the intersection, and then go through all of them for which ones had my phrase in literal order. And then it found it." Pretty mind-blowing that today it can do that in < 1 second.

solipsism 7y ago
when I first performed it, it took 30+ seconds Pretty mind-blowing that today it can do that in < 1 second You are reading a lot into what sounds like it was a single measurement. Was this experiment repeatable,?
- 867-5309 7y ago
  due to caching, probably not
- deleted 7y ago
  [deleted]
thrwawy3493 7y ago
The key for people who don't get why it was so much work for Google is this: where I just wrote "then go through all of them for which ones had my phrase in literal order" I meant "then go through all of the cached contents of every single one of the web pages on the results list -- since the joined list itself would have every web site that has those 6 words, which is pretty much every English-language page on the web of more than a few thousand words. So it neeeded to scan through the cached contents of all of them to find which ones had the phrase in order." For example I just looked at the top post on Reddit right now, it's about 20 page-downs of comments, and has the words this many times: from 17 what 22 it 223 is 169 to 195 a - more than 1000 pretty much every English-language web page on the whole Internet will have those words, unless it is very short.
- wereHamster 7y ago
  > pretty much every web page on the whole Internet will have those words, unless it is very short. … because everyone speaks english?!? England had a large empire back in the days but it wasn't that big, nor did it span the whole world.
  - thrwawy3493 7y ago
    updated my comment. My apologies.
  - deleted 7y ago
    [deleted]
  - treypitt 7y ago
    "The sun never sets on the British Empire" it was up there historically with Rome and Alexander's conquests (although the latter may not have constituted a bona fide empire)
- yorwba 7y ago
  > So it neeeded to scan through the cached contents of all of them to find which ones had the phrase in order. If you have a positional index [1] you don't have to go through the full cached content, you only have to check the index to see whether there's an occurrence of the words in the query with the correct distance. E.g. for that Reddit post, you'd check the 17 occurrences of "from" and notice quickly that your query string doesn't match at that position. [1] https://nlp.stanford.edu/IR-book/html/htmledition/positional-indexes-1.html https://nlp.stanford.edu/IR-book/html/htmledition/positional...
kburman 7y ago
Just did that same search on bing and it also returned 3 results within a second.
amelius 7y ago
Perhaps it also keeps an index of pairs of adjacent words. Another thing is that your query is essentially a literal "substring" search, which Google probably handles differently. See e.g. the Burrows Wheeler transform for an idea how it could be implemented.
computator 7y ago
> on the whole Internet it just found 4 matches, all being the exact phrase from Shakespeare But why just 4 occurrences? Every utterance of Shakespeare has been printed on thousands of web sites and Google has indexed thousands of those sites. Another line from the same play, "Nay, answer me: stand, and unfold yourself", gets 10,300 hits. I tried another line from deep within the play: "I know him well: he is the brooch indeed." Google found 3,890 results. Even though the search is slow, why aren't we getting thousands of hits for "from what it is to a"?
- makomk 7y ago
  The other odd thing is that if you search for the exact phrase "transform honesty from what it is to a bawd", which is what that particular all-stopword string is taken from, you get a lot more results. Clearly Google isn't actually finding most of the pages in its index that match that string.
- nwellnhof 7y ago
  > why aren't we getting thousands of hits for "from what it is to a"? Because Google isn't an exact search engine. Each of the terms in the phrase above appears on billions of pages. My guess is that for common terms Google doesn't store all postings in its inverted index but truncates the posting lists after a couple of million entries.
lol768 7y ago
If you're interested in slow queries, try the one below (via [1]): the OR google OR a OR "supercalifragilisticexpialidocious" -the -google -a You can replace the "supercalifragilisticexpialidocious" term with something unique if the results end up cached. This takes upwards of 5 seconds to return back. [1] https://www.quora.com/What-is-the-slowest-Google-query https://www.quora.com/What-is-the-slowest-Google-query
- amelius 7y ago
  One question is, will such complicated queries bring all of Google to a crawl, or will they e.g. be executed with lower priority or on different servers, leaving the rest of the queries unaffected?
  - pcnix 7y ago
    Of course they don't affect other queries, these would be non-locking queries on replicas. Or, to be even more accurate, they'd be non blocking queries on indices cached in memory on edge servers and probably several levels of optimization beyond that. There's no reason for these type of queries to lock a database.
    - amelius 7y ago
      I wasn't concerned about locking, but more about resource utilization. Searches are read-only, so I suppose locking doesn't need to happen anyway.
- needs 7y ago
  Or just search for "powered by".
lazyjones 7y ago
> Pretty mind-blowing that today it can do that in < 1 second. Today they probably use common pairs of words as well for their lists, so they have only 3-4 intersections of smaller lists in this case.
dekhn 7y ago
If you want to know how Google search got fast, the book "Managing Gigabytes" covers many of the basic optimizations to speed up search. I found the book very enjoyable to read.

solipsism 7y ago

when I first performed it, it took 30+ seconds Pretty mind-blowing that today it can do that in < 1 second You are reading a lot into what sounds like it was a single measurement. Was this experiment repeatable,?

867-5309 7y ago
due to caching, probably not
deleted 7y ago
[deleted]

thrwawy3493 7y ago

The key for people who don't get why it was so much work for Google is this: where I just wrote "then go through all of them for which ones had my phrase in literal order" I meant "then go through all of the cached contents of every single one of the web pages on the results list -- since the joined list itself would have every web site that has those 6 words, which is pretty much every English-language page on the web of more than a few thousand words. So it neeeded to scan through the cached contents of all of them to find which ones had the phrase in order." For example I just looked at the top post on Reddit right now, it's about 20 page-downs of comments, and has the words this many times: from 17 what 22 it 223 is 169 to 195 a - more than 1000 pretty much every English-language web page on the whole Internet will have those words, unless it is very short.

wereHamster 7y ago
> pretty much every web page on the whole Internet will have those words, unless it is very short. … because everyone speaks english?!? England had a large empire back in the days but it wasn't that big, nor did it span the whole world.
- thrwawy3493 7y ago
  updated my comment. My apologies.
- deleted 7y ago
  [deleted]
- treypitt 7y ago
  "The sun never sets on the British Empire" it was up there historically with Rome and Alexander's conquests (although the latter may not have constituted a bona fide empire)
yorwba 7y ago
> So it neeeded to scan through the cached contents of all of them to find which ones had the phrase in order. If you have a positional index [1] you don't have to go through the full cached content, you only have to check the index to see whether there's an occurrence of the words in the query with the correct distance. E.g. for that Reddit post, you'd check the 17 occurrences of "from" and notice quickly that your query string doesn't match at that position. [1] https://nlp.stanford.edu/IR-book/html/htmledition/positional-indexes-1.html https://nlp.stanford.edu/IR-book/html/htmledition/positional...

kburman 7y ago

Just did that same search on bing and it also returned 3 results within a second.

amelius 7y ago

Perhaps it also keeps an index of pairs of adjacent words. Another thing is that your query is essentially a literal "substring" search, which Google probably handles differently. See e.g. the Burrows Wheeler transform for an idea how it could be implemented.

computator 7y ago

> on the whole Internet it just found 4 matches, all being the exact phrase from Shakespeare But why just 4 occurrences? Every utterance of Shakespeare has been printed on thousands of web sites and Google has indexed thousands of those sites. Another line from the same play, "Nay, answer me: stand, and unfold yourself", gets 10,300 hits. I tried another line from deep within the play: "I know him well: he is the brooch indeed." Google found 3,890 results. Even though the search is slow, why aren't we getting thousands of hits for "from what it is to a"?

makomk 7y ago
The other odd thing is that if you search for the exact phrase "transform honesty from what it is to a bawd", which is what that particular all-stopword string is taken from, you get a lot more results. Clearly Google isn't actually finding most of the pages in its index that match that string.
nwellnhof 7y ago
> why aren't we getting thousands of hits for "from what it is to a"? Because Google isn't an exact search engine. Each of the terms in the phrase above appears on billions of pages. My guess is that for common terms Google doesn't store all postings in its inverted index but truncates the posting lists after a couple of million entries.

lol768 7y ago

If you're interested in slow queries, try the one below (via [1]): the OR google OR a OR "supercalifragilisticexpialidocious" -the -google -a You can replace the "supercalifragilisticexpialidocious" term with something unique if the results end up cached. This takes upwards of 5 seconds to return back. [1] https://www.quora.com/What-is-the-slowest-Google-query https://www.quora.com/What-is-the-slowest-Google-query

amelius 7y ago
One question is, will such complicated queries bring all of Google to a crawl, or will they e.g. be executed with lower priority or on different servers, leaving the rest of the queries unaffected?
- pcnix 7y ago
  Of course they don't affect other queries, these would be non-locking queries on replicas. Or, to be even more accurate, they'd be non blocking queries on indices cached in memory on edge servers and probably several levels of optimization beyond that. There's no reason for these type of queries to lock a database.
  - amelius 7y ago
    I wasn't concerned about locking, but more about resource utilization. Searches are read-only, so I suppose locking doesn't need to happen anyway.
needs 7y ago
Or just search for "powered by".

lazyjones 7y ago

> Pretty mind-blowing that today it can do that in < 1 second. Today they probably use common pairs of words as well for their lists, so they have only 3-4 intersections of smaller lists in this case.

dekhn 7y ago

If you want to know how Google search got fast, the book "Managing Gigabytes" covers many of the basic optimizations to speed up search. I found the book very enjoyable to read.