Order-Independent Stream Query Processing

• US 20110302164A1
• Filed: 05/05/2011
• Published: 12/08/2011
• 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, Thombre, Neil, Lewis, Michael R., Li, Wing, Davis, Jeffrey A., Farina, Daniel Robert
• Granted Patent: US 8,484,243 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• 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, the received data determined to be older than a previously emitted progress indicator;

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;

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

reporting the final results.

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:

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

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

processing the out-of-order tuple in the selected partition.

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

7. 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.

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

9. 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.

10. 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.

11. 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 said late data into auxiliary correction tables for asynchronous processing; and

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

12. The method of claim 11, further comprising:

detecting an aborted transaction while processing received data; and

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

14. The system of claim 12, the continuous query back ends further comprising a query receiving module, the query receiving module being configured to receive the query and, automatically dividingdivide the query into a parallel portion and a serial portion, the parallel portion of the query being amenable to partial processing, and rewrite the parallel portion into the one or more sub-queries.

15. The system of claim 14, the continuous query executor being further configured to evaluate the serial portion of the query to produce serial results and combine the parallel results and the serial results to produce compound final results, the final results comprising the compound final results.

16. The system of claim 15, further comprising a continuous query archiver configured to write out the serial data to serial tables.

13. A system for order-independent stream query processing comprising:

one or more continuous query back ends, each continuous query back end being configured to receive an input stream of data including a query, partition received data older than a previously emitted progress indicator into one or more partitions, and divide a received query into one or more sub-queries that produce partial results for each of the one or more partitions, each of the one or more sub-queries corresponding to a partition and a view that consolidates the partial results for each partition, and consolidate the partial results; and

one or more query back ends, the one or more query back ends receiving the final results from the one or more continuous query back ends via a continuous query executor.

17. The system of claim 13, further comprising a continuous query reducer configured to determine if there are large amounts of out-of-order data and derive a partial aggregate comprising a partial state record for a partition.

18. The system of claim 13, further comprising a continuous query repair module configured to receive an out-of-order tuple, the out-of-order tuple being too late to process for an original partition, spool the out-of-order tuple into an auxiliary structure, insert the out-of-order tuple into an appropriate portion of original tuples stored in a memory module, and recompute and update any affected portions of the partial results stored in a memory module.

19. The system of claim 18, the continuous query repair module being further configured to determine that the partial results need to be recalculated from at least one of the one or more partitions based upon a transaction rollback indicator, identify a range of tuples that need to be replaced in the memory module using the transaction rollback indicator in conjuction with an underlying metadata structure, and reprocess the identified range of tuples.

20. The system of claim 13, wherein the continuous query executor exploits a plurality of processor cores by splitting at least one of operators or queries across the plurality of processor cores.

21. A computer readable storage medium having embodied thereon a program, the program being executable by a processor to perform a method for order-independent stream query processing, the method comprising:

partitioning received data into one or more partitions, the received data determined to be older than a previously emitted progress indicator;

dividing a received query into one or more sub-queries that produce partial results for each of the one or more partitions, each of the one or more sub-queries corresponding to a partition and a view that consolidates the partial results for each partition;

consolidating the partial results based on a consolidation event to produce final results; and

reporting the final results.