diff options
Diffstat (limited to 'src/backend/optimizer')
| -rw-r--r-- | src/backend/optimizer/plan/analyzejoins.c | 2 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/initsplan.c | 37 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/planmain.c | 23 | ||||
| -rw-r--r-- | src/backend/optimizer/util/placeholder.c | 238 |
4 files changed, 266 insertions, 34 deletions
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c index 2a913578eba..89805c36b06 100644 --- a/src/backend/optimizer/plan/analyzejoins.c +++ b/src/backend/optimizer/plan/analyzejoins.c @@ -396,6 +396,8 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids) phinfo->ph_eval_at = bms_add_member(phinfo->ph_eval_at, relid); phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid); + /* ph_may_need probably isn't used after this, but fix it anyway */ + phinfo->ph_may_need = bms_del_member(phinfo->ph_may_need, relid); } /* diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 2c61795ff27..a2ff314679d 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -187,6 +187,13 @@ add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed) phinfo->ph_needed = bms_add_members(phinfo->ph_needed, where_needed); + /* + * Update ph_may_need too. This is currently only necessary + * when being called from build_base_rel_tlists, but we may as + * well do it always. + */ + phinfo->ph_may_need = bms_add_members(phinfo->ph_may_need, + where_needed); } else elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node)); @@ -465,7 +472,11 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, /* Now we can add the SpecialJoinInfo to join_info_list */ if (sjinfo) + { root->join_info_list = lappend(root->join_info_list, sjinfo); + /* Each time we do that, recheck placeholder eval levels */ + update_placeholder_eval_levels(root, sjinfo); + } /* * Finally, compute the output joinlist. We fold subproblems together @@ -688,6 +699,32 @@ make_outerjoininfo(PlannerInfo *root, } /* + * Examine PlaceHolderVars. If a PHV is supposed to be evaluated within + * this join's nullable side, and it may get used above this join, then + * ensure that min_righthand contains the full eval_at set of the PHV. + * This ensures that the PHV actually can be evaluated within the RHS. + * Note that this works only because we should already have determined + * the final eval_at level for any PHV syntactically within this join. + */ + foreach(l, root->placeholder_list) + { + PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l); + Relids ph_syn_level = phinfo->ph_var->phrels; + + /* Ignore placeholder if it didn't syntactically come from RHS */ + if (!bms_is_subset(ph_syn_level, right_rels)) + continue; + + /* We can also ignore it if it's certainly not used above this join */ + /* XXX this test is probably overly conservative */ + if (bms_is_subset(phinfo->ph_may_need, min_righthand)) + continue; + + /* Else, prevent join from being formed before we eval the PHV */ + min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at); + } + + /* * If we found nothing to put in min_lefthand, punt and make it the full * LHS, to avoid having an empty min_lefthand which will confuse later * processing. (We don't try to be smart about such cases, just correct.) diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index e82c3404b53..9e884cbb3cb 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -180,14 +180,19 @@ query_planner(PlannerInfo *root, List *tlist, add_base_rels_to_query(root, (Node *) parse->jointree); /* - * Examine the targetlist and qualifications, adding entries to baserel - * targetlists for all referenced Vars. Restrict and join clauses are - * added to appropriate lists belonging to the mentioned relations. We - * also build EquivalenceClasses for provably equivalent expressions, and - * form a target joinlist for make_one_rel() to work from. + * Examine the targetlist and join tree, adding entries to baserel + * targetlists for all referenced Vars, and generating PlaceHolderInfo + * entries for all referenced PlaceHolderVars. Restrict and join clauses + * are added to appropriate lists belonging to the mentioned relations. + * We also build EquivalenceClasses for provably equivalent expressions. + * The SpecialJoinInfo list is also built to hold information about join + * order restrictions. Finally, we form a target joinlist for + * make_one_rel() to work from. */ build_base_rel_tlists(root, tlist); + find_placeholders_in_jointree(root); + joinlist = deconstruct_jointree(root); /* @@ -218,10 +223,12 @@ query_planner(PlannerInfo *root, List *tlist, /* * Examine any "placeholder" expressions generated during subquery pullup. - * Make sure that we know what level to evaluate them at, and that the - * Vars they need are marked as needed. + * Make sure that the Vars they need are marked as needed at the relevant + * join level. This must be done before join removal because it might + * cause Vars or placeholders to be needed above a join when they weren't + * so marked before. */ - fix_placeholder_eval_levels(root); + fix_placeholder_input_needed_levels(root); /* * Remove any useless outer joins. Ideally this would be done during diff --git a/src/backend/optimizer/util/placeholder.c b/src/backend/optimizer/util/placeholder.c index 06bd6f2d011..c9da718bd1f 100644 --- a/src/backend/optimizer/util/placeholder.c +++ b/src/backend/optimizer/util/placeholder.c @@ -22,6 +22,11 @@ #include "optimizer/var.h" #include "utils/lsyscache.h" +/* Local functions */ +static Relids find_placeholders_recurse(PlannerInfo *root, Node *jtnode); +static void find_placeholders_in_qual(PlannerInfo *root, Node *qual, + Relids relids); + /* * make_placeholder_expr @@ -47,6 +52,12 @@ make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels) * find_placeholder_info * Fetch the PlaceHolderInfo for the given PHV; create it if not found * + * This is separate from make_placeholder_expr because subquery pullup has + * to make PlaceHolderVars for expressions that might not be used at all in + * the upper query, or might not remain after const-expression simplification. + * We build PlaceHolderInfos only for PHVs that are still present in the + * simplified query passed to query_planner(). + * * Note: this should only be called after query_planner() has started. */ PlaceHolderInfo * @@ -71,8 +82,9 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv) phinfo->phid = phv->phid; phinfo->ph_var = copyObject(phv); phinfo->ph_eval_at = pull_varnos((Node *) phv); - /* ph_eval_at may change later, see fix_placeholder_eval_levels */ + /* ph_eval_at may change later, see update_placeholder_eval_levels */ phinfo->ph_needed = NULL; /* initially it's unused */ + phinfo->ph_may_need = NULL; /* for the moment, estimate width using just the datatype info */ phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr), exprTypmod((Node *) phv->phexpr)); @@ -83,21 +95,168 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv) } /* - * fix_placeholder_eval_levels + * find_placeholders_in_jointree + * Search the jointree for PlaceHolderVars, and build PlaceHolderInfos + * + * We don't need to look at the targetlist because build_base_rel_tlists() + * will already have made entries for any PHVs in the tlist. + */ +void +find_placeholders_in_jointree(PlannerInfo *root) +{ + /* We need do nothing if the query contains no PlaceHolderVars */ + if (root->glob->lastPHId != 0) + { + /* Start recursion at top of jointree */ + Assert(root->parse->jointree != NULL && + IsA(root->parse->jointree, FromExpr)); + (void) find_placeholders_recurse(root, (Node *) root->parse->jointree); + } +} + +/* + * find_placeholders_recurse + * One recursion level of find_placeholders_in_jointree. + * + * jtnode is the current jointree node to examine. + * + * The result is the set of base Relids contained in or below jtnode. + * This is just an internal convenience, it's not used at the top level. + */ +static Relids +find_placeholders_recurse(PlannerInfo *root, Node *jtnode) +{ + Relids jtrelids; + + if (jtnode == NULL) + return NULL; + if (IsA(jtnode, RangeTblRef)) + { + int varno = ((RangeTblRef *) jtnode)->rtindex; + + /* No quals to deal with, just return correct result */ + jtrelids = bms_make_singleton(varno); + } + else if (IsA(jtnode, FromExpr)) + { + FromExpr *f = (FromExpr *) jtnode; + ListCell *l; + + /* + * First, recurse to handle child joins, and form their relid set. + */ + jtrelids = NULL; + foreach(l, f->fromlist) + { + Relids sub_relids; + + sub_relids = find_placeholders_recurse(root, lfirst(l)); + jtrelids = bms_join(jtrelids, sub_relids); + } + + /* + * Now process the top-level quals. + */ + find_placeholders_in_qual(root, f->quals, jtrelids); + } + else if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; + Relids leftids, + rightids; + + /* + * First, recurse to handle child joins, and form their relid set. + */ + leftids = find_placeholders_recurse(root, j->larg); + rightids = find_placeholders_recurse(root, j->rarg); + jtrelids = bms_join(leftids, rightids); + + /* Process the qual clauses */ + find_placeholders_in_qual(root, j->quals, jtrelids); + } + else + { + elog(ERROR, "unrecognized node type: %d", + (int) nodeTag(jtnode)); + jtrelids = NULL; /* keep compiler quiet */ + } + return jtrelids; +} + +/* + * find_placeholders_in_qual + * Process a qual clause for find_placeholders_in_jointree. + * + * relids is the syntactic join level to mark as the "maybe needed" level + * for each PlaceHolderVar found in the qual clause. + */ +static void +find_placeholders_in_qual(PlannerInfo *root, Node *qual, Relids relids) +{ + List *vars; + ListCell *vl; + + /* + * pull_var_clause does more than we need here, but it'll do and it's + * convenient to use. + */ + vars = pull_var_clause(qual, PVC_INCLUDE_PLACEHOLDERS); + foreach(vl, vars) + { + PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl); + PlaceHolderInfo *phinfo; + + /* Ignore any plain Vars */ + if (!IsA(phv, PlaceHolderVar)) + continue; + + /* Create a PlaceHolderInfo entry if there's not one already */ + phinfo = find_placeholder_info(root, phv); + + /* Mark the PHV as possibly needed at the qual's syntactic level */ + phinfo->ph_may_need = bms_add_members(phinfo->ph_may_need, relids); + + /* + * This is a bit tricky: the PHV's contained expression may contain + * other, lower-level PHVs. We need to get those into the + * PlaceHolderInfo list, but they aren't going to be needed where the + * outer PHV is referenced. Rather, they'll be needed where the outer + * PHV is evaluated. We can estimate that (conservatively) as the + * syntactic location of the PHV's expression. Recurse to take care + * of any such PHVs. + */ + find_placeholders_in_qual(root, (Node *) phv->phexpr, phv->phrels); + } + list_free(vars); +} + +/* + * update_placeholder_eval_levels * Adjust the target evaluation levels for placeholders * * The initial eval_at level set by find_placeholder_info was the set of - * rels used in the placeholder's expression (or the whole subselect if - * the expr is variable-free). If the subselect contains any outer joins - * that can null any of those rels, we must delay evaluation to above those - * joins. + * rels used in the placeholder's expression (or the whole subselect below + * the placeholder's syntactic location, if the expr is variable-free). + * If the subselect contains any outer joins that can null any of those rels, + * we must delay evaluation to above those joins. + * + * We repeat this operation each time we add another outer join to + * root->join_info_list. It's somewhat annoying to have to do that, but + * since we don't have very much information on the placeholders' locations, + * it's hard to avoid. Each placeholder's eval_at level must be correct + * by the time it starts to figure in outer-join delay decisions for higher + * outer joins. * * In future we might want to put additional policy/heuristics here to * try to determine an optimal evaluation level. The current rules will - * result in evaluation at the lowest possible level. + * result in evaluation at the lowest possible level. However, pushing a + * placeholder eval up the tree is likely to further constrain evaluation + * order for outer joins, so it could easily be counterproductive; and we + * don't have enough information at this point to make an intelligent choice. */ void -fix_placeholder_eval_levels(PlannerInfo *root) +update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo) { ListCell *lc1; @@ -105,16 +264,27 @@ fix_placeholder_eval_levels(PlannerInfo *root) { PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc1); Relids syn_level = phinfo->ph_var->phrels; - Relids eval_at = phinfo->ph_eval_at; + Relids eval_at; bool found_some; ListCell *lc2; /* + * We don't need to do any work on this placeholder unless the + * newly-added outer join is syntactically beneath its location. + */ + if (!bms_is_subset(new_sjinfo->syn_lefthand, syn_level) || + !bms_is_subset(new_sjinfo->syn_righthand, syn_level)) + continue; + + /* * Check for delays due to lower outer joins. This is the same logic * as in check_outerjoin_delay in initsplan.c, except that we don't - * want to modify the delay_upper_joins flags; that was all handled - * already during distribute_qual_to_rels. + * have anything to do with the delay_upper_joins flags; delay of + * upper outer joins will be handled later, based on the eval_at + * values we compute now. */ + eval_at = phinfo->ph_eval_at; + do { found_some = false; @@ -122,7 +292,7 @@ fix_placeholder_eval_levels(PlannerInfo *root) { SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc2); - /* disregard joins not within the expr's sub-select */ + /* disregard joins not within the PHV's sub-select */ if (!bms_is_subset(sjinfo->syn_lefthand, syn_level) || !bms_is_subset(sjinfo->syn_righthand, syn_level)) continue; @@ -149,16 +319,32 @@ fix_placeholder_eval_levels(PlannerInfo *root) } while (found_some); phinfo->ph_eval_at = eval_at; + } +} - /* - * Now that we know where to evaluate the placeholder, make sure that - * any vars or placeholders it uses will be available at that join - * level. NOTE: this could cause more PlaceHolderInfos to be added to - * placeholder_list. That is okay because we'll process them before - * falling out of the foreach loop. Also, it could cause the - * ph_needed sets of existing list entries to expand, which is also - * okay because this loop doesn't examine those. - */ +/* + * fix_placeholder_input_needed_levels + * Adjust the "needed at" levels for placeholder inputs + * + * This is called after we've finished determining the eval_at levels for + * all placeholders. We need to make sure that all vars and placeholders + * needed to evaluate each placeholder will be available at the join level + * where the evaluation will be done. Note that this loop can have + * side-effects on the ph_needed sets of other PlaceHolderInfos; that's okay + * because we don't examine ph_needed here, so there are no ordering issues + * to worry about. + */ +void +fix_placeholder_input_needed_levels(PlannerInfo *root) +{ + ListCell *lc; + + foreach(lc, root->placeholder_list) + { + PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc); + Relids eval_at = phinfo->ph_eval_at; + + /* No work unless it'll be evaluated above baserel level */ if (bms_membership(eval_at) == BMS_MULTIPLE) { List *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr, @@ -175,11 +361,11 @@ fix_placeholder_eval_levels(PlannerInfo *root) * Add any required PlaceHolderVars to base rels' targetlists. * * If any placeholder can be computed at a base rel and is needed above it, - * add it to that rel's targetlist. We have to do this separately from - * fix_placeholder_eval_levels() because join removal happens in between, - * and can change the ph_eval_at sets. There is essentially the same logic - * in add_placeholders_to_joinrel, but we can't do that part until joinrels - * are formed. + * add it to that rel's targetlist. This might look like it could be merged + * with fix_placeholder_input_needed_levels, but it must be separate because + * join removal happens in between, and can change the ph_eval_at sets. There + * is essentially the same logic in add_placeholders_to_joinrel, but we can't + * do that part until joinrels are formed. */ void add_placeholders_to_base_rels(PlannerInfo *root) |