Evaluating event-generated data using append-only tables

• US 7,840,575 B2
• Filed: 12/13/2006
• Issued: 11/23/2010
• Est. Priority Date: 05/19/2006
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chandrasekaran, Sashikanth
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Moser; Bruce M
• Application Number:
  US11/638,743
• Publication Number:
  US 20070271573A1
• Time in Patent Office: 1,441 Days
• Field of Search: 707/200, 707/999.2, 707/754, 707/821, 719/318
• US Class Current: 707/754
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

Techniques are provided for evaluating base events, compound events, and logical update events in an event processing system. In one embodiment, the base events, compound events, and logical update events are definitions in a particular syntax language that specify conditions for evaluating input event data. In this embodiment, base event definitions are evaluated over the input event data; logical update event definitions are evaluated by determining whether the effect of any earlier event is changed by the arrival of a new event; and compound event definitions are evaluated over records representing events that have been selected by evaluating the base event definitions over the input event data.

Claims

1. A method for evaluating events comprising:

creating a filter that specifies an array of constant values corresponding to one or more attributes that are associated with one or more events;

receiving and storing in memory a stream of records, wherein the stream of records is generated to represent a stream of events, and wherein each record of the stream of records includes a set of attributes that are associated with a particular event, of the stream of events, that is represented by said each record;

selecting a plurality of events from the stream of events by applying the filter to the stream of records in order to select a corresponding plurality of records, wherein applying the filter comprises performing one or more array operations to compare the array of constant values specified in the filter to attributes stored in the plurality of records; and

storing the plurality of records in an append-only sequence, wherein the append-only sequence is a storage representation of the plurality of events that allows only appending new records that represent new events but does not allow modifying and deleting existing records that represent already existing events;

wherein the method is performed by one or more computer systems.

2. The method of claim 1, further comprising defining a set of base events according to a particular syntax specification, wherein each base event specifies conditions for selecting one or more events from the stream of events based on one or more attributes included in one or more records, of the stream of records, that represent the one or more events.

3. The method of claim 2, wherein creating the filter further comprises compiling the set of base events to determine the array of constant values.

4. The method of claim 2, wherein applying the filter to the stream of records further comprises:

determining a candidate set of base events, from the set of base events, that need to be evaluated over the stream of records; and

determining the plurality of records from the stream of records by performing second one or more array operations to simultaneously evaluate the candidate set of base events over multiple records from the stream of records.

5. The method of claim 2, further comprising:

defining a logical update event based on at least two base events of the set of base events, wherein the logical update event indicates a first event of the plurality of events that changes the effect of a second event of the plurality of events, wherein the second event has occurred earlier than the first event;

recording a modification list for the logical update event, wherein the modification list identifies a pair of the first event and the second event; and

based at least in part on the modification list, evaluating the logical update event over multiple records of the plurality of records.

6. The method of claim 5, wherein:

the method further comprises;

determining, from the plurality of records, a first set of candidate records that represent the first event, wherein the first set of records includes a first record for which the logical update event is to be evaluated;

determining, from the plurality of records, a second set of candidate records that represent the second event; and

joining the first set of records to the second set of records to obtain a result set of records, wherein the latest occurring record in the result set is a second record that represents the second event; and

recording the modification list further comprises recording a pair of indices that identify the first record and the second record in the append-only sequence.

7. The method of claim 2, further comprising:

defining a set of compound events according to the particular syntax specification, wherein each compound event specifies correlation conditions between multiple base events of the set of base events; and

evaluating the set of compound events over the plurality of records.

8. The method of claim 7, wherein evaluating the set of compound events further comprises continuously evaluating the set of compound events over batches of records, of the plurality of records, as the batches of records are stored in the append-only sequence.

9. The method of claim 8, wherein continuously evaluating the set of compound events over the batches of records further comprises:

maintaining a sequence-marker that determines the point in the append-only sequence until which the set of compound events has been evaluated;

