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