How a Web Search Engine Answers a Query

Two queries typed into a web search engine a second apart can need entirely different treatment. facebook is almost certainly a request to go to one particular website, and the best result page has exactly one useful link at the top. best budget smartphone asks for a comparison of current products, and a page that was the best answer two years ago is now a poor one. barack obama biography asks for stable facts from an authoritative source, and freshness hardly matters. A web search engine must recognize which kind of request it has received, retrieve candidates from an index of billions of pages, rank them using evidence of very different kinds, and return a page of results, typically in a few hundred milliseconds.

This article follows a single query through that process. It builds on the general architecture of a search engine, adding what is specific to the web: short and ambiguous queries, an adversarial collection, and signals from links and user behavior that a closed collection does not have. The next article covers how the same process is distributed across thousands of machines.

Who is asking, and what for

Short queries, quick decisions

Studies of search logs established early what web queries look like. In an analysis of about a billion search requests to AltaVista, Silverstein, Henzinger, Marais, and Moricz (1999) found that distinct queries averaged 2.35 terms. For 85 percent of queries, only the first page of results was requested, and most sessions contained a single query. Later studies of other engines found similar figures. Query lengths have grown somewhat since, especially with spoken and conversational queries, but the core pattern holds. A query is a few words, most people read only the top of the results, and the system has a single chance to get the first few results right.

Two consequences follow. First, the system must infer most of the need, because the query states little of it. Second, ranking quality at the top of the list matters far more than quality deeper down. Evaluation measures for web search, introduced in evaluation, weight the top positions heavily for this reason.

Three kinds of intent

Andrei Broder (2002) classified web queries by the need behind them:

• Navigational queries seek a particular site the user has in mind: facebook, irs, united airlines. There is usually one correct result, and success means placing it first.
• Informational queries seek information assumed to exist on one or more pages: how do vaccines work, causes of the 1929 crash. Several pages may serve the need, and the user may read more than one.
• Transactional queries seek a site where something further will be done: shopping, downloading, booking, or using a service. buy running shoes and convert pdf to word are transactional.

Broder estimated the proportions from a survey of AltaVista users and from a sample of its query log: informational queries were the largest group, navigational queries made up roughly a fifth to a quarter, and transactional queries most of the remainder. Rose and Levinson (2004) refined the taxonomy with subcategories, such as informational queries that ask for advice or for a list.

The taxonomy matters because each intent calls for a different ranking. A navigational query is served by the one official site, and showing ten different pages would be worse than showing that one at the top. An informational query is served by several good sources, often from different perspectives. A transactional query is served by pages where the action can actually be completed. Modern engines classify queries along many more dimensions: whether a query wants fresh content, local results, images, a product, or a direct answer. These classifications decide which ranking signals carry the most weight and which kinds of results appear on the page.

Understanding the query

Before the index is consulted, the query is analyzed and often altered. The analysis begins with normalization compatible with that applied to documents, as described in the architecture article: tokenization, case folding, and a matching treatment of word variants. Web engines then go further.

Spelling correction. A large fraction of queries contain misspellings. Query logs provide the best evidence for correcting them, since a misspelled query that users frequently retype in one particular corrected form reveals its own correction. Cucerzan and Brill (2004) built a spelling corrector of this kind from query logs rather than a dictionary, which also handled names and new terms that no dictionary contains. Spelling correction and phonetic matching covers the edit-distance and k-gram methods behind spelling correction.

Recognizing structure. The engine identifies phrases (new york times), named entities (people, places, products), and operators the user typed explicitly, such as quotation marks or a minus sign. Stop words need care here. Most stop words can be ignored in matching, but some queries consist mostly of them. the who names a band and to be or not to be is a quotation, and dropping the stop words destroys both.

Expansion and rewriting. The engine may add terms the user did not type, such as morphological variants, synonyms (nyc and new york city), and expansions of abbreviations. Jones, Rey, Madani, and Greiner (2006) showed that query logs can also supply substitutions: when users often follow one query with another, the second is a candidate rewrite of the first.

How visibly the engine changes the query is itself a design decision. There are three common choices:

1. Suggest without rewriting. The original query is run and an alternative is offered ("Did you mean ...?"). This is appropriate when the engine is unsure.
2. Rewrite with notice. The engine runs the corrected query and says so ("Showing results for ..."), with a link to run the original instead. This is appropriate when the engine is confident, as with an obvious misspelling.
3. Rewrite silently. The engine expands or alters the query without telling the user. A query for nj tax return may also match pages that say New Jersey tax return. Silent rewriting is appropriate only when the expansion is very unlikely to change the meaning, because a user who cannot see the change cannot correct it.

