1. A method for generating a statistic for a pattern matching predicate on an attribute of a relation, to be used in optimizing execution of a query directed to one or more attributes of said relation, comprising providing a data storage structure storing character statistics on said attribute, comprising a first structure storing, for each of a plurality of character positions, frequently occurring characters in that character position, and statistics for each frequently occurring character, retrieving said statistics in response to said pattern matching predicate based upon the character positions of characters in said pattern matching predicate, and generating said statistic based upon said retrieved character statistics.