diff options
Diffstat (limited to 'src/backend/optimizer/plan/planner.c')
-rw-r--r-- | src/backend/optimizer/plan/planner.c | 506 |
1 files changed, 398 insertions, 108 deletions
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d6e2330cc8..937628121b 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.90 2000/09/25 18:09:28 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.91 2000/09/29 18:21:33 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -25,11 +25,24 @@ #include "optimizer/subselect.h" #include "optimizer/tlist.h" #include "optimizer/var.h" +#include "parser/parsetree.h" #include "parser/parse_expr.h" +#include "rewrite/rewriteManip.h" #include "utils/lsyscache.h" -static void preprocess_join_conditions(Query *parse, Node *jtnode); +/* Expression kind codes for preprocess_expression */ +#define EXPRKIND_TARGET 0 +#define EXPRKIND_WHERE 1 +#define EXPRKIND_HAVING 2 + + +static Node *pull_up_subqueries(Query *parse, Node *jtnode); +static bool is_simple_subquery(Query *subquery); +static void resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist); +static Node *preprocess_jointree(Query *parse, Node *jtnode); +static Node *preprocess_expression(Query *parse, Node *expr, int kind); +static void preprocess_qual_conditions(Query *parse, Node *jtnode); static List *make_subplanTargetList(Query *parse, List *tlist, AttrNumber **groupColIdx); static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup, @@ -52,8 +65,9 @@ planner(Query *parse) int save_PlannerPlanId; /* - * The planner can be called recursively (an example is when - * eval_const_expressions tries to simplify an SQL function). + * The outer planner can be called recursively, for example to process + * a subquery in the rangetable. (A less obvious example occurs when + * eval_const_expressions tries to simplify an SQL function.) * So, global state variables must be saved and restored. * * (Perhaps these should be moved into the Query structure instead?) @@ -72,7 +86,7 @@ planner(Query *parse) /* this should go away sometime soon */ transformKeySetQuery(parse); - /* primary planning entry point (may recurse for subplans) */ + /* primary planning entry point (may recurse for sublinks) */ result_plan = subquery_planner(parse, -1.0 /* default case */ ); Assert(PlannerQueryLevel == 1); @@ -127,6 +141,18 @@ Plan * subquery_planner(Query *parse, double tuple_fraction) { /* + * Check to see if any subqueries in the rangetable can be merged into + * this query. + */ + parse->jointree = (FromExpr *) + pull_up_subqueries(parse, (Node *) parse->jointree); + /* + * If so, we may have created opportunities to simplify the jointree. + */ + parse->jointree = (FromExpr *) + preprocess_jointree(parse, (Node *) parse->jointree); + + /* * A HAVING clause without aggregates is equivalent to a WHERE clause * (except it can only refer to grouped fields). If there are no aggs * anywhere in the query, then we don't want to create an Agg plan @@ -135,150 +161,413 @@ subquery_planner(Query *parse, double tuple_fraction) */ if (parse->havingQual != NULL && !parse->hasAggs) { - if (parse->qual == NULL) - parse->qual = parse->havingQual; - else - parse->qual = (Node *) make_andclause(lappend(lcons(parse->qual, - NIL), - parse->havingQual)); + parse->jointree->quals = make_and_qual(parse->jointree->quals, + parse->havingQual); parse->havingQual = NULL; } /* - * Simplify constant expressions in targetlist and quals. - * - * Note that at this point the qual has not yet been converted to - * implicit-AND form, so we can apply eval_const_expressions directly. - * Also note that we need to do this before SS_process_sublinks, - * because that routine inserts bogus "Const" nodes. + * Do preprocessing on targetlist and quals. */ parse->targetList = (List *) - eval_const_expressions((Node *) parse->targetList); - parse->qual = eval_const_expressions(parse->qual); - parse->havingQual = eval_const_expressions(parse->havingQual); + preprocess_expression(parse, (Node *) parse->targetList, + EXPRKIND_TARGET); + + preprocess_qual_conditions(parse, (Node *) parse->jointree); + + parse->havingQual = preprocess_expression(parse, parse->havingQual, + EXPRKIND_HAVING); /* - * Canonicalize the qual, and convert it to implicit-AND format. - * - * XXX Is there any value in re-applying eval_const_expressions after - * canonicalize_qual? + * Do the main planning (potentially recursive) */ - parse->qual = (Node *) canonicalize_qual((Expr *) parse->qual, true); - -#ifdef OPTIMIZER_DEBUG - printf("After canonicalize_qual()\n"); - pprint(parse->qual); -#endif + return union_planner(parse, tuple_fraction); /* - * Ditto for the havingQual + * XXX should any more of union_planner's activity be moved here? + * + * That would take careful study of the interactions with prepunion.c, + * but I suspect it would pay off in simplicity and avoidance of + * wasted cycles. */ - parse->havingQual = (Node *) canonicalize_qual((Expr *) parse->havingQual, - true); +} - /* Expand SubLinks to SubPlans */ - if (parse->hasSubLinks) +/* + * pull_up_subqueries + * Look for subqueries in the rangetable that can be pulled up into + * the parent query. If the subquery has no special features like + * grouping/aggregation then we can merge it into the parent's jointree. + * + * A tricky aspect of this code is that if we pull up a subquery we have + * to replace Vars that reference the subquery's outputs throughout the + * parent query, including quals attached to jointree nodes above the one + * we are currently processing! We handle this by being careful not to + * change the jointree structure while recursing: no nodes other than + * subquery RangeTblRef entries will be replaced. Also, we can't turn + * ResolveNew loose on the whole jointree, because it'll return a mutated + * copy of the tree; we have to invoke it just on the quals, instead. + */ +static Node * +pull_up_subqueries(Query *parse, Node *jtnode) +{ + if (jtnode == NULL) + return NULL; + if (IsA(jtnode, RangeTblRef)) { - parse->targetList = (List *) - SS_process_sublinks((Node *) parse->targetList); - parse->qual = SS_process_sublinks(parse->qual); - parse->havingQual = SS_process_sublinks(parse->havingQual); + int varno = ((RangeTblRef *) jtnode)->rtindex; + RangeTblEntry *rte = rt_fetch(varno, parse->rtable); + Query *subquery = rte->subquery; - if (parse->groupClause != NIL || parse->hasAggs) + /* + * Is this a subquery RTE, and if so, is the subquery simple enough + * to pull up? (If not, do nothing at this node.) + */ + if (subquery && is_simple_subquery(subquery)) { + int rtoffset; + Node *subjointree; + List *subtlist; /* - * Check for ungrouped variables passed to subplans. Note we - * do NOT do this for subplans in WHERE; it's legal there - * because WHERE is evaluated pre-GROUP. - * - * An interesting fine point: if we reassigned a HAVING qual into - * WHERE above, then we will accept references to ungrouped - * vars from subplans in the HAVING qual. This is not - * entirely consistent, but it doesn't seem particularly - * harmful... + * First, recursively pull up the subquery's subqueries, + * so that this routine's processing is complete for its + * jointree and rangetable. + */ + subquery->jointree = (FromExpr *) + pull_up_subqueries(subquery, (Node *) subquery->jointree); + /* + * Append the subquery's rangetable to mine (currently, + * no adjustments will be needed in the subquery's rtable). + */ + rtoffset = length(parse->rtable); + parse->rtable = nconc(parse->rtable, subquery->rtable); + /* + * Make copies of the subquery's jointree and targetlist + * with varnos adjusted to match the merged rangetable. + */ + subjointree = copyObject(subquery->jointree); + OffsetVarNodes(subjointree, rtoffset, 0); + subtlist = copyObject(subquery->targetList); + OffsetVarNodes((Node *) subtlist, rtoffset, 0); + /* + * Replace all of the top query's references to the subquery's + * outputs with copies of the adjusted subtlist items, being + * careful not to replace any of the jointree structure. */ - check_subplans_for_ungrouped_vars((Node *) parse->targetList, - parse); - check_subplans_for_ungrouped_vars(parse->havingQual, parse); + parse->targetList = (List *) + ResolveNew((Node *) parse->targetList, + varno, 0, subtlist, CMD_SELECT, 0); + resolvenew_in_jointree((Node *) parse->jointree, varno, subtlist); + parse->havingQual = + ResolveNew(parse->havingQual, + varno, 0, subtlist, CMD_SELECT, 0); + /* + * Miscellaneous housekeeping. + */ + parse->hasSubLinks |= subquery->hasSubLinks; + /* + * Return the adjusted subquery jointree to replace the + * RangeTblRef entry in my jointree. + */ + return subjointree; } } - - /* Replace uplevel vars with Param nodes */ - if (PlannerQueryLevel > 1) + else if (IsA(jtnode, FromExpr)) { - parse->targetList = (List *) - SS_replace_correlation_vars((Node *) parse->targetList); - parse->qual = SS_replace_correlation_vars(parse->qual); - parse->havingQual = SS_replace_correlation_vars(parse->havingQual); - } - - /* Do all the above for each qual condition (ON clause) in the join tree */ - preprocess_join_conditions(parse, (Node *) parse->jointree); + FromExpr *f = (FromExpr *) jtnode; + List *l; - /* Do the main planning (potentially recursive) */ + foreach(l, f->fromlist) + { + lfirst(l) = pull_up_subqueries(parse, lfirst(l)); + } + } + else if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; - return union_planner(parse, tuple_fraction); + j->larg = pull_up_subqueries(parse, j->larg); + j->rarg = pull_up_subqueries(parse, j->rarg); + } + else + elog(ERROR, "pull_up_subqueries: unexpected node type %d", + nodeTag(jtnode)); + return jtnode; +} +/* + * is_simple_subquery + * Check a subquery in the range table to see if it's simple enough + * to pull up into the parent query. + */ +static bool +is_simple_subquery(Query *subquery) +{ /* - * XXX should any more of union_planner's activity be moved here? - * - * That would take careful study of the interactions with prepunion.c, - * but I suspect it would pay off in simplicity and avoidance of - * wasted cycles. + * Let's just make sure it's a valid subselect ... + */ + if (!IsA(subquery, Query) || + subquery->commandType != CMD_SELECT || + subquery->resultRelation != 0 || + subquery->into != NULL || + subquery->isPortal) + elog(ERROR, "is_simple_subquery: subquery is bogus"); + /* + * Also check for currently-unsupported features. + */ + if (subquery->rowMarks) + elog(ERROR, "FOR UPDATE is not supported in subselects"); + if (subquery->limitOffset || subquery->limitCount) + elog(ERROR, "LIMIT is not supported in subselects"); + /* + * Can't currently pull up a union query. Maybe after querytree redesign. */ + if (subquery->unionClause) + return false; + /* + * Can't pull up a subquery involving grouping, aggregation, or sorting. + */ + if (subquery->hasAggs || + subquery->groupClause || + subquery->havingQual || + subquery->sortClause || + subquery->distinctClause) + return false; + /* + * Hack: don't try to pull up a subquery with an empty jointree. + * query_planner() will correctly generate a Result plan for a + * jointree that's totally empty, but I don't think the right things + * happen if an empty FromExpr appears lower down in a jointree. + * Not worth working hard on this, just to collapse SubqueryScan/Result + * into Result... + */ + if (subquery->jointree->fromlist == NIL) + return false; + + return true; } /* - * preprocess_join_conditions - * Recursively scan the query's jointree and do subquery_planner's - * qual preprocessing work on each ON condition found therein. + * Helper routine for pull_up_subqueries: do ResolveNew on every expression + * in the jointree, without changing the jointree structure itself. Ugly, + * but there's no other way... */ static void -preprocess_join_conditions(Query *parse, Node *jtnode) +resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist) { if (jtnode == NULL) return; - if (IsA(jtnode, List)) + if (IsA(jtnode, RangeTblRef)) { + /* nothing to do here */ + } + else if (IsA(jtnode, FromExpr)) + { + FromExpr *f = (FromExpr *) jtnode; List *l; - foreach(l, (List *) jtnode) - preprocess_join_conditions(parse, lfirst(l)); + foreach(l, f->fromlist) + resolvenew_in_jointree(lfirst(l), varno, subtlist); + f->quals = ResolveNew(f->quals, + varno, 0, subtlist, CMD_SELECT, 0); } - else if (IsA(jtnode, RangeTblRef)) + else if (IsA(jtnode, JoinExpr)) { - /* nothing to do here */ + JoinExpr *j = (JoinExpr *) jtnode; + + resolvenew_in_jointree(j->larg, varno, subtlist); + resolvenew_in_jointree(j->rarg, varno, subtlist); + j->quals = ResolveNew(j->quals, + varno, 0, subtlist, CMD_SELECT, 0); + /* We don't bother to update the colvars list, since it won't be + * used again ... + */ + } + else + elog(ERROR, "resolvenew_in_jointree: unexpected node type %d", + nodeTag(jtnode)); +} + +/* + * preprocess_jointree + * Attempt to simplify a query's jointree. + * + * If we succeed in pulling up a subquery then we might form a jointree + * in which a FromExpr is a direct child of another FromExpr. In that + * case we can consider collapsing the two FromExprs into one. This is + * an optional conversion, since the planner will work correctly either + * way. But we may find a better plan (at the cost of more planning time) + * if we merge the two nodes. + * + * NOTE: don't try to do this in the same jointree scan that does subquery + * pullup! Since we're changing the jointree structure here, that wouldn't + * work reliably --- see comments for pull_up_subqueries(). + */ +static Node * +preprocess_jointree(Query *parse, Node *jtnode) +{ + if (jtnode == NULL) + return NULL; + if (IsA(jtnode, RangeTblRef)) + { + /* nothing to do here... */ + } + else if (IsA(jtnode, FromExpr)) + { + FromExpr *f = (FromExpr *) jtnode; + List *newlist = NIL; + List *l; + + foreach(l, f->fromlist) + { + Node *child = (Node *) lfirst(l); + + /* Recursively simplify the child... */ + child = preprocess_jointree(parse, child); + /* Now, is it a FromExpr? */ + if (child && IsA(child, FromExpr)) + { + /* + * Yes, so do we want to merge it into parent? Always do so + * if child has just one element (since that doesn't make the + * parent's list any longer). Otherwise we have to be careful + * about the increase in planning time caused by combining the + * two join search spaces into one. Our heuristic is to merge + * if the merge will produce a join list no longer than + * GEQO_RELS/2. (Perhaps need an additional user parameter?) + */ + FromExpr *subf = (FromExpr *) child; + int childlen = length(subf->fromlist); + int myothers = length(newlist) + length(lnext(l)); + + if (childlen <= 1 || (childlen+myothers) <= geqo_rels/2) + { + newlist = nconc(newlist, subf->fromlist); + f->quals = make_and_qual(f->quals, subf->quals); + } + else + newlist = lappend(newlist, child); + } + else + newlist = lappend(newlist, child); + } + f->fromlist = newlist; } else if (IsA(jtnode, JoinExpr)) { JoinExpr *j = (JoinExpr *) jtnode; - preprocess_join_conditions(parse, j->larg); - preprocess_join_conditions(parse, j->rarg); + /* Can't usefully change the JoinExpr, but recurse on children */ + j->larg = preprocess_jointree(parse, j->larg); + j->rarg = preprocess_jointree(parse, j->rarg); + } + else + elog(ERROR, "preprocess_jointree: unexpected node type %d", + nodeTag(jtnode)); + return jtnode; +} - /* Simplify constant expressions */ - j->quals = eval_const_expressions(j->quals); +/* + * preprocess_expression + * Do subquery_planner's preprocessing work for an expression, + * which can be a targetlist, a WHERE clause (including JOIN/ON + * conditions), or a HAVING clause. + */ +static Node * +preprocess_expression(Query *parse, Node *expr, int kind) +{ + /* + * Simplify constant expressions. + * + * Note that at this point quals have not yet been converted to + * implicit-AND form, so we can apply eval_const_expressions directly. + * Also note that we need to do this before SS_process_sublinks, + * because that routine inserts bogus "Const" nodes. + */ + expr = eval_const_expressions(expr); - /* Canonicalize the qual, and convert it to implicit-AND format */ - j->quals = (Node *) canonicalize_qual((Expr *) j->quals, true); + /* + * If it's a qual or havingQual, canonicalize it, and convert it + * to implicit-AND format. + * + * XXX Is there any value in re-applying eval_const_expressions after + * canonicalize_qual? + */ + if (kind != EXPRKIND_TARGET) + { + expr = (Node *) canonicalize_qual((Expr *) expr, true); + +#ifdef OPTIMIZER_DEBUG + printf("After canonicalize_qual()\n"); + pprint(expr); +#endif + } + if (parse->hasSubLinks) + { /* Expand SubLinks to SubPlans */ - if (parse->hasSubLinks) + expr = SS_process_sublinks(expr); + + if (kind != EXPRKIND_WHERE && + (parse->groupClause != NIL || parse->hasAggs)) { - j->quals = SS_process_sublinks(j->quals); /* - * ON conditions, like WHERE clauses, are evaluated pre-GROUP; - * so we allow ungrouped vars in them. + * Check for ungrouped variables passed to subplans. Note we + * do NOT do this for subplans in WHERE (or JOIN/ON); it's legal + * there because WHERE is evaluated pre-GROUP. + * + * An interesting fine point: if subquery_planner reassigned a + * HAVING qual into WHERE, then we will accept references to + * ungrouped vars from subplans in the HAVING qual. This is not + * entirely consistent, but it doesn't seem particularly + * harmful... */ + check_subplans_for_ungrouped_vars(expr, parse); } + } + + /* Replace uplevel vars with Param nodes */ + if (PlannerQueryLevel > 1) + expr = SS_replace_correlation_vars(expr); - /* Replace uplevel vars with Param nodes */ - if (PlannerQueryLevel > 1) - j->quals = SS_replace_correlation_vars(j->quals); + return expr; +} + +/* + * preprocess_qual_conditions + * Recursively scan the query's jointree and do subquery_planner's + * preprocessing work on each qual condition found therein. + */ +static void +preprocess_qual_conditions(Query *parse, Node *jtnode) +{ + if (jtnode == NULL) + return; + if (IsA(jtnode, RangeTblRef)) + { + /* nothing to do here */ + } + else if (IsA(jtnode, FromExpr)) + { + FromExpr *f = (FromExpr *) jtnode; + List *l; + + foreach(l, f->fromlist) + preprocess_qual_conditions(parse, lfirst(l)); + + f->quals = preprocess_expression(parse, f->quals, EXPRKIND_WHERE); + } + else if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; + + preprocess_qual_conditions(parse, j->larg); + preprocess_qual_conditions(parse, j->rarg); + + j->quals = preprocess_expression(parse, j->quals, EXPRKIND_WHERE); } else - elog(ERROR, "preprocess_join_conditions: unexpected node type %d", + elog(ERROR, "preprocess_qual_conditions: unexpected node type %d", nodeTag(jtnode)); } @@ -309,7 +598,6 @@ union_planner(Query *parse, double tuple_fraction) { List *tlist = parse->targetList; - List *rangetable = parse->rtable; Plan *result_plan = (Plan *) NULL; AttrNumber *groupColIdx = NULL; List *current_pathkeys = NIL; @@ -342,7 +630,7 @@ union_planner(Query *parse, sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause, tlist); } - else if (find_inheritable_rt_entry(rangetable, + else if (find_inheritable_rt_entry(parse->rtable, &rt_index, &inheritors)) { List *sub_tlist; @@ -373,7 +661,7 @@ union_planner(Query *parse, parse->resultRelation, parse->rtable); - if (parse->rowMark != NULL) + if (parse->rowMarks) elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries"); /* @@ -401,33 +689,35 @@ union_planner(Query *parse, parse->rtable); /* - * Add row-mark targets for UPDATE (should this be done in - * preprocess_targetlist?) + * Add TID targets for rels selected FOR UPDATE (should this be + * done in preprocess_targetlist?). The executor uses the TID + * to know which rows to lock, much as for UPDATE or DELETE. */ - if (parse->rowMark != NULL) + if (parse->rowMarks) { List *l; - foreach(l, parse->rowMark) + foreach(l, parse->rowMarks) { - RowMark *rowmark = (RowMark *) lfirst(l); - TargetEntry *ctid; + Index rti = lfirsti(l); + char *resname; Resdom *resdom; Var *var; - char *resname; - - if (!(rowmark->info & ROW_MARK_FOR_UPDATE)) - continue; + TargetEntry *ctid; resname = (char *) palloc(32); - sprintf(resname, "ctid%u", rowmark->rti); + sprintf(resname, "ctid%u", rti); resdom = makeResdom(length(tlist) + 1, TIDOID, -1, resname, true); - var = makeVar(rowmark->rti, -1, TIDOID, -1, 0); + var = makeVar(rti, + SelfItemPointerAttributeNumber, + TIDOID, + -1, + 0); ctid = makeTargetEntry(resdom, (Node *) var); tlist = lappend(tlist, ctid); |