commit d8f1b8b5ea948d564dd5225a42c5f97719019327 Author: Tom Lane Date: Fri Dec 23 11:11:59 2022 -0500 Teach remove_useless_result_rtes to also remove useless FromExprs. If a FromExpr has but one child, we can get rid of it even if it has some quals, if we can move those quals up to the parent jointree node. In particular, this works for a FromExpr just below the RHS of a LEFT JOIN, because the quals of such a FromExpr are equivalent to degenerate quals of the left join. By recursively applying this rule, we can guarantee that the RHS child of a left join is either not a FromExpr or has more than one child. The point of this transformation is not so much to simplify the join tree as it is to eliminate the problem for which commit 11086f2f2 invented the delay_upper_joins mechanism. The idea of that was to ensure that quals in such a FromExpr would block outer join rearrangement as if they were degenerate quals of the upper join. But after this transformation, they *are* degenerate quals of the upper join, and we don't need an indirect mechanism any more. (Note that a multi-child FromExpr isn't a problem, because that must represent an inner join, which can't commute with the outer join anyway.) This results in one visible change in regression outputs: in one test case, there is now an explicit constant-false join filter condition, which got there by being pushed up from a removed FromExpr. We still detect that the child plan is dummy, but now that happens because populate_joinrel_with_paths pushes the knowledge back down after noticing that the parent left join has a constant-false join condition. Since it's such a hokey case, I'm not concerned about the extra qual condition, and see no point in making an effort to eliminate it. Having done that, the delay_upper_joins flag serves no purpose any more and we can remove it, largely reverting 11086f2f2. (The end game here is to get rid of check_outerjoin_delay altogether, but first we must get rid of its side effects.) Although this patch doesn't make any net code savings, I think it's still an improvement because it replaces a fuzzily-defined action-at-a-distance flag with a simple and provably correct jointree transformation. diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 92c0644d14..846335043e 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -4787,7 +4787,6 @@ compute_semi_anti_join_factors(PlannerInfo *root, norm_sjinfo.commute_below = NULL; /* we don't bother trying to make the remaining fields valid */ norm_sjinfo.lhs_strict = false; - norm_sjinfo.delay_upper_joins = false; norm_sjinfo.semi_can_btree = false; norm_sjinfo.semi_can_hash = false; norm_sjinfo.semi_operators = NIL; @@ -4956,7 +4955,6 @@ approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals) sjinfo.commute_below = NULL; /* we don't bother trying to make the remaining fields valid */ sjinfo.lhs_strict = false; - sjinfo.delay_upper_joins = false; sjinfo.semi_can_btree = false; sjinfo.semi_can_hash = false; sjinfo.semi_operators = NIL; diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index 605f466bdd..4c0b81a8d0 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -743,7 +743,6 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) sjinfo->commute_below = NULL; /* we don't bother trying to make the remaining fields valid */ sjinfo->lhs_strict = false; - sjinfo->delay_upper_joins = false; sjinfo->semi_can_btree = false; sjinfo->semi_can_hash = false; sjinfo->semi_operators = NIL; diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c index 79fd240cf3..3174d77554 100644 --- a/src/backend/optimizer/plan/analyzejoins.c +++ b/src/backend/optimizer/plan/analyzejoins.c @@ -170,11 +170,10 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo) int attroff; /* - * Must be a non-delaying left join to a single baserel, else we aren't - * going to be able to do anything with it. + * Must be a left join to a single baserel, else we aren't going to be + * able to do anything with it. */ - if (sjinfo->jointype != JOIN_LEFT || - sjinfo->delay_upper_joins) + if (sjinfo->jointype != JOIN_LEFT) return false; if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid)) @@ -570,13 +569,10 @@ reduce_unique_semijoins(PlannerInfo *root) List *restrictlist; /* - * Must be a non-delaying semijoin to a single baserel, else we aren't - * going to be able to do anything with it. (It's probably not - * possible for delay_upper_joins to be set on a semijoin, but we - * might as well check.) + * Must be a semijoin to a single baserel, else we aren't going to be + * able to do anything with it. */ - if (sjinfo->jointype != JOIN_SEMI || - sjinfo->delay_upper_joins) + if (sjinfo->jointype != JOIN_SEMI) continue; if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid)) diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 0432df29fe..c9b9cc3f74 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -130,8 +130,7 @@ static void distribute_qual_to_rels(PlannerInfo *root, Node *clause, bool is_clone, List **postponed_qual_list, List **postponed_oj_qual_list); -static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p, - bool is_pushed_down); +static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p); static bool check_equivalence_delay(PlannerInfo *root, RestrictInfo *restrictinfo); static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause); @@ -1439,8 +1438,6 @@ make_outerjoininfo(PlannerInfo *root, sjinfo->commute_above_l = NULL; sjinfo->commute_above_r = NULL; sjinfo->commute_below = NULL; - /* this always starts out false */ - sjinfo->delay_upper_joins = false; compute_semijoin_info(root, sjinfo, clause); @@ -1595,17 +1592,6 @@ make_outerjoininfo(PlannerInfo *root, * Also, we must preserve ordering anyway if we have unsafe PHVs, or * if either this join or the lower OJ is a semijoin or antijoin. * - * Here, we have to consider that "our join condition" includes any - * clauses that syntactically appeared above the lower OJ and below - * ours; those are equivalent to degenerate clauses in our OJ and must - * be treated as such. Such clauses obviously can't reference our - * LHS, and they must be non-strict for the lower OJ's RHS (else - * reduce_outer_joins would have reduced the lower OJ to a plain - * join). Hence the other ways in which we handle clauses within our - * join condition are not affected by them. The net effect is - * therefore sufficiently represented by the delay_upper_joins flag - * saved for us by check_outerjoin_delay. - * * When we don't need to preserve ordering, check to see if outer join * identity 3 applies, and if so, remove the lower OJ's ojrelid from * our min_righthand so that commutation is allowed. @@ -1619,7 +1605,7 @@ make_outerjoininfo(PlannerInfo *root, jointype == JOIN_ANTI || otherinfo->jointype == JOIN_SEMI || otherinfo->jointype == JOIN_ANTI || - !otherinfo->lhs_strict || otherinfo->delay_upper_joins) + !otherinfo->lhs_strict) { /* Preserve ordering */ min_righthand = bms_add_members(min_righthand, @@ -2344,8 +2330,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, /* Check to see if must be delayed by lower outer join */ outerjoin_delayed = check_outerjoin_delay(root, - &relids, - false); + &relids); /* * Now force the qual to be evaluated exactly at the level of joining @@ -2371,8 +2356,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, /* Check to see if must be delayed by lower outer join */ outerjoin_delayed = check_outerjoin_delay(root, - &relids, - true); + &relids); if (outerjoin_delayed) { @@ -2583,13 +2567,10 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, /* * check_outerjoin_delay * Detect whether a qual referencing the given relids must be delayed - * in application due to the presence of a lower outer join, and/or - * may force extra delay of higher-level outer joins. + * in application due to the presence of a lower outer join. * * If the qual must be delayed, add relids to *relids_p to reflect the lowest - * safe level for evaluating the qual, and return true. Any extra delay for - * higher-level joins is reflected by setting delay_upper_joins to true in - * SpecialJoinInfo structs. + * safe level for evaluating the qual, and return true. * * For an is_pushed_down qual, we can evaluate the qual as soon as (1) we have * all the rels it mentions, and (2) we are at or above any outer joins that @@ -2614,24 +2595,10 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, * For a non-pushed-down qual, this isn't going to determine where we place the * qual, but we need to determine outerjoin_delayed anyway for use later in * the planning process. - * - * Lastly, a pushed-down qual that references the nullable side of any current - * join_info_list member and has to be evaluated above that OJ (because its - * required relids overlap the LHS too) causes that OJ's delay_upper_joins - * flag to be set true. This will prevent any higher-level OJs from - * being interchanged with that OJ, which would result in not having any - * correct place to evaluate the qual. (The case we care about here is a - * sub-select WHERE clause within the RHS of some outer join. The WHERE - * clause must effectively be treated as a degenerate clause of that outer - * join's condition. Rather than trying to match such clauses with joins - * directly, we set delay_upper_joins here, and when the upper outer join - * is processed by make_outerjoininfo, it will refrain from allowing the - * two OJs to commute.) */ static bool check_outerjoin_delay(PlannerInfo *root, - Relids *relids_p, /* in/out parameter */ - bool is_pushed_down) + Relids *relids_p) /* in/out parameter */ { Relids relids; bool outerjoin_delayed; @@ -2669,10 +2636,6 @@ check_outerjoin_delay(PlannerInfo *root, /* we'll need another iteration */ found_some = true; } - /* set delay_upper_joins if needed */ - if (is_pushed_down && sjinfo->jointype != JOIN_FULL && - bms_overlap(relids, sjinfo->min_lefthand)) - sjinfo->delay_upper_joins = true; } } } while (found_some); @@ -2709,12 +2672,12 @@ check_equivalence_delay(PlannerInfo *root, /* must copy restrictinfo's relids to avoid changing it */ relids = bms_copy(restrictinfo->left_relids); /* check left side does not need delay */ - if (check_outerjoin_delay(root, &relids, true)) + if (check_outerjoin_delay(root, &relids)) return false; /* and similarly for the right side */ relids = bms_copy(restrictinfo->right_relids); - if (check_outerjoin_delay(root, &relids, true)) + if (check_outerjoin_delay(root, &relids)) return false; return true; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index a139d94866..00b02d4e91 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -1043,10 +1043,11 @@ subquery_planner(PlannerGlobal *glob, Query *parse, /* * If we have any RTE_RESULT relations, see if they can be deleted from - * the jointree. This step is most effectively done after we've done - * expression preprocessing and outer join reduction. + * the jointree. We also rely on this processing to flatten single-child + * FromExprs underneath outer joins. This step is most effectively done + * after we've done expression preprocessing and outer join reduction. */ - if (hasResultRTEs) + if (hasResultRTEs || hasOuterJoins) remove_useless_result_rtes(root); /* diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index 356d81bfea..50018d0e85 100644 --- a/src/backend/optimizer/prep/prepjointree.c +++ b/src/backend/optimizer/prep/prepjointree.c @@ -130,6 +130,7 @@ static void reduce_outer_joins_pass2(Node *jtnode, static void report_reduced_full_join(reduce_outer_joins_pass2_state *state2, int rtindex, Relids relids); static Node *remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, + Node **parent_quals, Relids *dropped_outer_joins); static int get_result_relid(PlannerInfo *root, Node *jtnode); static void remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc); @@ -3083,12 +3084,31 @@ report_reduced_full_join(reduce_outer_joins_pass2_state *state2, /* * remove_useless_result_rtes * Attempt to remove RTE_RESULT RTEs from the join tree. + * Also, elide single-child FromExprs where possible. * * We can remove RTE_RESULT entries from the join tree using the knowledge * that RTE_RESULT returns exactly one row and has no output columns. Hence, * if one is inner-joined to anything else, we can delete it. Optimizations * are also possible for some outer-join cases, as detailed below. * + * This pass also replaces single-child FromExprs with their child node + * where possible. It's appropriate to do that here and not earlier because + * RTE_RESULT removal might reduce a multiple-child FromExpr to have only one + * child. We can remove such a FromExpr if its quals are empty, or if it's + * semantically valid to merge the quals into those of the parent node. + * While removing unnecessary join tree nodes has some micro-efficiency value, + * the real reason to do this is to eliminate cases where the nullable side of + * an outer join node is a FromExpr whose single child is another outer join. + * To correctly determine whether the two outer joins can commute, + * deconstruct_jointree() must treat any quals of such a FromExpr as being + * degenerate quals of the upper outer join. The best way to do that is to + * make them actually *be* quals of the upper join, by dropping the FromExpr + * and hoisting the quals up into the upper join's quals. (Note that there is + * no hazard when the intermediate FromExpr has multiple children, since then + * it represents an inner join that cannot commute with the upper outer join.) + * As long as we have to do that, we might as well elide such FromExprs + * everywhere. + * * Some of these optimizations depend on recognizing empty (constant-true) * quals for FromExprs and JoinExprs. That makes it useful to apply this * optimization pass after expression preprocessing, since that will have @@ -3129,6 +3149,7 @@ remove_useless_result_rtes(PlannerInfo *root) root->parse->jointree = (FromExpr *) remove_useless_results_recurse(root, (Node *) root->parse->jointree, + NULL, &dropped_outer_joins); /* We should still have a FromExpr */ Assert(IsA(root->parse->jointree, FromExpr)); @@ -3182,9 +3203,14 @@ remove_useless_result_rtes(PlannerInfo *root) * This recursively processes the jointree and returns a modified jointree. * In addition, the RT indexes of any removed outer-join nodes are added to * *dropped_outer_joins. + * + * jtnode is the current jointree node. If it could be valid to merge + * its quals into those of the parent node, parent_quals should point to + * the parent's quals list; otherwise, pass NULL for parent_quals. */ static Node * remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, + Node **parent_quals, Relids *dropped_outer_joins) { Assert(jtnode != NULL); @@ -3212,8 +3238,9 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, Node *child = (Node *) lfirst(cell); int varno; - /* Recursively transform child ... */ + /* Recursively transform child, allowing it to push up quals ... */ child = remove_useless_results_recurse(root, child, + &f->quals, dropped_outer_joins); /* ... and stick it back into the tree */ lfirst(cell) = child; @@ -3247,25 +3274,54 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, } /* - * If we're not at the top of the jointree, it's valid to simplify a - * degenerate FromExpr into its single child. (At the top, we must - * keep the FromExpr since Query.jointree is required to point to a - * FromExpr.) + * If the FromExpr now has only one child, see if we can elide it. + * This is always valid if there are no quals, except at the top of + * the jointree (since Query.jointree is required to point to a + * FromExpr). Otherwise, we can do it if we can push the quals up to + * the parent node. + * + * Note: while it would not be terribly hard to generalize this + * transformation to merge multi-child FromExprs into their parent + * FromExpr, that risks making the parent join too expensive to plan. + * We leave it to later processing to decide heuristically whether + * that's a good idea. Pulling up a single child is always OK, + * however. */ - if (f != root->parse->jointree && - f->quals == NULL && - list_length(f->fromlist) == 1) + if (list_length(f->fromlist) == 1 && + f != root->parse->jointree && + (f->quals == NULL || parent_quals != NULL)) + { + /* + * Merge any quals up to parent. They should be in implicit-AND + * format by now, so we just need to concatenate lists. Put the + * child quals at the front, on the grounds that they should + * nominally be evaluated earlier. + */ + if (f->quals != NULL) + *parent_quals = (Node *) + list_concat(castNode(List, f->quals), + castNode(List, *parent_quals)); return (Node *) linitial(f->fromlist); + } } else if (IsA(jtnode, JoinExpr)) { JoinExpr *j = (JoinExpr *) jtnode; int varno; - /* First, recurse */ + /* + * First, recurse. We can accept pushed-up FromExpr quals from either + * child if the jointype is INNER, and we can accept them from the RHS + * child if the jointype is LEFT. + */ j->larg = remove_useless_results_recurse(root, j->larg, + (j->jointype == JOIN_INNER) ? + &j->quals : NULL, dropped_outer_joins); j->rarg = remove_useless_results_recurse(root, j->rarg, + (j->jointype == JOIN_INNER || + j->jointype == JOIN_LEFT) ? + &j->quals : NULL, dropped_outer_joins); /* Apply join-type-specific optimization rules */ @@ -3276,9 +3332,9 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, /* * An inner join is equivalent to a FromExpr, so if either * side was simplified to an RTE_RESULT rel, we can replace - * the join with a FromExpr with just the other side; and if - * the qual is empty (JOIN ON TRUE) then we can omit the - * FromExpr as well. + * the join with a FromExpr with just the other side. + * Furthermore, we can elide that FromExpr according to the + * same rules as above. * * Just as in the FromExpr case, we can't simplify if the * other input rel references any PHVs that are marked as to @@ -3293,20 +3349,34 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, !find_dependent_phvs_in_jointree(root, j->rarg, varno)) { remove_result_refs(root, varno, j->rarg); - if (j->quals) + if (j->quals != NULL && parent_quals == NULL) jtnode = (Node *) makeFromExpr(list_make1(j->rarg), j->quals); else + { + /* Merge any quals up to parent */ + if (j->quals != NULL) + *parent_quals = (Node *) + list_concat(castNode(List, j->quals), + castNode(List, *parent_quals)); jtnode = j->rarg; + } } else if ((varno = get_result_relid(root, j->rarg)) != 0) { remove_result_refs(root, varno, j->larg); - if (j->quals) + if (j->quals != NULL && parent_quals == NULL) jtnode = (Node *) makeFromExpr(list_make1(j->larg), j->quals); else + { + /* Merge any quals up to parent */ + if (j->quals != NULL) + *parent_quals = (Node *) + list_concat(castNode(List, j->quals), + castNode(List, *parent_quals)); jtnode = j->larg; + } } break; case JOIN_LEFT: @@ -3344,8 +3414,9 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, /* * We may simplify this case if the RHS is an RTE_RESULT; the * join qual becomes effectively just a filter qual for the - * LHS, since we should either return the LHS row or not. For - * simplicity we inject the filter qual into a new FromExpr. + * LHS, since we should either return the LHS row or not. The + * filter clause must go into a new FromExpr if we can't push + * it up to the parent. * * There is a fine point about PHVs that are supposed to be * evaluated at the RHS. Such PHVs could only appear in the @@ -3363,11 +3434,18 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, { Assert(j->rtindex == 0); remove_result_refs(root, varno, j->larg); - if (j->quals) + if (j->quals != NULL && parent_quals == NULL) jtnode = (Node *) makeFromExpr(list_make1(j->larg), j->quals); else + { + /* Merge any quals up to parent */ + if (j->quals != NULL) + *parent_quals = (Node *) + list_concat(castNode(List, j->quals), + castNode(List, *parent_quals)); jtnode = j->larg; + } } break; case JOIN_FULL: diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c index 7ae058f4c8..e02dabe2ee 100644 --- a/src/backend/optimizer/util/orclauses.c +++ b/src/backend/optimizer/util/orclauses.c @@ -338,7 +338,6 @@ consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel, sjinfo.commute_below = NULL; /* we don't bother trying to make the remaining fields valid */ sjinfo.lhs_strict = false; - sjinfo.delay_upper_joins = false; sjinfo.semi_can_btree = false; sjinfo.semi_can_hash = false; sjinfo.semi_operators = NIL; diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c index b9cc983df7..25d4c54400 100644 --- a/src/backend/optimizer/util/placeholder.c +++ b/src/backend/optimizer/util/placeholder.c @@ -331,10 +331,7 @@ update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo) /* * Check for delays due to lower outer joins. This is the same logic - * as in check_outerjoin_delay in initsplan.c, except that we don't - * have anything to do with the delay_upper_joins flags; delay of - * upper outer joins will be handled later, based on the eval_at - * values we compute now. + * as in check_outerjoin_delay in initsplan.c. */ eval_at = phinfo->ph_eval_at; diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 2a2c5076df..6a6fbf3fd4 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -2746,12 +2746,6 @@ typedef struct PlaceHolderVar * upper-level outer joins even if it appears in their RHS). We don't bother * to set lhs_strict for FULL JOINs, however. * - * delay_upper_joins is set true if we detect a pushed-down clause that has - * to be evaluated after this join is formed (because it references the RHS). - * Any outer joins that have such a clause and this join in their RHS cannot - * commute with this join, because that would leave noplace to check the - * pushed-down clause. (We don't track this for FULL JOINs, either.) - * * For a semijoin, we also extract the join operators and their RHS arguments * and set semi_operators, semi_rhs_exprs, semi_can_btree, and semi_can_hash. * This is done in support of possibly unique-ifying the RHS, so we don't @@ -2766,8 +2760,8 @@ typedef struct PlaceHolderVar * not allowed within join_info_list. We also create transient * SpecialJoinInfos with jointype == JOIN_INNER for outer joins, since for * cost estimation purposes it is sometimes useful to know the join size under - * plain innerjoin semantics. Note that lhs_strict, delay_upper_joins, and - * of course the semi_xxx fields are not set meaningfully within such structs. + * plain innerjoin semantics. Note that lhs_strict and the semi_xxx fields + * are not set meaningfully within such structs. */ #ifndef HAVE_SPECIALJOININFO_TYPEDEF typedef struct SpecialJoinInfo SpecialJoinInfo; @@ -2789,7 +2783,6 @@ struct SpecialJoinInfo Relids commute_above_r; /* commuting OJs above this one, if RHS */ Relids commute_below; /* commuting OJs below this one */ bool lhs_strict; /* joinclause is strict for some LHS rel */ - bool delay_upper_joins; /* can't commute with upper RHS */ /* Remaining fields are set only for JOIN_SEMI jointype: */ bool semi_can_btree; /* true if semi_operators are all btree */ bool semi_can_hash; /* true if semi_operators are all hash */ diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 4185672a12..a5c09cce01 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -6038,12 +6038,13 @@ select * from int8_tbl i8 left join lateral -------------------------------------- Nested Loop Left Join Output: i8.q1, i8.q2, f1, (i8.q2) + Join Filter: false -> Seq Scan on public.int8_tbl i8 Output: i8.q1, i8.q2 -> Result Output: f1, i8.q2 One-Time Filter: false -(7 rows) +(8 rows) explain (verbose, costs off) select * from int8_tbl i8 left join lateral