Dead tuples block invoice job

At 03:40 your Postgres-backed billing service's nightly invoice job, which usually finishes in 8 minutes, is still running after 2 hours and is now blocking the morning batch. The query plan for its main aggregation flipped from a hash join to a nested loop sometime overnight. pg_stat_user_tables shows the invoices table has 40M dead tuples and last_autovacuum is 9 days ago. autovacuum_max_workers is at default and a large data-retention purge ran last night deleting 35M rows. How do you triage and resolve this?