A first workload that contains logged predicates contained in database queries is received. A subset of the predicates is selected based on costs associated with the predicates. A compressed workload is formed using the selected subset of the predicates. Indexes are then selected based on the compressed workload.