The trade-off is the familiar one between recall and precision, applied at the scale of an entire query. Each added term or substitution finds more pages, and each risks drifting from what the user meant.

Where the query physically goes

Before following the query through ranking, it helps to see the machines it passes through. A widely cited public account of a large engine's serving path is the one Google engineers gave in 2003 (Barroso, Dean, and Hölzle, 2003, pp. 22–23). When a user submits a query, the browser's DNS lookup is answered by a load-balancing system that picks one of several clusters around the world, taking into account the user's distance from each and the capacity each has free. From then on the query stays inside that cluster. A hardware load balancer passes it to one of many identical web servers, which coordinates everything else and finally formats the results page.

Query execution then has two phases. In the first, the query goes to the index servers. The index is too large for one machine, so it is split into shards, each holding the complete inverted index for a random subset of the documents, and each shard is served by a pool of identical replicas. One replica of every shard receives the query, intersects the postings lists of the query words for its own documents, scores the matches, and returns its best document identifiers. The web server merges these lists into one ranking. In the second phase, the top identifiers go to the document servers, which are sharded the same way and hold copies of the pages themselves. They fetch each page and produce its title, URL and query-specific snippet. Meanwhile the web server has also sent the query to a spell-checking service and to an ad-serving system, and it assembles all of these into the page.

Each stage of this article maps onto that picture. Query understanding happens at the web server and its helper services. Candidate retrieval and the first rounds of scoring happen inside each index shard, close to the postings. Snippets are made by the document servers, after ranking, and only for the handful of results that will be shown. The design is from 2003, and engines have since added caches, index tiers and more ranking stages, which search at scale describes, but the shape of sharded index lookup, merging, and then a separate pass over the winners is still the natural way to divide the work in a document-partitioned engine.

Retrieving candidates

The rewritten query is executed against the inverted index. On the web, even a precise query matches far too many pages to score carefully. A two-word query can match millions. The engine therefore first retrieves a manageable set of candidates using a fast, simple criterion, and ranks only those carefully.

A common lexical strategy treats a multi-word query as a conjunction, retrieving pages that contain all the terms, and relaxes the condition only if too few pages match. Modern engines also draw candidates from other sources, such as the rewritten forms of the query and learned representations of meaning, so a candidate need not contain every term the user typed. Tiered indexes and early termination, described in search at scale, keep this step fast. The aim at this stage is high recall at low cost: it must not lose the documents that would rank highest, but it does not need to order them correctly.

Ranking with many signals

The candidates are then scored. Web ranking combines evidence of two kinds.

Query-dependent signals describe the relationship between the query and a page:

• Text match: how well the page's words match the query, measured by functions such as TF-IDF and BM25, computed for the title, headings, body, and URL, either separately or combined across fields as in BM25F. Matches in the title count more than matches in the body.
• Proximity: whether the query terms appear close together, which distinguishes a page about climate policy from one that mentions climate and policy in different sections.
• Anchor text: the words in links that point to the page. Anchor text often describes a page better than the page describes itself, because it is written by other people for readers who have not yet seen the page. A company's home page may not contain the phrase car manufacturer, but links to it often do. Brin and Page (1998) identified anchor text as one of the main sources of Google's early quality.
• Click history: how users responded when the page was shown for this or similar queries. As discussed in the article on relevance, clicks are biased toward higher positions, so they are useful mainly as relative evidence.

Query-independent signals describe a page regardless of the query:

• Link-based authority, such as PageRank, which treats a link as an endorsement and rates a page highly if pages that are themselves highly rated link to it.
• Quality and spam indicators computed when the page is indexed. Ntoulas, Najork, Manasse, and Fetterly (2006) showed that spam pages can be detected from content features alone, such as unusually repetitive text or words copied from popular queries.
• Freshness, estimated from when a page was created or last substantively changed.
• Page properties such as language, the region it targets, and whether it loads quickly and displays well on a phone.

Some signals become important only for certain queries. Freshness barely matters for barack obama biography and dominates for best budget smartphone, where a review from two years ago describes phones no longer sold. For a query about a news event, the most useful pages may be only hours old, and the engine must recognize that a query has become newsworthy before links and clicks have accumulated (Dong et al., 2010). Location matters for pizza delivery and not for pythagorean theorem.

No hand-written formula combines this many signals well across every kind of query. Web engines use learning to rank: each candidate becomes a vector of signal values, and a model trained on human relevance judgments and on behavioral data learns how to combine them. The classical retrieval models of this course survive inside these systems as features: BM25 computed over each field is among the strongest inputs.

Ranking is also done in stages: a cheap function scores all candidates, and progressively more expensive models re-rank smaller and smaller subsets (Wang, Lin, and Metzler, 2011). In current systems the final stages include neural models that read the query and page text together. The scale article describes this cascade in more detail.

