MULTI-STATE QUERY MIGRATION IN DATA STREAM MANAGEMENT

• US 20130117317A1
• Filed: 11/03/2011
• Published: 05/09/2013
• Est. Priority Date: 11/03/2011
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Wolf, Bernhard
• Granted Patent: US 8,635,208 B2
• Time in Patent Office: Days
• US Class Current: 707/792
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A request handler may determine a query of a data stream management system (DSMS), wherein the query includes a plurality of operators being configured to execute the query collaboratively within the DSMS, and wherein stored stream-related data includes operator-associated windows of state data from the stream data, the request handler being further configured to determine a new query having new windows corresponding to the windows of the original query. A windows sorter may sort the new windows from longest duration to shortest duration to obtain a sorted new windows list. A migration estimator may calculate individual migration times for migrating state data from each window to its corresponding new window, beginning with the longest new window of the sorted new windows list. A migration aggregator may aggregate the individual migration times to obtain a total migration time for the new query.

Claims

1. A system including instructions recorded on a computer-readable medium and executable by at least one processor, the system comprising:

a request handler configured to

determine a query of a data stream management system (DSMS), the query currently being executed using stored stream data within a buffer associated with the query, the stored stream data being received from at least one data source and being removed from the buffer in association with new stream data being received, wherein the stored stream data includes at least one original window of state data from the stream data; and

determine a new query having at least one new window corresponding to the at least one original window of the query; and

a migration estimator configured to;

calculate at least one migration time for migrating state data from the at least one original window to the at least one new window; and

calculate an increase over the at least one migration time based on also accumulating newly arriving data.

2. The system of claim 1, wherein the original and new windows are expressed as durations in units of time.

3. The system of claim 2, wherein:

the original and new windows are initially received as being expressed in terms of a number of tuples of the stream data, and

the system further comprises a converter configured to convert the original windows for expression thereof as durations in units of time.

4. The system of claim 1, wherein the original and new windows are expressed in terms of a number of tuples of the stream data.

5. The system of claim 4, wherein the original and new windows are initially received as being expressed as durations in units of time, and wherein the migration estimator includes a converter configured to convert the original windows for expression thereof in terms of a number of tuples of the stream data.

6. The system of claim 1, further comprising the DSMS configured to process arriving events within the stream data and execute migration of state data from the at least one original window to its corresponding at least one new window between the processing of the arriving events.

7. The system of claim 6, wherein the processing of the arriving events is aperiodic.

8. The system of claim 6, wherein the migration estimator is configured to calculate an individual migration time for a corresponding state using an average measure of idle times to determine a number of state data values that can be transferred in each idle time.

9. The system of claim 6, wherein the at least one migration time for a state is a function of a number of corresponding state data values of the corresponding state to be transferred, and a function of a number of arriving events for the state which arrive during the processing.

10. The system of claim 1, further comprising the DSMS configured to process the stream data and to process the query during the migration of the at least new window of the new query.

11. The system of claim 1, wherein the at least one migration time for the at least one new window is a function of a size of the at least one new window.

12. The system of claim 11, wherein the migration estimator is configured to calculate the at least one migration time for a current state and corresponding at least one new window as an incremental increase over previously-calculated individual migration times, if any, for one or more earlier new windows.

13. The system of claim 12, wherein the migration estimator is configured to calculate the at least one migration time including calculating a reduced window size for the corresponding at least one new window, for purposes of determining that a reduced window size for the current state and corresponding at least one new window size is zero, so that the corresponding at least one migration time is also zero.

14. The system of claim 12, wherein the migration estimator is configured to aggregate the incremental increase over the previously-calculated individual migration times to obtain a total migration time.

24. The system of claim 1, wherein:

the at least one original window includes at least two original windows;

the at least one new window includes at least two new window;

the system further comprises a windows sorter configured to sort the at least two new windows from longest duration to shortest duration to obtain a sorted new windows list; and

the migration estimator is configured to calculate at least two migration times for migrating state data from the at least two original windows to the at least two new windows, beginning with a longest new window from the sorted at least two windows.

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

determining a query of a data stream management system (DSMS), the query currently being executed using stored stream-related data within a buffer associated with the query, the stored stream-related data being obtained from stream data received from at least one data source and being removed from the buffer in association with new stream data being received, wherein the stored stream-related data includes at least one original window of state data from the stream data;

determining a new query having at least one new window corresponding to the at least one original window of the query;

calculating at least one migration time for migrating state data from the at least one original window to the at least one new window; and

calculating an increase over the at least one migration time based on also accumulating newly arriving data.

16. The method of claim 15, further comprising processing arriving events within the stream data using a DSMS, and migrating state data from the at least one original window to its corresponding at least one new window between the processing of the arriving events.

17. The method of claim 15, wherein the at least one migration time for a current state and corresponding at least one new window is calculated as an incremental increase over previously-calculated individual migration times.

18. The method of claim 17, wherein the at least one migration time is calculated including calculating a reduced window size for the corresponding at least one new window and determining that the reduced window size for the current state and corresponding new window is zero, so that the corresponding at least one migration time is also zero.

19. A non-transitory computer program product comprising instructions that, when executed, are configured to cause a data processing apparatus to:

determine a query of a data stream management system, the query currently being executed using stored stream-related data within a buffer associated with the query, the stored stream-related data being obtained from stream data received from at least one data source and being removed from the buffer in association with new stream data being received, wherein the stored stream data includes at least one original window of state data from the stream data;

determine a new query having at least one new window corresponding to the at least one original window of the query;

calculate at least one individual migration time for migrating state data from the at least one original window to the at least one new window; and

calculate an increase over the at least one migration time based on also accumulating newly arriving data.

22. The non-transitory computer program product of claim 19, wherein the instructions, when executed, are further configured to cause the data processing apparatus to:

calculate the at least one migration time including calculating a reduced window size for the at least one new window; and

determine that the reduced window size for the current state and at least one new window size is zero, so that the corresponding at least one migration time is also zero.

23. The non-transitory computer program product of claim 19, wherein the calculating the increase over the at least one migration time includes calculating the increase over the at least one migration time based on also accumulating newly arriving data.

20. (canceled)

21. (canceled)