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-2017, 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/extensible.h"
  28 #include "nodes/makefuncs.h"
  29 #include "nodes/nodeFuncs.h"
  30 #include "optimizer/clauses.h"
  31 #include "optimizer/cost.h"
  32 #include "optimizer/paths.h"
  33 #include "optimizer/placeholder.h"
  34 #include "optimizer/plancat.h"
  35 #include "optimizer/planmain.h"
  36 #include "optimizer/planner.h"
  37 #include "optimizer/predtest.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 /*
  48  * Flag bits that can appear in the flags argument of create_plan_recurse().
  49  * These can be OR-ed together.
  50  *
  51  * CP_EXACT_TLIST specifies that the generated plan node must return exactly
  52  * the tlist specified by the path's pathtarget (this overrides both
  53  * CP_SMALL_TLIST and CP_LABEL_TLIST, if those are set).  Otherwise, the
  54  * plan node is allowed to return just the Vars and PlaceHolderVars needed
  55  * to evaluate the pathtarget.
  56  *
  57  * CP_SMALL_TLIST specifies that a narrower tlist is preferred.  This is
  58  * passed down by parent nodes such as Sort and Hash, which will have to
  59  * store the returned tuples.
  60  *
  61  * CP_LABEL_TLIST specifies that the plan node must return columns matching
  62  * any sortgrouprefs specified in its pathtarget, with appropriate
  63  * ressortgroupref labels.  This is passed down by parent nodes such as Sort
  64  * and Group, which need these values to be available in their inputs.
  65  */
  66 #define CP_EXACT_TLIST          0x0001          /* Plan must return specified tlist */
  67 #define CP_SMALL_TLIST          0x0002          /* Prefer narrower tlists */
  68 #define CP_LABEL_TLIST          0x0004          /* tlist must contain sortgrouprefs */
  69
  70
  71 static Plan *create_plan_recurse(PlannerInfo *root, Path *best_path,
  72                                         int flags);
  73 static Plan *create_scan_plan(PlannerInfo *root, Path *best_path,
  74                                  int flags);
  75 static List *build_path_tlist(PlannerInfo *root, Path *path);
  76 static bool use_physical_tlist(PlannerInfo *root, Path *path, int flags);
  77 static List *get_gating_quals(PlannerInfo *root, List *quals);
  78 static Plan *create_gating_plan(PlannerInfo *root, Path *path, Plan *plan,
  79                                    List *gating_quals);
  80 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
  81 static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
  82 static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path);
  83 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
  84 static ProjectSet *create_project_set_plan(PlannerInfo *root, ProjectSetPath *best_path);
  85 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path,
  86                                          int flags);
  87 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path,
  88                                    int flags);
  89 static Gather *create_gather_plan(PlannerInfo *root, GatherPath *best_path);
  90 static Plan *create_projection_plan(PlannerInfo *root, ProjectionPath *best_path);
  91 static Plan *inject_projection_plan(Plan *subplan, List *tlist);
  92 static Sort *create_sort_plan(PlannerInfo *root, SortPath *best_path, int flags);
  93 static Group *create_group_plan(PlannerInfo *root, GroupPath *best_path);
  94 static Unique *create_upper_unique_plan(PlannerInfo *root, UpperUniquePath *best_path,
  95                                                  int flags);
  96 static Agg *create_agg_plan(PlannerInfo *root, AggPath *best_path);
  97 static Plan *create_groupingsets_plan(PlannerInfo *root, GroupingSetsPath *best_path);
  98 static Result *create_minmaxagg_plan(PlannerInfo *root, MinMaxAggPath *best_path);
  99 static WindowAgg *create_windowagg_plan(PlannerInfo *root, WindowAggPath *best_path);
 100 static SetOp *create_setop_plan(PlannerInfo *root, SetOpPath *best_path,
 101                                   int flags);
 102 static RecursiveUnion *create_recursiveunion_plan(PlannerInfo *root, RecursiveUnionPath *best_path);
 103 static void get_column_info_for_window(PlannerInfo *root, WindowClause *wc,
 104                                                    List *tlist,
 105                                                    int numSortCols, AttrNumber *sortColIdx,
 106                                                    int *partNumCols,
 107                                                    AttrNumber **partColIdx,
 108                                                    Oid **partOperators,
 109                                                    int *ordNumCols,
 110                                                    AttrNumber **ordColIdx,
 111                                                    Oid **ordOperators);
 112 static LockRows *create_lockrows_plan(PlannerInfo *root, LockRowsPath *best_path,
 113                                          int flags);
 114 static ModifyTable *create_modifytable_plan(PlannerInfo *root, ModifyTablePath *best_path);
 115 static Limit *create_limit_plan(PlannerInfo *root, LimitPath *best_path,
 116                                   int flags);
 117 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
 118                                         List *tlist, List *scan_clauses);
 119 static SampleScan *create_samplescan_plan(PlannerInfo *root, Path *best_path,
 120                                            List *tlist, List *scan_clauses);
 121 static Scan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
 122                                           List *tlist, List *scan_clauses, bool indexonly);
 123 static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
 124                                                 BitmapHeapPath *best_path,
 125                                                 List *tlist, List *scan_clauses);
 126 static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
 127                                           List **qual, List **indexqual, List **indexECs);
 128 static void bitmap_subplan_mark_shared(Plan *plan);
 129 static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 130                                         List *tlist, List *scan_clauses);
 131 static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root,
 132                                                  SubqueryScanPath *best_path,
 133                                                  List *tlist, List *scan_clauses);
 134 static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
 135                                                  List *tlist, List *scan_clauses);
 136 static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
 137                                            List *tlist, List *scan_clauses);
 138 static TableFuncScan *create_tablefuncscan_plan(PlannerInfo *root, Path *best_path,
 139                                                   List *tlist, List *scan_clauses);
 140 static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path,
 141                                         List *tlist, List *scan_clauses);
 142 static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path,
 143                                                   List *tlist, List *scan_clauses);
 144 static ForeignScan *create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
 145                                                 List *tlist, List *scan_clauses);
 146 static CustomScan *create_customscan_plan(PlannerInfo *root,
 147                                            CustomPath *best_path,
 148                                            List *tlist, List *scan_clauses);
 149 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path);
 150 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path);
 151 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path);
 152 static Node *replace_nestloop_params(PlannerInfo *root, Node *expr);
 153 static Node *replace_nestloop_params_mutator(Node *node, PlannerInfo *root);
 154 static void process_subquery_nestloop_params(PlannerInfo *root,
 155                                                                  List *subplan_params);
 156 static List *fix_indexqual_references(PlannerInfo *root, IndexPath *index_path);
 157 static List *fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path);
 158 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol);
 159 static List *get_switched_clauses(List *clauses, Relids outerrelids);
 160 static List *order_qual_clauses(PlannerInfo *root, List *clauses);
 161 static void copy_generic_path_info(Plan *dest, Path *src);
 162 static void copy_plan_costsize(Plan *dest, Plan *src);
 163 static void label_sort_with_costsize(PlannerInfo *root, Sort *plan,
 164                                                  double limit_tuples);
 165 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
 166 static SampleScan *make_samplescan(List *qptlist, List *qpqual, Index scanrelid,
 167                                 TableSampleClause *tsc);
 168 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
 169                            Oid indexid, List *indexqual, List *indexqualorig,
 170                            List *indexorderby, List *indexorderbyorig,
 171                            List *indexorderbyops,
 172                            ScanDirection indexscandir);
 173 static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual,
 174                                    Index scanrelid, Oid indexid,
 175                                    List *indexqual, List *indexorderby,
 176                                    List *indextlist,
 177                                    ScanDirection indexscandir);
 178 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
 179                                           List *indexqual,
 180                                           List *indexqualorig);
 181 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
 182                                          List *qpqual,
 183                                          Plan *lefttree,
 184                                          List *bitmapqualorig,
 185                                          Index scanrelid);
 186 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
 187                          List *tidquals);
 188 static SubqueryScan *make_subqueryscan(List *qptlist,
 189                                   List *qpqual,
 190                                   Index scanrelid,
 191                                   Plan *subplan);
 192 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
 193                                   Index scanrelid, List *functions, bool funcordinality);
 194 static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
 195                                 Index scanrelid, List *values_lists);
 196 static TableFuncScan *make_tablefuncscan(List *qptlist, List *qpqual,
 197                                    Index scanrelid, TableFunc *tablefunc);
 198 static CteScan *make_ctescan(List *qptlist, List *qpqual,
 199                          Index scanrelid, int ctePlanId, int cteParam);
 200 static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
 201                                    Index scanrelid, int wtParam);
 202 static Append *make_append(List *appendplans, List *tlist);
 203 static RecursiveUnion *make_recursive_union(List *tlist,
 204                                          Plan *lefttree,
 205                                          Plan *righttree,
 206                                          int wtParam,
 207                                          List *distinctList,
 208                                          long numGroups);
 209 static BitmapAnd *make_bitmap_and(List *bitmapplans);
 210 static BitmapOr *make_bitmap_or(List *bitmapplans);
 211 static NestLoop *make_nestloop(List *tlist,
 212                           List *joinclauses, List *otherclauses, List *nestParams,
 213                           Plan *lefttree, Plan *righttree,
 214                           JoinType jointype);
 215 static HashJoin *make_hashjoin(List *tlist,
 216                           List *joinclauses, List *otherclauses,
 217                           List *hashclauses,
 218                           Plan *lefttree, Plan *righttree,
 219                           JoinType jointype);
 220 static Hash *make_hash(Plan *lefttree,
 221                   Oid skewTable,
 222                   AttrNumber skewColumn,
 223                   bool skewInherit,
 224                   Oid skewColType,
 225                   int32 skewColTypmod);
 226 static MergeJoin *make_mergejoin(List *tlist,
 227                            List *joinclauses, List *otherclauses,
 228                            List *mergeclauses,
 229                            Oid *mergefamilies,
 230                            Oid *mergecollations,
 231                            int *mergestrategies,
 232                            bool *mergenullsfirst,
 233                            Plan *lefttree, Plan *righttree,
 234                            JoinType jointype);
 235 static Sort *make_sort(Plan *lefttree, int numCols,
 236                   AttrNumber *sortColIdx, Oid *sortOperators,
 237                   Oid *collations, bool *nullsFirst);
 238 static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
 239                                                    Relids relids,
 240                                                    const AttrNumber *reqColIdx,
 241                                                    bool adjust_tlist_in_place,
 242                                                    int *p_numsortkeys,
 243                                                    AttrNumber **p_sortColIdx,
 244                                                    Oid **p_sortOperators,
 245                                                    Oid **p_collations,
 246                                                    bool **p_nullsFirst);
 247 static EquivalenceMember *find_ec_member_for_tle(EquivalenceClass *ec,
 248                                            TargetEntry *tle,
 249                                            Relids relids);
 250 static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys);
 251 static Sort *make_sort_from_groupcols(List *groupcls,
 252                                                  AttrNumber *grpColIdx,
 253                                                  Plan *lefttree);
 254 static Material *make_material(Plan *lefttree);
 255 static WindowAgg *make_windowagg(List *tlist, Index winref,
 256                            int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
 257                            int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators,
 258                            int frameOptions, Node *startOffset, Node *endOffset,
 259                            Plan *lefttree);
 260 static Group *make_group(List *tlist, List *qual, int numGroupCols,
 261                    AttrNumber *grpColIdx, Oid *grpOperators,
 262                    Plan *lefttree);
 263 static Unique *make_unique_from_sortclauses(Plan *lefttree, List *distinctList);
 264 static Unique *make_unique_from_pathkeys(Plan *lefttree,
 265                                                   List *pathkeys, int numCols);
 266 static Gather *make_gather(List *qptlist, List *qpqual,
 267                         int nworkers, bool single_copy, Plan *subplan);
 268 static SetOp *make_setop(SetOpCmd cmd, SetOpStrategy strategy, Plan *lefttree,
 269                    List *distinctList, AttrNumber flagColIdx, int firstFlag,
 270                    long numGroups);
 271 static LockRows *make_lockrows(Plan *lefttree, List *rowMarks, int epqParam);
 272 static Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan);
 273 static ProjectSet *make_project_set(List *tlist, Plan *subplan);
 274 static ModifyTable *make_modifytable(PlannerInfo *root,
 275                                  CmdType operation, bool canSetTag,
 276                                  Index nominalRelation,
 277                                  List *resultRelations, List *subplans,
 278                                  List *withCheckOptionLists, List *returningLists,
 279                                  List *rowMarks, OnConflictExpr *onconflict, int epqParam);
 280 static GatherMerge *create_gather_merge_plan(PlannerInfo *root,
 281                                                  GatherMergePath *best_path);
 282
 283
 284 /*
 285  * create_plan
 286  *        Creates the access plan for a query by recursively processing the
 287  *        desired tree of pathnodes, starting at the node 'best_path'.  For
 288  *        every pathnode found, we create a corresponding plan node containing
 289  *        appropriate id, target list, and qualification information.
 290  *
 291  *        The tlists and quals in the plan tree are still in planner format,
 292  *        ie, Vars still correspond to the parser's numbering.  This will be
 293  *        fixed later by setrefs.c.
 294  *
 295  *        best_path is the best access path
 296  *
 297  *        Returns a Plan tree.
 298  */
 299 Plan *
 300 create_plan(PlannerInfo *root, Path *best_path)
 301 {
 302         Plan       *plan;
 303
 304         /* plan_params should not be in use in current query level */
 305         Assert(root->plan_params == NIL);
 306
 307         /* Initialize this module's private workspace in PlannerInfo */
 308         root->curOuterRels = NULL;
 309         root->curOuterParams = NIL;
 310
 311         /* Recursively process the path tree, demanding the correct tlist result */
 312         plan = create_plan_recurse(root, best_path, CP_EXACT_TLIST);
 313
 314         /*
 315          * Make sure the topmost plan node's targetlist exposes the original
 316          * column names and other decorative info.  Targetlists generated within
 317          * the planner don't bother with that stuff, but we must have it on the
 318          * top-level tlist seen at execution time.  However, ModifyTable plan
 319          * nodes don't have a tlist matching the querytree targetlist.
 320          */
 321         if (!IsA(plan, ModifyTable))
 322                 apply_tlist_labeling(plan->targetlist, root->processed_tlist);
 323
 324         /*
 325          * Attach any initPlans created in this query level to the topmost plan
 326          * node.  (In principle the initplans could go in any plan node at or
 327          * above where they're referenced, but there seems no reason to put them
 328          * any lower than the topmost node for the query level.  Also, see
 329          * comments for SS_finalize_plan before you try to change this.)
 330          */
 331         SS_attach_initplans(root, plan);
 332
 333         /* Check we successfully assigned all NestLoopParams to plan nodes */
 334         if (root->curOuterParams != NIL)
 335                 elog(ERROR, "failed to assign all NestLoopParams to plan nodes");
 336
 337         /*
 338          * Reset plan_params to ensure param IDs used for nestloop params are not
 339          * re-used later
 340          */
 341         root->plan_params = NIL;
 342
 343         return plan;
 344 }
 345
 346 /*
 347  * create_plan_recurse
 348  *        Recursive guts of create_plan().
 349  */
 350 static Plan *
 351 create_plan_recurse(PlannerInfo *root, Path *best_path, int flags)
 352 {
 353         Plan       *plan;
 354
 355         switch (best_path->pathtype)
 356         {
 357                 case T_SeqScan:
 358                 case T_SampleScan:
 359                 case T_IndexScan:
 360                 case T_IndexOnlyScan:
 361                 case T_BitmapHeapScan:
 362                 case T_TidScan:
 363                 case T_SubqueryScan:
 364                 case T_FunctionScan:
 365                 case T_TableFuncScan:
 366                 case T_ValuesScan:
 367                 case T_CteScan:
 368                 case T_WorkTableScan:
 369                 case T_ForeignScan:
 370                 case T_CustomScan:
 371                         plan = create_scan_plan(root, best_path, flags);
 372                         break;
 373                 case T_HashJoin:
 374                 case T_MergeJoin:
 375                 case T_NestLoop:
 376                         plan = create_join_plan(root,
 377                                                                         (JoinPath *) best_path);
 378                         break;
 379                 case T_Append:
 380                         plan = create_append_plan(root,
 381                                                                           (AppendPath *) best_path);
 382                         break;
 383                 case T_MergeAppend:
 384                         plan = create_merge_append_plan(root,
 385                                                                                         (MergeAppendPath *) best_path);
 386                         break;
 387                 case T_Result:
 388                         if (IsA(best_path, ProjectionPath))
 389                         {
 390                                 plan = create_projection_plan(root,
 391                                                                                           (ProjectionPath *) best_path);
 392                         }
 393                         else if (IsA(best_path, MinMaxAggPath))
 394                         {
 395                                 plan = (Plan *) create_minmaxagg_plan(root,
 396                                                                                                 (MinMaxAggPath *) best_path);
 397                         }
 398                         else
 399                         {
 400                                 Assert(IsA(best_path, ResultPath));
 401                                 plan = (Plan *) create_result_plan(root,
 402                                                                                                    (ResultPath *) best_path);
 403                         }
 404                         break;
 405                 case T_ProjectSet:
 406                         plan = (Plan *) create_project_set_plan(root,
 407                                                                                            (ProjectSetPath *) best_path);
 408                         break;
 409                 case T_Material:
 410                         plan = (Plan *) create_material_plan(root,
 411                                                                                                  (MaterialPath *) best_path,
 412                                                                                                  flags);
 413                         break;
 414                 case T_Unique:
 415                         if (IsA(best_path, UpperUniquePath))
 416                         {
 417                                 plan = (Plan *) create_upper_unique_plan(root,
 418                                                                                            (UpperUniquePath *) best_path,
 419                                                                                                                  flags);
 420                         }
 421                         else
 422                         {
 423                                 Assert(IsA(best_path, UniquePath));
 424                                 plan = create_unique_plan(root,
 425                                                                                   (UniquePath *) best_path,
 426                                                                                   flags);
 427                         }
 428                         break;
 429                 case T_Gather:
 430                         plan = (Plan *) create_gather_plan(root,
 431                                                                                            (GatherPath *) best_path);
 432                         break;
 433                 case T_Sort:
 434                         plan = (Plan *) create_sort_plan(root,
 435                                                                                          (SortPath *) best_path,
 436                                                                                          flags);
 437                         break;
 438                 case T_Group:
 439                         plan = (Plan *) create_group_plan(root,
 440                                                                                           (GroupPath *) best_path);
 441                         break;
 442                 case T_Agg:
 443                         if (IsA(best_path, GroupingSetsPath))
 444                                 plan = create_groupingsets_plan(root,
 445                                                                                          (GroupingSetsPath *) best_path);
 446                         else
 447                         {
 448                                 Assert(IsA(best_path, AggPath));
 449                                 plan = (Plan *) create_agg_plan(root,
 450                                                                                                 (AggPath *) best_path);
 451                         }
 452                         break;
 453                 case T_WindowAgg:
 454                         plan = (Plan *) create_windowagg_plan(root,
 455                                                                                                 (WindowAggPath *) best_path);
 456                         break;
 457                 case T_SetOp:
 458                         plan = (Plan *) create_setop_plan(root,
 459                                                                                           (SetOpPath *) best_path,
 460                                                                                           flags);
 461                         break;
 462                 case T_RecursiveUnion:
 463                         plan = (Plan *) create_recursiveunion_plan(root,
 464                                                                                    (RecursiveUnionPath *) best_path);
 465                         break;
 466                 case T_LockRows:
 467                         plan = (Plan *) create_lockrows_plan(root,
 468                                                                                                  (LockRowsPath *) best_path,
 469                                                                                                  flags);
 470                         break;
 471                 case T_ModifyTable:
 472                         plan = (Plan *) create_modifytable_plan(root,
 473                                                                                           (ModifyTablePath *) best_path);
 474                         break;
 475                 case T_Limit:
 476                         plan = (Plan *) create_limit_plan(root,
 477                                                                                           (LimitPath *) best_path,
 478                                                                                           flags);
 479                         break;
 480                 case T_GatherMerge:
 481                         plan = (Plan *) create_gather_merge_plan(root,
 482                                                                                           (GatherMergePath *) best_path);
 483                         break;
 484                 default:
 485                         elog(ERROR, "unrecognized node type: %d",
 486                                  (int) best_path->pathtype);
 487                         plan = NULL;            /* keep compiler quiet */
 488                         break;
 489         }
 490
 491         return plan;
 492 }
 493
 494 /*
 495  * create_scan_plan
 496  *       Create a scan plan for the parent relation of 'best_path'.
 497  */
 498 static Plan *
 499 create_scan_plan(PlannerInfo *root, Path *best_path, int flags)
 500 {
 501         RelOptInfo *rel = best_path->parent;
 502         List       *scan_clauses;
 503         List       *gating_clauses;
 504         List       *tlist;
 505         Plan       *plan;
 506
 507         /*
 508          * Extract the relevant restriction clauses from the parent relation. The
 509          * executor must apply all these restrictions during the scan, except for
 510          * pseudoconstants which we'll take care of below.
 511          *
 512          * If this is a plain indexscan or index-only scan, we need not consider
 513          * restriction clauses that are implied by the index's predicate, so use
 514          * indrestrictinfo not baserestrictinfo.  Note that we can't do that for
 515          * bitmap indexscans, since there's not necessarily a single index
 516          * involved; but it doesn't matter since create_bitmap_scan_plan() will be
 517          * able to get rid of such clauses anyway via predicate proof.
 518          */
 519         switch (best_path->pathtype)
 520         {
 521                 case T_IndexScan:
 522                 case T_IndexOnlyScan:
 523                         scan_clauses = castNode(IndexPath, best_path)->indexinfo->indrestrictinfo;
 524                         break;
 525                 default:
 526                         scan_clauses = rel->baserestrictinfo;
 527                         break;
 528         }
 529
 530         /*
 531          * If this is a parameterized scan, we also need to enforce all the join
 532          * clauses available from the outer relation(s).
 533          *
 534          * For paranoia's sake, don't modify the stored baserestrictinfo list.
 535          */
 536         if (best_path->param_info)
 537                 scan_clauses = list_concat(list_copy(scan_clauses),
 538                                                                    best_path->param_info->ppi_clauses);
 539
 540         /*
 541          * Detect whether we have any pseudoconstant quals to deal with.  Then, if
 542          * we'll need a gating Result node, it will be able to project, so there
 543          * are no requirements on the child's tlist.
 544          */
 545         gating_clauses = get_gating_quals(root, scan_clauses);
 546         if (gating_clauses)
 547                 flags = 0;
 548
 549         /*
 550          * For table scans, rather than using the relation targetlist (which is
 551          * only those Vars actually needed by the query), we prefer to generate a
 552          * tlist containing all Vars in order.  This will allow the executor to
 553          * optimize away projection of the table tuples, if possible.
 554          */
 555         if (use_physical_tlist(root, best_path, flags))
 556         {
 557                 if (best_path->pathtype == T_IndexOnlyScan)
 558                 {
 559                         /* For index-only scan, the preferred tlist is the index's */
 560                         tlist = copyObject(((IndexPath *) best_path)->indexinfo->indextlist);
 561
 562                         /*
 563                          * Transfer any sortgroupref data to the replacement tlist, unless
 564                          * we don't care because the gating Result will handle it.
 565                          */
 566                         if (!gating_clauses)
 567                                 apply_pathtarget_labeling_to_tlist(tlist, best_path->pathtarget);
 568                 }
 569                 else
 570                 {
 571                         tlist = build_physical_tlist(root, rel);
 572                         if (tlist == NIL)
 573                         {
 574                                 /* Failed because of dropped cols, so use regular method */
 575                                 tlist = build_path_tlist(root, best_path);
 576                         }
 577                         else
 578                         {
 579                                 /* As above, transfer sortgroupref data to replacement tlist */
 580                                 if (!gating_clauses)
 581                                         apply_pathtarget_labeling_to_tlist(tlist, best_path->pathtarget);
 582                         }
 583                 }
 584         }
 585         else
 586         {
 587                 tlist = build_path_tlist(root, best_path);
 588         }
 589
 590         switch (best_path->pathtype)
 591         {
 592                 case T_SeqScan:
 593                         plan = (Plan *) create_seqscan_plan(root,
 594                                                                                                 best_path,
 595                                                                                                 tlist,
 596                                                                                                 scan_clauses);
 597                         break;
 598
 599                 case T_SampleScan:
 600                         plan = (Plan *) create_samplescan_plan(root,
 601                                                                                                    best_path,
 602                                                                                                    tlist,
 603                                                                                                    scan_clauses);
 604                         break;
 605
 606                 case T_IndexScan:
 607                         plan = (Plan *) create_indexscan_plan(root,
 608                                                                                                   (IndexPath *) best_path,
 609                                                                                                   tlist,
 610                                                                                                   scan_clauses,
 611                                                                                                   false);
 612                         break;
 613
 614                 case T_IndexOnlyScan:
 615                         plan = (Plan *) create_indexscan_plan(root,
 616                                                                                                   (IndexPath *) best_path,
 617                                                                                                   tlist,
 618                                                                                                   scan_clauses,
 619                                                                                                   true);
 620                         break;
 621
 622                 case T_BitmapHeapScan:
 623                         plan = (Plan *) create_bitmap_scan_plan(root,
 624                                                                                                 (BitmapHeapPath *) best_path,
 625                                                                                                         tlist,
 626                                                                                                         scan_clauses);
 627                         break;
 628
 629                 case T_TidScan:
 630                         plan = (Plan *) create_tidscan_plan(root,
 631                                                                                                 (TidPath *) best_path,
 632                                                                                                 tlist,
 633                                                                                                 scan_clauses);
 634                         break;
 635
 636                 case T_SubqueryScan:
 637                         plan = (Plan *) create_subqueryscan_plan(root,
 638                                                                                           (SubqueryScanPath *) best_path,
 639                                                                                                          tlist,
 640                                                                                                          scan_clauses);
 641                         break;
 642
 643                 case T_FunctionScan:
 644                         plan = (Plan *) create_functionscan_plan(root,
 645                                                                                                          best_path,
 646                                                                                                          tlist,
 647                                                                                                          scan_clauses);
 648                         break;
 649
 650                 case T_TableFuncScan:
 651                         plan = (Plan *) create_tablefuncscan_plan(root,
 652                                                                                                           best_path,
 653                                                                                                           tlist,
 654                                                                                                           scan_clauses);
 655                         break;
 656
 657                 case T_ValuesScan:
 658                         plan = (Plan *) create_valuesscan_plan(root,
 659                                                                                                    best_path,
 660                                                                                                    tlist,
 661                                                                                                    scan_clauses);
 662                         break;
 663
 664                 case T_CteScan:
 665                         plan = (Plan *) create_ctescan_plan(root,
 666                                                                                                 best_path,
 667                                                                                                 tlist,
 668                                                                                                 scan_clauses);
 669                         break;
 670
 671                 case T_WorkTableScan:
 672                         plan = (Plan *) create_worktablescan_plan(root,
 673                                                                                                           best_path,
 674                                                                                                           tlist,
 675                                                                                                           scan_clauses);
 676                         break;
 677
 678                 case T_ForeignScan:
 679                         plan = (Plan *) create_foreignscan_plan(root,
 680                                                                                                         (ForeignPath *) best_path,
 681                                                                                                         tlist,
 682                                                                                                         scan_clauses);
 683                         break;
 684
 685                 case T_CustomScan:
 686                         plan = (Plan *) create_customscan_plan(root,
 687                                                                                                    (CustomPath *) best_path,
 688                                                                                                    tlist,
 689                                                                                                    scan_clauses);
 690                         break;
 691
 692                 default:
 693                         elog(ERROR, "unrecognized node type: %d",
 694                                  (int) best_path->pathtype);
 695                         plan = NULL;            /* keep compiler quiet */
 696                         break;
 697         }
 698
 699         /*
 700          * If there are any pseudoconstant clauses attached to this node, insert a
 701          * gating Result node that evaluates the pseudoconstants as one-time
 702          * quals.
 703          */
 704         if (gating_clauses)
 705                 plan = create_gating_plan(root, best_path, plan, gating_clauses);
 706
 707         return plan;
 708 }
 709
 710 /*
 711  * Build a target list (ie, a list of TargetEntry) for the Path's output.
 712  *
 713  * This is almost just make_tlist_from_pathtarget(), but we also have to
 714  * deal with replacing nestloop params.
 715  */
 716 static List *
 717 build_path_tlist(PlannerInfo *root, Path *path)
 718 {
 719         List       *tlist = NIL;
 720         Index      *sortgrouprefs = path->pathtarget->sortgrouprefs;
 721         int                     resno = 1;
 722         ListCell   *v;
 723
 724         foreach(v, path->pathtarget->exprs)
 725         {
 726                 Node       *node = (Node *) lfirst(v);
 727                 TargetEntry *tle;
 728
 729                 /*
 730                  * If it's a parameterized path, there might be lateral references in
 731                  * the tlist, which need to be replaced with Params.  There's no need
 732                  * to remake the TargetEntry nodes, so apply this to each list item
 733                  * separately.
 734                  */
 735                 if (path->param_info)
 736                         node = replace_nestloop_params(root, node);
 737
 738                 tle = makeTargetEntry((Expr *) node,
 739                                                           resno,
 740                                                           NULL,
 741                                                           false);
 742                 if (sortgrouprefs)
 743                         tle->ressortgroupref = sortgrouprefs[resno - 1];
 744
 745                 tlist = lappend(tlist, tle);
 746                 resno++;
 747         }
 748         return tlist;
 749 }
 750
 751 /*
 752  * use_physical_tlist
 753  *              Decide whether to use a tlist matching relation structure,
 754  *              rather than only those Vars actually referenced.
 755  */
 756 static bool
 757 use_physical_tlist(PlannerInfo *root, Path *path, int flags)
 758 {
 759         RelOptInfo *rel = path->parent;
 760         int                     i;
 761         ListCell   *lc;
 762
 763         /*
 764          * Forget it if either exact tlist or small tlist is demanded.
 765          */
 766         if (flags & (CP_EXACT_TLIST | CP_SMALL_TLIST))
 767                 return false;
 768
 769         /*
 770          * We can do this for real relation scans, subquery scans, function scans,
 771          * tablefunc scans, values scans, and CTE scans (but not for, eg, joins).
 772          */
 773         if (rel->rtekind != RTE_RELATION &&
 774                 rel->rtekind != RTE_SUBQUERY &&
 775                 rel->rtekind != RTE_FUNCTION &&
 776                 rel->rtekind != RTE_TABLEFUNC &&
 777                 rel->rtekind != RTE_VALUES &&
 778                 rel->rtekind != RTE_CTE)
 779                 return false;
 780
 781         /*
 782          * Can't do it with inheritance cases either (mainly because Append
 783          * doesn't project; this test may be unnecessary now that
 784          * create_append_plan instructs its children to return an exact tlist).
 785          */
 786         if (rel->reloptkind != RELOPT_BASEREL)
 787                 return false;
 788
 789         /*
 790          * Can't do it if any system columns or whole-row Vars are requested.
 791          * (This could possibly be fixed but would take some fragile assumptions
 792          * in setrefs.c, I think.)
 793          */
 794         for (i = rel->min_attr; i <= 0; i++)
 795         {
 796                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
 797                         return false;
 798         }
 799
 800         /*
 801          * Can't do it if the rel is required to emit any placeholder expressions,
 802          * either.
 803          */
 804         foreach(lc, root->placeholder_list)
 805         {
 806                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 807
 808                 if (bms_nonempty_difference(phinfo->ph_needed, rel->relids) &&
 809                         bms_is_subset(phinfo->ph_eval_at, rel->relids))
 810                         return false;
 811         }
 812
 813         /*
 814          * Also, can't do it if CP_LABEL_TLIST is specified and path is requested
 815          * to emit any sort/group columns that are not simple Vars.  (If they are
 816          * simple Vars, they should appear in the physical tlist, and
 817          * apply_pathtarget_labeling_to_tlist will take care of getting them
 818          * labeled again.)      We also have to check that no two sort/group columns
 819          * are the same Var, else that element of the physical tlist would need
 820          * conflicting ressortgroupref labels.
 821          */
 822         if ((flags & CP_LABEL_TLIST) && path->pathtarget->sortgrouprefs)
 823         {
 824                 Bitmapset  *sortgroupatts = NULL;
 825
 826                 i = 0;
 827                 foreach(lc, path->pathtarget->exprs)
 828                 {
 829                         Expr       *expr = (Expr *) lfirst(lc);
 830
 831                         if (path->pathtarget->sortgrouprefs[i])
 832                         {
 833                                 if (expr && IsA(expr, Var))
 834                                 {
 835                                         int                     attno = ((Var *) expr)->varattno;
 836
 837                                         attno -= FirstLowInvalidHeapAttributeNumber;
 838                                         if (bms_is_member(attno, sortgroupatts))
 839                                                 return false;
 840                                         sortgroupatts = bms_add_member(sortgroupatts, attno);
 841                                 }
 842                                 else
 843                                         return false;
 844                         }
 845                         i++;
 846                 }
 847         }
 848
 849         return true;
 850 }
 851
 852 /*
 853  * get_gating_quals
 854  *        See if there are pseudoconstant quals in a node's quals list
 855  *
 856  * If the node's quals list includes any pseudoconstant quals,
 857  * return just those quals.
 858  */
 859 static List *
 860 get_gating_quals(PlannerInfo *root, List *quals)
 861 {
 862         /* No need to look if we know there are no pseudoconstants */
 863         if (!root->hasPseudoConstantQuals)
 864                 return NIL;
 865
 866         /* Sort into desirable execution order while still in RestrictInfo form */
 867         quals = order_qual_clauses(root, quals);
 868
 869         /* Pull out any pseudoconstant quals from the RestrictInfo list */
 870         return extract_actual_clauses(quals, true);
 871 }
 872
 873 /*
 874  * create_gating_plan
 875  *        Deal with pseudoconstant qual clauses
 876  *
 877  * Add a gating Result node atop the already-built plan.
 878  */
 879 static Plan *
 880 create_gating_plan(PlannerInfo *root, Path *path, Plan *plan,
 881                                    List *gating_quals)
 882 {
 883         Plan       *gplan;
 884
 885         Assert(gating_quals);
 886
 887         /*
 888          * Since we need a Result node anyway, always return the path's requested
 889          * tlist; that's never a wrong choice, even if the parent node didn't ask
 890          * for CP_EXACT_TLIST.
 891          */
 892         gplan = (Plan *) make_result(build_path_tlist(root, path),
 893                                                                  (Node *) gating_quals,
 894                                                                  plan);
 895
 896         /*
 897          * Notice that we don't change cost or size estimates when doing gating.
 898          * The costs of qual eval were already included in the subplan's cost.
 899          * Leaving the size alone amounts to assuming that the gating qual will
 900          * succeed, which is the conservative estimate for planning upper queries.
 901          * We certainly don't want to assume the output size is zero (unless the
 902          * gating qual is actually constant FALSE, and that case is dealt with in
 903          * clausesel.c).  Interpolating between the two cases is silly, because it
 904          * doesn't reflect what will really happen at runtime, and besides which
 905          * in most cases we have only a very bad idea of the probability of the
 906          * gating qual being true.
 907          */
 908         copy_plan_costsize(gplan, plan);
 909
 910         return gplan;
 911 }
 912
 913 /*
 914  * create_join_plan
 915  *        Create a join plan for 'best_path' and (recursively) plans for its
 916  *        inner and outer paths.
 917  */
 918 static Plan *
 919 create_join_plan(PlannerInfo *root, JoinPath *best_path)
 920 {
 921         Plan       *plan;
 922         List       *gating_clauses;
 923
 924         switch (best_path->path.pathtype)
 925         {
 926                 case T_MergeJoin:
 927                         plan = (Plan *) create_mergejoin_plan(root,
 928                                                                                                   (MergePath *) best_path);
 929                         break;
 930                 case T_HashJoin:
 931                         plan = (Plan *) create_hashjoin_plan(root,
 932                                                                                                  (HashPath *) best_path);
 933                         break;
 934                 case T_NestLoop:
 935                         plan = (Plan *) create_nestloop_plan(root,
 936                                                                                                  (NestPath *) best_path);
 937                         break;
 938                 default:
 939                         elog(ERROR, "unrecognized node type: %d",
 940                                  (int) best_path->path.pathtype);
 941                         plan = NULL;            /* keep compiler quiet */
 942                         break;
 943         }
 944
 945         /*
 946          * If there are any pseudoconstant clauses attached to this node, insert a
 947          * gating Result node that evaluates the pseudoconstants as one-time
 948          * quals.
 949          */
 950         gating_clauses = get_gating_quals(root, best_path->joinrestrictinfo);
 951         if (gating_clauses)
 952                 plan = create_gating_plan(root, (Path *) best_path, plan,
 953                                                                   gating_clauses);
 954
 955 #ifdef NOT_USED
 956
 957         /*
 958          * * Expensive function pullups may have pulled local predicates * into
 959          * this path node.  Put them in the qpqual of the plan node. * JMH,
 960          * 6/15/92
 961          */
 962         if (get_loc_restrictinfo(best_path) != NIL)
 963                 set_qpqual((Plan) plan,
 964                                    list_concat(get_qpqual((Plan) plan),
 965                                            get_actual_clauses(get_loc_restrictinfo(best_path))));
 966 #endif
 967
 968         return plan;
 969 }
 970
 971 /*
 972  * create_append_plan
 973  *        Create an Append plan for 'best_path' and (recursively) plans
 974  *        for its subpaths.
 975  *
 976  *        Returns a Plan node.
 977  */
 978 static Plan *
 979 create_append_plan(PlannerInfo *root, AppendPath *best_path)
 980 {
 981         Append     *plan;
 982         List       *tlist = build_path_tlist(root, &best_path->path);
 983         List       *subplans = NIL;
 984         ListCell   *subpaths;
 985
 986         /*
 987          * The subpaths list could be empty, if every child was proven empty by
 988          * constraint exclusion.  In that case generate a dummy plan that returns
 989          * no rows.
 990          *
 991          * Note that an AppendPath with no members is also generated in certain
 992          * cases where there was no appending construct at all, but we know the
 993          * relation is empty (see set_dummy_rel_pathlist).
 994          */
 995         if (best_path->subpaths == NIL)
 996         {
 997                 /* Generate a Result plan with constant-FALSE gating qual */
 998                 Plan       *plan;
 999
1000                 plan = (Plan *) make_result(tlist,
1001                                                                         (Node *) list_make1(makeBoolConst(false,
1002                                                                                                                                           false)),
1003                                                                         NULL);
1004
1005                 copy_generic_path_info(plan, (Path *) best_path);
1006
1007                 return plan;
1008         }
1009
1010         /* Build the plan for each child */
1011         foreach(subpaths, best_path->subpaths)
1012         {
1013                 Path       *subpath = (Path *) lfirst(subpaths);
1014                 Plan       *subplan;
1015
1016                 /* Must insist that all children return the same tlist */
1017                 subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
1018
1019                 subplans = lappend(subplans, subplan);
1020         }
1021
1022         /*
1023          * XXX ideally, if there's just one child, we'd not bother to generate an
1024          * Append node but just return the single child.  At the moment this does
1025          * not work because the varno of the child scan plan won't match the
1026          * parent-rel Vars it'll be asked to emit.
1027          */
1028
1029         plan = make_append(subplans, tlist);
1030
1031         copy_generic_path_info(&plan->plan, (Path *) best_path);
1032
1033         return (Plan *) plan;
1034 }
1035
1036 /*
1037  * create_merge_append_plan
1038  *        Create a MergeAppend plan for 'best_path' and (recursively) plans
1039  *        for its subpaths.
1040  *
1041  *        Returns a Plan node.
1042  */
1043 static Plan *
1044 create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
1045 {
1046         MergeAppend *node = makeNode(MergeAppend);
1047         Plan       *plan = &node->plan;
1048         List       *tlist = build_path_tlist(root, &best_path->path);
1049         List       *pathkeys = best_path->path.pathkeys;
1050         List       *subplans = NIL;
1051         ListCell   *subpaths;
1052
1053         /*
1054          * We don't have the actual creation of the MergeAppend node split out
1055          * into a separate make_xxx function.  This is because we want to run
1056          * prepare_sort_from_pathkeys on it before we do so on the individual
1057          * child plans, to make cross-checking the sort info easier.
1058          */
1059         copy_generic_path_info(plan, (Path *) best_path);
1060         plan->targetlist = tlist;
1061         plan->qual = NIL;
1062         plan->lefttree = NULL;
1063         plan->righttree = NULL;
1064
1065         /* Compute sort column info, and adjust MergeAppend's tlist as needed */
1066         (void) prepare_sort_from_pathkeys(plan, pathkeys,
1067                                                                           best_path->path.parent->relids,
1068                                                                           NULL,
1069                                                                           true,
1070                                                                           &node->numCols,
1071                                                                           &node->sortColIdx,
1072                                                                           &node->sortOperators,
1073                                                                           &node->collations,
1074                                                                           &node->nullsFirst);
1075
1076         /*
1077          * Now prepare the child plans.  We must apply prepare_sort_from_pathkeys
1078          * even to subplans that don't need an explicit sort, to make sure they
1079          * are returning the same sort key columns the MergeAppend expects.
1080          */
1081         foreach(subpaths, best_path->subpaths)
1082         {
1083                 Path       *subpath = (Path *) lfirst(subpaths);
1084                 Plan       *subplan;
1085                 int                     numsortkeys;
1086                 AttrNumber *sortColIdx;
1087                 Oid                *sortOperators;
1088                 Oid                *collations;
1089                 bool       *nullsFirst;
1090
1091                 /* Build the child plan */
1092                 /* Must insist that all children return the same tlist */
1093                 subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
1094
1095                 /* Compute sort column info, and adjust subplan's tlist as needed */
1096                 subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
1097                                                                                          subpath->parent->relids,
1098                                                                                          node->sortColIdx,
1099                                                                                          false,
1100                                                                                          &numsortkeys,
1101                                                                                          &sortColIdx,
1102                                                                                          &sortOperators,
1103                                                                                          &collations,
1104                                                                                          &nullsFirst);
1105
1106                 /*
1107                  * Check that we got the same sort key information.  We just Assert
1108                  * that the sortops match, since those depend only on the pathkeys;
1109                  * but it seems like a good idea to check the sort column numbers
1110                  * explicitly, to ensure the tlists really do match up.
1111                  */
1112                 Assert(numsortkeys == node->numCols);
1113                 if (memcmp(sortColIdx, node->sortColIdx,
1114                                    numsortkeys * sizeof(AttrNumber)) != 0)
1115                         elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
1116                 Assert(memcmp(sortOperators, node->sortOperators,
1117                                           numsortkeys * sizeof(Oid)) == 0);
1118                 Assert(memcmp(collations, node->collations,
1119                                           numsortkeys * sizeof(Oid)) == 0);
1120                 Assert(memcmp(nullsFirst, node->nullsFirst,
1121                                           numsortkeys * sizeof(bool)) == 0);
1122
1123                 /* Now, insert a Sort node if subplan isn't sufficiently ordered */
1124                 if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
1125                 {
1126                         Sort       *sort = make_sort(subplan, numsortkeys,
1127                                                                                  sortColIdx, sortOperators,
1128                                                                                  collations, nullsFirst);
1129
1130                         label_sort_with_costsize(root, sort, best_path->limit_tuples);
1131                         subplan = (Plan *) sort;
1132                 }
1133
1134                 subplans = lappend(subplans, subplan);
1135         }
1136
1137         node->mergeplans = subplans;
1138
1139         return (Plan *) node;
1140 }
1141
1142 /*
1143  * create_result_plan
1144  *        Create a Result plan for 'best_path'.
1145  *        This is only used for degenerate cases, such as a query with an empty
1146  *        jointree.
1147  *
1148  *        Returns a Plan node.
1149  */
1150 static Result *
1151 create_result_plan(PlannerInfo *root, ResultPath *best_path)
1152 {
1153         Result     *plan;
1154         List       *tlist;
1155         List       *quals;
1156
1157         tlist = build_path_tlist(root, &best_path->path);
1158
1159         /* best_path->quals is just bare clauses */
1160         quals = order_qual_clauses(root, best_path->quals);
1161
1162         plan = make_result(tlist, (Node *) quals, NULL);
1163
1164         copy_generic_path_info(&plan->plan, (Path *) best_path);
1165
1166         return plan;
1167 }
1168
1169 /*
1170  * create_project_set_plan
1171  *        Create a ProjectSet plan for 'best_path'.
1172  *
1173  *        Returns a Plan node.
1174  */
1175 static ProjectSet *
1176 create_project_set_plan(PlannerInfo *root, ProjectSetPath *best_path)
1177 {
1178         ProjectSet *plan;
1179         Plan       *subplan;
1180         List       *tlist;
1181
1182         /* Since we intend to project, we don't need to constrain child tlist */
1183         subplan = create_plan_recurse(root, best_path->subpath, 0);
1184
1185         tlist = build_path_tlist(root, &best_path->path);
1186
1187         plan = make_project_set(tlist, subplan);
1188
1189         copy_generic_path_info(&plan->plan, (Path *) best_path);
1190
1191         return plan;
1192 }
1193
1194 /*
1195  * create_material_plan
1196  *        Create a Material plan for 'best_path' and (recursively) plans
1197  *        for its subpaths.
1198  *
1199  *        Returns a Plan node.
1200  */
1201 static Material *
1202 create_material_plan(PlannerInfo *root, MaterialPath *best_path, int flags)
1203 {
1204         Material   *plan;
1205         Plan       *subplan;
1206
1207         /*
1208          * We don't want any excess columns in the materialized tuples, so request
1209          * a smaller tlist.  Otherwise, since Material doesn't project, tlist
1210          * requirements pass through.
1211          */
1212         subplan = create_plan_recurse(root, best_path->subpath,
1213                                                                   flags | CP_SMALL_TLIST);
1214
1215         plan = make_material(subplan);
1216
1217         copy_generic_path_info(&plan->plan, (Path *) best_path);
1218
1219         return plan;
1220 }
1221
1222 /*
1223  * create_unique_plan
1224  *        Create a Unique plan for 'best_path' and (recursively) plans
1225  *        for its subpaths.
1226  *
1227  *        Returns a Plan node.
1228  */
1229 static Plan *
1230 create_unique_plan(PlannerInfo *root, UniquePath *best_path, int flags)
1231 {
1232         Plan       *plan;
1233         Plan       *subplan;
1234         List       *in_operators;
1235         List       *uniq_exprs;
1236         List       *newtlist;
1237         int                     nextresno;
1238         bool            newitems;
1239         int                     numGroupCols;
1240         AttrNumber *groupColIdx;
1241         int                     groupColPos;
1242         ListCell   *l;
1243
1244         /* Unique doesn't project, so tlist requirements pass through */
1245         subplan = create_plan_recurse(root, best_path->subpath, flags);
1246
1247         /* Done if we don't need to do any actual unique-ifying */
1248         if (best_path->umethod == UNIQUE_PATH_NOOP)
1249                 return subplan;
1250
1251         /*
1252          * As constructed, the subplan has a "flat" tlist containing just the Vars
1253          * needed here and at upper levels.  The values we are supposed to
1254          * unique-ify may be expressions in these variables.  We have to add any
1255          * such expressions to the subplan's tlist.
1256          *
1257          * The subplan may have a "physical" tlist if it is a simple scan plan. If
1258          * we're going to sort, this should be reduced to the regular tlist, so
1259          * that we don't sort more data than we need to.  For hashing, the tlist
1260          * should be left as-is if we don't need to add any expressions; but if we
1261          * do have to add expressions, then a projection step will be needed at
1262          * runtime anyway, so we may as well remove unneeded items. Therefore
1263          * newtlist starts from build_path_tlist() not just a copy of the
1264          * subplan's tlist; and we don't install it into the subplan unless we are
1265          * sorting or stuff has to be added.
1266          */
1267         in_operators = best_path->in_operators;
1268         uniq_exprs = best_path->uniq_exprs;
1269
1270         /* initialize modified subplan tlist as just the "required" vars */
1271         newtlist = build_path_tlist(root, &best_path->path);
1272         nextresno = list_length(newtlist) + 1;
1273         newitems = false;
1274
1275         foreach(l, uniq_exprs)
1276         {
1277                 Node       *uniqexpr = lfirst(l);
1278                 TargetEntry *tle;
1279
1280                 tle = tlist_member(uniqexpr, newtlist);
1281                 if (!tle)
1282                 {
1283                         tle = makeTargetEntry((Expr *) uniqexpr,
1284                                                                   nextresno,
1285                                                                   NULL,
1286                                                                   false);
1287                         newtlist = lappend(newtlist, tle);
1288                         nextresno++;
1289                         newitems = true;
1290                 }
1291         }
1292
1293         if (newitems || best_path->umethod == UNIQUE_PATH_SORT)
1294         {
1295                 /*
1296                  * If the top plan node can't do projections and its existing target
1297                  * list isn't already what we need, we need to add a Result node to
1298                  * help it along.
1299                  */
1300                 if (!is_projection_capable_plan(subplan) &&
1301                         !tlist_same_exprs(newtlist, subplan->targetlist))
1302                         subplan = inject_projection_plan(subplan, newtlist);
1303                 else
1304                         subplan->targetlist = newtlist;
1305         }
1306
1307         /*
1308          * Build control information showing which subplan output columns are to
1309          * be examined by the grouping step.  Unfortunately we can't merge this
1310          * with the previous loop, since we didn't then know which version of the
1311          * subplan tlist we'd end up using.
1312          */
1313         newtlist = subplan->targetlist;
1314         numGroupCols = list_length(uniq_exprs);
1315         groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
1316
1317         groupColPos = 0;
1318         foreach(l, uniq_exprs)
1319         {
1320                 Node       *uniqexpr = lfirst(l);
1321                 TargetEntry *tle;
1322
1323                 tle = tlist_member(uniqexpr, newtlist);
1324                 if (!tle)                               /* shouldn't happen */
1325                         elog(ERROR, "failed to find unique expression in subplan tlist");
1326                 groupColIdx[groupColPos++] = tle->resno;
1327         }
1328
1329         if (best_path->umethod == UNIQUE_PATH_HASH)
1330         {
1331                 Oid                *groupOperators;
1332
1333                 /*
1334                  * Get the hashable equality operators for the Agg node to use.
1335                  * Normally these are the same as the IN clause operators, but if
1336                  * those are cross-type operators then the equality operators are the
1337                  * ones for the IN clause operators' RHS datatype.
1338                  */
1339                 groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
1340                 groupColPos = 0;
1341                 foreach(l, in_operators)
1342                 {
1343                         Oid                     in_oper = lfirst_oid(l);
1344                         Oid                     eq_oper;
1345
1346                         if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
1347                                 elog(ERROR, "could not find compatible hash operator for operator %u",
1348                                          in_oper);
1349                         groupOperators[groupColPos++] = eq_oper;
1350                 }
1351
1352                 /*
1353                  * Since the Agg node is going to project anyway, we can give it the
1354                  * minimum output tlist, without any stuff we might have added to the
1355                  * subplan tlist.
1356                  */
1357                 plan = (Plan *) make_agg(build_path_tlist(root, &best_path->path),
1358                                                                  NIL,
1359                                                                  AGG_HASHED,
1360                                                                  AGGSPLIT_SIMPLE,
1361                                                                  numGroupCols,
1362                                                                  groupColIdx,
1363                                                                  groupOperators,
1364                                                                  NIL,
1365                                                                  NIL,
1366                                                                  best_path->path.rows,
1367                                                                  subplan);
1368         }
1369         else
1370         {
1371                 List       *sortList = NIL;
1372                 Sort       *sort;
1373
1374                 /* Create an ORDER BY list to sort the input compatibly */
1375                 groupColPos = 0;
1376                 foreach(l, in_operators)
1377                 {
1378                         Oid                     in_oper = lfirst_oid(l);
1379                         Oid                     sortop;
1380                         Oid                     eqop;
1381                         TargetEntry *tle;
1382                         SortGroupClause *sortcl;
1383
1384                         sortop = get_ordering_op_for_equality_op(in_oper, false);
1385                         if (!OidIsValid(sortop))        /* shouldn't happen */
1386                                 elog(ERROR, "could not find ordering operator for equality operator %u",
1387                                          in_oper);
1388
1389                         /*
1390                          * The Unique node will need equality operators.  Normally these
1391                          * are the same as the IN clause operators, but if those are
1392                          * cross-type operators then the equality operators are the ones
1393                          * for the IN clause operators' RHS datatype.
1394                          */
1395                         eqop = get_equality_op_for_ordering_op(sortop, NULL);
1396                         if (!OidIsValid(eqop))          /* shouldn't happen */
1397                                 elog(ERROR, "could not find equality operator for ordering operator %u",
1398                                          sortop);
1399
1400                         tle = get_tle_by_resno(subplan->targetlist,
1401                                                                    groupColIdx[groupColPos]);
1402                         Assert(tle != NULL);
1403
1404                         sortcl = makeNode(SortGroupClause);
1405                         sortcl->tleSortGroupRef = assignSortGroupRef(tle,
1406                                                                                                                  subplan->targetlist);
1407                         sortcl->eqop = eqop;
1408                         sortcl->sortop = sortop;
1409                         sortcl->nulls_first = false;
1410                         sortcl->hashable = false;       /* no need to make this accurate */
1411                         sortList = lappend(sortList, sortcl);
1412                         groupColPos++;
1413                 }
1414                 sort = make_sort_from_sortclauses(sortList, subplan);
1415                 label_sort_with_costsize(root, sort, -1.0);
1416                 plan = (Plan *) make_unique_from_sortclauses((Plan *) sort, sortList);
1417         }
1418
1419         /* Copy cost data from Path to Plan */
1420         copy_generic_path_info(plan, &best_path->path);
1421
1422         return plan;
1423 }
1424
1425 /*
1426  * create_gather_plan
1427  *
1428  *        Create a Gather plan for 'best_path' and (recursively) plans
1429  *        for its subpaths.
1430  */
1431 static Gather *
1432 create_gather_plan(PlannerInfo *root, GatherPath *best_path)
1433 {
1434         Gather     *gather_plan;
1435         Plan       *subplan;
1436         List       *tlist;
1437
1438         /*
1439          * Although the Gather node can project, we prefer to push down such work
1440          * to its child node, so demand an exact tlist from the child.
1441          */
1442         subplan = create_plan_recurse(root, best_path->subpath, CP_EXACT_TLIST);
1443
1444         tlist = build_path_tlist(root, &best_path->path);
1445
1446         gather_plan = make_gather(tlist,
1447                                                           NIL,
1448                                                           best_path->path.parallel_workers,
1449                                                           best_path->single_copy,
1450                                                           subplan);
1451
1452         copy_generic_path_info(&gather_plan->plan, &best_path->path);
1453
1454         /* use parallel mode for parallel plans. */
1455         root->glob->parallelModeNeeded = true;
1456
1457         return gather_plan;
1458 }
1459
1460 /*
1461  * create_gather_merge_plan
1462  *
1463  *        Create a Gather Merge plan for 'best_path' and (recursively)
1464  *        plans for its subpaths.
1465  */
1466 static GatherMerge *
1467 create_gather_merge_plan(PlannerInfo *root, GatherMergePath *best_path)
1468 {
1469         GatherMerge *gm_plan;
1470         Plan       *subplan;
1471         List       *pathkeys = best_path->path.pathkeys;
1472         List       *tlist = build_path_tlist(root, &best_path->path);
1473
1474         /* As with Gather, it's best to project away columns in the workers. */
1475         subplan = create_plan_recurse(root, best_path->subpath, CP_EXACT_TLIST);
1476
1477         /* Create a shell for a GatherMerge plan. */
1478         gm_plan = makeNode(GatherMerge);
1479         gm_plan->plan.targetlist = tlist;
1480         gm_plan->num_workers = best_path->num_workers;
1481         copy_generic_path_info(&gm_plan->plan, &best_path->path);
1482
1483         /* Gather Merge is pointless with no pathkeys; use Gather instead. */
1484         Assert(pathkeys != NIL);
1485
1486         /* Compute sort column info, and adjust subplan's tlist as needed */
1487         subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
1488                                                                                  best_path->subpath->parent->relids,
1489                                                                                  gm_plan->sortColIdx,
1490                                                                                  false,
1491                                                                                  &gm_plan->numCols,
1492                                                                                  &gm_plan->sortColIdx,
1493                                                                                  &gm_plan->sortOperators,
1494                                                                                  &gm_plan->collations,
1495                                                                                  &gm_plan->nullsFirst);
1496
1497
1498         /* Now, insert a Sort node if subplan isn't sufficiently ordered */
1499         if (!pathkeys_contained_in(pathkeys, best_path->subpath->pathkeys))
1500                 subplan = (Plan *) make_sort(subplan, gm_plan->numCols,
1501                                                                          gm_plan->sortColIdx,
1502                                                                          gm_plan->sortOperators,
1503                                                                          gm_plan->collations,
1504                                                                          gm_plan->nullsFirst);
1505
1506         /* Now insert the subplan under GatherMerge. */
1507         gm_plan->plan.lefttree = subplan;
1508
1509         /* use parallel mode for parallel plans. */
1510         root->glob->parallelModeNeeded = true;
1511
1512         return gm_plan;
1513 }
1514
1515 /*
1516  * create_projection_plan
1517  *
1518  *        Create a plan tree to do a projection step and (recursively) plans
1519  *        for its subpaths.  We may need a Result node for the projection,
1520  *        but sometimes we can just let the subplan do the work.
1521  */
1522 static Plan *
1523 create_projection_plan(PlannerInfo *root, ProjectionPath *best_path)
1524 {
1525         Plan       *plan;
1526         Plan       *subplan;
1527         List       *tlist;
1528
1529         /* Since we intend to project, we don't need to constrain child tlist */
1530         subplan = create_plan_recurse(root, best_path->subpath, 0);
1531
1532         tlist = build_path_tlist(root, &best_path->path);
1533
1534         /*
1535          * We might not really need a Result node here, either because the subplan
1536          * can project or because it's returning the right list of expressions
1537          * anyway.  Usually create_projection_path will have detected that and set
1538          * dummypp if we don't need a Result; but its decision can't be final,
1539          * because some createplan.c routines change the tlists of their nodes.
1540          * (An example is that create_merge_append_plan might add resjunk sort
1541          * columns to a MergeAppend.)  So we have to recheck here.  If we do
1542          * arrive at a different answer than create_projection_path did, we'll
1543          * have made slightly wrong cost estimates; but label the plan with the
1544          * cost estimates we actually used, not "corrected" ones.  (XXX this could
1545          * be cleaned up if we moved more of the sortcolumn setup logic into Path
1546          * creation, but that would add expense to creating Paths we might end up
1547          * not using.)
1548          */
1549         if (is_projection_capable_path(best_path->subpath) ||
1550                 tlist_same_exprs(tlist, subplan->targetlist))
1551         {
1552                 /* Don't need a separate Result, just assign tlist to subplan */
1553                 plan = subplan;
1554                 plan->targetlist = tlist;
1555
1556                 /* Label plan with the estimated costs we actually used */
1557                 plan->startup_cost = best_path->path.startup_cost;
1558                 plan->total_cost = best_path->path.total_cost;
1559                 plan->plan_rows = best_path->path.rows;
1560                 plan->plan_width = best_path->path.pathtarget->width;
1561                 /* ... but be careful not to munge subplan's parallel-aware flag */
1562         }
1563         else
1564         {
1565                 /* We need a Result node */
1566                 plan = (Plan *) make_result(tlist, NULL, subplan);
1567
1568                 copy_generic_path_info(plan, (Path *) best_path);
1569         }
1570
1571         return plan;
1572 }
1573
1574 /*
1575  * inject_projection_plan
1576  *        Insert a Result node to do a projection step.
1577  *
1578  * This is used in a few places where we decide on-the-fly that we need a
1579  * projection step as part of the tree generated for some Path node.
1580  * We should try to get rid of this in favor of doing it more honestly.
1581  */
1582 static Plan *
1583 inject_projection_plan(Plan *subplan, List *tlist)
1584 {
1585         Plan       *plan;
1586
1587         plan = (Plan *) make_result(tlist, NULL, subplan);
1588
1589         /*
1590          * In principle, we should charge tlist eval cost plus cpu_per_tuple per
1591          * row for the Result node.  But the former has probably been factored in
1592          * already and the latter was not accounted for during Path construction,
1593          * so being formally correct might just make the EXPLAIN output look less
1594          * consistent not more so.  Hence, just copy the subplan's cost.
1595          */
1596         copy_plan_costsize(plan, subplan);
1597
1598         return plan;
1599 }
1600
1601 /*
1602  * create_sort_plan
1603  *
1604  *        Create a Sort plan for 'best_path' and (recursively) plans
1605  *        for its subpaths.
1606  */
1607 static Sort *
1608 create_sort_plan(PlannerInfo *root, SortPath *best_path, int flags)
1609 {
1610         Sort       *plan;
1611         Plan       *subplan;
1612
1613         /*
1614          * We don't want any excess columns in the sorted tuples, so request a
1615          * smaller tlist.  Otherwise, since Sort doesn't project, tlist
1616          * requirements pass through.
1617          */
1618         subplan = create_plan_recurse(root, best_path->subpath,
1619                                                                   flags | CP_SMALL_TLIST);
1620
1621         plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys);
1622
1623         copy_generic_path_info(&plan->plan, (Path *) best_path);
1624
1625         return plan;
1626 }
1627
1628 /*
1629  * create_group_plan
1630  *
1631  *        Create a Group plan for 'best_path' and (recursively) plans
1632  *        for its subpaths.
1633  */
1634 static Group *
1635 create_group_plan(PlannerInfo *root, GroupPath *best_path)
1636 {
1637         Group      *plan;
1638         Plan       *subplan;
1639         List       *tlist;
1640         List       *quals;
1641
1642         /*
1643          * Group can project, so no need to be terribly picky about child tlist,
1644          * but we do need grouping columns to be available
1645          */
1646         subplan = create_plan_recurse(root, best_path->subpath, CP_LABEL_TLIST);
1647
1648         tlist = build_path_tlist(root, &best_path->path);
1649
1650         quals = order_qual_clauses(root, best_path->qual);
1651
1652         plan = make_group(tlist,
1653                                           quals,
1654                                           list_length(best_path->groupClause),
1655                                           extract_grouping_cols(best_path->groupClause,
1656                                                                                         subplan->targetlist),
1657                                           extract_grouping_ops(best_path->groupClause),
1658                                           subplan);
1659
1660         copy_generic_path_info(&plan->plan, (Path *) best_path);
1661
1662         return plan;
1663 }
1664
1665 /*
1666  * create_upper_unique_plan
1667  *
1668  *        Create a Unique plan for 'best_path' and (recursively) plans
1669  *        for its subpaths.
1670  */
1671 static Unique *
1672 create_upper_unique_plan(PlannerInfo *root, UpperUniquePath *best_path, int flags)
1673 {
1674         Unique     *plan;
1675         Plan       *subplan;
1676
1677         /*
1678          * Unique doesn't project, so tlist requirements pass through; moreover we
1679          * need grouping columns to be labeled.
1680          */
1681         subplan = create_plan_recurse(root, best_path->subpath,
1682                                                                   flags | CP_LABEL_TLIST);
1683
1684         plan = make_unique_from_pathkeys(subplan,
1685                                                                          best_path->path.pathkeys,
1686                                                                          best_path->numkeys);
1687
1688         copy_generic_path_info(&plan->plan, (Path *) best_path);
1689
1690         return plan;
1691 }
1692
1693 /*
1694  * create_agg_plan
1695  *
1696  *        Create an Agg plan for 'best_path' and (recursively) plans
1697  *        for its subpaths.
1698  */
1699 static Agg *
1700 create_agg_plan(PlannerInfo *root, AggPath *best_path)
1701 {
1702         Agg                *plan;
1703         Plan       *subplan;
1704         List       *tlist;
1705         List       *quals;
1706
1707         /*
1708          * Agg can project, so no need to be terribly picky about child tlist, but
1709          * we do need grouping columns to be available
1710          */
1711         subplan = create_plan_recurse(root, best_path->subpath, CP_LABEL_TLIST);
1712
1713         tlist = build_path_tlist(root, &best_path->path);
1714
1715         quals = order_qual_clauses(root, best_path->qual);
1716
1717         plan = make_agg(tlist, quals,
1718                                         best_path->aggstrategy,
1719                                         best_path->aggsplit,
1720                                         list_length(best_path->groupClause),
1721                                         extract_grouping_cols(best_path->groupClause,
1722                                                                                   subplan->targetlist),
1723                                         extract_grouping_ops(best_path->groupClause),
1724                                         NIL,
1725                                         NIL,
1726                                         best_path->numGroups,
1727                                         subplan);
1728
1729         copy_generic_path_info(&plan->plan, (Path *) best_path);
1730
1731         return plan;
1732 }
1733
1734 /*
1735  * Given a groupclause for a collection of grouping sets, produce the
1736  * corresponding groupColIdx.
1737  *
1738  * root->grouping_map maps the tleSortGroupRef to the actual column position in
1739  * the input tuple. So we get the ref from the entries in the groupclause and
1740  * look them up there.
1741  */
1742 static AttrNumber *
1743 remap_groupColIdx(PlannerInfo *root, List *groupClause)
1744 {
1745         AttrNumber *grouping_map = root->grouping_map;
1746         AttrNumber *new_grpColIdx;
1747         ListCell   *lc;
1748         int                     i;
1749
1750         Assert(grouping_map);
1751
1752         new_grpColIdx = palloc0(sizeof(AttrNumber) * list_length(groupClause));
1753
1754         i = 0;
1755         foreach(lc, groupClause)
1756         {
1757                 SortGroupClause *clause = lfirst(lc);
1758
1759                 new_grpColIdx[i++] = grouping_map[clause->tleSortGroupRef];
1760         }
1761
1762         return new_grpColIdx;
1763 }
1764
1765 /*
1766  * create_groupingsets_plan
1767  *        Create a plan for 'best_path' and (recursively) plans
1768  *        for its subpaths.
1769  *
1770  *        What we emit is an Agg plan with some vestigial Agg and Sort nodes
1771  *        hanging off the side.  The top Agg implements the last grouping set
1772  *        specified in the GroupingSetsPath, and any additional grouping sets
1773  *        each give rise to a subsidiary Agg and Sort node in the top Agg's
1774  *        "chain" list.  These nodes don't participate in the plan directly,
1775  *        but they are a convenient way to represent the required data for
1776  *        the extra steps.
1777  *
1778  *        Returns a Plan node.
1779  */
1780 static Plan *
1781 create_groupingsets_plan(PlannerInfo *root, GroupingSetsPath *best_path)
1782 {
1783         Agg                *plan;
1784         Plan       *subplan;
1785         List       *rollup_groupclauses = best_path->rollup_groupclauses;
1786         List       *rollup_lists = best_path->rollup_lists;
1787         AttrNumber *grouping_map;
1788         int                     maxref;
1789         List       *chain;
1790         ListCell   *lc,
1791                            *lc2;
1792
1793         /* Shouldn't get here without grouping sets */
1794         Assert(root->parse->groupingSets);
1795         Assert(rollup_lists != NIL);
1796         Assert(list_length(rollup_lists) == list_length(rollup_groupclauses));
1797
1798         /*
1799          * Agg can project, so no need to be terribly picky about child tlist, but
1800          * we do need grouping columns to be available
1801          */
1802         subplan = create_plan_recurse(root, best_path->subpath, CP_LABEL_TLIST);
1803
1804         /*
1805          * Compute the mapping from tleSortGroupRef to column index in the child's
1806          * tlist.  First, identify max SortGroupRef in groupClause, for array
1807          * sizing.
1808          */
1809         maxref = 0;
1810         foreach(lc, root->parse->groupClause)
1811         {
1812                 SortGroupClause *gc = (SortGroupClause *) lfirst(lc);
1813
1814                 if (gc->tleSortGroupRef > maxref)
1815                         maxref = gc->tleSortGroupRef;
1816         }
1817
1818         grouping_map = (AttrNumber *) palloc0((maxref + 1) * sizeof(AttrNumber));
1819
1820         /* Now look up the column numbers in the child's tlist */
1821         foreach(lc, root->parse->groupClause)
1822         {
1823                 SortGroupClause *gc = (SortGroupClause *) lfirst(lc);
1824                 TargetEntry *tle = get_sortgroupclause_tle(gc, subplan->targetlist);
1825
1826                 grouping_map[gc->tleSortGroupRef] = tle->resno;
1827         }
1828
1829         /*
1830          * During setrefs.c, we'll need the grouping_map to fix up the cols lists
1831          * in GroupingFunc nodes.  Save it for setrefs.c to use.
1832          *
1833          * This doesn't work if we're in an inheritance subtree (see notes in
1834          * create_modifytable_plan).  Fortunately we can't be because there would
1835          * never be grouping in an UPDATE/DELETE; but let's Assert that.
1836          */
1837         Assert(!root->hasInheritedTarget);
1838         Assert(root->grouping_map == NULL);
1839         root->grouping_map = grouping_map;
1840
1841         /*
1842          * Generate the side nodes that describe the other sort and group
1843          * operations besides the top one.  Note that we don't worry about putting
1844          * accurate cost estimates in the side nodes; only the topmost Agg node's
1845          * costs will be shown by EXPLAIN.
1846          */
1847         chain = NIL;
1848         if (list_length(rollup_groupclauses) > 1)
1849         {
1850                 forboth(lc, rollup_groupclauses, lc2, rollup_lists)
1851                 {
1852                         List       *groupClause = (List *) lfirst(lc);
1853                         List       *gsets = (List *) lfirst(lc2);
1854                         AttrNumber *new_grpColIdx;
1855                         Plan       *sort_plan;
1856                         Plan       *agg_plan;
1857
1858                         /* We want to iterate over all but the last rollup list elements */
1859                         if (lnext(lc) == NULL)
1860                                 break;
1861
1862                         new_grpColIdx = remap_groupColIdx(root, groupClause);
1863
1864                         sort_plan = (Plan *)
1865                                 make_sort_from_groupcols(groupClause,
1866                                                                                  new_grpColIdx,
1867                                                                                  subplan);
1868
1869                         agg_plan = (Plan *) make_agg(NIL,
1870                                                                                  NIL,
1871                                                                                  AGG_SORTED,
1872                                                                                  AGGSPLIT_SIMPLE,
1873                                                                            list_length((List *) linitial(gsets)),
1874                                                                                  new_grpColIdx,
1875                                                                                  extract_grouping_ops(groupClause),
1876                                                                                  gsets,
1877                                                                                  NIL,
1878                                                                                  0,             /* numGroups not needed */
1879                                                                                  sort_plan);
1880
1881                         /*
1882                          * Nuke stuff we don't need to avoid bloating debug output.
1883                          */
1884                         sort_plan->targetlist = NIL;
1885                         sort_plan->lefttree = NULL;
1886
1887                         chain = lappend(chain, agg_plan);
1888                 }
1889         }
1890
1891         /*
1892          * Now make the final Agg node
1893          */
1894         {
1895                 List       *groupClause = (List *) llast(rollup_groupclauses);
1896                 List       *gsets = (List *) llast(rollup_lists);
1897                 AttrNumber *top_grpColIdx;
1898                 int                     numGroupCols;
1899
1900                 top_grpColIdx = remap_groupColIdx(root, groupClause);
1901
1902                 numGroupCols = list_length((List *) linitial(gsets));
1903
1904                 plan = make_agg(build_path_tlist(root, &best_path->path),
1905                                                 best_path->qual,
1906                                                 (numGroupCols > 0) ? AGG_SORTED : AGG_PLAIN,
1907                                                 AGGSPLIT_SIMPLE,
1908                                                 numGroupCols,
1909                                                 top_grpColIdx,
1910                                                 extract_grouping_ops(groupClause),
1911                                                 gsets,
1912                                                 chain,
1913                                                 0,              /* numGroups not needed */
1914                                                 subplan);
1915
1916                 /* Copy cost data from Path to Plan */
1917                 copy_generic_path_info(&plan->plan, &best_path->path);
1918         }
1919
1920         return (Plan *) plan;
1921 }
1922
1923 /*
1924  * create_minmaxagg_plan
1925  *
1926  *        Create a Result plan for 'best_path' and (recursively) plans
1927  *        for its subpaths.
1928  */
1929 static Result *
1930 create_minmaxagg_plan(PlannerInfo *root, MinMaxAggPath *best_path)
1931 {
1932         Result     *plan;
1933         List       *tlist;
1934         ListCell   *lc;
1935
1936         /* Prepare an InitPlan for each aggregate's subquery. */
1937         foreach(lc, best_path->mmaggregates)
1938         {
1939                 MinMaxAggInfo *mminfo = (MinMaxAggInfo *) lfirst(lc);
1940                 PlannerInfo *subroot = mminfo->subroot;
1941                 Query      *subparse = subroot->parse;
1942                 Plan       *plan;
1943
1944                 /*
1945                  * Generate the plan for the subquery. We already have a Path, but we
1946                  * have to convert it to a Plan and attach a LIMIT node above it.
1947                  * Since we are entering a different planner context (subroot),
1948                  * recurse to create_plan not create_plan_recurse.
1949                  */
1950                 plan = create_plan(subroot, mminfo->path);
1951
1952                 plan = (Plan *) make_limit(plan,
1953                                                                    subparse->limitOffset,
1954                                                                    subparse->limitCount);
1955
1956                 /* Must apply correct cost/width data to Limit node */
1957                 plan->startup_cost = mminfo->path->startup_cost;
1958                 plan->total_cost = mminfo->pathcost;
1959                 plan->plan_rows = 1;
1960                 plan->plan_width = mminfo->path->pathtarget->width;
1961                 plan->parallel_aware = false;
1962
1963                 /* Convert the plan into an InitPlan in the outer query. */
1964                 SS_make_initplan_from_plan(root, subroot, plan, mminfo->param);
1965         }
1966
1967         /* Generate the output plan --- basically just a Result */
1968         tlist = build_path_tlist(root, &best_path->path);
1969
1970         plan = make_result(tlist, (Node *) best_path->quals, NULL);
1971
1972         copy_generic_path_info(&plan->plan, (Path *) best_path);
1973
1974         /*
1975          * During setrefs.c, we'll need to replace references to the Agg nodes
1976          * with InitPlan output params.  (We can't just do that locally in the
1977          * MinMaxAgg node, because path nodes above here may have Agg references
1978          * as well.)  Save the mmaggregates list to tell setrefs.c to do that.
1979          *
1980          * This doesn't work if we're in an inheritance subtree (see notes in
1981          * create_modifytable_plan).  Fortunately we can't be because there would
1982          * never be aggregates in an UPDATE/DELETE; but let's Assert that.
1983          */
1984         Assert(!root->hasInheritedTarget);
1985         Assert(root->minmax_aggs == NIL);
1986         root->minmax_aggs = best_path->mmaggregates;
1987
1988         return plan;
1989 }
1990
1991 /*
1992  * create_windowagg_plan
1993  *
1994  *        Create a WindowAgg plan for 'best_path' and (recursively) plans
1995  *        for its subpaths.
1996  */
1997 static WindowAgg *
1998 create_windowagg_plan(PlannerInfo *root, WindowAggPath *best_path)
1999 {
2000         WindowAgg  *plan;
2001         WindowClause *wc = best_path->winclause;
2002         Plan       *subplan;
2003         List       *tlist;
2004         int                     numsortkeys;
2005         AttrNumber *sortColIdx;
2006         Oid                *sortOperators;
2007         Oid                *collations;
2008         bool       *nullsFirst;
2009         int                     partNumCols;
2010         AttrNumber *partColIdx;
2011         Oid                *partOperators;
2012         int                     ordNumCols;
2013         AttrNumber *ordColIdx;
2014         Oid                *ordOperators;
2015
2016         /*
2017          * WindowAgg can project, so no need to be terribly picky about child
2018          * tlist, but we do need grouping columns to be available
2019          */
2020         subplan = create_plan_recurse(root, best_path->subpath, CP_LABEL_TLIST);
2021
2022         tlist = build_path_tlist(root, &best_path->path);
2023
2024         /*
2025          * We shouldn't need to actually sort, but it's convenient to use
2026          * prepare_sort_from_pathkeys to identify the input's sort columns.
2027          */
2028         subplan = prepare_sort_from_pathkeys(subplan,
2029                                                                                  best_path->winpathkeys,
2030                                                                                  NULL,
2031                                                                                  NULL,
2032                                                                                  false,
2033                                                                                  &numsortkeys,
2034                                                                                  &sortColIdx,
2035                                                                                  &sortOperators,
2036                                                                                  &collations,
2037                                                                                  &nullsFirst);
2038
2039         /* Now deconstruct that into partition and ordering portions */
2040         get_column_info_for_window(root,
2041                                                            wc,
2042                                                            subplan->targetlist,
2043                                                            numsortkeys,
2044                                                            sortColIdx,
2045                                                            &partNumCols,
2046                                                            &partColIdx,
2047                                                            &partOperators,
2048                                                            &ordNumCols,
2049                                                            &ordColIdx,
2050                                                            &ordOperators);
2051
2052         /* And finally we can make the WindowAgg node */
2053         plan = make_windowagg(tlist,
2054                                                   wc->winref,
2055                                                   partNumCols,
2056                                                   partColIdx,
2057                                                   partOperators,
2058                                                   ordNumCols,
2059                                                   ordColIdx,
2060                                                   ordOperators,
2061                                                   wc->frameOptions,
2062                                                   wc->startOffset,
2063                                                   wc->endOffset,
2064                                                   subplan);
2065
2066         copy_generic_path_info(&plan->plan, (Path *) best_path);
2067
2068         return plan;
2069 }
2070
2071 /*
2072  * get_column_info_for_window
2073  *              Get the partitioning/ordering column numbers and equality operators
2074  *              for a WindowAgg node.
2075  *
2076  * This depends on the behavior of planner.c's make_pathkeys_for_window!
2077  *
2078  * We are given the target WindowClause and an array of the input column
2079  * numbers associated with the resulting pathkeys.  In the easy case, there
2080  * are the same number of pathkey columns as partitioning + ordering columns
2081  * and we just have to copy some data around.  However, it's possible that
2082  * some of the original partitioning + ordering columns were eliminated as
2083  * redundant during the transformation to pathkeys.  (This can happen even
2084  * though the parser gets rid of obvious duplicates.  A typical scenario is a
2085  * window specification "PARTITION BY x ORDER BY y" coupled with a clause
2086  * "WHERE x = y" that causes the two sort columns to be recognized as
2087  * redundant.)  In that unusual case, we have to work a lot harder to
2088  * determine which keys are significant.
2089  *
2090  * The method used here is a bit brute-force: add the sort columns to a list
2091  * one at a time and note when the resulting pathkey list gets longer.  But
2092  * it's a sufficiently uncommon case that a faster way doesn't seem worth
2093  * the amount of code refactoring that'd be needed.
2094  */
2095 static void
2096 get_column_info_for_window(PlannerInfo *root, WindowClause *wc, List *tlist,
2097                                                    int numSortCols, AttrNumber *sortColIdx,
2098                                                    int *partNumCols,
2099                                                    AttrNumber **partColIdx,
2100                                                    Oid **partOperators,
2101                                                    int *ordNumCols,
2102                                                    AttrNumber **ordColIdx,
2103                                                    Oid **ordOperators)
2104 {
2105         int                     numPart = list_length(wc->partitionClause);
2106         int                     numOrder = list_length(wc->orderClause);
2107
2108         if (numSortCols == numPart + numOrder)
2109         {
2110                 /* easy case */
2111                 *partNumCols = numPart;
2112                 *partColIdx = sortColIdx;
2113                 *partOperators = extract_grouping_ops(wc->partitionClause);
2114                 *ordNumCols = numOrder;
2115                 *ordColIdx = sortColIdx + numPart;
2116                 *ordOperators = extract_grouping_ops(wc->orderClause);
2117         }
2118         else
2119         {
2120                 List       *sortclauses;
2121                 List       *pathkeys;
2122                 int                     scidx;
2123                 ListCell   *lc;
2124
2125                 /* first, allocate what's certainly enough space for the arrays */
2126                 *partNumCols = 0;
2127                 *partColIdx = (AttrNumber *) palloc(numPart * sizeof(AttrNumber));
2128                 *partOperators = (Oid *) palloc(numPart * sizeof(Oid));
2129                 *ordNumCols = 0;
2130                 *ordColIdx = (AttrNumber *) palloc(numOrder * sizeof(AttrNumber));
2131                 *ordOperators = (Oid *) palloc(numOrder * sizeof(Oid));
2132                 sortclauses = NIL;
2133                 pathkeys = NIL;
2134                 scidx = 0;
2135                 foreach(lc, wc->partitionClause)
2136                 {
2137                         SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
2138                         List       *new_pathkeys;
2139
2140                         sortclauses = lappend(sortclauses, sgc);
2141                         new_pathkeys = make_pathkeys_for_sortclauses(root,
2142                                                                                                                  sortclauses,
2143                                                                                                                  tlist);
2144                         if (list_length(new_pathkeys) > list_length(pathkeys))
2145                         {
2146                                 /* this sort clause is actually significant */
2147                                 (*partColIdx)[*partNumCols] = sortColIdx[scidx++];
2148                                 (*partOperators)[*partNumCols] = sgc->eqop;
2149                                 (*partNumCols)++;
2150                                 pathkeys = new_pathkeys;
2151                         }
2152                 }
2153                 foreach(lc, wc->orderClause)
2154                 {
2155                         SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
2156                         List       *new_pathkeys;
2157
2158                         sortclauses = lappend(sortclauses, sgc);
2159                         new_pathkeys = make_pathkeys_for_sortclauses(root,
2160                                                                                                                  sortclauses,
2161                                                                                                                  tlist);
2162                         if (list_length(new_pathkeys) > list_length(pathkeys))
2163                         {
2164                                 /* this sort clause is actually significant */
2165                                 (*ordColIdx)[*ordNumCols] = sortColIdx[scidx++];
2166                                 (*ordOperators)[*ordNumCols] = sgc->eqop;
2167                                 (*ordNumCols)++;
2168                                 pathkeys = new_pathkeys;
2169                         }
2170                 }
2171                 /* complain if we didn't eat exactly the right number of sort cols */
2172                 if (scidx != numSortCols)
2173                         elog(ERROR, "failed to deconstruct sort operators into partitioning/ordering operators");
2174         }
2175 }
2176
2177 /*
2178  * create_setop_plan
2179  *
2180  *        Create a SetOp plan for 'best_path' and (recursively) plans
2181  *        for its subpaths.
2182  */
2183 static SetOp *
2184 create_setop_plan(PlannerInfo *root, SetOpPath *best_path, int flags)
2185 {
2186         SetOp      *plan;
2187         Plan       *subplan;
2188         long            numGroups;
2189
2190         /*
2191          * SetOp doesn't project, so tlist requirements pass through; moreover we
2192          * need grouping columns to be labeled.
2193          */
2194         subplan = create_plan_recurse(root, best_path->subpath,
2195                                                                   flags | CP_LABEL_TLIST);
2196
2197         /* Convert numGroups to long int --- but 'ware overflow! */
2198         numGroups = (long) Min(best_path->numGroups, (double) LONG_MAX);
2199
2200         plan = make_setop(best_path->cmd,
2201                                           best_path->strategy,
2202                                           subplan,
2203                                           best_path->distinctList,
2204                                           best_path->flagColIdx,
2205                                           best_path->firstFlag,
2206                                           numGroups);
2207
2208         copy_generic_path_info(&plan->plan, (Path *) best_path);
2209
2210         return plan;
2211 }
2212
2213 /*
2214  * create_recursiveunion_plan
2215  *
2216  *        Create a RecursiveUnion plan for 'best_path' and (recursively) plans
2217  *        for its subpaths.
2218  */
2219 static RecursiveUnion *
2220 create_recursiveunion_plan(PlannerInfo *root, RecursiveUnionPath *best_path)
2221 {
2222         RecursiveUnion *plan;
2223         Plan       *leftplan;
2224         Plan       *rightplan;
2225         List       *tlist;
2226         long            numGroups;
2227
2228         /* Need both children to produce same tlist, so force it */
2229         leftplan = create_plan_recurse(root, best_path->leftpath, CP_EXACT_TLIST);
2230         rightplan = create_plan_recurse(root, best_path->rightpath, CP_EXACT_TLIST);
2231
2232         tlist = build_path_tlist(root, &best_path->path);
2233
2234         /* Convert numGroups to long int --- but 'ware overflow! */
2235         numGroups = (long) Min(best_path->numGroups, (double) LONG_MAX);
2236
2237         plan = make_recursive_union(tlist,
2238                                                                 leftplan,
2239                                                                 rightplan,
2240                                                                 best_path->wtParam,
2241                                                                 best_path->distinctList,
2242                                                                 numGroups);
2243
2244         copy_generic_path_info(&plan->plan, (Path *) best_path);
2245
2246         return plan;
2247 }
2248
2249 /*
2250  * create_lockrows_plan
2251  *
2252  *        Create a LockRows plan for 'best_path' and (recursively) plans
2253  *        for its subpaths.
2254  */
2255 static LockRows *
2256 create_lockrows_plan(PlannerInfo *root, LockRowsPath *best_path,
2257                                          int flags)
2258 {
2259         LockRows   *plan;
2260         Plan       *subplan;
2261
2262         /* LockRows doesn't project, so tlist requirements pass through */
2263         subplan = create_plan_recurse(root, best_path->subpath, flags);
2264
2265         plan = make_lockrows(subplan, best_path->rowMarks, best_path->epqParam);
2266
2267         copy_generic_path_info(&plan->plan, (Path *) best_path);
2268
2269         return plan;
2270 }
2271
2272 /*
2273  * create_modifytable_plan
2274  *        Create a ModifyTable plan for 'best_path'.
2275  *
2276  *        Returns a Plan node.
2277  */
2278 static ModifyTable *
2279 create_modifytable_plan(PlannerInfo *root, ModifyTablePath *best_path)
2280 {
2281         ModifyTable *plan;
2282         List       *subplans = NIL;
2283         ListCell   *subpaths,
2284                            *subroots;
2285
2286         /* Build the plan for each input path */
2287         forboth(subpaths, best_path->subpaths,
2288                         subroots, best_path->subroots)
2289         {
2290                 Path       *subpath = (Path *) lfirst(subpaths);
2291                 PlannerInfo *subroot = (PlannerInfo *) lfirst(subroots);
2292                 Plan       *subplan;
2293
2294                 /*
2295                  * In an inherited UPDATE/DELETE, reference the per-child modified
2296                  * subroot while creating Plans from Paths for the child rel.  This is
2297                  * a kluge, but otherwise it's too hard to ensure that Plan creation
2298                  * functions (particularly in FDWs) don't depend on the contents of
2299                  * "root" matching what they saw at Path creation time.  The main
2300                  * downside is that creation functions for Plans that might appear
2301                  * below a ModifyTable cannot expect to modify the contents of "root"
2302                  * and have it "stick" for subsequent processing such as setrefs.c.
2303                  * That's not great, but it seems better than the alternative.
2304                  */
2305                 subplan = create_plan_recurse(subroot, subpath, CP_EXACT_TLIST);
2306
2307                 /* Transfer resname/resjunk labeling, too, to keep executor happy */
2308                 apply_tlist_labeling(subplan->targetlist, subroot->processed_tlist);
2309
2310                 subplans = lappend(subplans, subplan);
2311         }
2312
2313         plan = make_modifytable(root,
2314                                                         best_path->operation,
2315                                                         best_path->canSetTag,
2316                                                         best_path->nominalRelation,
2317                                                         best_path->resultRelations,
2318                                                         subplans,
2319                                                         best_path->withCheckOptionLists,
2320                                                         best_path->returningLists,
2321                                                         best_path->rowMarks,
2322                                                         best_path->onconflict,
2323                                                         best_path->epqParam);
2324
2325         copy_generic_path_info(&plan->plan, &best_path->path);
2326
2327         return plan;
2328 }
2329
2330 /*
2331  * create_limit_plan
2332  *
2333  *        Create a Limit plan for 'best_path' and (recursively) plans
2334  *        for its subpaths.
2335  */
2336 static Limit *
2337 create_limit_plan(PlannerInfo *root, LimitPath *best_path, int flags)
2338 {
2339         Limit      *plan;
2340         Plan       *subplan;
2341
2342         /* Limit doesn't project, so tlist requirements pass through */
2343         subplan = create_plan_recurse(root, best_path->subpath, flags);
2344
2345         plan = make_limit(subplan,
2346                                           best_path->limitOffset,
2347                                           best_path->limitCount);
2348
2349         copy_generic_path_info(&plan->plan, (Path *) best_path);
2350
2351         return plan;
2352 }
2353
2354
2355 /*****************************************************************************
2356  *
2357  *      BASE-RELATION SCAN METHODS
2358  *
2359  *****************************************************************************/
2360
2361
2362 /*
2363  * create_seqscan_plan
2364  *       Returns a seqscan plan for the base relation scanned by 'best_path'
2365  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2366  */
2367 static SeqScan *
2368 create_seqscan_plan(PlannerInfo *root, Path *best_path,
2369                                         List *tlist, List *scan_clauses)
2370 {
2371         SeqScan    *scan_plan;
2372         Index           scan_relid = best_path->parent->relid;
2373
2374         /* it should be a base rel... */
2375         Assert(scan_relid > 0);
2376         Assert(best_path->parent->rtekind == RTE_RELATION);
2377
2378         /* Sort clauses into best execution order */
2379         scan_clauses = order_qual_clauses(root, scan_clauses);
2380
2381         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2382         scan_clauses = extract_actual_clauses(scan_clauses, false);
2383
2384         /* Replace any outer-relation variables with nestloop params */
2385         if (best_path->param_info)
2386         {
2387                 scan_clauses = (List *)
2388                         replace_nestloop_params(root, (Node *) scan_clauses);
2389         }
2390
2391         scan_plan = make_seqscan(tlist,
2392                                                          scan_clauses,
2393                                                          scan_relid);
2394
2395         copy_generic_path_info(&scan_plan->plan, best_path);
2396
2397         return scan_plan;
2398 }
2399
2400 /*
2401  * create_samplescan_plan
2402  *       Returns a samplescan plan for the base relation scanned by 'best_path'
2403  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2404  */
2405 static SampleScan *
2406 create_samplescan_plan(PlannerInfo *root, Path *best_path,
2407                                            List *tlist, List *scan_clauses)
2408 {
2409         SampleScan *scan_plan;
2410         Index           scan_relid = best_path->parent->relid;
2411         RangeTblEntry *rte;
2412         TableSampleClause *tsc;
2413
2414         /* it should be a base rel with a tablesample clause... */
2415         Assert(scan_relid > 0);
2416         rte = planner_rt_fetch(scan_relid, root);
2417         Assert(rte->rtekind == RTE_RELATION);
2418         tsc = rte->tablesample;
2419         Assert(tsc != NULL);
2420
2421         /* Sort clauses into best execution order */
2422         scan_clauses = order_qual_clauses(root, scan_clauses);
2423
2424         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2425         scan_clauses = extract_actual_clauses(scan_clauses, false);
2426
2427         /* Replace any outer-relation variables with nestloop params */
2428         if (best_path->param_info)
2429         {
2430                 scan_clauses = (List *)
2431                         replace_nestloop_params(root, (Node *) scan_clauses);
2432                 tsc = (TableSampleClause *)
2433                         replace_nestloop_params(root, (Node *) tsc);
2434         }
2435
2436         scan_plan = make_samplescan(tlist,
2437                                                                 scan_clauses,
2438                                                                 scan_relid,
2439                                                                 tsc);
2440
2441         copy_generic_path_info(&scan_plan->scan.plan, best_path);
2442
2443         return scan_plan;
2444 }
2445
2446 /*
2447  * create_indexscan_plan
2448  *        Returns an indexscan plan for the base relation scanned by 'best_path'
2449  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2450  *
2451  * We use this for both plain IndexScans and IndexOnlyScans, because the
2452  * qual preprocessing work is the same for both.  Note that the caller tells
2453  * us which to build --- we don't look at best_path->path.pathtype, because
2454  * create_bitmap_subplan needs to be able to override the prior decision.
2455  */
2456 static Scan *
2457 create_indexscan_plan(PlannerInfo *root,
2458                                           IndexPath *best_path,
2459                                           List *tlist,
2460                                           List *scan_clauses,
2461                                           bool indexonly)
2462 {
2463         Scan       *scan_plan;
2464         List       *indexquals = best_path->indexquals;
2465         List       *indexorderbys = best_path->indexorderbys;
2466         Index           baserelid = best_path->path.parent->relid;
2467         Oid                     indexoid = best_path->indexinfo->indexoid;
2468         List       *qpqual;
2469         List       *stripped_indexquals;
2470         List       *fixed_indexquals;
2471         List       *fixed_indexorderbys;
2472         List       *indexorderbyops = NIL;
2473         ListCell   *l;
2474
2475         /* it should be a base rel... */
2476         Assert(baserelid > 0);
2477         Assert(best_path->path.parent->rtekind == RTE_RELATION);
2478
2479         /*
2480          * Build "stripped" indexquals structure (no RestrictInfos) to pass to
2481          * executor as indexqualorig
2482          */
2483         stripped_indexquals = get_actual_clauses(indexquals);
2484
2485         /*
2486          * The executor needs a copy with the indexkey on the left of each clause
2487          * and with index Vars substituted for table ones.
2488          */
2489         fixed_indexquals = fix_indexqual_references(root, best_path);
2490
2491         /*
2492          * Likewise fix up index attr references in the ORDER BY expressions.
2493          */
2494         fixed_indexorderbys = fix_indexorderby_references(root, best_path);
2495
2496         /*
2497          * The qpqual list must contain all restrictions not automatically handled
2498          * by the index, other than pseudoconstant clauses which will be handled
2499          * by a separate gating plan node.  All the predicates in the indexquals
2500          * will be checked (either by the index itself, or by nodeIndexscan.c),
2501          * but if there are any "special" operators involved then they must be
2502          * included in qpqual.  The upshot is that qpqual must contain
2503          * scan_clauses minus whatever appears in indexquals.
2504          *
2505          * In normal cases simple pointer equality checks will be enough to spot
2506          * duplicate RestrictInfos, so we try that first.
2507          *
2508          * Another common case is that a scan_clauses entry is generated from the
2509          * same EquivalenceClass as some indexqual, and is therefore redundant
2510          * with it, though not equal.  (This happens when indxpath.c prefers a
2511          * different derived equality than what generate_join_implied_equalities
2512          * picked for a parameterized scan's ppi_clauses.)
2513          *
2514          * In some situations (particularly with OR'd index conditions) we may
2515          * have scan_clauses that are not equal to, but are logically implied by,
2516          * the index quals; so we also try a predicate_implied_by() check to see
2517          * if we can discard quals that way.  (predicate_implied_by assumes its
2518          * first input contains only immutable functions, so we have to check
2519          * that.)
2520          *
2521          * Note: if you change this bit of code you should also look at
2522          * extract_nonindex_conditions() in costsize.c.
2523          */
2524         qpqual = NIL;
2525         foreach(l, scan_clauses)
2526         {
2527                 RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(l));
2528
2529                 if (rinfo->pseudoconstant)
2530                         continue;                       /* we may drop pseudoconstants here */
2531                 if (list_member_ptr(indexquals, rinfo))
2532                         continue;                       /* simple duplicate */
2533                 if (is_redundant_derived_clause(rinfo, indexquals))
2534                         continue;                       /* derived from same EquivalenceClass */
2535                 if (!contain_mutable_functions((Node *) rinfo->clause) &&
2536                         predicate_implied_by(list_make1(rinfo->clause), indexquals))
2537                         continue;                       /* provably implied by indexquals */
2538                 qpqual = lappend(qpqual, rinfo);
2539         }
2540
2541         /* Sort clauses into best execution order */
2542         qpqual = order_qual_clauses(root, qpqual);
2543
2544         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2545         qpqual = extract_actual_clauses(qpqual, false);
2546
2547         /*
2548          * We have to replace any outer-relation variables with nestloop params in
2549          * the indexqualorig, qpqual, and indexorderbyorig expressions.  A bit
2550          * annoying to have to do this separately from the processing in
2551          * fix_indexqual_references --- rethink this when generalizing the inner
2552          * indexscan support.  But note we can't really do this earlier because
2553          * it'd break the comparisons to predicates above ... (or would it?  Those
2554          * wouldn't have outer refs)
2555          */
2556         if (best_path->path.param_info)
2557         {
2558                 stripped_indexquals = (List *)
2559                         replace_nestloop_params(root, (Node *) stripped_indexquals);
2560                 qpqual = (List *)
2561                         replace_nestloop_params(root, (Node *) qpqual);
2562                 indexorderbys = (List *)
2563                         replace_nestloop_params(root, (Node *) indexorderbys);
2564         }
2565
2566         /*
2567          * If there are ORDER BY expressions, look up the sort operators for their
2568          * result datatypes.
2569          */
2570         if (indexorderbys)
2571         {
2572                 ListCell   *pathkeyCell,
2573                                    *exprCell;
2574
2575                 /*
2576                  * PathKey contains OID of the btree opfamily we're sorting by, but
2577                  * that's not quite enough because we need the expression's datatype
2578                  * to look up the sort operator in the operator family.
2579                  */
2580                 Assert(list_length(best_path->path.pathkeys) == list_length(indexorderbys));
2581                 forboth(pathkeyCell, best_path->path.pathkeys, exprCell, indexorderbys)
2582                 {
2583                         PathKey    *pathkey = (PathKey *) lfirst(pathkeyCell);
2584                         Node       *expr = (Node *) lfirst(exprCell);
2585                         Oid                     exprtype = exprType(expr);
2586                         Oid                     sortop;
2587
2588                         /* Get sort operator from opfamily */
2589                         sortop = get_opfamily_member(pathkey->pk_opfamily,
2590                                                                                  exprtype,
2591                                                                                  exprtype,
2592                                                                                  pathkey->pk_strategy);
2593                         if (!OidIsValid(sortop))
2594                                 elog(ERROR, "failed to find sort operator for ORDER BY expression");
2595                         indexorderbyops = lappend_oid(indexorderbyops, sortop);
2596                 }
2597         }
2598
2599         /* Finally ready to build the plan node */
2600         if (indexonly)
2601                 scan_plan = (Scan *) make_indexonlyscan(tlist,
2602                                                                                                 qpqual,
2603                                                                                                 baserelid,
2604                                                                                                 indexoid,
2605                                                                                                 fixed_indexquals,
2606                                                                                                 fixed_indexorderbys,
2607                                                                                         best_path->indexinfo->indextlist,
2608                                                                                                 best_path->indexscandir);
2609         else
2610                 scan_plan = (Scan *) make_indexscan(tlist,
2611                                                                                         qpqual,
2612                                                                                         baserelid,
2613                                                                                         indexoid,
2614                                                                                         fixed_indexquals,
2615                                                                                         stripped_indexquals,
2616                                                                                         fixed_indexorderbys,
2617                                                                                         indexorderbys,
2618                                                                                         indexorderbyops,
2619                                                                                         best_path->indexscandir);
2620
2621         copy_generic_path_info(&scan_plan->plan, &best_path->path);
2622
2623         return scan_plan;
2624 }
2625
2626 /*
2627  * create_bitmap_scan_plan
2628  *        Returns a bitmap scan plan for the base relation scanned by 'best_path'
2629  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2630  */
2631 static BitmapHeapScan *
2632 create_bitmap_scan_plan(PlannerInfo *root,
2633                                                 BitmapHeapPath *best_path,
2634                                                 List *tlist,
2635                                                 List *scan_clauses)
2636 {
2637         Index           baserelid = best_path->path.parent->relid;
2638         Plan       *bitmapqualplan;
2639         List       *bitmapqualorig;
2640         List       *indexquals;
2641         List       *indexECs;
2642         List       *qpqual;
2643         ListCell   *l;
2644         BitmapHeapScan *scan_plan;
2645
2646         /* it should be a base rel... */
2647         Assert(baserelid > 0);
2648         Assert(best_path->path.parent->rtekind == RTE_RELATION);
2649
2650         /* Process the bitmapqual tree into a Plan tree and qual lists */
2651         bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
2652                                                                                    &bitmapqualorig, &indexquals,
2653                                                                                    &indexECs);
2654
2655         if (best_path->path.parallel_aware)
2656                 bitmap_subplan_mark_shared(bitmapqualplan);
2657
2658         /*
2659          * The qpqual list must contain all restrictions not automatically handled
2660          * by the index, other than pseudoconstant clauses which will be handled
2661          * by a separate gating plan node.  All the predicates in the indexquals
2662          * will be checked (either by the index itself, or by
2663          * nodeBitmapHeapscan.c), but if there are any "special" operators
2664          * involved then they must be added to qpqual.  The upshot is that qpqual
2665          * must contain scan_clauses minus whatever appears in indexquals.
2666          *
2667          * This loop is similar to the comparable code in create_indexscan_plan(),
2668          * but with some differences because it has to compare the scan clauses to
2669          * stripped (no RestrictInfos) indexquals.  See comments there for more
2670          * info.
2671          *
2672          * In normal cases simple equal() checks will be enough to spot duplicate
2673          * clauses, so we try that first.  We next see if the scan clause is
2674          * redundant with any top-level indexqual by virtue of being generated
2675          * from the same EC.  After that, try predicate_implied_by().
2676          *
2677          * Unlike create_indexscan_plan(), the predicate_implied_by() test here is
2678          * useful for getting rid of qpquals that are implied by index predicates,
2679          * because the predicate conditions are included in the "indexquals"
2680          * returned by create_bitmap_subplan().  Bitmap scans have to do it that
2681          * way because predicate conditions need to be rechecked if the scan
2682          * becomes lossy, so they have to be included in bitmapqualorig.
2683          */
2684         qpqual = NIL;
2685         foreach(l, scan_clauses)
2686         {
2687                 RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(l));
2688                 Node       *clause = (Node *) rinfo->clause;
2689
2690                 if (rinfo->pseudoconstant)
2691                         continue;                       /* we may drop pseudoconstants here */
2692                 if (list_member(indexquals, clause))
2693                         continue;                       /* simple duplicate */
2694                 if (rinfo->parent_ec && list_member_ptr(indexECs, rinfo->parent_ec))
2695                         continue;                       /* derived from same EquivalenceClass */
2696                 if (!contain_mutable_functions(clause) &&
2697                         predicate_implied_by(list_make1(clause), indexquals))
2698                         continue;                       /* provably implied by indexquals */
2699                 qpqual = lappend(qpqual, rinfo);
2700         }
2701
2702         /* Sort clauses into best execution order */
2703         qpqual = order_qual_clauses(root, qpqual);
2704
2705         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2706         qpqual = extract_actual_clauses(qpqual, false);
2707
2708         /*
2709          * When dealing with special operators, we will at this point have
2710          * duplicate clauses in qpqual and bitmapqualorig.  We may as well drop
2711          * 'em from bitmapqualorig, since there's no point in making the tests
2712          * twice.
2713          */
2714         bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
2715
2716         /*
2717          * We have to replace any outer-relation variables with nestloop params in
2718          * the qpqual and bitmapqualorig expressions.  (This was already done for
2719          * expressions attached to plan nodes in the bitmapqualplan tree.)
2720          */
2721         if (best_path->path.param_info)
2722         {
2723                 qpqual = (List *)
2724                         replace_nestloop_params(root, (Node *) qpqual);
2725                 bitmapqualorig = (List *)
2726                         replace_nestloop_params(root, (Node *) bitmapqualorig);
2727         }
2728
2729         /* Finally ready to build the plan node */
2730         scan_plan = make_bitmap_heapscan(tlist,
2731                                                                          qpqual,
2732                                                                          bitmapqualplan,
2733                                                                          bitmapqualorig,
2734                                                                          baserelid);
2735
2736         copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
2737
2738         return scan_plan;
2739 }
2740
2741 /*
2742  * Given a bitmapqual tree, generate the Plan tree that implements it
2743  *
2744  * As byproducts, we also return in *qual and *indexqual the qual lists
2745  * (in implicit-AND form, without RestrictInfos) describing the original index
2746  * conditions and the generated indexqual conditions.  (These are the same in
2747  * simple cases, but when special index operators are involved, the former
2748  * list includes the special conditions while the latter includes the actual
2749  * indexable conditions derived from them.)  Both lists include partial-index
2750  * predicates, because we have to recheck predicates as well as index
2751  * conditions if the bitmap scan becomes lossy.
2752  *
2753  * In addition, we return a list of EquivalenceClass pointers for all the
2754  * top-level indexquals that were possibly-redundantly derived from ECs.
2755  * This allows removal of scan_clauses that are redundant with such quals.
2756  * (We do not attempt to detect such redundancies for quals that are within
2757  * OR subtrees.  This could be done in a less hacky way if we returned the
2758  * indexquals in RestrictInfo form, but that would be slower and still pretty
2759  * messy, since we'd have to build new RestrictInfos in many cases.)
2760  */
2761 static Plan *
2762 create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
2763                                           List **qual, List **indexqual, List **indexECs)
2764 {
2765         Plan       *plan;
2766
2767         if (IsA(bitmapqual, BitmapAndPath))
2768         {
2769                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
2770                 List       *subplans = NIL;
2771                 List       *subquals = NIL;
2772                 List       *subindexquals = NIL;
2773                 List       *subindexECs = NIL;
2774                 ListCell   *l;
2775
2776                 /*
2777                  * There may well be redundant quals among the subplans, since a
2778                  * top-level WHERE qual might have gotten used to form several
2779                  * different index quals.  We don't try exceedingly hard to eliminate
2780                  * redundancies, but we do eliminate obvious duplicates by using
2781                  * list_concat_unique.
2782                  */
2783                 foreach(l, apath->bitmapquals)
2784                 {
2785                         Plan       *subplan;
2786                         List       *subqual;
2787                         List       *subindexqual;
2788                         List       *subindexEC;
2789
2790                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
2791                                                                                         &subqual, &subindexqual,
2792                                                                                         &subindexEC);
2793                         subplans = lappend(subplans, subplan);
2794                         subquals = list_concat_unique(subquals, subqual);
2795                         subindexquals = list_concat_unique(subindexquals, subindexqual);
2796                         /* Duplicates in indexECs aren't worth getting rid of */
2797                         subindexECs = list_concat(subindexECs, subindexEC);
2798                 }
2799                 plan = (Plan *) make_bitmap_and(subplans);
2800                 plan->startup_cost = apath->path.startup_cost;
2801                 plan->total_cost = apath->path.total_cost;
2802                 plan->plan_rows =
2803                         clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
2804                 plan->plan_width = 0;   /* meaningless */
2805                 plan->parallel_aware = false;
2806                 *qual = subquals;
2807                 *indexqual = subindexquals;
2808                 *indexECs = subindexECs;
2809         }
2810         else if (IsA(bitmapqual, BitmapOrPath))
2811         {
2812                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
2813                 List       *subplans = NIL;
2814                 List       *subquals = NIL;
2815                 List       *subindexquals = NIL;
2816                 bool            const_true_subqual = false;
2817                 bool            const_true_subindexqual = false;
2818                 ListCell   *l;
2819
2820                 /*
2821                  * Here, we only detect qual-free subplans.  A qual-free subplan would
2822                  * cause us to generate "... OR true ..."  which we may as well reduce
2823                  * to just "true".  We do not try to eliminate redundant subclauses
2824                  * because (a) it's not as likely as in the AND case, and (b) we might
2825                  * well be working with hundreds or even thousands of OR conditions,
2826                  * perhaps from a long IN list.  The performance of list_append_unique
2827                  * would be unacceptable.
2828                  */
2829                 foreach(l, opath->bitmapquals)
2830                 {
2831                         Plan       *subplan;
2832                         List       *subqual;
2833                         List       *subindexqual;
2834                         List       *subindexEC;
2835
2836                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
2837                                                                                         &subqual, &subindexqual,
2838                                                                                         &subindexEC);
2839                         subplans = lappend(subplans, subplan);
2840                         if (subqual == NIL)
2841                                 const_true_subqual = true;
2842                         else if (!const_true_subqual)
2843                                 subquals = lappend(subquals,
2844                                                                    make_ands_explicit(subqual));
2845                         if (subindexqual == NIL)
2846                                 const_true_subindexqual = true;
2847                         else if (!const_true_subindexqual)
2848                                 subindexquals = lappend(subindexquals,
2849                                                                                 make_ands_explicit(subindexqual));
2850                 }
2851
2852                 /*
2853                  * In the presence of ScalarArrayOpExpr quals, we might have built
2854                  * BitmapOrPaths with just one subpath; don't add an OR step.
2855                  */
2856                 if (list_length(subplans) == 1)
2857                 {
2858                         plan = (Plan *) linitial(subplans);
2859                 }
2860                 else
2861                 {
2862                         plan = (Plan *) make_bitmap_or(subplans);
2863                         plan->startup_cost = opath->path.startup_cost;
2864                         plan->total_cost = opath->path.total_cost;
2865                         plan->plan_rows =
2866                                 clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
2867                         plan->plan_width = 0;           /* meaningless */
2868                         plan->parallel_aware = false;
2869                 }
2870
2871                 /*
2872                  * If there were constant-TRUE subquals, the OR reduces to constant
2873                  * TRUE.  Also, avoid generating one-element ORs, which could happen
2874                  * due to redundancy elimination or ScalarArrayOpExpr quals.
2875                  */
2876                 if (const_true_subqual)
2877                         *qual = NIL;
2878                 else if (list_length(subquals) <= 1)
2879                         *qual = subquals;
2880                 else
2881                         *qual = list_make1(make_orclause(subquals));
2882                 if (const_true_subindexqual)
2883                         *indexqual = NIL;
2884                 else if (list_length(subindexquals) <= 1)
2885                         *indexqual = subindexquals;
2886                 else
2887                         *indexqual = list_make1(make_orclause(subindexquals));
2888                 *indexECs = NIL;
2889         }
2890         else if (IsA(bitmapqual, IndexPath))
2891         {
2892                 IndexPath  *ipath = (IndexPath *) bitmapqual;
2893                 IndexScan  *iscan;
2894                 List       *subindexECs;
2895                 ListCell   *l;
2896
2897                 /* Use the regular indexscan plan build machinery... */
2898                 iscan = castNode(IndexScan,
2899                                                  create_indexscan_plan(root, ipath,
2900                                                                                            NIL, NIL, false));
2901                 /* then convert to a bitmap indexscan */
2902                 plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
2903                                                                                           iscan->indexid,
2904                                                                                           iscan->indexqual,
2905                                                                                           iscan->indexqualorig);
2906                 /* and set its cost/width fields appropriately */
2907                 plan->startup_cost = 0.0;
2908                 plan->total_cost = ipath->indextotalcost;
2909                 plan->plan_rows =
2910                         clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
2911                 plan->plan_width = 0;   /* meaningless */
2912                 plan->parallel_aware = false;
2913                 *qual = get_actual_clauses(ipath->indexclauses);
2914                 *indexqual = get_actual_clauses(ipath->indexquals);
2915                 foreach(l, ipath->indexinfo->indpred)
2916                 {
2917                         Expr       *pred = (Expr *) lfirst(l);
2918
2919                         /*
2920                          * We know that the index predicate must have been implied by the
2921                          * query condition as a whole, but it may or may not be implied by
2922                          * the conditions that got pushed into the bitmapqual.  Avoid
2923                          * generating redundant conditions.
2924                          */
2925                         if (!predicate_implied_by(list_make1(pred), ipath->indexclauses))
2926                         {
2927                                 *qual = lappend(*qual, pred);
2928                                 *indexqual = lappend(*indexqual, pred);
2929                         }
2930                 }
2931                 subindexECs = NIL;
2932                 foreach(l, ipath->indexquals)
2933                 {
2934                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
2935
2936                         if (rinfo->parent_ec)
2937                                 subindexECs = lappend(subindexECs, rinfo->parent_ec);
2938                 }
2939                 *indexECs = subindexECs;
2940         }
2941         else
2942         {
2943                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
2944                 plan = NULL;                    /* keep compiler quiet */
2945         }
2946
2947         return plan;
2948 }
2949
2950 /*
2951  * create_tidscan_plan
2952  *       Returns a tidscan plan for the base relation scanned by 'best_path'
2953  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2954  */
2955 static TidScan *
2956 create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
2957                                         List *tlist, List *scan_clauses)
2958 {
2959         TidScan    *scan_plan;
2960         Index           scan_relid = best_path->path.parent->relid;
2961         List       *tidquals = best_path->tidquals;
2962         List       *ortidquals;
2963
2964         /* it should be a base rel... */
2965         Assert(scan_relid > 0);
2966         Assert(best_path->path.parent->rtekind == RTE_RELATION);
2967
2968         /* Sort clauses into best execution order */
2969         scan_clauses = order_qual_clauses(root, scan_clauses);
2970
2971         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2972         scan_clauses = extract_actual_clauses(scan_clauses, false);
2973
2974         /* Replace any outer-relation variables with nestloop params */
2975         if (best_path->path.param_info)
2976         {
2977                 tidquals = (List *)
2978                         replace_nestloop_params(root, (Node *) tidquals);
2979                 scan_clauses = (List *)
2980                         replace_nestloop_params(root, (Node *) scan_clauses);
2981         }
2982
2983         /*
2984          * Remove any clauses that are TID quals.  This is a bit tricky since the
2985          * tidquals list has implicit OR semantics.
2986          */
2987         ortidquals = tidquals;
2988         if (list_length(ortidquals) > 1)
2989                 ortidquals = list_make1(make_orclause(ortidquals));
2990         scan_clauses = list_difference(scan_clauses, ortidquals);
2991
2992         scan_plan = make_tidscan(tlist,
2993                                                          scan_clauses,
2994                                                          scan_relid,
2995                                                          tidquals);
2996
2997         copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
2998
2999         return scan_plan;
3000 }
3001
3002 /*
3003  * create_subqueryscan_plan
3004  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
3005  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3006  */
3007 static SubqueryScan *
3008 create_subqueryscan_plan(PlannerInfo *root, SubqueryScanPath *best_path,
3009                                                  List *tlist, List *scan_clauses)
3010 {
3011         SubqueryScan *scan_plan;
3012         RelOptInfo *rel = best_path->path.parent;
3013         Index           scan_relid = rel->relid;
3014         Plan       *subplan;
3015
3016         /* it should be a subquery base rel... */
3017         Assert(scan_relid > 0);
3018         Assert(rel->rtekind == RTE_SUBQUERY);
3019
3020         /*
3021          * Recursively create Plan from Path for subquery.  Since we are entering
3022          * a different planner context (subroot), recurse to create_plan not
3023          * create_plan_recurse.
3024          */
3025         subplan = create_plan(rel->subroot, best_path->subpath);
3026
3027         /* Sort clauses into best execution order */
3028         scan_clauses = order_qual_clauses(root, scan_clauses);
3029
3030         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3031         scan_clauses = extract_actual_clauses(scan_clauses, false);
3032
3033         /* Replace any outer-relation variables with nestloop params */
3034         if (best_path->path.param_info)
3035         {
3036                 scan_clauses = (List *)
3037                         replace_nestloop_params(root, (Node *) scan_clauses);
3038                 process_subquery_nestloop_params(root,
3039                                                                                  rel->subplan_params);
3040         }
3041
3042         scan_plan = make_subqueryscan(tlist,
3043                                                                   scan_clauses,
3044                                                                   scan_relid,
3045                                                                   subplan);
3046
3047         copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
3048
3049         return scan_plan;
3050 }
3051
3052 /*
3053  * create_functionscan_plan
3054  *       Returns a functionscan plan for the base relation scanned by 'best_path'
3055  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3056  */
3057 static FunctionScan *
3058 create_functionscan_plan(PlannerInfo *root, Path *best_path,
3059                                                  List *tlist, List *scan_clauses)
3060 {
3061         FunctionScan *scan_plan;
3062         Index           scan_relid = best_path->parent->relid;
3063         RangeTblEntry *rte;
3064         List       *functions;
3065
3066         /* it should be a function base rel... */
3067         Assert(scan_relid > 0);
3068         rte = planner_rt_fetch(scan_relid, root);
3069         Assert(rte->rtekind == RTE_FUNCTION);
3070         functions = rte->functions;
3071
3072         /* Sort clauses into best execution order */
3073         scan_clauses = order_qual_clauses(root, scan_clauses);
3074
3075         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3076         scan_clauses = extract_actual_clauses(scan_clauses, false);
3077
3078         /* Replace any outer-relation variables with nestloop params */
3079         if (best_path->param_info)
3080         {
3081                 scan_clauses = (List *)
3082                         replace_nestloop_params(root, (Node *) scan_clauses);
3083                 /* The function expressions could contain nestloop params, too */
3084                 functions = (List *) replace_nestloop_params(root, (Node *) functions);
3085         }
3086
3087         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
3088                                                                   functions, rte->funcordinality);
3089
3090         copy_generic_path_info(&scan_plan->scan.plan, best_path);
3091
3092         return scan_plan;
3093 }
3094
3095 /*
3096  * create_tablefuncscan_plan
3097  *       Returns a tablefuncscan plan for the base relation scanned by 'best_path'
3098  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3099  */
3100 static TableFuncScan *
3101 create_tablefuncscan_plan(PlannerInfo *root, Path *best_path,
3102                                                   List *tlist, List *scan_clauses)
3103 {
3104         TableFuncScan *scan_plan;
3105         Index           scan_relid = best_path->parent->relid;
3106         RangeTblEntry *rte;
3107         TableFunc  *tablefunc;
3108
3109         /* it should be a function base rel... */
3110         Assert(scan_relid > 0);
3111         rte = planner_rt_fetch(scan_relid, root);
3112         Assert(rte->rtekind == RTE_TABLEFUNC);
3113         tablefunc = rte->tablefunc;
3114
3115         /* Sort clauses into best execution order */
3116         scan_clauses = order_qual_clauses(root, scan_clauses);
3117
3118         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3119         scan_clauses = extract_actual_clauses(scan_clauses, false);
3120
3121         /* Replace any outer-relation variables with nestloop params */
3122         if (best_path->param_info)
3123         {
3124                 scan_clauses = (List *)
3125                         replace_nestloop_params(root, (Node *) scan_clauses);
3126                 /* The function expressions could contain nestloop params, too */
3127                 tablefunc = (TableFunc *) replace_nestloop_params(root, (Node *) tablefunc);
3128         }
3129
3130         scan_plan = make_tablefuncscan(tlist, scan_clauses, scan_relid,
3131                                                                    tablefunc);
3132
3133         copy_generic_path_info(&scan_plan->scan.plan, best_path);
3134
3135         return scan_plan;
3136 }
3137
3138 /*
3139  * create_valuesscan_plan
3140  *       Returns a valuesscan plan for the base relation scanned by 'best_path'
3141  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3142  */
3143 static ValuesScan *
3144 create_valuesscan_plan(PlannerInfo *root, Path *best_path,
3145                                            List *tlist, List *scan_clauses)
3146 {
3147         ValuesScan *scan_plan;
3148         Index           scan_relid = best_path->parent->relid;
3149         RangeTblEntry *rte;
3150         List       *values_lists;
3151
3152         /* it should be a values base rel... */
3153         Assert(scan_relid > 0);
3154         rte = planner_rt_fetch(scan_relid, root);
3155         Assert(rte->rtekind == RTE_VALUES);
3156         values_lists = rte->values_lists;
3157
3158         /* Sort clauses into best execution order */
3159         scan_clauses = order_qual_clauses(root, scan_clauses);
3160
3161         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3162         scan_clauses = extract_actual_clauses(scan_clauses, false);
3163
3164         /* Replace any outer-relation variables with nestloop params */
3165         if (best_path->param_info)
3166         {
3167                 scan_clauses = (List *)
3168                         replace_nestloop_params(root, (Node *) scan_clauses);
3169                 /* The values lists could contain nestloop params, too */
3170                 values_lists = (List *)
3171                         replace_nestloop_params(root, (Node *) values_lists);
3172         }
3173
3174         scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
3175                                                                 values_lists);
3176
3177         copy_generic_path_info(&scan_plan->scan.plan, best_path);
3178
3179         return scan_plan;
3180 }
3181
3182 /*
3183  * create_ctescan_plan
3184  *       Returns a ctescan plan for the base relation scanned by 'best_path'
3185  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3186  */
3187 static CteScan *
3188 create_ctescan_plan(PlannerInfo *root, Path *best_path,
3189                                         List *tlist, List *scan_clauses)
3190 {
3191         CteScan    *scan_plan;
3192         Index           scan_relid = best_path->parent->relid;
3193         RangeTblEntry *rte;
3194         SubPlan    *ctesplan = NULL;
3195         int                     plan_id;
3196         int                     cte_param_id;
3197         PlannerInfo *cteroot;
3198         Index           levelsup;
3199         int                     ndx;
3200         ListCell   *lc;
3201
3202         Assert(scan_relid > 0);
3203         rte = planner_rt_fetch(scan_relid, root);
3204         Assert(rte->rtekind == RTE_CTE);
3205         Assert(!rte->self_reference);
3206
3207         /*
3208          * Find the referenced CTE, and locate the SubPlan previously made for it.
3209          */
3210         levelsup = rte->ctelevelsup;
3211         cteroot = root;
3212         while (levelsup-- > 0)
3213         {
3214                 cteroot = cteroot->parent_root;
3215                 if (!cteroot)                   /* shouldn't happen */
3216                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3217         }
3218
3219         /*
3220          * Note: cte_plan_ids can be shorter than cteList, if we are still working
3221          * on planning the CTEs (ie, this is a side-reference from another CTE).
3222          * So we mustn't use forboth here.
3223          */
3224         ndx = 0;
3225         foreach(lc, cteroot->parse->cteList)
3226         {
3227                 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
3228
3229                 if (strcmp(cte->ctename, rte->ctename) == 0)
3230                         break;
3231                 ndx++;
3232         }
3233         if (lc == NULL)                         /* shouldn't happen */
3234                 elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
3235         if (ndx >= list_length(cteroot->cte_plan_ids))
3236                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
3237         plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
3238         Assert(plan_id > 0);
3239         foreach(lc, cteroot->init_plans)
3240         {
3241                 ctesplan = (SubPlan *) lfirst(lc);
3242                 if (ctesplan->plan_id == plan_id)
3243                         break;
3244         }
3245         if (lc == NULL)                         /* shouldn't happen */
3246                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
3247
3248         /*
3249          * We need the CTE param ID, which is the sole member of the SubPlan's
3250          * setParam list.
3251          */
3252         cte_param_id = linitial_int(ctesplan->setParam);
3253
3254         /* Sort clauses into best execution order */
3255         scan_clauses = order_qual_clauses(root, scan_clauses);
3256
3257         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3258         scan_clauses = extract_actual_clauses(scan_clauses, false);
3259
3260         /* Replace any outer-relation variables with nestloop params */
3261         if (best_path->param_info)
3262         {
3263                 scan_clauses = (List *)
3264                         replace_nestloop_params(root, (Node *) scan_clauses);
3265         }
3266
3267         scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
3268                                                          plan_id, cte_param_id);
3269
3270         copy_generic_path_info(&scan_plan->scan.plan, best_path);
3271
3272         return scan_plan;
3273 }
3274
3275 /*
3276  * create_worktablescan_plan
3277  *       Returns a worktablescan plan for the base relation scanned by 'best_path'
3278  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3279  */
3280 static WorkTableScan *
3281 create_worktablescan_plan(PlannerInfo *root, Path *best_path,
3282                                                   List *tlist, List *scan_clauses)
3283 {
3284         WorkTableScan *scan_plan;
3285         Index           scan_relid = best_path->parent->relid;
3286         RangeTblEntry *rte;
3287         Index           levelsup;
3288         PlannerInfo *cteroot;
3289
3290         Assert(scan_relid > 0);
3291         rte = planner_rt_fetch(scan_relid, root);
3292         Assert(rte->rtekind == RTE_CTE);
3293         Assert(rte->self_reference);
3294
3295         /*
3296          * We need to find the worktable param ID, which is in the plan level
3297          * that's processing the recursive UNION, which is one level *below* where
3298          * the CTE comes from.
3299          */
3300         levelsup = rte->ctelevelsup;
3301         if (levelsup == 0)                      /* shouldn't happen */
3302                 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3303         levelsup--;
3304         cteroot = root;
3305         while (levelsup-- > 0)
3306         {
3307                 cteroot = cteroot->parent_root;
3308                 if (!cteroot)                   /* shouldn't happen */
3309                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3310         }
3311         if (cteroot->wt_param_id < 0)           /* shouldn't happen */
3312                 elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename);
3313
3314         /* Sort clauses into best execution order */
3315         scan_clauses = order_qual_clauses(root, scan_clauses);
3316
3317         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3318         scan_clauses = extract_actual_clauses(scan_clauses, false);
3319
3320         /* Replace any outer-relation variables with nestloop params */
3321         if (best_path->param_info)
3322         {
3323                 scan_clauses = (List *)
3324                         replace_nestloop_params(root, (Node *) scan_clauses);
3325         }
3326
3327         scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
3328                                                                    cteroot->wt_param_id);
3329
3330         copy_generic_path_info(&scan_plan->scan.plan, best_path);
3331
3332         return scan_plan;
3333 }
3334
3335 /*
3336  * create_foreignscan_plan
3337  *       Returns a foreignscan plan for the relation scanned by 'best_path'
3338  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3339  */
3340 static ForeignScan *
3341 create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
3342                                                 List *tlist, List *scan_clauses)
3343 {
3344         ForeignScan *scan_plan;
3345         RelOptInfo *rel = best_path->path.parent;
3346         Index           scan_relid = rel->relid;
3347         Oid                     rel_oid = InvalidOid;
3348         Plan       *outer_plan = NULL;
3349
3350         Assert(rel->fdwroutine != NULL);
3351
3352         /* transform the child path if any */
3353         if (best_path->fdw_outerpath)
3354                 outer_plan = create_plan_recurse(root, best_path->fdw_outerpath,
3355                                                                                  CP_EXACT_TLIST);
3356
3357         /*
3358          * If we're scanning a base relation, fetch its OID.  (Irrelevant if
3359          * scanning a join relation.)
3360          */
3361         if (scan_relid > 0)
3362         {
3363                 RangeTblEntry *rte;
3364
3365                 Assert(rel->rtekind == RTE_RELATION);
3366                 rte = planner_rt_fetch(scan_relid, root);
3367                 Assert(rte->rtekind == RTE_RELATION);
3368                 rel_oid = rte->relid;
3369         }
3370
3371         /*
3372          * Sort clauses into best execution order.  We do this first since the FDW
3373          * might have more info than we do and wish to adjust the ordering.
3374          */
3375         scan_clauses = order_qual_clauses(root, scan_clauses);
3376
3377         /*
3378          * Let the FDW perform its processing on the restriction clauses and
3379          * generate the plan node.  Note that the FDW might remove restriction
3380          * clauses that it intends to execute remotely, or even add more (if it
3381          * has selected some join clauses for remote use but also wants them
3382          * rechecked locally).
3383          */
3384         scan_plan = rel->fdwroutine->GetForeignPlan(root, rel, rel_oid,
3385                                                                                                 best_path,
3386                                                                                                 tlist, scan_clauses,
3387                                                                                                 outer_plan);
3388
3389         /* Copy cost data from Path to Plan; no need to make FDW do this */
3390         copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
3391
3392         /* Copy foreign server OID; likewise, no need to make FDW do this */
3393         scan_plan->fs_server = rel->serverid;
3394
3395         /*
3396          * Likewise, copy the relids that are represented by this foreign scan. An
3397          * upper rel doesn't have relids set, but it covers all the base relations
3398          * participating in the underlying scan, so use root's all_baserels.
3399          */
3400         if (rel->reloptkind == RELOPT_UPPER_REL)
3401                 scan_plan->fs_relids = root->all_baserels;
3402         else
3403                 scan_plan->fs_relids = best_path->path.parent->relids;
3404
3405         /*
3406          * If this is a foreign join, and to make it valid to push down we had to
3407          * assume that the current user is the same as some user explicitly named
3408          * in the query, mark the finished plan as depending on the current user.
3409          */
3410         if (rel->useridiscurrent)
3411                 root->glob->dependsOnRole = true;
3412
3413         /*
3414          * Replace any outer-relation variables with nestloop params in the qual,
3415          * fdw_exprs and fdw_recheck_quals expressions.  We do this last so that
3416          * the FDW doesn't have to be involved.  (Note that parts of fdw_exprs or
3417          * fdw_recheck_quals could have come from join clauses, so doing this
3418          * beforehand on the scan_clauses wouldn't work.)  We assume
3419          * fdw_scan_tlist contains no such variables.
3420          */
3421         if (best_path->path.param_info)
3422         {
3423                 scan_plan->scan.plan.qual = (List *)
3424                         replace_nestloop_params(root, (Node *) scan_plan->scan.plan.qual);
3425                 scan_plan->fdw_exprs = (List *)
3426                         replace_nestloop_params(root, (Node *) scan_plan->fdw_exprs);
3427                 scan_plan->fdw_recheck_quals = (List *)
3428                         replace_nestloop_params(root,
3429                                                                         (Node *) scan_plan->fdw_recheck_quals);
3430         }
3431
3432         /*
3433          * If rel is a base relation, detect whether any system columns are
3434          * requested from the rel.  (If rel is a join relation, rel->relid will be
3435          * 0, but there can be no Var with relid 0 in the rel's targetlist or the
3436          * restriction clauses, so we skip this in that case.  Note that any such
3437          * columns in base relations that were joined are assumed to be contained
3438          * in fdw_scan_tlist.)  This is a bit of a kluge and might go away
3439          * someday, so we intentionally leave it out of the API presented to FDWs.
3440          */
3441         scan_plan->fsSystemCol = false;
3442         if (scan_relid > 0)
3443         {
3444                 Bitmapset  *attrs_used = NULL;
3445                 ListCell   *lc;
3446                 int                     i;
3447
3448                 /*
3449                  * First, examine all the attributes needed for joins or final output.
3450                  * Note: we must look at rel's targetlist, not the attr_needed data,
3451                  * because attr_needed isn't computed for inheritance child rels.
3452                  */
3453                 pull_varattnos((Node *) rel->reltarget->exprs, scan_relid, &attrs_used);
3454
3455                 /* Add all the attributes used by restriction clauses. */
3456                 foreach(lc, rel->baserestrictinfo)
3457                 {
3458                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3459
3460                         pull_varattnos((Node *) rinfo->clause, scan_relid, &attrs_used);
3461                 }
3462
3463                 /* Now, are any system columns requested from rel? */
3464                 for (i = FirstLowInvalidHeapAttributeNumber + 1; i < 0; i++)
3465                 {
3466                         if (bms_is_member(i - FirstLowInvalidHeapAttributeNumber, attrs_used))
3467                         {
3468                                 scan_plan->fsSystemCol = true;
3469                                 break;
3470                         }
3471                 }
3472
3473                 bms_free(attrs_used);
3474         }
3475
3476         return scan_plan;
3477 }
3478
3479 /*
3480  * create_custom_plan
3481  *
3482  * Transform a CustomPath into a Plan.
3483  */
3484 static CustomScan *
3485 create_customscan_plan(PlannerInfo *root, CustomPath *best_path,
3486                                            List *tlist, List *scan_clauses)
3487 {
3488         CustomScan *cplan;
3489         RelOptInfo *rel = best_path->path.parent;
3490         List       *custom_plans = NIL;
3491         ListCell   *lc;
3492
3493         /* Recursively transform child paths. */
3494         foreach(lc, best_path->custom_paths)
3495         {
3496                 Plan       *plan = create_plan_recurse(root, (Path *) lfirst(lc),
3497                                                                                            CP_EXACT_TLIST);
3498
3499                 custom_plans = lappend(custom_plans, plan);
3500         }
3501
3502         /*
3503          * Sort clauses into the best execution order, although custom-scan
3504          * provider can reorder them again.
3505          */
3506         scan_clauses = order_qual_clauses(root, scan_clauses);
3507
3508         /*
3509          * Invoke custom plan provider to create the Plan node represented by the
3510          * CustomPath.
3511          */
3512         cplan = castNode(CustomScan,
3513                                          best_path->methods->PlanCustomPath(root,
3514                                                                                                                 rel,
3515                                                                                                                 best_path,
3516                                                                                                                 tlist,
3517                                                                                                                 scan_clauses,
3518                                                                                                                 custom_plans));
3519
3520         /*
3521          * Copy cost data from Path to Plan; no need to make custom-plan providers
3522          * do this
3523          */
3524         copy_generic_path_info(&cplan->scan.plan, &best_path->path);
3525
3526         /* Likewise, copy the relids that are represented by this custom scan */
3527         cplan->custom_relids = best_path->path.parent->relids;
3528
3529         /*
3530          * Replace any outer-relation variables with nestloop params in the qual
3531          * and custom_exprs expressions.  We do this last so that the custom-plan
3532          * provider doesn't have to be involved.  (Note that parts of custom_exprs
3533          * could have come from join clauses, so doing this beforehand on the
3534          * scan_clauses wouldn't work.)  We assume custom_scan_tlist contains no
3535          * such variables.
3536          */
3537         if (best_path->path.param_info)
3538         {
3539                 cplan->scan.plan.qual = (List *)
3540                         replace_nestloop_params(root, (Node *) cplan->scan.plan.qual);
3541                 cplan->custom_exprs = (List *)
3542                         replace_nestloop_params(root, (Node *) cplan->custom_exprs);
3543         }
3544
3545         return cplan;
3546 }
3547
3548
3549 /*****************************************************************************
3550  *
3551  *      JOIN METHODS
3552  *
3553  *****************************************************************************/
3554
3555 static NestLoop *
3556 create_nestloop_plan(PlannerInfo *root,
3557                                          NestPath *best_path)
3558 {
3559         NestLoop   *join_plan;
3560         Plan       *outer_plan;
3561         Plan       *inner_plan;
3562         List       *tlist = build_path_tlist(root, &best_path->path);
3563         List       *joinrestrictclauses = best_path->joinrestrictinfo;
3564         List       *joinclauses;
3565         List       *otherclauses;
3566         Relids          outerrelids;
3567         List       *nestParams;
3568         Relids          saveOuterRels = root->curOuterRels;
3569         ListCell   *cell;
3570         ListCell   *prev;
3571         ListCell   *next;
3572
3573         /* NestLoop can project, so no need to be picky about child tlists */
3574         outer_plan = create_plan_recurse(root, best_path->outerjoinpath, 0);
3575
3576         /* For a nestloop, include outer relids in curOuterRels for inner side */
3577         root->curOuterRels = bms_union(root->curOuterRels,
3578                                                                    best_path->outerjoinpath->parent->relids);
3579
3580         inner_plan = create_plan_recurse(root, best_path->innerjoinpath, 0);
3581
3582         /* Restore curOuterRels */
3583         bms_free(root->curOuterRels);
3584         root->curOuterRels = saveOuterRels;
3585
3586         /* Sort join qual clauses into best execution order */
3587         joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
3588
3589         /* Get the join qual clauses (in plain expression form) */
3590         /* Any pseudoconstant clauses are ignored here */
3591         if (IS_OUTER_JOIN(best_path->jointype))
3592         {
3593                 extract_actual_join_clauses(joinrestrictclauses,
3594                                                                         &joinclauses, &otherclauses);
3595         }
3596         else
3597         {
3598                 /* We can treat all clauses alike for an inner join */
3599                 joinclauses = extract_actual_clauses(joinrestrictclauses, false);
3600                 otherclauses = NIL;
3601         }
3602
3603         /* Replace any outer-relation variables with nestloop params */
3604         if (best_path->path.param_info)
3605         {
3606                 joinclauses = (List *)
3607                         replace_nestloop_params(root, (Node *) joinclauses);
3608                 otherclauses = (List *)
3609                         replace_nestloop_params(root, (Node *) otherclauses);
3610         }
3611
3612         /*
3613          * Identify any nestloop parameters that should be supplied by this join
3614          * node, and move them from root->curOuterParams to the nestParams list.
3615          */
3616         outerrelids = best_path->outerjoinpath->parent->relids;
3617         nestParams = NIL;
3618         prev = NULL;
3619         for (cell = list_head(root->curOuterParams); cell; cell = next)
3620         {
3621                 NestLoopParam *nlp = (NestLoopParam *) lfirst(cell);
3622
3623                 next = lnext(cell);
3624                 if (IsA(nlp->paramval, Var) &&
3625                         bms_is_member(nlp->paramval->varno, outerrelids))
3626                 {
3627                         root->curOuterParams = list_delete_cell(root->curOuterParams,
3628                                                                                                         cell, prev);
3629                         nestParams = lappend(nestParams, nlp);
3630                 }
3631                 else if (IsA(nlp->paramval, PlaceHolderVar) &&
3632                                  bms_overlap(((PlaceHolderVar *) nlp->paramval)->phrels,
3633                                                          outerrelids) &&
3634                                  bms_is_subset(find_placeholder_info(root,
3635                                                                                         (PlaceHolderVar *) nlp->paramval,
3636                                                                                                          false)->ph_eval_at,
3637                                                            outerrelids))
3638                 {
3639                         root->curOuterParams = list_delete_cell(root->curOuterParams,
3640                                                                                                         cell, prev);
3641                         nestParams = lappend(nestParams, nlp);
3642                 }
3643                 else
3644                         prev = cell;
3645         }
3646
3647         join_plan = make_nestloop(tlist,
3648                                                           joinclauses,
3649                                                           otherclauses,
3650                                                           nestParams,
3651                                                           outer_plan,
3652                                                           inner_plan,
3653                                                           best_path->jointype);
3654
3655         copy_generic_path_info(&join_plan->join.plan, &best_path->path);
3656
3657         return join_plan;
3658 }
3659
3660 static MergeJoin *
3661 create_mergejoin_plan(PlannerInfo *root,
3662                                           MergePath *best_path)
3663 {
3664         MergeJoin  *join_plan;
3665         Plan       *outer_plan;
3666         Plan       *inner_plan;
3667         List       *tlist = build_path_tlist(root, &best_path->jpath.path);
3668         List       *joinclauses;
3669         List       *otherclauses;
3670         List       *mergeclauses;
3671         List       *outerpathkeys;
3672         List       *innerpathkeys;
3673         int                     nClauses;
3674         Oid                *mergefamilies;
3675         Oid                *mergecollations;
3676         int                *mergestrategies;
3677         bool       *mergenullsfirst;
3678         int                     i;
3679         ListCell   *lc;
3680         ListCell   *lop;
3681         ListCell   *lip;
3682
3683         /*
3684          * MergeJoin can project, so we don't have to demand exact tlists from the
3685          * inputs.  However, if we're intending to sort an input's result, it's
3686          * best to request a small tlist so we aren't sorting more data than
3687          * necessary.
3688          */
3689         outer_plan = create_plan_recurse(root, best_path->jpath.outerjoinpath,
3690                                          (best_path->outersortkeys != NIL) ? CP_SMALL_TLIST : 0);
3691
3692         inner_plan = create_plan_recurse(root, best_path->jpath.innerjoinpath,
3693                                          (best_path->innersortkeys != NIL) ? CP_SMALL_TLIST : 0);
3694
3695         /* Sort join qual clauses into best execution order */
3696         /* NB: do NOT reorder the mergeclauses */
3697         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
3698
3699         /* Get the join qual clauses (in plain expression form) */
3700         /* Any pseudoconstant clauses are ignored here */
3701         if (IS_OUTER_JOIN(best_path->jpath.jointype))
3702         {
3703                 extract_actual_join_clauses(joinclauses,
3704                                                                         &joinclauses, &otherclauses);
3705         }
3706         else
3707         {
3708                 /* We can treat all clauses alike for an inner join */
3709                 joinclauses = extract_actual_clauses(joinclauses, false);
3710                 otherclauses = NIL;
3711         }
3712
3713         /*
3714          * Remove the mergeclauses from the list of join qual clauses, leaving the
3715          * list of quals that must be checked as qpquals.
3716          */
3717         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
3718         joinclauses = list_difference(joinclauses, mergeclauses);
3719
3720         /*
3721          * Replace any outer-relation variables with nestloop params.  There
3722          * should not be any in the mergeclauses.
3723          */
3724         if (best_path->jpath.path.param_info)
3725         {
3726                 joinclauses = (List *)
3727                         replace_nestloop_params(root, (Node *) joinclauses);
3728                 otherclauses = (List *)
3729                         replace_nestloop_params(root, (Node *) otherclauses);
3730         }
3731
3732         /*
3733          * Rearrange mergeclauses, if needed, so that the outer variable is always
3734          * on the left; mark the mergeclause restrictinfos with correct
3735          * outer_is_left status.
3736          */
3737         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
3738                                                          best_path->jpath.outerjoinpath->parent->relids);
3739
3740         /*
3741          * Create explicit sort nodes for the outer and inner paths if necessary.
3742          */
3743         if (best_path->outersortkeys)
3744         {
3745                 Sort       *sort = make_sort_from_pathkeys(outer_plan,
3746                                                                                                    best_path->outersortkeys);
3747
3748                 label_sort_with_costsize(root, sort, -1.0);
3749                 outer_plan = (Plan *) sort;
3750                 outerpathkeys = best_path->outersortkeys;
3751         }
3752         else
3753                 outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;
3754
3755         if (best_path->innersortkeys)
3756         {
3757                 Sort       *sort = make_sort_from_pathkeys(inner_plan,
3758                                                                                                    best_path->innersortkeys);
3759
3760                 label_sort_with_costsize(root, sort, -1.0);
3761                 inner_plan = (Plan *) sort;
3762                 innerpathkeys = best_path->innersortkeys;
3763         }
3764         else
3765                 innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;
3766
3767         /*
3768          * If specified, add a materialize node to shield the inner plan from the
3769          * need to handle mark/restore.
3770          */
3771         if (best_path->materialize_inner)
3772         {
3773                 Plan       *matplan = (Plan *) make_material(inner_plan);
3774
3775                 /*
3776                  * We assume the materialize will not spill to disk, and therefore
3777                  * charge just cpu_operator_cost per tuple.  (Keep this estimate in
3778                  * sync with final_cost_mergejoin.)
3779                  */
3780                 copy_plan_costsize(matplan, inner_plan);
3781                 matplan->total_cost += cpu_operator_cost * matplan->plan_rows;
3782
3783                 inner_plan = matplan;
3784         }
3785
3786         /*
3787          * Compute the opfamily/collation/strategy/nullsfirst arrays needed by the
3788          * executor.  The information is in the pathkeys for the two inputs, but
3789          * we need to be careful about the possibility of mergeclauses sharing a
3790          * pathkey (compare find_mergeclauses_for_pathkeys()).
3791          */
3792         nClauses = list_length(mergeclauses);
3793         Assert(nClauses == list_length(best_path->path_mergeclauses));
3794         mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
3795         mergecollations = (Oid *) palloc(nClauses * sizeof(Oid));
3796         mergestrategies = (int *) palloc(nClauses * sizeof(int));
3797         mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));
3798
3799         lop = list_head(outerpathkeys);
3800         lip = list_head(innerpathkeys);
3801         i = 0;
3802         foreach(lc, best_path->path_mergeclauses)
3803         {
3804                 RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(lc));
3805                 EquivalenceClass *oeclass;
3806                 EquivalenceClass *ieclass;
3807                 PathKey    *opathkey;
3808                 PathKey    *ipathkey;
3809                 EquivalenceClass *opeclass;
3810                 EquivalenceClass *ipeclass;
3811                 ListCell   *l2;
3812
3813                 /* fetch outer/inner eclass from mergeclause */
3814                 if (rinfo->outer_is_left)
3815                 {
3816                         oeclass = rinfo->left_ec;
3817                         ieclass = rinfo->right_ec;
3818                 }
3819                 else
3820                 {
3821                         oeclass = rinfo->right_ec;
3822                         ieclass = rinfo->left_ec;
3823                 }
3824                 Assert(oeclass != NULL);
3825                 Assert(ieclass != NULL);
3826
3827                 /*
3828                  * For debugging purposes, we check that the eclasses match the paths'
3829                  * pathkeys.  In typical cases the merge clauses are one-to-one with
3830                  * the pathkeys, but when dealing with partially redundant query
3831                  * conditions, we might have clauses that re-reference earlier path
3832                  * keys.  The case that we need to reject is where a pathkey is
3833                  * entirely skipped over.
3834                  *
3835                  * lop and lip reference the first as-yet-unused pathkey elements;
3836                  * it's okay to match them, or any element before them.  If they're
3837                  * NULL then we have found all pathkey elements to be used.
3838                  */
3839                 if (lop)
3840                 {
3841                         opathkey = (PathKey *) lfirst(lop);
3842                         opeclass = opathkey->pk_eclass;
3843                         if (oeclass == opeclass)
3844                         {
3845                                 /* fast path for typical case */
3846                                 lop = lnext(lop);
3847                         }
3848                         else
3849                         {
3850                                 /* redundant clauses ... must match something before lop */
3851                                 foreach(l2, outerpathkeys)
3852                                 {
3853                                         if (l2 == lop)
3854                                                 break;
3855                                         opathkey = (PathKey *) lfirst(l2);
3856                                         opeclass = opathkey->pk_eclass;
3857                                         if (oeclass == opeclass)
3858                                                 break;
3859                                 }
3860                                 if (oeclass != opeclass)
3861                                         elog(ERROR, "outer pathkeys do not match mergeclauses");
3862                         }
3863                 }
3864                 else
3865                 {
3866                         /* redundant clauses ... must match some already-used pathkey */
3867                         opathkey = NULL;
3868                         opeclass = NULL;
3869                         foreach(l2, outerpathkeys)
3870                         {
3871                                 opathkey = (PathKey *) lfirst(l2);
3872                                 opeclass = opathkey->pk_eclass;
3873                                 if (oeclass == opeclass)
3874                                         break;
3875                         }
3876                         if (l2 == NULL)
3877                                 elog(ERROR, "outer pathkeys do not match mergeclauses");
3878                 }
3879
3880                 if (lip)
3881                 {
3882                         ipathkey = (PathKey *) lfirst(lip);
3883                         ipeclass = ipathkey->pk_eclass;
3884                         if (ieclass == ipeclass)
3885                         {
3886                                 /* fast path for typical case */
3887                                 lip = lnext(lip);
3888                         }
3889                         else
3890                         {
3891                                 /* redundant clauses ... must match something before lip */
3892                                 foreach(l2, innerpathkeys)
3893                                 {
3894                                         if (l2 == lip)
3895                                                 break;
3896                                         ipathkey = (PathKey *) lfirst(l2);
3897                                         ipeclass = ipathkey->pk_eclass;
3898                                         if (ieclass == ipeclass)
3899                                                 break;
3900                                 }
3901                                 if (ieclass != ipeclass)
3902                                         elog(ERROR, "inner pathkeys do not match mergeclauses");
3903                         }
3904                 }
3905                 else
3906                 {
3907                         /* redundant clauses ... must match some already-used pathkey */
3908                         ipathkey = NULL;
3909                         ipeclass = NULL;
3910                         foreach(l2, innerpathkeys)
3911                         {
3912                                 ipathkey = (PathKey *) lfirst(l2);
3913                                 ipeclass = ipathkey->pk_eclass;
3914                                 if (ieclass == ipeclass)
3915                                         break;
3916                         }
3917                         if (l2 == NULL)
3918                                 elog(ERROR, "inner pathkeys do not match mergeclauses");
3919                 }
3920
3921                 /* pathkeys should match each other too (more debugging) */
3922                 if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
3923                         opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation ||
3924                         opathkey->pk_strategy != ipathkey->pk_strategy ||
3925                         opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
3926                         elog(ERROR, "left and right pathkeys do not match in mergejoin");
3927
3928                 /* OK, save info for executor */
3929                 mergefamilies[i] = opathkey->pk_opfamily;
3930                 mergecollations[i] = opathkey->pk_eclass->ec_collation;
3931                 mergestrategies[i] = opathkey->pk_strategy;
3932                 mergenullsfirst[i] = opathkey->pk_nulls_first;
3933                 i++;
3934         }
3935
3936         /*
3937          * Note: it is not an error if we have additional pathkey elements (i.e.,
3938          * lop or lip isn't NULL here).  The input paths might be better-sorted
3939          * than we need for the current mergejoin.
3940          */
3941
3942         /*
3943          * Now we can build the mergejoin node.
3944          */
3945         join_plan = make_mergejoin(tlist,
3946                                                            joinclauses,
3947                                                            otherclauses,
3948                                                            mergeclauses,
3949                                                            mergefamilies,
3950                                                            mergecollations,
3951                                                            mergestrategies,
3952                                                            mergenullsfirst,
3953                                                            outer_plan,
3954                                                            inner_plan,
3955                                                            best_path->jpath.jointype);
3956
3957         /* Costs of sort and material steps are included in path cost already */
3958         copy_generic_path_info(&join_plan->join.plan, &best_path->jpath.path);
3959
3960         return join_plan;
3961 }
3962
3963 static HashJoin *
3964 create_hashjoin_plan(PlannerInfo *root,
3965                                          HashPath *best_path)
3966 {
3967         HashJoin   *join_plan;
3968         Hash       *hash_plan;
3969         Plan       *outer_plan;
3970         Plan       *inner_plan;
3971         List       *tlist = build_path_tlist(root, &best_path->jpath.path);
3972         List       *joinclauses;
3973         List       *otherclauses;
3974         List       *hashclauses;
3975         Oid                     skewTable = InvalidOid;
3976         AttrNumber      skewColumn = InvalidAttrNumber;
3977         bool            skewInherit = false;
3978         Oid                     skewColType = InvalidOid;
3979         int32           skewColTypmod = -1;
3980
3981         /*
3982          * HashJoin can project, so we don't have to demand exact tlists from the
3983          * inputs.  However, it's best to request a small tlist from the inner
3984          * side, so that we aren't storing more data than necessary.  Likewise, if
3985          * we anticipate batching, request a small tlist from the outer side so
3986          * that we don't put extra data in the outer batch files.
3987          */
3988         outer_plan = create_plan_recurse(root, best_path->jpath.outerjoinpath,
3989                                                   (best_path->num_batches > 1) ? CP_SMALL_TLIST : 0);
3990
3991         inner_plan = create_plan_recurse(root, best_path->jpath.innerjoinpath,
3992                                                                          CP_SMALL_TLIST);
3993
3994         /* Sort join qual clauses into best execution order */
3995         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
3996         /* There's no point in sorting the hash clauses ... */
3997
3998         /* Get the join qual clauses (in plain expression form) */
3999         /* Any pseudoconstant clauses are ignored here */
4000         if (IS_OUTER_JOIN(best_path->jpath.jointype))
4001         {
4002                 extract_actual_join_clauses(joinclauses,
4003                                                                         &joinclauses, &otherclauses);
4004         }
4005         else
4006         {
4007                 /* We can treat all clauses alike for an inner join */
4008                 joinclauses = extract_actual_clauses(joinclauses, false);
4009                 otherclauses = NIL;
4010         }
4011
4012         /*
4013          * Remove the hashclauses from the list of join qual clauses, leaving the
4014          * list of quals that must be checked as qpquals.
4015          */
4016         hashclauses = get_actual_clauses(best_path->path_hashclauses);
4017         joinclauses = list_difference(joinclauses, hashclauses);
4018
4019         /*
4020          * Replace any outer-relation variables with nestloop params.  There
4021          * should not be any in the hashclauses.
4022          */
4023         if (best_path->jpath.path.param_info)
4024         {
4025                 joinclauses = (List *)
4026                         replace_nestloop_params(root, (Node *) joinclauses);
4027                 otherclauses = (List *)
4028                         replace_nestloop_params(root, (Node *) otherclauses);
4029         }
4030
4031         /*
4032          * Rearrange hashclauses, if needed, so that the outer variable is always
4033          * on the left.
4034          */
4035         hashclauses = get_switched_clauses(best_path->path_hashclauses,
4036                                                          best_path->jpath.outerjoinpath->parent->relids);
4037
4038         /*
4039          * If there is a single join clause and we can identify the outer variable
4040          * as a simple column reference, supply its identity for possible use in
4041          * skew optimization.  (Note: in principle we could do skew optimization
4042          * with multiple join clauses, but we'd have to be able to determine the
4043          * most common combinations of outer values, which we don't currently have
4044          * enough stats for.)
4045          */
4046         if (list_length(hashclauses) == 1)
4047         {
4048                 OpExpr     *clause = (OpExpr *) linitial(hashclauses);
4049                 Node       *node;
4050
4051                 Assert(is_opclause(clause));
4052                 node = (Node *) linitial(clause->args);
4053                 if (IsA(node, RelabelType))
4054                         node = (Node *) ((RelabelType *) node)->arg;
4055                 if (IsA(node, Var))
4056                 {
4057                         Var                *var = (Var *) node;
4058                         RangeTblEntry *rte;
4059
4060                         rte = root->simple_rte_array[var->varno];
4061                         if (rte->rtekind == RTE_RELATION)
4062                         {
4063                                 skewTable = rte->relid;
4064                                 skewColumn = var->varattno;
4065                                 skewInherit = rte->inh;
4066                                 skewColType = var->vartype;
4067                                 skewColTypmod = var->vartypmod;
4068                         }
4069                 }
4070         }
4071
4072         /*
4073          * Build the hash node and hash join node.
4074          */
4075         hash_plan = make_hash(inner_plan,
4076                                                   skewTable,
4077                                                   skewColumn,
4078                                                   skewInherit,
4079                                                   skewColType,
4080                                                   skewColTypmod);
4081
4082         /*
4083          * Set Hash node's startup & total costs equal to total cost of input
4084          * plan; this only affects EXPLAIN display not decisions.
4085          */
4086         copy_plan_costsize(&hash_plan->plan, inner_plan);
4087         hash_plan->plan.startup_cost = hash_plan->plan.total_cost;
4088
4089         join_plan = make_hashjoin(tlist,
4090                                                           joinclauses,
4091                                                           otherclauses,
4092                                                           hashclauses,
4093                                                           outer_plan,
4094                                                           (Plan *) hash_plan,
4095                                                           best_path->jpath.jointype);
4096
4097         copy_generic_path_info(&join_plan->join.plan, &best_path->jpath.path);
4098
4099         return join_plan;
4100 }
4101
4102
4103 /*****************************************************************************
4104  *
4105  *      SUPPORTING ROUTINES
4106  *
4107  *****************************************************************************/
4108
4109 /*
4110  * replace_nestloop_params
4111  *        Replace outer-relation Vars and PlaceHolderVars in the given expression
4112  *        with nestloop Params
4113  *
4114  * All Vars and PlaceHolderVars belonging to the relation(s) identified by
4115  * root->curOuterRels are replaced by Params, and entries are added to
4116  * root->curOuterParams if not already present.
4117  */
4118 static Node *
4119 replace_nestloop_params(PlannerInfo *root, Node *expr)
4120 {
4121         /* No setup needed for tree walk, so away we go */
4122         return replace_nestloop_params_mutator(expr, root);
4123 }
4124
4125 static Node *
4126 replace_nestloop_params_mutator(Node *node, PlannerInfo *root)
4127 {
4128         if (node == NULL)
4129                 return NULL;
4130         if (IsA(node, Var))
4131         {
4132                 Var                *var = (Var *) node;
4133                 Param      *param;
4134                 NestLoopParam *nlp;
4135                 ListCell   *lc;
4136
4137                 /* Upper-level Vars should be long gone at this point */
4138                 Assert(var->varlevelsup == 0);
4139                 /* If not to be replaced, we can just return the Var unmodified */
4140                 if (!bms_is_member(var->varno, root->curOuterRels))
4141                         return node;
4142                 /* Create a Param representing the Var */
4143                 param = assign_nestloop_param_var(root, var);
4144                 /* Is this param already listed in root->curOuterParams? */
4145                 foreach(lc, root->curOuterParams)
4146                 {
4147                         nlp = (NestLoopParam *) lfirst(lc);
4148                         if (nlp->paramno == param->paramid)
4149                         {
4150                                 Assert(equal(var, nlp->paramval));
4151                                 /* Present, so we can just return the Param */
4152                                 return (Node *) param;
4153                         }
4154                 }
4155                 /* No, so add it */
4156                 nlp = makeNode(NestLoopParam);
4157                 nlp->paramno = param->paramid;
4158                 nlp->paramval = var;
4159                 root->curOuterParams = lappend(root->curOuterParams, nlp);
4160                 /* And return the replacement Param */
4161                 return (Node *) param;
4162         }
4163         if (IsA(node, PlaceHolderVar))
4164         {
4165                 PlaceHolderVar *phv = (PlaceHolderVar *) node;
4166                 Param      *param;
4167                 NestLoopParam *nlp;
4168                 ListCell   *lc;
4169
4170                 /* Upper-level PlaceHolderVars should be long gone at this point */
4171                 Assert(phv->phlevelsup == 0);
4172
4173                 /*
4174                  * Check whether we need to replace the PHV.  We use bms_overlap as a
4175                  * cheap/quick test to see if the PHV might be evaluated in the outer
4176                  * rels, and then grab its PlaceHolderInfo to tell for sure.
4177                  */
4178                 if (!bms_overlap(phv->phrels, root->curOuterRels) ||
4179                   !bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
4180                                                  root->curOuterRels))
4181                 {
4182                         /*
4183                          * We can't replace the whole PHV, but we might still need to
4184                          * replace Vars or PHVs within its expression, in case it ends up
4185                          * actually getting evaluated here.  (It might get evaluated in
4186                          * this plan node, or some child node; in the latter case we don't
4187                          * really need to process the expression here, but we haven't got
4188                          * enough info to tell if that's the case.)  Flat-copy the PHV
4189                          * node and then recurse on its expression.
4190                          *
4191                          * Note that after doing this, we might have different
4192                          * representations of the contents of the same PHV in different
4193                          * parts of the plan tree.  This is OK because equal() will just
4194                          * match on phid/phlevelsup, so setrefs.c will still recognize an
4195                          * upper-level reference to a lower-level copy of the same PHV.
4196                          */
4197                         PlaceHolderVar *newphv = makeNode(PlaceHolderVar);
4198
4199                         memcpy(newphv, phv, sizeof(PlaceHolderVar));
4200                         newphv->phexpr = (Expr *)
4201                                 replace_nestloop_params_mutator((Node *) phv->phexpr,
4202                                                                                                 root);
4203                         return (Node *) newphv;
4204                 }
4205                 /* Create a Param representing the PlaceHolderVar */
4206                 param = assign_nestloop_param_placeholdervar(root, phv);
4207                 /* Is this param already listed in root->curOuterParams? */
4208                 foreach(lc, root->curOuterParams)
4209                 {
4210                         nlp = (NestLoopParam *) lfirst(lc);
4211                         if (nlp->paramno == param->paramid)
4212                         {
4213                                 Assert(equal(phv, nlp->paramval));
4214                                 /* Present, so we can just return the Param */
4215                                 return (Node *) param;
4216                         }
4217                 }
4218                 /* No, so add it */
4219                 nlp = makeNode(NestLoopParam);
4220                 nlp->paramno = param->paramid;
4221                 nlp->paramval = (Var *) phv;
4222                 root->curOuterParams = lappend(root->curOuterParams, nlp);
4223                 /* And return the replacement Param */
4224                 return (Node *) param;
4225         }
4226         return expression_tree_mutator(node,
4227                                                                    replace_nestloop_params_mutator,
4228                                                                    (void *) root);
4229 }
4230
4231 /*
4232  * process_subquery_nestloop_params
4233  *        Handle params of a parameterized subquery that need to be fed
4234  *        from an outer nestloop.
4235  *
4236  * Currently, that would be *all* params that a subquery in FROM has demanded
4237  * from the current query level, since they must be LATERAL references.
4238  *
4239  * The subplan's references to the outer variables are already represented
4240  * as PARAM_EXEC Params, so we need not modify the subplan here.  What we
4241  * do need to do is add entries to root->curOuterParams to signal the parent
4242  * nestloop plan node that it must provide these values.
4243  */
4244 static void
4245 process_subquery_nestloop_params(PlannerInfo *root, List *subplan_params)
4246 {
4247         ListCell   *ppl;
4248
4249         foreach(ppl, subplan_params)
4250         {
4251                 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(ppl);
4252
4253                 if (IsA(pitem->item, Var))
4254                 {
4255                         Var                *var = (Var *) pitem->item;
4256                         NestLoopParam *nlp;
4257                         ListCell   *lc;
4258
4259                         /* If not from a nestloop outer rel, complain */
4260                         if (!bms_is_member(var->varno, root->curOuterRels))
4261                                 elog(ERROR, "non-LATERAL parameter required by subquery");
4262                         /* Is this param already listed in root->curOuterParams? */
4263                         foreach(lc, root->curOuterParams)
4264                         {
4265                                 nlp = (NestLoopParam *) lfirst(lc);
4266                                 if (nlp->paramno == pitem->paramId)
4267                                 {
4268                                         Assert(equal(var, nlp->paramval));
4269                                         /* Present, so nothing to do */
4270                                         break;
4271                                 }
4272                         }
4273                         if (lc == NULL)
4274                         {
4275                                 /* No, so add it */
4276                                 nlp = makeNode(NestLoopParam);
4277                                 nlp->paramno = pitem->paramId;
4278                                 nlp->paramval = copyObject(var);
4279                                 root->curOuterParams = lappend(root->curOuterParams, nlp);
4280                         }
4281                 }
4282                 else if (IsA(pitem->item, PlaceHolderVar))
4283                 {
4284                         PlaceHolderVar *phv = (PlaceHolderVar *) pitem->item;
4285                         NestLoopParam *nlp;
4286                         ListCell   *lc;
4287
4288                         /* If not from a nestloop outer rel, complain */
4289                         if (!bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
4290                                                            root->curOuterRels))
4291                                 elog(ERROR, "non-LATERAL parameter required by subquery");
4292                         /* Is this param already listed in root->curOuterParams? */
4293                         foreach(lc, root->curOuterParams)
4294                         {
4295                                 nlp = (NestLoopParam *) lfirst(lc);
4296                                 if (nlp->paramno == pitem->paramId)
4297                                 {
4298                                         Assert(equal(phv, nlp->paramval));
4299                                         /* Present, so nothing to do */
4300                                         break;
4301                                 }
4302                         }
4303                         if (lc == NULL)
4304                         {
4305                                 /* No, so add it */
4306                                 nlp = makeNode(NestLoopParam);
4307                                 nlp->paramno = pitem->paramId;
4308                                 nlp->paramval = copyObject(phv);
4309                                 root->curOuterParams = lappend(root->curOuterParams, nlp);
4310                         }
4311                 }
4312                 else
4313                         elog(ERROR, "unexpected type of subquery parameter");
4314         }
4315 }
4316
4317 /*
4318  * fix_indexqual_references
4319  *        Adjust indexqual clauses to the form the executor's indexqual
4320  *        machinery needs.
4321  *
4322  * We have four tasks here:
4323  *      * Remove RestrictInfo nodes from the input clauses.
4324  *      * Replace any outer-relation Var or PHV nodes with nestloop Params.
4325  *        (XXX eventually, that responsibility should go elsewhere?)
4326  *      * Index keys must be represented by Var nodes with varattno set to the
4327  *        index's attribute number, not the attribute number in the original rel.
4328  *      * If the index key is on the right, commute the clause to put it on the
4329  *        left.
4330  *
4331  * The result is a modified copy of the path's indexquals list --- the
4332  * original is not changed.  Note also that the copy shares no substructure
4333  * with the original; this is needed in case there is a subplan in it (we need
4334  * two separate copies of the subplan tree, or things will go awry).
4335  */
4336 static List *
4337 fix_indexqual_references(PlannerInfo *root, IndexPath *index_path)
4338 {
4339         IndexOptInfo *index = index_path->indexinfo;
4340         List       *fixed_indexquals;
4341         ListCell   *lcc,
4342                            *lci;
4343
4344         fixed_indexquals = NIL;
4345
4346         forboth(lcc, index_path->indexquals, lci, index_path->indexqualcols)
4347         {
4348                 RestrictInfo *rinfo = castNode(RestrictInfo, lfirst(lcc));
4349                 int                     indexcol = lfirst_int(lci);
4350                 Node       *clause;
4351
4352                 /*
4353                  * Replace any outer-relation variables with nestloop params.
4354                  *
4355                  * This also makes a copy of the clause, so it's safe to modify it
4356                  * in-place below.
4357                  */
4358                 clause = replace_nestloop_params(root, (Node *) rinfo->clause);
4359
4360                 if (IsA(clause, OpExpr))
4361                 {
4362                         OpExpr     *op = (OpExpr *) clause;
4363
4364                         if (list_length(op->args) != 2)
4365                                 elog(ERROR, "indexqual clause is not binary opclause");
4366
4367                         /*
4368                          * Check to see if the indexkey is on the right; if so, commute
4369                          * the clause.  The indexkey should be the side that refers to
4370                          * (only) the base relation.
4371                          */
4372                         if (!bms_equal(rinfo->left_relids, index->rel->relids))
4373                                 CommuteOpExpr(op);
4374
4375                         /*
4376                          * Now replace the indexkey expression with an index Var.
4377                          */
4378                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
4379                                                                                                            index,
4380                                                                                                            indexcol);
4381                 }
4382                 else if (IsA(clause, RowCompareExpr))
4383                 {
4384                         RowCompareExpr *rc = (RowCompareExpr *) clause;
4385                         Expr       *newrc;
4386                         List       *indexcolnos;
4387                         bool            var_on_left;
4388                         ListCell   *lca,
4389                                            *lcai;
4390
4391                         /*
4392                          * Re-discover which index columns are used in the rowcompare.
4393                          */
4394                         newrc = adjust_rowcompare_for_index(rc,
4395                                                                                                 index,
4396                                                                                                 indexcol,
4397                                                                                                 &indexcolnos,
4398                                                                                                 &var_on_left);
4399
4400                         /*
4401                          * Trouble if adjust_rowcompare_for_index thought the
4402                          * RowCompareExpr didn't match the index as-is; the clause should
4403                          * have gone through that routine already.
4404                          */
4405                         if (newrc != (Expr *) rc)
4406                                 elog(ERROR, "inconsistent results from adjust_rowcompare_for_index");
4407
4408                         /*
4409                          * Check to see if the indexkey is on the right; if so, commute
4410                          * the clause.
4411                          */
4412                         if (!var_on_left)
4413                                 CommuteRowCompareExpr(rc);
4414
4415                         /*
4416                          * Now replace the indexkey expressions with index Vars.
4417                          */
4418                         Assert(list_length(rc->largs) == list_length(indexcolnos));
4419                         forboth(lca, rc->largs, lcai, indexcolnos)
4420                         {
4421                                 lfirst(lca) = fix_indexqual_operand(lfirst(lca),
4422                                                                                                         index,
4423                                                                                                         lfirst_int(lcai));
4424                         }
4425                 }
4426                 else if (IsA(clause, ScalarArrayOpExpr))
4427                 {
4428                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
4429
4430                         /* Never need to commute... */
4431
4432                         /* Replace the indexkey expression with an index Var. */
4433                         linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
4434                                                                                                                  index,
4435                                                                                                                  indexcol);
4436                 }
4437                 else if (IsA(clause, NullTest))
4438                 {
4439                         NullTest   *nt = (NullTest *) clause;
4440
4441                         /* Replace the indexkey expression with an index Var. */
4442                         nt->arg = (Expr *) fix_indexqual_operand((Node *) nt->arg,
4443                                                                                                          index,
4444                                                                                                          indexcol);
4445                 }
4446                 else
4447                         elog(ERROR, "unsupported indexqual type: %d",
4448                                  (int) nodeTag(clause));
4449
4450                 fixed_indexquals = lappend(fixed_indexquals, clause);
4451         }
4452
4453         return fixed_indexquals;
4454 }
4455
4456 /*
4457  * fix_indexorderby_references
4458  *        Adjust indexorderby clauses to the form the executor's index
4459  *        machinery needs.
4460  *
4461  * This is a simplified version of fix_indexqual_references.  The input does
4462  * not have RestrictInfo nodes, and we assume that indxpath.c already
4463  * commuted the clauses to put the index keys on the left.  Also, we don't
4464  * bother to support any cases except simple OpExprs, since nothing else
4465  * is allowed for ordering operators.
4466  */
4467 static List *
4468 fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path)
4469 {
4470         IndexOptInfo *index = index_path->indexinfo;
4471         List       *fixed_indexorderbys;
4472         ListCell   *lcc,
4473                            *lci;
4474
4475         fixed_indexorderbys = NIL;
4476
4477         forboth(lcc, index_path->indexorderbys, lci, index_path->indexorderbycols)
4478         {
4479                 Node       *clause = (Node *) lfirst(lcc);
4480                 int                     indexcol = lfirst_int(lci);
4481
4482                 /*
4483                  * Replace any outer-relation variables with nestloop params.
4484                  *
4485                  * This also makes a copy of the clause, so it's safe to modify it
4486                  * in-place below.
4487                  */
4488                 clause = replace_nestloop_params(root, clause);
4489
4490                 if (IsA(clause, OpExpr))
4491                 {
4492                         OpExpr     *op = (OpExpr *) clause;
4493
4494                         if (list_length(op->args) != 2)
4495                                 elog(ERROR, "indexorderby clause is not binary opclause");
4496
4497                         /*
4498                          * Now replace the indexkey expression with an index Var.
4499                          */
4500                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
4501                                                                                                            index,
4502                                                                                                            indexcol);
4503                 }
4504                 else
4505                         elog(ERROR, "unsupported indexorderby type: %d",
4506                                  (int) nodeTag(clause));
4507
4508                 fixed_indexorderbys = lappend(fixed_indexorderbys, clause);
4509         }
4510
4511         return fixed_indexorderbys;
4512 }
4513
4514 /*
4515  * fix_indexqual_operand
4516  *        Convert an indexqual expression to a Var referencing the index column.
4517  *
4518  * We represent index keys by Var nodes having varno == INDEX_VAR and varattno
4519  * equal to the index's attribute number (index column position).
4520  *
4521  * Most of the code here is just for sanity cross-checking that the given
4522  * expression actually matches the index column it's claimed to.
4523  */
4524 static Node *
4525 fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol)
4526 {
4527         Var                *result;
4528         int                     pos;
4529         ListCell   *indexpr_item;
4530
4531         /*
4532          * Remove any binary-compatible relabeling of the indexkey
4533          */
4534         if (IsA(node, RelabelType))
4535                 node = (Node *) ((RelabelType *) node)->arg;
4536
4537         Assert(indexcol >= 0 && indexcol < index->ncolumns);
4538
4539         if (index->indexkeys[indexcol] != 0)
4540         {
4541                 /* It's a simple index column */
4542                 if (IsA(node, Var) &&
4543                         ((Var *) node)->varno == index->rel->relid &&
4544                         ((Var *) node)->varattno == index->indexkeys[indexcol])
4545                 {
4546                         result = (Var *) copyObject(node);
4547                         result->varno = INDEX_VAR;
4548                         result->varattno = indexcol + 1;
4549                         return (Node *) result;
4550                 }
4551                 else
4552                         elog(ERROR, "index key does not match expected index column");
4553         }
4554
4555         /* It's an index expression, so find and cross-check the expression */
4556         indexpr_item = list_head(index->indexprs);
4557         for (pos = 0; pos < index->ncolumns; pos++)
4558         {
4559                 if (index->indexkeys[pos] == 0)
4560                 {
4561                         if (indexpr_item == NULL)
4562                                 elog(ERROR, "too few entries in indexprs list");
4563                         if (pos == indexcol)
4564                         {
4565                                 Node       *indexkey;
4566
4567                                 indexkey = (Node *) lfirst(indexpr_item);
4568                                 if (indexkey && IsA(indexkey, RelabelType))
4569                                         indexkey = (Node *) ((RelabelType *) indexkey)->arg;
4570                                 if (equal(node, indexkey))
4571                                 {
4572                                         result = makeVar(INDEX_VAR, indexcol + 1,
4573                                                                          exprType(lfirst(indexpr_item)), -1,
4574                                                                          exprCollation(lfirst(indexpr_item)),
4575                                                                          0);
4576                                         return (Node *) result;
4577                                 }
4578                                 else
4579                                         elog(ERROR, "index key does not match expected index column");
4580                         }
4581                         indexpr_item = lnext(indexpr_item);
4582                 }
4583         }
4584
4585         /* Oops... */
4586         elog(ERROR, "index key does not match expected index column");
4587         return NULL;                            /* keep compiler quiet */
4588 }
4589
4590 /*
4591  * get_switched_clauses
4592  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
4593  *        extract the bare clauses, and rearrange the elements within the
4594  *        clauses, if needed, so the outer join variable is on the left and
4595  *        the inner is on the right.  The original clause data structure is not
4596  *        touched; a modified list is returned.  We do, however, set the transient
4597  *        outer_is_left field in each RestrictInfo to show which side was which.
4598  */
4599 static List *
4600 get_switched_clauses(List *clauses, Relids outerrelids)
4601 {
4602         List       *t_list = NIL;
4603         ListCell   *l;
4604
4605         foreach(l, clauses)
4606         {
4607                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
4608                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
4609
4610                 Assert(is_opclause(clause));
4611                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
4612                 {
4613                         /*
4614                          * Duplicate just enough of the structure to allow commuting the
4615                          * clause without changing the original list.  Could use
4616                          * copyObject, but a complete deep copy is overkill.
4617                          */
4618                         OpExpr     *temp = makeNode(OpExpr);
4619
4620                         temp->opno = clause->opno;
4621                         temp->opfuncid = InvalidOid;
4622                         temp->opresulttype = clause->opresulttype;
4623                         temp->opretset = clause->opretset;
4624                         temp->opcollid = clause->opcollid;
4625                         temp->inputcollid = clause->inputcollid;
4626                         temp->args = list_copy(clause->args);
4627                         temp->location = clause->location;
4628                         /* Commute it --- note this modifies the temp node in-place. */
4629                         CommuteOpExpr(temp);
4630                         t_list = lappend(t_list, temp);
4631                         restrictinfo->outer_is_left = false;
4632                 }
4633                 else
4634                 {
4635                         Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
4636                         t_list = lappend(t_list, clause);
4637                         restrictinfo->outer_is_left = true;
4638                 }
4639         }
4640         return t_list;
4641 }
4642
4643 /*
4644  * order_qual_clauses
4645  *              Given a list of qual clauses that will all be evaluated at the same
4646  *              plan node, sort the list into the order we want to check the quals
4647  *              in at runtime.
4648  *
4649  * When security barrier quals are used in the query, we may have quals with
4650  * different security levels in the list.  Quals of lower security_level
4651  * must go before quals of higher security_level, except that we can grant
4652  * exceptions to move up quals that are leakproof.  When security level
4653  * doesn't force the decision, we prefer to order clauses by estimated
4654  * execution cost, cheapest first.
4655  *
4656  * Ideally the order should be driven by a combination of execution cost and
4657  * selectivity, but it's not immediately clear how to account for both,
4658  * and given the uncertainty of the estimates the reliability of the decisions
4659  * would be doubtful anyway.  So we just order by security level then
4660  * estimated per-tuple cost, being careful not to change the order when
4661  * (as is often the case) the estimates are identical.
4662  *
4663  * Although this will work on either bare clauses or RestrictInfos, it's
4664  * much faster to apply it to RestrictInfos, since it can re-use cost
4665  * information that is cached in RestrictInfos.  XXX in the bare-clause
4666  * case, we are also not able to apply security considerations.  That is
4667  * all right for the moment, because the bare-clause case doesn't occur
4668  * anywhere that barrier quals could be present, but it would be better to
4669  * get rid of it.
4670  *
4671  * Note: some callers pass lists that contain entries that will later be
4672  * removed; this is the easiest way to let this routine see RestrictInfos
4673  * instead of bare clauses.  This is another reason why trying to consider
4674  * selectivity in the ordering would likely do the wrong thing.
4675  */
4676 static List *
4677 order_qual_clauses(PlannerInfo *root, List *clauses)
4678 {
4679         typedef struct
4680         {
4681                 Node       *clause;
4682                 Cost            cost;
4683                 Index           security_level;
4684         } QualItem;
4685         int                     nitems = list_length(clauses);
4686         QualItem   *items;
4687         ListCell   *lc;
4688         int                     i;
4689         List       *result;
4690
4691         /* No need to work hard for 0 or 1 clause */
4692         if (nitems <= 1)
4693                 return clauses;
4694
4695         /*
4696          * Collect the items and costs into an array.  This is to avoid repeated
4697          * cost_qual_eval work if the inputs aren't RestrictInfos.
4698          */
4699         items = (QualItem *) palloc(nitems * sizeof(QualItem));
4700         i = 0;
4701         foreach(lc, clauses)
4702         {
4703                 Node       *clause = (Node *) lfirst(lc);
4704                 QualCost        qcost;
4705
4706                 cost_qual_eval_node(&qcost, clause, root);
4707                 items[i].clause = clause;
4708                 items[i].cost = qcost.per_tuple;
4709                 if (IsA(clause, RestrictInfo))
4710                 {
4711                         RestrictInfo *rinfo = (RestrictInfo *) clause;
4712
4713                         /*
4714                          * If a clause is leakproof, it doesn't have to be constrained by
4715                          * its nominal security level.  If it's also reasonably cheap
4716                          * (here defined as 10X cpu_operator_cost), pretend it has
4717                          * security_level 0, which will allow it to go in front of
4718                          * more-expensive quals of lower security levels.  Of course, that
4719                          * will also force it to go in front of cheaper quals of its own
4720                          * security level, which is not so great, but we can alleviate
4721                          * that risk by applying the cost limit cutoff.
4722                          */
4723                         if (rinfo->leakproof && items[i].cost < 10 * cpu_operator_cost)
4724                                 items[i].security_level = 0;
4725                         else
4726                                 items[i].security_level = rinfo->security_level;
4727                 }
4728                 else
4729                         items[i].security_level = 0;
4730                 i++;
4731         }
4732
4733         /*
4734          * Sort.  We don't use qsort() because it's not guaranteed stable for
4735          * equal keys.  The expected number of entries is small enough that a
4736          * simple insertion sort should be good enough.
4737          */
4738         for (i = 1; i < nitems; i++)
4739         {
4740                 QualItem        newitem = items[i];
4741                 int                     j;
4742
4743                 /* insert newitem into the already-sorted subarray */
4744                 for (j = i; j > 0; j--)
4745                 {
4746                         QualItem   *olditem = &items[j - 1];
4747
4748                         if (newitem.security_level > olditem->security_level ||
4749                                 (newitem.security_level == olditem->security_level &&
4750                                  newitem.cost >= olditem->cost))
4751                                 break;
4752                         items[j] = *olditem;
4753                 }
4754                 items[j] = newitem;
4755         }
4756
4757         /* Convert back to a list */
4758         result = NIL;
4759         for (i = 0; i < nitems; i++)
4760                 result = lappend(result, items[i].clause);
4761
4762         return result;
4763 }
4764
4765 /*
4766  * Copy cost and size info from a Path node to the Plan node created from it.
4767  * The executor usually won't use this info, but it's needed by EXPLAIN.
4768  * Also copy the parallel-aware flag, which the executor *will* use.
4769  */
4770 static void
4771 copy_generic_path_info(Plan *dest, Path *src)
4772 {
4773         dest->startup_cost = src->startup_cost;
4774         dest->total_cost = src->total_cost;
4775         dest->plan_rows = src->rows;
4776         dest->plan_width = src->pathtarget->width;
4777         dest->parallel_aware = src->parallel_aware;
4778 }
4779
4780 /*
4781  * Copy cost and size info from a lower plan node to an inserted node.
4782  * (Most callers alter the info after copying it.)
4783  */
4784 static void
4785 copy_plan_costsize(Plan *dest, Plan *src)
4786 {
4787         dest->startup_cost = src->startup_cost;
4788         dest->total_cost = src->total_cost;
4789         dest->plan_rows = src->plan_rows;
4790         dest->plan_width = src->plan_width;
4791         /* Assume the inserted node is not parallel-aware. */
4792         dest->parallel_aware = false;
4793 }
4794
4795 /*
4796  * Some places in this file build Sort nodes that don't have a directly
4797  * corresponding Path node.  The cost of the sort is, or should have been,
4798  * included in the cost of the Path node we're working from, but since it's
4799  * not split out, we have to re-figure it using cost_sort().  This is just
4800  * to label the Sort node nicely for EXPLAIN.
4801  *
4802  * limit_tuples is as for cost_sort (in particular, pass -1 if no limit)
4803  */
4804 static void
4805 label_sort_with_costsize(PlannerInfo *root, Sort *plan, double limit_tuples)
4806 {
4807         Plan       *lefttree = plan->plan.lefttree;
4808         Path            sort_path;              /* dummy for result of cost_sort */
4809
4810         cost_sort(&sort_path, root, NIL,
4811                           lefttree->total_cost,
4812                           lefttree->plan_rows,
4813                           lefttree->plan_width,
4814                           0.0,
4815                           work_mem,
4816                           limit_tuples);
4817         plan->plan.startup_cost = sort_path.startup_cost;
4818         plan->plan.total_cost = sort_path.total_cost;
4819         plan->plan.plan_rows = lefttree->plan_rows;
4820         plan->plan.plan_width = lefttree->plan_width;
4821         plan->plan.parallel_aware = false;
4822 }
4823
4824 /*
4825  * bitmap_subplan_mark_shared
4826  *   Set isshared flag in bitmap subplan so that it will be created in
4827  *       shared memory.
4828  */
4829 static void
4830 bitmap_subplan_mark_shared(Plan *plan)
4831 {
4832         if (IsA(plan, BitmapAnd))
4833                 bitmap_subplan_mark_shared(
4834                                                                 linitial(((BitmapAnd *) plan)->bitmapplans));
4835         else if (IsA(plan, BitmapOr))
4836                 ((BitmapOr *) plan)->isshared = true;
4837         else if (IsA(plan, BitmapIndexScan))
4838                 ((BitmapIndexScan *) plan)->isshared = true;
4839         else
4840                 elog(ERROR, "unrecognized node type: %d", nodeTag(plan));
4841 }
4842
4843 /*****************************************************************************
4844  *
4845  *      PLAN NODE BUILDING ROUTINES
4846  *
4847  * In general, these functions are not passed the original Path and therefore
4848  * leave it to the caller to fill in the cost/width fields from the Path,
4849  * typically by calling copy_generic_path_info().  This convention is
4850  * somewhat historical, but it does support a few places above where we build
4851  * a plan node without having an exactly corresponding Path node.  Under no
4852  * circumstances should one of these functions do its own cost calculations,
4853  * as that would be redundant with calculations done while building Paths.
4854  *
4855  *****************************************************************************/
4856
4857 static SeqScan *
4858 make_seqscan(List *qptlist,
4859                          List *qpqual,
4860                          Index scanrelid)
4861 {
4862         SeqScan    *node = makeNode(SeqScan);
4863         Plan       *plan = &node->plan;
4864
4865         plan->targetlist = qptlist;
4866         plan->qual = qpqual;
4867         plan->lefttree = NULL;
4868         plan->righttree = NULL;
4869         node->scanrelid = scanrelid;
4870
4871         return node;
4872 }
4873
4874 static SampleScan *
4875 make_samplescan(List *qptlist,
4876                                 List *qpqual,
4877                                 Index scanrelid,
4878                                 TableSampleClause *tsc)
4879 {
4880         SampleScan *node = makeNode(SampleScan);
4881         Plan       *plan = &node->scan.plan;
4882
4883         plan->targetlist = qptlist;
4884         plan->qual = qpqual;
4885         plan->lefttree = NULL;
4886         plan->righttree = NULL;
4887         node->scan.scanrelid = scanrelid;
4888         node->tablesample = tsc;
4889
4890         return node;
4891 }
4892
4893 static IndexScan *
4894 make_indexscan(List *qptlist,
4895                            List *qpqual,
4896                            Index scanrelid,
4897                            Oid indexid,
4898                            List *indexqual,
4899                            List *indexqualorig,
4900                            List *indexorderby,
4901                            List *indexorderbyorig,
4902                            List *indexorderbyops,
4903                            ScanDirection indexscandir)
4904 {
4905         IndexScan  *node = makeNode(IndexScan);
4906         Plan       *plan = &node->scan.plan;
4907
4908         plan->targetlist = qptlist;
4909         plan->qual = qpqual;
4910         plan->lefttree = NULL;
4911         plan->righttree = NULL;
4912         node->scan.scanrelid = scanrelid;
4913         node->indexid = indexid;
4914         node->indexqual = indexqual;
4915         node->indexqualorig = indexqualorig;
4916         node->indexorderby = indexorderby;
4917         node->indexorderbyorig = indexorderbyorig;
4918         node->indexorderbyops = indexorderbyops;
4919         node->indexorderdir = indexscandir;
4920
4921         return node;
4922 }
4923
4924 static IndexOnlyScan *
4925 make_indexonlyscan(List *qptlist,
4926                                    List *qpqual,
4927                                    Index scanrelid,
4928                                    Oid indexid,
4929                                    List *indexqual,
4930                                    List *indexorderby,
4931                                    List *indextlist,
4932                                    ScanDirection indexscandir)
4933 {
4934         IndexOnlyScan *node = makeNode(IndexOnlyScan);
4935         Plan       *plan = &node->scan.plan;
4936
4937         plan->targetlist = qptlist;
4938         plan->qual = qpqual;
4939         plan->lefttree = NULL;
4940         plan->righttree = NULL;
4941         node->scan.scanrelid = scanrelid;
4942         node->indexid = indexid;
4943         node->indexqual = indexqual;
4944         node->indexorderby = indexorderby;
4945         node->indextlist = indextlist;
4946         node->indexorderdir = indexscandir;
4947
4948         return node;
4949 }
4950
4951 static BitmapIndexScan *
4952 make_bitmap_indexscan(Index scanrelid,
4953                                           Oid indexid,
4954                                           List *indexqual,
4955                                           List *indexqualorig)
4956 {
4957         BitmapIndexScan *node = makeNode(BitmapIndexScan);
4958         Plan       *plan = &node->scan.plan;
4959
4960         plan->targetlist = NIL;         /* not used */
4961         plan->qual = NIL;                       /* not used */
4962         plan->lefttree = NULL;
4963         plan->righttree = NULL;
4964         node->scan.scanrelid = scanrelid;
4965         node->indexid = indexid;
4966         node->indexqual = indexqual;
4967         node->indexqualorig = indexqualorig;
4968
4969         return node;
4970 }
4971
4972 static BitmapHeapScan *
4973 make_bitmap_heapscan(List *qptlist,
4974                                          List *qpqual,
4975                                          Plan *lefttree,
4976                                          List *bitmapqualorig,
4977                                          Index scanrelid)
4978 {
4979         BitmapHeapScan *node = makeNode(BitmapHeapScan);
4980         Plan       *plan = &node->scan.plan;
4981
4982         plan->targetlist = qptlist;
4983         plan->qual = qpqual;
4984         plan->lefttree = lefttree;
4985         plan->righttree = NULL;
4986         node->scan.scanrelid = scanrelid;
4987         node->bitmapqualorig = bitmapqualorig;
4988
4989         return node;
4990 }
4991
4992 static TidScan *
4993 make_tidscan(List *qptlist,
4994                          List *qpqual,
4995                          Index scanrelid,
4996                          List *tidquals)
4997 {
4998         TidScan    *node = makeNode(TidScan);
4999         Plan       *plan = &node->scan.plan;
5000
5001         plan->targetlist = qptlist;
5002         plan->qual = qpqual;
5003         plan->lefttree = NULL;
5004         plan->righttree = NULL;
5005         node->scan.scanrelid = scanrelid;
5006         node->tidquals = tidquals;
5007
5008         return node;
5009 }
5010
5011 static SubqueryScan *
5012 make_subqueryscan(List *qptlist,
5013                                   List *qpqual,
5014                                   Index scanrelid,
5015                                   Plan *subplan)
5016 {
5017         SubqueryScan *node = makeNode(SubqueryScan);
5018         Plan       *plan = &node->scan.plan;
5019
5020         plan->targetlist = qptlist;
5021         plan->qual = qpqual;
5022         plan->lefttree = NULL;
5023         plan->righttree = NULL;
5024         node->scan.scanrelid = scanrelid;
5025         node->subplan = subplan;
5026
5027         return node;
5028 }
5029
5030 static FunctionScan *
5031 make_functionscan(List *qptlist,
5032                                   List *qpqual,
5033                                   Index scanrelid,
5034                                   List *functions,
5035                                   bool funcordinality)
5036 {
5037         FunctionScan *node = makeNode(FunctionScan);
5038         Plan       *plan = &node->scan.plan;
5039
5040         plan->targetlist = qptlist;
5041         plan->qual = qpqual;
5042         plan->lefttree = NULL;
5043         plan->righttree = NULL;
5044         node->scan.scanrelid = scanrelid;
5045         node->functions = functions;
5046         node->funcordinality = funcordinality;
5047
5048         return node;
5049 }
5050
5051 static TableFuncScan *
5052 make_tablefuncscan(List *qptlist,
5053                                    List *qpqual,
5054                                    Index scanrelid,
5055                                    TableFunc *tablefunc)
5056 {
5057         TableFuncScan *node = makeNode(TableFuncScan);
5058         Plan       *plan = &node->scan.plan;
5059
5060         plan->targetlist = qptlist;
5061         plan->qual = qpqual;
5062         plan->lefttree = NULL;
5063         plan->righttree = NULL;
5064         node->scan.scanrelid = scanrelid;
5065         node->tablefunc = tablefunc;
5066
5067         return node;
5068 }
5069
5070 static ValuesScan *
5071 make_valuesscan(List *qptlist,
5072                                 List *qpqual,
5073                                 Index scanrelid,
5074                                 List *values_lists)
5075 {
5076         ValuesScan *node = makeNode(ValuesScan);
5077         Plan       *plan = &node->scan.plan;
5078
5079         plan->targetlist = qptlist;
5080         plan->qual = qpqual;
5081         plan->lefttree = NULL;
5082         plan->righttree = NULL;
5083         node->scan.scanrelid = scanrelid;
5084         node->values_lists = values_lists;
5085
5086         return node;
5087 }
5088
5089 static CteScan *
5090 make_ctescan(List *qptlist,
5091                          List *qpqual,
5092                          Index scanrelid,
5093                          int ctePlanId,
5094                          int cteParam)
5095 {
5096         CteScan    *node = makeNode(CteScan);
5097         Plan       *plan = &node->scan.plan;
5098
5099         plan->targetlist = qptlist;
5100         plan->qual = qpqual;
5101         plan->lefttree = NULL;
5102         plan->righttree = NULL;
5103         node->scan.scanrelid = scanrelid;
5104         node->ctePlanId = ctePlanId;
5105         node->cteParam = cteParam;
5106
5107         return node;
5108 }
5109
5110 static WorkTableScan *
5111 make_worktablescan(List *qptlist,
5112                                    List *qpqual,
5113                                    Index scanrelid,
5114                                    int wtParam)
5115 {
5116         WorkTableScan *node = makeNode(WorkTableScan);
5117         Plan       *plan = &node->scan.plan;
5118
5119         plan->targetlist = qptlist;
5120         plan->qual = qpqual;
5121         plan->lefttree = NULL;
5122         plan->righttree = NULL;
5123         node->scan.scanrelid = scanrelid;
5124         node->wtParam = wtParam;
5125
5126         return node;
5127 }
5128
5129 ForeignScan *
5130 make_foreignscan(List *qptlist,
5131                                  List *qpqual,
5132                                  Index scanrelid,
5133                                  List *fdw_exprs,
5134                                  List *fdw_private,
5135                                  List *fdw_scan_tlist,
5136                                  List *fdw_recheck_quals,
5137                                  Plan *outer_plan)
5138 {
5139         ForeignScan *node = makeNode(ForeignScan);
5140         Plan       *plan = &node->scan.plan;
5141
5142         /* cost will be filled in by create_foreignscan_plan */
5143         plan->targetlist = qptlist;
5144         plan->qual = qpqual;
5145         plan->lefttree = outer_plan;
5146         plan->righttree = NULL;
5147         node->scan.scanrelid = scanrelid;
5148         node->operation = CMD_SELECT;
5149         /* fs_server will be filled in by create_foreignscan_plan */
5150         node->fs_server = InvalidOid;
5151         node->fdw_exprs = fdw_exprs;
5152         node->fdw_private = fdw_private;
5153         node->fdw_scan_tlist = fdw_scan_tlist;
5154         node->fdw_recheck_quals = fdw_recheck_quals;
5155         /* fs_relids will be filled in by create_foreignscan_plan */
5156         node->fs_relids = NULL;
5157         /* fsSystemCol will be filled in by create_foreignscan_plan */
5158         node->fsSystemCol = false;
5159
5160         return node;
5161 }
5162
5163 static Append *
5164 make_append(List *appendplans, List *tlist)
5165 {
5166         Append     *node = makeNode(Append);
5167         Plan       *plan = &node->plan;
5168
5169         plan->targetlist = tlist;
5170         plan->qual = NIL;
5171         plan->lefttree = NULL;
5172         plan->righttree = NULL;
5173         node->appendplans = appendplans;
5174
5175         return node;
5176 }
5177
5178 static RecursiveUnion *
5179 make_recursive_union(List *tlist,
5180                                          Plan *lefttree,
5181                                          Plan *righttree,
5182                                          int wtParam,
5183                                          List *distinctList,
5184                                          long numGroups)
5185 {
5186         RecursiveUnion *node = makeNode(RecursiveUnion);
5187         Plan       *plan = &node->plan;
5188         int                     numCols = list_length(distinctList);
5189
5190         plan->targetlist = tlist;
5191         plan->qual = NIL;
5192         plan->lefttree = lefttree;
5193         plan->righttree = righttree;
5194         node->wtParam = wtParam;
5195
5196         /*
5197          * convert SortGroupClause list into arrays of attr indexes and equality
5198          * operators, as wanted by executor
5199          */
5200         node->numCols = numCols;
5201         if (numCols > 0)
5202         {
5203                 int                     keyno = 0;
5204                 AttrNumber *dupColIdx;
5205                 Oid                *dupOperators;
5206                 ListCell   *slitem;
5207
5208                 dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
5209                 dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
5210
5211                 foreach(slitem, distinctList)
5212                 {
5213                         SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
5214                         TargetEntry *tle = get_sortgroupclause_tle(sortcl,
5215                                                                                                            plan->targetlist);
5216
5217                         dupColIdx[keyno] = tle->resno;
5218                         dupOperators[keyno] = sortcl->eqop;
5219                         Assert(OidIsValid(dupOperators[keyno]));
5220                         keyno++;
5221                 }
5222                 node->dupColIdx = dupColIdx;
5223                 node->dupOperators = dupOperators;
5224         }
5225         node->numGroups = numGroups;
5226
5227         return node;
5228 }
5229
5230 static BitmapAnd *
5231 make_bitmap_and(List *bitmapplans)
5232 {
5233         BitmapAnd  *node = makeNode(BitmapAnd);
5234         Plan       *plan = &node->plan;
5235
5236         plan->targetlist = NIL;
5237         plan->qual = NIL;
5238         plan->lefttree = NULL;
5239         plan->righttree = NULL;
5240         node->bitmapplans = bitmapplans;
5241
5242         return node;
5243 }
5244
5245 static BitmapOr *
5246 make_bitmap_or(List *bitmapplans)
5247 {
5248         BitmapOr   *node = makeNode(BitmapOr);
5249         Plan       *plan = &node->plan;
5250
5251         plan->targetlist = NIL;
5252         plan->qual = NIL;
5253         plan->lefttree = NULL;
5254         plan->righttree = NULL;
5255         node->bitmapplans = bitmapplans;
5256
5257         return node;
5258 }
5259
5260 static NestLoop *
5261 make_nestloop(List *tlist,
5262                           List *joinclauses,
5263                           List *otherclauses,
5264                           List *nestParams,
5265                           Plan *lefttree,
5266                           Plan *righttree,
5267                           JoinType jointype)
5268 {
5269         NestLoop   *node = makeNode(NestLoop);
5270         Plan       *plan = &node->join.plan;
5271
5272         plan->targetlist = tlist;
5273         plan->qual = otherclauses;
5274         plan->lefttree = lefttree;
5275         plan->righttree = righttree;
5276         node->join.jointype = jointype;
5277         node->join.joinqual = joinclauses;
5278         node->nestParams = nestParams;
5279
5280         return node;
5281 }
5282
5283 static HashJoin *
5284 make_hashjoin(List *tlist,
5285                           List *joinclauses,
5286                           List *otherclauses,
5287                           List *hashclauses,
5288                           Plan *lefttree,
5289                           Plan *righttree,
5290                           JoinType jointype)
5291 {
5292         HashJoin   *node = makeNode(HashJoin);
5293         Plan       *plan = &node->join.plan;
5294
5295         plan->targetlist = tlist;
5296         plan->qual = otherclauses;
5297         plan->lefttree = lefttree;
5298         plan->righttree = righttree;
5299         node->hashclauses = hashclauses;
5300         node->join.jointype = jointype;
5301         node->join.joinqual = joinclauses;
5302
5303         return node;
5304 }
5305
5306 static Hash *
5307 make_hash(Plan *lefttree,
5308                   Oid skewTable,
5309                   AttrNumber skewColumn,
5310                   bool skewInherit,
5311                   Oid skewColType,
5312                   int32 skewColTypmod)
5313 {
5314         Hash       *node = makeNode(Hash);
5315         Plan       *plan = &node->plan;
5316
5317         plan->targetlist = lefttree->targetlist;
5318         plan->qual = NIL;
5319         plan->lefttree = lefttree;
5320         plan->righttree = NULL;
5321
5322         node->skewTable = skewTable;
5323         node->skewColumn = skewColumn;
5324         node->skewInherit = skewInherit;
5325         node->skewColType = skewColType;
5326         node->skewColTypmod = skewColTypmod;
5327
5328         return node;
5329 }
5330
5331 static MergeJoin *
5332 make_mergejoin(List *tlist,
5333                            List *joinclauses,
5334                            List *otherclauses,
5335                            List *mergeclauses,
5336                            Oid *mergefamilies,
5337                            Oid *mergecollations,
5338                            int *mergestrategies,
5339                            bool *mergenullsfirst,
5340                            Plan *lefttree,
5341                            Plan *righttree,
5342                            JoinType jointype)
5343 {
5344         MergeJoin  *node = makeNode(MergeJoin);
5345         Plan       *plan = &node->join.plan;
5346
5347         plan->targetlist = tlist;
5348         plan->qual = otherclauses;
5349         plan->lefttree = lefttree;
5350         plan->righttree = righttree;
5351         node->mergeclauses = mergeclauses;
5352         node->mergeFamilies = mergefamilies;
5353         node->mergeCollations = mergecollations;
5354         node->mergeStrategies = mergestrategies;
5355         node->mergeNullsFirst = mergenullsfirst;
5356         node->join.jointype = jointype;
5357         node->join.joinqual = joinclauses;
5358
5359         return node;
5360 }
5361
5362 /*
5363  * make_sort --- basic routine to build a Sort plan node
5364  *
5365  * Caller must have built the sortColIdx, sortOperators, collations, and
5366  * nullsFirst arrays already.
5367  */
5368 static Sort *
5369 make_sort(Plan *lefttree, int numCols,
5370                   AttrNumber *sortColIdx, Oid *sortOperators,
5371                   Oid *collations, bool *nullsFirst)
5372 {
5373         Sort       *node = makeNode(Sort);
5374         Plan       *plan = &node->plan;
5375
5376         plan->targetlist = lefttree->targetlist;
5377         plan->qual = NIL;
5378         plan->lefttree = lefttree;
5379         plan->righttree = NULL;
5380         node->numCols = numCols;
5381         node->sortColIdx = sortColIdx;
5382         node->sortOperators = sortOperators;
5383         node->collations = collations;
5384         node->nullsFirst = nullsFirst;
5385
5386         return node;
5387 }
5388
5389 /*
5390  * prepare_sort_from_pathkeys
5391  *        Prepare to sort according to given pathkeys
5392  *
5393  * This is used to set up for Sort, MergeAppend, and Gather Merge nodes.  It
5394  * calculates the executor's representation of the sort key information, and
5395  * adjusts the plan targetlist if needed to add resjunk sort columns.
5396  *
5397  * Input parameters:
5398  *        'lefttree' is the plan node which yields input tuples
5399  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
5400  *        'relids' identifies the child relation being sorted, if any
5401  *        'reqColIdx' is NULL or an array of required sort key column numbers
5402  *        'adjust_tlist_in_place' is TRUE if lefttree must be modified in-place
5403  *
5404  * We must convert the pathkey information into arrays of sort key column
5405  * numbers, sort operator OIDs, collation OIDs, and nulls-first flags,
5406  * which is the representation the executor wants.  These are returned into
5407  * the output parameters *p_numsortkeys etc.
5408  *
5409  * When looking for matches to an EquivalenceClass's members, we will only
5410  * consider child EC members if they match 'relids'.  This protects against
5411  * possible incorrect matches to child expressions that contain no Vars.
5412  *
5413  * If reqColIdx isn't NULL then it contains sort key column numbers that
5414  * we should match.  This is used when making child plans for a MergeAppend;
5415  * it's an error if we can't match the columns.
5416  *
5417  * If the pathkeys include expressions that aren't simple Vars, we will
5418  * usually need to add resjunk items to the input plan's targetlist to
5419  * compute these expressions, since a Sort or MergeAppend node itself won't
5420  * do any such calculations.  If the input plan type isn't one that can do
5421  * projections, this means adding a Result node just to do the projection.
5422  * However, the caller can pass adjust_tlist_in_place = TRUE to force the
5423  * lefttree tlist to be modified in-place regardless of whether the node type
5424  * can project --- we use this for fixing the tlist of MergeAppend itself.
5425  *
5426  * Returns the node which is to be the input to the Sort (either lefttree,
5427  * or a Result stacked atop lefttree).
5428  */
5429 static Plan *
5430 prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
5431                                                    Relids relids,
5432                                                    const AttrNumber *reqColIdx,
5433                                                    bool adjust_tlist_in_place,
5434                                                    int *p_numsortkeys,
5435                                                    AttrNumber **p_sortColIdx,
5436                                                    Oid **p_sortOperators,
5437                                                    Oid **p_collations,
5438                                                    bool **p_nullsFirst)
5439 {
5440         List       *tlist = lefttree->targetlist;
5441         ListCell   *i;
5442         int                     numsortkeys;
5443         AttrNumber *sortColIdx;
5444         Oid                *sortOperators;
5445         Oid                *collations;
5446         bool       *nullsFirst;
5447
5448         /*
5449          * We will need at most list_length(pathkeys) sort columns; possibly less
5450          */
5451         numsortkeys = list_length(pathkeys);
5452         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
5453         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
5454         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
5455         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
5456
5457         numsortkeys = 0;
5458
5459         foreach(i, pathkeys)
5460         {
5461                 PathKey    *pathkey = (PathKey *) lfirst(i);
5462                 EquivalenceClass *ec = pathkey->pk_eclass;
5463                 EquivalenceMember *em;
5464                 TargetEntry *tle = NULL;
5465                 Oid                     pk_datatype = InvalidOid;
5466                 Oid                     sortop;
5467                 ListCell   *j;
5468
5469                 if (ec->ec_has_volatile)
5470                 {
5471                         /*
5472                          * If the pathkey's EquivalenceClass is volatile, then it must
5473                          * have come from an ORDER BY clause, and we have to match it to
5474                          * that same targetlist entry.
5475                          */
5476                         if (ec->ec_sortref == 0)        /* can't happen */
5477                                 elog(ERROR, "volatile EquivalenceClass has no sortref");
5478                         tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
5479                         Assert(tle);
5480                         Assert(list_length(ec->ec_members) == 1);
5481                         pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
5482                 }
5483                 else if (reqColIdx != NULL)
5484                 {
5485                         /*
5486                          * If we are given a sort column number to match, only consider
5487                          * the single TLE at that position.  It's possible that there is
5488                          * no such TLE, in which case fall through and generate a resjunk
5489                          * targetentry (we assume this must have happened in the parent
5490                          * plan as well).  If there is a TLE but it doesn't match the
5491                          * pathkey's EC, we do the same, which is probably the wrong thing
5492                          * but we'll leave it to caller to complain about the mismatch.
5493                          */
5494                         tle = get_tle_by_resno(tlist, reqColIdx[numsortkeys]);
5495                         if (tle)
5496                         {
5497                                 em = find_ec_member_for_tle(ec, tle, relids);
5498                                 if (em)
5499                                 {
5500                                         /* found expr at right place in tlist */
5501                                         pk_datatype = em->em_datatype;
5502                                 }
5503                                 else
5504                                         tle = NULL;
5505                         }
5506                 }
5507                 else
5508                 {
5509                         /*
5510                          * Otherwise, we can sort by any non-constant expression listed in
5511                          * the pathkey's EquivalenceClass.  For now, we take the first
5512                          * tlist item found in the EC. If there's no match, we'll generate
5513                          * a resjunk entry using the first EC member that is an expression
5514                          * in the input's vars.  (The non-const restriction only matters
5515                          * if the EC is below_outer_join; but if it isn't, it won't
5516                          * contain consts anyway, else we'd have discarded the pathkey as
5517                          * redundant.)
5518                          *
5519                          * XXX if we have a choice, is there any way of figuring out which
5520                          * might be cheapest to execute?  (For example, int4lt is likely
5521                          * much cheaper to execute than numericlt, but both might appear
5522                          * in the same equivalence class...)  Not clear that we ever will
5523                          * have an interesting choice in practice, so it may not matter.
5524                          */
5525                         foreach(j, tlist)
5526                         {
5527                                 tle = (TargetEntry *) lfirst(j);
5528                                 em = find_ec_member_for_tle(ec, tle, relids);
5529                                 if (em)
5530                                 {
5531                                         /* found expr already in tlist */
5532                                         pk_datatype = em->em_datatype;
5533                                         break;
5534                                 }
5535                                 tle = NULL;
5536                         }
5537                 }
5538
5539                 if (!tle)
5540                 {
5541                         /*
5542                          * No matching tlist item; look for a computable expression. Note
5543                          * that we treat Aggrefs as if they were variables; this is
5544                          * necessary when attempting to sort the output from an Agg node
5545                          * for use in a WindowFunc (since grouping_planner will have
5546                          * treated the Aggrefs as variables, too).  Likewise, if we find a
5547                          * WindowFunc in a sort expression, treat it as a variable.
5548                          */
5549                         Expr       *sortexpr = NULL;
5550
5551                         foreach(j, ec->ec_members)
5552                         {
5553                                 EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
5554                                 List       *exprvars;
5555                                 ListCell   *k;
5556
5557                                 /*
5558                                  * We shouldn't be trying to sort by an equivalence class that
5559                                  * contains a constant, so no need to consider such cases any
5560                                  * further.
5561                                  */
5562                                 if (em->em_is_const)
5563                                         continue;
5564
5565                                 /*
5566                                  * Ignore child members unless they match the rel being
5567                                  * sorted.
5568                                  */
5569                                 if (em->em_is_child &&
5570                                         !bms_equal(em->em_relids, relids))
5571                                         continue;
5572
5573                                 sortexpr = em->em_expr;
5574                                 exprvars = pull_var_clause((Node *) sortexpr,
5575                                                                                    PVC_INCLUDE_AGGREGATES |
5576                                                                                    PVC_INCLUDE_WINDOWFUNCS |
5577                                                                                    PVC_INCLUDE_PLACEHOLDERS);
5578                                 foreach(k, exprvars)
5579                                 {
5580                                         if (!tlist_member_ignore_relabel(lfirst(k), tlist))
5581                                                 break;
5582                                 }
5583                                 list_free(exprvars);
5584                                 if (!k)
5585                                 {
5586                                         pk_datatype = em->em_datatype;
5587                                         break;          /* found usable expression */
5588                                 }
5589                         }
5590                         if (!j)
5591                                 elog(ERROR, "could not find pathkey item to sort");
5592
5593                         /*
5594                          * Do we need to insert a Result node?
5595                          */
5596                         if (!adjust_tlist_in_place &&
5597                                 !is_projection_capable_plan(lefttree))
5598                         {
5599                                 /* copy needed so we don't modify input's tlist below */
5600                                 tlist = copyObject(tlist);
5601                                 lefttree = inject_projection_plan(lefttree, tlist);
5602                         }
5603
5604                         /* Don't bother testing is_projection_capable_plan again */
5605                         adjust_tlist_in_place = true;
5606
5607                         /*
5608                          * Add resjunk entry to input's tlist
5609                          */
5610                         tle = makeTargetEntry(sortexpr,
5611                                                                   list_length(tlist) + 1,
5612                                                                   NULL,
5613                                                                   true);
5614                         tlist = lappend(tlist, tle);
5615                         lefttree->targetlist = tlist;           /* just in case NIL before */
5616                 }
5617
5618                 /*
5619                  * Look up the correct sort operator from the PathKey's slightly
5620                  * abstracted representation.
5621                  */
5622                 sortop = get_opfamily_member(pathkey->pk_opfamily,
5623                                                                          pk_datatype,
5624                                                                          pk_datatype,
5625                                                                          pathkey->pk_strategy);
5626                 if (!OidIsValid(sortop))        /* should not happen */
5627                         elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
5628                                  pathkey->pk_strategy, pk_datatype, pk_datatype,
5629                                  pathkey->pk_opfamily);
5630
5631                 /* Add the column to the sort arrays */
5632                 sortColIdx[numsortkeys] = tle->resno;
5633                 sortOperators[numsortkeys] = sortop;
5634                 collations[numsortkeys] = ec->ec_collation;
5635                 nullsFirst[numsortkeys] = pathkey->pk_nulls_first;
5636                 numsortkeys++;
5637         }
5638
5639         /* Return results */
5640         *p_numsortkeys = numsortkeys;
5641         *p_sortColIdx = sortColIdx;
5642         *p_sortOperators = sortOperators;
5643         *p_collations = collations;
5644         *p_nullsFirst = nullsFirst;
5645
5646         return lefttree;
5647 }
5648
5649 /*
5650  * find_ec_member_for_tle
5651  *              Locate an EquivalenceClass member matching the given TLE, if any
5652  *
5653  * Child EC members are ignored unless they match 'relids'.
5654  */
5655 static EquivalenceMember *
5656 find_ec_member_for_tle(EquivalenceClass *ec,
5657                                            TargetEntry *tle,
5658                                            Relids relids)
5659 {
5660         Expr       *tlexpr;
5661         ListCell   *lc;
5662
5663         /* We ignore binary-compatible relabeling on both ends */
5664         tlexpr = tle->expr;
5665         while (tlexpr && IsA(tlexpr, RelabelType))
5666                 tlexpr = ((RelabelType *) tlexpr)->arg;
5667
5668         foreach(lc, ec->ec_members)
5669         {
5670                 EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
5671                 Expr       *emexpr;
5672
5673                 /*
5674                  * We shouldn't be trying to sort by an equivalence class that
5675                  * contains a constant, so no need to consider such cases any further.
5676                  */
5677                 if (em->em_is_const)
5678                         continue;
5679
5680                 /*
5681                  * Ignore child members unless they match the rel being sorted.
5682                  */
5683                 if (em->em_is_child &&
5684                         !bms_equal(em->em_relids, relids))
5685                         continue;
5686
5687                 /* Match if same expression (after stripping relabel) */
5688                 emexpr = em->em_expr;
5689                 while (emexpr && IsA(emexpr, RelabelType))
5690                         emexpr = ((RelabelType *) emexpr)->arg;
5691
5692                 if (equal(emexpr, tlexpr))
5693                         return em;
5694         }
5695
5696         return NULL;
5697 }
5698
5699 /*
5700  * make_sort_from_pathkeys
5701  *        Create sort plan to sort according to given pathkeys
5702  *
5703  *        'lefttree' is the node which yields input tuples
5704  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
5705  */
5706 static Sort *
5707 make_sort_from_pathkeys(Plan *lefttree, List *pathkeys)
5708 {
5709         int                     numsortkeys;
5710         AttrNumber *sortColIdx;
5711         Oid                *sortOperators;
5712         Oid                *collations;
5713         bool       *nullsFirst;
5714
5715         /* Compute sort column info, and adjust lefttree as needed */
5716         lefttree = prepare_sort_from_pathkeys(lefttree, pathkeys,
5717                                                                                   NULL,
5718                                                                                   NULL,
5719                                                                                   false,
5720                                                                                   &numsortkeys,
5721                                                                                   &sortColIdx,
5722                                                                                   &sortOperators,
5723                                                                                   &collations,
5724                                                                                   &nullsFirst);
5725
5726         /* Now build the Sort node */
5727         return make_sort(lefttree, numsortkeys,
5728                                          sortColIdx, sortOperators,
5729                                          collations, nullsFirst);
5730 }
5731
5732 /*
5733  * make_sort_from_sortclauses
5734  *        Create sort plan to sort according to given sortclauses
5735  *
5736  *        'sortcls' is a list of SortGroupClauses
5737  *        'lefttree' is the node which yields input tuples
5738  */
5739 Sort *
5740 make_sort_from_sortclauses(List *sortcls, Plan *lefttree)
5741 {
5742         List       *sub_tlist = lefttree->targetlist;
5743         ListCell   *l;
5744         int                     numsortkeys;
5745         AttrNumber *sortColIdx;
5746         Oid                *sortOperators;
5747         Oid                *collations;
5748         bool       *nullsFirst;
5749
5750         /* Convert list-ish representation to arrays wanted by executor */
5751         numsortkeys = list_length(sortcls);
5752         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
5753         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
5754         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
5755         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
5756
5757         numsortkeys = 0;
5758         foreach(l, sortcls)
5759         {
5760                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
5761                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
5762
5763                 sortColIdx[numsortkeys] = tle->resno;
5764                 sortOperators[numsortkeys] = sortcl->sortop;
5765                 collations[numsortkeys] = exprCollation((Node *) tle->expr);
5766                 nullsFirst[numsortkeys] = sortcl->nulls_first;
5767                 numsortkeys++;
5768         }
5769
5770         return make_sort(lefttree, numsortkeys,
5771                                          sortColIdx, sortOperators,
5772                                          collations, nullsFirst);
5773 }
5774
5775 /*
5776  * make_sort_from_groupcols
5777  *        Create sort plan to sort based on grouping columns
5778  *
5779  * 'groupcls' is the list of SortGroupClauses
5780  * 'grpColIdx' gives the column numbers to use
5781  *
5782  * This might look like it could be merged with make_sort_from_sortclauses,
5783  * but presently we *must* use the grpColIdx[] array to locate sort columns,
5784  * because the child plan's tlist is not marked with ressortgroupref info
5785  * appropriate to the grouping node.  So, only the sort ordering info
5786  * is used from the SortGroupClause entries.
5787  */
5788 static Sort *
5789 make_sort_from_groupcols(List *groupcls,
5790                                                  AttrNumber *grpColIdx,
5791                                                  Plan *lefttree)
5792 {
5793         List       *sub_tlist = lefttree->targetlist;
5794         ListCell   *l;
5795         int                     numsortkeys;
5796         AttrNumber *sortColIdx;
5797         Oid                *sortOperators;
5798         Oid                *collations;
5799         bool       *nullsFirst;
5800
5801         /* Convert list-ish representation to arrays wanted by executor */
5802         numsortkeys = list_length(groupcls);
5803         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
5804         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
5805         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
5806         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
5807
5808         numsortkeys = 0;
5809         foreach(l, groupcls)
5810         {
5811                 SortGroupClause *grpcl = (SortGroupClause *) lfirst(l);
5812                 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[numsortkeys]);
5813
5814                 if (!tle)
5815                         elog(ERROR, "could not retrieve tle for sort-from-groupcols");
5816
5817                 sortColIdx[numsortkeys] = tle->resno;
5818                 sortOperators[numsortkeys] = grpcl->sortop;
5819                 collations[numsortkeys] = exprCollation((Node *) tle->expr);
5820                 nullsFirst[numsortkeys] = grpcl->nulls_first;
5821                 numsortkeys++;
5822         }
5823
5824         return make_sort(lefttree, numsortkeys,
5825                                          sortColIdx, sortOperators,
5826                                          collations, nullsFirst);
5827 }
5828
5829 static Material *
5830 make_material(Plan *lefttree)
5831 {
5832         Material   *node = makeNode(Material);
5833         Plan       *plan = &node->plan;
5834
5835         plan->targetlist = lefttree->targetlist;
5836         plan->qual = NIL;
5837         plan->lefttree = lefttree;
5838         plan->righttree = NULL;
5839
5840         return node;
5841 }
5842
5843 /*
5844  * materialize_finished_plan: stick a Material node atop a completed plan
5845  *
5846  * There are a couple of places where we want to attach a Material node
5847  * after completion of create_plan(), without any MaterialPath path.
5848  * Those places should probably be refactored someday to do this on the
5849  * Path representation, but it's not worth the trouble yet.
5850  */
5851 Plan *
5852 materialize_finished_plan(Plan *subplan)
5853 {
5854         Plan       *matplan;
5855         Path            matpath;                /* dummy for result of cost_material */
5856
5857         matplan = (Plan *) make_material(subplan);
5858
5859         /*
5860          * XXX horrid kluge: if there are any initPlans attached to the subplan,
5861          * move them up to the Material node, which is now effectively the top
5862          * plan node in its query level.  This prevents failure in
5863          * SS_finalize_plan(), which see for comments.  We don't bother adjusting
5864          * the subplan's cost estimate for this.
5865          */
5866         matplan->initPlan = subplan->initPlan;
5867         subplan->initPlan = NIL;
5868
5869         /* Set cost data */
5870         cost_material(&matpath,
5871                                   subplan->startup_cost,
5872                                   subplan->total_cost,
5873                                   subplan->plan_rows,
5874                                   subplan->plan_width);
5875         matplan->startup_cost = matpath.startup_cost;
5876         matplan->total_cost = matpath.total_cost;
5877         matplan->plan_rows = subplan->plan_rows;
5878         matplan->plan_width = subplan->plan_width;
5879         matplan->parallel_aware = false;
5880
5881         return matplan;
5882 }
5883
5884 Agg *
5885 make_agg(List *tlist, List *qual,
5886                  AggStrategy aggstrategy, AggSplit aggsplit,
5887                  int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
5888                  List *groupingSets, List *chain,
5889                  double dNumGroups, Plan *lefttree)
5890 {
5891         Agg                *node = makeNode(Agg);
5892         Plan       *plan = &node->plan;
5893         long            numGroups;
5894
5895         /* Reduce to long, but 'ware overflow! */
5896         numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
5897
5898         node->aggstrategy = aggstrategy;
5899         node->aggsplit = aggsplit;
5900         node->numCols = numGroupCols;
5901         node->grpColIdx = grpColIdx;
5902         node->grpOperators = grpOperators;
5903         node->numGroups = numGroups;
5904         node->aggParams = NULL;         /* SS_finalize_plan() will fill this */
5905         node->groupingSets = groupingSets;
5906         node->chain = chain;
5907
5908         plan->qual = qual;
5909         plan->targetlist = tlist;
5910         plan->lefttree = lefttree;
5911         plan->righttree = NULL;
5912
5913         return node;
5914 }
5915
5916 static WindowAgg *
5917 make_windowagg(List *tlist, Index winref,
5918                            int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
5919                            int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators,
5920                            int frameOptions, Node *startOffset, Node *endOffset,
5921                            Plan *lefttree)
5922 {
5923         WindowAgg  *node = makeNode(WindowAgg);
5924         Plan       *plan = &node->plan;
5925
5926         node->winref = winref;
5927         node->partNumCols = partNumCols;
5928         node->partColIdx = partColIdx;
5929         node->partOperators = partOperators;
5930         node->ordNumCols = ordNumCols;
5931         node->ordColIdx = ordColIdx;
5932         node->ordOperators = ordOperators;
5933         node->frameOptions = frameOptions;
5934         node->startOffset = startOffset;
5935         node->endOffset = endOffset;
5936
5937         plan->targetlist = tlist;
5938         plan->lefttree = lefttree;
5939         plan->righttree = NULL;
5940         /* WindowAgg nodes never have a qual clause */
5941         plan->qual = NIL;
5942
5943         return node;
5944 }
5945
5946 static Group *
5947 make_group(List *tlist,
5948                    List *qual,
5949                    int numGroupCols,
5950                    AttrNumber *grpColIdx,
5951                    Oid *grpOperators,
5952                    Plan *lefttree)
5953 {
5954         Group      *node = makeNode(Group);
5955         Plan       *plan = &node->plan;
5956
5957         node->numCols = numGroupCols;
5958         node->grpColIdx = grpColIdx;
5959         node->grpOperators = grpOperators;
5960
5961         plan->qual = qual;
5962         plan->targetlist = tlist;
5963         plan->lefttree = lefttree;
5964         plan->righttree = NULL;
5965
5966         return node;
5967 }
5968
5969 /*
5970  * distinctList is a list of SortGroupClauses, identifying the targetlist items
5971  * that should be considered by the Unique filter.  The input path must
5972  * already be sorted accordingly.
5973  */
5974 static Unique *
5975 make_unique_from_sortclauses(Plan *lefttree, List *distinctList)
5976 {
5977         Unique     *node = makeNode(Unique);
5978         Plan       *plan = &node->plan;
5979         int                     numCols = list_length(distinctList);
5980         int                     keyno = 0;
5981         AttrNumber *uniqColIdx;
5982         Oid                *uniqOperators;
5983         ListCell   *slitem;
5984
5985         plan->targetlist = lefttree->targetlist;
5986         plan->qual = NIL;
5987         plan->lefttree = lefttree;
5988         plan->righttree = NULL;
5989
5990         /*
5991          * convert SortGroupClause list into arrays of attr indexes and equality
5992          * operators, as wanted by executor
5993          */
5994         Assert(numCols > 0);
5995         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
5996         uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);
5997
5998         foreach(slitem, distinctList)
5999         {
6000                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
6001                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
6002
6003                 uniqColIdx[keyno] = tle->resno;
6004                 uniqOperators[keyno] = sortcl->eqop;
6005                 Assert(OidIsValid(uniqOperators[keyno]));
6006                 keyno++;
6007         }
6008
6009         node->numCols = numCols;
6010         node->uniqColIdx = uniqColIdx;
6011         node->uniqOperators = uniqOperators;
6012
6013         return node;
6014 }
6015
6016 /*
6017  * as above, but use pathkeys to identify the sort columns and semantics
6018  */
6019 static Unique *
6020 make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols)
6021 {
6022         Unique     *node = makeNode(Unique);
6023         Plan       *plan = &node->plan;
6024         int                     keyno = 0;
6025         AttrNumber *uniqColIdx;
6026         Oid                *uniqOperators;
6027         ListCell   *lc;
6028
6029         plan->targetlist = lefttree->targetlist;
6030         plan->qual = NIL;
6031         plan->lefttree = lefttree;
6032         plan->righttree = NULL;
6033
6034         /*
6035          * Convert pathkeys list into arrays of attr indexes and equality
6036          * operators, as wanted by executor.  This has a lot in common with
6037          * prepare_sort_from_pathkeys ... maybe unify sometime?
6038          */
6039         Assert(numCols >= 0 && numCols <= list_length(pathkeys));
6040         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
6041         uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);
6042
6043         foreach(lc, pathkeys)
6044         {
6045                 PathKey    *pathkey = (PathKey *) lfirst(lc);
6046                 EquivalenceClass *ec = pathkey->pk_eclass;
6047                 EquivalenceMember *em;
6048                 TargetEntry *tle = NULL;
6049                 Oid                     pk_datatype = InvalidOid;
6050                 Oid                     eqop;
6051                 ListCell   *j;
6052
6053                 /* Ignore pathkeys beyond the specified number of columns */
6054                 if (keyno >= numCols)
6055                         break;
6056
6057                 if (ec->ec_has_volatile)
6058                 {
6059                         /*
6060                          * If the pathkey's EquivalenceClass is volatile, then it must
6061                          * have come from an ORDER BY clause, and we have to match it to
6062                          * that same targetlist entry.
6063                          */
6064                         if (ec->ec_sortref == 0)        /* can't happen */
6065                                 elog(ERROR, "volatile EquivalenceClass has no sortref");
6066                         tle = get_sortgroupref_tle(ec->ec_sortref, plan->targetlist);
6067                         Assert(tle);
6068                         Assert(list_length(ec->ec_members) == 1);
6069                         pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
6070                 }
6071                 else
6072                 {
6073                         /*
6074                          * Otherwise, we can use any non-constant expression listed in the
6075                          * pathkey's EquivalenceClass.  For now, we take the first tlist
6076                          * item found in the EC.
6077                          */
6078                         foreach(j, plan->targetlist)
6079                         {
6080                                 tle = (TargetEntry *) lfirst(j);
6081                                 em = find_ec_member_for_tle(ec, tle, NULL);
6082                                 if (em)
6083                                 {
6084                                         /* found expr already in tlist */
6085                                         pk_datatype = em->em_datatype;
6086                                         break;
6087                                 }
6088                                 tle = NULL;
6089                         }
6090                 }
6091
6092                 if (!tle)
6093                         elog(ERROR, "could not find pathkey item to sort");
6094
6095                 /*
6096                  * Look up the correct equality operator from the PathKey's slightly
6097                  * abstracted representation.
6098                  */
6099                 eqop = get_opfamily_member(pathkey->pk_opfamily,
6100                                                                    pk_datatype,
6101                                                                    pk_datatype,
6102                                                                    BTEqualStrategyNumber);
6103                 if (!OidIsValid(eqop))  /* should not happen */
6104                         elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
6105                                  BTEqualStrategyNumber, pk_datatype, pk_datatype,
6106                                  pathkey->pk_opfamily);
6107
6108                 uniqColIdx[keyno] = tle->resno;
6109                 uniqOperators[keyno] = eqop;
6110
6111                 keyno++;
6112         }
6113
6114         node->numCols = numCols;
6115         node->uniqColIdx = uniqColIdx;
6116         node->uniqOperators = uniqOperators;
6117
6118         return node;
6119 }
6120
6121 static Gather *
6122 make_gather(List *qptlist,
6123                         List *qpqual,
6124                         int nworkers,
6125                         bool single_copy,
6126                         Plan *subplan)
6127 {
6128         Gather     *node = makeNode(Gather);
6129         Plan       *plan = &node->plan;
6130
6131         plan->targetlist = qptlist;
6132         plan->qual = qpqual;
6133         plan->lefttree = subplan;
6134         plan->righttree = NULL;
6135         node->num_workers = nworkers;
6136         node->single_copy = single_copy;
6137         node->invisible = false;
6138
6139         return node;
6140 }
6141
6142 /*
6143  * distinctList is a list of SortGroupClauses, identifying the targetlist
6144  * items that should be considered by the SetOp filter.  The input path must
6145  * already be sorted accordingly.
6146  */
6147 static SetOp *
6148 make_setop(SetOpCmd cmd, SetOpStrategy strategy, Plan *lefttree,
6149                    List *distinctList, AttrNumber flagColIdx, int firstFlag,
6150                    long numGroups)
6151 {
6152         SetOp      *node = makeNode(SetOp);
6153         Plan       *plan = &node->plan;
6154         int                     numCols = list_length(distinctList);
6155         int                     keyno = 0;
6156         AttrNumber *dupColIdx;
6157         Oid                *dupOperators;
6158         ListCell   *slitem;
6159
6160         plan->targetlist = lefttree->targetlist;
6161         plan->qual = NIL;
6162         plan->lefttree = lefttree;
6163         plan->righttree = NULL;
6164
6165         /*
6166          * convert SortGroupClause list into arrays of attr indexes and equality
6167          * operators, as wanted by executor
6168          */
6169         Assert(numCols > 0);
6170         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
6171         dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
6172
6173         foreach(slitem, distinctList)
6174         {
6175                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
6176                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
6177
6178                 dupColIdx[keyno] = tle->resno;
6179                 dupOperators[keyno] = sortcl->eqop;
6180                 Assert(OidIsValid(dupOperators[keyno]));
6181                 keyno++;
6182         }
6183
6184         node->cmd = cmd;
6185         node->strategy = strategy;
6186         node->numCols = numCols;
6187         node->dupColIdx = dupColIdx;
6188         node->dupOperators = dupOperators;
6189         node->flagColIdx = flagColIdx;
6190         node->firstFlag = firstFlag;
6191         node->numGroups = numGroups;
6192
6193         return node;
6194 }
6195
6196 /*
6197  * make_lockrows
6198  *        Build a LockRows plan node
6199  */
6200 static LockRows *
6201 make_lockrows(Plan *lefttree, List *rowMarks, int epqParam)
6202 {
6203         LockRows   *node = makeNode(LockRows);
6204         Plan       *plan = &node->plan;
6205
6206         plan->targetlist = lefttree->targetlist;
6207         plan->qual = NIL;
6208         plan->lefttree = lefttree;
6209         plan->righttree = NULL;
6210
6211         node->rowMarks = rowMarks;
6212         node->epqParam = epqParam;
6213
6214         return node;
6215 }
6216
6217 /*
6218  * make_limit
6219  *        Build a Limit plan node
6220  */
6221 Limit *
6222 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount)
6223 {
6224         Limit      *node = makeNode(Limit);
6225         Plan       *plan = &node->plan;
6226
6227         plan->targetlist = lefttree->targetlist;
6228         plan->qual = NIL;
6229         plan->lefttree = lefttree;
6230         plan->righttree = NULL;
6231
6232         node->limitOffset = limitOffset;
6233         node->limitCount = limitCount;
6234
6235         return node;
6236 }
6237
6238 /*
6239  * make_result
6240  *        Build a Result plan node
6241  */
6242 static Result *
6243 make_result(List *tlist,
6244                         Node *resconstantqual,
6245                         Plan *subplan)
6246 {
6247         Result     *node = makeNode(Result);
6248         Plan       *plan = &node->plan;
6249
6250         plan->targetlist = tlist;
6251         plan->qual = NIL;
6252         plan->lefttree = subplan;
6253         plan->righttree = NULL;
6254         node->resconstantqual = resconstantqual;
6255
6256         return node;
6257 }
6258
6259 /*
6260  * make_project_set
6261  *        Build a ProjectSet plan node
6262  */
6263 static ProjectSet *
6264 make_project_set(List *tlist,
6265                                  Plan *subplan)
6266 {
6267         ProjectSet *node = makeNode(ProjectSet);
6268         Plan       *plan = &node->plan;
6269
6270         plan->targetlist = tlist;
6271         plan->qual = NIL;
6272         plan->lefttree = subplan;
6273         plan->righttree = NULL;
6274
6275         return node;
6276 }
6277
6278 /*
6279  * make_modifytable
6280  *        Build a ModifyTable plan node
6281  */
6282 static ModifyTable *
6283 make_modifytable(PlannerInfo *root,
6284                                  CmdType operation, bool canSetTag,
6285                                  Index nominalRelation,
6286                                  List *resultRelations, List *subplans,
6287                                  List *withCheckOptionLists, List *returningLists,
6288                                  List *rowMarks, OnConflictExpr *onconflict, int epqParam)
6289 {
6290         ModifyTable *node = makeNode(ModifyTable);
6291         List       *fdw_private_list;
6292         Bitmapset  *direct_modify_plans;
6293         ListCell   *lc;
6294         int                     i;
6295
6296         Assert(list_length(resultRelations) == list_length(subplans));
6297         Assert(withCheckOptionLists == NIL ||
6298                    list_length(resultRelations) == list_length(withCheckOptionLists));
6299         Assert(returningLists == NIL ||
6300                    list_length(resultRelations) == list_length(returningLists));
6301
6302         node->plan.lefttree = NULL;
6303         node->plan.righttree = NULL;
6304         node->plan.qual = NIL;
6305         /* setrefs.c will fill in the targetlist, if needed */
6306         node->plan.targetlist = NIL;
6307
6308         node->operation = operation;
6309         node->canSetTag = canSetTag;
6310         node->nominalRelation = nominalRelation;
6311         node->resultRelations = resultRelations;
6312         node->resultRelIndex = -1;      /* will be set correctly in setrefs.c */
6313         node->plans = subplans;
6314         if (!onconflict)
6315         {
6316                 node->onConflictAction = ONCONFLICT_NONE;
6317                 node->onConflictSet = NIL;
6318                 node->onConflictWhere = NULL;
6319                 node->arbiterIndexes = NIL;
6320                 node->exclRelRTI = 0;
6321                 node->exclRelTlist = NIL;
6322         }
6323         else
6324         {
6325                 node->onConflictAction = onconflict->action;
6326                 node->onConflictSet = onconflict->onConflictSet;
6327                 node->onConflictWhere = onconflict->onConflictWhere;
6328
6329                 /*
6330                  * If a set of unique index inference elements was provided (an
6331                  * INSERT...ON CONFLICT "inference specification"), then infer
6332                  * appropriate unique indexes (or throw an error if none are
6333                  * available).
6334                  */
6335                 node->arbiterIndexes = infer_arbiter_indexes(root);
6336
6337                 node->exclRelRTI = onconflict->exclRelIndex;
6338                 node->exclRelTlist = onconflict->exclRelTlist;
6339         }
6340         node->withCheckOptionLists = withCheckOptionLists;
6341         node->returningLists = returningLists;
6342         node->rowMarks = rowMarks;
6343         node->epqParam = epqParam;
6344
6345         /*
6346          * For each result relation that is a foreign table, allow the FDW to
6347          * construct private plan data, and accumulate it all into a list.
6348          */
6349         fdw_private_list = NIL;
6350         direct_modify_plans = NULL;
6351         i = 0;
6352         foreach(lc, resultRelations)
6353         {
6354                 Index           rti = lfirst_int(lc);
6355                 FdwRoutine *fdwroutine;
6356                 List       *fdw_private;
6357                 bool            direct_modify;
6358
6359                 /*
6360                  * If possible, we want to get the FdwRoutine from our RelOptInfo for
6361                  * the table.  But sometimes we don't have a RelOptInfo and must get
6362                  * it the hard way.  (In INSERT, the target relation is not scanned,
6363                  * so it's not a baserel; and there are also corner cases for
6364                  * updatable views where the target rel isn't a baserel.)
6365                  */
6366                 if (rti < root->simple_rel_array_size &&
6367                         root->simple_rel_array[rti] != NULL)
6368                 {
6369                         RelOptInfo *resultRel = root->simple_rel_array[rti];
6370
6371                         fdwroutine = resultRel->fdwroutine;
6372                 }
6373                 else
6374                 {
6375                         RangeTblEntry *rte = planner_rt_fetch(rti, root);
6376
6377                         Assert(rte->rtekind == RTE_RELATION);
6378                         if (rte->relkind == RELKIND_FOREIGN_TABLE)
6379                                 fdwroutine = GetFdwRoutineByRelId(rte->relid);
6380                         else
6381                                 fdwroutine = NULL;
6382                 }
6383
6384                 /*
6385                  * If the target foreign table has any row-level triggers, we can't
6386                  * modify the foreign table directly.
6387                  */
6388                 direct_modify = false;
6389                 if (fdwroutine != NULL &&
6390                         fdwroutine->PlanDirectModify != NULL &&
6391                         fdwroutine->BeginDirectModify != NULL &&
6392                         fdwroutine->IterateDirectModify != NULL &&
6393                         fdwroutine->EndDirectModify != NULL &&
6394                         !has_row_triggers(root, rti, operation))
6395                         direct_modify = fdwroutine->PlanDirectModify(root, node, rti, i);
6396                 if (direct_modify)
6397                         direct_modify_plans = bms_add_member(direct_modify_plans, i);
6398
6399                 if (!direct_modify &&
6400                         fdwroutine != NULL &&
6401                         fdwroutine->PlanForeignModify != NULL)
6402                         fdw_private = fdwroutine->PlanForeignModify(root, node, rti, i);
6403                 else
6404                         fdw_private = NIL;
6405                 fdw_private_list = lappend(fdw_private_list, fdw_private);
6406                 i++;
6407         }
6408         node->fdwPrivLists = fdw_private_list;
6409         node->fdwDirectModifyPlans = direct_modify_plans;
6410
6411         return node;
6412 }
6413
6414 /*
6415  * is_projection_capable_path
6416  *              Check whether a given Path node is able to do projection.
6417  */
6418 bool
6419 is_projection_capable_path(Path *path)
6420 {
6421         /* Most plan types can project, so just list the ones that can't */
6422         switch (path->pathtype)
6423         {
6424                 case T_Hash:
6425                 case T_Material:
6426                 case T_Sort:
6427                 case T_Unique:
6428                 case T_SetOp:
6429                 case T_LockRows:
6430                 case T_Limit:
6431                 case T_ModifyTable:
6432                 case T_MergeAppend:
6433                 case T_RecursiveUnion:
6434                         return false;
6435                 case T_Append:
6436
6437                         /*
6438                          * Append can't project, but if it's being used to represent a
6439                          * dummy path, claim that it can project.  This prevents us from
6440                          * converting a rel from dummy to non-dummy status by applying a
6441                          * projection to its dummy path.
6442                          */
6443                         return IS_DUMMY_PATH(path);
6444                 case T_ProjectSet:
6445
6446                         /*
6447                          * Although ProjectSet certainly projects, say "no" because we
6448                          * don't want the planner to randomly replace its tlist with
6449                          * something else; the SRFs have to stay at top level.  This might
6450                          * get relaxed later.
6451                          */
6452                         return false;
6453                 default:
6454                         break;
6455         }
6456         return true;
6457 }
6458
6459 /*
6460  * is_projection_capable_plan
6461  *              Check whether a given Plan node is able to do projection.
6462  */
6463 bool
6464 is_projection_capable_plan(Plan *plan)
6465 {
6466         /* Most plan types can project, so just list the ones that can't */
6467         switch (nodeTag(plan))
6468         {
6469                 case T_Hash:
6470                 case T_Material:
6471                 case T_Sort:
6472                 case T_Unique:
6473                 case T_SetOp:
6474                 case T_LockRows:
6475                 case T_Limit:
6476                 case T_ModifyTable:
6477                 case T_Append:
6478                 case T_MergeAppend:
6479                 case T_RecursiveUnion:
6480                         return false;
6481                 case T_ProjectSet:
6482
6483                         /*
6484                          * Although ProjectSet certainly projects, say "no" because we
6485                          * don't want the planner to randomly replace its tlist with
6486                          * something else; the SRFs have to stay at top level.  This might
6487                          * get relaxed later.
6488                          */
6489                         return false;
6490                 default:
6491                         break;
6492         }
6493         return true;
6494 }