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