[matttah]

At 500 million+ records, even a 0.01 second per lookup/update is going to be too slow at that scale even in parallel, unless the DB is able to process in parallel without lock contention extremely quickly.

[prostoalex]

An index on ID should help.

If it doesn’t, then set up a DB replica (good idea in any case), do SELECTs on slave, DELETEs on master.