Scheduling for Fast Response Multi-Pattern Matching Over Streaming Events

• US 20110137942A1
• Filed: 01/29/2010
• Published: 06/09/2011
• Est. Priority Date: 12/09/2009
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Zhang, Jin, Yan, Ying, Shan, Ming-Chien
• Granted Patent: US 8,433,725 B2
• Time in Patent Office: Days
• US Class Current: 707/780
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

A query pattern handler may be configured to determine at least one query pattern to be matched against a stream of events, and may be configured to determine a plurality of run-time patterns representing active instances of the at least one query pattern which are currently available for matching, and which each include a plurality of states. An event scheduler may be configured to receive an event of the stream of events, the event associated with a current event set of the stream of events. A run-time pattern scheduler may be configured to determine a ranked set of the run-time patterns based on a priority metric which characterizes, for each run-time pattern, an advancement of each run-time pattern from a current state thereof when matched against the current event set. A pattern match evaluator may be configured to evaluate each run-time pattern of the ranked set, in turn, against the current event set.

Claims

1. A system including instructions recorded on a computer-readable medium, the system comprising:

a query pattern handler configured to determine at least one query pattern to be matched against a stream of events, and configured to determine a plurality of run-time patterns representing active instances of the at least one query pattern which are currently available for matching, and which each include a plurality of states;

an event scheduler configured to receive an event of the stream of events, the event associated with a current event set of the stream of events;

a run-time pattern scheduler configured to determine a ranked set of the run-time patterns based on a priority metric which characterizes, for each run-time pattern, an advancement of each run-time pattern from a current state thereof when matched against the current event set; and

a pattern match evaluator configured to evaluate each run-time pattern of the ranked set, in turn, against the current event set.

2. The system of claim 1, wherein the query pattern handler comprises a state machine generator configured to generate at least one finite state machine to represent the at least one query pattern, the at least one finite state machine including a plurality of states connected by edges having predicate conditions to be evaluated against events of the stream of events.

3. The system of claim 1, wherein the query pattern handler comprises a runtime pattern generator configured to generate each runtime pattern of the plurality of runtime patterns, in response to a corresponding triggering event of the stream of events.

4. The system of claim 1, wherein the event scheduler comprises an event queue configured to store the current event set.

5. The system of claim 1 wherein the runtime pattern scheduler comprises a pattern list manager configured to maintain a pending list of the runtime patterns which are available for matching, and a running list which includes a subset of the pending list, including the ranked set, for provision to the pattern match evaluator therefrom.

6. The system of claim 1, wherein the runtime pattern scheduler comprises a priority manager configured to calculate the priority metric based on characteristics of the stream of events.

7. The system of claim 1, wherein the runtime pattern scheduler comprises a priority manager configured to calculate the priority metric based on a current state of each runtime pattern.

8. The system of claim 1, wherein the runtime patterns are expressed as finite state machines including a plurality of states connected by edges having predicate conditions to be evaluated against events of the stream of events, and wherein the runtime pattern scheduler comprises a priority manager configured to calculate the priority metric for each runtime pattern including an expectation of completion that is determined based on a length of each independent path through each state machine and a probability of completion of each path, including a conditional probability of the completion of each path considering individual predicate conditions of each path.

9. The system of claim 1, wherein the runtime patterns are expressed as finite state machines including a plurality of states connected by edges having predicate conditions to be evaluated against events of the stream of events, and wherein the runtime pattern scheduler comprises a priority manager configured to calculate the priority metric for each runtime pattern including a cost of completion that is determined based on a length of each independent path through each state machine.

10. The system of claim 1, wherein the runtime pattern scheduler comprises a priority manager configured to calculate the priority metric based on an expectation of completion of the runtime pattern relative to a cost of completion of the runtime pattern.

11. The system of claim 10, wherein the priority manager is configured to use a dummy runtime pattern during a design time to estimate and store the expectation and cost for each state of a runtime pattern, and configured to compare a current event distribution and current state of the runtime pattern during runtime to retrieve a corresponding expectation and cost.

12. The system of claim 1, wherein the runtime patterns are expressed as finite state machines which include a plurality of states connected by edges having predicate conditions, and wherein the pattern match evaluator is configured to evaluate each runtime pattern by comparing events of the current event set against each runtime pattern of the ranked set to determine whether each event of the current event set satisfies a current predicate condition thereof.

13. The system of claim 1 wherein the pattern match evaluator is configured to output all matched and completed runtime patterns of the ranked set as matched patterns, and further configured to return any remaining runtime patterns of the ranked set to the run-time pattern scheduler.

14. The system of claim 13, wherein the run-time pattern scheduler is configured to receive the remaining runtime patterns for combination with any newly-available runtime patterns, and configured to re-determine the priority metric for each runtime pattern of the combination to determine an updated ranked set to be evaluated against an updated event set.

15. A computer-implemented method for executing instructions stored on a computer readable storage medium, the method comprising:

determining at least one query pattern to be matched against a stream of events;

receiving an event of the stream of events, the event associated with a current event set of the stream of events;

determining a plurality of run-time patterns representing active instances of the at least one query pattern which are currently available for matching, and which each include a plurality of states;

determining a ranked set of the run-time patterns based on a priority metric which characterizes, for each run-time pattern, an advancement of each run-time pattern from a current state thereof when matched against the current event set; and

evaluating each run-time pattern of the ranked set, in turn, against the current event set.

16. The method of claim 15, wherein determining the plurality of run-time patterns comprises generating a corresponding plurality of finite state machines to represent each runtime pattern, each finite state machine including a plurality of states connected by edges having predicate conditions to be evaluated against events of the stream of events.

17. The method of claim 15 wherein the evaluating comprises:

outputting all matched and completed runtime patterns of the ranked set as matched patterns; and

returning any remaining runtime patterns of the ranked set for combination with any newly-available runtime patterns.

18. The method of claim 15, comprising:

re-determining the priority metric for each runtime pattern of the combination to determine an updated ranked set to be evaluated against an updated event set.

19. A computer program product, the computer program product being tangibly embodied on a computer-readable storage medium and comprising instructions that, when executed, are configured to:

determine at least one query pattern to be matched against a stream of events;

receive an event of the stream of events, the event associated with a current event set of the stream of events;

determine a plurality of run-time patterns representing active instances of the at least one query pattern which are currently available for matching, and which each include a plurality of states;

determine a ranked set of the run-time patterns based on a priority metric which characterizes, for each run-time pattern, an advancement of each run-time pattern from a current state thereof when matched against the current event set; and

evaluate each run-time pattern of the ranked set, in turn, against the current event set.

20. The computer program product of claim 19, wherein the instructions, when executed, are further configured to:

output all matched and completed runtime patterns of the ranked set as matched patterns;

return any remaining runtime patterns of the ranked set for combination with any newly-available runtime patterns; and

re-determine the priority metric for each runtime pattern of the combination to determine an updated ranked set to be evaluated against an updated event set.