System and method for selectively searching partitions of a database

• US 7,254,580 B1
• Filed: 09/30/2003
• Issued: 08/07/2007
• Est. Priority Date: 07/31/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghemawat, Sanjay, Dean, Jeffrey, Wallach, Deborah Anne, Chang, Fay Wen, Gharachorloo, Kourosh
• Primary Examiner(s): Alam; Hosain
• Assistant Examiner(s): LIN, SHEW FEN
• Application Number:
  US10/676,651
• Time in Patent Office: 1,407 Days
• Field of Search: 707/6, 707/3, 707/100, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

When a search query is received, a plurality of partition indexes are searched using the set of search terms in the search query. Each partition index corresponds to a partition of a document index. The search of each respective partition index identifies a subset of a plurality of document index sub-partitions corresponding to the respective partition index. Next, the search query is executed by only those document index sub-partitions identified by the subsets, thereby identifying documents that satisfy the search query. By using the partition index to reduce the number of document index sub-partitions searched while executing a search query, the execution of the search query is made more efficient.

Claims

1. A computer implemented document search system comprising multiple computing devices each having at least one processor and memory, said document search system, comprising:

a first document index;

a second document index comprising a plurality of document index partitions, each partition comprising a subset of the second document index, each document index partition comprising a plurality of document index sub-partitions, each document index sub-partition configured to map terms to documents;

a plurality of partition indexes, each corresponding to a respective document index partition, each partition index mapping a specified term to a subset of the document index sub-partitions of the corresponding document index partition;

wherein the plurality of partition indexes together correspond to all partitions of the second document index;

a plurality of balancers, each respective balancer configured to receive a search query having a set of terms, comprising one or more terms, to search a respective partition index of the plurality of partition indexes so as to identify a subset of the document index sub-partitions that contain the set of terms, and to direct the search query to only the identified subset of the document index sub-partitions;

wherein the plurality of balancers operate in parallel;

wherein the plurality of balancers direct each search query to all of the partition indexes in the plurality of partition indexes; and

a mixer for obtaining first search results from a first document index for documents that satisfy the search query, for determining whether first search results satisfy predetermined criteria, and when the first search results do not satisfy the predetermined criteria, for performing additional operations, including sending the search query to all of the plurality of balancers and receiving and collating search results from the plurality of balancers to produce second search results.

2. The document search system of claim 1, wherein a respective partition index maps the specified term to an empty subset when the specified term is not contained within the respective partition index.

3. The document search system of claim 1, including a plurality of index search servers, each index search server configured to search at least a portion of at least one document index sub-partition of the plurality of document index sub-partitions so as to identify documents containing specified terms.

4. The document search system of claim 3, wherein a respective balancer is configured to direct the search query to only the servers, of the one of more servers, that are configured to search document index sub-partitions included in the identified subset.

5. The document search system of claim 1, wherein a respective balancer comprises:

a processor;

a communications interface; and

a memory, comprising;

communications procedures for receiving the search query, and for transmitting search results; and

a balancer filter comprising;

mapping instructions for searching a respective partition index for each term in the search query so as to generate a map for each said term;

combining instructions, utilized when the search query comprises a plurality of terms and the first instructions generate a plurality of maps, for generating a single map from the plurality of maps; and

identifying instructions for identifying a subset of the document index sub-partitions in accordance with the map or single map; and

distribution instructions for sending the search query to each document index sub-partition, if any, in the identified subset.

6. The document search system of claim 1, wherein

a respective balancer is configured so that when the search query includes a plurality of distinct terms, the respective balancer searches a respective partition index so as to obtain a plurality of maps, performs a Boolean operation on the plurality of maps so as to generate a single map, wherein the single map identifies a set of document index sub-partitions, and based on the identified set of document index sub-partitions identifies the subset of document index sub-partitions.

7. The document search system of claim 1, wherein

a plurality of document index sub-partitions correspond to each document index partition of the plurality of document index partitions;

and

