Patent ID: 7249120

Claim:
A computer implemented method for approximating a number of tuples returned by a database query to optimize queries on a computerized database that comprises a set of predicates that each reference a set of database tables, the method comprising the steps of: a) determining whether a first estimated selectivity value of the query is stored and returning the stored first estimated selectivity value to approximate the number of tuples returned by the query; b) if a first estimated selectivity value of the query is not stored, expressing the query as an input selectivity value; c) determining if the query is separable based on properties of the input selectivity value; d) if the query is separable: separating the input selectivity value to form a product of query selectivity factors; recursively determining a selectivity value for each query selectivity factor; combining the selectivity values for each query selectivity factor to determine a second estimated selectivity value of the query; e) if the query is not separable: atomically decomposing the input selectivity value to form a product that comprises a conditional selectivity expression, wherein the atomically decomposing step is repeated for one or more atomic decompositions of the input selectivity value to produce a plurality of alternative products that comprise corresponding conditional selectivity expressions; for each of the plurality of alternative products, matching a corresponding conditional selectivity expression with stored statistics to obtain statistics that can estimate a selectivity value of the conditional selectivity expression by: compiling a set of candidate statistics that can be used to estimate the selectivity value of the conditional selectivity expression; selecting candidate statistics to estimate the selectivity value of the conditional selectivity expression based on a selection criteria; and using the statistics to obtain an estimated selectivity value of the conditional selectivity expression; and combining the estimated selectivity values of the conditional selectivity expressions corresponding to each alternative product to determine a third estimated selectivity value of the query; f) storing in memory either the second or third estimated selectivity value of the query based on whether the query is separable.