1. For a database management system to be operatively coupled to a data processing system, a method for optimizing compression of a workload comprising a plurality of queries, the method comprising: estimating a cost to execute the queries; selecting a sub-set of queries from the workload according to a threshold level, the threshold level being a function of the estimated cost to execute the queries; and compressing the selected sub-set of queries.