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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * createplan.c
   4  *        Routines to create the desired plan for processing a query.
   5  *        Planning is complete, we just need to convert the selected
   6  *        Path into a Plan.
   7  *
   8  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
   9  * Portions Copyright (c) 1994, Regents of the University of California
  10  *
  11  *
  12  * IDENTIFICATION
  13  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.139 2003/05/06 00:20:32 tgl Exp $
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #include "postgres.h"
  18
  19 #include <limits.h>
  20
  21 #include "nodes/makefuncs.h"
  22 #include "nodes/nodeFuncs.h"
  23 #include "optimizer/clauses.h"
  24 #include "optimizer/cost.h"
  25 #include "optimizer/paths.h"
  26 #include "optimizer/planmain.h"
  27 #include "optimizer/restrictinfo.h"
  28 #include "optimizer/tlist.h"
  29 #include "optimizer/var.h"
  30 #include "parser/parse_clause.h"
  31 #include "parser/parse_expr.h"
  32 #include "utils/lsyscache.h"
  33 #include "utils/syscache.h"
  34
  35
  36 static Scan *create_scan_plan(Query *root, Path *best_path);
  37 static bool use_physical_tlist(RelOptInfo *rel);
  38 static void disuse_physical_tlist(Plan *plan, Path *path);
  39 static Join *create_join_plan(Query *root, JoinPath *best_path);
  40 static Append *create_append_plan(Query *root, AppendPath *best_path);
  41 static Result *create_result_plan(Query *root, ResultPath *best_path);
  42 static Material *create_material_plan(Query *root, MaterialPath *best_path);
  43 static Plan *create_unique_plan(Query *root, UniquePath *best_path);
  44 static SeqScan *create_seqscan_plan(Path *best_path, List *tlist,
  45                                         List *scan_clauses);
  46 static IndexScan *create_indexscan_plan(Query *root, IndexPath *best_path,
  47                                           List *tlist, List *scan_clauses);
  48 static TidScan *create_tidscan_plan(TidPath *best_path, List *tlist,
  49                                         List *scan_clauses);
  50 static SubqueryScan *create_subqueryscan_plan(Path *best_path,
  51                                                  List *tlist, List *scan_clauses);
  52 static FunctionScan *create_functionscan_plan(Path *best_path,
  53                                                  List *tlist, List *scan_clauses);
  54 static NestLoop *create_nestloop_plan(Query *root,
  55                                          NestPath *best_path, List *tlist,
  56                                          List *joinclauses, List *otherclauses,
  57                                          Plan *outer_plan, Plan *inner_plan);
  58 static MergeJoin *create_mergejoin_plan(Query *root,
  59                                           MergePath *best_path, List *tlist,
  60                                           List *joinclauses, List *otherclauses,
  61                                           Plan *outer_plan, Plan *inner_plan);
  62 static HashJoin *create_hashjoin_plan(Query *root,
  63                                          HashPath *best_path, List *tlist,
  64                                          List *joinclauses, List *otherclauses,
  65                                          Plan *outer_plan, Plan *inner_plan);
  66 static void fix_indxqual_references(List *indexquals, IndexPath *index_path,
  67                                                 List **fixed_indexquals,
  68                                                 List **recheck_indexquals);
  69 static void fix_indxqual_sublist(List *indexqual,
  70                                                                  Relids baserelids, int baserelid,
  71                                                                  IndexOptInfo *index,
  72                                                                  List **fixed_quals, List **recheck_quals);
  73 static Node *fix_indxqual_operand(Node *node, int baserelid,
  74                                          IndexOptInfo *index,
  75                                          Oid *opclass);
  76 static List *get_switched_clauses(List *clauses, Relids outerrelids);
  77 static List *order_qual_clauses(Query *root, List *clauses);
  78 static void copy_path_costsize(Plan *dest, Path *src);
  79 static void copy_plan_costsize(Plan *dest, Plan *src);
  80 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
  81 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
  82                            List *indxid, List *indxqual,
  83                            List *indxqualorig,
  84                            ScanDirection indexscandir);
  85 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
  86                          List *tideval);
  87 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
  88                                   Index scanrelid);
  89 static NestLoop *make_nestloop(List *tlist,
  90                           List *joinclauses, List *otherclauses,
  91                           Plan *lefttree, Plan *righttree,
  92                           JoinType jointype);
  93 static HashJoin *make_hashjoin(List *tlist,
  94                           List *joinclauses, List *otherclauses,
  95                           List *hashclauses,
  96                           Plan *lefttree, Plan *righttree,
  97                           JoinType jointype);
  98 static Hash *make_hash(List *tlist, List *hashkeys, Plan *lefttree);
  99 static MergeJoin *make_mergejoin(List *tlist,
 100                            List *joinclauses, List *otherclauses,
 101                            List *mergeclauses,
 102                            Plan *lefttree, Plan *righttree,
 103                            JoinType jointype);
 104 static Sort *make_sort(Query *root, List *tlist, Plan *lefttree, int numCols,
 105                                            AttrNumber *sortColIdx, Oid *sortOperators);
 106 static Sort *make_sort_from_pathkeys(Query *root, Plan *lefttree,
 107                                                                          Relids relids, List *pathkeys);
 108
 109
 110 /*
 111  * create_plan
 112  *        Creates the access plan for a query by tracing backwards through the
 113  *        desired chain of pathnodes, starting at the node 'best_path'.  For
 114  *        every pathnode found:
 115  *        (1) Create a corresponding plan node containing appropriate id,
 116  *                target list, and qualification information.
 117  *        (2) Modify qual clauses of join nodes so that subplan attributes are
 118  *                referenced using relative values.
 119  *        (3) Target lists are not modified, but will be in setrefs.c.
 120  *
 121  *        best_path is the best access path
 122  *
 123  *        Returns a Plan tree.
 124  */
 125 Plan *
 126 create_plan(Query *root, Path *best_path)
 127 {
 128         Plan       *plan;
 129
 130         switch (best_path->pathtype)
 131         {
 132                 case T_IndexScan:
 133                 case T_SeqScan:
 134                 case T_TidScan:
 135                 case T_SubqueryScan:
 136                 case T_FunctionScan:
 137                         plan = (Plan *) create_scan_plan(root, best_path);
 138                         break;
 139                 case T_HashJoin:
 140                 case T_MergeJoin:
 141                 case T_NestLoop:
 142                         plan = (Plan *) create_join_plan(root,
 143                                                                                          (JoinPath *) best_path);
 144                         break;
 145                 case T_Append:
 146                         plan = (Plan *) create_append_plan(root,
 147                                                                                            (AppendPath *) best_path);
 148                         break;
 149                 case T_Result:
 150                         plan = (Plan *) create_result_plan(root,
 151                                                                                            (ResultPath *) best_path);
 152                         break;
 153                 case T_Material:
 154                         plan = (Plan *) create_material_plan(root,
 155                                                                                                  (MaterialPath *) best_path);
 156                         break;
 157                 case T_Unique:
 158                         plan = (Plan *) create_unique_plan(root,
 159                                                                                            (UniquePath *) best_path);
 160                         break;
 161                 default:
 162                         elog(ERROR, "create_plan: unknown pathtype %d",
 163                                  best_path->pathtype);
 164                         plan = NULL;            /* keep compiler quiet */
 165                         break;
 166         }
 167
 168 #ifdef NOT_USED                                 /* fix xfunc */
 169         /* sort clauses by cost/(1-selectivity) -- JMH 2/26/92 */
 170         if (XfuncMode != XFUNC_OFF)
 171         {
 172                 set_qpqual((Plan) plan,
 173                                    lisp_qsort(get_qpqual((Plan) plan),
 174                                                           xfunc_clause_compare));
 175                 if (XfuncMode != XFUNC_NOR)
 176                         /* sort the disjuncts within each clause by cost -- JMH 3/4/92 */
 177                         xfunc_disjunct_sort(plan->qpqual);
 178         }
 179 #endif
 180
 181         return plan;
 182 }
 183
 184 /*
 185  * create_scan_plan
 186  *       Create a scan plan for the parent relation of 'best_path'.
 187  *
 188  *       Returns a Plan node.
 189  */
 190 static Scan *
 191 create_scan_plan(Query *root, Path *best_path)
 192 {
 193         RelOptInfo *rel = best_path->parent;
 194         List       *tlist;
 195         List       *scan_clauses;
 196         Scan       *plan;
 197
 198         /*
 199          * For table scans, rather than using the relation targetlist (which is
 200          * only those Vars actually needed by the query), we prefer to generate a
 201          * tlist containing all Vars in order.  This will allow the executor to
 202          * optimize away projection of the table tuples, if possible.  (Note that
 203          * planner.c may replace the tlist we generate here, forcing projection to
 204          * occur.)
 205          */
 206         if (use_physical_tlist(rel))
 207         {
 208                 int             resdomno = 1;
 209                 List   *v;
 210
 211                 tlist = NIL;
 212                 foreach(v, rel->varlist)
 213                 {
 214                         Var        *var = (Var *) lfirst(v);
 215
 216                         tlist = lappend(tlist, create_tl_element(var, resdomno));
 217                         resdomno++;
 218                 }
 219         }
 220         else
 221                 tlist = rel->targetlist;
 222
 223         /*
 224          * Extract the relevant restriction clauses from the parent relation;
 225          * the executor must apply all these restrictions during the scan.
 226          */
 227         scan_clauses = get_actual_clauses(rel->baserestrictinfo);
 228
 229         /* Sort clauses into best execution order */
 230         scan_clauses = order_qual_clauses(root, scan_clauses);
 231
 232         switch (best_path->pathtype)
 233         {
 234                 case T_SeqScan:
 235                         plan = (Scan *) create_seqscan_plan(best_path,
 236                                                                                                 tlist,
 237                                                                                                 scan_clauses);
 238                         break;
 239
 240                 case T_IndexScan:
 241                         plan = (Scan *) create_indexscan_plan(root,
 242                                                                                                   (IndexPath *) best_path,
 243                                                                                                   tlist,
 244                                                                                                   scan_clauses);
 245                         break;
 246
 247                 case T_TidScan:
 248                         plan = (Scan *) create_tidscan_plan((TidPath *) best_path,
 249                                                                                                 tlist,
 250                                                                                                 scan_clauses);
 251                         break;
 252
 253                 case T_SubqueryScan:
 254                         plan = (Scan *) create_subqueryscan_plan(best_path,
 255                                                                                                          tlist,
 256                                                                                                          scan_clauses);
 257                         break;
 258
 259                 case T_FunctionScan:
 260                         plan = (Scan *) create_functionscan_plan(best_path,
 261                                                                                                          tlist,
 262                                                                                                          scan_clauses);
 263                         break;
 264
 265                 default:
 266                         elog(ERROR, "create_scan_plan: unknown node type: %d",
 267                                  best_path->pathtype);
 268                         plan = NULL;            /* keep compiler quiet */
 269                         break;
 270         }
 271
 272         return plan;
 273 }
 274
 275 /*
 276  * use_physical_tlist
 277  *              Decide whether to use a tlist matching relation structure,
 278  *              rather than only those Vars actually referenced.
 279  */
 280 static bool
 281 use_physical_tlist(RelOptInfo *rel)
 282 {
 283         List       *t;
 284
 285         /*
 286          * Currently, can't do this for subquery or function scans.  (This
 287          * is mainly because we don't set up the necessary info when creating
 288          * their RelOptInfo nodes.)
 289          */
 290         if (rel->rtekind != RTE_RELATION)
 291                 return false;
 292         /*
 293          * Can't do it with inheritance cases either (mainly because Append
 294          * doesn't project).
 295          */
 296         if (rel->reloptkind != RELOPT_BASEREL)
 297                 return false;
 298         /*
 299          * Can't do it if any system columns are requested, either.  (This could
 300          * possibly be fixed but would take some fragile assumptions in setrefs.c,
 301          * I think.)
 302          */
 303         foreach(t, rel->targetlist)
 304         {
 305                 TargetEntry *tle = (TargetEntry *) lfirst(t);
 306                 Var                *var = (Var *) tle->expr;
 307
 308                 if (!var || !IsA(var, Var))
 309                         return false;           /* probably can't happen */
 310                 if (var->varattno <= 0)
 311                         return false;           /* system column! */
 312         }
 313         return true;
 314 }
 315
 316 /*
 317  * disuse_physical_tlist
 318  *              Switch a plan node back to emitting only Vars actually referenced.
 319  *
 320  * If the plan node immediately above a scan would prefer to get only
 321  * needed Vars and not a physical tlist, it must call this routine to
 322  * undo the decision made by use_physical_tlist().  Currently, Hash, Sort,
 323  * and Material nodes want this, so they don't have to store useless columns.
 324  */
 325 static void
 326 disuse_physical_tlist(Plan *plan, Path *path)
 327 {
 328         /* Only need to undo it for path types handled by create_scan_plan() */
 329         switch (path->pathtype)
 330         {
 331                 case T_IndexScan:
 332                 case T_SeqScan:
 333                 case T_TidScan:
 334                 case T_SubqueryScan:
 335                 case T_FunctionScan:
 336                         plan->targetlist = path->parent->targetlist;
 337                         break;
 338                 default:
 339                         break;
 340         }
 341 }
 342
 343 /*
 344  * create_join_plan
 345  *        Create a join plan for 'best_path' and (recursively) plans for its
 346  *        inner and outer paths.
 347  *
 348  *        Returns a Plan node.
 349  */
 350 static Join *
 351 create_join_plan(Query *root, JoinPath *best_path)
 352 {
 353         List       *join_tlist = best_path->path.parent->targetlist;
 354         Plan       *outer_plan;
 355         Plan       *inner_plan;
 356         List       *joinclauses;
 357         List       *otherclauses;
 358         Join       *plan;
 359
 360         outer_plan = create_plan(root, best_path->outerjoinpath);
 361         inner_plan = create_plan(root, best_path->innerjoinpath);
 362
 363         if (IS_OUTER_JOIN(best_path->jointype))
 364         {
 365                 get_actual_join_clauses(best_path->joinrestrictinfo,
 366                                                                 &joinclauses, &otherclauses);
 367         }
 368         else
 369         {
 370                 /* We can treat all clauses alike for an inner join */
 371                 joinclauses = get_actual_clauses(best_path->joinrestrictinfo);
 372                 otherclauses = NIL;
 373         }
 374
 375         switch (best_path->path.pathtype)
 376         {
 377                 case T_MergeJoin:
 378                         plan = (Join *) create_mergejoin_plan(root,
 379                                                                                                   (MergePath *) best_path,
 380                                                                                                   join_tlist,
 381                                                                                                   joinclauses,
 382                                                                                                   otherclauses,
 383                                                                                                   outer_plan,
 384                                                                                                   inner_plan);
 385                         break;
 386                 case T_HashJoin:
 387                         plan = (Join *) create_hashjoin_plan(root,
 388                                                                                                  (HashPath *) best_path,
 389                                                                                                  join_tlist,
 390                                                                                                  joinclauses,
 391                                                                                                  otherclauses,
 392                                                                                                  outer_plan,
 393                                                                                                  inner_plan);
 394                         break;
 395                 case T_NestLoop:
 396                         plan = (Join *) create_nestloop_plan(root,
 397                                                                                                  (NestPath *) best_path,
 398                                                                                                  join_tlist,
 399                                                                                                  joinclauses,
 400                                                                                                  otherclauses,
 401                                                                                                  outer_plan,
 402                                                                                                  inner_plan);
 403                         break;
 404                 default:
 405                         elog(ERROR, "create_join_plan: unknown node type: %d",
 406                                  best_path->path.pathtype);
 407                         plan = NULL;            /* keep compiler quiet */
 408                         break;
 409         }
 410
 411 #ifdef NOT_USED
 412
 413         /*
 414          * * Expensive function pullups may have pulled local predicates *
 415          * into this path node.  Put them in the qpqual of the plan node. *
 416          * JMH, 6/15/92
 417          */
 418         if (get_loc_restrictinfo(best_path) != NIL)
 419                 set_qpqual((Plan) plan,
 420                                    nconc(get_qpqual((Plan) plan),
 421                                    get_actual_clauses(get_loc_restrictinfo(best_path))));
 422 #endif
 423
 424         return plan;
 425 }
 426
 427 /*
 428  * create_append_plan
 429  *        Create an Append plan for 'best_path' and (recursively) plans
 430  *        for its subpaths.
 431  *
 432  *        Returns a Plan node.
 433  */
 434 static Append *
 435 create_append_plan(Query *root, AppendPath *best_path)
 436 {
 437         Append     *plan;
 438         List       *tlist = best_path->path.parent->targetlist;
 439         List       *subplans = NIL;
 440         List       *subpaths;
 441
 442         foreach(subpaths, best_path->subpaths)
 443         {
 444                 Path       *subpath = (Path *) lfirst(subpaths);
 445
 446                 subplans = lappend(subplans, create_plan(root, subpath));
 447         }
 448
 449         plan = make_append(subplans, false, tlist);
 450
 451         return plan;
 452 }
 453
 454 /*
 455  * create_result_plan
 456  *        Create a Result plan for 'best_path' and (recursively) plans
 457  *        for its subpaths.
 458  *
 459  *        Returns a Plan node.
 460  */
 461 static Result *
 462 create_result_plan(Query *root, ResultPath *best_path)
 463 {
 464         Result     *plan;
 465         List       *tlist;
 466         List       *constclauses;
 467         Plan       *subplan;
 468
 469         if (best_path->path.parent)
 470                 tlist = best_path->path.parent->targetlist;
 471         else
 472                 tlist = NIL;                    /* will be filled in later */
 473
 474         if (best_path->subpath)
 475                 subplan = create_plan(root, best_path->subpath);
 476         else
 477                 subplan = NULL;
 478
 479         constclauses = order_qual_clauses(root, best_path->constantqual);
 480
 481         plan = make_result(tlist, (Node *) constclauses, subplan);
 482
 483         return plan;
 484 }
 485
 486 /*
 487  * create_material_plan
 488  *        Create a Material plan for 'best_path' and (recursively) plans
 489  *        for its subpaths.
 490  *
 491  *        Returns a Plan node.
 492  */
 493 static Material *
 494 create_material_plan(Query *root, MaterialPath *best_path)
 495 {
 496         Material   *plan;
 497         Plan       *subplan;
 498
 499         subplan = create_plan(root, best_path->subpath);
 500
 501         /* We don't want any excess columns in the materialized tuples */
 502         disuse_physical_tlist(subplan, best_path->subpath);
 503
 504         plan = make_material(subplan->targetlist, subplan);
 505
 506         copy_path_costsize(&plan->plan, (Path *) best_path);
 507
 508         return plan;
 509 }
 510
 511 /*
 512  * create_unique_plan
 513  *        Create a Unique plan for 'best_path' and (recursively) plans
 514  *        for its subpaths.
 515  *
 516  *        Returns a Plan node.
 517  */
 518 static Plan *
 519 create_unique_plan(Query *root, UniquePath *best_path)
 520 {
 521         Plan       *plan;
 522         Plan       *subplan;
 523         List       *sub_targetlist;
 524         List       *my_tlist;
 525         List       *l;
 526
 527         subplan = create_plan(root, best_path->subpath);
 528
 529         /*
 530          * If the subplan came from an IN subselect (currently always the case),
 531          * we need to instantiate the correct output targetlist for the subselect,
 532          * rather than using the flattened tlist.
 533          */
 534         sub_targetlist = NIL;
 535         foreach(l, root->in_info_list)
 536         {
 537                 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
 538
 539                 if (bms_equal(ininfo->righthand, best_path->path.parent->relids))
 540                 {
 541                         sub_targetlist = ininfo->sub_targetlist;
 542                         break;
 543                 }
 544         }
 545
 546         if (sub_targetlist)
 547         {
 548                 /*
 549                  * Transform list of plain Vars into targetlist
 550                  */
 551                 List   *newtlist = NIL;
 552                 int             resno = 1;
 553
 554                 foreach(l, sub_targetlist)
 555                 {
 556                         Node       *tlexpr = lfirst(l);
 557                         TargetEntry *tle;
 558
 559                         tle = makeTargetEntry(makeResdom(resno,
 560                                                                                          exprType(tlexpr),
 561                                                                                          exprTypmod(tlexpr),
 562                                                                                          NULL,
 563                                                                                          false),
 564                                                                   (Expr *) tlexpr);
 565                         newtlist = lappend(newtlist, tle);
 566                         resno++;
 567                 }
 568                 /*
 569                  * If the top plan node can't do projections, we need to add a
 570                  * Result node to help it along.
 571                  *
 572                  * Currently, the only non-projection-capable plan type
 573                  * we can see here is Append.
 574                  */
 575                 if (IsA(subplan, Append))
 576                         subplan = (Plan *) make_result(newtlist, NULL, subplan);
 577                 else
 578                         subplan->targetlist = newtlist;
 579         }
 580
 581         my_tlist = copyObject(subplan->targetlist);
 582
 583         if (best_path->use_hash)
 584         {
 585                 int             numGroupCols = length(my_tlist);
 586                 long    numGroups;
 587                 AttrNumber *groupColIdx;
 588                 int             i;
 589
 590                 numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
 591
 592                 groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
 593                 for (i = 0; i < numGroupCols; i++)
 594                         groupColIdx[i] = i+1;
 595
 596                 plan = (Plan *) make_agg(root,
 597                                                                  my_tlist,
 598                                                                  NIL,
 599                                                                  AGG_HASHED,
 600                                                                  numGroupCols,
 601                                                                  groupColIdx,
 602                                                                  numGroups,
 603                                                                  0,
 604                                                                  subplan);
 605         }
 606         else
 607         {
 608                 List       *sortList;
 609
 610                 sortList = addAllTargetsToSortList(NIL, my_tlist);
 611                 plan = (Plan *) make_sort_from_sortclauses(root, my_tlist,
 612                                                                                                    subplan, sortList);
 613                 plan = (Plan *) make_unique(my_tlist, plan, sortList);
 614         }
 615
 616         plan->plan_rows = best_path->rows;
 617
 618         return plan;
 619 }
 620
 621
 622 /*****************************************************************************
 623  *
 624  *      BASE-RELATION SCAN METHODS
 625  *
 626  *****************************************************************************/
 627
 628
 629 /*
 630  * create_seqscan_plan
 631  *       Returns a seqscan plan for the base relation scanned by 'best_path'
 632  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 633  */
 634 static SeqScan *
 635 create_seqscan_plan(Path *best_path, List *tlist, List *scan_clauses)
 636 {
 637         SeqScan    *scan_plan;
 638         Index           scan_relid = best_path->parent->relid;
 639
 640         /* it should be a base rel... */
 641         Assert(scan_relid > 0);
 642         Assert(best_path->parent->rtekind == RTE_RELATION);
 643
 644         scan_plan = make_seqscan(tlist,
 645                                                          scan_clauses,
 646                                                          scan_relid);
 647
 648         copy_path_costsize(&scan_plan->plan, best_path);
 649
 650         return scan_plan;
 651 }
 652
 653 /*
 654  * create_indexscan_plan
 655  *        Returns a indexscan plan for the base relation scanned by 'best_path'
 656  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 657  *
 658  * The indexqual of the path contains a sublist of implicitly-ANDed qual
 659  * conditions for each scan of the index(es); if there is more than one
 660  * scan then the retrieved tuple sets are ORed together.  The indexqual
 661  * and indexinfo lists must have the same length, ie, the number of scans
 662  * that will occur.  Note it is possible for a qual condition sublist
 663  * to be empty --- then no index restrictions will be applied during that
 664  * scan.
 665  */
 666 static IndexScan *
 667 create_indexscan_plan(Query *root,
 668                                           IndexPath *best_path,
 669                                           List *tlist,
 670                                           List *scan_clauses)
 671 {
 672         List       *indxqual = best_path->indexqual;
 673         Index           baserelid = best_path->path.parent->relid;
 674         List       *qpqual;
 675         Expr       *indxqual_or_expr = NULL;
 676         List       *fixed_indxqual;
 677         List       *recheck_indxqual;
 678         List       *indexids;
 679         List       *ixinfo;
 680         IndexScan  *scan_plan;
 681
 682         /* it should be a base rel... */
 683         Assert(baserelid > 0);
 684         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 685
 686         /*
 687          * Build list of index OIDs.
 688          */
 689         indexids = NIL;
 690         foreach(ixinfo, best_path->indexinfo)
 691         {
 692                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ixinfo);
 693
 694                 indexids = lappendo(indexids, index->indexoid);
 695         }
 696
 697         /*
 698          * The qpqual list must contain all restrictions not automatically
 699          * handled by the index.  Normally the predicates in the indxqual are
 700          * checked fully by the index, but if the index is "lossy" for a
 701          * particular operator (as signaled by the amopreqcheck flag in
 702          * pg_amop), then we need to double-check that predicate in qpqual,
 703          * because the index may return more tuples than match the predicate.
 704          *
 705          * Since the indexquals were generated from the restriction clauses given
 706          * by scan_clauses, there will normally be some duplications between
 707          * the lists.  We get rid of the duplicates, then add back if lossy.
 708          */
 709         if (length(indxqual) > 1)
 710         {
 711                 /*
 712                  * Build an expression representation of the indexqual, expanding
 713                  * the implicit OR and AND semantics of the first- and
 714                  * second-level lists.
 715                  */
 716                 List       *orclauses = NIL;
 717                 List       *orclause;
 718
 719                 foreach(orclause, indxqual)
 720                 {
 721                         orclauses = lappend(orclauses,
 722                                                                 make_ands_explicit(lfirst(orclause)));
 723                 }
 724                 indxqual_or_expr = make_orclause(orclauses);
 725
 726                 qpqual = set_difference(scan_clauses, makeList1(indxqual_or_expr));
 727         }
 728         else if (indxqual != NIL)
 729         {
 730                 /*
 731                  * Here, we can simply treat the first sublist as an independent
 732                  * set of qual expressions, since there is no top-level OR
 733                  * behavior.
 734                  */
 735                 qpqual = set_difference(scan_clauses, lfirst(indxqual));
 736         }
 737         else
 738                 qpqual = scan_clauses;
 739
 740         /*
 741          * The executor needs a copy with the indexkey on the left of each
 742          * clause and with index attr numbers substituted for table ones. This
 743          * pass also looks for "lossy" operators.
 744          */
 745         fix_indxqual_references(indxqual, best_path,
 746                                                         &fixed_indxqual, &recheck_indxqual);
 747
 748         /*
 749          * If there were any "lossy" operators, need to add back the
 750          * appropriate qual clauses to the qpqual.      When there is just one
 751          * indexscan being performed (ie, we have simple AND semantics), we
 752          * can just add the lossy clauses themselves to qpqual.  If we have
 753          * OR-of-ANDs, we'd better add the entire original indexqual to make
 754          * sure that the semantics are correct.
 755          */
 756         if (recheck_indxqual != NIL)
 757         {
 758                 if (indxqual_or_expr)
 759                 {
 760                         /* Better do a deep copy of the original scanclauses */
 761                         qpqual = lappend(qpqual, copyObject(indxqual_or_expr));
 762                 }
 763                 else
 764                 {
 765                         /* Subroutine already copied quals, so just append to list */
 766                         Assert(length(recheck_indxqual) == 1);
 767                         qpqual = nconc(qpqual, (List *) lfirst(recheck_indxqual));
 768                 }
 769         }
 770
 771         /* Finally ready to build the plan node */
 772         scan_plan = make_indexscan(tlist,
 773                                                            qpqual,
 774                                                            baserelid,
 775                                                            indexids,
 776                                                            fixed_indxqual,
 777                                                            indxqual,
 778                                                            best_path->indexscandir);
 779
 780         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 781         /* use the indexscan-specific rows estimate, not the parent rel's */
 782         scan_plan->scan.plan.plan_rows = best_path->rows;
 783
 784         return scan_plan;
 785 }
 786
 787 /*
 788  * create_tidscan_plan
 789  *       Returns a tidscan plan for the base relation scanned by 'best_path'
 790  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 791  */
 792 static TidScan *
 793 create_tidscan_plan(TidPath *best_path, List *tlist, List *scan_clauses)
 794 {
 795         TidScan    *scan_plan;
 796         Index           scan_relid = best_path->path.parent->relid;
 797
 798         /* it should be a base rel... */
 799         Assert(scan_relid > 0);
 800         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 801
 802         scan_plan = make_tidscan(tlist,
 803                                                          scan_clauses,
 804                                                          scan_relid,
 805                                                          best_path->tideval);
 806
 807         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 808
 809         return scan_plan;
 810 }
 811
 812 /*
 813  * create_subqueryscan_plan
 814  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
 815  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 816  */
 817 static SubqueryScan *
 818 create_subqueryscan_plan(Path *best_path, List *tlist, List *scan_clauses)
 819 {
 820         SubqueryScan *scan_plan;
 821         Index           scan_relid = best_path->parent->relid;
 822
 823         /* it should be a subquery base rel... */
 824         Assert(scan_relid > 0);
 825         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
 826
 827         scan_plan = make_subqueryscan(tlist,
 828                                                                   scan_clauses,
 829                                                                   scan_relid,
 830                                                                   best_path->parent->subplan);
 831
 832         return scan_plan;
 833 }
 834
 835 /*
 836  * create_functionscan_plan
 837  *       Returns a functionscan plan for the base relation scanned by 'best_path'
 838  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 839  */
 840 static FunctionScan *
 841 create_functionscan_plan(Path *best_path, List *tlist, List *scan_clauses)
 842 {
 843         FunctionScan *scan_plan;
 844         Index           scan_relid = best_path->parent->relid;
 845
 846         /* it should be a function base rel... */
 847         Assert(scan_relid > 0);
 848         Assert(best_path->parent->rtekind == RTE_FUNCTION);
 849
 850         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid);
 851
 852         copy_path_costsize(&scan_plan->scan.plan, best_path);
 853
 854         return scan_plan;
 855 }
 856
 857 /*****************************************************************************
 858  *
 859  *      JOIN METHODS
 860  *
 861  *****************************************************************************/
 862
 863 static NestLoop *
 864 create_nestloop_plan(Query *root,
 865                                          NestPath *best_path,
 866                                          List *tlist,
 867                                          List *joinclauses,
 868                                          List *otherclauses,
 869                                          Plan *outer_plan,
 870                                          Plan *inner_plan)
 871 {
 872         NestLoop   *join_plan;
 873
 874         if (IsA(inner_plan, IndexScan))
 875         {
 876                 /*
 877                  * An index is being used to reduce the number of tuples scanned
 878                  * in the inner relation.  If there are join clauses being used
 879                  * with the index, we may remove those join clauses from the list of
 880                  * clauses that have to be checked as qpquals at the join node ---
 881                  * but only if there's just one indexscan in the inner path
 882                  * (otherwise, several different sets of clauses are being ORed
 883                  * together).
 884                  *
 885                  * Note we must compare against indxqualorig not the "fixed" indxqual
 886                  * (which has index attnos instead of relation attnos, and may have
 887                  * been commuted as well).
 888                  */
 889                 IndexScan  *innerscan = (IndexScan *) inner_plan;
 890                 List       *indxqualorig = innerscan->indxqualorig;
 891
 892                 if (length(indxqualorig) == 1) /* single indexscan? */
 893                 {
 894                         /* No work needed if indxqual refers only to its own relation... */
 895                         if (NumRelids((Node *) indxqualorig) > 1)
 896                                 joinclauses = set_difference(joinclauses,
 897                                                                                          lfirst(indxqualorig));
 898                 }
 899         }
 900
 901         join_plan = make_nestloop(tlist,
 902                                                           joinclauses,
 903                                                           otherclauses,
 904                                                           outer_plan,
 905                                                           inner_plan,
 906                                                           best_path->jointype);
 907
 908         copy_path_costsize(&join_plan->join.plan, &best_path->path);
 909
 910         return join_plan;
 911 }
 912
 913 static MergeJoin *
 914 create_mergejoin_plan(Query *root,
 915                                           MergePath *best_path,
 916                                           List *tlist,
 917                                           List *joinclauses,
 918                                           List *otherclauses,
 919                                           Plan *outer_plan,
 920                                           Plan *inner_plan)
 921 {
 922         List       *mergeclauses;
 923         MergeJoin  *join_plan;
 924
 925         /*
 926          * Remove the mergeclauses from the list of join qual clauses, leaving
 927          * the list of quals that must be checked as qpquals.
 928          */
 929         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
 930         joinclauses = set_difference(joinclauses, mergeclauses);
 931
 932         /*
 933          * Rearrange mergeclauses, if needed, so that the outer variable
 934          * is always on the left.
 935          */
 936         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
 937                                                                                 best_path->jpath.outerjoinpath->parent->relids);
 938
 939         /*
 940          * Create explicit sort nodes for the outer and inner join paths if
 941          * necessary.  The sort cost was already accounted for in the path.
 942          * Make sure there are no excess columns in the inputs if sorting.
 943          */
 944         if (best_path->outersortkeys)
 945         {
 946                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
 947                 outer_plan = (Plan *)
 948                         make_sort_from_pathkeys(root,
 949                                                                         outer_plan,
 950                                                                         best_path->jpath.outerjoinpath->parent->relids,
 951                                                                         best_path->outersortkeys);
 952         }
 953
 954         if (best_path->innersortkeys)
 955         {
 956                 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
 957                 inner_plan = (Plan *)
 958                         make_sort_from_pathkeys(root,
 959                                                                         inner_plan,
 960                                                                         best_path->jpath.innerjoinpath->parent->relids,
 961                                                                         best_path->innersortkeys);
 962         }
 963
 964         /*
 965          * Now we can build the mergejoin node.
 966          */
 967         join_plan = make_mergejoin(tlist,
 968                                                            joinclauses,
 969                                                            otherclauses,
 970                                                            mergeclauses,
 971                                                            outer_plan,
 972                                                            inner_plan,
 973                                                            best_path->jpath.jointype);
 974
 975         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
 976
 977         return join_plan;
 978 }
 979
 980 static HashJoin *
 981 create_hashjoin_plan(Query *root,
 982                                          HashPath *best_path,
 983                                          List *tlist,
 984                                          List *joinclauses,
 985                                          List *otherclauses,
 986                                          Plan *outer_plan,
 987                                          Plan *inner_plan)
 988 {
 989         List       *hashclauses;
 990         HashJoin   *join_plan;
 991         Hash       *hash_plan;
 992         List       *innerhashkeys;
 993         List       *hcl;
 994
 995         /*
 996          * Remove the hashclauses from the list of join qual clauses, leaving
 997          * the list of quals that must be checked as qpquals.
 998          */
 999         hashclauses = get_actual_clauses(best_path->path_hashclauses);
1000         joinclauses = set_difference(joinclauses, hashclauses);
1001
1002         /*
1003          * Rearrange hashclauses, if needed, so that the outer variable
1004          * is always on the left.
1005          */
1006         hashclauses = get_switched_clauses(best_path->path_hashclauses,
1007                                                                            best_path->jpath.outerjoinpath->parent->relids);
1008
1009         /*
1010          * Extract the inner hash keys (right-hand operands of the hashclauses)
1011          * to put in the Hash node.
1012          */
1013         innerhashkeys = NIL;
1014         foreach(hcl, hashclauses)
1015         {
1016                 innerhashkeys = lappend(innerhashkeys, get_rightop(lfirst(hcl)));
1017         }
1018
1019         /* We don't want any excess columns in the hashed tuples */
1020         disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1021
1022         /*
1023          * Build the hash node and hash join node.
1024          */
1025         hash_plan = make_hash(inner_plan->targetlist,
1026                                                   innerhashkeys,
1027                                                   inner_plan);
1028         join_plan = make_hashjoin(tlist,
1029                                                           joinclauses,
1030                                                           otherclauses,
1031                                                           hashclauses,
1032                                                           outer_plan,
1033                                                           (Plan *) hash_plan,
1034                                                           best_path->jpath.jointype);
1035
1036         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1037
1038         return join_plan;
1039 }
1040
1041
1042 /*****************************************************************************
1043  *
1044  *      SUPPORTING ROUTINES
1045  *
1046  *****************************************************************************/
1047
1048 /*
1049  * fix_indxqual_references
1050  *        Adjust indexqual clauses to the form the executor's indexqual
1051  *        machinery needs, and check for recheckable (lossy) index conditions.
1052  *
1053  * We have four tasks here:
1054  *      * Index keys must be represented by Var nodes with varattno set to the
1055  *        index's attribute number, not the attribute number in the original rel.
1056  *      * indxpath.c may have selected an index that is binary-compatible with
1057  *        the actual expression operator, but not exactly the same datatype.
1058  *        We must replace the expression's operator with the binary-compatible
1059  *        equivalent operator that the index will recognize.
1060  *      * If the index key is on the right, commute the clause to put it on the
1061  *        left.  (Someday the executor might not need this, but for now it does.)
1062  *      * If the indexable operator is marked 'amopreqcheck' in pg_amop, then
1063  *        the index is "lossy" for this operator: it may return more tuples than
1064  *        actually satisfy the operator condition.      For each such operator, we
1065  *        must add (the original form of) the indexqual clause to the "qpquals"
1066  *        of the indexscan node, where the operator will be re-evaluated to
1067  *        ensure it passes.
1068  *
1069  * This code used to be entirely bogus for multi-index scans.  Now it keeps
1070  * track of which index applies to each subgroup of index qual clauses...
1071  *
1072  * Both the input list and the output lists have the form of lists of sublists
1073  * of qual clauses --- the top-level list has one entry for each indexscan
1074  * to be performed.  The semantics are OR-of-ANDs.
1075  *
1076  * fixed_indexquals receives a modified copy of the indexqual list --- the
1077  * original is not changed.  Note also that the copy shares no substructure
1078  * with the original; this is needed in case there is a subplan in it (we need
1079  * two separate copies of the subplan tree, or things will go awry).
1080  *
1081  * recheck_indexquals similarly receives a full copy of whichever clauses
1082  * need rechecking.
1083  */
1084 static void
1085 fix_indxqual_references(List *indexquals, IndexPath *index_path,
1086                                           List **fixed_indexquals, List **recheck_indexquals)
1087 {
1088         List       *fixed_quals = NIL;
1089         List       *recheck_quals = NIL;
1090         Relids          baserelids = index_path->path.parent->relids;
1091         int                     baserelid = index_path->path.parent->relid;
1092         List       *ixinfo = index_path->indexinfo;
1093         List       *i;
1094
1095         foreach(i, indexquals)
1096         {
1097                 List       *indexqual = lfirst(i);
1098                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ixinfo);
1099                 List       *fixed_qual;
1100                 List       *recheck_qual;
1101
1102                 fix_indxqual_sublist(indexqual, baserelids, baserelid, index,
1103                                                          &fixed_qual, &recheck_qual);
1104                 fixed_quals = lappend(fixed_quals, fixed_qual);
1105                 if (recheck_qual != NIL)
1106                         recheck_quals = lappend(recheck_quals, recheck_qual);
1107
1108                 ixinfo = lnext(ixinfo);
1109         }
1110
1111         *fixed_indexquals = fixed_quals;
1112         *recheck_indexquals = recheck_quals;
1113 }
1114
1115 /*
1116  * Fix the sublist of indexquals to be used in a particular scan.
1117  *
1118  * For each qual clause, commute if needed to put the indexkey operand on the
1119  * left, and then fix its varattno.  (We do not need to change the other side
1120  * of the clause.)      Also change the operator if necessary, and check for
1121  * lossy index behavior.
1122  *
1123  * Returns two lists: the list of fixed indexquals, and the list (usually
1124  * empty) of original clauses that must be rechecked as qpquals because
1125  * the index is lossy for this operator type.
1126  */
1127 static void
1128 fix_indxqual_sublist(List *indexqual,
1129                                          Relids baserelids, int baserelid,
1130                                          IndexOptInfo *index,
1131                                          List **fixed_quals, List **recheck_quals)
1132 {
1133         List       *fixed_qual = NIL;
1134         List       *recheck_qual = NIL;
1135         List       *i;
1136
1137         foreach(i, indexqual)
1138         {
1139                 OpExpr     *clause = (OpExpr *) lfirst(i);
1140                 OpExpr     *newclause;
1141                 Relids          leftvarnos;
1142                 Oid                     opclass;
1143
1144                 if (!IsA(clause, OpExpr) || length(clause->args) != 2)
1145                         elog(ERROR, "fix_indxqual_sublist: indexqual clause is not binary opclause");
1146
1147                 /*
1148                  * Make a copy that will become the fixed clause.
1149                  *
1150                  * We used to try to do a shallow copy here, but that fails if there
1151                  * is a subplan in the arguments of the opclause.  So just do a
1152                  * full copy.
1153                  */
1154                 newclause = (OpExpr *) copyObject((Node *) clause);
1155
1156                 /*
1157                  * Check to see if the indexkey is on the right; if so, commute
1158                  * the clause.  The indexkey should be the side that refers to
1159                  * (only) the base relation.
1160                  */
1161                 leftvarnos = pull_varnos((Node *) lfirst(newclause->args));
1162                 if (!bms_equal(leftvarnos, baserelids))
1163                         CommuteClause(newclause);
1164                 bms_free(leftvarnos);
1165
1166                 /*
1167                  * Now, determine which index attribute this is, change the
1168                  * indexkey operand as needed, and get the index opclass.
1169                  */
1170                 lfirst(newclause->args) = fix_indxqual_operand(lfirst(newclause->args),
1171                                                                                                            baserelid,
1172                                                                                                            index,
1173                                                                                                            &opclass);
1174
1175                 fixed_qual = lappend(fixed_qual, newclause);
1176
1177                 /*
1178                  * Finally, check to see if index is lossy for this operator. If
1179                  * so, add (a copy of) original form of clause to recheck list.
1180                  */
1181                 if (op_requires_recheck(newclause->opno, opclass))
1182                         recheck_qual = lappend(recheck_qual,
1183                                                                    copyObject((Node *) clause));
1184         }
1185
1186         *fixed_quals = fixed_qual;
1187         *recheck_quals = recheck_qual;
1188 }
1189
1190 static Node *
1191 fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index,
1192                                          Oid *opclass)
1193 {
1194         /*
1195          * Remove any binary-compatible relabeling of the indexkey
1196          */
1197         if (IsA(node, RelabelType))
1198                 node = (Node *) ((RelabelType *) node)->arg;
1199
1200         /*
1201          * We represent index keys by Var nodes having the varno of the base
1202          * table but varattno equal to the index's attribute number (index
1203          * column position).  This is a bit hokey ... would be cleaner to use
1204          * a special-purpose node type that could not be mistaken for a
1205          * regular Var.  But it will do for now.
1206          */
1207         if (IsA(node, Var))
1208         {
1209                 /* If it's a var, find which index key position it occupies */
1210                 Assert(index->indproc == InvalidOid);
1211
1212                 if (((Var *) node)->varno == baserelid)
1213                 {
1214                         int                     varatt = ((Var *) node)->varattno;
1215                         int                     pos;
1216
1217                         for (pos = 0; pos < index->nkeys; pos++)
1218                         {
1219                                 if (index->indexkeys[pos] == varatt)
1220                                 {
1221                                         Node       *newnode = copyObject(node);
1222
1223                                         ((Var *) newnode)->varattno = pos + 1;
1224                                         /* return the correct opclass, too */
1225                                         *opclass = index->classlist[pos];
1226                                         return newnode;
1227                                 }
1228                         }
1229                 }
1230
1231                 /*
1232                  * Oops, this Var isn't an indexkey!
1233                  */
1234                 elog(ERROR, "fix_indxqual_operand: var is not index attribute");
1235         }
1236
1237         /*
1238          * Else, it must be a func expression matching a functional index.
1239          * Since we currently only support single-column functional indexes,
1240          * the returned varattno must be 1.
1241          */
1242         Assert(index->indproc != InvalidOid);
1243         Assert(is_funcclause(node));    /* not a very thorough check, but easy */
1244
1245         /* classlist[0] is the only class of a functional index */
1246         *opclass = index->classlist[0];
1247
1248         return (Node *) makeVar(baserelid, 1, exprType(node), -1, 0);
1249 }
1250
1251 /*
1252  * get_switched_clauses
1253  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
1254  *        extract the bare clauses, and rearrange the elements within the
1255  *        clauses, if needed, so the outer join variable is on the left and
1256  *        the inner is on the right.  The original data structure is not touched;
1257  *        a modified list is returned.
1258  */
1259 static List *
1260 get_switched_clauses(List *clauses, Relids outerrelids)
1261 {
1262         List       *t_list = NIL;
1263         List       *i;
1264
1265         foreach(i, clauses)
1266         {
1267                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
1268                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
1269
1270                 Assert(is_opclause(clause));
1271                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
1272                 {
1273                         /*
1274                          * Duplicate just enough of the structure to allow commuting
1275                          * the clause without changing the original list.  Could use
1276                          * copyObject, but a complete deep copy is overkill.
1277                          */
1278                         OpExpr     *temp = makeNode(OpExpr);
1279
1280                         temp->opno = clause->opno;
1281                         temp->opfuncid = InvalidOid;
1282                         temp->opresulttype = clause->opresulttype;
1283                         temp->opretset = clause->opretset;
1284                         temp->args = listCopy(clause->args);
1285                         /* Commute it --- note this modifies the temp node in-place. */
1286                         CommuteClause(temp);
1287                         t_list = lappend(t_list, temp);
1288                 }
1289                 else
1290                         t_list = lappend(t_list, clause);
1291         }
1292         return t_list;
1293 }
1294
1295 /*
1296  * order_qual_clauses
1297  *              Given a list of qual clauses that will all be evaluated at the same
1298  *              plan node, sort the list into the order we want to check the quals
1299  *              in at runtime.
1300  *
1301  * Ideally the order should be driven by a combination of execution cost and
1302  * selectivity, but unfortunately we have so little information about
1303  * execution cost of operators that it's really hard to do anything smart.
1304  * For now, we just move any quals that contain SubPlan references (but not
1305  * InitPlan references) to the end of the list.
1306  */
1307 static List *
1308 order_qual_clauses(Query *root, List *clauses)
1309 {
1310         List       *nosubplans;
1311         List       *withsubplans;
1312         List       *l;
1313
1314         /* No need to work hard if the query is subselect-free */
1315         if (!root->hasSubLinks)
1316                 return clauses;
1317
1318         nosubplans = withsubplans = NIL;
1319         foreach(l, clauses)
1320         {
1321                 Node   *clause = lfirst(l);
1322
1323                 if (contain_subplans(clause))
1324                         withsubplans = lappend(withsubplans, clause);
1325                 else
1326                         nosubplans = lappend(nosubplans, clause);
1327         }
1328
1329         return nconc(nosubplans, withsubplans);
1330 }
1331
1332 /*
1333  * Copy cost and size info from a Path node to the Plan node created from it.
1334  * The executor won't use this info, but it's needed by EXPLAIN.
1335  */
1336 static void
1337 copy_path_costsize(Plan *dest, Path *src)
1338 {
1339         if (src)
1340         {
1341                 dest->startup_cost = src->startup_cost;
1342                 dest->total_cost = src->total_cost;
1343                 dest->plan_rows = src->parent->rows;
1344                 dest->plan_width = src->parent->width;
1345         }
1346         else
1347         {
1348                 dest->startup_cost = 0;
1349                 dest->total_cost = 0;
1350                 dest->plan_rows = 0;
1351                 dest->plan_width = 0;
1352         }
1353 }
1354
1355 /*
1356  * Copy cost and size info from a lower plan node to an inserted node.
1357  * This is not critical, since the decisions have already been made,
1358  * but it helps produce more reasonable-looking EXPLAIN output.
1359  * (Some callers alter the info after copying it.)
1360  */
1361 static void
1362 copy_plan_costsize(Plan *dest, Plan *src)
1363 {
1364         if (src)
1365         {
1366                 dest->startup_cost = src->startup_cost;
1367                 dest->total_cost = src->total_cost;
1368                 dest->plan_rows = src->plan_rows;
1369                 dest->plan_width = src->plan_width;
1370         }
1371         else
1372         {
1373                 dest->startup_cost = 0;
1374                 dest->total_cost = 0;
1375                 dest->plan_rows = 0;
1376                 dest->plan_width = 0;
1377         }
1378 }
1379
1380
1381 /*****************************************************************************
1382  *
1383  *      PLAN NODE BUILDING ROUTINES
1384  *
1385  * Some of these are exported because they are called to build plan nodes
1386  * in contexts where we're not deriving the plan node from a path node.
1387  *
1388  *****************************************************************************/
1389
1390 static SeqScan *
1391 make_seqscan(List *qptlist,
1392                          List *qpqual,
1393                          Index scanrelid)
1394 {
1395         SeqScan    *node = makeNode(SeqScan);
1396         Plan       *plan = &node->plan;
1397
1398         /* cost should be inserted by caller */
1399         plan->targetlist = qptlist;
1400         plan->qual = qpqual;
1401         plan->lefttree = NULL;
1402         plan->righttree = NULL;
1403         node->scanrelid = scanrelid;
1404
1405         return node;
1406 }
1407
1408 static IndexScan *
1409 make_indexscan(List *qptlist,
1410                            List *qpqual,
1411                            Index scanrelid,
1412                            List *indxid,
1413                            List *indxqual,
1414                            List *indxqualorig,
1415                            ScanDirection indexscandir)
1416 {
1417         IndexScan  *node = makeNode(IndexScan);
1418         Plan       *plan = &node->scan.plan;
1419
1420         /* cost should be inserted by caller */
1421         plan->targetlist = qptlist;
1422         plan->qual = qpqual;
1423         plan->lefttree = NULL;
1424         plan->righttree = NULL;
1425         node->scan.scanrelid = scanrelid;
1426         node->indxid = indxid;
1427         node->indxqual = indxqual;
1428         node->indxqualorig = indxqualorig;
1429         node->indxorderdir = indexscandir;
1430
1431         return node;
1432 }
1433
1434 static TidScan *
1435 make_tidscan(List *qptlist,
1436                          List *qpqual,
1437                          Index scanrelid,
1438                          List *tideval)
1439 {
1440         TidScan    *node = makeNode(TidScan);
1441         Plan       *plan = &node->scan.plan;
1442
1443         /* cost should be inserted by caller */
1444         plan->targetlist = qptlist;
1445         plan->qual = qpqual;
1446         plan->lefttree = NULL;
1447         plan->righttree = NULL;
1448         node->scan.scanrelid = scanrelid;
1449         node->tideval = tideval;
1450
1451         return node;
1452 }
1453
1454 SubqueryScan *
1455 make_subqueryscan(List *qptlist,
1456                                   List *qpqual,
1457                                   Index scanrelid,
1458                                   Plan *subplan)
1459 {
1460         SubqueryScan *node = makeNode(SubqueryScan);
1461         Plan       *plan = &node->scan.plan;
1462
1463         /* cost is figured here for the convenience of prepunion.c */
1464         copy_plan_costsize(plan, subplan);
1465         plan->targetlist = qptlist;
1466         plan->qual = qpqual;
1467         plan->lefttree = NULL;
1468         plan->righttree = NULL;
1469         node->scan.scanrelid = scanrelid;
1470         node->subplan = subplan;
1471
1472         return node;
1473 }
1474
1475 static FunctionScan *
1476 make_functionscan(List *qptlist,
1477                                   List *qpqual,
1478                                   Index scanrelid)
1479 {
1480         FunctionScan *node = makeNode(FunctionScan);
1481         Plan       *plan = &node->scan.plan;
1482
1483         /* cost should be inserted by caller */
1484         plan->targetlist = qptlist;
1485         plan->qual = qpqual;
1486         plan->lefttree = NULL;
1487         plan->righttree = NULL;
1488         node->scan.scanrelid = scanrelid;
1489
1490         return node;
1491 }
1492
1493 Append *
1494 make_append(List *appendplans, bool isTarget, List *tlist)
1495 {
1496         Append     *node = makeNode(Append);
1497         Plan       *plan = &node->plan;
1498         List       *subnode;
1499
1500         /* compute costs from subplan costs */
1501         plan->startup_cost = 0;
1502         plan->total_cost = 0;
1503         plan->plan_rows = 0;
1504         plan->plan_width = 0;
1505         foreach(subnode, appendplans)
1506         {
1507                 Plan       *subplan = (Plan *) lfirst(subnode);
1508
1509                 if (subnode == appendplans)             /* first node? */
1510                         plan->startup_cost = subplan->startup_cost;
1511                 plan->total_cost += subplan->total_cost;
1512                 plan->plan_rows += subplan->plan_rows;
1513                 if (plan->plan_width < subplan->plan_width)
1514                         plan->plan_width = subplan->plan_width;
1515         }
1516         plan->targetlist = tlist;
1517         plan->qual = NIL;
1518         plan->lefttree = NULL;
1519         plan->righttree = NULL;
1520         node->appendplans = appendplans;
1521         node->isTarget = isTarget;
1522
1523         return node;
1524 }
1525
1526 static NestLoop *
1527 make_nestloop(List *tlist,
1528                           List *joinclauses,
1529                           List *otherclauses,
1530                           Plan *lefttree,
1531                           Plan *righttree,
1532                           JoinType jointype)
1533 {
1534         NestLoop   *node = makeNode(NestLoop);
1535         Plan       *plan = &node->join.plan;
1536
1537         /* cost should be inserted by caller */
1538         plan->targetlist = tlist;
1539         plan->qual = otherclauses;
1540         plan->lefttree = lefttree;
1541         plan->righttree = righttree;
1542         node->join.jointype = jointype;
1543         node->join.joinqual = joinclauses;
1544
1545         return node;
1546 }
1547
1548 static HashJoin *
1549 make_hashjoin(List *tlist,
1550                           List *joinclauses,
1551                           List *otherclauses,
1552                           List *hashclauses,
1553                           Plan *lefttree,
1554                           Plan *righttree,
1555                           JoinType jointype)
1556 {
1557         HashJoin   *node = makeNode(HashJoin);
1558         Plan       *plan = &node->join.plan;
1559
1560         /* cost should be inserted by caller */
1561         plan->targetlist = tlist;
1562         plan->qual = otherclauses;
1563         plan->lefttree = lefttree;
1564         plan->righttree = righttree;
1565         node->hashclauses = hashclauses;
1566         node->join.jointype = jointype;
1567         node->join.joinqual = joinclauses;
1568
1569         return node;
1570 }
1571
1572 static Hash *
1573 make_hash(List *tlist, List *hashkeys, Plan *lefttree)
1574 {
1575         Hash       *node = makeNode(Hash);
1576         Plan       *plan = &node->plan;
1577
1578         copy_plan_costsize(plan, lefttree);
1579
1580         /*
1581          * For plausibility, make startup & total costs equal total cost of
1582          * input plan; this only affects EXPLAIN display not decisions.
1583          */
1584         plan->startup_cost = plan->total_cost;
1585         plan->targetlist = tlist;
1586         plan->qual = NIL;
1587         plan->lefttree = lefttree;
1588         plan->righttree = NULL;
1589         node->hashkeys = hashkeys;
1590
1591         return node;
1592 }
1593
1594 static MergeJoin *
1595 make_mergejoin(List *tlist,
1596                            List *joinclauses,
1597                            List *otherclauses,
1598                            List *mergeclauses,
1599                            Plan *lefttree,
1600                            Plan *righttree,
1601                            JoinType jointype)
1602 {
1603         MergeJoin  *node = makeNode(MergeJoin);
1604         Plan       *plan = &node->join.plan;
1605
1606         /* cost should be inserted by caller */
1607         plan->targetlist = tlist;
1608         plan->qual = otherclauses;
1609         plan->lefttree = lefttree;
1610         plan->righttree = righttree;
1611         node->mergeclauses = mergeclauses;
1612         node->join.jointype = jointype;
1613         node->join.joinqual = joinclauses;
1614
1615         return node;
1616 }
1617
1618 /*
1619  * make_sort --- basic routine to build a Sort plan node
1620  *
1621  * Caller must have built the sortColIdx and sortOperators arrays already.
1622  */
1623 static Sort *
1624 make_sort(Query *root, List *tlist, Plan *lefttree, int numCols,
1625                   AttrNumber *sortColIdx, Oid *sortOperators)
1626 {
1627         Sort       *node = makeNode(Sort);
1628         Plan       *plan = &node->plan;
1629         Path            sort_path;              /* dummy for result of cost_sort */
1630
1631         copy_plan_costsize(plan, lefttree); /* only care about copying size */
1632         cost_sort(&sort_path, root, NIL,
1633                           lefttree->total_cost,
1634                           lefttree->plan_rows,
1635                           lefttree->plan_width);
1636         plan->startup_cost = sort_path.startup_cost;
1637         plan->total_cost = sort_path.total_cost;
1638         plan->targetlist = tlist;
1639         plan->qual = NIL;
1640         plan->lefttree = lefttree;
1641         plan->righttree = NULL;
1642         node->numCols = numCols;
1643         node->sortColIdx = sortColIdx;
1644         node->sortOperators = sortOperators;
1645
1646         return node;
1647 }
1648
1649 /*
1650  * add_sort_column --- utility subroutine for building sort info arrays
1651  *
1652  * We need this routine because the same column might be selected more than
1653  * once as a sort key column; if so, the extra mentions are redundant.
1654  *
1655  * Caller is assumed to have allocated the arrays large enough for the
1656  * max possible number of columns.  Return value is the new column count.
1657  */
1658 static int
1659 add_sort_column(AttrNumber colIdx, Oid sortOp,
1660                                 int numCols, AttrNumber *sortColIdx, Oid *sortOperators)
1661 {
1662         int                     i;
1663
1664         for (i = 0; i < numCols; i++)
1665         {
1666                 if (sortColIdx[i] == colIdx)
1667                 {
1668                         /* Already sorting by this col, so extra sort key is useless */
1669                         return numCols;
1670                 }
1671         }
1672
1673         /* Add the column */
1674         sortColIdx[numCols] = colIdx;
1675         sortOperators[numCols] = sortOp;
1676         return numCols + 1;
1677 }
1678
1679 /*
1680  * make_sort_from_pathkeys
1681  *        Create sort plan to sort according to given pathkeys
1682  *
1683  *        'lefttree' is the node which yields input tuples
1684  *        'relids' is the set of relids represented by the input node
1685  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
1686  *
1687  * We must convert the pathkey information into arrays of sort key column
1688  * numbers and sort operator OIDs.
1689  *
1690  * If the pathkeys include expressions that aren't simple Vars, we will
1691  * usually need to add resjunk items to the input plan's targetlist to
1692  * compute these expressions (since the Sort node itself won't do it).
1693  * If the input plan type isn't one that can do projections, this means
1694  * adding a Result node just to do the projection.
1695  */
1696 static Sort *
1697 make_sort_from_pathkeys(Query *root, Plan *lefttree,
1698                                                 Relids relids, List *pathkeys)
1699 {
1700         List       *tlist = lefttree->targetlist;
1701         List       *sort_tlist;
1702         List       *i;
1703         int                     numsortkeys;
1704         AttrNumber *sortColIdx;
1705         Oid                *sortOperators;
1706
1707         /* We will need at most length(pathkeys) sort columns; possibly less */
1708         numsortkeys = length(pathkeys);
1709         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
1710         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
1711
1712         numsortkeys = 0;
1713
1714         foreach(i, pathkeys)
1715         {
1716                 List       *keysublist = (List *) lfirst(i);
1717                 PathKeyItem *pathkey = NULL;
1718                 Resdom     *resdom = NULL;
1719                 List       *j;
1720
1721                 /*
1722                  * We can sort by any one of the sort key items listed in this
1723                  * sublist.  For now, we take the first one that corresponds to an
1724                  * available Var in the tlist.  If there isn't any, use the
1725                  * first one that is an expression in the input's vars.
1726                  *
1727                  * XXX if we have a choice, is there any way of figuring out which
1728                  * might be cheapest to execute?  (For example, int4lt is likely
1729                  * much cheaper to execute than numericlt, but both might appear
1730                  * in the same pathkey sublist...)      Not clear that we ever will
1731                  * have a choice in practice, so it may not matter.
1732                  */
1733                 foreach(j, keysublist)
1734                 {
1735                         pathkey = lfirst(j);
1736                         Assert(IsA(pathkey, PathKeyItem));
1737                         resdom = tlist_member(pathkey->key, tlist);
1738                         if (resdom)
1739                                 break;
1740                 }
1741                 if (!resdom)
1742                 {
1743                         /* No matching Var; look for an expression */
1744                         foreach(j, keysublist)
1745                         {
1746                                 pathkey = lfirst(j);
1747                                 if (bms_is_subset(pull_varnos(pathkey->key), relids))
1748                                         break;
1749                         }
1750                         if (!j)
1751                                 elog(ERROR, "make_sort_from_pathkeys: cannot find pathkey item to sort");
1752                         /*
1753                          * Do we need to insert a Result node?
1754                          *
1755                          * Currently, the only non-projection-capable plan type
1756                          * we can see here is Append.
1757                          */
1758                         if (IsA(lefttree, Append))
1759                         {
1760                                 tlist = copyObject(tlist);
1761                                 lefttree = (Plan *) make_result(tlist, NULL, lefttree);
1762                         }
1763                         /*
1764                          * Add resjunk entry to input's tlist
1765                          */
1766                         resdom = makeResdom(length(tlist) + 1,
1767                                                                 exprType(pathkey->key),
1768                                                                 exprTypmod(pathkey->key),
1769                                                                 NULL,
1770                                                                 true);
1771                         tlist = lappend(tlist,
1772                                                         makeTargetEntry(resdom,
1773                                                                                         (Expr *) pathkey->key));
1774                         lefttree->targetlist = tlist; /* just in case NIL before */
1775                 }
1776                 /*
1777                  * The column might already be selected as a sort key, if the
1778                  * pathkeys contain duplicate entries.  (This can happen in
1779                  * scenarios where multiple mergejoinable clauses mention the same
1780                  * var, for example.)  So enter it only once in the sort arrays.
1781                  */
1782                 numsortkeys = add_sort_column(resdom->resno, pathkey->sortop,
1783                                                                           numsortkeys, sortColIdx, sortOperators);
1784         }
1785
1786         Assert(numsortkeys > 0);
1787
1788         /* Give Sort node its own copy of the tlist (still necessary?) */
1789         sort_tlist = copyObject(tlist);
1790
1791         return make_sort(root, sort_tlist, lefttree, numsortkeys,
1792                                          sortColIdx, sortOperators);
1793 }
1794
1795 /*
1796  * make_sort_from_sortclauses
1797  *        Create sort plan to sort according to given sortclauses
1798  *
1799  *        'tlist' is the targetlist
1800  *        'lefttree' is the node which yields input tuples
1801  *        'sortcls' is a list of SortClauses
1802  */
1803 Sort *
1804 make_sort_from_sortclauses(Query *root, List *tlist,
1805                                                    Plan *lefttree, List *sortcls)
1806 {
1807         List       *sort_tlist;
1808         List       *i;
1809         int                     numsortkeys;
1810         AttrNumber *sortColIdx;
1811         Oid                *sortOperators;
1812
1813         /* We will need at most length(sortcls) sort columns; possibly less */
1814         numsortkeys = length(sortcls);
1815         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
1816         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
1817
1818         numsortkeys = 0;
1819
1820         foreach(i, sortcls)
1821         {
1822                 SortClause *sortcl = (SortClause *) lfirst(i);
1823                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, tlist);
1824                 Resdom     *resdom = tle->resdom;
1825
1826                 /*
1827                  * Check for the possibility of duplicate order-by clauses --- the
1828                  * parser should have removed 'em, but no point in sorting redundantly.
1829                  */
1830                 numsortkeys = add_sort_column(resdom->resno, sortcl->sortop,
1831                                                                           numsortkeys, sortColIdx, sortOperators);
1832         }
1833
1834         Assert(numsortkeys > 0);
1835
1836         /* Give Sort node its own copy of the tlist (still necessary?) */
1837         sort_tlist = copyObject(tlist);
1838
1839         return make_sort(root, sort_tlist, lefttree, numsortkeys,
1840                                          sortColIdx, sortOperators);
1841 }
1842
1843 /*
1844  * make_sort_from_groupcols
1845  *        Create sort plan to sort based on grouping columns
1846  *
1847  * 'groupcls' is the list of GroupClauses
1848  * 'grpColIdx' gives the column numbers to use
1849  *
1850  * This might look like it could be merged with make_sort_from_sortclauses,
1851  * but presently we *must* use the grpColIdx[] array to locate sort columns,
1852  * because the child plan's tlist is not marked with ressortgroupref info
1853  * appropriate to the grouping node.  So, only the sortop is used from the
1854  * GroupClause entries.
1855  */
1856 Sort *
1857 make_sort_from_groupcols(Query *root,
1858                                                  List *groupcls,
1859                                                  AttrNumber *grpColIdx,
1860                                                  Plan *lefttree)
1861 {
1862         List       *sub_tlist = lefttree->targetlist;
1863         List       *sort_tlist;
1864         int                     grpno = 0;
1865         List       *i;
1866         int                     numsortkeys;
1867         AttrNumber *sortColIdx;
1868         Oid                *sortOperators;
1869
1870         /* We will need at most length(groupcls) sort columns; possibly less */
1871         numsortkeys = length(groupcls);
1872         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
1873         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
1874
1875         numsortkeys = 0;
1876
1877         foreach(i, groupcls)
1878         {
1879                 GroupClause *grpcl = (GroupClause *) lfirst(i);
1880                 TargetEntry *tle = nth(grpColIdx[grpno] - 1, sub_tlist);
1881                 Resdom     *resdom = tle->resdom;
1882
1883                 /*
1884                  * Check for the possibility of duplicate group-by clauses --- the
1885                  * parser should have removed 'em, but no point in sorting redundantly.
1886                  */
1887                 numsortkeys = add_sort_column(resdom->resno, grpcl->sortop,
1888                                                                           numsortkeys, sortColIdx, sortOperators);
1889                 grpno++;
1890         }
1891
1892         Assert(numsortkeys > 0);
1893
1894         /* Give Sort node its own copy of the tlist (still necessary?) */
1895         sort_tlist = copyObject(sub_tlist);
1896
1897         return make_sort(root, sort_tlist, lefttree, numsortkeys,
1898                                          sortColIdx, sortOperators);
1899 }
1900
1901 Material *
1902 make_material(List *tlist, Plan *lefttree)
1903 {
1904         Material   *node = makeNode(Material);
1905         Plan       *plan = &node->plan;
1906
1907         /* cost should be inserted by caller */
1908         plan->targetlist = tlist;
1909         plan->qual = NIL;
1910         plan->lefttree = lefttree;
1911         plan->righttree = NULL;
1912
1913         return node;
1914 }
1915
1916 /*
1917  * materialize_finished_plan: stick a Material node atop a completed plan
1918  *
1919  * There are a couple of places where we want to attach a Material node
1920  * after completion of subquery_planner().  This currently requires hackery.
1921  * Since subquery_planner has already run SS_finalize_plan on the subplan
1922  * tree, we have to kluge up parameter lists for the Material node.
1923  * Possibly this could be fixed by postponing SS_finalize_plan processing
1924  * until setrefs.c is run?
1925  */
1926 Plan *
1927 materialize_finished_plan(Plan *subplan)
1928 {
1929         Plan       *matplan;
1930         Path            matpath;                /* dummy for result of cost_material */
1931
1932         matplan = (Plan *) make_material(subplan->targetlist, subplan);
1933
1934         /* Set cost data */
1935         cost_material(&matpath,
1936                                   subplan->total_cost,
1937                                   subplan->plan_rows,
1938                                   subplan->plan_width);
1939         matplan->startup_cost = matpath.startup_cost;
1940         matplan->total_cost = matpath.total_cost;
1941         matplan->plan_rows = subplan->plan_rows;
1942         matplan->plan_width = subplan->plan_width;
1943
1944         /* parameter kluge --- see comments above */
1945         matplan->extParam = bms_copy(subplan->extParam);
1946         matplan->allParam = bms_copy(subplan->allParam);
1947
1948         return matplan;
1949 }
1950
1951 Agg *
1952 make_agg(Query *root, List *tlist, List *qual,
1953                  AggStrategy aggstrategy,
1954                  int numGroupCols, AttrNumber *grpColIdx,
1955                  long numGroups, int numAggs,
1956                  Plan *lefttree)
1957 {
1958         Agg                *node = makeNode(Agg);
1959         Plan       *plan = &node->plan;
1960         Path            agg_path;               /* dummy for result of cost_agg */
1961         QualCost        qual_cost;
1962
1963         node->aggstrategy = aggstrategy;
1964         node->numCols = numGroupCols;
1965         node->grpColIdx = grpColIdx;
1966         node->numGroups = numGroups;
1967
1968         copy_plan_costsize(plan, lefttree); /* only care about copying size */
1969         cost_agg(&agg_path, root,
1970                          aggstrategy, numAggs,
1971                          numGroupCols, numGroups,
1972                          lefttree->startup_cost,
1973                          lefttree->total_cost,
1974                          lefttree->plan_rows);
1975         plan->startup_cost = agg_path.startup_cost;
1976         plan->total_cost = agg_path.total_cost;
1977
1978         /*
1979          * We will produce a single output tuple if not grouping,
1980          * and a tuple per group otherwise.
1981          */
1982         if (aggstrategy == AGG_PLAIN)
1983                 plan->plan_rows = 1;
1984         else
1985                 plan->plan_rows = numGroups;
1986
1987         /*
1988          * We also need to account for the cost of evaluation of the qual
1989          * (ie, the HAVING clause) and the tlist.  Note that cost_qual_eval
1990          * doesn't charge anything for Aggref nodes; this is okay since
1991          * they are really comparable to Vars.
1992          *
1993          * See notes in grouping_planner about why this routine and make_group
1994          * are the only ones in this file that worry about tlist eval cost.
1995          */
1996         if (qual)
1997         {
1998                 cost_qual_eval(&qual_cost, qual);
1999                 plan->startup_cost += qual_cost.startup;
2000                 plan->total_cost += qual_cost.startup;
2001                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2002         }
2003         cost_qual_eval(&qual_cost, tlist);
2004         plan->startup_cost += qual_cost.startup;
2005         plan->total_cost += qual_cost.startup;
2006         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2007
2008         plan->qual = qual;
2009         plan->targetlist = tlist;
2010         plan->lefttree = lefttree;
2011         plan->righttree = (Plan *) NULL;
2012
2013         return node;
2014 }
2015
2016 Group *
2017 make_group(Query *root,
2018                    List *tlist,
2019                    int numGroupCols,
2020                    AttrNumber *grpColIdx,
2021                    double numGroups,
2022                    Plan *lefttree)
2023 {
2024         Group      *node = makeNode(Group);
2025         Plan       *plan = &node->plan;
2026         Path            group_path;             /* dummy for result of cost_group */
2027         QualCost        qual_cost;
2028
2029         node->numCols = numGroupCols;
2030         node->grpColIdx = grpColIdx;
2031
2032         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2033         cost_group(&group_path, root,
2034                            numGroupCols, numGroups,
2035                            lefttree->startup_cost,
2036                            lefttree->total_cost,
2037                            lefttree->plan_rows);
2038         plan->startup_cost = group_path.startup_cost;
2039         plan->total_cost = group_path.total_cost;
2040
2041         /* One output tuple per estimated result group */
2042         plan->plan_rows = numGroups;
2043
2044         /*
2045          * We also need to account for the cost of evaluation of the tlist.
2046          *
2047          * XXX this double-counts the cost of evaluation of any expressions
2048          * used for grouping, since in reality those will have been evaluated
2049          * at a lower plan level and will only be copied by the Group node.
2050          * Worth fixing?
2051          *
2052          * See notes in grouping_planner about why this routine and make_agg
2053          * are the only ones in this file that worry about tlist eval cost.
2054          */
2055         cost_qual_eval(&qual_cost, tlist);
2056         plan->startup_cost += qual_cost.startup;
2057         plan->total_cost += qual_cost.startup;
2058         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2059
2060         plan->qual = NIL;
2061         plan->targetlist = tlist;
2062         plan->lefttree = lefttree;
2063         plan->righttree = (Plan *) NULL;
2064
2065         return node;
2066 }
2067
2068 /*
2069  * distinctList is a list of SortClauses, identifying the targetlist items
2070  * that should be considered by the Unique filter.
2071  */
2072 Unique *
2073 make_unique(List *tlist, Plan *lefttree, List *distinctList)
2074 {
2075         Unique     *node = makeNode(Unique);
2076         Plan       *plan = &node->plan;
2077         int                     numCols = length(distinctList);
2078         int                     keyno = 0;
2079         AttrNumber *uniqColIdx;
2080         List       *slitem;
2081
2082         copy_plan_costsize(plan, lefttree);
2083
2084         /*
2085          * Charge one cpu_operator_cost per comparison per input tuple. We
2086          * assume all columns get compared at most of the tuples.  (XXX probably
2087          * this is an overestimate.)
2088          */
2089         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
2090
2091         /*
2092          * plan->plan_rows is left as a copy of the input subplan's plan_rows;
2093          * ie, we assume the filter removes nothing.  The caller must alter this
2094          * if he has a better idea.
2095          */
2096
2097         plan->targetlist = tlist;
2098         plan->qual = NIL;
2099         plan->lefttree = lefttree;
2100         plan->righttree = NULL;
2101
2102         /*
2103          * convert SortClause list into array of attr indexes, as wanted by
2104          * exec
2105          */
2106         Assert(numCols > 0);
2107         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2108
2109         foreach(slitem, distinctList)
2110         {
2111                 SortClause *sortcl = (SortClause *) lfirst(slitem);
2112                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, tlist);
2113
2114                 uniqColIdx[keyno++] = tle->resdom->resno;
2115         }
2116
2117         node->numCols = numCols;
2118         node->uniqColIdx = uniqColIdx;
2119
2120         return node;
2121 }
2122
2123 /*
2124  * distinctList is a list of SortClauses, identifying the targetlist items
2125  * that should be considered by the SetOp filter.
2126  */
2127
2128 SetOp *
2129 make_setop(SetOpCmd cmd, List *tlist, Plan *lefttree,
2130                    List *distinctList, AttrNumber flagColIdx)
2131 {
2132         SetOp      *node = makeNode(SetOp);
2133         Plan       *plan = &node->plan;
2134         int                     numCols = length(distinctList);
2135         int                     keyno = 0;
2136         AttrNumber *dupColIdx;
2137         List       *slitem;
2138
2139         copy_plan_costsize(plan, lefttree);
2140
2141         /*
2142          * Charge one cpu_operator_cost per comparison per input tuple. We
2143          * assume all columns get compared at most of the tuples.
2144          */
2145         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
2146
2147         /*
2148          * We make the unsupported assumption that there will be 10% as many
2149          * tuples out as in.  Any way to do better?
2150          */
2151         plan->plan_rows *= 0.1;
2152         if (plan->plan_rows < 1)
2153                 plan->plan_rows = 1;
2154
2155         plan->targetlist = tlist;
2156         plan->qual = NIL;
2157         plan->lefttree = lefttree;
2158         plan->righttree = NULL;
2159
2160         /*
2161          * convert SortClause list into array of attr indexes, as wanted by
2162          * exec
2163          */
2164         Assert(numCols > 0);
2165         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2166
2167         foreach(slitem, distinctList)
2168         {
2169                 SortClause *sortcl = (SortClause *) lfirst(slitem);
2170                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, tlist);
2171
2172                 dupColIdx[keyno++] = tle->resdom->resno;
2173         }
2174
2175         node->cmd = cmd;
2176         node->numCols = numCols;
2177         node->dupColIdx = dupColIdx;
2178         node->flagColIdx = flagColIdx;
2179
2180         return node;
2181 }
2182
2183 Limit *
2184 make_limit(List *tlist, Plan *lefttree,
2185                    Node *limitOffset, Node *limitCount)
2186 {
2187         Limit      *node = makeNode(Limit);
2188         Plan       *plan = &node->plan;
2189
2190         copy_plan_costsize(plan, lefttree);
2191
2192         /*
2193          * If offset/count are constants, adjust the output rows count and
2194          * costs accordingly.  This is only a cosmetic issue if we are at top
2195          * level, but if we are building a subquery then it's important to
2196          * report correct info to the outer planner.
2197          */
2198         if (limitOffset && IsA(limitOffset, Const))
2199         {
2200                 Const      *limito = (Const *) limitOffset;
2201                 int32           offset = DatumGetInt32(limito->constvalue);
2202
2203                 if (!limito->constisnull && offset > 0)
2204                 {
2205                         if (offset > plan->plan_rows)
2206                                 offset = (int32) plan->plan_rows;
2207                         if (plan->plan_rows > 0)
2208                                 plan->startup_cost +=
2209                                         (plan->total_cost - plan->startup_cost)
2210                                         * ((double) offset) / plan->plan_rows;
2211                         plan->plan_rows -= offset;
2212                         if (plan->plan_rows < 1)
2213                                 plan->plan_rows = 1;
2214                 }
2215         }
2216         if (limitCount && IsA(limitCount, Const))
2217         {
2218                 Const      *limitc = (Const *) limitCount;
2219                 int32           count = DatumGetInt32(limitc->constvalue);
2220
2221                 if (!limitc->constisnull && count >= 0)
2222                 {
2223                         if (count > plan->plan_rows)
2224                                 count = (int32) plan->plan_rows;
2225                         if (plan->plan_rows > 0)
2226                                 plan->total_cost = plan->startup_cost +
2227                                         (plan->total_cost - plan->startup_cost)
2228                                         * ((double) count) / plan->plan_rows;
2229                         plan->plan_rows = count;
2230                         if (plan->plan_rows < 1)
2231                                 plan->plan_rows = 1;
2232                 }
2233         }
2234
2235         plan->targetlist = tlist;
2236         plan->qual = NIL;
2237         plan->lefttree = lefttree;
2238         plan->righttree = NULL;
2239
2240         node->limitOffset = limitOffset;
2241         node->limitCount = limitCount;
2242
2243         return node;
2244 }
2245
2246 Result *
2247 make_result(List *tlist,
2248                         Node *resconstantqual,
2249                         Plan *subplan)
2250 {
2251         Result     *node = makeNode(Result);
2252         Plan       *plan = &node->plan;
2253
2254         if (subplan)
2255                 copy_plan_costsize(plan, subplan);
2256         else
2257         {
2258                 plan->startup_cost = 0;
2259                 plan->total_cost = cpu_tuple_cost;
2260                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
2261                 plan->plan_width = 0;   /* XXX try to be smarter? */
2262         }
2263
2264         if (resconstantqual)
2265         {
2266                 QualCost        qual_cost;
2267
2268                 cost_qual_eval(&qual_cost, (List *) resconstantqual);
2269                 /* resconstantqual is evaluated once at startup */
2270                 plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
2271                 plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
2272         }
2273
2274         plan->targetlist = tlist;
2275         plan->qual = NIL;
2276         plan->lefttree = subplan;
2277         plan->righttree = NULL;
2278         node->resconstantqual = resconstantqual;
2279
2280         return node;
2281 }