Estimation and use of access plan statistics

Abstract

In processing a query including a selection criterion on one or more attributes of a relation, a prior statistic generated for a prior different selection criterion on the same one or more attributes of the relation, may be revalidated for use in processing the query, based upon a measure of the entropy of the one or more attributes of the relation. In this way, the re-validation of statistics may be performed more efficiently. Furthermore, attribute groups of a relation for which multi-dimensional indexes are to be formed, are identified by evaluating the correlation of attribute values within tuples of the relation and determining that the correlation of attribute values within tuples of the relation exceeds a threshold.

1 . A method for identifying a group of attributes of a relation for which a multi-dimensional index is to be formed, comprising 
 computing a correlation of attribute values within tuples of the relation, and    forming a multi-dimensional index for a group of attributes within tuples of the relation having a correlation of attribute values in excess of a threshold.    
   
   
       2 . The method of  claim 1 , wherein computing a correlation of attribute values within tuples of the relation comprises collecting a sample of tuples of the relation, and computing correlation of attribute values within the sampled tuples.  
   
   
       3 . The method of  claim 1  wherein a correlation of attribute values is computed as an information gain for those attributes by comparing, for a common set of tuples, a sum of individual entropies of values of each attribute, to a joint entropy of the values of all attributes.  
   
   
       4 . The method of  claim 3 , wherein a measure for the entropy of one or more attributes is generated by computing frequencies of different values for the one or more attributes in tuples of the relation, and combining the measured frequencies into a measure of the entropy of the one or more attributes.  
   
   
       5 . The method of  claim 4 , wherein generating a measure for the entropy of said one or more attributes of said relation further comprises collecting a sample of tuples of the relation, wherein frequencies of different values are computed for tuples in the sample.  
   
   
       6 . The method of  claim 4  wherein combining the measured frequencies comprises determining a number of distinct values for the one or more attributes, and converting the computed frequencies to probabilities by dividing the frequencies by number of distinct values.  
   
   
       7 . The method of  claim 6  wherein combining the measured frequencies further comprises forming a weighted sum of the computed probabilities.  
   
   
       8 . The method of  claim 1  further comprising evaluating attribute groups found to have correlation to identify primary sources of correlation, by determining a mutual information gain by comparing information gain for a group of attributes, to the largest information gain of any sub-group of fewer of the same attributes.  
   
   
       9 . The method of  claim 8  wherein a multi-dimensional index is formed for an attribute group having information gain greater than a threshold, if there is no larger attribute group including the same attributes having a mutual information gain greater than a threshold.  
   
   
       10 . The method of  claim 1  wherein correlation of attribute values is computed for all combinations of attributes of a relation, or alternatively by sampling a set of attribute groups and then evaluating other related groups of those found to have substantial correlation.  
   
   
       11 . A computer system implementing a relational database system including indexes for said relational database, comprising 
 storage for said relational database, including a relation having a plurality of tuples including values for a plurality of attributes, and    computing circuitry performing query execution upon said relational database, and identifying a group of attributes of a relation for which a multi-dimensional index is to be formed, by computing a correlation of attribute values within tuples of the relation, and forming a multi-dimensional index for a group of attributes within tuples of the relation having a correlation of attribute values in excess of a threshold.    
   
   
       12 . A program product for implementing a relational database system, comprising 
 a relational database, including a relation having a plurality of tuples including values for a plurality of attributes,    relational database software performing query execution upon said relational database, and identifying a group of attributes of a relation for which a multi-dimensional index is to be formed, by computing a correlation of attribute values within tuples of the relation, and forming a multi-dimensional index for a group of attributes within tuples of the relation having a correlation of attribute values in excess of a threshold, and    a signal bearing media holding said relational database and relational database software.    
   
   
       13 . The program product of  claim 12  wherein the signal bearing media comprises transmission media.  
   
   
       14 . The program product of  claim 12  wherein the signal bearing media comprises recordable media.