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