This can be resolved by having Indexes on those columns that are appearing in the Where clause.. Even once the Update is done you can drop those indexes.

This will increae the performance for the update.

I have tried and it's very very fast.

Thanks.