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