Method and Apparatus for Efficient Aggregate Computation over Data Streams

• US 20090006346A1
• Filed: 06/29/2007
• Published: 01/01/2009
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: V M, Naidu K, Satkin, Scott, C N, Kanthi, Rastogi, Rajeev
• Granted Patent: US 8,832,073 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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.

2. The method of claim 1, wherein the intermediate aggregate query reduces the number of computations that would otherwise be required to generate results of the subset of aggregate queries.

3. The method of claim 1, wherein the generated query plan for executing the set of aggregate queries for the data stream is substantially entirely executed using a main memory of a machine hosting the generated query plan.

4. The method of claim 1, wherein the generated query plan comprises a tree structure.

5. The method of claim 4, wherein the query plan generating step further comprises determining an optimal query plan with a lowest computation cost by determining a minimum-cost aggregate tree.

6. The method of claim 5, wherein the minimum-cost aggregate tree is determined using a heuristic which performs one or more locally-optimal modifications to the aggregate tree such that a maximum cost reduction is realized.

7. The method of claim 5, wherein 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.

8. The method of claim 1, wherein the generated query plan further comprises generating other intermediate aggregate queries, wherein a first one of the other intermediate aggregate queries combines second and third ones of the other intermediate aggregate queries.

9. The method of claim 1, wherein the data stream comprises records received from a data network, wherein each of the data records comprises attributes that describe flow statistics in the data network.

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

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

12. The method of claim 11, wherein the generated query plan further comprises generating other filters, wherein a first one of the other generated filters pre-filters data prior to the data entering a second one of the other generated filters, and the second one of the other generated filters pre-filters data prior to the data entering one or more of the set of aggregate queries.

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

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

15. The apparatus of claim 14, wherein the intermediate aggregate query reduces the number of computations that would otherwise be required to generate results of the subset of aggregate queries.

16. The apparatus of claim 14, wherein the memory comprises main memory and the generated query plan for executing the set of aggregate queries for the data stream is substantially entirely executed using the main memory.

17. The apparatus of claim 14, wherein the generated query plan comprises a tree structure.

18. The apparatus of claim 17, wherein the query plan generating operation further comprises determining an optimal query plan with a lowest computation cost by determining a minimum-cost aggregate tree.

19. The apparatus of claim 18, wherein the minimum-cost aggregate tree is determined using a heuristic which performs one or more locally-optimal modifications to the aggregate tree such that a maximum cost reduction is realized.

20. The apparatus of claim 18, wherein 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.