MIME-Version: 1.0
References: <0b1f670d-b39d-4966-bf32-f0d502ebc564@postgrespro.ru>
 <CAEudQAoD707uh5Pjpg5NMyF-QO=fzajA+BmtcoqQAeXN1C+TkQ@mail.gmail.com>
 <46bc4eaf-58c5-42ab-8041-d3380a0768de@postgrespro.ru>
 <9b041978-06e3-4a50-8a5d-dacbb054f23e@tantorlabs.com>
 <8d7cbbf6-ddc0-4696-8af2-a68d740e14f2@postgrespro.ru>
 <6078f7e1-4b29-4b31-bd28-b84149e404e4@postgrespro.ru>
 <975a3736-a8b5-49b3-8009-4d4e86867aa1@postgrespro.ru>
 <0adbf75a-2059-4bb7-b878-c33892dbc1f0@tantorlabs.com>
 <300d7bb0-345c-4c0b-a0ef-4de573fcc94b@postgrespro.ru>
 <e172de23-7acb-4330-a40a-58ead7a47944@postgrespro.ru>
 <32446f52-1b18-499a-a77b-d6b66ad0f4cf@tantorlabs.com>
 <87a6fcbf-929a-408a-9471-28be3080254a@postgrespro.ru>
 <4e9d279c-83c1-42d3-b74d-7366ecd7f085@tantorlabs.com>
 <0c498546-8af0-4aec-98fa-ad4f373cf711@yandex.ru>
 <0686b354-57dc-46e9-b756-21661c656c10@yandex.ru>
In-Reply-To: <0686b354-57dc-46e9-b756-21661c656c10@yandex.ru>
From: Peter Petrov <pspetrov91@gmail.com>
Date: Fri, 8 May 2026 20:45:31 +0300
Message-ID: 
 <CAJ-KsAw0zS_OEcEraRdgD0wJF5-BHW9nWy286cyQryzo_HTD2Q@mail.gmail.com>
Subject: Re: pull-up subquery if JOIN-ON contains refs to upper-query
To: Alena Rybakina <lena.ribackina@yandex.ru>
Cc: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>,
	PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>,
 Ranier Vilela <ranier.vf@gmail.com>,
	David Rowley <dgrowleyml@gmail.com>
Content-Type: multipart/alternative; boundary="0000000000004a5d05065151f761"
Archived-At: 
 <https://www.postgresql.org/message-id/CAJ-KsAw0zS_OEcEraRdgD0wJF5-BHW9nWy286cyQryzo_HTD2Q%40mail.gmail.com>
Precedence: bulk

--0000000000004a5d05065151f761
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hello Alena!

Sorry for my long silence, if you are interested in my thoughts about your
patch then here they are:

1)  First of all, let's read the comment below.

/*
 * Separate out the WHERE clause.  (We could theoretically also remove
 * top-level plain JOIN/ON clauses, but it's probably not worth the
 * trouble.)
 */

We need to separate two things: the jointree and the WHERE clause, so it's
possible to do something like this

whereClause =3D subselect->jointree->quals;
subselect->jointree->quals =3D NULL;

jointree =3D subselect->jointree;
subselect->jointree =3D NULL;

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

/* Do our checks in the jointree and stop if we can't do pullup */

/* Return the jointree back */
subselect->jointree =3D jointree;

I think it's more clear than in the patch right now.

2) We don't need to use get_relids_in_jointree() and nullable_above since
the tree's traversing is from the top to the bottom and we know that

     in LEFT JOIN and FULL JOIN LHS is nullable
     in RIGHT JOIN and FULL JOIN RHS  is nullable

So we can use a boolean variables like this

rarg_is_nullable =3D (is_nullable_side ||
                                  j->jointype =3D=3D JOIN_FULL ||
                                  j->jointype =3D=3D JOIN_LEFT);

larg_is_nullable =3D (is_nullable_side ||
                                 j->jointype =3D=3D JOIN_FULL ||
                                 j->jointype =3D=3D JOIN_RIGHT);

And then work with them. I suspect it will be much easier to follow that in
the patch right now.

I fear that you don't check FULL JOINS here.

3) To be honest, we just work with the top jointree, we don't descend to
subqueries, therefore, I am not sure that the mutator is a good name here.

    AFAICS, mutators were designed to modify something including some parts
of the subqueries but it's not the case here.

    It's a simple jointree traversal, we don't need HoistJoinQualsContext
as well.

    I think, we need three things here:

    Node *node - the node in the jointree we are working with

    bool is_nullable_side - are we on the nullable side of some outer join

    List **exprs - the list in which we collect JoinExpr and FromExpr with
outer references.

    I propose just traverse the jointree, make our checks and then collect
JoinExpr and FromExpr for the further processing if everything is good.

4) After checking the WHERE clause and the jointree we can traverse our
list, make a new whereClause by appending quals with outer references and
then replace quals in JoinExprs to constant true.

    Something like make_and_qual()

5) I have also noticed that you are using canonicalize_qual()

    I suspect we don't need it either since it will be called later. And
