1 /*-------------------------------------------------------------------------
4 * The query optimizer external interface.
6 * Copyright (c) 1994, Regents of the University of California
10 * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.67 1999/09/13 00:17:25 tgl Exp $
12 *-------------------------------------------------------------------------
14 #include <sys/types.h>
18 #include "access/genam.h"
19 #include "access/heapam.h"
20 #include "catalog/pg_type.h"
21 #include "executor/executor.h"
22 #include "nodes/makefuncs.h"
23 #include "optimizer/clauses.h"
24 #include "optimizer/internal.h"
25 #include "optimizer/paths.h"
26 #include "optimizer/planmain.h"
27 #include "optimizer/planner.h"
28 #include "optimizer/prep.h"
29 #include "optimizer/subselect.h"
30 #include "optimizer/tlist.h"
31 #include "optimizer/var.h"
32 #include "parser/parse_expr.h"
33 #include "parser/parse_oper.h"
34 #include "utils/builtins.h"
35 #include "utils/lsyscache.h"
36 #include "utils/syscache.h"
38 static List *make_subplanTargetList(Query *parse, List *tlist,
39 AttrNumber **groupColIdx);
40 static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup,
41 List *groupClause, AttrNumber *grpColIdx,
42 bool is_presorted, Plan *subplan);
43 static Plan *make_sortplan(List *tlist, List *sortcls, Plan *plannode);
45 /*****************************************************************************
47 * Query optimizer entry point
49 *****************************************************************************/
55 /* Initialize state for subselects */
56 PlannerQueryLevel = 1;
57 PlannerInitPlan = NULL;
58 PlannerParamVar = NULL;
61 transformKeySetQuery(parse);
63 result_plan = union_planner(parse);
65 Assert(PlannerQueryLevel == 1);
66 if (PlannerPlanId > 0)
68 result_plan->initPlan = PlannerInitPlan;
69 (void) SS_finalize_plan(result_plan);
71 result_plan->nParamExec = length(PlannerParamVar);
73 set_plan_references(result_plan);
81 * Invokes the planner on union queries if there are any left,
82 * recursing if necessary to get them all, then processes normal plans.
84 * Returns a query plan.
88 union_planner(Query *parse)
90 List *tlist = parse->targetList;
91 List *rangetable = parse->rtable;
92 Plan *result_plan = (Plan *) NULL;
93 AttrNumber *groupColIdx = NULL;
94 List *current_pathkeys = NIL;
97 if (parse->unionClause)
99 result_plan = (Plan *) plan_union_queries(parse);
100 /* XXX do we need to do this? bjm 12/19/97 */
101 tlist = preprocess_targetlist(tlist,
103 parse->resultRelation,
106 * We leave current_pathkeys NIL indicating we do not know sort order.
107 * Actually, for a normal UNION we have done an explicit sort; ought
108 * to change interface to plan_union_queries to pass that info back!
111 else if ((rt_index = first_inherit_rt_entry(rangetable)) != -1)
116 * Generate appropriate target list for subplan; may be different
117 * from tlist if grouping or aggregation is needed.
119 sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);
122 * Recursively plan the subqueries needed for inheritance
124 result_plan = (Plan *) plan_inherit_queries(parse, sub_tlist,
128 * Fix up outer target list. NOTE: unlike the case for non-inherited
129 * query, we pass the unfixed tlist to subplans, which do their own
130 * fixing. But we still want to fix the outer target list afterwards.
131 * I *think* this is correct --- doing the fix before recursing is
132 * definitely wrong, because preprocess_targetlist() will do the
133 * wrong thing if invoked twice on the same list. Maybe that is a bug?
136 tlist = preprocess_targetlist(tlist,
138 parse->resultRelation,
141 if (parse->rowMark != NULL)
142 elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries");
144 * We leave current_pathkeys NIL indicating we do not know sort order
145 * of the Append-ed results.
152 /* Preprocess targetlist in case we are inside an INSERT/UPDATE. */
153 tlist = preprocess_targetlist(tlist,
155 parse->resultRelation,
159 * Add row-mark targets for UPDATE (should this be done in
160 * preprocess_targetlist?)
162 if (parse->rowMark != NULL)
166 foreach(l, parse->rowMark)
168 RowMark *rowmark = (RowMark *) lfirst(l);
174 if (!(rowmark->info & ROW_MARK_FOR_UPDATE))
177 resname = (char *) palloc(32);
178 sprintf(resname, "ctid%u", rowmark->rti);
179 resdom = makeResdom(length(tlist) + 1,
187 var = makeVar(rowmark->rti, -1, TIDOID, -1, 0);
189 ctid = makeTargetEntry(resdom, (Node *) var);
190 tlist = lappend(tlist, ctid);
195 * Generate appropriate target list for subplan; may be different
196 * from tlist if grouping or aggregation is needed.
198 sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);
201 * Figure out whether we need a sorted result from query_planner.
203 * If we have a GROUP BY clause, then we want a result sorted
204 * properly for grouping. Otherwise, if there is an ORDER BY clause,
205 * we want to sort by the ORDER BY clause.
207 if (parse->groupClause)
209 parse->query_pathkeys =
210 make_pathkeys_for_sortclauses(parse->groupClause, tlist);
212 else if (parse->sortClause)
214 parse->query_pathkeys =
215 make_pathkeys_for_sortclauses(parse->sortClause, tlist);
219 parse->query_pathkeys = NIL;
222 /* Generate the (sub) plan */
223 result_plan = query_planner(parse,
226 (List *) parse->qual);
228 /* query_planner returns actual sort order (which is not
229 * necessarily what we requested) in query_pathkeys.
231 current_pathkeys = parse->query_pathkeys;
234 /* query_planner returns NULL if it thinks plan is bogus */
236 elog(ERROR, "union_planner: failed to create plan");
239 * If we have a GROUP BY clause, insert a group node (plus the
240 * appropriate sort node, if necessary).
242 if (parse->groupClause)
246 List *group_pathkeys;
250 * Decide whether how many tuples per group the Group node needs
251 * to return. (Needs only one tuple per group if no aggregate is
252 * present. Otherwise, need every tuple from the group to do the
253 * aggregation.) Note tuplePerGroup is named backwards :-(
255 tuplePerGroup = parse->hasAggs;
258 * If there are aggregates then the Group node should just return
259 * the same set of vars as the subplan did (but we can exclude
260 * any GROUP BY expressions). If there are no aggregates
261 * then the Group node had better compute the final tlist.
264 group_tlist = flatten_tlist(result_plan->targetlist);
269 * Figure out whether the path result is already ordered the way we
270 * need it --- if so, no need for an explicit sort step.
272 group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause,
274 if (pathkeys_contained_in(group_pathkeys, current_pathkeys))
276 is_sorted = true; /* no sort needed now */
277 /* current_pathkeys remains unchanged */
281 /* We will need to do an explicit sort by the GROUP BY clause.
282 * make_groupplan will do the work, but set current_pathkeys
283 * to indicate the resulting order.
286 current_pathkeys = group_pathkeys;
289 result_plan = make_groupplan(group_tlist,
298 * If we have a HAVING clause, do the necessary things with it.
299 * This code should parallel query_planner()'s initial processing
300 * of the WHERE clause.
302 if (parse->havingQual)
306 /* Replace uplevel Vars with Params */
307 if (PlannerQueryLevel > 1)
308 parse->havingQual = SS_replace_correlation_vars(parse->havingQual);
310 if (parse->hasSubLinks)
312 /* Expand SubLinks to SubPlans */
313 parse->havingQual = SS_process_sublinks(parse->havingQual);
316 * Check for ungrouped variables passed to subplans. (Probably
317 * this should be done for the targetlist as well??? But we
318 * should NOT do it for the WHERE qual, since WHERE is
319 * evaluated pre-GROUP.)
321 if (check_subplans_for_ungrouped_vars(parse->havingQual,
324 elog(ERROR, "Sub-SELECT in HAVING clause must use only GROUPed attributes from outer SELECT");
327 /* convert the havingQual to implicit-AND normal form */
328 parse->havingQual = (Node *)
329 canonicalize_qual((Expr *) parse->havingQual, true);
332 * Require an aggregate function to appear in each clause of the
333 * havingQual (else it could have been done as a WHERE constraint).
335 foreach(ql, (List *) parse->havingQual)
337 if (pull_agg_clause(lfirst(ql)) == NIL)
338 elog(ERROR, "SELECT/HAVING requires aggregates to be valid");
343 * If aggregate is present, insert the agg node
347 result_plan = (Plan *) make_agg(tlist, result_plan);
349 /* HAVING clause, if any, becomes qual of the Agg node */
350 result_plan->qual = (List *) parse->havingQual;
352 /* Note: Agg does not affect any existing sort order of the tuples */
356 * If we were not able to make the plan come out in the right order,
357 * add an explicit sort step.
359 if (parse->sortClause)
363 sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
365 if (! pathkeys_contained_in(sort_pathkeys, current_pathkeys))
367 result_plan = make_sortplan(tlist, parse->sortClause, result_plan);
372 * Finally, if there is a UNIQUE clause, add the UNIQUE node.
374 if (parse->uniqueFlag)
376 result_plan = (Plan *) make_unique(tlist, result_plan,
384 * make_subplanTargetList
385 * Generate appropriate target list when grouping is required.
387 * When union_planner inserts Aggregate and/or Group plan nodes above
388 * the result of query_planner, we typically want to pass a different
389 * target list to query_planner than the outer plan nodes should have.
390 * This routine generates the correct target list for the subplan.
392 * The initial target list passed from the parser already contains entries
393 * for all ORDER BY and GROUP BY expressions, but it will not have entries
394 * for variables used only in HAVING clauses; so we need to add those
395 * variables to the subplan target list. Also, if we are doing either
396 * grouping or aggregation, we flatten all expressions except GROUP BY items
397 * into their component variables; the other expressions will be computed by
398 * the inserted nodes rather than by the subplan. For example,
400 * SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
401 * we want to pass this targetlist to the subplan:
403 * where the a+b target will be used by the Sort/Group steps, and the
404 * other targets will be used for computing the final results. (In the
405 * above example we could theoretically suppress the a and b targets and
406 * use only a+b, but it's not really worth the trouble.)
408 * 'parse' is the query being processed.
409 * 'tlist' is the query's target list.
410 * 'groupColIdx' receives an array of column numbers for the GROUP BY
411 * expressions (if there are any) in the subplan's target list.
413 * The result is the targetlist to be passed to the subplan.
417 make_subplanTargetList(Query *parse,
419 AttrNumber **groupColIdx)
428 * If we're not grouping or aggregating, nothing to do here;
429 * query_planner should receive the unmodified target list.
431 if (!parse->hasAggs && !parse->groupClause && !parse->havingQual)
435 * Otherwise, start with a "flattened" tlist (having just the vars
436 * mentioned in the targetlist and HAVING qual --- but not upper-
437 * level Vars; they will be replaced by Params later on).
439 sub_tlist = flatten_tlist(tlist);
440 extravars = pull_var_clause(parse->havingQual, false);
441 sub_tlist = add_to_flat_tlist(sub_tlist, extravars);
445 * If grouping, create sub_tlist entries for all GROUP BY expressions
446 * (GROUP BY items that are simple Vars should be in the list already),
447 * and make an array showing where the group columns are in the sub_tlist.
449 numCols = length(parse->groupClause);
453 AttrNumber *grpColIdx;
456 grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
457 *groupColIdx = grpColIdx;
459 foreach(gl, parse->groupClause)
461 GroupClause *grpcl = (GroupClause *) lfirst(gl);
462 Node *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
463 TargetEntry *te = NULL;
466 /* Find or make a matching sub_tlist entry */
467 foreach(sl, sub_tlist)
469 te = (TargetEntry *) lfirst(sl);
470 if (equal(groupexpr, te->expr))
475 te = makeTargetEntry(makeResdom(length(sub_tlist) + 1,
477 exprTypmod(groupexpr),
483 sub_tlist = lappend(sub_tlist, te);
486 /* and save its resno */
487 grpColIdx[keyno++] = te->resdom->resno;
496 * Add a Group node for GROUP BY processing.
497 * If we couldn't make the subplan produce presorted output for grouping,
498 * first add an explicit Sort node.
501 make_groupplan(List *group_tlist,
504 AttrNumber *grpColIdx,
508 int numCols = length(groupClause);
513 * The Sort node always just takes a copy of the subplan's tlist
514 * plus ordering information. (This might seem inefficient if the
515 * subplan contains complex GROUP BY expressions, but in fact Sort
516 * does not evaluate its targetlist --- it only outputs the same
517 * tuples in a new order. So the expressions we might be copying
518 * are just dummies with no extra execution cost.)
520 List *sort_tlist = new_unsorted_tlist(subplan->targetlist);
524 foreach(gl, groupClause)
526 GroupClause *grpcl = (GroupClause *) lfirst(gl);
527 TargetEntry *te = nth(grpColIdx[keyno]-1, sort_tlist);
528 Resdom *resdom = te->resdom;
531 * Check for the possibility of duplicate group-by clauses --- the
532 * parser should have removed 'em, but the Sort executor will get
533 * terribly confused if any get through!
535 if (resdom->reskey == 0)
537 /* OK, insert the ordering info needed by the executor. */
538 resdom->reskey = ++keyno;
539 resdom->reskeyop = get_opcode(grpcl->sortop);
543 subplan = (Plan *) make_sort(sort_tlist,
544 _NONAME_RELATION_ID_,
549 return (Plan *) make_group(group_tlist, tuplePerGroup, numCols,
555 * Add a Sort node to implement an explicit ORDER BY clause.
558 make_sortplan(List *tlist, List *sortcls, Plan *plannode)
565 * First make a copy of the tlist so that we don't corrupt the
569 temp_tlist = new_unsorted_tlist(tlist);
573 SortClause *sortcl = (SortClause *) lfirst(i);
574 Index refnumber = sortcl->tleSortGroupRef;
575 TargetEntry *tle = NULL;
579 foreach(l, temp_tlist)
581 tle = (TargetEntry *) lfirst(l);
582 if (tle->resdom->ressortgroupref == refnumber)
586 elog(ERROR, "make_sortplan: ORDER BY expression not found in targetlist");
587 resdom = tle->resdom;
590 * Check for the possibility of duplicate order-by clauses --- the
591 * parser should have removed 'em, but the executor will get terribly
592 * confused if any get through!
594 if (resdom->reskey == 0)
596 /* OK, insert the ordering info needed by the executor. */
597 resdom->reskey = ++keyno;
598 resdom->reskeyop = get_opcode(sortcl->sortop);
602 return (Plan *) make_sort(temp_tlist,
603 _NONAME_RELATION_ID_,
609 * pg_checkretval() -- check return value of a list of sql parse
612 * The return value of a sql function is the value returned by
613 * the final query in the function. We do some ad-hoc define-time
614 * type checking here to be sure that the user is returning the
617 * XXX Why is this function in this module?
620 pg_checkretval(Oid rettype, List *queryTreeList)
634 /* find the final query */
635 parse = (Query *) nth(length(queryTreeList) - 1, queryTreeList);
638 * test 1: if the last query is a utility invocation, then there had
639 * better not be a return value declared.
641 if (parse->commandType == CMD_UTILITY)
643 if (rettype == InvalidOid)
646 elog(ERROR, "return type mismatch in function decl: final query is a catalog utility");
649 /* okay, it's an ordinary query */
650 tlist = parse->targetList;
652 cmd = parse->commandType;
655 * test 2: if the function is declared to return no value, then the
656 * final query had better not be a retrieve.
658 if (rettype == InvalidOid)
660 if (cmd == CMD_SELECT)
662 "function declared with no return type, but final query is a retrieve");
667 /* by here, the function is declared to return some type */
668 if ((typ = typeidType(rettype)) == NULL)
669 elog(ERROR, "can't find return type %u for function\n", rettype);
672 * test 3: if the function is declared to return a value, then the
673 * final query had better be a retrieve.
675 if (cmd != CMD_SELECT)
676 elog(ERROR, "function declared to return type %s, but final query is not a retrieve", typeTypeName(typ));
679 * test 4: for base type returns, the target list should have exactly
680 * one entry, and its type should agree with what the user declared.
683 if (typeTypeRelid(typ) == InvalidOid)
685 if (ExecTargetListLength(tlist) > 1)
686 elog(ERROR, "function declared to return %s returns multiple values in final retrieve", typeTypeName(typ));
688 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
689 if (resnode->restype != rettype)
690 elog(ERROR, "return type mismatch in function: declared to return %s, returns %s", typeTypeName(typ), typeidTypeName(resnode->restype));
692 /* by here, base return types match */
697 * If the target list is of length 1, and the type of the varnode in
698 * the target list is the same as the declared return type, this is
699 * okay. This can happen, for example, where the body of the function
700 * is 'retrieve (x = func2())', where func2 has the same return type
701 * as the function that's calling it.
703 if (ExecTargetListLength(tlist) == 1)
705 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
706 if (resnode->restype == rettype)
711 * By here, the procedure returns a (set of) tuples. This part of the
712 * typechecking is a hack. We look up the relation that is the
713 * declared return type, and be sure that attributes 1 .. n in the
714 * target list match the declared types.
716 reln = heap_open(typeTypeRelid(typ));
718 if (!RelationIsValid(reln))
719 elog(ERROR, "cannot open relation relid %u", typeTypeRelid(typ));
722 relnatts = reln->rd_rel->relnatts;
724 if (ExecTargetListLength(tlist) != relnatts)
725 elog(ERROR, "function declared to return type %s does not retrieve (%s.*)", typeTypeName(typ), typeTypeName(typ));
727 /* expect attributes 1 .. n in order */
728 for (i = 1; i <= relnatts; i++)
730 TargetEntry *tle = lfirst(tlist);
731 Node *thenode = tle->expr;
733 tlist = lnext(tlist);
734 tletype = exprType(thenode);
736 #ifdef NOT_USED /* fix me */
737 /* this is tedious */
738 if (IsA(thenode, Var))
739 tletype = (Oid) ((Var *) thenode)->vartype;
740 else if (IsA(thenode, Const))
741 tletype = (Oid) ((Const *) thenode)->consttype;
742 else if (IsA(thenode, Param))
743 tletype = (Oid) ((Param *) thenode)->paramtype;
744 else if (IsA(thenode, Expr))
747 else if (IsA(thenode, LispList))
749 thenode = lfirst(thenode);
750 if (IsA(thenode, Oper))
751 tletype = (Oid) get_opresulttype((Oper *) thenode);
752 else if (IsA(thenode, Func))
753 tletype = (Oid) get_functype((Func *) thenode);
755 elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
758 elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
760 /* reach right in there, why don't you? */
761 if (tletype != reln->rd_att->attrs[i - 1]->atttypid)
762 elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));