vacuum frees tuples just fine. It's just that by the time each run finishes many more accumulate due to table update activity, ad nauseum. So this unused space constantly grows. Here's a sample autovacuum run:
2019-04-11 19:39:44.450841500 [] LOG: automatic vacuum of table "foo.public.bar": index scans: 1
2019-04-11 19:39:44.450843500 pages: 0 removed, 472095 remain, 4 skipped due to pins, 39075 skipped frozen
2019-04-11 19:39:44.450844500 tuples: 19150 removed, 2725811 remain, 465 are dead but not yet removable
2019-04-11 19:39:44.450845500 buffer usage: 62407557 hits, 6984769 misses, 116409 dirtied
2019-04-11 19:39:44.450846500 avg read rate: 16.263 MB/s, avg write rate: 0.271 MB/s
2019-04-11 19:39:44.450847500 system usage: CPU 59.05s/115.26u sec elapsed 3355.28 sec
Maybe I am off base, but those read/write rates seem very low. Is this running on spinny disks? Also, less than half a million rows remain and 2.7 million dead but not removed in this auto vacuum. It seems to indicate that auto vacuum is not as aggressive as it needs to be. Have you verified that it blocks normal activity when autovacuum does more work each pass? If you are hardware bound, could you use partitioning to allow auto vacuum to work on the partitions separately and perhaps keep up?
