Enforcing delete cascade will also help here, instead of creating indexes. I believe it should eliminate the deadlock. Of course if you enable delete cascade it's no point in deleting from child table first and then parent table. We have to do just a delete from parent table.