Real-time query optimization in a decision support system

• US 6,338,055 B1
• Filed: 12/07/1998
• Issued: 01/08/2002
• Est. Priority Date: 12/07/1998
• Status: Expired due to Term

• Current Assignee: Innovation Technology Group Incorporated
• Original Assignee: Vitria Technology Incorporated (Innovation Technology Group Incorporated)
• Inventors: Hagmann, Robert, Skeen, Marion D.
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/206,664
• Time in Patent Office: 1,128 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A computer-implemented process for evaluating events furnished to a real time decision support system executing on a computer with respect to queries submitted by users comprising the steps of parsing each query into its elements to determine its correctness, eliminating incorrect queries, performing single query optimizations on each query, performing multiquery optimizations on all queries for each event type, and performing result processing optimizations for each query.

Claims

1. A computer-implemented process for generating a process for evaluating events furnished to a real time decision support system executing on a computer comprising the steps of:

parsing a query furnished by a user to the real time decision support system to determine the contents of the query,

testing the correctness of the structure of the query,

determining whether a structurally-correct query is of a category which may be optimized to reduce the time for query processing,

optimizing a query determined to be of such a category, and

selecting an attribute from an expected event to initiate processing of the query.

2. A computer-implemented process for evaluating events furnished to a real time decision support system executing on a computer with respect to queries submitted by users comprising the steps of:

parsing each query into its elements to determine its correctness,

eliminating incorrect queries,

performing single query optimizations on each query,

performing multiquery optimizations on all queries for each event type, and

performing result processing optimizations for each query.

3. A process as claimed in claim 2 in which the step of eliminating incorrect queries includes the step of eliminating syntactically incorrect queries.

4. A process as claimed in claim 2 in which the step of eliminating incorrect queries includes the step of eliminating queries that always provide a null result.

5. A process as claimed in claim 2 in which the step of performing single query optimizations on each query includes a step of precomputing and storing reference subqueries.

6. A process as claimed in claim 5 in which the step of performing single query optimizations on each query includes an additional step of rerunning the step of precomputing and storing reference subqueries to reoptimize any query when an event includes data changing a precomputed and stored reference subquery.

7. A process as claimed in claim 2 in which the step of performing single query optimizations on each query includes a step of reordering commutable expressions.

8. A process as claimed in claim 2 in which the step of performing single query optimizations on each query includes a step of placing a query in normal form.

9. A process as claimed in claim 2 in which the step of performing single query optimizations on each query includes a step of constructing a decision tree to optimize query constraint checking.

10. A process as claimed in claim 9 in which the step of constructing a decision tree to optimize query constraint checking includes a step of arranging constraints of the query to test attributes of data sources in order from most to least selective.

11. A process as claimed in claim 2 in which the step of constructing a decision tree to optimize query constraint checking includes a step of selecting a constraint of a query as an entry point for testing the constraints of a query based on the selectivity of the constraint.

12. A process as claimed in claim 2 in which the step of performing multiquery optimizations on all queries for each event type comprises constructing a constraint index for each attribute of the event type.

13. A process as claimed in claim 2 in which the step of constructing a constraint index for each attribute of the event type provides a set of queries having a constraint satisfied by a value of the attribute.

14. A process as claimed in claim 2 in which the step of performing multiquery optimizations on all queries for each event type comprises modifying any decision tree of each query referred to be each constraint index to be specific to the event type.

15. A process as claimed in claim 2 in which the step of performing result processing optimizations for each query comprises the step of selecting multivariate queries for processing by a brute force algorithm.

16. A process as claimed in claim 2 in which the step of performing result processing optimizations for each query comprises the step of selecting simple queries for processing by a simple incremental processing algorithm.

17. A process as claimed in claim 2 in which the step of performing result processing optimizations for each query comprises the steps of

selecting univariate queries for optimization, and

optimizing functions of univariate queries in result expressions.