1. A method of estimating selectivity of a given string predicate in a database query, comprising: a) estimating selectivities of string predicate substrings of various substring lengths; b) selecting a candidate substring for each substring length based on estimated selectivities of the substrings; c) combining the estimated selectivities of the candidate substrings; and d) returning the combined estimated selectivities of the candidate substrings as the estimated selectivity of the given string predicate.