Order-independent stream query processing

• US 8,972,446 B2
• Filed: 07/08/2013
• Issued: 03/03/2015
• 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/936,922
• Publication Number:
  US 20140012877A1
• Time in Patent Office: 603 Days
• Field of Search: None
• 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 system for order-independent stream query processing comprising:

one or more continuous nodes comprising a memory and a processor, wherein each of the one or more continuous nodes are configured to;

partition received data into one or more partitions;

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

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

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

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

consolidate the partial results for each partition on a continuous basis to produce final results.

2. The system of claim 1, wherein each of the one or more continuous nodes are further configured to produce, for each partition, a streaming view that consolidates the partial results for the partition.

3. The system of claim 1, wherein each of the one or more continuous nodes are further configured to produce, for each partition, a non-streaming view that consolidates the partial results for the partition.

4. The system of claim 1, wherein each of the one or more continuous nodes are further configured to close a partition when no progress is made in the partition over a predetermined time interval and a heartbeat is received.

5. The system of claim 1, wherein each of the one or more continuous nodes are further configured to close a partition when predetermined conditions are satisfied.

6. The system of claim 1, wherein the received query includes a parallel portion and a serial portion, and wherein each of the one or more continuous nodes are further configured to:

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

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

process the one or more sub-queries to produce partial parallel results;

process the serial portion of the received query to produce serial results;

combine the partial parallel results and the serial results to produce compound fmal results.

7. The system of claim 1, wherein each of the one or more continuous nodes are further configured to produce, for each partition, a view that consolidates the partial results for the partition, the view including one or more relational views that encapsulate deferred consolidation of partial aggregates.

8. The system of claim 1, wherein each of the one or more continuous nodes are further configured, as part of consolidating the partial results for each partition, to:

consolidate the partial results for a partition;

derive a partial aggregate, the partial aggregate comprising a partial state record for the partition.

9. The system of claim 1, wherein each of the one or more continuous nodes are further configured to, as part of consolidating the partial results for each partition, derive a final aggregate, the final aggregate being derived from one or more partial state records, the final aggregate comprising a final result.

10. The system of claim 1, wherein each of the one or more continuous nodes are further configured to:

consolidate the partial results for each partition on continuous basis to produce final results;

categorize a portion of the partial results for each partition as being too late to process for serial path queries;

store the late portion of the partial results into one or more auxiliary correction tables for asynchronous processing;

perform a repair process that periodically scans records from the one or more auxiliary correction tables and combines scanned records with an appropriate portion of originally arrived records.

11. The system of claim 1, wherein the out-of-order datum is a tuple.

12. The system of claim 1, wherein the one or more continuous nodes are continuous back ends.

13. The system of claim 1, wherein the one or more continuous nodes are a plurality of continuous nodes, and wherein received data at one continuous node of the plurality of continuous nodes are final results produced at another continuous node of the plurality of continuous nodes.