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