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

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