Subject: A new strategy for pull-up correlated ANY_SUBLINK

From: Andy Fan <[email-masked]>
Date: Wed, 2 Nov 2022 11:02:58 +0800

In the past we pull-up the ANY-sublink with 2 steps, the first step is to
pull up the sublink as a subquery, and the next step is to pull up the
subquery if it is allowed.  The benefits of this method are obvious,
pulling up the subquery has more requirements, even if we can just finish
the first step, we still get huge benefits. However the bad stuff happens
if varlevelsup = 1 involves, things fail at step 1.

convert_ANY_sublink_to_join ...

    if (contain_vars_of_level((Node *) subselect, 1))
        return NULL;

In this patch we distinguish the above case and try to pull-up it within
one step if it is helpful, It looks to me that what we need to do is just
transform it to EXIST-SUBLINK.

The only change is transforming the format of SUBLINK, so outer-join /
pull-up as semi-join is unrelated, so the correctness should not be an
issue.

I can help with the following query very much.

master:
explain (costs off, analyze) select * from tenk1 t1
where hundred in (select hundred from tenk2 t2
                  where t2.odd = t1.odd
                  and even in (select even from tenk1 t3
                               where t3.fivethous = t2.fivethous))
and even > 0;
                                     QUERY PLAN
------------------------------------------------------------------------------------
 Seq Scan on tenk1 t1 (actual time=0.023..234.955 rows=10000 loops=1)
   Filter: ((even > 0) AND (SubPlan 2))
   SubPlan 2
     ->  Seq Scan on tenk2 t2 (actual time=0.023..0.023 rows=1 loops=10000)
           Filter: ((odd = t1.odd) AND (SubPlan 1))
           Rows Removed by Filter: 94
           SubPlan 1
             ->  Seq Scan on tenk1 t3 (actual time=0.011..0.011 rows=1
loops=10000)
                   Filter: (fivethous = t2.fivethous)
                   Rows Removed by Filter: 94
 Planning Time: 0.169 ms
 Execution Time: 235.488 ms
(12 rows)

patched:

explain (costs off, analyze) select * from tenk1 t1
where hundred in (select hundred from tenk2 t2
                  where t2.odd = t1.odd
                  and even in (select even from tenk1 t3
                               where t3.fivethous = t2.fivethous))
and even > 0;
                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Hash Join (actual time=13.102..17.676 rows=10000 loops=1)
   Hash Cond: ((t1.odd = t2.odd) AND (t1.hundred = t2.hundred))
   ->  Seq Scan on tenk1 t1 (actual time=0.014..1.702 rows=10000 loops=1)
         Filter: (even > 0)
   ->  Hash (actual time=13.080..13.082 rows=100 loops=1)
         Buckets: 1024  Batches: 1  Memory Usage: 12kB
         ->  HashAggregate (actual time=13.041..13.060 rows=100 loops=1)
               Group Key: t2.odd, t2.hundred
               Batches: 1  Memory Usage: 73kB
               ->  Hash Join (actual time=8.044..11.296 rows=10000 loops=1)
                     Hash Cond: ((t3.fivethous = t2.fivethous) AND (t3.even
= t2.even))
                     ->  HashAggregate (actual time=4.054..4.804 rows=5000
loops=1)
                           Group Key: t3.fivethous, t3.even
                           Batches: 1  Memory Usage: 465kB
                           ->  Seq Scan on tenk1 t3 (actual
time=0.002..0.862 rows=10000 loops=1)
                     ->  Hash (actual time=3.962..3.962 rows=10000 loops=1)
                           Buckets: 16384  Batches: 1  Memory Usage: 597kB
                           ->  Seq Scan on tenk2 t2 (actual
time=0.004..2.289 rows=10000 loops=1)
 Planning Time: 0.426 ms
 Execution Time: 18.129 ms
(20 rows)

The execution time is 33ms (patched) VS 235ms (master).
The planning time is 0.426ms (patched) VS 0.169ms (master).

I think the extra planning time comes from the search space increasing a
lot and that's where the better plan comes.