loading in memory as a batch of records only records that are stored in the append-only sequence after the sequence-marker; and

evaluating the set of compound events for the loaded batch of records.

10. The method of claim 7, wherein:

the method further comprises analyzing the correlation conditions specified in one or more compound events of the set of compound events to determine whether there exist any timestamp-based orderings among the multiple base events specified in the one or more compound events; and

evaluating the set of compound events further comprises evaluating the one or more compound events by computing the correlation conditions based on one or more timestamp-based orderings when the one or more timestamp-based orderings are determined to exist among the multiple base events.

11. The method of claim 2, further comprising:

defining a compound event according to the particular syntax specification, wherein the compound event specifies correlation conditions between multiple base events of the set of base events;

based on a particular event of the plurality of events and on the correlation conditions specified in the compound event, analyzing the compound event to determine an additional event, not among the plurality of events, that can be scheduled for future evaluation; and

scheduling an evaluation of the additional event at a future point in time, wherein the evaluation of the additional event comprises evaluating the compound event.

12. The method of claim 2, further comprising:

defining a compound event according to the particular syntax specification, wherein the compound event specifies correlation conditions between multiple base events of the set of base events;

defining a logical update event based on at least one base event of the multiple base events, wherein the logical update event when evaluated affects at least one evaluation of the compound event, wherein the logical update event indicates a first event of the plurality of events that changes the effect of a second event of the plurality of events; and

evaluating the compound event, wherein evaluating the compound event comprises;

determining first ranges of records, stored in the append-only sequence, for which the compound event evaluates to TRUE; and

determining second ranges of records, stored in the append-only sequence, for which the compound event evaluates to FALSE.

13. The method of claim 12, wherein:

the method further comprises;

maintaining the logical update event and the compound event in such order that the logical update event is always evaluated before the compound event is evaluated; and

marking, as a copy alias event, a single base event from the at least one base event defined in the logical update event; and

evaluating the compound event further comprises;

evaluating the compound event at one or more barrier points in the append-only sequence, wherein the one or more barrier points are those points in the append-only sequence at which a dependent event of the compound event has been recorded;

based on the one or more barrier points, determining first points in the append-only sequence at which the compound event is evaluated to TRUE;

determining a list of undo points in the append-only sequence, wherein the undo points are second points in the append-only sequence at which the compound event evaluates to FALSE, and wherein determining the list of undo points comprises evaluating the copy alias event after at least one of the one or more barrier points; and

determining the first ranges of records and the second ranges of records based on the first points and the second points determined in the append-only sequence.

14. A method for evaluating events comprising:

receiving a request to evaluate a compound event, wherein the compound event specifies correlation conditions between a set of base events, wherein the correlation conditions specify one or more join operations between the set of base events, wherein each base event in the set of base events specifies conditions for selecting one or more events that are included in a plurality of events that are stored in an append-only sequence;

retrieving a sequence of events from the append-only sequence, wherein each event in the sequence of events has been selected into the plurality of events and stored in the append-only sequence based on the conditions specified in one or more base events of the set of base events; and

evaluating the compound event, wherein evaluating the compound event comprises;

analyzing the correlation conditions that are specified in the compound event;

automatically splitting the sequence of events into two or more sub-sequences of events based on the analysis of the correlation conditions; and

processing the two or more sub-sequences of events in parallel;

wherein the method is performed by one or more computer systems.

15. The method of claim 14, wherein the append-only sequence is a storage representation of the plurality of events that allows only appending new records that represent new events but does not allow modifying and deleting existing records that represent already existing events.

16. The method of claim 14, wherein:

each event in the sequence of events is associated with a set of attributes;

the correlation conditions specified in the compound event indicate a group of attributes from the sets of attributes associated with the sequence of events;

analyzing the correlation conditions further comprises determining a maximal partitioning key for the compound event, wherein the maximal partitioning key includes one or more attributes from the group of attributes indicated in the correlation conditions; and

