Patent Document ID: 20050004907
Application ID: 10608083
Patent Flag: 0

Claim One:
1. A method for approximating a number of tuples returned by a database query that comprises a set of predicates that each reference a set of database tables, the method comprising the steps of: a) expressing the query as a query selectivity; b) determining if the query is separable and if so separating the query selectivity to form a product of query selectivity factors; c) if the query is not separable, decomposing the query selectivity to form a product that comprises a conditional selectivity expression; d) recursively performing steps b)-f) to determine a selectivity value for each query selectivity factor; e) matching any conditional selectivity expression with stored statistics to obtain statistics that can estimate the selectivity of the conditional selectivity expressions and using the statistics to obtain an estimated selectivity value; and f) combining the Selectivity values obtained in step d) and the estimated selectivity values obtained in step e) to estimate the selectivity of the query.