DYNAMIC QUERY MASTER AGENT FOR QUERY EXECUTION

• US 20120130984A1
• Filed: 03/25/2011
• Published: 05/24/2012
• Est. Priority Date: 11/22/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: RISVIK, KNUT MAGNE, HOPCROFT, MICHAEL, CHILIMBI, TRISHUL, ANDERSON, CHRISTOPHER W., KALYANARAMAN, KARTHIK, SETIAWAN, HENRY
• Granted Patent: US 9,195,745 B2
• Time in Patent Office: Days
• US Class Current: 707/715
• 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 media 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;

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;

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 media of claim 1, wherein each node in the set of nodes has stored thereon a portion of a search index that is used to execute the search query.

3. The computer-storage media of claim 1, wherein the preliminary segment root is selected at random.

4. The computer-storage media 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 media 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 media 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 media 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 media of claim 1, further comprising executing the search query using the set of nodes.

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

10. One or more computer-storage media 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 that will be used to execute the search query;

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 from each node in the set of nodes that will be used to execute the search query, 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 computer-storage media 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;

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 that collects query-execution data from the set of nodes in its corresponding segment;

based on the statistical data, selecting the final segment root for each segment; and

executing the search query.

18. The computer-storage media 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 media 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 media of claim 17, further comprising, at each final segment root, receiving the query-execution data from the set of nodes.