automatically splitting the sequence of events further comprises determining the two or more sub-sequences of events based on unique values of the one or more attributes included in the maximal partitioning key.

17. A machine-readable volatile or non-volatile medium storing one or more sequences of instructions comprising instructions which, when executed by one or more processors, cause the one or more processors to perform:

creating a filter that specifies an array of constant values corresponding to one or more attributes that are associated with one or more events;

receiving and storing in memory a stream of records, wherein the stream of records is generated to represent a stream of events, and wherein each record of the stream of records includes a set of attributes that are associated with a particular event, of the stream of events, that is represented by said each record;

selecting a plurality of events from the stream of events by applying the filter to the stream of records in order to select a corresponding plurality of records, wherein applying the filter comprises performing one or more array operations to compare the array of constant values specified in the filter to attributes stored in the plurality of records; and

storing the plurality of records in an append-only sequence, wherein the append-only sequence is a storage representation of the plurality of events that allows only appending new records that represent new events but does not allow modifying and deleting existing records that represent already existing events.

18. The machine-readable volatile or non-volatile medium of claim 17, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform defining a set of base events according to a particular syntax specification, wherein each base event specifies conditions for selecting one or more events from the stream of events based on one or more attributes included in one or more records, of the stream of records, that represent the one or more events.

19. The machine-readable volatile or non-volatile medium of claim 18, wherein the instructions that cause creating the filter further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform compiling the set of base events to determine the array of constant values.

20. The machine-readable volatile or non-volatile medium of claim 18, wherein the instructions that cause applying the filter to the stream of records further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:

determining a candidate set of base events, from the set of base events, that need to be evaluated over the stream of records; and

determining the plurality of records from the stream of records by performing second one or more array operations to simultaneously evaluate the candidate set of base events over multiple records from the stream of records.

21. The machine-readable volatile or non-volatile medium of claim 18, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:

defining a logical update event based on at least two base events of the set of base events, wherein the logical update event indicates a first event of the plurality of events that changes the effect of a second event of the plurality of events, wherein the second event has occurred earlier than the first event;

recording a modification list for the logical update event, wherein the modification list identifies a pair of the first event and the second event; and

based at least in part on the modification list, evaluating the logical update event over multiple records of the plurality of records.

22. The machine-readable volatile or non-volatile medium of claim 21, wherein:

the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform;

determining, from the plurality of records, a first set of candidate records that represent the first event, wherein the first set of records includes a first record for which the logical update event is to be evaluated;

determining, from the plurality of records, a second set of candidate records that represent the second event; and

joining the first set of records to the second set of records to obtain a result set of records, wherein the latest occurring record in the result set is a second record that represents the second event; and

the instructions that cause recording the modification list further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform recording a pair of indices that identify the first record and the second record in the append-only sequence.

23. The machine-readable volatile or non-volatile medium of claim 18, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:

defining a set of compound events according to the particular syntax specification, wherein each compound event specifies correlation conditions between multiple base events of the set of base events; and

evaluating the set of compound events over the plurality of records.

24. The machine-readable volatile or non-volatile medium of claim 23, wherein the instructions that cause evaluating the set of compound events further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform continuously evaluating the set of compound events over batches of records, of the plurality of records, as the batches of records are stored in the append-only sequence.

25. The machine-readable volatile or non-volatile medium of claim 24, wherein the instructions that cause continuously evaluating the set of compound events over the batches of records further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:

maintaining a sequence-marker that determines the point in the append-only sequence until which the set of compound events has been evaluated;

loading in memory as a batch of records only records that are stored in the append-only sequence after the sequence-marker; and

evaluating the set of compound events for the loaded batch of records.

26. The machine-readable volatile or non-volatile medium of claim 23, wherein:

the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform analyzing the correlation conditions specified in one or more compound events of the set of compound events to determine whether there exist any timestamp-based orderings among the multiple base events specified in the one or more compound events; and

