PostgreSQL query plan changed

I recently did a full vacuum on a range of tables, and a specific monitoring query suddenly became really slow. This used to be a query we used for monitoring, so would happily run every 10sec for the past 2 months, but with the performance hit that came after the vacuum, most dashboards using that is down, and it ramps up until the server runs out of connections or resources depending.

Unfortunately I do not have the explain output of the previous one.

By not specifying a date limitation:

explain (analyze,timing) select min(id) from iqsim_cdrs;

 Result  (cost=0.64..0.65 rows=1 width=8) (actual time=6.222..6.222 rows=1 loops=1)
   InitPlan 1 (returns $0)
     ->  Limit  (cost=0.57..0.64 rows=1 width=8) (actual time=6.216..6.217 rows=1 loops=1)
           ->  Index Only Scan using iqsim_cdrs_pkey on iqsim_cdrs  (cost=0.57..34265771.63 rows=531041357 width=8) (a
ctual time=6.213..6.213 rows=1 loops=1)
                 Index Cond: (id IS NOT NULL)
                 Heap Fetches: 1
 Planning time: 1.876 ms
 Execution time: 6.313 ms
(8 rows)

By limiting the date:

explain (analyze,timing) select min(id) from iqsim_cdrs where timestamp < '2019-01-01 00:00:00';

 Result  (cost=7.38..7.39 rows=1 width=8) (actual time=363763.144..363763.145 rows=1 loops=1)
   InitPlan 1 (returns $0)
     ->  Limit  (cost=0.57..7.38 rows=1 width=8) (actual time=363763.137..363763.138 rows=1 loops=1)
           ->  Index Scan using iqsim_cdrs_pkey on iqsim_cdrs  (cost=0.57..35593384.68 rows=5227047 width=8) (actual t
ime=363763.133..363763.133 rows=1 loops=1)
                 Index Cond: (id IS NOT NULL)
                 Filter: ("timestamp" < '2019-01-01 00:00:00'::timestamp without time zone)
                 Rows Removed by Filter: 488693105
 Planning time: 7.707 ms
 Execution time: 363763.219 ms
(9 rows)

Not sure what could have caused this, I can only presume before the full vacuum it used the index on timestamp?

* UPDATE * As per @jjanes's recommendation, here the id+0 update

 explain (analyze,timing) select min(id+0) from iqsim_cdrs where timestamp < '2019-01-01 00:00:00';
                                                                          QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=377400.34..377400.35 rows=1 width=8) (actual time=109.176..109.177 rows=1 loops=1)
   ->  Index Scan using index_iqsim_cdrs_on_timestamp on iqsim_cdrs  (cost=0.57..351196.84 rows=5240699 width=8) (actual time=0.131..108.911 rows=126 loops=1)
         Index Cond: ("timestamp" < '2019-01-01 00:00:00'::timestamp without time zone)
 Planning time: 4.756 ms
 Execution time: 109.405 ms
(5 rows)