granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/planner.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * planner.c
   4  *        The query optimizer external interface.
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.48 1999/05/03 00:38:43 tgl Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include <sys/types.h>
  15 #include <string.h>
  16
  17 #include "postgres.h"
  18
  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"
  26
  27 #include "utils/elog.h"
  28 #include "utils/lsyscache.h"
  29 #include "access/heapam.h"
  30
  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"
  39
  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"
  50
  51 #include "executor/executor.h"
  52
  53 #include "utils/builtins.h"
  54 #include "utils/syscache.h"
  55 #include "access/genam.h"
  56 #include "parser/parse_oper.h"
  57
  58 static List *make_subplanTargetList(Query *parse, List *tlist,
  59                                                                         AttrNumber **groupColIdx);
  60 static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup,
  61                                                         List *groupClause, AttrNumber *grpColIdx,
  62                                                         Plan *subplan);
  63 static bool need_sortplan(List *sortcls, Plan *plan);
  64 static Plan *make_sortplan(List *tlist, List *sortcls, Plan *plannode);
  65
  66 /*****************************************************************************
  67  *
  68  *         Query optimizer entry point
  69  *
  70  *****************************************************************************/
  71 Plan *
  72 planner(Query *parse)
  73 {
  74         Plan       *result_plan;
  75
  76         PlannerQueryLevel = 1;
  77         PlannerVarParam = NULL;
  78         PlannerParamVar = NULL;
  79         PlannerInitPlan = NULL;
  80         PlannerPlanId = 0;
  81
  82         transformKeySetQuery(parse);
  83         result_plan = union_planner(parse);
  84
  85         Assert(PlannerQueryLevel == 1);
  86         if (PlannerPlanId > 0)
  87         {
  88                 result_plan->initPlan = PlannerInitPlan;
  89                 (void) SS_finalize_plan(result_plan);
  90         }
  91         result_plan->nParamExec = length(PlannerParamVar);
  92
  93         return result_plan;
  94 }
  95
  96 /*
  97  * union_planner
  98  *
  99  *        Invokes the planner on union queries if there are any left,
 100  *        recursing if necessary to get them all, then processes normal plans.
 101  *
 102  * Returns a query plan.
 103  *
 104  */
 105 Plan *
 106 union_planner(Query *parse)
 107 {
 108         List       *tlist = parse->targetList;
 109         List       *rangetable = parse->rtable;
 110         Plan       *result_plan = (Plan *) NULL;
 111         AttrNumber *groupColIdx = NULL;
 112         Index           rt_index;
 113
 114         if (parse->unionClause)
 115         {
 116           result_plan = (Plan *) plan_union_queries(parse);
 117           /* XXX do we need to do this? bjm 12/19/97 */
 118           tlist = preprocess_targetlist(tlist,
 119                                         parse->commandType,
 120                                         parse->resultRelation,
 121                                         parse->rtable);
 122         }
 123         else if ((rt_index = first_inherit_rt_entry(rangetable)) != -1)
 124         {
 125                 if (parse->rowMark != NULL)
 126                         elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries");
 127                 result_plan = (Plan *) plan_inherit_queries(parse, rt_index);
 128                 /* XXX do we need to do this? bjm 12/19/97 */
 129                 tlist = preprocess_targetlist(tlist,
 130                                               parse->commandType,
 131                                               parse->resultRelation,
 132                                               parse->rtable);
 133         }
 134         else
 135         {
 136           List  **vpm = NULL;
 137           List  *sub_tlist;
 138
 139           /* Preprocess targetlist in case we are inside an INSERT/UPDATE. */
 140           tlist = preprocess_targetlist(tlist,
 141                                                                         parse->commandType,
 142                                                                         parse->resultRelation,
 143                                                                         parse->rtable);
 144
 145           /* Add row-mark targets for UPDATE
 146            * (should this be done in preprocess_targetlist?)
 147            */
 148           if (parse->rowMark != NULL)
 149           {
 150                 List               *l;
 151
 152                 foreach (l, parse->rowMark)
 153                 {
 154                         RowMark            *rowmark = (RowMark*) lfirst(l);
 155                         TargetEntry        *ctid;
 156                         Resdom             *resdom;
 157                         Var                        *var;
 158                         char               *resname;
 159
 160                         if (!(rowmark->info & ROW_MARK_FOR_UPDATE))
 161                                 continue;
 162
 163                         resname = (char*) palloc(32);
 164                         sprintf(resname, "ctid%u", rowmark->rti);
 165                         resdom = makeResdom(length(tlist) + 1,
 166                                                                 TIDOID,
 167                                                                 -1,
 168                                                                 resname,
 169                                                                 0,
 170                                                                 0,
 171                                                                 1);
 172
 173                         var = makeVar(rowmark->rti, -1, TIDOID,
 174                                                   -1, 0, rowmark->rti, -1);
 175
 176                         ctid = makeTargetEntry(resdom, (Node *) var);
 177                         tlist = lappend(tlist, ctid);
 178                 }
 179           }
 180
 181           /* Generate appropriate target list for subplan; may be different
 182            * from tlist if grouping or aggregation is needed.
 183            */
 184           sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx);
 185
 186           /* Generate the (sub) plan */
 187           if (parse->rtable != NULL)
 188           {
 189               vpm = (List **) palloc(length(parse->rtable) * sizeof(List *));
 190               memset(vpm, 0, length(parse->rtable) * sizeof(List *));
 191           }
 192           PlannerVarParam = lcons(vpm, PlannerVarParam);
 193           result_plan = query_planner(parse,
 194                                                                   parse->commandType,
 195                                                                   sub_tlist,
 196                                                                   (List *) parse->qual);
 197           PlannerVarParam = lnext(PlannerVarParam);
 198           if (vpm != NULL)
 199             pfree(vpm);
 200         }
 201
 202         /*
 203          * If we have a GROUP BY clause, insert a group node (with the
 204          * appropriate sort node.)
 205          */
 206         if (parse->groupClause)
 207         {
 208                 bool            tuplePerGroup;
 209                 List       *group_tlist;
 210
 211                 /*
 212                  * Decide whether how many tuples per group the Group node needs
 213                  * to return. (Needs only one tuple per group if no aggregate is
 214                  * present. Otherwise, need every tuple from the group to do the
 215                  * aggregation.)  Note tuplePerGroup is named backwards :-(
 216                  */
 217                 tuplePerGroup = parse->hasAggs;
 218
 219                 /* If there are aggregates then the Group node should just return
 220                  * the same (simplified) tlist as the subplan, which we indicate
 221                  * to make_groupplan by passing NIL.  If there are no aggregates
 222                  * then the Group node had better compute the final tlist.
 223                  */
 224                 group_tlist = parse->hasAggs ? NIL : tlist;
 225
 226                 result_plan = make_groupplan(group_tlist,
 227                                                                          tuplePerGroup,
 228                                                                          parse->groupClause,
 229                                                                          groupColIdx,
 230                                                                          result_plan);
 231         }
 232
 233         /*
 234          * If we have a HAVING clause, do the necessary things with it.
 235          */
 236         if (parse->havingQual)
 237         {
 238                 List  **vpm = NULL;
 239
 240                 if (parse->rtable != NULL)
 241                 {
 242                         vpm = (List **) palloc(length(parse->rtable) * sizeof(List *));
 243                         memset(vpm, 0, length(parse->rtable) * sizeof(List *));
 244                 }
 245                 PlannerVarParam = lcons(vpm, PlannerVarParam);
 246
 247                 /* convert the havingQual to conjunctive normal form (cnf) */
 248                 parse->havingQual = (Node *) cnfify((Expr *) parse->havingQual, true);
 249
 250                 if (parse->hasSubLinks)
 251                 {
 252                         /* There is a subselect in the havingQual, so we have to process it
 253                          * using the same function as for a subselect in 'where'
 254                          */
 255                         parse->havingQual =
 256                                 (Node *) SS_process_sublinks(parse->havingQual);
 257                         /* Check for ungrouped variables passed to subplans.
 258                          * (Probably this should be done by the parser, but right now
 259                          * the parser is not smart enough to tell which level the vars
 260                          * belong to?)
 261                          */
 262                         check_having_for_ungrouped_vars(parse->havingQual,
 263                                                                                         parse->groupClause);
 264                 }
 265
 266                 /* Calculate the opfids from the opnos */
 267                 parse->havingQual = (Node *) fix_opids((List *) parse->havingQual);
 268
 269                 PlannerVarParam = lnext(PlannerVarParam);
 270                 if (vpm != NULL)
 271                         pfree(vpm);
 272         }
 273
 274         /*
 275          * If aggregate is present, insert the agg node
 276          */
 277         if (parse->hasAggs)
 278         {
 279                 result_plan = (Plan *) make_agg(tlist, result_plan);
 280
 281                 /* HAVING clause, if any, becomes qual of the Agg node */
 282                 result_plan->qual = (List *) parse->havingQual;
 283
 284                 /*
 285                  * Update vars to refer to subplan result tuples,
 286                  * find Aggrefs, make sure there is an Aggref in every HAVING clause.
 287                  */
 288                 if (! set_agg_tlist_references((Agg *) result_plan))
 289                         elog(ERROR, "SELECT/HAVING requires aggregates to be valid");
 290
 291                 /*
 292                  * Check that we actually found some aggregates, else executor
 293                  * will die unpleasantly.  (The rewrite module currently has bugs
 294                  * that allow hasAggs to be incorrectly set 'true' sometimes.
 295                  * It's not easy to recover here, since we've already made decisions
 296                  * assuming there will be an Agg node.)
 297                  */
 298                 if (((Agg *) result_plan)->aggs == NIL)
 299                         elog(ERROR, "union_planner: query is marked hasAggs, but I don't see any");
 300         }
 301
 302         /*
 303          * For now, before we hand back the plan, check to see if there is a
 304          * user-specified sort that needs to be done.  Eventually, this will
 305          * be moved into the guts of the planner s.t. user specified sorts
 306          * will be considered as part of the planning process. Since we can
 307          * only make use of user-specified sorts in special cases, we can do
 308          * the optimization step later.
 309          */
 310
 311         if (parse->uniqueFlag)
 312         {
 313                 Plan       *sortplan = make_sortplan(tlist, parse->sortClause, result_plan);
 314
 315                 return ((Plan *) make_unique(tlist, sortplan, parse->uniqueFlag));
 316         }
 317         else
 318         {
 319                 if (parse->sortClause && need_sortplan(parse->sortClause, result_plan))
 320                         return (make_sortplan(tlist, parse->sortClause, result_plan));
 321                 else
 322                         return ((Plan *) result_plan);
 323         }
 324
 325 }
 326
 327 /*---------------
 328  * make_subplanTargetList
 329  *        Generate appropriate target lists when grouping is required.
 330  *
 331  * When union_planner inserts Aggregate and/or Group/Sort plan nodes above
 332  * the result of query_planner, we typically need to pass a different
 333  * target list to query_planner than the outer plan nodes should have.
 334  * This routine generates the correct target list for the subplan, and
 335  * if necessary modifies the target list for the inserted nodes as well.
 336  *
 337  * The initial target list passed from the parser already contains entries
 338  * for all ORDER BY and GROUP BY expressions, but it will not have entries
 339  * for variables used only in HAVING clauses; so we need to add those
 340  * variables to the subplan target list.  Also, if we are doing either
 341  * grouping or aggregation, we flatten all expressions except GROUP BY items
 342  * into their component variables; the other expressions will be computed by
 343  * the inserted nodes rather than by the subplan.  For example,
 344  * given a query like
 345  *              SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
 346  * we want to pass this targetlist to the subplan:
 347  *              a+b,c,d
 348  * where the a+b target will be used by the Sort/Group steps, and the
 349  * c and d targets will be needed to compute the aggregate results.
 350  *
 351  * 'parse' is the query being processed.
 352  * 'tlist' is the query's target list.  CAUTION: list elements may be
 353  * modified by this routine!
 354  * 'groupColIdx' receives an array of column numbers for the GROUP BY
 355  * expressions (if there are any) in the subplan's target list.
 356  *
 357  * The result is the targetlist to be passed to the subplan.  Also,
 358  * the parent tlist is modified so that any nontrivial targetlist items that
 359  * exactly match GROUP BY items are replaced by simple Var nodes referencing
 360  * those outputs of the subplan.  This avoids redundant recalculations in
 361  * cases like
 362  *              SELECT a+1, ... GROUP BY a+1
 363  * Note, however, that other varnodes in the parent's targetlist (and
 364  * havingQual, if any) will still need to be updated to refer to outputs
 365  * of the subplan.  This routine is quite large enough already, so we do
 366  * that later.
 367  *---------------
 368  */
 369 static List *
 370 make_subplanTargetList(Query *parse,
 371                                            List *tlist,
 372                                            AttrNumber **groupColIdx)
 373 {
 374         List       *sub_tlist;
 375         List       *prnt_tlist;
 376         List       *sl,
 377                            *gl;
 378         List       *glc = NIL;
 379         List       *extravars = NIL;
 380         int                     numCols;
 381         AttrNumber *grpColIdx = NULL;
 382         int                     next_resno = 1;
 383
 384         *groupColIdx = NULL;
 385
 386         /* If we're not grouping or aggregating, nothing to do here;
 387          * query_planner should receive the unmodified target list.
 388          */
 389         if (!parse->hasAggs && !parse->groupClause && !parse->havingQual)
 390                 return tlist;
 391
 392         /* If grouping, make a working copy of groupClause list (which we use
 393          * just to verify that we found all the groupClause items in tlist).
 394          * Also allocate space to remember where the group columns are in the
 395          * subplan tlist.
 396          */
 397         numCols = length(parse->groupClause);
 398         if (numCols > 0)
 399         {
 400                 glc = listCopy(parse->groupClause);
 401                 grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
 402                 *groupColIdx = grpColIdx;
 403         }
 404
 405         sub_tlist = new_unsorted_tlist(tlist);  /* make a modifiable copy */
 406
 407         /*
 408          * Step 1: build grpColIdx by finding targetlist items that match
 409          * GroupBy entries.  If there are aggregates, remove non-GroupBy items
 410          * from sub_tlist, and reset its resnos accordingly.  When we leave an
 411          * expression in the subplan tlist, modify the parent tlist to copy the
 412          * value from the subplan output rather than re-evaluating it.
 413          */
 414         prnt_tlist = tlist;                     /* scans parent tlist in sync with sl */
 415         foreach(sl, sub_tlist)
 416         {
 417                 TargetEntry *te = (TargetEntry *) lfirst(sl);
 418                 TargetEntry *parentte = (TargetEntry *) lfirst(prnt_tlist);
 419                 Resdom     *resdom = te->resdom;
 420                 bool            keepInSubPlan = true;
 421                 bool            foundGroupClause = false;
 422                 int                     keyno = 0;
 423
 424                 foreach(gl, parse->groupClause)
 425                 {
 426                         GroupClause *grpcl = (GroupClause *) lfirst(gl);
 427
 428                         keyno++;                        /* sort key # for this GroupClause */
 429                         /* Is it safe to use just resno to match tlist and glist items?? */
 430                         if (grpcl->entry->resdom->resno == resdom->resno)
 431                         {
 432                                 /* Found a matching groupclause; record info for sorting */
 433                                 foundGroupClause = true;
 434                                 resdom->reskey = keyno;
 435                                 resdom->reskeyop = get_opcode(grpcl->grpOpoid);
 436                                 grpColIdx[keyno - 1] = next_resno;
 437                                 /* Remove groupclause from our list of unmatched groupclauses.
 438                                  * NB: this depends on having used a shallow listCopy() above.
 439                                  */
 440                                 glc = lremove((void*) grpcl, glc);
 441                                 break;
 442                         }
 443                 }
 444
 445                 if (! foundGroupClause)
 446                 {
 447                         /*
 448                          * Non-GroupBy entry: remove it from subplan if there are
 449                          * aggregates in query - it will be evaluated by Aggregate plan.
 450                          * But do not remove simple-Var entries; we'd just have to add
 451                          * them back anyway, and we risk confusing INSERT/UPDATE.
 452                          */
 453                         if (parse->hasAggs && ! IsA(te->expr, Var))
 454                                 keepInSubPlan = false;
 455                 }
 456
 457                 if (keepInSubPlan)
 458                 {
 459                         /* Assign new sequential resnos to subplan tlist items */
 460                         resdom->resno = next_resno++;
 461                         if (! IsA(parentte->expr, Var))
 462                         {
 463                                 /* Since the item is being computed in the subplan,
 464                                  * we can just make a Var node to reference it in the
 465                                  * outer plan, rather than recomputing it there.
 466                                  * Note we use varnoold = -1 as a flag to let
 467                                  * replace_vars_with_subplan_refs know it needn't change
 468                                  * this Var node.
 469                                  * If it's only a Var anyway, we leave it alone for now;
 470                                  * replace_vars_with_subplan_refs will fix it later.
 471                                  */
 472                                 parentte->expr = (Node *) makeVar(1, resdom->resno,
 473                                                                                                   resdom->restype,
 474                                                                                                   resdom->restypmod,
 475                                                                                                   0, -1, resdom->resno);
 476                         }
 477                 }
 478                 else
 479                 {
 480                         /* Remove this tlist item from the subplan, but remember the
 481                          * vars it needs.  The outer tlist item probably needs changes,
 482                          * but that will happen later.
 483                          */
 484                         sub_tlist = lremove(te, sub_tlist);
 485                         extravars = nconc(extravars, pull_var_clause(te->expr));
 486                 }
 487
 488                 prnt_tlist = lnext(prnt_tlist);
 489         }
 490
 491         /* We should have found all the GROUP BY clauses in the tlist. */
 492         if (length(glc) != 0)
 493                 elog(ERROR, "make_subplanTargetList: GROUP BY attribute not found in target list");
 494
 495         /*
 496          * Add subplan targets for any variables needed by removed tlist entries
 497          * that aren't otherwise mentioned in the subplan target list.
 498          * We'll also need targets for any variables seen only in HAVING.
 499          */
 500         extravars = nconc(extravars, pull_var_clause(parse->havingQual));
 501
 502         foreach(gl, extravars)
 503         {
 504                 Var                *v = (Var *) lfirst(gl);
 505
 506                 if (tlist_member(v, sub_tlist) == NULL)
 507                 {
 508                         sub_tlist = lappend(sub_tlist,
 509                                                                 create_tl_element(v, next_resno));
 510                         next_resno++;
 511                 }
 512         }
 513
 514         return sub_tlist;
 515 }
 516
 517 static Plan *
 518 make_groupplan(List *group_tlist,
 519                            bool tuplePerGroup,
 520                            List *groupClause,
 521                            AttrNumber *grpColIdx,
 522                            Plan *subplan)
 523 {
 524         List       *sort_tlist;
 525         List       *sl;
 526         Sort       *sortplan;
 527         Group      *grpplan;
 528         int                     numCols = length(groupClause);
 529
 530         /*
 531          * Make the targetlist for the Sort node; it always just references
 532          * each of the corresponding target items of the subplan.  We need to
 533          * ensure that simple Vars in the subplan's target list are recognizable
 534          * by replace_vars_with_subplan_refs when it's applied to the Sort/Group
 535          * target list, so copy up their varnoold/varoattno.
 536          */
 537         sort_tlist = NIL;
 538         foreach(sl, subplan->targetlist)
 539         {
 540                 TargetEntry *te = (TargetEntry *) lfirst(sl);
 541                 Resdom     *resdom = te->resdom;
 542                 Var                *newvar;
 543
 544                 if (IsA(te->expr, Var))
 545                 {
 546                         Var        *subvar = (Var *) te->expr;
 547                         newvar = makeVar(1, resdom->resno,
 548                                                          resdom->restype, resdom->restypmod,
 549                                                          0, subvar->varnoold, subvar->varoattno);
 550                 }
 551                 else
 552                 {
 553                         newvar = makeVar(1, resdom->resno,
 554                                                          resdom->restype, resdom->restypmod,
 555                                                          0, -1, resdom->resno);
 556                 }
 557
 558                 sort_tlist = lappend(sort_tlist,
 559                                                          makeTargetEntry((Resdom *) copyObject(resdom),
 560                                                                                          (Node *) newvar));
 561         }
 562
 563         /*
 564          * Make the Sort node
 565          */
 566         sortplan = make_sort(sort_tlist,
 567                                                  _NONAME_RELATION_ID_,
 568                                                  subplan,
 569                                                  numCols);
 570         sortplan->plan.cost = subplan->cost;            /* XXX assume no cost */
 571
 572         /*
 573          * If the caller gave us a target list, use it after fixing the variables.
 574          * If not, we need the same sort of "repeater" tlist as for the Sort node.
 575          */
 576         if (group_tlist)
 577         {
 578                 group_tlist = copyObject(group_tlist); /* necessary?? */
 579                 replace_tlist_with_subplan_refs(group_tlist,
 580                                                                                 (Index) 0,
 581                                                                                 subplan->targetlist);
 582         }
 583         else
 584         {
 585                 group_tlist = copyObject(sort_tlist);
 586         }
 587
 588         /*
 589          * Make the Group node
 590          */
 591         grpplan = make_group(group_tlist, tuplePerGroup, numCols,
 592                                                  grpColIdx, sortplan);
 593
 594         return (Plan *) grpplan;
 595 }
 596
 597 /*
 598  * make_sortplan
 599  *        Returns a sortplan which is basically a SORT node attached to the
 600  *        top of the plan returned from the planner.  It also adds the
 601  *         cost of sorting into the plan.
 602  *
 603  * sortkeys: ( resdom1 resdom2 resdom3 ...)
 604  * sortops:  (sortop1 sortop2 sortop3 ...)
 605  */
 606 static Plan *
 607 make_sortplan(List *tlist, List *sortcls, Plan *plannode)
 608 {
 609         Plan       *sortplan = (Plan *) NULL;
 610         List       *temp_tlist = NIL;
 611         List       *i = NIL;
 612         Resdom     *resnode = (Resdom *) NULL;
 613         Resdom     *resdom = (Resdom *) NULL;
 614         int                     keyno = 1;
 615
 616         /*
 617          * First make a copy of the tlist so that we don't corrupt the the
 618          * original .
 619          */
 620
 621         temp_tlist = new_unsorted_tlist(tlist);
 622
 623         foreach(i, sortcls)
 624         {
 625                 SortClause *sortcl = (SortClause *) lfirst(i);
 626
 627                 resnode = sortcl->resdom;
 628                 resdom = tlist_resdom(temp_tlist, resnode);
 629
 630                 /*
 631                  * Order the resdom keys and replace the operator OID for each key
 632                  * with the regproc OID.
 633                  */
 634                 resdom->reskey = keyno;
 635                 resdom->reskeyop = get_opcode(sortcl->opoid);
 636                 keyno += 1;
 637         }
 638
 639         sortplan = (Plan *) make_sort(temp_tlist,
 640                                                                   _NONAME_RELATION_ID_,
 641                                                                   (Plan *) plannode,
 642                                                                   length(sortcls));
 643
 644         /*
 645          * XXX Assuming that an internal sort has no. cost. This is wrong, but
 646          * given that at this point, we don't know the no. of tuples returned,
 647          * etc, we can't do better than to add a constant cost. This will be
 648          * fixed once we move the sort further into the planner, but for now
 649          * ... functionality....
 650          */
 651
 652         sortplan->cost = plannode->cost;
 653
 654         return sortplan;
 655 }
 656
 657 /*
 658  * pg_checkretval() -- check return value of a list of sql parse
 659  *                                              trees.
 660  *
 661  * The return value of a sql function is the value returned by
 662  * the final query in the function.  We do some ad-hoc define-time
 663  * type checking here to be sure that the user is returning the
 664  * type he claims.
 665  *
 666  * XXX Why is this function in this module?
 667  */
 668 void
 669 pg_checkretval(Oid rettype, QueryTreeList *queryTreeList)
 670 {
 671         Query      *parse;
 672         List       *tlist;
 673         List       *rt;
 674         int                     cmd;
 675         Type            typ;
 676         Resdom     *resnode;
 677         Relation        reln;
 678         Oid                     relid;
 679         Oid                     tletype;
 680         int                     relnatts;
 681         int                     i;
 682
 683         /* find the final query */
 684         parse = queryTreeList->qtrees[queryTreeList->len - 1];
 685
 686         /*
 687          * test 1:      if the last query is a utility invocation, then there had
 688          * better not be a return value declared.
 689          */
 690         if (parse->commandType == CMD_UTILITY)
 691         {
 692                 if (rettype == InvalidOid)
 693                         return;
 694                 else
 695                         elog(ERROR, "return type mismatch in function decl: final query is a catalog utility");
 696         }
 697
 698         /* okay, it's an ordinary query */
 699         tlist = parse->targetList;
 700         rt = parse->rtable;
 701         cmd = parse->commandType;
 702
 703         /*
 704          * test 2:      if the function is declared to return no value, then the
 705          * final query had better not be a retrieve.
 706          */
 707         if (rettype == InvalidOid)
 708         {
 709                 if (cmd == CMD_SELECT)
 710                         elog(ERROR,
 711                                  "function declared with no return type, but final query is a retrieve");
 712                 else
 713                         return;
 714         }
 715
 716         /* by here, the function is declared to return some type */
 717         if ((typ = typeidType(rettype)) == NULL)
 718                 elog(ERROR, "can't find return type %d for function\n", rettype);
 719
 720         /*
 721          * test 3:      if the function is declared to return a value, then the
 722          * final query had better be a retrieve.
 723          */
 724         if (cmd != CMD_SELECT)
 725                 elog(ERROR, "function declared to return type %s, but final query is not a retrieve", typeTypeName(typ));
 726
 727         /*
 728          * test 4:      for base type returns, the target list should have exactly
 729          * one entry, and its type should agree with what the user declared.
 730          */
 731
 732         if (typeTypeRelid(typ) == InvalidOid)
 733         {
 734                 if (ExecTargetListLength(tlist) > 1)
 735                         elog(ERROR, "function declared to return %s returns multiple values in final retrieve", typeTypeName(typ));
 736
 737                 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
 738                 if (resnode->restype != rettype)
 739                         elog(ERROR, "return type mismatch in function: declared to return %s, returns %s", typeTypeName(typ), typeidTypeName(resnode->restype));
 740
 741                 /* by here, base return types match */
 742                 return;
 743         }
 744
 745         /*
 746          * If the target list is of length 1, and the type of the varnode in
 747          * the target list is the same as the declared return type, this is
 748          * okay.  This can happen, for example, where the body of the function
 749          * is 'retrieve (x = func2())', where func2 has the same return type
 750          * as the function that's calling it.
 751          */
 752         if (ExecTargetListLength(tlist) == 1)
 753         {
 754                 resnode = (Resdom *) ((TargetEntry *) lfirst(tlist))->resdom;
 755                 if (resnode->restype == rettype)
 756                         return;
 757         }
 758
 759         /*
 760          * By here, the procedure returns a (set of) tuples.  This part of the
 761          * typechecking is a hack.      We look up the relation that is the
 762          * declared return type, and be sure that attributes 1 .. n in the
 763          * target list match the declared types.
 764          */
 765         reln = heap_open(typeTypeRelid(typ));
 766
 767         if (!RelationIsValid(reln))
 768                 elog(ERROR, "cannot open relation relid %d", typeTypeRelid(typ));
 769
 770         relid = reln->rd_id;
 771         relnatts = reln->rd_rel->relnatts;
 772
 773         if (ExecTargetListLength(tlist) != relnatts)
 774                 elog(ERROR, "function declared to return type %s does not retrieve (%s.*)", typeTypeName(typ), typeTypeName(typ));
 775
 776         /* expect attributes 1 .. n in order */
 777         for (i = 1; i <= relnatts; i++)
 778         {
 779                 TargetEntry *tle = lfirst(tlist);
 780                 Node       *thenode = tle->expr;
 781
 782                 tlist = lnext(tlist);
 783                 tletype = exprType(thenode);
 784
 785 #ifdef NOT_USED                                         /* fix me */
 786                 /* this is tedious */
 787                 if (IsA(thenode, Var))
 788                         tletype = (Oid) ((Var *) thenode)->vartype;
 789                 else if (IsA(thenode, Const))
 790                         tletype = (Oid) ((Const *) thenode)->consttype;
 791                 else if (IsA(thenode, Param))
 792                         tletype = (Oid) ((Param *) thenode)->paramtype;
 793                 else if (IsA(thenode, Expr))
 794                         tletype = Expr;
 795
 796                 else if (IsA(thenode, LispList))
 797                 {
 798                         thenode = lfirst(thenode);
 799                         if (IsA(thenode, Oper))
 800                                 tletype = (Oid) get_opresulttype((Oper *) thenode);
 801                         else if (IsA(thenode, Func))
 802                                 tletype = (Oid) get_functype((Func *) thenode);
 803                         else
 804                                 elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
 805                 }
 806                 else
 807                         elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
 808 #endif
 809                 /* reach right in there, why don't you? */
 810                 if (tletype != reln->rd_att->attrs[i - 1]->atttypid)
 811                         elog(ERROR, "function declared to return type %s does not retrieve (%s.all)", typeTypeName(typ), typeTypeName(typ));
 812         }
 813
 814         heap_close(reln);
 815
 816         /* success */
 817         return;
 818 }
 819
 820
 821 /* ----------
 822  * Support function for need_sortplan
 823  * ----------
 824  */
 825 static TargetEntry *
 826 get_matching_tle(Plan *plan, Resdom *resdom)
 827 {
 828         List            *i;
 829         TargetEntry     *tle;
 830
 831         foreach (i, plan->targetlist) {
 832                 tle = (TargetEntry *)lfirst(i);
 833                 if (tle->resdom->resno == resdom->resno)
 834                         return tle;
 835         }
 836         return NULL;
 837 }
 838
 839
 840 /* ----------
 841  * Check if a user requested ORDER BY is already satisfied by
 842  * the choosen index scan.
 843  *
 844  * Returns TRUE if sort is required, FALSE if can be omitted.
 845  * ----------
 846  */
 847 static bool
 848 need_sortplan(List *sortcls, Plan *plan)
 849 {
 850         Relation        indexRel;
 851         IndexScan       *indexScan;
 852         Oid             indexId;
 853         List            *i;
 854         HeapTuple       htup;
 855         Form_pg_index   index_tup;
 856         int             key_no = 0;
 857
 858         /* ----------
 859          * Must be an IndexScan
 860          * ----------
 861          */
 862         if (nodeTag(plan) != T_IndexScan) {
 863                 return TRUE;
 864         }
 865
 866         indexScan = (IndexScan *)plan;
 867
 868         /* ----------
 869          * Should not have left- or righttree
 870          * ----------
 871          */
 872         if (plan->lefttree != NULL) {
 873                 return TRUE;
 874         }
 875         if (plan->righttree != NULL) {
 876                 return TRUE;
 877         }
 878
 879         /* ----------
 880          * Must be a single index scan
 881          * ----------
 882          */
 883         if (length(indexScan->indxid) != 1) {
 884                 return TRUE;
 885         }
 886
 887         /* ----------
 888          * Indices can only have up to 8 attributes. So an ORDER BY using
 889          * more that 8 attributes could never be satisfied by an index.
 890          * ----------
 891          */
 892         if (length(sortcls) > 8) {
 893                 return TRUE;
 894         }
 895
 896         /* ----------
 897          * The choosen Index must be a btree
 898          * ----------
 899          */
 900         indexId = lfirsti(indexScan->indxid);
 901
 902         indexRel = index_open(indexId);
 903         if (strcmp(nameout(&(indexRel->rd_am->amname)), "btree") != 0) {
 904                 heap_close(indexRel);
 905                 return TRUE;
 906         }
 907         heap_close(indexRel);
 908
 909         /* ----------
 910          * Fetch the index tuple
 911          * ----------
 912          */
 913         htup = SearchSysCacheTuple(INDEXRELID,
 914                         ObjectIdGetDatum(indexId), 0, 0, 0);
 915         if (!HeapTupleIsValid(htup)) {
 916                 elog(ERROR, "cache lookup for index %d failed", indexId);
 917         }
 918         index_tup = (Form_pg_index) GETSTRUCT(htup);
 919
 920         /* ----------
 921          * Check if all the sort clauses match the attributes in the index
 922          * ----------
 923          */
 924         foreach (i, sortcls) {
 925                 SortClause      *sortcl;
 926                 Resdom          *resdom;
 927                 TargetEntry     *tle;
 928                 Var             *var;
 929
 930                 sortcl = (SortClause *) lfirst(i);
 931
 932                 resdom = sortcl->resdom;
 933                 tle = get_matching_tle(plan, resdom);
 934                 if (tle == NULL) {
 935                         /* ----------
 936                          * Could this happen?
 937                          * ----------
 938                          */
 939                         return TRUE;
 940                 }
 941                 if (nodeTag(tle->expr) != T_Var) {
 942                         /* ----------
 943                          * The target list expression isn't a var, so it
 944                          * cannot be the indexed attribute
 945                          * ----------
 946                          */
 947                         return TRUE;
 948                 }
 949                 var = (Var *)(tle->expr);
 950
 951                 if (var->varno != indexScan->scan.scanrelid) {
 952                         /* ----------
 953                          * This Var isn't from the scan relation. So it isn't
 954                          * that of the index
 955                          * ----------
 956                          */
 957                         return TRUE;
 958                 }
 959
 960                 if (var->varattno != index_tup->indkey[key_no]) {
 961                         /* ----------
 962                          * It isn't the indexed attribute.
 963                          * ----------
 964                          */
 965                         return TRUE;
 966                 }
 967
 968                 if (oprid(oper("<", resdom->restype, resdom->restype, FALSE)) != sortcl->opoid) {
 969                         /* ----------
 970                          * Sort order isn't in ascending order.
 971                          * ----------
 972                          */
 973                         return TRUE;
 974                 }
 975
 976                 key_no++;
 977         }
 978
 979         /* ----------
 980          * Index matches ORDER BY - sort not required
 981          * ----------
 982          */
 983         return FALSE;
 984 }
 985