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