Re: A new strategy for pull-up correlated ANY_SUBLINK

Hi!

I reviewed your patch and it was interesting for me!

Thank you for the explanation. It was really informative for me!

>
> I think we need the restriction and that should be enough for this feature
> . Given the query Richard provided before:
>
> explain
> select * from tenk1 A where exists
> (select 1 from tenk2 B
> where A.hundred in (select C.hundred FROM tenk2 C
> WHERE c.odd = b.odd));
>
> It first can be converted to the below format without any issue.
>
> SELECT * FROM tenk1 A SEMI JOIN tenk2 B
> on A.hundred in (select C.hundred FROM tenk2 C
> WHERE c.odd = b.odd);
>
> Then without the restriction, since we only pull the varnos from
> sublink->testexpr, then it is {A}, so it convert to
>
> SELECT * FROM
> (tenk1 A SEMI JOIN LATERAL (SELECT c.hundred FROM tenk2 C)
> ON c.odd = b.odd AND a.hundred = v.hundred)
> SEMI JOIN on tenk2 B ON TRUE;
>
> then the above query is NOT A VALID QUERY since:
> 1. The above query is *not* same as
>
> SELECT * FROM (tenk1 A SEMI JOIN tenk2 B) on true
> SEMI JOIN LATERAL (SELECT c.hundred FROM tenk2 C) v
> ON v.odd = b.odd;
>
> 2. The above query requires b.odd when B is not available. So it is
> right that an optimizer can't generate a plan for it. The fix would
> be to do the restriction before applying this optimization.
>
> I'm not sure pull-up-subquery can play any role here, IIUC, the bad thing
> happens before pull-up-subquery.
>
> I also write & analyze more test and found no issue by me
>
> 1. SELECT * FROM tenk1 A LEFT JOIN tenk2 B
> ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
> ==> should not be pull-up to rarg of the left join since A.hundred is not
> available.
>
> 2.  SELECT * FROM tenk1 A LEFT JOIN tenk2 B
> ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = a.odd);
> ==> should not be pull-up to rarg of the left join since A.odd is not
> available.
>
> 3. SELECT * FROM tenk1 A LEFT JOIN tenk2 B
> ON B.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
> ==> should be pull-up to rarg of left join.
>
> 4. SELECT * FROM tenk1 A INNER JOIN tenk2 B
> ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
> ==> pull-up as expected.
>
> 5. SELECT * FROM tenk1 A RIGHT JOIN tenk2 B
> ON A.hundred in (SELECT c.hundred FROM tenk2 C WHERE c.odd = b.odd);
> ==> should not be pull-up into larg of left join since b.odd is not
> available.
>
>
After reviewing, I want to suggest some changes related to the code and
tests.

First of all, I think, it would be better to "treat" change to
"consider" and rewrite the pull-up check condition in two lines:

/*
 * If the sub-select refers to any Vars of the parent query, we so let's
 * considering it as LATERAL.  (Vars of higher levels don't matter here.)
 */

use_lateral = !bms_is_empty(sub_ref_outer_relids) &&
bms_is_subset(sub_ref_outer_relids, available_rels);

if (!use_lateral && !bms_is_empty(sub_ref_outer_relids))
    return NULL;

Secondly, I noticed another interesting feature in your patch and I
think it could be added to the test.

If we get only one row from the aggregated subquery, we can pull-up it
in the subquery scan filter.

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)

It was impossible without 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
         ->  Seq Scan on tenk2 b
               Filter: (SubPlan 1)
               SubPlan 1
                 ->  Aggregate
                       ->  Seq Scan on tenk2 c
                             Filter: (odd = b.odd)
(9 rows)

And I found an alternative query, when aggregated sublink will pull-up
into JoinExpr condition.

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));
                         QUERY PLAN
-------------------------------------------------------------
 Nested Loop Left Join
   ->  Seq Scan on tenk1 a
   ->  Materialize
         ->  Hash Semi Join
*Hash Cond: (b.hundred = "ANY_subquery".count)*
               ->  Seq Scan on tenk2 b
               ->  Hash
                     ->  Subquery Scan on "ANY_subquery"
                           ->  HashAggregate
                                 Group Key: c.odd
                                 ->  Seq Scan on tenk2 c
(11 rows)

Unfortunately, I found a request when sublink did not pull-up, as in the
examples above. I couldn't quite figure out why.

create table a (x int, y int, z int, t int);
create table b (x int, t int);
create unique index on a (t, x);
create index on b (t,x);
insert into a select id, id, id, id FROM generate_series(1,100000) As id;
insert into b select id, id FROM generate_series(1,1000) As id;

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);

QUERY PLAN
------------------------------------------------------------------------------------------------------------
 Hash Right Join (actual time=1.150..58.512 rows=1000 loops=1)
   Hash Cond: (a.x = b.x)
*Join Filter: (SubPlan 2)*
   Buffers: shared hit=3546
   ->  Seq Scan on a (actual time=0.023..15.798 rows=100000 loops=1)
         Buffers: shared hit=541
   ->  Hash (actual time=1.038..1.042 rows=1000 loops=1)
         Buckets: 4096  Batches: 1  Memory Usage: 72kB
         Buffers: shared hit=5
         ->  Seq Scan on b (actual time=0.047..0.399 rows=1000 loops=1)
               Buffers: shared hit=5
   SubPlan 2
     ->  Result (actual time=0.018..0.018 rows=1 loops=1000)
           Buffers: shared hit=3000
           InitPlan 1 (returns $2)
             ->  Limit (actual time=0.015..0.016 rows=1 loops=1000)
                   Buffers: shared hit=3000
                   ->  Index Only Scan using a_t_x_idx on a a0 (actual
time=0.014..0.014 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.630 ms
 Execution Time: 58.941 ms
(23 rows)

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 took the liberty of adding this to your patch and added myself as
reviewer, if you don't mind.

--
Regards,
Alena Rybakina