Method, system, and program for query optimization with algebraic rules
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
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.
-
Specification