ASYNCHRONOUS TRANSFER OF STATE INFORMATION BETWEEN CONTINUOUS QUERY PLANS

• US 20120166417A1
• Filed: 12/23/2010
• Published: 06/28/2012
• Est. Priority Date: 12/23/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chandramouli, Badrish, Goldstein, Jonathan David, Zabback, Peter Alfred, Maier, David Eugene, Wang, Di
• Granted Patent: US 8,478,743 B2
• Time in Patent Office: Days
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

Described herein are technologies pertaining to migrating state information of operators in a first continuous query plan to a second continuous query plan in an asynchronous manner, such that the first continuous query plan need not cease executing during the migrating of the state information. State information pertaining to stateful operators, such as join operators, is migrated from the first continuous query plan to the second continuous query plan by way of a transformation plan. State matching is utilized to generate the transformation plan.

Claims

1. A method, comprising:

receiving a first continuous query plan, wherein a continuous query plan is a logical representation of a query, wherein the first continuous query plan comprises a first plurality of operators that are configured to continuously perform processing operations on temporal event streams with revisions;

receiving a second continuous query plan, wherein the second continuous query plan comprises a second plurality of operators that are configured to continuously perform processing operations on the temporal events; and

using a processor to automatically migrate, in an asynchronous manner, state information of at least one operator in the first plurality of operators to the second continuous query plan.

2. The method of claim 1, wherein the processing operations in the first continuous query plan and the second continuous query plan comprise a join operation.

3. The method of claim 1, wherein the first continuous query plan and the second continuous query plan are structurally and logically equivalent continuous query plans.

4. The method of claim 1, wherein the first continuous query plan and the second continuous query plan are logically equivalent but structurally non-identical continuous query plans.

5. The method of claim 1, wherein automatically migrating in the asynchronous manner comprises migrating states of operators in the first continuous query plan to the second continuous query plan incrementally.

6. The method of claim 1, wherein the first continuous query plan is executed over the temporal events without interruption while the state information is migrated from the at least one operator in the first plurality of operators to the second continuous query plan.

7. The method of claim 1, wherein the first continuous query plan comprises a stateful operator, and further comprising preparing the first continuous query plan for migrating state information, wherein preparing the first continuous query plan for migrating state information comprises inserting a multicast operator immediately beneath the stateful operator in the first continuous query plan.

8. The method of claim 7, wherein preparing the first continuous query plan for migrating the state information further comprises adding at least one additional output stream to the stateful operator.

9. The method of claim 1, wherein the second continuous query plan comprises a stateful operator, and further comprising preparing the second continuous query for receiving state information from the at least one operator in the first continuous query plan, wherein preparing the second continuous query for receiving the state information comprises inserting a union operator immediately beneath the stateful operator in the second continuous query plan, wherein the union operator is configured to receive state information pertaining to the at least one operator in the first continuous query plan.

10. The method of claim 1, wherein the act of automatically migrating comprises transferring state information of the at least one operator in the first continuous query plan to the second continuous query plan by way of a transformation plan.

11. The method of claim 1, further comprising, subsequent to the automatic migrating, terminating the first continuous query plan while continuing execution of the second continuous query plan.

12. The method of claim 1, further comprising, subsequent to the automatic migrating, simultaneously executing both the first continuous query plan and the second continuous query plan.

13. The method of claim 1, wherein the first plurality of operators execute across a plurality of computing devices.

18. The system of claim 13, wherein the migrator component comprises a preparer component that prepares the first continuous query plan and the second continuous query plan for asynchronous migration of state information by adding a first operator to the first continuous query plan and adding a second operator to the second continuous query plan.

19. The system of claim 13, wherein at least one operator in the plurality of operators is a join operator that concatenates events from two input streams based at least in part upon windows of the events overlapping.

14. A system comprising a plurality of components that are executable by a processor, the components comprising:

a receiver component that receives a first continuous query plan and a second continuous query plan, wherein the first continuous query plan and the second continuous query plan are configured to execute continuously over a data stream that comprises temporal events, wherein outputs of the first continuous query plan and the second continuous query plan are logically equivalent, and wherein the first continuous query plan comprises a first plurality of operators that perform processing operations on events in the data stream and the second continuous query plan comprises a second plurality of operators that are configured to perform processing operations on events in the data stream; and

a migrator component that causes state information corresponding to the plurality of operators in the first continuous query plan to be asynchronously migrated to the second continuous query plan.

15. The system of claim 14, wherein the first continuous query plan and the second continuous query plan are structurally equivalent.

16. The system of claim 14, wherein the migrator component causes an event to be received by an operator in the first continuous query plan, wherein the operator initiates migration of state information corresponding to the operator to the second continuous query plan responsive to receipt of the event.

17. The system of claim 14, wherein the migrator component causes the state information corresponding to the plurality of operators in the first continuous query plan to be asynchronously migrated to the second continuous query plan by way of a transformation plan, wherein the transformation plan comprises a set of operations that are constructed by utilizing signature information computed and associated with operators and/or synopses in the first continuous query plan and the second continuous query plan.

20. A non-transitory computer-readable medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

receiving an input data stream, wherein the input data stream comprises a plurality of temporal events;

executing a first continuous query plan over the input data stream to generate an output data stream, wherein the first continuous query plan comprises a plurality of operators that perform processing operations on events in the input data stream, wherein at least one operator in the plurality of operators is a stateful operator; and

causing a migrator event to be received by the at least one stateful operator, wherein responsive to receiving the migrator event the at least one stateful operator commences migrating state information corresponding thereto to a second continuous query plan, wherein the first continuous query plan continues to produce the output stream while the at least one stateful operator migrates the state information corresponding thereto to the second continuous query plan.