X-Git-Url: https://granicus.if.org/sourcecode?a=blobdiff_plain;f=src%2Fbackend%2Foptimizer%2Fpath%2Fallpaths.c;h=458dae0489c029bd743c75c82f8e5102067e89bf;hb=46c508fbcf98ac334f1e831d21021d731c882fbb;hp=aa9a90cbfa2e67ef572b683f9b8938725ff271b8;hpb=11cad29c91524aac1d0b61e0ea0357398ab79bf8;p=postgresql diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index aa9a90cbfa..458dae0489 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3,7 +3,7 @@ * allpaths.c * Routines to find possible search paths for processing a query * - * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group + * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * @@ -17,6 +17,8 @@ #include +#include "catalog/pg_class.h" +#include "foreign/fdwapi.h" #include "nodes/nodeFuncs.h" #ifdef OPTIMIZER_DEBUG #include "nodes/print.h" @@ -34,6 +36,7 @@ #include "parser/parse_clause.h" #include "parser/parsetree.h" #include "rewrite/rewriteManip.h" +#include "utils/lsyscache.h" /* These parameters are set by GUC */ @@ -44,13 +47,27 @@ int geqo_threshold; join_search_hook_type join_search_hook = NULL; +static void set_base_rel_sizes(PlannerInfo *root); static void set_base_rel_pathlists(PlannerInfo *root); +static void set_rel_size(PlannerInfo *root, RelOptInfo *rel, + Index rti, RangeTblEntry *rte); static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte); +static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, + RangeTblEntry *rte); static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte); +static void set_foreign_size(PlannerInfo *root, RelOptInfo *rel, + RangeTblEntry *rte); +static void set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel, + RangeTblEntry *rte); +static void set_append_rel_size(PlannerInfo *root, RelOptInfo *rel, + Index rti, RangeTblEntry *rte); static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte); +static void generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel, + List *live_childrels, + List *all_child_pathkeys); 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, @@ -87,10 +104,33 @@ RelOptInfo * make_one_rel(PlannerInfo *root, List *joinlist) { RelOptInfo *rel; + Index rti; + + /* + * Construct the all_baserels Relids set. + */ + root->all_baserels = NULL; + for (rti = 1; rti < root->simple_rel_array_size; rti++) + { + RelOptInfo *brel = root->simple_rel_array[rti]; + + /* there may be empty slots corresponding to non-baserel RTEs */ + if (brel == NULL) + continue; + + Assert(brel->relid == rti); /* sanity check on array */ + + /* ignore RTEs that are "other rels" */ + if (brel->reloptkind != RELOPT_BASEREL) + continue; + + root->all_baserels = bms_add_member(root->all_baserels, brel->relid); + } /* * Generate access paths for the base rels. */ + set_base_rel_sizes(root); set_base_rel_pathlists(root); /* @@ -101,33 +141,39 @@ make_one_rel(PlannerInfo *root, List *joinlist) /* * The result should join all and only the query's base rels. */ -#ifdef USE_ASSERT_CHECKING - { - int num_base_rels = 0; - Index rti; + Assert(bms_equal(rel->relids, root->all_baserels)); - for (rti = 1; rti < root->simple_rel_array_size; rti++) - { - RelOptInfo *brel = root->simple_rel_array[rti]; + return rel; +} - if (brel == NULL) - continue; +/* + * set_base_rel_sizes + * Set the size estimates (rows and widths) for each base-relation entry. + * + * We do this in a separate pass over the base rels so that rowcount + * estimates are available for parameterized path generation. + */ +static void +set_base_rel_sizes(PlannerInfo *root) +{ + Index rti; - Assert(brel->relid == rti); /* sanity check on array */ + for (rti = 1; rti < root->simple_rel_array_size; rti++) + { + RelOptInfo *rel = root->simple_rel_array[rti]; - /* ignore RTEs that are "other rels" */ - if (brel->reloptkind != RELOPT_BASEREL) - continue; + /* there may be empty slots corresponding to non-baserel RTEs */ + if (rel == NULL) + continue; - Assert(bms_is_member(rti, rel->relids)); - num_base_rels++; - } + Assert(rel->relid == rti); /* sanity check on array */ - Assert(bms_num_members(rel->relids) == num_base_rels); - } -#endif + /* ignore RTEs that are "other rels" */ + if (rel->reloptkind != RELOPT_BASEREL) + continue; - return rel; + set_rel_size(root, rel, rti, root->simple_rte_array[rti]); + } } /* @@ -160,46 +206,135 @@ set_base_rel_pathlists(PlannerInfo *root) } /* - * set_rel_pathlist - * Build access paths for a base relation + * set_rel_size + * Set size estimates for a base relation */ static void -set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, - Index rti, RangeTblEntry *rte) +set_rel_size(PlannerInfo *root, RelOptInfo *rel, + Index rti, RangeTblEntry *rte) { - if (rte->inh) + if (rel->reloptkind == RELOPT_BASEREL && + relation_excluded_by_constraints(root, rel, rte)) { - /* It's an "append relation", process accordingly */ - set_append_rel_pathlist(root, rel, rti, rte); + /* + * We proved we don't need to scan the rel via constraint exclusion, + * so set up a single dummy path for it. Here we only check this for + * regular baserels; if it's an otherrel, CE was already checked in + * set_append_rel_pathlist(). + * + * In this case, we go ahead and set up the relation's path right away + * instead of leaving it for set_rel_pathlist to do. This is because + * we don't have a convention for marking a rel as dummy except by + * assigning a dummy path to it. + */ + set_dummy_rel_pathlist(rel); } - else if (rel->rtekind == RTE_SUBQUERY) + else if (rte->inh) { - /* Subquery --- generate a separate plan for it */ - set_subquery_pathlist(root, rel, rti, rte); + /* It's an "append relation", process accordingly */ + set_append_rel_size(root, rel, rti, rte); } - else if (rel->rtekind == RTE_FUNCTION) + else { - /* RangeFunction --- generate a suitable path for it */ - set_function_pathlist(root, rel, rte); + switch (rel->rtekind) + { + case RTE_RELATION: + if (rte->relkind == RELKIND_FOREIGN_TABLE) + { + /* Foreign table */ + set_foreign_size(root, rel, rte); + } + else + { + /* Plain relation */ + set_plain_rel_size(root, rel, rte); + } + break; + case RTE_SUBQUERY: + + /* + * Subqueries don't support making a choice between + * parameterized and unparameterized paths, so just go ahead + * and build their paths immediately. + */ + set_subquery_pathlist(root, rel, rti, rte); + break; + case RTE_FUNCTION: + set_function_size_estimates(root, rel); + break; + case RTE_VALUES: + set_values_size_estimates(root, rel); + break; + case RTE_CTE: + + /* + * CTEs don't support making a choice between parameterized + * and unparameterized paths, so just go ahead and build their + * paths immediately. + */ + if (rte->self_reference) + set_worktable_pathlist(root, rel, rte); + else + set_cte_pathlist(root, rel, rte); + break; + default: + elog(ERROR, "unexpected rtekind: %d", (int) rel->rtekind); + break; + } } - else if (rel->rtekind == RTE_VALUES) +} + +/* + * set_rel_pathlist + * Build access paths for a base relation + */ +static void +set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, + Index rti, RangeTblEntry *rte) +{ + if (IS_DUMMY_REL(rel)) { - /* Values list --- generate a suitable path for it */ - set_values_pathlist(root, rel, rte); + /* We already proved the relation empty, so nothing more to do */ } - else if (rel->rtekind == RTE_CTE) + else if (rte->inh) { - /* CTE reference --- generate a suitable path for it */ - if (rte->self_reference) - set_worktable_pathlist(root, rel, rte); - else - set_cte_pathlist(root, rel, rte); + /* It's an "append relation", process accordingly */ + set_append_rel_pathlist(root, rel, rti, rte); } else { - /* Plain relation */ - Assert(rel->rtekind == RTE_RELATION); - set_plain_rel_pathlist(root, rel, rte); + switch (rel->rtekind) + { + case RTE_RELATION: + if (rte->relkind == RELKIND_FOREIGN_TABLE) + { + /* Foreign table */ + set_foreign_pathlist(root, rel, rte); + } + else + { + /* Plain relation */ + set_plain_rel_pathlist(root, rel, rte); + } + break; + case RTE_SUBQUERY: + /* Subquery --- fully handled during set_rel_size */ + break; + case RTE_FUNCTION: + /* RangeFunction */ + set_function_pathlist(root, rel, rte); + break; + case RTE_VALUES: + /* Values list */ + set_values_pathlist(root, rel, rte); + break; + case RTE_CTE: + /* CTE reference --- fully handled during set_rel_size */ + break; + default: + elog(ERROR, "unexpected rtekind: %d", (int) rel->rtekind); + break; + } } #ifdef OPTIMIZER_DEBUG @@ -208,25 +343,12 @@ set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, } /* - * set_plain_rel_pathlist - * Build access paths for a plain relation (no subquery, no inheritance) + * set_plain_rel_size + * Set size estimates for a plain relation (no subquery, no inheritance) */ static void -set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) +set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) { - /* - * If we can prove we don't need to scan the rel via constraint exclusion, - * set up a single dummy path for it. We only need to check for regular - * baserels; if it's an otherrel, CE was already checked in - * set_append_rel_pathlist(). - */ - if (rel->reloptkind == RELOPT_BASEREL && - relation_excluded_by_constraints(root, rel, rte)) - { - set_dummy_rel_pathlist(rel); - return; - } - /* * Test any partial indexes of rel for applicability. We must do this * first since partial unique indexes can affect size estimates. @@ -246,17 +368,27 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) check_partial_indexes(root, rel); set_baserel_size_estimates(root, rel); } +} + +/* + * set_plain_rel_pathlist + * Build access paths for a plain relation (no subquery, no inheritance) + */ +static void +set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) +{ + Relids required_outer; /* - * Generate paths and add them to the rel's pathlist. - * - * Note: add_path() will discard any paths that are dominated by another - * available path, keeping only those paths that are superior along at - * least one dimension of cost or sortedness. + * We don't support pushing join clauses into the quals of a seqscan, but + * it could still have required parameterization due to LATERAL refs in + * its tlist. (That can only happen if the seqscan is on a relation + * pulled up out of a UNION ALL appendrel.) */ + required_outer = rel->lateral_relids; /* Consider sequential scan */ - add_path(rel, create_seqscan_path(root, rel)); + add_path(rel, create_seqscan_path(root, rel, required_outer)); /* Consider index scans */ create_index_paths(root, rel); @@ -269,8 +401,39 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) } /* - * set_append_rel_pathlist - * Build access paths for an "append relation" + * set_foreign_size + * Set size estimates for a foreign table RTE + */ +static void +set_foreign_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) +{ + /* Mark rel with estimated output rows, width, etc */ + set_foreign_size_estimates(root, rel); + + /* Get FDW routine pointers for the rel */ + rel->fdwroutine = GetFdwRoutineByRelId(rte->relid); + + /* Let FDW adjust the size estimates, if it can */ + rel->fdwroutine->GetForeignRelSize(root, rel, rte->relid); +} + +/* + * set_foreign_pathlist + * Build access paths for a foreign table RTE + */ +static void +set_foreign_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) +{ + /* Call the FDW's GetForeignPaths function to generate path(s) */ + rel->fdwroutine->GetForeignPaths(root, rel, rte->relid); + + /* Select cheapest path */ + set_cheapest(rel); +} + +/* + * set_append_rel_size + * Set size estimates for an "append relation" * * The passed-in rel and RTE represent the entire append relation. The * relation's contents are computed by appending together the output of @@ -280,13 +443,10 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) * a good thing because their outputs are not the same size. */ static void -set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, - Index rti, RangeTblEntry *rte) +set_append_rel_size(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; @@ -312,10 +472,6 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, nattrs = rel->max_attr - rel->min_attr + 1; parent_attrsizes = (double *) palloc0(nattrs * sizeof(double)); - /* - * Generate access paths for each member relation, and pick the cheapest - * path for each one. - */ foreach(l, root->append_rel_list) { AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l); @@ -324,7 +480,6 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RelOptInfo *childrel; List *childquals; Node *childqual; - ListCell *lcp; ListCell *parentvars; ListCell *childvars; @@ -357,7 +512,8 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, * reconstitute the RestrictInfo layer. */ childquals = get_all_actual_clauses(rel->baserestrictinfo); - childquals = (List *) adjust_appendrel_attrs((Node *) childquals, + childquals = (List *) adjust_appendrel_attrs(root, + (Node *) childquals, appinfo); childqual = eval_const_expressions(root, (Node *) make_ands_explicit(childquals)); @@ -381,28 +537,37 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, { /* * This child need not be scanned, so we can omit it from the - * appendrel. Mark it with a dummy cheapest-path though, in case - * best_appendrel_indexscan() looks at it later. + * appendrel. */ set_dummy_rel_pathlist(childrel); continue; } - /* CE failed, so finish copying targetlist and join quals */ + /* + * CE failed, so finish copying/modifying targetlist and join quals. + * + * Note: the resulting childrel->reltargetlist may contain arbitrary + * expressions, which otherwise would not occur in a reltargetlist. + * Code that might be looking at an appendrel child must cope with + * such. Note in particular that "arbitrary expression" can include + * "Var belonging to another relation", due to LATERAL references. + */ childrel->joininfo = (List *) - adjust_appendrel_attrs((Node *) rel->joininfo, + adjust_appendrel_attrs(root, + (Node *) rel->joininfo, appinfo); childrel->reltargetlist = (List *) - adjust_appendrel_attrs((Node *) rel->reltargetlist, + adjust_appendrel_attrs(root, + (Node *) rel->reltargetlist, appinfo); /* * We have to make child entries in the EquivalenceClass data - * 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). + * 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 || has_useful_pathkeys(root, rel)) add_child_rel_equivalences(root, appinfo, rel, childrel); @@ -416,78 +581,58 @@ 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. + * Compute the child's size. */ - set_rel_pathlist(root, childrel, childRTindex, childRTE); - - subpaths = accumulate_append_subpath(subpaths, - childrel->cheapest_total_path); + set_rel_size(root, childrel, childRTindex, childRTE); /* - * 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. + * It is possible that constraint exclusion detected a contradiction + * within a child subquery, even though we didn't prove one above. If + * so, we can skip this child. */ - 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); - } - } + if (IS_DUMMY_REL(childrel)) + continue; /* - * Accumulate size information from each child. + * Accumulate size information from each live child. */ if (childrel->rows > 0) { parent_rows += childrel->rows; parent_size += childrel->width * childrel->rows; + /* + * Accumulate per-column estimates too. We need not do anything + * for PlaceHolderVars in the parent list. If child expression + * isn't a Var, or we didn't record a width estimate for it, we + * have to fall back on a datatype-based estimate. + * + * By construction, child's reltargetlist is 1-to-1 with parent's. + */ forboth(parentvars, rel->reltargetlist, childvars, childrel->reltargetlist) { Var *parentvar = (Var *) lfirst(parentvars); - Var *childvar = (Var *) lfirst(childvars); + Node *childvar = (Node *) lfirst(childvars); - /* - * Accumulate per-column estimates too. Whole-row Vars and - * PlaceHolderVars can be ignored here. - */ - if (IsA(parentvar, Var) && - IsA(childvar, Var)) + if (IsA(parentvar, Var)) { int pndx = parentvar->varattno - rel->min_attr; - int cndx = childvar->varattno - childrel->min_attr; - - parent_attrsizes[pndx] += childrel->attr_widths[cndx] * childrel->rows; + int32 child_width = 0; + + if (IsA(childvar, Var) && + ((Var *) childvar)->varno == childrel->relid) + { + int cndx = ((Var *) childvar)->varattno - childrel->min_attr; + + child_width = childrel->attr_widths[cndx]; + } + if (child_width <= 0) + child_width = get_typavgwidth(exprType(childvar), + exprTypmod(childvar)); + Assert(child_width > 0); + parent_attrsizes[pndx] += child_width * childrel->rows; } } } @@ -515,28 +660,249 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, rel->tuples = parent_rows; pfree(parent_attrsizes); +} + +/* + * set_append_rel_pathlist + * Build access paths for an "append relation" + */ +static void +set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, + Index rti, RangeTblEntry *rte) +{ + 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; /* - * 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.) + * Generate access paths for each member relation, and remember the + * cheapest path for each one. Also, identify all pathkeys (orderings) + * and parameterizations (required_outer sets) available for the member + * relations. */ - add_path(rel, (Path *) create_append_path(rel, subpaths)); + foreach(l, root->append_rel_list) + { + AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l); + int childRTindex; + RangeTblEntry *childRTE; + RelOptInfo *childrel; + ListCell *lcp; + + /* append_rel_list contains all append rels; ignore others */ + if (appinfo->parent_relid != parentRTindex) + continue; + + /* Re-locate the child RTE and RelOptInfo */ + childRTindex = appinfo->child_relid; + childRTE = root->simple_rte_array[childRTindex]; + childrel = root->simple_rel_array[childRTindex]; + + /* + * Compute the child's access paths. + */ + set_rel_pathlist(root, childrel, childRTindex, childRTE); + + /* + * If child is dummy, ignore it. + */ + if (IS_DUMMY_REL(childrel)) + continue; + + /* + * Child is live, so add it to the live_childrels list for use 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 + * should build Append and MergeAppend paths for. + */ + foreach(lcp, childrel->pathlist) + { + Path *childpath = (Path *) lfirst(lcp); + List *childkeys = childpath->pathkeys; + Relids childouter = PATH_REQ_OUTER(childpath); + + /* Unsorted paths don't contribute to pathkey list */ + if (childkeys != NIL) + { + ListCell *lpk; + bool found = false; + + /* 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); + } + } + + /* Unparameterized paths don't contribute to param-set list */ + if (childouter) + { + ListCell *lco; + bool found = false; + + /* Have we already seen this param set? */ + foreach(lco, all_child_outers) + { + Relids existing_outers = (Relids) lfirst(lco); + + if (bms_equal(existing_outers, childouter)) + { + found = true; + break; + } + } + if (!found) + { + /* No, so add it to all_child_outers */ + all_child_outers = lappend(all_child_outers, + childouter); + } + } + } + } /* - * 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. + * 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.) */ - foreach(l, all_child_pathkeys) + if (subpaths_valid) + add_path(rel, (Path *) create_append_path(rel, subpaths, NULL)); + + /* + * Also build unparameterized MergeAppend paths based on the collected + * list of 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. + * (This may look pretty expensive, but in most cases of practical + * interest, the child rels will expose mostly the same parameterizations, + * so that not that many cases actually get considered here.) + * + * The Append node itself cannot enforce quals, so all qual checking must + * be done in the child paths. This means that to have a parameterized + * Append path, we must have the exact same parameterization for each + * child path; otherwise some children might be failing to check the + * moved-down quals. To make them match up, we can try to increase the + * parameterization of lesser-parameterized paths. + */ + foreach(l, all_child_outers) + { + Relids required_outer = (Relids) lfirst(l); + 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); + + /* Children must have exactly the desired parameterization */ + if (!bms_equal(PATH_REQ_OUTER(cheapest_total), required_outer)) + { + cheapest_total = reparameterize_path(root, cheapest_total, + required_outer, 1.0); + if (cheapest_total == NULL) + { + subpaths_valid = false; + break; + } + } + + subpaths = accumulate_append_subpath(subpaths, cheapest_total); + } + + if (subpaths_valid) + add_path(rel, (Path *) + create_append_path(rel, subpaths, required_outer)); + } + + /* Select cheapest paths */ + set_cheapest(rel); +} + +/* + * generate_mergeappend_paths + * Generate MergeAppend paths for an append relation + * + * Generate a path for each ordering (pathkey list) appearing in + * all_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 case. + * + * We don't currently generate any parameterized MergeAppend paths. While + * it would not take much more code here to do so, it's very unclear that it + * is worth the planning cycles to investigate such paths: there's little + * use for an ordered path on the inside of a nestloop. In fact, it's likely + * that the current coding of add_path would reject such paths out of hand, + * because add_path gives no credit for sort ordering of parameterized paths, + * and a parameterized MergeAppend is going to be more expensive than the + * corresponding parameterized Append path. If we ever try harder to support + * parameterized mergejoin plans, it might be worth adding support for + * parameterized MergeAppends to feed such joins. (See notes in + * optimizer/README for why that might not ever happen, though.) + */ +static void +generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel, + List *live_childrels, + List *all_child_pathkeys) +{ + ListCell *lcp; + + foreach(lcp, all_child_pathkeys) { - List *pathkeys = (List *) lfirst(l); - List *startup_subpaths = NIL; - List *total_subpaths = NIL; - bool startup_neq_total = false; - ListCell *lcr; + List *pathkeys = (List *) lfirst(lcp); + 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) @@ -549,25 +915,30 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, cheapest_startup = get_cheapest_path_for_pathkeys(childrel->pathlist, pathkeys, + NULL, STARTUP_COST); cheapest_total = get_cheapest_path_for_pathkeys(childrel->pathlist, pathkeys, + NULL, 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 we can't find any paths with the right order just use the + * cheapest-total path; we'll have to sort it later. */ - if (cheapest_startup == NULL) - cheapest_startup = childrel->cheapest_total_path; - if (cheapest_total == NULL) - cheapest_total = childrel->cheapest_total_path; + if (cheapest_startup == NULL || cheapest_total == NULL) + { + cheapest_startup = cheapest_total = + childrel->cheapest_total_path; + /* Assert we do have an unparameterized path for this child */ + Assert(cheapest_total->param_info == NULL); + } /* * 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. + * "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; @@ -582,16 +953,15 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, add_path(rel, (Path *) create_merge_append_path(root, rel, startup_subpaths, - pathkeys)); + pathkeys, + NULL)); if (startup_neq_total) add_path(rel, (Path *) create_merge_append_path(root, rel, total_subpaths, - pathkeys)); + pathkeys, + NULL)); } - - /* Select cheapest path */ - set_cheapest(rel); } /* @@ -608,7 +978,7 @@ accumulate_append_subpath(List *subpaths, Path *path) { if (IsA(path, AppendPath)) { - AppendPath *apath = (AppendPath *) path; + AppendPath *apath = (AppendPath *) path; /* list_copy is important here to avoid sharing list substructure */ return list_concat(subpaths, list_copy(apath->subpaths)); @@ -622,7 +992,7 @@ accumulate_append_subpath(List *subpaths, Path *path) * Build a dummy path for a relation that's been excluded by constraints * * Rather than inventing a special "dummy" path type, we represent this as an - * AppendPath with no members (see also IS_DUMMY_PATH macro). + * AppendPath with no members (see also IS_DUMMY_PATH/IS_DUMMY_REL macros). */ static void set_dummy_rel_pathlist(RelOptInfo *rel) @@ -631,7 +1001,10 @@ set_dummy_rel_pathlist(RelOptInfo *rel) rel->rows = 0; rel->width = 0; - add_path(rel, (Path *) create_append_path(rel, NIL)); + /* Discard any pre-existing paths; no further need for them */ + rel->pathlist = NIL; + + add_path(rel, (Path *) create_append_path(rel, NIL, NULL)); /* Select cheapest path (pretty easy in this case...) */ set_cheapest(rel); @@ -662,6 +1035,14 @@ has_multiple_baserels(PlannerInfo *root) /* * set_subquery_pathlist * Build the (single) access path for a subquery RTE + * + * We don't currently support generating parameterized paths for subqueries + * by pushing join clauses down into them; it seems too expensive to re-plan + * the subquery multiple times to consider different alternatives. So the + * subquery will have exactly one path. (The path will be parameterized + * if the subquery contains LATERAL references, otherwise not.) Since there's + * no freedom of action here, there's no need for a separate set_subquery_size + * phase: we just make the path right away. */ static void set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, @@ -669,6 +1050,7 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, { Query *parse = root->parse; Query *subquery = rte->subquery; + Relids required_outer; bool *differentTypes; double tuple_fraction; PlannerInfo *subroot; @@ -681,6 +1063,13 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, */ subquery = copyObject(subquery); + /* + * If it's a LATERAL subquery, it might contain some Vars of the current + * query level, requiring it to be treated as parameterized, even though + * we don't support pushing down join quals into subqueries. + */ + required_outer = rel->lateral_relids; + /* We need a workspace for keeping track of set-op type coercions */ differentTypes = (bool *) palloc0((list_length(subquery->targetList) + 1) * sizeof(bool)); @@ -699,6 +1088,10 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, * pseudoconstant clauses; better to have the gating node above the * subquery. * + * Also, if the sub-query has the "security_barrier" flag, it means the + * sub-query originated from a view that must enforce row-level security. + * Then we must not push down quals that contain leaky functions. + * * Non-pushed-down clauses will get evaluated as qpquals of the * SubqueryScan node. * @@ -718,6 +1111,8 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, Node *clause = (Node *) rinfo->clause; if (!rinfo->pseudoconstant && + (!rte->security_barrier || + !contain_leaky_functions(clause)) && qual_is_pushdown_safe(subquery, rti, clause, differentTypes)) { /* Push it down */ @@ -750,25 +1145,39 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, else tuple_fraction = root->tuple_fraction; + /* plan_params should not be in use in current query level */ + Assert(root->plan_params == NIL); + /* Generate the plan for the subquery */ rel->subplan = subquery_planner(root->glob, subquery, root, false, tuple_fraction, &subroot); - rel->subrtable = subroot->parse->rtable; - rel->subrowmark = subroot->rowMarks; + rel->subroot = subroot; - /* Copy number of output rows from subplan */ - rel->tuples = rel->subplan->plan_rows; + /* Isolate the params needed by this specific subplan */ + rel->subplan_params = root->plan_params; + root->plan_params = NIL; + + /* + * It's possible that constraint exclusion proved the subquery empty. If + * so, it's convenient to turn it back into a dummy path so that we will + * recognize appropriate optimizations at this level. + */ + if (is_dummy_plan(rel->subplan)) + { + set_dummy_rel_pathlist(rel); + return; + } /* Mark rel with estimated output rows, width, etc */ - set_baserel_size_estimates(root, rel); + set_subquery_size_estimates(root, rel); /* Convert subquery pathkeys to outer representation */ pathkeys = convert_subquery_pathkeys(root, rel, subroot->query_pathkeys); /* Generate appropriate path */ - add_path(rel, create_subqueryscan_path(rel, pathkeys)); + add_path(rel, create_subqueryscan_path(root, rel, pathkeys, required_outer)); /* Select cheapest path (pretty easy in this case...) */ set_cheapest(rel); @@ -781,11 +1190,17 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, static void set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) { - /* Mark rel with estimated output rows, width, etc */ - set_function_size_estimates(root, rel); + Relids required_outer; + + /* + * We don't support pushing join clauses into the quals of a function + * scan, but it could still have required parameterization due to LATERAL + * refs in the function expression. + */ + required_outer = rel->lateral_relids; /* Generate appropriate path */ - add_path(rel, create_functionscan_path(root, rel)); + add_path(rel, create_functionscan_path(root, rel, required_outer)); /* Select cheapest path (pretty easy in this case...) */ set_cheapest(rel); @@ -798,11 +1213,17 @@ set_function_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) static void set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) { - /* Mark rel with estimated output rows, width, etc */ - set_values_size_estimates(root, rel); + Relids required_outer; + + /* + * We don't support pushing join clauses into the quals of a values scan, + * but it could still have required parameterization due to LATERAL refs + * in the values expressions. + */ + required_outer = rel->lateral_relids; /* Generate appropriate path */ - add_path(rel, create_valuesscan_path(root, rel)); + add_path(rel, create_valuesscan_path(root, rel, required_outer)); /* Select cheapest path (pretty easy in this case...) */ set_cheapest(rel); @@ -811,6 +1232,9 @@ set_values_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) /* * set_cte_pathlist * Build the (single) access path for a non-self-reference CTE RTE + * + * There's no need for a separate set_cte_size phase, since we don't + * support join-qual-parameterized paths for CTEs. */ static void set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) @@ -821,6 +1245,7 @@ set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) int ndx; ListCell *lc; int plan_id; + Relids required_outer; /* * Find the referenced CTE, and locate the plan previously made for it. @@ -859,8 +1284,16 @@ set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) /* Mark rel with estimated output rows, width, etc */ set_cte_size_estimates(root, rel, cteplan); + /* + * We don't support pushing join clauses into the quals of a CTE scan, but + * it could still have required parameterization due to LATERAL refs in + * its tlist. (That can only happen if the CTE scan is on a relation + * pulled up out of a UNION ALL appendrel.) + */ + required_outer = rel->lateral_relids; + /* Generate appropriate path */ - add_path(rel, create_ctescan_path(root, rel)); + add_path(rel, create_ctescan_path(root, rel, required_outer)); /* Select cheapest path (pretty easy in this case...) */ set_cheapest(rel); @@ -869,6 +1302,9 @@ set_cte_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) /* * set_worktable_pathlist * Build the (single) access path for a self-reference CTE RTE + * + * There's no need for a separate set_worktable_size phase, since we don't + * support join-qual-parameterized paths for CTEs. */ static void set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) @@ -876,6 +1312,7 @@ set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) Plan *cteplan; PlannerInfo *cteroot; Index levelsup; + Relids required_outer; /* * We need to find the non-recursive term's plan, which is in the plan @@ -900,8 +1337,18 @@ set_worktable_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) /* Mark rel with estimated output rows, width, etc */ set_cte_size_estimates(root, rel, cteplan); + /* + * We don't support pushing join clauses into the quals of a worktable + * scan, but it could still have required parameterization due to LATERAL + * refs in its tlist. (That can only happen if the worktable scan is on a + * relation pulled up out of a UNION ALL appendrel. I'm not sure this is + * actually possible given the restrictions on recursive references, but + * it's easy enough to support.) + */ + required_outer = rel->lateral_relids; + /* Generate appropriate path */ - add_path(rel, create_worktablescan_path(root, rel)); + add_path(rel, create_worktablescan_path(root, rel, required_outer)); /* Select cheapest path (pretty easy in this case...) */ set_cheapest(rel); @@ -1275,7 +1722,8 @@ qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual, /* * It would be unsafe to push down window function calls, but at least for - * the moment we could never see any in a qual anyhow. + * the moment we could never see any in a qual anyhow. (The same applies + * to aggregates, which we check for in pull_var_clause below.) */ Assert(!contain_window_function(qual)); @@ -1283,7 +1731,9 @@ qual_is_pushdown_safe(Query *subquery, Index rti, Node *qual, * Examine all Vars used in clause; since it's a restriction clause, all * such Vars must refer to subselect output columns. */ - vars = pull_var_clause(qual, PVC_INCLUDE_PLACEHOLDERS); + vars = pull_var_clause(qual, + PVC_REJECT_AGGREGATES, + PVC_INCLUDE_PLACEHOLDERS); foreach(vl, vars) { Var *var = (Var *) lfirst(vl); @@ -1506,6 +1956,9 @@ print_path(PlannerInfo *root, Path *path, int indent) case T_TidPath: ptype = "TidScan"; break; + case T_ForeignPath: + ptype = "ForeignScan"; + break; case T_AppendPath: ptype = "Append"; break; @@ -1616,10 +2069,16 @@ debug_print_rel(PlannerInfo *root, RelOptInfo *rel) printf("\tpath list:\n"); foreach(l, rel->pathlist) print_path(root, lfirst(l), 1); - printf("\n\tcheapest startup path:\n"); - print_path(root, rel->cheapest_startup_path, 1); - printf("\n\tcheapest total path:\n"); - print_path(root, rel->cheapest_total_path, 1); + if (rel->cheapest_startup_path) + { + printf("\n\tcheapest startup path:\n"); + print_path(root, rel->cheapest_startup_path, 1); + } + if (rel->cheapest_total_path) + { + printf("\n\tcheapest total path:\n"); + print_path(root, rel->cheapest_total_path, 1); + } printf("\n"); fflush(stdout); }