Disclosed are examples of systems, apparatus, methods and computer program products for deleting data of an object within a multi-tenant database. Described is a mechanism for performing operations such as an efficient delete operation by introducing a new delete operation (or method) that is configured to allow a data structure such as an object to identify one or more records to be deleted. In order to ensure that the operation is efficient, the mechanism may determine characteristics of a data store and determine whether the information provided within the data structure provides an efficient identification of the data to be deleted. Upon a successful validation, an initial delete request may be translated to an appropriate delete operation for the underlying database.