I used below queries to measure how much effort we made but got nothing:
run twice in 1 session and just count the second planning time.

explain (costs off, analyze) select * from tenk1 t1
where
(hundred, odd) in (select hundred, odd from tenk2 t2
                  where (even, fivethous) in
                  (select even, fivethous from tenk1 t3));

psql regression -f 1.sql | grep 'Planning Time' | tail -1

master:

Planning Time: 0.430 ms
Planning Time: 0.551 ms
Planning Time: 0.316 ms
Planning Time: 0.342 ms
Planning Time: 0.390 ms

patched:

Planning Time: 0.405 ms
Planning Time: 0.406 ms
Planning Time: 0.433 ms
Planning Time: 0.371 ms
Planning Time: 0.425 ms

I think this can show us the extra planning effort is pretty low.

This topic has been raised many times, at least at [1] [2]. and even MySQL
can support some simple but common cases. I think we can do something
helpful as well.  Any feedback is welcome.

[1] https://www.postgresql.org/message-id/3691.1342650974%40sss.pgh.pa.us
[2]
https://www.postgresql.org/message-id/[email-masked]

-- 
Best Regards
Andy Fan

---

From: Andrey Lepikhov <[email-masked]>
Date: Wed, 2 Nov 2022 09:42:28 +0600

> transform it to EXIST-SUBLINK.
Maybe code [1] would be useful for your purposes/tests.
We implemented flattening of correlated subqueries for simple N-J case, 
but found out that in some cases the flattening isn't obvious the best 
solution - we haven't info about cardinality/cost estimations and can do 
worse.
I guess, for more complex flattening procedure (with aggregate function 
in a targetlist of correlated subquery) situation can be even worse.
Maybe your idea has such corner cases too ?

[1] 
https://www.postgresql.org/message-id/flat/CALNJ-vTa5VgvV1NPRHnypdnbx-fhDu7vWp73EkMUbZRpNHTYQQ%40mail.gmail.com

-- 
regards,
Andrey Lepikhov
Postgres Professional

---

From: Andy Fan <[email-masked]>
Date: Wed, 2 Nov 2022 13:34:54 +0800

> Maybe code [1] would be useful for your purposes/tests.

Looks like we are resolving the same problem, IIUC,  great that more
people are interested in it!

I went through the code,  and it looks like you tried to do the pull-up by
yourself, which would have many troubles to think about.  but I just
transformed
it into EXIST sublink after I distinguish it as the case I can improve.
> pull-up as semi-join is unrelated, so the correctness should not be an

That is just a difference, no matter which one is better.

> Maybe your idea has such corner cases too ?

In my case, since aggregate function can't be handled by
covert_EXISTS_sublink_to_join, so it is not the target I want to optimize in
this patch.  More testing/review on my method would be pretty appreciated.
but I'm not insisting on my method at all.  Link [2] might be useful as
well.

[2]
https://www.postgresql.org/message-id/CAKU4AWpi9oztiomUQt4JCxXEr6EaQ2thY-7JYDm6c9he0A7oCA%40mail.gmail.com

-- 
Best Regards
Andy Fan

---

From: Tom Lane <[email-masked]>
Date: Sat, 12 Nov 2022 17:45:43 -0500

> transform it to EXIST-SUBLINK.

This patch seems awfully messy to me.  The fact that you're having to
duplicate stuff done elsewhere suggests at the least that you've not
plugged the code into the best place.

Looking again at that contain_vars_of_level restriction, I think the
reason for it was just to avoid making a FROM subquery that has outer
references, and the reason we needed to avoid that was merely that we
didn't have LATERAL at the time.  So I experimented with the attached.
It seems to work, in that we don't get wrong answers from any of the
small number of places that are affected.  (I wonder though whether
those test cases still test what they were intended to, particularly
the postgres_fdw one.  We might have to try to hack them some more
to not get affected by this optimization.)  Could do with more test
cases, no doubt.

One thing I'm not at all clear about is whether we need to restrict
the optimization so that it doesn't occur if the subquery contains
outer references falling outside available_rels.  I think that that
case is covered by is_simple_subquery() deciding later to not pull up
the subquery based on LATERAL restrictions, but maybe that misses
something.

