I don't think that he did it because it's his job to stop random people on the Internet from running slow queries. I think she was just surprised how creative people are and found it funny.
The reason stop words take such a long time is that millions of sites have words like "the" on them, so doing a join on all those simply takes a long time.
My method to find a long string consisting entirely of stop words, was to just download a project gutenberg of the complete works of shakespeare, and find the longest string consisting of just stop words in there, then search for it as a literal quote.
The longest one I found was: "From what it is to a".
Let me see how long Google takes to do it now :)
2.04 seconds! Nice :) - http://i.imgur.com/IhPTpr6.png
that took 30+ seconds 'back in the day'.
Today it resolves instantly and finds at least 10 publications from before 2000.
By the way I believe I wanted to know whether it would return the Shakespeare quote at all.
If you mean that it might have cached the results of the query, I doubt anyone else queried that exact phrase, other than me.
I'm guessing you're most familiar with btree indexes as present and default in many SQL solutions, which are good for quickly answering exact, greater/less matches. There are dozens of data structures useful for indexing, some of which are built to index full text documents. For an example, check out the gin and gist indexes in Postgres [1].
It's my understanding that database indexing and index compression was a primary differentiator Google excelled at from the beginning. They could beat others at fractions of the typical cost because they didn't need data centers to store and query huge quantities of documents.
Seriously, there's no way even Google could intersect the sets of all crawled web documents containing those individual words in 30 seconds, much less two seconds.
[1] https://www.postgresql.org/docs/current/static/textsearch-in...
I believe you're mistaken. What I've heard is that for every word, Google has a list of every web site that contains that word - they've flipped the database. So, I believe, if you search for (without quotes) neanderthal violet narwhal obsequious tandem then -- and I just did this query, which took 0.56 seconds, but decided to remove some of the words, so it can get it me results. When I did plus signs, making my query +neanderthal +violet +narwhal +obsequious +tandem it said it worked 0.7 seconds to determine that in all of the entirety of the Internet, there is not a single document that has those 5 words on it.
How do you think it determines in 700 ms that all of the sites it has indexed on all of the Internet does not contain those 5 words anywhere on it?
The answer is that it has a rather short list of sites that contain the word narwhal, which it then intersects with the somewhat larger list of sites that contain obsequious and so on. 700 seconds is plenty fast when you take that approach.
so, this explains why joining stop words (which consist of billions of pages, each) takes so very long.
using stop words it is easy to make queries that take one or two seconds each.
Huh? What do you mean? Google indexes HTML web page content from the entire public internet using web crawlers...
The reason my search took 30 seconds is because it started by getting a list of every site with "from" on it, every site with "what" on it, and so on, intereseecting them all. That's how it ended up finding my quote. how else do you think it did it?
----- edit:
to find the string "from what it is to a" which occurs only hidden in the middle of shaespeare's texts -- what do you think they do?
In my opinion they combine the list of sites that have every word - starting with the least common ones. It's easier if you search for something that has a few uncommon words. Then you start with a small list, and have to combine it with other small lists.
When every word in the phrase has billions of sites (there are billions of pages that have the word "to" on them, same for "from", "what", "it", "is", "a"), you have to combine them all. Then you have to do a string search within the resulting set, since I put it in quotation marks. There is no easy strategy. Hence the long search time.
what else could they be doing?
the sense you mean is a different sense of the word index - meaning, to crawl. Yes, of course it does that too.
Google, no doubt, has a very sophisticated way of querying against their cache of the WWW and it has probably evolved over time. However, it is inappropriate to say Google does a join over the entire internet for one query. It is much more reasonable to say that Google checked your query string against their gigantic index of terms, and it took a while to dig that deep into the pile. The performance hit such a complex query takes is more like unzipping a large archive to get a specific megabyte's worth of info, rather than saying it smashed all the files together and then searched for the exact term like notepad.
Anyway, think about it for a while, it's clearly a cool issue in search, and programs and algorithms do not have to visually search things as humans must.
I recommend reading the Stanford paper[0] (page 12), which spells out in a lot of detail exactly what they were doing.
In short, your pathological query would have searched for every document which contained one of your words, discarded those which didn't match all, and then sorted by word proximity. I expect for a literal phase search, there would be a final pass to look for the exact phrase in order.
Have you accidentally searched Google for a long URL and seen it come up? It is actively caching stuff all the time, and that cache just grows and grows, and it must be a pretty beautiful megastructure that you can run queries against.
Normally it ignored those words. I am fairly certain of this detail. I must have found a list of those words - how else would I have found the string "from what it is to a"? I had a list of its stop words.
Edit: for proof, here's someone's screenshot of the same - http://farm3.static.flickr.com/2270/2201828252_45a32da7f4.jp...
As you can see, it is Google saying it is ignoring a word because it is too common. It has a list of every site that has that, but that list is huge and it doesn't usually use it.
My same query as you took 0.3s, but if I stripped out one word ("From what it is to") it took 2.2 seconds.
Shouldn't someone with a job in statistics know how to account for outliers?
This is why companies like Google have bounties for such things. "Please submit bugs and performance issues privately so we can patch them before you disclose the details publicly and hurt our services - we'll even pay you for your discretion!"
When you operate at the scale of Google, everything is expected to be airtight; outliers should not be possible. It wouldn't surprise me if their monitoring systems are built without the ability to "massage" (ie: manipulate) statistics, as it is a terrible practice. I don't think a statistician who relies on ignoring outliers would last long working for Google. They're not doing their job if the only thing they care about is silencing warnings to make pretty graphs that falsely show everything is running smoothly. Their job is to work with the truth - not manufacture little white lies to appease management.
Nobody ever asks about that 0.1%...
One of my young-adulthood colleagues went on to be an early googler who is influential in relevant policies. We built our relationship sharing bugs and analysis techniques. Quite a few years ago some scoundrels whose trust I gained proudly showed me how they were using youtube links to drop malware. Since my old mate worked there, I mentioned it and they were quite interested.
We hadn't shared anything in a while, both of us demonstrating loyalty to our employers and not talking about work details. I said that it would be really cool to have a one dollar check from Google for a bug report. I probably offered to send something cool from my workplace too.
They said, "We don't pay for bugs" Fifty cents? "We don't pay for bugs!"
I felt like I was simply after a piece of paper and the evildoers were a mildly useful source, but I could easily do without them and the souvenir would have been treasured.
I was unreasonably miffed that I couldn't get that piece of paper, though. So I reviewed the links I'd collected and passed some general information but withheld details that would be obviously unique to these attackers. They expressed disappointment with me the next time we spoke. It turns out that what I gave wasn't specific enough to easily identify the lame cross site exploit, despite my actual intent to lead them to the bug.
Interesting they have a bounty program now.