BUG #14863: wrong reltuples statistics after vacuum without analyze

The following bug has been logged on the website:

Bug reference: 14863
Logged by: Pavel Suderevsky
Email address: psuderevsky(at)gmail(dot)com
PostgreSQL version: 9.6.3
Operating system: CentOS 7.2/7.3
Description:

Hi,

I've faced strange behaviour of statistics state after (auto)VACUUM
execution without ANALYZE. While ANALYZE operation makes statistics good,
VACUUM breaks it to inconsistent state.

1. most real values
database=# select count(*) from schema.table1;
count
-------
26
database=# select count(*) from schema.table2;
count
-------
553

2. after ANALYZE reltuples values appear to be true.
database=# analyze schema.table1; analyze schema.table2;
ANALYZE
ANALYZE
database=# select pg_class.relname, to_char(pg_class.reltuples,
'9G999G999G999') as pg_class_reltuples, n_live_tup, n_dead_tup from
pg_class, pg_stat_user_tables where pg_class.relname =
pg_stat_user_tables.relname and pg_class.relname in ('table1', 'table2');
relname | pg_class_reltuples | n_live_tup | n_dead_tup
-----------+--------------------+------------+------------
table1 | 26 | 26 | 0
table2 | 553 | 553 | 0
(2 rows)

3. after VACUUM reltuples value for one table appears to be wrong
database=# vacuum schema.table1; vacuum schema.table2;
VACUUM
VACUUM
database=# select pg_class.relname, to_char(pg_class.reltuples,
'9G999G999G999') as pg_class_reltuples, n_live_tup, n_dead_tup from
pg_class, pg_stat_user_tables where pg_class.relname =
pg_stat_user_tables.relname and pg_class.relname in ('table1', 'table2');
relname | pg_class_reltuples | n_live_tup | n_dead_tup
-----------+--------------------+------------+------------
table1 | 38 | 38 | 0
table2 | 553 | 553 | 0
(2 rows)

4. when VACUUM is performed with ANALYZE statistics is great again
database=# vacuum analyze schema.table1; vacuum analyze schema.table2;
VACUUM
VACUUM
database=# select pg_class.relname, to_char(pg_class.reltuples,
'9G999G999G999') as pg_class_reltuples, n_live_tup, n_dead_tup from
pg_class, pg_stat_user_tables where pg_class.relname =
pg_stat_user_tables.relname and pg_class.relname in ('table1', 'table2');
relname | pg_class_reltuples | n_live_tup | n_dead_tup
-----------+--------------------+------------+------------
table1 | 26 | 26 | 0
table2 | 553 | 553 | 0
(2 rows)

5. The most frustrating case is when there are dead tuples in relation that
can not be removed because of some running transaction with xid older than
tuples xmax's.
database=# select pg_class.relname, to_char(pg_class.reltuples,
'9G999G999G999') as pg_class_reltuples, n_live_tup, n_dead_tup from
pg_class, pg_stat_user_tables where pg_class.relname =
pg_stat_user_tables.relname and pg_class.relname = 'table1';
relname | pg_class_reltuples | n_live_tup | n_dead_tup
-----------+--------------------+------------+------------
table1 | 2,576 | 26 | 2550

While true reltuples value must be 26 VACUUM makes it much more higher (it
is not always straight n_live_tup + n_dead_tup value as in this example, but
always near that value). As far as I now pg_class.reltuples values are used
by query optimizer for rows estimations, so this can lead to bad query
plans.

Please assist in understanding this behaviour.
Unlikely such bug could pass by community, but still, and I couldn't find
current issue in release notes for 9.6.4/9.6.5.