Method, system, and program for query optimization with algebraic rules

• US 7,945,557 B2
• Filed: 05/25/2007
• Issued: 05/17/2011
• Est. Priority Date: 11/25/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cheng, Qi, Sun, Yang, Zuzarte, Calisto Paul, Pirahesh, Mir Hamid
• Primary Examiner(s): Coby; Frantz
• Application Number:
  US11/754,213
• Publication Number:
  US 20070226180A1
• Time in Patent Office: 1,453 Days
• Field of Search: 709201-203, 709217-219, 707713-721, 707/705, 707/769
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A set of algebraic rules applicable to a query are identified, wherein each of the algebraic rules represents a relationship between two columns in a relational database table. A source column is identified by searching the query for a source predicate, wherein the source predicate is a range predicate. One or more candidate target columns are identified by searching the set of algebraic rules, wherein each of the candidate target columns occurs on one side of a binding expression and the source column occurs on the other side of the binding expression. For each of the one or more candidate target columns, a bounds subquery that provides a lower bound and an upper bound for a new range predicate is derived and he new range predicate is introduced into the query, wherein the query is executed to retrieve data from one or more data stores.

Claims

1. A method for executing a query, comprising:

with a computer including a processor;

receiving the query that references one or more relational database tables;

creating an outlier materialized query table storing exception data that represents a set of algebraic rules applicable to the query, wherein each of the algebraic rules represents a relationship between two columns in at least one of the one or more relational database tables;

identifying a source column by searching the query for a source predicate, wherein the source predicate is a range predicate;

identifying one or more candidate target columns by searching the set of algebraic rules represented by the outlier materialized query table, wherein each of the candidate target columns occurs on one side of a binding expression and the source column occurs on the other side of the binding expression, wherein the binding expression is a subtraction expression; and

for each of the one or more candidate target columns,

using the outlier materialized query table to determine one or more ranges each having a lower bound and an upper bound for a new range predicate that is applied to one of the relational database tables by;

selecting qualified outliers from the outlier materialized query table;

for each of the selected outliers, determining a range having the lower bound and the upper bound;

in response to determining that there is an overlapping between ranges, merging the ranges and using the merged ranges for the new range predicate; and

in response to determining that there is no overlapping between ranges, using the ranges for the new range predicate;

introducing the new range predicate into the query by merging the bounds subquery into a portion of the query and adding the new range predicate to the query; and

executing the portion of the query against the one or more relational database tables to retrieve data from one or more data stores.

2. The method of claim 1, wherein introducing the new range predicate into the query further comprises:

generating the new range predicate based on whether the candidate target column occurs on the left hand side of the binding expression or the right hand side of the binding expression.

3. The method of claim 1, further comprising:

generating a bounds view from source predicate information collected for a candidate target column and a lower bound and an upper bound of a range, and wherein the bounds view is capable of being generated using at least one of a range multiplying technique or a range stretching technique.

4. The method of claim 1, wherein identifying the set of algebraic rules further comprises:

creating a first query graph model representation of the query;

creating a second query graph model representation of the outlier materialized query table; and

comparing the first query graph model and the second query graph model.

5. The method of claim 1, wherein a candidate target column is from a same relational database table as a relational database table in which the source column resides.

6. The method of claim 4, wherein there is a join in the outlier materialized query table and wherein identifying the set of algebraic rules:

determining that join predicates other than the outlier predicate in the outlier materialized query table have matching predicates in the query.

7. The method of claim 6, wherein the new range predicate is derived by selecting a candidate target column from base tables involved in the join.

8. The method of claim 1, wherein the candidate target column is from a relational database table other than a relational database table in which the source column resides.

9. The method of claim 6, wherein the query contains a correlation predicate.

10. The method of claim 9, further comprising:

translating the correlation predicate into a join predicate in a context of the outlier materialized query table;

when the translated join predicate matches the join predicate in the outlier materialized query table, deriving a new predicate for the correlation predicate in a child query block using a source predicate on a quantifier of a parent query block; and

wherein searching the query for the source predicate further includes searching the parent query block for the source predicate.

11. An article of manufacture comprising a computer readable medium including a program for executing a query, wherein the program, when executed by a processor of a computer, causes operations to be performed, the operations comprising:

receiving the query that references one or more relational database tables;

