Partitioned query execution in event processing systems

• US 8,195,648 B2
• Filed: 10/21/2009
• Issued: 06/05/2012
• Est. Priority Date: 10/21/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zabback, Peter, Tarnavski, Tihomir, Sezgin, Beysim, Verona, Tomer
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US12/603,385
• Publication Number:
  US 20110093491A1
• Time in Patent Office: 958 Days
• Field of Search: None
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24535 of sub-queries or views

Abstract

Methods, systems, and computer-readable media are disclosed for partitioned query execution in event processing systems. A particular method includes receiving a plurality of events via an input stream. The plurality of events is partitioned into one or more groups, and a query application module is instantiated for each of the one or more groups based on a compiled query application plan. Each particular query application module for a particular group is configured to apply a query to events of the particular group to generate partial results. The method includes merging the partial results of each of the query application modules to generate merged output results and providing the output results to an output stream.

Claims

1. A computer system, comprising:

a processor; and

a memory communicatively coupled to the processor, the memory having computer-executable instructions that when executed by the processor provide one or more modules, the one or more modules further comprising;

an execution module configured to;

partition a plurality of events into one or more groups based on a partitioning operator;

instantiate a query application module for each of the one or more groups, wherein each particular query application module for a particular group includes data associated with the query and group-specific data associated with the particular group, and is configured to apply the query to events of the particular group to generate results, and wherein each query application module for a group comprises logic to execute a plurality of complex event processing (CEP) operators and wherein the logic of each query application module is configured for execution at a separate execution thread of the computer system; and

merge results of each of the query application modules.

2. The computer system of claim 1, further comprising:

a planning module configured to generate a query application plan based on a query that includes a partitioning operator, wherein the planning module executes during a compile-time of the computer system and wherein the execution module executes during a run-time of the computer system.

3. The computer system of claim 1, further comprising an input interface configured to receive the plurality of events via an input stream and an output interface configured to provide the merged results to an output stream.

4. The computer system of claim 1, wherein the execution module is further configured to receive a punctuation event and to selectively transmit the punctuation event to each query application module.

5. The computer system of claim 4, wherein the execution module is further configured to not transmit the punctuation event to a query application module for a group upon determining that the group does not include any events having a validity start time previous to or equal to a timestamp of the punctuation event.

6. The computer system of claim 4, wherein each query application module for a group is configured to delete events from the group that are invalidated by the punctuation event.

7. The computer system of claim 1, wherein the execution module is further configured to delete query application modules for empty groups.

8. The computer system of claim 1, wherein the execution module is further configured to instantiate additional query application modules for new groups.

9. The computer system of claim 1, wherein when the partition operator partitions events based on event payload, a number of the query application modules is determined at run-time, and wherein when the partition operator partitions events based on a hash function, the number of the query application modules is determined at compile-time.

10. The computer system of claim 1, wherein each query application module is further configured to merge logic to execute a first CEP operator with logic to execute a second CEP operator and wherein the merged logic executes at a single execution thread of the computer system.

11. A method, comprising:

receiving a plurality of events via an input stream, wherein a query application plan is compiled prior to receiving the plurality of events and wherein the query application plan determines partitioning logic that partitions the plurality of events;

partitioning the plurality of events into one or more groups;

instantiating a query application module for each of the one or more groups, wherein each particular query application module for a particular group is configured to apply a query to events of the particular group to generate partial results;

merging the partial results of each of the query application modules to generate merged output results; and

providing the merged output results to an output stream.

12. The method of claim 11, further comprising receiving a punctuation event.

13. The method of claim 12, further comprising:

determining that a first query application module includes at least one event having a validity start time previous to or equal to a timestamp of the punctuation event; and

transmitting the punctuation event to the first query application module.

14. The method of claim 13, further comprising:

determining that a second query application module does not include at least one event having a validity start time previous to or equal to the timestamp of the punctuation event; and

not transmitting the punctuation event to the second query application module.

15. The method of claim 11, further comprising deleting an existing query application module for a group in response to determining that the group does not include any events.

16. The method of claim 11, further comprising instantiating a new query application module for a new group without re-compiling the query application plan.

17. A computer-readable medium comprising instructions, that when executed by a computer, cause the computer to:

receive a user-defined query that includes a partitioning operator and at least one non-partitioning operator;

compile a query application plan for the query, wherein the query application plan indicates how to parallelize application of the at least one nonpartitioning operator;

during a run-time of the computer, receive a plurality of events via an input stream;

partition the plurality of events into one or more groups based on the partitioning operator;

instantiate a plurality of query application modules based on the compiled query application plan, wherein each particular query application module is associated with a particular group and is configured to apply the at least one non-partitioning operator to events of the particular group to generate partial results, wherein each query application module is associated with a single group;

merge the partial results of each of the query application modules to generate output results; and

provide the output results to an output stream.

18. The computer-readable medium of claim 17, wherein query is a continuously executing complex event processing (CEP) query.