commit 90559097c8b6397c4457c55838aa6ebbcf0732de Author: Tom Lane Date: Thu Dec 22 18:38:33 2022 -0500 Teach the planner to cope with Vars bearing nullingrels. The core idea of this step is to include varnullingrels in the relid sets that qual clauses are considered to depend on. So that we can still easily compare quals' relids to RelOptInfos' relids, that means also adding outer join relids to the identifying relids of join relations. Much of the bulk of this step is concerned with fallout from the latter change. I've resolved the previous squishiness entailed by outer join identity 3 by generating multiple versions of outer-join quals that could get moved to a join level where they need to contain different nullingrels sets. Now we have versions of such quals with the correct nullingrels for each level where they could appear. This requires a bit of new mechanism (RestrictInfo.has_clone/is_clone) to prevent multiple versions of the same qual from getting used in the plan. My worry about how that could work with EquivalenceClasses is resolved by creating EquivalenceClasses only from the least-marked version of a qual. (This doesn't really lose anything, since versions with more nullingrels bits don't correspond to any equalities available outside the nest of commuting outer joins.) These extra versions of quals would also result in generating multiple parameterized paths that differ only in what nullingrels they expect for the Vars from the parameterization rel(s). That seems like it'd be very wasteful, so I've arranged to generate such paths only from the least-marked version of a qual (the has_clone version). Unlike in the previous version of this patch, setrefs.c is able to cross-check the nullingrel sets of most Vars and PlaceHolderVars to ensure that they match up with what the previous plan step produces. But there are three cases that I've so far punted on: 1. The targetlist and qpqual of an outer join node will contain nullingrels bits for the outer join itself. To check exact matching to the input, we'd need to know the OJ's relid as well as which input(s) got nulled, neither of which is cheaply available in setrefs.c. For now, it's just checking that such Vars have a superset of the input's nullingrels bits. 2. Parameterized paths will generally refer to the least-marked version of whichever outer-side Vars they use, which may not be what's actually available from the outside of the nestloop. (We're relying on the join ordering rules for that to be sensible.) Again, setrefs.c is in no position to pass judgment on correctness, so it's just checking that the parameter expression has a subset of the outer-side marking. 3. Row identity variables are not marked with any nullingrels, which may not correspond to reality. I've punted on this by skipping the checks when varattno <= 0. Point 1 could be addressed if we were willing to add informational fields to join plan nodes, which might be worth doing, but I'm not sure. The other two points seem like the extra mechanisms needed for a bulletproof check would be considerably more trouble than they'd be worth. There is still some confusion about which versions of a cloned qual are actually necessary to check, which results in some extra filter conditions showing up in a couple of regression test plans. There are also some failure cases involving full joins that remain to be fixed. This patch is already mighty big, so I'll address those failures separately. This step removes some low-hanging fruit from the old implementation, such as the need to track lowest_nulling_outer_join during subquery pullup. There's much more to do in that line, though. diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 004481d608..1c921879a9 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -273,7 +273,7 @@ merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene, * rel once we know the final targetlist (see * grouping_planner). */ - if (!bms_equal(joinrel->relids, root->all_baserels)) + if (!bms_equal(joinrel->relids, root->all_query_rels)) generate_useful_gather_paths(root, joinrel, false); /* Find and save the cheapest paths for this joinrel */ diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 10ac01ac36..d81b09add5 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -211,9 +211,9 @@ make_one_rel(PlannerInfo *root, List *joinlist) rel = make_rel_from_joinlist(root, joinlist); /* - * The result should join all and only the query's base rels. + * The result should join all and only the query's base + outer-join rels. */ - Assert(bms_equal(rel->relids, root->all_baserels)); + Assert(bms_equal(rel->relids, root->all_query_rels)); return rel; } @@ -538,7 +538,7 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, * the final scan/join targetlist is available (see grouping_planner). */ if (rel->reloptkind == RELOPT_BASEREL && - !bms_equal(rel->relids, root->all_baserels)) + !bms_equal(rel->relids, root->all_query_rels)) generate_useful_gather_paths(root, rel, false); /* Now find the cheapest of the paths for this rel */ @@ -859,7 +859,7 @@ set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry * * to support an uncommon usage of second-rate sampling methods. Instead, * if there is a risk that the query might perform an unsafe join, just * wrap the SampleScan in a Materialize node. We can check for joins by - * counting the membership of all_baserels (note that this correctly + * counting the membership of all_query_rels (note that this correctly * counts inheritance trees as single rels). If we're inside a subquery, * we can't easily check whether a join might occur in the outer query, so * just assume one is possible. @@ -868,7 +868,7 @@ set_tablesample_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry * * so check repeatable_across_scans last, even though that's a bit odd. */ if ((root->query_level > 1 || - bms_membership(root->all_baserels) != BMS_SINGLETON) && + bms_membership(root->all_query_rels) != BMS_SINGLETON) && !(GetTsmRoutine(rte->tablesample->tsmhandler)->repeatable_across_scans)) { path = (Path *) create_material_path(rel, path); @@ -950,7 +950,7 @@ set_append_rel_size(PlannerInfo *root, RelOptInfo *rel, if (enable_partitionwise_join && rel->reloptkind == RELOPT_BASEREL && rte->relkind == RELKIND_PARTITIONED_TABLE && - rel->attr_needed[InvalidAttrNumber - rel->min_attr] == NULL) + bms_is_empty(rel->attr_needed[InvalidAttrNumber - rel->min_attr])) rel->consider_partitionwise_join = true; /* @@ -3409,7 +3409,7 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels) * partial paths. We'll do the same for the topmost scan/join rel * once we know the final targetlist (see grouping_planner). */ - if (!bms_equal(rel->relids, root->all_baserels)) + if (!bms_equal(rel->relids, root->all_query_rels)) generate_useful_gather_paths(root, rel, false); /* Find and save the cheapest paths for this rel */ diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c index 06f836308d..c08eb2b1c5 100644 --- a/src/backend/optimizer/path/clausesel.c +++ b/src/backend/optimizer/path/clausesel.c @@ -218,7 +218,7 @@ clauselist_selectivity_ext(PlannerInfo *root, if (rinfo) { - ok = (bms_membership(rinfo->clause_relids) == BMS_SINGLETON) && + ok = (rinfo->num_base_rels == 1) && (is_pseudo_constant_clause_relids(lsecond(expr->args), rinfo->right_relids) || (varonleft = false, @@ -579,30 +579,6 @@ find_single_rel_for_clauses(PlannerInfo *root, List *clauses) return NULL; /* no clauses */ } -/* - * bms_is_subset_singleton - * - * Same result as bms_is_subset(s, bms_make_singleton(x)), - * but a little faster and doesn't leak memory. - * - * Is this of use anywhere else? If so move to bitmapset.c ... - */ -static bool -bms_is_subset_singleton(const Bitmapset *s, int x) -{ - switch (bms_membership(s)) - { - case BMS_EMPTY_SET: - return true; - case BMS_SINGLETON: - return bms_is_member(x, s); - case BMS_MULTIPLE: - return false; - } - /* can't get here... */ - return false; -} - /* * treat_as_join_clause - * Decide whether an operator clause is to be handled by the @@ -631,17 +607,20 @@ treat_as_join_clause(PlannerInfo *root, Node *clause, RestrictInfo *rinfo, else { /* - * Otherwise, it's a join if there's more than one relation used. We - * can optimize this calculation if an rinfo was passed. + * Otherwise, it's a join if there's more than one base relation used. + * We can optimize this calculation if an rinfo was passed. * * XXX Since we know the clause is being evaluated at a join, the * only way it could be single-relation is if it was delayed by outer - * joins. Although we can make use of the restriction qual estimators - * anyway, it seems likely that we ought to account for the - * probability of injected nulls somehow. + * joins. We intentionally count only baserels here, not OJs that + * might be present in rinfo->clause_relids, so that we direct such + * cases to the restriction qual estimators not join estimators. + * Eventually some notice should be taken of the possibility of + * injected nulls, but we'll likely want to do that in the restriction + * estimators rather than starting to treat such cases as join quals. */ if (rinfo) - return (bms_membership(rinfo->clause_relids) == BMS_MULTIPLE); + return (rinfo->num_base_rels > 1); else return (NumRelids(root, clause) > 1); } @@ -754,7 +733,9 @@ clause_selectivity_ext(PlannerInfo *root, * for all non-JOIN_INNER cases. */ if (varRelid == 0 || - bms_is_subset_singleton(rinfo->clause_relids, varRelid)) + rinfo->num_base_rels == 0 || + (rinfo->num_base_rels == 1 && + bms_is_member(varRelid, rinfo->clause_relids))) { /* Cacheable --- do we already have the result? */ if (jointype == JOIN_INNER) diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 89d3c4352c..92c0644d14 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -4781,6 +4781,10 @@ compute_semi_anti_join_factors(PlannerInfo *root, norm_sjinfo.syn_lefthand = outerrel->relids; norm_sjinfo.syn_righthand = innerrel->relids; norm_sjinfo.jointype = JOIN_INNER; + norm_sjinfo.ojrelid = 0; + norm_sjinfo.commute_above_l = NULL; + norm_sjinfo.commute_above_r = NULL; + 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; @@ -4946,6 +4950,10 @@ approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals) sjinfo.syn_lefthand = path->outerjoinpath->parent->relids; sjinfo.syn_righthand = path->innerjoinpath->parent->relids; sjinfo.jointype = JOIN_INNER; + sjinfo.ojrelid = 0; + sjinfo.commute_above_l = NULL; + sjinfo.commute_above_r = NULL; + sjinfo.commute_below = NULL; /* we don't bother trying to make the remaining fields valid */ sjinfo.lhs_strict = false; sjinfo.delay_upper_joins = false; diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 019972cefc..055d70b8e3 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -29,6 +29,7 @@ #include "optimizer/paths.h" #include "optimizer/planmain.h" #include "optimizer/restrictinfo.h" +#include "rewrite/rewriteManip.h" #include "utils/lsyscache.h" @@ -757,6 +758,12 @@ get_eclass_for_sort_expr(PlannerInfo *root, { RelOptInfo *rel = root->simple_rel_array[i]; + if (rel == NULL) /* must be an outer join */ + { + Assert(bms_is_member(i, root->outer_join_rels)); + continue; + } + Assert(rel->reloptkind == RELOPT_BASEREL || rel->reloptkind == RELOPT_DEADREL); @@ -1113,6 +1120,12 @@ generate_base_implied_equalities(PlannerInfo *root) { RelOptInfo *rel = root->simple_rel_array[i]; + if (rel == NULL) /* must be an outer join */ + { + Assert(bms_is_member(i, root->outer_join_rels)); + continue; + } + Assert(rel->reloptkind == RELOPT_BASEREL); rel->eclass_indexes = bms_add_member(rel->eclass_indexes, @@ -2195,6 +2208,8 @@ static bool reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo) { RestrictInfo *rinfo = ojcinfo->rinfo; + SpecialJoinInfo *sjinfo = ojcinfo->sjinfo; + Relids fjrelids = bms_make_singleton(sjinfo->ojrelid); Expr *leftvar; Expr *rightvar; Oid opno, @@ -2276,6 +2291,18 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo) cfirst = (Node *) linitial(cexpr->args); csecond = (Node *) lsecond(cexpr->args); + /* + * The COALESCE arguments will be marked as possibly nulled by + * the full join, while we wish to generate clauses that apply + * to the join's inputs. So we must strip the join from the + * nullingrels fields of cfirst/csecond before comparing them + * to leftvar/rightvar. (Perhaps with a less hokey + * representation for FULL JOIN USING output columns, this + * wouldn't be needed?) + */ + cfirst = remove_nulling_relids(cfirst, fjrelids, NULL); + csecond = remove_nulling_relids(csecond, fjrelids, NULL); + if (equal(leftvar, cfirst) && equal(rightvar, csecond)) { coal_idx = foreach_current_index(lc2); @@ -3212,6 +3239,12 @@ get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids) { RelOptInfo *rel = root->simple_rel_array[i]; + if (rel == NULL) /* must be an outer join */ + { + Assert(bms_is_member(i, root->outer_join_rels)); + continue; + } + ec_indexes = bms_add_members(ec_indexes, rel->eclass_indexes); } return ec_indexes; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 914bfd90bc..e24a9c14a9 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -3352,13 +3352,13 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel) * Add on any equivalence-derivable join clauses. Computing the correct * relid sets for generate_join_implied_equalities is slightly tricky * because the rel could be a child rel rather than a true baserel, and in - * that case we must remove its parents' relid(s) from all_baserels. + * that case we must subtract its parents' relid(s) from all_query_rels. */ if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL) - otherrels = bms_difference(root->all_baserels, + otherrels = bms_difference(root->all_query_rels, find_childrel_parents(root, rel)); else - otherrels = bms_difference(root->all_baserels, rel->relids); + otherrels = bms_difference(root->all_query_rels, rel->relids); if (!bms_is_empty(otherrels)) clauselist = @@ -3736,7 +3736,8 @@ match_index_to_operand(Node *operand, */ if (operand && IsA(operand, Var) && index->rel->relid == ((Var *) operand)->varno && - indkey == ((Var *) operand)->varattno) + indkey == ((Var *) operand)->varattno && + ((Var *) operand)->varnullingrels == NULL) return true; } else diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 4d09881259..3d7ee7dfe5 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -234,7 +234,9 @@ add_paths_to_joinrel(PlannerInfo *root, * reduces the number of parameterized paths we have to deal with at * higher join levels, without compromising the quality of the resulting * plan. We express the restriction as a Relids set that must overlap the - * parameterization of any proposed join path. + * parameterization of any proposed join path. Note: param_source_rels + * should contain only baserels, not OJ relids, so starting from + * all_baserels not all_query_rels is correct. */ foreach(lc, root->join_info_list) { @@ -365,6 +367,47 @@ allow_star_schema_join(PlannerInfo *root, bms_nonempty_difference(inner_paramrels, outerrelids)); } +/* + * If the parameterization is only partly satisfied by the outer rel, + * the unsatisfied part can't include any outer-join relids that could + * null rels of the satisfied part. That would imply that we're trying + * to use a clause involving a Var with nonempty varnullingrels at + * a join level where that value isn't yet computable. + */ +static inline bool +have_unsafe_outer_join_ref(PlannerInfo *root, + Relids outerrelids, + Relids inner_paramrels) +{ + bool result = false; + Relids unsatisfied = bms_difference(inner_paramrels, outerrelids); + + if (bms_overlap(unsatisfied, root->outer_join_rels)) + { + ListCell *lc; + + foreach(lc, root->join_info_list) + { + SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); + + if (!bms_is_member(sjinfo->ojrelid, unsatisfied)) + continue; /* not relevant */ + if (bms_overlap(inner_paramrels, sjinfo->min_righthand) || + (sjinfo->jointype == JOIN_FULL && + bms_overlap(inner_paramrels, sjinfo->min_lefthand))) + { + result = true; /* doesn't work */ + break; + } + } + } + + /* Waste no memory when we reject a path here */ + bms_free(unsatisfied); + + return result; +} + /* * paraminfo_get_equal_hashops * Determine if param_info and innerrel's lateral_vars can be hashed. @@ -657,15 +700,16 @@ try_nestloop_path(PlannerInfo *root, /* * Check to see if proposed path is still parameterized, and reject if the * parameterization wouldn't be sensible --- unless allow_star_schema_join - * says to allow it anyway. Also, we must reject if have_dangerous_phv - * doesn't like the look of it, which could only happen if the nestloop is - * still parameterized. + * says to allow it anyway. Also, we must reject if either + * have_unsafe_outer_join_ref or have_dangerous_phv don't like the look of + * it, which could only happen if the nestloop is still parameterized. */ required_outer = calc_nestloop_required_outer(outerrelids, outer_paramrels, innerrelids, inner_paramrels); if (required_outer && ((!bms_overlap(required_outer, extra->param_source_rels) && !allow_star_schema_join(root, outerrelids, inner_paramrels)) || + have_unsafe_outer_join_ref(root, outerrelids, inner_paramrels) || have_dangerous_phv(root, outerrelids, inner_paramrels))) { /* Waste no memory when we reject a path here */ diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index 9da3ff2f9a..605f466bdd 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -353,7 +353,10 @@ make_rels_by_clauseless_joins(PlannerInfo *root, * * Caller must supply not only the two rels, but the union of their relids. * (We could simplify the API by computing joinrelids locally, but this - * would be redundant work in the normal path through make_join_rel.) + * would be redundant work in the normal path through make_join_rel. + * Note that this value does NOT include the RT index of any outer join that + * might need to be performed here, so it's not the canonical identifier + * of the join relation.) * * On success, *sjinfo_p is set to NULL if this is to be a plain inner join, * else it's set to point to the associated SpecialJoinInfo node. Also, @@ -695,7 +698,7 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) /* We should never try to join two overlapping sets of rels. */ Assert(!bms_overlap(rel1->relids, rel2->relids)); - /* Construct Relids set that identifies the joinrel. */ + /* Construct Relids set that identifies the joinrel (without OJ as yet). */ joinrelids = bms_union(rel1->relids, rel2->relids); /* Check validity and determine join type. */ @@ -707,6 +710,10 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) return NULL; } + /* If we have an outer join, add its RTI to form the canonical relids. */ + if (sjinfo && sjinfo->ojrelid != 0) + joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid); + /* Swap rels if needed to match the join info. */ if (reversed) { @@ -730,6 +737,10 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2) sjinfo->syn_lefthand = rel1->relids; sjinfo->syn_righthand = rel2->relids; sjinfo->jointype = JOIN_INNER; + sjinfo->ojrelid = 0; + sjinfo->commute_above_l = NULL; + sjinfo->commute_above_r = NULL; + sjinfo->commute_below = NULL; /* we don't bother trying to make the remaining fields valid */ sjinfo->lhs_strict = false; sjinfo->delay_upper_joins = false; @@ -1510,8 +1521,6 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, /* We should never try to join two overlapping sets of rels. */ Assert(!bms_overlap(child_rel1->relids, child_rel2->relids)); - child_joinrelids = bms_union(child_rel1->relids, child_rel2->relids); - appinfos = find_appinfos_by_relids(root, child_joinrelids, &nappinfos); /* * Construct SpecialJoinInfo from parent join relations's @@ -1521,6 +1530,15 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, child_rel1->relids, child_rel2->relids); + /* Build correct join relids for child join */ + child_joinrelids = bms_union(child_rel1->relids, child_rel2->relids); + if (child_sjinfo->ojrelid != 0) + child_joinrelids = bms_add_member(child_joinrelids, + child_sjinfo->ojrelid); + + /* Find the AppendRelInfo structures */ + appinfos = find_appinfos_by_relids(root, child_joinrelids, &nappinfos); + /* * Construct restrictions applicable to the child join from those * applicable to the parent join. @@ -1536,8 +1554,7 @@ try_partitionwise_join(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, { child_joinrel = build_child_join_rel(root, child_rel1, child_rel2, joinrel, child_restrictlist, - child_sjinfo, - child_sjinfo->jointype); + child_sjinfo); joinrel->part_rels[cnt_parts] = child_joinrel; joinrel->live_parts = bms_add_member(joinrel->live_parts, cnt_parts); joinrel->all_partrels = bms_add_members(joinrel->all_partrels, @@ -1583,6 +1600,7 @@ build_child_join_sjinfo(PlannerInfo *root, SpecialJoinInfo *parent_sjinfo, sjinfo->syn_righthand = adjust_child_relids(sjinfo->syn_righthand, right_nappinfos, right_appinfos); + /* outer-join relids need no adjustment */ sjinfo->semi_rhs_exprs = (List *) adjust_appendrel_attrs(root, (Node *) sjinfo->semi_rhs_exprs, right_nappinfos, diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c index c4e035b049..71488cec00 100644 --- a/src/backend/optimizer/path/tidpath.c +++ b/src/backend/optimizer/path/tidpath.c @@ -59,6 +59,7 @@ IsCTIDVar(Var *var, RelOptInfo *rel) if (var->varattno == SelfItemPointerAttributeNumber && var->vartype == TIDOID && var->varno == rel->relid && + var->varnullingrels == NULL && var->varlevelsup == 0) return true; return false; diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c index dc0f165477..79fd240cf3 100644 --- a/src/backend/optimizer/plan/analyzejoins.c +++ b/src/backend/optimizer/plan/analyzejoins.c @@ -34,7 +34,7 @@ /* local functions */ static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo); -static void remove_rel_from_query(PlannerInfo *root, int relid, +static void remove_rel_from_query(PlannerInfo *root, int relid, int ojrelid, Relids joinrelids); static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved); static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel); @@ -70,6 +70,7 @@ restart: foreach(lc, root->join_info_list) { SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); + Relids joinrelids; int innerrelid; int nremoved; @@ -84,9 +85,12 @@ restart: */ innerrelid = bms_singleton_member(sjinfo->min_righthand); - remove_rel_from_query(root, innerrelid, - bms_union(sjinfo->min_lefthand, - sjinfo->min_righthand)); + /* Compute the relid set for the join we are considering */ + joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + if (sjinfo->ojrelid != 0) + joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid); + + remove_rel_from_query(root, innerrelid, sjinfo->ojrelid, joinrelids); /* We verify that exactly one reference gets removed from joinlist */ nremoved = 0; @@ -188,6 +192,8 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo) /* Compute the relid set for the join we are considering */ joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + if (sjinfo->ojrelid != 0) + joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid); /* * We can't remove the join if any inner-rel attributes are used above the @@ -247,6 +253,17 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l); + /* + * If the current join commutes with some other outer join(s) via + * outer join identity 3, there will be multiple clones of its join + * clauses in the joininfo list. We want to consider only the + * has_clone form of such clauses. Processing more than one form + * would be wasteful, and also some of the others would confuse the + * RINFO_IS_PUSHED_DOWN test below. + */ + if (restrictinfo->is_clone) + continue; /* ignore it */ + /* * If it's not a join clause for this outer join, we can't use it. * Note that if the clause is pushed-down, then it is logically from @@ -306,10 +323,12 @@ join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo) * no longer treated as a baserel, and that attributes of other baserels * are no longer marked as being needed at joins involving this rel. * Also, join quals involving the rel have to be removed from the joininfo - * lists, but only if they belong to the outer join identified by joinrelids. + * lists, but only if they belong to the outer join identified by ojrelid + * and joinrelids. */ static void -remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) +remove_rel_from_query(PlannerInfo *root, int relid, int ojrelid, + Relids joinrelids) { RelOptInfo *rel = find_base_rel(root, relid); List *joininfos; @@ -346,6 +365,8 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) { otherrel->attr_needed[attroff] = bms_del_member(otherrel->attr_needed[attroff], relid); + otherrel->attr_needed[attroff] = + bms_del_member(otherrel->attr_needed[attroff], ojrelid); } } @@ -353,6 +374,9 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) * Update all_baserels and related relid sets. */ root->all_baserels = bms_del_member(root->all_baserels, relid); + root->outer_join_rels = bms_del_member(root->outer_join_rels, ojrelid); + root->all_query_rels = bms_del_member(root->all_query_rels, relid); + root->all_query_rels = bms_del_member(root->all_query_rels, ojrelid); /* * Likewise remove references from SpecialJoinInfo data structures. @@ -370,6 +394,14 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, relid); sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, relid); sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, relid); + sjinfo->min_lefthand = bms_del_member(sjinfo->min_lefthand, ojrelid); + sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, ojrelid); + sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, ojrelid); + sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, ojrelid); + /* relid cannot appear in these fields, but ojrelid can: */ + sjinfo->commute_above_l = bms_del_member(sjinfo->commute_above_l, ojrelid); + sjinfo->commute_above_r = bms_del_member(sjinfo->commute_above_r, ojrelid); + sjinfo->commute_below = bms_del_member(sjinfo->commute_below, ojrelid); } /* @@ -401,8 +433,10 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) else { phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid); + phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, ojrelid); Assert(!bms_is_empty(phinfo->ph_eval_at)); phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid); + phinfo->ph_needed = bms_del_member(phinfo->ph_needed, ojrelid); } } @@ -427,7 +461,12 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) remove_join_clause_from_rels(root, rinfo, rinfo->required_relids); - if (RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)) + /* + * If the qual lists ojrelid in its required_relids, it must have come + * from above the outer join we're removing (so we need to keep it); + * if it does not, then it didn't and we can discard it. + */ + if (bms_is_member(ojrelid, rinfo->required_relids)) { /* Recheck that qual doesn't actually reference the target rel */ Assert(!bms_is_member(relid, rinfo->clause_relids)); @@ -439,6 +478,8 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) rinfo->required_relids = bms_copy(rinfo->required_relids); rinfo->required_relids = bms_del_member(rinfo->required_relids, relid); + rinfo->required_relids = bms_del_member(rinfo->required_relids, + ojrelid); distribute_restrictinfo_to_rels(root, rinfo); } } @@ -553,6 +594,7 @@ reduce_unique_semijoins(PlannerInfo *root) /* Compute the relid set for the join we are considering */ joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + Assert(sjinfo->ojrelid == 0); /* SEMI joins don't have RT indexes */ /* * Since we're only considering a single-rel RHS, any join clauses it diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 2ee58f0a68..90da123c10 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -48,7 +48,9 @@ int join_collapse_limit; * * deconstruct_recurse recursively examines the join tree and builds a List * (in depth-first traversal order) of JoinTreeItem structs, which are then - * processed iteratively by deconstruct_distribute. + * processed iteratively by deconstruct_distribute. If there are outer + * joins, non-degenerate outer join clauses are processed in a third pass + * deconstruct_distribute_oj_quals. * * The JoinTreeItem structs themselves can be freed at the end of * deconstruct_jointree, but do not modify or free their substructure, @@ -60,17 +62,18 @@ typedef struct JoinTreeItem /* Fields filled during deconstruct_recurse: */ Node *jtnode; /* jointree node to examine */ bool below_outer_join; /* is it below an outer join? */ - Relids qualscope; /* base Relids syntactically included in this - * jointree node */ - Relids inner_join_rels; /* base Relids syntactically included in - * inner joins appearing at or below this - * jointree node */ + Relids qualscope; /* base+OJ Relids syntactically included in + * this jointree node */ + Relids inner_join_rels; /* base+OJ Relids syntactically included + * in inner joins appearing at or below + * this jointree node */ Relids left_rels; /* if join node, Relids of the left side */ Relids right_rels; /* if join node, Relids of the right side */ Relids nonnullable_rels; /* if outer join, Relids of the * non-nullable side */ /* Fields filled during deconstruct_distribute: */ SpecialJoinInfo *sjinfo; /* if outer join, its SpecialJoinInfo */ + List *oj_joinclauses; /* outer join quals not yet distributed */ } JoinTreeItem; /* Elements of the postponed_qual_list used during deconstruct_distribute */ @@ -94,9 +97,13 @@ static void process_security_barrier_quals(PlannerInfo *root, static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root, Relids left_rels, Relids right_rels, Relids inner_join_rels, - JoinType jointype, List *clause); + JoinType jointype, Index ojrelid, + List *clause); static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause); +static void deconstruct_distribute_oj_quals(PlannerInfo *root, + List *jtitems, + JoinTreeItem *jtitem); static void distribute_quals_to_rels(PlannerInfo *root, List *clauses, bool below_outer_join, SpecialJoinInfo *sjinfo, @@ -104,7 +111,11 @@ static void distribute_quals_to_rels(PlannerInfo *root, List *clauses, Relids qualscope, Relids ojscope, Relids outerjoin_nonnullable, - List **postponed_qual_list); + bool allow_equivalence, + bool has_clone, + bool is_clone, + List **postponed_qual_list, + List **postponed_oj_qual_list); static void distribute_qual_to_rels(PlannerInfo *root, Node *clause, bool below_outer_join, SpecialJoinInfo *sjinfo, @@ -112,7 +123,11 @@ static void distribute_qual_to_rels(PlannerInfo *root, Node *clause, Relids qualscope, Relids ojscope, Relids outerjoin_nonnullable, - List **postponed_qual_list); + bool allow_equivalence, + bool has_clone, + bool is_clone, + List **postponed_qual_list, + List **postponed_oj_qual_list); static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p, Relids *nullable_relids_p, bool is_pushed_down); static bool check_equivalence_delay(PlannerInfo *root, @@ -290,10 +305,16 @@ add_vars_to_targetlist(PlannerInfo *root, List *vars, attno -= rel->min_attr; if (rel->attr_needed[attno] == NULL) { - /* Variable not yet requested, so add to rel's targetlist */ - /* XXX is copyObject necessary here? */ - rel->reltarget->exprs = lappend(rel->reltarget->exprs, - copyObject(var)); + /* + * Variable not yet requested, so add to rel's targetlist. + * + * The value available at the rel's scan level has not been + * nulled by any outer join, so drop its varnullingrels. + * (We'll put those back as we climb up the join tree.) + */ + var = copyObject(var); + var->varnullingrels = NULL; + rel->reltarget->exprs = lappend(rel->reltarget->exprs, var); /* reltarget cost and width will be computed later */ } rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno], @@ -589,8 +610,10 @@ create_lateral_join_info(PlannerInfo *root) varno = -1; while ((varno = bms_next_member(eval_at, varno)) >= 0) { - RelOptInfo *brel = find_base_rel(root, varno); + RelOptInfo *brel = find_base_rel_ignore_join(root, varno); + if (brel == NULL) + continue; /* ignore outer joins in eval_at */ brel->lateral_relids = bms_add_members(brel->lateral_relids, phinfo->ph_lateral); } @@ -681,7 +704,10 @@ create_lateral_join_info(PlannerInfo *root) { RelOptInfo *brel2 = root->simple_rel_array[rti2]; - Assert(brel2 != NULL && brel2->reloptkind == RELOPT_BASEREL); + if (brel2 == NULL) + continue; /* must be an OJ */ + + Assert(brel2->reloptkind == RELOPT_BASEREL); brel2->lateral_referencers = bms_add_member(brel2->lateral_referencers, rti); } @@ -743,6 +769,7 @@ deconstruct_jointree(PlannerInfo *root) /* These are filled as we scan the jointree */ root->all_baserels = NULL; + root->outer_join_rels = NULL; root->nullable_baserels = NULL; /* Perform the initial scan of the jointree */ @@ -750,6 +777,9 @@ deconstruct_jointree(PlannerInfo *root) false, &item_list); + /* Now we can form the value of all_query_rels, too */ + root->all_query_rels = bms_union(root->all_baserels, root->outer_join_rels); + /* Now scan all the jointree nodes again, and distribute quals */ foreach(lc, item_list) { @@ -762,6 +792,40 @@ deconstruct_jointree(PlannerInfo *root) /* Shouldn't be any leftover postponed quals */ Assert(postponed_qual_list == NIL); + /* + * However, if there were any special joins then we may have some + * postponed LEFT JOIN clauses to deal with. + */ + if (root->join_info_list) + { + /* + * XXX hack: when we call distribute_qual_to_rels to process one of + * these clauses, neither the owning SpecialJoinInfo nor any later + * ones can appear in root->join_info_list, else the wrong things will + * happen. Fake it out by emptying join_info_list and rebuilding it + * as we go. This works because join_info_list is only appended to + * during deconstruct_distribute, so we know we are examining + * SpecialJoinInfos bottom-up, just like the first time. We can get + * rid of this hack later, after fixing things so that + * distribute_qual_to_rels doesn't have that requirement about + * join_info_list. + */ + root->join_info_list = NIL; + + foreach(lc, item_list) + { + JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc); + + if (jtitem->oj_joinclauses != NIL) + deconstruct_distribute_oj_quals(root, item_list, jtitem); + + /* XXX Rest of hack: rebuild join_info_list as we go */ + if (jtitem->sjinfo) + root->join_info_list = lappend(root->join_info_list, + jtitem->sjinfo); + } + } + /* Don't need the JoinTreeItems any more */ list_free_deep(item_list); @@ -905,6 +969,14 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, /* Compute qualscope etc */ jtitem->qualscope = bms_union(left_item->qualscope, right_item->qualscope); + /* caution: ANTI join derived from SEMI will lack rtindex */ + if (j->rtindex != 0) + { + jtitem->qualscope = bms_add_member(jtitem->qualscope, + j->rtindex); + root->outer_join_rels = bms_add_member(root->outer_join_rels, + j->rtindex); + } jtitem->inner_join_rels = bms_union(left_item->inner_join_rels, right_item->inner_join_rels); jtitem->left_rels = left_item->qualscope; @@ -925,6 +997,8 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, /* Compute qualscope etc */ jtitem->qualscope = bms_union(left_item->qualscope, right_item->qualscope); + /* SEMI join never has rtindex, so don't add to anything */ + Assert(j->rtindex == 0); jtitem->inner_join_rels = bms_union(left_item->inner_join_rels, right_item->inner_join_rels); jtitem->left_rels = left_item->qualscope; @@ -952,6 +1026,11 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, /* Compute qualscope etc */ jtitem->qualscope = bms_union(left_item->qualscope, right_item->qualscope); + Assert(j->rtindex != 0); + jtitem->qualscope = bms_add_member(jtitem->qualscope, + j->rtindex); + root->outer_join_rels = bms_add_member(root->outer_join_rels, + j->rtindex); jtitem->inner_join_rels = bms_union(left_item->inner_join_rels, right_item->inner_join_rels); jtitem->left_rels = left_item->qualscope; @@ -1073,7 +1152,8 @@ deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, NULL, root->qual_security_level, jtitem->qualscope, NULL, NULL, - NULL); + true, false, false, + NULL, NULL); else new_postponed_quals = lappend(new_postponed_quals, pq); } @@ -1087,7 +1167,8 @@ deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, NULL, root->qual_security_level, jtitem->qualscope, NULL, NULL, - postponed_qual_list); + true, false, false, + postponed_qual_list, NULL); } else if (IsA(jtnode, JoinExpr)) { @@ -1096,6 +1177,7 @@ deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, Relids ojscope; List *my_quals; SpecialJoinInfo *sjinfo; + List **postponed_oj_qual_list; ListCell *l; /* @@ -1138,6 +1220,7 @@ deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, jtitem->right_rels, jtitem->inner_join_rels, j->jointype, + j->rtindex, my_quals); jtitem->sjinfo = sjinfo; if (j->jointype == JOIN_SEMI) @@ -1146,6 +1229,19 @@ deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, { ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + + /* + * Add back any commutable lower OJ relids that were removed + * from min_lefthand or min_righthand, else the ojscope + * cross-check in distribute_qual_to_rels will complain. If + * any such OJs were removed, we will postpone processing of + * non-degenerate clauses, so this addition doesn't affect + * anything except that cross-check and some Asserts. Real + * clause positioning decisions will be made later, when we + * revisit the postponed clauses. + */ + if (sjinfo->commute_below) + ojscope = bms_add_members(ojscope, sjinfo->commute_below); } } else @@ -1154,6 +1250,18 @@ deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, ojscope = NULL; } + /* + * If it's a left join with a join clause that is strict for the LHS, + * then we need to postpone handling of any non-degenerate join + * clauses, in case the join is able to commute with another left join + * per identity 3. (Degenerate clauses need not be postponed, since + * they will drop down below this join anyway.) + */ + if (j->jointype == JOIN_LEFT && sjinfo->lhs_strict) + postponed_oj_qual_list = &jtitem->oj_joinclauses; + else + postponed_oj_qual_list = NULL; + /* Process the JOIN's qual clauses */ distribute_quals_to_rels(root, my_quals, jtitem->below_outer_join, @@ -1161,7 +1269,10 @@ deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem, root->qual_security_level, jtitem->qualscope, ojscope, jtitem->nonnullable_rels, - postponed_qual_list); + true, /* allow_equivalence */ + false, false, /* not clones */ + postponed_qual_list, + postponed_oj_qual_list); /* And add the SpecialJoinInfo to join_info_list */ if (sjinfo) @@ -1223,6 +1334,9 @@ process_security_barrier_quals(PlannerInfo *root, qualscope, qualscope, NULL, + true, + false, false, /* not clones */ + NULL, NULL); security_level++; } @@ -1236,10 +1350,11 @@ process_security_barrier_quals(PlannerInfo *root, * Build a SpecialJoinInfo for the current outer join * * Inputs: - * left_rels: the base Relids syntactically on outer side of join - * right_rels: the base Relids syntactically on inner side of join - * inner_join_rels: base Relids participating in inner joins below this one + * left_rels: the base+OJ Relids syntactically on outer side of join + * right_rels: the base+OJ Relids syntactically on inner side of join + * inner_join_rels: base+OJ Relids participating in inner joins below this one * jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI) + * ojrelid: RT index of the join RTE (0 for SEMI, which isn't in the RT list) * clause: the outer join's join condition (in implicit-AND format) * * The node should eventually be appended to root->join_info_list, but we @@ -1253,7 +1368,8 @@ static SpecialJoinInfo * make_outerjoininfo(PlannerInfo *root, Relids left_rels, Relids right_rels, Relids inner_join_rels, - JoinType jointype, List *clause) + JoinType jointype, Index ojrelid, + List *clause) { SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo); Relids clause_relids; @@ -1301,6 +1417,11 @@ make_outerjoininfo(PlannerInfo *root, sjinfo->syn_lefthand = left_rels; sjinfo->syn_righthand = right_rels; sjinfo->jointype = jointype; + sjinfo->ojrelid = ojrelid; + /* these fields may get added to later: */ + sjinfo->commute_above_l = NULL; + sjinfo->commute_above_r = NULL; + sjinfo->commute_below = NULL; /* this always starts out false */ sjinfo->delay_upper_joins = false; @@ -1348,6 +1469,7 @@ make_outerjoininfo(PlannerInfo *root, foreach(l, root->join_info_list) { SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l); + bool have_unsafe_phvs; /* * A full join is an optimization barrier: we can't associate into or @@ -1363,6 +1485,9 @@ make_outerjoininfo(PlannerInfo *root, otherinfo->syn_lefthand); min_lefthand = bms_add_members(min_lefthand, otherinfo->syn_righthand); + if (otherinfo->ojrelid != 0) + min_lefthand = bms_add_member(min_lefthand, + otherinfo->ojrelid); } if (bms_overlap(right_rels, otherinfo->syn_lefthand) || bms_overlap(right_rels, otherinfo->syn_righthand)) @@ -1371,11 +1496,26 @@ make_outerjoininfo(PlannerInfo *root, otherinfo->syn_lefthand); min_righthand = bms_add_members(min_righthand, otherinfo->syn_righthand); + if (otherinfo->ojrelid != 0) + min_righthand = bms_add_member(min_righthand, + otherinfo->ojrelid); } /* Needn't do anything else with the full join */ continue; } + /* + * If our join condition contains any PlaceHolderVars that need to be + * evaluated above the lower OJ, then we can't commute with it. + */ + if (otherinfo->ojrelid != 0) + have_unsafe_phvs = + contain_placeholder_references_to(root, + (Node *) clause, + otherinfo->ojrelid); + else + have_unsafe_phvs = false; + /* * For a lower OJ in our LHS, if our join condition uses the lower * join's RHS and is not strict for that rel, we must preserve the @@ -1383,23 +1523,44 @@ make_outerjoininfo(PlannerInfo *root, * min_lefthand. (We must use its full syntactic relset, not just its * min_lefthand + min_righthand. This is because there might be other * OJs below this one that this one can commute with, but we cannot - * commute with them if we don't with this one.) Also, if the current - * join is a semijoin or antijoin, we must preserve ordering - * regardless of strictness. + * commute with them if we don't with this one.) Also, if we have + * unsafe PHVs or the current join is a semijoin or antijoin, we must + * preserve ordering regardless of strictness. * * Note: I believe we have to insist on being strict for at least one * rel in the lower OJ's min_righthand, not its whole syn_righthand. + * + * 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_lefthand so that commutation is allowed. */ if (bms_overlap(left_rels, otherinfo->syn_righthand)) { if (bms_overlap(clause_relids, otherinfo->syn_righthand) && - (jointype == JOIN_SEMI || jointype == JOIN_ANTI || + (have_unsafe_phvs || + jointype == JOIN_SEMI || jointype == JOIN_ANTI || !bms_overlap(strict_relids, otherinfo->min_righthand))) { + /* Preserve ordering */ min_lefthand = bms_add_members(min_lefthand, otherinfo->syn_lefthand); min_lefthand = bms_add_members(min_lefthand, otherinfo->syn_righthand); + if (otherinfo->ojrelid != 0) + min_lefthand = bms_add_member(min_lefthand, + otherinfo->ojrelid); + } + else if (jointype == JOIN_LEFT && + otherinfo->jointype == JOIN_LEFT && + bms_overlap(strict_relids, otherinfo->min_righthand)) + { + /* Identity 3 applies, so remove the ordering restriction */ + min_lefthand = bms_del_member(min_lefthand, otherinfo->ojrelid); + /* Add commutability markers to both SpecialJoinInfos */ + otherinfo->commute_above_l = + bms_add_member(otherinfo->commute_above_l, ojrelid); + sjinfo->commute_below = + bms_add_member(sjinfo->commute_below, otherinfo->ojrelid); } } @@ -1414,8 +1575,8 @@ make_outerjoininfo(PlannerInfo *root, * up with SpecialJoinInfos with identical min_righthands, which can * confuse join_is_legal (see discussion in backend/optimizer/README). * - * Also, we must preserve ordering anyway if either the current join - * or the lower OJ is either a semijoin or an antijoin. + * 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 @@ -1427,21 +1588,43 @@ make_outerjoininfo(PlannerInfo *root, * 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. */ if (bms_overlap(right_rels, otherinfo->syn_righthand)) { if (bms_overlap(clause_relids, otherinfo->syn_righthand) || !bms_overlap(clause_relids, otherinfo->min_lefthand) || + have_unsafe_phvs || jointype == JOIN_SEMI || jointype == JOIN_ANTI || otherinfo->jointype == JOIN_SEMI || otherinfo->jointype == JOIN_ANTI || !otherinfo->lhs_strict || otherinfo->delay_upper_joins) { + /* Preserve ordering */ min_righthand = bms_add_members(min_righthand, otherinfo->syn_lefthand); min_righthand = bms_add_members(min_righthand, otherinfo->syn_righthand); + if (otherinfo->ojrelid != 0) + min_righthand = bms_add_member(min_righthand, + otherinfo->ojrelid); + } + else if (jointype == JOIN_LEFT && + otherinfo->jointype == JOIN_LEFT && + otherinfo->lhs_strict) + { + /* Identity 3 applies, so remove the ordering restriction */ + min_righthand = bms_del_member(min_righthand, + otherinfo->ojrelid); + /* Add commutability markers to both SpecialJoinInfos */ + otherinfo->commute_above_r = + bms_add_member(otherinfo->commute_above_r, ojrelid); + sjinfo->commute_below = + bms_add_member(sjinfo->commute_below, otherinfo->ojrelid); } } } @@ -1666,6 +1849,207 @@ compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause) sjinfo->semi_rhs_exprs = semi_rhs_exprs; } +/* + * deconstruct_distribute_oj_quals + * Adjust LEFT JOIN quals to be suitable for commuted-left-join cases, + * then push them into the joinqual lists and EquivalenceClass structures. + * + * This runs immediately after we've completed the deconstruct_distribute scan. + * jtitems contains all the JoinTreeItems (in depth-first order), and jtitem + * is one that has postponed oj_joinclauses to deal with. + */ +static void +deconstruct_distribute_oj_quals(PlannerInfo *root, + List *jtitems, + JoinTreeItem *jtitem) +{ + SpecialJoinInfo *sjinfo = jtitem->sjinfo; + Relids qualscope, + ojscope, + nonnullable_rels; + + /* Recompute syntactic and semantic scopes of this left join */ + qualscope = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand); + qualscope = bms_add_member(qualscope, sjinfo->ojrelid); + ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand); + nonnullable_rels = sjinfo->syn_lefthand; + + /* + * If this join can commute with any other ones per outer-join identity 3, + * and it is the one providing the join clause with flexible semantics, + * then we have to generate variants of the join clause with different + * nullingrels labeling. Otherwise, just push out the postponed clause + * as-is. + */ + Assert(sjinfo->lhs_strict); /* else we shouldn't be here */ + if (sjinfo->commute_above_r || + bms_overlap(sjinfo->commute_below, sjinfo->syn_lefthand)) + { + Relids joins_above; + Relids joins_below; + Relids joins_so_far; + List *quals; + ListCell *lc; + + /* + * Put any OJ relids that were removed from min_righthand back into + * ojscope, else distribute_qual_to_rels will complain. + */ + ojscope = bms_join(ojscope, bms_intersect(sjinfo->commute_below, + sjinfo->syn_righthand)); + + /* Identify the outer joins this one commutes with */ + joins_above = sjinfo->commute_above_r; + joins_below = bms_intersect(sjinfo->commute_below, + sjinfo->syn_lefthand); + + /* + * Generate qual variants with different sets of nullingrels bits. + * + * We only need bit-sets that correspond to the successively less + * deeply syntactically-nested subsets of this join and its + * commutators. That's true first because obviously only those forms + * of the Vars and PHVs could appear elsewhere in the query, and + * second because the outer join identities do not provide a way to + * re-order such joins in a way that would require different marking. + * (That is, while the current join may commute with several others, + * none of those others can commute with each other.) To visit the + * interesting joins in syntactic nesting order, we rely on the + * jtitems list to be ordered that way. + * + * We first strip out all the nullingrels bits corresponding to + * commutating joins below this one, and then successively put them + * back as we crawl up the join stack. + */ + quals = jtitem->oj_joinclauses; + if (!bms_is_empty(joins_below)) + quals = (List *) remove_nulling_relids((Node *) quals, + joins_below, + NULL); + + joins_so_far = NULL; + foreach(lc, jtitems) + { + JoinTreeItem *otherjtitem = (JoinTreeItem *) lfirst(lc); + SpecialJoinInfo *othersj = otherjtitem->sjinfo; + bool below_sjinfo = false; + bool above_sjinfo = false; + Relids this_qualscope; + Relids this_ojscope; + bool allow_equivalence, + has_clone, + is_clone; + + if (othersj == NULL) + continue; /* not an outer-join item, ignore */ + + if (bms_is_member(othersj->ojrelid, joins_below)) + { + /* othersj commutes with sjinfo from below left */ + below_sjinfo = true; + } + else if (othersj == sjinfo) + { + /* found our join in syntactic order */ + Assert(bms_equal(joins_so_far, joins_below)); + } + else if (bms_is_member(othersj->ojrelid, joins_above)) + { + /* othersj commutes with sjinfo from above */ + above_sjinfo = true; + } + else + { + /* othersj is not relevant, ignore */ + continue; + } + + /* + * When we are looking at joins above sjinfo, we are envisioning + * pushing sjinfo to above othersj, so add othersj's nulling bit + * before distributing the quals. + */ + if (above_sjinfo) + quals = (List *) + add_nulling_relids((Node *) quals, + othersj->min_righthand, + bms_make_singleton(othersj->ojrelid)); + + /* Compute qualscope and ojscope for this join level */ + this_qualscope = bms_union(qualscope, joins_so_far); + this_ojscope = bms_union(ojscope, joins_so_far); + if (above_sjinfo) + { + /* othersj is not yet in joins_so_far, but we need it */ + this_qualscope = bms_add_member(this_qualscope, + othersj->ojrelid); + this_ojscope = bms_add_member(this_ojscope, + othersj->ojrelid); + /* sjinfo is in joins_so_far, and we don't want it */ + this_ojscope = bms_del_member(this_ojscope, + sjinfo->ojrelid); + } + + /* + * We generate EquivalenceClasses only from the first form of the + * quals, with the fewest nullingrels bits set. An EC made from + * this version of the quals can be useful below the outer-join + * nest, whereas versions with some nullingrels bits set would not + * be. We cannot generate ECs from more than one version, or + * we'll make nonsensical conclusions that Vars with nullingrels + * bits set are equal to their versions without. Fortunately, + * such ECs wouldn't be very useful anyway, because they'd equate + * values not observable outside the join nest. (See + * optimizer/README.) + * + * The first form of the quals is also the only one marked as + * has_clone rather than is_clone. + */ + allow_equivalence = (joins_so_far == NULL); + has_clone = allow_equivalence; + is_clone = !has_clone; + + distribute_quals_to_rels(root, quals, + true, + sjinfo, + root->qual_security_level, + this_qualscope, + this_ojscope, nonnullable_rels, + allow_equivalence, + has_clone, + is_clone, + NULL, NULL); /* no more postponement */ + + /* + * Adjust qual nulling bits for next level up, if needed. We + * don't want to put sjinfo's own bit in at all, and if we're + * above sjinfo then we did it already. + */ + if (below_sjinfo) + quals = (List *) + add_nulling_relids((Node *) quals, + othersj->min_righthand, + bms_make_singleton(othersj->ojrelid)); + + /* ... and track joins processed so far */ + joins_so_far = bms_add_member(joins_so_far, othersj->ojrelid); + } + } + else + { + /* No commutation possible, just process the postponed clauses */ + distribute_quals_to_rels(root, jtitem->oj_joinclauses, + true, + sjinfo, + root->qual_security_level, + qualscope, + ojscope, nonnullable_rels, + true, /* allow_equivalence */ + false, false, /* not clones */ + NULL, NULL); /* no more postponement */ + } +} + /***************************************************************************** * @@ -1686,7 +2070,11 @@ distribute_quals_to_rels(PlannerInfo *root, List *clauses, Relids qualscope, Relids ojscope, Relids outerjoin_nonnullable, - List **postponed_qual_list) + bool allow_equivalence, + bool has_clone, + bool is_clone, + List **postponed_qual_list, + List **postponed_oj_qual_list) { ListCell *lc; @@ -1701,7 +2089,11 @@ distribute_quals_to_rels(PlannerInfo *root, List *clauses, qualscope, ojscope, outerjoin_nonnullable, - postponed_qual_list); + allow_equivalence, + has_clone, + is_clone, + postponed_qual_list, + postponed_oj_qual_list); } } @@ -1711,26 +2103,35 @@ distribute_quals_to_rels(PlannerInfo *root, List *clauses, * (depending on whether the clause is a join) of each base relation * mentioned in the clause. A RestrictInfo node is created and added to * the appropriate list for each rel. Alternatively, if the clause uses a - * mergejoinable operator and is not delayed by outer-join rules, enter - * the left- and right-side expressions into the query's list of - * EquivalenceClasses. Alternatively, if the clause needs to be treated - * as belonging to a higher join level, just add it to postponed_qual_list. + * mergejoinable operator, enter its left- and right-side expressions into + * the query's EquivalenceClasses. + * + * In some cases, quals will be added to postponed_qual_list or + * postponed_oj_qual_list instead of being processed right away. + * These will be dealt with in later steps of deconstruct_jointree. * * 'clause': the qual clause to be distributed * 'below_outer_join': true if the qual is from a JOIN/ON that is below the * nullable side of a higher-level outer join * 'sjinfo': join's SpecialJoinInfo (NULL for an inner join or WHERE clause) * 'security_level': security_level to assign to the qual - * 'qualscope': set of baserels the qual's syntactic scope covers - * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels - * needed to form this join + * 'qualscope': set of base+OJ rels the qual's syntactic scope covers + * 'ojscope': NULL if not an outer-join qual, else the minimum set of base+OJ + * rels needed to form this join * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of - * baserels appearing on the outer (nonnullable) side of the join + * base+OJ rels appearing on the outer (nonnullable) side of the join * (for FULL JOIN this includes both sides of the join, and must in fact * equal qualscope) + * 'allow_equivalence': true if it's okay to convert clause into an + * EquivalenceClass + * 'has_clone': has_clone property to assign to the qual + * 'is_clone': is_clone property to assign to the qual * 'postponed_qual_list': list of PostponedQual structs, which we can add * this qual to if it turns out to belong to a higher join level. * Can be NULL if caller knows postponement is impossible. + * 'postponed_oj_qual_list': if not NULL, non-degenerate outer join clauses + * should be added to this list instead of being processed (list entries + * are just the bare clauses) * * 'qualscope' identifies what level of JOIN the qual came from syntactically. * 'ojscope' is needed if we decide to force the qual up to the outer-join @@ -1748,7 +2149,11 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, Relids qualscope, Relids ojscope, Relids outerjoin_nonnullable, - List **postponed_qual_list) + bool allow_equivalence, + bool has_clone, + bool is_clone, + List **postponed_qual_list, + List **postponed_oj_qual_list) { Relids relids; bool is_pushed_down; @@ -1842,7 +2247,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, { relids = get_relids_in_jointree((Node *) root->parse->jointree, - false); + true, false); qualscope = bms_copy(relids); } } @@ -1885,8 +2290,18 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, { /* * The qual is attached to an outer join and mentions (some of the) - * rels on the nonnullable side, so it's not degenerate. - * + * rels on the nonnullable side, so it's not degenerate. If the + * caller wants to postpone handling such clauses, just add it to + * postponed_oj_qual_list and return. (The work we've done up to here + * will have to be redone later, but there's not much of it.) + */ + if (postponed_oj_qual_list != NULL) + { + *postponed_oj_qual_list = lappend(*postponed_oj_qual_list, clause); + return; + } + + /* * We can't use such a clause to deduce equivalence (the left and * right sides might be unequal above the join because one of them has * gone to NULL) ... but we might be able to use it for more limited @@ -1952,6 +2367,11 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, if (check_redundant_nullability_qual(root, clause)) return; } + else if (!allow_equivalence) + { + /* Caller says it mustn't become an equivalence class */ + maybe_equivalence = false; + } else { /* @@ -1986,11 +2406,22 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, outerjoin_nonnullable, nullable_relids); + /* Apply appropriate clone marking, too */ + restrictinfo->has_clone = has_clone; + restrictinfo->is_clone = is_clone; + /* - * If it's a join clause (either naturally, or because delayed by - * outer-join rules), add vars used in the clause to targetlists of their - * relations, so that they will be emitted by the plan nodes that scan - * those relations (else they won't be available at the join node!). + * If it's a join clause, add vars used in the clause to targetlists of + * their relations, so that they will be emitted by the plan nodes that + * scan those relations (else they won't be available at the join node!). + * + * Normally we mark the vars as needed at the join identified by "relids". + * However, if this is a clone clause then ignore the outer-join relids in + * that set. Otherwise, vars appearing in a cloned clause would end up + * marked as having to propagate to the highest one of the commuting + * joins, which would often be an overestimate. For such clauses, correct + * var propagation is ensured by making ojscope include input rels from + * both sides of the join. * * Note: if the clause gets absorbed into an EquivalenceClass then this * may be unnecessary, but for now we have to do it to cover the case @@ -2003,8 +2434,13 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, PVC_RECURSE_AGGREGATES | PVC_RECURSE_WINDOWFUNCS | PVC_INCLUDE_PLACEHOLDERS); + Relids where_needed; - add_vars_to_targetlist(root, vars, relids); + if (is_clone) + where_needed = bms_intersect(relids, root->all_baserels); + else + where_needed = relids; + add_vars_to_targetlist(root, vars, where_needed); list_free(vars); } @@ -2495,7 +2931,7 @@ process_implied_equality(PlannerInfo *root, { relids = get_relids_in_jointree((Node *) root->parse->jointree, - false); + true, false); } } } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index e21e72eb87..71b4d3ca56 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -2231,7 +2231,7 @@ preprocess_rowmarks(PlannerInfo *root) * make a bitmapset of all base rels and then remove the items we don't * need or have FOR [KEY] UPDATE/SHARE marks for. */ - rels = get_relids_in_jointree((Node *) parse->jointree, false); + rels = get_relids_in_jointree((Node *) parse->jointree, false, false); if (parse->resultRelation) rels = bms_del_member(rels, parse->resultRelation); diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 596f1fbc8e..846ca39269 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -30,11 +30,21 @@ #include "utils/syscache.h" +typedef enum +{ + NRM_EQUAL, /* expect exact match of nullingrels */ + NRM_SUBSET, /* actual Var may have a subset of input */ + NRM_SUPERSET /* actual Var may have a superset of input */ +} NullingRelsMatch; + typedef struct { int varno; /* RT index of Var */ AttrNumber varattno; /* attr number of Var */ AttrNumber resno; /* TLE position of Var */ +#ifdef USE_ASSERT_CHECKING + Bitmapset *varnullingrels; /* Var's varnullingrels */ +#endif } tlist_vinfo; typedef struct @@ -60,6 +70,7 @@ typedef struct indexed_tlist *inner_itlist; Index acceptable_rel; int rtoffset; + NullingRelsMatch nrm_match; double num_exec; } fix_join_expr_context; @@ -69,6 +80,7 @@ typedef struct indexed_tlist *subplan_itlist; int newvarno; int rtoffset; + NullingRelsMatch nrm_match; double num_exec; } fix_upper_expr_context; @@ -159,7 +171,12 @@ static indexed_tlist *build_tlist_index(List *tlist); static Var *search_indexed_tlist_for_var(Var *var, indexed_tlist *itlist, int newvarno, - int rtoffset); + int rtoffset, + NullingRelsMatch nrm_match); +static Var *search_indexed_tlist_for_phv(PlaceHolderVar *phv, + indexed_tlist *itlist, + int newvarno, + NullingRelsMatch nrm_match); static Var *search_indexed_tlist_for_non_var(Expr *node, indexed_tlist *itlist, int newvarno); @@ -172,14 +189,18 @@ static List *fix_join_expr(PlannerInfo *root, indexed_tlist *outer_itlist, indexed_tlist *inner_itlist, Index acceptable_rel, - int rtoffset, double num_exec); + int rtoffset, + NullingRelsMatch nrm_match, + double num_exec); static Node *fix_join_expr_mutator(Node *node, fix_join_expr_context *context); static Node *fix_upper_expr(PlannerInfo *root, Node *node, indexed_tlist *subplan_itlist, int newvarno, - int rtoffset, double num_exec); + int rtoffset, + NullingRelsMatch nrm_match, + double num_exec); static Node *fix_upper_expr_mutator(Node *node, fix_upper_expr_context *context); static List *set_returning_clause_references(PlannerInfo *root, @@ -1113,13 +1134,13 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset) fix_join_expr(root, splan->onConflictSet, NULL, itlist, linitial_int(splan->resultRelations), - rtoffset, NUM_EXEC_QUAL(plan)); + rtoffset, NRM_EQUAL, NUM_EXEC_QUAL(plan)); splan->onConflictWhere = (Node *) fix_join_expr(root, (List *) splan->onConflictWhere, NULL, itlist, linitial_int(splan->resultRelations), - rtoffset, NUM_EXEC_QUAL(plan)); + rtoffset, NRM_EQUAL, NUM_EXEC_QUAL(plan)); pfree(itlist); @@ -1176,6 +1197,7 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset) NULL, itlist, resultrel, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST(plan)); /* Fix quals too. */ @@ -1184,6 +1206,7 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset) NULL, itlist, resultrel, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL(plan)); } } @@ -1329,6 +1352,7 @@ set_indexonlyscan_references(PlannerInfo *root, index_itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST((Plan *) plan)); plan->scan.plan.qual = (List *) fix_upper_expr(root, @@ -1336,6 +1360,7 @@ set_indexonlyscan_references(PlannerInfo *root, index_itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) plan)); plan->recheckqual = (List *) fix_upper_expr(root, @@ -1343,6 +1368,7 @@ set_indexonlyscan_references(PlannerInfo *root, index_itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) plan)); /* indexqual is already transformed to reference index columns */ plan->indexqual = fix_scan_list(root, plan->indexqual, @@ -1549,6 +1575,7 @@ set_foreignscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST((Plan *) fscan)); fscan->scan.plan.qual = (List *) fix_upper_expr(root, @@ -1556,6 +1583,7 @@ set_foreignscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) fscan)); fscan->fdw_exprs = (List *) fix_upper_expr(root, @@ -1563,6 +1591,7 @@ set_foreignscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) fscan)); fscan->fdw_recheck_quals = (List *) fix_upper_expr(root, @@ -1570,6 +1599,7 @@ set_foreignscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) fscan)); pfree(itlist); /* fdw_scan_tlist itself just needs fix_scan_list() adjustments */ @@ -1630,6 +1660,7 @@ set_customscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST((Plan *) cscan)); cscan->scan.plan.qual = (List *) fix_upper_expr(root, @@ -1637,6 +1668,7 @@ set_customscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) cscan)); cscan->custom_exprs = (List *) fix_upper_expr(root, @@ -1644,6 +1676,7 @@ set_customscan_references(PlannerInfo *root, itlist, INDEX_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) cscan)); pfree(itlist); /* custom_scan_tlist itself just needs fix_scan_list() adjustments */ @@ -1830,6 +1863,7 @@ set_hash_references(PlannerInfo *root, Plan *plan, int rtoffset) outer_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL(plan)); /* Hash doesn't project */ @@ -2165,6 +2199,7 @@ fix_scan_expr_mutator(Node *node, fix_scan_expr_context *context) /* At scan level, we should always just evaluate the contained expr */ PlaceHolderVar *phv = (PlaceHolderVar *) node; + Assert(phv->phnullingrels == NULL); return fix_scan_expr_mutator((Node *) phv->phexpr, context); } if (IsA(node, AlternativeSubPlan)) @@ -2222,6 +2257,7 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) inner_itlist, (Index) 0, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) join)); /* Now do join-type-specific stuff */ @@ -2234,11 +2270,21 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) { NestLoopParam *nlp = (NestLoopParam *) lfirst(lc); + /* + * Because we don't reparameterize parameterized paths to match + * the outer-join level at which they are used, Vars seen in the + * NestLoopParam expression may have nullingrels that are just a + * subset of those in the Vars actually available from the outer + * side. Not checking this exactly is a bit grotty, but the work + * needed to make things match up perfectly seems well out of + * proportion to the value. + */ nlp->paramval = (Var *) fix_upper_expr(root, (Node *) nlp->paramval, outer_itlist, OUTER_VAR, rtoffset, + NRM_SUBSET, NUM_EXEC_TLIST(outer_plan)); /* Check we replaced any PlaceHolderVar with simple Var */ if (!(IsA(nlp->paramval, Var) && @@ -2256,6 +2302,7 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) inner_itlist, (Index) 0, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) join)); } else if (IsA(join, HashJoin)) @@ -2268,6 +2315,7 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) inner_itlist, (Index) 0, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) join)); /* @@ -2279,45 +2327,27 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) outer_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL((Plan *) join)); } /* * Now we need to fix up the targetlist and qpqual, which are logically - * above the join. This means they should not re-use any input expression - * that was computed in the nullable side of an outer join. Vars and - * PlaceHolderVars are fine, so we can implement this restriction just by - * clearing has_non_vars in the indexed_tlist structs. - * - * XXX This is a grotty workaround for the fact that we don't clearly - * distinguish between a Var appearing below an outer join and the "same" - * Var appearing above it. If we did, we'd not need to hack the matching - * rules this way. + * above the join. This means that, if it's not an inner join, any Vars + * and PHVs appearing here should have nullingrels that include the + * effects of the outer join, ie they will have nullingrels equal to the + * input Vars' nullingrels plus the bit added by the outer join. We don't + * currently have enough info available here to identify what that should + * be, so we just tell fix_join_expr to accept superset nullingrels + * matches instead of exact ones. */ - switch (join->jointype) - { - case JOIN_LEFT: - case JOIN_SEMI: - case JOIN_ANTI: - inner_itlist->has_non_vars = false; - break; - case JOIN_RIGHT: - outer_itlist->has_non_vars = false; - break; - case JOIN_FULL: - outer_itlist->has_non_vars = false; - inner_itlist->has_non_vars = false; - break; - default: - break; - } - join->plan.targetlist = fix_join_expr(root, join->plan.targetlist, outer_itlist, inner_itlist, (Index) 0, rtoffset, + (join->jointype == JOIN_INNER ? NRM_EQUAL : NRM_SUPERSET), NUM_EXEC_TLIST((Plan *) join)); join->plan.qual = fix_join_expr(root, join->plan.qual, @@ -2325,6 +2355,7 @@ set_join_references(PlannerInfo *root, Join *join, int rtoffset) inner_itlist, (Index) 0, rtoffset, + (join->jointype == JOIN_INNER ? NRM_EQUAL : NRM_SUPERSET), NUM_EXEC_QUAL((Plan *) join)); pfree(outer_itlist); @@ -2379,6 +2410,7 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset) subplan_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST(plan)); } else @@ -2387,6 +2419,7 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset) subplan_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST(plan)); tle = flatCopyTargetEntry(tle); tle->expr = (Expr *) newexpr; @@ -2400,6 +2433,7 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset) subplan_itlist, OUTER_VAR, rtoffset, + NRM_EQUAL, NUM_EXEC_QUAL(plan)); pfree(subplan_itlist); @@ -2600,7 +2634,7 @@ set_dummy_tlist_references(Plan *plan, int rtoffset) * tlist_member() searches. * * The result of this function is an indexed_tlist struct to pass to - * search_indexed_tlist_for_var() or search_indexed_tlist_for_non_var(). + * search_indexed_tlist_for_var() and siblings. * When done, the indexed_tlist may be freed with a single pfree(). */ static indexed_tlist * @@ -2632,6 +2666,9 @@ build_tlist_index(List *tlist) vinfo->varno = var->varno; vinfo->varattno = var->varattno; vinfo->resno = tle->resno; +#ifdef USE_ASSERT_CHECKING + vinfo->varnullingrels = var->varnullingrels; +#endif vinfo++; } else if (tle->expr && IsA(tle->expr, PlaceHolderVar)) @@ -2684,6 +2721,9 @@ build_tlist_index_other_vars(List *tlist, int ignore_rel) vinfo->varno = var->varno; vinfo->varattno = var->varattno; vinfo->resno = tle->resno; +#ifdef USE_ASSERT_CHECKING + vinfo->varnullingrels = var->varnullingrels; +#endif vinfo++; } } @@ -2703,10 +2743,17 @@ build_tlist_index_other_vars(List *tlist, int ignore_rel) * modified varno/varattno (to wit, newvarno and the resno of the TLE entry). * Also ensure that varnosyn is incremented by rtoffset. * If no match, return NULL. + * + * In debugging builds, we cross-check the varnullingrels of the subplan + * output Var based on nrm_match. Most call sites should pass NRM_EQUAL + * indicating we expect an exact match. However, there are places where + * we haven't cleaned things up completely, and we have to settle for + * allowing subset or superset matches. */ static Var * search_indexed_tlist_for_var(Var *var, indexed_tlist *itlist, - int newvarno, int rtoffset) + int newvarno, int rtoffset, + NullingRelsMatch nrm_match) { int varno = var->varno; AttrNumber varattno = var->varattno; @@ -2722,6 +2769,36 @@ search_indexed_tlist_for_var(Var *var, indexed_tlist *itlist, /* Found a match */ Var *newvar = copyVar(var); + /* + * Assert that we kept all the nullingrels machinations straight. + * + * XXX eventually reduce this to a plain Assert. Right now it's + * more useful to warn and keep going. + * + * XXX skip this check for system columns and whole-row Vars. + * That's because such Vars might be row identity Vars, which are + * generated without any varnullingrels. It'd be hard to do + * otherwise, since they're normally made very early in planning, + * when we haven't looked at the jointree yet and don't know which + * joins might null such Vars. Doesn't seem worth the expense to + * make them fully valid. (While it's slightly annoying that we + * thereby lose checking for user-written references to such + * columns, it seems unlikely that a bug in nullingrels logic + * would affect only system columns.) + */ +#ifdef USE_ASSERT_CHECKING + if (!(varattno <= 0 || + (nrm_match == NRM_SUBSET ? + bms_is_subset(var->varnullingrels, vinfo->varnullingrels) : + nrm_match == NRM_SUPERSET ? + bms_is_subset(vinfo->varnullingrels, var->varnullingrels) : + bms_equal(vinfo->varnullingrels, var->varnullingrels)))) + elog(WARNING, "bogus varnullingrels for (%d,%d): expected %s, found %s in subplan", + varno, varattno, + bmsToString(var->varnullingrels), + bmsToString(vinfo->varnullingrels)); +#endif + newvar->varno = newvarno; newvar->varattno = vinfo->resno; if (newvar->varnosyn > 0) @@ -2734,15 +2811,74 @@ search_indexed_tlist_for_var(Var *var, indexed_tlist *itlist, } /* - * search_indexed_tlist_for_non_var --- find a non-Var in an indexed tlist + * search_indexed_tlist_for_phv --- find a PlaceHolderVar in an indexed tlist * * If a match is found, return a Var constructed to reference the tlist item. * If no match, return NULL. * - * NOTE: it is a waste of time to call this unless itlist->has_ph_vars or - * itlist->has_non_vars. Furthermore, set_join_references() relies on being - * able to prevent matching of non-Vars by clearing itlist->has_non_vars, - * so there's a correctness reason not to call it unless that's set. + * Cross-check phnullingrels as in search_indexed_tlist_for_var. + * + * NOTE: it is a waste of time to call this unless itlist->has_ph_vars. + */ +static Var * +search_indexed_tlist_for_phv(PlaceHolderVar *phv, + indexed_tlist *itlist, int newvarno, + NullingRelsMatch nrm_match) +{ + ListCell *lc; + + foreach(lc, itlist->tlist) + { + TargetEntry *tle = (TargetEntry *) lfirst(lc); + + if (tle->expr && IsA(tle->expr, PlaceHolderVar)) + { + PlaceHolderVar *subphv = (PlaceHolderVar *) tle->expr; + Var *newvar; + + /* + * Analogously to search_indexed_tlist_for_var, we match on phid + * only. We don't use equal(), partially for speed but mostly + * because phnullingrels might not be exactly equal. + */ + if (phv->phid != subphv->phid) + continue; + + /* + * Assert that we kept all the nullingrels machinations straight. + * + * XXX eventually reduce this to a plain Assert. Right now it's + * more useful to warn and keep going. + */ +#ifdef USE_ASSERT_CHECKING + if (!(nrm_match == NRM_SUBSET ? + bms_is_subset(phv->phnullingrels, subphv->phnullingrels) : + nrm_match == NRM_SUPERSET ? + bms_is_subset(subphv->phnullingrels, phv->phnullingrels) : + bms_equal(subphv->phnullingrels, phv->phnullingrels))) + elog(WARNING, "bogus phnullingrels for %d: expected %s, found %s in subplan", + phv->phid, + bmsToString(phv->phnullingrels), + bmsToString(subphv->phnullingrels)); +#endif + + /* Found a matching subplan output expression */ + newvar = makeVarFromTargetEntry(newvarno, tle); + newvar->varnosyn = 0; /* wasn't ever a plain Var */ + newvar->varattnosyn = 0; + return newvar; + } + } + return NULL; /* no match */ +} + +/* + * search_indexed_tlist_for_non_var --- find a non-Var/PHV in an indexed tlist + * + * If a match is found, return a Var constructed to reference the tlist item. + * If no match, return NULL. + * + * NOTE: it is a waste of time to call this unless itlist->has_non_vars. */ static Var * search_indexed_tlist_for_non_var(Expr *node, @@ -2849,6 +2985,7 @@ search_indexed_tlist_for_sortgroupref(Expr *node, * 'acceptable_rel' is either zero or the rangetable index of a relation * whose Vars may appear in the clause without provoking an error * 'rtoffset': how much to increment varnos by + * 'nrm_match': as for search_indexed_tlist_for_var() * 'num_exec': estimated number of executions of expression * * Returns the new expression tree. The original clause structure is @@ -2861,6 +2998,7 @@ fix_join_expr(PlannerInfo *root, indexed_tlist *inner_itlist, Index acceptable_rel, int rtoffset, + NullingRelsMatch nrm_match, double num_exec) { fix_join_expr_context context; @@ -2870,6 +3008,7 @@ fix_join_expr(PlannerInfo *root, context.inner_itlist = inner_itlist; context.acceptable_rel = acceptable_rel; context.rtoffset = rtoffset; + context.nrm_match = nrm_match; context.num_exec = num_exec; return (List *) fix_join_expr_mutator((Node *) clauses, &context); } @@ -2891,7 +3030,8 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) newvar = search_indexed_tlist_for_var(var, context->outer_itlist, OUTER_VAR, - context->rtoffset); + context->rtoffset, + context->nrm_match); if (newvar) return (Node *) newvar; } @@ -2902,7 +3042,8 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) newvar = search_indexed_tlist_for_var(var, context->inner_itlist, INNER_VAR, - context->rtoffset); + context->rtoffset, + context->nrm_match); if (newvar) return (Node *) newvar; } @@ -2927,22 +3068,25 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) /* See if the PlaceHolderVar has bubbled up from a lower plan node */ if (context->outer_itlist && context->outer_itlist->has_ph_vars) { - newvar = search_indexed_tlist_for_non_var((Expr *) phv, - context->outer_itlist, - OUTER_VAR); + newvar = search_indexed_tlist_for_phv(phv, + context->outer_itlist, + OUTER_VAR, + context->nrm_match); if (newvar) return (Node *) newvar; } if (context->inner_itlist && context->inner_itlist->has_ph_vars) { - newvar = search_indexed_tlist_for_non_var((Expr *) phv, - context->inner_itlist, - INNER_VAR); + newvar = search_indexed_tlist_for_phv(phv, + context->inner_itlist, + INNER_VAR, + context->nrm_match); if (newvar) return (Node *) newvar; } /* If not supplied by input plans, evaluate the contained expr */ + /* XXX can we assert something about phnullingrels? */ return fix_join_expr_mutator((Node *) phv->phexpr, context); } /* Try matching more complex expressions too, if tlists have any */ @@ -3001,6 +3145,7 @@ fix_join_expr_mutator(Node *node, fix_join_expr_context *context) * 'subplan_itlist': indexed target list for subplan (or index) * 'newvarno': varno to use for Vars referencing tlist elements * 'rtoffset': how much to increment varnos by + * 'nrm_match': as for search_indexed_tlist_for_var() * 'num_exec': estimated number of executions of expression * * The resulting tree is a copy of the original in which all Var nodes have @@ -3013,6 +3158,7 @@ fix_upper_expr(PlannerInfo *root, indexed_tlist *subplan_itlist, int newvarno, int rtoffset, + NullingRelsMatch nrm_match, double num_exec) { fix_upper_expr_context context; @@ -3021,6 +3167,7 @@ fix_upper_expr(PlannerInfo *root, context.subplan_itlist = subplan_itlist; context.newvarno = newvarno; context.rtoffset = rtoffset; + context.nrm_match = nrm_match; context.num_exec = num_exec; return fix_upper_expr_mutator(node, &context); } @@ -3039,7 +3186,8 @@ fix_upper_expr_mutator(Node *node, fix_upper_expr_context *context) newvar = search_indexed_tlist_for_var(var, context->subplan_itlist, context->newvarno, - context->rtoffset); + context->rtoffset, + context->nrm_match); if (!newvar) elog(ERROR, "variable not found in subplan target list"); return (Node *) newvar; @@ -3051,13 +3199,15 @@ fix_upper_expr_mutator(Node *node, fix_upper_expr_context *context) /* See if the PlaceHolderVar has bubbled up from a lower plan node */ if (context->subplan_itlist->has_ph_vars) { - newvar = search_indexed_tlist_for_non_var((Expr *) phv, - context->subplan_itlist, - context->newvarno); + newvar = search_indexed_tlist_for_phv(phv, + context->subplan_itlist, + context->newvarno, + context->nrm_match); if (newvar) return (Node *) newvar; } /* If not supplied by input plan, evaluate the contained expr */ + /* XXX can we assert something about phnullingrels? */ return fix_upper_expr_mutator((Node *) phv->phexpr, context); } /* Try matching more complex expressions too, if tlist has any */ @@ -3164,6 +3314,7 @@ set_returning_clause_references(PlannerInfo *root, NULL, resultRelation, rtoffset, + NRM_EQUAL, NUM_EXEC_TLIST(topplan)); pfree(itlist); diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index 4cec12ab19..13bbdfd7ba 100644 --- a/src/backend/optimizer/prep/prepjointree.c +++ b/src/backend/optimizer/prep/prepjointree.c @@ -51,17 +51,28 @@ typedef struct pullup_replace_vars_context * pullup (set only if target_rte->lateral) */ bool *outer_hasSubLinks; /* -> outer query's hasSubLinks */ int varno; /* varno of subquery */ - bool need_phvs; /* do we need PlaceHolderVars? */ - bool wrap_non_vars; /* do we need 'em on *all* non-Vars? */ + bool wrap_non_vars; /* do we need all non-Var outputs to be PHVs? */ Node **rv_cache; /* cache for results with PHVs */ } pullup_replace_vars_context; -typedef struct reduce_outer_joins_state +typedef struct reduce_outer_joins_pass1_state { Relids relids; /* base relids within this subtree */ bool contains_outer; /* does subtree contain outer join(s)? */ List *sub_states; /* List of states for subtree components */ -} reduce_outer_joins_state; +} reduce_outer_joins_pass1_state; + +typedef struct reduce_outer_joins_pass2_state +{ + Relids inner_reduced; /* OJ relids reduced to plain inner joins */ + List *partial_reduced; /* List of partially reduced FULL joins */ +} reduce_outer_joins_pass2_state; + +typedef struct reduce_outer_joins_partial_state +{ + int full_join_rti; /* RT index of a formerly-FULL join */ + Relids unreduced_side; /* relids in its still-nullable side */ +} reduce_outer_joins_partial_state; static Node *pull_up_sublinks_jointree_recurse(PlannerInfo *root, Node *jtnode, Relids *relids); @@ -70,12 +81,10 @@ static Node *pull_up_sublinks_qual_recurse(PlannerInfo *root, Node *node, Node **jtlink2, Relids available_rels2); static Node *pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode, JoinExpr *lowest_outer_join, - JoinExpr *lowest_nulling_outer_join, AppendRelInfo *containing_appendrel); static Node *pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, JoinExpr *lowest_outer_join, - JoinExpr *lowest_nulling_outer_join, AppendRelInfo *containing_appendrel); static Node *pull_up_simple_union_all(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte); @@ -92,7 +101,6 @@ static Node *pull_up_simple_values(PlannerInfo *root, Node *jtnode, static bool is_simple_values(PlannerInfo *root, RangeTblEntry *rte); static Node *pull_up_constant_function(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, - JoinExpr *lowest_nulling_outer_join, AppendRelInfo *containing_appendrel); static bool is_simple_union_all(Query *subquery); static bool is_simple_union_all_recurse(Node *setOp, Query *setOpQuery, @@ -103,24 +111,26 @@ static bool jointree_contains_lateral_outer_refs(PlannerInfo *root, Relids safe_upper_varnos); static void perform_pullup_replace_vars(PlannerInfo *root, pullup_replace_vars_context *rvcontext, - JoinExpr *lowest_nulling_outer_join, AppendRelInfo *containing_appendrel); static void replace_vars_in_jointree(Node *jtnode, - pullup_replace_vars_context *context, - JoinExpr *lowest_nulling_outer_join); + pullup_replace_vars_context *context); static Node *pullup_replace_vars(Node *expr, pullup_replace_vars_context *context); static Node *pullup_replace_vars_callback(Var *var, replace_rte_variables_context *context); static Query *pullup_replace_vars_subquery(Query *query, pullup_replace_vars_context *context); -static reduce_outer_joins_state *reduce_outer_joins_pass1(Node *jtnode); +static reduce_outer_joins_pass1_state *reduce_outer_joins_pass1(Node *jtnode); static void reduce_outer_joins_pass2(Node *jtnode, - reduce_outer_joins_state *state, + reduce_outer_joins_pass1_state *state1, + reduce_outer_joins_pass2_state *state2, PlannerInfo *root, Relids nonnullable_rels, List *forced_null_vars); -static Node *remove_useless_results_recurse(PlannerInfo *root, 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, + Relids *dropped_outer_joins); static int get_result_relid(PlannerInfo *root, Node *jtnode); static void remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc); static bool find_dependent_phvs(PlannerInfo *root, int varno); @@ -761,7 +771,7 @@ pull_up_subqueries(PlannerInfo *root) /* Recursion starts with no containing join nor appendrel */ root->parse->jointree = (FromExpr *) pull_up_subqueries_recurse(root, (Node *) root->parse->jointree, - NULL, NULL, NULL); + NULL, NULL); /* We should still have a FromExpr */ Assert(IsA(root->parse->jointree, FromExpr)); } @@ -776,12 +786,6 @@ pull_up_subqueries(PlannerInfo *root) * lowest_outer_join references the lowest such JoinExpr node; otherwise * it is NULL. We use this to constrain the effects of LATERAL subqueries. * - * If this jointree node is within the nullable side of an outer join, then - * lowest_nulling_outer_join references the lowest such JoinExpr node; - * otherwise it is NULL. This forces use of the PlaceHolderVar mechanism for - * references to non-nullable targetlist items, but only for references above - * that join. - * * If we are looking at a member subquery of an append relation, * containing_appendrel describes that relation; else it is NULL. * This forces use of the PlaceHolderVar mechanism for all non-Var targetlist @@ -798,15 +802,14 @@ pull_up_subqueries(PlannerInfo *root) * Notice also that we can't turn pullup_replace_vars loose on the whole * jointree, because it'd return a mutated copy of the tree; we have to * invoke it just on the quals, instead. This behavior is what makes it - * reasonable to pass lowest_outer_join and lowest_nulling_outer_join as - * pointers rather than some more-indirect way of identifying the lowest - * OJs. Likewise, we don't replace append_rel_list members but only their - * substructure, so the containing_appendrel reference is safe to use. + * reasonable to pass lowest_outer_join as a pointer rather than some + * more-indirect way of identifying the lowest OJ. Likewise, we don't + * replace append_rel_list members but only their substructure, so the + * containing_appendrel reference is safe to use. */ static Node * pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode, JoinExpr *lowest_outer_join, - JoinExpr *lowest_nulling_outer_join, AppendRelInfo *containing_appendrel) { /* Since this function recurses, it could be driven to stack overflow. */ @@ -833,7 +836,6 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode, is_safe_append_member(rte->subquery))) return pull_up_simple_subquery(root, jtnode, rte, lowest_outer_join, - lowest_nulling_outer_join, containing_appendrel); /* @@ -866,7 +868,6 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode, */ if (rte->rtekind == RTE_FUNCTION) return pull_up_constant_function(root, jtnode, rte, - lowest_nulling_outer_join, containing_appendrel); /* Otherwise, do nothing at this node. */ @@ -882,7 +883,6 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode, { lfirst(l) = pull_up_subqueries_recurse(root, lfirst(l), lowest_outer_join, - lowest_nulling_outer_join, NULL); } } @@ -897,11 +897,9 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode, case JOIN_INNER: j->larg = pull_up_subqueries_recurse(root, j->larg, lowest_outer_join, - lowest_nulling_outer_join, NULL); j->rarg = pull_up_subqueries_recurse(root, j->rarg, lowest_outer_join, - lowest_nulling_outer_join, NULL); break; case JOIN_LEFT: @@ -909,31 +907,25 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode, case JOIN_ANTI: j->larg = pull_up_subqueries_recurse(root, j->larg, j, - lowest_nulling_outer_join, NULL); j->rarg = pull_up_subqueries_recurse(root, j->rarg, - j, j, NULL); break; case JOIN_FULL: j->larg = pull_up_subqueries_recurse(root, j->larg, - j, j, NULL); j->rarg = pull_up_subqueries_recurse(root, j->rarg, - j, j, NULL); break; case JOIN_RIGHT: j->larg = pull_up_subqueries_recurse(root, j->larg, - j, j, NULL); j->rarg = pull_up_subqueries_recurse(root, j->rarg, j, - lowest_nulling_outer_join, NULL); break; default: @@ -963,7 +955,6 @@ pull_up_subqueries_recurse(PlannerInfo *root, Node *jtnode, static Node * pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, JoinExpr *lowest_outer_join, - JoinExpr *lowest_nulling_outer_join, AppendRelInfo *containing_appendrel) { Query *parse = root->parse; @@ -1110,31 +1101,25 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, * The subquery's targetlist items are now in the appropriate form to * insert into the top query, except that we may need to wrap them in * PlaceHolderVars. Set up required context data for pullup_replace_vars. + * (Note that we should include the subquery's inner joins in relids, + * since it may include join alias vars referencing them.) */ rvcontext.root = root; rvcontext.targetlist = subquery->targetList; rvcontext.target_rte = rte; if (rte->lateral) rvcontext.relids = get_relids_in_jointree((Node *) subquery->jointree, - true); + true, true); else /* won't need relids */ rvcontext.relids = NULL; rvcontext.outer_hasSubLinks = &parse->hasSubLinks; rvcontext.varno = varno; - /* these flags will be set below, if needed */ - rvcontext.need_phvs = false; + /* this flag will be set below, if needed */ rvcontext.wrap_non_vars = false; /* initialize cache array with indexes 0 .. length(tlist) */ rvcontext.rv_cache = palloc0((list_length(subquery->targetList) + 1) * sizeof(Node *)); - /* - * If we are under an outer join then non-nullable items and lateral - * references may have to be turned into PlaceHolderVars. - */ - if (lowest_nulling_outer_join != NULL) - rvcontext.need_phvs = true; - /* * If we are dealing with an appendrel member then anything that's not a * simple Var has to be turned into a PlaceHolderVar. We force this to @@ -1143,10 +1128,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, * expression actually available from the appendrel. */ if (containing_appendrel != NULL) - { - rvcontext.need_phvs = true; rvcontext.wrap_non_vars = true; - } /* * If the parent query uses grouping sets, we need a PlaceHolderVar for @@ -1158,10 +1140,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, * that pullup_replace_vars hasn't currently got.) */ if (parse->groupingSets) - { - rvcontext.need_phvs = true; rvcontext.wrap_non_vars = true; - } /* * Replace all of the top query's references to the subquery's outputs @@ -1169,7 +1148,6 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, * replace any of the jointree structure. */ perform_pullup_replace_vars(root, &rvcontext, - lowest_nulling_outer_join, containing_appendrel); /* @@ -1236,7 +1214,8 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, { Relids subrelids; - subrelids = get_relids_in_jointree((Node *) subquery->jointree, false); + subrelids = get_relids_in_jointree((Node *) subquery->jointree, + true, false); if (root->glob->lastPHId != 0) substitute_phv_relids((Node *) parse, varno, subrelids); fix_append_rel_relids(root, varno, subrelids); @@ -1432,7 +1411,7 @@ pull_up_union_leaf_queries(Node *setOp, PlannerInfo *root, int parentRTindex, rtr = makeNode(RangeTblRef); rtr->rtindex = childRTindex; (void) pull_up_subqueries_recurse(root, (Node *) rtr, - NULL, NULL, appinfo); + NULL, appinfo); } else if (IsA(setOp, SetOperationStmt)) { @@ -1569,7 +1548,7 @@ is_simple_subquery(PlannerInfo *root, Query *subquery, RangeTblEntry *rte, { restricted = true; safe_upper_varnos = get_relids_in_jointree((Node *) lowest_outer_join, - true); + true, true); } else { @@ -1681,7 +1660,6 @@ pull_up_simple_values(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte) rvcontext.relids = NULL; rvcontext.outer_hasSubLinks = &parse->hasSubLinks; rvcontext.varno = varno; - rvcontext.need_phvs = false; rvcontext.wrap_non_vars = false; /* initialize cache array with indexes 0 .. length(tlist) */ rvcontext.rv_cache = palloc0((list_length(tlist) + 1) * @@ -1693,7 +1671,7 @@ pull_up_simple_values(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte) * any of the jointree structure. We can assume there's no outer joins or * appendrels in the dummy Query that surrounds a VALUES RTE. */ - perform_pullup_replace_vars(root, &rvcontext, NULL, NULL); + perform_pullup_replace_vars(root, &rvcontext, NULL); /* * There should be no appendrels to fix, nor any outer joins and hence no @@ -1792,7 +1770,6 @@ is_simple_values(PlannerInfo *root, RangeTblEntry *rte) static Node * pull_up_constant_function(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte, - JoinExpr *lowest_nulling_outer_join, AppendRelInfo *containing_appendrel) { Query *parse = root->parse; @@ -1844,40 +1821,26 @@ pull_up_constant_function(PlannerInfo *root, Node *jtnode, rvcontext.outer_hasSubLinks = &parse->hasSubLinks; rvcontext.varno = ((RangeTblRef *) jtnode)->rtindex; - /* these flags will be set below, if needed */ - rvcontext.need_phvs = false; + /* this flag will be set below, if needed */ rvcontext.wrap_non_vars = false; /* initialize cache array with indexes 0 .. length(tlist) */ rvcontext.rv_cache = palloc0((list_length(rvcontext.targetlist) + 1) * sizeof(Node *)); - /* - * If we are under an outer join then non-nullable items and lateral - * references may have to be turned into PlaceHolderVars. - */ - if (lowest_nulling_outer_join != NULL) - rvcontext.need_phvs = true; - /* * If we are dealing with an appendrel member then anything that's not a * simple Var has to be turned into a PlaceHolderVar. (See comments in * pull_up_simple_subquery().) */ if (containing_appendrel != NULL) - { - rvcontext.need_phvs = true; rvcontext.wrap_non_vars = true; - } /* * If the parent query uses grouping sets, we need a PlaceHolderVar for * anything that's not a simple Var. */ if (parse->groupingSets) - { - rvcontext.need_phvs = true; rvcontext.wrap_non_vars = true; - } /* * Replace all of the top query's references to the RTE's output with @@ -1885,7 +1848,6 @@ pull_up_constant_function(PlannerInfo *root, Node *jtnode, * jointree structure. */ perform_pullup_replace_vars(root, &rvcontext, - lowest_nulling_outer_join, containing_appendrel); /* @@ -2110,13 +2072,11 @@ jointree_contains_lateral_outer_refs(PlannerInfo *root, Node *jtnode, * * Caller has already filled *rvcontext with data describing what to * substitute for Vars referencing the target subquery. In addition - * we need the identity of the lowest outer join that can null the - * target subquery, and its containing appendrel if any. + * we need the identity of the containing appendrel if any. */ static void perform_pullup_replace_vars(PlannerInfo *root, pullup_replace_vars_context *rvcontext, - JoinExpr *lowest_nulling_outer_join, AppendRelInfo *containing_appendrel) { Query *parse = root->parse; @@ -2126,18 +2086,18 @@ perform_pullup_replace_vars(PlannerInfo *root, * If we are considering an appendrel child subquery (that is, a UNION ALL * member query that we're pulling up), then the only part of the upper * query that could reference the child yet is the translated_vars list of - * the associated AppendRelInfo. Furthermore, we do not need to insert - * PHVs in the AppendRelInfo --- there isn't any outer join between. + * the associated AppendRelInfo. Furthermore, we do not want to force use + * of PHVs in the AppendRelInfo --- there isn't any outer join between. */ if (containing_appendrel) { - bool save_need_phvs = rvcontext->need_phvs; + bool save_wrap_non_vars = rvcontext->wrap_non_vars; - rvcontext->need_phvs = false; + rvcontext->wrap_non_vars = false; containing_appendrel->translated_vars = (List *) pullup_replace_vars((Node *) containing_appendrel->translated_vars, rvcontext); - rvcontext->need_phvs = save_need_phvs; + rvcontext->wrap_non_vars = save_wrap_non_vars; return; } @@ -2188,8 +2148,7 @@ perform_pullup_replace_vars(PlannerInfo *root, pullup_replace_vars((Node *) action->targetList, rvcontext); } } - replace_vars_in_jointree((Node *) parse->jointree, rvcontext, - lowest_nulling_outer_join); + replace_vars_in_jointree((Node *) parse->jointree, rvcontext); Assert(parse->setOperations == NULL); parse->havingQual = pullup_replace_vars(parse->havingQual, rvcontext); @@ -2206,12 +2165,6 @@ perform_pullup_replace_vars(PlannerInfo *root, /* * Replace references in the joinaliasvars lists of join RTEs. - * - * You might think that we could avoid using PHVs for alias vars of joins - * below lowest_nulling_outer_join, but that doesn't work because the - * alias vars could be referenced above that join; we need the PHVs to be - * present in such references after the alias vars get flattened. (It - * might be worth trying to be smarter here, someday.) */ foreach(lc, parse->rtable) { @@ -2228,14 +2181,10 @@ perform_pullup_replace_vars(PlannerInfo *root, * Helper routine for perform_pullup_replace_vars: do pullup_replace_vars on * every expression in the jointree, without changing the jointree structure * itself. Ugly, but there's no other way... - * - * If we are at or below lowest_nulling_outer_join, we can suppress use of - * PlaceHolderVars wrapped around the replacement expressions. */ static void replace_vars_in_jointree(Node *jtnode, - pullup_replace_vars_context *context, - JoinExpr *lowest_nulling_outer_join) + pullup_replace_vars_context *context) { if (jtnode == NULL) return; @@ -2245,10 +2194,8 @@ replace_vars_in_jointree(Node *jtnode, * If the RangeTblRef refers to a LATERAL subquery (that isn't the * same subquery we're pulling up), it might contain references to the * target subquery, which we must replace. We drive this from the - * jointree scan, rather than a scan of the rtable, for a couple of - * reasons: we can avoid processing no-longer-referenced RTEs, and we - * can use the appropriate setting of need_phvs depending on whether - * the RTE is above possibly-nulling outer joins or not. + * jointree scan, rather than a scan of the rtable, so that we can + * avoid processing no-longer-referenced RTEs. */ int varno = ((RangeTblRef *) jtnode)->rtindex; @@ -2305,42 +2252,30 @@ replace_vars_in_jointree(Node *jtnode, ListCell *l; foreach(l, f->fromlist) - replace_vars_in_jointree(lfirst(l), context, - lowest_nulling_outer_join); + replace_vars_in_jointree(lfirst(l), context); f->quals = pullup_replace_vars(f->quals, context); } else if (IsA(jtnode, JoinExpr)) { JoinExpr *j = (JoinExpr *) jtnode; - bool save_need_phvs = context->need_phvs; + bool save_wrap_non_vars = context->wrap_non_vars; - if (j == lowest_nulling_outer_join) - { - /* no more PHVs in or below this join */ - context->need_phvs = false; - lowest_nulling_outer_join = NULL; - } - replace_vars_in_jointree(j->larg, context, lowest_nulling_outer_join); - replace_vars_in_jointree(j->rarg, context, lowest_nulling_outer_join); + replace_vars_in_jointree(j->larg, context); + replace_vars_in_jointree(j->rarg, context); /* - * Use PHVs within the join quals of a full join, even when it's the - * lowest nulling outer join. Otherwise, we cannot identify which - * side of the join a pulled-up var-free expression came from, which - * can lead to failure to make a plan at all because none of the quals - * appear to be mergeable or hashable conditions. For this purpose we - * don't care about the state of wrap_non_vars, so leave it alone. + * Use PHVs within the join quals of a full join. Otherwise, we + * cannot identify which side of the join a pulled-up var-free + * expression came from, which can lead to failure to make a plan at + * all because none of the quals appear to be mergeable or hashable + * conditions. */ if (j->jointype == JOIN_FULL) - context->need_phvs = true; + context->wrap_non_vars = true; j->quals = pullup_replace_vars(j->quals, context); - /* - * We don't bother to update the colvars list, since it won't be used - * again ... - */ - context->need_phvs = save_need_phvs; + context->wrap_non_vars = save_wrap_non_vars; } else elog(ERROR, "unrecognized node type: %d", @@ -2369,8 +2304,18 @@ pullup_replace_vars_callback(Var *var, { pullup_replace_vars_context *rcon = (pullup_replace_vars_context *) context->callback_arg; int varattno = var->varattno; + bool need_phv; Node *newnode; + /* + * We need a PlaceHolderVar if the Var-to-be-replaced has nonempty + * varnullingrels (unless we find below that the replacement expression is + * a Var or PlaceHolderVar that we can just add the nullingrels to). We + * also need one if the caller has instructed us that all non-Var/PHV + * replacements need to be wrapped for identification purposes. + */ + need_phv = (var->varnullingrels != NULL) || rcon->wrap_non_vars; + /* * If PlaceHolderVars are needed, we cache the modified expressions in * rcon->rv_cache[]. This is not in hopes of any material speed gain @@ -2379,13 +2324,16 @@ pullup_replace_vars_callback(Var *var, * and possibly prevent optimizations that rely on recognizing different * references to the same subquery output as being equal(). So it's worth * a bit of extra effort to avoid it. + * + * The cached items have phlevelsup = 0 and phnullingrels = NULL; we'll + * copy them and adjust those values for this reference site below. */ - if (rcon->need_phvs && + if (need_phv && varattno >= InvalidAttrNumber && varattno <= list_length(rcon->targetlist) && rcon->rv_cache[varattno] != NULL) { - /* Just copy the entry and fall through to adjust its varlevelsup */ + /* Just copy the entry and fall through to adjust phlevelsup etc */ newnode = copyObject(rcon->rv_cache[varattno]); } else if (varattno == InvalidAttrNumber) @@ -2394,7 +2342,7 @@ pullup_replace_vars_callback(Var *var, RowExpr *rowexpr; List *colnames; List *fields; - bool save_need_phvs = rcon->need_phvs; + bool save_wrap_non_vars = rcon->wrap_non_vars; int save_sublevelsup = context->sublevels_up; /* @@ -2405,18 +2353,18 @@ pullup_replace_vars_callback(Var *var, * the RowExpr for use of the executor and ruleutils.c. * * In order to be able to cache the results, we always generate the - * expansion with varlevelsup = 0, and then adjust if needed. + * expansion with varlevelsup = 0, and then adjust below if needed. */ expandRTE(rcon->target_rte, var->varno, 0 /* not varlevelsup */ , var->location, (var->vartype != RECORDOID), &colnames, &fields); - /* Adjust the generated per-field Vars, but don't insert PHVs */ - rcon->need_phvs = false; + /* Expand the generated per-field Vars, but don't insert PHVs there */ + rcon->wrap_non_vars = false; context->sublevels_up = 0; /* to match the expandRTE output */ fields = (List *) replace_rte_variables_mutator((Node *) fields, context); - rcon->need_phvs = save_need_phvs; + rcon->wrap_non_vars = save_wrap_non_vars; context->sublevels_up = save_sublevelsup; rowexpr = makeNode(RowExpr); @@ -2434,14 +2382,13 @@ pullup_replace_vars_callback(Var *var, * expression to yield NULL, not ROW(NULL,NULL,...) when it is forced * to null by an outer join. */ - if (rcon->need_phvs) + if (need_phv) { - /* RowExpr is certainly not strict, so always need PHV */ newnode = (Node *) make_placeholder_expr(rcon->root, (Expr *) newnode, bms_make_singleton(rcon->varno)); - /* cache it with the PHV, and with varlevelsup still zero */ + /* cache it with the PHV, and with phlevelsup etc not set yet */ rcon->rv_cache[InvalidAttrNumber] = copyObject(newnode); } } @@ -2458,7 +2405,7 @@ pullup_replace_vars_callback(Var *var, newnode = (Node *) copyObject(tle->expr); /* Insert PlaceHolderVar if needed */ - if (rcon->need_phvs) + if (need_phv) { bool wrap; @@ -2484,69 +2431,61 @@ pullup_replace_vars_callback(Var *var, /* No need to wrap a PlaceHolderVar with another one, either */ wrap = false; } - else if (rcon->wrap_non_vars) - { - /* Wrap all non-Vars in a PlaceHolderVar */ - wrap = true; - } else { /* - * If it contains a Var of the subquery being pulled up, and - * does not contain any non-strict constructs, then it's - * certainly nullable so we don't need to insert a - * PlaceHolderVar. - * - * This analysis could be tighter: in particular, a non-strict - * construct hidden within a lower-level PlaceHolderVar is not - * reason to add another PHV. But for now it doesn't seem - * worth the code to be more exact. - * - * Note: in future maybe we should insert a PlaceHolderVar - * anyway, if the tlist item is expensive to evaluate? - * - * For a LATERAL subquery, we have to check the actual var - * membership of the node, but if it's non-lateral then any - * level-zero var must belong to the subquery. + * Must wrap, either because we need a place to insert + * varnullingrels or because caller told us to wrap + * everything. */ - if ((rcon->target_rte->lateral ? - bms_overlap(pull_varnos(rcon->root, (Node *) newnode), - rcon->relids) : - contain_vars_of_level((Node *) newnode, 0)) && - !contain_nonstrict_functions((Node *) newnode)) - { - /* No wrap needed */ - wrap = false; - } - else - { - /* Else wrap it in a PlaceHolderVar */ - wrap = true; - } + wrap = true; } if (wrap) + { newnode = (Node *) make_placeholder_expr(rcon->root, (Expr *) newnode, bms_make_singleton(rcon->varno)); - /* - * Cache it if possible (ie, if the attno is in range, which it - * probably always should be). We can cache the value even if we - * decided we didn't need a PHV, since this result will be - * suitable for any request that has need_phvs. - */ - if (varattno > InvalidAttrNumber && - varattno <= list_length(rcon->targetlist)) - rcon->rv_cache[varattno] = copyObject(newnode); + /* + * Cache it if possible (ie, if the attno is in range, which + * it probably always should be). + */ + if (varattno > InvalidAttrNumber && + varattno <= list_length(rcon->targetlist)) + rcon->rv_cache[varattno] = copyObject(newnode); + } } } - /* Must adjust varlevelsup if tlist item is from higher query */ + /* Must adjust varlevelsup if replaced Var is within a subquery */ if (var->varlevelsup > 0) IncrementVarSublevelsUp(newnode, var->varlevelsup, 0); + /* Propagate any varnullingrels into the replacement Var or PHV */ + if (var->varnullingrels != NULL) + { + if (IsA(newnode, Var)) + { + Var *newvar = (Var *) newnode; + + Assert(newvar->varlevelsup == var->varlevelsup); + newvar->varnullingrels = bms_add_members(newvar->varnullingrels, + var->varnullingrels); + } + else if (IsA(newnode, PlaceHolderVar)) + { + PlaceHolderVar *newphv = (PlaceHolderVar *) newnode; + + Assert(newphv->phlevelsup == var->varlevelsup); + newphv->phnullingrels = bms_add_members(newphv->phnullingrels, + var->varnullingrels); + } + else + elog(ERROR, "failed to wrap a non-Var"); + } + return newnode; } @@ -2705,7 +2644,9 @@ flatten_simple_union_all(PlannerInfo *root) void reduce_outer_joins(PlannerInfo *root) { - reduce_outer_joins_state *state; + reduce_outer_joins_pass1_state *state1; + reduce_outer_joins_pass2_state state2; + ListCell *lc; /* * To avoid doing strictness checks on more quals than necessary, we want @@ -2716,14 +2657,56 @@ reduce_outer_joins(PlannerInfo *root) * join(s) below each side of each join clause. The second pass examines * qual clauses and changes join types as it descends the tree. */ - state = reduce_outer_joins_pass1((Node *) root->parse->jointree); + state1 = reduce_outer_joins_pass1((Node *) root->parse->jointree); /* planner.c shouldn't have called me if no outer joins */ - if (state == NULL || !state->contains_outer) + if (state1 == NULL || !state1->contains_outer) elog(ERROR, "so where are the outer joins?"); + state2.inner_reduced = NULL; + state2.partial_reduced = NIL; + reduce_outer_joins_pass2((Node *) root->parse->jointree, - state, root, NULL, NIL); + state1, &state2, + root, NULL, NIL); + + /* + * If we successfully reduced the strength of any outer joins, we must + * remove references to those joins as nulling rels. This is handled as + * an additional pass, for simplicity and because we can handle all + * fully-reduced joins in a single pass over the parse tree. + */ + if (!bms_is_empty(state2.inner_reduced)) + { + root->parse = (Query *) + remove_nulling_relids((Node *) root->parse, + state2.inner_reduced, + NULL); + /* There could be references in the append_rel_list, too */ + root->append_rel_list = (List *) + remove_nulling_relids((Node *) root->append_rel_list, + state2.inner_reduced, + NULL); + } + + /* + * Partially-reduced full joins have to be done one at a time, since + * they'll each need a different setting of except_relids. + */ + foreach(lc, state2.partial_reduced) + { + reduce_outer_joins_partial_state *statep = lfirst(lc); + Relids full_join_relids = bms_make_singleton(statep->full_join_rti); + + root->parse = (Query *) + remove_nulling_relids((Node *) root->parse, + full_join_relids, + statep->unreduced_side); + root->append_rel_list = (List *) + remove_nulling_relids((Node *) root->append_rel_list, + full_join_relids, + statep->unreduced_side); + } } /* @@ -2731,13 +2714,13 @@ reduce_outer_joins(PlannerInfo *root) * * Returns a state node describing the given jointree node. */ -static reduce_outer_joins_state * +static reduce_outer_joins_pass1_state * reduce_outer_joins_pass1(Node *jtnode) { - reduce_outer_joins_state *result; + reduce_outer_joins_pass1_state *result; - result = (reduce_outer_joins_state *) - palloc(sizeof(reduce_outer_joins_state)); + result = (reduce_outer_joins_pass1_state *) + palloc(sizeof(reduce_outer_joins_pass1_state)); result->relids = NULL; result->contains_outer = false; result->sub_states = NIL; @@ -2757,7 +2740,7 @@ reduce_outer_joins_pass1(Node *jtnode) foreach(l, f->fromlist) { - reduce_outer_joins_state *sub_state; + reduce_outer_joins_pass1_state *sub_state; sub_state = reduce_outer_joins_pass1(lfirst(l)); result->relids = bms_add_members(result->relids, @@ -2769,7 +2752,7 @@ reduce_outer_joins_pass1(Node *jtnode) else if (IsA(jtnode, JoinExpr)) { JoinExpr *j = (JoinExpr *) jtnode; - reduce_outer_joins_state *sub_state; + reduce_outer_joins_pass1_state *sub_state; /* join's own RT index is not wanted in result->relids */ if (IS_OUTER_JOIN(j->jointype)) @@ -2797,14 +2780,22 @@ reduce_outer_joins_pass1(Node *jtnode) * reduce_outer_joins_pass2 - phase 2 processing * * jtnode: current jointree node - * state: state data collected by phase 1 for this node + * state1: state data collected by phase 1 for this node + * state2: where to accumulate info about successfully-reduced joins * root: toplevel planner state * nonnullable_rels: set of base relids forced non-null by upper quals * forced_null_vars: multibitmapset of Vars forced null by upper quals + * + * Returns info in state2 about outer joins that were successfully simplified. + * Joins that were fully reduced to inner joins are all added to + * state2->inner_reduced. If a full join is reduced to a left join, + * it needs its own entry in state2->partial_reduced, since that will + * require custom processing to remove only the correct nullingrel markers. */ static void reduce_outer_joins_pass2(Node *jtnode, - reduce_outer_joins_state *state, + reduce_outer_joins_pass1_state *state1, + reduce_outer_joins_pass2_state *state2, PlannerInfo *root, Relids nonnullable_rels, List *forced_null_vars) @@ -2833,13 +2824,14 @@ reduce_outer_joins_pass2(Node *jtnode, pass_forced_null_vars = mbms_add_members(pass_forced_null_vars, forced_null_vars); /* And recurse --- but only into interesting subtrees */ - Assert(list_length(f->fromlist) == list_length(state->sub_states)); - forboth(l, f->fromlist, s, state->sub_states) + Assert(list_length(f->fromlist) == list_length(state1->sub_states)); + forboth(l, f->fromlist, s, state1->sub_states) { - reduce_outer_joins_state *sub_state = lfirst(s); + reduce_outer_joins_pass1_state *sub_state = lfirst(s); if (sub_state->contains_outer) - reduce_outer_joins_pass2(lfirst(l), sub_state, root, + reduce_outer_joins_pass2(lfirst(l), sub_state, + state2, root, pass_nonnullable_rels, pass_forced_null_vars); } @@ -2851,8 +2843,8 @@ reduce_outer_joins_pass2(Node *jtnode, JoinExpr *j = (JoinExpr *) jtnode; int rtindex = j->rtindex; JoinType jointype = j->jointype; - reduce_outer_joins_state *left_state = linitial(state->sub_states); - reduce_outer_joins_state *right_state = lsecond(state->sub_states); + reduce_outer_joins_pass1_state *left_state = linitial(state1->sub_states); + reduce_outer_joins_pass1_state *right_state = lsecond(state1->sub_states); /* Can we simplify this join? */ switch (jointype) @@ -2873,12 +2865,22 @@ reduce_outer_joins_pass2(Node *jtnode, if (bms_overlap(nonnullable_rels, right_state->relids)) jointype = JOIN_INNER; else + { jointype = JOIN_LEFT; + /* Also report partial reduction in state2 */ + report_reduced_full_join(state2, rtindex, + right_state->relids); + } } else { if (bms_overlap(nonnullable_rels, right_state->relids)) + { jointype = JOIN_RIGHT; + /* Also report partial reduction in state2 */ + report_reduced_full_join(state2, rtindex, + left_state->relids); + } } break; case JOIN_SEMI: @@ -2911,8 +2913,8 @@ reduce_outer_joins_pass2(Node *jtnode, j->larg = j->rarg; j->rarg = tmparg; jointype = JOIN_LEFT; - right_state = linitial(state->sub_states); - left_state = lsecond(state->sub_states); + right_state = linitial(state1->sub_states); + left_state = lsecond(state1->sub_states); } /* @@ -2943,7 +2945,10 @@ reduce_outer_joins_pass2(Node *jtnode, jointype = JOIN_ANTI; } - /* Apply the jointype change, if any, to both jointree node and RTE */ + /* + * Apply the jointype change, if any, to both jointree node and RTE. + * Also, if we changed an RTE to INNER, add its RTI to inner_reduced. + */ if (rtindex && jointype != j->jointype) { RangeTblEntry *rte = rt_fetch(rtindex, root->parse->rtable); @@ -2951,6 +2956,9 @@ reduce_outer_joins_pass2(Node *jtnode, Assert(rte->rtekind == RTE_JOIN); Assert(rte->jointype == j->jointype); rte->jointype = jointype; + if (jointype == JOIN_INNER) + state2->inner_reduced = bms_add_member(state2->inner_reduced, + rtindex); } j->jointype = jointype; @@ -3023,7 +3031,8 @@ reduce_outer_joins_pass2(Node *jtnode, pass_nonnullable_rels = NULL; pass_forced_null_vars = NIL; } - reduce_outer_joins_pass2(j->larg, left_state, root, + reduce_outer_joins_pass2(j->larg, left_state, + state2, root, pass_nonnullable_rels, pass_forced_null_vars); } @@ -3042,7 +3051,8 @@ reduce_outer_joins_pass2(Node *jtnode, pass_nonnullable_rels = NULL; pass_forced_null_vars = NIL; } - reduce_outer_joins_pass2(j->rarg, right_state, root, + reduce_outer_joins_pass2(j->rarg, right_state, + state2, root, pass_nonnullable_rels, pass_forced_null_vars); } @@ -3054,6 +3064,19 @@ reduce_outer_joins_pass2(Node *jtnode, (int) nodeTag(jtnode)); } +/* Helper for reduce_outer_joins_pass2 */ +static void +report_reduced_full_join(reduce_outer_joins_pass2_state *state2, + int rtindex, Relids relids) +{ + reduce_outer_joins_partial_state *statep; + + statep = palloc(sizeof(reduce_outer_joins_partial_state)); + statep->full_join_rti = rtindex; + statep->unreduced_side = relids; + state2->partial_reduced = lappend(state2->partial_reduced, statep); +} + /* * remove_useless_result_rtes @@ -3095,16 +3118,41 @@ reduce_outer_joins_pass2(Node *jtnode, void remove_useless_result_rtes(PlannerInfo *root) { + Relids dropped_outer_joins = NULL; ListCell *cell; /* Top level of jointree must always be a FromExpr */ Assert(IsA(root->parse->jointree, FromExpr)); /* Recurse ... */ root->parse->jointree = (FromExpr *) - remove_useless_results_recurse(root, (Node *) root->parse->jointree); + remove_useless_results_recurse(root, + (Node *) root->parse->jointree, + &dropped_outer_joins); /* We should still have a FromExpr */ Assert(IsA(root->parse->jointree, FromExpr)); + /* + * If we removed any outer-join nodes from the jointree, run around and + * remove references to those joins as nulling rels. (There could be such + * references in PHVs that we pulled up out of the original subquery that + * the RESULT rel replaced. This is kosher on the grounds that we now + * know that such an outer join wouldn't really have nulled anything.) We + * don't do this during the main recursion, for simplicity and because we + * can handle all such joins in a single pass over the parse tree. + */ + if (!bms_is_empty(dropped_outer_joins)) + { + root->parse = (Query *) + remove_nulling_relids((Node *) root->parse, + dropped_outer_joins, + NULL); + /* There could be references in the append_rel_list, too */ + root->append_rel_list = (List *) + remove_nulling_relids((Node *) root->append_rel_list, + dropped_outer_joins, + NULL); + } + /* * Remove any PlanRowMark referencing an RTE_RESULT RTE. We obviously * must do that for any RTE_RESULT that we just removed. But one for a @@ -3130,9 +3178,12 @@ remove_useless_result_rtes(PlannerInfo *root) * Recursive guts of remove_useless_result_rtes. * * 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. */ static Node * -remove_useless_results_recurse(PlannerInfo *root, Node *jtnode) +remove_useless_results_recurse(PlannerInfo *root, Node *jtnode, + Relids *dropped_outer_joins) { Assert(jtnode != NULL); if (IsA(jtnode, RangeTblRef)) @@ -3160,7 +3211,8 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode) int varno; /* Recursively transform child ... */ - child = remove_useless_results_recurse(root, child); + child = remove_useless_results_recurse(root, child, + dropped_outer_joins); /* ... and stick it back into the tree */ lfirst(cell) = child; @@ -3209,8 +3261,10 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode) int varno; /* First, recurse */ - j->larg = remove_useless_results_recurse(root, j->larg); - j->rarg = remove_useless_results_recurse(root, j->rarg); + j->larg = remove_useless_results_recurse(root, j->larg, + dropped_outer_joins); + j->rarg = remove_useless_results_recurse(root, j->rarg, + dropped_outer_joins); /* Apply join-type-specific optimization rules */ switch (j->jointype) @@ -3278,6 +3332,8 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode) !find_dependent_phvs(root, varno))) { remove_result_refs(root, varno, j->larg); + *dropped_outer_joins = bms_add_member(*dropped_outer_joins, + j->rtindex); jtnode = j->larg; } break; @@ -3297,9 +3353,13 @@ remove_useless_results_recurse(PlannerInfo *root, Node *jtnode) * it'd be OK to just remove the PHV wrapping. We don't have * infrastructure for that, but remove_result_refs() will * relabel them as to be evaluated at the LHS, which is fine. + * + * Also, we don't need to worry about removing traces of the + * join's rtindex, since it hasn't got one. */ if ((varno = get_result_relid(root, j->rarg)) != 0) { + Assert(j->rtindex == 0); remove_result_refs(root, varno, j->larg); if (j->quals) jtnode = (Node *) @@ -3369,7 +3429,7 @@ remove_result_refs(PlannerInfo *root, int varno, Node *newjtloc) { Relids subrelids; - subrelids = get_relids_in_jointree(newjtloc, false); + subrelids = get_relids_in_jointree(newjtloc, true, false); Assert(!bms_is_empty(subrelids)); substitute_phv_relids((Node *) root->parse, varno, subrelids); fix_append_rel_relids(root, varno, subrelids); @@ -3426,9 +3486,8 @@ find_dependent_phvs_walker(Node *node, context->sublevels_up--; return result; } - /* Shouldn't need to handle planner auxiliary nodes here */ + /* Shouldn't need to handle most planner auxiliary nodes here */ Assert(!IsA(node, SpecialJoinInfo)); - Assert(!IsA(node, AppendRelInfo)); Assert(!IsA(node, PlaceHolderInfo)); Assert(!IsA(node, MinMaxAggInfo)); @@ -3448,10 +3507,17 @@ find_dependent_phvs(PlannerInfo *root, int varno) context.relids = bms_make_singleton(varno); context.sublevels_up = 0; - return query_tree_walker(root->parse, - find_dependent_phvs_walker, - (void *) &context, - 0); + if (query_tree_walker(root->parse, + find_dependent_phvs_walker, + (void *) &context, + 0)) + return true; + /* The append_rel_list could be populated already, so check it too */ + if (expression_tree_walker((Node *) root->append_rel_list, + find_dependent_phvs_walker, + (void *) &context)) + return true; + return false; } static bool @@ -3481,7 +3547,7 @@ find_dependent_phvs_in_jointree(PlannerInfo *root, Node *node, int varno) * are not marked LATERAL, though, since they couldn't possibly contain * any cross-references to other RTEs. */ - subrelids = get_relids_in_jointree(node, false); + subrelids = get_relids_in_jointree(node, false, false); relid = -1; while ((relid = bms_next_member(subrelids, relid)) >= 0) { @@ -3626,11 +3692,17 @@ fix_append_rel_relids(PlannerInfo *root, int varno, Relids subrelids) /* * get_relids_in_jointree: get set of RT indexes present in a jointree * - * If include_joins is true, join RT indexes are included; if false, - * only base rels are included. + * Base-relation relids are always included in the result. + * If include_outer_joins is true, outer-join RT indexes are included. + * If include_inner_joins is true, inner-join RT indexes are included. + * + * Note that for most purposes in the planner, outer joins are included + * in standard relid sets. Setting include_inner_joins true is only + * appropriate for special purposes during subquery flattening. */ Relids -get_relids_in_jointree(Node *jtnode, bool include_joins) +get_relids_in_jointree(Node *jtnode, bool include_outer_joins, + bool include_inner_joins) { Relids result = NULL; @@ -3651,18 +3723,34 @@ get_relids_in_jointree(Node *jtnode, bool include_joins) { result = bms_join(result, get_relids_in_jointree(lfirst(l), - include_joins)); + include_outer_joins, + include_inner_joins)); } } else if (IsA(jtnode, JoinExpr)) { JoinExpr *j = (JoinExpr *) jtnode; - result = get_relids_in_jointree(j->larg, include_joins); + result = get_relids_in_jointree(j->larg, + include_outer_joins, + include_inner_joins); result = bms_join(result, - get_relids_in_jointree(j->rarg, include_joins)); - if (include_joins && j->rtindex) - result = bms_add_member(result, j->rtindex); + get_relids_in_jointree(j->rarg, + include_outer_joins, + include_inner_joins)); + if (j->rtindex) + { + if (j->jointype == JOIN_INNER) + { + if (include_inner_joins) + result = bms_add_member(result, j->rtindex); + } + else + { + if (include_outer_joins) + result = bms_add_member(result, j->rtindex); + } + } } else elog(ERROR, "unrecognized node type: %d", @@ -3671,7 +3759,7 @@ get_relids_in_jointree(Node *jtnode, bool include_joins) } /* - * get_relids_for_join: get set of base RT indexes making up a join + * get_relids_for_join: get set of base+OJ RT indexes making up a join */ Relids get_relids_for_join(Query *query, int joinrelid) @@ -3682,7 +3770,7 @@ get_relids_for_join(Query *query, int joinrelid) joinrelid); if (!jtnode) elog(ERROR, "could not find join node %d", joinrelid); - return get_relids_in_jointree(jtnode, false); + return get_relids_in_jointree(jtnode, true, false); } /* diff --git a/src/backend/optimizer/util/appendinfo.c b/src/backend/optimizer/util/appendinfo.c index f6fc62aa5d..11c6bbaba6 100644 --- a/src/backend/optimizer/util/appendinfo.c +++ b/src/backend/optimizer/util/appendinfo.c @@ -228,6 +228,14 @@ adjust_appendrel_attrs_mutator(Node *node, if (var->varlevelsup != 0) return (Node *) var; /* no changes needed */ + /* + * You might think we need to adjust var->varnullingrels, but that + * shouldn't need any changes. It will contain outer-join relids, + * while the transformation we are making affects only baserels. + * Below, we just propagate var->varnullingrels into the translated + * Var. (XXX what to do if translation is not a Var??) + */ + for (cnt = 0; cnt < nappinfos; cnt++) { if (var->varno == appinfos[cnt]->parent_relid) @@ -255,6 +263,8 @@ adjust_appendrel_attrs_mutator(Node *node, if (newnode == NULL) elog(ERROR, "attribute %d of relation \"%s\" does not exist", var->varattno, get_rel_name(appinfo->parent_reloid)); + if (IsA(newnode, Var)) + ((Var *) newnode)->varnullingrels = var->varnullingrels; return newnode; } else if (var->varattno == 0) @@ -348,6 +358,8 @@ adjust_appendrel_attrs_mutator(Node *node, var = copyObject(ridinfo->rowidvar); /* ... but use the correct relid */ var->varno = leaf_relid; + /* identity vars shouldn't have nulling rels */ + Assert(var->varnullingrels == NULL); /* varnosyn in the RowIdentityVarInfo is probably wrong */ var->varnosyn = 0; var->varattnosyn = 0; @@ -392,8 +404,11 @@ adjust_appendrel_attrs_mutator(Node *node, (void *) context); /* now fix PlaceHolderVar's relid sets */ if (phv->phlevelsup == 0) - phv->phrels = adjust_child_relids(phv->phrels, context->nappinfos, - context->appinfos); + { + phv->phrels = adjust_child_relids(phv->phrels, + nappinfos, appinfos); + /* as above, we needn't touch phnullingrels */ + } return (Node *) phv; } /* Shouldn't need to handle planner auxiliary nodes here */ @@ -688,7 +703,11 @@ get_translated_update_targetlist(PlannerInfo *root, Index relid, /* * find_appinfos_by_relids - * Find AppendRelInfo structures for all relations specified by relids. + * Find AppendRelInfo structures for base relations listed in relids. + * + * The relids argument is typically a join relation's relids, which can + * include outer-join RT indexes in addition to baserels. We silently + * ignore the outer joins. * * The AppendRelInfos are returned in an array, which can be pfree'd by the * caller. *nappinfos is set to the number of entries in the array. @@ -700,8 +719,9 @@ find_appinfos_by_relids(PlannerInfo *root, Relids relids, int *nappinfos) int cnt = 0; int i; - *nappinfos = bms_num_members(relids); - appinfos = (AppendRelInfo **) palloc(sizeof(AppendRelInfo *) * *nappinfos); + /* Allocate an array that's certainly big enough */ + appinfos = (AppendRelInfo **) + palloc(sizeof(AppendRelInfo *) * bms_num_members(relids)); i = -1; while ((i = bms_next_member(relids, i)) >= 0) @@ -709,10 +729,17 @@ find_appinfos_by_relids(PlannerInfo *root, Relids relids, int *nappinfos) AppendRelInfo *appinfo = root->append_rel_array[i]; if (!appinfo) + { + /* Probably i is an OJ index, but let's check */ + if (find_base_rel_ignore_join(root, i) == NULL) + continue; + /* It's a base rel, but we lack an append_rel_array entry */ elog(ERROR, "child rel %d not found in append_rel_array", i); + } appinfos[cnt++] = appinfo; } + *nappinfos = cnt; return appinfos; } @@ -754,6 +781,7 @@ add_row_identity_var(PlannerInfo *root, Var *orig_var, Assert(IsA(orig_var, Var)); Assert(orig_var->varno == rtindex); Assert(orig_var->varlevelsup == 0); + Assert(orig_var->varnullingrels == NULL); /* * If we're doing non-inherited UPDATE/DELETE/MERGE, there's little need diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index bffc8112aa..5976862c10 100644 --- a/src/backend/optimizer/util/clauses.c +++ b/src/backend/optimizer/util/clauses.c @@ -2004,14 +2004,16 @@ is_pseudo_constant_clause_relids(Node *clause, Relids relids) * NumRelids * (formerly clause_relids) * - * Returns the number of different relations referenced in 'clause'. + * Returns the number of different base relations referenced in 'clause'. */ int NumRelids(PlannerInfo *root, Node *clause) { + int result; Relids varnos = pull_varnos(root, clause); - int result = bms_num_members(varnos); + varnos = bms_del_members(varnos, root->outer_join_rels); + result = bms_num_members(varnos); bms_free(varnos); return result; } diff --git a/src/backend/optimizer/util/joininfo.c b/src/backend/optimizer/util/joininfo.c index d4cffdb198..afd243f5d8 100644 --- a/src/backend/optimizer/util/joininfo.c +++ b/src/backend/optimizer/util/joininfo.c @@ -88,8 +88,8 @@ have_relevant_joinclause(PlannerInfo *root, * not depend on context). * * 'restrictinfo' describes the join clause - * 'join_relids' is the list of relations participating in the join clause - * (there must be more than one) + * 'join_relids' is the set of relations participating in the join clause + * (some of these could be outer joins) */ void add_join_clause_to_rels(PlannerInfo *root, @@ -101,8 +101,11 @@ add_join_clause_to_rels(PlannerInfo *root, cur_relid = -1; while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0) { - RelOptInfo *rel = find_base_rel(root, cur_relid); + RelOptInfo *rel = find_base_rel_ignore_join(root, cur_relid); + /* We only need to add the clause to baserels */ + if (rel == NULL) + continue; rel->joininfo = lappend(rel->joininfo, restrictinfo); } } @@ -115,8 +118,8 @@ add_join_clause_to_rels(PlannerInfo *root, * discover that a relation need not be joined at all. * * 'restrictinfo' describes the join clause - * 'join_relids' is the list of relations participating in the join clause - * (there must be more than one) + * 'join_relids' is the set of relations participating in the join clause + * (some of these could be outer joins) */ void remove_join_clause_from_rels(PlannerInfo *root, @@ -128,7 +131,11 @@ remove_join_clause_from_rels(PlannerInfo *root, cur_relid = -1; while ((cur_relid = bms_next_member(join_relids, cur_relid)) >= 0) { - RelOptInfo *rel = find_base_rel(root, cur_relid); + RelOptInfo *rel = find_base_rel_ignore_join(root, cur_relid); + + /* We would only have added the clause to baserels */ + if (rel == NULL) + continue; /* * Remove the restrictinfo from the list. Pointer comparison is diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c index b1363df065..e96ef176ad 100644 --- a/src/backend/optimizer/util/orclauses.c +++ b/src/backend/optimizer/util/orclauses.c @@ -338,6 +338,10 @@ consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel, sjinfo.syn_lefthand = sjinfo.min_lefthand; sjinfo.syn_righthand = sjinfo.min_righthand; sjinfo.jointype = JOIN_INNER; + sjinfo.ojrelid = 0; + sjinfo.commute_above_l = NULL; + sjinfo.commute_above_r = NULL; + sjinfo.commute_below = NULL; /* we don't bother trying to make the remaining fields valid */ sjinfo.lhs_strict = false; sjinfo.delay_upper_joins = false; diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 55deee555a..70a343b108 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -1307,7 +1307,7 @@ create_append_path(PlannerInfo *root, * Apply query-wide LIMIT if known and path is for sole base relation. * (Handling this at this low level is a bit klugy.) */ - if (root != NULL && bms_equal(rel->relids, root->all_baserels)) + if (root != NULL && bms_equal(rel->relids, root->all_query_rels)) pathnode->limit_tuples = root->limit_tuples; else pathnode->limit_tuples = -1.0; @@ -1436,7 +1436,7 @@ create_merge_append_path(PlannerInfo *root, * Apply query-wide LIMIT if known and path is for sole base relation. * (Handling this at this low level is a bit klugy.) */ - if (bms_equal(rel->relids, root->all_baserels)) + if (bms_equal(rel->relids, root->all_query_rels)) pathnode->limit_tuples = root->limit_tuples; else pathnode->limit_tuples = -1.0; diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c index c55027377f..b9cc983df7 100644 --- a/src/backend/optimizer/util/placeholder.c +++ b/src/backend/optimizer/util/placeholder.c @@ -23,17 +23,32 @@ #include "optimizer/planmain.h" #include "utils/lsyscache.h" + +typedef struct contain_placeholder_references_context +{ + int relid; + int sublevels_up; +} contain_placeholder_references_context; + /* Local functions */ static void find_placeholders_recurse(PlannerInfo *root, Node *jtnode); static void find_placeholders_in_expr(PlannerInfo *root, Node *expr); +static bool contain_placeholder_references_walker(Node *node, + contain_placeholder_references_context *context); /* * make_placeholder_expr * Make a PlaceHolderVar for the given expression. * - * phrels is the syntactic location (as a set of baserels) to attribute + * phrels is the syntactic location (as a set of relids) to attribute * to the expression. + * + * The caller is responsible for adjusting phlevelsup and phnullingrels + * as needed. Because we do not know here which query level the PHV + * will be associated with, it's important that this function touches + * only root->glob; messing with other parts of PlannerInfo would be + * likely to do the wrong thing. */ PlaceHolderVar * make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels) @@ -42,8 +57,9 @@ make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels) phv->phexpr = expr; phv->phrels = phrels; + phv->phnullingrels = NULL; /* caller may change this later */ phv->phid = ++(root->glob->lastPHId); - phv->phlevelsup = 0; + phv->phlevelsup = 0; /* caller may change this later */ return phv; } @@ -92,6 +108,15 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv) phinfo->phid = phv->phid; phinfo->ph_var = copyObject(phv); + /* + * By convention, phinfo->ph_var->phnullingrels is always empty, since the + * PlaceHolderInfo represents the initially-calculated state of the + * PlaceHolderVar. PlaceHolderVars appearing in the query tree might have + * varying values of phnullingrels, reflecting outer joins applied above + * the calculation level. + */ + phinfo->ph_var->phnullingrels = NULL; + /* * Any referenced rels that are outside the PHV's syntactic scope are * LATERAL references, which should be included in ph_lateral but not in @@ -339,6 +364,8 @@ update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo) sjinfo->min_lefthand); eval_at = bms_add_members(eval_at, sjinfo->min_righthand); + if (sjinfo->ojrelid) + eval_at = bms_add_member(eval_at, sjinfo->ojrelid); /* we'll need another iteration */ found_some = true; } @@ -413,6 +440,14 @@ add_placeholders_to_base_rels(PlannerInfo *root) { RelOptInfo *rel = find_base_rel(root, varno); + /* + * As in add_vars_to_targetlist(), a value computed at scan level + * has not yet been nulled by any outer join, so its phnullingrels + * should be empty. + */ + Assert(phinfo->ph_var->phnullingrels == NULL); + + /* Copying the PHV might be unnecessary here, but be safe */ rel->reltarget->exprs = lappend(rel->reltarget->exprs, copyObject(phinfo->ph_var)); /* reltarget's cost and width fields will be updated later */ @@ -435,7 +470,8 @@ add_placeholders_to_base_rels(PlannerInfo *root) */ void add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, - RelOptInfo *outer_rel, RelOptInfo *inner_rel) + RelOptInfo *outer_rel, RelOptInfo *inner_rel, + SpecialJoinInfo *sjinfo) { Relids relids = joinrel->relids; ListCell *lc; @@ -466,9 +502,17 @@ add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, if (!bms_is_subset(phinfo->ph_eval_at, outer_rel->relids) && !bms_is_subset(phinfo->ph_eval_at, inner_rel->relids)) { - PlaceHolderVar *phv = phinfo->ph_var; + /* Copying might be unnecessary here, but be safe */ + PlaceHolderVar *phv = copyObject(phinfo->ph_var); QualCost cost; + /* + * It'll start out not nulled by anything. Joins above + * this one might add to its phnullingrels later, in much + * the same way as for Vars. + */ + Assert(phv->phnullingrels == NULL); + joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, phv); cost_qual_eval_node(&cost, (Node *) phv->phexpr, root); @@ -499,3 +543,74 @@ add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, } } } + +/* + * contain_placeholder_references_to + * Detect whether any PlaceHolderVars in the given clause contain + * references to the given relid (typically an OJ relid). + * + * "Contain" means that there's a use of the relid inside the PHV's + * contained expression, so that changing the nullability status of + * the rel might change what the PHV computes. + * + * The code here to cope with upper-level PHVs is likely dead, but keep it + * anyway just in case. + */ +bool +contain_placeholder_references_to(PlannerInfo *root, Node *clause, + int relid) +{ + contain_placeholder_references_context context; + + /* We can answer quickly in the common case that there's no PHVs at all */ + if (root->glob->lastPHId == 0) + return false; + /* Else run the recursive search */ + context.relid = relid; + context.sublevels_up = 0; + return contain_placeholder_references_walker(clause, &context); +} + +static bool +contain_placeholder_references_walker(Node *node, + contain_placeholder_references_context *context) +{ + if (node == NULL) + return false; + if (IsA(node, PlaceHolderVar)) + { + PlaceHolderVar *phv = (PlaceHolderVar *) node; + + /* We should just look through PHVs of other query levels */ + if (phv->phlevelsup == context->sublevels_up) + { + /* If phrels matches, we found what we came for */ + if (bms_is_member(context->relid, phv->phrels)) + return true; + + /* + * We should not examine phnullingrels: what we are looking for is + * references in the contained expression, not OJs that might null + * the result afterwards. Also, we don't need to recurse into the + * contained expression, because phrels should adequately + * summarize what's in there. So we're done here. + */ + return false; + } + } + else if (IsA(node, Query)) + { + /* Recurse into RTE subquery or not-yet-planned sublink subquery */ + bool result; + + context->sublevels_up++; + result = query_tree_walker((Query *) node, + contain_placeholder_references_walker, + context, + 0); + context->sublevels_up--; + return result; + } + return expression_tree_walker(node, contain_placeholder_references_walker, + context); +} diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 7085cf3c41..acee3e2559 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -28,6 +28,7 @@ #include "optimizer/plancat.h" #include "optimizer/restrictinfo.h" #include "optimizer/tlist.h" +#include "rewrite/rewriteManip.h" #include "parser/parse_relation.h" #include "utils/hsearch.h" #include "utils/lsyscache.h" @@ -40,7 +41,9 @@ typedef struct JoinHashEntry } JoinHashEntry; static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, - RelOptInfo *input_rel); + RelOptInfo *input_rel, + SpecialJoinInfo *sjinfo, + bool can_null); static List *build_joinrel_restrictlist(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outer_rel, @@ -48,8 +51,10 @@ static List *build_joinrel_restrictlist(PlannerInfo *root, static void build_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel); -static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel, - List *joininfo_list, +static List *subbuild_joinrel_restrictlist(PlannerInfo *root, + RelOptInfo *joinrel, + RelOptInfo *input_rel, + Relids both_input_relids, List *new_restrictlist); static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel, List *joininfo_list, @@ -57,10 +62,12 @@ static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel, static void set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel); static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel); -static void build_joinrel_partition_info(RelOptInfo *joinrel, +static void build_joinrel_partition_info(PlannerInfo *root, + RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel, - List *restrictlist, JoinType jointype); -static bool have_partkey_equi_join(RelOptInfo *joinrel, + SpecialJoinInfo *sjinfo, + List *restrictlist); +static bool have_partkey_equi_join(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype, List *restrictlist); static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, @@ -373,7 +380,7 @@ build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent) /* * find_base_rel - * Find a base or other relation entry, which must already exist. + * Find a base or otherrel relation entry, which must already exist. */ RelOptInfo * find_base_rel(PlannerInfo *root, int relid) @@ -394,6 +401,44 @@ find_base_rel(PlannerInfo *root, int relid) return NULL; /* keep compiler quiet */ } +/* + * find_base_rel_ignore_join + * Find a base or otherrel relation entry, which must already exist. + * + * Unlike find_base_rel, if relid references an outer join then this + * will return NULL rather than raising an error. This is convenient + * for callers that must deal with relid sets including both base and + * outer joins. + */ +RelOptInfo * +find_base_rel_ignore_join(PlannerInfo *root, int relid) +{ + Assert(relid > 0); + + if (relid < root->simple_rel_array_size) + { + RelOptInfo *rel; + RangeTblEntry *rte; + + rel = root->simple_rel_array[relid]; + if (rel) + return rel; + + /* + * We could just return NULL here, but for debugging purposes it seems + * best to actually verify that the relid is an outer join and not + * something weird. + */ + rte = root->simple_rte_array[relid]; + if (rte && rte->rtekind == RTE_JOIN && rte->jointype != JOIN_INNER) + return NULL; + } + + elog(ERROR, "no relation entry for relid %d", relid); + + return NULL; /* keep compiler quiet */ +} + /* * build_join_rel_hash * Construct the auxiliary hash table for join relations. @@ -693,9 +738,11 @@ build_join_rel(PlannerInfo *root, * and inner rels we first try to build it from. But the contents should * be the same regardless. */ - build_joinrel_tlist(root, joinrel, outer_rel); - build_joinrel_tlist(root, joinrel, inner_rel); - add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel); + build_joinrel_tlist(root, joinrel, outer_rel, sjinfo, + (sjinfo->jointype == JOIN_FULL)); + build_joinrel_tlist(root, joinrel, inner_rel, sjinfo, + (sjinfo->jointype != JOIN_INNER)); + add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel, sjinfo); /* * add_placeholders_to_joinrel also took care of adding the ph_lateral @@ -727,8 +774,8 @@ build_join_rel(PlannerInfo *root, joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel); /* Store the partition information. */ - build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist, - sjinfo->jointype); + build_joinrel_partition_info(root, joinrel, outer_rel, inner_rel, sjinfo, + restrictlist); /* * Set estimates of the joinrel's size. @@ -784,16 +831,14 @@ build_join_rel(PlannerInfo *root, * 'parent_joinrel' is the RelOptInfo representing the join between parent * relations. Some of the members of new RelOptInfo are produced by * translating corresponding members of this RelOptInfo - * 'sjinfo': child-join context info * 'restrictlist': list of RestrictInfo nodes that apply to this particular * pair of joinable relations - * 'jointype' is the join type (inner, left, full, etc) + * 'sjinfo': child join's join-type details */ RelOptInfo * build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, - List *restrictlist, SpecialJoinInfo *sjinfo, - JoinType jointype) + List *restrictlist, SpecialJoinInfo *sjinfo) { RelOptInfo *joinrel = makeNode(RelOptInfo); AppendRelInfo **appinfos; @@ -807,6 +852,8 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, joinrel->reloptkind = RELOPT_OTHER_JOINREL; joinrel->relids = bms_union(outer_rel->relids, inner_rel->relids); + if (sjinfo->ojrelid != 0) + joinrel->relids = bms_add_member(joinrel->relids, sjinfo->ojrelid); joinrel->rows = 0; /* cheap startup cost is interesting iff not all tuples to be retrieved */ joinrel->consider_startup = (root->tuple_fraction > 0); @@ -893,8 +940,8 @@ build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, joinrel->has_eclass_joins = parent_joinrel->has_eclass_joins; /* Is the join between partitions itself partitioned? */ - build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist, - jointype); + build_joinrel_partition_info(root, joinrel, outer_rel, inner_rel, sjinfo, + restrictlist); /* Child joinrel is parallel safe if parent is parallel safe. */ joinrel->consider_parallel = parent_joinrel->consider_parallel; @@ -976,10 +1023,41 @@ min_join_parameterization(PlannerInfo *root, * * We also compute the expected width of the join's output, making use * of data that was cached at the baserel level by set_rel_width(). + * + * Pass can_null as true if the join is an outer join that can null Vars + * from this input relation. If so, we will (normally) add the join's relid + * to the nulling bitmaps of Vars and PHVs bubbled up from the input. + * + * When forming an outer join's target list, special handling is needed + * in case the outer join was commuted with another one per outer join + * identity 3 (see optimizer/README). We must take steps to ensure that + * the output Vars have the same nulling bitmaps that they would if the + * two joins had been done in syntactic order; else they won't match Vars + * appearing higher in the query tree. We need to do two things: + * + * First, sjinfo->commute_above_r is added to the nulling bitmaps of RHS Vars. + * This takes care of the case where we implement + * A leftjoin (B leftjoin C on (Pbc)) on (Pab) + * as + * (A leftjoin B on (Pab)) leftjoin C on (Pbc) + * The C columns emitted by the B/C join need to be shown as nulled by both + * the B/C and A/B joins, even though they've not traversed the A/B join. + * (If the joins haven't been commuted, we are adding the nullingrel bits + * prematurely; but that's okay because the C columns can't be referenced + * between here and the upper join.) + * + * Second, if a RHS Var has any of the relids in sjinfo->commute_above_l + * already set in its nulling bitmap, then we *don't* add sjinfo->ojrelid + * to its nulling bitmap (but we do still add commute_above_r). This takes + * care of the reverse transformation: if the original syntax was + * (A leftjoin B on (Pab)) leftjoin C on (Pbc) + * then the now-upper A/B join must not mark C columns as nulled by itself. */ static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, - RelOptInfo *input_rel) + RelOptInfo *input_rel, + SpecialJoinInfo *sjinfo, + bool can_null) { Relids relids = joinrel->relids; ListCell *vars; @@ -999,7 +1077,24 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, /* Is it still needed above this joinrel? */ if (bms_nonempty_difference(phinfo->ph_needed, relids)) { - /* Yup, add it to the output */ + /* + * Yup, add it to the output. If this join potentially nulls + * this input, we have to update the PHV's phnullingrels, + * which means making a copy. + */ + if (can_null) + { + phv = copyObject(phv); + /* See comments above to understand this logic */ + if (sjinfo->ojrelid != 0 && + !bms_overlap(phv->phnullingrels, sjinfo->commute_above_l)) + phv->phnullingrels = bms_add_member(phv->phnullingrels, + sjinfo->ojrelid); + if (sjinfo->commute_above_r) + phv->phnullingrels = bms_add_members(phv->phnullingrels, + sjinfo->commute_above_r); + } + joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, phv); /* Bubbling up the precomputed result has cost zero */ @@ -1023,9 +1118,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, RowIdentityVarInfo *ridinfo = (RowIdentityVarInfo *) list_nth(root->row_identity_vars, var->varattno - 1); - joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, - var); - /* Vars have cost zero, so no need to adjust reltarget->cost */ + /* Update reltarget width estimate from RowIdentityVarInfo */ joinrel->reltarget->width += ridinfo->rowidwidth; } else @@ -1038,15 +1131,35 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, /* Is it still needed above this joinrel? */ ndx = var->varattno - baserel->min_attr; - if (bms_nonempty_difference(baserel->attr_needed[ndx], relids)) - { - /* Yup, add it to the output */ - joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, - var); - /* Vars have cost zero, so no need to adjust reltarget->cost */ - joinrel->reltarget->width += baserel->attr_widths[ndx]; - } + if (!bms_nonempty_difference(baserel->attr_needed[ndx], relids)) + continue; /* nope, skip it */ + + /* Update reltarget width estimate from baserel's attr_widths */ + joinrel->reltarget->width += baserel->attr_widths[ndx]; + } + + /* + * Add the Var to the output. If this join potentially nulls this + * input, we have to update the Var's varnullingrels, which means + * making a copy. + */ + if (can_null) + { + var = copyObject(var); + /* See comments above to understand this logic */ + if (sjinfo->ojrelid != 0 && + !bms_overlap(var->varnullingrels, sjinfo->commute_above_l)) + var->varnullingrels = bms_add_member(var->varnullingrels, + sjinfo->ojrelid); + if (sjinfo->commute_above_r) + var->varnullingrels = bms_add_members(var->varnullingrels, + sjinfo->commute_above_r); } + + joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, + var); + + /* Vars have cost zero, so no need to adjust reltarget->cost */ } } @@ -1065,7 +1178,7 @@ build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, * is not handled in the sub-relations, so it depends on which * sub-relations are considered. * - * If a join clause from an input relation refers to base rels still not + * If a join clause from an input relation refers to base+OJ rels still not * present in the joinrel, then it is still a join clause for the joinrel; * we put it into the joininfo list for the joinrel. Otherwise, * the clause is now a restrict clause for the joined relation, and we @@ -1099,14 +1212,19 @@ build_joinrel_restrictlist(PlannerInfo *root, RelOptInfo *inner_rel) { List *result; + Relids both_input_relids; + + both_input_relids = bms_union(outer_rel->relids, inner_rel->relids); /* * Collect all the clauses that syntactically belong at this level, * eliminating any duplicates (important since we will see many of the * same clauses arriving from both input relations). */ - result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL); - result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result); + result = subbuild_joinrel_restrictlist(root, joinrel, outer_rel, + both_input_relids, NIL); + result = subbuild_joinrel_restrictlist(root, joinrel, inner_rel, + both_input_relids, result); /* * Add on any clauses derived from EquivalenceClasses. These cannot be @@ -1141,24 +1259,63 @@ build_joinrel_joinlist(RelOptInfo *joinrel, } static List * -subbuild_joinrel_restrictlist(RelOptInfo *joinrel, - List *joininfo_list, +subbuild_joinrel_restrictlist(PlannerInfo *root, + RelOptInfo *joinrel, + RelOptInfo *input_rel, + Relids both_input_relids, List *new_restrictlist) { ListCell *l; - foreach(l, joininfo_list) + foreach(l, input_rel->joininfo) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); if (bms_is_subset(rinfo->required_relids, joinrel->relids)) { /* - * This clause becomes a restriction clause for the joinrel, since - * it refers to no outside rels. Add it to the list, being - * careful to eliminate duplicates. (Since RestrictInfo nodes in - * different joinlists will have been multiply-linked rather than - * copied, pointer equality should be a sufficient test.) + * This clause should become a restriction clause for the joinrel, + * since it refers to no outside rels. However, if it's a clone + * clause then it might be too late to evaluate it, so we have to + * check. (If it is too late, just ignore the clause, taking it + * on faith that another clone was or will be selected.) Clone + * clauses should always be outer-join clauses, so we compare + * against both_input_relids. + */ + if (rinfo->has_clone || rinfo->is_clone) + { + Assert(!RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids)); + if (!bms_is_subset(rinfo->required_relids, both_input_relids)) + continue; + if (!clause_is_computable_at(root, rinfo->clause_relids, + both_input_relids)) + continue; + } + else + { + /* + * For non-clone clauses, we just Assert it's OK. These might + * be either join or filter clauses. + */ +#ifdef USE_ASSERT_CHECKING + if (RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids)) + Assert(clause_is_computable_at(root, rinfo->clause_relids, + joinrel->relids)); + else + { + Assert(bms_is_subset(rinfo->required_relids, + both_input_relids)); + Assert(clause_is_computable_at(root, rinfo->clause_relids, + both_input_relids)); + } +#endif + } + + /* + * OK, so add it to the list, being careful to eliminate + * duplicates. (Since RestrictInfo nodes in different joinlists + * will have been multiply-linked rather than copied, pointer + * equality should be a sufficient test.) */ new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo); } @@ -1665,9 +1822,10 @@ find_param_path_info(RelOptInfo *rel, Relids required_outer) * partitioned join relation. */ static void -build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel, - RelOptInfo *inner_rel, List *restrictlist, - JoinType jointype) +build_joinrel_partition_info(PlannerInfo *root, + RelOptInfo *joinrel, RelOptInfo *outer_rel, + RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, + List *restrictlist) { PartitionScheme part_scheme; @@ -1693,8 +1851,8 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel, !outer_rel->consider_partitionwise_join || !inner_rel->consider_partitionwise_join || outer_rel->part_scheme != inner_rel->part_scheme || - !have_partkey_equi_join(joinrel, outer_rel, inner_rel, - jointype, restrictlist)) + !have_partkey_equi_join(root, joinrel, outer_rel, inner_rel, + sjinfo->jointype, restrictlist)) { Assert(!IS_PARTITIONED_REL(joinrel)); return; @@ -1718,7 +1876,8 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel, * child-join relations of the join relation in try_partitionwise_join(). */ joinrel->part_scheme = part_scheme; - set_joinrel_partition_key_exprs(joinrel, outer_rel, inner_rel, jointype); + set_joinrel_partition_key_exprs(joinrel, outer_rel, inner_rel, + sjinfo->jointype); /* * Set the consider_partitionwise_join flag. @@ -1736,7 +1895,7 @@ build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel, * partition keys. */ static bool -have_partkey_equi_join(RelOptInfo *joinrel, +have_partkey_equi_join(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *rel1, RelOptInfo *rel2, JoinType jointype, List *restrictlist) { @@ -1801,6 +1960,24 @@ have_partkey_equi_join(RelOptInfo *joinrel, */ strict_op = op_strict(opexpr->opno); + /* + * Vars appearing in the relation's partition keys will not have any + * varnullingrels, but those in expr1 and expr2 will if we're above + * outer joins that could null the respective rels. It's okay to + * match anyway, if the join operator is strict. + */ + if (strict_op) + { + if (bms_overlap(rel1->relids, root->outer_join_rels)) + expr1 = (Expr *) remove_nulling_relids((Node *) expr1, + root->outer_join_rels, + NULL); + if (bms_overlap(rel2->relids, root->outer_join_rels)) + expr2 = (Expr *) remove_nulling_relids((Node *) expr2, + root->outer_join_rels, + NULL); + } + /* * Only clauses referencing the partition keys are useful for * partitionwise join. @@ -2013,7 +2190,12 @@ set_joinrel_partition_key_exprs(RelOptInfo *joinrel, * partitionwise nesting of any outer join.) We assume no * type coercions are needed to make the coalesce expressions, * since columns of different types won't have gotten - * classified as the same PartitionScheme. + * classified as the same PartitionScheme. Note that we + * intentionally leave out the varnullingrels decoration that + * would ordinarily appear on the Vars inside these + * CoalesceExprs, because have_partkey_equi_join will strip + * varnullingrels from the expressions it will compare to the + * partexprs. */ foreach(lc, list_concat_copy(outer_expr, outer_null_expr)) { diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c index ef8df3d098..327c3ba563 100644 --- a/src/backend/optimizer/util/restrictinfo.c +++ b/src/backend/optimizer/util/restrictinfo.c @@ -53,6 +53,10 @@ static Expr *make_sub_restrictinfos(PlannerInfo *root, * required_relids can be NULL, in which case it defaults to the actual clause * contents (i.e., clause_relids). * + * Note that there aren't options to set the has_clone and is_clone flags: + * we always initialize those to false. There's just one place that wants + * something different, so making all callers pass them seems inconvenient. + * * We initialize fields that depend only on the given subexpression, leaving * others that depend on context (or may never be needed at all) to be filled * later. @@ -116,12 +120,15 @@ make_restrictinfo_internal(PlannerInfo *root, Relids nullable_relids) { RestrictInfo *restrictinfo = makeNode(RestrictInfo); + Relids baserels; restrictinfo->clause = clause; restrictinfo->orclause = orclause; restrictinfo->is_pushed_down = is_pushed_down; restrictinfo->outerjoin_delayed = outerjoin_delayed; restrictinfo->pseudoconstant = pseudoconstant; + restrictinfo->has_clone = false; /* may get set by caller */ + restrictinfo->is_clone = false; /* may get set by caller */ restrictinfo->can_join = false; /* may get set below */ restrictinfo->security_level = security_level; restrictinfo->outer_relids = outer_relids; @@ -187,6 +194,20 @@ make_restrictinfo_internal(PlannerInfo *root, else restrictinfo->required_relids = restrictinfo->clause_relids; + /* + * Count the number of base rels appearing in clause_relids. To do this, + * we just delete rels mentioned in root->outer_join_rels and count the + * survivors. Because we are called during deconstruct_jointree which is + * the same tree walk that populates outer_join_rels, this is a little bit + * unsafe-looking; but it should be fine because the recursion in + * deconstruct_jointree should already have visited any outer join that + * could be mentioned in this clause. + */ + baserels = bms_difference(restrictinfo->clause_relids, + root->outer_join_rels); + restrictinfo->num_base_rels = bms_num_members(baserels); + bms_free(baserels); + /* * Fill in all the cacheable fields with "not yet set" markers. None of * these will be computed until/unless needed. Note in particular that we @@ -497,6 +518,58 @@ extract_actual_join_clauses(List *restrictinfo_list, } } +/* + * clause_is_computable_at + * Test whether a clause is computable at a given evaluation level. + * + * There are two conditions for whether an expression can actually be + * evaluated at a given join level: the evaluation context must include + * all the relids (both base and OJ) used by the expression, and we must + * not have already evaluated any outer joins that null Vars/PHVs of the + * expression and are not listed in their nullingrels. + * + * This function checks the second condition; we assume the caller already + * saw to the first one. + * + * For speed reasons, we don't individually examine each Var/PHV of the + * expression, but just look at the overall clause_relids (the union of the + * varnos and varnullingrels). This could give a misleading answer if the + * Vars of a given varno don't all have the same varnullingrels; but that + * really shouldn't happen within a single scalar expression or RestrictInfo + * clause. Despite that, this is still annoyingly expensive :-( + */ +bool +clause_is_computable_at(PlannerInfo *root, + Relids clause_relids, + Relids eval_relids) +{ + ListCell *lc; + + /* Nothing to do if no outer joins have been performed yet. */ + if (!bms_overlap(eval_relids, root->outer_join_rels)) + return true; + + foreach(lc, root->join_info_list) + { + SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc); + + /* Ignore outer joins that are not yet performed. */ + if (!bms_is_member(sjinfo->ojrelid, eval_relids)) + continue; + + /* OK if clause lists it (we assume all Vars in it agree). */ + if (bms_is_member(sjinfo->ojrelid, clause_relids)) + continue; + + /* Else, trouble if clause mentions any nullable Vars. */ + if (bms_overlap(clause_relids, sjinfo->min_righthand) || + (sjinfo->jointype == JOIN_FULL && + bms_overlap(clause_relids, sjinfo->min_lefthand))) + return false; /* doesn't work */ + } + + return true; /* OK */ +} /* * join_clause_is_movable_to @@ -522,6 +595,12 @@ extract_actual_join_clauses(List *restrictinfo_list, * Also, the join clause must not use any relations that have LATERAL * references to the target relation, since we could not put such rels on * the outer side of a nestloop with the target relation. + * + * Also, we reject is_clone versions of outer-join clauses. This has the + * effect of preventing us from generating variant parameterized paths + * that differ only in which outer joins null the parameterization rel(s). + * Generating one path from the minimally-parameterized has_clone version + * is sufficient. */ bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel) @@ -542,6 +621,10 @@ join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel) if (bms_overlap(baserel->lateral_referencers, rinfo->clause_relids)) return false; + /* Ignore clones, too */ + if (rinfo->is_clone) + return false; + return true; } @@ -587,6 +670,9 @@ join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel) * moved for some valid set of outer rels, so we don't have the benefit of * relying on prior checks for lateral-reference validity. * + * Likewise, we don't check is_clone here: rejecting the inappropriate + * variants of a cloned clause must be handled upstream. + * * Note: if this returns true, it means that the clause could be moved to * this join relation, but that doesn't mean that this is the lowest join * it could be moved to. Caller may need to make additional calls to verify diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c index 7db86c39ef..8d8c9136f8 100644 --- a/src/backend/optimizer/util/var.c +++ b/src/backend/optimizer/util/var.c @@ -88,6 +88,9 @@ static Relids alias_relid_set(Query *query, Relids relids); * Create a set of all the distinct varnos present in a parsetree. * Only varnos that reference level-zero rtable entries are considered. * + * The result includes outer-join relids mentioned in Var.varnullingrels and + * PlaceHolderVar.phnullingrels fields in the parsetree. + * * "root" can be passed as NULL if it is not necessary to process * PlaceHolderVars. * @@ -153,7 +156,11 @@ pull_varnos_walker(Node *node, pull_varnos_context *context) Var *var = (Var *) node; if (var->varlevelsup == context->sublevels_up) + { context->varnos = bms_add_member(context->varnos, var->varno); + context->varnos = bms_add_members(context->varnos, + var->varnullingrels); + } return false; } if (IsA(node, CurrentOfExpr)) @@ -244,6 +251,14 @@ pull_varnos_walker(Node *node, pull_varnos_context *context) context->varnos = bms_join(context->varnos, newevalat); } + + /* + * In all three cases, include phnullingrels in the result. We + * don't worry about possibly needing to translate it, because + * appendrels only translate varnos of baserels, not outer joins. + */ + context->varnos = bms_add_members(context->varnos, + phv->phnullingrels); return false; /* don't recurse into expression */ } } diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index 48858a871a..32bd70faad 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -2205,7 +2205,7 @@ rowcomparesel(PlannerInfo *root, else { /* - * Otherwise, it's a join if there's more than one relation used. + * Otherwise, it's a join if there's more than one base relation used. */ is_join_clause = (NumRelids(root, (Node *) opargs) > 1); } diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 287bd554f6..8449dd7202 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -254,6 +254,20 @@ struct PlannerInfo */ Relids all_baserels; + /* + * outer_join_rels is a Relids set of all outer-join relids in the query. + * This is computed in deconstruct_jointree. + */ + Relids outer_join_rels; + + /* + * all_query_rels is a Relids set of all base relids and outer join relids + * (but not "other" relids) in the query. This is the Relids identifier + * of the final join we need to form. This is computed in + * deconstruct_jointree. + */ + Relids all_query_rels; + /* * nullable_baserels is a Relids set of base relids that are nullable by * some outer join in the jointree; these are rels that are potentially @@ -562,9 +576,10 @@ typedef struct PartitionSchemeData *PartitionScheme; * or the output of a sub-SELECT or function that appears in the range table. * In either case it is uniquely identified by an RT index. A "joinrel" * is the joining of two or more base rels. A joinrel is identified by - * the set of RT indexes for its component baserels. We create RelOptInfo - * nodes for each baserel and joinrel, and store them in the PlannerInfo's - * simple_rel_array and join_rel_list respectively. + * the set of RT indexes for its component baserels, along with RT indexes + * for any outer joins it has computed. We create RelOptInfo nodes for each + * baserel and joinrel, and store them in the PlannerInfo's simple_rel_array + * and join_rel_list respectively. * * Note that there is only one joinrel for any given set of component * baserels, no matter what order we assemble them in; so an unordered @@ -603,8 +618,10 @@ typedef struct PartitionSchemeData *PartitionScheme; * Parts of this data structure are specific to various scan and join * mechanisms. It didn't seem worth creating new node types for them. * - * relids - Set of base-relation identifiers; it is a base relation - * if there is just one, a join relation if more than one + * relids - Set of relation identifiers (RT indexes). This is a base + * relation if there is just one, a join relation if more; + * in the join case, RT indexes of any outer joins formed + * at or below this join are included along with baserels * rows - estimated number of tuples in the relation after restriction * clauses have been applied (ie, output rows of a plan for it) * consider_startup - true if there is any value in keeping plain paths for @@ -816,7 +833,7 @@ typedef struct RelOptInfo RelOptKind reloptkind; /* - * all relations included in this RelOptInfo; set of base relids + * all relations included in this RelOptInfo; set of base + OJ relids * (rangetable indexes) */ Relids relids; @@ -2286,17 +2303,17 @@ typedef struct LimitPath * If a restriction clause references a single base relation, it will appear * in the baserestrictinfo list of the RelOptInfo for that base rel. * - * If a restriction clause references more than one base rel, it will + * If a restriction clause references more than one base+OJ relation, it will * appear in the joininfo list of every RelOptInfo that describes a strict - * subset of the base rels mentioned in the clause. The joininfo lists are + * subset of the relations mentioned in the clause. The joininfo lists are * used to drive join tree building by selecting plausible join candidates. * The clause cannot actually be applied until we have built a join rel - * containing all the base rels it references, however. + * containing all the relations it references, however. * - * When we construct a join rel that includes all the base rels referenced + * When we construct a join rel that includes all the relations referenced * in a multi-relation restriction clause, we place that clause into the * joinrestrictinfo lists of paths for the join rel, if neither left nor - * right sub-path includes all base rels referenced in the clause. The clause + * right sub-path includes all relations referenced in the clause. The clause * will be applied at that join level, and will not propagate any further up * the join tree. (Note: the "predicate migration" code was once intended to * push restriction clauses up and down the plan tree based on evaluation @@ -2317,12 +2334,14 @@ typedef struct LimitPath * or join to enforce that all members of each EquivalenceClass are in fact * equal in all rows emitted by the scan or join. * - * When dealing with outer joins we have to be very careful about pushing qual - * clauses up and down the tree. An outer join's own JOIN/ON conditions must - * be evaluated exactly at that join node, unless they are "degenerate" - * conditions that reference only Vars from the nullable side of the join. - * Quals appearing in WHERE or in a JOIN above the outer join cannot be pushed - * down below the outer join, if they reference any nullable Vars. + * The clause_relids field lists the base plus outer-join RT indexes that + * actually appear in the clause. required_relids lists the minimum set of + * relids needed to evaluate the clause; while this is often equal to + * clause_relids, it can be more. We will add relids to required_relids when + * we need to force an outer join ON clause to be evaluated exactly at the + * level of the outer join, which is true except when it is a "degenerate" + * condition that references only Vars from the nullable side of the join. + * * RestrictInfo nodes contain a flag to indicate whether a qual has been * pushed down to a lower level than its original syntactic placement in the * join tree would suggest. If an outer join prevents us from pushing a qual @@ -2407,6 +2426,12 @@ typedef struct LimitPath * or merge or hash join clause, so it's of no interest to large parts of * the planner. * + * When we generate multiple versions of a clause so as to have versions + * that will work after commuting some left joins per outer join identity 3, + * we mark the one with the fewest nullingrels bits with has_clone = true, + * and the rest with is_clone = true. This allows proper filtering of + * these redundant clauses, so that we apply only one version of them. + * * When join clauses are generated from EquivalenceClasses, there may be * several equally valid ways to enforce join equivalence, of which we need * apply only one. We mark clauses of this kind by setting parent_ec to @@ -2441,16 +2466,23 @@ typedef struct RestrictInfo /* see comment above */ bool pseudoconstant pg_node_attr(equal_ignore); + /* see comment above */ + bool has_clone; + bool is_clone; + /* true if known to contain no leaked Vars */ bool leakproof pg_node_attr(equal_ignore); - /* to indicate if clause contains any volatile functions. */ + /* indicates if clause contains any volatile functions */ VolatileFunctionStatus has_volatile pg_node_attr(equal_ignore); /* see comment above */ Index security_level; - /* The set of relids (varnos) actually referenced in the clause: */ + /* number of base rels in clause_relids */ + int num_base_rels pg_node_attr(equal_ignore); + + /* The relids (varnos+varnullingrels) actually referenced in the clause: */ Relids clause_relids pg_node_attr(equal_ignore); /* The set of relids required to evaluate the clause: */ @@ -2654,20 +2686,49 @@ typedef struct PlaceHolderVar * We make SpecialJoinInfos for FULL JOINs even though there is no flexibility * of planning for them, because this simplifies make_join_rel()'s API. * - * min_lefthand and min_righthand are the sets of base relids that must be - * available on each side when performing the special join. lhs_strict is - * true if the special join's condition cannot succeed when the LHS variables - * are all NULL (this means that an outer join can commute with upper-level - * outer joins even if it appears in their RHS). We don't bother to set - * lhs_strict for FULL JOINs, however. - * + * min_lefthand and min_righthand are the sets of base+OJ relids that must be + * available on each side when performing the special join. * It is not valid for either min_lefthand or min_righthand to be empty sets; * if they were, this would break the logic that enforces join order. * - * syn_lefthand and syn_righthand are the sets of base relids that are + * syn_lefthand and syn_righthand are the sets of base+OJ relids that are * syntactically below this special join. (These are needed to help compute * min_lefthand and min_righthand for higher joins.) * + * jointype is never JOIN_RIGHT; a RIGHT JOIN is handled by switching + * the inputs to make it a LEFT JOIN. So the allowed values of jointype + * in a join_info_list member are only LEFT, FULL, SEMI, or ANTI. + * + * ojrelid is the RT index of the join RTE representing this outer join, + * if there is one. It is zero when jointype is INNER or SEMI, and can be + * zero for jointype ANTI (if the join was transformed from a SEMI join). + * One use for this field is that when constructing the output targetlist of a + * join relation that implements this OJ, we add ojrelid to the varnullingrels + * and phnullingrels fields of nullable (RHS) output columns, so that the + * output Vars and PlaceHolderVars correctly reflect the nulling that has + * potentially happened to them. + * + * commute_above_l is filled with the relids of syntactically-higher outer + * joins that have been found to commute with this one per outer join identity + * 3 (see optimizer/README), when this join is in the LHS of the upper join + * (so, this is the lower join in the first form of the identity). + * + * commute_above_r is filled with the relids of syntactically-higher outer + * joins that have been found to commute with this one per outer join identity + * 3, when this join is in the RHS of the upper join (so, this is the lower + * join in the second form of the identity). + * + * commute_below is filled with the relids of syntactically-lower outer joins + * that have been found to commute with this one per outer join identity 3. + * (We need not record which side they are on, since that can be determined + * by seeing whether the lower join's relid appears in syn_lefthand or + * syn_righthand.) + * + * lhs_strict is true if the special join's condition cannot succeed when the + * LHS variables are all NULL (this means that an outer join can commute with + * 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 @@ -2682,10 +2743,6 @@ typedef struct PlaceHolderVar * join planning; but it's helpful to have it available during planning of * parameterized table scans, so we store it in the SpecialJoinInfo structs.) * - * jointype is never JOIN_RIGHT; a RIGHT JOIN is handled by switching - * the inputs to make it a LEFT JOIN. So the allowed values of jointype - * in a join_info_list member are only LEFT, FULL, SEMI, or ANTI. - * * For purposes of join selectivity estimation, we create transient * SpecialJoinInfo structures for regular inner joins; so it is possible * to have jointype == JOIN_INNER in such a structure, even though this is @@ -2705,11 +2762,15 @@ struct SpecialJoinInfo pg_node_attr(no_read) NodeTag type; - Relids min_lefthand; /* base relids in minimum LHS for join */ - Relids min_righthand; /* base relids in minimum RHS for join */ - Relids syn_lefthand; /* base relids syntactically within LHS */ - Relids syn_righthand; /* base relids syntactically within RHS */ + Relids min_lefthand; /* base+OJ relids in minimum LHS for join */ + Relids min_righthand; /* base+OJ relids in minimum RHS for join */ + Relids syn_lefthand; /* base+OJ relids syntactically within LHS */ + Relids syn_righthand; /* base+OJ relids syntactically within RHS */ JoinType jointype; /* always INNER, LEFT, FULL, SEMI, or ANTI */ + Index ojrelid; /* outer join's RT index; 0 if none */ + Relids commute_above_l; /* commuting OJs above this one, if LHS */ + 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: */ diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index 050f00e79a..197234d44c 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -304,6 +304,7 @@ extern void expand_planner_arrays(PlannerInfo *root, int add_size); extern RelOptInfo *build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent); extern RelOptInfo *find_base_rel(PlannerInfo *root, int relid); +extern RelOptInfo *find_base_rel_ignore_join(PlannerInfo *root, int relid); extern RelOptInfo *find_join_rel(PlannerInfo *root, Relids relids); extern RelOptInfo *build_join_rel(PlannerInfo *root, Relids joinrelids, @@ -335,6 +336,6 @@ extern ParamPathInfo *find_param_path_info(RelOptInfo *rel, extern RelOptInfo *build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel, RelOptInfo *inner_rel, RelOptInfo *parent_joinrel, List *restrictlist, - SpecialJoinInfo *sjinfo, JoinType jointype); + SpecialJoinInfo *sjinfo); #endif /* PATHNODE_H */ diff --git a/src/include/optimizer/placeholder.h b/src/include/optimizer/placeholder.h index 507dbc6175..3fe9b57415 100644 --- a/src/include/optimizer/placeholder.h +++ b/src/include/optimizer/placeholder.h @@ -27,6 +27,9 @@ extern void update_placeholder_eval_levels(PlannerInfo *root, extern void fix_placeholder_input_needed_levels(PlannerInfo *root); extern void add_placeholders_to_base_rels(PlannerInfo *root); extern void add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel, - RelOptInfo *outer_rel, RelOptInfo *inner_rel); + RelOptInfo *outer_rel, RelOptInfo *inner_rel, + SpecialJoinInfo *sjinfo); +extern bool contain_placeholder_references_to(PlannerInfo *root, Node *clause, + int relid); #endif /* PLACEHOLDER_H */ diff --git a/src/include/optimizer/prep.h b/src/include/optimizer/prep.h index 5b4f350b33..0847cfd5f4 100644 --- a/src/include/optimizer/prep.h +++ b/src/include/optimizer/prep.h @@ -29,7 +29,8 @@ extern void pull_up_subqueries(PlannerInfo *root); extern void flatten_simple_union_all(PlannerInfo *root); extern void reduce_outer_joins(PlannerInfo *root); extern void remove_useless_result_rtes(PlannerInfo *root); -extern Relids get_relids_in_jointree(Node *jtnode, bool include_joins); +extern Relids get_relids_in_jointree(Node *jtnode, bool include_outer_joins, + bool include_inner_joins); extern Relids get_relids_for_join(Query *query, int joinrelid); /* diff --git a/src/include/optimizer/restrictinfo.h b/src/include/optimizer/restrictinfo.h index 6d30bd5e9d..17d3b4ab05 100644 --- a/src/include/optimizer/restrictinfo.h +++ b/src/include/optimizer/restrictinfo.h @@ -41,6 +41,9 @@ extern void extract_actual_join_clauses(List *restrictinfo_list, Relids joinrelids, List **joinquals, List **otherquals); +extern bool clause_is_computable_at(PlannerInfo *root, + Relids clause_relids, + Relids eval_relids); extern bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel); extern bool join_clause_is_movable_into(RestrictInfo *rinfo, Relids currentrelids,