Patent ID: 7149735

Claim:
A method of estimating selectivity of a given string predicate of length n in a database query, comprising: a) estimating selectivities of a plurality of string predicate substrings, the plurality of string predicate substrings including substrings of the given string predicate and having each substring length between q to n, where q<n; b) categorizing each of the string predicate substrings based on length; c) selecting one candidate substring for each category of substring length based on estimated selectivities of the substrings to obtain a plurality of candidate identifying substrings, each candidate identifying substring in the plurality of identifying substrings having a different length between q and n; d) combining the estimated selectivities of each of the candidate substrings in the plurality of identifying substrings; and e) generating the combined estimated selectivities of the candidate substrings as the estimated selectivity of the given string predicate.