PostgreSQL - VACUUM speed (Heroku)
This means you need to tune your autovacuum settings. 

Auto vacuum is not the enemy

The default settings for autovacuum will trigger when the 20% rows are dead. This is not a good choice for a large OLTP system. So tune it on Number basis not the percentage.

Like, set auto vacuum when the dead tuple count reaches 10000.

autovacuum_vacuum_scale_factor = 0
autovacuum_vacuum_threshold = 10000
autovacuum_max_workers = 4


OR

you can set this threshold on a particular table.

ALTER TABLE t SET (autovacuum_vacuum_scale_factor = 0);
ALTER TABLE t SET (autovacuum_vacuum_threshold = 10000);


In some worst cases auto vaccum will not work. Read why? 
The above parameters for Autovacuum for Ad-Hoc vacuum set something like,

vacuum_cost_delay = 20ms
vacuum_cost_limit = 200

vacuum_cost_page_hit = 1
vacuum_cost_page_miss = 10
vacuum_cost_page_dirty = 20


maintenance_work_mem  is also a contributing for this