Speculative execution in a real-time data environment

• US 8,688,646 B2
• Filed: 11/19/2012
• Issued: 04/01/2014
• Est. Priority Date: 09/15/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Barsness, Eric L., Santosuosso, John M.
• Primary Examiner(s): Kerzhner, Aleksandr
• Application Number:
  US13/680,586
• Publication Number:
  US 20130080400A1
• Time in Patent Office: 498 Days
• Field of Search: 707/687, 707/999.002
• US Class Current: 707/687
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

Techniques are described for speculatively executing operations on data in a data stream in parallel in a manner that increases the efficiency of the stream-based application. In addition to executing operations in parallel, embodiments of the invention may determine whether certain results produced by the parallel operations are valid results and discard any results determined to be invalid.

Claims

1. A computer-implemented method for processing a data stream, comprising:

executing, by operation of one or more computer processors, a first operation on a first tuple of the data stream by a first processing element to produce a first result tuple;

upon determining that a likelihood that a second operation will be valid if executed on the first tuple in parallel with the first operation exceeds a predetermined threshold value, executing the second operation on the first tuple of the data stream by a second processing element, wherein the second operation is executed in parallel with the first operation;

determining one or more attributes of the first tuple used in executing the second operation on the second processing element; and

comparing the determined one or more attributes of the first tuple with attributes of the first result tuple produced from executing the first operation by the first processing element, to determine whether the second operation executed by the second processing element is valid.

2. The method of claim 1, further comprising:

upon determining the second operation is invalid;

discarding a second result tuple, wherein the second result tuple is produced from executing the second operation on the first tuple of the data stream on the second processing element; and

executing the second operation on the first result tuple on the second processing element.

3. The method of claim 1, wherein determining the likelihood that the second operation will be valid, further comprises:

determining a second likelihood that the first operation modifies at least one attribute in the first tuple of the data stream.

4. The method of claim 1, wherein comparing the determined one or more attributes of the first tuple with attributes of the first result tuple to determine whether the second operation is valid, is further based on at least one of (i) whether the first result tuple contains fewer attributes than the first tuple of the data stream, (ii) whether the first result tuple contains more attributes than the first tuple of the data stream, and (iii) which attributes in the first tuple of the data stream are modified by the first operation.

5. The method of claim 1, further comprising:

calculating a time savings value for executing the second operation in parallel with the first operation, wherein the second operation is executed only when the time savings value exceeds a predetermined threshold value.

6. A computer-implemented method of processing a data stream, comprising:

executing a first operation on a first tuple of the data stream by a first processing element;

calculating a utility value for executing a second operation on the first tuple of the data stream by a second processing element in parallel to executing the first operation by the first processing element, wherein the utility value is based on (i) a likelihood that the second operation will be valid if executed on the first tuple in parallel with the first operation and (ii) a time savings value for executing the second operation in parallel with the first operation;

upon determining the calculated utility value exceeds a threshold utility value, executing the second operation on the first tuple of the data stream by the second processing element, wherein the second operation is executed in parallel with the first operation; and

determining whether a result of the second operation is valid, based on whether the first operation modified the first tuple.

7. The method of claim 6, further comprising:

upon determining the second operation is invalid, executing the second operation on a first result tuple produced from executing the first operation by the first processing element, by the second processing element.

8. The method of claim 6, wherein calculating the utility value for processing the first tuple of the data stream by the second processing element in parallel to executing the first operation, further comprises:

determining the likelihood that executing the second operation will produce a valid result; and

calculating the time savings value for executing the second operation in parallel with the first operation, wherein the second operation is executed only when the time savings value exceeds a predetermined threshold value.

9. The method of claim 8, wherein determining a likelihood that the second operation will produce a valid result is further based on historical data collected from previously-processed tuples on the first processing element.

10. The method of claim 9, wherein the historical data includes at least one of (i) a likelihood the first result tuple is produced, (ii) a likelihood one or more attributes are changed, and (iii) a likelihood one or more attributes are added, and (iv) a likelihood one or more attributes are removed.

11. A computer-implemented method for processing a data stream, comprising:

executing, by operation of one or more computer processors, a first operation on a first tuple of the data stream by a first processing element to produce a first result tuple;

executing a second operation on the first tuple of the data stream by a second processing element, wherein the second operation is executed in parallel with the first operation;

determining one or more attributes of the first tuple used in executing the second operation on the second processing element; and

comparing the determined one or more attributes of the first tuple with attributes of the first result tuple produced from executing the first operation by the first processing element, to determine whether the second operation executed by the second processing element is valid, based on at least one of (i) whether the first result tuple contains fewer attributes than the first tuple of the data stream, (ii) whether the first result tuple contains more attributes than the first tuple of the data stream, and (iii) which attributes in the first tuple of the data stream are modified by the first operation.