Evaluating event-generated data using append-only tables

• US 8,762,395 B2
• Filed: 10/27/2010
• Issued: 06/24/2014
• 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): Mofiz, Apu
• Assistant Examiner(s): NGUYEN, THU N
• Application Number:
  US12/913,739
• Publication Number:
  US 20120109985A1
• Time in Patent Office: 1,336 Days
• Field of Search: None
• US Class Current: 707/754
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

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 an N-way join of multiple sets of records, the method comprising:

analyzing a plurality of correlation conditions that are defined in the N-way join, wherein the plurality of correlation conditions indicate a group of attributes from the multiple sets of records;

based on the analysis of the plurality of correlation conditions, determining a maximal partitioning key for the N-way join, wherein the maximal partitioning key includes one or more attributes from the group of attributes indicated in the plurality of correlation conditions;

automatically splitting the multiple sets of records into two or more sub-sequences of records based on unique values in the one or more attributes, of the maximal partitioning key, that are included in the records of the multiple sets of records; and

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

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

2. The method of claim 1, further comprising ordering all the records of the multiple sets of records in a sequence prior to automatically splitting the multiple sets of records.

3. The method of claim 2, wherein ordering all the records of the multiple sets of records in the sequence comprises generating an index of ascending or descending values to identify each record in the sequence.

4. The method of claim 1, wherein automatically splitting the multiple sets of records into the two or more sub-sequences of records further comprises storing values from the one or more attributes of the maximal partitioning key into each sub-sequence of the two or more sub-sequences in order to identify all records that are included in said each sub-sequence.

5. The method of claim 1, wherein automatically splitting the multiple sets of records into the two or more sub-sequences of records comprises:

automatically splitting the multiple sets of records into two or more first-level sub-sequences of records based on unique values corresponding to a first set of attributes from the one or more attributes of the maximal partitioning key; and

automatically splitting at least one of the two or more first-level sub-sequences of records into two or more second-level sub-sequences of records based on unique values corresponding to a second set of attributes from the one or more attributes of the maximal partitioning key.

6. The method of claim 1, wherein processing the two or more sub-sequences of records in parallel further comprises evaluating one or more correlation conditions of the plurality of correlation conditions separately for each sub-sequence of the two or more sub-sequences.

7. The method of claim 1, wherein the plurality of correlation conditions includes one or more equi-join conditions.

8. The method of claim 1, wherein the multiple sets of records include N sets of records.

9. The method of claim 1, further comprising retrieving at least one of the multiple sets of records from an append-only sequence, wherein the append-only sequence is a storage representation that allows only appending new records but does not allow modifying and deleting existing records.

10. The method of claim 9, wherein the append-only sequence is implemented as one or more tables, and wherein said at least one of the multiple sets of records is stored as rows in the one or more tables.

11. A non-transitory machine-readable storage medium storing one or more sequences of instructions for evaluating an N-way join of multiple sets of records wherein, when executed by one or more processors, the one or more sequences of instructions cause the one or more processors to perform steps comprising:

analyzing a plurality of correlation conditions that are defined in the N-way join, wherein the plurality of correlation conditions indicate a group of attributes from the multiple sets of records;

based on the analysis of the plurality of correlation conditions, determining a maximal partitioning key for the N-way join, wherein the maximal partitioning key includes one or more attributes from the group of attributes indicated in the plurality of correlation conditions;

automatically splitting the multiple sets of records into two or more sub-sequences of records based on unique values in the one or more attributes, of the maximal partitioning key, that are included in the records of the multiple sets of records; and

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

12. The machine-readable storage medium of claim 11, 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 the step of ordering all the records of the multiple sets of records in a sequence prior to automatically splitting the multiple sets of records.

13. The machine-readable storage medium of claim 12, wherein the instructions that cause ordering all the records of the multiple sets of records in the sequence comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of generating an index of ascending or descending values to identify each record in the sequence.

14. The machine-readable storage medium of claim 11, wherein the instructions that cause automatically splitting the multiple sets of records into the two or more sub-sequences of records further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of storing values from the one or more attributes of the maximal partitioning key into each sub-sequence of the two or more sub-sequences in order to identify all records that are included in said each sub-sequence.

15. The machine-readable storage medium of claim 11, wherein the instructions that cause automatically splitting the multiple sets of records into the two or more sub-sequences of records comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of:

automatically splitting the multiple sets of records into two or more first-level sub-sequences of records based on unique values corresponding to a first set of attributes from the one or more attributes of the maximal partitioning key; and

automatically splitting at least one of the two or more first-level sub-sequences of records into two or more second-level sub-sequences of records based on unique values corresponding to a second set of attributes from the one or more attributes of the maximal partitioning key.

16. The machine-readable storage medium of claim 11, wherein the instructions that cause processing the two or more sub-sequences of records in parallel further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of evaluating one or more correlation conditions of the plurality of correlation conditions separately for each sub-sequence of the two or more sub-sequences.

17. The machine-readable storage medium of claim 11, wherein the plurality of correlation conditions includes one or more equi-join conditions.

18. The machine-readable storage medium of claim 11, wherein the multiple sets of records include N sets of records.

19. The machine-readable storage medium of claim 11, 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 the step of retrieving at least one of the multiple sets of records from an append-only sequence, wherein the append-only sequence is a storage representation that allows only appending new records but does not allow modifying and deleting existing records.

20. The machine-readable storage medium of claim 19, wherein the append-only sequence is implemented as one or more tables, and wherein said at least one of the multiple sets of records is stored as rows in the one or more tables.