here is the stack

    subquery_planner
       pull_up_sublinks(root)
       preprocess_qual_conditions(root, (Node *) parse->jointree)
           j->quals =3D preprocess_expression(root, j->quals, EXPRKIND_QUAL=
)
              expr =3D (Node *) canonicalize_qual((Expr *) expr, false)
                 find_duplicate_ors(qual, is_check)

   So we will flatten all nested BoolExpr with the type BOOL_AND.

6) I have noticed the new output from one regression test. The previous
output was

    Merge Anti Join
      Merge Cond: (t1.c1 =3D t2.c2)
       ->  Sort
               Sort Key: t1.c1
               ->  Seq Scan on tt4x t1
       ->  Sort

   and the new output is the Hash Anti Join

   Hash Anti Join
       Hash Cond: (t1.c1 =3D t2.c2)
        ->  Seq Scan on tt4x t1
        ->  Hash

  This is very suspicious, why does this patch cause such changes?

7) There is a SubLink which won't be pulled up, you can see it below

explain (COSTS OFF)
SELECT *
  FROM tenk1 A
 WHERE EXISTS (SELECT 1
                                 FROM tenk2 B, (SELECT f.hundred
                                                               FROM (SELECT
A.hundred) AS f
                                                           ) AS v
                              WHERE B.hundred =3D v.hundred
                             );
And the reason is the following. (SELECT A.hundred) is the subquery and
won't be processed until the function pull_up_sublinks() finishes its job.

But it leads us to an interesting observation. Maybe we could process it
somewhere in the SS_process_sublinks().

Perhaps, f and v subqueries could be pulled up and then the EXISTS sublink
could be replaced with a SEMI JOIN.

I don't know whether we should solve this problem right now. I have never
seen such queries in real workloads but it doesn't mean that they don't
exist.

In short, I think your patch can be simplified.


=D0=BF=D1=82, 8 =D0=BC=D0=B0=D1=8F 2026=E2=80=AF=D0=B3. =D0=B2 20:37, Alena=
 Rybakina <lena.ribackina@yandex.ru>:

>
> Feel free to review my patch!
>
> -----------
> Best regards,
> Yandex Cloud
> Alena Rybakina
>

--0000000000004a5d05065151f761
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><p>Hello Alena!<br>
      <br>
      Sorry for my long silence, if you are interested in my thoughts
      about your patch then here they are:<br>
      <br>
      1)=C2=A0 First of all, let&#39;s read the comment below.<br>
      <br>
      /*<br>
      =C2=A0* Separate out the WHERE clause.=C2=A0 (We could theoretically =
also
      remove<br>
      =C2=A0* top-level plain JOIN/ON clauses, but it&#39;s probably not wo=
rth
      the<br>
      =C2=A0* trouble.)<br>
      =C2=A0*/<br>
      <br>
      We need to separate two things: the jointree and the WHERE clause,
      so it&#39;s possible to do something like this<br>
      <br>
      whereClause =3D subselect-&gt;jointree-&gt;quals;<br>
      subselect-&gt;jointree-&gt;quals =3D NULL;<br>
      <br>
      jointree =3D subselect-&gt;jointree;<br>
      subselect-&gt;jointree =3D NULL;<br>
      <br>
      if (contain_vars_of_level((Node *) subselect, 1))<br>
      =C2=A0 =C2=A0 return NULL;<br>
    </p>
    <p>/* Do our checks in the jointree and stop if we can&#39;t do pullup
      */</p>
    <p>/* Return the jointree back */<br>
      subselect-&gt;jointree =3D jointree;<br>
      <br>
      I think it&#39;s more clear than in the patch right now.</p>
    <p>2) We don&#39;t need to use get_relids_in_jointree() and
      nullable_above since the tree&#39;s traversing is from the top to the
      bottom and we know that</p>
    <p>=C2=A0 =C2=A0 =C2=A0in LEFT JOIN and FULL JOIN LHS is nullable<br>
      =C2=A0 =C2=A0 =C2=A0in RIGHT JOIN and FULL JOIN RHS=C2=A0 is nullable=
<br>
      <br>
      So we can use a boolean variables like this<br>
    </p>
    <p>rarg_is_nullable =3D (is_nullable_side ||<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 j-&gt;jointype =3D=3D JOI=
N_FULL ||<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 j-&gt;jointype =3D=3D JOI=
N_LEFT);<br>
      <br>
      larg_is_nullable =3D (is_nullable_side ||<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0j-&gt;jointype =3D=3D JOIN=
_FULL ||<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0j-&gt;jointype =3D=3D JOIN=
_RIGHT);<br>
      <br>
      And then work with them. I suspect it will be much easier to
      follow that in the patch right now.<br>
      <br>
      I fear that you don&#39;t check FULL JOINS here.</p>
    <p>3) To be honest, we just work with the top jointree, we don&#39;t
      descend to subqueries, therefore, I am not sure that the mutator
      is a good name here.<br>
      <br>
      =C2=A0 =C2=A0 AFAICS, mutators were designed to modify something incl=
