A method, information processing system, and computer readable storage product estimate a compression factor. A set of key values within an index are analyzed. Each key value is associated with a record identifier (“RID”) list comprising a set of RIDs. The index is in an uncompressed format and includes a total byte length. A number of RIDs associated with each key value is estimated for each key value in the set of key values. A total byte length for all RID deltas between each at least two consecutive RIDs within a RID list is estimated for each RID list based on the number of RIDs that have been determined. The total byte length estimated for each RID list is accumulated. A compression factor associated with the index is determined by dividing the total byte length that has been accumulated by the byte length of the index.