Index server architecture using tiered and sharded phrase posting lists

• US 8,090,723 B2
• Filed: 03/02/2010
• Issued: 01/03/2012
• 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:
  US12/716,008
• Publication Number:
  US 20100161617A1
• Time in Patent Office: 672 Days
• Field of Search: 707/741, 707/736, 707/792, 707/802, 707/830, 707/999.06, 707/706, 707/709, 707/737, 707/750, 707/999.004, 707/999.003, 707/999.005
• US Class Current: 707/741
• 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 of indexing documents based on phrases occurring in the documents, the method comprising:

selecting a phrase posting list associated with a phrase, the phrase posting list identifying a number of documents having at least one occurrence of the phrase;

determining, with one or more processors, a length of the phrase posting list, the length of the phrase posting list being based on the number of documents having at least one occurrence of the phrase;

when the length of the phrase posting list is less than a first predetermined length, associating the phrase posting list with one of a plurality of first tier index servers;

when the length of the phrase posting list is greater than the first predetermined length;

dividing the phrase posting list into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list; and

associating each phrase posting list shard with a corresponding selected second tier index server.

2. The method of claim 1, wherein the phrase is a multi-word phrase.

3. The method of claim 1, wherein each index server includes a plurality of phrase posting lists that are each divided into a plurality of shards, and further comprising:

within each index server, ordering the phrase posting lists according to phrase identifiers associated with the phrase posting lists; and

within each phrase posting list shard, ordering the phrase posting list according to document identifiers of the documents included in the shard.

4. The method of claim 1, further comprising:

when the length of the phrase posting list is greater than a second predetermined length that is greater than the first predetermined length;

dividing the phrase posting list into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list; and

associating each phrase posting list shard with a corresponding selected third tier index server.

5. The method of claim 4, wherein the number of shards correspond to the number of third tier index servers, and wherein the number of third tier index servers is an integer multiple of the number of second tier index servers.

6. The method of claim 1, wherein when the length of the phrase posting list is greater than the first predetermined length the number of shards correspond to the number of second tier index servers.

7. A method of indexing documents based on phrases occurring in the documents, the method comprising:

storing a first plurality of phrase posting lists in one or more memories of a first set of index servers, each of the first plurality of phrase posting lists being associated with a phrase and identifying a set of documents having at least one occurrence of the phrase, wherein a length of the each of the first plurality of phrase posting lists is less than a first predetermined length; and

storing a second plurality of phrase posting lists in one or more memories of a second set of index servers, each of the second plurality of phrase posting lists being associated with a phrase and identifying a set of documents having at least one occurrence of the phrase, wherein a length of the second plurality of phrase posting lists is greater than the first predetermined length, each the second plurality of phrase posting lists being partitioned into a number of shards.

8. The method of claim 7, wherein the phrases associated with which the first and second plurality of phrase posting lists include multi-word phrases.

9. The method of claim 7, wherein the first set of index servers is different from the second set of index servers.

10. The method of claim 7, wherein the first set of index servers include one or more index servers from the second set of index servers.

11. The method of claim 7, further comprising:

within each index server of the second set of index servers, ordering the phrase posting lists according to phrase identifiers associated with the phrase posting lists; and

within each phrase posting list shard, ordering the phrase posting list according to document identifiers of the documents included in the shard.

12. A phrase-based indexing system for indexing documents according to phrases, the system comprising:

a first number of first tier index servers configured to store phrase posting lists for each of a plurality of phrases, each phrase posting list associated with one of the plurality of phrases and identifying a number of documents having at least one occurrence of the phrase; and

a second number of second tier index servers, configured to store shards of phrase posting lists, the phrase posting lists being associated with a phrase and a list of documents having at least one occurrence of the phrase, and each phrase posting list shard being associated with a phrase and a subset of the list of documents that are associated with the phrase posting list for the phrase;

wherein the first tier index servers are configured to store phrase posting lists having a length less than a first predetermined length;

wherein the second tier index servers are configured to store phrase posting lists having a length greater than the first predetermined length.

13. The system of claim 12, wherein the phrases include multi-word phrases.

14. The system of claim 12, wherein the first tier index servers are different from the second tier index servers.

15. The system of claim 12, wherein the first tier index servers include one or more index servers from the second tier index servers.

16. The system of claim 12, wherein the number of shards for a phrase posting list having a length greater than the first predetermined length corresponds to the number of second tier index servers and each shard of the phrase posting list is stored in a different second tier index server.

17. A method of indexing documents based on phrases occurring in the documents of a document collection, the method comprising:

determining, with one or more processors, a plurality of phrase posting lists, each phrase posting list associated with a phrase that occurs in the documents and identifying a number of documents having at least one occurrence of the phrase;

associating a first subset of the plurality of phrase posting lists with a first tier of index servers;

associating a second subset of the plurality of phrase posting lists with a second tier of index servers; and

dividing a phrase posting list from the second subset into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list,

wherein the first tier index servers are configured to store phrase posting lists having a length less than a first predetermined length;

wherein the second tier index servers are configured to store phrase posting lists having a length greater than the first predetermined length.

18. The method of claim 17, wherein the phrases include multi-word phrases.

19. The method of claim 17, wherein a number of shards for a phrase posting list from the second subset corresponds to a number of second tier index servers.

20. The method of claim 19, wherein each shard of the phrase posting list is stored in a different second tier index server.