IP Library › Granted Patent US 8,682,901

Granted Patent B1

US 8,682,901 · App. 13/332,278 · Granted Mar 25, 2014

Index server architecture using tiered and sharded phrase posting lists

Inventors: Pei Cao (Palo Alto, CA); Nadav Eiron (San Jose, CA); Soham Mazumdar (San Francisco, CA); Anna L. Patterson (San Jose, CA); Russell Power (New York, NY); Yonatan Zunger (Mountain View, CA)

Assignee: Google Inc.

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 8,682,901
App. No.: 13/332,278
Granted: Mar 25, 2014
Kind: B1

External Links

USPTO Patent Center↗ Full Patent PDF↗

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 (155)

1. A method of indexing documents of a document collection in an indexing system that includes a plurality of index servers, the method comprising:

determining a phrase posting list associated with a first phrase, the phrase posting list identifying documents of the document collection associated with the first phrase;

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

storing each different shard of the phrase posting list for the first phrase on a corresponding different index server;

storing a plurality of shards of different phrase posting lists on a first index server;

storing a plurality of shards of different phrase posting lists on a second index server; and

within each of the first and second index servers, for each shard of a phrase posting list, ordering the shard according to document identifiers of the documents included in the shard.

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

3. The method of claim 1 , wherein the number of shards into which the phrase posting list for the first phrase is divided corresponds to the number of index servers in the indexing system.

4. The method of claim 1 , further comprising storing shards of the phrase posting list for the first phrase in duplicate on different index servers.

5. The method of claim 1 , further comprising:

associating a first set of index servers with a first tier of index servers;

associating a second set of index servers with a second tier of index servers; and

determining whether to store shards of the phrase posting list for the first phrase on first tier or the second tier based on a query processing cost for the phrase posting list.

6. The method of claim 5 , wherein the number of shards stored on the second tier is an integer multiple of the number of shards stored on the first tier.

7. The method of claim 1 , further comprising:

determining a phrase posting list associated with a second phrase, the phrase posting list identifying a number of documents of the document collection having at least one occurrence of the second phrase;

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

storing each different shard of the phrase posting list for the second phrase on a corresponding different index server, wherein shards of the phrase posting list for the first phrase and shards of the phrase posting list for the second phrase, which identify the same document, are stored on the same index server.

8. The method of claim 7 , wherein the plurality of index servers are configured to perform query intersections among the documents identified by the shards of the first and second posting lists.

9. The method of claim 7 , wherein index servers that store different shards of a posting list for a phrase are configured to respond to a query in parallel.

10. The method of claim 9 , wherein the response to the query includes providing document identifiers from the shards of the posting list to other index servers without cross-communication between the index servers that store the different shards of the posting list.

11. A computer-implemented method comprising:

receiving a query for information from the document collection, wherein the query includes a first phrase;

accessing a plurality of index servers to retrieve identifiers of documents on a phrase posting list associated with the first phrase, wherein the phrase posting list identifies documents of the document collection associated with the first phrase, and is divided into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list, and each different shard being stored on a corresponding different index server of the plurality of index servers;

serving a response to the query, wherein the response is based on information in the phrase posting list associated with the first phrase; and

storing a plurality of shards of different phrase posting lists on a first index server;

storing plurality of shards of different phrase posting lists on a second index server; and

within each of the first and second index servers, for each shard of a phrase posting list, ordering the shard according to document identifiers of the documents included in the shard.

12. The method of claim 11 , wherein the first phrase is a multi-word phrase.

13. The method of claim 11 , wherein the number of shards into which the phrase posting list for the first phrase is divided corresponds to the number of index servers in the indexing system.

14. The method of claim 11 , further comprising storing shards of the phrase posting list for the first phrase in duplicate on different index servers.

15. The method of claim 11 , further comprising:

associating a first set of index servers with a first tier of index servers;

associating a second set of index servers with a second tier of index servers; and

determining whether to store shards of the phrase posting list for the first phrase on the first tier or the second tier based on a query processing cost for the phrase posting list.

16. The method of claim 15 , wherein the number shards stored on the second tier is an integer multiple of the number of shards stored on the first tier.

17. The method of claim 11 , wherein the query further includes a second phrase and further comprising:

accessing a plurality of index servers to retrieve identifiers of documents on a phrase posting list associated with the second phrase, wherein the phrase posting list identifies documents of the document collection associated with the second phrase, and is divided into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list, and each shard being stored on a corresponding index server of the plurality of index servers; and

wherein serving the response to the query is further based on information in the phrase posting list associated with the second phrase.

18. An indexing system for indexing documents in a document collection, the system comprising:

a plurality of index servers;

one or more memory devices configured store executable instructions; and

one or more processors configured to execute the stored instructions to cause the system to:

determine a phrase posting list associated with a first phrase, the phrase posting list identifying documents of the document collection associated with the first phrase;

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

store each shard of the phrase posting list for the first phrase on a corresponding index server;

