Method and apparatus for exploiting statistics on query expressions for optimization

Abstract

A method for evaluating a user query on a relational database having records stored therein, a workload made up of a set of queries that have been executed on the database, and a query optimizer that generates a query execution plan for the user query. Each query plan includes a plurality of intermediate query plan components that verify a subset of records from the database meeting query criteria. The method accesses the query plan and a set of stored intermediate statistics for records verified by query components, such as histograms that summarize the cardinality of the records that verify the query component. The method forms a transformed query plan based on the selected intermediate statistics (possibly by rewriting the query plan) and estimates the cardinality of the transformed query plan to arrive at a more accurate cardinality estimate for the query. If additional intermediate statistics are necessary, a pool of intermediate statistics may be generated based on the queries in the workload by evaluating the benefit of a given statistic over the workload and adding intermediate statistics to the pool that provide relatively great benefit.

1. In a relational database having records stored therein and having a query optimizer that generates a query execution plan wherein each query plan comprises a plurality of intermediate query plan components that verify a subset of records from the database meeting query criteria, a method for evaluating a user query comprising the steps of:
 accessing the query plan and a set of stored intermediate statistics for records verified by query components of the query plan;  
 selecting intermediate statistics and applying them to the query plan to form a transformed query plan; and  
 estimating the cardinality of the transformed query plan.  
 
   
   
     2. The method of  claim 1  wherein an intermediate statistic comprises a cardinality of the records verified by a given query component. 
   
   
     3. The method of  claim 1  wherein an intermediate statistic is a histogram that describes the records verified by a given query component. 
   
   
     4. The method of  claim 1  comprising the step of rewriting the query plan to incorporate intermediate statistics. 
   
   
     5. The method of  claim 1  wherein the intermediate statistics are viewed as hypothetical base tables having statistics on a given attribute by the query optimizer. 
   
   
     6. The method of  claim 1  wherein the step of selecting intermediate statistics is performed by selecting a set of intermediate statistics that minimizes a number of independence assumptions that will be made in evaluating the query plan according to the selected set. 
   
   
     7. The method of  claim 1  wherein the step of selecting intermediate statistics is performed by:
 selecting an intermediate statistic that minimizes a number of independence assumptions that will be made in evaluating the query plan and adding the selected statistic to a set of selected statistics;  
 selecting an intermediate statistic that, when applied in conjunction with the selected set minimizes a number of independence assumptions that will be made in evaluating the query plan and adding the selected statistic to the set of selected statistics; and  
 continuing to select intermediate statistics for the set of selected statistics until no new intermediate statistic can be applied.  
 
   
   
     8. The method of  claim 1  wherein the relational database has a workload comprising a set of queries that have been executed on the database and comprising the step of generating a pool of intermediate statistics to be stored for query plan evaluation based on the queries in the workload. 
   
   
     9. The method of  claim 1  wherein at least one of the stored intermediate statistics is generated by approximating a result of a query component and computing statistics on the approximate result. 
   
   
     10. For use in a relational database having records stored therein and having a query optimizer that generates a query execution plan wherein each query plan comprises a plurality of intermediate query plan components that verify a subset of records from the database meeting query criteria, a computer-readable medium comprising computer executable instructions for performing a method for evaluating a user query comprising the steps of:
 accessing the query plan and a set of stored intermediate statistics for records verified by query components of the query plan;  
 selecting intermediate statistics and applying them to the query plan to form a transformed query plan; and  
 estimating the cardinality of the transformed query plan.  
 
   
   
     11. The computer-readable medium of  claim 10  wherein the step of selecting intermediate statistics is performed by selecting a set of intermediate statistics that minimizes a number of independence assumptions that will be made in evaluating the query plan according to the selected set. 
   
   
     12. The computer-readable medium of  claim 10  wherein the step of selecting intermediate statistics is performed by:
 selecting an intermediate statistic that minimizes a number of independence assumptions that will be made in evaluating the query plan and adding the selected statistic to a set of selected statistics;  
 selecting an intermediate statistic that, when applied in conjunction with the selected set minimizes a number of independence assumptions that will be made in evaluating the query plan and adding the selected statistic to the set of selected statistics; and  
 continuing to select intermediate statistics for the set of selected statistics until no new intermediate statistic can be applied.  
 
   
   
     13. The computer-readable medium of  claim 10  wherein the relational database has a workload comprising a set of queries that have been executed on the database and comprising the step of generating a pool of intermediate statistics to be stored for query plan evaluation based on the queries in the workload. 
   
   
     14. For use in a relational database having records stored therein and having a query optimizer that generates a query execution plan wherein each query plan comprises a plurality of intermediate query plan components that verify a subset of records from the database meeting query criteria, an apparatus for evaluating a user query comprising:
 a query plan access tool for accessing the query plan and a set of stored intermediate statistics for records verified by query components of the query plan;  
 an intermediate statistic selector for selecting intermediate statistics and applying them to the query plan to form a transformed query plan; and  
 a cardinality estimator for estimating the cardinality of the transformed query plan.  
 
   
   
     15. The apparatus of  claim 14  comprising a query plan rewriter that rewrites the query plan to incorporate intermediate statistics. 
   
   
     16. The apparatus of  claim 14  wherein the intermediate statistic selector selects a set of intermediate statistics that minimizes a number of independence assumptions that will be made in evaluating the query plan according to the selected set. 
   
   
     17. The apparatus of  claim 14  wherein the intermediate statistic selector selects intermediate statistics by:
 selecting an intermediate statistic that minimizes a number of independence assumptions that will be made in evaluating the query plan and adding the selected statistic to a set of selected statistics;  
 selecting an intermediate statistic that, when applied in conjunction with the selected set minimizes a number of independence assumptions that will be made in evaluating the query plan and adding the selected statistic to the set of selected statistics; and  
 continuing to select intermediate statistics for the set of selected statistics until no new intermediate statistic can be applied.  
 
   
   
     18. The apparatus of  claim 14  wherein the relational database has a workload comprising a set of queries that have been executed on the database and wherein the apparatus comprises an intermediate statistic generator for generating a pool of intermediate statistics to be stored for query plan evaluation based on the queries in the workload. 
   
   
     19. For use in a relational database having records stored therein and having a query optimizer that generates a query execution plan wherein each query plan comprises a plurality of intermediate query plan components that verify a subset of records from the database meeting query criteria, an apparatus for evaluating a user query comprising:
 means for accessing the query plan and a set of stored intermediate statistics for records verified by query components of the query plan;  
 means for selecting intermediate statistics and applying them to the query plan to form a transformed query plan; and  
 means for estimating the cardinality of the transformed query plan.  
 
   
   
     20. The apparatus of  claim 19  comprising a means for rewriting the query plan to incorporate intermediate statistics. 
   
   
     21. The apparatus of  claim 19  wherein the means for selecting intermediate statistics selects a set of intermediate statistics that minimizes a number of independence assumptions that will be made in evaluating the query plan according to the selected set. 
   
   
     22. The apparatus of  claim 19  wherein the means for selecting intermediate statistics selects intermediate statistics by:
 selecting an intermediate statistic that minimizes a number of independence assumptions that will be made in evaluating the query plan and adding the selected statistic to a set of selected statistics;  
 selecting an intermediate statistic that, when applied in conjunction with the selected set minimizes a number of independence assumptions that will be made in evaluating the query plan and adding the selected statistic to the set of selected statistics; and  
 continuing to select intermediate statistics for the set of selected statistics until no new intermediate statistic can be applied.  
 
   
   
     23. The apparatus of  claim 19  wherein the relational database has a workload comprising a set of queries that have been executed on the database and wherein the apparatus comprises a means for generating a pool of intermediate statistics to be stored for query plan evaluation based on the queries in the workload.