Subject: Re: A new strategy for pull-up correlated ANY_SUBLINK

From: Alena Rybakina <[email-masked]>
Date: Fri, 13 Oct 2023 02:14:13 +0300

On 12.10.2023 10:52, Andy Fan wrote:
>
>     Unfortunately, I found a request when sublink did not pull-up, as
>     in the
>
>     examples above. I couldn't quite figure out why.
>
> I'm not sure what you mean with the "above", I guess it should be the 
> "below"?

Yes, you are right)

>
>     explain (analyze, costs off, buffers)
>     select b.x, b.x, a.y
>     from b
>         left join a
>             on b.x=a.x and
>     *b.t in
>                 (select max(a0.t) *
>                  from a a0
>                  where a0.x = b.x and
>                        a0.t = b.t);
>
> ...
>
>        SubPlan 2
>
>
> Here the sublink can't be pulled up because of its reference to
> the  LHS of left join, the original logic is that no matter the 'b.t 
> in ..'
> returns the true or false,  the rows in LHS will be returned.  If we
> pull it up to LHS, some rows in LHS will be filtered out, which
> breaks its original semantics.

Thanks for the explanation, it became more clear to me here.

>     I thought it would be:
>
>     explain (analyze, costs off, buffers)
>     select b.x, b.x, a.y
>     from b
>         left join a on
>             b.x=a.x and
>     *b.t =
>                 (select max(a0.t) *
>                  from a a0
>                  where a0.x = b.x and
>                        a0.t <= b.t);
>
>     QUERY PLAN
>     ---------------------------------------------------------------------------------------------------------------------
>      Hash Right Join (actual time=1.181..67.927 rows=1000 loops=1)
>        Hash Cond: (a.x = b.x)
>     *Join Filter: (b.t = (SubPlan 2))*
>        Buffers: shared hit=3546
>        ->  Seq Scan on a (actual time=0.022..17.109 rows=100000 loops=1)
>              Buffers: shared hit=541
>        ->  Hash (actual time=1.065..1.068 rows=1000 loops=1)
>              Buckets: 4096  Batches: 1  Memory Usage: 72kB
>              Buffers: shared hit=5
>              ->  Seq Scan on b (actual time=0.049..0.401 rows=1000
>     loops=1)
>                    Buffers: shared hit=5
>        SubPlan 2
>          ->  Result (actual time=0.025..0.025 rows=1 loops=1000)
>                Buffers: shared hit=3000
>                InitPlan 1 (returns $2)
>                  ->  Limit (actual time=0.024..0.024 rows=1 loops=1000)
>                        Buffers: shared hit=3000
>                        ->  Index Only Scan Backward using a_t_x_idx on
>     a a0 (actual time=0.023..0.023 rows=1 loops=1000)
>                              Index Cond: ((t IS NOT NULL) AND (t <=
>     b.t) AND (x = b.x))
>                              Heap Fetches: 1000
>                              Buffers: shared hit=3000
>      Planning Time: 0.689 ms
>      Execution Time: 68.220 ms
>     (23 rows)
>
>     If you noticed, it became possible after replacing the "in"
>     operator with "=".
>
> I didn't notice much difference between the 'in'  and '=',  maybe I
> missed something?

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. In general, this expression can be considered as b=const, so 
push down will be applied to b and we can filter b during its scanning 
by the subquery's result.
But I think your explanation is necessary here, that this is all 
possible, because we can pull up the sublink here, since filtering is 
allowed on the right side (the nullable side) and does not break the 
semantics of LHS. But in contrast, I also added two queries where 
pull-up is impossible and it is not done here. Otherwise if filtering 
was applied on the left it would be mistake.

To be honest, I'm not sure if this explanation is needed in the test 
anymore, so I didn't add it.

explain (costs off)
SELECT * FROM tenk1 A LEFT JOIN tenk2 B
ON A.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
                            QUERY PLAN
-----------------------------------------------------------------
  Nested Loop Left Join
    Join Filter: (SubPlan 2)
    ->  Seq Scan on tenk1 a
    ->  Materialize
          ->  Seq Scan on tenk2 b
    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)

explain (costs off)
SELECT * FROM tenk1 A LEFT JOIN tenk2 B
ON A.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd));
             QUERY PLAN
-----------------------------------
  Nested Loop Left Join
    Join Filter: (hashed SubPlan 1)
    ->  Seq Scan on tenk1 a
    ->  Materialize
          ->  Seq Scan on tenk2 b
    SubPlan 1
      ->  HashAggregate
            Group Key: c.odd
            ->  Seq Scan on tenk2 c
(9 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.

-- 
Regards,
Alena Rybakina
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index b70b346696d..0b8f28b157f 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -2028,7 +2028,7 @@ ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
          ->  Seq Scan on tenk2 b
 (11 rows)
 
--- we can pull up the aggregate sublink into the subquery scan because of got one row.
+-- we can pull up the aggregate sublink into RHS of a left join.
 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);
@@ -2052,7 +2052,6 @@ ON B.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
                                                Filter: (odd = b.odd)
 (16 rows)
 
--- we can pull up the aggregate sublink into the JoinExpr.
 explain (costs off)
 SELECT * FROM tenk1 A LEFT JOIN tenk2 B
 ON B.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd));
