Thread: pgsql: Avoid mislabeling of lateral references when pulling up a subque

Avoid mislabeling of lateral references when pulling up a subquery.

If we are pulling up a subquery that's under an outer join, and
the subquery's target list contains a strict expression that uses
both a subquery variable and a lateral-reference variable, it's okay
to pull up the expression without wrapping it in a PlaceHolderVar.
That's safe because if the subquery variable is forced to NULL
by the outer join, the expression result will come out as NULL too,
so we don't have to force that outcome by evaluating the expression
below the outer join.  It'd be correct to wrap in a PHV, but that can
lead to very significantly worse plans, since we'd then have to use
a nestloop plan to pass down the lateral reference to where the
expression will be evaluated.

However, when we do that, we should not mark the lateral reference
variable as being nulled by the outer join, because it isn't after
we pull up the expression in this way.  So the marking logic added
by cb8e50a4a was incorrect in this detail, leading to "wrong
varnullingrels" errors from the consistency-checking logic in
setrefs.c.  It seems to be sufficient to just not mark lateral
references at all in this case.  (I have a nagging feeling that more
complexity may be needed in cases where there are several levels of
outer join, but some attempts to break it with that didn't succeed.)

Per report from Bertrand Mamasam.  Back-patch to v16, as the previous
patch was.

Discussion: https://postgr.es/m/CACZ67_UA_EVrqiFXJu9XK50baEpH=ofEPJswa2kFxg6xuSw-ww@mail.gmail.com

Branch
------
REL_16_STABLE

Details
-------
https://git.postgresql.org/pg/commitdiff/85990e2fd5610576635c65db9292297b1730c947

Modified Files
--------------
src/backend/optimizer/prep/prepjointree.c | 19 +++++++++++--
src/test/regress/expected/subselect.out   | 47 +++++++++++++++++++++++++++++++
src/test/regress/sql/subselect.sql        | 16 +++++++++++
3 files changed, 80 insertions(+), 2 deletions(-)

On Fri, Nov 29, 2024 at 7:33 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> It seems to be sufficient to just not mark lateral
> references at all in this case.  (I have a nagging feeling that more
> complexity may be needed in cases where there are several levels of
> outer join, but some attempts to break it with that didn't succeed.)

You're right about your feeling.  Here is a query that breaks it.

create table t (a int, b int);

explain (costs off)
select x from
  t t1 left join
  (t t2 left join
   lateral (select t2.a+t3.a as x, * from t t3) t3 on t2.a <> t3.a)
  on t1.b = t2.b;
ERROR:  wrong varnullingrels (b) (expected (b 5)) for Var 2/1

'x' is nulled by ojrelids {4, 5}.  When pulling up the subquery, it's
right that we should not mark the lateral reference variable 't2' as
being nulled by {4}, but we should mark it as being nulled by {5}.

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:
> On Fri, Nov 29, 2024 at 7:33 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> It seems to be sufficient to just not mark lateral
>> references at all in this case.  (I have a nagging feeling that more
>> complexity may be needed in cases where there are several levels of
>> outer join, but some attempts to break it with that didn't succeed.)

> You're right about your feeling.  Here is a query that breaks it.

Ah, thanks for the test case.  I'll look into it tomorrow.

            regards, tom lane

Richard Guo <guofenglinux@gmail.com> writes:
> I spent some time looking into this issue.

Thanks for looking at it!

> First of all, the lateral references cannot be outside of the lowest
> outer join above the subquery; otherwise, is_simple_subquery() would
> consider the subquery not eligible for pull-up.

Yeah.  While looking at this, I've been wondering if we don't have
enough infrastructure now to relax is_simple_subquery's restrictions.
The way it is now was designed to keep the world safe for placing
quals based on is_pushed_down flags (cf c64de21e9), but maybe with
OJ-labeled Vars we don't need to be so restrictive.  Clearly, a
back-patched bug fix is no place to actually make such a change,
but we might want to code the fix with the thought in mind that that
could happen later.  In particular, I'm not sure I buy the theory
that there's just one relid to get rid of when calculating the
appropriate nullingrels for a lateral reference.

Also, I don't think I buy the assumption that all the lateral
references need the same nullingrels.  Your test case could easily
be extended to have lateral refs coming from two different levels
of outer join.  So I think we need to calculate the right new
nullingrels for each lateral-ref varno appearing in the expression,
and do add_nulling_relids() over again for each one.

The ideas I'd been toying with last night involved a pre-scan over
the join tree to calculate the potential nullingrels of each leaf RTE
(same idea as RelOptInfo.nulling_relids, but of course we don't have
any RelOptInfos yet).  That seems painful though because we'd have to
update the data structure somehow after each subquery pullup.  It
might be better just to assume that pulled-up lateral references are
uncommon and push the work into the case where we have one, rather than
try to do setup work to make that case cheaper.  With that approach,
you could imagine writing a function that traverses the join tree
from the top and computes the set of OJ relids that can potentially
null a particular target relid.  Then we'd intersect that with the
varnullingrels of the Var being replaced to derive the correct
nullingrels for the lateral-ref Vars.  (If we do it like that,
we may not need lowest_nullable_side etc yet, but I attach some
comments on that code anyway.)

> I've drafted a patch based on this idea.  I borrowed the concept of
> lowest_nullable_relids from another patch of mine [1], which uses
> lowest_nullable_relids to avoid wrapping lateral references that are
> under the same lowest nulling outer join.

I find lowest_nullable_side fairly messy/confusing, in particular
that it might point at something that's not either side of the
lowest_outer_join parameter.  I wonder whether there's another way
to do that.  At the very least, the header comment for
pull_up_subqueries_recurse should point out that the two values
might be unrelated.

The calculation of lowest_nullable_relids in pull_up_simple_subquery
doesn't feel right --- it needs some comments at least.

On the same reasoning that a back-patched fix is no place to be
introducing unnecessary changes, I don't agree with revising the
rules for whether to wrap plain Vars/PHVs in this patch.  We can
do that in a separate HEAD-only patch.

Do you want to continue working on this, or shall I take it?
The bug is my fault in the end :-(

            regards, tom lane

I wrote:
> The ideas I'd been toying with last night involved a pre-scan over
> the join tree to calculate the potential nullingrels of each leaf RTE
> (same idea as RelOptInfo.nulling_relids, but of course we don't have
> any RelOptInfos yet).  That seems painful though because we'd have to
> update the data structure somehow after each subquery pullup.

I realized that we can make that work by doing the pre-calculation
at the start of each pull_up_simple_subquery.  We only have to do
it for subqueries marked LATERAL, so this doesn't seem too horribly
inefficient.  Draft patch attached.  I didn't spend effort on
devising test cases, but it works for your example.

            regards, tom lane

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 2e0d41a8d1..ff9c1cd24e 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -42,6 +42,17 @@
 #include "rewrite/rewriteManip.h"


+typedef struct nullingrel_info
+{
+    /*
+     * For each leaf RTE, nullingrels[rti] is the set of relids of outer joins
+     * that potentially null that RTE.
+     */
+    Relids       *nullingrels;
+    /* Length of range table (maximum index in nullingrels[]) */
+    int            rtlength;        /* used only for assertion checks */
+} nullingrel_info;
+
 typedef struct pullup_replace_vars_context
 {
     PlannerInfo *root;
@@ -49,6 +60,8 @@ typedef struct pullup_replace_vars_context
     RangeTblEntry *target_rte;    /* RTE of subquery */
     Relids        relids;            /* relids within subquery, as numbered after
                                  * pullup (set only if target_rte->lateral) */
+    nullingrel_info *nullinfo;    /* per-RTE nullingrel info (set only if
+                                 * target_rte->lateral) */
     bool       *outer_hasSubLinks;    /* -> outer query's hasSubLinks */
     int            varno;            /* varno of subquery */
     bool        wrap_non_vars;    /* do we need all non-Var outputs to be PHVs? */
@@ -142,6 +155,9 @@ static void substitute_phv_relids(Node *node,
 static void fix_append_rel_relids(PlannerInfo *root, int varno,
                                   Relids subrelids);
 static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
+static nullingrel_info *get_nullingrels(Query *parse);
+static void get_nullingrels_recurse(Node *jtnode, Relids upper_nullingrels,
+                                    nullingrel_info *info);


 /*
@@ -1259,10 +1275,16 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
     rvcontext.targetlist = subquery->targetList;
     rvcontext.target_rte = rte;
     if (rte->lateral)
+    {
         rvcontext.relids = get_relids_in_jointree((Node *) subquery->jointree,
                                                   true, true);
-    else                        /* won't need relids */
+        rvcontext.nullinfo = get_nullingrels(parse);
+    }
+    else                        /* won't need these fields */
+    {
         rvcontext.relids = NULL;
+        rvcontext.nullinfo = NULL;
+    }
     rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
     rvcontext.varno = varno;
     /* this flag will be set below, if needed */
@@ -1809,7 +1831,8 @@ pull_up_simple_values(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte)
     rvcontext.root = root;
     rvcontext.targetlist = tlist;
     rvcontext.target_rte = rte;
-    rvcontext.relids = NULL;
+    rvcontext.relids = NULL;    /* can't be any lateral references here */
+    rvcontext.nullinfo = NULL;
     rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
     rvcontext.varno = varno;
     rvcontext.wrap_non_vars = false;
@@ -1971,9 +1994,10 @@ pull_up_constant_function(PlannerInfo *root, Node *jtnode,
     /*
      * Since this function was reduced to a Const, it doesn't contain any
      * lateral references, even if it's marked as LATERAL.  This means we
-     * don't need to fill relids.
+     * don't need to fill relids or nullinfo.
      */
     rvcontext.relids = NULL;
+    rvcontext.nullinfo = NULL;

     rvcontext.outer_hasSubLinks = &parse->hasSubLinks;
     rvcontext.varno = ((RangeTblRef *) jtnode)->rtindex;
@@ -2688,9 +2712,42 @@ pullup_replace_vars_callback(Var *var,
         {
             /*
              * There should be Vars/PHVs within the expression that we can
-             * modify.  Per above discussion, modify only Vars/PHVs of the
-             * subquery, not lateral references.
+             * modify.  Vars/PHVs of the subquery should have the full
+             * var->varnullingrels added to them, but if there are lateral
+             * references within the expression, those must be marked with
+             * only the nullingrels that potentially apply to them.  That
+             * could be different for different lateral relations, so we have
+             * to do this work for each one.
              */
+            if (rcon->target_rte->lateral)
+            {
+                nullingrel_info *nullinfo = rcon->nullinfo;
+                Relids        lvarnos;
+                int            lvarno;
+
+                /*
+                 * Identify lateral varnos used within newnode.  We must do
+                 * this before injecting var->varnullingrels into the tree.
+                 */
+                lvarnos = pull_varnos(rcon->root, newnode);
+                lvarnos = bms_del_members(lvarnos, rcon->relids);
+                /* For each one, add relevant nullingrels if any */
+                lvarno = -1;
+                while ((lvarno = bms_next_member(lvarnos, lvarno)) >= 0)
+                {
+                    Relids        lnullingrels;
+
+                    Assert(lvarno > 0 && lvarno <= nullinfo->rtlength);
+                    lnullingrels = bms_intersect(var->varnullingrels,
+                                                 nullinfo->nullingrels[lvarno]);
+                    if (!bms_is_empty(lnullingrels))
+                        newnode = add_nulling_relids(newnode,
+                                                     bms_make_singleton(lvarno),
+                                                     lnullingrels);
+                }
+            }
+
+            /* Finally, deal with Vars/PHVs of the subquery itself */
             newnode = add_nulling_relids(newnode,
                                          rcon->relids,
                                          var->varnullingrels);
@@ -4120,3 +4177,94 @@ find_jointree_node_for_rel(Node *jtnode, int relid)
              (int) nodeTag(jtnode));
     return NULL;
 }
+
+/*
+ * get_nullingrels: collect info about which outer joins null which relations
+ *
+ * The result struct contains, for each leaf relation used in the query,
+ * the set of relids of outer joins that potentially null that rel.
+ */
+static nullingrel_info *
+get_nullingrels(Query *parse)
+{
+    nullingrel_info *result = palloc_object(nullingrel_info);
+
+    result->rtlength = list_length(parse->rtable);
+    result->nullingrels = palloc0_array(Relids, result->rtlength + 1);
+    get_nullingrels_recurse((Node *) parse->jointree, NULL, result);
+    return result;
+}
+
+/*
+ * Recursive guts of get_nullingrels().
+ *
+ * Note: at any recursion level, the passed-down upper_nullingrels must be
+ * treated as a constant, but it can be stored directly into *info
+ * if we're at leaf level.  Upper recursion levels do not free their mutated
+ * copies of the nullingrels, because those are probably referenced by
+ * at least one leaf rel.
+ */
+static void
+get_nullingrels_recurse(Node *jtnode, Relids upper_nullingrels,
+                        nullingrel_info *info)
+{
+    if (jtnode == NULL)
+        return;
+    if (IsA(jtnode, RangeTblRef))
+    {
+        int            varno = ((RangeTblRef *) jtnode)->rtindex;
+
+        Assert(varno > 0 && varno <= info->rtlength);
+        info->nullingrels[varno] = upper_nullingrels;
+    }
+    else if (IsA(jtnode, FromExpr))
+    {
+        FromExpr   *f = (FromExpr *) jtnode;
+        ListCell   *l;
+
+        foreach(l, f->fromlist)
+        {
+            get_nullingrels_recurse(lfirst(l), upper_nullingrels, info);
+        }
+    }
+    else if (IsA(jtnode, JoinExpr))
+    {
+        JoinExpr   *j = (JoinExpr *) jtnode;
+        Relids        local_nullingrels;
+
+        switch (j->jointype)
+        {
+            case JOIN_INNER:
+                get_nullingrels_recurse(j->larg, upper_nullingrels, info);
+                get_nullingrels_recurse(j->rarg, upper_nullingrels, info);
+                break;
+            case JOIN_LEFT:
+            case JOIN_SEMI:
+            case JOIN_ANTI:
+                local_nullingrels = bms_add_member(bms_copy(upper_nullingrels),
+                                                   j->rtindex);
+                get_nullingrels_recurse(j->larg, upper_nullingrels, info);
+                get_nullingrels_recurse(j->rarg, local_nullingrels, info);
+                break;
+            case JOIN_FULL:
+                local_nullingrels = bms_add_member(bms_copy(upper_nullingrels),
+                                                   j->rtindex);
+                get_nullingrels_recurse(j->larg, local_nullingrels, info);
+                get_nullingrels_recurse(j->rarg, local_nullingrels, info);
+                break;
+            case JOIN_RIGHT:
+                local_nullingrels = bms_add_member(bms_copy(upper_nullingrels),
+                                                   j->rtindex);
+                get_nullingrels_recurse(j->larg, local_nullingrels, info);
+                get_nullingrels_recurse(j->rarg, upper_nullingrels, info);
+                break;
+            default:
+                elog(ERROR, "unrecognized join type: %d",
+                     (int) j->jointype);
+                break;
+        }
+    }
+    else
+        elog(ERROR, "unrecognized node type: %d",
+             (int) nodeTag(jtnode));
+}
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index b54428b38c..2d4c870423 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -3665,6 +3665,7 @@ nodeitem
 normal_rand_fctx
 nsphash_hash
 ntile_context
+nullingrel_info
 numeric
 object_access_hook_type
 object_access_hook_type_str

On Sat, Nov 30, 2024 at 6:31 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wrote:
> > The ideas I'd been toying with last night involved a pre-scan over
> > the join tree to calculate the potential nullingrels of each leaf RTE
> > (same idea as RelOptInfo.nulling_relids, but of course we don't have
> > any RelOptInfos yet).  That seems painful though because we'd have to
> > update the data structure somehow after each subquery pullup.
>
> I realized that we can make that work by doing the pre-calculation
> at the start of each pull_up_simple_subquery.  We only have to do
> it for subqueries marked LATERAL, so this doesn't seem too horribly
> inefficient.  Draft patch attached.  I didn't spend effort on
> devising test cases, but it works for your example.

This patch looks good to me.  I like that it will still work if,
someday, the restrictions of is_simple_subquery are relaxed to allow
lateral references to be outside the lowest outer join above the
subquery.

This patch can also simplify my other patch, which is to avoid
unnecessary wrapping for plain Vars/PHVs.  We can check the new
nullingrel_info to see if the nullingrels of the subquery RTE are a
subset of the nullingrels of the lateral referenced rel, to determine
if the referenced rel is under the same lowest nulling outer join.
And this eliminates the need to introduce lowest_nullable_side.

Thanks
Richard

Richard Guo <guofenglinux@gmail.com> writes:
> This patch can also simplify my other patch, which is to avoid
> unnecessary wrapping for plain Vars/PHVs.  We can check the new
> nullingrel_info to see if the nullingrels of the subquery RTE are a
> subset of the nullingrels of the lateral referenced rel, to determine
> if the referenced rel is under the same lowest nulling outer join.
> And this eliminates the need to introduce lowest_nullable_side.

Right, because that's more or less the same problem.  Or indeed
it's exactly the same problem, we're just making fast paths for
the easiest cases.

Another thought: the reason I made get_nullingrels return a new
struct rather than tying it directly to filling some fields in
pullup_replace_vars_context was that I think we might want to
reconsider where to call it from.  Perhaps it'd be useful to
have the info during is_simple_subquery, for example.

            regards, tom lane

On 11/29/24 05:33, Tom Lane wrote:
> Avoid mislabeling of lateral references when pulling up a subquery.
> 
> If we are pulling up a subquery that's under an outer join, and
> the subquery's target list contains a strict expression that uses
> both a subquery variable and a lateral-reference variable, it's okay
> to pull up the expression without wrapping it in a PlaceHolderVar.
> That's safe because if the subquery variable is forced to NULL
> by the outer join, the expression result will come out as NULL too,
> so we don't have to force that outcome by evaluating the expression
> below the outer join.  It'd be correct to wrap in a PHV, but that can
> lead to very significantly worse plans, since we'd then have to use
> a nestloop plan to pass down the lateral reference to where the
> expression will be evaluated.
Pardon the noise, but I'm curious why the optimiser must choose NestLoop 
in the case of lateral reference.

It would be nice to provide alternatives. Because now we have some 
corner cases. For example, with pull-up correlated subqueries, we've got 
one degraded case. Look the following:

DROP TABLE IF EXISTS t1,t2;
CREATE TABLE t1(x int, y int);
CREATE TABLE t2(x int, y int);
INSERT INTO t1 (x,y)
   SELECT gs,-gs FROM generate_series(1,1E4) AS gs;
ANALYZE t1,t2;

EXPLAIN (ANALYZE, COSTS ON)
SELECT t1.* FROM t1 LEFT JOIN LATERAL (
   SELECT t3.* FROM t1 t3 WHERE t3.x=t1.x) AS t4
ON (t4.y IN (SELECT y FROM t2 WHERE t4.x=t2.x));

In previous versions Postgres executed this plan in milliseconds:

  Hash Left Join
    Hash Cond: (t1.x = t3.x)
    ->  Seq Scan on t1
    ->  Hash
          ->  Seq Scan on t1 t3
                Filter: (ANY (y = (SubPlan 1).col1))
                SubPlan 1
                  ->  Seq Scan on t2
                        Filter: (t3.x = x)
  Planning Time: 0.175 ms
  Execution Time: 6.396 ms

But now we have seconds:

  Nested Loop Left Join
    ->  Seq Scan on t1
    ->  Nested Loop Semi Join
          Join Filter: ((t3.x = t2.x) AND (t3.y = t2.y))
          ->  Seq Scan on t1 t3
                Filter: (x = t1.x)
          ->  Seq Scan on t2
  Planning Time: 1.309 ms
  Execution Time: 6780.217 ms

Correlated subquery pull-up is a nice optimisation, of course. So, why 
not let optimiser try a HashJoin like that (not a really generated 
plan, just my imagination):

  Hash Left Join
    Hash Cond: (t1.x = t3.x)
    ->  Seq Scan on t1
    Hash
    ->  Nested Loop Semi Join
          Join Filter: ((t3.x = t2.x) AND (t3.y = t2.y))
          ->  Seq Scan on t1 t3
          ->  Seq Scan on t2

Does the optimiser have some internal limits to let such a path?

-- 
regards, Andrei Lepikhov

Andrei Lepikhov <lepihov@gmail.com> writes:
> Pardon the noise, but I'm curious why the optimiser must choose NestLoop 
> in the case of lateral reference.

To pass down the current outer row's value of the lateral reference.

> It would be nice to provide alternatives. Because now we have some 
> corner cases.

That's a fairly bizarre case, and I'm not at all convinced that
the old plan was correct.

            regards, tom lane