Evaluating LIKE predicates against compressed data. An alphabet, a LIKE predicate, a compressed string, and a compression dictionary for the compressed string are received. Entries in the compression dictionary include a character string and an associated token. The LIKE predicate is converted to an equivalent pattern matching form, involving a search pattern of length m. For each character of the alphabet that appears in a string associated with a token, a mask of predetermined length k is created. For each entry in the compression dictionary a cumulative mask of length k is computed. A bit vector of length k is initialized, based on the search pattern. Successive tokens in the compressed string are processed using a logical shift of the bit vector and a bitwise operation of the bit vector with the cumulative mask associated with the token.