determine a phrase posting list associated with a second phrase, the phrase posting list identifying a number of documents of the document collection having at least one occurrence of the second phrase;

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

store each shard of the phrase posting list for the second phrase on a corresponding index server,

wherein shards of the phrase posting list for the first phrase and shards of the phrase posting list for the second phrase, which identify the same document, are stored on the same index server.

19. The system of claim 18 , wherein the one or more processors are further configured to execute the stored instructions to cause the system to:

store a plurality of shards of different phrase posting lists on a first index server;

store a plurality of shards of different phrase posting lists on a second index server; and

within each of the first and second index servers, for each shard of a phrase posting list, order the shard according to document identifiers of the documents included in the shard.

20. The system of claim 18 , wherein the number of shards into which the phrase posting list for the first phrase is divided corresponds to the number of index servers in the indexing system.

21. The system of claim 18 , wherein the one or more processors are further configured to execute the stored instructions to cause the system to:

associate a first set of index servers with a first tier of index servers;

associate a second set of index servers with a second tier of index servers; and

determine whether to store shards of the phrase posting list for the first phrase on first tier or the second tier based on a query processing cost for the phrase posting list.

22. An indexing system for indexing documents of a document collection, the system comprising:

a plurality of index servers;

one or more memory devices configured store executable instructions; and

one or more processors configured to execute the stored instructions to cause the system to:

receive a query for information from the document collection, wherein the query includes a first phrase and a second phrase;

access a plurality of index servers to retrieve identifiers of documents on a phrase posting list associated with the first phrase, wherein the phrase posting list identifies documents of the document collection associated with the first phrase, and is divided into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list, and each shard being stored on a corresponding index server of the plurality of index servers;

access a plurality of the index servers to retrieve identifiers of documents on a phrase posting list associated with the second phrase, wherein the phrase posting list identifies documents of the document collection associated with the second phrase, and is divided into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list, and each shard being stored on a corresponding index server of the plurality of index servers; and

serve a response to the query, wherein the response is based on information in the phrase posting list associated with the first phrase and is based on information in the phrase posting list associated with the second phrase.

23. The system of claim 22 , wherein the one or more processors are further configured to execute the stored instructions to cause the system to:

store a plurality of shards of different phrase posting lists on a first index server;

store plurality of shards of different phrase posting lists on a second index server; and

within each of the first and second index servers, for each shard of a phrase posting list, order the shard according to document identifiers of the documents included in the shard.

24. The system of claim 22 , wherein the number of shards into which the phrase posting list is divided corresponds to the number of index servers in the indexing system.

25. The system of claim 22 , wherein the one or more processors are further configured to execute the stored instructions to cause the system to:

associate a first set of index servers with a first tier of index servers;

associate a second set of index servers with a second tier of index servers; and

determine whether to store shards of the phrase posting list on the first tier or the second tier based on a query processing cost for the phrase posting list.

26. The system of claim 22 , wherein the plurality of index servers are configured to perform query intersections among the documents identified by the shards of the first and second posting lists.

27. The system of claim 22 , wherein index servers that store different shards of a posting list for a phrase are configured to respond to a query in parallel.

28. The system of claim 27 , wherein the response to the query includes providing document identifiers from the shards of the posting list to other index servers without cross-communication between the index servers that store the different shards of the posting list.

29. The system of claim 22 , wherein the number of shards into which the phrase posting list is divided corresponds to the number of index servers in the indexing system.

30. The system of claim 22 , wherein the one or more processors are further configured to execute the stored instructions to cause the system to:

associate a first set of index servers with a first tier of index servers;

associate a second set of index servers with a second tier of index servers; and

determine whether to store shards of the phrase posting list on the first tier or the second tier based on a query processing cost for the phrase posting list.

31. A method of indexing documents of a document collection in an indexing system that includes a plurality of index servers, the method comprising:

determining a phrase posting list associated with a first phrase, the phrase posting list identifying documents of the document collection associated with the first phrase;

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

storing each different shard of the phrase posting list for the first phrase on a corresponding different index server;

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

storing each different shard of the phrase posting list for the second phrase on a corresponding different index server,

wherein shards of the phrase posting list for the first phrase and shards of the phrase posting list for the second phrase, which identify the same document, are stored on the same index server.

32. The method of claim 31 , wherein the first phrase is a multi-word phrase.

33. The method of claim 31 , further comprising:

storing a plurality of shards of different phrase posting lists on a first index server;

storing a plurality of shards of different phrase posting lists on a second index server; and

within each of the first and second index servers, for each shard of a phrase posting list, ordering the shard according to document identifiers of the documents included in the shard.

34. The method of claim 31 , wherein the number of shards into which the phrase posting list for the first phrase is divided corresponds to the number of index servers in the indexing system.

35. The method of claim 31 , further comprising storing shards of the phrase posting list for the first phrase in duplicate on different index servers.

36. The method of claim 31 , further comprising:

associating a first set of index servers with a first tier of index servers;

