A method for data storage includes representing logical volumes by respective sets of pointers to physical partitions in which data used by the logical volumes is stored. One or more of the logical volumes are defined as provisionally deleted. A subset of the provisionally-deleted logical volumes is selected such that each logical volume in the subset has one or more private physical partitions whose data is used exclusively by that logical volume. One or more of the private physical partitions of the logical volumes in the subset are released for reallocation to another logical volume.