OK, I did try you proposal and correlated subselect. I have a database ~900000 companies. First try was to remove randomly selected 1000 companies Uncorrelated subselect: 65899ms Correlated subselect: 97467ms using: 9605ms my way: 104979ms. (without constraints recreate) My is the worst because it is oriented on massive delete. So I thought USING would perform better, so I did try 10000 companies my way: 190527ms. (without constraints recreate) using: 694144ms I was a little shocked, but I did check plans and found out that it did switch from Nested Loop to Hash Join. I did disable Hash Join, it not show Merge Join. This was also disabled.... and I've got 747253ms. Then I've tried combinations: Without hash join it was the best result of 402629ms, without merge join it was 1096116ms.
My conclusion: Until optimizer would take into account additional actions needed (like constraints check/cascade deletes/triggers), it can not make good plan.
