Table structure is important. 131000 is not really a big number. It would be great if you could provide the kind of indexes that exist on the tale and how the data is updated. AS of now I could give the following hints:

1. The column based on which the update happens should be indexed

2. The index on the column which actually gets updated can be removed tempirarily and can be created once the index is complete

3. Any foreign key relationships on the actual column getting updated should be removed during the time of update

Thanks

Satish More