A predicate over a single column of a table is converted into at least one IN-list, wherein the IN-list is generated for a set of tuples of the column, and the generation is done over a data structure representing a set of distinct values of the column where the predicate applies and having a smaller cardinality than the table. The generated IN-list is evaluated over the set of tuples and the results of the evaluation are outputted as an evaluation of the predicate.