Dynamic query master agent for query execution

• US 9,195,745 B2
• Filed: 03/25/2011
• Issued: 11/24/2015
• Est. Priority Date: 11/22/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Risvik, Knut Magne, Hopcroft, Michael, Kalyanaraman, Karthik, Chilimbi, Trishul, Anderson, Christopher W., Setiawan, Henry
• Primary Examiner(s): Shanmugasundaram, Kannan
• Application Number:
  US13/072,419
• Publication Number:
  US 20120130984A1
• Time in Patent Office: 1,705 Days
• Field of Search: 707/718, 707/719, 707/770
• US Class Current: 1/1
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation

Abstract

A preliminary segment root and a final segment root are selected for each segment. Each time a search query is received, a set of nodes in each segment that will be used to resolve the search query is identified. A preliminary segment root is selected from the set of nodes. Based on statistical data from each node in the set of nodes indicating each node'"'"'s capability to act as a final segment root that assembles query-execution data, the preliminary segment root algorithmically selects the final segment root. The other nodes in the set of nodes are notified regarding the identity of the final segment root.

Claims

1. One or more computer-storage memory storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for assigning a segment root, the method comprising:

receiving a search query;

identifying a set of nodes in a segment that will be used to resolve the search query, the segment is assigned a group of documents indexed by atom in a reverse index and indexed by document in a forward index, wherein corresponding portions of the reverse index and forward index are apportioned to each node in the set of nodes, and wherein the reverse index is used for a preliminary ranking process and the forward index is used for a final ranking process;

selecting a preliminary segment root from the set of nodes;

receiving, at the preliminary segment root, statistical data from each node in the identified set of nodes, the statistical data indicating each node'"'"'s capability to act as a final segment root that is responsible for assembling query-execution results from the set of nodes based on the search query, wherein the statistical data is generated based on, at least in part, the preliminary ranking process and the final ranking process;

algorithmically selecting the final segment root from the set of nodes based on the statistical data; and

notifying the set of nodes about the final segment root so that the nodes know where to send their respective query-execution results.

2. The computer-storage memory of claim 1, wherein each node in the set of nodes in each segment is identified based on a hash of one or more atoms in the query to the portion of the index stored in each node.

3. The computer-storage memory of claim 1,

wherein the preliminary segment root is selected at random.

4. The computer-storage memory of claim 1, wherein the preliminary segment root is selected based on an expected load such that the node having the lowest expected load is selected as the preliminary segment root.

5. The computer-storage memory of claim 1, wherein the preliminary segment root is selected based on a current load such that the node having the lowest current load of outstanding queries is selected as the preliminary segment root.

6. The computer-storage memory of claim 1, wherein the preliminary segment root and the final segment root are selected for each segment in response to the received search query.

7. The computer-storage memory of claim 1, wherein the statistical data comprises one or more of a length of each node'"'"'s posting list, an input/output load, problem signals associated with a particular node, or a quantity of data that would be required to be transferred to the final segment root.

8. The computer-storage memory of claim 1, further comprising executing the search query using the set of nodes.

9. The computer-storage memory of claim 8, wherein the query-execution results from multiple segments are aggregated and returned to a user.

10. One or more tangible computer-storage memory storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for assigning a segment root, the method comprising:

at a segment comprising a plurality of nodes, receiving a search query to be executed;

identifying a set of nodes from the plurality of nodes in the segment that will be used to execute the search query, the segment is assigned a group of documents indexed by atom in a reverse index and indexed by document in a forward index, wherein corresponding portions of the reverse index and forward index are apportioned to each node in the set of nodes, and wherein the reverse index is used for a preliminary ranking process and the forward index is used for a final ranking process;

prior to execution of the search query, selecting a preliminary segment root from the plurality of nodes, the selection based on one or more of an expected load for each node or a random selection;

receiving statistical data at the preliminary segment root at the preliminary segment root from each node in the set of nodes that will be used to execute the search query, the statistical data generated based on, at least in part, the preliminary ranking process and the final ranking process, wherein the statistical data includes current load and cost data associated with sending data across a network;

based on the statistical data, selecting a final segment root that will aggregate query-execution data from the set of nodes during query execution; and

executing the search query.

11. The method of claim 10, wherein each node in the plurality of nodes has stored thereon a portion of a search index used to identify relevant documents based on the search query.

12. The method of claim 10, wherein the final segment root is selected based on a lowest load and lowest cost of the set of nodes.

13. The method of claim 10, wherein the final segment root accepts the search query from an external source.

14. The method of claim 10, wherein each of the plurality of nodes has stored thereon a portion of a reverse index that is indexed by atom and a portion of a forward index that is indexed by document.

15. The method of claim 14, wherein executing the search query further comprises a preliminary ranking process that utilizes the set of nodes whose reverse indexes include an atom contained in the search query.

16. The method of claim 15, wherein executing the search query further comprises a final ranking process that utilizes a different set of nodes whose forward indexes include a document identified from the preliminary ranking process.

17. One or more memory storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for assigning a segment root, the method comprising:

at a corpus root that comprises a plurality of segments, receiving a search query, wherein each of the plurality of segments comprises a plurality of nodes that each has a portion of a search index stored thereon, the search index comprising a group of documents indexed by atom in a reverse index and indexed by document in a forward index, and wherein each of the plurality of nodes has stored thereon corresponding portions of the reverse index and forward index apportioned to each node, and wherein the reverse index is used for a preliminary ranking process and the forward index is used for a final ranking process;

identifying a set of nodes in each segment that will be used to execute the received search query;

for each of the plurality of segments, identifying a preliminary segment root from the set of nodes;

requesting statistical data from each node in the set of nodes that will be used to execute the received search query;

receiving the statistical data from each node of the set of nodes, the statistical data indicating an availability of each node to act as a final segment root, wherein the statistical data is generated based on, at least in part, the preliminary ranking process and the final ranking process;

based on the statistical data, selecting the final segment root for each segment such that the final segment root collects the query-execution data for both the preliminary ranking process and the final ranking process; and

executing the search query.

18. The computer-storage memory of claim 17, wherein the statistical data is communicated to the preliminary segment root by way of a communication bus accessible by each of the plurality of nodes.

19. The computer-storage memory of claim 17, further comprising communicating a finalization message to the plurality of nodes indicating an identification of the final segment root.

20. The computer-storage memory of claim 17, further comprising, at each final segment root, receiving the query-execution data from the set of nodes.