Filter index slow initial use I have a filtered index like this:
CREATE INDEX idx1
   ON public.tbl1 USING btree
    (col1 COLLATE pg_catalog.&quot;default&quot; ASC NULLS LAST, col2 ASC NULLS LAST)  
    WHERE col3 IS NULL;

and a query like:
SELECT * FROM tb1 WHERE col3 is null and col4 = 12

This query scan idx1 which is fine as this index is only a few rows (max 400 or so) the underlying table is millions of rows.
The first time this query runs, it runs painfully slow (almost a minute) but the seconds time it runs it does so in 20ms.
Can someone help me understand what is happening? The index gets rebuilt every evening but seems to bloat (gets to a few hundred megs) during the day. From the behaviour it feels like it has to load data into memory and the next time its faster because the data is cached. The database is quite busy 2k tupples in and 4k tuples out.
QUERY PLAN
Index Scan using unsubmittedmsgs_1 on tbl1 s  (cost=0.38..1.88 rows=1 width=315) (actual time=145.335..39385.943 rows=101 loops=1)
  Index Cond: (created_dow = 1)
  Filter: (machine_id = 20)
  Rows Removed by Filter: 155
  Buffers: shared hit=803132 read=25838 dirtied=85580
Planning:
  Buffers: shared hit=255 dirtied=3
Planning Time: 1.759 ms
Execution Time: 39386.110 ms
Very selective partial indexes tend to get bloated quickly, because the table autovacuuming is triggered off the percent turn over in the table.  But 20% turn over in a table can mean many thousands of percent turn over in the partial index.  Nightly reindexing can also solve the bloat, but it won't stay solved for long if turn over is high.  You can crank up autovacuum so it happens multiple times throughout the day.
The first time you run this query in a while, it is probably marking a lot of obsolete index entries as killed.  That is probably one reason there are so many dirtied buffers, and also one reason it will be faster the next time, as it will no longer have to visit all the obsolete entries just to discover they are obsolete.  Of course the buffers it does still need to read are likely to be cached as well, so that would be another reason for it to be faster.
Note that this index-entry killing doesn't work in bitmap index scans, only on regular index scans.  Also, it doesn't work on hot standbys. Both of which can be a real problem for some setups.