associating a second set of index servers with a second tier of index servers; and

determining whether to store shards of the phrase posting list for the first phrase on first tier or the second tier based on a query processing cost for the phrase posting list.

37. The method of claim 36 , wherein the number shards stored on the second tier is an integer multiple of the number of shards stored on the first tier.

38. The method of claim 31 , wherein the plurality of index servers are configured to perform query intersections among the documents identified by the shards of the first and second posting lists.

39. The method of claim 31 , wherein index servers that store different shards of a posting list for a phrase are configured to respond to a query in parallel.

40. A computer-implemented method comprising:

receiving a query for information from the document collection, wherein the query includes a first phrase and a second phrase;

accessing a plurality of index servers to retrieve identifiers of documents on a phrase posting list associated with the first phrase, wherein the phrase posting list identifies documents of the document collection associated with the first phrase, and is divided into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list, and each different shard being stored on a corresponding index server of the plurality of different index servers;

accessing a plurality of the index servers to retrieve identifiers of documents on a phrase posting list associated with the second phrase, wherein the phrase posting list identifies documents of the document collection associated with the second phrase, and is divided into a plurality of shards, each shard identifying a subset of the plurality of the documents identified by the posting list, and each shard being stored on a corresponding index server of the plurality of index servers; and

serving a response to the query, wherein the response is based on information in the phrase posting list associated with the first phrase and is based on information in the phrase posting list associated with the second phrase.

41. The method of claim 40 , wherein the number of shards into which the phrase posting list for the first phrase is divided corresponds to the number of index servers in the indexing system.

42. The method of claim 40 , further comprising storing shards of the phrase posting list for the first phrase in duplicate on different index servers.

43. The method of claim 40 , further comprising:

associating a first set of index servers with a first tier of index servers;

associating a second set of index servers with a second tier of index servers; and

determining whether to store shards of the phrase posting list for the first phrase on the first tier or the second tier based on a query processing cost for the phrase posting list.

44. The method of claim 43 , wherein the number shards stored on the second tier is an integer multiple of the number of shards stored on the first tier.

45. The method of claim 40 , further comprising:

storing a plurality of shards of different phrase posting lists on a first index server;

storing plurality of shards of different phrase posting lists on a second index server; and

within each of the first and second index servers, for each shard of a phrase posting list, ordering the shard according to document identifiers of the documents included in the shard.

46. An indexing system for indexing documents in a document collection, the system comprising:

a plurality of index servers;

one or more memory devices configured store executable instructions; and

one or more processors configured to execute the stored instructions to cause the system to:

determine a phrase posting list associated with a first phrase, the phrase posting list identifying documents of the document collection associated with the first phrase;

divide the phrase posting list for the first phrase into a plurality of shards, each shard identifying a subset of the documents identified by the posting list;

store each shard of the phrase posting list for the first phrase on a corresponding index server;

store a plurality of shards of different phrase posting lists on a first index server;

store a plurality of shards of different phrase posting lists on a second index server; and

within each of the first and second index servers, for each shard of a phrase posting list, order the shard according to document identifiers of the documents included in the shard.

47. The system of claim 46 , wherein the number of shards into which the phrase posting list is divided corresponds to the number of index servers in the indexing system.

48. The system of claim 46 , wherein the one or more processors are further configured to execute the stored instructions to cause the system to:

associate a first set of index servers with a first tier of index servers;

associate a second set of index servers with a second tier of index servers; and

determine whether to store shards of the phrase posting list for the first phrase on first tier or the second tier based on a query processing cost for the phrase posting list.

49. The system of claim 46 , wherein the one or more processors are further configured to execute the stored instructions to cause the system to:

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

store each shard of the phrase posting list for the second phrase on a corresponding index server, wherein shards of the phrase posting list for the first phrase and shards of the phrase posting list for the second phrase, which identify the same document, are stored on the same index server.

50. An indexing system for indexing documents of a document collection, the system comprising:

a plurality of index servers;

one or more memory devices configured store executable instructions; and

one or more processors configured to execute the stored instructions to cause the system to:

receive a query for information from the document collection, wherein the query includes a first phrase;

serve a response to the query, wherein the response is based on information in the phrase posting list associated with the first phrase;

store a plurality of shards of different phrase posting lists on a first index server;

store plurality of shards of different phrase posting lists on a second index server; and

within each of the first and second index servers, for each shard of a phrase posting list, order the shard according to document identifiers of the documents included in the shard.

51. The system of claim 50 , wherein the one or more processors are further configured to execute the stored instructions to cause the system to:

Assignments (2)

CHANGE OF NAME Recorded Oct 2, 2017

From: GOOGLE INC.

To: GOOGLE LLC

Reel/Frame 044101/0299 →

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jan 25, 2013

From: PATTERSON, ANNA L.

To: GOOGLE INC.

Reel/Frame 029695/0389 →

Continuity (2)

Continuation 12716008 · Mar 2, 2010

Continuation 11694780 · Mar 30, 2007