Redundant join elimination and sub-query elimination using subsumption
First Claim
1. A computer-implemented method for optimizing a query in a relational database management system, wherein the computer performs the following functions comprising:
- evaluating the query to determine whether a sub-expression of the query is being joined to itself and whether a predicate of the query comprises an equality test between a same column of the sub-expression;
determining whether a first row set producible from a first set of references of the query to the sub-expression is subsumed by a second row set producible from a second set of references of the query to the sub-expression; and
reforming the query to eliminate the joining of the sub-expression to itself based on evaluation of the query and determination of whether the first row set is subsumed by the second row set.
2 Assignments
0 Petitions
Accused Products
Abstract
A method, computer readable medium, and system for optimizing a query in a relational database processing system is disclosed. The present invention relates to a query rewrite optimization method for eliminating a redundant join and equivalent subquery in an SQL query before generation and selection of the optimal query execution plan. The method of the present invention includes evaluating the query to identify a join predicate joining a sub-expression of the query to itself, and determining whether a row set producible from a first set of references of the query to the sub-expression is subsumed by a row set producible from a second set of references of the query to the sub-expression. Based on such evaluation and determination, the query may be reformed to eliminate the join predicate and the second quantifier. A further determination of the removability of the second quantifier may be required such as by evaluating a cardinality constraint when query output cardinality is material.
80 Citations
27 Claims
-
1. A computer-implemented method for optimizing a query in a relational database management system, wherein the computer performs the following functions comprising:
-
evaluating the query to determine whether a sub-expression of the query is being joined to itself and whether a predicate of the query comprises an equality test between a same column of the sub-expression; determining whether a first row set producible from a first set of references of the query to the sub-expression is subsumed by a second row set producible from a second set of references of the query to the sub-expression; and reforming the query to eliminate the joining of the sub-expression to itself based on evaluation of the query and determination of whether the first row set is subsumed by the second row set. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A computer readable medium containing a computer program for optimizing a query in a relational database management system, the computer program comprising program instructions for:
-
evaluating the query to determine whether a sub-expression of the query is being joined to itself and whether a predicate of the query comprises an equality test between a same column of the sub-expression; determining whether a first row set producible from a first set of references of the query to the sub-expression is subsumed by a second row set producible from a second set of references of the query to the sub-expression; and reforming the query to eliminate the joining of the sub-expression to itself based on evaluation of the query and determination of whether the first row set is subsumed by the second row set. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A computer-implemented query optimizer system for optimizing a query in a relational database management system, wherein the computer performs the following functions comprising:
-
means for evaluating the query to determine whether a sub-expression of the query is being joined to itself and whether a predicate of the query comprises an equality test between a same column of the sub-expression; means for determining whether a first row set producible from a first set of references of the query to the sub-expression is subsumed by a second row set producible from a second set of references of the query to the sub-expression; and means for reforming the query to eliminate the joining of the sub-expression to itself based on the means for evaluating the query and the means for determining whether the first row set is subsumed by the second row set. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
-
Specification