5 ms·
There are two basic ways to build a search engine. First think of the web as a big matrix with each row being a document and each column being a term. The firs
by moultano 16y ago
There are two basic ways to build a search engine.
First think of the web as a big matrix with each row being a document and each column being a term. The first step is to decide how you want to shard this matrix across multiple machines.
You can shard by row, which lets you do really complicated scoring, but you have to hit every machine for every query.
You can shard by column, which is much cheaper, but limits how sophisticated your scoring can be.
Within each machine the problems are all probably fairly familiar.
- ugh 16y agoDoesn’t that matrix get big fairly quickly? Are there any tricks to keep it as small as possible?
- jerf 16y agoOne trick I think people underestimate the effect of is that Google caches queries. When you're searching for "Madonna", you are not causing the web index to be traversed, you're retrieving the saved search for "Madonna". Google can take a couple of seconds if you throw a truly novel query at it. Of course, storing millions of the "common queries" isn't a joke either and that still doesn't answer the question of how they search the internet within a few seconds anyhow; I'm not trying to give a complete answer, just point one aspect out. Google Instant, by design, provides the Google Suggest queries the vast bulk of the time and I guaranteed that those are either largely or possibly even entirely pre-cached, so you're not doing 10 web searches in two seconds, you're doing 10 hash lookups in 2 seconds. Which is still damned impressive, I can't hardly keep my web site loading in less than two seconds for one hit where I work.
- moultano 16y agoMajor parts of that aren't true. I think something like 30% of queries have never been seen before, and Google provides low latency on those as well.
- snprbob86 16y agoCut him some slack, it was clearly a simplification. Also, you're wrong to declare him inaccurate. Even if 30% of queries are truly unique (a number that people have quoted from years ago, may no longer be true) caching 70% of the queries is a big win. Also, instant search is heavily relying on Google Suggest, which by it's very nature, are queries which have been performed already, so are trivially cacheable.
- deleted 16y ago[deleted]
- percept 16y agoI've always used lengthy, quoted search phrases, but what's really interesting is that Google's autocomplete has slowly trained monkey-me to follow the well-worn path and use the search terms it suggests. It's a great example of using the UI to encourage a desired behavior.
- jerf 16y agoSo, let's just turn off caching and triple or quadruple the size of the Google cluster, eh? No big deal. I completely fail to see how you think that disproves my point.
- moultano 16y agoI should probably mention that I work in search quality at Google. The part I took issue with is "Google can take a couple of seconds if you throw a truly novel query at it." which is definitely not true. Google can't cache nearly as much as you would expect, not because the queries change, but because the results change.
- deleted 16y ago[deleted]
- moultano 16y agoYes. It's huge.
- mtklein 16y agoIt gets fantastically huge when you look at quoted searches. Sure, you can build an index of key words to documents containing them, but how do you build an index for literal text searches like "to the bridge, he said"?