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.42 1999/02/03 21:16:36 momjian Exp $
12 *-------------------------------------------------------------------------
14 #include <sys/types.h>
19 #include "nodes/pg_list.h"
20 #include "nodes/plannodes.h"
21 #include "nodes/parsenodes.h"
22 #include "nodes/relation.h"
23 #include "nodes/makefuncs.h"
24 #include "catalog/pg_type.h"
25 #include "parser/parse_expr.h"
27 #include "utils/elog.h"
28 #include "utils/lsyscache.h"
29 #include "access/heapam.h"
31 #include "optimizer/internal.h"
32 #include "optimizer/planner.h"
33 #include "optimizer/plancat.h"
34 #include "optimizer/prep.h"
35 #include "optimizer/planmain.h"
36 #include "optimizer/subselect.h"
37 #include "optimizer/paths.h"
38 #include "optimizer/cost.h"
40 /* DATA STRUCTURE CREATION/MANIPULATION ROUTINES */
41 #include "nodes/relation.h"
42 #include "optimizer/restrictinfo.h"
43 #include "optimizer/joininfo.h"
44 #include "optimizer/keys.h"
45 #include "optimizer/ordering.h"
46 #include "optimizer/pathnode.h"
47 #include "optimizer/clauses.h"
48 #include "optimizer/tlist.h"
49 #include "optimizer/var.h"
51 #include "executor/executor.h"
53 #include "utils/builtins.h"
54 #include "utils/syscache.h"
55 #include "access/genam.h"
56 #include "parser/parse_oper.h"
58 static bool need_sortplan(List *sortcls, Plan *plan);
59 static Plan *make_sortplan(List *tlist, List *sortcls, Plan *plannode);
60 extern Plan *make_groupPlan(List **tlist, bool tuplePerGroup,
61 List *groupClause, Plan *subplan);
63 /*****************************************************************************
65 * Query optimizer entry point
67 *****************************************************************************/
73 PlannerQueryLevel = 1;
74 PlannerVarParam = NULL;
75 PlannerParamVar = NULL;
76 PlannerInitPlan = NULL;
79 transformKeySetQuery(parse);
80 result_plan = union_planner(parse);
82 Assert(PlannerQueryLevel == 1);
83 if (PlannerPlanId > 0)
85 result_plan->initPlan = PlannerInitPlan;
86 (void) SS_finalize_plan(result_plan);
88 result_plan->nParamExec = length(PlannerParamVar);
96 * Invokes the planner on union queries if there are any left,
97 * recursing if necessary to get them all, then processes normal plans.
99 * Returns a query plan.
103 union_planner(Query *parse)
105 List *tlist = parse->targetList;
108 /* copy the original tlist, we will need the original one
109 * for the AGG node later on */
110 List *new_tlist = new_unsorted_tlist(tlist);
112 List *rangetable = parse->rtable;
114 Plan *result_plan = (Plan *) NULL;
118 if (parse->unionClause)
120 result_plan = (Plan *) plan_union_queries(parse);
121 /* XXX do we need to do this? bjm 12/19/97 */
122 tlist = preprocess_targetlist(tlist,
124 parse->resultRelation,
127 else if ((rt_index = first_inherit_rt_entry(rangetable)) != -1)
129 if (parse->rowMark != NULL)
130 elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries");
131 result_plan = (Plan *) plan_inherit_queries(parse, rt_index);
132 /* XXX do we need to do this? bjm 12/19/97 */
133 tlist = preprocess_targetlist(tlist,
135 parse->resultRelation,
143 /* This is only necessary if aggregates are in use in queries like:
147 * HAVING MIN(pid) > 1; (pid is used but never selected for!!!)
148 * because the function 'query_planner' creates the plan for the lefttree
149 * of the 'GROUP' node and returns only those attributes contained in 'tlist'.
150 * The original 'tlist' contains only 'sid' here and that's why we have to
151 * to extend it to attributes which are not selected but are used in the
154 /* 'check_having_qual_for_vars' takes the havingQual and the actual 'tlist'
155 * as arguments and recursively scans the havingQual for attributes
156 * (VAR nodes) that are not contained in 'tlist' yet. If so, it creates
157 * a new entry and attaches it to the list 'new_tlist' (consisting of the
158 * VAR node and the RESDOM node as usual with tlists :-) ) */
161 if (parse->havingQual != NULL)
163 new_tlist = check_having_qual_for_vars(parse->havingQual,new_tlist);
167 new_tlist = preprocess_targetlist(new_tlist,
169 parse->resultRelation,
173 if (parse->rowMark != NULL)
181 foreach (l, parse->rowMark)
183 if (!(((RowMark*)lfirst(l))->info & ROW_MARK_FOR_UPDATE))
186 resname = (char*) palloc(32);
187 sprintf(resname, "ctid%u", ((RowMark*)lfirst(l))->rti);
188 resdom = makeResdom(length(new_tlist) + 1,
196 var = makeVar(((RowMark*)lfirst(l))->rti, -1, TIDOID,
197 -1, 0, ((RowMark*)lfirst(l))->rti, -1);
199 ctid = makeTargetEntry(resdom, (Node *) var);
200 new_tlist = lappend(new_tlist, ctid);
204 /* Here starts the original (pre having) code */
205 tlist = preprocess_targetlist(tlist,
207 parse->resultRelation,
210 if (parse->rtable != NULL)
212 vpm = (List **) palloc(length(parse->rtable) * sizeof(List *));
213 memset(vpm, 0, length(parse->rtable) * sizeof(List *));
215 PlannerVarParam = lcons(vpm, PlannerVarParam);
216 result_plan = query_planner(parse,
219 (List *) parse->qual);
220 PlannerVarParam = lnext(PlannerVarParam);
226 * If we have a GROUP BY clause, insert a group node (with the
227 * appropriate sort node.)
229 if (parse->groupClause)
234 * decide whether how many tuples per group the Group node needs
235 * to return. (Needs only one tuple per group if no aggregate is
236 * present. Otherwise, need every tuple from the group to do the
239 tuplePerGroup = parse->hasAggs;
242 /* Use 'new_tlist' instead of 'tlist' */
243 result_plan = make_groupPlan(&new_tlist,
250 * If aggregate is present, insert the agg node
254 int old_length=0, new_length=0;
256 /* Create the Agg node but use 'tlist' not 'new_tlist' as target list because we
257 * don't want the additional attributes (only used for the havingQual, see above)
258 * to show up in the result */
259 result_plan = (Plan *) make_agg(tlist, result_plan);
262 * get the varno/attno entries to the appropriate references to
263 * the result tuple of the subplans.
265 ((Agg *) result_plan)->aggs = get_agg_tlist_references((Agg *) result_plan);
268 if(parse->havingQual!=NULL)
274 /* stuff copied from above to handle the use of attributes from outside
277 if (parse->rtable != NULL)
279 vpm = (List **) palloc(length(parse->rtable) * sizeof(List *));
280 memset(vpm, 0, length(parse->rtable) * sizeof(List *));
282 PlannerVarParam = lcons(vpm, PlannerVarParam);
285 /* convert the havingQual to conjunctive normal form (cnf) */
286 (List *) parse->havingQual=cnfify((Expr *)(Node *) parse->havingQual,true);
288 /* There is a subselect in the havingQual, so we have to process it
289 * using the same function as for a subselect in 'where' */
290 if (parse->hasSubLinks)
292 (List *) parse->havingQual =
293 (List *) SS_process_sublinks((Node *) parse->havingQual);
297 /* Calculate the opfids from the opnos (=select the correct functions for
298 * the used VAR datatypes) */
299 (List *) parse->havingQual=fix_opids((List *) parse->havingQual);
301 ((Agg *) result_plan)->plan.qual=(List *) parse->havingQual;
303 /* Check every clause of the havingQual for aggregates used and append
304 * them to result_plan->aggs
306 foreach(clause, ((Agg *) result_plan)->plan.qual)
308 /* Make sure there are aggregates in the havingQual
309 * if so, the list must be longer after check_having_qual_for_aggs
311 old_length=length(((Agg *) result_plan)->aggs);
313 ((Agg *) result_plan)->aggs = nconc(((Agg *) result_plan)->aggs,
314 check_having_qual_for_aggs((Node *) lfirst(clause),
315 ((Agg *) result_plan)->plan.lefttree->targetlist,
316 ((List *) parse->groupClause)));
318 /* Have a look at the length of the returned list. If there is no
319 * difference, no aggregates have been found and that means, that
320 * the Qual belongs to the where clause */
321 if (((new_length=length(((Agg *) result_plan)->aggs)) == old_length) ||
324 elog(ERROR,"This could have been done in a where clause!!");
328 PlannerVarParam = lnext(PlannerVarParam);
335 * For now, before we hand back the plan, check to see if there is a
336 * user-specified sort that needs to be done. Eventually, this will
337 * be moved into the guts of the planner s.t. user specified sorts
338 * will be considered as part of the planning process. Since we can
339 * only make use of user-specified sorts in special cases, we can do
340 * the optimization step later.
343 if (parse->uniqueFlag)
345 Plan *sortplan = make_sortplan(tlist, parse->sortClause, result_plan);
347 return ((Plan *) make_unique(tlist, sortplan, parse->uniqueFlag));
351 if (parse->sortClause && need_sortplan(parse->sortClause, result_plan))
352 return (make_sortplan(tlist, parse->sortClause, result_plan));
354 return ((Plan *) result_plan);
361 * Returns a sortplan which is basically a SORT node attached to the
362 * top of the plan returned from the planner. It also adds the
363 * cost of sorting into the plan.
365 * sortkeys: ( resdom1 resdom2 resdom3 ...)
366 * sortops: (sortop1 sortop2 sortop3 ...)
369 make_sortplan(List *tlist, List *sortcls, Plan *plannode)
371 Plan *sortplan = (Plan *) NULL;
372 List *temp_tlist = NIL;
374 Resdom *resnode = (Resdom *) NULL;
375 Resdom *resdom = (Resdom *) NULL;
379 * First make a copy of the tlist so that we don't corrupt the the
383 temp_tlist = new_unsorted_tlist(tlist);
387 SortClause *sortcl = (SortClause *) lfirst(i);
389 resnode = sortcl->resdom;
390 resdom = tlist_resdom(temp_tlist, resnode);
393 * Order the resdom keys and replace the operator OID for each key
394 * with the regproc OID.
396 resdom->reskey = keyno;
397 resdom->reskeyop = get_opcode(sortcl->opoid);
401 sortplan = (Plan *) make_sort(temp_tlist,
407 * XXX Assuming that an internal sort has no. cost. This is wrong, but
408 * given that at this point, we don't know the no. of tuples returned,
409 * etc, we can't do better than to add a constant cost. This will be
410 * fixed once we move the sort further into the planner, but for now
411 * ... functionality....
414 sortplan->cost = plannode->cost;
420 * pg_checkretval() -- check return value of a list of sql parse
423 * The return value of a sql function is the value returned by
424 * the final query in the function. We do some ad-hoc define-time
425 * type checking here to be sure that the user is returning the
429 pg_checkretval(Oid rettype, QueryTreeList *queryTreeList)
443 /* find the final query */
444 parse = queryTreeList->qtrees[queryTreeList->len - 1];
447 * test 1: if the last query is a utility invocation, then there had
448 * better not be a return value declared.
450 if (parse->commandType == CMD_UTILITY)
452 if (rettype == InvalidOid)
455 elog(ERROR, "return type mismatch in function decl: final query is a catalog utility");
458 /* okay, it's an ordinary query */
459 tlist = parse->targetList;
461 cmd = parse->commandType;
464 * test 2: if the function is declared to return no value, then the
465 * final query had better not be a retrieve.
467 if (rettype == InvalidOid)
469 if (cmd == CMD_SELECT)
471 "function declared with no return type, but final query is a retrieve");
476 /* by here, the function is declared to return some type */
477 if ((typ = typeidType(rettype)) == NULL)
478 elog(ERROR, "can't find return type %d for function\n", rettype);
481 * test 3: if the function is declared to return a value, then the
482 * final query had better be a retrieve.
484 if (cmd != CMD_SELECT)
485 elog(ERROR, "function declared to return type %s, but final query is not a retrieve", typeTypeName(typ));
488 * test 4: for base type returns, the target list should have exactly
489 * one entry, and its type should agree with what the user declared.
492 if (typeTypeRelid(typ) == InvalidOid)
494 if (ExecTargetListLength(tlist) > 1)
495 elog(ERROR, "function declared to return %s returns multiple values in final retrieve", typeTypeName(typ));
497 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
498 if (resnode->restype != rettype)
499 elog(ERROR, "return type mismatch in function: declared to return %s, returns %s", typeTypeName(typ), typeidTypeName(resnode->restype));
501 /* by here, base return types match */
506 * If the target list is of length 1, and the type of the varnode in
507 * the target list is the same as the declared return type, this is
508 * okay. This can happen, for example, where the body of the function
509 * is 'retrieve (x = func2())', where func2 has the same return type
510 * as the function that's calling it.
512 if (ExecTargetListLength(tlist) == 1)
514 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
515 if (resnode->restype == rettype)
520 * By here, the procedure returns a (set of) tuples. This part of the
521 * typechecking is a hack. We look up the relation that is the
522 * declared return type, and be sure that attributes 1 .. n in the
523 * target list match the declared types.
525 reln = heap_open(typeTypeRelid(typ));
527 if (!RelationIsValid(reln))
528 elog(ERROR, "cannot open relation relid %d", typeTypeRelid(typ));
531 relnatts = reln->rd_rel->relnatts;
533 if (ExecTargetListLength(tlist) != relnatts)
534 elog(ERROR, "function declared to return type %s does not retrieve (%s.*)", typeTypeName(typ), typeTypeName(typ));
536 /* expect attributes 1 .. n in order */
537 for (i = 1; i <= relnatts; i++)
539 TargetEntry *tle = lfirst(tlist);
540 Node *thenode = tle->expr;
542 tlist = lnext(tlist);
543 tletype = exprType(thenode);
546 /* this is tedious */
547 if (IsA(thenode, Var))
548 tletype = (Oid) ((Var *) thenode)->vartype;
549 else if (IsA(thenode, Const))
550 tletype = (Oid) ((Const *) thenode)->consttype;
551 else if (IsA(thenode, Param))
552 tletype = (Oid) ((Param *) thenode)->paramtype;
553 else if (IsA(thenode, Expr))
556 else if (IsA(thenode, LispList))
558 thenode = lfirst(thenode);
559 if (IsA(thenode, Oper))
560 tletype = (Oid) get_opresulttype((Oper *) thenode);
561 else if (IsA(thenode, Func))
562 tletype = (Oid) get_functype((Func *) thenode);
564 elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
567 elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
569 /* reach right in there, why don't you? */
570 if (tletype != reln->rd_att->attrs[i - 1]->atttypid)
571 elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
582 * Support function for need_sortplan
586 get_matching_tle(Plan *plan, Resdom *resdom)
591 foreach (i, plan->targetlist) {
592 tle = (TargetEntry *)lfirst(i);
593 if (tle->resdom->resno == resdom->resno)
601 * Check if a user requested ORDER BY is already satisfied by
602 * the choosen index scan.
604 * Returns TRUE if sort is required, FALSE if can be omitted.
608 need_sortplan(List *sortcls, Plan *plan)
611 IndexScan *indexScan;
615 Form_pg_index index_tup;
619 * Must be an IndexScan
622 if (nodeTag(plan) != T_IndexScan) {
626 indexScan = (IndexScan *)plan;
629 * Should not have left- or righttree
632 if (plan->lefttree != NULL) {
635 if (plan->righttree != NULL) {
640 * Must be a single index scan
643 if (length(indexScan->indxid) != 1) {
648 * Indices can only have up to 8 attributes. So an ORDER BY using
649 * more that 8 attributes could never be satisfied by an index.
652 if (length(sortcls) > 8) {
657 * The choosen Index must be a btree
660 indexId = lfirsti(indexScan->indxid);
662 indexRel = index_open(indexId);
663 if (strcmp(nameout(&(indexRel->rd_am->amname)), "btree") != 0) {
664 heap_close(indexRel);
667 heap_close(indexRel);
670 * Fetch the index tuple
673 htup = SearchSysCacheTuple(INDEXRELID,
674 ObjectIdGetDatum(indexId), 0, 0, 0);
675 if (!HeapTupleIsValid(htup)) {
676 elog(ERROR, "cache lookup for index %d failed", indexId);
678 index_tup = (Form_pg_index) GETSTRUCT(htup);
681 * Check if all the sort clauses match the attributes in the index
684 foreach (i, sortcls) {
690 sortcl = (SortClause *) lfirst(i);
692 resdom = sortcl->resdom;
693 tle = get_matching_tle(plan, resdom);
701 if (nodeTag(tle->expr) != T_Var) {
703 * The target list expression isn't a var, so it
704 * cannot be the indexed attribute
709 var = (Var *)(tle->expr);
711 if (var->varno != indexScan->scan.scanrelid) {
713 * This Var isn't from the scan relation. So it isn't
720 if (var->varattno != index_tup->indkey[key_no]) {
722 * It isn't the indexed attribute.
728 if (oprid(oper("<", resdom->restype, resdom->restype, FALSE)) != sortcl->opoid) {
730 * Sort order isn't in ascending order.
740 * Index matches ORDER BY - sort not required