Re: "failed to build any N-way joins" from a five-relation query - Mailing list pgsql-hackers

Thanks for the patch and the detailed analysis.

The problem diagnosis and the example query (t1 --LJ--> t2 <--lateral-- s1 --LJ--> t3 <--lateral-- s2) are very clear. Rejecting joins whose lateral references are trapped inside outer joins or downstream lateral dependencies is topologically sound and nicely fixes the "failed to build any 5-way joins" failure.

Just a couple of small thoughts regarding the implementation and back-patching, for your consideration:

1. Leveraging existing lateral_referencers

In the patch, the search loops over simple_rel_array on every iteration of do ... while (more):


+                   /* add rels that laterally reference any rel found so far */
+                   for (int rti = 1; rti < root->simple_rel_array_size; rti++)
+                   {
+                        RelOptInfo *brel = root->simple_rel_array[rti];
...
+                        if (!bms_is_member(rti, join_plus_rhs) &&
+                             bms_overlap(brel->lateral_relids, join_plus_rhs))
+                        {
+                             join_plus_rhs = bms_add_member(join_plus_rhs, rti);
+                             more = true;
+                        }
+                   }

Since join_is_legal() is on the critical hot path of join search, doing a full linear scan of simple_rel_array and checking bms_overlap() on every iteration could introduce overhead, especially for queries on partitioned tables where simple_rel_array_size can be large.

In src/backend/optimizer/plan/initsplan.c, create_lateral_join_info() already builds the inverse mapping with transitive closure already computed:


/*
 * Now that we've identified all lateral references, mark each baserel
 * with the set of relids of rels that reference it laterally (possibly
 * indirectly) --- that is, the inverse mapping of lateral_relids.
 */
brel2->lateral_referencers = bms_add_member(brel2->lateral_referencers, rti);

Could we take advantage of brel->lateral_referencers for the relations already present in join_plus_rhs instead of scanning all baserels from scratch? That would directly yield all direct and indirect lateral referencers without repeatedly inspecting unrelated baserels.

2. Interactions with PG 17+ Outer Join infrastructure (ojrelid)

The patch targets Backpatch-through: 14. However, in PG 17 and master, the outer join infrastructure was significantly refactored by Tom Lane to give outer joins their own ojrelid (root->outer_join_rels, sjinfo->ojrelid).

Notice the check that immediately follows this loop in v17/master:


if (bms_overlap(join_lateral_rels, root->outer_join_rels))
{
    foreach(l, root->join_info_list)
    {
        SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
        if (!bms_is_member(sjinfo->ojrelid, join_lateral_rels))
            continue;
        if (bms_overlap(join_plus_rhs, sjinfo->min_lefthand) ||
            bms_overlap(join_plus_rhs, sjinfo->min_righthand))
            return false;   /* OJ can't be formed outside join */
    }
}

In PG 17 and master, join_plus_rhs can contain ojrelids in addition to baserel relids. The proposed loop skips anything where brel == NULL || brel->reloptkind != RELOPT_BASEREL. While this assumption holds cleanly on v14–v16, on v17/master:

If join_plus_rhs contains an ojrelid, looking only at baserel lateral_relids might miss lateral dependencies that reference an outer join (for instance, via a PlaceHolderVar evaluated at that outer join).
Conversely, whether join_plus_rhs containing ojrelids needs explicit propagation through lateral references should probably be verified or documented to ensure complete branch compatibility between v14–v16 and v17/master.

What are your thoughts on these two points?