It would be helpful if you mention the index structure on both the tables involved in delete operation.

Manu