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

Hi Richard Guo

> 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?
>

Thanks