uding
      some parts of the subqueries but it&#39;s not the case here.<br>
      <br>
      =C2=A0 =C2=A0 It&#39;s a simple jointree traversal, we don&#39;t need
      HoistJoinQualsContext as well.<br>
      <br>
      =C2=A0 =C2=A0 I think, we need three things here:</p>
    <p>=C2=A0 =C2=A0 Node *node - the node in the jointree we are working w=
ith</p>
    <p>=C2=A0 =C2=A0 bool is_nullable_side - are we on the nullable side of=
 some
      outer join<br>
      <br>
      =C2=A0 =C2=A0 List **exprs - the list in which we collect JoinExpr an=
d
      FromExpr with outer references.<br>
      <br>
      =C2=A0 =C2=A0 I propose just traverse the jointree, make our checks a=
nd then
      collect JoinExpr and FromExpr for the further processing if
      everything is good.=C2=A0 =C2=A0 =C2=A0</p>
    <p>4) After checking the WHERE clause and the jointree we can
      traverse our list, make a new whereClause by appending quals with
      outer references and then replace quals in JoinExprs to constant
      true.<br>
      <br>
      =C2=A0 =C2=A0 Something like make_and_qual()<br>
      <br>
      5) I have also noticed that you are using canonicalize_qual()<br>
      <br>
      =C2=A0 =C2=A0 I suspect we don&#39;t need it either since it will be =
called
      later. And here is the stack<br>
    </p>
    <p>=C2=A0 =C2=A0 subquery_planner<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0pull_up_sublinks(root)<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0preprocess_qual_conditions(root, (Node *)
      parse-&gt;jointree)<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0j-&gt;quals =3D preprocess_e=
xpression(root, j-&gt;quals,
      EXPRKIND_QUAL)<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 expr =3D (Node *) ca=
nonicalize_qual((Expr *) expr,
      false)<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0find_du=
plicate_ors(qual, is_check)=C2=A0=C2=A0<br>
      =C2=A0<br>
      =C2=A0 =C2=A0So we will flatten all nested BoolExpr with the type BOO=
L_AND.<br>
      <br>
      6) I have noticed the new output from one regression test. The
      previous output was<br>
      <br>
      =C2=A0 =C2=A0 Merge Anti Join<br>
      =C2=A0 =C2=A0 =C2=A0 Merge Cond: (t1.c1 =3D t2.c2)<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt;=C2=A0 Sort<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Sort Key: t1.c=
1<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt;=C2=A0 Se=
q Scan on tt4x t1<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt;=C2=A0 Sort<br>
      <br>
      =C2=A0 =C2=A0and the new output is the Hash Anti Join<br>
    </p>
    <p>=C2=A0 =C2=A0Hash Anti Join<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0Hash Cond: (t1.c1 =3D t2.c2)<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 -&gt;=C2=A0 Seq Scan on tt4x t1<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 -&gt;=C2=A0 Hash<br>
      =C2=A0 =C2=A0<br>
      =C2=A0 This is very suspicious, why does this patch cause such change=
s?<br>
      <br>
      7) There is a SubLink which won&#39;t be pulled up, you can see it
      below<br>
      <br>
      explain (COSTS OFF)<br>
      SELECT *<br>
      =C2=A0 FROM tenk1 A<br>
      =C2=A0WHERE EXISTS (SELECT 1<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0FROM tenk2 B, (SELECT f.hundred<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0
      =C2=A0FROM (SELECT A.hundred) AS f<br>
      =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0) AS v<br=
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 WHERE B.hundred =3D v.hundred<br>=C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0);</p>
    <div class=3D"gmail-moz-cite-prefix">And the reason is the following. (=
SELECT
      A.hundred) is the subquery and won&#39;t be processed until the
      function pull_up_sublinks() finishes its job.<br>
      <br>
      But it leads us to an interesting observation. Maybe we could
      process it somewhere in the SS_process_sublinks().<br>
      <br>
      Perhaps, f and v subqueries could be pulled up and then the EXISTS
      sublink could be replaced with a SEMI JOIN.<br>
      <br>
      I don&#39;t know whether we should solve this problem right now. I
      have never seen such queries in real workloads but it doesn&#39;t mea=
n
      that they don&#39;t exist.<br>
      <br>
      In short, I think your patch can be simplified.</div><br></div><br><d=
iv class=3D"gmail_quote gmail_quote_container"><div dir=3D"ltr" class=3D"gm=
ail_attr">=D0=BF=D1=82, 8 =D0=BC=D0=B0=D1=8F 2026=E2=80=AF=D0=B3. =D0=B2 20=
:37, Alena Rybakina &lt;<a href=3D"mailto:lena.ribackina@yandex.ru">lena.ri=
backina@yandex.ru</a>&gt;:<br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><br>
Feel free to review my patch!<br>
<br>
-----------<br>
Best regards,<br>
Yandex Cloud<br>
Alena Rybakina<br>
</blockquote></div></div>

--0000000000004a5d05065151f761--