Abstract:
A system and method for improving cardinality estimation in a relational database management system is provided. The method is suitable for use with a query optimizer for improved estimation of various predicates in the query optimizer&#39;s cost estimation plan by combining pre-computed statistics and information from sampled data. The system and method include sampling a relational database for generating a sample data set and estimating cardinalities of the sample data set. The estimated cardinalities sample data sets are reduced in accordance with the present invention by determining a first and second weight set, and minimizing a distance between the first and second weight set.

Description:
TRADEMARKS 
       [0001]    IBM® is a registered trademark of International Business Machines Corporation, Armonk, New York, U.S.A. Other names used herein may be registered trademarks, trademarks or product names of International Business Machines Corporation or other companies. 
       BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    This invention relates to database management systems and more particularly to a method and system for improved cardinality estimation after applying various predicates in a query optimizer&#39;s plan by combining pre-computed statistics and information from sampled data. 
         [0004]    2. Description of the Related Art 
         [0005]    A database management system (DBMS) comprises the combination of an appropriate computer, direct access storage devices (DASD) or disk drives, and database management software. A relational database management system is a DBMS which uses relational techniques for storing and retrieving information. The relational database management system or RDBMS comprises computerized information storage and retrieval systems in which data is stored on disk drives or DASD for semi-permanent storage. The data is stored in the form of tables which comprise rows and columns. Each row or table has one or more columns. 
         [0006]    The RDBMS is designed to accept commands to store, retrieve, and delete data. One widely used and well known set of commands is based on the Structured Query Language or SQL. The term “query” refers to a set of commands in SQL for retrieving data from the RDBMS. The definitions of SQL provide that a RDBMS should respond to a particular query with a particular set of data given specified database content. SQL however does not specify the actual method to find the requested information in the tables on the disk drives. There are many ways in which a query can be processed and each consumes a different amount of processor and input/output access time. The method in which the query is processed (i.e., a query plan) affects the overall time for retrieving the data. The time taken to retrieve data can be critical to the operation of the database. It is therefore important to select a method for finding the data requested in a query which minimizes the computer and disk access time, and therefore, optimizing the cost of doing the query. 
         [0007]    A database system user retrieves data from the database by entering requests or queries into the database. The RDBMS interprets the user&#39;s query and then determines how best to go about retrieving the requested data. In order to achieve this, the RDBMS has a component called the query optimizer. The RDBMS uses the query optimizer to analyze how to best conduct the user&#39;s query of the database with optimum speed in accessing the database being the primary factor. The query optimizer takes the query and generates a query execution plan. The query plan comprises a translation of the user&#39;s SQL commands in terms of the RDBMS operators. There may be several alternative query plans generated by the query optimizer, each specifying a set of operations to be executed by the RDBMS. 
         [0008]    The many query plans generated for a single query ultimately differ in their total cost of obtaining the desired data. The query optimizer then evaluates these cost estimates for each query plan in order to determine which plan has the lowest execution cost. In order to determine a query plan with the lowest execution cost, the query optimizer uses specific combinations of operations to collect and retrieve the desired data. When a query execution plan is finally selected and executed, the data requested by the user is retrieved according to that specific query plan however manipulated or rearranged. 
         [0009]    Query optimizers in most relational database systems rely on cost estimation of various candidate query execution plans to select a cost effective plan. Accurate plan costing can help avoid intolerably slow plans. A key ingredient in cost estimation is to estimate the selectivity of various predicates in order to obtain the cardinality estimates which are the sizes of the intermediate results. Better cardinality estimation allows the query optimizer to get better query execution plans. 
         [0010]    Before our invention methods for selectivity estimation fall into two broad categories, synopsis-based and sampling-based. Synopsis-based methods, such as histograms, incur minimal overhead at query optimization time and thus are widely used in commercial database systems. Sampling-based methods are more suited for ad-hoc queries, but often involve high I/O cost because of random access to the underlying data. Though both methods serve the same purpose of selectivity estimation, their interaction in the case of selectivity estimation for conjuncts of predicates on multiple attributes is largely unexplored. 
         [0011]    In terms of methodology, existing work on selectivity estimation takes two fundamentally different approaches: one is based on synopsis data structures and the other is based on sampling. 
         [0012]    Synopsis-based approaches seek to pre-compute summary data structures which capture statistics on the data (attribute value distributions). Such synopses are stored in the database catalogs, and subsequently used for estimation when required. A prominent example in this class of approaches is histograms, which have been proposed in recent years, aiming to improve the accuracy of histogram-based selectivity estimation. Almost all major commercial database management systems (e.g., IBM® DB2® Universal Database™ product (DB2 UDB), Oracle, SQL Server) keep some form of histograms in their catalogs and use them for selectivity estimation. 
         [0013]    Sampling-based approaches are more query-driven in nature, in the sense that data is not accessed until optimization time. Given a query, a sample is derived from the database, and selectivities are estimated based on this sample. There exists an extensive literature on sampling-based methods for selectivity estimation. In recent years, all of the major commercial database system vendors have incorporated sampling capabilities into their engines. 
         [0014]    Both prior art approaches have their advantages and disadvantages. Synopsis structures, such as histograms, only need to be computed once and can be used many times while incurring minimal overhead at selectivity estimation time. However, it is difficult to capture all useful information in the limited space. For example, the one-dimensional histograms commonly used in the commercial DBMS&#39;s do not provide correlation information between attributes. Although it is possible to compute multi-dimensional histograms for some attribute combinations, it is generally not feasible to compute and store the multi-dimensional histograms for all attribute combinations, because the number of combinations is exponential in the number of attributes [5]. Without knowing of the query workload, deciding which combinations of attributes to choose in order to construct multi-dimensional histograms can be very difficult. 
         [0015]    Sampling approaches, on the other hand, are able to provide such crucial information through a representative sample of the data. The downside, however, is that sampling at selectivity estimation time incurs non-trivial cost, because in order to obtain a fairly accurate estimate, sometimes a significant portion of the data might have to be accessed. Since sampling requires random access, which is much slower than sequential access, it is possible that the cost of sampling exceeds that of a sequential scan of the data when the sample size is relatively large. 
         [0016]    By way of example, if we are interested in predicates taking the form of Q=P 1 ̂P 2 ̂ . . . ̂P m , where each P i (1≦i≦m) is a simple predicate of the form (attribute op constant) with op being one of the comparison operators &lt;,≦,=,≠,≧, or &gt;. The selectivity s i (∈[0,1]) is defined as the fraction of tuples on which predicate P i  evaluates to true, i.e., s i =N i /N, where N is the number of tuples in the table, and N i  is the number of tuples satisfying P i . The selectivity of the conjuncts of predicates Q, denoted by s Q (∈[0,1]), is the fraction of tuples satisfying all the P i &#39;s simultaneously. s Q  is the quantity to estimate. When there is no ambiguity, for purposes of clarity, this description use s as a shorthand for s Q . 
         [0017]    The query optimizer measures the error of an estimate ŝ by the absolute relative error, as provided in Eq. (1). 
         [0000]    
       
         
           
             
               
                 
                   
                     E 
                      
                     
                       ( 
                       
                         s 
                         ^ 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                          
                         
                           
                             s 
                             ^ 
                           
                           - 
                           s 
                         
                          
                       
                       s 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0018]    The following scenario is used as an example. Consider a table R with N=10,000 tuples and three attributes A i (i=1,2,3). Let P 1 =(A 1 =1), and P 2 =(A 2 =1). For example, if there is a need to estimate the selectivity of the following query: Q=P 1 ̂P 2 . If there are 500 tuples satisfying Q, then the true selectivity of Q is s=500/10000=0.05. 
         [0019]    Synopsis-based estimation. Assume that we have access to synopsis structures for all individual attributes involved such that selectivity estimates s i (1≦i≦m) can be obtained. Without any information regarding the correlation between attributes, optimizers in current database systems estimate s Q  based on the assumption that the values in distinct attributes are independently distributed. In other words, knowing that a tuple satisfies a predicate on one attribute does not give any information as to whether it satisfies a predicate on another. Therefore, s is estimated by taking a product of the selectivity estimates of individual predicates, 
         [0000]    
       
         
           
             
               i 
               . 
               e 
               . 
             
             , 
             
               
                 
                   s 
                   ^ 
                 
                 his 
               
               = 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   m 
                 
                  
                 
                   
                     s 
                     i 
                   
                   . 
                 
               
             
           
         
       
     
         [0020]    In the running example, suppose we have access to single-attribute histograms on A 1  and A 2 , and therefore we can derive the selectivities of the two predicates, namely s 1  and s 2 , from the histograms. Suppose s 1 =0.6, and s 2 =0.3. If we assume A 1  and A 2  are independent, then the selectivity of Q is estimated to be ŝ his =s 1 ·s 2 =0.18, and the error is E(ŝ his )=|0.18−0.05|/0.05=260%. 
         [0021]    This simple estimation scheme gives accurate estimates when the attributes are indeed independent. Real-life data sets, however, almost always demonstrate a certain degree of correlation between attributes, therefore, making the attribute-value independence assumption often leads to erroneous estimates. In the above example, treating the attributes A 1  and A 2  as independent incurs a large error (260%). 
         [0022]    As another example, suppose we have the following query on a CAR table in a vehicle information database: Q=(MAKE=“BMW”)̂(MODEL=“M3”), and we know through one-dimensional histograms that the selectivity of the predicate (MAKE=“BMW”) is 0.1, and that the predicate (MODEL=“M3”) has a selectivity of 0.01. The optimizer then would estimate the selectivity of Q as 0.1×0.01=0.001, as per the attribute-value independence assumption. 
         [0023]    Note, however, that there is strong correlation between the attributes MAKE and MODEL. Because M3 is exclusively made by BMW, all tuples satisfying the predicate MODEL=“M3” would also satisfy the predicate MAKE=“BMW”. Therefore, the selectivity of Q is actually 0.01, 10 times that of the estimated selectivity. 
         [0024]    Sampling-based estimation. Now let us look at how to obtain an estimate of the selectivity based on a sample of the data. Suppose a random sample S of size n is taken from the queried table R of size N, where the inclusion probability (the probability of being selected into the sample) of the j-th tuple is π j . The Horvitz-Thompson (HT) estimator [for the selectivity of the query Q, given the sample S, is 
         [0000]    
       
         
           
             
               
                 
                   
                     s 
                     
                       sp 
                        
                       
                           
                       
                        
                       1 
                     
                   
                   = 
                   
                     
                       1 
                       N 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           S 
                         
                         
                             
                         
                       
                        
                       
                         
                           y 
                           j 
                         
                         
                           π 
                           j 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where y j  is an indicator variable such that y j =1 if tuple j satisfies Q, and y j =0 otherwise. In the case of simple random sampling (SRS), where the inclusion probabilities are all equal to n/N, Eq. (2) simplifies to 
         [0000]    
       
         
           
             
               
                 s 
                 ^ 
               
               
                 sp 
                  
                 
                     
                 
                  
                 1 
               
             
             = 
             
               
                 1 
                 N 
               
                
               
                 
                   ∑ 
                   
                     j 
                     ∈ 
                     S 
                   
                   
                       
                   
                 
                  
                 
                   
                     y 
                     j 
                   
                   . 
                 
               
             
           
         
       
     
         [0025]    In the running example, suppose we tale an SRS S of size n=100 from table R. Clearly, the inclusion probabilities for tuples in R are all equal to 100/10000=0.01. If 9 tuples in the sample satisfy Q, then the HT estimator is ŝ spl =9/100=0.09, and the error is E(ŝ spl )=80%. 
         [0026]    A major problem with the use of sampling is the I/O overhead incurred. Since sampling requires random access to data, it is often the case that even if a very small sample is taken, the associated I/O cost is comparable to that of a full sequential scan of the data. For example, if each page contains 50 tuples, and the sample rate is higher than 2%, essentially all pages have to be accessed because 50×2%=1. 
         [0027]    The prior art shows that the expected fraction f of pages to be accessed for a sample rate of q is given by f=1−(1−q) c , where c is the number of tuples on each page. It is evident that f decreases very fast as the sample rate drops, which means that achieving the same level of accuracy with a lower sample rate, will result in significant I/O savings. 
         [0028]    There is no known previous work exploring the interaction of sampling based and synopsis based approaches in order to make consistent use of both sources of information to get reasonably accurate cardinality estimates and at the same time not rely on a very large sample to do that. Therefore, there exists a need for a hybrid system and method that combines both sampling based and synopsis based query estimations. 
       SUMMARY OF THE INVENTION 
       [0029]    The shortcomings of the prior art are overcome and additional advantages are provided through the provision of a hybrid sampling and synopsis selectivity estimation method and system. Sampling-based methods usually associate with each sampled tuple a sampling weight reflecting its inclusion probability (i.e., the probability of being selected to the sample), which is used to produce a selectivity estimate. Given selectivities of individual predicates P i  (which can be obtained from attribute synopses), in addition to the sample, better estimates may be obtained by adjusting sampling weights, in a way that is consistent with the information on individual selectivities obtained from the synopses. 
         [0030]    In particular, the weights of the tuples in the sample are adjusted, while maintaining the new weights as close as possible to the original weights. New weights that can then be used to obtain improved selectivity estimates are derived via an optimization problem solution. 
         [0031]    In accordance with one embodiment of the present invention a general numerical solution to this optimization problem, as well as an iterative solution based on the intrinsic structure of the problem is provided. Also provided are two different measures of “closeness” between the new weights and the original weights, namely the linear distance function and the multiplicative distance function, and are compared in terms of computational efficiency and interpretability. Also provided are asymptotic bounds on the estimation errors. 
         [0032]    In accordance with another embodiment of the present invention a method for selectivity estimation for conjunctive predicates for use in a query optimizer for a relational database management system is provided. The method includes sampling a relational database for generating a sample data set and estimating cardinalities of the sampled data set. The method also includes iteratively adjusting the estimated cardinalities of the sample data set by determining a first and second weight set and minimizing the distance between the first weight set and the second weight set. 
         [0033]    The invention is also directed towards a relational database management system for improving cardinality estimation for use with a computer system wherein queries are entered for retrieving data. The system includes means for sampling a relational database for generating a sample data set and means for estimating cardinalities of the sampled data set. The system also includes means for reducing the estimated cardinalities of the sample data set via means for determining a first and second weight set and minimizing the distance between the first weight set and the second weight set. 
         [0034]    System and computer program products corresponding to the above-summarized methods are also described and claimed herein. 
         [0035]    Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention. For a better understanding of the invention with advantages and features, refer to the description and to the drawings. 
       TECHNICAL EFFECTS 
       [0036]    As a result of the summarized invention, technically we have achieved a solution by which a program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine performs a method for improving cardinality estimation in a relational database management system. The method includes sampling a relational database for generating a sample data set and determining individual and combined predicates. The method also includes estimating cardinalities of the sampled data set with respect to the individual and combined predicates and reducing the estimated cardinalities of the sampled data set. The program of instructions reduces the cardinalities of the sample data set by first determining a plurality of tuples in the sampled data set and weighting each of the plurality of tuples in the sample data set according to predetermined statistics. The method then determines a second weight set using a distance function to derive the second weight set. The distance function is selected from the group consisting of a linear distance function and a multiplicative distance function and is used to minimize the distance between the first weight set and the second weight set. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0037]    The subject matter which is regarded as the invention is particularly pointed out and distinctly claimed in the claims at the conclusion of the specification. The foregoing and other objects, features, and advantages of the invention are apparent from the following detailed description taken in conjunction with the accompanying drawings in which: 
           [0038]      FIG. 1  is a block diagram showing software components of a relational database management system suitable for a method for estimating cardinalities according to the present invention; 
           [0039]      FIG. 2  is a block diagram showing a data processing system employing the present invention; 
           [0040]      FIG. 3  illustrates one example of a method for computing the calibration estimator in accordance with an embodiment of the present invention; 
           [0041]      FIG. 4  illustrates one example of an alternate method for determining the calibration estimator in accordance with an embodiment of the present invention; 
           [0042]      FIG. 5A  is a graph comparing embodiments of the present invention with prior art methods in terms of accuracy vs. correlation; 
           [0043]      FIG. 5B  is a graph comparing embodiments of the present invention with prior art methods in terms of accuracy vs. data skew; 
           [0044]      FIG. 6A  is a graph comparing embodiments of the present invention with prior art methods in terms of accuracy vs. sample rate; 
           [0045]      FIG. 6B  is a graph comparing embodiments of the present invention with prior art methods in terms of accuracy vs. number of attributes; and 
           [0046]      FIG. 7  is a graph comparing an embodiment of the present invention with prior art methods in terms of accuracy vs. sample rate on Census Income data. 
       
    
    
       [0047]    The detailed description explains the preferred embodiments of the invention, together with advantages and features, by way of example with reference to the drawings. 
       DETAILED DESCRIPTION OF THE INVENTION 
       [0048]    Reference is made to  FIG. 1  which shows in block diagram form a Relational Database Management System or RDBMS system  10  suitable for use with a method according to the present invention. One skilled in the art will be familiar with how a RDBMS is implemented. Such techniques are straightforward and well known in the art. Briefly, the RDBMS  10  comprises a client application module  12  and a server module  14  as shown in  FIG. 1 . One of the functions of the server  14  is to process the SQL query entered by the database user. The server  14  comprises a relational data services and SQL compiler  16 . The SQL compiler  16  includes a plan optimization module  18  or query optimizer. The primary function of the query optimizer  18  is to find an access strategy or query plan that would incur or result in minimum processing time and input/output time for retrieving the information requested by the user. In  FIG. 1 , the query plan is represented by block  20 . 
         [0049]    Reference is next made to  FIG. 2  which shows a data processing system  22  incorporating the present invention. The data processing system  22  comprises a central processing unit  24 , a video display  26 , a keyboard  28 , random access memory  30  and one or more disk storage devices  32 . One skilled in the art will recognize the data processing system  22  a conventional general purpose digital computer. In  FIG. 2 , the relational database management system  10  incorporating the present invention includes a software module which includes a query optimizer, and which is stored or loaded on the disk storage device  32 . Data items, e.g. cards, tables, rows, etc. which are associated with the relational database management system  10  can be stored on the same disk  32  or on another disk  34 . 
         [0050]    The method, a hybrid approach to selectivity estimation for conjunctive predicates (HASE), according to the invention makes consistent use of synopses and sample information when both present. To achieve this goal, the method uses a novel estimation scheme utilizing a powerful mechanism called generalized raking. The method formalizes selectivity estimation in the presence of single attribute synopses and sample information as a constrained optimization problem. By solving this problem, the method obtains a new set of weights associated with the sampled tuples, which has the advantageous property of reproducing the known selectivities when applied to individual predicates. 
         [0051]    It will be understood that the description presented herein will be mainly concerned with selectivity estimation for conjunctive predicates of the form Q=P 1 ̂P 2  . . . P m  where each component P i  is a simple predicate on a single attribute, taking the form of (attribute op constant) with op being one of the comparison operators &lt;,≦,=,≠,≧, or &gt;(e.g., R.a=100 or R.a≦200). 
       Calibration 
       [0052]    For example, for a sample of data with known selectivities of individual predicates P i . The method begins with an estimator constructed based on the sample only, without reference to any additional information, such as the HT estimator (Eq. (2)). For each tuple j in table R, in addition to the variable of interest y j , the method in accordance with the invention also associates with it an auxiliary vector x j  to reflect the results of evaluating P i  on j. For purposes of this example, each predicate P i  divides tuples in R into two disjoint subsets, D i  and  D   i , according to whether they satisfy the predicate or not. Also for purposes of this example, further define D m+1 =R i.e., j ∈ D m+1  for all j. Let x j  be a column vector of length m+1: x j   T =(x j1 , . . . ,x jm ,x j,m+1 ), with the i-th (1≦i≦m+1) element being 1 if j ∈ D i , and 0 otherwise. For instance, in the running example described above, x j   T =(1,0,1) indicates that tuple j satisfies P 1 , but not P 2 . 
         [0053]    Let t x   T =(t x1 , . . . ,t xm ,t x,m+1 )=1/N Σ j∈R  x j . Clearly, t xi =1/N Σ j∈S  x ji =s i  (1≦i≦m), the selectivity of predicate P i , and t x,m+1 =1. Therefore, 
         [0000]        t   x   T =( s   1   ,s   2   , . . . ,s   m ,1)   (3) 
         [0054]    Also, for purposes of this example s i  can be obtained based on synopsis structures, and x j  are observed for each tuple j ∈ S. This allows construction of a new estimator (the calibration estimator) 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         s 
                         ^ 
                       
                       cal 
                     
                     = 
                     
                       
                         1 
                         N 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             S 
                           
                           
                               
                           
                         
                          
                         
                           
                             w 
                             j 
                           
                            
                           
                             y 
                             j 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the weights w j  are as close to the weights d j =1/π j  as possible according to some distance metric (recall that π j  is the inclusion probability of j), and where 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         1 
                         N 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             S 
                           
                           
                               
                           
                         
                          
                         
                           
                             w 
                             j 
                           
                            
                           
                             y 
                             j 
                           
                         
                       
                     
                     = 
                     
                       t 
                       x 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    meaning that the weighted average of the observed x j  has to reproduce the known selectivities s i . 
         [0055]    In light of the definition of x j  and Eq. (3), Eq. (5) can be rewritten as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         1 
                         N 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             
                               S 
                               ⋂ 
                               
                                 D 
                                 i 
                               
                             
                           
                           
                               
                           
                         
                          
                         
                           w 
                           j 
                         
                       
                     
                     = 
                     
                       s 
                       i 
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     i 
                     = 
                     1 
                   
                   , 
                   2 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     m 
                     + 
                     1. 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where s m+1 =s. Now w j  has a natural representation interpretation: it is the number of tuples “represented” by the sampled tuple j. 
         [0056]    In the running example, Eq. (6) becomes 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         1 
                         10000 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             
                               S 
                               ⋂ 
                               
                                 D 
                                 1 
                               
                             
                           
                           
                               
                           
                         
                          
                         
                           w 
                           j 
                         
                       
                     
                     = 
                     0.6 
                   
                   , 
                   
                     
                       
                         1 
                         10000 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             
                               S 
                               ⋂ 
                               
                                 D 
                                 2 
                               
                             
                           
                           
                               
                           
                         
                          
                         
                           w 
                           j 
                         
                       
                     
                     = 
                     0.3 
                   
                   , 
                   
                     
                       and 
                        
                       
                           
                       
                        
                       
                         1 
                         10000 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             S 
                           
                           
                               
                           
                         
                          
                         
                           w 
                           j 
                         
                       
                     
                     = 
                     1 
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0057]    Although in general, there can be many possible choices for the sets of weights {w j } satisfying the constraints in Eq. (6), the goal of the method is to select a set of new weights that are as close as possible to the original weights d i =1/π i , which enjoy the desirable property of producing unbiased estimates. By keeping the distance between the new weights and the original weights as small as possible, in accordance with one method of the invention, the new weights remain nearly unbiased. Thus, the method advantageously provides a constrained optimization solution as described herein. 
         [0058]    The constrained optimization solution. Let D(x) be a distance function (with x=w j /d j ) that measures the distance between the new weights w j  and the original weights d j . The query optimizer assures that D(x) satisfies the following requirements (for reasons that will become clear later): (i) D is positive and strictly convex, (ii) D(1)=D′(1)=0, and (iii) D″(1)=1. The optimization for the method to determine is: 
       Minimize 
       [0059]    
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       j 
                       ∈ 
                       S 
                     
                     
                         
                     
                   
                    
                   
                     
                       d 
                       j 
                     
                      
                     
                       D 
                        
                       
                         ( 
                         
                           
                             w 
                             j 
                           
                           / 
                           
                             d 
                             j 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    subject to 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       1 
                       N 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           S 
                         
                         
                             
                         
                       
                        
                       
                         
                           w 
                           j 
                         
                          
                         
                           x 
                           j 
                         
                       
                     
                   
                   = 
                   
                     
                       t 
                       x 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0060]    Here, both x j  and t x  are defined earlier. Since D(w j /d j ) can have a large response to even a slight change in w j  when d j  is small, the query optimizer minimizes Σ j∈S  d j D(w j /d j ) instead of Σ j∈S  D(w j /d j ) in order to dampen this effect. Also note that different distance functions can be used to measure the distance between {w j } and {d j }, as long as the distance function complies with conditions (i) to (iii). 
         [0061]    Alternative methods of the invention can choose different distance functions. For example, the following two distance functions may be chosen for computational efficiency and interpretability. Both of these distance functions exhibit properties (i) to (iii): 
         [0062]    The linear distance function 
         [0000]    
       
         
           
             
               
                 D 
                 
                   lin 
                    
                   
                     ( 
                     
                       
                         w 
                         j 
                       
                       / 
                       
                         d 
                         j 
                       
                     
                     ) 
                   
                 
               
               = 
               
                 
                   1 
                   2 
                 
                  
                 
                   
                     ( 
                     
                       
                         
                           w 
                           j 
                         
                         
                           d 
                           j 
                         
                       
                       - 
                       1 
                     
                     ) 
                   
                   2 
                 
               
             
             , 
           
         
       
     
         [0000]    and 
         [0063]    The multiplicative distance function: 
         [0000]    
       
         
           
             
               D 
               
                 mul 
                  
                 
                   ( 
                   
                     
                       w 
                       j 
                     
                     / 
                     
                       d 
                       j 
                     
                   
                   ) 
                 
               
             
             = 
             
               
                 
                   
                     w 
                     j 
                   
                   
                     d 
                     j 
                   
                 
                  
                 log 
                  
                 
                     
                 
                  
                 
                   
                     w 
                     j 
                   
                   
                     d 
                     j 
                   
                 
               
               - 
               
                 
                   w 
                   j 
                 
                 
                   d 
                   j 
                 
               
               + 
               1 
             
           
         
       
     
       It will be appreciated that any suitable distance function may be chosen. 
       [0064]    In accordance with features of the present invention the following methods may be used to solve the constrained optimization problem. One method for solving constrained optimization problems is the method of Lagrange multipliers. Note that the optimization problem can states as follows: 
       Minimize 
       [0065]    
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         j 
                         ∈ 
                         S 
                       
                       
                           
                       
                     
                      
                     
                       
                         d 
                         j 
                       
                        
                       
                         D 
                          
                         
                           ( 
                           
                             
                               w 
                               j 
                             
                             / 
                             
                               d 
                               j 
                             
                           
                           ) 
                         
                       
                     
                   
                   - 
                   
                     
                       λ 
                       T 
                     
                     ( 
                     
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             S 
                           
                           
                               
                           
                         
                          
                         
                           
                             w 
                             j 
                           
                            
                           
                             x 
                             j 
                           
                         
                       
                       - 
                       
                         Nt 
                         x 
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0000]    with respect to w j (j ∈ S),
 
