Method to create a partition-by time/tuple-based window in an event processing service

• US 7,945,540 B2
• Filed: 10/04/2007
• Issued: 05/17/2011
• Est. Priority Date: 05/04/2007
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Mishra, Shailendra, Park, Hoyong, Jain, Namit, Srinivasan, Anand
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US11/867,471
• Publication Number:
  US 20080275891A1
• Time in Patent Office: 1,321 Days
• Field of Search: 707/1, 707/6, 707/8, 707/100, 707/104.1, 707/200, 707/201, 707/202, 707/205, 707/206, 707/609, 707/610, 707/618, 707/625, 707/654, 707/669, 707/681, 707/689, 707/692, 707/693, 707/812, 707/813, 707/821, 707662-664, 707/769, 707/999.006, 707/999.007, 707/999.201, 705/1, 705/10, 705/22, 705/23, 705/24, 705/1.1
• US Class Current: 707/692
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries

Abstract

A method to create a partition by time/tuple based window in an event processing service is provided. When continuous data streams are received, tuples are stored in a data structure with partitions based upon partition keys. Only a specified amount of tuples may be stored in each partition. When a partition exceeds the specified number of tuples, the oldest tuples are removed from the data structure. Tuples stored beyond a specified time period are also removed from the data structure. Two data structures may also be used to implement a time/tuple based window. Tuples are stored in both a data structure with a partition by window and a data structure with a range window. Tuples are removed in the partition by window when tuples exceed the amount in the partition. Tuples are removed in the range window when tuples exceed a specified time period. The two data structures are synchronized.

Claims

1. A method comprising the steps of:

receiving one or more continuous data streams that comprise a plurality of tuples of data, wherein each tuple, within the plurality of tuples of data, is associated with a particular time, wherein the particular time is no earlier than the time of any previously generated tuple in the plurality of tuples received;

retaining in partitions of a data structure the plurality of tuples that fall within a sliding time-based window, wherein the sliding time-based window is bounded by (a) a specified relative range of time and (b) a maximum number of tuples to retain;

wherein retaining in partitions of a data structure the plurality of tuples that fall within a sliding time-based window comprises;

in response to receiving a tuple from the one or more continuous data streams, performing;

(a) removing, from each particular partition of said partitions of said data structure, tuples that exceed a specified amount of tuples to be stored in each particular partition, wherein the partitions in the data structure are based upon one or more partition keys;

(b) removing, from each particular partition of said partitions of said data structure, tuples that are associated with a particular time that is not within the specified relative range of time; and

(c) storing, in a particular partition among the partitions of the data structure, the tuple; and

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the particular time for a tuple is based on the time that the tuple is received.

3. The method of claim 1, wherein the particular time for a tuple is based on an order in which the tuple is received.

4. The method of claim 1, wherein storing the tuple in the particular partition among partitions of the data structure is performed using a hash index.

5. The method of claim 1, further comprising:

registering a query based upon CQL; and

in response to receiving a tuple from the one or more continuous data streams, evaluating the query with the tuple.

6. A method comprising the steps of:

receiving one or more continuous data streams that comprise a plurality of tuples of data, wherein each tuple, within the plurality of tuples of data, is associated with a particular time, wherein the particular time is no less than the time of any previously generated tuple in the plurality of tuples received;

retaining in a data structure the plurality of tuples that fall within a sliding time-based window, wherein the sliding time-based window is bounded by (a) a specified relative range of time and (b) a maximum number of tuples to retain, wherein the data structure comprises a first data structure and a second data structure;

wherein retaining in a data structure the plurality of tuples that fall within a sliding time-based window comprises;

in response to receiving a tuple from the one or more continuous data streams, performing the steps of;

(a) removing, from each particular partition of a first data structure, tuples that exceed a specified amount of tuples to be stored in each particular partition;

(b) removing, from a second data structure, tuples that are associated with a particular time that is not within a range of time;

(c) storing, the tuple, in the first data structure and the second data structure,

wherein tuples stored in the first data structure are stored in a particular partition among partitions based upon one or more partition keys, and

