Another possibility is that this is part of some large batch, and autovacuum simply did not have change to do the work.
Yes, I think that's it: I've just realized that immediately prior to the INSERT, in the same transaction, an unfiltered DELETE has been issued; i.e. the whole table is being rewritten. Then the INSERT is issued ... with a WHERE clause on non-existence in the (now empty) table.
In that case of course the WHERE clause is unnecessary, as it will always evaluate as true (and we've locked the whole table for writes). Looks like it is a lot worse than unnecessary, though, if it triggers this performance snafu in EXPLAIN INSERT.
This seems very likely to be the explanation here. So our workaround will be to simply omit the WHERE clause in those cases where the full DELETE has been issued. (And then vacuum afterwards.)
(Even better, just make the new table not temporary, and have it replace the former table altogether. But that's for later; requires some broader changes in our application.)
I'll report back if I *do* see the problem come up again despite this change.
