Streaming Queries

• US 20100088325A1
• Filed: 10/07/2008
• Published: 04/08/2010
• Est. Priority Date: 10/07/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Maier, David E., Goldstein, Jonathan D.
• Application Number:
  US12/246,509
• Publication Number:
  US 20100088325A1
• Time in Patent Office: Days
• US Class Current: 707/756
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

The described implementations relate to recursive streaming queries. One technique processes a recursive streaming query through a query graph. The technique also detects when output produced by executing the query graph advances to a specific point.

Claims

1. A system, comprising:

first and second networked stream operators for operating on a recursive streaming query, wherein the first operator is configured to receive at least two input streams and to generate an output stream based upon a first set of conditions and wherein the second operator is positioned downstream from the first operator and is configured to generate a multicast output, and wherein a portion of the multicast output is recursively directed back as an input to the first operator thereby forming a recursive loop.

2. The system of claim 1, wherein the first operator comprises a union operator and the second operator comprises a flying fixed-point (FFP) operator and wherein at least one additional operator is interposed between the union operator and the FFP operator.

3. The system of claim 1, wherein the at least one additional operator comprises a join operator that is configured to receive output from the union operator and at least one other stream as inputs.

4. The system of claim 1, wherein the second operator comprises a flying fixed-point (FFP) operator that is configured to probe the recursive loop with speculative times to determine a specific point in time to which the recursive loop has completed processing.

5. The system of claim 4, wherein the speculative times are based on timestamps of input events.

6. The system of claim 1, wherein the first operator comprises a union operator and the second operator comprises a flying fixed-point (FFP) operator and wherein at least one additional operator is interposed between the union operator and the FFP operator and wherein the FFP operator and the one or more additional operators are configured to correctly handle stream events that arrive out of time order.

7. The system of claim 6, wherein the FFP operator and the at least one additional operator are configured to correctly handle stream events that retract or reduce a validity of previously seen stream events.

8. The system of claim 1, wherein the second operator is configured to probe the recursive loop with speculative times to determine a point in time to which the recursive loop has completed processing.

9. A method, comprising:

processing at least one input stream associated with a recursive streaming query; and

,

advancing time for the recursive streaming query to a specific point when the at least one input stream has advanced to the specific point and recursive computations on the input stream are complete to the specific point.

10. The method of claim 9, wherein the processing comprising processing two input streams.

11. The method of claim 9, wherein the processing comprising introducing speculative time events to determine the specific point.

12. The method of claim 9, further comprising generating an output from the processing and wherein the output includes information about the advancing.

13. The method of claim 12, wherein the generating comprises generating the output as an event that contains time information associated with the advancing.

14. The method of claim 9, wherein the advancing occurs while recursive computations continue for events subsequent to the point.

15. The method of claim 9, wherein the advancing is repeated for additional times that are subsequent to the specific point.

16. A computer-readable storage media having instructions stored thereon that when executed by a computing device cause the computing device to perform acts, comprising:

processing a recursive streaming query through a query graph; and

,

detecting when output produced by executing the query graph advances to a specific point.

17. The computer-readable storage media of claim 16, wherein the processing comprises a recursive step on the query graph.

18. The computer-readable storage media of claim 17, wherein the detecting comprises detecting a passage of time on the recursive step.

19. The computer-readable storage media of claim 16, wherein the detecting comprises probing the query graph with the specific point in time.

20. The computer-readable storage media of claim 19, wherein the probing is accomplished with a speculative event.