Patent ID: 7519611

Claim:
A method of using a compressed trie to estimate a number of rows in a data table that match a like predicate, the method comprising: for each child node of a root node of the trie, examining the child by: removing a longest matching prefix of the like predicate and the child from the like predicate and the child; determining if the remaining child has a length of zero; matching based on the like predicate when the remaining child has length of zero; and matching based on the like predicate and the child when the remaining child does not have a length of zero; and transforming a value representing the estimated number of rows in the data table that match the like predicate in accordance with matching of the compressed trie to the like predicate, the transforming enabling the number of rows in the data table that match the like predicate to be estimated, the method being executed on a computer comprising a processor and a memory.