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