A database may delete rows of data based on one or more predicate parameters. A method of data storage includes receiving a delete request for a database, where the delete request includes one or more predicate parameters and adding the predicate parameters to a set of deletion predicate parameters in metadata of the database. The method may further include performing a compaction of the database, where the compaction includes rewriting each data element of the database unless a key of the data element corresponds to at least one of the set of deletion predicate parameters.