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

Question

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!

• Lennart - Slava Ukraini: Have you tried NOT EXISTS or LEFT JOIN ... WHERE ... IS NULL in comparison?
• Vérace: +1 for an excellent first question - welcome to the forum!

Answer 1

It picks the plan it thinks will be faster.

If you SET cpu_index_tuple_cost TO 0 and SET random_page_cost to 1 you will probably find it using the index only scan.

And also find that it is not reliably better, or at least not by much.

• Qiushi Bai: Thank you for the brief and accurate answer! It works!