Data parallel searching

• US 9,251,291 B2
• Filed: 11/29/2007
• Issued: 02/02/2016
• Est. Priority Date: 11/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Duffy, John, Essey, Edward G., Callahan, Charles D. II
• Primary Examiner(s): Jacob, Ajith
• Application Number:
  US11/947,539
• Publication Number:
  US 20090144232A1
• Time in Patent Office: 2,987 Days
• Field of Search: 707/3, 707/655
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

A query that includes a search operator and that identifies an input data source is received. The input data source is partitioned into a plurality of partitions. A parallel search through the partitions is performed for an element that could halt the search. The parallel search is performed using a plurality of parallel workers. One of the parallel workers generates a notification when the element is found by that worker. The notification notifies the other parallel workers that the search could be halted. Each of the parallel workers generates an output set based on results of the search. The output sets are merged into a merged output set.

Claims

1. A computer-readable storage medium storing computer-executable instructions for performing a method comprising:

receiving a query that includes a search operator and that identifies an input data source;

partitioning the input data source into a plurality of partitions;

performing a parallel search through the partitions for an element that could halt the search using a plurality of parallel workers that concurrently search the partitions;

generating a notification with one of the parallel workers when the element is found by that worker, thereby notifying other parallel workers that the search could be halted; and

making a determination with each of the other parallel workers whether to continue performing the search based on the generated notification.

2. The computer-readable medium of claim 1, wherein the method further comprises:

generating an output set with each of the parallel workers based on results of the search, thereby generating a plurality of output sets; and

merging the plurality of output sets into a merged output set.

3. The computer-readable medium of claim 1, wherein the method further comprises:

stopping performance of the search by all of the parallel workers when the notification is generated.

4. The computer-readable medium of claim 1, wherein the method further comprises:

making a determination with each of the other parallel workers whether to continue performing the search based on an index for the found element.

5. The computer-readable medium of claim 1, wherein the method further comprises:

providing a plurality of partitioning methods;

selecting one of the partitioning methods based on a type of the search operator; and

partitioning the input data source into the plurality of partitions using the selected partitioning method.

6. The computer-readable medium of claim 5, wherein one of the plurality of partitioning methods comprises a striping partitioning method in which each partition is divided into a plurality of chunks that are searched in parallel by the plurality of workers.

7. The computer-readable medium of claim 6, wherein the striping partitioning method includes selecting a size of each of the plurality of chunks to be a multiple of a cache line size.

8. The computer-readable medium of claim 1, wherein the method further comprises:

performing with at least one of the parallel workers a speculative execution of at least one additional operator contained in the query prior to completion of the search by all of the parallel workers.

9. The computer-readable medium of claim 8, wherein the speculative execution is performed using transactional memory.

10. The computer-readable medium of claim 1, wherein the search operator comprises an ALL search operator, wherein the notification is generated when one of the parallel workers finds an element that does not satisfy criteria specified by the ALL search operator, and wherein the notification causes the other parallel workers to stop searching.

11. The computer-readable medium of claim 1, wherein the search operator comprises one of an ANY search operator or a CONTAINS search operator, wherein the notification is generated when one of the parallel workers finds an element that satisfies criteria specified by the search operator, and wherein the notification causes the other parallel workers to stop searching.

12. The computer-readable medium of claim 1, wherein the search operator comprises one of a FIRST search operator or a LAST search operator, and wherein the method further comprises:

providing a shared variable that is shared by the plurality of workers and that stores an index value for an element that satisfies criteria specified by the search operator;

comparing an index for each element that satisfies criteria specified by the search operator to the index value of the shared variable; and

selectively updating the index value of the shared variable based on the comparison.

13. The computer-readable medium of claim 12, wherein the method further comprises:

comparing an index for an element currently being examined by one of the parallel workers to the index value of the shared variable; and

determining whether the parallel worker will stop searching based on a result of the comparison for the element currently being examined.

14. The computer-readable medium of claim 1, wherein the search operator comprises one of a TAKEWHILE search operator or a SKIPWHILE search operator, and wherein the method further comprises:

providing a shared variable that is shared by the plurality of workers and that stores an index value for an element that does not satisfy criteria specified by the search operator;

comparing an index for each element that does not satisfy criteria specified by the search operator to the index value of the shared variable; and

selectively updating the index value of the shared variable based on the comparison.

15. The computer-readable medium of claim 14, wherein the method further comprises:

storing each element that satisfies criteria specified by the search operator in a buffer of the worker that examined the element.

16. The computer-readable medium of claim 15, wherein the method further comprises:

comparing an index for an element currently being examined by one of the parallel workers to the index value of the shared variable; and

determining whether the parallel worker will stop searching based on a result of the comparison for the element currently being examined.

17. A method for performing a parallel execution of a query, the method comprising:

receiving a search operator and that identifies an input data source;

partitioning the input data source into a partitioned data source comprising a plurality of partitions;

performing a parallel search through the partitions using a plurality of parallel workers that concurrently search the partitions;

providing a notification from a first one of the parallel workers to other parallel workers when the first parallel worker finds an element that could result in the search being halted; and

making a determination with each of the other parallel workers whether to continue performing the search based on the notification.

18. The method of claim 17, and further comprising:

stopping performance of the search by all of the parallel workers when the notification is provided.

19. The method of claim 17, and further comprising:

making a determination with each of the other parallel workers whether to continue performing the search based on an index for the found element.

20. A computer-readable storage medium storing computer-executable instructions for performing a method comprising:

receiving a query that includes a search operator and that identifies an input data source;

partitioning the input data source into a plurality of partitions;

providing the plurality of partitions to a plurality of parallel workers, wherein each of the parallel workers is provided a different one of the partitions;

searching elements within the partitions concurrently with the plurality of parallel workers to identify an element that could result in the search being halted;

generating a notification with one of the parallel workers when a potentially search halting element is found by that parallel worker to notify other parallel workers of the found element; and

making an independent determination with each of the other parallel workers whether to continue performing the search based on an index for the found element, wherein the independent determination made by each of the other parallel workers is made in response to receiving the notification.