Dynamically Sharing A Subtree Of Operators In A Data Stream Management System Operating On Existing Queries

• US 20090106189A1
• Filed: 10/17/2007
• Published: 04/23/2009
• Est. Priority Date: 10/17/2007
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Jain, Namit, Srinivasan, Anand, Mishra, Shailendra Kumar
• Granted Patent: US 8,296,316 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A new continuous query to a data stream management system (DSMS) may use several operators that are equivalent to operators currently being used by continuous queries that have been previously registered in the DSMS. To determine equivalence of operators, the DSMS checks at least the function and the data input to the operators. On finding equivalence, the DSMS modifies a global plan being executed, to use at least an existing subtree of operators during execution of the new continuous query, to generate a modified plan. The DSMS is also programmed to cause each relation source operator (which outputs a relation) to propagate a current state of the relation to each operator newly coupled to the relational operator. After propagation of current state to newly-coupled operators, each operator in the modified plan processes any new data and supplies the result to all operators coupled thereto, including newly-coupled operators and existing operators.

Claims

1. A computer-implemented method of processing a plurality of input streams of data using a plurality of continuous queries, the method comprising:

processing the plurality of input streams in a computer, by executing thereon the plurality of continuous queries based on a global plan;

during said processing, receiving a new continuous query to be executed;

during said processing, preparing an additional plan for execution of the new continuous query independent of the global plan;

during said processing, traversing the additional plan in a bottom up manner, to select therefrom a current node;

during said processing, checking if an operator at the current node is equivalent to any operator in a plurality of operators in the global plan;

wherein two operators that perform identical functions with identical inputs are determined by said checking to be equivalent;

if said checking finds no equivalent, modifying the global plan by adding thereto said operator at the current node to obtain a modified plan during said processing;

if said checking finds equivalence, and if said operator at the current node outputs a relation, propagating from said operator a current state of said relation to a new operator in said new continuous query prior to execution of the new continuous query;

returning to said traversing with the modified plan as the global plan, unless the current node is a root of the additional plan;

altering said processing, to cause execution of the new continuous query in addition to said plurality of continuous queries, based on the modified plan; and

outputting from said computer, a stream generated based at least partially on processing of said data by executing the new continuous query.

2. The method of claim 1 wherein:

storing an identifier of said any operator determined to be equivalent, in a temporary variable associated with the first operator, if a result of said checking is true; and

using said identifier during said modifying.

3. The method of claim 1 wherein:

said propagating is performed in a manner transparent to the user, relative to at least one predetermined soft exception.

4. The method of claim 1 further comprising:

said propagating to the first operator is performed at a time when the first operator is awakened subsequent to creation of the modified plan.

5. The method of claim 1 wherein:

the relation is represented incrementally in the global plan, as a plurality of tuples with each tuple being time stamped; and

all tuples of the relation having a time stamp older than a current time represent said current state.

6. A computer readable storage medium encoded with a plurality of instructions for a computer, the instructions comprising:

instructions to process a plurality of input streams in the computer, by executing thereon a plurality of continuous queries based on a global plan;

instructions to receive a new continuous query during processing by said instructions to process, wherein the new continuous query is to be executed;

instructions to prepare an additional plan during processing by said instructions to process, wherein the additional plan is for execution of the new continuous query independent of the global plan;

instructions to traverse the additional plan in a bottom up manner, during processing by said instructions to process, to select therefrom a current node;

instructions to check if an operator at the current node is equivalent to any operator in a plurality of operators in the global plan, during processing by said instructions to process;

wherein two operators that perform identical functions with identical inputs are determined to be equivalent by said instructions to check;

instructions responsive to said instructions to check, to modify the global plan by adding thereto said operator at the current node to obtain a modified plan if said instructions to check find no equivalent;

instructions to propagate from said operator a current state of said relation to a new operator in said new continuous query prior to execution of the new continuous query if said instructions to check find equivalence and if said operator at the current node outputs a relation,

instructions, to return control to said instructions to traverse, with the modified plan as the global plan, unless the current node is a root of the additional plan;

instructions, to alter said instructions to process, to cause execution of the new continuous query in addition to said plurality of continuous queries, based on the modified plan; and

instructions to output from said computer, a stream generated based at least partially on processing of said data by executing the new continuous query.