GilaMonster is exactly right - removing the NOT INs is not a long term resolution as the deadlocks will still occur, just not as frequently. Expressing them as left joins though is a MUCH faster solution which will minimize the deadlocks. It won't get rid of them completely though.