Elements of a database object are removed. The database object is stored as a plurality of different object portions, where each object portion is associated with one or more versions of transaction identifiers stored separately from the database object. An oldest transaction identifier is determined for a transaction for which data portions of the database object remains visible. Each object portion is examined and object portions with a threshold amount of data to remove are determined based on a comparison of the transaction identifiers for those object portions and the oldest transaction identifier. Data from the database object are removed in response to a sufficient quantity of data is to be removed from object portions containing the threshold amount of data.