A computing system for providing improved column imprints that are correlated to an expected workload, comprising: one or more memories (1020, 1025); one or more processing units (1010, 1015) coupled to the one or more memories (1020, 1025); and one or more computer readable storage media storing computer-executable instructions specifying operations for: receiving a plurality of first queries, wherein respective first queries of the plurality of first queries specify a lower bound value and an upper bound value for a value type; determining a plurality of unique values for the value type in a data set, the data set being partitioned into a plurality of discrete data subsets; defining a plurality of bins based on upper bounds and lower bounds specified by the plurality of first queries and on weights assigned to the plurality of unique values, wherein a given bin of the plurality of bins comprises at least one unique value of the plurality of unique values; determining a cost of placing a first bin boundary on one of the upper or lower bounds based on the weights, wherein the weights are determined based on a number of queries that request a value and/or a number of times a value occurs in the data set, wherein the first bin boundary defines the at least one unique value associated with at least one bin of the plurality of bins; iteratively defining additional bin boundaries based on costs associated with such definitions, wherein the costs are determined based on any previously defined bin boundaries; and defining an imprint for at least one discrete data subset of the plurality of discrete data subsets, wherein, for each bin of the plurality of bins, the imprint identifies whether a unique value associated with a given bin is present in the at least one discrete data subset. one or more memories (1020, 1025); one or more processing units (1010, 1015) coupled to the one or more memories (1020, 1025); and one or more computer readable storage media storing computer-executable instructions specifying operations for: receiving a plurality of first queries, wherein respective first queries of the plurality of first queries specify a lower bound value and an upper bound value for a value type; determining a plurality of unique values for the value type in a data set, the data set being partitioned into a plurality of discrete data subsets; defining a plurality of bins based on upper bounds and lower bounds specified by the plurality of first queries and on weights assigned to the plurality of unique values, wherein a given bin of the plurality of bins comprises at least one unique value of the plurality of unique values; determining a cost of placing a first bin boundary on one of the upper or lower bounds based on the weights, wherein the weights are determined based on a number of queries that request a value and/or a number of times a value occurs in the data set, wherein the first bin boundary defines the at least one unique value associated with at least one bin of the plurality of bins; iteratively defining additional bin boundaries based on costs associated with such definitions, wherein the costs are determined based on any previously defined bin boundaries; and defining an imprint for at least one discrete data subset of the plurality of discrete data subsets, wherein, for each bin of the plurality of bins, the imprint identifies whether a unique value associated with a given bin is present in the at least one discrete data subset. receiving a plurality of first queries, wherein respective first queries of the plurality of first queries specify a lower bound value and an upper bound value for a value type; determining a plurality of unique values for the value type in a data set, the data set being partitioned into a plurality of discrete data subsets; defining a plurality of bins based on upper bounds and lower bounds specified by the plurality of first queries and on weights assigned to the plurality of unique values, wherein a given bin of the plurality of bins comprises at least one unique value of the plurality of unique values; determining a cost of placing a first bin boundary on one of the upper or lower bounds based on the weights, wherein the weights are determined based on a number of queries that request a value and/or a number of times a value occurs in the data set, wherein the first bin boundary defines the at least one unique value associated with at least one bin of the plurality of bins; iteratively defining additional bin boundaries based on costs associated with such definitions, wherein the costs are determined based on any previously defined bin boundaries; and defining an imprint for at least one discrete data subset of the plurality of discrete data subsets, wherein, for each bin of the plurality of bins, the imprint identifies whether a unique value associated with a given bin is present in the at least one discrete data subset.