The arithmetic behind the cascade is easiest to see with numbers attached. The table below follows one query through the stages. The counts are illustrative orders of magnitude chosen for the arithmetic, not figures published for any engine:

Each stage but the last cuts the set by a factor of a hundred or more, and each spends far more per document than the stage before. An expensive model that would take a millisecond per document is unaffordable over twenty million matches (more than five hours of computation) but costs a third of a second over 300, and that work can itself be spread across machines. The same reasoning sets the latency budget. A results page expected in about 200 milliseconds might, again for illustration, divide its time like this:

The point of such a budget is that every stage has one, so a new ranking feature is judged not only by how much it improves the ranking but by whether it fits in its slot. The first-stage slot is also only as fast as the slowest shard, since the merge must wait for all of them, a problem that search at scale treats under tail latency.

Assembling the results page

Removing duplicates

Much of the web is copied. The same article appears on many sites, the same page is reachable at several URLs, and mirrors reproduce entire sites. A results page that shows five copies of one article wastes four positions. Engines detect exact duplicates with fingerprints of the page content, and near-duplicates with shingling: each page is reduced to a sample of its overlapping word sequences, and pages that share most of their sample are treated as copies (Broder, Glassman, Manasse, and Zweig, 1997). Much of this work happens at indexing time, so that clusters of copies are already known when the results page is assembled and can be collapsed to a single representative. Web crawling covers the method in detail.

Diversity

Results are also checked against one another, not only against the query. For an ambiguous query such as jaguar, a ranking that places the ten most relevant pages about the car first fails every user who meant the animal. Diversification methods select each result to be both relevant and different from those already selected. Carbonell and Goldstein (1998) introduced the approach as maximal marginal relevance, which scores a document by its relevance minus its similarity to documents already chosen. At each step, MMR selects the candidate $d$ that maximizes $\lambda\,\mathrm{sim}_1(d, q) - (1 - \lambda) \max_{d' \in S} \mathrm{sim}_2(d, d')$, where $q$ is the query, $S$ is the set of documents already selected, $\mathrm{sim}_1$ and $\mathrm{sim}_2$ are similarity functions that need not be the same, and $\lambda$ between 0 and 1 sets the balance between relevance and novelty. This is a practical answer to the problem raised in the relevance article: a document's value depends on what the user has already seen.

A small example shows the selection at work. Five candidates for jaguar have been retrieved: three pages about the car (car1, car2, car3) and two about the animal (cat1, cat2). Their similarities to the query, $\mathrm{sim}_1$, are 0.90, 0.85, 0.80, 0.70 and 0.60. Pages about the same sense are similar to each other ($\mathrm{sim}_2 = 0.8$) and pages about different senses are not ($\mathrm{sim}_2 = 0.1$). These numbers are invented to make the arithmetic clear. With $\lambda = 1$, MMR ignores novelty and returns car1, car2, car3: every one of the top three is about the car. With $\lambda = 0.7$, the selection goes as follows.

At step 1 nothing has been selected, so the penalty is zero and each score is $0.7 \times \mathrm{sim}_1$; car1 wins. At step 2 every remaining car page pays a penalty of $0.3 \times 0.8 = 0.24$ for its similarity to car1, while the animal pages pay only $0.3 \times 0.1 = 0.03$. car2 drops to $0.595 - 0.24 = 0.355$ and cat1 to $0.49 - 0.03 = 0.46$, so cat1 is chosen. At step 3, cat2 is now penalized for resembling cat1 ($0.42 - 0.24 = 0.18$), and car2 takes third place. The result, car1, cat1, car2, gives a user who meant the animal a relevant page in second place.

The balance point can be found exactly. cat1 beats car2 at step 2 when $0.7\lambda - 0.1(1 - \lambda) > 0.85\lambda - 0.8(1 - \lambda)$, which simplifies to $\lambda < 0.7/0.85 \approx 0.82$. Above that value the second car page is relevant enough to outweigh its redundancy. In a real engine $\lambda$ is tuned, and the similarities come from the ranking model and from document representations rather than being assigned by hand.

Snippets

The query-dependent snippets described in the architecture article are not only a convenience. Tombros and Sanderson (1998) showed that query-biased summaries let users judge relevance more accurately and quickly than fixed summaries such as the first lines of a page. On the web they also change what a click means: a snippet that answers the question removes the need to click at all, so a query with no clicks may be a success rather than a failure. Generating snippets requires the document text, so engines typically store the text of each page, often compressed, and generate snippets only for the few results actually shown (Turpin, Tsegay, Hawking, and Williams, 2007).

Beyond ten links

