diff options
Diffstat (limited to 'src/backend/optimizer')
| -rw-r--r-- | src/backend/optimizer/README | 5 | ||||
| -rw-r--r-- | src/backend/optimizer/path/allpaths.c | 169 | ||||
| -rw-r--r-- | src/backend/optimizer/path/costsize.c | 78 | ||||
| -rw-r--r-- | src/backend/optimizer/path/equivclass.c | 14 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/createplan.c | 205 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/setrefs.c | 18 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/subselect.c | 16 | ||||
| -rw-r--r-- | src/backend/optimizer/util/pathnode.c | 71 |
8 files changed, 529 insertions, 47 deletions
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README index fc793ac8ae..d6402cf911 100644 --- a/src/backend/optimizer/README +++ b/src/backend/optimizer/README @@ -343,11 +343,12 @@ RelOptInfo - a relation or joined relations join clauses) Path - every way to generate a RelOptInfo(sequential,index,joins) - SeqScan - a plain Path node with pathtype = T_SeqScan - IndexPath - index scans + SeqScan - represents a sequential scan plan + IndexPath - index scan BitmapHeapPath - top of a bitmapped index scan TidPath - scan by CTID AppendPath - append multiple subpaths together + MergeAppendPath - merge multiple subpaths, preserving their common sort order ResultPath - a Result plan node (used for FROM-less SELECT) MaterialPath - a Material plan node UniquePath - remove duplicate rows diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index b7cf0b815b..aa9a90cbfa 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -51,6 +51,7 @@ static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte); +static List *accumulate_append_subpath(List *subpaths, Path *path); static void set_dummy_rel_pathlist(RelOptInfo *rel); static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte); @@ -283,7 +284,9 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte) { int parentRTindex = rti; + List *live_childrels = NIL; List *subpaths = NIL; + List *all_child_pathkeys = NIL; double parent_rows; double parent_size; double *parent_attrsizes; @@ -321,7 +324,7 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RelOptInfo *childrel; List *childquals; Node *childqual; - Path *childpath; + ListCell *lcp; ListCell *parentvars; ListCell *childvars; @@ -395,13 +398,15 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, /* * We have to make child entries in the EquivalenceClass data - * structures as well. + * structures as well. This is needed either if the parent + * participates in some eclass joins (because we will want to + * consider inner-indexscan joins on the individual children) + * or if the parent has useful pathkeys (because we should try + * to build MergeAppend paths that produce those sort orderings). */ - if (rel->has_eclass_joins) - { + if (rel->has_eclass_joins || has_useful_pathkeys(root, rel)) add_child_rel_equivalences(root, appinfo, rel, childrel); - childrel->has_eclass_joins = true; - } + childrel->has_eclass_joins = rel->has_eclass_joins; /* * Note: we could compute appropriate attr_needed data for the child's @@ -411,23 +416,52 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, * otherrels. So we just leave the child's attr_needed empty. */ + /* Remember which childrels are live, for MergeAppend logic below */ + live_childrels = lappend(live_childrels, childrel); + /* * Compute the child's access paths, and add the cheapest one to the * Append path we are constructing for the parent. - * - * It's possible that the child is itself an appendrel, in which case - * we can "cut out the middleman" and just add its child paths to our - * own list. (We don't try to do this earlier because we need to - * apply both levels of transformation to the quals.) */ set_rel_pathlist(root, childrel, childRTindex, childRTE); - childpath = childrel->cheapest_total_path; - if (IsA(childpath, AppendPath)) - subpaths = list_concat(subpaths, - list_copy(((AppendPath *) childpath)->subpaths)); - else - subpaths = lappend(subpaths, childpath); + subpaths = accumulate_append_subpath(subpaths, + childrel->cheapest_total_path); + + /* + * Collect a list of all the available path orderings for all the + * children. We use this as a heuristic to indicate which sort + * orderings we should build MergeAppend paths for. + */ + foreach(lcp, childrel->pathlist) + { + Path *childpath = (Path *) lfirst(lcp); + List *childkeys = childpath->pathkeys; + ListCell *lpk; + bool found = false; + + /* Ignore unsorted paths */ + if (childkeys == NIL) + continue; + + /* Have we already seen this ordering? */ + foreach(lpk, all_child_pathkeys) + { + List *existing_pathkeys = (List *) lfirst(lpk); + + if (compare_pathkeys(existing_pathkeys, + childkeys) == PATHKEYS_EQUAL) + { + found = true; + break; + } + } + if (!found) + { + /* No, so add it to all_child_pathkeys */ + all_child_pathkeys = lappend(all_child_pathkeys, childkeys); + } + } /* * Accumulate size information from each child. @@ -483,17 +517,107 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, pfree(parent_attrsizes); /* - * Finally, build Append path and install it as the only access path for - * the parent rel. (Note: this is correct even if we have zero or one - * live subpath due to constraint exclusion.) + * Next, build an unordered 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)); - /* Select cheapest path (pretty easy in this case...) */ + /* + * Next, build MergeAppend paths based on the collected list of child + * pathkeys. We consider both cheapest-startup and cheapest-total + * cases, ie, for each interesting ordering, collect all the cheapest + * startup subpaths and all the cheapest total paths, and build a + * MergeAppend path for each list. + */ + foreach(l, all_child_pathkeys) + { + List *pathkeys = (List *) lfirst(l); + List *startup_subpaths = NIL; + List *total_subpaths = NIL; + bool startup_neq_total = false; + ListCell *lcr; + + /* Select the child paths for this ordering... */ + foreach(lcr, live_childrels) + { + RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr); + Path *cheapest_startup, + *cheapest_total; + + /* Locate the right paths, if they are available. */ + cheapest_startup = + get_cheapest_path_for_pathkeys(childrel->pathlist, + pathkeys, + STARTUP_COST); + cheapest_total = + get_cheapest_path_for_pathkeys(childrel->pathlist, + pathkeys, + TOTAL_COST); + + /* + * If we can't find any paths with the right order just add the + * cheapest-total path; we'll have to sort it. + */ + if (cheapest_startup == NULL) + cheapest_startup = childrel->cheapest_total_path; + if (cheapest_total == NULL) + cheapest_total = childrel->cheapest_total_path; + + /* + * Notice whether we actually have different paths for the + * "cheapest" and "total" cases; frequently there will be no + * point in two create_merge_append_path() calls. + */ + if (cheapest_startup != cheapest_total) + startup_neq_total = true; + + startup_subpaths = + accumulate_append_subpath(startup_subpaths, cheapest_startup); + total_subpaths = + accumulate_append_subpath(total_subpaths, cheapest_total); + } + + /* ... and build the MergeAppend paths */ + add_path(rel, (Path *) create_merge_append_path(root, + rel, + startup_subpaths, + pathkeys)); + if (startup_neq_total) + add_path(rel, (Path *) create_merge_append_path(root, + rel, + total_subpaths, + pathkeys)); + } + + /* Select cheapest path */ set_cheapest(rel); } /* + * accumulate_append_subpath + * Add a subpath to the list being built for an Append or MergeAppend + * + * It's possible that the child is itself an Append path, in which case + * we can "cut out the middleman" and just add its child paths to our + * own list. (We don't try to do this earlier because we need to + * apply both levels of transformation to the quals.) + */ +static List * +accumulate_append_subpath(List *subpaths, Path *path) +{ + if (IsA(path, AppendPath)) + { + AppendPath *apath = (AppendPath *) path; + + /* list_copy is important here to avoid sharing list substructure */ + return list_concat(subpaths, list_copy(apath->subpaths)); + } + else + return lappend(subpaths, path); +} + +/* * set_dummy_rel_pathlist * Build a dummy path for a relation that's been excluded by constraints * @@ -1385,6 +1509,9 @@ print_path(PlannerInfo *root, Path *path, int indent) case T_AppendPath: ptype = "Append"; break; + case T_MergeAppendPath: + ptype = "MergeAppend"; + break; case T_ResultPath: ptype = "Result"; break; diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index b27dc53fef..067cbca125 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -1210,6 +1210,70 @@ cost_sort(Path *path, PlannerInfo *root, } /* + * cost_merge_append + * Determines and returns the cost of a MergeAppend node. + * + * MergeAppend merges several pre-sorted input streams, using a heap that + * at any given instant holds the next tuple from each stream. If there + * are N streams, we need about N*log2(N) tuple comparisons to construct + * the heap at startup, and then for each output tuple, about log2(N) + * comparisons to delete the top heap entry and another log2(N) comparisons + * to insert its successor from the same stream. + * + * (The effective value of N will drop once some of the input streams are + * exhausted, but it seems unlikely to be worth trying to account for that.) + * + * The heap is never spilled to disk, since we assume N is not very large. + * So this is much simpler than cost_sort. + * + * As in cost_sort, we charge two operator evals per tuple comparison. + * + * 'pathkeys' is a list of sort keys + * 'n_streams' is the number of input streams + * 'input_startup_cost' is the sum of the input streams' startup costs + * 'input_total_cost' is the sum of the input streams' total costs + * 'tuples' is the number of tuples in all the streams + */ +void +cost_merge_append(Path *path, PlannerInfo *root, + List *pathkeys, int n_streams, + Cost input_startup_cost, Cost input_total_cost, + double tuples) +{ + Cost startup_cost = 0; + Cost run_cost = 0; + Cost comparison_cost; + double N; + double logN; + + /* + * Avoid log(0)... + */ + N = (n_streams < 2) ? 2.0 : (double) n_streams; + logN = LOG2(N); + + /* Assumed cost per tuple comparison */ + comparison_cost = 2.0 * cpu_operator_cost; + + /* Heap creation cost */ + startup_cost += comparison_cost * N * logN; + + /* Per-tuple heap maintenance cost */ + run_cost += tuples * comparison_cost * 2.0 * logN; + + /* + * Also charge a small amount (arbitrarily set equal to operator cost) per + * extracted tuple. We don't charge cpu_tuple_cost because a MergeAppend + * node doesn't do qual-checking or projection, so it has less overhead + * than most plan nodes. + */ + run_cost += cpu_operator_cost * tuples; + + path->startup_cost = startup_cost + input_startup_cost; + path->total_cost = startup_cost + run_cost + input_total_cost; +} + +/* * cost_material * Determines and returns the cost of materializing a relation, including * the cost of reading the input data. @@ -1405,7 +1469,9 @@ cost_group(Path *path, PlannerInfo *root, * output row count, which may be lower than the restriction-clause-only row * count of its parent. (We don't include this case in the PATH_ROWS macro * because it applies *only* to a nestloop's inner relation.) We have to - * be prepared to recurse through Append nodes in case of an appendrel. + * be prepared to recurse through Append or MergeAppend nodes in case of an + * appendrel. (It's not clear MergeAppend can be seen here, but we may as + * well handle it if so.) */ static double nestloop_inner_path_rows(Path *path) @@ -1426,6 +1492,16 @@ nestloop_inner_path_rows(Path *path) result += nestloop_inner_path_rows((Path *) lfirst(l)); } } + else if (IsA(path, MergeAppendPath)) + { + ListCell *l; + + result = 0; + foreach(l, ((MergeAppendPath *) path)->subpaths) + { + result += nestloop_inner_path_rows((Path *) lfirst(l)); + } + } else result = PATH_ROWS(path); diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index a20ed5f36c..e44e960b54 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -1611,8 +1611,8 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2) * Search for EC members that reference (only) the parent_rel, and * add transformed members referencing the child_rel. * - * We only need to do this for ECs that could generate join conditions, - * since the child members are only used for creating inner-indexscan paths. + * Note that this function won't be called at all unless we have at least some + * reason to believe that the EC members it generates will be useful. * * parent_rel and child_rel could be derived from appinfo, but since the * caller has already computed them, we might as well just pass them in. @@ -1631,10 +1631,14 @@ add_child_rel_equivalences(PlannerInfo *root, ListCell *lc2; /* - * Won't generate joinclauses if const or single-member (the latter - * test covers the volatile case too) + * If this EC contains a constant, then it's not useful for sorting + * or driving an inner index-scan, so we skip generating child EMs. + * + * If this EC contains a volatile expression, then generating child + * EMs would be downright dangerous. We rely on a volatile EC having + * only one EM. */ - if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1) + if (cur_ec->ec_has_const || cur_ec->ec_has_volatile) continue; /* No point in searching if parent rel not mentioned in eclass */ diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 2c398d2eed..52dd27b158 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -25,6 +25,7 @@ #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" +#include "optimizer/paths.h" #include "optimizer/plancat.h" #include "optimizer/planmain.h" #include "optimizer/predtest.h" @@ -45,6 +46,7 @@ static void disuse_physical_tlist(Plan *plan, Path *path); static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals); static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path); static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path); +static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path); static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path); static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path); static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path); @@ -134,6 +136,13 @@ static MergeJoin *make_mergejoin(List *tlist, static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols, AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst, double limit_tuples); +static Plan *prepare_sort_from_pathkeys(PlannerInfo *root, + Plan *lefttree, List *pathkeys, + bool adjust_tlist_in_place, + int *p_numsortkeys, + AttrNumber **p_sortColIdx, + Oid **p_sortOperators, + bool **p_nullsFirst); static Material *make_material(Plan *lefttree); @@ -203,6 +212,10 @@ create_plan_recurse(PlannerInfo *root, Path *best_path) plan = create_append_plan(root, (AppendPath *) best_path); break; + case T_MergeAppend: + plan = create_merge_append_plan(root, + (MergeAppendPath *) best_path); + break; case T_Result: plan = (Plan *) create_result_plan(root, (ResultPath *) best_path); @@ -620,6 +633,97 @@ create_append_plan(PlannerInfo *root, AppendPath *best_path) } /* + * create_merge_append_plan + * Create a MergeAppend plan for 'best_path' and (recursively) plans + * for its subpaths. + * + * Returns a Plan node. + */ +static Plan * +create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path) +{ + MergeAppend *node = makeNode(MergeAppend); + Plan *plan = &node->plan; + List *tlist = build_relation_tlist(best_path->path.parent); + List *pathkeys = best_path->path.pathkeys; + List *subplans = NIL; + ListCell *subpaths; + + /* + * We don't have the actual creation of the MergeAppend node split out + * into a separate make_xxx function. This is because we want to run + * prepare_sort_from_pathkeys on it before we do so on the individual + * child plans, to make cross-checking the sort info easier. + */ + copy_path_costsize(plan, (Path *) best_path); + plan->targetlist = tlist; + plan->qual = NIL; + plan->lefttree = NULL; + plan->righttree = NULL; + + /* Compute sort column info, and adjust MergeAppend's tlist as needed */ + (void) prepare_sort_from_pathkeys(root, plan, pathkeys, + true, + &node->numCols, + &node->sortColIdx, + &node->sortOperators, + &node->nullsFirst); + + /* + * Now prepare the child plans. We must apply prepare_sort_from_pathkeys + * even to subplans that don't need an explicit sort, to make sure they + * are returning the same sort key columns the MergeAppend expects. + */ + foreach(subpaths, best_path->subpaths) + { + Path *subpath = (Path *) lfirst(subpaths); + Plan *subplan; + int numsortkeys; + AttrNumber *sortColIdx; + Oid *sortOperators; + bool *nullsFirst; + + /* Build the child plan */ + subplan = create_plan_recurse(root, subpath); + + /* Compute sort column info, and adjust subplan's tlist as needed */ + subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys, + false, + &numsortkeys, + &sortColIdx, + &sortOperators, + &nullsFirst); + + /* + * Check that we got the same sort key information. We just Assert + * that the sortops match, since those depend only on the pathkeys; + * but it seems like a good idea to check the sort column numbers + * explicitly, to ensure the tlists really do match up. + */ + Assert(numsortkeys == node->numCols); + if (memcmp(sortColIdx, node->sortColIdx, + numsortkeys * sizeof(AttrNumber)) != 0) + elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend"); + Assert(memcmp(sortOperators, node->sortOperators, + numsortkeys * sizeof(Oid)) == 0); + Assert(memcmp(nullsFirst, node->nullsFirst, + numsortkeys * sizeof(bool)) == 0); + + /* Now, insert a Sort node if subplan isn't sufficiently ordered */ + if (!pathkeys_contained_in(pathkeys, subpath->pathkeys)) + subplan = (Plan *) make_sort(root, subplan, numsortkeys, + sortColIdx, sortOperators, nullsFirst, + -1.0); + + subplans = lappend(subplans, subplan); + } + + node->mergeplans = subplans; + + return (Plan *) node; +} + +/* * create_result_plan * Create a Result plan for 'best_path'. * This is only used for the case of a query with an empty jointree. @@ -2502,7 +2606,7 @@ order_qual_clauses(PlannerInfo *root, List *clauses) /* * Copy cost and size info from a Path node to the Plan node created from it. - * The executor won't use this info, but it's needed by EXPLAIN. + * The executor usually won't use this info, but it's needed by EXPLAIN. */ static void copy_path_costsize(Plan *dest, Path *src) @@ -2525,9 +2629,7 @@ copy_path_costsize(Plan *dest, Path *src) /* * Copy cost and size info from a lower plan node to an inserted node. - * This is not critical, since the decisions have already been made, - * but it helps produce more reasonable-looking EXPLAIN output. - * (Some callers alter the info after copying it.) + * (Most callers alter the info after copying it.) */ static void copy_plan_costsize(Plan *dest, Plan *src) @@ -2796,6 +2898,12 @@ make_append(List *appendplans, List *tlist) * Compute cost as sum of subplan costs. We charge nothing extra for the * Append itself, which perhaps is too optimistic, but since it doesn't do * any selection or projection, it is a pretty cheap node. + * + * If you change this, see also create_append_path(). Also, the size + * calculations should match set_append_rel_pathlist(). It'd be better + * not to duplicate all this logic, but some callers of this function + * aren't working from an appendrel or AppendPath, so there's noplace + * to copy the data from. */ plan->startup_cost = 0; plan->total_cost = 0; @@ -3102,26 +3210,41 @@ add_sort_column(AttrNumber colIdx, Oid sortOp, bool nulls_first, } /* - * make_sort_from_pathkeys - * Create sort plan to sort according to given pathkeys + * prepare_sort_from_pathkeys + * Prepare to sort according to given pathkeys + * + * This is used to set up for both Sort and MergeAppend nodes. It calculates + * the executor's representation of the sort key information, and adjusts the + * plan targetlist if needed to add resjunk sort columns. * + * Input parameters: * 'lefttree' is the node which yields input tuples * 'pathkeys' is the list of pathkeys by which the result is to be sorted - * 'limit_tuples' is the bound on the number of output tuples; - * -1 if no bound + * 'adjust_tlist_in_place' is TRUE if lefttree must be modified in-place * * We must convert the pathkey information into arrays of sort key column - * numbers and sort operator OIDs. + * numbers and sort operator OIDs, which is the representation the executor + * wants. These are returned into the output parameters *p_numsortkeys etc. * * If the pathkeys include expressions that aren't simple Vars, we will * usually need to add resjunk items to the input plan's targetlist to - * compute these expressions (since the Sort node itself won't do it). - * If the input plan type isn't one that can do projections, this means - * adding a Result node just to do the projection. + * compute these expressions, since the Sort/MergeAppend node itself won't + * do any such calculations. If the input plan type isn't one that can do + * projections, this means adding a Result node just to do the projection. + * However, the caller can pass adjust_tlist_in_place = TRUE to force the + * lefttree tlist to be modified in-place regardless of whether the node type + * can project --- we use this for fixing the tlist of MergeAppend itself. + * + * Returns the node which is to be the input to the Sort (either lefttree, + * or a Result stacked atop lefttree). */ -Sort * -make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, - double limit_tuples) +static Plan * +prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, + bool adjust_tlist_in_place, + int *p_numsortkeys, + AttrNumber **p_sortColIdx, + Oid **p_sortOperators, + bool **p_nullsFirst) { List *tlist = lefttree->targetlist; ListCell *i; @@ -3185,7 +3308,12 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, { EquivalenceMember *em = (EquivalenceMember *) lfirst(j); - if (em->em_is_const || em->em_is_child) + /* + * We shouldn't be trying to sort by an equivalence class that + * contains a constant, so no need to consider such cases any + * further. + */ + if (em->em_is_const) continue; tle = tlist_member((Node *) em->em_expr, tlist); @@ -3221,7 +3349,7 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, List *exprvars; ListCell *k; - if (em->em_is_const || em->em_is_child) + if (em->em_is_const) continue; sortexpr = em->em_expr; exprvars = pull_var_clause((Node *) sortexpr, @@ -3244,7 +3372,8 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, /* * Do we need to insert a Result node? */ - if (!is_projection_capable_plan(lefttree)) + if (!adjust_tlist_in_place && + !is_projection_capable_plan(lefttree)) { /* copy needed so we don't modify input's tlist below */ tlist = copyObject(tlist); @@ -3252,6 +3381,9 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, lefttree); } + /* Don't bother testing is_projection_capable_plan again */ + adjust_tlist_in_place = true; + /* * Add resjunk entry to input's tlist */ @@ -3292,6 +3424,42 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, Assert(numsortkeys > 0); + /* Return results */ + *p_numsortkeys = numsortkeys; + *p_sortColIdx = sortColIdx; + *p_sortOperators = sortOperators; + *p_nullsFirst = nullsFirst; + + return lefttree; +} + +/* + * make_sort_from_pathkeys + * Create sort plan to sort according to given pathkeys + * + * 'lefttree' is the node which yields input tuples + * 'pathkeys' is the list of pathkeys by which the result is to be sorted + * 'limit_tuples' is the bound on the number of output tuples; + * -1 if no bound + */ +Sort * +make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, + double limit_tuples) +{ + int numsortkeys; + AttrNumber *sortColIdx; + Oid *sortOperators; + bool *nullsFirst; + + /* Compute sort column info, and adjust lefttree as needed */ + lefttree = prepare_sort_from_pathkeys(root, lefttree, pathkeys, + false, + &numsortkeys, + &sortColIdx, + &sortOperators, + &nullsFirst); + + /* Now build the Sort node */ return make_sort(root, lefttree, numsortkeys, sortColIdx, sortOperators, nullsFirst, limit_tuples); } @@ -3998,6 +4166,7 @@ is_projection_capable_plan(Plan *plan) case T_Limit: case T_ModifyTable: case T_Append: + case T_MergeAppend: case T_RecursiveUnion: return false; default: diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index d5e9212f6a..9aef7fc35a 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -554,6 +554,24 @@ set_plan_refs(PlannerGlobal *glob, Plan *plan, int rtoffset) } } break; + case T_MergeAppend: + { + MergeAppend *splan = (MergeAppend *) plan; + + /* + * MergeAppend, like Sort et al, doesn't actually evaluate its + * targetlist or check quals. + */ + set_dummy_tlist_references(plan, rtoffset); + Assert(splan->plan.qual == NIL); + foreach(l, splan->mergeplans) + { + lfirst(l) = set_plan_refs(glob, + (Plan *) lfirst(l), + rtoffset); + } + } + break; case T_RecursiveUnion: /* This doesn't evaluate targetlist or check quals either */ set_dummy_tlist_references(plan, rtoffset); diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index ab62e2a234..137e2ce049 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -2065,6 +2065,22 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params, } break; + case T_MergeAppend: + { + ListCell *l; + + foreach(l, ((MergeAppend *) plan)->mergeplans) + { + context.paramids = + bms_add_members(context.paramids, + finalize_plan(root, + (Plan *) lfirst(l), + valid_params, + scan_params)); + } + } + break; + case T_BitmapAnd: { ListCell *l; diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 71e0e75a56..8214acc571 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -636,6 +636,8 @@ create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals) * create_append_path * Creates a path corresponding to an Append plan, returning the * pathnode. + * + * Note that we must handle subpaths = NIL, representing a dummy access path. */ AppendPath * create_append_path(RelOptInfo *rel, List *subpaths) @@ -649,6 +651,13 @@ create_append_path(RelOptInfo *rel, List *subpaths) * unsorted */ pathnode->subpaths = subpaths; + /* + * Compute cost as sum of subplan costs. We charge nothing extra for the + * Append itself, which perhaps is too optimistic, but since it doesn't do + * any selection or projection, it is a pretty cheap node. + * + * If you change this, see also make_append(). + */ pathnode->path.startup_cost = 0; pathnode->path.total_cost = 0; foreach(l, subpaths) @@ -664,6 +673,68 @@ create_append_path(RelOptInfo *rel, List *subpaths) } /* + * create_merge_append_path + * Creates a path corresponding to a MergeAppend plan, returning the + * pathnode. + */ +MergeAppendPath * +create_merge_append_path(PlannerInfo *root, + RelOptInfo *rel, + List *subpaths, + List *pathkeys) +{ + MergeAppendPath *pathnode = makeNode(MergeAppendPath); + Cost input_startup_cost; + Cost input_total_cost; + ListCell *l; + + pathnode->path.pathtype = T_MergeAppend; + pathnode->path.parent = rel; + pathnode->path.pathkeys = pathkeys; + pathnode->subpaths = subpaths; + + /* Add up all the costs of the input paths */ + input_startup_cost = 0; + input_total_cost = 0; + foreach(l, subpaths) + { + Path *subpath = (Path *) lfirst(l); + + if (pathkeys_contained_in(pathkeys, subpath->pathkeys)) + { + /* Subpath is adequately ordered, we won't need to sort it */ + input_startup_cost += subpath->startup_cost; + input_total_cost += subpath->total_cost; + } + else + { + /* We'll need to insert a Sort node, so include cost for that */ + Path sort_path; /* dummy for result of cost_sort */ + + cost_sort(&sort_path, + root, + pathkeys, + subpath->total_cost, + subpath->parent->tuples, + subpath->parent->width, + 0.0, + work_mem, + -1.0); + input_startup_cost += sort_path.startup_cost; + input_total_cost += sort_path.total_cost; + } + } + + /* Now we can compute total costs of the MergeAppend */ + cost_merge_append(&pathnode->path, root, + pathkeys, list_length(subpaths), + input_startup_cost, input_total_cost, + rel->tuples); + + return pathnode; +} + +/* * create_result_path * Creates a path representing a Result-and-nothing-else plan. * This is only used for the case of a query with an empty jointree. |