In token compression, a column value is represented by a encoded token. During early predicate evaluation, the result that a decoded token in a column does not satisfy a predicate condition in a predicate conjunction is recorded in a cache as a “FALSE”. Such a result not only means that when the column contains that token that the predicate condition is not satisfied, but also that a predicate conjunction containing the predicate condition is not satisfied. When performing early predicate evaluation on a subsequent row on a token in a column, the conjunction result cache is referred to. If the cache records a FALSE for that token in that column, then it is known the predicate conjunction cannot be satisfied by the decoded token.