wherein tuples stored in the second data structure are sorted by the particular time of the tuples; and

(d) synchronizing tuples stored in the first data structure with tuples stored in the second data structure; and

wherein the method is performed by one or more computing devices.

7. The method of claim 6, wherein the first data structure is a partition-by data structure.

8. The method of claim 6, wherein the second data structure is a time-based data structure.

9. The method of claim 6, wherein the particular time for a tuple is based on the time that the tuple is received.

10. The method of claim 6, wherein the particular time for a tuple is based in an order in which the tuple is received.

11. The method of claim 6, further comprising:

registering a query based upon CQL; and

upon receiving a tuple from the one or more continuous data streams, evaluating the query with the tuple.

12. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform:

receiving one or more continuous data streams that comprise a plurality of tuples of data, wherein each tuple, within the plurality of tuples of data, is associated with a particular time, wherein the particular time is no earlier than the time of any previously generated tuple in the plurality of tuples received;

retaining in partitions of a data structure the plurality of tuples that fall within a sliding time-based window, wherein the sliding time-based window is bounded by (a) a specified relative range of time and (b) a maximum number of tuples to retain; and

wherein retaining in partitions of a data structure the plurality of tuples that fall within a sliding time-based window comprises;

in response to receiving a tuple from the one or more continuous data streams, performing;

(a) removing, from each particular partition of said partitions of said data structure, tuples that exceed a specified amount of tuples to be stored in each particular partition, wherein the partitions in the data structure are based upon one or more partition keys;

(b) removing, from each particular partition of said partitions of said data structure, tuples that are associated with a particular time that is not within the specified relative range of time; and

(c) storing, in a particular partition among the partitions of the data structure, the tuple.

13. The computer-readable storage medium of claim 12, wherein the particular time for a tuple is based on the time that the tuple is received.

14. The computer-readable storage medium of claim 12, wherein the particular time for a tuple is based on an order in which the tuple is received.

15. The computer-readable storage medium of claim 12, wherein storing the tuple in the particular partition among partitions of the data structure is performed using a hash index.

16. The computer-readable storage medium of claim 12, further comprising:

registering a query based upon CQL; and

in response to receiving a tuple from the one or more continuous data streams, evaluating the query with the tuple.

17. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to:

receiving one or more continuous data streams that comprise a plurality of tuples of data, wherein each tuple, within the plurality of tuples of data, is associated with a particular time, wherein the particular time is no less than the time of any previously generated tuple in the plurality of tuples received;

retaining in a data structure the plurality of tuples that fall within a sliding time-based window, wherein the sliding time-based window is bounded by (a) a specified relative range of time and (b) a maximum number of tuples to retain, wherein the data structure comprises a first data structure and a second data structure; and

wherein retaining in a data structure the plurality of tuples that fall within a sliding time-based window comprises;

in response to receiving a tuple from the one or more continuous data streams, performing the steps of;

(a) removing, from each particular partition of a first data structure, tuples that exceed a specified amount of tuples to be stored in each particular partition;

(b) removing, from a second data structure, tuples that are associated with a particular time that is not within a range of time;

(c) storing, the tuple, in the first data structure and the second data structure,

wherein tuples stored in the first data structure are stored in a particular partition among partitions based upon one or more partition keys, and

wherein tuples stored in the second data structure are sorted by the particular time of the tuples; and

(d) synchronizing tuples stored in the first data structure with tuples stored in the second data structure.

18. The computer-readable storage medium of claim 17, wherein the first data structure is a partition-by data structure.

19. The computer-readable storage medium of claim 17, wherein the second data structure is a time-based data structure.

20. The computer-readable storage medium of claim 17, wherein the particular time for a tuple is based on the time that the tuple is received.

21. The computer-readable storage medium of claim 17, wherein the particular time for a tuple is based in an order in which the tuple is received.

22. The computer-readable storage medium of claim 17, further comprising:

registering a query based upon CQL; and

upon receiving a tuple from the one or more continuous data streams, evaluating the query with the tuple.