PostgreSQL prepared statement becomes slower after repeated executions because the plan changes

How does PostgreSQL decide when to switch from a custom plan to a generic plan for a prepared statement, and why can that make performance worse for skewed data?

Take a look at the Notes section in the PREPARE doc:

By default (that is, when plancachemode is set to auto), the server will automatically choose whether to use a generic or custom plan for a prepared statement that has parameters. The current rule for this is that the first five executions are done with custom plans and the average estimated cost of those plans is calculated. Then a generic plan is created and its estimated cost is compared to the average custom-plan cost. Subsequent executions use the generic plan if its cost is not so much higher than the average custom-plan cost as to make repeated replanning seem preferable.

This heuristic can be overridden, forcing the server to use either generic or custom plans, by setting plancachemode to forcegenericplan or forcecustomplan respectively. This setting is primarily useful if the generic plan's cost estimate is badly off for some reason, allowing it to be chosen even though its actual cost is much more than that of a custom plan.

Aside from switching your plancachemode setting, you can take a look at pgpreparedstatements.genericplans and .customplans to see what you were dealing with.

You could also try to deallocate and prepare it again, fresh, especially if your data profile changed.