4 ms·
To understand this you need to understand a bit about the way a search engine works. (I used to work at Google on the search engine but I am not revealing anyth
by lacker 10y ago
To understand this you need to understand a bit about the way a search engine works. (I used to work at Google on the search engine but I am not revealing anything besides information retrieval 101 here.)
Roughly, there is a database of the entire internet that is broken into 1000 "shards". The database has a really complex indexing scheme. You can think of each shard as having one "worker" process, and then there are some "merger" processes that combine the results from workers.
So there are basically four phases: retrieval, scoring, merging, and display. In the "retrieval" phase, each worker uses the complicated indexes to retrieve a bunch of documents that are relevant to the query. In the "scoring" phase, each worker puts a specific score on each document, using more information about the document to get a more accurate score than the retrieval phase did. Finally, in the "merging" phase, the results from all the shards are combined by the mergers and you get your eventual top list.
When you ask for the 10th page of results, it actually only affects the final "display" step. Everything before that is just producing a list of the top 1000. That way you can reuse caches in all the expensive places.
Why does it drop everything past the top 1000? In fact, you probably aren't getting the precise top 1000 in the first place. The retrieval and scoring phases use a lot of heuristics to determine when it's worth sending a document on to the next phase. Each shard might only need to send back its top 5 or so documents. Since it's very rare to go past the first 100 documents, going a bit faster by sacrificing the quality of responses 200+ will almost always be a good tradeoff.
There's a product-centric reason as well as an infrastructure-centric reason to not go past 1000. Who actually wants those results? Normal people are almost never looking at the 100th page of results. Viruses looking for vulnerable webservers, spammers, scrapers, all of these malicious actors still do want that 100th page of results, though. At some point it's not actually helping the world to provide the nth page of results.
- Red_Tarsius 10y agoThat was very fascinating and I appreciate you thorough answer!
- tedmiston 10y ago^ Great answer. So far, this is the only correct one in the thread. I took Information Retrieval 101 in grad school and it was an interesting course. If you're curious to learn more, term frequency–inverse document frequency (tf–idf) is a good place to start. The underlying idea is surprisingly simple. https://en.wikipedia.org/wiki/Tf–idf https://en.wikipedia.org/wiki/Tf–idf Likewise with the core of Google's (original) ranking algorithm, PageRank, which is inspired by ideas like h-index. https://en.wikipedia.org/wiki/PageRank https://en.wikipedia.org/wiki/PageRank Also, the "standard" book which we used is quite readable: Introduction to Information Retrieval by Manning, et al. https://www.amazon.com/Introduction-Information-Retrieval-Christopher-Manning/dp/0521865719/ https://www.amazon.com/Introduction-Information-Retrieval-Ch...