METHOD,SYSTEM, AND PROGRAM FOR QUERY OPTIMIZATION WITH ALGEBRAIC RULES

• US 20070226180A1
• Filed: 05/25/2007
• Published: 09/27/2007
• Est. Priority Date: 11/25/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: CHENG, Qi, PIRAHESH, Mir, SUN, Yang, ZUZARTE, Calisto
• Granted Patent: US 7,945,557 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

Disclosed is technique for executing a query. A set of algebraic rules applicable to the 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 the 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:

identifying a set of algebraic rules applicable to the query, wherein each of the algebraic rules represents a relationship between two columns in a relational database table;

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, 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; and

for each of the one or more candidate target columns,

deriving a bounds subquery that provides a lower bound and an upper bound for a new range predicate; and

introducing the new range predicate into the query, wherein the query is executed to retrieve data from one or more data stores.

2. The method of claim 1, further comprising:

merging the new range predicate into the query.

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 the set of algebraic rules is represented by an outlier materialized query table and 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 4, wherein a candidate target column is from a same table as the one 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 7, wherein the candidate target column is from a table other than the one 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 one of hardware logic and a computer readable medium including a program for executing a query, wherein the hardware logic or program causes operations to be performed, the operations comprising:

identifying a set of algebraic rules applicable to the query, wherein each of the algebraic rules represents a relationship between two columns in a relational database table;

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, 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; and

for each of the one or more candidate target columns,

deriving a bounds subquery that provides a lower bound and an upper bound for a new range predicate; and

introducing the new range predicate into the query, wherein the query is executed to retrieve data from one or more data stores.

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

merging the new range predicate into the query.

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 the set of algebraic rules is represented by an outlier materialized query table and 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 14, wherein a candidate target column is from a same table as the one 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 17, wherein the candidate target column is from a table other than the one 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:

means for identifying a set of algebraic rules applicable to the query, wherein each of the algebraic rules represents a relationship between two columns in a relational database table;

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

means for identifying one or more candidate target columns 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; and

for each of the one or more candidate target columns,

means for deriving a bounds subquery that provides a lower bound and an upper bound for a new range predicate; and

means for introducing the new range predicate into the query, wherein the query is executed to retrieve data from one or more data stores.