Systems, apparatus, methods and computer program products for deleting data of an object within a multi-tenant database via an efficient delete operation are described herein. The new delete operation (or method) may be configured to identify one or more records to be deleted within a data structure such as an object. 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.