Index server architecture using tiered and sharded phrase posting lists

• US 9,223,877 B1
• Filed: 01/07/2015
• Issued: 12/29/2015
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cao, Pei, Eiron, Nadav, Mazumdar, Soham, Patterson, Anna L., Power, Russell, Zunger, Yonatan
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US14/591,746
• Time in Patent Office: 356 Days
• Field of Search: 707/713, 707/715, 707/741, 704/1, 709/223
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

An information retrieval system uses phrases to index, retrieve, organize and describe documents. Phrases are extracted from the document collection. Documents are the indexed according to their included phrases, using phrase posting lists. The phrase posting lists are stored in an cluster of index servers. The phrase posting lists can be tiered into groups, and sharded into partitions. Phrases in a query are identified based on possible phrasifications. A query schedule based on the phrases is created from the phrases, and then optimized to reduce query processing and communication costs. The execution of the query schedule is managed to further reduce or eliminate query processing operations at various ones of the index servers.

Claims

1. A method comprising:

determining a phrase posting list for a phrase, the phrase posting list identifying a set of web-pages that include the phrase;

determining a cost for the phrase posting list; and

assigning the phrase posting list to one of a plurality of tiers based on the cost, where each tier has a respective minimum cost used to assign the phrase posting list and where higher cost results in the phrase posting list being assigned to a tier with higher performance.

2. The method of claim 1, wherein the cost is based on based on a quantity of web-pages in the set.

3. The method of claim 1, wherein the cost is based on based on a length in bytes of the phrase posting list.

4. The method of claim 1, wherein higher performance is faster memory.

5. The method of claim 1, wherein the phrase posting list is assigned to one of three tiers based on the cost.

6. The method of claim 1, wherein assigning the phrase includes:

assigning the phrase to a tier of the plurality of tiers for which the cost of the phrase posting list is greater than the minimum cost for the tier and less than the minimum cost for a next tier.

7. The method of claim 1, wherein the phrase posting list for the phrase is a first phrase posting list for the first phrase, the set is a first set of web-pages, and the cost is a first cost, and the method further comprises:

determining a second phrase posting list for a second phrase, the second phrase posting list identifying a second set of web-pages that include the second phrase, the second set of web-pages including a first web-page and the first set of web-pages included the first web-page;

determining a second cost for the second phrase posting list, the second cost being less than the first cost; and

assigning the second phrase posting list to one of the plurality of tiers based on the second cost,

wherein the first phrase posting list and the second phrase posting list are assigned to different tiers.

8. The method of claim 1, further comprising:

receiving a query for the phrase;

accessing the one tier to which the phrase posting list is assigned; and

providing the identifiers for the set of web-pages from the one tier without accessing remaining tiers.

9. An indexing system comprising:

an index having at least two tiers, each tier being associated with a minimum cost;

at least one processor; and

memory storing instructions that, when executed by the at least one processor, cause the indexing system to;

determine a phrase posting list for a phrase, the phrase posting list identifying a set of web-pages that include the phrase;

determining a cost for the phrase posting list; and

assigning the phrase posting list to one of the at least two tiers based on the cost by determining a tier having a minimum cost less than or equal to the cost for the phrase, where the minimum cost for a next tier is greater than the cost for the phrase.

10. The system of claim 9, further comprising a plurality of index servers and the memory further stores instructions that, when executed by the at least one processor, cause the indexing system to:

store phrase posting lists assigned to a lowest tier to one index server; and

store phrase posting lists assigned to a highest tier across the plurality of index servers.

11. The system of claim 9, further comprising a plurality of index servers, wherein each tier is divided among a number of the plurality of index servers, so that the number of index servers is an integer multiple of the number of index servers in a next lower tier.

12. The system of claim 11, wherein a lowest tier is divided among one index server.

13. The system of claim 9, wherein the cost is based on based on a quantity of web-pages in the set and the minimum cost is a minimum number of identified web-pages.

14. The system of claim 9, wherein the cost is based on based on a length in bytes of the phrase posting list and the minimum cost is a minimum length.

15. The system of claim 9, wherein a tier with a higher minimum cost is associated with faster memory.

16. The system of claim 9, wherein the phrase posting list for the phrase is a first phrase posting list for the first phrase, the set is a first set of web-pages, and the cost is a first cost that is higher than the minimum cost for a second tier, and the memory further includes instructions that, when executed by the at least one processor, cause the indexing system to:

determine a second phrase posting list for a second phrase, the second phrase posting list identifying a second set of web-pages that include the second phrase, the second set of web-pages including a first web-page and the first set of web-pages included the first web-page;

determine a second cost for the second phrase posting list, the second cost being less than the minimum cost for the second tier; and

assign the second phrase posting list to a first tier of the at least two tiers based on the second cost.