Correlated IN/Any Subquery Transformation

Hi PGHackers:

Currently, correlated IN/Any subquery always gets planned as a SubPlan which leads to poor performance:

postgres=# explain (costs off) select count(*) from s where s.n in (select l.n from l where l.u != s.u);
             QUERY PLAN
------------------------------------
Aggregate
   ->  Seq Scan on s
         Filter: (SubPlan 1)
         SubPlan 1
           ->  Seq Scan on l
                 Filter: (u <> s.u)
                            
postgres=# select count() from s where s.n in (select l.n from l where l.u != s.u);
Time: 3419.466 ms (00:03.419)

However, you can rewrite the query using exists which will be executed using join. In this example the join plan is more than 3 orders of magnitudes faster than the SubPlan:

postgres=# explain (costs off) select count(*) from s where exists (select 1 from l where l.n = s.n and l.u != s.u);
              QUERY PLAN
---------------------------------------
Aggregate
   ->  Merge Semi Join
         Merge Cond: (s.n = l.n)
         Join Filter: (l.u <> s.u)
         ->  Index Scan using s_n on s
         ->  Index Scan using l_n on l


postgres=# select count() from s where exists (select 1 from l where l.n = s.n and l.u != s.u);
Time: 1.188 ms
        

Table s has 10 rows, table l has 1, 000, 000 rows.

This patch enables correlated IN/Any subquery to be transformed to join, the transformation is allowed only when the correlated Var is in the where clause of the subquery. It covers the most common correlated cases and follows the same criteria that is followed by the correlated Exists transformation code.

Here is the new query plan for the same correlated IN query:

postgres=# explain (costs off) select count(*) from s where s.n in (select l.n from l where l.u != s.u);
QUERY PLAN

Aggregate
-> Merge Semi Join
Merge Cond: (s.n = l.n)
Join Filter: (l.u <> s.u)
-> Index Scan using s_n on s
-> Index Scan using l_n on l

postgres=# select count(*) from s where s.n in (select l.n from l where l.u != s.u);
Time: 1.693 ms

Also the patch introduces a new GUC enable_correlated_any_transform (on by default) to guard the optimization. Test cases are included in the patch. Comments are welcome!

-----------

Zheng Li

AWS, Amazon Aurora PostgreSQL