Degraded performance during table rewrite

Hi all,

I am attempting to do a bunch of table rewrites to shrink a table in the
absence of pg_repack and vacuum full (both not an option). The database is
growing fast and has had significant bloat in both heaps and indexes, so
index rebuilds alone won't cut it. We found that table inheritance can be
used to achieve this rather nicely. We are running PG v9.6.18.

We are setting up the inheritance as follows:

BEGIN;
ALTER TABLE #{table} RENAME TO #{table}_old;
CREATE TABLE #{table} (LIKE #{table}_old INCLUDING ALL);
ALTER TABLE #{table}_old INHERIT #{table};
ALTER SEQUENCE #{table}_id_seq OWNED BY #{table}.id;
COMMIT;

Then, the migration itself runs as follows (each in a transaction, looping
through records and sleeping for a bit)

WITH del AS (
DELETE FROM #{old_table}
WHERE id IN (
SELECT id
FROM #{old_table}
WHERE id > #{max_deleted_id} -- This is the max deleted from the
previous batch, we grab it programmatically.
ORDER BY id ASC
LIMIT #{batch_size}
)
RETURNING *
)
INSERT INTO #{table}
SELECT * FROM del
RETURNING id

For instance, the batch_size can be 10_000, and the code sleeps
programatically for 200ms (this is done in a Ruby script).

"max_deleted_id" is passed to each run from the previous one. This improves
the inner SELECT query.

This works very well. However, I noticed two suprising things:

1. The performance of the delete and insert drops by several orders of
magnitude as the script runs. For instance, in one run, it goes from 150ms
average run to 700ms per batch.

2. The explain itself takes a while to run on a sample batch. In one table,
the explain alone took four seconds.

To try and reproduce this locally, I used the following dummy table:

create table towns (id serial primary key, code text, article text, name
text, department text);

insert into towns (
code, article, name, department
)
select
left(md5(i::text), 10),
md5(random()::text),
md5(random()::text),
left(md5(random()::text), 4)

from generate_series(1, 100000000) s(i);

This spends 150ms per batch, which climbs to 700ms per batch. A vacuum of
the old table lowers is back to 150ms, but I don't understand why, because
we structure the query to jump over all previously dead rows. There is an
old thread in which Tom Lane mentions that the planner might itself be
walking that primary index. Is this applicable here? And is there anything
we can do besides more aggressive and continued vacuuming of the old table
(or a change in autovacuum settings)? Ideally, we want to run this
overnight without much supervision.