I’m not familiar with the VACUUM changes but the situation you’re describing suggests something is wrong with the table definition or database configuration.
Postgres docs are quite clear. Table space is not reclaimed without a vacuum full. So delete a column in a big table? you are storing that data forever.
Are you able to partition any of your tables so that you can VACUUM FULL the partitions individually?
The data that will be "not removed" will just be used by new data.
Only real use case is "we've loaded way too many data, removed it, and want to recover that space because we will never need it", and that is not enough to matter, as usually database have its own filesystem and most filesystems can't be shrunk online so any shrinking needs downtime
Parent literally provided one: deleting a column.
Another is that it's very easy in PostgreSQL to bloat indexes. Load a bunch of data. Update (or delete) that data and now your index is bloated.
The only resolution is to REINDEX (or VACUUM FULL).
The nature of fragmentation means that you need to move a lot of data around to actually make that file smaller. In Postgres, that's typically done with VACUUM FULL. The problem of fragmentation is not unique to Postgres, it's a fundamental issue; but perhaps other systems are able to move the data around in a less disruptive way.
If you just delete a column, that creates a different type of fragmentation within the tuples themselves (e.g. you delete the middle column, and the tuple itself doesn't shrink, it just ignores that middle column). You are right that can be a problem. Postgres could be improved to rewrite tuples to eliminate the wasted space from deleted columns in the middle, which would probably be (computationally) worth it to do if it's already performing cleanup on the page.