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.
If it doesn’t, then set up a DB replica (good idea in any case), do SELECTs on slave, DELETEs on master.