Vryjdfkk

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!