Data parallel searching

Patent metadata

Field	Value
Publication number	US-9251291-B2
Application number	US-94753907-A
Country	US
Kind code	B2
Filing date	Nov 29, 2007
Priority date	Nov 29, 2007
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

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.

First claim

What is claimed is:

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 fo

Assignees

• Duffy John
• Essey Edward G
• Callahan Ii Charles D
• Microsoft Technology Licensing Llc

Inventors

• Duffy John
• Essey Edward G
• Callahan Ii Charles D

Classifications

• G06F16/90335 Primary

  Query processing · CPC title

• G06F16/24532

  of parallel queries · CPC title

• G06F17/30979 Primary

  Physics · mapped topic

• G06F17/30445

  Physics · mapped topic