where λ=(λ 1 , . . . ,λ m ,λ m+1 ) is a Lagrange multiplier. Differentiating Eq. (10) with respect to w j , to obtain:
 
         [0000]        D′ ( w   j   /d   j )−x j   T λ=0   (11) 
         [0066]    Then solve the system formed by Eq. (11) and (9) for w j . To do this, obtain from (11) that 
         [0000]        w   j   =d   j   F ( x   j   T λ),   (12) 
         [0000]    where F(x) is the inverse function of D′(x). Conditions (i)-(iii) dictate that the inverse function always exists, and F(0)=F′(0)=1. Substituting (12) into Eq. (9), results in the calibration equations 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           S 
                         
                         
                             
                         
                       
                        
                       
                         
                           d 
                           j 
                         
                          
                         
                           F 
                            
                           
                             ( 
                             
                               
                                 x 
                                 j 
                                 T 
                               
                                
                               λ 
                             
                             ) 
                           
                         
                          
                         
                           x 
                           j 
                         
                       
                     
                     = 
                     
                       Nt 
                       x 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0000]    which can be solved numerically using Newton&#39;s method. 
         [0000]    
       
         
           
             
               Let 
                
               
                   
               
                
               
                 φ 
                  
                 
                   ( 
                   λ 
                   ) 
                 
               
             
             = 
             
               
                 
                   
                     ∑ 
                     
                       j 
                       ∈ 
                       S 
                     
                     
                         
                     
                   
                    
                   
                     
                       d 
                       j 
                     
                      
                     
                       F 
                        
                       
                         ( 
                         
                           
                             x 
                             j 
                             T 
                           
                            
                           λ 
                         
                         ) 
                       
                     
                      
                     
                       x 
                       j 
                     
                   
                 
                 - 
                 
                   
                     
                       Nt 
                       x 
                     
                     . 
                     
                       
 
                     
                      
                     Then 
                   
                    
                   
                       
                   
                    
                   
                     
                       φ 
                       ′ 
                     
                      
                     
                       ( 
                       λ 
                       ) 
                     
                   
                 
               
               = 
               
                 
                   
                     ∂ 
                     
                       φ 
                        
                       
                         ( 
                         λ 
                         ) 
                       
                     
                   
                   / 
                   
                     ∂ 
                     λ 
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       j 
                       ∈ 
                       S 
                     
                     
                         
                     
                   
                    
                   
                     
                       d 
                       j 
                     
                      
                     
                       
                         F 
                         ′ 
                       
                        
                       
                         ( 
                         
                           
                             x 
                             j 
                             T 
                           
                            
                           λ 
                         
                         ) 
                       
                     
                      
                     
                       x 
                       j 
                     
                      
                     
                       
                         x 
                         j 
                         T 
                       
                       . 
                     
                   
                 
               
             
           
         
       
     
         [0067]    Then obtain successive estimates of λ, denoted by λ k  (k=0,1, . . . ), through the following iteration: 
         [0000]      λ k+1 =λ k +[φ′(λ k )] −1 φ(λ k )   (14) 
         [0000]    take λ 0 =0. Since one has 
         [0000]    
       
         
           
             
               
                 φ 
                  
                 
                   ( 
                   0 
                   ) 
                 
               
               = 
               
                 
                   
                     
                       ∑ 
                       
                         j 
                         ∈ 
                         S 
                       
                       
                           
                       
                     
                      
                     
                       
                         d 
                         j 
                       
                        
                       
                         F 
                          
                         
                           ( 
                           0 
                           ) 
                         
                       
                        
                       
                         x 
                         j 
                       
                     
                   
                   - 
                   
                     Nt 
                     x 
                   
                 
                 = 
                 
                   
                     
                       ∑ 
                       
                         j 
                         ∈ 
                         S 
                       
                       
                           
                       
                     
                      
                     
                       
                         d 
                         j 
                       
                        
                       
                         x 
                         j 
                       
                     
                   
                   - 
                   
                     Nt 
                     x 
                   
                 
               
             
             , 
             
               
 
             
              
             and 
           
         
       
       
         
           
             
               
                 
                   φ 
                   ′ 
                 
                  
                 
                   ( 
                   0 
                   ) 
                 
               
               = 
               
                 
                   
                     ∑ 
                     
                       j 
                       ∈ 
                       S 
                     
                     
                         
                     
                   
                    
                   
                     
                       d 
                       j 
                     
                      
                     
                       
                         F 
                         ′ 
                       
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                      
                     
                       x 
                       j 
                     
                      
                     
                       x 
                       j 
                       T 
                     
                   
                 
                 = 
                 
                   
                     ∑ 
                     
                       j 
                       ∈ 
                       S 
                     
                     
                         
                     
                   
                    
                   
                     
                       d 
                       j 
                     
                      
                     
                       x 
                       j 
                     
                      
                     
                       x 
                       j 
                       T 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    the first iteration yields λ 1 =(Σ j∈S  d j x j x j   T ) −1 (Σ j∈S  d j x j −Nt x ). The subsequent values of λ k  can be obtained following Eq. (14) until convergence. 
         [0068]    In summary, the method to estimate the selectivity of Q is presented in  FIG. 3 . Continuing the running example, the true frequencies obtained by evaluating the query Q on table R, and the observed frequency information based on a simple random sample S are given in Tables 1(a) and 1(b) showing true frequencies and observed frequencies from the sample, respectively (both tables are normalized so that all frequencies sum up to 1). The last row and column in each table correspond to the marginal frequencies. 
         [0069]    From Table 1(a) and Table 1(b), it is seen that the true selectivity of Q is 0.05 (the cell corresponding to P 1 =truêP 2 =true in  FIG. 1(   a )), and the sampling-based selectivity estimate is 0.09 (the cell corresponding to P 1 =trueΛP 2 =true in Table 1(b)). 
         [0000]    
       
         
               
             
               
               
               
               
             
               
               
               
               
               
             
           
               
                 TABLE 1(a) 
               
             
             
               
                   
               
               
                 True frequencies 
               
             
          
           
               
                   
                 P 2  = true 
                 P 2  = false 
                 — 
               
               
                   
                   
               
             
          
           
               
                   
                 P 1  = true 
                 0.05 
                 0.55 
                 .60 
               
               
                   
                 P 1  = false 
                 0.25 
                 0.15 
                 .40 
               
               
                   
                 — 
                 .30 
                 .70 
               
               
                   
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
               
               
             
               
               
               
               
               
             
           
               
                 TABLE 2(b) 
               
             
             
               
                   
               
               
                 Observed frequencies 
               
             
          
           
               
                   
                 P 2  = true 
                 P 2  = false 
                 — 
               
               
                   
                   
               
             
          
           
               
                   
                 P 1  = true 
                 0.09 
                 0.56 
                 .65 
               
               
                   
                 P 1  = false 
                 0.24 
                 0.11 
                 .35 
               
               
                   
                 — 
                 .33 
                 .67 
               
               
                   
                   
               
             
          
         
       
     
         [0070]    Clearly, the marginal frequencies obtained from the sample do not agree with the true marginal frequencies; therefore, calibration is needed. Applying the method shown in  FIG. 3  to solve the calibration equations as shown in Eq. (7), obtains the following calibrated weights (using the multiplicative distance function): 
         [0000]      w j ≈60 for j ∈ S∩D 1 ∩D 2 ,w j ≈102 for j ∈ S∩D 1 ∩  D   2    
         [0000]      w j ≈97 for j ∈ S∩  D   1 ∩D 2 ,w j ≈140 for j ∈ S∩  D   1 ∩  D   2 . 
         [0071]    The selectivity estimate can then be determined: 
         [0000]    
       
         
           
             
               
                 s 
                 ^ 
               
               cal 
             
             = 
             
               
                 
                   1 
                   N 
                 
                  
                 
                   
                     ∑ 
                     
                       j 
                       ∈ 
                       S 
                     
                     
                         
                     
                   
                    
                   
                     
                       w 
                       j 
                     
                      
                     
                       y 
                       j 
                     
                   
                 
               
               = 
               
                 
                   
                     1 
                     N 
                   
                    
                   
                     
                       ∑ 
                       
                         j 
                         ∈ 
                         
                           S 
                           ⋂ 
                           
                             D 
                             1 
                           
                           ⋂ 
                           
                             D 
                             2 
                           
                         
                       
                       
                           
                       
                     
                      
                     
                       w 
                       j 
                     
                   
                 
                 = 
                 
                   
                     60 
                     × 
                     
                       9 
                       / 
                       10000 
                     
                   
                   = 
                   
                     0.054 
                     . 
                   
                 
               
             
           
         
       
     
         [0072]    The estimation error is E(ŝ cal )=|0.054−0.05|/0.05=8%. Compared with the error of the prior art synopsis-based estimate E(ŝ his )=260% and the error of the prior art sampling-based estimate E(ŝ spl )=80%, this method represents a significant improvement in the estimation accuracy. 
         [0073]    An alternative implementation. Now is presented an alternative method for solving the calibration equations, which takes advantage of the intrinsic structure of the equations in (6) and does not require matrix inversion. 
         [0074]    Since w j =d j F(x j   T λ), Eq. (6) becomes 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         1 
                         N 
                       
                        
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             
                               S 
                               ⋂ 
                               
                                 D 
                                 1 
                               
                             
                           
                           
                               
                           
                         
                          
                         
                           
                             d 
                             j 
                           
                            
                           
                             F 
                              
                             
                               ( 
                               
                                 
                                   x 
                                   j 
                                   T 
                                 
                                  
                                 λ 
                               
                               ) 
                             
                           
                         
                       
                     
                     = 
                     
                       s 
                       i 
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     i 
                     = 
                     1 
                   
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     m 
                     + 
                     1. 
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0075]    Observe that the i-th Eq. (2≦i≦m) can be solved for λ i , assuming all other λ l (l≠i) are known, and the first and last equations can be solved for λ 1  and λ m+1  assuming all other λ l (l≠1,l≠m+1) are known. 
         [0076]    This method is shown in  FIG. 4 . It will be appreciated that such an iterative procedure converges to a proper solution, and in the case of multiplicative distance functions, this method yields a variant of the classical iterative proportional fitting algorithm. Replacing lines 6 to 11 in  FIG. 3  with the method shown in  FIG. 4  results in an alternative estimation method. 
         [0077]    Distance measures. We now present the implications of the choice of distance functions D described earlier. In general, different distance functions result in different calibration estimators. However, it will be understood that regardless of the distance functions used (as long as the functions comply with conditions (i)-(iii)), the estimates obtained using the outcome of the specific optimization problem will converge asymptotically. 
         [0078]    Therefore, for medium to large sized samples (empirically, with sample size greater than 30), the choice of distance function does not have a heavy impact on the properties of the estimator; in general only slight differences in the estimates produced by using different functions will arise. 
         [0079]    The main difference between the distance functions is thus their computational efficiency as well as interpretability. 
         [0080]    For the linear function, D lin , D′(x)=x−1; therefore, the inverse function is F(z)=z+1. In  FIG. 2 , it is can be verified that λ converges at 
         [0000]      λ 1 =(Σ j∈S    d   j   x   j   x   j   T ) −1 (Σ j∈S    d   j   x   j   −t   x ). 
         [0081]    Therefore, when the linear function is used, only one iteration is required, which makes the linear method the faster of the two distance functions considered here. A major drawback of this function is that the weights can be negative. This can lead to negative selectivity estimates. For instance, in the running example, taking a sample of size 10 from R, and the observed frequencies are the following: P 1 =true∩P 2 =true: 2; P 1 =true,P 2 =false: 5; P 1 =false∩P 2 =true: 3; P 1 =false∩P 2 =false: 0. Solving the calibration equation, results in w j =−500 for j ∈ S∩D 1 ∩D 2 . Therefore, the selectivity estimate ŝ cal =2×(−500)/10000=−0.1. Negative weights and selectivity estimates do not have a natural interpretation and thus are undesirable. Note that, however, this usually only occurs for small-sized samples. When the sample size gets large, all estimators with distance functions satisfying conditions (i)-(iii) are asymptotically equivalent and give positive weights and selectivity estimates. 
         [0082]    For the multiplicative function, D mul , D′(x)=log x; the inverse function is therefore F(z)=e z . When the multiplicative function is used, it may require more than one iteration, but it often converges after only a few iterations (typically two in our experiments). An advantage of using this function is that it always leads to positive weights because w j =d j F(x j   T λ)=d j  exp {x j   T λ}&gt;0. 
         [0083]    Probabilistic bounds on the estimation error. Let π jl  be the probability that both j and l are included in the sample, and π jj =π j . Assuming that the sampling scheme is such that the π jl &#39;s are strictly positive. Let β be a vector satisfying the equation 
         [0000]    
       
         
           
             
               
                 ∑ 
                 
                   j 
                   ∈ 
                   R 
                 
                 
                     
                 
               
                
               
                 
                   d 
                   j 
                 
                  
                 
                   
                     x 
                     j 
                   
                    
                   
                     ( 
                     
                       
                         y 
                         j 
                       
                       - 
                       
                         
                           x 
                           j 
                           T 
                         
                          
                         β 
                       
                     
                     ) 
                   
                 
               
             
             = 
             0 
           
         
       
     
         [0000]    and let Δ jl =π jl −π j π l , ε j =y j −x j   T β. Which gives the following result on the error bounds of the estimation error. When the sample size is sufficiently large, for a given constant α ∈ (0,1), the selectivity s Q  is bounded by (ŝ cal −z α/2 √{square root over (V(ŝ cal ))},ŝ cal +z α/2 √{square root over (V(ŝ cal ))} with probability 1−α, where z α/2  is the upper alp ha/2 point of the standard normal distribution, and V(ŝ cal )=Σ j∈R  Σ j∈R  (Δ jl /π jl )(w j ε j )(w l ε i ). 
         [0084]    Proof Sketch: When the linear distance function is used, w j =d j (1+x j   T λ). We know from Section 3.5 that the solution of the calibration equation converges at λ=(Σ j∈S  d j x j x j   T ) −1 (Σ j∈S  d j x j −t x ). Therefore, w j =d j [1+x j   T (Σ j∈S  d j x j x j   T ) −1 (Σ j∈S  d j x j −t x )]. Let {circumflex over (β)} s  be the solution to the equation 
         [0000]    
       
         
           
             
               
                 ∑ 
                 
                   j 
                   ∈ 
                   S 
                 
                 
                     
                 
               
                
               
                 
                   d 
                   j 
                 
                  
                 
                   
                     x 
                     j 
                   
                    
                   
                     ( 
                     
                       
                         y 
                         j 
                       
                       - 
                       
                         
                           x 
                           j 
                           T 
                         
                          
                         
                           
                             β 
                             ^ 
                           
                           s 
                         
                       
                     
                     ) 
                   
                 
               
             
             = 
             0. 
           
         
       
     
         [0085]    Then the estimator ŝ cal  can be written as 
         [0000]    
       
         
           
             
               
                 
                   s 
                   ^ 
                 
                 cal 
               
               = 
               
                 
                   
                     1 
                     N 
                   
                    
                   
                     
                       ∑ 
                       
                         j 
                         ∈ 
                         S 
                       
                       
                           
                       
                     
                      
                     
                       
                         w 
                         j 
                       
                        
                       
                         y 
                         j 
                       
                     
                   
                 
                 = 
                 
                   
                     
                       s 
                       ^ 
                     
                     
                       sp 
                        
                       
                           
                       
                        
                       1 
                     
                   
                   + 
                   
                     
                       1 
                       N 
                     
                      
                     
                       
                         ( 
                         
                           
                             t 
                             x 
                           
                           - 
                           
                             
                               ∑ 
                               
                                 j 
                                 ∈ 
                                 S 
                               
                               
                                   
                               
                             
                              
                             
                               
                                 d 
                                 j 
                               
                                
                               
                                 x 
                                 j 
                               
                             
                           
                         
                         ) 
                       
                       T 
                     
                      
                     
                       
                         β 
                         ^ 
                       
                       s 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    which takes the form of a generalized regression estimator (GREG). Applying results on the asymptotic variance of GREG to obtain the asymptotic variance of the estimator ŝ cal : 
         [0000]    
       
         
           
             
               V 
                
               
                 ( 
                 
                   
                     s 
                     ^ 
                   
                   cal 
                 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 
                   j 
                   ∈ 
                   R 
                 
                 
                     
                 
               
                
               
                 
                   ∑ 
                   
                     j 
                     ∈ 
                     R 
                   
                   
                       
                   
                 
                  
                 
                   
                     ( 
                     
                       
                         Δ 
                         jl 
                       
                       / 
                       
                         π 
                         jl 
                       
                     
                     ) 
                   
                    
                   
                     ( 
                     
                       
                         w 
                         j 
                       
                        
                       
                         ɛ 
                         j 
                       
                     
                     ) 
                   
                    
                   
                     
                       ( 
                       
                         
                           w 
                           l 
                         
                          
                         
                           ɛ 
                           l 
                         
                       
                       ) 
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0086]    Since it has been shown that all estimators with distance functions satisfying conditions (i)-(iii) are asymptotically equivalent, all estimators have the same asymptotic variance V(ŝ cal ). When the sample S is large enough, the Central Limit Theorem applies. Therefore, for a given constant or α ∈ (0,1), s Q  is bounded by (ŝ cal −z α/2 √{square root over (V(ŝ cal ))}, ŝ cal +z α/2 √{square root over (V(ŝ cal ))} with probability 1−α. 
         [0087]    Utilizing multi-attribute synopses. In the discussion, it has been assumed that there is prior knowledge of the selectivities s i  of individual predicates P i  based on single-attribute synopsis structures. However, it will be understood that the estimation procedure can be advantageously extended so that multi-attribute synopsis structures can also be utilized when they are present. 
         [0088]    For example, suppose that a multi-dimensional synopsis exists on a set of attributes A. Thus, in accordance with one method of the invention it is straightforward to derive lower-dimensional synopses from higher-dimensional synopses, i.e., synopses on any subset(s) of A can be obtained from the synopsis on A. Let A Q  be the set of attributes involved in query Q. If A∩A Q ≠Ø, the synopsis on A can be utilized. Let U=A∩A Q , and let P U  be the conjuncts of predicates in which attributes in U are involved. Then the selectivity s U  of P U  can be estimated based on the synopsis on U. We augment the auxiliary vector x j  by an additional element reflecting whether j satisfies P U . Changes are also made accordingly to t x , with the addition of an element with value s U . The algorithms for solving the calibration equations presented above can then be applied in order to obtain ŝ cal . 
         [0089]    Experimental evaluation. This section reports the results of an experimental evaluation of the estimation methods disclosed herein. The following compares the accuracy of the methods in accordance with the invention with that of the synopsis-based and sampling-based approaches using synthetic as well as a real data set. The real data set used is the Census Income data. 
         [0090]    Synthetic data are used to study the properties of the methods presented herein in a controlled manner. A large number of synthetic data sets are generated by varying the following parameters: 
         [0091]    Data skew: The data in each attribute are generated from a Zipfian distribution with parameter z ranging from 0 (uniform distribution) to 3 (highly-skewed distribution). The number of distinct values in each attribute is fixed to 10. 
         [0092]    Correlation: By default, the data are independently generated for each attribute. We introduce correlation between a pair of attributes by transforming the data such that the correlation coefficient between the two attributes is approximately ρ. The parameter ρ ranges from 0 to 1, representing an increasing degree of correlation. In particular, ρ=0 corresponds to the case where there is no correlation between the two attributes; ρ=1 indicates that the two attributes are fully dependent, i.e., knowing the value of one attribute enables one to perfectly predict the value of the other attribute. This is achieved by first independently generating the data for both attributes (say, A 1  and A 2 ) and then performing the following transformation. For each tuple with A i =a 1  and A 2 =a 2 , replace a 2  by a 1 ×ρ+a 2 ×√{square root over (1−p 2 )}, suitably rounded. For three or more attributes, create data such that the correlation coefficient between any pair of attributes is approximately ρ. 
         [0093]    The real data set Census Income contains weighted census data extracted from the 1994 and 1995 population surveys conducted by the U.S. Census Bureau. It has 199,523 tuples and 40 attributes representing demographic and employment related information. Out of the 40 attributes, 7 are continuous, and 33 are nominal. 
         [0094]    The following evaluates the methods presented herein on two different query workloads. The first set of queries consist of 100 range queries where each predicate in the query takes the form of (attribute&lt;=constant) with randomly chosen constant. The second set of queries consist of 100 equality queries where each predicate takes the form of (attribute=constant) where constant is randomly chosen. 
         [0095]    It will also be appreciated that simple random sampling are used as the sampling scheme in the experiments for both the sampling-based approach and the methods presented herein. All numbers reported are averages of 30 repetitions. 
         [0096]    It will also be understood that the exact frequency distributions of individual attributes as the synopses are used, and that the absolute relative error defined in Eq. (1) is used as the error metric. 
         [0097]    Results on synthetic data. In all experiments, similar trends are observed for both range and equality queries; thus only the results on range queries are reported because of space limitations. 
         [0098]    First the effects of various parameters in the case of two attributes (i.e., only two predicates on two different attributes are involved in the query) are shown, and then show the effect of the number of attributes on the estimation accuracy. The individual selectivities are obtained based on the frequencies of values in each attribute. Since results indicate that the number of tuples T in the table does not have a significant effect on the accuracy of the estimators, only the results for T=100,000 are shown here. 
         [0099]    Correlation. The effect of the correlation between attributes on the estimation accuracy by varying the correlation coefficient ρ from 0 to 1, representing an increasing degree of correlation. are shown.  FIG. 5A  presents a typical result. 
         [0100]    The accuracy of the methods in accordance with the present invention increase with the degree of correlation. Since the methods utilize sample information, when the degree of correlation increases, the number of distinct value combinations in the two attributes decreases, as the data become more “concentrated”. Therefore, the sample space (containing all distinct value combinations) becomes smaller, and thus sampling becomes more efficient (i.e., for a given sample rate, it is more likely to include in the sample a tuple satisfying the query). 
         [0101]    In addition, as the degree of correlation increases, the benefit of adjusting the weights in accordance with known single-attribute synopses becomes more evident. In the extreme case where the two attributes are fully dependent (ρ=1), it essentially produces the exact selectivity, provided that there is at least one tuple in the sample satisfying the query. 
         [0102]    To understand why this is the case, consider the following query: Q=P 1 ∩P 2 =(A 1 =a)∩(A 2 =b). Full dependency dictates that if there is at least one tuple in the table satisfying this query, then for any other value c (c≠a)in A 1  and d (d≠b) in A 2 , both (A 1 =a)∩(A 2 =d) and (A 1 =c)∩(A 2 =b) evaluate to false. This implies that s=s 1 =s 2 . 
         [0103]    Therefore, if in the auxiliary vector x j  for tuple j, we have x j1 =1 (which corresponds to A 1 =a), then y j (the variable indicating whether j satisfies Q) must also be 1, and vice versa. Since we know s 1 , we have 
         [0000]    
       
         
           
             
               
                 1 
                 N 
               
                
               
                 
                   ∑ 
                   
                     j 
                     ∈ 
                     S 
                   
                   
                       
                   
                 
                  
                 
                   
                     w 
                     j 
                   
                    
                   
                     x 
                     
                       j 
                        
                       
                           
                       
                        
                       1 
                     
                   
                 
               
             
             = 
             
               s 
               1 
             
           
         
       
     
         [0000]    as a constraint in the optimization problem. If we can find a set of w j  that satisfy this constraint, then the calibration estimator 
         [0000]    
       
         
           
             
               1 
               N 
             
              
             
               
                 ∑ 
                 
                   j 
                   ∈ 
                   S 
                 
                 
                     
                 
               
                
               
                 
                   w 
                   j 
                 
                  
                 
                   y 
                   j 
                 
               
             
           
         
       
     
         [0000]    must also yield s 1 , which means a perfect selectivity estimate. 
         [0104]    One exception to this analysis is that when there is no tuple j ∈ S satisfying Q, it may no longer be possible to produce the exact estimate. In such cases, all y j (j ∈ S) are 0; therefore, regardless of the weights, the calibration estimator 1/N Σ j∈S  w j y j  will also be zero, which may be different from the exact selectivity. 
         [0105]    In all cases, the methods disclosed herein produce significantly more accurate estimates than the sampling-based method, with a 50%-100% reduction in error. Both distance functions give very close estimates, verifying the claim that estimators using different distance functions are asymptotically equivalent. 
         [0106]    Data skew. The effect of data skew by varying the Zipfian parameter z from 0 (uniform) to 3 (highly-skewed), a typical result is shown in  FIG. 5(   b ) It will be seen that the errors increase as the data becomes increasingly more skewed. The reason is that when the data skew in each attribute increases, the frequencies of some value combinations decrease. As a result, when there is a query on those value combinations with low occurrence frequencies, it becomes increasingly possible that no sampled tuple can satisfy the query. This gives rise to more errors, because with no sampled tuple satisfying the query, the estimate has to be zero, whereas the actual selectivities are not. 
         [0107]    Note that this situation is different from the case of increasing correlation as discussed above. The main effect of increasing the skew is a decrease in the frequencies of some value combinations, not necessarily reducing the number of value combinations present in the table. Increasing correlation, on the other hand, generally results in a reduction in the number of value combinations. 
         [0108]    Another interesting observation from  FIG. 5(   b ) is that the accuracy of the prior art synopsis-based approach remains virtually the same regardless of the data skew. The reason is as follows. Assuming independence between attributes, the synopsis-based approach estimates the selectivity by ŝ his =s 1 *s 2  In  FIG. 5(   b ), the two attributes are fully dependent, which implies that the actual selectivity s=s 1 =s 2 . Thus, E(ŝ his )=(s−s 1 s 2 )/s 1 =1−s 1 . The average error over a large number of (uniformly) randomly selected equality queries is therefore 1−avg(s 1 ). In this case, since there are 10 distinct values in each attribute, avg(s 1 )=1/10=0.1 the average error of the estimate is thus 1−0.1=0.9. Therefore, the accuracy of this approach does not change with data skew in this case. 
         [0109]    Sample rate  FIG. 6A  shows a typical result on how the three methods behave as the sample rate is increased. The number of attributes in the data set is 2. The accuracy of the synopsis-based approach remains unchanged across the range of sample rates, because it does not depend on sampling. It will be appreciated that the accuracy of the methods presented herein, in accordance with the present invention, improves with increasing sample rate. For all sample rates, the methods disclosed herein, in accordance with the present invention, improve outperform both the synopsis-based and the sampling-based approaches. 
         [0110]    It is also worth noting that with methods of the present invention, the same level of accuracy with a much smaller sample rate than that required by the sampling-based approach may be achieved. For example, in  FIG. 6A , the sampling-based approach has an error of 0.07 when the sample rate is 0.005. The methods presented herein achieve approximately the same level of accuracy with a sample rate of 0.001, resulting in a reduction by a factor of 5. It will be appreciated that this translates into more significant I/O savings because of the non-linear relationship between the I/O cost and the sample rate as discussed earlier. 
         [0111]    Number of attributes. The number of attributes involved in the query range from 2 to 5 to study the impact of the number of attributes on the estimation accuracy. A typical result is shown in  FIG. 6B . Clearly, the accuracy of all three approaches decreases as the number of attributes increases since having more attributes would introduce more sources of errors. A space of higher dimensionality requires a much larger sample to cover a fixed portion of the space, in comparison with a space of lower dimensionality. 
         [0112]    Note from  FIG. 6B , however, that the methods disclosed herein disclosed herein, in accordance with the present invention, outperforms the other two prior art approaches for all number of attributes, and has a lower rate of decrease in accuracy. 
         [0113]    Results on real data. Since the Census Income data has 40 attributes, there are 40×39=1560 attribute pairs. Randomly choosing 100 attribute pairs and recording the accuracy of the methods disclosed herein with prior art approaches, as the sample rate increases, results in  FIG. 7 . It will be seen that the trends are similar to those for the synthetic data, with the methods of the present invention significantly outperforming both the synopsis-based and the sampling-based approaches. The error response to the number of attributes is also similar to that for the synthetic data, and is therefore omitted here. 
         [0114]    It will be understood that the capabilities of the present invention can be implemented in software, firmware, hardware or some combination thereof. 
         [0115]    As one example, one or more aspects of the present invention can be included in an article of manufacture (e.g., one or more computer program products) having, for instance, computer usable media. The media has embodied therein, for instance, computer readable program code means for providing and facilitating the capabilities of the present invention. The article of manufacture can be included as a part of a computer system or sold separately. 
         [0116]    Additionally, at least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform the capabilities of the present invention can be provided. 
         [0117]    The flow diagrams depicted herein are just examples. There may be many variations to these diagrams or the steps (or operations) described therein without departing from the spirit of the invention. For instance, the steps may be performed in a differing order, or steps may be added, deleted or modified. All of these variations are considered a part of the claimed invention. 
         [0118]    While the preferred embodiment to the invention has been described, it will be understood that those skilled in the art, both now and in the future, may make various improvements and enhancements which fall within the scope of the claims which follow. These claims should be construed to maintain the proper protection for the invention first described.