With respect to the database/table: Throw away the indices and other constraints of the table that is target of the deletion. Otherwise, indices must be rebuilt after every delete, constraints need to be checked. In most cases the contraint check and index rebuilt is much more expensive with respect to the database time than the loss due to the missing index coverage. In particular, your database is quite small, so that the delete-search is not really an issue. The issue of communication time might be improved by sending a larger query batch, if possible.