4 ms·

I, for one, forget to appreciate the fact that one of the fastest web apps I regularly use is the one that searches the entire* internet. *kinda

moultano 16y ago
The internet that Google doesn't search is almost always not the internet you want to find. :)
ugh 16y ago
I would still love to get a good layman’s explanation of how Google and other search engines can be so fast. I’m not a developer but I know a few basic concepts. Sorting makes searching fast – but that fast? I can imagine that if I’m searching for “ball” Google already has the PageRank sorted results somewhere on its servers. That seems easy enough. But what about arbitrary search terms? Searching for “tango durlast 1978” (a soccer ball) gives me results just as fast, does Google have all of that pre-computed somewhere? If they did that (to pick an arbitrary number) for search terms up to 100 characters (say all 26 letters, ten digits and space) that would mean that they would have to have something like 37^100=6.6e+156 pre-computed lists of results somewhere on their servers. That can’t be what they are doing. If they were to use only one byte per possible search term (to pick another arbitrary and completely ridiculous number) they would still need to store 6.6e+144 terabyte. Which seems kinda impossible.
- acqq 16y ago
  1) To be able to "search (almost) the whole internet" you have to pull the content and have "almost whole internet" on your own servers. 2) You have to update your copy of the internet regularly. 3) You don't want to search all that whenever somebody types a few words. So write programs to regularly prepare indexes in advance (just like in the books) and then when the query with words comes you can "just" look up in these. The steps above sound simple, but you can imagine that the devil is in details, that there's a lot of knowhow needed and a lot of money to do that really right. Just ask Microsoft or even some failed search company.
- kenjackson 16y ago
  It's a combination of embarassing parallelism and clever indexing.
- 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 ago
    Doesn’t that matrix get big fairly quickly? Are there any tricks to keep it as small as possible?
    - jerf 16y ago
      One 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 ago
        Major 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 ago
- deleted 16y ago
  [deleted]
- mkelly 16y ago
  Some typical search engine strategies are on this page (and specifically in this subsection): https://secure.wikimedia.org/wikipedia/en/wiki/Index_%28search_engine%29#Inverted_indices https://secure.wikimedia.org/wikipedia/en/wiki/Index_%28sear...

moultano 16y ago

The internet that Google doesn't search is almost always not the internet you want to find. :)

ugh 16y ago

I would still love to get a good layman’s explanation of how Google and other search engines can be so fast. I’m not a developer but I know a few basic concepts. Sorting makes searching fast – but that fast? I can imagine that if I’m searching for “ball” Google already has the PageRank sorted results somewhere on its servers. That seems easy enough. But what about arbitrary search terms? Searching for “tango durlast 1978” (a soccer ball) gives me results just as fast, does Google have all of that pre-computed somewhere? If they did that (to pick an arbitrary number) for search terms up to 100 characters (say all 26 letters, ten digits and space) that would mean that they would have to have something like 37^100=6.6e+156 pre-computed lists of results somewhere on their servers. That can’t be what they are doing. If they were to use only one byte per possible search term (to pick another arbitrary and completely ridiculous number) they would still need to store 6.6e+144 terabyte. Which seems kinda impossible.

acqq 16y ago
1) To be able to "search (almost) the whole internet" you have to pull the content and have "almost whole internet" on your own servers. 2) You have to update your copy of the internet regularly. 3) You don't want to search all that whenever somebody types a few words. So write programs to regularly prepare indexes in advance (just like in the books) and then when the query with words comes you can "just" look up in these. The steps above sound simple, but you can imagine that the devil is in details, that there's a lot of knowhow needed and a lot of money to do that really right. Just ask Microsoft or even some failed search company.
kenjackson 16y ago
It's a combination of embarassing parallelism and clever indexing.
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 ago
  Doesn’t that matrix get big fairly quickly? Are there any tricks to keep it as small as possible?
  - jerf 16y ago
    One 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 ago
      Major 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 ago
deleted 16y ago
[deleted]
mkelly 16y ago
Some typical search engine strategies are on this page (and specifically in this subsection): https://secure.wikimedia.org/wikipedia/en/wiki/Index_%28search_engine%29#Inverted_indices https://secure.wikimedia.org/wikipedia/en/wiki/Index_%28sear...