Processing Overlapping Continuous Queries

• US 20090043729A1
• Filed: 08/09/2007
• Published: 02/12/2009
• Est. Priority Date: 08/09/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Ranganathan, Anand, Yang, Hao, Parthasarathy, Srinivasan
• Granted Patent: US 8,055,653 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

An edge-covering based greedy method for shared filter ordering includes receiving a plurality of queries, wherein each query is a conjunction of filters, and each filter is shared across multiple queries of the plurality of queries, evaluating a unit price of each filter, evaluating, sequentially, each filter in order of a lowest to a highest unit price, to determine a value for each filter, and changing an ordering of the filters according to the values.

An edge-covering based harmonic method for shared filter ordering includes receiving a plurality of queries, wherein each query is a conjunction of filters, and each filter is shared across multiple queries of the plurality of queries, evaluating a weight of each filter, evaluating, randomly, each filter having a probability inversely proportionally to its weight, to determine a value, and changing an ordering of the filters according to the values.

Claims

1. A computer readable medium embodying instructions executable by a processor to perform a method for an edge-covering based greedy method for shared filter ordering, the method comprising:

receiving a plurality of queries, wherein each query is a conjunction of filters, and each filter is shared across multiple queries of,the plurality of queries;

evaluating a unit price of each filter;

evaluating, sequentially, each filter in order of a lowest unit price to a highest unit price, to determine a value for each filter; and

changing an ordering of the filters according to the values, wherein the ordering of the filters is an evaluation plan having a lowest cost among possible evaluation plans.

2. The method of claim 1, wherein evaluating, sequentially, each filter further comprises determining any filter that has been decided due to an evaluation of a prior filter to have been evaluated and skipping to a subsequent filter.

3. The method of claim 1, wherein the plurality of queries and filters area arranged in a residual graph having edges between queries and corresponding filters, wherein each filter evaluation results in a subset of edges in the residual graph being covered.

4. The method of claim 3, wherein the method terminates upon covering all edges.

5. A computer readable medium embodying instructions executable by a processor to perform a method for an edge-covering based harmonic method for shared filter ordering, the method comprising:

receiving a plurality of queries, wherein each query is a conjunction of filters, and each filter is shared across multiple queries of the plurality of queries;

evaluating a weight of each filter;

evaluating, randomly, each filter having a probability inversely proportionally to its weight, to determine a value; and

changing an ordering of the filters according to the values, wherein the ordering of the filters is an evaluation plan having a lowest cost among possible evaluation plans.

6. The method of claim 5, wherein the plurality of queries and filters area arranged in a residual graph having edges between queries and corresponding filters, wherein each filter evaluation results in a subset of edges in the residual graph being covered.

7. The method of claim 6, further comprising updating the residual graph by removing an evaluated filter, edges covered by the evaluated filter, newly decided queries, and any filter that is not longer part of any yet-to-be decided queries.

8. The method of claim 5, wherein the method terminates upon deciding all queries.

9. The method of claim 5, wherein the method is performed in parallel on a plurality of interconnected systems.

10. A system for an edge-covering based greedy method for shared filter ordering comprising:

a memory storing a plurality of queries, wherein each query is a conjunction of filters, and each filter is shared across multiple queries of the plurality of queries; and

a processor in communication with the memory for receiving the plurality of queries and executing commands for ordering the plurality of queries comprising,

evaluating a unit price of each filter;

evaluating, sequentially, each filter in order of a lowest unit price to a highest unit price, to determine a value for each filter; and

changing an ordering of the filters according to the values, wherein the ordering of the filters is an evaluation plan having a lowest cost among possible evaluation plans.

11. The system of claim 10, wherein evaluating, sequentially, each filter further comprises determining any filter that has been decided due to an evaluation of a prior filter to have been evaluated and skipping to a subsequent filter.

12. The system of claim 10, wherein the plurality of queries and filters area arranged in a residual graph stored in the memory having edges between queries and corresponding filters, wherein each filter evaluation results in a subset of edges in the residual graph being covered.

13. The system of claim 12, wherein the processor terminates the execution upon covering all edges.

14. A system for an edge-covering based harmonic method for shared filter ordering comprising:

a memory storing a plurality of queries, wherein each query is a conjunction of filters, and each filter is shared across multiple queries of the plurality of queries; and

a processor in communication with the memory for receiving the plurality of queries and executing commands for ordering the plurality of queries comprising,

evaluating a weight of each filter;

evaluating, randomly, each filter having a probability inversely proportionally to its weight, to determine a value; and

changing an ordering of the filters according to the values, wherein the ordering of the filters is an evaluation plan having a lowest cost among possible evaluation plans.

15. The system of claim 14, wherein the plurality of queries and filters area arranged in a residual graph stored in the memory having edges between queries and corresponding filters, wherein each filter evaluation results in a subset of edges in the residual graph being covered.

16. The system of claim 15, further comprising updating the residual graph by removing an evaluated filter, edges covered by the evaluated filter, newly decided queries, and any filter that is not longer part of any yet-to-be decided queries.

17. The system of claim 14, wherein the processor terminates the execution upon deciding all queries.

18. The system of claim 14, interconnected with at least one other system for executing the commands for ordering the plurality of queries in parallel.