[prostoalex]

Have a job queue running lower-priority DB queries. The queue workers select all records for a given ID, then prune off older records above X.

Insert a fresh record immediately, since you know it’s recent. Upon successful insert, fire off a queue request to go check on that ID.

[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.