the balancer is configured so to search the partition index so as to obtain a map for each term of the search query, the map identifying a subset of the document index sub-partitions, wherein each document index sub-partition in the subset contains at least one document having the specified term.

8. The document search system of claim 7, including a plurality of index search servers, each index search server configured to search at least one document index sub-partition so as to identify documents containing specified terms.

9. The document search system of claim 8, wherein the map identifying the subset comprises a set of bits, each respective bit of the map corresponds to a respective subset of the index search servers, and the balancer is configured to direct the search query to only index search servers corresponding to bits in the map having a first predefined value.

10. The document search system of claim 8, wherein a respective balancer is configured to direct the search query to only the index search servers, of the plurality of index search servers, that are configured to search document index sub-partitions included in the identified subset of document index sub-partitions.

11. A computer implemented method of searching for documents, comprising:

receiving a search query containing a set of search terms, the set of search terms having at least one search term;

searching a first document index for documents that satisfy the search query to produce first search results;

when the first search results satisfy predetermined criteria, transmitting at least a portion of the first search results as a response to the search query;

when the first search results do not satisfy the predetermined criteria, performing additional operations, comprising;

searching for the set of search terms in each of a plurality of partition indexes, each partition index corresponding to a document index partition of a second document index, wherein the search of each respective partition index identifies a subset of a plurality of document index sub-partitions of the document index partition corresponding to the respective partition index that contain the set of search terms; and

searching, in only those document index sub-partitions in the identified subsets, for documents containing the set of search terms; and

receiving and collating second search results from the searched document index sub-partitions in the identified subsets;

transmitting at least a portion of the second search results as a response to the search query;

wherein the plurality of partition indexes together correspond to all partitions of the second document index and each search query is directed to all the partition indexes in the plurality of partition indexes;

wherein each respective partition index maps any specified term to a respective subset of the document index sub-partitions of a corresponding document index partition, and wherein each document index sub-partition in the respective subset maps the specified term to at least one document containing the specified term.

12. The method of claim 11, wherein the searching in the document index sub-partitions in the identified subset includes directing the search query to one or more servers configured to search the document index sub-partitions in the identified subset.

13. The method of claim 11, wherein the respective partition index is configured to map a specified term in the search query to a set of document index sub-partitions, each document index sub-partition corresponding to a subset of the documents indexed by a respective document index partition of the set of document index partitions;

wherein each document index sub-partition to which the specified term is mapped by the partition index maps the specified term to at least one document having the specified term.

14. The method of claim 13, wherein the searching in the respective partition index includes, when the search query includes a plurality of distinct terms, searching the partition index with respect to each term in the plurality of distinct terms so as to obtain a plurality of maps, performing a Boolean operation on the plurality of maps so as to generate a single map, and based on the single map identifying the subset of document index partitions, wherein the single map identifies a set of document index sub-partitions.

15. The method of claim 13, including searching, in only those document index sub-partitions in the identified set of document index sub-partitions, for documents containing the set of search terms.

16. The method of claim 13, including identifying the subset of document index partitions based on the identified set of document index sub-partitions.

17. The method of claim 13, wherein

a plurality of document index sub-partitions correspond to each document index partition of the plurality of document index partitions;

and

the method includes searching the partition index so as to obtain a map for each term of the search query, the map identifying a subset of the document index sub-partitions, wherein each document index sub-partition in the subset maps the specified term to at least one document having the specified term.

18. The method of claim 17, including searching, in only those document index sub-partitions in the identified subset of document index sub-partitions, for documents containing the set of search terms.

19. The method of claim 17, wherein the map identifying the subset comprises a set of bits, each respective bit of the map corresponds to a respective subset of a set of index search servers, and the searching for documents includes directing the search query only to index search servers corresponding to bits in the map having a first predefined value.

20. The method of claim 17, including directing the search query only to index search servers, of a plurality of index search servers, that are configured to search document index sub-partitions included in the identified subset of document index sub-partitions.