Computer program product for choosing largest selectivities among eligible predicates of join equivalence classes for query optimization

• US 5,542,073 A
• Filed: 08/01/1995
• Issued: 07/30/1996
• Est. Priority Date: 01/07/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Schiefer, Klaus B., Swami, Arun N.
• Primary Examiner(s): Amsbury, Wayne
• Application Number:
  US08/510,078
• Time in Patent Office: 364 Days
• Field of Search: 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

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.

Claims

1. A computer program product for use in a query optimizer in a relational database computer system wherein selectivity values for each eligible join predicate are known comprising:

a recording medium;

means, recorded on said recording medium, for instructing said computer system to determine the equivalence classes for a plurality of join attributes; and

means, recorded on said recording medium, for instructing said computer system, for each equivalence class to;

1) determine the eligible join predicates belonging to each of said equivalence classes; and

2) choose the largest selectivity among said eligible join predicates in each of said equivalence classes.