A method, apparatus and computer program product selectively delete records from a cache in a manner that not only takes into account usage of the record, but also the cost associated with the generation of the record. In regards to a method, a cost associated with generation of a record maintained in a cache is determined. The cost may be defined in terms of the time consumed to generate the record. The method also determines usage of the record. At least one of the cost or the usage may be determined on a relative basis with respect to the cost or the usage, respectively, of other records maintained in the cache. Further, the method determines whether the record should be deleted from the cache based upon the cost and the usage of the record. Based on this determination, the record may be selectively deleted from or retained within the cache.