BUG #16423: Sequential Scan on query after reindex was done

The following bug has been logged on the website:

Bug reference: 16423
Logged by: Jamie Koceniak
Email address: jkoceniak(at)mediamath(dot)com
PostgreSQL version: 12.2
Operating system: Debian GNU/Linux 10 (buster)
Description:

The query below had been using the primary key index but now the optimizer
has decide to perform a sequential scan.
This happened after a reindex was done.

I've made multiple attempts to run analyze.
I have also tried increasing default_statistics_target followed by analyze
with no success.
I don't have the option to use ENABLE_SEQSCAN.

Is there a way to make the query use the index again? the 120ms makes a
difference since this query is called millions of time per day. Here is all
the information I could gather:

explain analyze SELECT * FROM user_games t1 JOIN games t2 ON (t1.game_id =
t2.id) WHERE t1.user_id = '15202';

New Query Plan:

QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=5709.96..14397.40 rows=12403 width=156) (actual
time=141.685..149.109 rows=11043 loops=1)
Hash Cond: (t1.game_id = t2.id)
-> Index Scan using user_games_user_id_idx on user_games t1
(cost=0.43..8655.31 rows=12403 width=16) (actual time=0.102..2.883
rows=11043 loops=1)
Index Cond: (user_id = 2966)
-> Hash (cost=3993.68..3993.68 rows=137268 width=140) (actual
time=140.319..140.319 rows=137270 loops=1)
Buckets: 262144 Batches: 1 Memory Usage: 22765kB
-> Seq Scan on games t2 (cost=0.00..3993.68 rows=137268
width=140) (actual time=0.030..73.581 rows=137270 loops=1)
Planning Time: 2.383 ms
Execution Time: 149.903 ms

Query Plan before using the index. We want this query plan back.

QUERY
PLAN

-----------------------------------------------------------------------------------------------------------------------------------------------------------
Gather (cost=1166.97..16022.92 rows=12403 width=156) (actual
time=1.403..27.847 rows=11043 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Nested Loop (cost=166.97..13782.62 rows=5168 width=156) (actual
time=0.437..15.659 rows=3681 loops=3)
-> Parallel Bitmap Heap Scan on user_games t1
(cost=166.55..9020.75 rows=5168 width=16) (actual time=0.304..1.173
rows=3681 loops=3)
Recheck Cond: (user_id = 2966)
Heap Blocks: exact=27
-> Bitmap Index Scan on user_games_user_id_idx
(cost=0.00..163.45 rows=12403 width=0) (actual time=0.745..0.745 rows=11043
loops=1)
Index Cond: (user_id = 2966)
-> Index Scan using games_pkey on games t2 (cost=0.42..0.92
rows=1 width=140) (actual time=0.003..0.003 rows=1 loops=11043)
Index Cond: (id = t1.game_id)
Planning Time: 0.297 ms
Execution Time: 28.365 ms

user_games table:
Table "public.user_games"
Column | Type | Collation | Nullable | Default

---------------+---------+-----------+----------+----------------------------------------------
user_id | integer | | not null |
game_id | integer | | not null |
id | integer | | not null |
nextval('user_games_id_seq'::regclass)
version | integer | | not null | 0
Indexes:
"user_games_pkey" PRIMARY KEY, btree (id)
"user_games_game_id_idx" btree (game_id)

Games table:
Table "public.games"
Column | Type | Collation
| Nullable | Default
-----------------------------+-----------------------------------+-----------+----------+-------------------------------------------
id | integer |
| not null | nextval('games_id_seq'::regclass)
version | integer |
| not null | 0
mfc_id | integer | |
not null |
name | character varying(64) |
| not null |
Indexes:
"games_pkey" PRIMARY KEY, btree (id)
"games_mfc_id_idx" btree (mfc_id)

select * from pg_stats where tablename = 'games' and attname = 'id';
-[ RECORD 1
]----------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
schemaname | public
tablename | games
attname | id
inherited | f
null_frac | 0
avg_width | 4
n_distinct | -1
most_common_vals |
most_common_freqs |
histogram_bounds |
{16,101290,102673,104007,105347,106625,107971,109385,110637,112010,113409,114858,116219,117562,119024,120240,121725,123136,124414,125702,127068,128351,129698,131087,132423,133814,135191,136577,137990,139470,140801,142212,143650,145027,146448,147922,149417,150887,152146,153552,154994,156330,157769,159183,160487,161859,163227,164532,166006,167300,168680,170063,171305,172752,174121,175542,176931,178244,179657,180978,182297,183611,184973,186294,187499,188845,190205,191528,192890,194151,195500,196908,198314,199789,201140,202524,203953,205301,206637,207987,209474,210880,212325,213684,215134,216611,218152,219447,220897,222242,223627,225008,226448,227870,229242,230592,232001,233496,234808,236228,237644}
correlation | 0.30886832
most_common_elems |
most_common_elem_freqs |
elem_count_histogram |

-- note totalseqscan is increasing fast
SELECT
relname AS TableName,
to_char(seq_scan, '999,999,999,999') AS TotalSeqScan,
to_char(idx_scan, '999,999,999,999') AS TotalIndexScan,
to_char(n_live_tup, '999,999,999,999') AS TableRows,
pg_size_pretty(pg_relation_size(relname :: regclass)) AS TableSize
FROM pg_stat_all_tables
WHERE schemaname = 'public'
and relname = 'games'
ORDER BY relname ASC;
tablename | totalseqscan | totalindexscan | tablerows |
tablesize
-------------+------------------+------------------+------------------+-----------
games | 263,044 | 16,349,470,806 | 137,270 | 20 MB