EFFICIENT LOGICAL MERGING OVER PHYSICALLY DIVERGENT STREAMS

• US 20120324453A1
• Filed: 06/17/2011
• Published: 12/20/2012
• Est. Priority Date: 06/17/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chandramouli, Badrish, Maier, David E., Goldstein, Jonathan D., Zabback, Peter A.
• Granted Patent: US 9,965,520 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements

Abstract

A logical merge module is described herein for producing an output stream which is logically compatible with two or more physically divergent input streams. Representative applications of the logical merge module are also set forth herein.

Claims

1. A method, implemented by physical and tangible computing functionality, for merging streams of data, comprising:

receiving plural physically divergent input streams from respective sources; and

using a logical merge module to produce an output stream which is logically compatible with each of the input streams.

2. The method of claim 1, wherein a data stream management system performs said receiving and said using to implement a continuous query.

3. The method of claim 2, wherein the logical merge module represents an operator that is combinable with one or more other operators.

4. The method of claim 1, further comprising:

analyzing the input streams to determine one or more constraints associated with the input streams;

selecting a case associated with said one or more constraints; and

invoking, based on the case, a particular algorithm to produce the output stream, using the logical merge module.

5. The method of claim 1, further comprising, for each element in each input stream:

assessing a type of the element;

determining an output action to take in response to the element, the output action selected from among;

providing no contribution to the output stream;

providing new output information to the output stream;

adjusting previous output information in the output stream; and

providing progress marker information to the output stream; and

adjusting a state associated with the logical merge module.

6. The method of claim 5, wherein the logical merge module applies an algorithm, selected from among a plurality of algorithms, for performing said determining and said adjusting, wherein the algorithms are associated with varying respective levels of constraints associated with the plurality of input streams.

7. The method of claim 5, wherein the logical merge module applies a policy, selected from among a plurality of possible policies, for performing said determining and adjusting.

8. The method of claim 1, wherein the input streams originate from plural respective units, wherein the units implement a same continuous query.

9. The method of claim 8, wherein the plural respective units execute the continuous query using different respective query plans.

10. The method of claim 8, further comprising sending feedback information to at least one of the plural units to enable said at least one of the plural units to advance its operation.

11. The method of claim 1, wherein the output stream is produced by the logical merge module by selecting from at least one non-failed input stream at any given time, to provide high availability.

12. The method of claim 1, wherein the output stream is produced by the logical merge module by selecting from at least one timely input stream at any given time, to provide fast availability.

13. The method of claim 1, further comprising using the logical merge module to accelerate introduction of a new source which produces a new input stream.

14. The method of claim 1, further comprising using the logical merge module to transition from one input stream to another input stream.

15. A logical merge module, implemented by physical and tangible computing functionality, for processing streams, comprising:

an element parsing module for parsing elements in plural physically divergent input streams;

an element type determining module for assessing a type of each element identified by the element parsing module;

an element processing module for determining an output action to take in response to each element that has been identified, to produce an output stream, the output action selected from among;

providing no contribution to the output stream;

providing new output information to the output stream;

adjusting previous output information in the output stream; and

providing progress marker information to the output stream; and

a state management module for adjusting a state associated with the logical merge module,

the output stream produced by the element processing module being logically compatible with each of the plural input streams.

16. The logical merge module of claim 15, wherein the logical merge module applies an algorithm, selected from among a plurality of algorithms, for implementing the element processing module and the state management module,

wherein the algorithms are associated with varying respective levels of constraints associated with the plurality of input streams.

17. A computer readable storage medium for storing computer readable instructions, the computer readable instructions providing a logical merge module when executed by one or more processing devices, the computer readable instructions comprising:

logic for receiving plural physically divergent input streams from respective sources that execute a same continuous query; and

logic for using a logical merge operator to produce an output stream which has a temporal database (TDB) representation that is logically equivalent with TDB representations of each of the input streams.

18. The computer readable storage medium of claim 17, wherein one or more of the plural input streams include at least one of characteristics (a)-(c):

(a) temporally disordered stream elements;

(b) revisions made to prior stream elements; and

(c) missing stream elements.

19. The computer readable storage medium of claim 17, wherein the plural input streams include elements associated with at least element types of:

an insert element type which adds new output information to the output stream;

an adjust element type which adjusts previous output information in the output stream; and

a progress marker element type which defines a time prior to which no further modifications are permitted.

20. The computer readable storage medium of claim 17, wherein the TDB representation of the output stream comprises a plurality of events, each event specifying a payload and a validity interval, the validity interval defining a time span over which the event is active and contributes to an output.