@@ -2071,3 +2070,39 @@ ON B.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd));
                                  ->  Seq Scan on tenk2 c
 (11 rows)
 
+-- we can't pull up the aggregate sublink into LHS of a left join.
+explain (costs off)
+SELECT * FROM tenk1 A LEFT JOIN tenk2 B
+ON A.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
+                           QUERY PLAN                            
+-----------------------------------------------------------------
+ Nested Loop Left Join
+   Join Filter: (SubPlan 2)
+   ->  Seq Scan on tenk1 a
+   ->  Materialize
+         ->  Seq Scan on tenk2 b
+   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)
+
+explain (costs off)
+SELECT * FROM tenk1 A LEFT JOIN tenk2 B
+ON A.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd));
+            QUERY PLAN             
+-----------------------------------
+ Nested Loop Left Join
+   Join Filter: (hashed SubPlan 1)
+   ->  Seq Scan on tenk1 a
+   ->  Materialize
+         ->  Seq Scan on tenk2 b
+   SubPlan 1
+     ->  HashAggregate
+           Group Key: c.odd
+           ->  Seq Scan on tenk2 c
+(9 rows)
+
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index 5d33eb39baa..c02513c4989 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -1001,12 +1001,20 @@ explain (costs off)
 SELECT * FROM tenk1 A INNER JOIN tenk2 B
 ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
 
--- we can pull up the aggregate sublink into the subquery scan because of got one row.
+-- we can pull up the aggregate sublink into RHS of a left join.
 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);
 
--- we can pull up the aggregate sublink into the JoinExpr.
 explain (costs off)
 SELECT * FROM tenk1 A LEFT JOIN tenk2 B
-ON B.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd));
\ No newline at end of file
+ON B.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd));
+
+-- we can't pull up the aggregate sublink into LHS of a left join.
+explain (costs off)
+SELECT * FROM tenk1 A LEFT JOIN tenk2 B
+ON A.hundred in (SELECT min(c.hundred) FROM tenk2 C WHERE c.odd = b.odd);
+
+explain (costs off)
+SELECT * FROM tenk1 A LEFT JOIN tenk2 B
+ON A.hundred in (SELECT count(c.hundred) FROM tenk2 C group by (c.odd));
\ No newline at end of file

---

From: Andy Fan <[email-masked]>
Date: Fri, 13 Oct 2023 15:04:45 +0800

> 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.

I took the liberty of adding this to your patch and added myself as
>> reviewer, if you don't mind.
>>

Actually I meant to discuss the "Unfortunately, I found a request..", looks
we have reached an agreement there:)

-- 
Best Regards
Andy Fan

---

From: Andy Fan <[email-masked]>
Date: Fri, 13 Oct 2023 15:29:25 +0800

Hi Tom,

Would you like to have a look at this?  The change is not big and the
optimization has also been asked for many times. The attached is the
v5 version and  I also try my best to write a good commit message.

Here is the commit fest entry:

https://commitfest.postgresql.org/45/4268/

---

From: Alena Rybakina <[email-masked]>
Date: Fri, 13 Oct 2023 11:39:41 +0300

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, 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.
>>
Yes, we have)

-- 
Regards,
Alena Rybakina
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index 17df6b5dc9c..e41b728df83 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -2028,3 +2028,27 @@ ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
          ->  Seq Scan on tenk2 b
 (11 rows)
 
+-- we can pull up the aggregate sublink into RHS of a left join.
+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
+               ->  Memoize
+                     Cache Key: b.hundred, b.odd
+                     Cache Mode: binary
+                     ->  Subquery Scan on "ANY_subquery"
+                           Filter: (b.hundred = "ANY_subquery".min)
+                           ->  Result
+                                 InitPlan 1 (returns $1)
+                                   ->  Limit
+                                         ->  Index Scan using tenk2_hundred on tenk2 c
+                                               Index Cond: (hundred IS NOT NULL)
+                                               Filter: (odd = b.odd)
+(16 rows)
+
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index 49ce5fc99a8..2f3601a0582 100644
--- a/src/test/regress/sql/subselect.sql
+++ b/src/test/regress/sql/subselect.sql
@@ -1000,3 +1000,8 @@ ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
 explain (costs off)
 SELECT * FROM tenk1 A INNER JOIN tenk2 B
 ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
+
+-- we can pull up the aggregate sublink into RHS of a left join.
+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);
\ No newline at end of file

---

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:
>> 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, 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)
>                 ->  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.
>>

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

---

From: Alexander Korotkov <[email-masked]>
Date: Tue, 13 Feb 2024 12:50:40 +0200

Hi!

> and failing with the following at [1]:

I think this is a very nice and pretty simple optimization.  I've
merged the changes by Alena, and slightly revised the code changes in
convert_ANY_sublink_to_join().  I'm going to push this if there are no
objections.

------
Regards,
Alexander Korotkov

---

From: Andy Fan <[email-masked]>
Date: Thu, 15 Feb 2024 17:51:28 +0800

Hi Alexander,

> convert_ANY_sublink_to_join().  I'm going to push this if there are no

Thanks for picking up this! I double checked the patch, it looks good to
me. 

-- 
Best Regards
Andy Fan