I'm also wondering whether the similar restriction in
convert_EXISTS_sublink_to_join could be removed similarly.
In this light it was a mistake for convert_EXISTS_sublink_to_join
to manage the pullup itself rather than doing it in the two-step
fashion that convert_ANY_sublink_to_join does it.

			regards, tom lane

diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 558e94b845..c07280d836 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -11377,19 +11377,19 @@ CREATE FOREIGN TABLE foreign_tbl2 () INHERITS (foreign_tbl)
   SERVER loopback OPTIONS (table_name 'base_tbl');
 EXPLAIN (VERBOSE, COSTS OFF)
 SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl);
-                                 QUERY PLAN                                  
------------------------------------------------------------------------------
- Seq Scan on public.base_tbl
+                                QUERY PLAN                                 
+---------------------------------------------------------------------------
+ Nested Loop Semi Join
    Output: base_tbl.a
-   Filter: (SubPlan 1)
-   SubPlan 1
-     ->  Result
-           Output: base_tbl.a
-           ->  Append
-                 ->  Async Foreign Scan on public.foreign_tbl foreign_tbl_1
-                       Remote SQL: SELECT NULL FROM public.base_tbl
-                 ->  Async Foreign Scan on public.foreign_tbl2 foreign_tbl_2
-                       Remote SQL: SELECT NULL FROM public.base_tbl
+   ->  Seq Scan on public.base_tbl
+         Output: base_tbl.a, base_tbl.b
+         Filter: (base_tbl.a IS NOT NULL)
+   ->  Materialize
+         ->  Append
+               ->  Async Foreign Scan on public.foreign_tbl foreign_tbl_1
+                     Remote SQL: SELECT NULL FROM public.base_tbl
+               ->  Async Foreign Scan on public.foreign_tbl2 foreign_tbl_2
+                     Remote SQL: SELECT NULL FROM public.base_tbl
 (11 rows)
 
 SELECT a FROM base_tbl WHERE a IN (SELECT a FROM foreign_tbl);
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 92e3338584..3d4645a154 100644
--- a/src/backend/optimizer/plan/subselect.c
+++ b/src/backend/optimizer/plan/subselect.c
@@ -1271,6 +1271,7 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 	JoinExpr   *result;
 	Query	   *parse = root->parse;
 	Query	   *subselect = (Query *) sublink->subselect;
+	bool		has_level_1_vars;
 	Relids		upper_varnos;
 	int			rtindex;
 	ParseNamespaceItem *nsitem;
@@ -1283,11 +1284,10 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 	Assert(sublink->subLinkType == ANY_SUBLINK);
 
 	/*
-	 * The sub-select must not refer to any Vars of the parent query. (Vars of
-	 * higher levels should be okay, though.)
+	 * If the sub-select refers to any Vars of the parent query, we have to
+	 * treat it as LATERAL.  (Vars of higher levels don't matter here.)
 	 */
