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-2005, PostgreSQL Global Development Group
   9  * Portions Copyright (c) 1994, Regents of the University of California
  10  *
  11  *
  12  * IDENTIFICATION
  13  *        $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.191 2005/06/05 22:32:55 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/plancat.h"
  27 #include "optimizer/planmain.h"
  28 #include "optimizer/restrictinfo.h"
  29 #include "optimizer/tlist.h"
  30 #include "optimizer/var.h"
  31 #include "parser/parsetree.h"
  32 #include "parser/parse_clause.h"
  33 #include "parser/parse_expr.h"
  34 #include "utils/lsyscache.h"
  35 #include "utils/syscache.h"
  36
  37
  38 static Scan *create_scan_plan(PlannerInfo *root, Path *best_path);
  39 static List *build_relation_tlist(RelOptInfo *rel);
  40 static bool use_physical_tlist(RelOptInfo *rel);
  41 static void disuse_physical_tlist(Plan *plan, Path *path);
  42 static Join *create_join_plan(PlannerInfo *root, JoinPath *best_path);
  43 static Append *create_append_plan(PlannerInfo *root, AppendPath *best_path);
  44 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
  45 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
  46 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
  47 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
  48                                         List *tlist, List *scan_clauses);
  49 static IndexScan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
  50                                           List *tlist, List *scan_clauses,
  51                                           List **nonlossy_clauses);
  52 static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
  53                                                                                            BitmapHeapPath *best_path,
  54                                                                                            List *tlist, List *scan_clauses);
  55 static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
  56                                                                    List **qual, List **indexqual);
  57 static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
  58                                         List *tlist, List *scan_clauses);
  59 static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
  60                                                  List *tlist, List *scan_clauses);
  61 static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
  62                                                  List *tlist, List *scan_clauses);
  63 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
  64                                          Plan *outer_plan, Plan *inner_plan);
  65 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
  66                                           Plan *outer_plan, Plan *inner_plan);
  67 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
  68                                          Plan *outer_plan, Plan *inner_plan);
  69 static void fix_indexqual_references(List *indexquals, IndexPath *index_path,
  70                                                  List **fixed_indexquals,
  71                                                  List **nonlossy_indexquals,
  72                                                  List **indexstrategy,
  73                                                  List **indexsubtype);
  74 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index,
  75                                                                   Oid *opclass);
  76 static List *get_switched_clauses(List *clauses, Relids outerrelids);
  77 static void copy_path_costsize(Plan *dest, Path *src);
  78 static void copy_plan_costsize(Plan *dest, Plan *src);
  79 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
  80 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
  81                            Oid indexid, List *indexqual, List *indexqualorig,
  82                            List *indexstrategy, List *indexsubtype,
  83                            ScanDirection indexscandir);
  84 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
  85                                                                                           List *indexqual,
  86                                                                                           List *indexqualorig,
  87                                                                                           List *indexstrategy,
  88                                                                                           List *indexsubtype);
  89 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
  90                                                                                         List *qpqual,
  91                                                                                         Plan *lefttree,
  92                                                                                         List *bitmapqualorig,
  93                                                                                         Index scanrelid);
  94 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
  95                          List *tideval);
  96 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
  97                                   Index scanrelid);
  98 static BitmapAnd *make_bitmap_and(List *bitmapplans);
  99 static BitmapOr *make_bitmap_or(List *bitmapplans);
 100 static NestLoop *make_nestloop(List *tlist,
 101                           List *joinclauses, List *otherclauses,
 102                           Plan *lefttree, Plan *righttree,
 103                           JoinType jointype);
 104 static HashJoin *make_hashjoin(List *tlist,
 105                           List *joinclauses, List *otherclauses,
 106                           List *hashclauses,
 107                           Plan *lefttree, Plan *righttree,
 108                           JoinType jointype);
 109 static Hash *make_hash(Plan *lefttree);
 110 static MergeJoin *make_mergejoin(List *tlist,
 111                            List *joinclauses, List *otherclauses,
 112                            List *mergeclauses,
 113                            Plan *lefttree, Plan *righttree,
 114                            JoinType jointype);
 115 static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
 116                   AttrNumber *sortColIdx, Oid *sortOperators);
 117 static Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
 118                                                 List *pathkeys);
 119
 120
 121 /*
 122  * create_plan
 123  *        Creates the access plan for a query by tracing backwards through the
 124  *        desired chain of pathnodes, starting at the node 'best_path'.  For
 125  *        every pathnode found:
 126  *        (1) Create a corresponding plan node containing appropriate id,
 127  *                target list, and qualification information.
 128  *        (2) Modify qual clauses of join nodes so that subplan attributes are
 129  *                referenced using relative values.
 130  *        (3) Target lists are not modified, but will be in setrefs.c.
 131  *
 132  *        best_path is the best access path
 133  *
 134  *        Returns a Plan tree.
 135  */
 136 Plan *
 137 create_plan(PlannerInfo *root, Path *best_path)
 138 {
 139         Plan       *plan;
 140
 141         switch (best_path->pathtype)
 142         {
 143                 case T_SeqScan:
 144                 case T_IndexScan:
 145                 case T_BitmapHeapScan:
 146                 case T_TidScan:
 147                 case T_SubqueryScan:
 148                 case T_FunctionScan:
 149                         plan = (Plan *) create_scan_plan(root, best_path);
 150                         break;
 151                 case T_HashJoin:
 152                 case T_MergeJoin:
 153                 case T_NestLoop:
 154                         plan = (Plan *) create_join_plan(root,
 155                                                                                          (JoinPath *) best_path);
 156                         break;
 157                 case T_Append:
 158                         plan = (Plan *) create_append_plan(root,
 159                                                                                            (AppendPath *) best_path);
 160                         break;
 161                 case T_Result:
 162                         plan = (Plan *) create_result_plan(root,
 163                                                                                            (ResultPath *) best_path);
 164                         break;
 165                 case T_Material:
 166                         plan = (Plan *) create_material_plan(root,
 167                                                                                          (MaterialPath *) best_path);
 168                         break;
 169                 case T_Unique:
 170                         plan = (Plan *) create_unique_plan(root,
 171                                                                                            (UniquePath *) best_path);
 172                         break;
 173                 default:
 174                         elog(ERROR, "unrecognized node type: %d",
 175                                  (int) best_path->pathtype);
 176                         plan = NULL;            /* keep compiler quiet */
 177                         break;
 178         }
 179
 180         return plan;
 181 }
 182
 183 /*
 184  * create_scan_plan
 185  *       Create a scan plan for the parent relation of 'best_path'.
 186  *
 187  *       Returns a Plan node.
 188  */
 189 static Scan *
 190 create_scan_plan(PlannerInfo *root, Path *best_path)
 191 {
 192         RelOptInfo *rel = best_path->parent;
 193         List       *tlist;
 194         List       *scan_clauses;
 195         Scan       *plan;
 196
 197         /*
 198          * For table scans, rather than using the relation targetlist (which
 199          * is only those Vars actually needed by the query), we prefer to
 200          * generate a tlist containing all Vars in order.  This will allow the
 201          * executor to optimize away projection of the table tuples, if
 202          * possible.  (Note that planner.c may replace the tlist we generate
 203          * here, forcing projection to occur.)
 204          */
 205         if (use_physical_tlist(rel))
 206         {
 207                 tlist = build_physical_tlist(root, rel);
 208                 /* if fail because of dropped cols, use regular method */
 209                 if (tlist == NIL)
 210                         tlist = build_relation_tlist(rel);
 211         }
 212         else
 213                 tlist = build_relation_tlist(rel);
 214
 215         /*
 216          * Extract the relevant restriction clauses from the parent relation;
 217          * the executor must apply all these restrictions during the scan.
 218          */
 219         scan_clauses = rel->baserestrictinfo;
 220
 221         switch (best_path->pathtype)
 222         {
 223                 case T_SeqScan:
 224                         plan = (Scan *) create_seqscan_plan(root,
 225                                                                                                 best_path,
 226                                                                                                 tlist,
 227                                                                                                 scan_clauses);
 228                         break;
 229
 230                 case T_IndexScan:
 231                         plan = (Scan *) create_indexscan_plan(root,
 232                                                                                                   (IndexPath *) best_path,
 233                                                                                                   tlist,
 234                                                                                                   scan_clauses,
 235                                                                                                   NULL);
 236                         break;
 237
 238                 case T_BitmapHeapScan:
 239                         plan = (Scan *) create_bitmap_scan_plan(root,
 240                                                                                                         (BitmapHeapPath *) best_path,
 241                                                                                                         tlist,
 242                                                                                                         scan_clauses);
 243                         break;
 244
 245                 case T_TidScan:
 246                         plan = (Scan *) create_tidscan_plan(root,
 247                                                                                                 (TidPath *) best_path,
 248                                                                                                 tlist,
 249                                                                                                 scan_clauses);
 250                         break;
 251
 252                 case T_SubqueryScan:
 253                         plan = (Scan *) create_subqueryscan_plan(root,
 254                                                                                                          best_path,
 255                                                                                                          tlist,
 256                                                                                                          scan_clauses);
 257                         break;
 258
 259                 case T_FunctionScan:
 260                         plan = (Scan *) create_functionscan_plan(root,
 261                                                                                                          best_path,
 262                                                                                                          tlist,
 263                                                                                                          scan_clauses);
 264                         break;
 265
 266                 default:
 267                         elog(ERROR, "unrecognized node type: %d",
 268                                  (int) best_path->pathtype);
 269                         plan = NULL;            /* keep compiler quiet */
 270                         break;
 271         }
 272
 273         return plan;
 274 }
 275
 276 /*
 277  * Build a target list (ie, a list of TargetEntry) for a relation.
 278  */
 279 static List *
 280 build_relation_tlist(RelOptInfo *rel)
 281 {
 282         List       *tlist = NIL;
 283         int                     resno = 1;
 284         ListCell   *v;
 285
 286         foreach(v, rel->reltargetlist)
 287         {
 288                 /* Do we really need to copy here?      Not sure */
 289                 Var                *var = (Var *) copyObject(lfirst(v));
 290
 291                 tlist = lappend(tlist, makeTargetEntry((Expr *) var,
 292                                                                                            resno,
 293                                                                                            NULL,
 294                                                                                            false));
 295                 resno++;
 296         }
 297         return tlist;
 298 }
 299
 300 /*
 301  * use_physical_tlist
 302  *              Decide whether to use a tlist matching relation structure,
 303  *              rather than only those Vars actually referenced.
 304  */
 305 static bool
 306 use_physical_tlist(RelOptInfo *rel)
 307 {
 308         int                     i;
 309
 310         /*
 311          * OK for subquery and function scans; otherwise, can't do it for
 312          * anything except real relations.
 313          */
 314         if (rel->rtekind != RTE_RELATION)
 315         {
 316                 if (rel->rtekind == RTE_SUBQUERY)
 317                         return true;
 318                 if (rel->rtekind == RTE_FUNCTION)
 319                         return true;
 320                 return false;
 321         }
 322
 323         /*
 324          * Can't do it with inheritance cases either (mainly because Append
 325          * doesn't project).
 326          */
 327         if (rel->reloptkind != RELOPT_BASEREL)
 328                 return false;
 329
 330         /*
 331          * Can't do it if any system columns are requested, either.  (This
 332          * could possibly be fixed but would take some fragile assumptions in
 333          * setrefs.c, I think.)
 334          */
 335         for (i = rel->min_attr; i <= 0; i++)
 336         {
 337                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
 338                         return false;
 339         }
 340         return true;
 341 }
 342
 343 /*
 344  * disuse_physical_tlist
 345  *              Switch a plan node back to emitting only Vars actually referenced.
 346  *
 347  * If the plan node immediately above a scan would prefer to get only
 348  * needed Vars and not a physical tlist, it must call this routine to
 349  * undo the decision made by use_physical_tlist().      Currently, Hash, Sort,
 350  * and Material nodes want this, so they don't have to store useless columns.
 351  */
 352 static void
 353 disuse_physical_tlist(Plan *plan, Path *path)
 354 {
 355         /* Only need to undo it for path types handled by create_scan_plan() */
 356         switch (path->pathtype)
 357         {
 358                 case T_SeqScan:
 359                 case T_IndexScan:
 360                 case T_BitmapHeapScan:
 361                 case T_TidScan:
 362                 case T_SubqueryScan:
 363                 case T_FunctionScan:
 364                         plan->targetlist = build_relation_tlist(path->parent);
 365                         break;
 366                 default:
 367                         break;
 368         }
 369 }
 370
 371 /*
 372  * create_join_plan
 373  *        Create a join plan for 'best_path' and (recursively) plans for its
 374  *        inner and outer paths.
 375  *
 376  *        Returns a Plan node.
 377  */
 378 static Join *
 379 create_join_plan(PlannerInfo *root, JoinPath *best_path)
 380 {
 381         Plan       *outer_plan;
 382         Plan       *inner_plan;
 383         Join       *plan;
 384
 385         outer_plan = create_plan(root, best_path->outerjoinpath);
 386         inner_plan = create_plan(root, best_path->innerjoinpath);
 387
 388         switch (best_path->path.pathtype)
 389         {
 390                 case T_MergeJoin:
 391                         plan = (Join *) create_mergejoin_plan(root,
 392                                                                                                   (MergePath *) best_path,
 393                                                                                                   outer_plan,
 394                                                                                                   inner_plan);
 395                         break;
 396                 case T_HashJoin:
 397                         plan = (Join *) create_hashjoin_plan(root,
 398                                                                                                  (HashPath *) best_path,
 399                                                                                                  outer_plan,
 400                                                                                                  inner_plan);
 401                         break;
 402                 case T_NestLoop:
 403                         plan = (Join *) create_nestloop_plan(root,
 404                                                                                                  (NestPath *) best_path,
 405                                                                                                  outer_plan,
 406                                                                                                  inner_plan);
 407                         break;
 408                 default:
 409                         elog(ERROR, "unrecognized node type: %d",
 410                                  (int) best_path->path.pathtype);
 411                         plan = NULL;            /* keep compiler quiet */
 412                         break;
 413         }
 414
 415 #ifdef NOT_USED
 416
 417         /*
 418          * * Expensive function pullups may have pulled local predicates *
 419          * into this path node.  Put them in the qpqual of the plan node. *
 420          * JMH, 6/15/92
 421          */
 422         if (get_loc_restrictinfo(best_path) != NIL)
 423                 set_qpqual((Plan) plan,
 424                                    list_concat(get_qpqual((Plan) plan),
 425                                    get_actual_clauses(get_loc_restrictinfo(best_path))));
 426 #endif
 427
 428         return plan;
 429 }
 430
 431 /*
 432  * create_append_plan
 433  *        Create an Append plan for 'best_path' and (recursively) plans
 434  *        for its subpaths.
 435  *
 436  *        Returns a Plan node.
 437  */
 438 static Append *
 439 create_append_plan(PlannerInfo *root, AppendPath *best_path)
 440 {
 441         Append     *plan;
 442         List       *tlist = build_relation_tlist(best_path->path.parent);
 443         List       *subplans = NIL;
 444         ListCell   *subpaths;
 445
 446         foreach(subpaths, best_path->subpaths)
 447         {
 448                 Path       *subpath = (Path *) lfirst(subpaths);
 449
 450                 subplans = lappend(subplans, create_plan(root, subpath));
 451         }
 452
 453         plan = make_append(subplans, false, tlist);
 454
 455         return plan;
 456 }
 457
 458 /*
 459  * create_result_plan
 460  *        Create a Result plan for 'best_path' and (recursively) plans
 461  *        for its subpaths.
 462  *
 463  *        Returns a Plan node.
 464  */
 465 static Result *
 466 create_result_plan(PlannerInfo *root, ResultPath *best_path)
 467 {
 468         Result     *plan;
 469         List       *tlist;
 470         List       *constclauses;
 471         Plan       *subplan;
 472
 473         if (best_path->path.parent)
 474                 tlist = build_relation_tlist(best_path->path.parent);
 475         else
 476                 tlist = NIL;                    /* will be filled in later */
 477
 478         if (best_path->subpath)
 479                 subplan = create_plan(root, best_path->subpath);
 480         else
 481                 subplan = NULL;
 482
 483         constclauses = order_qual_clauses(root, best_path->constantqual);
 484
 485         plan = make_result(tlist, (Node *) constclauses, subplan);
 486
 487         return plan;
 488 }
 489
 490 /*
 491  * create_material_plan
 492  *        Create a Material plan for 'best_path' and (recursively) plans
 493  *        for its subpaths.
 494  *
 495  *        Returns a Plan node.
 496  */
 497 static Material *
 498 create_material_plan(PlannerInfo *root, MaterialPath *best_path)
 499 {
 500         Material   *plan;
 501         Plan       *subplan;
 502
 503         subplan = create_plan(root, best_path->subpath);
 504
 505         /* We don't want any excess columns in the materialized tuples */
 506         disuse_physical_tlist(subplan, best_path->subpath);
 507
 508         plan = make_material(subplan);
 509
 510         copy_path_costsize(&plan->plan, (Path *) best_path);
 511
 512         return plan;
 513 }
 514
 515 /*
 516  * create_unique_plan
 517  *        Create a Unique plan for 'best_path' and (recursively) plans
 518  *        for its subpaths.
 519  *
 520  *        Returns a Plan node.
 521  */
 522 static Plan *
 523 create_unique_plan(PlannerInfo *root, UniquePath *best_path)
 524 {
 525         Plan       *plan;
 526         Plan       *subplan;
 527         List       *uniq_exprs;
 528         int                     numGroupCols;
 529         AttrNumber *groupColIdx;
 530         int                     groupColPos;
 531         List       *newtlist;
 532         int                     nextresno;
 533         bool            newitems;
 534         ListCell   *l;
 535
 536         subplan = create_plan(root, best_path->subpath);
 537
 538         /*----------
 539          * As constructed, the subplan has a "flat" tlist containing just the
 540          * Vars needed here and at upper levels.  The values we are supposed
 541          * to unique-ify may be expressions in these variables.  We have to
 542          * add any such expressions to the subplan's tlist.  We then build
 543          * control information showing which subplan output columns are to be
 544          * examined by the grouping step.  (Since we do not remove any
 545          * existing subplan outputs, not all the output columns may be used
 546          * for grouping.)
 547          *
 548          * Note: the reason we don't remove any subplan outputs is that there
 549          * are scenarios where a Var is needed at higher levels even though
 550          * it is not one of the nominal outputs of an IN clause.        Consider
 551          *              WHERE x IN (SELECT y FROM t1,t2 WHERE y = z)
 552          * Implied equality deduction will generate an "x = z" clause, which may
 553          * get used instead of "x = y" in the upper join step.  Therefore the
 554          * sub-select had better deliver both y and z in its targetlist.
 555          * It is sufficient to unique-ify on y, however.
 556          *
 557          * To find the correct list of values to unique-ify, we look in the
 558          * information saved for IN expressions.  If this code is ever used in
 559          * other scenarios, some other way of finding what to unique-ify will
 560          * be needed.
 561          *----------
 562          */
 563         uniq_exprs = NIL;                       /* just to keep compiler quiet */
 564         foreach(l, root->in_info_list)
 565         {
 566                 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
 567
 568                 if (bms_equal(ininfo->righthand, best_path->path.parent->relids))
 569                 {
 570                         uniq_exprs = ininfo->sub_targetlist;
 571                         break;
 572                 }
 573         }
 574         if (l == NULL)                          /* fell out of loop? */
 575                 elog(ERROR, "could not find UniquePath in in_info_list");
 576
 577         /* set up to record positions of unique columns */
 578         numGroupCols = list_length(uniq_exprs);
 579         groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
 580         groupColPos = 0;
 581         /* not sure if tlist might be shared with other nodes, so copy */
 582         newtlist = copyObject(subplan->targetlist);
 583         nextresno = list_length(newtlist) + 1;
 584         newitems = false;
 585
 586         foreach(l, uniq_exprs)
 587         {
 588                 Node       *uniqexpr = lfirst(l);
 589                 TargetEntry *tle;
 590
 591                 tle = tlist_member(uniqexpr, newtlist);
 592                 if (!tle)
 593                 {
 594                         tle = makeTargetEntry((Expr *) uniqexpr,
 595                                                                   nextresno,
 596                                                                   NULL,
 597                                                                   false);
 598                         newtlist = lappend(newtlist, tle);
 599                         nextresno++;
 600                         newitems = true;
 601                 }
 602                 groupColIdx[groupColPos++] = tle->resno;
 603         }
 604
 605         if (newitems)
 606         {
 607                 /*
 608                  * If the top plan node can't do projections, we need to add a
 609                  * Result node to help it along.
 610                  */
 611                 if (!is_projection_capable_plan(subplan))
 612                         subplan = (Plan *) make_result(newtlist, NULL, subplan);
 613                 else
 614                         subplan->targetlist = newtlist;
 615         }
 616
 617         /* Done if we don't need to do any actual unique-ifying */
 618         if (best_path->umethod == UNIQUE_PATH_NOOP)
 619                 return subplan;
 620
 621         if (best_path->umethod == UNIQUE_PATH_HASH)
 622         {
 623                 long            numGroups;
 624
 625                 numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
 626
 627                 plan = (Plan *) make_agg(root,
 628                                                                  copyObject(subplan->targetlist),
 629                                                                  NIL,
 630                                                                  AGG_HASHED,
 631                                                                  numGroupCols,
 632                                                                  groupColIdx,
 633                                                                  numGroups,
 634                                                                  0,
 635                                                                  subplan);
 636         }
 637         else
 638         {
 639                 List       *sortList = NIL;
 640
 641                 for (groupColPos = 0; groupColPos < numGroupCols; groupColPos++)
 642                 {
 643                         TargetEntry *tle;
 644
 645                         tle = get_tle_by_resno(subplan->targetlist,
 646                                                                    groupColIdx[groupColPos]);
 647                         Assert(tle != NULL);
 648                         sortList = addTargetToSortList(NULL, tle,
 649                                                                                    sortList, subplan->targetlist,
 650                                                                                    SORTBY_ASC, NIL, false);
 651                 }
 652                 plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
 653                 plan = (Plan *) make_unique(plan, sortList);
 654         }
 655
 656         /* Adjust output size estimate (other fields should be OK already) */
 657         plan->plan_rows = best_path->rows;
 658
 659         return plan;
 660 }
 661
 662
 663 /*****************************************************************************
 664  *
 665  *      BASE-RELATION SCAN METHODS
 666  *
 667  *****************************************************************************/
 668
 669
 670 /*
 671  * create_seqscan_plan
 672  *       Returns a seqscan plan for the base relation scanned by 'best_path'
 673  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 674  */
 675 static SeqScan *
 676 create_seqscan_plan(PlannerInfo *root, Path *best_path,
 677                                         List *tlist, List *scan_clauses)
 678 {
 679         SeqScan    *scan_plan;
 680         Index           scan_relid = best_path->parent->relid;
 681
 682         /* it should be a base rel... */
 683         Assert(scan_relid > 0);
 684         Assert(best_path->parent->rtekind == RTE_RELATION);
 685
 686         /* Reduce RestrictInfo list to bare expressions */
 687         scan_clauses = get_actual_clauses(scan_clauses);
 688
 689         /* Sort clauses into best execution order */
 690         scan_clauses = order_qual_clauses(root, scan_clauses);
 691
 692         scan_plan = make_seqscan(tlist,
 693                                                          scan_clauses,
 694                                                          scan_relid);
 695
 696         copy_path_costsize(&scan_plan->plan, best_path);
 697
 698         return scan_plan;
 699 }
 700
 701 /*
 702  * create_indexscan_plan
 703  *        Returns an indexscan plan for the base relation scanned by 'best_path'
 704  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 705  *
 706  * The indexquals list of the path contains implicitly-ANDed qual conditions.
 707  * The list can be empty --- then no index restrictions will be applied during
 708  * the scan.
 709  *
 710  * If nonlossy_clauses isn't NULL, *nonlossy_clauses receives a list of the
 711  * nonlossy indexquals.
 712  */
 713 static IndexScan *
 714 create_indexscan_plan(PlannerInfo *root,
 715                                           IndexPath *best_path,
 716                                           List *tlist,
 717                                           List *scan_clauses,
 718                                           List **nonlossy_clauses)
 719 {
 720         List       *indexquals = best_path->indexquals;
 721         Index           baserelid = best_path->path.parent->relid;
 722         Oid                     indexoid = best_path->indexinfo->indexoid;
 723         List       *qpqual;
 724         List       *stripped_indexquals;
 725         List       *fixed_indexquals;
 726         List       *nonlossy_indexquals;
 727         List       *indexstrategy;
 728         List       *indexsubtype;
 729         ListCell   *l;
 730         IndexScan  *scan_plan;
 731
 732         /* it should be a base rel... */
 733         Assert(baserelid > 0);
 734         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 735
 736         /*
 737          * Build "stripped" indexquals structure (no RestrictInfos) to pass to
 738          * executor as indexqualorig
 739          */
 740         stripped_indexquals = get_actual_clauses(indexquals);
 741
 742         /*
 743          * The executor needs a copy with the indexkey on the left of each
 744          * clause and with index attr numbers substituted for table ones. This
 745          * pass also gets strategy info and looks for "lossy" operators.
 746          */
 747         fix_indexqual_references(indexquals, best_path,
 748                                                          &fixed_indexquals,
 749                                                          &nonlossy_indexquals,
 750                                                          &indexstrategy,
 751                                                          &indexsubtype);
 752
 753         /* pass back nonlossy quals if caller wants 'em */
 754         if (nonlossy_clauses)
 755                 *nonlossy_clauses = nonlossy_indexquals;
 756
 757         /*
 758          * If this is an innerjoin scan, the indexclauses will contain join
 759          * clauses that are not present in scan_clauses (since the passed-in
 760          * value is just the rel's baserestrictinfo list).  We must add these
 761          * clauses to scan_clauses to ensure they get checked.  In most cases
 762          * we will remove the join clauses again below, but if a join clause
 763          * contains a special operator, we need to make sure it gets into the
 764          * scan_clauses.
 765          *
 766          * Note: pointer comparison should be enough to determine RestrictInfo
 767          * matches.
 768          */
 769         if (best_path->isjoininner)
 770                 scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
 771
 772         /*
 773          * The qpqual list must contain all restrictions not automatically
 774          * handled by the index.  All the predicates in the indexquals will be
 775          * checked (either by the index itself, or by nodeIndexscan.c), but if
 776          * there are any "special" operators involved then they must be included
 777          * in qpqual.  Also, any lossy index operators must be rechecked in
 778          * the qpqual.  The upshot is that qpqual must contain scan_clauses
 779          * minus whatever appears in nonlossy_indexquals.
 780          *
 781          * In normal cases simple pointer equality checks will be enough to
 782          * spot duplicate RestrictInfos, so we try that first.  In some situations
 783          * (particularly with OR'd index conditions) we may have scan_clauses
 784          * that are not equal to, but are logically implied by, the index quals;
 785          * so we also try a pred_test() check to see if we can discard quals
 786          * that way.
 787          *
 788          * While at it, we strip off the RestrictInfos to produce a list of
 789          * plain expressions.
 790          */
 791         qpqual = NIL;
 792         foreach(l, scan_clauses)
 793         {
 794                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 795
 796                 Assert(IsA(rinfo, RestrictInfo));
 797                 if (list_member_ptr(nonlossy_indexquals, rinfo))
 798                         continue;
 799                 if (pred_test(list_make1(rinfo->clause), nonlossy_indexquals))
 800                         continue;
 801                 qpqual = lappend(qpqual, rinfo->clause);
 802         }
 803
 804         /* Sort clauses into best execution order */
 805         qpqual = order_qual_clauses(root, qpqual);
 806
 807         /* Finally ready to build the plan node */
 808         scan_plan = make_indexscan(tlist,
 809                                                            qpqual,
 810                                                            baserelid,
 811                                                            indexoid,
 812                                                            fixed_indexquals,
 813                                                            stripped_indexquals,
 814                                                            indexstrategy,
 815                                                            indexsubtype,
 816                                                            best_path->indexscandir);
 817
 818         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 819         /* use the indexscan-specific rows estimate, not the parent rel's */
 820         scan_plan->scan.plan.plan_rows = best_path->rows;
 821
 822         return scan_plan;
 823 }
 824
 825 /*
 826  * create_bitmap_scan_plan
 827  *        Returns a bitmap scan plan for the base relation scanned by 'best_path'
 828  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 829  */
 830 static BitmapHeapScan *
 831 create_bitmap_scan_plan(PlannerInfo *root,
 832                                                 BitmapHeapPath *best_path,
 833                                                 List *tlist,
 834                                                 List *scan_clauses)
 835 {
 836         Index           baserelid = best_path->path.parent->relid;
 837         Plan       *bitmapqualplan;
 838         List       *bitmapqualorig;
 839         List       *indexquals;
 840         List       *qpqual;
 841         ListCell   *l;
 842         BitmapHeapScan *scan_plan;
 843
 844         /* it should be a base rel... */
 845         Assert(baserelid > 0);
 846         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 847
 848         /* Process the bitmapqual tree into a Plan tree and qual lists */
 849         bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
 850                                                                                    &bitmapqualorig, &indexquals);
 851
 852         /* Reduce RestrictInfo list to bare expressions */
 853         scan_clauses = get_actual_clauses(scan_clauses);
 854
 855         /*
 856          * If this is a innerjoin scan, the indexclauses will contain join
 857          * clauses that are not present in scan_clauses (since the passed-in
 858          * value is just the rel's baserestrictinfo list).  We must add these
 859          * clauses to scan_clauses to ensure they get checked.  In most cases
 860          * we will remove the join clauses again below, but if a join clause
 861          * contains a special operator, we need to make sure it gets into the
 862          * scan_clauses.
 863          */
 864         if (best_path->isjoininner)
 865         {
 866                 scan_clauses = list_union(scan_clauses, bitmapqualorig);
 867         }
 868
 869         /*
 870          * The qpqual list must contain all restrictions not automatically
 871          * handled by the index.  All the predicates in the indexquals will be
 872          * checked (either by the index itself, or by nodeBitmapHeapscan.c),
 873          * but if there are any "special" or lossy operators involved then they
 874          * must be added to qpqual.  The upshot is that qpquals must contain
 875          * scan_clauses minus whatever appears in indexquals.
 876          *
 877          * In normal cases simple equal() checks will be enough to spot duplicate
 878          * clauses, so we try that first.  In some situations (particularly with
 879          * OR'd index conditions) we may have scan_clauses that are not equal to,
 880          * but are logically implied by, the index quals; so we also try a
 881          * pred_test() check to see if we can discard quals that way.
 882          */
 883         qpqual = NIL;
 884         foreach(l, scan_clauses)
 885         {
 886                 Node   *clause = (Node *) lfirst(l);
 887
 888                 if (list_member(indexquals, clause))
 889                         continue;
 890                 if (pred_test(list_make1(clause), indexquals))
 891                         continue;
 892                 qpqual = lappend(qpqual, clause);
 893         }
 894
 895         /* Sort clauses into best execution order */
 896         qpqual = order_qual_clauses(root, qpqual);
 897
 898         /*
 899          * When dealing with special or lossy operators, we will at this point
 900          * have duplicate clauses in qpqual and bitmapqualorig.  We may as well
 901          * drop 'em from bitmapqualorig, since there's no point in making the
 902          * tests twice.
 903          */
 904         bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
 905
 906         /* Finally ready to build the plan node */
 907         scan_plan = make_bitmap_heapscan(tlist,
 908                                                                          qpqual,
 909                                                                          bitmapqualplan,
 910                                                                          bitmapqualorig,
 911                                                                          baserelid);
 912
 913         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 914         /* use the indexscan-specific rows estimate, not the parent rel's */
 915         scan_plan->scan.plan.plan_rows = best_path->rows;
 916
 917         return scan_plan;
 918 }
 919
 920 /*
 921  * Given a bitmapqual tree, generate the Plan tree that implements it
 922  *
 923  * As byproducts, we also return in *qual and *indexqual the qual lists
 924  * (in implicit-AND form, without RestrictInfos) describing the original index
 925  * conditions and the generated indexqual conditions.  The latter is made to
 926  * exclude lossy index operators.
 927  */
 928 static Plan *
 929 create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
 930                                           List **qual, List **indexqual)
 931 {
 932         Plan       *plan;
 933
 934         if (IsA(bitmapqual, BitmapAndPath))
 935         {
 936                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
 937                 List       *subplans = NIL;
 938                 List       *subquals = NIL;
 939                 List       *subindexquals = NIL;
 940                 ListCell   *l;
 941
 942                 foreach(l, apath->bitmapquals)
 943                 {
 944                         Plan   *subplan;
 945                         List   *subqual;
 946                         List   *subindexqual;
 947
 948                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
 949                                                                                         &subqual, &subindexqual);
 950                         subplans = lappend(subplans, subplan);
 951                         subquals = list_concat(subquals, subqual);
 952                         subindexquals = list_concat(subindexquals, subindexqual);
 953                 }
 954                 plan = (Plan *) make_bitmap_and(subplans);
 955                 plan->startup_cost = apath->path.startup_cost;
 956                 plan->total_cost = apath->path.total_cost;
 957                 plan->plan_rows =
 958                         clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
 959                 plan->plan_width = 0;   /* meaningless */
 960                 *qual = subquals;
 961                 *indexqual = subindexquals;
 962         }
 963         else if (IsA(bitmapqual, BitmapOrPath))
 964         {
 965                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
 966                 List       *subplans = NIL;
 967                 List       *subquals = NIL;
 968                 List       *subindexquals = NIL;
 969                 ListCell   *l;
 970
 971                 foreach(l, opath->bitmapquals)
 972                 {
 973                         Plan   *subplan;
 974                         List   *subqual;
 975                         List   *subindexqual;
 976
 977                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
 978                                                                                         &subqual, &subindexqual);
 979                         subplans = lappend(subplans, subplan);
 980                         subquals = lappend(subquals,
 981                                                            make_ands_explicit(subqual));
 982                         subindexquals = lappend(subindexquals,
 983                                                                         make_ands_explicit(subindexqual));
 984                 }
 985                 plan = (Plan *) make_bitmap_or(subplans);
 986                 plan->startup_cost = opath->path.startup_cost;
 987                 plan->total_cost = opath->path.total_cost;
 988                 plan->plan_rows =
 989                         clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
 990                 plan->plan_width = 0;   /* meaningless */
 991                 *qual = list_make1(make_orclause(subquals));
 992                 *indexqual = list_make1(make_orclause(subindexquals));
 993         }
 994         else if (IsA(bitmapqual, IndexPath))
 995         {
 996                 IndexPath *ipath = (IndexPath *) bitmapqual;
 997                 IndexScan *iscan;
 998                 List   *nonlossy_clauses;
 999
1000                 /* Use the regular indexscan plan build machinery... */
1001                 iscan = create_indexscan_plan(root, ipath, NIL, NIL,
1002                                                                           &nonlossy_clauses);
1003                 /* then convert to a bitmap indexscan */
1004                 plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
1005                                                                                           iscan->indexid,
1006                                                                                           iscan->indexqual,
1007                                                                                           iscan->indexqualorig,
1008                                                                                           iscan->indexstrategy,
1009                                                                                           iscan->indexsubtype);
1010                 plan->startup_cost = 0.0;
1011                 plan->total_cost = ipath->indextotalcost;
1012                 plan->plan_rows =
1013                         clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
1014                 plan->plan_width = 0;   /* meaningless */
1015                 *qual = get_actual_clauses(ipath->indexclauses);
1016                 *indexqual = get_actual_clauses(nonlossy_clauses);
1017         }
1018         else
1019         {
1020                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
1021                 plan = NULL;                    /* keep compiler quiet */
1022         }
1023
1024         return plan;
1025 }
1026
1027 /*
1028  * create_tidscan_plan
1029  *       Returns a tidscan plan for the base relation scanned by 'best_path'
1030  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1031  */
1032 static TidScan *
1033 create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
1034                                         List *tlist, List *scan_clauses)
1035 {
1036         TidScan    *scan_plan;
1037         Index           scan_relid = best_path->path.parent->relid;
1038
1039         /* it should be a base rel... */
1040         Assert(scan_relid > 0);
1041         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1042
1043         /* Reduce RestrictInfo list to bare expressions */
1044         scan_clauses = get_actual_clauses(scan_clauses);
1045
1046         /* Sort clauses into best execution order */
1047         scan_clauses = order_qual_clauses(root, scan_clauses);
1048
1049         scan_plan = make_tidscan(tlist,
1050                                                          scan_clauses,
1051                                                          scan_relid,
1052                                                          best_path->tideval);
1053
1054         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1055
1056         return scan_plan;
1057 }
1058
1059 /*
1060  * create_subqueryscan_plan
1061  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
1062  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1063  */
1064 static SubqueryScan *
1065 create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
1066                                                  List *tlist, List *scan_clauses)
1067 {
1068         SubqueryScan *scan_plan;
1069         Index           scan_relid = best_path->parent->relid;
1070
1071         /* it should be a subquery base rel... */
1072         Assert(scan_relid > 0);
1073         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
1074
1075         /* Reduce RestrictInfo list to bare expressions */
1076         scan_clauses = get_actual_clauses(scan_clauses);
1077
1078         /* Sort clauses into best execution order */
1079         scan_clauses = order_qual_clauses(root, scan_clauses);
1080
1081         scan_plan = make_subqueryscan(tlist,
1082                                                                   scan_clauses,
1083                                                                   scan_relid,
1084                                                                   best_path->parent->subplan);
1085
1086         copy_path_costsize(&scan_plan->scan.plan, best_path);
1087
1088         return scan_plan;
1089 }
1090
1091 /*
1092  * create_functionscan_plan
1093  *       Returns a functionscan plan for the base relation scanned by 'best_path'
1094  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1095  */
1096 static FunctionScan *
1097 create_functionscan_plan(PlannerInfo *root, Path *best_path,
1098                                                  List *tlist, List *scan_clauses)
1099 {
1100         FunctionScan *scan_plan;
1101         Index           scan_relid = best_path->parent->relid;
1102
1103         /* it should be a function base rel... */
1104         Assert(scan_relid > 0);
1105         Assert(best_path->parent->rtekind == RTE_FUNCTION);
1106
1107         /* Reduce RestrictInfo list to bare expressions */
1108         scan_clauses = get_actual_clauses(scan_clauses);
1109
1110         /* Sort clauses into best execution order */
1111         scan_clauses = order_qual_clauses(root, scan_clauses);
1112
1113         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid);
1114
1115         copy_path_costsize(&scan_plan->scan.plan, best_path);
1116
1117         return scan_plan;
1118 }
1119
1120 /*****************************************************************************
1121  *
1122  *      JOIN METHODS
1123  *
1124  *****************************************************************************/
1125
1126 static NestLoop *
1127 create_nestloop_plan(PlannerInfo *root,
1128                                          NestPath *best_path,
1129                                          Plan *outer_plan,
1130                                          Plan *inner_plan)
1131 {
1132         List       *tlist = build_relation_tlist(best_path->path.parent);
1133         List       *joinrestrictclauses = best_path->joinrestrictinfo;
1134         List       *joinclauses;
1135         List       *otherclauses;
1136         NestLoop   *join_plan;
1137
1138         if (IsA(best_path->innerjoinpath, IndexPath))
1139         {
1140                 /*
1141                  * An index is being used to reduce the number of tuples scanned
1142                  * in the inner relation.  If there are join clauses being used
1143                  * with the index, we may remove those join clauses from the list
1144                  * of clauses that have to be checked as qpquals at the join node.
1145                  *
1146                  * We can also remove any join clauses that are redundant with those
1147                  * being used in the index scan; prior redundancy checks will not
1148                  * have caught this case because the join clauses would never have
1149                  * been put in the same joininfo list.
1150                  *
1151                  * We can skip this if the index path is an ordinary indexpath and
1152                  * not a special innerjoin path.
1153                  */
1154                 IndexPath  *innerpath = (IndexPath *) best_path->innerjoinpath;
1155
1156                 if (innerpath->isjoininner)
1157                 {
1158                         joinrestrictclauses =
1159                                 select_nonredundant_join_clauses(root,
1160                                                                                                  joinrestrictclauses,
1161                                                                                                  innerpath->indexclauses,
1162                                                                                                  IS_OUTER_JOIN(best_path->jointype));
1163                 }
1164         }
1165         else if (IsA(best_path->innerjoinpath, BitmapHeapPath))
1166         {
1167                 /*
1168                  * Same deal for bitmapped index scans.
1169                  */
1170                 BitmapHeapPath *innerpath = (BitmapHeapPath *) best_path->innerjoinpath;
1171
1172                 if (innerpath->isjoininner)
1173                 {
1174                         List       *bitmapclauses;
1175
1176                         bitmapclauses =
1177                                 make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
1178                                                                                                   true, true);
1179                         joinrestrictclauses =
1180                                 select_nonredundant_join_clauses(root,
1181                                                                                                  joinrestrictclauses,
1182                                                                                                  bitmapclauses,
1183                                                                                                  IS_OUTER_JOIN(best_path->jointype));
1184                 }
1185         }
1186
1187         /* Get the join qual clauses (in plain expression form) */
1188         if (IS_OUTER_JOIN(best_path->jointype))
1189         {
1190                 get_actual_join_clauses(joinrestrictclauses,
1191                                                                 &joinclauses, &otherclauses);
1192         }
1193         else
1194         {
1195                 /* We can treat all clauses alike for an inner join */
1196                 joinclauses = get_actual_clauses(joinrestrictclauses);
1197                 otherclauses = NIL;
1198         }
1199
1200         /* Sort clauses into best execution order */
1201         joinclauses = order_qual_clauses(root, joinclauses);
1202         otherclauses = order_qual_clauses(root, otherclauses);
1203
1204         join_plan = make_nestloop(tlist,
1205                                                           joinclauses,
1206                                                           otherclauses,
1207                                                           outer_plan,
1208                                                           inner_plan,
1209                                                           best_path->jointype);
1210
1211         copy_path_costsize(&join_plan->join.plan, &best_path->path);
1212
1213         return join_plan;
1214 }
1215
1216 static MergeJoin *
1217 create_mergejoin_plan(PlannerInfo *root,
1218                                           MergePath *best_path,
1219                                           Plan *outer_plan,
1220                                           Plan *inner_plan)
1221 {
1222         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1223         List       *joinclauses;
1224         List       *otherclauses;
1225         List       *mergeclauses;
1226         MergeJoin  *join_plan;
1227
1228         /* Get the join qual clauses (in plain expression form) */
1229         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1230         {
1231                 get_actual_join_clauses(best_path->jpath.joinrestrictinfo,
1232                                                                 &joinclauses, &otherclauses);
1233         }
1234         else
1235         {
1236                 /* We can treat all clauses alike for an inner join */
1237                 joinclauses = get_actual_clauses(best_path->jpath.joinrestrictinfo);
1238                 otherclauses = NIL;
1239         }
1240
1241         /*
1242          * Remove the mergeclauses from the list of join qual clauses, leaving
1243          * the list of quals that must be checked as qpquals.
1244          */
1245         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
1246         joinclauses = list_difference(joinclauses, mergeclauses);
1247
1248         /*
1249          * Rearrange mergeclauses, if needed, so that the outer variable is
1250          * always on the left.
1251          */
1252         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
1253                                                  best_path->jpath.outerjoinpath->parent->relids);
1254
1255         /* Sort clauses into best execution order */
1256         /* NB: do NOT reorder the mergeclauses */
1257         joinclauses = order_qual_clauses(root, joinclauses);
1258         otherclauses = order_qual_clauses(root, otherclauses);
1259
1260         /*
1261          * Create explicit sort nodes for the outer and inner join paths if
1262          * necessary.  The sort cost was already accounted for in the path.
1263          * Make sure there are no excess columns in the inputs if sorting.
1264          */
1265         if (best_path->outersortkeys)
1266         {
1267                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
1268                 outer_plan = (Plan *)
1269                         make_sort_from_pathkeys(root,
1270                                                                         outer_plan,
1271                                                                         best_path->outersortkeys);
1272         }
1273
1274         if (best_path->innersortkeys)
1275         {
1276                 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1277                 inner_plan = (Plan *)
1278                         make_sort_from_pathkeys(root,
1279                                                                         inner_plan,
1280                                                                         best_path->innersortkeys);
1281         }
1282
1283         /*
1284          * Now we can build the mergejoin node.
1285          */
1286         join_plan = make_mergejoin(tlist,
1287                                                            joinclauses,
1288                                                            otherclauses,
1289                                                            mergeclauses,
1290                                                            outer_plan,
1291                                                            inner_plan,
1292                                                            best_path->jpath.jointype);
1293
1294         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1295
1296         return join_plan;
1297 }
1298
1299 static HashJoin *
1300 create_hashjoin_plan(PlannerInfo *root,
1301                                          HashPath *best_path,
1302                                          Plan *outer_plan,
1303                                          Plan *inner_plan)
1304 {
1305         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1306         List       *joinclauses;
1307         List       *otherclauses;
1308         List       *hashclauses;
1309         HashJoin   *join_plan;
1310         Hash       *hash_plan;
1311
1312         /* Get the join qual clauses (in plain expression form) */
1313         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1314         {
1315                 get_actual_join_clauses(best_path->jpath.joinrestrictinfo,
1316                                                                 &joinclauses, &otherclauses);
1317         }
1318         else
1319         {
1320                 /* We can treat all clauses alike for an inner join */
1321                 joinclauses = get_actual_clauses(best_path->jpath.joinrestrictinfo);
1322                 otherclauses = NIL;
1323         }
1324
1325         /*
1326          * Remove the hashclauses from the list of join qual clauses, leaving
1327          * the list of quals that must be checked as qpquals.
1328          */
1329         hashclauses = get_actual_clauses(best_path->path_hashclauses);
1330         joinclauses = list_difference(joinclauses, hashclauses);
1331
1332         /*
1333          * Rearrange hashclauses, if needed, so that the outer variable is
1334          * always on the left.
1335          */
1336         hashclauses = get_switched_clauses(best_path->path_hashclauses,
1337                                                  best_path->jpath.outerjoinpath->parent->relids);
1338
1339         /* Sort clauses into best execution order */
1340         joinclauses = order_qual_clauses(root, joinclauses);
1341         otherclauses = order_qual_clauses(root, otherclauses);
1342         hashclauses = order_qual_clauses(root, hashclauses);
1343
1344         /* We don't want any excess columns in the hashed tuples */
1345         disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1346
1347         /*
1348          * Build the hash node and hash join node.
1349          */
1350         hash_plan = make_hash(inner_plan);
1351         join_plan = make_hashjoin(tlist,
1352                                                           joinclauses,
1353                                                           otherclauses,
1354                                                           hashclauses,
1355                                                           outer_plan,
1356                                                           (Plan *) hash_plan,
1357                                                           best_path->jpath.jointype);
1358
1359         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1360
1361         return join_plan;
1362 }
1363
1364
1365 /*****************************************************************************
1366  *
1367  *      SUPPORTING ROUTINES
1368  *
1369  *****************************************************************************/
1370
1371 /*
1372  * fix_indexqual_references
1373  *        Adjust indexqual clauses to the form the executor's indexqual
1374  *        machinery needs, and check for recheckable (lossy) index conditions.
1375  *
1376  * We have five tasks here:
1377  *      * Remove RestrictInfo nodes from the input clauses.
1378  *      * Index keys must be represented by Var nodes with varattno set to the
1379  *        index's attribute number, not the attribute number in the original rel.
1380  *      * If the index key is on the right, commute the clause to put it on the
1381  *        left.
1382  *      * We must construct lists of operator strategy numbers and subtypes
1383  *        for the top-level operators of each index clause.
1384  *      * We must detect any lossy index operators.  The API is that we return
1385  *        a list of the input clauses whose operators are NOT lossy.
1386  *
1387  * fixed_indexquals receives a modified copy of the indexquals list --- the
1388  * original is not changed.  Note also that the copy shares no substructure
1389  * with the original; this is needed in case there is a subplan in it (we need
1390  * two separate copies of the subplan tree, or things will go awry).
1391  *
1392  * nonlossy_indexquals receives a list of the original input clauses (with
1393  * RestrictInfos) that contain non-lossy operators.
1394  *
1395  * indexstrategy receives an integer list of strategy numbers.
1396  * indexsubtype receives an OID list of strategy subtypes.
1397  */
1398 static void
1399 fix_indexqual_references(List *indexquals, IndexPath *index_path,
1400                                                  List **fixed_indexquals,
1401                                                  List **nonlossy_indexquals,
1402                                                  List **indexstrategy,
1403                                                  List **indexsubtype)
1404 {
1405         IndexOptInfo *index = index_path->indexinfo;
1406         ListCell   *l;
1407
1408         *fixed_indexquals = NIL;
1409         *nonlossy_indexquals = NIL;
1410         *indexstrategy = NIL;
1411         *indexsubtype = NIL;
1412
1413         /*
1414          * For each qual clause, commute if needed to put the indexkey operand on
1415          * the left, and then fix its varattno.  (We do not need to change the
1416          * other side of the clause.)  Then determine the operator's strategy
1417          * number and subtype number, and check for lossy index behavior.
1418          */
1419         foreach(l, indexquals)
1420         {
1421                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1422                 OpExpr     *clause;
1423                 OpExpr     *newclause;
1424                 Oid                     opclass;
1425                 int                     stratno;
1426                 Oid                     stratsubtype;
1427                 bool            recheck;
1428
1429                 Assert(IsA(rinfo, RestrictInfo));
1430                 clause = (OpExpr *) rinfo->clause;
1431                 if (!IsA(clause, OpExpr) ||
1432                         list_length(clause->args) != 2)
1433                         elog(ERROR, "indexqual clause is not binary opclause");
1434
1435                 /*
1436                  * Make a copy that will become the fixed clause.
1437                  *
1438                  * We used to try to do a shallow copy here, but that fails if there
1439                  * is a subplan in the arguments of the opclause.  So just do a
1440                  * full copy.
1441                  */
1442                 newclause = (OpExpr *) copyObject((Node *) clause);
1443
1444                 /*
1445                  * Check to see if the indexkey is on the right; if so, commute
1446                  * the clause.  The indexkey should be the side that refers to
1447                  * (only) the base relation.
1448                  */
1449                 if (!bms_equal(rinfo->left_relids, index->rel->relids))
1450                         CommuteClause(newclause);
1451
1452                 /*
1453                  * Now, determine which index attribute this is, change the
1454                  * indexkey operand as needed, and get the index opclass.
1455                  */
1456                 linitial(newclause->args) =
1457                         fix_indexqual_operand(linitial(newclause->args),
1458                                                                   index,
1459                                                                   &opclass);
1460
1461                 *fixed_indexquals = lappend(*fixed_indexquals, newclause);
1462
1463                 /*
1464                  * Look up the (possibly commuted) operator in the operator class
1465                  * to get its strategy numbers and the recheck indicator.  This
1466                  * also double-checks that we found an operator matching the
1467                  * index.
1468                  */
1469                 get_op_opclass_properties(newclause->opno, opclass,
1470                                                                   &stratno, &stratsubtype, &recheck);
1471
1472                 *indexstrategy = lappend_int(*indexstrategy, stratno);
1473                 *indexsubtype = lappend_oid(*indexsubtype, stratsubtype);
1474
1475                 /* If it's not lossy, add to nonlossy_indexquals */
1476                 if (!recheck)
1477                         *nonlossy_indexquals = lappend(*nonlossy_indexquals, rinfo);
1478         }
1479 }
1480
1481 static Node *
1482 fix_indexqual_operand(Node *node, IndexOptInfo *index, Oid *opclass)
1483 {
1484         /*
1485          * We represent index keys by Var nodes having the varno of the base
1486          * table but varattno equal to the index's attribute number (index
1487          * column position).  This is a bit hokey ... would be cleaner to use
1488          * a special-purpose node type that could not be mistaken for a
1489          * regular Var.  But it will do for now.
1490          */
1491         Var                *result;
1492         int                     pos;
1493         ListCell   *indexpr_item;
1494
1495         /*
1496          * Remove any binary-compatible relabeling of the indexkey
1497          */
1498         if (IsA(node, RelabelType))
1499                 node = (Node *) ((RelabelType *) node)->arg;
1500
1501         if (IsA(node, Var) &&
1502                 ((Var *) node)->varno == index->rel->relid)
1503         {
1504                 /* Try to match against simple index columns */
1505                 int                     varatt = ((Var *) node)->varattno;
1506
1507                 if (varatt != 0)
1508                 {
1509                         for (pos = 0; pos < index->ncolumns; pos++)
1510                         {
1511                                 if (index->indexkeys[pos] == varatt)
1512                                 {
1513                                         result = (Var *) copyObject(node);
1514                                         result->varattno = pos + 1;
1515                                         /* return the correct opclass, too */
1516                                         *opclass = index->classlist[pos];
1517                                         return (Node *) result;
1518                                 }
1519                         }
1520                 }
1521         }
1522
1523         /* Try to match against index expressions */
1524         indexpr_item = list_head(index->indexprs);
1525         for (pos = 0; pos < index->ncolumns; pos++)
1526         {
1527                 if (index->indexkeys[pos] == 0)
1528                 {
1529                         Node       *indexkey;
1530
1531                         if (indexpr_item == NULL)
1532                                 elog(ERROR, "too few entries in indexprs list");
1533                         indexkey = (Node *) lfirst(indexpr_item);
1534                         if (indexkey && IsA(indexkey, RelabelType))
1535                                 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
1536                         if (equal(node, indexkey))
1537                         {
1538                                 /* Found a match */
1539                                 result = makeVar(index->rel->relid, pos + 1,
1540                                                                  exprType(lfirst(indexpr_item)), -1,
1541                                                                  0);
1542                                 /* return the correct opclass, too */
1543                                 *opclass = index->classlist[pos];
1544                                 return (Node *) result;
1545                         }
1546                         indexpr_item = lnext(indexpr_item);
1547                 }
1548         }
1549
1550         /* Ooops... */
1551         elog(ERROR, "node is not an index attribute");
1552         return NULL;                            /* keep compiler quiet */
1553 }
1554
1555 /*
1556  * get_switched_clauses
1557  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
1558  *        extract the bare clauses, and rearrange the elements within the
1559  *        clauses, if needed, so the outer join variable is on the left and
1560  *        the inner is on the right.  The original data structure is not touched;
1561  *        a modified list is returned.
1562  */
1563 static List *
1564 get_switched_clauses(List *clauses, Relids outerrelids)
1565 {
1566         List       *t_list = NIL;
1567         ListCell   *l;
1568
1569         foreach(l, clauses)
1570         {
1571                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1572                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
1573
1574                 Assert(is_opclause(clause));
1575                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
1576                 {
1577                         /*
1578                          * Duplicate just enough of the structure to allow commuting
1579                          * the clause without changing the original list.  Could use
1580                          * copyObject, but a complete deep copy is overkill.
1581                          */
1582                         OpExpr     *temp = makeNode(OpExpr);
1583
1584                         temp->opno = clause->opno;
1585                         temp->opfuncid = InvalidOid;
1586                         temp->opresulttype = clause->opresulttype;
1587                         temp->opretset = clause->opretset;
1588                         temp->args = list_copy(clause->args);
1589                         /* Commute it --- note this modifies the temp node in-place. */
1590                         CommuteClause(temp);
1591                         t_list = lappend(t_list, temp);
1592                 }
1593                 else
1594                         t_list = lappend(t_list, clause);
1595         }
1596         return t_list;
1597 }
1598
1599 /*
1600  * order_qual_clauses
1601  *              Given a list of qual clauses that will all be evaluated at the same
1602  *              plan node, sort the list into the order we want to check the quals
1603  *              in at runtime.
1604  *
1605  * Ideally the order should be driven by a combination of execution cost and
1606  * selectivity, but unfortunately we have so little information about
1607  * execution cost of operators that it's really hard to do anything smart.
1608  * For now, we just move any quals that contain SubPlan references (but not
1609  * InitPlan references) to the end of the list.
1610  */
1611 List *
1612 order_qual_clauses(PlannerInfo *root, List *clauses)
1613 {
1614         List       *nosubplans;
1615         List       *withsubplans;
1616         ListCell   *l;
1617
1618         /* No need to work hard if the query is subselect-free */
1619         if (!root->parse->hasSubLinks)
1620                 return clauses;
1621
1622         nosubplans = NIL;
1623         withsubplans = NIL;
1624         foreach(l, clauses)
1625         {
1626                 Node       *clause = (Node *) lfirst(l);
1627
1628                 if (contain_subplans(clause))
1629                         withsubplans = lappend(withsubplans, clause);
1630                 else
1631                         nosubplans = lappend(nosubplans, clause);
1632         }
1633
1634         return list_concat(nosubplans, withsubplans);
1635 }
1636
1637 /*
1638  * Copy cost and size info from a Path node to the Plan node created from it.
1639  * The executor won't use this info, but it's needed by EXPLAIN.
1640  */
1641 static void
1642 copy_path_costsize(Plan *dest, Path *src)
1643 {
1644         if (src)
1645         {
1646                 dest->startup_cost = src->startup_cost;
1647                 dest->total_cost = src->total_cost;
1648                 dest->plan_rows = src->parent->rows;
1649                 dest->plan_width = src->parent->width;
1650         }
1651         else
1652         {
1653                 dest->startup_cost = 0;
1654                 dest->total_cost = 0;
1655                 dest->plan_rows = 0;
1656                 dest->plan_width = 0;
1657         }
1658 }
1659
1660 /*
1661  * Copy cost and size info from a lower plan node to an inserted node.
1662  * This is not critical, since the decisions have already been made,
1663  * but it helps produce more reasonable-looking EXPLAIN output.
1664  * (Some callers alter the info after copying it.)
1665  */
1666 static void
1667 copy_plan_costsize(Plan *dest, Plan *src)
1668 {
1669         if (src)
1670         {
1671                 dest->startup_cost = src->startup_cost;
1672                 dest->total_cost = src->total_cost;
1673                 dest->plan_rows = src->plan_rows;
1674                 dest->plan_width = src->plan_width;
1675         }
1676         else
1677         {
1678                 dest->startup_cost = 0;
1679                 dest->total_cost = 0;
1680                 dest->plan_rows = 0;
1681                 dest->plan_width = 0;
1682         }
1683 }
1684
1685
1686 /*****************************************************************************
1687  *
1688  *      PLAN NODE BUILDING ROUTINES
1689  *
1690  * Some of these are exported because they are called to build plan nodes
1691  * in contexts where we're not deriving the plan node from a path node.
1692  *
1693  *****************************************************************************/
1694
1695 static SeqScan *
1696 make_seqscan(List *qptlist,
1697                          List *qpqual,
1698                          Index scanrelid)
1699 {
1700         SeqScan    *node = makeNode(SeqScan);
1701         Plan       *plan = &node->plan;
1702
1703         /* cost should be inserted by caller */
1704         plan->targetlist = qptlist;
1705         plan->qual = qpqual;
1706         plan->lefttree = NULL;
1707         plan->righttree = NULL;
1708         node->scanrelid = scanrelid;
1709
1710         return node;
1711 }
1712
1713 static IndexScan *
1714 make_indexscan(List *qptlist,
1715                            List *qpqual,
1716                            Index scanrelid,
1717                            Oid indexid,
1718                            List *indexqual,
1719                            List *indexqualorig,
1720                            List *indexstrategy,
1721                            List *indexsubtype,
1722                            ScanDirection indexscandir)
1723 {
1724         IndexScan  *node = makeNode(IndexScan);
1725         Plan       *plan = &node->scan.plan;
1726
1727         /* cost should be inserted by caller */
1728         plan->targetlist = qptlist;
1729         plan->qual = qpqual;
1730         plan->lefttree = NULL;
1731         plan->righttree = NULL;
1732         node->scan.scanrelid = scanrelid;
1733         node->indexid = indexid;
1734         node->indexqual = indexqual;
1735         node->indexqualorig = indexqualorig;
1736         node->indexstrategy = indexstrategy;
1737         node->indexsubtype = indexsubtype;
1738         node->indexorderdir = indexscandir;
1739
1740         return node;
1741 }
1742
1743 static BitmapIndexScan *
1744 make_bitmap_indexscan(Index scanrelid,
1745                                           Oid indexid,
1746                                           List *indexqual,
1747                                           List *indexqualorig,
1748                                           List *indexstrategy,
1749                                           List *indexsubtype)
1750 {
1751         BitmapIndexScan *node = makeNode(BitmapIndexScan);
1752         Plan       *plan = &node->scan.plan;
1753
1754         /* cost should be inserted by caller */
1755         plan->targetlist = NIL;         /* not used */
1756         plan->qual = NIL;                       /* not used */
1757         plan->lefttree = NULL;
1758         plan->righttree = NULL;
1759         node->scan.scanrelid = scanrelid;
1760         node->indexid = indexid;
1761         node->indexqual = indexqual;
1762         node->indexqualorig = indexqualorig;
1763         node->indexstrategy = indexstrategy;
1764         node->indexsubtype = indexsubtype;
1765
1766         return node;
1767 }
1768
1769 static BitmapHeapScan *
1770 make_bitmap_heapscan(List *qptlist,
1771                                          List *qpqual,
1772                                          Plan *lefttree,
1773                                          List *bitmapqualorig,
1774                                          Index scanrelid)
1775 {
1776         BitmapHeapScan *node = makeNode(BitmapHeapScan);
1777         Plan       *plan = &node->scan.plan;
1778
1779         /* cost should be inserted by caller */
1780         plan->targetlist = qptlist;
1781         plan->qual = qpqual;
1782         plan->lefttree = lefttree;
1783         plan->righttree = NULL;
1784         node->scan.scanrelid = scanrelid;
1785         node->bitmapqualorig = bitmapqualorig;
1786
1787         return node;
1788 }
1789
1790 static TidScan *
1791 make_tidscan(List *qptlist,
1792                          List *qpqual,
1793                          Index scanrelid,
1794                          List *tideval)
1795 {
1796         TidScan    *node = makeNode(TidScan);
1797         Plan       *plan = &node->scan.plan;
1798
1799         /* cost should be inserted by caller */
1800         plan->targetlist = qptlist;
1801         plan->qual = qpqual;
1802         plan->lefttree = NULL;
1803         plan->righttree = NULL;
1804         node->scan.scanrelid = scanrelid;
1805         node->tideval = tideval;
1806
1807         return node;
1808 }
1809
1810 SubqueryScan *
1811 make_subqueryscan(List *qptlist,
1812                                   List *qpqual,
1813                                   Index scanrelid,
1814                                   Plan *subplan)
1815 {
1816         SubqueryScan *node = makeNode(SubqueryScan);
1817         Plan       *plan = &node->scan.plan;
1818
1819         /*
1820          * Cost is figured here for the convenience of prepunion.c.  Note this
1821          * is only correct for the case where qpqual is empty; otherwise
1822          * caller should overwrite cost with a better estimate.
1823          */
1824         copy_plan_costsize(plan, subplan);
1825         plan->total_cost += cpu_tuple_cost * subplan->plan_rows;
1826
1827         plan->targetlist = qptlist;
1828         plan->qual = qpqual;
1829         plan->lefttree = NULL;
1830         plan->righttree = NULL;
1831         node->scan.scanrelid = scanrelid;
1832         node->subplan = subplan;
1833
1834         return node;
1835 }
1836
1837 static FunctionScan *
1838 make_functionscan(List *qptlist,
1839                                   List *qpqual,
1840                                   Index scanrelid)
1841 {
1842         FunctionScan *node = makeNode(FunctionScan);
1843         Plan       *plan = &node->scan.plan;
1844
1845         /* cost should be inserted by caller */
1846         plan->targetlist = qptlist;
1847         plan->qual = qpqual;
1848         plan->lefttree = NULL;
1849         plan->righttree = NULL;
1850         node->scan.scanrelid = scanrelid;
1851
1852         return node;
1853 }
1854
1855 Append *
1856 make_append(List *appendplans, bool isTarget, List *tlist)
1857 {
1858         Append     *node = makeNode(Append);
1859         Plan       *plan = &node->plan;
1860         ListCell   *subnode;
1861
1862         /*
1863          * Compute cost as sum of subplan costs.  We charge nothing extra for
1864          * the Append itself, which perhaps is too optimistic, but since it
1865          * doesn't do any selection or projection, it is a pretty cheap node.
1866          */
1867         plan->startup_cost = 0;
1868         plan->total_cost = 0;
1869         plan->plan_rows = 0;
1870         plan->plan_width = 0;
1871         foreach(subnode, appendplans)
1872         {
1873                 Plan       *subplan = (Plan *) lfirst(subnode);
1874
1875                 if (subnode == list_head(appendplans))  /* first node? */
1876                         plan->startup_cost = subplan->startup_cost;
1877                 plan->total_cost += subplan->total_cost;
1878                 plan->plan_rows += subplan->plan_rows;
1879                 if (plan->plan_width < subplan->plan_width)
1880                         plan->plan_width = subplan->plan_width;
1881         }
1882
1883         plan->targetlist = tlist;
1884         plan->qual = NIL;
1885         plan->lefttree = NULL;
1886         plan->righttree = NULL;
1887         node->appendplans = appendplans;
1888         node->isTarget = isTarget;
1889
1890         return node;
1891 }
1892
1893 static BitmapAnd *
1894 make_bitmap_and(List *bitmapplans)
1895 {
1896         BitmapAnd  *node = makeNode(BitmapAnd);
1897         Plan       *plan = &node->plan;
1898
1899         /* cost should be inserted by caller */
1900         plan->targetlist = NIL;
1901         plan->qual = NIL;
1902         plan->lefttree = NULL;
1903         plan->righttree = NULL;
1904         node->bitmapplans = bitmapplans;
1905
1906         return node;
1907 }
1908
1909 static BitmapOr *
1910 make_bitmap_or(List *bitmapplans)
1911 {
1912         BitmapOr   *node = makeNode(BitmapOr);
1913         Plan       *plan = &node->plan;
1914
1915         /* cost should be inserted by caller */
1916         plan->targetlist = NIL;
1917         plan->qual = NIL;
1918         plan->lefttree = NULL;
1919         plan->righttree = NULL;
1920         node->bitmapplans = bitmapplans;
1921
1922         return node;
1923 }
1924
1925 static NestLoop *
1926 make_nestloop(List *tlist,
1927                           List *joinclauses,
1928                           List *otherclauses,
1929                           Plan *lefttree,
1930                           Plan *righttree,
1931                           JoinType jointype)
1932 {
1933         NestLoop   *node = makeNode(NestLoop);
1934         Plan       *plan = &node->join.plan;
1935
1936         /* cost should be inserted by caller */
1937         plan->targetlist = tlist;
1938         plan->qual = otherclauses;
1939         plan->lefttree = lefttree;
1940         plan->righttree = righttree;
1941         node->join.jointype = jointype;
1942         node->join.joinqual = joinclauses;
1943
1944         return node;
1945 }
1946
1947 static HashJoin *
1948 make_hashjoin(List *tlist,
1949                           List *joinclauses,
1950                           List *otherclauses,
1951                           List *hashclauses,
1952                           Plan *lefttree,
1953                           Plan *righttree,
1954                           JoinType jointype)
1955 {
1956         HashJoin   *node = makeNode(HashJoin);
1957         Plan       *plan = &node->join.plan;
1958
1959         /* cost should be inserted by caller */
1960         plan->targetlist = tlist;
1961         plan->qual = otherclauses;
1962         plan->lefttree = lefttree;
1963         plan->righttree = righttree;
1964         node->hashclauses = hashclauses;
1965         node->join.jointype = jointype;
1966         node->join.joinqual = joinclauses;
1967
1968         return node;
1969 }
1970
1971 static Hash *
1972 make_hash(Plan *lefttree)
1973 {
1974         Hash       *node = makeNode(Hash);
1975         Plan       *plan = &node->plan;
1976
1977         copy_plan_costsize(plan, lefttree);
1978
1979         /*
1980          * For plausibility, make startup & total costs equal total cost of
1981          * input plan; this only affects EXPLAIN display not decisions.
1982          */
1983         plan->startup_cost = plan->total_cost;
1984         plan->targetlist = copyObject(lefttree->targetlist);
1985         plan->qual = NIL;
1986         plan->lefttree = lefttree;
1987         plan->righttree = NULL;
1988
1989         return node;
1990 }
1991
1992 static MergeJoin *
1993 make_mergejoin(List *tlist,
1994                            List *joinclauses,
1995                            List *otherclauses,
1996                            List *mergeclauses,
1997                            Plan *lefttree,
1998                            Plan *righttree,
1999                            JoinType jointype)
2000 {
2001         MergeJoin  *node = makeNode(MergeJoin);
2002         Plan       *plan = &node->join.plan;
2003
2004         /* cost should be inserted by caller */
2005         plan->targetlist = tlist;
2006         plan->qual = otherclauses;
2007         plan->lefttree = lefttree;
2008         plan->righttree = righttree;
2009         node->mergeclauses = mergeclauses;
2010         node->join.jointype = jointype;
2011         node->join.joinqual = joinclauses;
2012
2013         return node;
2014 }
2015
2016 /*
2017  * make_sort --- basic routine to build a Sort plan node
2018  *
2019  * Caller must have built the sortColIdx and sortOperators arrays already.
2020  */
2021 static Sort *
2022 make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
2023                   AttrNumber *sortColIdx, Oid *sortOperators)
2024 {
2025         Sort       *node = makeNode(Sort);
2026         Plan       *plan = &node->plan;
2027         Path            sort_path;              /* dummy for result of cost_sort */
2028
2029         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2030         cost_sort(&sort_path, root, NIL,
2031                           lefttree->total_cost,
2032                           lefttree->plan_rows,
2033                           lefttree->plan_width);
2034         plan->startup_cost = sort_path.startup_cost;
2035         plan->total_cost = sort_path.total_cost;
2036         plan->targetlist = copyObject(lefttree->targetlist);
2037         plan->qual = NIL;
2038         plan->lefttree = lefttree;
2039         plan->righttree = NULL;
2040         node->numCols = numCols;
2041         node->sortColIdx = sortColIdx;
2042         node->sortOperators = sortOperators;
2043
2044         return node;
2045 }
2046
2047 /*
2048  * add_sort_column --- utility subroutine for building sort info arrays
2049  *
2050  * We need this routine because the same column might be selected more than
2051  * once as a sort key column; if so, the extra mentions are redundant.
2052  *
2053  * Caller is assumed to have allocated the arrays large enough for the
2054  * max possible number of columns.      Return value is the new column count.
2055  */
2056 static int
2057 add_sort_column(AttrNumber colIdx, Oid sortOp,
2058                                 int numCols, AttrNumber *sortColIdx, Oid *sortOperators)
2059 {
2060         int                     i;
2061
2062         for (i = 0; i < numCols; i++)
2063         {
2064                 if (sortColIdx[i] == colIdx)
2065                 {
2066                         /* Already sorting by this col, so extra sort key is useless */
2067                         return numCols;
2068                 }
2069         }
2070
2071         /* Add the column */
2072         sortColIdx[numCols] = colIdx;
2073         sortOperators[numCols] = sortOp;
2074         return numCols + 1;
2075 }
2076
2077 /*
2078  * make_sort_from_pathkeys
2079  *        Create sort plan to sort according to given pathkeys
2080  *
2081  *        'lefttree' is the node which yields input tuples
2082  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
2083  *
2084  * We must convert the pathkey information into arrays of sort key column
2085  * numbers and sort operator OIDs.
2086  *
2087  * If the pathkeys include expressions that aren't simple Vars, we will
2088  * usually need to add resjunk items to the input plan's targetlist to
2089  * compute these expressions (since the Sort node itself won't do it).
2090  * If the input plan type isn't one that can do projections, this means
2091  * adding a Result node just to do the projection.
2092  */
2093 static Sort *
2094 make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
2095 {
2096         List       *tlist = lefttree->targetlist;
2097         ListCell   *i;
2098         int                     numsortkeys;
2099         AttrNumber *sortColIdx;
2100         Oid                *sortOperators;
2101
2102         /*
2103          * We will need at most list_length(pathkeys) sort columns; possibly
2104          * less
2105          */
2106         numsortkeys = list_length(pathkeys);
2107         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2108         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2109
2110         numsortkeys = 0;
2111
2112         foreach(i, pathkeys)
2113         {
2114                 List       *keysublist = (List *) lfirst(i);
2115                 PathKeyItem *pathkey = NULL;
2116                 TargetEntry *tle = NULL;
2117                 ListCell   *j;
2118
2119                 /*
2120                  * We can sort by any one of the sort key items listed in this
2121                  * sublist.  For now, we take the first one that corresponds to an
2122                  * available Var in the tlist.  If there isn't any, use the first
2123                  * one that is an expression in the input's vars.
2124                  *
2125                  * XXX if we have a choice, is there any way of figuring out which
2126                  * might be cheapest to execute?  (For example, int4lt is likely
2127                  * much cheaper to execute than numericlt, but both might appear
2128                  * in the same pathkey sublist...)      Not clear that we ever will
2129                  * have a choice in practice, so it may not matter.
2130                  */
2131                 foreach(j, keysublist)
2132                 {
2133                         pathkey = (PathKeyItem *) lfirst(j);
2134                         Assert(IsA(pathkey, PathKeyItem));
2135                         tle = tlist_member(pathkey->key, tlist);
2136                         if (tle)
2137                                 break;
2138                 }
2139                 if (!tle)
2140                 {
2141                         /* No matching Var; look for a computable expression */
2142                         foreach(j, keysublist)
2143                         {
2144                                 List       *exprvars;
2145                                 ListCell   *k;
2146
2147                                 pathkey = (PathKeyItem *) lfirst(j);
2148                                 exprvars = pull_var_clause(pathkey->key, false);
2149                                 foreach(k, exprvars)
2150                                 {
2151                                         if (!tlist_member(lfirst(k), tlist))
2152                                                 break;
2153                                 }
2154                                 list_free(exprvars);
2155                                 if (!k)
2156                                         break;          /* found usable expression */
2157                         }
2158                         if (!j)
2159                                 elog(ERROR, "could not find pathkey item to sort");
2160
2161                         /*
2162                          * Do we need to insert a Result node?
2163                          */
2164                         if (!is_projection_capable_plan(lefttree))
2165                         {
2166                                 tlist = copyObject(tlist);
2167                                 lefttree = (Plan *) make_result(tlist, NULL, lefttree);
2168                         }
2169
2170                         /*
2171                          * Add resjunk entry to input's tlist
2172                          */
2173                         tle = makeTargetEntry((Expr *) pathkey->key,
2174                                                                   list_length(tlist) + 1,
2175                                                                   NULL,
2176                                                                   true);
2177                         tlist = lappend(tlist, tle);
2178                         lefttree->targetlist = tlist;           /* just in case NIL before */
2179                 }
2180
2181                 /*
2182                  * The column might already be selected as a sort key, if the
2183                  * pathkeys contain duplicate entries.  (This can happen in
2184                  * scenarios where multiple mergejoinable clauses mention the same
2185                  * var, for example.)  So enter it only once in the sort arrays.
2186                  */
2187                 numsortkeys = add_sort_column(tle->resno, pathkey->sortop,
2188                                                                  numsortkeys, sortColIdx, sortOperators);
2189         }
2190
2191         Assert(numsortkeys > 0);
2192
2193         return make_sort(root, lefttree, numsortkeys,
2194                                          sortColIdx, sortOperators);
2195 }
2196
2197 /*
2198  * make_sort_from_sortclauses
2199  *        Create sort plan to sort according to given sortclauses
2200  *
2201  *        'sortcls' is a list of SortClauses
2202  *        'lefttree' is the node which yields input tuples
2203  */
2204 Sort *
2205 make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
2206 {
2207         List       *sub_tlist = lefttree->targetlist;
2208         ListCell   *l;
2209         int                     numsortkeys;
2210         AttrNumber *sortColIdx;
2211         Oid                *sortOperators;
2212
2213         /*
2214          * We will need at most list_length(sortcls) sort columns; possibly
2215          * less
2216          */
2217         numsortkeys = list_length(sortcls);
2218         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2219         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2220
2221         numsortkeys = 0;
2222
2223         foreach(l, sortcls)
2224         {
2225                 SortClause *sortcl = (SortClause *) lfirst(l);
2226                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
2227
2228                 /*
2229                  * Check for the possibility of duplicate order-by clauses --- the
2230                  * parser should have removed 'em, but no point in sorting
2231                  * redundantly.
2232                  */
2233                 numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
2234                                                                  numsortkeys, sortColIdx, sortOperators);
2235         }
2236
2237         Assert(numsortkeys > 0);
2238
2239         return make_sort(root, lefttree, numsortkeys,
2240                                          sortColIdx, sortOperators);
2241 }
2242
2243 /*
2244  * make_sort_from_groupcols
2245  *        Create sort plan to sort based on grouping columns
2246  *
2247  * 'groupcls' is the list of GroupClauses
2248  * 'grpColIdx' gives the column numbers to use
2249  *
2250  * This might look like it could be merged with make_sort_from_sortclauses,
2251  * but presently we *must* use the grpColIdx[] array to locate sort columns,
2252  * because the child plan's tlist is not marked with ressortgroupref info
2253  * appropriate to the grouping node.  So, only the sortop is used from the
2254  * GroupClause entries.
2255  */
2256 Sort *
2257 make_sort_from_groupcols(PlannerInfo *root,
2258                                                  List *groupcls,
2259                                                  AttrNumber *grpColIdx,
2260                                                  Plan *lefttree)
2261 {
2262         List       *sub_tlist = lefttree->targetlist;
2263         int                     grpno = 0;
2264         ListCell   *l;
2265         int                     numsortkeys;
2266         AttrNumber *sortColIdx;
2267         Oid                *sortOperators;
2268
2269         /*
2270          * We will need at most list_length(groupcls) sort columns; possibly
2271          * less
2272          */
2273         numsortkeys = list_length(groupcls);
2274         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2275         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2276
2277         numsortkeys = 0;
2278
2279         foreach(l, groupcls)
2280         {
2281                 GroupClause *grpcl = (GroupClause *) lfirst(l);
2282                 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
2283
2284                 /*
2285                  * Check for the possibility of duplicate group-by clauses --- the
2286                  * parser should have removed 'em, but no point in sorting
2287                  * redundantly.
2288                  */
2289                 numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
2290                                                                  numsortkeys, sortColIdx, sortOperators);
2291                 grpno++;
2292         }
2293
2294         Assert(numsortkeys > 0);
2295
2296         return make_sort(root, lefttree, numsortkeys,
2297                                          sortColIdx, sortOperators);
2298 }
2299
2300 Material *
2301 make_material(Plan *lefttree)
2302 {
2303         Material   *node = makeNode(Material);
2304         Plan       *plan = &node->plan;
2305
2306         /* cost should be inserted by caller */
2307         plan->targetlist = copyObject(lefttree->targetlist);
2308         plan->qual = NIL;
2309         plan->lefttree = lefttree;
2310         plan->righttree = NULL;
2311
2312         return node;
2313 }
2314
2315 /*
2316  * materialize_finished_plan: stick a Material node atop a completed plan
2317  *
2318  * There are a couple of places where we want to attach a Material node
2319  * after completion of subquery_planner().      This currently requires hackery.
2320  * Since subquery_planner has already run SS_finalize_plan on the subplan
2321  * tree, we have to kluge up parameter lists for the Material node.
2322  * Possibly this could be fixed by postponing SS_finalize_plan processing
2323  * until setrefs.c is run?
2324  */
2325 Plan *
2326 materialize_finished_plan(Plan *subplan)
2327 {
2328         Plan       *matplan;
2329         Path            matpath;                /* dummy for result of cost_material */
2330
2331         matplan = (Plan *) make_material(subplan);
2332
2333         /* Set cost data */
2334         cost_material(&matpath,
2335                                   subplan->total_cost,
2336                                   subplan->plan_rows,
2337                                   subplan->plan_width);
2338         matplan->startup_cost = matpath.startup_cost;
2339         matplan->total_cost = matpath.total_cost;
2340         matplan->plan_rows = subplan->plan_rows;
2341         matplan->plan_width = subplan->plan_width;
2342
2343         /* parameter kluge --- see comments above */
2344         matplan->extParam = bms_copy(subplan->extParam);
2345         matplan->allParam = bms_copy(subplan->allParam);
2346
2347         return matplan;
2348 }
2349
2350 Agg *
2351 make_agg(PlannerInfo *root, List *tlist, List *qual,
2352                  AggStrategy aggstrategy,
2353                  int numGroupCols, AttrNumber *grpColIdx,
2354                  long numGroups, int numAggs,
2355                  Plan *lefttree)
2356 {
2357         Agg                *node = makeNode(Agg);
2358         Plan       *plan = &node->plan;
2359         Path            agg_path;               /* dummy for result of cost_agg */
2360         QualCost        qual_cost;
2361
2362         node->aggstrategy = aggstrategy;
2363         node->numCols = numGroupCols;
2364         node->grpColIdx = grpColIdx;
2365         node->numGroups = numGroups;
2366
2367         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2368         cost_agg(&agg_path, root,
2369                          aggstrategy, numAggs,
2370                          numGroupCols, numGroups,
2371                          lefttree->startup_cost,
2372                          lefttree->total_cost,
2373                          lefttree->plan_rows);
2374         plan->startup_cost = agg_path.startup_cost;
2375         plan->total_cost = agg_path.total_cost;
2376
2377         /*
2378          * We will produce a single output tuple if not grouping, and a tuple
2379          * per group otherwise.
2380          */
2381         if (aggstrategy == AGG_PLAIN)
2382                 plan->plan_rows = 1;
2383         else
2384                 plan->plan_rows = numGroups;
2385
2386         /*
2387          * We also need to account for the cost of evaluation of the qual (ie,
2388          * the HAVING clause) and the tlist.  Note that cost_qual_eval doesn't
2389          * charge anything for Aggref nodes; this is okay since they are
2390          * really comparable to Vars.
2391          *
2392          * See notes in grouping_planner about why this routine and make_group
2393          * are the only ones in this file that worry about tlist eval cost.
2394          */
2395         if (qual)
2396         {
2397                 cost_qual_eval(&qual_cost, qual);
2398                 plan->startup_cost += qual_cost.startup;
2399                 plan->total_cost += qual_cost.startup;
2400                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2401         }
2402         cost_qual_eval(&qual_cost, tlist);
2403         plan->startup_cost += qual_cost.startup;
2404         plan->total_cost += qual_cost.startup;
2405         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2406
2407         plan->qual = qual;
2408         plan->targetlist = tlist;
2409         plan->lefttree = lefttree;
2410         plan->righttree = NULL;
2411
2412         return node;
2413 }
2414
2415 Group *
2416 make_group(PlannerInfo *root,
2417                    List *tlist,
2418                    List *qual,
2419                    int numGroupCols,
2420                    AttrNumber *grpColIdx,
2421                    double numGroups,
2422                    Plan *lefttree)
2423 {
2424         Group      *node = makeNode(Group);
2425         Plan       *plan = &node->plan;
2426         Path            group_path;             /* dummy for result of cost_group */
2427         QualCost        qual_cost;
2428
2429         node->numCols = numGroupCols;
2430         node->grpColIdx = grpColIdx;
2431
2432         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2433         cost_group(&group_path, root,
2434                            numGroupCols, numGroups,
2435                            lefttree->startup_cost,
2436                            lefttree->total_cost,
2437                            lefttree->plan_rows);
2438         plan->startup_cost = group_path.startup_cost;
2439         plan->total_cost = group_path.total_cost;
2440
2441         /* One output tuple per estimated result group */
2442         plan->plan_rows = numGroups;
2443
2444         /*
2445          * We also need to account for the cost of evaluation of the qual (ie,
2446          * the HAVING clause) and the tlist.
2447          *
2448          * XXX this double-counts the cost of evaluation of any expressions used
2449          * for grouping, since in reality those will have been evaluated at a
2450          * lower plan level and will only be copied by the Group node. Worth
2451          * fixing?
2452          *
2453          * See notes in grouping_planner about why this routine and make_agg are
2454          * the only ones in this file that worry about tlist eval cost.
2455          */
2456         if (qual)
2457         {
2458                 cost_qual_eval(&qual_cost, qual);
2459                 plan->startup_cost += qual_cost.startup;
2460                 plan->total_cost += qual_cost.startup;
2461                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2462         }
2463         cost_qual_eval(&qual_cost, tlist);
2464         plan->startup_cost += qual_cost.startup;
2465         plan->total_cost += qual_cost.startup;
2466         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2467
2468         plan->qual = qual;
2469         plan->targetlist = tlist;
2470         plan->lefttree = lefttree;
2471         plan->righttree = NULL;
2472
2473         return node;
2474 }
2475
2476 /*
2477  * distinctList is a list of SortClauses, identifying the targetlist items
2478  * that should be considered by the Unique filter.
2479  */
2480 Unique *
2481 make_unique(Plan *lefttree, List *distinctList)
2482 {
2483         Unique     *node = makeNode(Unique);
2484         Plan       *plan = &node->plan;
2485         int                     numCols = list_length(distinctList);
2486         int                     keyno = 0;
2487         AttrNumber *uniqColIdx;
2488         ListCell   *slitem;
2489
2490         copy_plan_costsize(plan, lefttree);
2491
2492         /*
2493          * Charge one cpu_operator_cost per comparison per input tuple. We
2494          * assume all columns get compared at most of the tuples.  (XXX
2495          * probably this is an overestimate.)
2496          */
2497         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
2498
2499         /*
2500          * plan->plan_rows is left as a copy of the input subplan's plan_rows;
2501          * ie, we assume the filter removes nothing.  The caller must alter
2502          * this if he has a better idea.
2503          */
2504
2505         plan->targetlist = copyObject(lefttree->targetlist);
2506         plan->qual = NIL;
2507         plan->lefttree = lefttree;
2508         plan->righttree = NULL;
2509
2510         /*
2511          * convert SortClause list into array of attr indexes, as wanted by
2512          * exec
2513          */
2514         Assert(numCols > 0);
2515         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2516
2517         foreach(slitem, distinctList)
2518         {
2519                 SortClause *sortcl = (SortClause *) lfirst(slitem);
2520                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
2521
2522                 uniqColIdx[keyno++] = tle->resno;
2523         }
2524
2525         node->numCols = numCols;
2526         node->uniqColIdx = uniqColIdx;
2527
2528         return node;
2529 }
2530
2531 /*
2532  * distinctList is a list of SortClauses, identifying the targetlist items
2533  * that should be considered by the SetOp filter.
2534  */
2535
2536 SetOp *
2537 make_setop(SetOpCmd cmd, Plan *lefttree,
2538                    List *distinctList, AttrNumber flagColIdx)
2539 {
2540         SetOp      *node = makeNode(SetOp);
2541         Plan       *plan = &node->plan;
2542         int                     numCols = list_length(distinctList);
2543         int                     keyno = 0;
2544         AttrNumber *dupColIdx;
2545         ListCell   *slitem;
2546
2547         copy_plan_costsize(plan, lefttree);
2548
2549         /*
2550          * Charge one cpu_operator_cost per comparison per input tuple. We
2551          * assume all columns get compared at most of the tuples.
2552          */
2553         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
2554
2555         /*
2556          * We make the unsupported assumption that there will be 10% as many
2557          * tuples out as in.  Any way to do better?
2558          */
2559         plan->plan_rows *= 0.1;
2560         if (plan->plan_rows < 1)
2561                 plan->plan_rows = 1;
2562
2563         plan->targetlist = copyObject(lefttree->targetlist);
2564         plan->qual = NIL;
2565         plan->lefttree = lefttree;
2566         plan->righttree = NULL;
2567
2568         /*
2569          * convert SortClause list into array of attr indexes, as wanted by
2570          * exec
2571          */
2572         Assert(numCols > 0);
2573         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2574
2575         foreach(slitem, distinctList)
2576         {
2577                 SortClause *sortcl = (SortClause *) lfirst(slitem);
2578                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
2579
2580                 dupColIdx[keyno++] = tle->resno;
2581         }
2582
2583         node->cmd = cmd;
2584         node->numCols = numCols;
2585         node->dupColIdx = dupColIdx;
2586         node->flagColIdx = flagColIdx;
2587
2588         return node;
2589 }
2590
2591 Limit *
2592 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount)
2593 {
2594         Limit      *node = makeNode(Limit);
2595         Plan       *plan = &node->plan;
2596
2597         copy_plan_costsize(plan, lefttree);
2598
2599         /*
2600          * If offset/count are constants, adjust the output rows count and
2601          * costs accordingly.  This is only a cosmetic issue if we are at top
2602          * level, but if we are building a subquery then it's important to
2603          * report correct info to the outer planner.
2604          */
2605         if (limitOffset && IsA(limitOffset, Const))
2606         {
2607                 Const      *limito = (Const *) limitOffset;
2608                 int32           offset = DatumGetInt32(limito->constvalue);
2609
2610                 if (!limito->constisnull && offset > 0)
2611                 {
2612                         if (offset > plan->plan_rows)
2613                                 offset = (int32) plan->plan_rows;
2614                         if (plan->plan_rows > 0)
2615                                 plan->startup_cost +=
2616                                         (plan->total_cost - plan->startup_cost)
2617                                         * ((double) offset) / plan->plan_rows;
2618                         plan->plan_rows -= offset;
2619                         if (plan->plan_rows < 1)
2620                                 plan->plan_rows = 1;
2621                 }
2622         }
2623         if (limitCount && IsA(limitCount, Const))
2624         {
2625                 Const      *limitc = (Const *) limitCount;
2626                 int32           count = DatumGetInt32(limitc->constvalue);
2627
2628                 if (!limitc->constisnull && count >= 0)
2629                 {
2630                         if (count > plan->plan_rows)
2631                                 count = (int32) plan->plan_rows;
2632                         if (plan->plan_rows > 0)
2633                                 plan->total_cost = plan->startup_cost +
2634                                         (plan->total_cost - plan->startup_cost)
2635                                         * ((double) count) / plan->plan_rows;
2636                         plan->plan_rows = count;
2637                         if (plan->plan_rows < 1)
2638                                 plan->plan_rows = 1;
2639                 }
2640         }
2641
2642         plan->targetlist = copyObject(lefttree->targetlist);
2643         plan->qual = NIL;
2644         plan->lefttree = lefttree;
2645         plan->righttree = NULL;
2646
2647         node->limitOffset = limitOffset;
2648         node->limitCount = limitCount;
2649
2650         return node;
2651 }
2652
2653 Result *
2654 make_result(List *tlist,
2655                         Node *resconstantqual,
2656                         Plan *subplan)
2657 {
2658         Result     *node = makeNode(Result);
2659         Plan       *plan = &node->plan;
2660
2661         if (subplan)
2662                 copy_plan_costsize(plan, subplan);
2663         else
2664         {
2665                 plan->startup_cost = 0;
2666                 plan->total_cost = cpu_tuple_cost;
2667                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
2668                 plan->plan_width = 0;   /* XXX try to be smarter? */
2669         }
2670
2671         if (resconstantqual)
2672         {
2673                 QualCost        qual_cost;
2674
2675                 cost_qual_eval(&qual_cost, (List *) resconstantqual);
2676                 /* resconstantqual is evaluated once at startup */
2677                 plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
2678                 plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
2679         }
2680
2681         plan->targetlist = tlist;
2682         plan->qual = NIL;
2683         plan->lefttree = subplan;
2684         plan->righttree = NULL;
2685         node->resconstantqual = resconstantqual;
2686
2687         return node;
2688 }
2689
2690 /*
2691  * is_projection_capable_plan
2692  *              Check whether a given Plan node is able to do projection.
2693  */
2694 bool
2695 is_projection_capable_plan(Plan *plan)
2696 {
2697         /* Most plan types can project, so just list the ones that can't */
2698         switch (nodeTag(plan))
2699         {
2700                 case T_Hash:
2701                 case T_Material:
2702                 case T_Sort:
2703                 case T_Unique:
2704                 case T_SetOp:
2705                 case T_Limit:
2706                 case T_Append:
2707                         return false;
2708                 default:
2709                         break;
2710         }
2711         return true;
2712 }