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