Order-independent stream query processing

• US 8,484,243 B2
• Filed: 05/05/2011
• Issued: 07/09/2013
• Est. Priority Date: 05/05/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Krishnamurthy, Saileshwar, Lewis, Michael R., Li, Wing, Thombre, Neil, Davis, Jeffrey A., Farina, Daniel Robert
• Primary Examiner(s): Lee, Wilson
• Application Number:
  US13/101,967
• Publication Number:
  US 20110302164A1
• Time in Patent Office: 796 Days
• Field of Search: 707713-720, 707760-781
• US Class Current: 707/771
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

In a system and method for order-independent stream query processing, one or more input streams of data are received, and the one or more input streams are analyzed to determine data which is older than an already emitted progress indicator. The data which is older than the already emitted progress indicator is partitioned into one or more partitions, and each of the one or more partitions are independently processed using out-of-order processing techniques. A query is received, rewritten and decomposed into one or more sub-queries that produce partial results for each of the one or more partitions, where each of the one or more sub-queries correspond to a partition. A view is also produced that consolidates the partial results for each partition. The partial results are consolidated at a consolidation time specified by the query to produce final results, and the final results are provided.

Claims

1. A method for order-independent stream query processing, the method comprising:

partitioning received data into one or more partitions;

decomposing a received query into one or more sub-queries that can operate on independent partitions to produce partial results for each partition and a view that consolidates the partial results for each partition;

receiving an out-of-order datum, the out-of-order datum being too late to process for an original partition;

selecting a partition whose latest data is closest to the out-of-order datum;

processing the out-of-order datum in the selected partition;

consolidating the partial results on a continuous basis to produce final results; and

reporting the final results;

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

2. The method of claim 1, the view including a streaming view.

3. The method of claim 1, the view including a non-streaming view.

4. The method of claim 1, further comprising closing a partition when no progress is made in the partition over a predetermined time interval and a heartbeat is received.

5. The method of claim 1, further comprising closing a partition when predetermined conditions are satisfied.

6. The method of claim 1, the query including a parallel portion and a serial portion, the method further comprising:

decomposing the query into the parallel portion and the serial portion, the parallel portion of the query being amenable to partial processing;

rewriting the parallel portion into the one or more sub-queries;

evaluating the serial portion of the query to produce serial results;

combining the parallel results and the serial results to produce compound final results; and

providing the compound final results.

7. The method of claim 1, the view including one or more relational views that encapsulates deferred consolidation of partial aggregates.

8. The method of claim 1, the consolidating the partial results including deriving a partial aggregate, the partial aggregate comprising a partial state record for a partition.

9. The method of claim 1, the consolidating the partial results comprising deriving a final aggregate, the final aggregate being derived from one or more partial state records, the final aggregate comprising a final result.

10. The method of claim 1, further comprising:

consolidating the partial results on continuous basis to produce final results;

in the case of final results feeding a serial path stream, categorizing the partial results as being too late to process for serial path queries;

store the late partial results into auxiliary correction tables for asynchronous processing; and

performing a repair process that periodically scans records from the auxiliary tables and combines them with an appropriate portion of originally arrived records.

11. The method of claim 10, further comprising:

detecting an aborted transaction while processing received data;

using the repair process to repair ranges of serial path data that was received as part of the aborted transaction.

23. The method of claim 1, wherein the out-of-order datum is a tuple.

12. A non-transitory computer readable storage medium storing instructions, which when executed by one or more processors, cause the one or more processors to perform:

partitioning received data into one or more partitions;

decomposing a received query into one or more sub-queries that can operate on independent partitions to produce partial results for each partition and a view that consolidates the partial results for each partition;

receiving an out-of-order datum, the out-of-order datum being too late to process for an original partition;

selecting a partition whose latest data is closest to the out-of-order datum;

processing the out-of-order datum in the selected partition;

consolidating the partial results on a continuous basis to produce final results; and

reporting the final results.

13. The non-transitory computer-readable storage medium of claim 12, the view including a streaming view.

14. The non-transitory computer-readable storage medium of claim 12, the view including a non-streaming view.

15. The non-transitory computer-readable storage medium of claim 12, further comprising instructions which when executed cause closing a partition when no progress is made in the partition over a predetermined time interval and a heartbeat is received.

16. The non-transitory computer-readable storage medium of claim 12, further comprising instructions which when executed cause closing a partition when predetermined conditions are satisfied.

17. The non-transitory computer-readable storage medium of claim 12, further comprising instructions which when executed cause:

decomposing the query into the parallel portion and the serial portion, the parallel portion of the query being amenable to partial processing, the query including a parallel portion and a serial portion;

rewriting the parallel portion into the one or more sub-queries;

evaluating the serial portion of the query to produce serial results;

combining the parallel results and the serial results to produce compound final results;

providing the compound final results.

18. The non-transitory computer-readable storage medium of claim 12, the view including one or more relational views that encapsulates deferred consolidation of partial aggregates.

19. The non-transitory computer-readable storage medium of claim 12, further comprising instructions which when executed cause the consolidating the partial results including deriving a partial aggregate, the partial aggregate comprising a partial state record for a partition.

20. The non-transitory computer-readable storage medium of claim 12, instructions which when executed cause the consolidating the partial results comprising deriving a final aggregate, the final aggregate being derived from one or more partial state records, the final aggregate comprising a final result.

21. The non-transitory computer-readable storage medium of claim 12, further comprising instructions which when executed cause:

consolidating the partial results on continuous basis to produce final results;

in the case of final results feeding a serial path stream, categorizing the partial results as being too late to process for serial path queries;

store the late partial results into auxiliary correction tables for asynchronous processing;

performing a repair process that periodically scans records from the auxiliary tables and combines them with an appropriate portion of originally arrived records.

22. The non-transitory computer-readable storage medium of claim 21, further comprising instructions which when executed cause:

detecting an aborted transaction while processing received data;

using the repair process to repair ranges of serial path data that was received as part of the aborted transaction.

24. The non-transitory computer-readable storage medium of claim 12, wherein the out-of-order datum is a tuple.