diff options
Diffstat (limited to 'src/backend/optimizer/plan')
| -rw-r--r-- | src/backend/optimizer/plan/createplan.c | 235 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/planner.c | 36 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/setrefs.c | 32 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/subselect.c | 168 |
4 files changed, 455 insertions, 16 deletions
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 1195024b5fc..aabbf64a755 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -10,7 +10,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.248 2008/09/05 21:07:29 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.249 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -62,6 +62,10 @@ static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path List *tlist, List *scan_clauses); static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path, List *tlist, List *scan_clauses); +static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses); +static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses); static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path, Plan *outer_plan, Plan *inner_plan); static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path, @@ -93,6 +97,10 @@ static FunctionScan *make_functionscan(List *qptlist, List *qpqual, List *funccoltypes, List *funccoltypmods); static ValuesScan *make_valuesscan(List *qptlist, List *qpqual, Index scanrelid, List *values_lists); +static CteScan *make_ctescan(List *qptlist, List *qpqual, + Index scanrelid, int ctePlanId, int cteParam); +static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual, + Index scanrelid, int wtParam); static BitmapAnd *make_bitmap_and(List *bitmapplans); static BitmapOr *make_bitmap_or(List *bitmapplans); static NestLoop *make_nestloop(List *tlist, @@ -148,6 +156,8 @@ create_plan(PlannerInfo *root, Path *best_path) case T_SubqueryScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: plan = create_scan_plan(root, best_path); break; case T_HashJoin: @@ -270,6 +280,20 @@ create_scan_plan(PlannerInfo *root, Path *best_path) scan_clauses); break; + case T_CteScan: + plan = (Plan *) create_ctescan_plan(root, + best_path, + tlist, + scan_clauses); + break; + + case T_WorkTableScan: + plan = (Plan *) create_worktablescan_plan(root, + best_path, + tlist, + scan_clauses); + break; + default: elog(ERROR, "unrecognized node type: %d", (int) best_path->pathtype); @@ -324,12 +348,13 @@ use_physical_tlist(RelOptInfo *rel) /* * We can do this for real relation scans, subquery scans, function scans, - * and values scans (but not for, eg, joins). + * values scans, and CTE scans (but not for, eg, joins). */ if (rel->rtekind != RTE_RELATION && rel->rtekind != RTE_SUBQUERY && rel->rtekind != RTE_FUNCTION && - rel->rtekind != RTE_VALUES) + rel->rtekind != RTE_VALUES && + rel->rtekind != RTE_CTE) return false; /* @@ -375,6 +400,8 @@ disuse_physical_tlist(Plan *plan, Path *path) case T_SubqueryScan: case T_FunctionScan: case T_ValuesScan: + case T_CteScan: + case T_WorkTableScan: plan->targetlist = build_relation_tlist(path->parent); break; default: @@ -1335,6 +1362,145 @@ create_valuesscan_plan(PlannerInfo *root, Path *best_path, return scan_plan; } +/* + * create_ctescan_plan + * Returns a ctescan plan for the base relation scanned by 'best_path' + * with restriction clauses 'scan_clauses' and targetlist 'tlist'. + */ +static CteScan * +create_ctescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses) +{ + CteScan *scan_plan; + Index scan_relid = best_path->parent->relid; + RangeTblEntry *rte; + SubPlan *ctesplan = NULL; + int plan_id; + int cte_param_id; + PlannerInfo *cteroot; + Index levelsup; + int ndx; + ListCell *lc; + + Assert(scan_relid > 0); + rte = planner_rt_fetch(scan_relid, root); + Assert(rte->rtekind == RTE_CTE); + Assert(!rte->self_reference); + + /* + * Find the referenced CTE, and locate the SubPlan previously made for it. + */ + levelsup = rte->ctelevelsup; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + /* + * Note: cte_plan_ids can be shorter than cteList, if we are still working + * on planning the CTEs (ie, this is a side-reference from another CTE). + * So we mustn't use forboth here. + */ + ndx = 0; + foreach(lc, cteroot->parse->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + + if (strcmp(cte->ctename, rte->ctename) == 0) + break; + ndx++; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find CTE \"%s\"", rte->ctename); + if (ndx >= list_length(cteroot->cte_plan_ids)) + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + plan_id = list_nth_int(cteroot->cte_plan_ids, ndx); + Assert(plan_id > 0); + foreach(lc, cteroot->init_plans) + { + ctesplan = (SubPlan *) lfirst(lc); + if (ctesplan->plan_id == plan_id) + break; + } + if (lc == NULL) /* shouldn't happen */ + elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename); + + /* + * We need the CTE param ID, which is the sole member of the + * SubPlan's setParam list. + */ + cte_param_id = linitial_int(ctesplan->setParam); + + /* Sort clauses into best execution order */ + scan_clauses = order_qual_clauses(root, scan_clauses); + + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); + + scan_plan = make_ctescan(tlist, scan_clauses, scan_relid, + plan_id, cte_param_id); + + copy_path_costsize(&scan_plan->scan.plan, best_path); + + return scan_plan; +} + +/* + * create_worktablescan_plan + * Returns a worktablescan plan for the base relation scanned by 'best_path' + * with restriction clauses 'scan_clauses' and targetlist 'tlist'. + */ +static WorkTableScan * +create_worktablescan_plan(PlannerInfo *root, Path *best_path, + List *tlist, List *scan_clauses) +{ + WorkTableScan *scan_plan; + Index scan_relid = best_path->parent->relid; + RangeTblEntry *rte; + Index levelsup; + PlannerInfo *cteroot; + + Assert(scan_relid > 0); + rte = planner_rt_fetch(scan_relid, root); + Assert(rte->rtekind == RTE_CTE); + Assert(rte->self_reference); + + /* + * We need to find the worktable param ID, which is in the plan level + * that's processing the recursive UNION, which is one level *below* + * where the CTE comes from. + */ + levelsup = rte->ctelevelsup; + if (levelsup == 0) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + levelsup--; + cteroot = root; + while (levelsup-- > 0) + { + cteroot = cteroot->parent_root; + if (!cteroot) /* shouldn't happen */ + elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename); + } + if (cteroot->wt_param_id < 0) /* shouldn't happen */ + elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename); + + /* Sort clauses into best execution order */ + scan_clauses = order_qual_clauses(root, scan_clauses); + + /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */ + scan_clauses = extract_actual_clauses(scan_clauses, false); + + scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid, + cteroot->wt_param_id); + + copy_path_costsize(&scan_plan->scan.plan, best_path); + + return scan_plan; +} + + /***************************************************************************** * * JOIN METHODS @@ -2291,6 +2457,48 @@ make_valuesscan(List *qptlist, return node; } +static CteScan * +make_ctescan(List *qptlist, + List *qpqual, + Index scanrelid, + int ctePlanId, + int cteParam) +{ + CteScan *node = makeNode(CteScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->ctePlanId = ctePlanId; + node->cteParam = cteParam; + + return node; +} + +static WorkTableScan * +make_worktablescan(List *qptlist, + List *qpqual, + Index scanrelid, + int wtParam) +{ + WorkTableScan *node = makeNode(WorkTableScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->wtParam = wtParam; + + return node; +} + Append * make_append(List *appendplans, bool isTarget, List *tlist) { @@ -2333,6 +2541,26 @@ make_append(List *appendplans, bool isTarget, List *tlist) return node; } +RecursiveUnion * +make_recursive_union(List *tlist, + Plan *lefttree, + Plan *righttree, + int wtParam) +{ + RecursiveUnion *node = makeNode(RecursiveUnion); + Plan *plan = &node->plan; + + cost_recursive_union(plan, lefttree, righttree); + + plan->targetlist = tlist; + plan->qual = NIL; + plan->lefttree = lefttree; + plan->righttree = righttree; + node->wtParam = wtParam; + + return node; +} + static BitmapAnd * make_bitmap_and(List *bitmapplans) { @@ -3284,6 +3512,7 @@ is_projection_capable_plan(Plan *plan) case T_SetOp: case T_Limit: case T_Append: + case T_RecursiveUnion: return false; default: break; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index ec2b0f794a0..0a704dc6545 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.243 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.244 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -173,7 +173,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams) } /* primary planning entry point (may recurse for subqueries) */ - top_plan = subquery_planner(glob, parse, 1, tuple_fraction, &root); + top_plan = subquery_planner(glob, parse, NULL, + false, tuple_fraction, &root); /* * If creating a plan for a scrollable cursor, make sure it can run @@ -228,7 +229,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams) * * glob is the global state for the current planner run. * parse is the querytree produced by the parser & rewriter. - * level is the current recursion depth (1 at the top-level Query). + * parent_root is the immediate parent Query's info (NULL at the top level). + * hasRecursion is true if this is a recursive WITH query. * tuple_fraction is the fraction of tuples we expect will be retrieved. * tuple_fraction is interpreted as explained for grouping_planner, below. * @@ -249,7 +251,8 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams) */ Plan * subquery_planner(PlannerGlobal *glob, Query *parse, - Index level, double tuple_fraction, + PlannerInfo *parent_root, + bool hasRecursion, double tuple_fraction, PlannerInfo **subroot) { int num_old_subplans = list_length(glob->subplans); @@ -263,12 +266,28 @@ subquery_planner(PlannerGlobal *glob, Query *parse, root = makeNode(PlannerInfo); root->parse = parse; root->glob = glob; - root->query_level = level; + root->query_level = parent_root ? parent_root->query_level + 1 : 1; + root->parent_root = parent_root; root->planner_cxt = CurrentMemoryContext; root->init_plans = NIL; + root->cte_plan_ids = NIL; root->eq_classes = NIL; root->append_rel_list = NIL; + root->hasRecursion = hasRecursion; + if (hasRecursion) + root->wt_param_id = SS_assign_worktable_param(root); + else + root->wt_param_id = -1; + root->non_recursive_plan = NULL; + + /* + * If there is a WITH list, process each WITH query and build an + * initplan SubPlan structure for it. + */ + if (parse->cteList) + SS_process_ctes(root); + /* * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try * to transform them into joins. Note that this step does not descend @@ -776,7 +795,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) /* * Construct the plan for set operations. The result will not need - * any work except perhaps a top-level sort and/or LIMIT. + * any work except perhaps a top-level sort and/or LIMIT. Note that + * any special work for recursive unions is the responsibility of + * plan_set_operations. */ result_plan = plan_set_operations(root, tuple_fraction, &set_sortclauses); @@ -838,6 +859,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction) MemSet(&agg_counts, 0, sizeof(AggClauseCounts)); + /* A recursive query should always have setOperations */ + Assert(!root->hasRecursion); + /* Preprocess GROUP BY clause, if any */ if (parse->groupClause) preprocess_groupclause(root); diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 18362628727..6d7ec283b34 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.144 2008/09/09 18:58:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/setrefs.c,v 1.145 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -201,11 +201,13 @@ set_plan_references(PlannerGlobal *glob, Plan *plan, List *rtable) /* zap unneeded sub-structure */ newrte->subquery = NULL; + newrte->joinaliasvars = NIL; newrte->funcexpr = NULL; newrte->funccoltypes = NIL; newrte->funccoltypmods = NIL; newrte->values_lists = NIL; - newrte->joinaliasvars = NIL; + newrte->ctecoltypes = NIL; + newrte->ctecoltypmods = NIL; glob->finalrtable = lappend(glob->finalrtable, newrte); @@ -343,7 +345,28 @@ set_plan_refs(PlannerGlobal *glob, Plan *plan, int rtoffset) fix_scan_list(glob, splan->values_lists, rtoffset); } break; + case T_CteScan: + { + CteScan *splan = (CteScan *) plan; + + splan->scan.scanrelid += rtoffset; + splan->scan.plan.targetlist = + fix_scan_list(glob, splan->scan.plan.targetlist, rtoffset); + splan->scan.plan.qual = + fix_scan_list(glob, splan->scan.plan.qual, rtoffset); + } + break; + case T_WorkTableScan: + { + WorkTableScan *splan = (WorkTableScan *) plan; + splan->scan.scanrelid += rtoffset; + splan->scan.plan.targetlist = + fix_scan_list(glob, splan->scan.plan.targetlist, rtoffset); + splan->scan.plan.qual = + fix_scan_list(glob, splan->scan.plan.qual, rtoffset); + } + break; case T_NestLoop: case T_MergeJoin: case T_HashJoin: @@ -434,6 +457,11 @@ set_plan_refs(PlannerGlobal *glob, Plan *plan, int rtoffset) } } break; + case T_RecursiveUnion: + /* This doesn't evaluate targetlist or check quals either */ + set_dummy_tlist_references(plan, rtoffset); + Assert(plan->qual == NIL); + break; case T_BitmapAnd: { BitmapAnd *splan = (BitmapAnd *) plan; diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index fe8be5b1bbb..00d84d56823 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.140 2008/08/28 23:09:46 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.141 2008/10/04 21:56:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -213,6 +213,20 @@ generate_new_param(PlannerInfo *root, Oid paramtype, int32 paramtypmod) } /* + * Assign a (nonnegative) PARAM_EXEC ID for a recursive query's worktable. + */ +int +SS_assign_worktable_param(PlannerInfo *root) +{ + Param *param; + + /* We generate a Param of datatype INTERNAL */ + param = generate_new_param(root, INTERNALOID, -1); + /* ... but the caller only cares about its ID */ + return param->paramid; +} + +/* * Get the datatype of the first column of the plan's output. * * This is stored for ARRAY_SUBLINK and for exprType(), which doesn't have any @@ -308,8 +322,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery, SubLinkType subLinkType, * Generate the plan for the subquery. */ plan = subquery_planner(root->glob, subquery, - root->query_level + 1, - tuple_fraction, + root, + false, tuple_fraction, &subroot); /* And convert to SubPlan or InitPlan format. */ @@ -342,8 +356,8 @@ make_subplan(PlannerInfo *root, Query *orig_subquery, SubLinkType subLinkType, { /* Generate the plan for the ANY subquery; we'll need all rows */ plan = subquery_planner(root->glob, subquery, - root->query_level + 1, - 0.0, + root, + false, 0.0, &subroot); /* Now we can check if it'll fit in work_mem */ @@ -549,6 +563,8 @@ build_subplan(PlannerInfo *root, Plan *plan, List *rtable, { case T_Material: case T_FunctionScan: + case T_CteScan: + case T_WorkTableScan: case T_Sort: use_material = false; break; @@ -798,6 +814,123 @@ hash_ok_operator(OpExpr *expr) return true; } + +/* + * SS_process_ctes: process a query's WITH list + * + * We plan each interesting WITH item and convert it to an initplan. + * A side effect is to fill in root->cte_plan_ids with a list that + * parallels root->parse->cteList and provides the subplan ID for + * each CTE's initplan. + */ +void +SS_process_ctes(PlannerInfo *root) +{ + ListCell *lc; + + Assert(root->cte_plan_ids == NIL); + + foreach(lc, root->parse->cteList) + { + CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc); + Query *subquery; + Plan *plan; + PlannerInfo *subroot; + SubPlan *splan; + Bitmapset *tmpset; + int paramid; + Param *prm; + + /* + * Ignore CTEs that are not actually referenced anywhere. + */ + if (cte->cterefcount == 0) + { + /* Make a dummy entry in cte_plan_ids */ + root->cte_plan_ids = lappend_int(root->cte_plan_ids, -1); + continue; + } + + /* + * Copy the source Query node. Probably not necessary, but let's + * keep this similar to make_subplan. + */ + subquery = (Query *) copyObject(cte->ctequery); + + /* + * Generate the plan for the CTE query. Always plan for full + * retrieval --- we don't have enough info to predict otherwise. + */ + plan = subquery_planner(root->glob, subquery, + root, + cte->cterecursive, 0.0, + &subroot); + + /* + * Make a SubPlan node for it. This is just enough unlike + * build_subplan that we can't share code. + * + * Note plan_id isn't set till further down, likewise the cost fields. + */ + splan = makeNode(SubPlan); + splan->subLinkType = CTE_SUBLINK; + splan->testexpr = NULL; + splan->paramIds = NIL; + splan->firstColType = get_first_col_type(plan); + splan->useHashTable = false; + splan->unknownEqFalse = false; + splan->setParam = NIL; + splan->parParam = NIL; + splan->args = NIL; + + /* + * Make parParam and args lists of param IDs and expressions that + * current query level will pass to this child plan. Even though + * this is an initplan, there could be side-references to earlier + * initplan's outputs, specifically their CTE output parameters. + */ + tmpset = bms_copy(plan->extParam); + while ((paramid = bms_first_member(tmpset)) >= 0) + { + PlannerParamItem *pitem = list_nth(root->glob->paramlist, paramid); + + if (pitem->abslevel == root->query_level) + { + prm = (Param *) pitem->item; + if (!IsA(prm, Param) || + prm->paramtype != INTERNALOID) + elog(ERROR, "bogus local parameter passed to WITH query"); + + splan->parParam = lappend_int(splan->parParam, paramid); + splan->args = lappend(splan->args, copyObject(prm)); + } + } + bms_free(tmpset); + + /* + * Assign a param to represent the query output. We only really + * care about reserving a parameter ID number. + */ + prm = generate_new_param(root, INTERNALOID, -1); + splan->setParam = list_make1_int(prm->paramid); + + /* + * Add the subplan and its rtable to the global lists. + */ + root->glob->subplans = lappend(root->glob->subplans, plan); + root->glob->subrtables = lappend(root->glob->subrtables, + subroot->parse->rtable); + splan->plan_id = list_length(root->glob->subplans); + + root->init_plans = lappend(root->init_plans, splan); + + root->cte_plan_ids = lappend_int(root->cte_plan_ids, splan->plan_id); + + /* Lastly, fill in the cost estimates for use later */ + cost_subplan(root, splan, plan); + } +} + /* * convert_ANY_sublink_to_join: can we convert an ANY SubLink to a join? * @@ -1589,6 +1722,9 @@ SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans) paramid++; } + /* Also include the recursion working table, if any */ + if (root->wt_param_id >= 0) + valid_params = bms_add_member(valid_params, root->wt_param_id); /* * Now recurse through plan tree. @@ -1719,6 +1855,18 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params) &context); break; + case T_CteScan: + context.paramids = + bms_add_member(context.paramids, + ((CteScan *) plan)->cteParam); + break; + + case T_WorkTableScan: + context.paramids = + bms_add_member(context.paramids, + ((WorkTableScan *) plan)->wtParam); + break; + case T_Append: { ListCell *l; @@ -1790,6 +1938,7 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params) &context); break; + case T_RecursiveUnion: case T_Hash: case T_Agg: case T_SeqScan: @@ -1816,6 +1965,15 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params) plan->righttree, valid_params)); + /* + * RecursiveUnion *generates* its worktable param, so don't bubble that up + */ + if (IsA(plan, RecursiveUnion)) + { + context.paramids = bms_del_member(context.paramids, + ((RecursiveUnion *) plan)->wtParam); + } + /* Now we have all the paramids */ if (!bms_is_subset(context.paramids, valid_params)) |