BUG #17693: Slow performance: Much slower queries on pg_stat_all_tables since 13.4

The following bug has been logged on the website:

Bug reference:      17693
Logged by:          Alessandro Jeanteur
Email address:      aless.jeant@gmail.com
PostgreSQL version: 13.7
Operating system:   RDS
Description:

We did a point upgrade through RDS's managed service which went from 13.4 to
13.7. (13.9 is unavailable and we have yet to upgrade to 13.8 - however I
couldn't find any documentation or issue history reporting similar symptoms
in the past year of discussions here)

This created a weird bug which is causing a lot of strain on our systems,
because we currently run a lot of queries over the pg_stat_all_tables, in
order to choose candidate tables most appropriate to vacuum preemptively in
a production system (we have a lot of active tables, order of magnitude 100k
tables)

Before this, queries would take <<1 second, now they're always ~5 seconds,
regardless of what we are filtering on.
EXPLAIN ANALYZE reports an odd fixed cost (that's not expected by EXPLAIN's
query plan) of roughly 5 seconds at the last layer of the query on this
view, GroupAggregate.
Similarly, when running the same query through the equivalent functions
(pg_stat_get_mod_since_analyze, pg_stat_get_dead_tuples,
pg_stat_get_live_tuples) we always run into this obscure huge fixed cost.
What is it, and how can we optionally get rid of it, presumably going back
to the previous performance characteristics?

example without a filter, limit 1:
```EXPLAIN ANALYZE SELECT n_mod_since_analyze, n_live_tup, n_dead_tup FROM
pg_stat_all_tables limit 1;
Limit (cost=2.80..4.15 rows=1 width=24) (actual time=5912.121..5912.125
rows=1 loops=1)
 -> Subquery Scan on pg_stat_all_tables (cost=2.80..1515002.24 rows=1119834
width=24) (actual time=5912.120..5912.124 rows=1 loops=1)
 -> GroupAggregate (cost=2.80..1503803.90 rows=1119834 width=292) (actual
time=5912.118..5912.121 rows=1 loops=1)
 Group Key: c.oid, n.nspname, c.relname
 -> Incremental Sort (cost=2.80..1475808.05 rows=1119834 width=132) (actual
time=0.122..0.124 rows=3 loops=1)
 Sort Key: c.oid, n.nspname, c.relname
 Presorted Key: c.oid
 Full-sort Groups: 1 Sort Method: quicksort Average Memory: 33kB Peak
Memory: 33kB
 -> Nested Loop Left Join (cost=1.52..1425415.52 rows=1119834 width=132)
(actual time=0.021..0.106 rows=34 loops=1)
 -> Merge Left Join (cost=1.11..940324.82 rows=1119834 width=72) (actual
time=0.016..0.044 rows=34 loops=1)
 Merge Cond: (c.oid = i.indrelid)
 -> Index Scan using pg_class_oid_index on pg_class c (cost=0.56..700419.45
rows=1119834 width=72) (actual time=0.009..0.025 rows=19 loops=1)
 Filter: (relkind = ANY ('{r,t,m}'::\"char\"[]))
 Rows Removed by Filter: 14
 -> Index Only Scan using pg_index_indrelid_index on pg_index i
(cost=0.55..227140.96 rows=1659053 width=4) (actual time=0.006..0.010
rows=34 loops=1)
 Heap Fetches: 0
 -> Index Scan using pg_namespace_oid_index on pg_namespace n
(cost=0.41..0.43 rows=1 width=68) (actual time=0.001..0.001 rows=1
loops=34)
 Index Cond: (oid = c.relnamespace)
Planning Time: 1.024 ms
Execution Time: 5912.239 ms
```
(with OID unique key filter, the only difference is in the GroupAggregate
plan, where (cost=25.72..25.83 rows=4 width=292))

Thank you in advance,
Best,