found xmin X from before relfrozenxid Y during vacuum The vacuum of two pg_catalog tables runs into the following error and stops there. 


  found xmin X from before relfrozenxid Y during vacuum


I could find a lot of discussions about this problem but solutions are hard to find. Is there any solution for this problem other then restoring the database from a backup?

postgresql 9.3.22 (I know it is old, the server is being phased out but needs to continue working for now).
You might be in luck.

The last but one point release for 9.3 has this change:


  
  Ensure that updates to the relfrozenxid and relminmxid values for "nailed" system catalogs are processed in a timely fashion (Andres Freund)
  
  Overoptimistic caching rules could prevent these updates from being seen by other sessions, leading to spurious errors and/or data corruption. The problem was significantly worse for shared catalogs, such as pg_authid, because the stale cache data could persist into new sessions as well as existing ones.
  


See the discussion on the -hackers list.