DATA PARALLEL PRODUCTION AND CONSUMPTION

• US 20090144228A1
• Filed: 11/29/2007
• Published: 06/04/2009
• Est. Priority Date: 11/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Callahan, Charles D. II, Essey, Edward G., Duffy, John
• Granted Patent: US 8,190,624 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

Abstract

A parallel execution of a query is performed with a plurality of producers using a partitioned data source, thereby producing output data. The output data is consumed with at least one consumer. The at least one consumer is monitored. A determination is made whether to stop producing output data by at least one of the producers prior to completion of the execution of the query based on the monitoring.

Claims

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

performing a parallel execution of a query with a plurality of producers using a partitioned data source, thereby producing output data;

consuming the output data with at least one consumer;

monitoring the at least one consumer; and

determining whether to stop producing output data by at least one of the producers prior to completion of the execution of the query based on the monitoring.

2. The computer-readable medium of claim 1, wherein the at least one consumer runs concurrently with the plurality of producers.

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

storing produced output data in at least one bounded buffer, wherein the at least one consumer consumes output data from the at least one bounded buffer.

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

determining whether a cancellation event has occurred indicating that the at least one consumer will no longer consume any more output data; and

performing a cancellation of the producers when a cancellation event occurs, thereby causing the producers to no longer produce any more output data.

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

setting a shared flag when a cancellation event occurs that indicates that the at least one consumer will no longer consume any more output data; and

monitoring the shared flag with each of the producers.

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

each producer performing a cancellation of itself when the producer determines that the shared flag has been set, thereby causing the producer to no longer produce any more output data.

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

determining whether to place at least one of the producers in a quiescent state based on the monitoring.

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

placing at least one of the producers in a quiescent state when the monitoring indicates that the at least one consumer has stopped consuming output data for more than a threshold period of time, thereby causing the at least one producer placed in the quiescent state to stop producing output data.

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

causing producers in a quiescent state to exit the quiescent state and resume producing output data when the at least one consumer resumes consuming output data.

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

identifying an amount of output data that has been buffered by the producers but not yet consumed by the at least one consumer;

causing the at least one consumer to resume consuming output data; and

determining whether to cause producers in quiescent state to exit the quiescent state and resume producing output data based on the identified amount of output data.

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

providing a shared variable that stores a last consumption time value indicating a last time that the at least one consumer consumed output data;

periodically comparing a current time value with the last consumption time value with each of the producers; and

causing a producer to enter a quiescent state when the producer determines that a difference between the current time value and the last consumption time value is greater than a threshold value, thereby causing the producer to stop producing output data.

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

generating an output set with each of the producers based on results of the execution of the query, thereby generating a plurality of output sets; and

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

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

receiving a query 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 processing of the plurality of partitions using a plurality of producers, thereby producing output data; and

consuming the output data with at least one consumer; and

causing the producers to stop producing output data prior to completion of the parallel processing when the at least one consumer stops consuming output data for more than a threshold period of time.

14. The method of claim 13, and further comprising:

determining whether a cancellation event has occurred indicating that the at least one consumer will no longer consume any more output data; and

performing a cancellation of the producers when a cancellation event occurs, thereby causing the producers to no longer produce any more output data.

15. The method of claim 13, and further comprising:

setting a shared flag when a cancellation event occurs that indicates that the at least one consumer will no longer consume any more output data;

monitoring the shared flag with each of the producers; and

each producer performing a cancellation of itself when the producer determines that the shared flag has been set, thereby causing the producer to no longer produce any more output data.

16. The method of claim 13, and further comprising:

placing the producers in a quiescent state when the at least one consumer stops consuming output data for more than the threshold period of time, thereby causing the producers placed in the quiescent state to stop producing output data.

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

causing producers in a quiescent state to exit the quiescent state and resume producing output data when the at least one consumer resumes consuming output data.

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

providing a shared variable that stores a last consumption time value indicating a last time that the at least one consumer consumed output data;

periodically comparing a current time value with the last consumption time value with each of the producers; and

causing a producer to enter a quiescent state when the producer determines that a difference between the current time value and the last consumption time value is greater than a threshold value, thereby causing the producer to stop producing output data.

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

performing a parallel execution of a query with a plurality of producers using a partitioned data source, thereby producing output data;

storing the produced output data in a plurality of buffers;

consuming the stored output data with at least one consumer concurrently with the execution of the query;

placing the producers in a quiescent state when the at least one consumer stops consuming output data for more than a threshold period of time, thereby causing the producers placed in the quiescent state to stop producing output data; and

performing a cancellation of the producers when a cancellation event occurs that indicates that the at least one consumer will no longer consume any more output data, thereby causing the producers to no longer produce any more output data.

20. The computer-readable medium of claim 19, wherein the method further comprises:

causing producers in a quiescent state to exit the quiescent state and resume producing output data when the at least one consumer resumes consuming output data.