the instructions that cause evaluating the set of compound events further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform evaluating the one or more compound events by computing the correlation conditions based on one or more timestamp-based orderings when the one or more timestamp-based orderings are determined to exist among the multiple base events.

27. The machine-readable volatile or non-volatile medium of claim 18, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:

defining a compound event according to the particular syntax specification, wherein the compound event specifies correlation conditions between multiple base events of the set of base events;

based on a particular event of the plurality of events and on the correlation conditions specified in the compound event, analyzing the compound event to determine an additional event, not among the plurality of events, that can be scheduled for future evaluation; and

scheduling an evaluation of the additional event at a future point in time, wherein the evaluation of the additional event comprises evaluating the compound event.

28. The machine-readable volatile or non-volatile medium of claim 18, wherein the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform:

defining a compound event according to the particular syntax specification, wherein the compound event specifies correlation conditions between multiple base events of the set of base events;

defining a logical update event based on at least one base event of the multiple base events, wherein the logical update event when evaluated affects at least one evaluation of the compound event, wherein the logical update event indicates a first event of the plurality of events that changes the effect of a second event of the plurality of events; and

evaluating the compound event, wherein evaluating the compound event comprises;

determining first ranges of records, stored in the append-only sequence, for which the compound event evaluates to TRUE; and

determining second ranges of records, stored in the append-only sequence, for which the compound event evaluates to FALSE.

29. The machine-readable volatile or non-volatile medium of claim 18, wherein:

the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform;

maintaining the logical update event and the compound event in such order that the logical update event is always evaluated before the compound event is evaluated; and

marking, as a copy alias event, a single base event from the at least one base event defined in the logical update event; and

the instructions that cause evaluating the compound event further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform;

evaluating the compound event at one or more barrier points in the append-only sequence, wherein the one or more barrier points are those points in the append-only sequence at which a dependent event of the compound event has been recorded;

based on the one or more barrier points, determining first points in the append-only sequence at which the compound event is evaluated to TRUE;

determining a list of undo points in the append-only sequence, wherein the undo points are second points in the append-only sequence at which the compound event evaluates to FALSE, and wherein determining the list of undo points comprises evaluating the copy alias event after at least one of the one or more barrier points; and

determining the first ranges of records and the second ranges of records based on the first points and the second points determined in the append-only sequence.

30. A machine-readable volatile or non-volatile medium storing one or more sequences of instructions comprising instructions which, when executed by one or more processors, cause the one or more processors to perform:

receiving a request to evaluate a compound event, wherein the compound event specifies correlation conditions between a set of base events, wherein the correlation conditions specify one or more join operations between the set of base events, wherein each base event in the set of base events specifies conditions for selecting one or more events that are included in a plurality of events that are stored in an append-only sequence;

retrieving a sequence of events from the append-only sequence, wherein each event in the sequence of events has been selected into the plurality of events and stored in the append-only sequence based on the conditions specified in one or more base events of the set of base events; and

evaluating the compound event, wherein evaluating the compound event comprises;

analyzing the correlation conditions that are specified in the compound event;

automatically splitting the sequence of events into two or more sub-sequences of events based on the analysis of the correlation conditions; and

processing the two or more sub-sequences of events in parallel.

31. The machine-readable volatile or non-volatile medium of claim 30, wherein the append-only sequence is a storage representation of the plurality of events that allows only appending new records that represent new events but does not allow modifying and deleting existing records that represent already existing events.

32. The machine-readable volatile or non-volatile medium of claim 30, wherein:

each event in the sequence of events is associated with a set of attributes;

the correlation conditions specified in the compound event indicate a group of attributes from the sets of attributes associated with the sequence of events;

the instructions that cause analyzing the correlation conditions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform determining a maximal partitioning key for the compound event, wherein the maximal partitioning key includes one or more attributes from the group of attributes indicated in the correlation conditions; and

the instructions that cause automatically splitting the sequence of events further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform determining the two or more sub-sequences of events based on unique values of the one or more attributes included in the maximal partitioning key.