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-2012, PostgreSQL Global Development Group
   9  * Portions Copyright (c) 1994, Regents of the University of California
  10  *
  11  *
  12  * IDENTIFICATION
  13  *        src/backend/optimizer/plan/createplan.c
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #include "postgres.h"
  18
  19 #include <limits.h>
  20 #include <math.h>
  21
  22 #include "access/skey.h"
  23 #include "foreign/fdwapi.h"
  24 #include "miscadmin.h"
  25 #include "nodes/makefuncs.h"
  26 #include "nodes/nodeFuncs.h"
  27 #include "optimizer/clauses.h"
  28 #include "optimizer/cost.h"
  29 #include "optimizer/paths.h"
  30 #include "optimizer/placeholder.h"
  31 #include "optimizer/plancat.h"
  32 #include "optimizer/planmain.h"
  33 #include "optimizer/predtest.h"
  34 #include "optimizer/restrictinfo.h"
  35 #include "optimizer/subselect.h"
  36 #include "optimizer/tlist.h"
  37 #include "optimizer/var.h"
  38 #include "parser/parse_clause.h"
  39 #include "parser/parsetree.h"
  40 #include "utils/lsyscache.h"
  41
  42
  43 static Plan *create_plan_recurse(PlannerInfo *root, Path *best_path);
  44 static Plan *create_scan_plan(PlannerInfo *root, Path *best_path);
  45 static List *build_relation_tlist(RelOptInfo *rel);
  46 static bool use_physical_tlist(PlannerInfo *root, RelOptInfo *rel);
  47 static void disuse_physical_tlist(Plan *plan, Path *path);
  48 static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals);
  49 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
  50 static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
  51 static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path);
  52 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
  53 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
  54 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
  55 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
  56                                         List *tlist, List *scan_clauses);
  57 static Scan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
  58                                           List *tlist, List *scan_clauses, bool indexonly);
  59 static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
  60                                                 BitmapHeapPath *best_path,
  61                                                 List *tlist, List *scan_clauses);
  62 static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
  63                                           List **qual, List **indexqual);
  64 static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
  65                                         List *tlist, List *scan_clauses);
  66 static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
  67                                                  List *tlist, List *scan_clauses);
  68 static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
  69                                                  List *tlist, List *scan_clauses);
  70 static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
  71                                            List *tlist, List *scan_clauses);
  72 static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path,
  73                                         List *tlist, List *scan_clauses);
  74 static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path,
  75                                                   List *tlist, List *scan_clauses);
  76 static ForeignScan *create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
  77                                                 List *tlist, List *scan_clauses);
  78 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
  79                                          Plan *outer_plan, Plan *inner_plan);
  80 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
  81                                           Plan *outer_plan, Plan *inner_plan);
  82 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
  83                                          Plan *outer_plan, Plan *inner_plan);
  84 static Node *replace_nestloop_params(PlannerInfo *root, Node *expr);
  85 static Node *replace_nestloop_params_mutator(Node *node, PlannerInfo *root);
  86 static List *fix_indexqual_references(PlannerInfo *root, IndexPath *index_path);
  87 static List *fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path);
  88 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol);
  89 static List *get_switched_clauses(List *clauses, Relids outerrelids);
  90 static List *order_qual_clauses(PlannerInfo *root, List *clauses);
  91 static void copy_path_costsize(Plan *dest, Path *src);
  92 static void copy_plan_costsize(Plan *dest, Plan *src);
  93 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
  94 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
  95                            Oid indexid, List *indexqual, List *indexqualorig,
  96                            List *indexorderby, List *indexorderbyorig,
  97                            ScanDirection indexscandir);
  98 static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual,
  99                                    Index scanrelid, Oid indexid,
 100                                    List *indexqual, List *indexorderby,
 101                                    List *indextlist,
 102                                    ScanDirection indexscandir);
 103 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
 104                                           List *indexqual,
 105                                           List *indexqualorig);
 106 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
 107                                          List *qpqual,
 108                                          Plan *lefttree,
 109                                          List *bitmapqualorig,
 110                                          Index scanrelid);
 111 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
 112                          List *tidquals);
 113 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
 114                                   Index scanrelid, Node *funcexpr, List *funccolnames,
 115                                   List *funccoltypes, List *funccoltypmods,
 116                                   List *funccolcollations);
 117 static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
 118                                 Index scanrelid, List *values_lists);
 119 static CteScan *make_ctescan(List *qptlist, List *qpqual,
 120                          Index scanrelid, int ctePlanId, int cteParam);
 121 static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
 122                                    Index scanrelid, int wtParam);
 123 static ForeignScan *make_foreignscan(List *qptlist, List *qpqual,
 124                                  Index scanrelid, bool fsSystemCol, FdwPlan *fdwplan);
 125 static BitmapAnd *make_bitmap_and(List *bitmapplans);
 126 static BitmapOr *make_bitmap_or(List *bitmapplans);
 127 static NestLoop *make_nestloop(List *tlist,
 128                           List *joinclauses, List *otherclauses, List *nestParams,
 129                           Plan *lefttree, Plan *righttree,
 130                           JoinType jointype);
 131 static HashJoin *make_hashjoin(List *tlist,
 132                           List *joinclauses, List *otherclauses,
 133                           List *hashclauses,
 134                           Plan *lefttree, Plan *righttree,
 135                           JoinType jointype);
 136 static Hash *make_hash(Plan *lefttree,
 137                   Oid skewTable,
 138                   AttrNumber skewColumn,
 139                   bool skewInherit,
 140                   Oid skewColType,
 141                   int32 skewColTypmod);
 142 static MergeJoin *make_mergejoin(List *tlist,
 143                            List *joinclauses, List *otherclauses,
 144                            List *mergeclauses,
 145                            Oid *mergefamilies,
 146                            Oid *mergecollations,
 147                            int *mergestrategies,
 148                            bool *mergenullsfirst,
 149                            Plan *lefttree, Plan *righttree,
 150                            JoinType jointype);
 151 static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
 152                   AttrNumber *sortColIdx, Oid *sortOperators,
 153                   Oid *collations, bool *nullsFirst,
 154                   double limit_tuples);
 155 static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
 156                                                    Plan *lefttree, List *pathkeys,
 157                                                    bool adjust_tlist_in_place,
 158                                                    int *p_numsortkeys,
 159                                                    AttrNumber **p_sortColIdx,
 160                                                    Oid **p_sortOperators,
 161                                                    Oid **p_collations,
 162                                                    bool **p_nullsFirst);
 163 static Material *make_material(Plan *lefttree);
 164
 165
 166 /*
 167  * create_plan
 168  *        Creates the access plan for a query by recursively processing the
 169  *        desired tree of pathnodes, starting at the node 'best_path'.  For
 170  *        every pathnode found, we create a corresponding plan node containing
 171  *        appropriate id, target list, and qualification information.
 172  *
 173  *        The tlists and quals in the plan tree are still in planner format,
 174  *        ie, Vars still correspond to the parser's numbering.  This will be
 175  *        fixed later by setrefs.c.
 176  *
 177  *        best_path is the best access path
 178  *
 179  *        Returns a Plan tree.
 180  */
 181 Plan *
 182 create_plan(PlannerInfo *root, Path *best_path)
 183 {
 184         Plan       *plan;
 185
 186         /* Initialize this module's private workspace in PlannerInfo */
 187         root->curOuterRels = NULL;
 188         root->curOuterParams = NIL;
 189
 190         /* Recursively process the path tree */
 191         plan = create_plan_recurse(root, best_path);
 192
 193         /* Check we successfully assigned all NestLoopParams to plan nodes */
 194         if (root->curOuterParams != NIL)
 195                 elog(ERROR, "failed to assign all NestLoopParams to plan nodes");
 196
 197         return plan;
 198 }
 199
 200 /*
 201  * create_plan_recurse
 202  *        Recursive guts of create_plan().
 203  */
 204 static Plan *
 205 create_plan_recurse(PlannerInfo *root, Path *best_path)
 206 {
 207         Plan       *plan;
 208
 209         switch (best_path->pathtype)
 210         {
 211                 case T_SeqScan:
 212                 case T_IndexScan:
 213                 case T_IndexOnlyScan:
 214                 case T_BitmapHeapScan:
 215                 case T_TidScan:
 216                 case T_SubqueryScan:
 217                 case T_FunctionScan:
 218                 case T_ValuesScan:
 219                 case T_CteScan:
 220                 case T_WorkTableScan:
 221                 case T_ForeignScan:
 222                         plan = create_scan_plan(root, best_path);
 223                         break;
 224                 case T_HashJoin:
 225                 case T_MergeJoin:
 226                 case T_NestLoop:
 227                         plan = create_join_plan(root,
 228                                                                         (JoinPath *) best_path);
 229                         break;
 230                 case T_Append:
 231                         plan = create_append_plan(root,
 232                                                                           (AppendPath *) best_path);
 233                         break;
 234                 case T_MergeAppend:
 235                         plan = create_merge_append_plan(root,
 236                                                                                         (MergeAppendPath *) best_path);
 237                         break;
 238                 case T_Result:
 239                         plan = (Plan *) create_result_plan(root,
 240                                                                                            (ResultPath *) best_path);
 241                         break;
 242                 case T_Material:
 243                         plan = (Plan *) create_material_plan(root,
 244                                                                                                  (MaterialPath *) best_path);
 245                         break;
 246                 case T_Unique:
 247                         plan = create_unique_plan(root,
 248                                                                           (UniquePath *) best_path);
 249                         break;
 250                 default:
 251                         elog(ERROR, "unrecognized node type: %d",
 252                                  (int) best_path->pathtype);
 253                         plan = NULL;            /* keep compiler quiet */
 254                         break;
 255         }
 256
 257         return plan;
 258 }
 259
 260 /*
 261  * create_scan_plan
 262  *       Create a scan plan for the parent relation of 'best_path'.
 263  */
 264 static Plan *
 265 create_scan_plan(PlannerInfo *root, Path *best_path)
 266 {
 267         RelOptInfo *rel = best_path->parent;
 268         List       *tlist;
 269         List       *scan_clauses;
 270         Plan       *plan;
 271
 272         /*
 273          * For table scans, rather than using the relation targetlist (which is
 274          * only those Vars actually needed by the query), we prefer to generate a
 275          * tlist containing all Vars in order.  This will allow the executor to
 276          * optimize away projection of the table tuples, if possible.  (Note that
 277          * planner.c may replace the tlist we generate here, forcing projection to
 278          * occur.)
 279          */
 280         if (use_physical_tlist(root, rel))
 281         {
 282                 if (best_path->pathtype == T_IndexOnlyScan)
 283                 {
 284                         /* For index-only scan, the preferred tlist is the index's */
 285                         tlist = copyObject(((IndexPath *) best_path)->indexinfo->indextlist);
 286                 }
 287                 else
 288                 {
 289                         tlist = build_physical_tlist(root, rel);
 290                         /* if fail because of dropped cols, use regular method */
 291                         if (tlist == NIL)
 292                                 tlist = build_relation_tlist(rel);
 293                 }
 294         }
 295         else
 296                 tlist = build_relation_tlist(rel);
 297
 298         /*
 299          * Extract the relevant restriction clauses from the parent relation. The
 300          * executor must apply all these restrictions during the scan, except for
 301          * pseudoconstants which we'll take care of below.
 302          */
 303         scan_clauses = rel->baserestrictinfo;
 304
 305         switch (best_path->pathtype)
 306         {
 307                 case T_SeqScan:
 308                         plan = (Plan *) create_seqscan_plan(root,
 309                                                                                                 best_path,
 310                                                                                                 tlist,
 311                                                                                                 scan_clauses);
 312                         break;
 313
 314                 case T_IndexScan:
 315                         plan = (Plan *) create_indexscan_plan(root,
 316                                                                                                   (IndexPath *) best_path,
 317                                                                                                   tlist,
 318                                                                                                   scan_clauses,
 319                                                                                                   false);
 320                         break;
 321
 322                 case T_IndexOnlyScan:
 323                         plan = (Plan *) create_indexscan_plan(root,
 324                                                                                                   (IndexPath *) best_path,
 325                                                                                                   tlist,
 326                                                                                                   scan_clauses,
 327                                                                                                   true);
 328                         break;
 329
 330                 case T_BitmapHeapScan:
 331                         plan = (Plan *) create_bitmap_scan_plan(root,
 332                                                                                                 (BitmapHeapPath *) best_path,
 333                                                                                                         tlist,
 334                                                                                                         scan_clauses);
 335                         break;
 336
 337                 case T_TidScan:
 338                         plan = (Plan *) create_tidscan_plan(root,
 339                                                                                                 (TidPath *) best_path,
 340                                                                                                 tlist,
 341                                                                                                 scan_clauses);
 342                         break;
 343
 344                 case T_SubqueryScan:
 345                         plan = (Plan *) create_subqueryscan_plan(root,
 346                                                                                                          best_path,
 347                                                                                                          tlist,
 348                                                                                                          scan_clauses);
 349                         break;
 350
 351                 case T_FunctionScan:
 352                         plan = (Plan *) create_functionscan_plan(root,
 353                                                                                                          best_path,
 354                                                                                                          tlist,
 355                                                                                                          scan_clauses);
 356                         break;
 357
 358                 case T_ValuesScan:
 359                         plan = (Plan *) create_valuesscan_plan(root,
 360                                                                                                    best_path,
 361                                                                                                    tlist,
 362                                                                                                    scan_clauses);
 363                         break;
 364
 365                 case T_CteScan:
 366                         plan = (Plan *) create_ctescan_plan(root,
 367                                                                                                 best_path,
 368                                                                                                 tlist,
 369                                                                                                 scan_clauses);
 370                         break;
 371
 372                 case T_WorkTableScan:
 373                         plan = (Plan *) create_worktablescan_plan(root,
 374                                                                                                           best_path,
 375                                                                                                           tlist,
 376                                                                                                           scan_clauses);
 377                         break;
 378
 379                 case T_ForeignScan:
 380                         plan = (Plan *) create_foreignscan_plan(root,
 381                                                                                                         (ForeignPath *) best_path,
 382                                                                                                         tlist,
 383                                                                                                         scan_clauses);
 384                         break;
 385
 386                 default:
 387                         elog(ERROR, "unrecognized node type: %d",
 388                                  (int) best_path->pathtype);
 389                         plan = NULL;            /* keep compiler quiet */
 390                         break;
 391         }
 392
 393         /*
 394          * If there are any pseudoconstant clauses attached to this node, insert a
 395          * gating Result node that evaluates the pseudoconstants as one-time
 396          * quals.
 397          */
 398         if (root->hasPseudoConstantQuals)
 399                 plan = create_gating_plan(root, plan, scan_clauses);
 400
 401         return plan;
 402 }
 403
 404 /*
 405  * Build a target list (ie, a list of TargetEntry) for a relation.
 406  */
 407 static List *
 408 build_relation_tlist(RelOptInfo *rel)
 409 {
 410         List       *tlist = NIL;
 411         int                     resno = 1;
 412         ListCell   *v;
 413
 414         foreach(v, rel->reltargetlist)
 415         {
 416                 /* Do we really need to copy here?      Not sure */
 417                 Node       *node = (Node *) copyObject(lfirst(v));
 418
 419                 tlist = lappend(tlist, makeTargetEntry((Expr *) node,
 420                                                                                            resno,
 421                                                                                            NULL,
 422                                                                                            false));
 423                 resno++;
 424         }
 425         return tlist;
 426 }
 427
 428 /*
 429  * use_physical_tlist
 430  *              Decide whether to use a tlist matching relation structure,
 431  *              rather than only those Vars actually referenced.
 432  */
 433 static bool
 434 use_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
 435 {
 436         int                     i;
 437         ListCell   *lc;
 438
 439         /*
 440          * We can do this for real relation scans, subquery scans, function scans,
 441          * values scans, and CTE scans (but not for, eg, joins).
 442          */
 443         if (rel->rtekind != RTE_RELATION &&
 444                 rel->rtekind != RTE_SUBQUERY &&
 445                 rel->rtekind != RTE_FUNCTION &&
 446                 rel->rtekind != RTE_VALUES &&
 447                 rel->rtekind != RTE_CTE)
 448                 return false;
 449
 450         /*
 451          * Can't do it with inheritance cases either (mainly because Append
 452          * doesn't project).
 453          */
 454         if (rel->reloptkind != RELOPT_BASEREL)
 455                 return false;
 456
 457         /*
 458          * Can't do it if any system columns or whole-row Vars are requested.
 459          * (This could possibly be fixed but would take some fragile assumptions
 460          * in setrefs.c, I think.)
 461          */
 462         for (i = rel->min_attr; i <= 0; i++)
 463         {
 464                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
 465                         return false;
 466         }
 467
 468         /*
 469          * Can't do it if the rel is required to emit any placeholder expressions,
 470          * either.
 471          */
 472         foreach(lc, root->placeholder_list)
 473         {
 474                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 475
 476                 if (bms_nonempty_difference(phinfo->ph_needed, rel->relids) &&
 477                         bms_is_subset(phinfo->ph_eval_at, rel->relids))
 478                         return false;
 479         }
 480
 481         return true;
 482 }
 483
 484 /*
 485  * disuse_physical_tlist
 486  *              Switch a plan node back to emitting only Vars actually referenced.
 487  *
 488  * If the plan node immediately above a scan would prefer to get only
 489  * needed Vars and not a physical tlist, it must call this routine to
 490  * undo the decision made by use_physical_tlist().      Currently, Hash, Sort,
 491  * and Material nodes want this, so they don't have to store useless columns.
 492  */
 493 static void
 494 disuse_physical_tlist(Plan *plan, Path *path)
 495 {
 496         /* Only need to undo it for path types handled by create_scan_plan() */
 497         switch (path->pathtype)
 498         {
 499                 case T_SeqScan:
 500                 case T_IndexScan:
 501                 case T_IndexOnlyScan:
 502                 case T_BitmapHeapScan:
 503                 case T_TidScan:
 504                 case T_SubqueryScan:
 505                 case T_FunctionScan:
 506                 case T_ValuesScan:
 507                 case T_CteScan:
 508                 case T_WorkTableScan:
 509                 case T_ForeignScan:
 510                         plan->targetlist = build_relation_tlist(path->parent);
 511                         break;
 512                 default:
 513                         break;
 514         }
 515 }
 516
 517 /*
 518  * create_gating_plan
 519  *        Deal with pseudoconstant qual clauses
 520  *
 521  * If the node's quals list includes any pseudoconstant quals, put them
 522  * into a gating Result node atop the already-built plan.  Otherwise,
 523  * return the plan as-is.
 524  *
 525  * Note that we don't change cost or size estimates when doing gating.
 526  * The costs of qual eval were already folded into the plan's startup cost.
 527  * Leaving the size alone amounts to assuming that the gating qual will
 528  * succeed, which is the conservative estimate for planning upper queries.
 529  * We certainly don't want to assume the output size is zero (unless the
 530  * gating qual is actually constant FALSE, and that case is dealt with in
 531  * clausesel.c).  Interpolating between the two cases is silly, because
 532  * it doesn't reflect what will really happen at runtime, and besides which
 533  * in most cases we have only a very bad idea of the probability of the gating
 534  * qual being true.
 535  */
 536 static Plan *
 537 create_gating_plan(PlannerInfo *root, Plan *plan, List *quals)
 538 {
 539         List       *pseudoconstants;
 540
 541         /* Sort into desirable execution order while still in RestrictInfo form */
 542         quals = order_qual_clauses(root, quals);
 543
 544         /* Pull out any pseudoconstant quals from the RestrictInfo list */
 545         pseudoconstants = extract_actual_clauses(quals, true);
 546
 547         if (!pseudoconstants)
 548                 return plan;
 549
 550         return (Plan *) make_result(root,
 551                                                                 plan->targetlist,
 552                                                                 (Node *) pseudoconstants,
 553                                                                 plan);
 554 }
 555
 556 /*
 557  * create_join_plan
 558  *        Create a join plan for 'best_path' and (recursively) plans for its
 559  *        inner and outer paths.
 560  */
 561 static Plan *
 562 create_join_plan(PlannerInfo *root, JoinPath *best_path)
 563 {
 564         Plan       *outer_plan;
 565         Plan       *inner_plan;
 566         Plan       *plan;
 567         Relids          saveOuterRels = root->curOuterRels;
 568
 569         outer_plan = create_plan_recurse(root, best_path->outerjoinpath);
 570
 571         /* For a nestloop, include outer relids in curOuterRels for inner side */
 572         if (best_path->path.pathtype == T_NestLoop)
 573                 root->curOuterRels = bms_union(root->curOuterRels,
 574                                                                    best_path->outerjoinpath->parent->relids);
 575
 576         inner_plan = create_plan_recurse(root, best_path->innerjoinpath);
 577
 578         switch (best_path->path.pathtype)
 579         {
 580                 case T_MergeJoin:
 581                         plan = (Plan *) create_mergejoin_plan(root,
 582                                                                                                   (MergePath *) best_path,
 583                                                                                                   outer_plan,
 584                                                                                                   inner_plan);
 585                         break;
 586                 case T_HashJoin:
 587                         plan = (Plan *) create_hashjoin_plan(root,
 588                                                                                                  (HashPath *) best_path,
 589                                                                                                  outer_plan,
 590                                                                                                  inner_plan);
 591                         break;
 592                 case T_NestLoop:
 593                         /* Restore curOuterRels */
 594                         bms_free(root->curOuterRels);
 595                         root->curOuterRels = saveOuterRels;
 596
 597                         plan = (Plan *) create_nestloop_plan(root,
 598                                                                                                  (NestPath *) best_path,
 599                                                                                                  outer_plan,
 600                                                                                                  inner_plan);
 601                         break;
 602                 default:
 603                         elog(ERROR, "unrecognized node type: %d",
 604                                  (int) best_path->path.pathtype);
 605                         plan = NULL;            /* keep compiler quiet */
 606                         break;
 607         }
 608
 609         /*
 610          * If there are any pseudoconstant clauses attached to this node, insert a
 611          * gating Result node that evaluates the pseudoconstants as one-time
 612          * quals.
 613          */
 614         if (root->hasPseudoConstantQuals)
 615                 plan = create_gating_plan(root, plan, best_path->joinrestrictinfo);
 616
 617 #ifdef NOT_USED
 618
 619         /*
 620          * * Expensive function pullups may have pulled local predicates * into
 621          * this path node.      Put them in the qpqual of the plan node. * JMH,
 622          * 6/15/92
 623          */
 624         if (get_loc_restrictinfo(best_path) != NIL)
 625                 set_qpqual((Plan) plan,
 626                                    list_concat(get_qpqual((Plan) plan),
 627                                            get_actual_clauses(get_loc_restrictinfo(best_path))));
 628 #endif
 629
 630         return plan;
 631 }
 632
 633 /*
 634  * create_append_plan
 635  *        Create an Append plan for 'best_path' and (recursively) plans
 636  *        for its subpaths.
 637  *
 638  *        Returns a Plan node.
 639  */
 640 static Plan *
 641 create_append_plan(PlannerInfo *root, AppendPath *best_path)
 642 {
 643         Append     *plan;
 644         List       *tlist = build_relation_tlist(best_path->path.parent);
 645         List       *subplans = NIL;
 646         ListCell   *subpaths;
 647
 648         /*
 649          * It is possible for the subplans list to contain only one entry, or even
 650          * no entries.  Handle these cases specially.
 651          *
 652          * XXX ideally, if there's just one entry, we'd not bother to generate an
 653          * Append node but just return the single child.  At the moment this does
 654          * not work because the varno of the child scan plan won't match the
 655          * parent-rel Vars it'll be asked to emit.
 656          */
 657         if (best_path->subpaths == NIL)
 658         {
 659                 /* Generate a Result plan with constant-FALSE gating qual */
 660                 return (Plan *) make_result(root,
 661                                                                         tlist,
 662                                                                         (Node *) list_make1(makeBoolConst(false,
 663                                                                                                                                           false)),
 664                                                                         NULL);
 665         }
 666
 667         /* Normal case with multiple subpaths */
 668         foreach(subpaths, best_path->subpaths)
 669         {
 670                 Path       *subpath = (Path *) lfirst(subpaths);
 671
 672                 subplans = lappend(subplans, create_plan_recurse(root, subpath));
 673         }
 674
 675         plan = make_append(subplans, tlist);
 676
 677         return (Plan *) plan;
 678 }
 679
 680 /*
 681  * create_merge_append_plan
 682  *        Create a MergeAppend plan for 'best_path' and (recursively) plans
 683  *        for its subpaths.
 684  *
 685  *        Returns a Plan node.
 686  */
 687 static Plan *
 688 create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
 689 {
 690         MergeAppend *node = makeNode(MergeAppend);
 691         Plan       *plan = &node->plan;
 692         List       *tlist = build_relation_tlist(best_path->path.parent);
 693         List       *pathkeys = best_path->path.pathkeys;
 694         List       *subplans = NIL;
 695         ListCell   *subpaths;
 696
 697         /*
 698          * We don't have the actual creation of the MergeAppend node split out
 699          * into a separate make_xxx function.  This is because we want to run
 700          * prepare_sort_from_pathkeys on it before we do so on the individual
 701          * child plans, to make cross-checking the sort info easier.
 702          */
 703         copy_path_costsize(plan, (Path *) best_path);
 704         plan->targetlist = tlist;
 705         plan->qual = NIL;
 706         plan->lefttree = NULL;
 707         plan->righttree = NULL;
 708
 709         /* Compute sort column info, and adjust MergeAppend's tlist as needed */
 710         (void) prepare_sort_from_pathkeys(root, plan, pathkeys,
 711                                                                           true,
 712                                                                           &node->numCols,
 713                                                                           &node->sortColIdx,
 714                                                                           &node->sortOperators,
 715                                                                           &node->collations,
 716                                                                           &node->nullsFirst);
 717
 718         /*
 719          * Now prepare the child plans.  We must apply prepare_sort_from_pathkeys
 720          * even to subplans that don't need an explicit sort, to make sure they
 721          * are returning the same sort key columns the MergeAppend expects.
 722          */
 723         foreach(subpaths, best_path->subpaths)
 724         {
 725                 Path       *subpath = (Path *) lfirst(subpaths);
 726                 Plan       *subplan;
 727                 int                     numsortkeys;
 728                 AttrNumber *sortColIdx;
 729                 Oid                *sortOperators;
 730                 Oid                *collations;
 731                 bool       *nullsFirst;
 732
 733                 /* Build the child plan */
 734                 subplan = create_plan_recurse(root, subpath);
 735
 736                 /* Compute sort column info, and adjust subplan's tlist as needed */
 737                 subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
 738                                                                                          false,
 739                                                                                          &numsortkeys,
 740                                                                                          &sortColIdx,
 741                                                                                          &sortOperators,
 742                                                                                          &collations,
 743                                                                                          &nullsFirst);
 744
 745                 /*
 746                  * Check that we got the same sort key information.  We just Assert
 747                  * that the sortops match, since those depend only on the pathkeys;
 748                  * but it seems like a good idea to check the sort column numbers
 749                  * explicitly, to ensure the tlists really do match up.
 750                  */
 751                 Assert(numsortkeys == node->numCols);
 752                 if (memcmp(sortColIdx, node->sortColIdx,
 753                                    numsortkeys * sizeof(AttrNumber)) != 0)
 754                         elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
 755                 Assert(memcmp(sortOperators, node->sortOperators,
 756                                           numsortkeys * sizeof(Oid)) == 0);
 757                 Assert(memcmp(collations, node->collations,
 758                                           numsortkeys * sizeof(Oid)) == 0);
 759                 Assert(memcmp(nullsFirst, node->nullsFirst,
 760                                           numsortkeys * sizeof(bool)) == 0);
 761
 762                 /* Now, insert a Sort node if subplan isn't sufficiently ordered */
 763                 if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
 764                         subplan = (Plan *) make_sort(root, subplan, numsortkeys,
 765                                                                                  sortColIdx, sortOperators,
 766                                                                                  collations, nullsFirst,
 767                                                                                  best_path->limit_tuples);
 768
 769                 subplans = lappend(subplans, subplan);
 770         }
 771
 772         node->mergeplans = subplans;
 773
 774         return (Plan *) node;
 775 }
 776
 777 /*
 778  * create_result_plan
 779  *        Create a Result plan for 'best_path'.
 780  *        This is only used for the case of a query with an empty jointree.
 781  *
 782  *        Returns a Plan node.
 783  */
 784 static Result *
 785 create_result_plan(PlannerInfo *root, ResultPath *best_path)
 786 {
 787         List       *tlist;
 788         List       *quals;
 789
 790         /* The tlist will be installed later, since we have no RelOptInfo */
 791         Assert(best_path->path.parent == NULL);
 792         tlist = NIL;
 793
 794         /* best_path->quals is just bare clauses */
 795
 796         quals = order_qual_clauses(root, best_path->quals);
 797
 798         return make_result(root, tlist, (Node *) quals, NULL);
 799 }
 800
 801 /*
 802  * create_material_plan
 803  *        Create a Material plan for 'best_path' and (recursively) plans
 804  *        for its subpaths.
 805  *
 806  *        Returns a Plan node.
 807  */
 808 static Material *
 809 create_material_plan(PlannerInfo *root, MaterialPath *best_path)
 810 {
 811         Material   *plan;
 812         Plan       *subplan;
 813
 814         subplan = create_plan_recurse(root, best_path->subpath);
 815
 816         /* We don't want any excess columns in the materialized tuples */
 817         disuse_physical_tlist(subplan, best_path->subpath);
 818
 819         plan = make_material(subplan);
 820
 821         copy_path_costsize(&plan->plan, (Path *) best_path);
 822
 823         return plan;
 824 }
 825
 826 /*
 827  * create_unique_plan
 828  *        Create a Unique plan for 'best_path' and (recursively) plans
 829  *        for its subpaths.
 830  *
 831  *        Returns a Plan node.
 832  */
 833 static Plan *
 834 create_unique_plan(PlannerInfo *root, UniquePath *best_path)
 835 {
 836         Plan       *plan;
 837         Plan       *subplan;
 838         List       *in_operators;
 839         List       *uniq_exprs;
 840         List       *newtlist;
 841         int                     nextresno;
 842         bool            newitems;
 843         int                     numGroupCols;
 844         AttrNumber *groupColIdx;
 845         int                     groupColPos;
 846         ListCell   *l;
 847
 848         subplan = create_plan_recurse(root, best_path->subpath);
 849
 850         /* Done if we don't need to do any actual unique-ifying */
 851         if (best_path->umethod == UNIQUE_PATH_NOOP)
 852                 return subplan;
 853
 854         /*
 855          * As constructed, the subplan has a "flat" tlist containing just the Vars
 856          * needed here and at upper levels.  The values we are supposed to
 857          * unique-ify may be expressions in these variables.  We have to add any
 858          * such expressions to the subplan's tlist.
 859          *
 860          * The subplan may have a "physical" tlist if it is a simple scan plan. If
 861          * we're going to sort, this should be reduced to the regular tlist, so
 862          * that we don't sort more data than we need to.  For hashing, the tlist
 863          * should be left as-is if we don't need to add any expressions; but if we
 864          * do have to add expressions, then a projection step will be needed at
 865          * runtime anyway, so we may as well remove unneeded items. Therefore
 866          * newtlist starts from build_relation_tlist() not just a copy of the
 867          * subplan's tlist; and we don't install it into the subplan unless we are
 868          * sorting or stuff has to be added.
 869          */
 870         in_operators = best_path->in_operators;
 871         uniq_exprs = best_path->uniq_exprs;
 872
 873         /* initialize modified subplan tlist as just the "required" vars */
 874         newtlist = build_relation_tlist(best_path->path.parent);
 875         nextresno = list_length(newtlist) + 1;
 876         newitems = false;
 877
 878         foreach(l, uniq_exprs)
 879         {
 880                 Node       *uniqexpr = lfirst(l);
 881                 TargetEntry *tle;
 882
 883                 tle = tlist_member(uniqexpr, newtlist);
 884                 if (!tle)
 885                 {
 886                         tle = makeTargetEntry((Expr *) uniqexpr,
 887                                                                   nextresno,
 888                                                                   NULL,
 889                                                                   false);
 890                         newtlist = lappend(newtlist, tle);
 891                         nextresno++;
 892                         newitems = true;
 893                 }
 894         }
 895
 896         if (newitems || best_path->umethod == UNIQUE_PATH_SORT)
 897         {
 898                 /*
 899                  * If the top plan node can't do projections, we need to add a Result
 900                  * node to help it along.
 901                  */
 902                 if (!is_projection_capable_plan(subplan))
 903                         subplan = (Plan *) make_result(root, newtlist, NULL, subplan);
 904                 else
 905                         subplan->targetlist = newtlist;
 906         }
 907
 908         /*
 909          * Build control information showing which subplan output columns are to
 910          * be examined by the grouping step.  Unfortunately we can't merge this
 911          * with the previous loop, since we didn't then know which version of the
 912          * subplan tlist we'd end up using.
 913          */
 914         newtlist = subplan->targetlist;
 915         numGroupCols = list_length(uniq_exprs);
 916         groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
 917
 918         groupColPos = 0;
 919         foreach(l, uniq_exprs)
 920         {
 921                 Node       *uniqexpr = lfirst(l);
 922                 TargetEntry *tle;
 923
 924                 tle = tlist_member(uniqexpr, newtlist);
 925                 if (!tle)                               /* shouldn't happen */
 926                         elog(ERROR, "failed to find unique expression in subplan tlist");
 927                 groupColIdx[groupColPos++] = tle->resno;
 928         }
 929
 930         if (best_path->umethod == UNIQUE_PATH_HASH)
 931         {
 932                 long            numGroups;
 933                 Oid                *groupOperators;
 934
 935                 numGroups = (long) Min(best_path->path.rows, (double) LONG_MAX);
 936
 937                 /*
 938                  * Get the hashable equality operators for the Agg node to use.
 939                  * Normally these are the same as the IN clause operators, but if
 940                  * those are cross-type operators then the equality operators are the
 941                  * ones for the IN clause operators' RHS datatype.
 942                  */
 943                 groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
 944                 groupColPos = 0;
 945                 foreach(l, in_operators)
 946                 {
 947                         Oid                     in_oper = lfirst_oid(l);
 948                         Oid                     eq_oper;
 949
 950                         if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
 951                                 elog(ERROR, "could not find compatible hash operator for operator %u",
 952                                          in_oper);
 953                         groupOperators[groupColPos++] = eq_oper;
 954                 }
 955
 956                 /*
 957                  * Since the Agg node is going to project anyway, we can give it the
 958                  * minimum output tlist, without any stuff we might have added to the
 959                  * subplan tlist.
 960                  */
 961                 plan = (Plan *) make_agg(root,
 962                                                                  build_relation_tlist(best_path->path.parent),
 963                                                                  NIL,
 964                                                                  AGG_HASHED,
 965                                                                  NULL,
 966                                                                  numGroupCols,
 967                                                                  groupColIdx,
 968                                                                  groupOperators,
 969                                                                  numGroups,
 970                                                                  subplan);
 971         }
 972         else
 973         {
 974                 List       *sortList = NIL;
 975
 976                 /* Create an ORDER BY list to sort the input compatibly */
 977                 groupColPos = 0;
 978                 foreach(l, in_operators)
 979                 {
 980                         Oid                     in_oper = lfirst_oid(l);
 981                         Oid                     sortop;
 982                         Oid                     eqop;
 983                         TargetEntry *tle;
 984                         SortGroupClause *sortcl;
 985
 986                         sortop = get_ordering_op_for_equality_op(in_oper, false);
 987                         if (!OidIsValid(sortop))        /* shouldn't happen */
 988                                 elog(ERROR, "could not find ordering operator for equality operator %u",
 989                                          in_oper);
 990
 991                         /*
 992                          * The Unique node will need equality operators.  Normally these
 993                          * are the same as the IN clause operators, but if those are
 994                          * cross-type operators then the equality operators are the ones
 995                          * for the IN clause operators' RHS datatype.
 996                          */
 997                         eqop = get_equality_op_for_ordering_op(sortop, NULL);
 998                         if (!OidIsValid(eqop))          /* shouldn't happen */
 999                                 elog(ERROR, "could not find equality operator for ordering operator %u",
1000                                          sortop);
1001
1002                         tle = get_tle_by_resno(subplan->targetlist,
1003                                                                    groupColIdx[groupColPos]);
1004                         Assert(tle != NULL);
1005
1006                         sortcl = makeNode(SortGroupClause);
1007                         sortcl->tleSortGroupRef = assignSortGroupRef(tle,
1008                                                                                                                  subplan->targetlist);
1009                         sortcl->eqop = eqop;
1010                         sortcl->sortop = sortop;
1011                         sortcl->nulls_first = false;
1012                         sortcl->hashable = false;       /* no need to make this accurate */
1013                         sortList = lappend(sortList, sortcl);
1014                         groupColPos++;
1015                 }
1016                 plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
1017                 plan = (Plan *) make_unique(plan, sortList);
1018         }
1019
1020         /* Adjust output size estimate (other fields should be OK already) */
1021         plan->plan_rows = best_path->path.rows;
1022
1023         return plan;
1024 }
1025
1026
1027 /*****************************************************************************
1028  *
1029  *      BASE-RELATION SCAN METHODS
1030  *
1031  *****************************************************************************/
1032
1033
1034 /*
1035  * create_seqscan_plan
1036  *       Returns a seqscan plan for the base relation scanned by 'best_path'
1037  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1038  */
1039 static SeqScan *
1040 create_seqscan_plan(PlannerInfo *root, Path *best_path,
1041                                         List *tlist, List *scan_clauses)
1042 {
1043         SeqScan    *scan_plan;
1044         Index           scan_relid = best_path->parent->relid;
1045
1046         /* it should be a base rel... */
1047         Assert(scan_relid > 0);
1048         Assert(best_path->parent->rtekind == RTE_RELATION);
1049
1050         /* Sort clauses into best execution order */
1051         scan_clauses = order_qual_clauses(root, scan_clauses);
1052
1053         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1054         scan_clauses = extract_actual_clauses(scan_clauses, false);
1055
1056         scan_plan = make_seqscan(tlist,
1057                                                          scan_clauses,
1058                                                          scan_relid);
1059
1060         copy_path_costsize(&scan_plan->plan, best_path);
1061
1062         return scan_plan;
1063 }
1064
1065 /*
1066  * create_indexscan_plan
1067  *        Returns an indexscan plan for the base relation scanned by 'best_path'
1068  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1069  *
1070  * We use this for both plain IndexScans and IndexOnlyScans, because the
1071  * qual preprocessing work is the same for both.  Note that the caller tells
1072  * us which to build --- we don't look at best_path->path.pathtype, because
1073  * create_bitmap_subplan needs to be able to override the prior decision.
1074  */
1075 static Scan *
1076 create_indexscan_plan(PlannerInfo *root,
1077                                           IndexPath *best_path,
1078                                           List *tlist,
1079                                           List *scan_clauses,
1080                                           bool indexonly)
1081 {
1082         Scan       *scan_plan;
1083         List       *indexquals = best_path->indexquals;
1084         List       *indexorderbys = best_path->indexorderbys;
1085         Index           baserelid = best_path->path.parent->relid;
1086         Oid                     indexoid = best_path->indexinfo->indexoid;
1087         List       *qpqual;
1088         List       *stripped_indexquals;
1089         List       *fixed_indexquals;
1090         List       *fixed_indexorderbys;
1091         ListCell   *l;
1092
1093         /* it should be a base rel... */
1094         Assert(baserelid > 0);
1095         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1096
1097         /*
1098          * Build "stripped" indexquals structure (no RestrictInfos) to pass to
1099          * executor as indexqualorig
1100          */
1101         stripped_indexquals = get_actual_clauses(indexquals);
1102
1103         /*
1104          * The executor needs a copy with the indexkey on the left of each clause
1105          * and with index Vars substituted for table ones.
1106          */
1107         fixed_indexquals = fix_indexqual_references(root, best_path);
1108
1109         /*
1110          * Likewise fix up index attr references in the ORDER BY expressions.
1111          */
1112         fixed_indexorderbys = fix_indexorderby_references(root, best_path);
1113
1114         /*
1115          * If this is a parameterized scan, the indexclauses will contain join
1116          * clauses that are not present in scan_clauses (since the passed-in value
1117          * is just the rel's baserestrictinfo list).  We must add these clauses to
1118          * scan_clauses to ensure they get checked.  In most cases we will remove
1119          * the join clauses again below, but if a join clause contains a special
1120          * operator, we need to make sure it gets into the scan_clauses.
1121          *
1122          * Note: pointer comparison should be enough to determine RestrictInfo
1123          * matches.
1124          */
1125         if (best_path->path.required_outer)
1126                 scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
1127
1128         /*
1129          * The qpqual list must contain all restrictions not automatically handled
1130          * by the index.  All the predicates in the indexquals will be checked
1131          * (either by the index itself, or by nodeIndexscan.c), but if there are
1132          * any "special" operators involved then they must be included in qpqual.
1133          * The upshot is that qpqual must contain scan_clauses minus whatever
1134          * appears in indexquals.
1135          *
1136          * In normal cases simple pointer equality checks will be enough to spot
1137          * duplicate RestrictInfos, so we try that first.  In some situations
1138          * (particularly with OR'd index conditions) we may have scan_clauses that
1139          * are not equal to, but are logically implied by, the index quals; so we
1140          * also try a predicate_implied_by() check to see if we can discard quals
1141          * that way.  (predicate_implied_by assumes its first input contains only
1142          * immutable functions, so we have to check that.)
1143          *
1144          * We can also discard quals that are implied by a partial index's
1145          * predicate, but only in a plain SELECT; when scanning a target relation
1146          * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
1147          * plan so that they'll be properly rechecked by EvalPlanQual testing.
1148          */
1149         qpqual = NIL;
1150         foreach(l, scan_clauses)
1151         {
1152                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1153
1154                 Assert(IsA(rinfo, RestrictInfo));
1155                 if (rinfo->pseudoconstant)
1156                         continue;                       /* we may drop pseudoconstants here */
1157                 if (list_member_ptr(indexquals, rinfo))
1158                         continue;
1159                 if (!contain_mutable_functions((Node *) rinfo->clause))
1160                 {
1161                         List       *clausel = list_make1(rinfo->clause);
1162
1163                         if (predicate_implied_by(clausel, indexquals))
1164                                 continue;
1165                         if (best_path->indexinfo->indpred)
1166                         {
1167                                 if (baserelid != root->parse->resultRelation &&
1168                                         get_parse_rowmark(root->parse, baserelid) == NULL)
1169                                         if (predicate_implied_by(clausel,
1170                                                                                          best_path->indexinfo->indpred))
1171                                                 continue;
1172                         }
1173                 }
1174                 qpqual = lappend(qpqual, rinfo);
1175         }
1176
1177         /* Sort clauses into best execution order */
1178         qpqual = order_qual_clauses(root, qpqual);
1179
1180         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1181         qpqual = extract_actual_clauses(qpqual, false);
1182
1183         /*
1184          * We have to replace any outer-relation variables with nestloop params in
1185          * the indexqualorig, qpqual, and indexorderbyorig expressions.  A bit
1186          * annoying to have to do this separately from the processing in
1187          * fix_indexqual_references --- rethink this when generalizing the inner
1188          * indexscan support.  But note we can't really do this earlier because
1189          * it'd break the comparisons to predicates above ... (or would it?  Those
1190          * wouldn't have outer refs)
1191          */
1192         if (best_path->path.required_outer)
1193         {
1194                 stripped_indexquals = (List *)
1195                         replace_nestloop_params(root, (Node *) stripped_indexquals);
1196                 qpqual = (List *)
1197                         replace_nestloop_params(root, (Node *) qpqual);
1198                 indexorderbys = (List *)
1199                         replace_nestloop_params(root, (Node *) indexorderbys);
1200         }
1201
1202         /* Finally ready to build the plan node */
1203         if (indexonly)
1204                 scan_plan = (Scan *) make_indexonlyscan(tlist,
1205                                                                                                 qpqual,
1206                                                                                                 baserelid,
1207                                                                                                 indexoid,
1208                                                                                                 fixed_indexquals,
1209                                                                                                 fixed_indexorderbys,
1210                                                                                                 best_path->indexinfo->indextlist,
1211                                                                                                 best_path->indexscandir);
1212         else
1213                 scan_plan = (Scan *) make_indexscan(tlist,
1214                                                                                         qpqual,
1215                                                                                         baserelid,
1216                                                                                         indexoid,
1217                                                                                         fixed_indexquals,
1218                                                                                         stripped_indexquals,
1219                                                                                         fixed_indexorderbys,
1220                                                                                         indexorderbys,
1221                                                                                         best_path->indexscandir);
1222
1223         copy_path_costsize(&scan_plan->plan, &best_path->path);
1224
1225         return scan_plan;
1226 }
1227
1228 /*
1229  * create_bitmap_scan_plan
1230  *        Returns a bitmap scan plan for the base relation scanned by 'best_path'
1231  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1232  */
1233 static BitmapHeapScan *
1234 create_bitmap_scan_plan(PlannerInfo *root,
1235                                                 BitmapHeapPath *best_path,
1236                                                 List *tlist,
1237                                                 List *scan_clauses)
1238 {
1239         Index           baserelid = best_path->path.parent->relid;
1240         Plan       *bitmapqualplan;
1241         List       *bitmapqualorig;
1242         List       *indexquals;
1243         List       *qpqual;
1244         ListCell   *l;
1245         BitmapHeapScan *scan_plan;
1246
1247         /* it should be a base rel... */
1248         Assert(baserelid > 0);
1249         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1250
1251         /* Process the bitmapqual tree into a Plan tree and qual lists */
1252         bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
1253                                                                                    &bitmapqualorig, &indexquals);
1254
1255         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1256         scan_clauses = extract_actual_clauses(scan_clauses, false);
1257
1258         /*
1259          * If this is a parameterized scan, the indexclauses will contain join clauses
1260          * that are not present in scan_clauses (since the passed-in value is just
1261          * the rel's baserestrictinfo list).  We must add these clauses to
1262          * scan_clauses to ensure they get checked.  In most cases we will remove
1263          * the join clauses again below, but if a join clause contains a special
1264          * operator, we need to make sure it gets into the scan_clauses.
1265          */
1266         if (best_path->path.required_outer)
1267         {
1268                 scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
1269         }
1270
1271         /*
1272          * The qpqual list must contain all restrictions not automatically handled
1273          * by the index.  All the predicates in the indexquals will be checked
1274          * (either by the index itself, or by nodeBitmapHeapscan.c), but if there
1275          * are any "special" operators involved then they must be added to qpqual.
1276          * The upshot is that qpqual must contain scan_clauses minus whatever
1277          * appears in indexquals.
1278          *
1279          * In normal cases simple equal() checks will be enough to spot duplicate
1280          * clauses, so we try that first.  In some situations (particularly with
1281          * OR'd index conditions) we may have scan_clauses that are not equal to,
1282          * but are logically implied by, the index quals; so we also try a
1283          * predicate_implied_by() check to see if we can discard quals that way.
1284          * (predicate_implied_by assumes its first input contains only immutable
1285          * functions, so we have to check that.)
1286          *
1287          * Unlike create_indexscan_plan(), we need take no special thought here
1288          * for partial index predicates; this is because the predicate conditions
1289          * are already listed in bitmapqualorig and indexquals.  Bitmap scans have
1290          * to do it that way because predicate conditions need to be rechecked if
1291          * the scan becomes lossy.
1292          */
1293         qpqual = NIL;
1294         foreach(l, scan_clauses)
1295         {
1296                 Node       *clause = (Node *) lfirst(l);
1297
1298                 if (list_member(indexquals, clause))
1299                         continue;
1300                 if (!contain_mutable_functions(clause))
1301                 {
1302                         List       *clausel = list_make1(clause);
1303
1304                         if (predicate_implied_by(clausel, indexquals))
1305                                 continue;
1306                 }
1307                 qpqual = lappend(qpqual, clause);
1308         }
1309
1310         /* Sort clauses into best execution order */
1311         qpqual = order_qual_clauses(root, qpqual);
1312
1313         /*
1314          * When dealing with special operators, we will at this point have
1315          * duplicate clauses in qpqual and bitmapqualorig.      We may as well drop
1316          * 'em from bitmapqualorig, since there's no point in making the tests
1317          * twice.
1318          */
1319         bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
1320
1321         /* Finally ready to build the plan node */
1322         scan_plan = make_bitmap_heapscan(tlist,
1323                                                                          qpqual,
1324                                                                          bitmapqualplan,
1325                                                                          bitmapqualorig,
1326                                                                          baserelid);
1327
1328         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1329
1330         return scan_plan;
1331 }
1332
1333 /*
1334  * Given a bitmapqual tree, generate the Plan tree that implements it
1335  *
1336  * As byproducts, we also return in *qual and *indexqual the qual lists
1337  * (in implicit-AND form, without RestrictInfos) describing the original index
1338  * conditions and the generated indexqual conditions.  (These are the same in
1339  * simple cases, but when special index operators are involved, the former
1340  * list includes the special conditions while the latter includes the actual
1341  * indexable conditions derived from them.)  Both lists include partial-index
1342  * predicates, because we have to recheck predicates as well as index
1343  * conditions if the bitmap scan becomes lossy.
1344  *
1345  * Note: if you find yourself changing this, you probably need to change
1346  * make_restrictinfo_from_bitmapqual too.
1347  */
1348 static Plan *
1349 create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
1350                                           List **qual, List **indexqual)
1351 {
1352         Plan       *plan;
1353
1354         if (IsA(bitmapqual, BitmapAndPath))
1355         {
1356                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
1357                 List       *subplans = NIL;
1358                 List       *subquals = NIL;
1359                 List       *subindexquals = NIL;
1360                 ListCell   *l;
1361
1362                 /*
1363                  * There may well be redundant quals among the subplans, since a
1364                  * top-level WHERE qual might have gotten used to form several
1365                  * different index quals.  We don't try exceedingly hard to eliminate
1366                  * redundancies, but we do eliminate obvious duplicates by using
1367                  * list_concat_unique.
1368                  */
1369                 foreach(l, apath->bitmapquals)
1370                 {
1371                         Plan       *subplan;
1372                         List       *subqual;
1373                         List       *subindexqual;
1374
1375                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1376                                                                                         &subqual, &subindexqual);
1377                         subplans = lappend(subplans, subplan);
1378                         subquals = list_concat_unique(subquals, subqual);
1379                         subindexquals = list_concat_unique(subindexquals, subindexqual);
1380                 }
1381                 plan = (Plan *) make_bitmap_and(subplans);
1382                 plan->startup_cost = apath->path.startup_cost;
1383                 plan->total_cost = apath->path.total_cost;
1384                 plan->plan_rows =
1385                         clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
1386                 plan->plan_width = 0;   /* meaningless */
1387                 *qual = subquals;
1388                 *indexqual = subindexquals;
1389         }
1390         else if (IsA(bitmapqual, BitmapOrPath))
1391         {
1392                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
1393                 List       *subplans = NIL;
1394                 List       *subquals = NIL;
1395                 List       *subindexquals = NIL;
1396                 bool            const_true_subqual = false;
1397                 bool            const_true_subindexqual = false;
1398                 ListCell   *l;
1399
1400                 /*
1401                  * Here, we only detect qual-free subplans.  A qual-free subplan would
1402                  * cause us to generate "... OR true ..."  which we may as well reduce
1403                  * to just "true".      We do not try to eliminate redundant subclauses
1404                  * because (a) it's not as likely as in the AND case, and (b) we might
1405                  * well be working with hundreds or even thousands of OR conditions,
1406                  * perhaps from a long IN list.  The performance of list_append_unique
1407                  * would be unacceptable.
1408                  */
1409                 foreach(l, opath->bitmapquals)
1410                 {
1411                         Plan       *subplan;
1412                         List       *subqual;
1413                         List       *subindexqual;
1414
1415                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1416                                                                                         &subqual, &subindexqual);
1417                         subplans = lappend(subplans, subplan);
1418                         if (subqual == NIL)
1419                                 const_true_subqual = true;
1420                         else if (!const_true_subqual)
1421                                 subquals = lappend(subquals,
1422                                                                    make_ands_explicit(subqual));
1423                         if (subindexqual == NIL)
1424                                 const_true_subindexqual = true;
1425                         else if (!const_true_subindexqual)
1426                                 subindexquals = lappend(subindexquals,
1427                                                                                 make_ands_explicit(subindexqual));
1428                 }
1429
1430                 /*
1431                  * In the presence of ScalarArrayOpExpr quals, we might have built
1432                  * BitmapOrPaths with just one subpath; don't add an OR step.
1433                  */
1434                 if (list_length(subplans) == 1)
1435                 {
1436                         plan = (Plan *) linitial(subplans);
1437                 }
1438                 else
1439                 {
1440                         plan = (Plan *) make_bitmap_or(subplans);
1441                         plan->startup_cost = opath->path.startup_cost;
1442                         plan->total_cost = opath->path.total_cost;
1443                         plan->plan_rows =
1444                                 clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
1445                         plan->plan_width = 0;           /* meaningless */
1446                 }
1447
1448                 /*
1449                  * If there were constant-TRUE subquals, the OR reduces to constant
1450                  * TRUE.  Also, avoid generating one-element ORs, which could happen
1451                  * due to redundancy elimination or ScalarArrayOpExpr quals.
1452                  */
1453                 if (const_true_subqual)
1454                         *qual = NIL;
1455                 else if (list_length(subquals) <= 1)
1456                         *qual = subquals;
1457                 else
1458                         *qual = list_make1(make_orclause(subquals));
1459                 if (const_true_subindexqual)
1460                         *indexqual = NIL;
1461                 else if (list_length(subindexquals) <= 1)
1462                         *indexqual = subindexquals;
1463                 else
1464                         *indexqual = list_make1(make_orclause(subindexquals));
1465         }
1466         else if (IsA(bitmapqual, IndexPath))
1467         {
1468                 IndexPath  *ipath = (IndexPath *) bitmapqual;
1469                 IndexScan  *iscan;
1470                 ListCell   *l;
1471
1472                 /* Use the regular indexscan plan build machinery... */
1473                 iscan = (IndexScan *) create_indexscan_plan(root, ipath,
1474                                                                                                         NIL, NIL, false);
1475                 Assert(IsA(iscan, IndexScan));
1476                 /* then convert to a bitmap indexscan */
1477                 plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
1478                                                                                           iscan->indexid,
1479                                                                                           iscan->indexqual,
1480                                                                                           iscan->indexqualorig);
1481                 plan->startup_cost = 0.0;
1482                 plan->total_cost = ipath->indextotalcost;
1483                 plan->plan_rows =
1484                         clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
1485                 plan->plan_width = 0;   /* meaningless */
1486                 *qual = get_actual_clauses(ipath->indexclauses);
1487                 *indexqual = get_actual_clauses(ipath->indexquals);
1488                 foreach(l, ipath->indexinfo->indpred)
1489                 {
1490                         Expr       *pred = (Expr *) lfirst(l);
1491
1492                         /*
1493                          * We know that the index predicate must have been implied by the
1494                          * query condition as a whole, but it may or may not be implied by
1495                          * the conditions that got pushed into the bitmapqual.  Avoid
1496                          * generating redundant conditions.
1497                          */
1498                         if (!predicate_implied_by(list_make1(pred), ipath->indexclauses))
1499                         {
1500                                 *qual = lappend(*qual, pred);
1501                                 *indexqual = lappend(*indexqual, pred);
1502                         }
1503                 }
1504
1505                 /*
1506                  * Replace outer-relation variables with nestloop params, but only
1507                  * after doing the above comparisons to index predicates.
1508                  */
1509                 if (ipath->path.required_outer)
1510                 {
1511                         *qual = (List *)
1512                                 replace_nestloop_params(root, (Node *) *qual);
1513                         *indexqual = (List *)
1514                                 replace_nestloop_params(root, (Node *) *indexqual);
1515                 }
1516         }
1517         else
1518         {
1519                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
1520                 plan = NULL;                    /* keep compiler quiet */
1521         }
1522
1523         return plan;
1524 }
1525
1526 /*
1527  * create_tidscan_plan
1528  *       Returns a tidscan plan for the base relation scanned by 'best_path'
1529  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1530  */
1531 static TidScan *
1532 create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
1533                                         List *tlist, List *scan_clauses)
1534 {
1535         TidScan    *scan_plan;
1536         Index           scan_relid = best_path->path.parent->relid;
1537         List       *ortidquals;
1538
1539         /* it should be a base rel... */
1540         Assert(scan_relid > 0);
1541         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1542
1543         /* Sort clauses into best execution order */
1544         scan_clauses = order_qual_clauses(root, scan_clauses);
1545
1546         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1547         scan_clauses = extract_actual_clauses(scan_clauses, false);
1548
1549         /*
1550          * Remove any clauses that are TID quals.  This is a bit tricky since the
1551          * tidquals list has implicit OR semantics.
1552          */
1553         ortidquals = best_path->tidquals;
1554         if (list_length(ortidquals) > 1)
1555                 ortidquals = list_make1(make_orclause(ortidquals));
1556         scan_clauses = list_difference(scan_clauses, ortidquals);
1557
1558         scan_plan = make_tidscan(tlist,
1559                                                          scan_clauses,
1560                                                          scan_relid,
1561                                                          best_path->tidquals);
1562
1563         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1564
1565         return scan_plan;
1566 }
1567
1568 /*
1569  * create_subqueryscan_plan
1570  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
1571  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1572  */
1573 static SubqueryScan *
1574 create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
1575                                                  List *tlist, List *scan_clauses)
1576 {
1577         SubqueryScan *scan_plan;
1578         Index           scan_relid = best_path->parent->relid;
1579
1580         /* it should be a subquery base rel... */
1581         Assert(scan_relid > 0);
1582         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
1583
1584         /* Sort clauses into best execution order */
1585         scan_clauses = order_qual_clauses(root, scan_clauses);
1586
1587         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1588         scan_clauses = extract_actual_clauses(scan_clauses, false);
1589
1590         scan_plan = make_subqueryscan(tlist,
1591                                                                   scan_clauses,
1592                                                                   scan_relid,
1593                                                                   best_path->parent->subplan);
1594
1595         copy_path_costsize(&scan_plan->scan.plan, best_path);
1596
1597         return scan_plan;
1598 }
1599
1600 /*
1601  * create_functionscan_plan
1602  *       Returns a functionscan plan for the base relation scanned by 'best_path'
1603  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1604  */
1605 static FunctionScan *
1606 create_functionscan_plan(PlannerInfo *root, Path *best_path,
1607                                                  List *tlist, List *scan_clauses)
1608 {
1609         FunctionScan *scan_plan;
1610         Index           scan_relid = best_path->parent->relid;
1611         RangeTblEntry *rte;
1612
1613         /* it should be a function base rel... */
1614         Assert(scan_relid > 0);
1615         rte = planner_rt_fetch(scan_relid, root);
1616         Assert(rte->rtekind == RTE_FUNCTION);
1617
1618         /* Sort clauses into best execution order */
1619         scan_clauses = order_qual_clauses(root, scan_clauses);
1620
1621         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1622         scan_clauses = extract_actual_clauses(scan_clauses, false);
1623
1624         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
1625                                                                   rte->funcexpr,
1626                                                                   rte->eref->colnames,
1627                                                                   rte->funccoltypes,
1628                                                                   rte->funccoltypmods,
1629                                                                   rte->funccolcollations);
1630
1631         copy_path_costsize(&scan_plan->scan.plan, best_path);
1632
1633         return scan_plan;
1634 }
1635
1636 /*
1637  * create_valuesscan_plan
1638  *       Returns a valuesscan plan for the base relation scanned by 'best_path'
1639  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1640  */
1641 static ValuesScan *
1642 create_valuesscan_plan(PlannerInfo *root, Path *best_path,
1643                                            List *tlist, List *scan_clauses)
1644 {
1645         ValuesScan *scan_plan;
1646         Index           scan_relid = best_path->parent->relid;
1647         RangeTblEntry *rte;
1648
1649         /* it should be a values base rel... */
1650         Assert(scan_relid > 0);
1651         rte = planner_rt_fetch(scan_relid, root);
1652         Assert(rte->rtekind == RTE_VALUES);
1653
1654         /* Sort clauses into best execution order */
1655         scan_clauses = order_qual_clauses(root, scan_clauses);
1656
1657         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1658         scan_clauses = extract_actual_clauses(scan_clauses, false);
1659
1660         scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
1661                                                                 rte->values_lists);
1662
1663         copy_path_costsize(&scan_plan->scan.plan, best_path);
1664
1665         return scan_plan;
1666 }
1667
1668 /*
1669  * create_ctescan_plan
1670  *       Returns a ctescan plan for the base relation scanned by 'best_path'
1671  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1672  */
1673 static CteScan *
1674 create_ctescan_plan(PlannerInfo *root, Path *best_path,
1675                                         List *tlist, List *scan_clauses)
1676 {
1677         CteScan    *scan_plan;
1678         Index           scan_relid = best_path->parent->relid;
1679         RangeTblEntry *rte;
1680         SubPlan    *ctesplan = NULL;
1681         int                     plan_id;
1682         int                     cte_param_id;
1683         PlannerInfo *cteroot;
1684         Index           levelsup;
1685         int                     ndx;
1686         ListCell   *lc;
1687
1688         Assert(scan_relid > 0);
1689         rte = planner_rt_fetch(scan_relid, root);
1690         Assert(rte->rtekind == RTE_CTE);
1691         Assert(!rte->self_reference);
1692
1693         /*
1694          * Find the referenced CTE, and locate the SubPlan previously made for it.
1695          */
1696         levelsup = rte->ctelevelsup;
1697         cteroot = root;
1698         while (levelsup-- > 0)
1699         {
1700                 cteroot = cteroot->parent_root;
1701                 if (!cteroot)                   /* shouldn't happen */
1702                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1703         }
1704
1705         /*
1706          * Note: cte_plan_ids can be shorter than cteList, if we are still working
1707          * on planning the CTEs (ie, this is a side-reference from another CTE).
1708          * So we mustn't use forboth here.
1709          */
1710         ndx = 0;
1711         foreach(lc, cteroot->parse->cteList)
1712         {
1713                 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
1714
1715                 if (strcmp(cte->ctename, rte->ctename) == 0)
1716                         break;
1717                 ndx++;
1718         }
1719         if (lc == NULL)                         /* shouldn't happen */
1720                 elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
1721         if (ndx >= list_length(cteroot->cte_plan_ids))
1722                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
1723         plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
1724         Assert(plan_id > 0);
1725         foreach(lc, cteroot->init_plans)
1726         {
1727                 ctesplan = (SubPlan *) lfirst(lc);
1728                 if (ctesplan->plan_id == plan_id)
1729                         break;
1730         }
1731         if (lc == NULL)                         /* shouldn't happen */
1732                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
1733
1734         /*
1735          * We need the CTE param ID, which is the sole member of the SubPlan's
1736          * setParam list.
1737          */
1738         cte_param_id = linitial_int(ctesplan->setParam);
1739
1740         /* Sort clauses into best execution order */
1741         scan_clauses = order_qual_clauses(root, scan_clauses);
1742
1743         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1744         scan_clauses = extract_actual_clauses(scan_clauses, false);
1745
1746         scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
1747                                                          plan_id, cte_param_id);
1748
1749         copy_path_costsize(&scan_plan->scan.plan, best_path);
1750
1751         return scan_plan;
1752 }
1753
1754 /*
1755  * create_worktablescan_plan
1756  *       Returns a worktablescan plan for the base relation scanned by 'best_path'
1757  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1758  */
1759 static WorkTableScan *
1760 create_worktablescan_plan(PlannerInfo *root, Path *best_path,
1761                                                   List *tlist, List *scan_clauses)
1762 {
1763         WorkTableScan *scan_plan;
1764         Index           scan_relid = best_path->parent->relid;
1765         RangeTblEntry *rte;
1766         Index           levelsup;
1767         PlannerInfo *cteroot;
1768
1769         Assert(scan_relid > 0);
1770         rte = planner_rt_fetch(scan_relid, root);
1771         Assert(rte->rtekind == RTE_CTE);
1772         Assert(rte->self_reference);
1773
1774         /*
1775          * We need to find the worktable param ID, which is in the plan level
1776          * that's processing the recursive UNION, which is one level *below* where
1777          * the CTE comes from.
1778          */
1779         levelsup = rte->ctelevelsup;
1780         if (levelsup == 0)                      /* shouldn't happen */
1781                 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1782         levelsup--;
1783         cteroot = root;
1784         while (levelsup-- > 0)
1785         {
1786                 cteroot = cteroot->parent_root;
1787                 if (!cteroot)                   /* shouldn't happen */
1788                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1789         }
1790         if (cteroot->wt_param_id < 0)           /* shouldn't happen */
1791                 elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename);
1792
1793         /* Sort clauses into best execution order */
1794         scan_clauses = order_qual_clauses(root, scan_clauses);
1795
1796         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1797         scan_clauses = extract_actual_clauses(scan_clauses, false);
1798
1799         scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
1800                                                                    cteroot->wt_param_id);
1801
1802         copy_path_costsize(&scan_plan->scan.plan, best_path);
1803
1804         return scan_plan;
1805 }
1806
1807 /*
1808  * create_foreignscan_plan
1809  *       Returns a foreignscan plan for the base relation scanned by 'best_path'
1810  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1811  */
1812 static ForeignScan *
1813 create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
1814                                                 List *tlist, List *scan_clauses)
1815 {
1816         ForeignScan *scan_plan;
1817         RelOptInfo *rel = best_path->path.parent;
1818         Index           scan_relid = rel->relid;
1819         RangeTblEntry *rte;
1820         bool            fsSystemCol;
1821         int                     i;
1822
1823         /* it should be a base rel... */
1824         Assert(scan_relid > 0);
1825         Assert(rel->rtekind == RTE_RELATION);
1826         rte = planner_rt_fetch(scan_relid, root);
1827         Assert(rte->rtekind == RTE_RELATION);
1828
1829         /* Sort clauses into best execution order */
1830         scan_clauses = order_qual_clauses(root, scan_clauses);
1831
1832         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1833         scan_clauses = extract_actual_clauses(scan_clauses, false);
1834
1835         /* Detect whether any system columns are requested from rel */
1836         fsSystemCol = false;
1837         for (i = rel->min_attr; i < 0; i++)
1838         {
1839                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
1840                 {
1841                         fsSystemCol = true;
1842                         break;
1843                 }
1844         }
1845
1846         scan_plan = make_foreignscan(tlist,
1847                                                                  scan_clauses,
1848                                                                  scan_relid,
1849                                                                  fsSystemCol,
1850                                                                  best_path->fdwplan);
1851
1852         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1853
1854         return scan_plan;
1855 }
1856
1857
1858 /*****************************************************************************
1859  *
1860  *      JOIN METHODS
1861  *
1862  *****************************************************************************/
1863
1864 static NestLoop *
1865 create_nestloop_plan(PlannerInfo *root,
1866                                          NestPath *best_path,
1867                                          Plan *outer_plan,
1868                                          Plan *inner_plan)
1869 {
1870         NestLoop   *join_plan;
1871         List       *tlist = build_relation_tlist(best_path->path.parent);
1872         List       *joinrestrictclauses = best_path->joinrestrictinfo;
1873         List       *joinclauses;
1874         List       *otherclauses;
1875         Relids          outerrelids;
1876         List       *nestParams;
1877         ListCell   *cell;
1878         ListCell   *prev;
1879         ListCell   *next;
1880
1881         /*
1882          * If the inner path is parameterized, it might have already used some of
1883          * the join quals, in which case we don't have to check them again at the
1884          * join node.  Remove any join quals that are redundant.
1885          */
1886         joinrestrictclauses =
1887                 select_nonredundant_join_clauses(joinrestrictclauses,
1888                                                                                  best_path->innerjoinpath->param_clauses);
1889
1890         /* Sort join qual clauses into best execution order */
1891         joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
1892
1893         /* Get the join qual clauses (in plain expression form) */
1894         /* Any pseudoconstant clauses are ignored here */
1895         if (IS_OUTER_JOIN(best_path->jointype))
1896         {
1897                 extract_actual_join_clauses(joinrestrictclauses,
1898                                                                         &joinclauses, &otherclauses);
1899         }
1900         else
1901         {
1902                 /* We can treat all clauses alike for an inner join */
1903                 joinclauses = extract_actual_clauses(joinrestrictclauses, false);
1904                 otherclauses = NIL;
1905         }
1906
1907         /*
1908          * Identify any nestloop parameters that should be supplied by this join
1909          * node, and move them from root->curOuterParams to the nestParams list.
1910          */
1911         outerrelids = best_path->outerjoinpath->parent->relids;
1912         nestParams = NIL;
1913         prev = NULL;
1914         for (cell = list_head(root->curOuterParams); cell; cell = next)
1915         {
1916                 NestLoopParam *nlp = (NestLoopParam *) lfirst(cell);
1917
1918                 next = lnext(cell);
1919                 if (IsA(nlp->paramval, Var) &&
1920                         bms_is_member(nlp->paramval->varno, outerrelids))
1921                 {
1922                         root->curOuterParams = list_delete_cell(root->curOuterParams,
1923                                                                                                         cell, prev);
1924                         nestParams = lappend(nestParams, nlp);
1925                 }
1926                 else if (IsA(nlp->paramval, PlaceHolderVar) &&
1927                                  bms_overlap(((PlaceHolderVar *) nlp->paramval)->phrels,
1928                                                          outerrelids) &&
1929                                  bms_is_subset(find_placeholder_info(root,
1930                                                                                                          (PlaceHolderVar *) nlp->paramval,
1931                                                                                                          false)->ph_eval_at,
1932                                                            outerrelids))
1933                 {
1934                         root->curOuterParams = list_delete_cell(root->curOuterParams,
1935                                                                                                         cell, prev);
1936                         nestParams = lappend(nestParams, nlp);
1937                 }
1938                 else
1939                         prev = cell;
1940         }
1941
1942         join_plan = make_nestloop(tlist,
1943                                                           joinclauses,
1944                                                           otherclauses,
1945                                                           nestParams,
1946                                                           outer_plan,
1947                                                           inner_plan,
1948                                                           best_path->jointype);
1949
1950         copy_path_costsize(&join_plan->join.plan, &best_path->path);
1951
1952         return join_plan;
1953 }
1954
1955 static MergeJoin *
1956 create_mergejoin_plan(PlannerInfo *root,
1957                                           MergePath *best_path,
1958                                           Plan *outer_plan,
1959                                           Plan *inner_plan)
1960 {
1961         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1962         List       *joinclauses;
1963         List       *otherclauses;
1964         List       *mergeclauses;
1965         List       *outerpathkeys;
1966         List       *innerpathkeys;
1967         int                     nClauses;
1968         Oid                *mergefamilies;
1969         Oid                *mergecollations;
1970         int                *mergestrategies;
1971         bool       *mergenullsfirst;
1972         MergeJoin  *join_plan;
1973         int                     i;
1974         ListCell   *lc;
1975         ListCell   *lop;
1976         ListCell   *lip;
1977
1978         /* Sort join qual clauses into best execution order */
1979         /* NB: do NOT reorder the mergeclauses */
1980         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
1981
1982         /* Get the join qual clauses (in plain expression form) */
1983         /* Any pseudoconstant clauses are ignored here */
1984         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1985         {
1986                 extract_actual_join_clauses(joinclauses,
1987                                                                         &joinclauses, &otherclauses);
1988         }
1989         else
1990         {
1991                 /* We can treat all clauses alike for an inner join */
1992                 joinclauses = extract_actual_clauses(joinclauses, false);
1993                 otherclauses = NIL;
1994         }
1995
1996         /*
1997          * Remove the mergeclauses from the list of join qual clauses, leaving the
1998          * list of quals that must be checked as qpquals.
1999          */
2000         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
2001         joinclauses = list_difference(joinclauses, mergeclauses);
2002
2003         /*
2004          * Rearrange mergeclauses, if needed, so that the outer variable is always
2005          * on the left; mark the mergeclause restrictinfos with correct
2006          * outer_is_left status.
2007          */
2008         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
2009                                                          best_path->jpath.outerjoinpath->parent->relids);
2010
2011         /*
2012          * Create explicit sort nodes for the outer and inner paths if necessary.
2013          * Make sure there are no excess columns in the inputs if sorting.
2014          */
2015         if (best_path->outersortkeys)
2016         {
2017                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
2018                 outer_plan = (Plan *)
2019                         make_sort_from_pathkeys(root,
2020                                                                         outer_plan,
2021                                                                         best_path->outersortkeys,
2022                                                                         -1.0);
2023                 outerpathkeys = best_path->outersortkeys;
2024         }
2025         else
2026                 outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;
2027
2028         if (best_path->innersortkeys)
2029         {
2030                 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
2031                 inner_plan = (Plan *)
2032                         make_sort_from_pathkeys(root,
2033                                                                         inner_plan,
2034                                                                         best_path->innersortkeys,
2035                                                                         -1.0);
2036                 innerpathkeys = best_path->innersortkeys;
2037         }
2038         else
2039                 innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;
2040
2041         /*
2042          * If specified, add a materialize node to shield the inner plan from the
2043          * need to handle mark/restore.
2044          */
2045         if (best_path->materialize_inner)
2046         {
2047                 Plan       *matplan = (Plan *) make_material(inner_plan);
2048
2049                 /*
2050                  * We assume the materialize will not spill to disk, and therefore
2051                  * charge just cpu_operator_cost per tuple.  (Keep this estimate in
2052                  * sync with final_cost_mergejoin.)
2053                  */
2054                 copy_plan_costsize(matplan, inner_plan);
2055                 matplan->total_cost += cpu_operator_cost * matplan->plan_rows;
2056
2057                 inner_plan = matplan;
2058         }
2059
2060         /*
2061          * Compute the opfamily/collation/strategy/nullsfirst arrays needed by the
2062          * executor.  The information is in the pathkeys for the two inputs, but
2063          * we need to be careful about the possibility of mergeclauses sharing a
2064          * pathkey (compare find_mergeclauses_for_pathkeys()).
2065          */
2066         nClauses = list_length(mergeclauses);
2067         Assert(nClauses == list_length(best_path->path_mergeclauses));
2068         mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
2069         mergecollations = (Oid *) palloc(nClauses * sizeof(Oid));
2070         mergestrategies = (int *) palloc(nClauses * sizeof(int));
2071         mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));
2072
2073         lop = list_head(outerpathkeys);
2074         lip = list_head(innerpathkeys);
2075         i = 0;
2076         foreach(lc, best_path->path_mergeclauses)
2077         {
2078                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2079                 EquivalenceClass *oeclass;
2080                 EquivalenceClass *ieclass;
2081                 PathKey    *opathkey;
2082                 PathKey    *ipathkey;
2083                 EquivalenceClass *opeclass;
2084                 EquivalenceClass *ipeclass;
2085                 ListCell   *l2;
2086
2087                 /* fetch outer/inner eclass from mergeclause */
2088                 Assert(IsA(rinfo, RestrictInfo));
2089                 if (rinfo->outer_is_left)
2090                 {
2091                         oeclass = rinfo->left_ec;
2092                         ieclass = rinfo->right_ec;
2093                 }
2094                 else
2095                 {
2096                         oeclass = rinfo->right_ec;
2097                         ieclass = rinfo->left_ec;
2098                 }
2099                 Assert(oeclass != NULL);
2100                 Assert(ieclass != NULL);
2101
2102                 /*
2103                  * For debugging purposes, we check that the eclasses match the paths'
2104                  * pathkeys.  In typical cases the merge clauses are one-to-one with
2105                  * the pathkeys, but when dealing with partially redundant query
2106                  * conditions, we might have clauses that re-reference earlier path
2107                  * keys.  The case that we need to reject is where a pathkey is
2108                  * entirely skipped over.
2109                  *
2110                  * lop and lip reference the first as-yet-unused pathkey elements;
2111                  * it's okay to match them, or any element before them.  If they're
2112                  * NULL then we have found all pathkey elements to be used.
2113                  */
2114                 if (lop)
2115                 {
2116                         opathkey = (PathKey *) lfirst(lop);
2117                         opeclass = opathkey->pk_eclass;
2118                         if (oeclass == opeclass)
2119                         {
2120                                 /* fast path for typical case */
2121                                 lop = lnext(lop);
2122                         }
2123                         else
2124                         {
2125                                 /* redundant clauses ... must match something before lop */
2126                                 foreach(l2, outerpathkeys)
2127                                 {
2128                                         if (l2 == lop)
2129                                                 break;
2130                                         opathkey = (PathKey *) lfirst(l2);
2131                                         opeclass = opathkey->pk_eclass;
2132                                         if (oeclass == opeclass)
2133                                                 break;
2134                                 }
2135                                 if (oeclass != opeclass)
2136                                         elog(ERROR, "outer pathkeys do not match mergeclauses");
2137                         }
2138                 }
2139                 else
2140                 {
2141                         /* redundant clauses ... must match some already-used pathkey */
2142                         opathkey = NULL;
2143                         opeclass = NULL;
2144                         foreach(l2, outerpathkeys)
2145                         {
2146                                 opathkey = (PathKey *) lfirst(l2);
2147                                 opeclass = opathkey->pk_eclass;
2148                                 if (oeclass == opeclass)
2149                                         break;
2150                         }
2151                         if (l2 == NULL)
2152                                 elog(ERROR, "outer pathkeys do not match mergeclauses");
2153                 }
2154
2155                 if (lip)
2156                 {
2157                         ipathkey = (PathKey *) lfirst(lip);
2158                         ipeclass = ipathkey->pk_eclass;
2159                         if (ieclass == ipeclass)
2160                         {
2161                                 /* fast path for typical case */
2162                                 lip = lnext(lip);
2163                         }
2164                         else
2165                         {
2166                                 /* redundant clauses ... must match something before lip */
2167                                 foreach(l2, innerpathkeys)
2168                                 {
2169                                         if (l2 == lip)
2170                                                 break;
2171                                         ipathkey = (PathKey *) lfirst(l2);
2172                                         ipeclass = ipathkey->pk_eclass;
2173                                         if (ieclass == ipeclass)
2174                                                 break;
2175                                 }
2176                                 if (ieclass != ipeclass)
2177                                         elog(ERROR, "inner pathkeys do not match mergeclauses");
2178                         }
2179                 }
2180                 else
2181                 {
2182                         /* redundant clauses ... must match some already-used pathkey */
2183                         ipathkey = NULL;
2184                         ipeclass = NULL;
2185                         foreach(l2, innerpathkeys)
2186                         {
2187                                 ipathkey = (PathKey *) lfirst(l2);
2188                                 ipeclass = ipathkey->pk_eclass;
2189                                 if (ieclass == ipeclass)
2190                                         break;
2191                         }
2192                         if (l2 == NULL)
2193                                 elog(ERROR, "inner pathkeys do not match mergeclauses");
2194                 }
2195
2196                 /* pathkeys should match each other too (more debugging) */
2197                 if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
2198                         opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation ||
2199                         opathkey->pk_strategy != ipathkey->pk_strategy ||
2200                         opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
2201                         elog(ERROR, "left and right pathkeys do not match in mergejoin");
2202
2203                 /* OK, save info for executor */
2204                 mergefamilies[i] = opathkey->pk_opfamily;
2205                 mergecollations[i] = opathkey->pk_eclass->ec_collation;
2206                 mergestrategies[i] = opathkey->pk_strategy;
2207                 mergenullsfirst[i] = opathkey->pk_nulls_first;
2208                 i++;
2209         }
2210
2211         /*
2212          * Note: it is not an error if we have additional pathkey elements (i.e.,
2213          * lop or lip isn't NULL here).  The input paths might be better-sorted
2214          * than we need for the current mergejoin.
2215          */
2216
2217         /*
2218          * Now we can build the mergejoin node.
2219          */
2220         join_plan = make_mergejoin(tlist,
2221                                                            joinclauses,
2222                                                            otherclauses,
2223                                                            mergeclauses,
2224                                                            mergefamilies,
2225                                                            mergecollations,
2226                                                            mergestrategies,
2227                                                            mergenullsfirst,
2228                                                            outer_plan,
2229                                                            inner_plan,
2230                                                            best_path->jpath.jointype);
2231
2232         /* Costs of sort and material steps are included in path cost already */
2233         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
2234
2235         return join_plan;
2236 }
2237
2238 static HashJoin *
2239 create_hashjoin_plan(PlannerInfo *root,
2240                                          HashPath *best_path,
2241                                          Plan *outer_plan,
2242                                          Plan *inner_plan)
2243 {
2244         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
2245         List       *joinclauses;
2246         List       *otherclauses;
2247         List       *hashclauses;
2248         Oid                     skewTable = InvalidOid;
2249         AttrNumber      skewColumn = InvalidAttrNumber;
2250         bool            skewInherit = false;
2251         Oid                     skewColType = InvalidOid;
2252         int32           skewColTypmod = -1;
2253         HashJoin   *join_plan;
2254         Hash       *hash_plan;
2255
2256         /* Sort join qual clauses into best execution order */
2257         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
2258         /* There's no point in sorting the hash clauses ... */
2259
2260         /* Get the join qual clauses (in plain expression form) */
2261         /* Any pseudoconstant clauses are ignored here */
2262         if (IS_OUTER_JOIN(best_path->jpath.jointype))
2263         {
2264                 extract_actual_join_clauses(joinclauses,
2265                                                                         &joinclauses, &otherclauses);
2266         }
2267         else
2268         {
2269                 /* We can treat all clauses alike for an inner join */
2270                 joinclauses = extract_actual_clauses(joinclauses, false);
2271                 otherclauses = NIL;
2272         }
2273
2274         /*
2275          * Remove the hashclauses from the list of join qual clauses, leaving the
2276          * list of quals that must be checked as qpquals.
2277          */
2278         hashclauses = get_actual_clauses(best_path->path_hashclauses);
2279         joinclauses = list_difference(joinclauses, hashclauses);
2280
2281         /*
2282          * Rearrange hashclauses, if needed, so that the outer variable is always
2283          * on the left.
2284          */
2285         hashclauses = get_switched_clauses(best_path->path_hashclauses,
2286                                                          best_path->jpath.outerjoinpath->parent->relids);
2287
2288         /* We don't want any excess columns in the hashed tuples */
2289         disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
2290
2291         /* If we expect batching, suppress excess columns in outer tuples too */
2292         if (best_path->num_batches > 1)
2293                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
2294
2295         /*
2296          * If there is a single join clause and we can identify the outer variable
2297          * as a simple column reference, supply its identity for possible use in
2298          * skew optimization.  (Note: in principle we could do skew optimization
2299          * with multiple join clauses, but we'd have to be able to determine the
2300          * most common combinations of outer values, which we don't currently have
2301          * enough stats for.)
2302          */
2303         if (list_length(hashclauses) == 1)
2304         {
2305                 OpExpr     *clause = (OpExpr *) linitial(hashclauses);
2306                 Node       *node;
2307
2308                 Assert(is_opclause(clause));
2309                 node = (Node *) linitial(clause->args);
2310                 if (IsA(node, RelabelType))
2311                         node = (Node *) ((RelabelType *) node)->arg;
2312                 if (IsA(node, Var))
2313                 {
2314                         Var                *var = (Var *) node;
2315                         RangeTblEntry *rte;
2316
2317                         rte = root->simple_rte_array[var->varno];
2318                         if (rte->rtekind == RTE_RELATION)
2319                         {
2320                                 skewTable = rte->relid;
2321                                 skewColumn = var->varattno;
2322                                 skewInherit = rte->inh;
2323                                 skewColType = var->vartype;
2324                                 skewColTypmod = var->vartypmod;
2325                         }
2326                 }
2327         }
2328
2329         /*
2330          * Build the hash node and hash join node.
2331          */
2332         hash_plan = make_hash(inner_plan,
2333                                                   skewTable,
2334                                                   skewColumn,
2335                                                   skewInherit,
2336                                                   skewColType,
2337                                                   skewColTypmod);
2338         join_plan = make_hashjoin(tlist,
2339                                                           joinclauses,
2340                                                           otherclauses,
2341                                                           hashclauses,
2342                                                           outer_plan,
2343                                                           (Plan *) hash_plan,
2344                                                           best_path->jpath.jointype);
2345
2346         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
2347
2348         return join_plan;
2349 }
2350
2351
2352 /*****************************************************************************
2353  *
2354  *      SUPPORTING ROUTINES
2355  *
2356  *****************************************************************************/
2357
2358 /*
2359  * replace_nestloop_params
2360  *        Replace outer-relation Vars and PlaceHolderVars in the given expression
2361  *        with nestloop Params
2362  *
2363  * All Vars and PlaceHolderVars belonging to the relation(s) identified by
2364  * root->curOuterRels are replaced by Params, and entries are added to
2365  * root->curOuterParams if not already present.
2366  */
2367 static Node *
2368 replace_nestloop_params(PlannerInfo *root, Node *expr)
2369 {
2370         /* No setup needed for tree walk, so away we go */
2371         return replace_nestloop_params_mutator(expr, root);
2372 }
2373
2374 static Node *
2375 replace_nestloop_params_mutator(Node *node, PlannerInfo *root)
2376 {
2377         if (node == NULL)
2378                 return NULL;
2379         if (IsA(node, Var))
2380         {
2381                 Var                *var = (Var *) node;
2382                 Param      *param;
2383                 NestLoopParam *nlp;
2384                 ListCell   *lc;
2385
2386                 /* Upper-level Vars should be long gone at this point */
2387                 Assert(var->varlevelsup == 0);
2388                 /* If not to be replaced, we can just return the Var unmodified */
2389                 if (!bms_is_member(var->varno, root->curOuterRels))
2390                         return node;
2391                 /* Create a Param representing the Var */
2392                 param = assign_nestloop_param_var(root, var);
2393                 /* Is this param already listed in root->curOuterParams? */
2394                 foreach(lc, root->curOuterParams)
2395                 {
2396                         nlp = (NestLoopParam *) lfirst(lc);
2397                         if (nlp->paramno == param->paramid)
2398                         {
2399                                 Assert(equal(var, nlp->paramval));
2400                                 /* Present, so we can just return the Param */
2401                                 return (Node *) param;
2402                         }
2403                 }
2404                 /* No, so add it */
2405                 nlp = makeNode(NestLoopParam);
2406                 nlp->paramno = param->paramid;
2407                 nlp->paramval = var;
2408                 root->curOuterParams = lappend(root->curOuterParams, nlp);
2409                 /* And return the replacement Param */
2410                 return (Node *) param;
2411         }
2412         if (IsA(node, PlaceHolderVar))
2413         {
2414                 PlaceHolderVar *phv = (PlaceHolderVar *) node;
2415                 Param      *param;
2416                 NestLoopParam *nlp;
2417                 ListCell   *lc;
2418
2419                 /* Upper-level PlaceHolderVars should be long gone at this point */
2420                 Assert(phv->phlevelsup == 0);
2421
2422                 /*
2423                  * If not to be replaced, just return the PlaceHolderVar unmodified.
2424                  * We use bms_overlap as a cheap/quick test to see if the PHV might
2425                  * be evaluated in the outer rels, and then grab its PlaceHolderInfo
2426                  * to tell for sure.
2427                  */
2428                 if (!bms_overlap(phv->phrels, root->curOuterRels))
2429                         return node;
2430                 if (!bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
2431                                                    root->curOuterRels))
2432                         return node;
2433                 /* Create a Param representing the PlaceHolderVar */
2434                 param = assign_nestloop_param_placeholdervar(root, phv);
2435                 /* Is this param already listed in root->curOuterParams? */
2436                 foreach(lc, root->curOuterParams)
2437                 {
2438                         nlp = (NestLoopParam *) lfirst(lc);
2439                         if (nlp->paramno == param->paramid)
2440                         {
2441                                 Assert(equal(phv, nlp->paramval));
2442                                 /* Present, so we can just return the Param */
2443                                 return (Node *) param;
2444                         }
2445                 }
2446                 /* No, so add it */
2447                 nlp = makeNode(NestLoopParam);
2448                 nlp->paramno = param->paramid;
2449                 nlp->paramval = (Var *) phv;
2450                 root->curOuterParams = lappend(root->curOuterParams, nlp);
2451                 /* And return the replacement Param */
2452                 return (Node *) param;
2453         }
2454         return expression_tree_mutator(node,
2455                                                                    replace_nestloop_params_mutator,
2456                                                                    (void *) root);
2457 }
2458
2459 /*
2460  * fix_indexqual_references
2461  *        Adjust indexqual clauses to the form the executor's indexqual
2462  *        machinery needs.
2463  *
2464  * We have four tasks here:
2465  *      * Remove RestrictInfo nodes from the input clauses.
2466  *      * Replace any outer-relation Var or PHV nodes with nestloop Params.
2467  *        (XXX eventually, that responsibility should go elsewhere?)
2468  *      * Index keys must be represented by Var nodes with varattno set to the
2469  *        index's attribute number, not the attribute number in the original rel.
2470  *      * If the index key is on the right, commute the clause to put it on the
2471  *        left.
2472  *
2473  * The result is a modified copy of the path's indexquals list --- the
2474  * original is not changed.  Note also that the copy shares no substructure
2475  * with the original; this is needed in case there is a subplan in it (we need
2476  * two separate copies of the subplan tree, or things will go awry).
2477  */
2478 static List *
2479 fix_indexqual_references(PlannerInfo *root, IndexPath *index_path)
2480 {
2481         IndexOptInfo *index = index_path->indexinfo;
2482         List       *fixed_indexquals;
2483         ListCell   *lcc,
2484                            *lci;
2485
2486         fixed_indexquals = NIL;
2487
2488         forboth(lcc, index_path->indexquals, lci, index_path->indexqualcols)
2489         {
2490                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
2491                 int                     indexcol = lfirst_int(lci);
2492                 Node       *clause;
2493
2494                 Assert(IsA(rinfo, RestrictInfo));
2495
2496                 /*
2497                  * Replace any outer-relation variables with nestloop params.
2498                  *
2499                  * This also makes a copy of the clause, so it's safe to modify it
2500                  * in-place below.
2501                  */
2502                 clause = replace_nestloop_params(root, (Node *) rinfo->clause);
2503
2504                 if (IsA(clause, OpExpr))
2505                 {
2506                         OpExpr     *op = (OpExpr *) clause;
2507
2508                         if (list_length(op->args) != 2)
2509                                 elog(ERROR, "indexqual clause is not binary opclause");
2510
2511                         /*
2512                          * Check to see if the indexkey is on the right; if so, commute
2513                          * the clause.  The indexkey should be the side that refers to
2514                          * (only) the base relation.
2515                          */
2516                         if (!bms_equal(rinfo->left_relids, index->rel->relids))
2517                                 CommuteOpExpr(op);
2518
2519                         /*
2520                          * Now replace the indexkey expression with an index Var.
2521                          */
2522                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
2523                                                                                                            index,
2524                                                                                                            indexcol);
2525                 }
2526                 else if (IsA(clause, RowCompareExpr))
2527                 {
2528                         RowCompareExpr *rc = (RowCompareExpr *) clause;
2529                         Expr       *newrc;
2530                         List       *indexcolnos;
2531                         bool            var_on_left;
2532                         ListCell   *lca,
2533                                            *lcai;
2534
2535                         /*
2536                          * Re-discover which index columns are used in the rowcompare.
2537                          */
2538                         newrc = adjust_rowcompare_for_index(rc,
2539                                                                                                 index,
2540                                                                                                 indexcol,
2541                                                                                                 &indexcolnos,
2542                                                                                                 &var_on_left);
2543
2544                         /*
2545                          * Trouble if adjust_rowcompare_for_index thought the
2546                          * RowCompareExpr didn't match the index as-is; the clause should
2547                          * have gone through that routine already.
2548                          */
2549                         if (newrc != (Expr *) rc)
2550                                 elog(ERROR, "inconsistent results from adjust_rowcompare_for_index");
2551
2552                         /*
2553                          * Check to see if the indexkey is on the right; if so, commute
2554                          * the clause.
2555                          */
2556                         if (!var_on_left)
2557                                 CommuteRowCompareExpr(rc);
2558
2559                         /*
2560                          * Now replace the indexkey expressions with index Vars.
2561                          */
2562                         Assert(list_length(rc->largs) == list_length(indexcolnos));
2563                         forboth(lca, rc->largs, lcai, indexcolnos)
2564                         {
2565                                 lfirst(lca) = fix_indexqual_operand(lfirst(lca),
2566                                                                                                         index,
2567                                                                                                         lfirst_int(lcai));
2568                         }
2569                 }
2570                 else if (IsA(clause, ScalarArrayOpExpr))
2571                 {
2572                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
2573
2574                         /* Never need to commute... */
2575
2576                         /* Replace the indexkey expression with an index Var. */
2577                         linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
2578                                                                                                                  index,
2579                                                                                                                  indexcol);
2580                 }
2581                 else if (IsA(clause, NullTest))
2582                 {
2583                         NullTest   *nt = (NullTest *) clause;
2584
2585                         /* Replace the indexkey expression with an index Var. */
2586                         nt->arg = (Expr *) fix_indexqual_operand((Node *) nt->arg,
2587                                                                                                          index,
2588                                                                                                          indexcol);
2589                 }
2590                 else
2591                         elog(ERROR, "unsupported indexqual type: %d",
2592                                  (int) nodeTag(clause));
2593
2594                 fixed_indexquals = lappend(fixed_indexquals, clause);
2595         }
2596
2597         return fixed_indexquals;
2598 }
2599
2600 /*
2601  * fix_indexorderby_references
2602  *        Adjust indexorderby clauses to the form the executor's index
2603  *        machinery needs.
2604  *
2605  * This is a simplified version of fix_indexqual_references.  The input does
2606  * not have RestrictInfo nodes, and we assume that indxpath.c already
2607  * commuted the clauses to put the index keys on the left.      Also, we don't
2608  * bother to support any cases except simple OpExprs, since nothing else
2609  * is allowed for ordering operators.
2610  */
2611 static List *
2612 fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path)
2613 {
2614         IndexOptInfo *index = index_path->indexinfo;
2615         List       *fixed_indexorderbys;
2616         ListCell   *lcc,
2617                            *lci;
2618
2619         fixed_indexorderbys = NIL;
2620
2621         forboth(lcc, index_path->indexorderbys, lci, index_path->indexorderbycols)
2622         {
2623                 Node       *clause = (Node *) lfirst(lcc);
2624                 int                     indexcol = lfirst_int(lci);
2625
2626                 /*
2627                  * Replace any outer-relation variables with nestloop params.
2628                  *
2629                  * This also makes a copy of the clause, so it's safe to modify it
2630                  * in-place below.
2631                  */
2632                 clause = replace_nestloop_params(root, clause);
2633
2634                 if (IsA(clause, OpExpr))
2635                 {
2636                         OpExpr     *op = (OpExpr *) clause;
2637
2638                         if (list_length(op->args) != 2)
2639                                 elog(ERROR, "indexorderby clause is not binary opclause");
2640
2641                         /*
2642                          * Now replace the indexkey expression with an index Var.
2643                          */
2644                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
2645                                                                                                            index,
2646                                                                                                            indexcol);
2647                 }
2648                 else
2649                         elog(ERROR, "unsupported indexorderby type: %d",
2650                                  (int) nodeTag(clause));
2651
2652                 fixed_indexorderbys = lappend(fixed_indexorderbys, clause);
2653         }
2654
2655         return fixed_indexorderbys;
2656 }
2657
2658 /*
2659  * fix_indexqual_operand
2660  *        Convert an indexqual expression to a Var referencing the index column.
2661  *
2662  * We represent index keys by Var nodes having varno == INDEX_VAR and varattno
2663  * equal to the index's attribute number (index column position).
2664  *
2665  * Most of the code here is just for sanity cross-checking that the given
2666  * expression actually matches the index column it's claimed to.
2667  */
2668 static Node *
2669 fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol)
2670 {
2671         Var                *result;
2672         int                     pos;
2673         ListCell   *indexpr_item;
2674
2675         /*
2676          * Remove any binary-compatible relabeling of the indexkey
2677          */
2678         if (IsA(node, RelabelType))
2679                 node = (Node *) ((RelabelType *) node)->arg;
2680
2681         Assert(indexcol >= 0 && indexcol < index->ncolumns);
2682
2683         if (index->indexkeys[indexcol] != 0)
2684         {
2685                 /* It's a simple index column */
2686                 if (IsA(node, Var) &&
2687                         ((Var *) node)->varno == index->rel->relid &&
2688                         ((Var *) node)->varattno == index->indexkeys[indexcol])
2689                 {
2690                         result = (Var *) copyObject(node);
2691                         result->varno = INDEX_VAR;
2692                         result->varattno = indexcol + 1;
2693                         return (Node *) result;
2694                 }
2695                 else
2696                         elog(ERROR, "index key does not match expected index column");
2697         }
2698
2699         /* It's an index expression, so find and cross-check the expression */
2700         indexpr_item = list_head(index->indexprs);
2701         for (pos = 0; pos < index->ncolumns; pos++)
2702         {
2703                 if (index->indexkeys[pos] == 0)
2704                 {
2705                         if (indexpr_item == NULL)
2706                                 elog(ERROR, "too few entries in indexprs list");
2707                         if (pos == indexcol)
2708                         {
2709                                 Node       *indexkey;
2710
2711                                 indexkey = (Node *) lfirst(indexpr_item);
2712                                 if (indexkey && IsA(indexkey, RelabelType))
2713                                         indexkey = (Node *) ((RelabelType *) indexkey)->arg;
2714                                 if (equal(node, indexkey))
2715                                 {
2716                                         result = makeVar(INDEX_VAR, indexcol + 1,
2717                                                                          exprType(lfirst(indexpr_item)), -1,
2718                                                                          exprCollation(lfirst(indexpr_item)),
2719                                                                          0);
2720                                         return (Node *) result;
2721                                 }
2722                                 else
2723                                         elog(ERROR, "index key does not match expected index column");
2724                         }
2725                         indexpr_item = lnext(indexpr_item);
2726                 }
2727         }
2728
2729         /* Ooops... */
2730         elog(ERROR, "index key does not match expected index column");
2731         return NULL;                            /* keep compiler quiet */
2732 }
2733
2734 /*
2735  * get_switched_clauses
2736  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
2737  *        extract the bare clauses, and rearrange the elements within the
2738  *        clauses, if needed, so the outer join variable is on the left and
2739  *        the inner is on the right.  The original clause data structure is not
2740  *        touched; a modified list is returned.  We do, however, set the transient
2741  *        outer_is_left field in each RestrictInfo to show which side was which.
2742  */
2743 static List *
2744 get_switched_clauses(List *clauses, Relids outerrelids)
2745 {
2746         List       *t_list = NIL;
2747         ListCell   *l;
2748
2749         foreach(l, clauses)
2750         {
2751                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2752                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
2753
2754                 Assert(is_opclause(clause));
2755                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
2756                 {
2757                         /*
2758                          * Duplicate just enough of the structure to allow commuting the
2759                          * clause without changing the original list.  Could use
2760                          * copyObject, but a complete deep copy is overkill.
2761                          */
2762                         OpExpr     *temp = makeNode(OpExpr);
2763
2764                         temp->opno = clause->opno;
2765                         temp->opfuncid = InvalidOid;
2766                         temp->opresulttype = clause->opresulttype;
2767                         temp->opretset = clause->opretset;
2768                         temp->opcollid = clause->opcollid;
2769                         temp->inputcollid = clause->inputcollid;
2770                         temp->args = list_copy(clause->args);
2771                         temp->location = clause->location;
2772                         /* Commute it --- note this modifies the temp node in-place. */
2773                         CommuteOpExpr(temp);
2774                         t_list = lappend(t_list, temp);
2775                         restrictinfo->outer_is_left = false;
2776                 }
2777                 else
2778                 {
2779                         Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
2780                         t_list = lappend(t_list, clause);
2781                         restrictinfo->outer_is_left = true;
2782                 }
2783         }
2784         return t_list;
2785 }
2786
2787 /*
2788  * order_qual_clauses
2789  *              Given a list of qual clauses that will all be evaluated at the same
2790  *              plan node, sort the list into the order we want to check the quals
2791  *              in at runtime.
2792  *
2793  * Ideally the order should be driven by a combination of execution cost and
2794  * selectivity, but it's not immediately clear how to account for both,
2795  * and given the uncertainty of the estimates the reliability of the decisions
2796  * would be doubtful anyway.  So we just order by estimated per-tuple cost,
2797  * being careful not to change the order when (as is often the case) the
2798  * estimates are identical.
2799  *
2800  * Although this will work on either bare clauses or RestrictInfos, it's
2801  * much faster to apply it to RestrictInfos, since it can re-use cost
2802  * information that is cached in RestrictInfos.
2803  *
2804  * Note: some callers pass lists that contain entries that will later be
2805  * removed; this is the easiest way to let this routine see RestrictInfos
2806  * instead of bare clauses.  It's OK because we only sort by cost, but
2807  * a cost/selectivity combination would likely do the wrong thing.
2808  */
2809 static List *
2810 order_qual_clauses(PlannerInfo *root, List *clauses)
2811 {
2812         typedef struct
2813         {
2814                 Node       *clause;
2815                 Cost            cost;
2816         } QualItem;
2817         int                     nitems = list_length(clauses);
2818         QualItem   *items;
2819         ListCell   *lc;
2820         int                     i;
2821         List       *result;
2822
2823         /* No need to work hard for 0 or 1 clause */
2824         if (nitems <= 1)
2825                 return clauses;
2826
2827         /*
2828          * Collect the items and costs into an array.  This is to avoid repeated
2829          * cost_qual_eval work if the inputs aren't RestrictInfos.
2830          */
2831         items = (QualItem *) palloc(nitems * sizeof(QualItem));
2832         i = 0;
2833         foreach(lc, clauses)
2834         {
2835                 Node       *clause = (Node *) lfirst(lc);
2836                 QualCost        qcost;
2837
2838                 cost_qual_eval_node(&qcost, clause, root);
2839                 items[i].clause = clause;
2840                 items[i].cost = qcost.per_tuple;
2841                 i++;
2842         }
2843
2844         /*
2845          * Sort.  We don't use qsort() because it's not guaranteed stable for
2846          * equal keys.  The expected number of entries is small enough that a
2847          * simple insertion sort should be good enough.
2848          */
2849         for (i = 1; i < nitems; i++)
2850         {
2851                 QualItem        newitem = items[i];
2852                 int                     j;
2853
2854                 /* insert newitem into the already-sorted subarray */
2855                 for (j = i; j > 0; j--)
2856                 {
2857                         if (newitem.cost >= items[j - 1].cost)
2858                                 break;
2859                         items[j] = items[j - 1];
2860                 }
2861                 items[j] = newitem;
2862         }
2863
2864         /* Convert back to a list */
2865         result = NIL;
2866         for (i = 0; i < nitems; i++)
2867                 result = lappend(result, items[i].clause);
2868
2869         return result;
2870 }
2871
2872 /*
2873  * Copy cost and size info from a Path node to the Plan node created from it.
2874  * The executor usually won't use this info, but it's needed by EXPLAIN.
2875  */
2876 static void
2877 copy_path_costsize(Plan *dest, Path *src)
2878 {
2879         if (src)
2880         {
2881                 dest->startup_cost = src->startup_cost;
2882                 dest->total_cost = src->total_cost;
2883                 dest->plan_rows = src->rows;
2884                 dest->plan_width = src->parent->width;
2885         }
2886         else
2887         {
2888                 dest->startup_cost = 0;
2889                 dest->total_cost = 0;
2890                 dest->plan_rows = 0;
2891                 dest->plan_width = 0;
2892         }
2893 }
2894
2895 /*
2896  * Copy cost and size info from a lower plan node to an inserted node.
2897  * (Most callers alter the info after copying it.)
2898  */
2899 static void
2900 copy_plan_costsize(Plan *dest, Plan *src)
2901 {
2902         if (src)
2903         {
2904                 dest->startup_cost = src->startup_cost;
2905                 dest->total_cost = src->total_cost;
2906                 dest->plan_rows = src->plan_rows;
2907                 dest->plan_width = src->plan_width;
2908         }
2909         else
2910         {
2911                 dest->startup_cost = 0;
2912                 dest->total_cost = 0;
2913                 dest->plan_rows = 0;
2914                 dest->plan_width = 0;
2915         }
2916 }
2917
2918
2919 /*****************************************************************************
2920  *
2921  *      PLAN NODE BUILDING ROUTINES
2922  *
2923  * Some of these are exported because they are called to build plan nodes
2924  * in contexts where we're not deriving the plan node from a path node.
2925  *
2926  *****************************************************************************/
2927
2928 static SeqScan *
2929 make_seqscan(List *qptlist,
2930                          List *qpqual,
2931                          Index scanrelid)
2932 {
2933         SeqScan    *node = makeNode(SeqScan);
2934         Plan       *plan = &node->plan;
2935
2936         /* cost should be inserted by caller */
2937         plan->targetlist = qptlist;
2938         plan->qual = qpqual;
2939         plan->lefttree = NULL;
2940         plan->righttree = NULL;
2941         node->scanrelid = scanrelid;
2942
2943         return node;
2944 }
2945
2946 static IndexScan *
2947 make_indexscan(List *qptlist,
2948                            List *qpqual,
2949                            Index scanrelid,
2950                            Oid indexid,
2951                            List *indexqual,
2952                            List *indexqualorig,
2953                            List *indexorderby,
2954                            List *indexorderbyorig,
2955                            ScanDirection indexscandir)
2956 {
2957         IndexScan  *node = makeNode(IndexScan);
2958         Plan       *plan = &node->scan.plan;
2959
2960         /* cost should be inserted by caller */
2961         plan->targetlist = qptlist;
2962         plan->qual = qpqual;
2963         plan->lefttree = NULL;
2964         plan->righttree = NULL;
2965         node->scan.scanrelid = scanrelid;
2966         node->indexid = indexid;
2967         node->indexqual = indexqual;
2968         node->indexqualorig = indexqualorig;
2969         node->indexorderby = indexorderby;
2970         node->indexorderbyorig = indexorderbyorig;
2971         node->indexorderdir = indexscandir;
2972
2973         return node;
2974 }
2975
2976 static IndexOnlyScan *
2977 make_indexonlyscan(List *qptlist,
2978                                    List *qpqual,
2979                                    Index scanrelid,
2980                                    Oid indexid,
2981                                    List *indexqual,
2982                                    List *indexorderby,
2983                                    List *indextlist,
2984                                    ScanDirection indexscandir)
2985 {
2986         IndexOnlyScan *node = makeNode(IndexOnlyScan);
2987         Plan       *plan = &node->scan.plan;
2988
2989         /* cost should be inserted by caller */
2990         plan->targetlist = qptlist;
2991         plan->qual = qpqual;
2992         plan->lefttree = NULL;
2993         plan->righttree = NULL;
2994         node->scan.scanrelid = scanrelid;
2995         node->indexid = indexid;
2996         node->indexqual = indexqual;
2997         node->indexorderby = indexorderby;
2998         node->indextlist = indextlist;
2999         node->indexorderdir = indexscandir;
3000
3001         return node;
3002 }
3003
3004 static BitmapIndexScan *
3005 make_bitmap_indexscan(Index scanrelid,
3006                                           Oid indexid,
3007                                           List *indexqual,
3008                                           List *indexqualorig)
3009 {
3010         BitmapIndexScan *node = makeNode(BitmapIndexScan);
3011         Plan       *plan = &node->scan.plan;
3012
3013         /* cost should be inserted by caller */
3014         plan->targetlist = NIL;         /* not used */
3015         plan->qual = NIL;                       /* not used */
3016         plan->lefttree = NULL;
3017         plan->righttree = NULL;
3018         node->scan.scanrelid = scanrelid;
3019         node->indexid = indexid;
3020         node->indexqual = indexqual;
3021         node->indexqualorig = indexqualorig;
3022
3023         return node;
3024 }
3025
3026 static BitmapHeapScan *
3027 make_bitmap_heapscan(List *qptlist,
3028                                          List *qpqual,
3029                                          Plan *lefttree,
3030                                          List *bitmapqualorig,
3031                                          Index scanrelid)
3032 {
3033         BitmapHeapScan *node = makeNode(BitmapHeapScan);
3034         Plan       *plan = &node->scan.plan;
3035
3036         /* cost should be inserted by caller */
3037         plan->targetlist = qptlist;
3038         plan->qual = qpqual;
3039         plan->lefttree = lefttree;
3040         plan->righttree = NULL;
3041         node->scan.scanrelid = scanrelid;
3042         node->bitmapqualorig = bitmapqualorig;
3043
3044         return node;
3045 }
3046
3047 static TidScan *
3048 make_tidscan(List *qptlist,
3049                          List *qpqual,
3050                          Index scanrelid,
3051                          List *tidquals)
3052 {
3053         TidScan    *node = makeNode(TidScan);
3054         Plan       *plan = &node->scan.plan;
3055
3056         /* cost should be inserted by caller */
3057         plan->targetlist = qptlist;
3058         plan->qual = qpqual;
3059         plan->lefttree = NULL;
3060         plan->righttree = NULL;
3061         node->scan.scanrelid = scanrelid;
3062         node->tidquals = tidquals;
3063
3064         return node;
3065 }
3066
3067 SubqueryScan *
3068 make_subqueryscan(List *qptlist,
3069                                   List *qpqual,
3070                                   Index scanrelid,
3071                                   Plan *subplan)
3072 {
3073         SubqueryScan *node = makeNode(SubqueryScan);
3074         Plan       *plan = &node->scan.plan;
3075
3076         /*
3077          * Cost is figured here for the convenience of prepunion.c.  Note this is
3078          * only correct for the case where qpqual is empty; otherwise caller
3079          * should overwrite cost with a better estimate.
3080          */
3081         copy_plan_costsize(plan, subplan);
3082         plan->total_cost += cpu_tuple_cost * subplan->plan_rows;
3083
3084         plan->targetlist = qptlist;
3085         plan->qual = qpqual;
3086         plan->lefttree = NULL;
3087         plan->righttree = NULL;
3088         node->scan.scanrelid = scanrelid;
3089         node->subplan = subplan;
3090
3091         return node;
3092 }
3093
3094 static FunctionScan *
3095 make_functionscan(List *qptlist,
3096                                   List *qpqual,
3097                                   Index scanrelid,
3098                                   Node *funcexpr,
3099                                   List *funccolnames,
3100                                   List *funccoltypes,
3101                                   List *funccoltypmods,
3102                                   List *funccolcollations)
3103 {
3104         FunctionScan *node = makeNode(FunctionScan);
3105         Plan       *plan = &node->scan.plan;
3106
3107         /* cost should be inserted by caller */
3108         plan->targetlist = qptlist;
3109         plan->qual = qpqual;
3110         plan->lefttree = NULL;
3111         plan->righttree = NULL;
3112         node->scan.scanrelid = scanrelid;
3113         node->funcexpr = funcexpr;
3114         node->funccolnames = funccolnames;
3115         node->funccoltypes = funccoltypes;
3116         node->funccoltypmods = funccoltypmods;
3117         node->funccolcollations = funccolcollations;
3118
3119         return node;
3120 }
3121
3122 static ValuesScan *
3123 make_valuesscan(List *qptlist,
3124                                 List *qpqual,
3125                                 Index scanrelid,
3126                                 List *values_lists)
3127 {
3128         ValuesScan *node = makeNode(ValuesScan);
3129         Plan       *plan = &node->scan.plan;
3130
3131         /* cost should be inserted by caller */
3132         plan->targetlist = qptlist;
3133         plan->qual = qpqual;
3134         plan->lefttree = NULL;
3135         plan->righttree = NULL;
3136         node->scan.scanrelid = scanrelid;
3137         node->values_lists = values_lists;
3138
3139         return node;
3140 }
3141
3142 static CteScan *
3143 make_ctescan(List *qptlist,
3144                          List *qpqual,
3145                          Index scanrelid,
3146                          int ctePlanId,
3147                          int cteParam)
3148 {
3149         CteScan    *node = makeNode(CteScan);
3150         Plan       *plan = &node->scan.plan;
3151
3152         /* cost should be inserted by caller */
3153         plan->targetlist = qptlist;
3154         plan->qual = qpqual;
3155         plan->lefttree = NULL;
3156         plan->righttree = NULL;
3157         node->scan.scanrelid = scanrelid;
3158         node->ctePlanId = ctePlanId;
3159         node->cteParam = cteParam;
3160
3161         return node;
3162 }
3163
3164 static WorkTableScan *
3165 make_worktablescan(List *qptlist,
3166                                    List *qpqual,
3167                                    Index scanrelid,
3168                                    int wtParam)
3169 {
3170         WorkTableScan *node = makeNode(WorkTableScan);
3171         Plan       *plan = &node->scan.plan;
3172
3173         /* cost should be inserted by caller */
3174         plan->targetlist = qptlist;
3175         plan->qual = qpqual;
3176         plan->lefttree = NULL;
3177         plan->righttree = NULL;
3178         node->scan.scanrelid = scanrelid;
3179         node->wtParam = wtParam;
3180
3181         return node;
3182 }
3183
3184 static ForeignScan *
3185 make_foreignscan(List *qptlist,
3186                                  List *qpqual,
3187                                  Index scanrelid,
3188                                  bool fsSystemCol,
3189                                  FdwPlan *fdwplan)
3190 {
3191         ForeignScan *node = makeNode(ForeignScan);
3192         Plan       *plan = &node->scan.plan;
3193
3194         /* cost should be inserted by caller */
3195         plan->targetlist = qptlist;
3196         plan->qual = qpqual;
3197         plan->lefttree = NULL;
3198         plan->righttree = NULL;
3199         node->scan.scanrelid = scanrelid;
3200         node->fsSystemCol = fsSystemCol;
3201         node->fdwplan = fdwplan;
3202
3203         return node;
3204 }
3205
3206 Append *
3207 make_append(List *appendplans, List *tlist)
3208 {
3209         Append     *node = makeNode(Append);
3210         Plan       *plan = &node->plan;
3211         double          total_size;
3212         ListCell   *subnode;
3213
3214         /*
3215          * Compute cost as sum of subplan costs.  We charge nothing extra for the
3216          * Append itself, which perhaps is too optimistic, but since it doesn't do
3217          * any selection or projection, it is a pretty cheap node.
3218          *
3219          * If you change this, see also create_append_path().  Also, the size
3220          * calculations should match set_append_rel_pathlist().  It'd be better
3221          * not to duplicate all this logic, but some callers of this function
3222          * aren't working from an appendrel or AppendPath, so there's noplace to
3223          * copy the data from.
3224          */
3225         plan->startup_cost = 0;
3226         plan->total_cost = 0;
3227         plan->plan_rows = 0;
3228         total_size = 0;
3229         foreach(subnode, appendplans)
3230         {
3231                 Plan       *subplan = (Plan *) lfirst(subnode);
3232
3233                 if (subnode == list_head(appendplans))  /* first node? */
3234                         plan->startup_cost = subplan->startup_cost;
3235                 plan->total_cost += subplan->total_cost;
3236                 plan->plan_rows += subplan->plan_rows;
3237                 total_size += subplan->plan_width * subplan->plan_rows;
3238         }
3239         if (plan->plan_rows > 0)
3240                 plan->plan_width = rint(total_size / plan->plan_rows);
3241         else
3242                 plan->plan_width = 0;
3243
3244         plan->targetlist = tlist;
3245         plan->qual = NIL;
3246         plan->lefttree = NULL;
3247         plan->righttree = NULL;
3248         node->appendplans = appendplans;
3249
3250         return node;
3251 }
3252
3253 RecursiveUnion *
3254 make_recursive_union(List *tlist,
3255                                          Plan *lefttree,
3256                                          Plan *righttree,
3257                                          int wtParam,
3258                                          List *distinctList,
3259                                          long numGroups)
3260 {
3261         RecursiveUnion *node = makeNode(RecursiveUnion);
3262         Plan       *plan = &node->plan;
3263         int                     numCols = list_length(distinctList);
3264
3265         cost_recursive_union(plan, lefttree, righttree);
3266
3267         plan->targetlist = tlist;
3268         plan->qual = NIL;
3269         plan->lefttree = lefttree;
3270         plan->righttree = righttree;
3271         node->wtParam = wtParam;
3272
3273         /*
3274          * convert SortGroupClause list into arrays of attr indexes and equality
3275          * operators, as wanted by executor
3276          */
3277         node->numCols = numCols;
3278         if (numCols > 0)
3279         {
3280                 int                     keyno = 0;
3281                 AttrNumber *dupColIdx;
3282                 Oid                *dupOperators;
3283                 ListCell   *slitem;
3284
3285                 dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3286                 dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3287
3288                 foreach(slitem, distinctList)
3289                 {
3290                         SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
3291                         TargetEntry *tle = get_sortgroupclause_tle(sortcl,
3292                                                                                                            plan->targetlist);
3293
3294                         dupColIdx[keyno] = tle->resno;
3295                         dupOperators[keyno] = sortcl->eqop;
3296                         Assert(OidIsValid(dupOperators[keyno]));
3297                         keyno++;
3298                 }
3299                 node->dupColIdx = dupColIdx;
3300                 node->dupOperators = dupOperators;
3301         }
3302         node->numGroups = numGroups;
3303
3304         return node;
3305 }
3306
3307 static BitmapAnd *
3308 make_bitmap_and(List *bitmapplans)
3309 {
3310         BitmapAnd  *node = makeNode(BitmapAnd);
3311         Plan       *plan = &node->plan;
3312
3313         /* cost should be inserted by caller */
3314         plan->targetlist = NIL;
3315         plan->qual = NIL;
3316         plan->lefttree = NULL;
3317         plan->righttree = NULL;
3318         node->bitmapplans = bitmapplans;
3319
3320         return node;
3321 }
3322
3323 static BitmapOr *
3324 make_bitmap_or(List *bitmapplans)
3325 {
3326         BitmapOr   *node = makeNode(BitmapOr);
3327         Plan       *plan = &node->plan;
3328
3329         /* cost should be inserted by caller */
3330         plan->targetlist = NIL;
3331         plan->qual = NIL;
3332         plan->lefttree = NULL;
3333         plan->righttree = NULL;
3334         node->bitmapplans = bitmapplans;
3335
3336         return node;
3337 }
3338
3339 static NestLoop *
3340 make_nestloop(List *tlist,
3341                           List *joinclauses,
3342                           List *otherclauses,
3343                           List *nestParams,
3344                           Plan *lefttree,
3345                           Plan *righttree,
3346                           JoinType jointype)
3347 {
3348         NestLoop   *node = makeNode(NestLoop);
3349         Plan       *plan = &node->join.plan;
3350
3351         /* cost should be inserted by caller */
3352         plan->targetlist = tlist;
3353         plan->qual = otherclauses;
3354         plan->lefttree = lefttree;
3355         plan->righttree = righttree;
3356         node->join.jointype = jointype;
3357         node->join.joinqual = joinclauses;
3358         node->nestParams = nestParams;
3359
3360         return node;
3361 }
3362
3363 static HashJoin *
3364 make_hashjoin(List *tlist,
3365                           List *joinclauses,
3366                           List *otherclauses,
3367                           List *hashclauses,
3368                           Plan *lefttree,
3369                           Plan *righttree,
3370                           JoinType jointype)
3371 {
3372         HashJoin   *node = makeNode(HashJoin);
3373         Plan       *plan = &node->join.plan;
3374
3375         /* cost should be inserted by caller */
3376         plan->targetlist = tlist;
3377         plan->qual = otherclauses;
3378         plan->lefttree = lefttree;
3379         plan->righttree = righttree;
3380         node->hashclauses = hashclauses;
3381         node->join.jointype = jointype;
3382         node->join.joinqual = joinclauses;
3383
3384         return node;
3385 }
3386
3387 static Hash *
3388 make_hash(Plan *lefttree,
3389                   Oid skewTable,
3390                   AttrNumber skewColumn,
3391                   bool skewInherit,
3392                   Oid skewColType,
3393                   int32 skewColTypmod)
3394 {
3395         Hash       *node = makeNode(Hash);
3396         Plan       *plan = &node->plan;
3397
3398         copy_plan_costsize(plan, lefttree);
3399
3400         /*
3401          * For plausibility, make startup & total costs equal total cost of input
3402          * plan; this only affects EXPLAIN display not decisions.
3403          */
3404         plan->startup_cost = plan->total_cost;
3405         plan->targetlist = lefttree->targetlist;
3406         plan->qual = NIL;
3407         plan->lefttree = lefttree;
3408         plan->righttree = NULL;
3409
3410         node->skewTable = skewTable;
3411         node->skewColumn = skewColumn;
3412         node->skewInherit = skewInherit;
3413         node->skewColType = skewColType;
3414         node->skewColTypmod = skewColTypmod;
3415
3416         return node;
3417 }
3418
3419 static MergeJoin *
3420 make_mergejoin(List *tlist,
3421                            List *joinclauses,
3422                            List *otherclauses,
3423                            List *mergeclauses,
3424                            Oid *mergefamilies,
3425                            Oid *mergecollations,
3426                            int *mergestrategies,
3427                            bool *mergenullsfirst,
3428                            Plan *lefttree,
3429                            Plan *righttree,
3430                            JoinType jointype)
3431 {
3432         MergeJoin  *node = makeNode(MergeJoin);
3433         Plan       *plan = &node->join.plan;
3434
3435         /* cost should be inserted by caller */
3436         plan->targetlist = tlist;
3437         plan->qual = otherclauses;
3438         plan->lefttree = lefttree;
3439         plan->righttree = righttree;
3440         node->mergeclauses = mergeclauses;
3441         node->mergeFamilies = mergefamilies;
3442         node->mergeCollations = mergecollations;
3443         node->mergeStrategies = mergestrategies;
3444         node->mergeNullsFirst = mergenullsfirst;
3445         node->join.jointype = jointype;
3446         node->join.joinqual = joinclauses;
3447
3448         return node;
3449 }
3450
3451 /*
3452  * make_sort --- basic routine to build a Sort plan node
3453  *
3454  * Caller must have built the sortColIdx, sortOperators, collations, and
3455  * nullsFirst arrays already.
3456  * limit_tuples is as for cost_sort (in particular, pass -1 if no limit)
3457  */
3458 static Sort *
3459 make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
3460                   AttrNumber *sortColIdx, Oid *sortOperators,
3461                   Oid *collations, bool *nullsFirst,
3462                   double limit_tuples)
3463 {
3464         Sort       *node = makeNode(Sort);
3465         Plan       *plan = &node->plan;
3466         Path            sort_path;              /* dummy for result of cost_sort */
3467
3468         copy_plan_costsize(plan, lefttree); /* only care about copying size */
3469         cost_sort(&sort_path, root, NIL,
3470                           lefttree->total_cost,
3471                           lefttree->plan_rows,
3472                           lefttree->plan_width,
3473                           0.0,
3474                           work_mem,
3475                           limit_tuples);
3476         plan->startup_cost = sort_path.startup_cost;
3477         plan->total_cost = sort_path.total_cost;
3478         plan->targetlist = lefttree->targetlist;
3479         plan->qual = NIL;
3480         plan->lefttree = lefttree;
3481         plan->righttree = NULL;
3482         node->numCols = numCols;
3483         node->sortColIdx = sortColIdx;
3484         node->sortOperators = sortOperators;
3485         node->collations = collations;
3486         node->nullsFirst = nullsFirst;
3487
3488         return node;
3489 }
3490
3491 /*
3492  * add_sort_column --- utility subroutine for building sort info arrays
3493  *
3494  * We need this routine because the same column might be selected more than
3495  * once as a sort key column; if so, the extra mentions are redundant.
3496  *
3497  * Caller is assumed to have allocated the arrays large enough for the
3498  * max possible number of columns.      Return value is the new column count.
3499  */
3500 static int
3501 add_sort_column(AttrNumber colIdx, Oid sortOp, Oid coll, bool nulls_first,
3502                                 int numCols, AttrNumber *sortColIdx,
3503                                 Oid *sortOperators, Oid *collations, bool *nullsFirst)
3504 {
3505         int                     i;
3506
3507         Assert(OidIsValid(sortOp));
3508
3509         for (i = 0; i < numCols; i++)
3510         {
3511                 /*
3512                  * Note: we check sortOp because it's conceivable that "ORDER BY foo
3513                  * USING <, foo USING <<<" is not redundant, if <<< distinguishes
3514                  * values that < considers equal.  We need not check nulls_first
3515                  * however because a lower-order column with the same sortop but
3516                  * opposite nulls direction is redundant.
3517                  *
3518                  * We could probably consider sort keys with the same sortop and
3519                  * different collations to be redundant too, but for the moment treat
3520                  * them as not redundant.  This will be needed if we ever support
3521                  * collations with different notions of equality.
3522                  */
3523                 if (sortColIdx[i] == colIdx &&
3524                         sortOperators[numCols] == sortOp &&
3525                         collations[numCols] == coll)
3526                 {
3527                         /* Already sorting by this col, so extra sort key is useless */
3528                         return numCols;
3529                 }
3530         }
3531
3532         /* Add the column */
3533         sortColIdx[numCols] = colIdx;
3534         sortOperators[numCols] = sortOp;
3535         collations[numCols] = coll;
3536         nullsFirst[numCols] = nulls_first;
3537         return numCols + 1;
3538 }
3539
3540 /*
3541  * prepare_sort_from_pathkeys
3542  *        Prepare to sort according to given pathkeys
3543  *
3544  * This is used to set up for both Sort and MergeAppend nodes.  It calculates
3545  * the executor's representation of the sort key information, and adjusts the
3546  * plan targetlist if needed to add resjunk sort columns.
3547  *
3548  * Input parameters:
3549  *        'lefttree' is the node which yields input tuples
3550  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
3551  *        'adjust_tlist_in_place' is TRUE if lefttree must be modified in-place
3552  *
3553  * We must convert the pathkey information into arrays of sort key column
3554  * numbers, sort operator OIDs, collation OIDs, and nulls-first flags,
3555  * which is the representation the executor wants.      These are returned into
3556  * the output parameters *p_numsortkeys etc.
3557  *
3558  * If the pathkeys include expressions that aren't simple Vars, we will
3559  * usually need to add resjunk items to the input plan's targetlist to
3560  * compute these expressions, since the Sort/MergeAppend node itself won't
3561  * do any such calculations.  If the input plan type isn't one that can do
3562  * projections, this means adding a Result node just to do the projection.
3563  * However, the caller can pass adjust_tlist_in_place = TRUE to force the
3564  * lefttree tlist to be modified in-place regardless of whether the node type
3565  * can project --- we use this for fixing the tlist of MergeAppend itself.
3566  *
3567  * Returns the node which is to be the input to the Sort (either lefttree,
3568  * or a Result stacked atop lefttree).
3569  */
3570 static Plan *
3571 prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
3572                                                    bool adjust_tlist_in_place,
3573                                                    int *p_numsortkeys,
3574                                                    AttrNumber **p_sortColIdx,
3575                                                    Oid **p_sortOperators,
3576                                                    Oid **p_collations,
3577                                                    bool **p_nullsFirst)
3578 {
3579         List       *tlist = lefttree->targetlist;
3580         ListCell   *i;
3581         int                     numsortkeys;
3582         AttrNumber *sortColIdx;
3583         Oid                *sortOperators;
3584         Oid                *collations;
3585         bool       *nullsFirst;
3586
3587         /*
3588          * We will need at most list_length(pathkeys) sort columns; possibly less
3589          */
3590         numsortkeys = list_length(pathkeys);
3591         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3592         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3593         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3594         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3595
3596         numsortkeys = 0;
3597
3598         foreach(i, pathkeys)
3599         {
3600                 PathKey    *pathkey = (PathKey *) lfirst(i);
3601                 EquivalenceClass *ec = pathkey->pk_eclass;
3602                 TargetEntry *tle = NULL;
3603                 Oid                     pk_datatype = InvalidOid;
3604                 Oid                     sortop;
3605                 ListCell   *j;
3606
3607                 if (ec->ec_has_volatile)
3608                 {
3609                         /*
3610                          * If the pathkey's EquivalenceClass is volatile, then it must
3611                          * have come from an ORDER BY clause, and we have to match it to
3612                          * that same targetlist entry.
3613                          */
3614                         if (ec->ec_sortref == 0)        /* can't happen */
3615                                 elog(ERROR, "volatile EquivalenceClass has no sortref");
3616                         tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
3617                         Assert(tle);
3618                         Assert(list_length(ec->ec_members) == 1);
3619                         pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
3620                 }
3621                 else
3622                 {
3623                         /*
3624                          * Otherwise, we can sort by any non-constant expression listed in
3625                          * the pathkey's EquivalenceClass.  For now, we take the first one
3626                          * that corresponds to an available item in the tlist.  If there
3627                          * isn't any, use the first one that is an expression in the
3628                          * input's vars.  (The non-const restriction only matters if the
3629                          * EC is below_outer_join; but if it isn't, it won't contain
3630                          * consts anyway, else we'd have discarded the pathkey as
3631                          * redundant.)
3632                          *
3633                          * XXX if we have a choice, is there any way of figuring out which
3634                          * might be cheapest to execute?  (For example, int4lt is likely
3635                          * much cheaper to execute than numericlt, but both might appear
3636                          * in the same equivalence class...)  Not clear that we ever will
3637                          * have an interesting choice in practice, so it may not matter.
3638                          */
3639                         foreach(j, ec->ec_members)
3640                         {
3641                                 EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
3642
3643                                 /*
3644                                  * We shouldn't be trying to sort by an equivalence class that
3645                                  * contains a constant, so no need to consider such cases any
3646                                  * further.
3647                                  */
3648                                 if (em->em_is_const)
3649                                         continue;
3650
3651                                 tle = tlist_member((Node *) em->em_expr, tlist);
3652                                 if (tle)
3653                                 {
3654                                         pk_datatype = em->em_datatype;
3655                                         break;          /* found expr already in tlist */
3656                                 }
3657
3658                                 /*
3659                                  * We can also use it if the pathkey expression is a relabel
3660                                  * of the tlist entry, or vice versa.  This is needed for
3661                                  * binary-compatible cases (cf. make_pathkey_from_sortinfo).
3662                                  * We prefer an exact match, though, so we do the basic search
3663                                  * first.
3664                                  */
3665                                 tle = tlist_member_ignore_relabel((Node *) em->em_expr, tlist);
3666                                 if (tle)
3667                                 {
3668                                         pk_datatype = em->em_datatype;
3669                                         break;          /* found expr already in tlist */
3670                                 }
3671                         }
3672
3673                         if (!tle)
3674                         {
3675                                 /*
3676                                  * No matching tlist item; look for a computable expression.
3677                                  * Note that we treat Aggrefs as if they were variables; this
3678                                  * is necessary when attempting to sort the output from an Agg
3679                                  * node for use in a WindowFunc (since grouping_planner will
3680                                  * have treated the Aggrefs as variables, too).
3681                                  */
3682                                 Expr       *sortexpr = NULL;
3683
3684                                 foreach(j, ec->ec_members)
3685                                 {
3686                                         EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
3687                                         List       *exprvars;
3688                                         ListCell   *k;
3689
3690                                         if (em->em_is_const)
3691                                                 continue;
3692                                         sortexpr = em->em_expr;
3693                                         exprvars = pull_var_clause((Node *) sortexpr,
3694                                                                                            PVC_INCLUDE_AGGREGATES,
3695                                                                                            PVC_INCLUDE_PLACEHOLDERS);
3696                                         foreach(k, exprvars)
3697                                         {
3698                                                 if (!tlist_member_ignore_relabel(lfirst(k), tlist))
3699                                                         break;
3700                                         }
3701                                         list_free(exprvars);
3702                                         if (!k)
3703                                         {
3704                                                 pk_datatype = em->em_datatype;
3705                                                 break;  /* found usable expression */
3706                                         }
3707                                 }
3708                                 if (!j)
3709                                         elog(ERROR, "could not find pathkey item to sort");
3710
3711                                 /*
3712                                  * Do we need to insert a Result node?
3713                                  */
3714                                 if (!adjust_tlist_in_place &&
3715                                         !is_projection_capable_plan(lefttree))
3716                                 {
3717                                         /* copy needed so we don't modify input's tlist below */
3718                                         tlist = copyObject(tlist);
3719                                         lefttree = (Plan *) make_result(root, tlist, NULL,
3720                                                                                                         lefttree);
3721                                 }
3722
3723                                 /* Don't bother testing is_projection_capable_plan again */
3724                                 adjust_tlist_in_place = true;
3725
3726                                 /*
3727                                  * Add resjunk entry to input's tlist
3728                                  */
3729                                 tle = makeTargetEntry(sortexpr,
3730                                                                           list_length(tlist) + 1,
3731                                                                           NULL,
3732                                                                           true);
3733                                 tlist = lappend(tlist, tle);
3734                                 lefttree->targetlist = tlist;   /* just in case NIL before */
3735                         }
3736                 }
3737
3738                 /*
3739                  * Look up the correct sort operator from the PathKey's slightly
3740                  * abstracted representation.
3741                  */
3742                 sortop = get_opfamily_member(pathkey->pk_opfamily,
3743                                                                          pk_datatype,
3744                                                                          pk_datatype,
3745                                                                          pathkey->pk_strategy);
3746                 if (!OidIsValid(sortop))        /* should not happen */
3747                         elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
3748                                  pathkey->pk_strategy, pk_datatype, pk_datatype,
3749                                  pathkey->pk_opfamily);
3750
3751                 /*
3752                  * The column might already be selected as a sort key, if the pathkeys
3753                  * contain duplicate entries.  (This can happen in scenarios where
3754                  * multiple mergejoinable clauses mention the same var, for example.)
3755                  * So enter it only once in the sort arrays.
3756                  */
3757                 numsortkeys = add_sort_column(tle->resno,
3758                                                                           sortop,
3759                                                                           pathkey->pk_eclass->ec_collation,
3760                                                                           pathkey->pk_nulls_first,
3761                                                                           numsortkeys,
3762                                                                           sortColIdx, sortOperators,
3763                                                                           collations, nullsFirst);
3764         }
3765
3766         Assert(numsortkeys > 0);
3767
3768         /* Return results */
3769         *p_numsortkeys = numsortkeys;
3770         *p_sortColIdx = sortColIdx;
3771         *p_sortOperators = sortOperators;
3772         *p_collations = collations;
3773         *p_nullsFirst = nullsFirst;
3774
3775         return lefttree;
3776 }
3777
3778 /*
3779  * make_sort_from_pathkeys
3780  *        Create sort plan to sort according to given pathkeys
3781  *
3782  *        'lefttree' is the node which yields input tuples
3783  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
3784  *        'limit_tuples' is the bound on the number of output tuples;
3785  *                              -1 if no bound
3786  */
3787 Sort *
3788 make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
3789                                                 double limit_tuples)
3790 {
3791         int                     numsortkeys;
3792         AttrNumber *sortColIdx;
3793         Oid                *sortOperators;
3794         Oid                *collations;
3795         bool       *nullsFirst;
3796
3797         /* Compute sort column info, and adjust lefttree as needed */
3798         lefttree = prepare_sort_from_pathkeys(root, lefttree, pathkeys,
3799                                                                                   false,
3800                                                                                   &numsortkeys,
3801                                                                                   &sortColIdx,
3802                                                                                   &sortOperators,
3803                                                                                   &collations,
3804                                                                                   &nullsFirst);
3805
3806         /* Now build the Sort node */
3807         return make_sort(root, lefttree, numsortkeys,
3808                                          sortColIdx, sortOperators, collations,
3809                                          nullsFirst, limit_tuples);
3810 }
3811
3812 /*
3813  * make_sort_from_sortclauses
3814  *        Create sort plan to sort according to given sortclauses
3815  *
3816  *        'sortcls' is a list of SortGroupClauses
3817  *        'lefttree' is the node which yields input tuples
3818  */
3819 Sort *
3820 make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
3821 {
3822         List       *sub_tlist = lefttree->targetlist;
3823         ListCell   *l;
3824         int                     numsortkeys;
3825         AttrNumber *sortColIdx;
3826         Oid                *sortOperators;
3827         Oid                *collations;
3828         bool       *nullsFirst;
3829
3830         /*
3831          * We will need at most list_length(sortcls) sort columns; possibly less
3832          */
3833         numsortkeys = list_length(sortcls);
3834         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3835         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3836         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3837         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3838
3839         numsortkeys = 0;
3840
3841         foreach(l, sortcls)
3842         {
3843                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
3844                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
3845
3846                 /*
3847                  * Check for the possibility of duplicate order-by clauses --- the
3848                  * parser should have removed 'em, but no point in sorting
3849                  * redundantly.
3850                  */
3851                 numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
3852                                                                           exprCollation((Node *) tle->expr),
3853                                                                           sortcl->nulls_first,
3854                                                                           numsortkeys,
3855                                                                           sortColIdx, sortOperators,
3856                                                                           collations, nullsFirst);
3857         }
3858
3859         Assert(numsortkeys > 0);
3860
3861         return make_sort(root, lefttree, numsortkeys,
3862                                          sortColIdx, sortOperators, collations,
3863                                          nullsFirst, -1.0);
3864 }
3865
3866 /*
3867  * make_sort_from_groupcols
3868  *        Create sort plan to sort based on grouping columns
3869  *
3870  * 'groupcls' is the list of SortGroupClauses
3871  * 'grpColIdx' gives the column numbers to use
3872  *
3873  * This might look like it could be merged with make_sort_from_sortclauses,
3874  * but presently we *must* use the grpColIdx[] array to locate sort columns,
3875  * because the child plan's tlist is not marked with ressortgroupref info
3876  * appropriate to the grouping node.  So, only the sort ordering info
3877  * is used from the SortGroupClause entries.
3878  */
3879 Sort *
3880 make_sort_from_groupcols(PlannerInfo *root,
3881                                                  List *groupcls,
3882                                                  AttrNumber *grpColIdx,
3883                                                  Plan *lefttree)
3884 {
3885         List       *sub_tlist = lefttree->targetlist;
3886         int                     grpno = 0;
3887         ListCell   *l;
3888         int                     numsortkeys;
3889         AttrNumber *sortColIdx;
3890         Oid                *sortOperators;
3891         Oid                *collations;
3892         bool       *nullsFirst;
3893
3894         /*
3895          * We will need at most list_length(groupcls) sort columns; possibly less
3896          */
3897         numsortkeys = list_length(groupcls);
3898         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3899         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3900         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3901         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3902
3903         numsortkeys = 0;
3904
3905         foreach(l, groupcls)
3906         {
3907                 SortGroupClause *grpcl = (SortGroupClause *) lfirst(l);
3908                 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
3909
3910                 /*
3911                  * Check for the possibility of duplicate group-by clauses --- the
3912                  * parser should have removed 'em, but no point in sorting
3913                  * redundantly.
3914                  */
3915                 numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
3916                                                                           exprCollation((Node *) tle->expr),
3917                                                                           grpcl->nulls_first,
3918                                                                           numsortkeys,
3919                                                                           sortColIdx, sortOperators,
3920                                                                           collations, nullsFirst);
3921                 grpno++;
3922         }
3923
3924         Assert(numsortkeys > 0);
3925
3926         return make_sort(root, lefttree, numsortkeys,
3927                                          sortColIdx, sortOperators, collations,
3928                                          nullsFirst, -1.0);
3929 }
3930
3931 static Material *
3932 make_material(Plan *lefttree)
3933 {
3934         Material   *node = makeNode(Material);
3935         Plan       *plan = &node->plan;
3936
3937         /* cost should be inserted by caller */
3938         plan->targetlist = lefttree->targetlist;
3939         plan->qual = NIL;
3940         plan->lefttree = lefttree;
3941         plan->righttree = NULL;
3942
3943         return node;
3944 }
3945
3946 /*
3947  * materialize_finished_plan: stick a Material node atop a completed plan
3948  *
3949  * There are a couple of places where we want to attach a Material node
3950  * after completion of subquery_planner().      This currently requires hackery.
3951  * Since subquery_planner has already run SS_finalize_plan on the subplan
3952  * tree, we have to kluge up parameter lists for the Material node.
3953  * Possibly this could be fixed by postponing SS_finalize_plan processing
3954  * until setrefs.c is run?
3955  */
3956 Plan *
3957 materialize_finished_plan(Plan *subplan)
3958 {
3959         Plan       *matplan;
3960         Path            matpath;                /* dummy for result of cost_material */
3961
3962         matplan = (Plan *) make_material(subplan);
3963
3964         /* Set cost data */
3965         cost_material(&matpath,
3966                                   subplan->startup_cost,
3967                                   subplan->total_cost,
3968                                   subplan->plan_rows,
3969                                   subplan->plan_width);
3970         matplan->startup_cost = matpath.startup_cost;
3971         matplan->total_cost = matpath.total_cost;
3972         matplan->plan_rows = subplan->plan_rows;
3973         matplan->plan_width = subplan->plan_width;
3974
3975         /* parameter kluge --- see comments above */
3976         matplan->extParam = bms_copy(subplan->extParam);
3977         matplan->allParam = bms_copy(subplan->allParam);
3978
3979         return matplan;
3980 }
3981
3982 Agg *
3983 make_agg(PlannerInfo *root, List *tlist, List *qual,
3984                  AggStrategy aggstrategy, const AggClauseCosts *aggcosts,
3985                  int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
3986                  long numGroups,
3987                  Plan *lefttree)
3988 {
3989         Agg                *node = makeNode(Agg);
3990         Plan       *plan = &node->plan;
3991         Path            agg_path;               /* dummy for result of cost_agg */
3992         QualCost        qual_cost;
3993
3994         node->aggstrategy = aggstrategy;
3995         node->numCols = numGroupCols;
3996         node->grpColIdx = grpColIdx;
3997         node->grpOperators = grpOperators;
3998         node->numGroups = numGroups;
3999
4000         copy_plan_costsize(plan, lefttree); /* only care about copying size */
4001         cost_agg(&agg_path, root,
4002                          aggstrategy, aggcosts,
4003                          numGroupCols, numGroups,
4004                          lefttree->startup_cost,
4005                          lefttree->total_cost,
4006                          lefttree->plan_rows);
4007         plan->startup_cost = agg_path.startup_cost;
4008         plan->total_cost = agg_path.total_cost;
4009
4010         /*
4011          * We will produce a single output tuple if not grouping, and a tuple per
4012          * group otherwise.
4013          */
4014         if (aggstrategy == AGG_PLAIN)
4015                 plan->plan_rows = 1;
4016         else
4017                 plan->plan_rows = numGroups;
4018
4019         /*
4020          * We also need to account for the cost of evaluation of the qual (ie, the
4021          * HAVING clause) and the tlist.  Note that cost_qual_eval doesn't charge
4022          * anything for Aggref nodes; this is okay since they are really
4023          * comparable to Vars.
4024          *
4025          * See notes in grouping_planner about why only make_agg, make_windowagg
4026          * and make_group worry about tlist eval cost.
4027          */
4028         if (qual)
4029         {
4030                 cost_qual_eval(&qual_cost, qual, root);
4031                 plan->startup_cost += qual_cost.startup;
4032                 plan->total_cost += qual_cost.startup;
4033                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4034         }
4035         cost_qual_eval(&qual_cost, tlist, root);
4036         plan->startup_cost += qual_cost.startup;
4037         plan->total_cost += qual_cost.startup;
4038         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4039
4040         plan->qual = qual;
4041         plan->targetlist = tlist;
4042         plan->lefttree = lefttree;
4043         plan->righttree = NULL;
4044
4045         return node;
4046 }
4047
4048 WindowAgg *
4049 make_windowagg(PlannerInfo *root, List *tlist,
4050                            List *windowFuncs, Index winref,
4051                            int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
4052                            int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators,
4053                            int frameOptions, Node *startOffset, Node *endOffset,
4054                            Plan *lefttree)
4055 {
4056         WindowAgg  *node = makeNode(WindowAgg);
4057         Plan       *plan = &node->plan;
4058         Path            windowagg_path; /* dummy for result of cost_windowagg */
4059         QualCost        qual_cost;
4060
4061         node->winref = winref;
4062         node->partNumCols = partNumCols;
4063         node->partColIdx = partColIdx;
4064         node->partOperators = partOperators;
4065         node->ordNumCols = ordNumCols;
4066         node->ordColIdx = ordColIdx;
4067         node->ordOperators = ordOperators;
4068         node->frameOptions = frameOptions;
4069         node->startOffset = startOffset;
4070         node->endOffset = endOffset;
4071
4072         copy_plan_costsize(plan, lefttree); /* only care about copying size */
4073         cost_windowagg(&windowagg_path, root,
4074                                    windowFuncs, partNumCols, ordNumCols,
4075                                    lefttree->startup_cost,
4076                                    lefttree->total_cost,
4077                                    lefttree->plan_rows);
4078         plan->startup_cost = windowagg_path.startup_cost;
4079         plan->total_cost = windowagg_path.total_cost;
4080
4081         /*
4082          * We also need to account for the cost of evaluation of the tlist.
4083          *
4084          * See notes in grouping_planner about why only make_agg, make_windowagg
4085          * and make_group worry about tlist eval cost.
4086          */
4087         cost_qual_eval(&qual_cost, tlist, root);
4088         plan->startup_cost += qual_cost.startup;
4089         plan->total_cost += qual_cost.startup;
4090         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4091
4092         plan->targetlist = tlist;
4093         plan->lefttree = lefttree;
4094         plan->righttree = NULL;
4095         /* WindowAgg nodes never have a qual clause */
4096         plan->qual = NIL;
4097
4098         return node;
4099 }
4100
4101 Group *
4102 make_group(PlannerInfo *root,
4103                    List *tlist,
4104                    List *qual,
4105                    int numGroupCols,
4106                    AttrNumber *grpColIdx,
4107                    Oid *grpOperators,
4108                    double numGroups,
4109                    Plan *lefttree)
4110 {
4111         Group      *node = makeNode(Group);
4112         Plan       *plan = &node->plan;
4113         Path            group_path;             /* dummy for result of cost_group */
4114         QualCost        qual_cost;
4115
4116         node->numCols = numGroupCols;
4117         node->grpColIdx = grpColIdx;
4118         node->grpOperators = grpOperators;
4119
4120         copy_plan_costsize(plan, lefttree); /* only care about copying size */
4121         cost_group(&group_path, root,
4122                            numGroupCols, numGroups,
4123                            lefttree->startup_cost,
4124                            lefttree->total_cost,
4125                            lefttree->plan_rows);
4126         plan->startup_cost = group_path.startup_cost;
4127         plan->total_cost = group_path.total_cost;
4128
4129         /* One output tuple per estimated result group */
4130         plan->plan_rows = numGroups;
4131
4132         /*
4133          * We also need to account for the cost of evaluation of the qual (ie, the
4134          * HAVING clause) and the tlist.
4135          *
4136          * XXX this double-counts the cost of evaluation of any expressions used
4137          * for grouping, since in reality those will have been evaluated at a
4138          * lower plan level and will only be copied by the Group node. Worth
4139          * fixing?
4140          *
4141          * See notes in grouping_planner about why only make_agg, make_windowagg
4142          * and make_group worry about tlist eval cost.
4143          */
4144         if (qual)
4145         {
4146                 cost_qual_eval(&qual_cost, qual, root);
4147                 plan->startup_cost += qual_cost.startup;
4148                 plan->total_cost += qual_cost.startup;
4149                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4150         }
4151         cost_qual_eval(&qual_cost, tlist, root);
4152         plan->startup_cost += qual_cost.startup;
4153         plan->total_cost += qual_cost.startup;
4154         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4155
4156         plan->qual = qual;
4157         plan->targetlist = tlist;
4158         plan->lefttree = lefttree;
4159         plan->righttree = NULL;
4160
4161         return node;
4162 }
4163
4164 /*
4165  * distinctList is a list of SortGroupClauses, identifying the targetlist items
4166  * that should be considered by the Unique filter.      The input path must
4167  * already be sorted accordingly.
4168  */
4169 Unique *
4170 make_unique(Plan *lefttree, List *distinctList)
4171 {
4172         Unique     *node = makeNode(Unique);
4173         Plan       *plan = &node->plan;
4174         int                     numCols = list_length(distinctList);
4175         int                     keyno = 0;
4176         AttrNumber *uniqColIdx;
4177         Oid                *uniqOperators;
4178         ListCell   *slitem;
4179
4180         copy_plan_costsize(plan, lefttree);
4181
4182         /*
4183          * Charge one cpu_operator_cost per comparison per input tuple. We assume
4184          * all columns get compared at most of the tuples.      (XXX probably this is
4185          * an overestimate.)
4186          */
4187         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
4188
4189         /*
4190          * plan->plan_rows is left as a copy of the input subplan's plan_rows; ie,
4191          * we assume the filter removes nothing.  The caller must alter this if he
4192          * has a better idea.
4193          */
4194
4195         plan->targetlist = lefttree->targetlist;
4196         plan->qual = NIL;
4197         plan->lefttree = lefttree;
4198         plan->righttree = NULL;
4199
4200         /*
4201          * convert SortGroupClause list into arrays of attr indexes and equality
4202          * operators, as wanted by executor
4203          */
4204         Assert(numCols > 0);
4205         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
4206         uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);
4207
4208         foreach(slitem, distinctList)
4209         {
4210                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
4211                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
4212
4213                 uniqColIdx[keyno] = tle->resno;
4214                 uniqOperators[keyno] = sortcl->eqop;
4215                 Assert(OidIsValid(uniqOperators[keyno]));
4216                 keyno++;
4217         }
4218
4219         node->numCols = numCols;
4220         node->uniqColIdx = uniqColIdx;
4221         node->uniqOperators = uniqOperators;
4222
4223         return node;
4224 }
4225
4226 /*
4227  * distinctList is a list of SortGroupClauses, identifying the targetlist
4228  * items that should be considered by the SetOp filter.  The input path must
4229  * already be sorted accordingly.
4230  */
4231 SetOp *
4232 make_setop(SetOpCmd cmd, SetOpStrategy strategy, Plan *lefttree,
4233                    List *distinctList, AttrNumber flagColIdx, int firstFlag,
4234                    long numGroups, double outputRows)
4235 {
4236         SetOp      *node = makeNode(SetOp);
4237         Plan       *plan = &node->plan;
4238         int                     numCols = list_length(distinctList);
4239         int                     keyno = 0;
4240         AttrNumber *dupColIdx;
4241         Oid                *dupOperators;
4242         ListCell   *slitem;
4243
4244         copy_plan_costsize(plan, lefttree);
4245         plan->plan_rows = outputRows;
4246
4247         /*
4248          * Charge one cpu_operator_cost per comparison per input tuple. We assume
4249          * all columns get compared at most of the tuples.
4250          */
4251         plan->total_cost += cpu_operator_cost * lefttree->plan_rows * numCols;
4252
4253         plan->targetlist = lefttree->targetlist;
4254         plan->qual = NIL;
4255         plan->lefttree = lefttree;
4256         plan->righttree = NULL;
4257
4258         /*
4259          * convert SortGroupClause list into arrays of attr indexes and equality
4260          * operators, as wanted by executor
4261          */
4262         Assert(numCols > 0);
4263         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
4264         dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
4265
4266         foreach(slitem, distinctList)
4267         {
4268                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
4269                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
4270
4271                 dupColIdx[keyno] = tle->resno;
4272                 dupOperators[keyno] = sortcl->eqop;
4273                 Assert(OidIsValid(dupOperators[keyno]));
4274                 keyno++;
4275         }
4276
4277         node->cmd = cmd;
4278         node->strategy = strategy;
4279         node->numCols = numCols;
4280         node->dupColIdx = dupColIdx;
4281         node->dupOperators = dupOperators;
4282         node->flagColIdx = flagColIdx;
4283         node->firstFlag = firstFlag;
4284         node->numGroups = numGroups;
4285
4286         return node;
4287 }
4288
4289 /*
4290  * make_lockrows
4291  *        Build a LockRows plan node
4292  */
4293 LockRows *
4294 make_lockrows(Plan *lefttree, List *rowMarks, int epqParam)
4295 {
4296         LockRows   *node = makeNode(LockRows);
4297         Plan       *plan = &node->plan;
4298
4299         copy_plan_costsize(plan, lefttree);
4300
4301         /* charge cpu_tuple_cost to reflect locking costs (underestimate?) */
4302         plan->total_cost += cpu_tuple_cost * plan->plan_rows;
4303
4304         plan->targetlist = lefttree->targetlist;
4305         plan->qual = NIL;
4306         plan->lefttree = lefttree;
4307         plan->righttree = NULL;
4308
4309         node->rowMarks = rowMarks;
4310         node->epqParam = epqParam;
4311
4312         return node;
4313 }
4314
4315 /*
4316  * Note: offset_est and count_est are passed in to save having to repeat
4317  * work already done to estimate the values of the limitOffset and limitCount
4318  * expressions.  Their values are as returned by preprocess_limit (0 means
4319  * "not relevant", -1 means "couldn't estimate").  Keep the code below in sync
4320  * with that function!
4321  */
4322 Limit *
4323 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount,
4324                    int64 offset_est, int64 count_est)
4325 {
4326         Limit      *node = makeNode(Limit);
4327         Plan       *plan = &node->plan;
4328
4329         copy_plan_costsize(plan, lefttree);
4330
4331         /*
4332          * Adjust the output rows count and costs according to the offset/limit.
4333          * This is only a cosmetic issue if we are at top level, but if we are
4334          * building a subquery then it's important to report correct info to the
4335          * outer planner.
4336          *
4337          * When the offset or count couldn't be estimated, use 10% of the
4338          * estimated number of rows emitted from the subplan.
4339          */
4340         if (offset_est != 0)
4341         {
4342                 double          offset_rows;
4343
4344                 if (offset_est > 0)
4345                         offset_rows = (double) offset_est;
4346                 else
4347                         offset_rows = clamp_row_est(lefttree->plan_rows * 0.10);
4348                 if (offset_rows > plan->plan_rows)
4349                         offset_rows = plan->plan_rows;
4350                 if (plan->plan_rows > 0)
4351                         plan->startup_cost +=
4352                                 (plan->total_cost - plan->startup_cost)
4353                                 * offset_rows / plan->plan_rows;
4354                 plan->plan_rows -= offset_rows;
4355                 if (plan->plan_rows < 1)
4356                         plan->plan_rows = 1;
4357         }
4358
4359         if (count_est != 0)
4360         {
4361                 double          count_rows;
4362
4363                 if (count_est > 0)
4364                         count_rows = (double) count_est;
4365                 else
4366                         count_rows = clamp_row_est(lefttree->plan_rows * 0.10);
4367                 if (count_rows > plan->plan_rows)
4368                         count_rows = plan->plan_rows;
4369                 if (plan->plan_rows > 0)
4370                         plan->total_cost = plan->startup_cost +
4371                                 (plan->total_cost - plan->startup_cost)
4372                                 * count_rows / plan->plan_rows;
4373                 plan->plan_rows = count_rows;
4374                 if (plan->plan_rows < 1)
4375                         plan->plan_rows = 1;
4376         }
4377
4378         plan->targetlist = lefttree->targetlist;
4379         plan->qual = NIL;
4380         plan->lefttree = lefttree;
4381         plan->righttree = NULL;
4382
4383         node->limitOffset = limitOffset;
4384         node->limitCount = limitCount;
4385
4386         return node;
4387 }
4388
4389 /*
4390  * make_result
4391  *        Build a Result plan node
4392  *
4393  * If we have a subplan, assume that any evaluation costs for the gating qual
4394  * were already factored into the subplan's startup cost, and just copy the
4395  * subplan cost.  If there's no subplan, we should include the qual eval
4396  * cost.  In either case, tlist eval cost is not to be included here.
4397  */
4398 Result *
4399 make_result(PlannerInfo *root,
4400                         List *tlist,
4401                         Node *resconstantqual,
4402                         Plan *subplan)
4403 {
4404         Result     *node = makeNode(Result);
4405         Plan       *plan = &node->plan;
4406
4407         if (subplan)
4408                 copy_plan_costsize(plan, subplan);
4409         else
4410         {
4411                 plan->startup_cost = 0;
4412                 plan->total_cost = cpu_tuple_cost;
4413                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
4414                 plan->plan_width = 0;   /* XXX is it worth being smarter? */
4415                 if (resconstantqual)
4416                 {
4417                         QualCost        qual_cost;
4418
4419                         cost_qual_eval(&qual_cost, (List *) resconstantqual, root);
4420                         /* resconstantqual is evaluated once at startup */
4421                         plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
4422                         plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
4423                 }
4424         }
4425
4426         plan->targetlist = tlist;
4427         plan->qual = NIL;
4428         plan->lefttree = subplan;
4429         plan->righttree = NULL;
4430         node->resconstantqual = resconstantqual;
4431
4432         return node;
4433 }
4434
4435 /*
4436  * make_modifytable
4437  *        Build a ModifyTable plan node
4438  *
4439  * Currently, we don't charge anything extra for the actual table modification
4440  * work, nor for the RETURNING expressions if any.      It would only be window
4441  * dressing, since these are always top-level nodes and there is no way for
4442  * the costs to change any higher-level planning choices.  But we might want
4443  * to make it look better sometime.
4444  */
4445 ModifyTable *
4446 make_modifytable(CmdType operation, bool canSetTag,
4447                                  List *resultRelations,
4448                                  List *subplans, List *returningLists,
4449                                  List *rowMarks, int epqParam)
4450 {
4451         ModifyTable *node = makeNode(ModifyTable);
4452         Plan       *plan = &node->plan;
4453         double          total_size;
4454         ListCell   *subnode;
4455
4456         Assert(list_length(resultRelations) == list_length(subplans));
4457         Assert(returningLists == NIL ||
4458                    list_length(resultRelations) == list_length(returningLists));
4459
4460         /*
4461          * Compute cost as sum of subplan costs.
4462          */
4463         plan->startup_cost = 0;
4464         plan->total_cost = 0;
4465         plan->plan_rows = 0;
4466         total_size = 0;
4467         foreach(subnode, subplans)
4468         {
4469                 Plan       *subplan = (Plan *) lfirst(subnode);
4470
4471                 if (subnode == list_head(subplans))             /* first node? */
4472                         plan->startup_cost = subplan->startup_cost;
4473                 plan->total_cost += subplan->total_cost;
4474                 plan->plan_rows += subplan->plan_rows;
4475                 total_size += subplan->plan_width * subplan->plan_rows;
4476         }
4477         if (plan->plan_rows > 0)
4478                 plan->plan_width = rint(total_size / plan->plan_rows);
4479         else
4480                 plan->plan_width = 0;
4481
4482         node->plan.lefttree = NULL;
4483         node->plan.righttree = NULL;
4484         node->plan.qual = NIL;
4485
4486         /*
4487          * Set up the visible plan targetlist as being the same as the first
4488          * RETURNING list.      This is for the use of EXPLAIN; the executor won't pay
4489          * any attention to the targetlist.
4490          */
4491         if (returningLists)
4492                 node->plan.targetlist = copyObject(linitial(returningLists));
4493         else
4494                 node->plan.targetlist = NIL;
4495
4496         node->operation = operation;
4497         node->canSetTag = canSetTag;
4498         node->resultRelations = resultRelations;
4499         node->resultRelIndex = -1;      /* will be set correctly in setrefs.c */
4500         node->plans = subplans;
4501         node->returningLists = returningLists;
4502         node->rowMarks = rowMarks;
4503         node->epqParam = epqParam;
4504
4505         return node;
4506 }
4507
4508 /*
4509  * is_projection_capable_plan
4510  *              Check whether a given Plan node is able to do projection.
4511  */
4512 bool
4513 is_projection_capable_plan(Plan *plan)
4514 {
4515         /* Most plan types can project, so just list the ones that can't */
4516         switch (nodeTag(plan))
4517         {
4518                 case T_Hash:
4519                 case T_Material:
4520                 case T_Sort:
4521                 case T_Unique:
4522                 case T_SetOp:
4523                 case T_LockRows:
4524                 case T_Limit:
4525                 case T_ModifyTable:
4526                 case T_Append:
4527                 case T_MergeAppend:
4528                 case T_RecursiveUnion:
4529                         return false;
4530                 default:
4531                         break;
4532         }
4533         return true;
4534 }