Re: A new strategy for pull-up correlated ANY_SUBLINK - Mailing list pgsql-hackers

From Alena Rybakina
Subject Re: A new strategy for pull-up correlated ANY_SUBLINK
Date
Msg-id 602d6b44-c734-4f7f-8999-99b6cac9bf17@yandex.ru
Whole thread Raw
In response to Re: A new strategy for pull-up correlated ANY_SUBLINK  (Andy Fan <zhihui.fan1213@gmail.com>)
Responses Re: A new strategy for pull-up correlated ANY_SUBLINK
List pgsql-hackers
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
Attachment

pgsql-hackers by date:

Previous
From: Noah Misch
Date:
Subject: Re: interval_ops shall stop using btequalimage (deduplication)
Next
From: Michael Paquier
Date:
Subject: Re: odd buildfarm failure - "pg_ctl: control file appears to be corrupt"