A modern results page is assembled from several sources. Vertical results, such as images, news, videos, maps, and shopping, come from separate specialized indexes, and the engine must decide which verticals the query warrants and where to place them (Arguello, Diaz, Callan, and Crespo, 2009). Answers to factual questions may be displayed directly, extracted from a page or from a structured knowledge base. Advertisements are retrieved and ranked by a separate system with its own auction. Increasingly, the page includes a generated summary that cites retrieved pages, which is retrieval-augmented generation applied to web search. Each of these components is itself a retrieval problem with its own index and its own ranking.

The results become evidence

The results page is also a measurement. The engine logs the query, the ranking, and the user's behavior: which results were clicked, how long the user stayed on a page before returning, and whether they reformulated the query. A query rewritten immediately suggests the first ranking failed. A click followed by a long visit and no further search suggests success. These logs train the spelling corrector, the query rewriter, the intent classifiers, and the ranking model itself. They also feed controlled experiments, in which a small fraction of traffic sees a modified ranker and its behavior is compared with that of users who see the current one.

The loop has hazards. Because of the position bias described in the relevance article, a model trained naively on clicks learns to keep its current top results where they are. Engines counter this by correcting for position bias, by randomizing some rankings to collect unbiased evidence, and by combining behavioral data with judgments from trained human raters. The loop also creates an incentive for manipulation, since anyone who can fake clicks or links can influence rankings. That is why web search has always been, in part, an adversarial problem. Finally, query logs record what people search for, which can be sensitive, so their collection and retention carry privacy obligations.

Summary

A web search engine answers a query in a sequence of steps:

1. Classify the intent and analyze the query.
2. Correct, expand, and rewrite the query, with a deliberate choice of how visible each change is.
3. Retrieve a large candidate set cheaply from the inverted index.
4. Score the candidates with many query-dependent and query-independent signals, combined by a learned model and refined in stages.
5. Remove duplicates, diversify the results, and generate snippets.
6. Assemble the page from several verticals.
7. Log what happens so that the next ranking is better.

The classical models covered in the rest of the course appear inside this process as components: the inverted index in step 3, term weighting and BM25 as ranking features in step 4, and evaluation methods for measuring the whole. The next article shows how the process runs within a few hundred milliseconds over an index far too large for any single machine.

References

• Arguello, J., Diaz, F., Callan, J., and Crespo, J.-F. (2009). Sources of evidence for vertical selection. In Proceedings of SIGIR 2009, 315–322.
• Barroso, L. A., Dean, J., and Hölzle, U. (2003). Web search for a planet: The Google cluster architecture. IEEE Micro, 23(2), 22–28.
• Brin, S., and Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7), 107–117.
• Broder, A. (2002). A taxonomy of web search. SIGIR Forum, 36(2), 3–10.
• Broder, A. Z., Glassman, S. C., Manasse, M. S., and Zweig, G. (1997). Syntactic clustering of the Web. Computer Networks and ISDN Systems, 29(8–13), 1157–1166.
• Carbonell, J., and Goldstein, J. (1998). The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proceedings of SIGIR 1998, 335–336.
• Cucerzan, S., and Brill, E. (2004). Spelling correction as an iterative process that exploits the collective knowledge of web users. In Proceedings of EMNLP 2004, 293–300.
• Dong, A., Chang, Y., Zheng, Z., Mishne, G., Bai, J., Zhang, R., Buchner, K., Liao, C., and Diaz, F. (2010). Towards recency ranking in web search. In Proceedings of WSDM 2010, 11–20.
• Jones, R., Rey, B., Madani, O., and Greiner, W. (2006). Generating query substitutions. In Proceedings of WWW 2006, 387–396.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapters 19 and 21. Cambridge University Press.
• Ntoulas, A., Najork, M., Manasse, M., and Fetterly, D. (2006). Detecting spam web pages through content analysis. In Proceedings of WWW 2006, 83–92.
• Rose, D. E., and Levinson, D. (2004). Understanding user goals in web search. In Proceedings of WWW 2004, 13–19.
• Silverstein, C., Henzinger, M., Marais, H., and Moricz, M. (1999). Analysis of a very large web search engine query log. SIGIR Forum, 33(1), 6–12.
• Tombros, A., and Sanderson, M. (1998). Advantages of query biased summaries in information retrieval. In Proceedings of SIGIR 1998, 2–10.
• Turpin, A., Tsegay, Y., Hawking, D., and Williams, H. E. (2007). Fast generation of result snippets in web search. In Proceedings of SIGIR 2007, 127–134.
• Wang, L., Lin, J., and Metzler, D. (2011). A cascade ranking model for efficient ranked retrieval. In Proceedings of SIGIR 2011, 105–114.