Self Tuning Database Retrieval Optimization Using Regression Functions

Abstract

A system and method for accessing a relational database and estimating the selectivity of a query (e.g., an SQL query) in order to better predict the number of qualifying records for simple and complex queries. A dataset is created based upon queries applied against the database by the user community. The dataset is populated with information related to query conditions and their respective combinations. A regression function reflecting correlations between query conditions is generated and used as a data mining model to calculate table-specific estimates for the cardinality of subsequent queries. An appropriate access method is then selected from a set of available access methods based upon the number of estimated query-qualifying records. By periodically updating the regression model with FIFO managed queries, a self-tuning mechanism is achieved resulting in better selectivity/result size estimates for use in selecting access methods used in compiling subsequent SQL queries applied against the database.

1 - 15 . (canceled) 
   
   
       16 . A computer system for estimating a selectivity of a query containing at least one column-associated condition related to column attributes of a relational database table, the system comprising:
 a sampling module for generating a dataset by sampling queries applied against the database, wherein the dataset includes a plurality of query conditions and information related to combinations of said query conditions,   a regression module for determining at least one regression function that reflects correlations between particular query conditions based on said dataset,   a processing module for determining a table-specific estimate of a cardinality of a query based upon the regression function serving as a data mining model, and   an update module to synchronize at least one regression function with said database by updating that at least one regression function based on recently applied queries.   
   
   
       17 . The system of  claim 16 , wherein the processing module selects an access method for an incoming query from a plurality of database access methods based upon the table-specific estimate for said incoming query. 
   
   
       18 . The system of  claim 16 , wherein said query includes column associated conditions related to a plurality of tables, and wherein the processing module determines a table-combining cardinality estimate based upon said table-specific estimate. 
   
   
       19 . The system of  claim 16 , wherein the sampling module further comprises:
 a dataset module for generating a dataset including queries q j , j=1, . . . N, wherein each query includes a plurality of column-associated conditions c jk , k=1, . . . M j , N, M being integer variables, wherein said dataset module further comprises:
 a first storage module for storing a cardinality C of an elementary operation associated with a column-associated condition c jk , 
 a second storage module for storing a count of query-qualifying database records reflecting the correlation between the database table column attributes referred to in each elementary operation, 
   wherein the processing module further comprises:
 an estimation module for determining a cardinality estimate CE of said query with the following formula: 
   
     
       
         
           
             CE 
             = 
             
               
                 ∑ 
                 
                   
                     i 
                     = 
                     1 
                   
                   , 
                   
                       
                   
                    
                   
                     … 
                      
                     
                         
                     
                      
                     L 
                   
                 
               
                
               
                   
               
                
               
                 f 
                  
                 
                   ( 
                   
                     Z 
                     i 
                   
                   ) 
                 
               
             
           
         
       
     
     wherein f (Z i ) is a regression function, CE is a total of correlations between the plurality of combinations of elementary operations used in said sampled queries, and Z i  is a frequency of occurrence for one or more column-associated conditions c jk , and
 wherein the regression module further comprises:
 a function module for generating said regression function using said data mining model. 
 
 
   
   
       20 . The system of  claim 19 , wherein the processing module estimates the cardinality of each of the plurality of column-associated conditions c jk  referring to the same column using the data mining model. 
   
   
       21 . The system of  claim 16 , wherein the processing module trains the model by using queries that include logical AND operators to determine a correlation between corresponding column predicates. 
   
   
       22 . The system of  claim 16 , wherein the processing module transforms a query containing OR predicates to an equivalent query containing AND predicates to simplify training of a model. 
   
   
       23 . The system of  claim 16 , wherein the processing module normalizes the determined cardinality based upon a current total number of rows in the database table. 
   
   
       24 . The system of  claim 16 , wherein the processing module normalizes the cardinality associated with a sampled query with a size of the database table when the query is sampled, and denormalizes a cardinality associated with a query for which a cardinality is to be predicted with the size of the database table when the selectivity for that query is predicted. 
   
   
       25 . A program product apparatus having a computer readable medium with computer program logic recorded thereon for estimating a selectivity of a query containing at least one column-associated condition related to column attributes of a relational database table, said program product apparatus comprising:
 a sampling module for generating a dataset by sampling queries applied against the database, wherein the dataset includes a plurality of query conditions and information related to combinations of said query conditions,   a regression module for determining at least one regression function that reflects correlations between particular query conditions based on said dataset,   a processing module for determining a table-specific estimate of a cardinality of a query based upon the regression function serving as a data mining model, and   an update module to synchronize at least one regression function with said database by updating that at least one regression function based on recently applied queries.   
   
   
       26 . The program product of  claim 25 , wherein the processing module selects an access method for an incoming query from a plurality of database access methods based upon the table-specific estimate for said incoming query. 
   
   
       27 . The program product of  claim 25 , wherein said query includes column associated conditions related to a plurality of tables, and wherein the processing module determines a table-combining cardinality estimate based upon said table-specific estimate. 
   
   
       28 . The program product of  claim 25 , wherein the sampling module further comprises:
 a dataset module for generating a dataset including queries q j , j=1, . . . N, wherein each query includes a plurality of column-associated conditions c jk , k=1, . . . M j , N, M being integer variables, wherein said dataset module further comprises:
 a first storage module for storing a cardinality C of an elementary operation associated with a column-associated condition c jk , 
 a second storage module for storing a count of query-qualifying database records reflecting the correlation between the database table column attributes referred to in each elementary operation, 
   wherein the processing module further comprises:
 an estimation module for determining a cardinality estimate CE of said query with the following formula: 
   
     
       
         
           
             CE 
             = 
             
               
                 ∑ 
                 
                   
                     i 
                     = 
                     1 
                   
                   , 
                   
                       
                   
                    
                   
                     … 
                      
                     
                         
                     
                      
                     L 
                   
                 
               
                
               
                   
               
                
               
                 f 
                  
                 
                   ( 
                   
                     Z 
                     i 
                   
                   ) 
                 
               
             
           
         
       
     
     wherein f (Z i ) is a regression function, CE is a total of correlations between the plurality of combinations of elementary operations used in said sampled queries, and Z i  is a frequency of occurrence for one or more column-associated conditions c jk , and
 wherein the regression module further comprises:
 a function module for generating said regression function using said data mining model. 
 
 
   
   
       29 . The program product of  claim 28 , wherein the processing module estimates the cardinality of each of the plurality of column-associated conditions c jk  referring to the same column using the data mining model. 
   
   
       30 . The program product of  claim 25 , wherein the processing module trains the model by using queries that include logical AND operators to determine a correlation between corresponding column predicates.—