Method for choosing largest selectivities among eligible predicates of join equivalence classes for query optimization
First Claim
1. A method for determining and selecting join selectivities for use by a query optimizer to improve the performance of a query in a relational database management system including a computer having memory, wherein the query optimizer is coupled to the memory of the computer and is adapted to execute the steps of the method in the memory, and wherein selectivity values for each eligible join predicate are known, said method comprising the machine-executed steps of:
- determining the equivalence classes for a plurality of join attributes; and
for each equivalence class performing the machine-executed steps of;
a) determining the eligible join predicates belonging to each of said equivalence classes; and
b) selecting the largest selectivity among said eligible join predicates in each of said equivalence classes.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for choosing join selectivities in a query optimizer in a relational database management system is disclosed which facilitates the estimation of join result sizes by a query optimizer in a relational database system, wherein a new relation R is to be joined with an intermediate relation I, and wherein the selectivity values for each eligible join predicate are known. The method has the steps of determining the equivalence classes for a plurality of join attributes and then computing for each relation an estimate of the cardinality and the number of distinct values in each attribute after all the local predicates have been included. These are used in further computation of join selectivities and join result sizes. The join predicates must then be processed by correctly choosing the join selectivities. The join result sizes can then be correctly calculated.
63 Citations
8 Claims
-
1. A method for determining and selecting join selectivities for use by a query optimizer to improve the performance of a query in a relational database management system including a computer having memory, wherein the query optimizer is coupled to the memory of the computer and is adapted to execute the steps of the method in the memory, and wherein selectivity values for each eligible join predicate are known, said method comprising the machine-executed steps of:
determining the equivalence classes for a plurality of join attributes; and
for each equivalence class performing the machine-executed steps of;a) determining the eligible join predicates belonging to each of said equivalence classes; and b) selecting the largest selectivity among said eligible join predicates in each of said equivalence classes. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
8. A relational database management system having a database computer, the computer having memory, wherein queries are entered on the computer for data retrieval, wherein selectivity values for each eligible join predicate are known, said system comprising:
means coupled with the memory for executing the queries, the means including; a) means for parsing queries; b) means for query optimization for operating on said parsed queries to generate a query execution plan; c) means for determining the equivalence classes for a plurality of join attributes identified in the queries; d) means for determining the eligible join predicates belonging to each of said equivalence classes; and e) means for selecting the largest selectivity among said eligible join predicates.
Specification