Method and apparatus for efficient aggregate computation over data streams

• US 8,832,073 B2
• Filed: 06/29/2007
• Issued: 09/09/2014
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Rastogi, Rajeev, Satkin, Scott, Nagaraj, Kanthi Chikguntakal, Marayya, Naidu Kundrapu Venkata
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US11/770,926
• Publication Number:
  US 20090006346A1
• Time in Patent Office: 2,629 Days
• Field of Search: 707/713, 707/722
• US Class Current: 707/713
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Improved techniques are disclosed for processing data stream queries wherein a data stream is obtained, a set of aggregate queries to be executed on the data stream is obtained, and a query plan for executing the set of aggregate queries on the data stream is generated. In a first method, the generated query plan includes generating at least one intermediate aggregate query, wherein the intermediate aggregate query combines a subset of aggregate queries from the set of aggregate queries so as to pre-aggregate data from the data stream prior to execution of the subset of aggregate queries such that the generated query plan is optimized for computational expense based on a given cost model. In a second method, the generated query plan includes identifying similar filters in two or more aggregate queries of the set of aggregate queries and combining the similar filters into a single filter such that the single filter is usable to pre-filter data input to the two or more aggregate queries.

Claims

1. A method, comprising:

obtaining a data stream;

obtaining a set of aggregate queries to be executed on the data stream; and

generating a query plan for executing the set of aggregate queries on the data stream, wherein the generated query plan comprises generating at least one intermediate aggregate query, wherein the intermediate aggregate query combines a subset of aggregate queries from the set of aggregate queries so as to pre-aggregate data from the data stream prior to execution of the subset of aggregate queries such that the generated query plan is optimized for computational expense based on a given cost model;

wherein the generated query plan comprises a tree structure, the query plan generating step further comprises determining an optimal query plan with a lowest computation cost by determining a minimum-cost aggregate tree, and the minimum-cost aggregate tree is determined using a heuristic which adds one or more random aggregate queries to the aggregate tree to form an expanded aggregate graph, and uses a directed Steiner tree heuristic to find the minimum-cost aggregate subtree of the expanded aggregate graph;

wherein the generation of the query plan is implemented by executing one or more software programs on a processor device.

2. An article of manufacture comprising a processor-readable non-transitory storage medium storing one or more software programs which when executed by a processor perform the steps of the method of claim 1.

3. Apparatus, comprising:

a memory; and

a processor coupled to the memory and operative to;

obtain a data stream;

obtain a set of aggregate queries to be executed on the data stream; and

generate a query plan for executing the set of aggregate queries on the data stream, wherein the generated query plan comprises at least one of;

(i) generating at least one intermediate aggregate query, wherein the intermediate aggregate query combines a subset of aggregate queries from the set of aggregate queries so as to pre-aggregate data from the data stream prior to execution of the subset of aggregate queries such that the generated query plan is optimized for computational expense based on a given cost model; and

(ii) identifying similar filters in two or more aggregate queries of the set of aggregate queries and combining the similar filters into a single filter such that the single filter is usable to pre-filter data input to the two or more aggregate queries;

wherein the generated query plan comprises a tree structure, the query plan generating operation further comprises determining an optimal query plan with a lowest computation cost by determining a minimum-cost aggregate tree, and the minimum-cost aggregate tree is determined using a heuristic which adds one or more random aggregate queries to the aggregate tree to form an expanded aggregate graph, and uses a directed Steiner tree heuristic to find the minimum-cost aggregate subtree of the expanded aggregate graph.