Patent ID: 7483888

Claim:
A computer storage media for predicting a selectivity of a set of at least one logical query condition for querying a database, said at least one logical query condition comprising at least one join condition for joining multiple tables of said database, said storage media comprising: a plurality of computer-executable instructions stored on said computer storage media, wherein said instructions, when executed by at least one computer system, cause the at least one computer system to perform the steps of: (a) identifying at least one skewed value for a first field of said database specified in said at least one join condition; (b) for each skewed value identified by said step of identifying at least one skewed value, constructing a corresponding set of one or more hypothetical query predicates, each hypothetical query predicate of said set of hypothetical query predicates corresponding to a respective query condition of said set of at least one logical query condition, wherein each respective said hypothetical query predicate is constructed by replacing each occurrence of said first field in the corresponding query condition with a constant equal to the skewed value corresponding to the set of hypothetical query predicates containing the hypothetical query predicate; (c) predicting a respective selectivity for each said set of hypothetical query predicates; and (d) predicting a composite selectivity for said set of at least one logical query condition using the respective selectivity for each said set of hypothetical query predicates; wherein said step of predicting a respective selectivity for each said set of hypothetical query predicates comprises accessing at least one respective index for each of at least one hypothetical query predicate, and predicting a number of records satisfying each said at least one hypothetical query predicate using said respective index.