-	if (contain_vars_of_level((Node *) subselect, 1))
-		return NULL;
+	has_level_1_vars = contain_vars_of_level((Node *) subselect, 1);
 
 	/*
 	 * The test expression must contain some Vars of the parent query, else
@@ -1324,7 +1324,7 @@ convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
 	nsitem = addRangeTableEntryForSubquery(pstate,
 										   subselect,
 										   makeAlias("ANY_subquery", NIL),
-										   false,
+										   has_level_1_vars,
 										   false);
 	rte = nsitem->p_rte;
 	parse->rtable = lappend(parse->rtable, rte);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 9358371072..cdaedb92b2 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4657,17 +4657,17 @@ explain (costs off)
 select a.unique1, b.unique2
   from onek a left join onek b on a.unique1 = b.unique2
   where b.unique2 = any (select q1 from int8_tbl c where c.q1 < b.unique1);
-                        QUERY PLAN                        
-----------------------------------------------------------
- Hash Join
-   Hash Cond: (b.unique2 = a.unique1)
-   ->  Seq Scan on onek b
-         Filter: (SubPlan 1)
-         SubPlan 1
-           ->  Seq Scan on int8_tbl c
-                 Filter: (q1 < b.unique1)
-   ->  Hash
-         ->  Index Only Scan using onek_unique1 on onek a
+                     QUERY PLAN                     
+----------------------------------------------------
+ Nested Loop
+   ->  Hash Semi Join
+         Hash Cond: (b.unique2 = c.q1)
+         Join Filter: (c.q1 < b.unique1)
+         ->  Seq Scan on onek b
+         ->  Hash
+               ->  Seq Scan on int8_tbl c
+   ->  Index Only Scan using onek_unique1 on onek a
+         Index Cond: (unique1 = b.unique2)
 (9 rows)
 
 select a.unique1, b.unique2
@@ -6074,8 +6074,8 @@ lateral (select * from int8_tbl t1,
                                      where q2 = (select greatest(t1.q1,t2.q2))
                                        and (select v.id=0)) offset 0) ss2) ss
          where t1.q1 = ss.q2) ss0;
-                           QUERY PLAN                            
------------------------------------------------------------------
+                             QUERY PLAN                              
+---------------------------------------------------------------------
  Nested Loop
    Output: "*VALUES*".column1, t1.q1, t1.q2, ss2.q1, ss2.q2
    ->  Seq Scan on public.int8_tbl t1
@@ -6087,23 +6087,24 @@ lateral (select * from int8_tbl t1,
          ->  Subquery Scan on ss2
                Output: ss2.q1, ss2.q2
                Filter: (t1.q1 = ss2.q2)
-               ->  Seq Scan on public.int8_tbl t2
+               ->  Result
                      Output: t2.q1, t2.q2
-                     Filter: (SubPlan 3)
-                     SubPlan 3
+                     One-Time Filter: $3
+                     InitPlan 2 (returns $3)
                        ->  Result
-                             Output: t3.q2
-                             One-Time Filter: $4
-                             InitPlan 1 (returns $2)
-                               ->  Result
-                                     Output: GREATEST($0, t2.q2)
-                             InitPlan 2 (returns $4)
-                               ->  Result
-                                     Output: ($3 = 0)
-                             ->  Seq Scan on public.int8_tbl t3
-                                   Output: t3.q1, t3.q2
-                                   Filter: (t3.q2 = $2)
-(27 rows)
+                             Output: ($2 = 0)
+                     ->  Nested Loop Semi Join
+                           Output: t2.q1, t2.q2
+                           Join Filter: (t2.q1 = t3.q2)
+                           ->  Seq Scan on public.int8_tbl t2
+                                 Output: t2.q1, t2.q2
+                                 Filter: ((SubPlan 1) = t2.q1)
+                                 SubPlan 1
+                                   ->  Result
+                                         Output: GREATEST($0, t2.q2)
+                           ->  Seq Scan on public.int8_tbl t3
+                                 Output: t3.q1, t3.q2
+(28 rows)
 
 select * from (values (0), (1)) v(id),
 lateral (select * from int8_tbl t1,

---

From: Richard Guo <[email-masked]>
Date: Tue, 15 Nov 2022 09:02:13 +0800

> to not get affected by this optimization.)  Could do with more test

Hmm, it seems there were discussions about this change before, such as
in [1].

> the subquery based on LATERAL restrictions, but maybe that misses

I think we need to do this, otherwise we'd encounter the problem
described in [2].  In short, the problem is that the constraints imposed
by LATERAL references may make us fail to find any legal join order.  As
an example, consider

explain select * from A where exists
    (select * from B where A.i in (select C.i from C where C.j = B.j));
ERROR:  failed to build any 3-way joins

[1]
https://www.postgresql.org/message-id/flat/CAN_9JTx7N%2BCxEQLnu_uHxx%2BEscSgxLLuNgaZT6Sjvdpt7toy3w%40mail.gmail.com

[2]
https://www.postgresql.org/message-id/CAMbWs49cvkF9akbomz_fCCKS=D5TY=[email-masked]

Thanks
Richard

---

From: vignesh C <[email-masked]>
Date: Fri, 26 Jan 2024 18:16:02 +0530

On Fri, 13 Oct 2023 at 14:09, Alena Rybakina <[email-masked]> wrote:
>
> On 13.10.2023 10:04, Andy Fan wrote:
>>
>> It seems to me that the expressions "=" and "IN" are equivalent here due to the fact that the aggregated subquery returns only one value, and the result with the "IN" operation can be considered as the intersection of elements on the left and right. In this query, we have some kind of set on the left, among which there will be found or not only one element on the right.
>
>
> Yes, they are equivalent at the final result, but there are some
> differences at the execution level.  the '=' case will be transformed
> to a Subplan whose subPlanType is EXPR_SUBLINK, so if there
> is more than 1 rows is returned in the subplan, error will be raised.
>
> select * from tenk1 where
>   ten =  (select ten from tenk1 i where i.two = tenk1.two );
>
> ERROR:  more than one row returned by a subquery used as an expression
>
> However the IN case would not.
> select * from tenk1 where
>   ten =  (select ten from tenk1 i where i.two = tenk1.two ) is OK.
>
>
> I think the test case you added is not related to this feature. the
> difference is there even without the patch.  so I kept the code
> you changed, but not for the test  case.
>
> Yes, I understand and agree with you that we should delete the last queries, except to one.
>
> The query below have a different result compared to master, and it is correct.
>
>
> Without your patch:
>
> explain (costs off)
> +SELECT * FROM tenk1 A LEFT JOIN tenk2 B
> ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
>                                  QUERY PLAN
> -----------------------------------------------------------------------------
>  Nested Loop Left Join
>    ->  Seq Scan on tenk1 a
>    ->  Materialize
>          ->  Seq Scan on tenk2 b
>                Filter: (SubPlan 2)
>                SubPlan 2
>                  ->  Result
>                        InitPlan 1 (returns $1)
>                          ->  Limit
>                                ->  Index Scan using tenk2_hundred on tenk2 c
>                                      Index Cond: (hundred IS NOT NULL)
>                                      Filter: (odd = b.odd)
> (12 rows)
>
>
> After your patch:
>
> postgres=# explain (costs off)
> SELECT * FROM tenk1 A LEFT JOIN tenk2 B
> ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
>
>                            QUERY PLAN
> --------------------------------------------------------------
>   Nested Loop Left Join
>     ->  Seq Scan on tenk1 a
>     ->  Materialize
>           ->  Nested Loop
>                 ->  Seq Scan on tenk2 b
>                 ->  Subquery Scan on "ANY_subquery"
>                       Filter: (b.hundred = "ANY_subquery".min)
>                       ->  Aggregate
>                             ->  Seq Scan on tenk2 c
>                                   Filter: (odd = b.odd)
> (10 rows)
>
>
>>> I took the liberty of adding this to your patch and added myself as reviewer, if you don't mind.
>>
>> Sure, the patch after your modification looks better than the original.
>> I'm not sure how the test case around "because of got one row" is
>> relevant to the current changes.  After we reach to some agreement
>> on the above discussion, I think v4 is good for committer to review!
>>
>>
>> Thank you!) I am ready to discuss it.
>
>
> Actually I meant to discuss the "Unfortunately, I found a request..", looks
> we have reached an agreement there:)
>
> Yes, we have)

Hi Andy Fan,

If the changes of Alena are ok, can you merge the changes and post an
updated version so that CFBot can apply the patch and verify the
changes. As currently CFBot is trying to apply only Alena's changes
and failing with the following at [1]:
=== Applying patches on top of PostgreSQL commit ID
fba2112b1569fd001a9e54dfdd73fd3cb8f16140 ===
=== applying patch ./pull-up.diff
patching file src/test/regress/expected/subselect.out
Hunk #1 succeeded at 1926 with fuzz 2 (offset -102 lines).
patching file src/test/regress/sql/subselect.sql
Hunk #1 FAILED at 1000.
1 out of 1 hunk FAILED -- saving rejects to file
src/test/regress/sql/subselect.sql.rej

[1] - http://cfbot.cputube.org/patch_46_4268.log

Regards,
Vignesh