Vacuum does not have to read the full data set every time. The visibility map tracks, on a block level, whether all rows in a page are known to be visible to ev

Vacuum does not have to read the full data set every time. The visibility map tracks, on a block level, whether all rows in a page are known to be visible to everyone (starting in 8.4 or such) and whether the page is "frozen", i.e., does not contain visibility information that might need vacuuming (starting in 9.6 IIRC). However, indexes do currently have to be scanned as a whole. But that's only done by autovacuum if there's enough row versions for that to be worth it (in recent versions).