From ad3b946231496d3ac0ba69e80daea9b14625b879 Mon Sep 17 00:00:00 2001 From: Takashi Suzuki Date: Wed, 15 Jan 2014 17:11:02 +0900 Subject: [PATCH] =?utf8?q?core.c=E3=81=AE=E5=90=84=E9=96=A2=E6=95=B0?= =?utf8?q?=E3=82=92PG93=E5=90=91=E3=81=91=E3=81=AB=E6=9B=B4=E6=96=B0?= =?utf8?q?=E3=81=97=E3=81=9F=E3=80=82?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- core.c | 211 ++++++++++++++++++++++++++++++++++++++++++++++----------- pg_hint_plan.c | 3 + 2 files changed, 174 insertions(+), 40 deletions(-) diff --git a/core.c b/core.c index 3d3cdfb..727c498 100644 --- a/core.c +++ b/core.c @@ -6,6 +6,7 @@ * src/backend/optimizer/path/allpaths.c * set_append_rel_pathlist() * generate_mergeappend_paths() + * get_cheapest_parameterized_child_path() * accumulate_append_subpath() * standard_join_search() * @@ -36,6 +37,7 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, int parentRTindex = rti; List *live_childrels = NIL; List *subpaths = NIL; + bool subpaths_valid = true; List *all_child_pathkeys = NIL; List *all_child_outers = NIL; ListCell *l; @@ -75,16 +77,22 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, continue; /* - * Child is live, so add its cheapest access path to the Append path - * we are constructing for the parent. + * Child is live, so add it to the live_childrels list for use below. */ - subpaths = accumulate_append_subpath(subpaths, - childrel->cheapest_total_path); - - /* Remember which childrels are live, for logic below */ live_childrels = lappend(live_childrels, childrel); /* + * If child has an unparameterized cheapest-total path, add that to + * the unparameterized Append path we are constructing for the parent. + * If not, there's no workable unparameterized path. + */ + if (childrel->cheapest_total_path->param_info == NULL) + subpaths = accumulate_append_subpath(subpaths, + childrel->cheapest_total_path); + else + subpaths_valid = false; + + /* * Collect lists of all the available path orderings and * parameterizations for all the children. We use these as a * heuristic to indicate which sort orderings and parameterizations we @@ -150,17 +158,20 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, } /* - * Next, build an unordered, unparameterized Append path for the rel. - * (Note: this is correct even if we have zero or one live subpath due to - * constraint exclusion.) + * If we found unparameterized paths for all children, build an unordered, + * unparameterized Append path for the rel. (Note: this is correct even + * if we have zero or one live subpath due to constraint exclusion.) */ - add_path(rel, (Path *) create_append_path(rel, subpaths, NULL)); + if (subpaths_valid) + add_path(rel, (Path *) create_append_path(rel, subpaths, NULL)); /* - * Build unparameterized MergeAppend paths based on the collected list of - * child pathkeys. + * Also build unparameterized MergeAppend paths based on the collected + * list of child pathkeys. */ - generate_mergeappend_paths(root, rel, live_childrels, all_child_pathkeys); + if (subpaths_valid) + generate_mergeappend_paths(root, rel, live_childrels, + all_child_pathkeys); /* * Build Append paths for each parameterization seen among the child rels. @@ -178,39 +189,29 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, foreach(l, all_child_outers) { Relids required_outer = (Relids) lfirst(l); - bool ok = true; ListCell *lcr; /* Select the child paths for an Append with this parameterization */ subpaths = NIL; + subpaths_valid = true; foreach(lcr, live_childrels) { RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr); - Path *cheapest_total; - - cheapest_total = - get_cheapest_path_for_pathkeys(childrel->pathlist, - NIL, - required_outer, - TOTAL_COST); - Assert(cheapest_total != NULL); + Path *subpath; - /* Children must have exactly the desired parameterization */ - if (!bms_equal(PATH_REQ_OUTER(cheapest_total), required_outer)) + subpath = get_cheapest_parameterized_child_path(root, + childrel, + required_outer); + if (subpath == NULL) { - cheapest_total = reparameterize_path(root, cheapest_total, - required_outer, 1.0); - if (cheapest_total == NULL) - { - ok = false; - break; - } + /* failed to make a suitable path for this child */ + subpaths_valid = false; + break; } - - subpaths = accumulate_append_subpath(subpaths, cheapest_total); + subpaths = accumulate_append_subpath(subpaths, subpath); } - if (ok) + if (subpaths_valid) add_path(rel, (Path *) create_append_path(rel, subpaths, required_outer)); } @@ -284,7 +285,8 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel, { cheapest_startup = cheapest_total = childrel->cheapest_total_path; - Assert(cheapest_total != NULL); + /* Assert we do have an unparameterized path for this child */ + Assert(cheapest_total->param_info == NULL); } /* @@ -317,6 +319,79 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel, } /* + * get_cheapest_parameterized_child_path + * Get cheapest path for this relation that has exactly the requested + * parameterization. + * + * Returns NULL if unable to create such a path. + */ +static Path * +get_cheapest_parameterized_child_path(PlannerInfo *root, RelOptInfo *rel, + Relids required_outer) +{ + Path *cheapest; + ListCell *lc; + + /* + * Look up the cheapest existing path with no more than the needed + * parameterization. If it has exactly the needed parameterization, we're + * done. + */ + cheapest = get_cheapest_path_for_pathkeys(rel->pathlist, + NIL, + required_outer, + TOTAL_COST); + Assert(cheapest != NULL); + if (bms_equal(PATH_REQ_OUTER(cheapest), required_outer)) + return cheapest; + + /* + * Otherwise, we can "reparameterize" an existing path to match the given + * parameterization, which effectively means pushing down additional + * joinquals to be checked within the path's scan. However, some existing + * paths might check the available joinquals already while others don't; + * therefore, it's not clear which existing path will be cheapest after + * reparameterization. We have to go through them all and find out. + */ + cheapest = NULL; + foreach(lc, rel->pathlist) + { + Path *path = (Path *) lfirst(lc); + + /* Can't use it if it needs more than requested parameterization */ + if (!bms_is_subset(PATH_REQ_OUTER(path), required_outer)) + continue; + + /* + * Reparameterization can only increase the path's cost, so if it's + * already more expensive than the current cheapest, forget it. + */ + if (cheapest != NULL && + compare_path_costs(cheapest, path, TOTAL_COST) <= 0) + continue; + + /* Reparameterize if needed, then recheck cost */ + if (!bms_equal(PATH_REQ_OUTER(path), required_outer)) + { + path = reparameterize_path(root, path, required_outer, 1.0); + if (path == NULL) + continue; /* failed to reparameterize this one */ + Assert(bms_equal(PATH_REQ_OUTER(path), required_outer)); + + if (cheapest != NULL && + compare_path_costs(cheapest, path, TOTAL_COST) <= 0) + continue; + } + + /* We have a new best path */ + cheapest = path; + } + + /* Return the best path, or NULL if we found no suitable candidate */ + return cheapest; +} + +/* * accumulate_append_subpath * Add a subpath to the list being built for an Append or MergeAppend * @@ -626,11 +701,14 @@ join_search_one_level(PlannerInfo *root, int level) * to accept failure at level 4 and go on to discover a workable * bushy plan at level 5. * - * However, if there are no special joins then join_is_legal() should - * never fail, and so the following sanity check is useful. + * However, if there are no special joins and no lateral references + * then join_is_legal() should never fail, and so the following sanity + * check is useful. *---------- */ - if (joinrels[level] == NIL && root->join_info_list == NIL) + if (joinrels[level] == NIL && + root->join_info_list == NIL && + root->lateral_info_list == NIL) elog(ERROR, "failed to build any %d-way joins", level); } } @@ -730,6 +808,8 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, bool reversed; bool unique_ified; bool is_valid_inner; + bool lateral_fwd; + bool lateral_rev; ListCell *l; /* @@ -909,6 +989,47 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, (match_sjinfo == NULL || unique_ified)) return false; /* invalid join path */ + /* + * We also have to check for constraints imposed by LATERAL references. + * The proposed rels could each contain lateral references to the other, + * in which case the join is impossible. If there are lateral references + * in just one direction, then the join has to be done with a nestloop + * with the lateral referencer on the inside. If the join matches an SJ + * that cannot be implemented by such a nestloop, the join is impossible. + */ + lateral_fwd = lateral_rev = false; + foreach(l, root->lateral_info_list) + { + LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l); + + if (bms_is_subset(ljinfo->lateral_rhs, rel2->relids) && + bms_overlap(ljinfo->lateral_lhs, rel1->relids)) + { + /* has to be implemented as nestloop with rel1 on left */ + if (lateral_rev) + return false; /* have lateral refs in both directions */ + lateral_fwd = true; + if (!bms_is_subset(ljinfo->lateral_lhs, rel1->relids)) + return false; /* rel1 can't compute the required parameter */ + if (match_sjinfo && + (reversed || match_sjinfo->jointype == JOIN_FULL)) + return false; /* not implementable as nestloop */ + } + if (bms_is_subset(ljinfo->lateral_rhs, rel1->relids) && + bms_overlap(ljinfo->lateral_lhs, rel2->relids)) + { + /* has to be implemented as nestloop with rel2 on left */ + if (lateral_fwd) + return false; /* have lateral refs in both directions */ + lateral_rev = true; + if (!bms_is_subset(ljinfo->lateral_lhs, rel2->relids)) + return false; /* rel2 can't compute the required parameter */ + if (match_sjinfo && + (!reversed || match_sjinfo->jointype == JOIN_FULL)) + return false; /* not implementable as nestloop */ + } + } + /* Otherwise, it's a valid join */ *sjinfo_p = match_sjinfo; *reversed_p = reversed; @@ -917,8 +1038,9 @@ join_is_legal(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2, /* * has_join_restriction - * Detect whether the specified relation has join-order restrictions - * due to being inside an outer join or an IN (sub-SELECT). + * Detect whether the specified relation has join-order restrictions, + * due to being inside an outer join or an IN (sub-SELECT), + * or participating in any LATERAL references. * * Essentially, this tests whether have_join_order_restriction() could * succeed with this rel and some other one. It's OK if we sometimes @@ -930,6 +1052,15 @@ has_join_restriction(PlannerInfo *root, RelOptInfo *rel) { ListCell *l; + foreach(l, root->lateral_info_list) + { + LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l); + + if (bms_is_subset(ljinfo->lateral_rhs, rel->relids) || + bms_overlap(ljinfo->lateral_lhs, rel->relids)) + return true; + } + foreach(l, root->join_info_list) { SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l); diff --git a/pg_hint_plan.c b/pg_hint_plan.c index 2df69d9..aebc709 100644 --- a/pg_hint_plan.c +++ b/pg_hint_plan.c @@ -416,6 +416,9 @@ static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel, List *live_childrels, List *all_child_pathkeys); +static Path *get_cheapest_parameterized_child_path(PlannerInfo *root, + RelOptInfo *rel, + Relids required_outer); static List *accumulate_append_subpath(List *subpaths, Path *path); RelOptInfo *pg_hint_plan_make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2); -- 2.11.0