creating an outlier materialized query table storing exception data that represents a set of algebraic rules applicable to the query, wherein each of the algebraic rules represents a relationship between two columns in at least one of the one or more relational database tables;

identifying a source column by searching the query for a source predicate, wherein the source predicate is a range predicate;

identifying one or more candidate target columns by searching the set of algebraic rules represented by the outlier materialized query table, wherein each of the candidate target columns occurs on one side of a binding expression and the source column occurs on the other side of the binding expression, wherein the binding expression is a subtraction expression; and

for each of the one or more candidate target columns,

using the outlier materialized query table to determine one or more ranges each having a lower bound and an upper bound for a new range predicate that is applied to one of the relational database tables by;

selecting qualified outliers from the outlier materialized query table;

for each of the selected outliers, determining a range having the lower bound and the upper bound;

in response to determining that there is an overlapping between ranges, merging the ranges and using the merged ranges for the new range predicate; and

in response to determining that there is no overlapping between ranges, using the ranges for the new range predicate;

introducing the new range predicate into the query by merging the bounds subquery into a portion of the query and adding the new range predicate to the query; and

executing the portion of the query against the one or more relational database tables to retrieve data from one or more data stores.

12. The article of manufacture of claim 11, wherein the operations for introducing the new range predicate into the query further comprise:

generating the new range predicate based on whether the candidate target column occurs on the left hand side of the binding expression or the right hand side of the binding expression.

13. The article of manufacture of claim 11, wherein the operations further comprise:

generating a bounds view from source predicate information collected for a candidate target column and a lower bound and an upper bound of a range, and wherein the bounds view is capable of being generated using at least one of a range multiplying technique or a range stretching technique.

14. The article of manufacture of claim 11, wherein operations for identifying the set of algebraic rules further comprise:

creating a first query graph model representation of the query;

creating a second query graph model representation of the outlier materialized query table; and

comparing the first query graph model and the second query graph model.

15. The article of manufacture of claim 11, wherein a candidate target column is from a same relational database table as a relational database table in which the source column resides.

16. The article of manufacture of claim 14, wherein there is a join in the outlier materialized query table and wherein operations for identifying the set of algebraic rules further comprise:

determining that join predicates other than the outlier predicate in the outlier materialized query table have matching predicates in the query.

17. The article of manufacture of claim 16, wherein the new range predicate is derived by selecting a candidate target column from base tables involved in the join.

18. The article of manufacture of claim 11, wherein the candidate target column is from a relational database table other than a relational database table in which the source column resides.

19. The article of manufacture of claim 16, wherein the query contains a correlation predicate.

20. The article of manufacture of claim 19, wherein the operations further comprise:

translating the correlation predicate into a join predicate in a context of the outlier materialized query table;

when the translated join predicate matches the join predicate in the outlier materialized query table, deriving a new predicate for the correlation predicate in a child query block using a source predicate on a quantifier of a parent query block; and

wherein searching the query for the source predicate further includes searching the parent query block for the source predicate.

21. A system for executing a query, comprising:

a processor; and

gate array logic performing operations, the operations comprising;

receiving the query that references one or more relational database tables;

creating an outlier materialized query table storing exception data that represents a set of algebraic rules applicable to the query, wherein each of the algebraic rules represents a relationship between two columns in at least one of the one or more relational database tables;

identifying a source column by searching the query for a source predicate, wherein the source predicate is a range predicate;

identifying one or more candidate target columns by searching the set of algebraic rules represented by the outlier materialized query table, wherein each of the candidate target columns occurs on one side of a binding expression and the source column occurs on the other side of the binding expression, wherein the binding expression is a subtraction expression; and

for each of the one or more candidate target columns,

using the outlier materialized query table to determine one or more ranges each having a lower bound and an upper bound for a new range predicate that is applied to one of the relational database tables by;

selecting qualified outliers from the outlier materialized query table;

for each of the selected outliers, determining a range having the lower bound and the upper bound;

in response to determining that there is an overlapping between ranges, merging the ranges and using the merged ranges for the new range predicate; and

in response to determining that there is no overlapping between ranges, using the ranges for the new range predicate;

introducing the new range predicate into the query by merging the bounds subquery into a portion of the query and adding the new range predicate to the query; and

executing the portion of the query against the one or more relational database tables to retrieve data from one or more data stores.