Small addendum: Unless the whole table is in that state (or even newer), vacuum shouldn't do a full table scan, but only process not yet vacuumed parts of the table. There are some exceptions to that (evenly randomly updated tables, very small tables), but they shouldn't apply in a case like this.