Re: Pathify RHS unique-ification for semijoin planning

Hello,

As a very trivial test on this patch, I ran the query in your opening
email, both with and without the patch, scaling up the size of the table
a little bit.  So I did this

	drop table if exists t;
	create table t(a int, b int);
	insert into t select i % 100000, i from generate_series(1,1e7) i;
	create index on t(a);
	vacuum analyze t;

	set enable_hashagg to off;

	explain (costs off, analyze, buffers)
	select * from t t1 where t1.a in
	  (select a from t t2 where a < 10000)
	order by t1.a;


This is the plan without the patch:

                                                    QUERY PLAN                                                     
───────────────────────────────────────────────────────────────────────────────────────────────────────────────────
 Merge Join (actual time=289.262..700.761 rows=1000000.00 loops=1)
   Merge Cond: (t1.a = t2.a)
   Buffers: shared hit=1017728 read=3945 written=3361, temp read=1471 written=1476
   ->  Index Scan using t_a_idx on t t1 (actual time=0.011..320.747 rows=1000001.00 loops=1)
         Index Searches: 1
         Buffers: shared hit=997725 read=3112 written=2664
   ->  Sort (actual time=219.273..219.771 rows=10000.00 loops=1)
         Sort Key: t2.a
         Sort Method: quicksort  Memory: 385kB
         Buffers: shared hit=20003 read=833 written=697, temp read=1471 written=1476
         ->  Unique (actual time=128.173..218.708 rows=10000.00 loops=1)
               Buffers: shared hit=20003 read=833 written=697, temp read=1471 written=1476
               ->  Sort (actual time=128.170..185.461 rows=1000000.00 loops=1)
                     Sort Key: t2.a
                     Sort Method: external merge  Disk: 11768kB
                     Buffers: shared hit=20003 read=833 written=697, temp read=1471 written=1476
                     ->  Index Only Scan using t_a_idx on t t2 (actual time=0.024..74.171 rows=1000000.00 loops=1)
                           Index Cond: (a < 10000)
                           Heap Fetches: 0
                           Index Searches: 1
                           Buffers: shared hit=20003 read=833 written=697
 Planning:
   Buffers: shared hit=28 read=7
 Planning Time: 0.212 ms
 Execution Time: 732.840 ms


and this is the plan with the patch:

                                              QUERY PLAN                                               
───────────────────────────────────────────────────────────────────────────────────────────────────────
 Merge Join (actual time=70.310..595.116 rows=1000000.00 loops=1)
   Merge Cond: (t1.a = t2.a)
   Buffers: shared hit=1017750 read=3923 written=3586
   ->  Index Scan using t_a_idx on t t1 (actual time=0.020..341.257 rows=1000001.00 loops=1)
         Index Searches: 1
         Buffers: shared hit=996914 read=3923 written=3586
   ->  Unique (actual time=0.028..99.074 rows=10000.00 loops=1)
         Buffers: shared hit=20836
         ->  Index Only Scan using t_a_idx on t t2 (actual time=0.026..66.219 rows=1000000.00 loops=1)
               Index Cond: (a < 10000)
               Heap Fetches: 0
               Index Searches: 1
               Buffers: shared hit=20836
 Planning:
   Buffers: shared hit=55 read=15 written=14
 Planning Time: 0.391 ms
 Execution Time: 621.377 ms


This is a really nice improvement.  I think we could find queries that
are arbitrarily faster, by feeding enough tuples to the unnecessary Sort
nodes.

-- 
Álvaro Herrera         PostgreSQL Developer  —  https://www.EnterpriseDB.com/
"No necesitamos banderas
 No reconocemos fronteras"                  (Jorge González)