Comment by thrwawy3493 | Hacker News Reader

Comment by thrwawy3493 | Hacker News Reader

Parent Full thread

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

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.

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.

> 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...

> 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.

"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)

updated my comment. My apologies.

> 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"?

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.

> 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.

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

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?

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.

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.

Or just search for "powered by".

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.

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.

> 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.

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

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,?

due to caching, probably not

Reply on news.ycombinator.com