How to maintain visibility of all new transactions in append-only PostgreSQL DB without scanning the whole table
You should run VACUUM (FREEZE) occasionally. The longer it doesn't run, the more it has to do, and the longer it will take.

To speed up VACUUM, increase maintenance_work_mem.