PostgreSQL doesn’t generate index-only plan when using NOT-IN but does when using IN with multicolumn covering index

I have two tables: A(id, x, cid) and B(cid). I need to fetch some records from A and excluding records with same cid in B.

I have btree index on A (cid, id).

Query-1 (NOT-IN): select id from a where cid not in (select distinct cid from b);

Plan:

Seq Scan on a  (cost=20418.20..340328.83 rows=5128145 width=8) (actual time=367.337..3820.175 rows=169046 loops=1)
   Filter: (NOT (hashed SubPlan 1))
   Rows Removed by Filter: 10087249
   SubPlan 1
     ->  HashAggregate  (cost=20283.84..20391.33 rows=10749 width=4) (actual time=351.301..357.395 rows=41493 loops=1)
           Group Key: b.cid
           ->  Seq Scan on b  (cost=0.00..17451.87 rows=1132787 width=4) (actual time=0.530..148.063 rows=1132787 loops=1)
 Planning time: 0.254 ms
 Execution time: 3827.324 ms

It does NOT generate a index-only-scan which I think should be reasonable since index btree on A(cid, id) is a covering index.

However, if I use IN operator instead, it can generate index-only-scan, shown as following:

Query-2 (IN): select id from a where cid in (select distinct cid from b);

Plan:

Nested Loop  (cost=20284.27..420607.83 rows=10256290 width=8) (actual time=290.225..2349.182 rows=10087249 loops=1)
   ->  HashAggregate  (cost=20283.84..20391.33 rows=10749 width=4) (actual time=290.162..304.054 rows=41493 loops=1)
         Group Key: b.cid
         ->  Seq Scan on b  (cost=0.00..17451.87 rows=1132787 width=4) (actual time=0.042..95.151 rows=1132787 loops=1)
   ->  Index Only Scan using idx_a_cid_id on a  (cost=0.43..27.61 rows=961 width=12) (actual time=0.005..0.028 rows=243 loops=41493)
         Index Cond: (cid = b.cid)
         Heap Fetches: 0
 Planning time: 0.197 ms
 Execution time: 2672.898 ms

If you may consider because the cardinalities of A and B are too different, that's true. A contains 10256295 rows while B contains 41493 distinct cids.

However, if I manually rewrite the Query-1 to the following Query-3 with the same logic, but just using IN, postgres can still generate a index-only-scan, shown as following:

Query-3 (IN-sub(NOT-IN)): select id from a where cid in (select cid from a where cid not in (select distinct cid from b));

Plan:

Nested Loop  (cost=325220.51..722952.01 rows=10256290 width=8) (actual time=3741.854..5607.756 rows=169046 loops=1)
   ->  HashAggregate  (cost=325220.07..325326.82 rows=10675 width=4) (actual time=3741.133..3763.512 rows=51758 loops=1)
         Group Key: a_1.cid
         ->  Index Only Scan using idx_a_cid on a a_1  (cost=20418.64..312399.71 rows=5128145 width=4) (actual time=377.384..3691.304 rows=169046 loops=1)
               Filter: (NOT (hashed SubPlan 1))
               Rows Removed by Filter: 10087249
               Heap Fetches: 0
               SubPlan 1
                 ->  HashAggregate  (cost=20283.84..20391.33 rows=10749 width=4) (actual time=359.015..365.864 rows=41493 loops=1)
                       Group Key: b.cid
                       ->  Seq Scan on b  (cost=0.00..17451.87 rows=1132787 width=4) (actual time=0.455..144.879 rows=1132787 loops=1)
   ->  Index Only Scan using idx_a_cid_id on a  (cost=0.43..27.64 rows=961 width=12) (actual time=0.033..0.035 rows=3 loops=51758)
         Index Cond: (cid = a_1.cid)
         Heap Fetches: 0
 Planning time: 2.758 ms
 Execution time: 5617.930 ms

So I'm very confused now, whether it's because NOT-IN operator itself is too hard/expensive to use index-only-scan? Or just because PostgreSQL's Query Optimizer is not smart enough to generate one?

BTW, my experiments are on PostgreSQL-9.6.

Thank you!

Follow Up (Mar-28-2019):

Using jjanes's approach, it works!

SET cpu_index_tuple_cost TO 0;

SET random_page_cost TO 1;

Explain Query-1 again:

explain analyze select id from a where cid not in (select distinct cid from b);

Plan:

Index Only Scan using idx_a_cid_id on a  (cost=20418.64..188115.26 rows=5128145 width=8) (actual time=308.552..1865.567 rows=169046 loops=1)
   Filter: (NOT (hashed SubPlan 1))
   Rows Removed by Filter: 10087249
   Heap Fetches: 0
   SubPlan 1
     ->  HashAggregate  (cost=20283.84..20391.33 rows=10749 width=4) (actual time=289.169..297.363 rows=41493 loops=1)
           Group Key: b.cid
           ->  Seq Scan on b  (cost=0.00..17451.87 rows=1132787 width=4) (actual time=0.020..94.442 rows=1132787 loops=1)
 Planning time: 0.112 ms
 Execution time: 1871.197 ms

Thank you all!