granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/createplan.c

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