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-2012, 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/skey.h"
  23 #include "foreign/fdwapi.h"
  24 #include "miscadmin.h"
  25 #include "nodes/makefuncs.h"
  26 #include "nodes/nodeFuncs.h"
  27 #include "optimizer/clauses.h"
  28 #include "optimizer/cost.h"
  29 #include "optimizer/paths.h"
  30 #include "optimizer/placeholder.h"
  31 #include "optimizer/plancat.h"
  32 #include "optimizer/planmain.h"
  33 #include "optimizer/predtest.h"
  34 #include "optimizer/restrictinfo.h"
  35 #include "optimizer/subselect.h"
  36 #include "optimizer/tlist.h"
  37 #include "optimizer/var.h"
  38 #include "parser/parse_clause.h"
  39 #include "parser/parsetree.h"
  40 #include "utils/lsyscache.h"
  41
  42
  43 static Plan *create_plan_recurse(PlannerInfo *root, Path *best_path);
  44 static Plan *create_scan_plan(PlannerInfo *root, Path *best_path);
  45 static List *build_relation_tlist(RelOptInfo *rel);
  46 static bool use_physical_tlist(PlannerInfo *root, RelOptInfo *rel);
  47 static void disuse_physical_tlist(Plan *plan, Path *path);
  48 static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals);
  49 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
  50 static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
  51 static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path);
  52 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
  53 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
  54 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
  55 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
  56                                         List *tlist, List *scan_clauses);
  57 static Scan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
  58                                           List *tlist, List *scan_clauses, bool indexonly);
  59 static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
  60                                                 BitmapHeapPath *best_path,
  61                                                 List *tlist, List *scan_clauses);
  62 static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
  63                                           List **qual, List **indexqual);
  64 static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
  65                                         List *tlist, List *scan_clauses);
  66 static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
  67                                                  List *tlist, List *scan_clauses);
  68 static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
  69                                                  List *tlist, List *scan_clauses);
  70 static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
  71                                            List *tlist, List *scan_clauses);
  72 static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path,
  73                                         List *tlist, List *scan_clauses);
  74 static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path,
  75                                                   List *tlist, List *scan_clauses);
  76 static ForeignScan *create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
  77                                                 List *tlist, List *scan_clauses);
  78 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
  79                                          Plan *outer_plan, Plan *inner_plan);
  80 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
  81                                           Plan *outer_plan, Plan *inner_plan);
  82 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
  83                                          Plan *outer_plan, Plan *inner_plan);
  84 static Node *replace_nestloop_params(PlannerInfo *root, Node *expr);
  85 static Node *replace_nestloop_params_mutator(Node *node, PlannerInfo *root);
  86 static List *fix_indexqual_references(PlannerInfo *root, IndexPath *index_path);
  87 static List *fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path);
  88 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol);
  89 static List *get_switched_clauses(List *clauses, Relids outerrelids);
  90 static List *order_qual_clauses(PlannerInfo *root, List *clauses);
  91 static void copy_path_costsize(Plan *dest, Path *src);
  92 static void copy_plan_costsize(Plan *dest, Plan *src);
  93 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
  94 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
  95                            Oid indexid, List *indexqual, List *indexqualorig,
  96                            List *indexorderby, List *indexorderbyorig,
  97                            ScanDirection indexscandir);
  98 static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual,
  99                                    Index scanrelid, Oid indexid,
 100                                    List *indexqual, List *indexorderby,
 101                                    List *indextlist,
 102                                    ScanDirection indexscandir);
 103 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
 104                                           List *indexqual,
 105                                           List *indexqualorig);
 106 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
 107                                          List *qpqual,
 108                                          Plan *lefttree,
 109                                          List *bitmapqualorig,
 110                                          Index scanrelid);
 111 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
 112                          List *tidquals);
 113 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
 114                                   Index scanrelid, Node *funcexpr, List *funccolnames,
 115                                   List *funccoltypes, List *funccoltypmods,
 116                                   List *funccolcollations);
 117 static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
 118                                 Index scanrelid, List *values_lists);
 119 static CteScan *make_ctescan(List *qptlist, List *qpqual,
 120                          Index scanrelid, int ctePlanId, int cteParam);
 121 static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
 122                                    Index scanrelid, int wtParam);
 123 static ForeignScan *make_foreignscan(List *qptlist, List *qpqual,
 124                                  Index scanrelid, bool fsSystemCol, FdwPlan *fdwplan);
 125 static BitmapAnd *make_bitmap_and(List *bitmapplans);
 126 static BitmapOr *make_bitmap_or(List *bitmapplans);
 127 static NestLoop *make_nestloop(List *tlist,
 128                           List *joinclauses, List *otherclauses, List *nestParams,
 129                           Plan *lefttree, Plan *righttree,
 130                           JoinType jointype);
 131 static HashJoin *make_hashjoin(List *tlist,
 132                           List *joinclauses, List *otherclauses,
 133                           List *hashclauses,
 134                           Plan *lefttree, Plan *righttree,
 135                           JoinType jointype);
 136 static Hash *make_hash(Plan *lefttree,
 137                   Oid skewTable,
 138                   AttrNumber skewColumn,
 139                   bool skewInherit,
 140                   Oid skewColType,
 141                   int32 skewColTypmod);
 142 static MergeJoin *make_mergejoin(List *tlist,
 143                            List *joinclauses, List *otherclauses,
 144                            List *mergeclauses,
 145                            Oid *mergefamilies,
 146                            Oid *mergecollations,
 147                            int *mergestrategies,
 148                            bool *mergenullsfirst,
 149                            Plan *lefttree, Plan *righttree,
 150                            JoinType jointype);
 151 static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
 152                   AttrNumber *sortColIdx, Oid *sortOperators,
 153                   Oid *collations, bool *nullsFirst,
 154                   double limit_tuples);
 155 static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
 156                                                    Plan *lefttree, List *pathkeys,
 157                                                    bool adjust_tlist_in_place,
 158                                                    int *p_numsortkeys,
 159                                                    AttrNumber **p_sortColIdx,
 160                                                    Oid **p_sortOperators,
 161                                                    Oid **p_collations,
 162                                                    bool **p_nullsFirst);
 163 static Material *make_material(Plan *lefttree);
 164
 165
 166 /*
 167  * create_plan
 168  *        Creates the access plan for a query by recursively processing the
 169  *        desired tree of pathnodes, starting at the node 'best_path'.  For
 170  *        every pathnode found, we create a corresponding plan node containing
 171  *        appropriate id, target list, and qualification information.
 172  *
 173  *        The tlists and quals in the plan tree are still in planner format,
 174  *        ie, Vars still correspond to the parser's numbering.  This will be
 175  *        fixed later by setrefs.c.
 176  *
 177  *        best_path is the best access path
 178  *
 179  *        Returns a Plan tree.
 180  */
 181 Plan *
 182 create_plan(PlannerInfo *root, Path *best_path)
 183 {
 184         Plan       *plan;
 185
 186         /* Initialize this module's private workspace in PlannerInfo */
 187         root->curOuterRels = NULL;
 188         root->curOuterParams = NIL;
 189
 190         /* Recursively process the path tree */
 191         plan = create_plan_recurse(root, best_path);
 192
 193         /* Check we successfully assigned all NestLoopParams to plan nodes */
 194         if (root->curOuterParams != NIL)
 195                 elog(ERROR, "failed to assign all NestLoopParams to plan nodes");
 196
 197         return plan;
 198 }
 199
 200 /*
 201  * create_plan_recurse
 202  *        Recursive guts of create_plan().
 203  */
 204 static Plan *
 205 create_plan_recurse(PlannerInfo *root, Path *best_path)
 206 {
 207         Plan       *plan;
 208
 209         switch (best_path->pathtype)
 210         {
 211                 case T_SeqScan:
 212                 case T_IndexScan:
 213                 case T_IndexOnlyScan:
 214                 case T_BitmapHeapScan:
 215                 case T_TidScan:
 216                 case T_SubqueryScan:
 217                 case T_FunctionScan:
 218                 case T_ValuesScan:
 219                 case T_CteScan:
 220                 case T_WorkTableScan:
 221                 case T_ForeignScan:
 222                         plan = create_scan_plan(root, best_path);
 223                         break;
 224                 case T_HashJoin:
 225                 case T_MergeJoin:
 226                 case T_NestLoop:
 227                         plan = create_join_plan(root,
 228                                                                         (JoinPath *) best_path);
 229                         break;
 230                 case T_Append:
 231                         plan = create_append_plan(root,
 232                                                                           (AppendPath *) best_path);
 233                         break;
 234                 case T_MergeAppend:
 235                         plan = create_merge_append_plan(root,
 236                                                                                         (MergeAppendPath *) best_path);
 237                         break;
 238                 case T_Result:
 239                         plan = (Plan *) create_result_plan(root,
 240                                                                                            (ResultPath *) best_path);
 241                         break;
 242                 case T_Material:
 243                         plan = (Plan *) create_material_plan(root,
 244                                                                                                  (MaterialPath *) best_path);
 245                         break;
 246                 case T_Unique:
 247                         plan = create_unique_plan(root,
 248                                                                           (UniquePath *) best_path);
 249                         break;
 250                 default:
 251                         elog(ERROR, "unrecognized node type: %d",
 252                                  (int) best_path->pathtype);
 253                         plan = NULL;            /* keep compiler quiet */
 254                         break;
 255         }
 256
 257         return plan;
 258 }
 259
 260 /*
 261  * create_scan_plan
 262  *       Create a scan plan for the parent relation of 'best_path'.
 263  */
 264 static Plan *
 265 create_scan_plan(PlannerInfo *root, Path *best_path)
 266 {
 267         RelOptInfo *rel = best_path->parent;
 268         List       *tlist;
 269         List       *scan_clauses;
 270         Plan       *plan;
 271
 272         /*
 273          * For table scans, rather than using the relation targetlist (which is
 274          * only those Vars actually needed by the query), we prefer to generate a
 275          * tlist containing all Vars in order.  This will allow the executor to
 276          * optimize away projection of the table tuples, if possible.  (Note that
 277          * planner.c may replace the tlist we generate here, forcing projection to
 278          * occur.)
 279          */
 280         if (use_physical_tlist(root, rel))
 281         {
 282                 if (best_path->pathtype == T_IndexOnlyScan)
 283                 {
 284                         /* For index-only scan, the preferred tlist is the index's */
 285                         tlist = copyObject(((IndexPath *) best_path)->indexinfo->indextlist);
 286                 }
 287                 else
 288                 {
 289                         tlist = build_physical_tlist(root, rel);
 290                         /* if fail because of dropped cols, use regular method */
 291                         if (tlist == NIL)
 292                                 tlist = build_relation_tlist(rel);
 293                 }
 294         }
 295         else
 296                 tlist = build_relation_tlist(rel);
 297
 298         /*
 299          * Extract the relevant restriction clauses from the parent relation. The
 300          * executor must apply all these restrictions during the scan, except for
 301          * pseudoconstants which we'll take care of below.
 302          */
 303         scan_clauses = rel->baserestrictinfo;
 304
 305         switch (best_path->pathtype)
 306         {
 307                 case T_SeqScan:
 308                         plan = (Plan *) create_seqscan_plan(root,
 309                                                                                                 best_path,
 310                                                                                                 tlist,
 311                                                                                                 scan_clauses);
 312                         break;
 313
 314                 case T_IndexScan:
 315                         plan = (Plan *) create_indexscan_plan(root,
 316                                                                                                   (IndexPath *) best_path,
 317                                                                                                   tlist,
 318                                                                                                   scan_clauses,
 319                                                                                                   false);
 320                         break;
 321
 322                 case T_IndexOnlyScan:
 323                         plan = (Plan *) create_indexscan_plan(root,
 324                                                                                                   (IndexPath *) best_path,
 325                                                                                                   tlist,
 326                                                                                                   scan_clauses,
 327                                                                                                   true);
 328                         break;
 329
 330                 case T_BitmapHeapScan:
 331                         plan = (Plan *) create_bitmap_scan_plan(root,
 332                                                                                                 (BitmapHeapPath *) best_path,
 333                                                                                                         tlist,
 334                                                                                                         scan_clauses);
 335                         break;
 336
 337                 case T_TidScan:
 338                         plan = (Plan *) create_tidscan_plan(root,
 339                                                                                                 (TidPath *) best_path,
 340                                                                                                 tlist,
 341                                                                                                 scan_clauses);
 342                         break;
 343
 344                 case T_SubqueryScan:
 345                         plan = (Plan *) create_subqueryscan_plan(root,
 346                                                                                                          best_path,
 347                                                                                                          tlist,
 348                                                                                                          scan_clauses);
 349                         break;
 350
 351                 case T_FunctionScan:
 352                         plan = (Plan *) create_functionscan_plan(root,
 353                                                                                                          best_path,
 354                                                                                                          tlist,
 355                                                                                                          scan_clauses);
 356                         break;
 357
 358                 case T_ValuesScan:
 359                         plan = (Plan *) create_valuesscan_plan(root,
 360                                                                                                    best_path,
 361                                                                                                    tlist,
 362                                                                                                    scan_clauses);
 363                         break;
 364
 365                 case T_CteScan:
 366                         plan = (Plan *) create_ctescan_plan(root,
 367                                                                                                 best_path,
 368                                                                                                 tlist,
 369                                                                                                 scan_clauses);
 370                         break;
 371
 372                 case T_WorkTableScan:
 373                         plan = (Plan *) create_worktablescan_plan(root,
 374                                                                                                           best_path,
 375                                                                                                           tlist,
 376                                                                                                           scan_clauses);
 377                         break;
 378
 379                 case T_ForeignScan:
 380                         plan = (Plan *) create_foreignscan_plan(root,
 381                                                                                                         (ForeignPath *) best_path,
 382                                                                                                         tlist,
 383                                                                                                         scan_clauses);
 384                         break;
 385
 386                 default:
 387                         elog(ERROR, "unrecognized node type: %d",
 388                                  (int) best_path->pathtype);
 389                         plan = NULL;            /* keep compiler quiet */
 390                         break;
 391         }
 392
 393         /*
 394          * If there are any pseudoconstant clauses attached to this node, insert a
 395          * gating Result node that evaluates the pseudoconstants as one-time
 396          * quals.
 397          */
 398         if (root->hasPseudoConstantQuals)
 399                 plan = create_gating_plan(root, plan, scan_clauses);
 400
 401         return plan;
 402 }
 403
 404 /*
 405  * Build a target list (ie, a list of TargetEntry) for a relation.
 406  */
 407 static List *
 408 build_relation_tlist(RelOptInfo *rel)
 409 {
 410         List       *tlist = NIL;
 411         int                     resno = 1;
 412         ListCell   *v;
 413
 414         foreach(v, rel->reltargetlist)
 415         {
 416                 /* Do we really need to copy here?      Not sure */
 417                 Node       *node = (Node *) copyObject(lfirst(v));
 418
 419                 tlist = lappend(tlist, makeTargetEntry((Expr *) node,
 420                                                                                            resno,
 421                                                                                            NULL,
 422                                                                                            false));
 423                 resno++;
 424         }
 425         return tlist;
 426 }
 427
 428 /*
 429  * use_physical_tlist
 430  *              Decide whether to use a tlist matching relation structure,
 431  *              rather than only those Vars actually referenced.
 432  */
 433 static bool
 434 use_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
 435 {
 436         int                     i;
 437         ListCell   *lc;
 438
 439         /*
 440          * We can do this for real relation scans, subquery scans, function scans,
 441          * values scans, and CTE scans (but not for, eg, joins).
 442          */
 443         if (rel->rtekind != RTE_RELATION &&
 444                 rel->rtekind != RTE_SUBQUERY &&
 445                 rel->rtekind != RTE_FUNCTION &&
 446                 rel->rtekind != RTE_VALUES &&
 447                 rel->rtekind != RTE_CTE)
 448                 return false;
 449
 450         /*
 451          * Can't do it with inheritance cases either (mainly because Append
 452          * doesn't project).
 453          */
 454         if (rel->reloptkind != RELOPT_BASEREL)
 455                 return false;
 456
 457         /*
 458          * Can't do it if any system columns or whole-row Vars are requested.
 459          * (This could possibly be fixed but would take some fragile assumptions
 460          * in setrefs.c, I think.)
 461          */
 462         for (i = rel->min_attr; i <= 0; i++)
 463         {
 464                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
 465                         return false;
 466         }
 467
 468         /*
 469          * Can't do it if the rel is required to emit any placeholder expressions,
 470          * either.
 471          */
 472         foreach(lc, root->placeholder_list)
 473         {
 474                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 475
 476                 if (bms_nonempty_difference(phinfo->ph_needed, rel->relids) &&
 477                         bms_is_subset(phinfo->ph_eval_at, rel->relids))
 478                         return false;
 479         }
 480
 481         return true;
 482 }
 483
 484 /*
 485  * disuse_physical_tlist
 486  *              Switch a plan node back to emitting only Vars actually referenced.
 487  *
 488  * If the plan node immediately above a scan would prefer to get only
 489  * needed Vars and not a physical tlist, it must call this routine to
 490  * undo the decision made by use_physical_tlist().      Currently, Hash, Sort,
 491  * and Material nodes want this, so they don't have to store useless columns.
 492  */
 493 static void
 494 disuse_physical_tlist(Plan *plan, Path *path)
 495 {
 496         /* Only need to undo it for path types handled by create_scan_plan() */
 497         switch (path->pathtype)
 498         {
 499                 case T_SeqScan:
 500                 case T_IndexScan:
 501                 case T_IndexOnlyScan:
 502                 case T_BitmapHeapScan:
 503                 case T_TidScan:
 504                 case T_SubqueryScan:
 505                 case T_FunctionScan:
 506                 case T_ValuesScan:
 507                 case T_CteScan:
 508                 case T_WorkTableScan:
 509                 case T_ForeignScan:
 510                         plan->targetlist = build_relation_tlist(path->parent);
 511                         break;
 512                 default:
 513                         break;
 514         }
 515 }
 516
 517 /*
 518  * create_gating_plan
 519  *        Deal with pseudoconstant qual clauses
 520  *
 521  * If the node's quals list includes any pseudoconstant quals, put them
 522  * into a gating Result node atop the already-built plan.  Otherwise,
 523  * return the plan as-is.
 524  *
 525  * Note that we don't change cost or size estimates when doing gating.
 526  * The costs of qual eval were already folded into the plan's startup cost.
 527  * Leaving the size alone amounts to assuming that the gating qual will
 528  * succeed, which is the conservative estimate for planning upper queries.
 529  * We certainly don't want to assume the output size is zero (unless the
 530  * gating qual is actually constant FALSE, and that case is dealt with in
 531  * clausesel.c).  Interpolating between the two cases is silly, because
 532  * it doesn't reflect what will really happen at runtime, and besides which
 533  * in most cases we have only a very bad idea of the probability of the gating
 534  * qual being true.
 535  */
 536 static Plan *
 537 create_gating_plan(PlannerInfo *root, Plan *plan, List *quals)
 538 {
 539         List       *pseudoconstants;
 540
 541         /* Sort into desirable execution order while still in RestrictInfo form */
 542         quals = order_qual_clauses(root, quals);
 543
 544         /* Pull out any pseudoconstant quals from the RestrictInfo list */
 545         pseudoconstants = extract_actual_clauses(quals, true);
 546
 547         if (!pseudoconstants)
 548                 return plan;
 549
 550         return (Plan *) make_result(root,
 551                                                                 plan->targetlist,
 552                                                                 (Node *) pseudoconstants,
 553                                                                 plan);
 554 }
 555
 556 /*
 557  * create_join_plan
 558  *        Create a join plan for 'best_path' and (recursively) plans for its
 559  *        inner and outer paths.
 560  */
 561 static Plan *
 562 create_join_plan(PlannerInfo *root, JoinPath *best_path)
 563 {
 564         Plan       *outer_plan;
 565         Plan       *inner_plan;
 566         Plan       *plan;
 567         Relids          saveOuterRels = root->curOuterRels;
 568
 569         outer_plan = create_plan_recurse(root, best_path->outerjoinpath);
 570
 571         /* For a nestloop, include outer relids in curOuterRels for inner side */
 572         if (best_path->path.pathtype == T_NestLoop)
 573                 root->curOuterRels = bms_union(root->curOuterRels,
 574                                                                    best_path->outerjoinpath->parent->relids);
 575
 576         inner_plan = create_plan_recurse(root, best_path->innerjoinpath);
 577
 578         switch (best_path->path.pathtype)
 579         {
 580                 case T_MergeJoin:
 581                         plan = (Plan *) create_mergejoin_plan(root,
 582                                                                                                   (MergePath *) best_path,
 583                                                                                                   outer_plan,
 584                                                                                                   inner_plan);
 585                         break;
 586                 case T_HashJoin:
 587                         plan = (Plan *) create_hashjoin_plan(root,
 588                                                                                                  (HashPath *) best_path,
 589                                                                                                  outer_plan,
 590                                                                                                  inner_plan);
 591                         break;
 592                 case T_NestLoop:
 593                         /* Restore curOuterRels */
 594                         bms_free(root->curOuterRels);
 595                         root->curOuterRels = saveOuterRels;
 596
 597                         plan = (Plan *) create_nestloop_plan(root,
 598                                                                                                  (NestPath *) best_path,
 599                                                                                                  outer_plan,
 600                                                                                                  inner_plan);
 601                         break;
 602                 default:
 603                         elog(ERROR, "unrecognized node type: %d",
 604                                  (int) best_path->path.pathtype);
 605                         plan = NULL;            /* keep compiler quiet */
 606                         break;
 607         }
 608
 609         /*
 610          * If there are any pseudoconstant clauses attached to this node, insert a
 611          * gating Result node that evaluates the pseudoconstants as one-time
 612          * quals.
 613          */
 614         if (root->hasPseudoConstantQuals)
 615                 plan = create_gating_plan(root, plan, best_path->joinrestrictinfo);
 616
 617 #ifdef NOT_USED
 618
 619         /*
 620          * * Expensive function pullups may have pulled local predicates * into
 621          * this path node.      Put them in the qpqual of the plan node. * JMH,
 622          * 6/15/92
 623          */
 624         if (get_loc_restrictinfo(best_path) != NIL)
 625                 set_qpqual((Plan) plan,
 626                                    list_concat(get_qpqual((Plan) plan),
 627                                            get_actual_clauses(get_loc_restrictinfo(best_path))));
 628 #endif
 629
 630         return plan;
 631 }
 632
 633 /*
 634  * create_append_plan
 635  *        Create an Append plan for 'best_path' and (recursively) plans
 636  *        for its subpaths.
 637  *
 638  *        Returns a Plan node.
 639  */
 640 static Plan *
 641 create_append_plan(PlannerInfo *root, AppendPath *best_path)
 642 {
 643         Append     *plan;
 644         List       *tlist = build_relation_tlist(best_path->path.parent);
 645         List       *subplans = NIL;
 646         ListCell   *subpaths;
 647
 648         /*
 649          * It is possible for the subplans list to contain only one entry, or even
 650          * no entries.  Handle these cases specially.
 651          *
 652          * XXX ideally, if there's just one entry, we'd not bother to generate an
 653          * Append node but just return the single child.  At the moment this does
 654          * not work because the varno of the child scan plan won't match the
 655          * parent-rel Vars it'll be asked to emit.
 656          */
 657         if (best_path->subpaths == NIL)
 658         {
 659                 /* Generate a Result plan with constant-FALSE gating qual */
 660                 return (Plan *) make_result(root,
 661                                                                         tlist,
 662                                                                         (Node *) list_make1(makeBoolConst(false,
 663                                                                                                                                           false)),
 664                                                                         NULL);
 665         }
 666
 667         /* Normal case with multiple subpaths */
 668         foreach(subpaths, best_path->subpaths)
 669         {
 670                 Path       *subpath = (Path *) lfirst(subpaths);
 671
 672                 subplans = lappend(subplans, create_plan_recurse(root, subpath));
 673         }
 674
 675         plan = make_append(subplans, tlist);
 676
 677         return (Plan *) plan;
 678 }
 679
 680 /*
 681  * create_merge_append_plan
 682  *        Create a MergeAppend plan for 'best_path' and (recursively) plans
 683  *        for its subpaths.
 684  *
 685  *        Returns a Plan node.
 686  */
 687 static Plan *
 688 create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
 689 {
 690         MergeAppend *node = makeNode(MergeAppend);
 691         Plan       *plan = &node->plan;
 692         List       *tlist = build_relation_tlist(best_path->path.parent);
 693         List       *pathkeys = best_path->path.pathkeys;
 694         List       *subplans = NIL;
 695         ListCell   *subpaths;
 696
 697         /*
 698          * We don't have the actual creation of the MergeAppend node split out
 699          * into a separate make_xxx function.  This is because we want to run
 700          * prepare_sort_from_pathkeys on it before we do so on the individual
 701          * child plans, to make cross-checking the sort info easier.
 702          */
 703         copy_path_costsize(plan, (Path *) best_path);
 704         plan->targetlist = tlist;
 705         plan->qual = NIL;
 706         plan->lefttree = NULL;
 707         plan->righttree = NULL;
 708
 709         /* Compute sort column info, and adjust MergeAppend's tlist as needed */
 710         (void) prepare_sort_from_pathkeys(root, plan, pathkeys,
 711                                                                           true,
 712                                                                           &node->numCols,
 713                                                                           &node->sortColIdx,
 714                                                                           &node->sortOperators,
 715                                                                           &node->collations,
 716                                                                           &node->nullsFirst);
 717
 718         /*
 719          * Now prepare the child plans.  We must apply prepare_sort_from_pathkeys
 720          * even to subplans that don't need an explicit sort, to make sure they
 721          * are returning the same sort key columns the MergeAppend expects.
 722          */
 723         foreach(subpaths, best_path->subpaths)
 724         {
 725                 Path       *subpath = (Path *) lfirst(subpaths);
 726                 Plan       *subplan;
 727                 int                     numsortkeys;
 728                 AttrNumber *sortColIdx;
 729                 Oid                *sortOperators;
 730                 Oid                *collations;
 731                 bool       *nullsFirst;
 732
 733                 /* Build the child plan */
 734                 subplan = create_plan_recurse(root, subpath);
 735
 736                 /* Compute sort column info, and adjust subplan's tlist as needed */
 737                 subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
 738                                                                                          false,
 739                                                                                          &numsortkeys,
 740                                                                                          &sortColIdx,
 741                                                                                          &sortOperators,
 742                                                                                          &collations,
 743                                                                                          &nullsFirst);
 744
 745                 /*
 746                  * Check that we got the same sort key information.  We just Assert
 747                  * that the sortops match, since those depend only on the pathkeys;
 748                  * but it seems like a good idea to check the sort column numbers
 749                  * explicitly, to ensure the tlists really do match up.
 750                  */
 751                 Assert(numsortkeys == node->numCols);
 752                 if (memcmp(sortColIdx, node->sortColIdx,
 753                                    numsortkeys * sizeof(AttrNumber)) != 0)
 754                         elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
 755                 Assert(memcmp(sortOperators, node->sortOperators,
 756                                           numsortkeys * sizeof(Oid)) == 0);
 757                 Assert(memcmp(collations, node->collations,
 758                                           numsortkeys * sizeof(Oid)) == 0);
 759                 Assert(memcmp(nullsFirst, node->nullsFirst,
 760                                           numsortkeys * sizeof(bool)) == 0);
 761
 762                 /* Now, insert a Sort node if subplan isn't sufficiently ordered */
 763                 if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
 764                         subplan = (Plan *) make_sort(root, subplan, numsortkeys,
 765                                                                                  sortColIdx, sortOperators,
 766                                                                                  collations, nullsFirst,
 767                                                                                  best_path->limit_tuples);
 768
 769                 subplans = lappend(subplans, subplan);
 770         }
 771
 772         node->mergeplans = subplans;
 773
 774         return (Plan *) node;
 775 }
 776
 777 /*
 778  * create_result_plan
 779  *        Create a Result plan for 'best_path'.
 780  *        This is only used for the case of a query with an empty jointree.
 781  *
 782  *        Returns a Plan node.
 783  */
 784 static Result *
 785 create_result_plan(PlannerInfo *root, ResultPath *best_path)
 786 {
 787         List       *tlist;
 788         List       *quals;
 789
 790         /* The tlist will be installed later, since we have no RelOptInfo */
 791         Assert(best_path->path.parent == NULL);
 792         tlist = NIL;
 793
 794         /* best_path->quals is just bare clauses */
 795
 796         quals = order_qual_clauses(root, best_path->quals);
 797
 798         return make_result(root, tlist, (Node *) quals, NULL);
 799 }
 800
 801 /*
 802  * create_material_plan
 803  *        Create a Material plan for 'best_path' and (recursively) plans
 804  *        for its subpaths.
 805  *
 806  *        Returns a Plan node.
 807  */
 808 static Material *
 809 create_material_plan(PlannerInfo *root, MaterialPath *best_path)
 810 {
 811         Material   *plan;
 812         Plan       *subplan;
 813
 814         subplan = create_plan_recurse(root, best_path->subpath);
 815
 816         /* We don't want any excess columns in the materialized tuples */
 817         disuse_physical_tlist(subplan, best_path->subpath);
 818
 819         plan = make_material(subplan);
 820
 821         copy_path_costsize(&plan->plan, (Path *) best_path);
 822
 823         return plan;
 824 }
 825
 826 /*
 827  * create_unique_plan
 828  *        Create a Unique plan for 'best_path' and (recursively) plans
 829  *        for its subpaths.
 830  *
 831  *        Returns a Plan node.
 832  */
 833 static Plan *
 834 create_unique_plan(PlannerInfo *root, UniquePath *best_path)
 835 {
 836         Plan       *plan;
 837         Plan       *subplan;
 838         List       *in_operators;
 839         List       *uniq_exprs;
 840         List       *newtlist;
 841         int                     nextresno;
 842         bool            newitems;
 843         int                     numGroupCols;
 844         AttrNumber *groupColIdx;
 845         int                     groupColPos;
 846         ListCell   *l;
 847
 848         subplan = create_plan_recurse(root, best_path->subpath);
 849
 850         /* Done if we don't need to do any actual unique-ifying */
 851         if (best_path->umethod == UNIQUE_PATH_NOOP)
 852                 return subplan;
 853
 854         /*
 855          * As constructed, the subplan has a "flat" tlist containing just the Vars
 856          * needed here and at upper levels.  The values we are supposed to
 857          * unique-ify may be expressions in these variables.  We have to add any
 858          * such expressions to the subplan's tlist.
 859          *
 860          * The subplan may have a "physical" tlist if it is a simple scan plan. If
 861          * we're going to sort, this should be reduced to the regular tlist, so
 862          * that we don't sort more data than we need to.  For hashing, the tlist
 863          * should be left as-is if we don't need to add any expressions; but if we
 864          * do have to add expressions, then a projection step will be needed at
 865          * runtime anyway, so we may as well remove unneeded items. Therefore
 866          * newtlist starts from build_relation_tlist() not just a copy of the
 867          * subplan's tlist; and we don't install it into the subplan unless we are
 868          * sorting or stuff has to be added.
 869          */
 870         in_operators = best_path->in_operators;
 871         uniq_exprs = best_path->uniq_exprs;
 872
 873         /* initialize modified subplan tlist as just the "required" vars */
 874         newtlist = build_relation_tlist(best_path->path.parent);
 875         nextresno = list_length(newtlist) + 1;
 876         newitems = false;
 877
 878         foreach(l, uniq_exprs)
 879         {
 880                 Node       *uniqexpr = lfirst(l);
 881                 TargetEntry *tle;
 882
 883                 tle = tlist_member(uniqexpr, newtlist);
 884                 if (!tle)
 885                 {
 886                         tle = makeTargetEntry((Expr *) uniqexpr,
 887                                                                   nextresno,
 888                                                                   NULL,
 889                                                                   false);
 890                         newtlist = lappend(newtlist, tle);
 891                         nextresno++;
 892                         newitems = true;
 893                 }
 894         }
 895
 896         if (newitems || best_path->umethod == UNIQUE_PATH_SORT)
 897         {
 898                 /*
 899                  * If the top plan node can't do projections, we need to add a Result
 900                  * node to help it along.
 901                  */
 902                 if (!is_projection_capable_plan(subplan))
 903                         subplan = (Plan *) make_result(root, newtlist, NULL, subplan);
 904                 else
 905                         subplan->targetlist = newtlist;
 906         }
 907
 908         /*
 909          * Build control information showing which subplan output columns are to
 910          * be examined by the grouping step.  Unfortunately we can't merge this
 911          * with the previous loop, since we didn't then know which version of the
 912          * subplan tlist we'd end up using.
 913          */
 914         newtlist = subplan->targetlist;
 915         numGroupCols = list_length(uniq_exprs);
 916         groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
 917
 918         groupColPos = 0;
 919         foreach(l, uniq_exprs)
 920         {
 921                 Node       *uniqexpr = lfirst(l);
 922                 TargetEntry *tle;
 923
 924                 tle = tlist_member(uniqexpr, newtlist);
 925                 if (!tle)                               /* shouldn't happen */
 926                         elog(ERROR, "failed to find unique expression in subplan tlist");
 927                 groupColIdx[groupColPos++] = tle->resno;
 928         }
 929
 930         if (best_path->umethod == UNIQUE_PATH_HASH)
 931         {
 932                 long            numGroups;
 933                 Oid                *groupOperators;
 934
 935                 numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
 936
 937                 /*
 938                  * Get the hashable equality operators for the Agg node to use.
 939                  * Normally these are the same as the IN clause operators, but if
 940                  * those are cross-type operators then the equality operators are the
 941                  * ones for the IN clause operators' RHS datatype.
 942                  */
 943                 groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
 944                 groupColPos = 0;
 945                 foreach(l, in_operators)
 946                 {
 947                         Oid                     in_oper = lfirst_oid(l);
 948                         Oid                     eq_oper;
 949
 950                         if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
 951                                 elog(ERROR, "could not find compatible hash operator for operator %u",
 952                                          in_oper);
 953                         groupOperators[groupColPos++] = eq_oper;
 954                 }
 955
 956                 /*
 957                  * Since the Agg node is going to project anyway, we can give it the
 958                  * minimum output tlist, without any stuff we might have added to the
 959                  * subplan tlist.
 960                  */
 961                 plan = (Plan *) make_agg(root,
 962                                                                  build_relation_tlist(best_path->path.parent),
 963                                                                  NIL,
 964                                                                  AGG_HASHED,
 965                                                                  NULL,
 966                                                                  numGroupCols,
 967                                                                  groupColIdx,
 968                                                                  groupOperators,
 969                                                                  numGroups,
 970                                                                  subplan);
 971         }
 972         else
 973         {
 974                 List       *sortList = NIL;
 975
 976                 /* Create an ORDER BY list to sort the input compatibly */
 977                 groupColPos = 0;
 978                 foreach(l, in_operators)
 979                 {
 980                         Oid                     in_oper = lfirst_oid(l);
 981                         Oid                     sortop;
 982                         Oid                     eqop;
 983                         TargetEntry *tle;
 984                         SortGroupClause *sortcl;
 985
 986                         sortop = get_ordering_op_for_equality_op(in_oper, false);
 987                         if (!OidIsValid(sortop))        /* shouldn't happen */
 988                                 elog(ERROR, "could not find ordering operator for equality operator %u",
 989                                          in_oper);
 990
 991                         /*
 992                          * The Unique node will need equality operators.  Normally these
 993                          * are the same as the IN clause operators, but if those are
 994                          * cross-type operators then the equality operators are the ones
 995                          * for the IN clause operators' RHS datatype.
 996                          */
 997                         eqop = get_equality_op_for_ordering_op(sortop, NULL);
 998                         if (!OidIsValid(eqop))          /* shouldn't happen */
 999                                 elog(ERROR, "could not find equality operator for ordering operator %u",
1000                                          sortop);
1001
1002                         tle = get_tle_by_resno(subplan->targetlist,
1003                                                                    groupColIdx[groupColPos]);
1004                         Assert(tle != NULL);
1005
1006                         sortcl = makeNode(SortGroupClause);
1007                         sortcl->tleSortGroupRef = assignSortGroupRef(tle,
1008                                                                                                                  subplan->targetlist);
1009                         sortcl->eqop = eqop;
1010                         sortcl->sortop = sortop;
1011                         sortcl->nulls_first = false;
1012                         sortcl->hashable = false;       /* no need to make this accurate */
1013                         sortList = lappend(sortList, sortcl);
1014                         groupColPos++;
1015                 }
1016                 plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
1017                 plan = (Plan *) make_unique(plan, sortList);
1018         }
1019
1020         /* Adjust output size estimate (other fields should be OK already) */
1021         plan->plan_rows = best_path->rows;
1022
1023         return plan;
1024 }
1025
1026
1027 /*****************************************************************************
1028  *
1029  *      BASE-RELATION SCAN METHODS
1030  *
1031  *****************************************************************************/
1032
1033
1034 /*
1035  * create_seqscan_plan
1036  *       Returns a seqscan plan for the base relation scanned by 'best_path'
1037  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1038  */
1039 static SeqScan *
1040 create_seqscan_plan(PlannerInfo *root, Path *best_path,
1041                                         List *tlist, List *scan_clauses)
1042 {
1043         SeqScan    *scan_plan;
1044         Index           scan_relid = best_path->parent->relid;
1045
1046         /* it should be a base rel... */
1047         Assert(scan_relid > 0);
1048         Assert(best_path->parent->rtekind == RTE_RELATION);
1049
1050         /* Sort clauses into best execution order */
1051         scan_clauses = order_qual_clauses(root, scan_clauses);
1052
1053         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1054         scan_clauses = extract_actual_clauses(scan_clauses, false);
1055
1056         scan_plan = make_seqscan(tlist,
1057                                                          scan_clauses,
1058                                                          scan_relid);
1059
1060         copy_path_costsize(&scan_plan->plan, best_path);
1061
1062         return scan_plan;
1063 }
1064
1065 /*
1066  * create_indexscan_plan
1067  *        Returns an indexscan plan for the base relation scanned by 'best_path'
1068  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1069  *
1070  * We use this for both plain IndexScans and IndexOnlyScans, because the
1071  * qual preprocessing work is the same for both.  Note that the caller tells
1072  * us which to build --- we don't look at best_path->path.pathtype, because
1073  * create_bitmap_subplan needs to be able to override the prior decision.
1074  */
1075 static Scan *
1076 create_indexscan_plan(PlannerInfo *root,
1077                                           IndexPath *best_path,
1078                                           List *tlist,
1079                                           List *scan_clauses,
1080                                           bool indexonly)
1081 {
1082         Scan       *scan_plan;
1083         List       *indexquals = best_path->indexquals;
1084         List       *indexorderbys = best_path->indexorderbys;
1085         Index           baserelid = best_path->path.parent->relid;
1086         Oid                     indexoid = best_path->indexinfo->indexoid;
1087         List       *qpqual;
1088         List       *stripped_indexquals;
1089         List       *fixed_indexquals;
1090         List       *fixed_indexorderbys;
1091         ListCell   *l;
1092
1093         /* it should be a base rel... */
1094         Assert(baserelid > 0);
1095         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1096
1097         /*
1098          * Build "stripped" indexquals structure (no RestrictInfos) to pass to
1099          * executor as indexqualorig
1100          */
1101         stripped_indexquals = get_actual_clauses(indexquals);
1102
1103         /*
1104          * The executor needs a copy with the indexkey on the left of each clause
1105          * and with index Vars substituted for table ones.
1106          */
1107         fixed_indexquals = fix_indexqual_references(root, best_path);
1108
1109         /*
1110          * Likewise fix up index attr references in the ORDER BY expressions.
1111          */
1112         fixed_indexorderbys = fix_indexorderby_references(root, best_path);
1113
1114         /*
1115          * If this is an innerjoin scan, the indexclauses will contain join
1116          * clauses that are not present in scan_clauses (since the passed-in value
1117          * is just the rel's baserestrictinfo list).  We must add these clauses to
1118          * scan_clauses to ensure they get checked.  In most cases we will remove
1119          * the join clauses again below, but if a join clause contains a special
1120          * operator, we need to make sure it gets into the scan_clauses.
1121          *
1122          * Note: pointer comparison should be enough to determine RestrictInfo
1123          * matches.
1124          */
1125         if (best_path->isjoininner)
1126                 scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
1127
1128         /*
1129          * The qpqual list must contain all restrictions not automatically handled
1130          * by the index.  All the predicates in the indexquals will be checked
1131          * (either by the index itself, or by nodeIndexscan.c), but if there are
1132          * any "special" operators involved then they must be included in qpqual.
1133          * The upshot is that qpqual must contain scan_clauses minus whatever
1134          * appears in indexquals.
1135          *
1136          * In normal cases simple pointer equality checks will be enough to spot
1137          * duplicate RestrictInfos, so we try that first.  In some situations
1138          * (particularly with OR'd index conditions) we may have scan_clauses that
1139          * are not equal to, but are logically implied by, the index quals; so we
1140          * also try a predicate_implied_by() check to see if we can discard quals
1141          * that way.  (predicate_implied_by assumes its first input contains only
1142          * immutable functions, so we have to check that.)
1143          *
1144          * We can also discard quals that are implied by a partial index's
1145          * predicate, but only in a plain SELECT; when scanning a target relation
1146          * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
1147          * plan so that they'll be properly rechecked by EvalPlanQual testing.
1148          */
1149         qpqual = NIL;
1150         foreach(l, scan_clauses)
1151         {
1152                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1153
1154                 Assert(IsA(rinfo, RestrictInfo));
1155                 if (rinfo->pseudoconstant)
1156                         continue;                       /* we may drop pseudoconstants here */
1157                 if (list_member_ptr(indexquals, rinfo))
1158                         continue;
1159                 if (!contain_mutable_functions((Node *) rinfo->clause))
1160                 {
1161                         List       *clausel = list_make1(rinfo->clause);
1162
1163                         if (predicate_implied_by(clausel, indexquals))
1164                                 continue;
1165                         if (best_path->indexinfo->indpred)
1166                         {
1167                                 if (baserelid != root->parse->resultRelation &&
1168                                         get_parse_rowmark(root->parse, baserelid) == NULL)
1169                                         if (predicate_implied_by(clausel,
1170                                                                                          best_path->indexinfo->indpred))
1171                                                 continue;
1172                         }
1173                 }
1174                 qpqual = lappend(qpqual, rinfo);
1175         }
1176
1177         /* Sort clauses into best execution order */
1178         qpqual = order_qual_clauses(root, qpqual);
1179
1180         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1181         qpqual = extract_actual_clauses(qpqual, false);
1182
1183         /*
1184          * We have to replace any outer-relation variables with nestloop params in
1185          * the indexqualorig, qpqual, and indexorderbyorig expressions.  A bit
1186          * annoying to have to do this separately from the processing in
1187          * fix_indexqual_references --- rethink this when generalizing the inner
1188          * indexscan support.  But note we can't really do this earlier because
1189          * it'd break the comparisons to predicates above ... (or would it?  Those
1190          * wouldn't have outer refs)
1191          */
1192         if (best_path->isjoininner)
1193         {
1194                 stripped_indexquals = (List *)
1195                         replace_nestloop_params(root, (Node *) stripped_indexquals);
1196                 qpqual = (List *)
1197                         replace_nestloop_params(root, (Node *) qpqual);
1198                 indexorderbys = (List *)
1199                         replace_nestloop_params(root, (Node *) indexorderbys);
1200         }
1201
1202         /* Finally ready to build the plan node */
1203         if (indexonly)
1204                 scan_plan = (Scan *) make_indexonlyscan(tlist,
1205                                                                                                 qpqual,
1206                                                                                                 baserelid,
1207                                                                                                 indexoid,
1208                                                                                                 fixed_indexquals,
1209                                                                                                 fixed_indexorderbys,
1210                                                                                                 best_path->indexinfo->indextlist,
1211                                                                                                 best_path->indexscandir);
1212         else
1213                 scan_plan = (Scan *) make_indexscan(tlist,
1214                                                                                         qpqual,
1215                                                                                         baserelid,
1216                                                                                         indexoid,
1217                                                                                         fixed_indexquals,
1218                                                                                         stripped_indexquals,
1219                                                                                         fixed_indexorderbys,
1220                                                                                         indexorderbys,
1221                                                                                         best_path->indexscandir);
1222
1223         copy_path_costsize(&scan_plan->plan, &best_path->path);
1224         /* use the indexscan-specific rows estimate, not the parent rel's */
1225         scan_plan->plan.plan_rows = best_path->rows;
1226
1227         return scan_plan;
1228 }
1229
1230 /*
1231  * create_bitmap_scan_plan
1232  *        Returns a bitmap scan plan for the base relation scanned by 'best_path'
1233  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1234  */
1235 static BitmapHeapScan *
1236 create_bitmap_scan_plan(PlannerInfo *root,
1237                                                 BitmapHeapPath *best_path,
1238                                                 List *tlist,
1239                                                 List *scan_clauses)
1240 {
1241         Index           baserelid = best_path->path.parent->relid;
1242         Plan       *bitmapqualplan;
1243         List       *bitmapqualorig;
1244         List       *indexquals;
1245         List       *qpqual;
1246         ListCell   *l;
1247         BitmapHeapScan *scan_plan;
1248
1249         /* it should be a base rel... */
1250         Assert(baserelid > 0);
1251         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1252
1253         /* Process the bitmapqual tree into a Plan tree and qual lists */
1254         bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
1255                                                                                    &bitmapqualorig, &indexquals);
1256
1257         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1258         scan_clauses = extract_actual_clauses(scan_clauses, false);
1259
1260         /*
1261          * If this is a innerjoin scan, the indexclauses will contain join clauses
1262          * that are not present in scan_clauses (since the passed-in value is just
1263          * the rel's baserestrictinfo list).  We must add these clauses to
1264          * scan_clauses to ensure they get checked.  In most cases we will remove
1265          * the join clauses again below, but if a join clause contains a special
1266          * operator, we need to make sure it gets into the scan_clauses.
1267          */
1268         if (best_path->isjoininner)
1269         {
1270                 scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
1271         }
1272
1273         /*
1274          * The qpqual list must contain all restrictions not automatically handled
1275          * by the index.  All the predicates in the indexquals will be checked
1276          * (either by the index itself, or by nodeBitmapHeapscan.c), but if there
1277          * are any "special" operators involved then they must be added to qpqual.
1278          * The upshot is that qpqual must contain scan_clauses minus whatever
1279          * appears in indexquals.
1280          *
1281          * In normal cases simple equal() checks will be enough to spot duplicate
1282          * clauses, so we try that first.  In some situations (particularly with
1283          * OR'd index conditions) we may have scan_clauses that are not equal to,
1284          * but are logically implied by, the index quals; so we also try a
1285          * predicate_implied_by() check to see if we can discard quals that way.
1286          * (predicate_implied_by assumes its first input contains only immutable
1287          * functions, so we have to check that.)
1288          *
1289          * Unlike create_indexscan_plan(), we need take no special thought here
1290          * for partial index predicates; this is because the predicate conditions
1291          * are already listed in bitmapqualorig and indexquals.  Bitmap scans have
1292          * to do it that way because predicate conditions need to be rechecked if
1293          * the scan becomes lossy.
1294          */
1295         qpqual = NIL;
1296         foreach(l, scan_clauses)
1297         {
1298                 Node       *clause = (Node *) lfirst(l);
1299
1300                 if (list_member(indexquals, clause))
1301                         continue;
1302                 if (!contain_mutable_functions(clause))
1303                 {
1304                         List       *clausel = list_make1(clause);
1305
1306                         if (predicate_implied_by(clausel, indexquals))
1307                                 continue;
1308                 }
1309                 qpqual = lappend(qpqual, clause);
1310         }
1311
1312         /* Sort clauses into best execution order */
1313         qpqual = order_qual_clauses(root, qpqual);
1314
1315         /*
1316          * When dealing with special operators, we will at this point have
1317          * duplicate clauses in qpqual and bitmapqualorig.      We may as well drop
1318          * 'em from bitmapqualorig, since there's no point in making the tests
1319          * twice.
1320          */
1321         bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
1322
1323         /* Finally ready to build the plan node */
1324         scan_plan = make_bitmap_heapscan(tlist,
1325                                                                          qpqual,
1326                                                                          bitmapqualplan,
1327                                                                          bitmapqualorig,
1328                                                                          baserelid);
1329
1330         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1331         /* use the indexscan-specific rows estimate, not the parent rel's */
1332         scan_plan->scan.plan.plan_rows = best_path->rows;
1333
1334         return scan_plan;
1335 }
1336
1337 /*
1338  * Given a bitmapqual tree, generate the Plan tree that implements it
1339  *
1340  * As byproducts, we also return in *qual and *indexqual the qual lists
1341  * (in implicit-AND form, without RestrictInfos) describing the original index
1342  * conditions and the generated indexqual conditions.  (These are the same in
1343  * simple cases, but when special index operators are involved, the former
1344  * list includes the special conditions while the latter includes the actual
1345  * indexable conditions derived from them.)  Both lists include partial-index
1346  * predicates, because we have to recheck predicates as well as index
1347  * conditions if the bitmap scan becomes lossy.
1348  *
1349  * Note: if you find yourself changing this, you probably need to change
1350  * make_restrictinfo_from_bitmapqual too.
1351  */
1352 static Plan *
1353 create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
1354                                           List **qual, List **indexqual)
1355 {
1356         Plan       *plan;
1357
1358         if (IsA(bitmapqual, BitmapAndPath))
1359         {
1360                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
1361                 List       *subplans = NIL;
1362                 List       *subquals = NIL;
1363                 List       *subindexquals = NIL;
1364                 ListCell   *l;
1365
1366                 /*
1367                  * There may well be redundant quals among the subplans, since a
1368                  * top-level WHERE qual might have gotten used to form several
1369                  * different index quals.  We don't try exceedingly hard to eliminate
1370                  * redundancies, but we do eliminate obvious duplicates by using
1371                  * list_concat_unique.
1372                  */
1373                 foreach(l, apath->bitmapquals)
1374                 {
1375                         Plan       *subplan;
1376                         List       *subqual;
1377                         List       *subindexqual;
1378
1379                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1380                                                                                         &subqual, &subindexqual);
1381                         subplans = lappend(subplans, subplan);
1382                         subquals = list_concat_unique(subquals, subqual);
1383                         subindexquals = list_concat_unique(subindexquals, subindexqual);
1384                 }
1385                 plan = (Plan *) make_bitmap_and(subplans);
1386                 plan->startup_cost = apath->path.startup_cost;
1387                 plan->total_cost = apath->path.total_cost;
1388                 plan->plan_rows =
1389                         clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
1390                 plan->plan_width = 0;   /* meaningless */
1391                 *qual = subquals;
1392                 *indexqual = subindexquals;
1393         }
1394         else if (IsA(bitmapqual, BitmapOrPath))
1395         {
1396                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
1397                 List       *subplans = NIL;
1398                 List       *subquals = NIL;
1399                 List       *subindexquals = NIL;
1400                 bool            const_true_subqual = false;
1401                 bool            const_true_subindexqual = false;
1402                 ListCell   *l;
1403
1404                 /*
1405                  * Here, we only detect qual-free subplans.  A qual-free subplan would
1406                  * cause us to generate "... OR true ..."  which we may as well reduce
1407                  * to just "true".      We do not try to eliminate redundant subclauses
1408                  * because (a) it's not as likely as in the AND case, and (b) we might
1409                  * well be working with hundreds or even thousands of OR conditions,
1410                  * perhaps from a long IN list.  The performance of list_append_unique
1411                  * would be unacceptable.
1412                  */
1413                 foreach(l, opath->bitmapquals)
1414                 {
1415                         Plan       *subplan;
1416                         List       *subqual;
1417                         List       *subindexqual;
1418
1419                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1420                                                                                         &subqual, &subindexqual);
1421                         subplans = lappend(subplans, subplan);
1422                         if (subqual == NIL)
1423                                 const_true_subqual = true;
1424                         else if (!const_true_subqual)
1425                                 subquals = lappend(subquals,
1426                                                                    make_ands_explicit(subqual));
1427                         if (subindexqual == NIL)
1428                                 const_true_subindexqual = true;
1429                         else if (!const_true_subindexqual)
1430                                 subindexquals = lappend(subindexquals,
1431                                                                                 make_ands_explicit(subindexqual));
1432                 }
1433
1434                 /*
1435                  * In the presence of ScalarArrayOpExpr quals, we might have built
1436                  * BitmapOrPaths with just one subpath; don't add an OR step.
1437                  */
1438                 if (list_length(subplans) == 1)
1439                 {
1440                         plan = (Plan *) linitial(subplans);
1441                 }
1442                 else
1443                 {
1444                         plan = (Plan *) make_bitmap_or(subplans);
1445                         plan->startup_cost = opath->path.startup_cost;
1446                         plan->total_cost = opath->path.total_cost;
1447                         plan->plan_rows =
1448                                 clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
1449                         plan->plan_width = 0;           /* meaningless */
1450                 }
1451
1452                 /*
1453                  * If there were constant-TRUE subquals, the OR reduces to constant
1454                  * TRUE.  Also, avoid generating one-element ORs, which could happen
1455                  * due to redundancy elimination or ScalarArrayOpExpr quals.
1456                  */
1457                 if (const_true_subqual)
1458                         *qual = NIL;
1459                 else if (list_length(subquals) <= 1)
1460                         *qual = subquals;
1461                 else
1462                         *qual = list_make1(make_orclause(subquals));
1463                 if (const_true_subindexqual)
1464                         *indexqual = NIL;
1465                 else if (list_length(subindexquals) <= 1)
1466                         *indexqual = subindexquals;
1467                 else
1468                         *indexqual = list_make1(make_orclause(subindexquals));
1469         }
1470         else if (IsA(bitmapqual, IndexPath))
1471         {
1472                 IndexPath  *ipath = (IndexPath *) bitmapqual;
1473                 IndexScan  *iscan;
1474                 ListCell   *l;
1475
1476                 /* Use the regular indexscan plan build machinery... */
1477                 iscan = (IndexScan *) create_indexscan_plan(root, ipath,
1478                                                                                                         NIL, NIL, false);
1479                 Assert(IsA(iscan, IndexScan));
1480                 /* then convert to a bitmap indexscan */
1481                 plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
1482                                                                                           iscan->indexid,
1483                                                                                           iscan->indexqual,
1484                                                                                           iscan->indexqualorig);
1485                 plan->startup_cost = 0.0;
1486                 plan->total_cost = ipath->indextotalcost;
1487                 plan->plan_rows =
1488                         clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
1489                 plan->plan_width = 0;   /* meaningless */
1490                 *qual = get_actual_clauses(ipath->indexclauses);
1491                 *indexqual = get_actual_clauses(ipath->indexquals);
1492                 foreach(l, ipath->indexinfo->indpred)
1493                 {
1494                         Expr       *pred = (Expr *) lfirst(l);
1495
1496                         /*
1497                          * We know that the index predicate must have been implied by the
1498                          * query condition as a whole, but it may or may not be implied by
1499                          * the conditions that got pushed into the bitmapqual.  Avoid
1500                          * generating redundant conditions.
1501                          */
1502                         if (!predicate_implied_by(list_make1(pred), ipath->indexclauses))
1503                         {
1504                                 *qual = lappend(*qual, pred);
1505                                 *indexqual = lappend(*indexqual, pred);
1506                         }
1507                 }
1508
1509                 /*
1510                  * Replace outer-relation variables with nestloop params, but only
1511                  * after doing the above comparisons to index predicates.
1512                  */
1513                 if (ipath->isjoininner)
1514                 {
1515                         *qual = (List *)
1516                                 replace_nestloop_params(root, (Node *) *qual);
1517                         *indexqual = (List *)
1518                                 replace_nestloop_params(root, (Node *) *indexqual);
1519                 }
1520         }
1521         else
1522         {
1523                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
1524                 plan = NULL;                    /* keep compiler quiet */
1525         }
1526
1527         return plan;
1528 }
1529
1530 /*
1531  * create_tidscan_plan
1532  *       Returns a tidscan plan for the base relation scanned by 'best_path'
1533  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1534  */
1535 static TidScan *
1536 create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
1537                                         List *tlist, List *scan_clauses)
1538 {
1539         TidScan    *scan_plan;
1540         Index           scan_relid = best_path->path.parent->relid;
1541         List       *ortidquals;
1542
1543         /* it should be a base rel... */
1544         Assert(scan_relid > 0);
1545         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1546
1547         /* Sort clauses into best execution order */
1548         scan_clauses = order_qual_clauses(root, scan_clauses);
1549
1550         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1551         scan_clauses = extract_actual_clauses(scan_clauses, false);
1552
1553         /*
1554          * Remove any clauses that are TID quals.  This is a bit tricky since the
1555          * tidquals list has implicit OR semantics.
1556          */
1557         ortidquals = best_path->tidquals;
1558         if (list_length(ortidquals) > 1)
1559                 ortidquals = list_make1(make_orclause(ortidquals));
1560         scan_clauses = list_difference(scan_clauses, ortidquals);
1561
1562         scan_plan = make_tidscan(tlist,
1563                                                          scan_clauses,
1564                                                          scan_relid,
1565                                                          best_path->tidquals);
1566
1567         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1568
1569         return scan_plan;
1570 }
1571
1572 /*
1573  * create_subqueryscan_plan
1574  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
1575  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1576  */
1577 static SubqueryScan *
1578 create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
1579                                                  List *tlist, List *scan_clauses)
1580 {
1581         SubqueryScan *scan_plan;
1582         Index           scan_relid = best_path->parent->relid;
1583
1584         /* it should be a subquery base rel... */
1585         Assert(scan_relid > 0);
1586         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
1587
1588         /* Sort clauses into best execution order */
1589         scan_clauses = order_qual_clauses(root, scan_clauses);
1590
1591         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1592         scan_clauses = extract_actual_clauses(scan_clauses, false);
1593
1594         scan_plan = make_subqueryscan(tlist,
1595                                                                   scan_clauses,
1596                                                                   scan_relid,
1597                                                                   best_path->parent->subplan);
1598
1599         copy_path_costsize(&scan_plan->scan.plan, best_path);
1600
1601         return scan_plan;
1602 }
1603
1604 /*
1605  * create_functionscan_plan
1606  *       Returns a functionscan plan for the base relation scanned by 'best_path'
1607  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1608  */
1609 static FunctionScan *
1610 create_functionscan_plan(PlannerInfo *root, Path *best_path,
1611                                                  List *tlist, List *scan_clauses)
1612 {
1613         FunctionScan *scan_plan;
1614         Index           scan_relid = best_path->parent->relid;
1615         RangeTblEntry *rte;
1616
1617         /* it should be a function base rel... */
1618         Assert(scan_relid > 0);
1619         rte = planner_rt_fetch(scan_relid, root);
1620         Assert(rte->rtekind == RTE_FUNCTION);
1621
1622         /* Sort clauses into best execution order */
1623         scan_clauses = order_qual_clauses(root, scan_clauses);
1624
1625         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1626         scan_clauses = extract_actual_clauses(scan_clauses, false);
1627
1628         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
1629                                                                   rte->funcexpr,
1630                                                                   rte->eref->colnames,
1631                                                                   rte->funccoltypes,
1632                                                                   rte->funccoltypmods,
1633                                                                   rte->funccolcollations);
1634
1635         copy_path_costsize(&scan_plan->scan.plan, best_path);
1636
1637         return scan_plan;
1638 }
1639
1640 /*
1641  * create_valuesscan_plan
1642  *       Returns a valuesscan plan for the base relation scanned by 'best_path'
1643  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1644  */
1645 static ValuesScan *
1646 create_valuesscan_plan(PlannerInfo *root, Path *best_path,
1647                                            List *tlist, List *scan_clauses)
1648 {
1649         ValuesScan *scan_plan;
1650         Index           scan_relid = best_path->parent->relid;
1651         RangeTblEntry *rte;
1652
1653         /* it should be a values base rel... */
1654         Assert(scan_relid > 0);
1655         rte = planner_rt_fetch(scan_relid, root);
1656         Assert(rte->rtekind == RTE_VALUES);
1657
1658         /* Sort clauses into best execution order */
1659         scan_clauses = order_qual_clauses(root, scan_clauses);
1660
1661         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1662         scan_clauses = extract_actual_clauses(scan_clauses, false);
1663
1664         scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
1665                                                                 rte->values_lists);
1666
1667         copy_path_costsize(&scan_plan->scan.plan, best_path);
1668
1669         return scan_plan;
1670 }
1671
1672 /*
1673  * create_ctescan_plan
1674  *       Returns a ctescan plan for the base relation scanned by 'best_path'
1675  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1676  */
1677 static CteScan *
1678 create_ctescan_plan(PlannerInfo *root, Path *best_path,
1679                                         List *tlist, List *scan_clauses)
1680 {
1681         CteScan    *scan_plan;
1682         Index           scan_relid = best_path->parent->relid;
1683         RangeTblEntry *rte;
1684         SubPlan    *ctesplan = NULL;
1685         int                     plan_id;
1686         int                     cte_param_id;
1687         PlannerInfo *cteroot;
1688         Index           levelsup;
1689         int                     ndx;
1690         ListCell   *lc;
1691
1692         Assert(scan_relid > 0);
1693         rte = planner_rt_fetch(scan_relid, root);
1694         Assert(rte->rtekind == RTE_CTE);
1695         Assert(!rte->self_reference);
1696
1697         /*
1698          * Find the referenced CTE, and locate the SubPlan previously made for it.
1699          */
1700         levelsup = rte->ctelevelsup;
1701         cteroot = root;
1702         while (levelsup-- > 0)
1703         {
1704                 cteroot = cteroot->parent_root;
1705                 if (!cteroot)                   /* shouldn't happen */
1706                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1707         }
1708
1709         /*
1710          * Note: cte_plan_ids can be shorter than cteList, if we are still working
1711          * on planning the CTEs (ie, this is a side-reference from another CTE).
1712          * So we mustn't use forboth here.
1713          */
1714         ndx = 0;
1715         foreach(lc, cteroot->parse->cteList)
1716         {
1717                 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
1718
1719                 if (strcmp(cte->ctename, rte->ctename) == 0)
1720                         break;
1721                 ndx++;
1722         }
1723         if (lc == NULL)                         /* shouldn't happen */
1724                 elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
1725         if (ndx >= list_length(cteroot->cte_plan_ids))
1726                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
1727         plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
1728         Assert(plan_id > 0);
1729         foreach(lc, cteroot->init_plans)
1730         {
1731                 ctesplan = (SubPlan *) lfirst(lc);
1732                 if (ctesplan->plan_id == plan_id)
1733                         break;
1734         }
1735         if (lc == NULL)                         /* shouldn't happen */
1736                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
1737
1738         /*
1739          * We need the CTE param ID, which is the sole member of the SubPlan's
1740          * setParam list.
1741          */
1742         cte_param_id = linitial_int(ctesplan->setParam);
1743
1744         /* Sort clauses into best execution order */
1745         scan_clauses = order_qual_clauses(root, scan_clauses);
1746
1747         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1748         scan_clauses = extract_actual_clauses(scan_clauses, false);
1749
1750         scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
1751                                                          plan_id, cte_param_id);
1752
1753         copy_path_costsize(&scan_plan->scan.plan, best_path);
1754
1755         return scan_plan;
1756 }
1757
1758 /*
1759  * create_worktablescan_plan
1760  *       Returns a worktablescan plan for the base relation scanned by 'best_path'
1761  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1762  */
1763 static WorkTableScan *
1764 create_worktablescan_plan(PlannerInfo *root, Path *best_path,
1765                                                   List *tlist, List *scan_clauses)
1766 {
1767         WorkTableScan *scan_plan;
1768         Index           scan_relid = best_path->parent->relid;
1769         RangeTblEntry *rte;
1770         Index           levelsup;
1771         PlannerInfo *cteroot;
1772
1773         Assert(scan_relid > 0);
1774         rte = planner_rt_fetch(scan_relid, root);
1775         Assert(rte->rtekind == RTE_CTE);
1776         Assert(rte->self_reference);
1777
1778         /*
1779          * We need to find the worktable param ID, which is in the plan level
1780          * that's processing the recursive UNION, which is one level *below* where
1781          * the CTE comes from.
1782          */
1783         levelsup = rte->ctelevelsup;
1784         if (levelsup == 0)                      /* shouldn't happen */
1785                 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1786         levelsup--;
1787         cteroot = root;
1788         while (levelsup-- > 0)
1789         {
1790                 cteroot = cteroot->parent_root;
1791                 if (!cteroot)                   /* shouldn't happen */
1792                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1793         }
1794         if (cteroot->wt_param_id < 0)           /* shouldn't happen */
1795                 elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename);
1796
1797         /* Sort clauses into best execution order */
1798         scan_clauses = order_qual_clauses(root, scan_clauses);
1799
1800         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1801         scan_clauses = extract_actual_clauses(scan_clauses, false);
1802
1803         scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
1804                                                                    cteroot->wt_param_id);
1805
1806         copy_path_costsize(&scan_plan->scan.plan, best_path);
1807
1808         return scan_plan;
1809 }
1810
1811 /*
1812  * create_foreignscan_plan
1813  *       Returns a foreignscan plan for the base relation scanned by 'best_path'
1814  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1815  */
1816 static ForeignScan *
1817 create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
1818                                                 List *tlist, List *scan_clauses)
1819 {
1820         ForeignScan *scan_plan;
1821         RelOptInfo *rel = best_path->path.parent;
1822         Index           scan_relid = rel->relid;
1823         RangeTblEntry *rte;
1824         bool            fsSystemCol;
1825         int                     i;
1826
1827         /* it should be a base rel... */
1828         Assert(scan_relid > 0);
1829         Assert(rel->rtekind == RTE_RELATION);
1830         rte = planner_rt_fetch(scan_relid, root);
1831         Assert(rte->rtekind == RTE_RELATION);
1832
1833         /* Sort clauses into best execution order */
1834         scan_clauses = order_qual_clauses(root, scan_clauses);
1835
1836         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1837         scan_clauses = extract_actual_clauses(scan_clauses, false);
1838
1839         /* Detect whether any system columns are requested from rel */
1840         fsSystemCol = false;
1841         for (i = rel->min_attr; i < 0; i++)
1842         {
1843                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
1844                 {
1845                         fsSystemCol = true;
1846                         break;
1847                 }
1848         }
1849
1850         scan_plan = make_foreignscan(tlist,
1851                                                                  scan_clauses,
1852                                                                  scan_relid,
1853                                                                  fsSystemCol,
1854                                                                  best_path->fdwplan);
1855
1856         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1857
1858         return scan_plan;
1859 }
1860
1861
1862 /*****************************************************************************
1863  *
1864  *      JOIN METHODS
1865  *
1866  *****************************************************************************/
1867
1868 static NestLoop *
1869 create_nestloop_plan(PlannerInfo *root,
1870                                          NestPath *best_path,
1871                                          Plan *outer_plan,
1872                                          Plan *inner_plan)
1873 {
1874         NestLoop   *join_plan;
1875         List       *tlist = build_relation_tlist(best_path->path.parent);
1876         List       *joinrestrictclauses = best_path->joinrestrictinfo;
1877         List       *joinclauses;
1878         List       *otherclauses;
1879         Relids          outerrelids;
1880         List       *nestParams;
1881         ListCell   *cell;
1882         ListCell   *prev;
1883         ListCell   *next;
1884
1885         /*
1886          * If the inner path is a nestloop inner indexscan, it might be using some
1887          * of the join quals as index quals, in which case we don't have to check
1888          * them again at the join node.  Remove any join quals that are redundant.
1889          */
1890         joinrestrictclauses =
1891                 select_nonredundant_join_clauses(root,
1892                                                                                  joinrestrictclauses,
1893                                                                                  best_path->innerjoinpath);
1894
1895         /* Sort join qual clauses into best execution order */
1896         joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
1897
1898         /* Get the join qual clauses (in plain expression form) */
1899         /* Any pseudoconstant clauses are ignored here */
1900         if (IS_OUTER_JOIN(best_path->jointype))
1901         {
1902                 extract_actual_join_clauses(joinrestrictclauses,
1903                                                                         &joinclauses, &otherclauses);
1904         }
1905         else
1906         {
1907                 /* We can treat all clauses alike for an inner join */
1908                 joinclauses = extract_actual_clauses(joinrestrictclauses, false);
1909                 otherclauses = NIL;
1910         }
1911
1912         /*
1913          * Identify any nestloop parameters that should be supplied by this join
1914          * node, and move them from root->curOuterParams to the nestParams list.
1915          */
1916         outerrelids = best_path->outerjoinpath->parent->relids;
1917         nestParams = NIL;
1918         prev = NULL;
1919         for (cell = list_head(root->curOuterParams); cell; cell = next)
1920         {
1921                 NestLoopParam *nlp = (NestLoopParam *) lfirst(cell);
1922
1923                 next = lnext(cell);
1924                 if (IsA(nlp->paramval, Var) &&
1925                         bms_is_member(nlp->paramval->varno, outerrelids))
1926                 {
1927                         root->curOuterParams = list_delete_cell(root->curOuterParams,
1928                                                                                                         cell, prev);
1929                         nestParams = lappend(nestParams, nlp);
1930                 }
1931                 else if (IsA(nlp->paramval, PlaceHolderVar) &&
1932                                  bms_overlap(((PlaceHolderVar *) nlp->paramval)->phrels,
1933                                                          outerrelids) &&
1934                                  bms_is_subset(find_placeholder_info(root,
1935                                                                                                          (PlaceHolderVar *) nlp->paramval,
1936                                                                                                          false)->ph_eval_at,
1937                                                            outerrelids))
1938                 {
1939                         root->curOuterParams = list_delete_cell(root->curOuterParams,
1940                                                                                                         cell, prev);
1941                         nestParams = lappend(nestParams, nlp);
1942                 }
1943                 else
1944                         prev = cell;
1945         }
1946
1947         join_plan = make_nestloop(tlist,
1948                                                           joinclauses,
1949                                                           otherclauses,
1950                                                           nestParams,
1951                                                           outer_plan,
1952                                                           inner_plan,
1953                                                           best_path->jointype);
1954
1955         copy_path_costsize(&join_plan->join.plan, &best_path->path);
1956
1957         return join_plan;
1958 }
1959
1960 static MergeJoin *
1961 create_mergejoin_plan(PlannerInfo *root,
1962                                           MergePath *best_path,
1963                                           Plan *outer_plan,
1964                                           Plan *inner_plan)
1965 {
1966         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1967         List       *joinclauses;
1968         List       *otherclauses;
1969         List       *mergeclauses;
1970         List       *outerpathkeys;
1971         List       *innerpathkeys;
1972         int                     nClauses;
1973         Oid                *mergefamilies;
1974         Oid                *mergecollations;
1975         int                *mergestrategies;
1976         bool       *mergenullsfirst;
1977         MergeJoin  *join_plan;
1978         int                     i;
1979         ListCell   *lc;
1980         ListCell   *lop;
1981         ListCell   *lip;
1982
1983         /* Sort join qual clauses into best execution order */
1984         /* NB: do NOT reorder the mergeclauses */
1985         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
1986
1987         /* Get the join qual clauses (in plain expression form) */
1988         /* Any pseudoconstant clauses are ignored here */
1989         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1990         {
1991                 extract_actual_join_clauses(joinclauses,
1992                                                                         &joinclauses, &otherclauses);
1993         }
1994         else
1995         {
1996                 /* We can treat all clauses alike for an inner join */
1997                 joinclauses = extract_actual_clauses(joinclauses, false);
1998                 otherclauses = NIL;
1999         }
2000
2001         /*
2002          * Remove the mergeclauses from the list of join qual clauses, leaving the
2003          * list of quals that must be checked as qpquals.
2004          */
2005         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
2006         joinclauses = list_difference(joinclauses, mergeclauses);
2007
2008         /*
2009          * Rearrange mergeclauses, if needed, so that the outer variable is always
2010          * on the left; mark the mergeclause restrictinfos with correct
2011          * outer_is_left status.
2012          */
2013         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
2014                                                          best_path->jpath.outerjoinpath->parent->relids);
2015
2016         /*
2017          * Create explicit sort nodes for the outer and inner paths if necessary.
2018          * Make sure there are no excess columns in the inputs if sorting.
2019          */
2020         if (best_path->outersortkeys)
2021         {
2022                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
2023                 outer_plan = (Plan *)
2024                         make_sort_from_pathkeys(root,
2025                                                                         outer_plan,
2026                                                                         best_path->outersortkeys,
2027                                                                         -1.0);
2028                 outerpathkeys = best_path->outersortkeys;
2029         }
2030         else
2031                 outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;
2032
2033         if (best_path->innersortkeys)
2034         {
2035                 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
2036                 inner_plan = (Plan *)
2037                         make_sort_from_pathkeys(root,
2038                                                                         inner_plan,
2039                                                                         best_path->innersortkeys,
2040                                                                         -1.0);
2041                 innerpathkeys = best_path->innersortkeys;
2042         }
2043         else
2044                 innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;
2045
2046         /*
2047          * If specified, add a materialize node to shield the inner plan from the
2048          * need to handle mark/restore.
2049          */
2050         if (best_path->materialize_inner)
2051         {
2052                 Plan       *matplan = (Plan *) make_material(inner_plan);
2053
2054                 /*
2055                  * We assume the materialize will not spill to disk, and therefore
2056                  * charge just cpu_operator_cost per tuple.  (Keep this estimate in
2057                  * sync with cost_mergejoin.)
2058                  */
2059                 copy_plan_costsize(matplan, inner_plan);
2060                 matplan->total_cost += cpu_operator_cost * matplan->plan_rows;
2061
2062                 inner_plan = matplan;
2063         }
2064
2065         /*
2066          * Compute the opfamily/collation/strategy/nullsfirst arrays needed by the
2067          * executor.  The information is in the pathkeys for the two inputs, but
2068          * we need to be careful about the possibility of mergeclauses sharing a
2069          * pathkey (compare find_mergeclauses_for_pathkeys()).
2070          */
2071         nClauses = list_length(mergeclauses);
2072         Assert(nClauses == list_length(best_path->path_mergeclauses));
2073         mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
2074         mergecollations = (Oid *) palloc(nClauses * sizeof(Oid));
2075         mergestrategies = (int *) palloc(nClauses * sizeof(int));
2076         mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));
2077
2078         lop = list_head(outerpathkeys);
2079         lip = list_head(innerpathkeys);
2080         i = 0;
2081         foreach(lc, best_path->path_mergeclauses)
2082         {
2083                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2084                 EquivalenceClass *oeclass;
2085                 EquivalenceClass *ieclass;
2086                 PathKey    *opathkey;
2087                 PathKey    *ipathkey;
2088                 EquivalenceClass *opeclass;
2089                 EquivalenceClass *ipeclass;
2090                 ListCell   *l2;
2091
2092                 /* fetch outer/inner eclass from mergeclause */
2093                 Assert(IsA(rinfo, RestrictInfo));
2094                 if (rinfo->outer_is_left)
2095                 {
2096                         oeclass = rinfo->left_ec;
2097                         ieclass = rinfo->right_ec;
2098                 }
2099                 else
2100                 {
2101                         oeclass = rinfo->right_ec;
2102                         ieclass = rinfo->left_ec;
2103                 }
2104                 Assert(oeclass != NULL);
2105                 Assert(ieclass != NULL);
2106
2107                 /*
2108                  * For debugging purposes, we check that the eclasses match the paths'
2109                  * pathkeys.  In typical cases the merge clauses are one-to-one with
2110                  * the pathkeys, but when dealing with partially redundant query
2111                  * conditions, we might have clauses that re-reference earlier path
2112                  * keys.  The case that we need to reject is where a pathkey is
2113                  * entirely skipped over.
2114                  *
2115                  * lop and lip reference the first as-yet-unused pathkey elements;
2116                  * it's okay to match them, or any element before them.  If they're
2117                  * NULL then we have found all pathkey elements to be used.
2118                  */
2119                 if (lop)
2120                 {
2121                         opathkey = (PathKey *) lfirst(lop);
2122                         opeclass = opathkey->pk_eclass;
2123                         if (oeclass == opeclass)
2124                         {
2125                                 /* fast path for typical case */
2126                                 lop = lnext(lop);
2127                         }
2128                         else
2129                         {
2130                                 /* redundant clauses ... must match something before lop */
2131                                 foreach(l2, outerpathkeys)
2132                                 {
2133                                         if (l2 == lop)
2134                                                 break;
2135                                         opathkey = (PathKey *) lfirst(l2);
2136                                         opeclass = opathkey->pk_eclass;
2137                                         if (oeclass == opeclass)
2138                                                 break;
2139                                 }
2140                                 if (oeclass != opeclass)
2141                                         elog(ERROR, "outer pathkeys do not match mergeclauses");
2142                         }
2143                 }
2144                 else
2145                 {
2146                         /* redundant clauses ... must match some already-used pathkey */
2147                         opathkey = NULL;
2148                         opeclass = NULL;
2149                         foreach(l2, outerpathkeys)
2150                         {
2151                                 opathkey = (PathKey *) lfirst(l2);
2152                                 opeclass = opathkey->pk_eclass;
2153                                 if (oeclass == opeclass)
2154                                         break;
2155                         }
2156                         if (l2 == NULL)
2157                                 elog(ERROR, "outer pathkeys do not match mergeclauses");
2158                 }
2159
2160                 if (lip)
2161                 {
2162                         ipathkey = (PathKey *) lfirst(lip);
2163                         ipeclass = ipathkey->pk_eclass;
2164                         if (ieclass == ipeclass)
2165                         {
2166                                 /* fast path for typical case */
2167                                 lip = lnext(lip);
2168                         }
2169                         else
2170                         {
2171                                 /* redundant clauses ... must match something before lip */
2172                                 foreach(l2, innerpathkeys)
2173                                 {
2174                                         if (l2 == lip)
2175                                                 break;
2176                                         ipathkey = (PathKey *) lfirst(l2);
2177                                         ipeclass = ipathkey->pk_eclass;
2178                                         if (ieclass == ipeclass)
2179                                                 break;
2180                                 }
2181                                 if (ieclass != ipeclass)
2182                                         elog(ERROR, "inner pathkeys do not match mergeclauses");
2183                         }
2184                 }
2185                 else
2186                 {
2187                         /* redundant clauses ... must match some already-used pathkey */
2188                         ipathkey = NULL;
2189                         ipeclass = NULL;
2190                         foreach(l2, innerpathkeys)
2191                         {
2192                                 ipathkey = (PathKey *) lfirst(l2);
2193                                 ipeclass = ipathkey->pk_eclass;
2194                                 if (ieclass == ipeclass)
2195                                         break;
2196                         }
2197                         if (l2 == NULL)
2198                                 elog(ERROR, "inner pathkeys do not match mergeclauses");
2199                 }
2200
2201                 /* pathkeys should match each other too (more debugging) */
2202                 if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
2203                         opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation ||
2204                         opathkey->pk_strategy != ipathkey->pk_strategy ||
2205                         opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
2206                         elog(ERROR, "left and right pathkeys do not match in mergejoin");
2207
2208                 /* OK, save info for executor */
2209                 mergefamilies[i] = opathkey->pk_opfamily;
2210                 mergecollations[i] = opathkey->pk_eclass->ec_collation;
2211                 mergestrategies[i] = opathkey->pk_strategy;
2212                 mergenullsfirst[i] = opathkey->pk_nulls_first;
2213                 i++;
2214         }
2215
2216         /*
2217          * Note: it is not an error if we have additional pathkey elements (i.e.,
2218          * lop or lip isn't NULL here).  The input paths might be better-sorted
2219          * than we need for the current mergejoin.
2220          */
2221
2222         /*
2223          * Now we can build the mergejoin node.
2224          */
2225         join_plan = make_mergejoin(tlist,
2226                                                            joinclauses,
2227                                                            otherclauses,
2228                                                            mergeclauses,
2229                                                            mergefamilies,
2230                                                            mergecollations,
2231                                                            mergestrategies,
2232                                                            mergenullsfirst,
2233                                                            outer_plan,
2234                                                            inner_plan,
2235                                                            best_path->jpath.jointype);
2236
2237         /* Costs of sort and material steps are included in path cost already */
2238         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
2239
2240         return join_plan;
2241 }
2242
2243 static HashJoin *
2244 create_hashjoin_plan(PlannerInfo *root,
2245                                          HashPath *best_path,
2246                                          Plan *outer_plan,
2247                                          Plan *inner_plan)
2248 {
2249         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
2250         List       *joinclauses;
2251         List       *otherclauses;
2252         List       *hashclauses;
2253         Oid                     skewTable = InvalidOid;
2254         AttrNumber      skewColumn = InvalidAttrNumber;
2255         bool            skewInherit = false;
2256         Oid                     skewColType = InvalidOid;
2257         int32           skewColTypmod = -1;
2258         HashJoin   *join_plan;
2259         Hash       *hash_plan;
2260
2261         /* Sort join qual clauses into best execution order */
2262         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
2263         /* There's no point in sorting the hash clauses ... */
2264
2265         /* Get the join qual clauses (in plain expression form) */
2266         /* Any pseudoconstant clauses are ignored here */
2267         if (IS_OUTER_JOIN(best_path->jpath.jointype))
2268         {
2269                 extract_actual_join_clauses(joinclauses,
2270                                                                         &joinclauses, &otherclauses);
2271         }
2272         else
2273         {
2274                 /* We can treat all clauses alike for an inner join */
2275                 joinclauses = extract_actual_clauses(joinclauses, false);
2276                 otherclauses = NIL;
2277         }
2278
2279         /*
2280          * Remove the hashclauses from the list of join qual clauses, leaving the
2281          * list of quals that must be checked as qpquals.
2282          */
2283         hashclauses = get_actual_clauses(best_path->path_hashclauses);
2284         joinclauses = list_difference(joinclauses, hashclauses);
2285
2286         /*
2287          * Rearrange hashclauses, if needed, so that the outer variable is always
2288          * on the left.
2289          */
2290         hashclauses = get_switched_clauses(best_path->path_hashclauses,
2291                                                          best_path->jpath.outerjoinpath->parent->relids);
2292
2293         /* We don't want any excess columns in the hashed tuples */
2294         disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
2295
2296         /* If we expect batching, suppress excess columns in outer tuples too */
2297         if (best_path->num_batches > 1)
2298                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
2299
2300         /*
2301          * If there is a single join clause and we can identify the outer variable
2302          * as a simple column reference, supply its identity for possible use in
2303          * skew optimization.  (Note: in principle we could do skew optimization
2304          * with multiple join clauses, but we'd have to be able to determine the
2305          * most common combinations of outer values, which we don't currently have
2306          * enough stats for.)
2307          */
2308         if (list_length(hashclauses) == 1)
2309         {
2310                 OpExpr     *clause = (OpExpr *) linitial(hashclauses);
2311                 Node       *node;
2312
2313                 Assert(is_opclause(clause));
2314                 node = (Node *) linitial(clause->args);
2315                 if (IsA(node, RelabelType))
2316                         node = (Node *) ((RelabelType *) node)->arg;
2317                 if (IsA(node, Var))
2318                 {
2319                         Var                *var = (Var *) node;
2320                         RangeTblEntry *rte;
2321
2322                         rte = root->simple_rte_array[var->varno];
2323                         if (rte->rtekind == RTE_RELATION)
2324                         {
2325                                 skewTable = rte->relid;
2326                                 skewColumn = var->varattno;
2327                                 skewInherit = rte->inh;
2328                                 skewColType = var->vartype;
2329                                 skewColTypmod = var->vartypmod;
2330                         }
2331                 }
2332         }
2333
2334         /*
2335          * Build the hash node and hash join node.
2336          */
2337         hash_plan = make_hash(inner_plan,
2338                                                   skewTable,
2339                                                   skewColumn,
2340                                                   skewInherit,
2341                                                   skewColType,
2342                                                   skewColTypmod);
2343         join_plan = make_hashjoin(tlist,
2344                                                           joinclauses,
2345                                                           otherclauses,
2346                                                           hashclauses,
2347                                                           outer_plan,
2348                                                           (Plan *) hash_plan,
2349                                                           best_path->jpath.jointype);
2350
2351         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
2352
2353         return join_plan;
2354 }
2355
2356
2357 /*****************************************************************************
2358  *
2359  *      SUPPORTING ROUTINES
2360  *
2361  *****************************************************************************/
2362
2363 /*
2364  * replace_nestloop_params
2365  *        Replace outer-relation Vars and PlaceHolderVars in the given expression
2366  *        with nestloop Params
2367  *
2368  * All Vars and PlaceHolderVars belonging to the relation(s) identified by
2369  * root->curOuterRels are replaced by Params, and entries are added to
2370  * root->curOuterParams if not already present.
2371  */
2372 static Node *
2373 replace_nestloop_params(PlannerInfo *root, Node *expr)
2374 {
2375         /* No setup needed for tree walk, so away we go */
2376         return replace_nestloop_params_mutator(expr, root);
2377 }
2378
2379 static Node *
2380 replace_nestloop_params_mutator(Node *node, PlannerInfo *root)
2381 {
2382         if (node == NULL)
2383                 return NULL;
2384         if (IsA(node, Var))
2385         {
2386                 Var                *var = (Var *) node;
2387                 Param      *param;
2388                 NestLoopParam *nlp;
2389                 ListCell   *lc;
2390
2391                 /* Upper-level Vars should be long gone at this point */
2392                 Assert(var->varlevelsup == 0);
2393                 /* If not to be replaced, we can just return the Var unmodified */
2394                 if (!bms_is_member(var->varno, root->curOuterRels))
2395                         return node;
2396                 /* Create a Param representing the Var */
2397                 param = assign_nestloop_param_var(root, var);
2398                 /* Is this param already listed in root->curOuterParams? */
2399                 foreach(lc, root->curOuterParams)
2400                 {
2401                         nlp = (NestLoopParam *) lfirst(lc);
2402                         if (nlp->paramno == param->paramid)
2403                         {
2404                                 Assert(equal(var, nlp->paramval));
2405                                 /* Present, so we can just return the Param */
2406                                 return (Node *) param;
2407                         }
2408                 }
2409                 /* No, so add it */
2410                 nlp = makeNode(NestLoopParam);
2411                 nlp->paramno = param->paramid;
2412                 nlp->paramval = var;
2413                 root->curOuterParams = lappend(root->curOuterParams, nlp);
2414                 /* And return the replacement Param */
2415                 return (Node *) param;
2416         }
2417         if (IsA(node, PlaceHolderVar))
2418         {
2419                 PlaceHolderVar *phv = (PlaceHolderVar *) node;
2420                 Param      *param;
2421                 NestLoopParam *nlp;
2422                 ListCell   *lc;
2423
2424                 /* Upper-level PlaceHolderVars should be long gone at this point */
2425                 Assert(phv->phlevelsup == 0);
2426
2427                 /*
2428                  * If not to be replaced, just return the PlaceHolderVar unmodified.
2429                  * We use bms_overlap as a cheap/quick test to see if the PHV might
2430                  * be evaluated in the outer rels, and then grab its PlaceHolderInfo
2431                  * to tell for sure.
2432                  */
2433                 if (!bms_overlap(phv->phrels, root->curOuterRels))
2434                         return node;
2435                 if (!bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
2436                                                    root->curOuterRels))
2437                         return node;
2438                 /* Create a Param representing the PlaceHolderVar */
2439                 param = assign_nestloop_param_placeholdervar(root, phv);
2440                 /* Is this param already listed in root->curOuterParams? */
2441                 foreach(lc, root->curOuterParams)
2442                 {
2443                         nlp = (NestLoopParam *) lfirst(lc);
2444                         if (nlp->paramno == param->paramid)
2445                         {
2446                                 Assert(equal(phv, nlp->paramval));
2447                                 /* Present, so we can just return the Param */
2448                                 return (Node *) param;
2449                         }
2450                 }
2451                 /* No, so add it */
2452                 nlp = makeNode(NestLoopParam);
2453                 nlp->paramno = param->paramid;
2454                 nlp->paramval = (Var *) phv;
2455                 root->curOuterParams = lappend(root->curOuterParams, nlp);
2456                 /* And return the replacement Param */
2457                 return (Node *) param;
2458         }
2459         return expression_tree_mutator(node,
2460                                                                    replace_nestloop_params_mutator,
2461                                                                    (void *) root);
2462 }
2463
2464 /*
2465  * fix_indexqual_references
2466  *        Adjust indexqual clauses to the form the executor's indexqual
2467  *        machinery needs.
2468  *
2469  * We have four tasks here:
2470  *      * Remove RestrictInfo nodes from the input clauses.
2471  *      * Replace any outer-relation Var or PHV nodes with nestloop Params.
2472  *        (XXX eventually, that responsibility should go elsewhere?)
2473  *      * Index keys must be represented by Var nodes with varattno set to the
2474  *        index's attribute number, not the attribute number in the original rel.
2475  *      * If the index key is on the right, commute the clause to put it on the
2476  *        left.
2477  *
2478  * The result is a modified copy of the path's indexquals list --- the
2479  * original is not changed.  Note also that the copy shares no substructure
2480  * with the original; this is needed in case there is a subplan in it (we need
2481  * two separate copies of the subplan tree, or things will go awry).
2482  */
2483 static List *
2484 fix_indexqual_references(PlannerInfo *root, IndexPath *index_path)
2485 {
2486         IndexOptInfo *index = index_path->indexinfo;
2487         List       *fixed_indexquals;
2488         ListCell   *lcc,
2489                            *lci;
2490
2491         fixed_indexquals = NIL;
2492
2493         forboth(lcc, index_path->indexquals, lci, index_path->indexqualcols)
2494         {
2495                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
2496                 int                     indexcol = lfirst_int(lci);
2497                 Node       *clause;
2498
2499                 Assert(IsA(rinfo, RestrictInfo));
2500
2501                 /*
2502                  * Replace any outer-relation variables with nestloop params.
2503                  *
2504                  * This also makes a copy of the clause, so it's safe to modify it
2505                  * in-place below.
2506                  */
2507                 clause = replace_nestloop_params(root, (Node *) rinfo->clause);
2508
2509                 if (IsA(clause, OpExpr))
2510                 {
2511                         OpExpr     *op = (OpExpr *) clause;
2512
2513                         if (list_length(op->args) != 2)
2514                                 elog(ERROR, "indexqual clause is not binary opclause");
2515
2516                         /*
2517                          * Check to see if the indexkey is on the right; if so, commute
2518                          * the clause.  The indexkey should be the side that refers to
2519                          * (only) the base relation.
2520                          */
2521                         if (!bms_equal(rinfo->left_relids, index->rel->relids))
2522                                 CommuteOpExpr(op);
2523
2524                         /*
2525                          * Now replace the indexkey expression with an index Var.
2526                          */
2527                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
2528                                                                                                            index,
2529                                                                                                            indexcol);
2530                 }
2531                 else if (IsA(clause, RowCompareExpr))
2532                 {
2533                         RowCompareExpr *rc = (RowCompareExpr *) clause;
2534                         Expr       *newrc;
2535                         List       *indexcolnos;
2536                         bool            var_on_left;
2537                         ListCell   *lca,
2538                                            *lcai;
2539
2540                         /*
2541                          * Re-discover which index columns are used in the rowcompare.
2542                          */
2543                         newrc = adjust_rowcompare_for_index(rc,
2544                                                                                                 index,
2545                                                                                                 indexcol,
2546                                                                                                 &indexcolnos,
2547                                                                                                 &var_on_left);
2548
2549                         /*
2550                          * Trouble if adjust_rowcompare_for_index thought the
2551                          * RowCompareExpr didn't match the index as-is; the clause should
2552                          * have gone through that routine already.
2553                          */
2554                         if (newrc != (Expr *) rc)
2555                                 elog(ERROR, "inconsistent results from adjust_rowcompare_for_index");
2556
2557                         /*
2558                          * Check to see if the indexkey is on the right; if so, commute
2559                          * the clause.
2560                          */
2561                         if (!var_on_left)
2562                                 CommuteRowCompareExpr(rc);
2563
2564                         /*
2565                          * Now replace the indexkey expressions with index Vars.
2566                          */
2567                         Assert(list_length(rc->largs) == list_length(indexcolnos));
2568                         forboth(lca, rc->largs, lcai, indexcolnos)
2569                         {
2570                                 lfirst(lca) = fix_indexqual_operand(lfirst(lca),
2571                                                                                                         index,
2572                                                                                                         lfirst_int(lcai));
2573                         }
2574                 }
2575                 else if (IsA(clause, ScalarArrayOpExpr))
2576                 {
2577                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
2578
2579                         /* Never need to commute... */
2580
2581                         /* Replace the indexkey expression with an index Var. */
2582                         linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
2583                                                                                                                  index,
2584                                                                                                                  indexcol);
2585                 }
2586                 else if (IsA(clause, NullTest))
2587                 {
2588                         NullTest   *nt = (NullTest *) clause;
2589
2590                         /* Replace the indexkey expression with an index Var. */
2591                         nt->arg = (Expr *) fix_indexqual_operand((Node *) nt->arg,
2592                                                                                                          index,
2593                                                                                                          indexcol);
2594                 }
2595                 else
2596                         elog(ERROR, "unsupported indexqual type: %d",
2597                                  (int) nodeTag(clause));
2598
2599                 fixed_indexquals = lappend(fixed_indexquals, clause);
2600         }
2601
2602         return fixed_indexquals;
2603 }
2604
2605 /*
2606  * fix_indexorderby_references
2607  *        Adjust indexorderby clauses to the form the executor's index
2608  *        machinery needs.
2609  *
2610  * This is a simplified version of fix_indexqual_references.  The input does
2611  * not have RestrictInfo nodes, and we assume that indxpath.c already
2612  * commuted the clauses to put the index keys on the left.      Also, we don't
2613  * bother to support any cases except simple OpExprs, since nothing else
2614  * is allowed for ordering operators.
2615  */
2616 static List *
2617 fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path)
2618 {
2619         IndexOptInfo *index = index_path->indexinfo;
2620         List       *fixed_indexorderbys;
2621         ListCell   *lcc,
2622                            *lci;
2623
2624         fixed_indexorderbys = NIL;
2625
2626         forboth(lcc, index_path->indexorderbys, lci, index_path->indexorderbycols)
2627         {
2628                 Node       *clause = (Node *) lfirst(lcc);
2629                 int                     indexcol = lfirst_int(lci);
2630
2631                 /*
2632                  * Replace any outer-relation variables with nestloop params.
2633                  *
2634                  * This also makes a copy of the clause, so it's safe to modify it
2635                  * in-place below.
2636                  */
2637                 clause = replace_nestloop_params(root, clause);
2638
2639                 if (IsA(clause, OpExpr))
2640                 {
2641                         OpExpr     *op = (OpExpr *) clause;
2642
2643                         if (list_length(op->args) != 2)
2644                                 elog(ERROR, "indexorderby clause is not binary opclause");
2645
2646                         /*
2647                          * Now replace the indexkey expression with an index Var.
2648                          */
2649                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
2650                                                                                                            index,
2651                                                                                                            indexcol);
2652                 }
2653                 else
2654                         elog(ERROR, "unsupported indexorderby type: %d",
2655                                  (int) nodeTag(clause));
2656
2657                 fixed_indexorderbys = lappend(fixed_indexorderbys, clause);
2658         }
2659
2660         return fixed_indexorderbys;
2661 }
2662
2663 /*
2664  * fix_indexqual_operand
2665  *        Convert an indexqual expression to a Var referencing the index column.
2666  *
2667  * We represent index keys by Var nodes having varno == INDEX_VAR and varattno
2668  * equal to the index's attribute number (index column position).
2669  *
2670  * Most of the code here is just for sanity cross-checking that the given
2671  * expression actually matches the index column it's claimed to.
2672  */
2673 static Node *
2674 fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol)
2675 {
2676         Var                *result;
2677         int                     pos;
2678         ListCell   *indexpr_item;
2679
2680         /*
2681          * Remove any binary-compatible relabeling of the indexkey
2682          */
2683         if (IsA(node, RelabelType))
2684                 node = (Node *) ((RelabelType *) node)->arg;
2685
2686         Assert(indexcol >= 0 && indexcol < index->ncolumns);
2687
2688         if (index->indexkeys[indexcol] != 0)
2689         {
2690                 /* It's a simple index column */
2691                 if (IsA(node, Var) &&
2692                         ((Var *) node)->varno == index->rel->relid &&
2693                         ((Var *) node)->varattno == index->indexkeys[indexcol])
2694                 {
2695                         result = (Var *) copyObject(node);
2696                         result->varno = INDEX_VAR;
2697                         result->varattno = indexcol + 1;
2698                         return (Node *) result;
2699                 }
2700                 else
2701                         elog(ERROR, "index key does not match expected index column");
2702         }
2703
2704         /* It's an index expression, so find and cross-check the expression */
2705         indexpr_item = list_head(index->indexprs);
2706         for (pos = 0; pos < index->ncolumns; pos++)
2707         {
2708                 if (index->indexkeys[pos] == 0)
2709                 {
2710                         if (indexpr_item == NULL)
2711                                 elog(ERROR, "too few entries in indexprs list");
2712                         if (pos == indexcol)
2713                         {
2714                                 Node       *indexkey;
2715
2716                                 indexkey = (Node *) lfirst(indexpr_item);
2717                                 if (indexkey && IsA(indexkey, RelabelType))
2718                                         indexkey = (Node *) ((RelabelType *) indexkey)->arg;
2719                                 if (equal(node, indexkey))
2720                                 {
2721                                         result = makeVar(INDEX_VAR, indexcol + 1,
2722                                                                          exprType(lfirst(indexpr_item)), -1,
2723                                                                          exprCollation(lfirst(indexpr_item)),
2724                                                                          0);
2725                                         return (Node *) result;
2726                                 }
2727                                 else
2728                                         elog(ERROR, "index key does not match expected index column");
2729                         }
2730                         indexpr_item = lnext(indexpr_item);
2731                 }
2732         }
2733
2734         /* Ooops... */
2735         elog(ERROR, "index key does not match expected index column");
2736         return NULL;                            /* keep compiler quiet */
2737 }
2738
2739 /*
2740  * get_switched_clauses
2741  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
2742  *        extract the bare clauses, and rearrange the elements within the
2743  *        clauses, if needed, so the outer join variable is on the left and
2744  *        the inner is on the right.  The original clause data structure is not
2745  *        touched; a modified list is returned.  We do, however, set the transient
2746  *        outer_is_left field in each RestrictInfo to show which side was which.
2747  */
2748 static List *
2749 get_switched_clauses(List *clauses, Relids outerrelids)
2750 {
2751         List       *t_list = NIL;
2752         ListCell   *l;
2753
2754         foreach(l, clauses)
2755         {
2756                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2757                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
2758
2759                 Assert(is_opclause(clause));
2760                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
2761                 {
2762                         /*
2763                          * Duplicate just enough of the structure to allow commuting the
2764                          * clause without changing the original list.  Could use
2765                          * copyObject, but a complete deep copy is overkill.
2766                          */
2767                         OpExpr     *temp = makeNode(OpExpr);
2768
2769                         temp->opno = clause->opno;
2770                         temp->opfuncid = InvalidOid;
2771                         temp->opresulttype = clause->opresulttype;
2772                         temp->opretset = clause->opretset;
2773                         temp->opcollid = clause->opcollid;
2774                         temp->inputcollid = clause->inputcollid;
2775                         temp->args = list_copy(clause->args);
2776                         temp->location = clause->location;
2777                         /* Commute it --- note this modifies the temp node in-place. */
2778                         CommuteOpExpr(temp);
2779                         t_list = lappend(t_list, temp);
2780                         restrictinfo->outer_is_left = false;
2781                 }
2782                 else
2783                 {
2784                         Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
2785                         t_list = lappend(t_list, clause);
2786                         restrictinfo->outer_is_left = true;
2787                 }
2788         }
2789         return t_list;
2790 }
2791
2792 /*
2793  * order_qual_clauses
2794  *              Given a list of qual clauses that will all be evaluated at the same
2795  *              plan node, sort the list into the order we want to check the quals
2796  *              in at runtime.
2797  *
2798  * Ideally the order should be driven by a combination of execution cost and
2799  * selectivity, but it's not immediately clear how to account for both,
2800  * and given the uncertainty of the estimates the reliability of the decisions
2801  * would be doubtful anyway.  So we just order by estimated per-tuple cost,
2802  * being careful not to change the order when (as is often the case) the
2803  * estimates are identical.
2804  *
2805  * Although this will work on either bare clauses or RestrictInfos, it's
2806  * much faster to apply it to RestrictInfos, since it can re-use cost
2807  * information that is cached in RestrictInfos.
2808  *
2809  * Note: some callers pass lists that contain entries that will later be
2810  * removed; this is the easiest way to let this routine see RestrictInfos
2811  * instead of bare clauses.  It's OK because we only sort by cost, but
2812  * a cost/selectivity combination would likely do the wrong thing.
2813  */
2814 static List *
2815 order_qual_clauses(PlannerInfo *root, List *clauses)
2816 {
2817         typedef struct
2818         {
2819                 Node       *clause;
2820                 Cost            cost;
2821         } QualItem;
2822         int                     nitems = list_length(clauses);
2823         QualItem   *items;
2824         ListCell   *lc;
2825         int                     i;
2826         List       *result;
2827
2828         /* No need to work hard for 0 or 1 clause */
2829         if (nitems <= 1)
2830                 return clauses;
2831
2832         /*
2833          * Collect the items and costs into an array.  This is to avoid repeated
2834          * cost_qual_eval work if the inputs aren't RestrictInfos.
2835          */
2836         items = (QualItem *) palloc(nitems * sizeof(QualItem));
2837         i = 0;
2838         foreach(lc, clauses)
2839         {
2840                 Node       *clause = (Node *) lfirst(lc);
2841                 QualCost        qcost;
2842
2843                 cost_qual_eval_node(&qcost, clause, root);
2844                 items[i].clause = clause;
2845                 items[i].cost = qcost.per_tuple;
2846                 i++;
2847         }
2848
2849         /*
2850          * Sort.  We don't use qsort() because it's not guaranteed stable for
2851          * equal keys.  The expected number of entries is small enough that a
2852          * simple insertion sort should be good enough.
2853          */
2854         for (i = 1; i < nitems; i++)
2855         {
2856                 QualItem        newitem = items[i];
2857                 int                     j;
2858
2859                 /* insert newitem into the already-sorted subarray */
2860                 for (j = i; j > 0; j--)
2861                 {
2862                         if (newitem.cost >= items[j - 1].cost)
2863                                 break;
2864                         items[j] = items[j - 1];
2865                 }
2866                 items[j] = newitem;
2867         }
2868
2869         /* Convert back to a list */
2870         result = NIL;
2871         for (i = 0; i < nitems; i++)
2872                 result = lappend(result, items[i].clause);
2873
2874         return result;
2875 }
2876
2877 /*
2878  * Copy cost and size info from a Path node to the Plan node created from it.
2879  * The executor usually won't use this info, but it's needed by EXPLAIN.
2880  */
2881 static void
2882 copy_path_costsize(Plan *dest, Path *src)
2883 {
2884         if (src)
2885         {
2886                 dest->startup_cost = src->startup_cost;
2887                 dest->total_cost = src->total_cost;
2888                 dest->plan_rows = src->parent->rows;
2889                 dest->plan_width = src->parent->width;
2890         }
2891         else
2892         {
2893                 dest->startup_cost = 0;
2894                 dest->total_cost = 0;
2895                 dest->plan_rows = 0;
2896                 dest->plan_width = 0;
2897         }
2898 }
2899
2900 /*
2901  * Copy cost and size info from a lower plan node to an inserted node.
2902  * (Most callers alter the info after copying it.)
2903  */
2904 static void
2905 copy_plan_costsize(Plan *dest, Plan *src)
2906 {
2907         if (src)
2908         {
2909                 dest->startup_cost = src->startup_cost;
2910                 dest->total_cost = src->total_cost;
2911                 dest->plan_rows = src->plan_rows;
2912                 dest->plan_width = src->plan_width;
2913         }
2914         else
2915         {
2916                 dest->startup_cost = 0;
2917                 dest->total_cost = 0;
2918                 dest->plan_rows = 0;
2919                 dest->plan_width = 0;
2920         }
2921 }
2922
2923
2924 /*****************************************************************************
2925  *
2926  *      PLAN NODE BUILDING ROUTINES
2927  *
2928  * Some of these are exported because they are called to build plan nodes
2929  * in contexts where we're not deriving the plan node from a path node.
2930  *
2931  *****************************************************************************/
2932
2933 static SeqScan *
2934 make_seqscan(List *qptlist,
2935                          List *qpqual,
2936                          Index scanrelid)
2937 {
2938         SeqScan    *node = makeNode(SeqScan);
2939         Plan       *plan = &node->plan;
2940
2941         /* cost should be inserted by caller */
2942         plan->targetlist = qptlist;
2943         plan->qual = qpqual;
2944         plan->lefttree = NULL;
2945         plan->righttree = NULL;
2946         node->scanrelid = scanrelid;
2947
2948         return node;
2949 }
2950
2951 static IndexScan *
2952 make_indexscan(List *qptlist,
2953                            List *qpqual,
2954                            Index scanrelid,
2955                            Oid indexid,
2956                            List *indexqual,
2957                            List *indexqualorig,
2958                            List *indexorderby,
2959                            List *indexorderbyorig,
2960                            ScanDirection indexscandir)
2961 {
2962         IndexScan  *node = makeNode(IndexScan);
2963         Plan       *plan = &node->scan.plan;
2964
2965         /* cost should be inserted by caller */
2966         plan->targetlist = qptlist;
2967         plan->qual = qpqual;
2968         plan->lefttree = NULL;
2969         plan->righttree = NULL;
2970         node->scan.scanrelid = scanrelid;
2971         node->indexid = indexid;
2972         node->indexqual = indexqual;
2973         node->indexqualorig = indexqualorig;
2974         node->indexorderby = indexorderby;
2975         node->indexorderbyorig = indexorderbyorig;
2976         node->indexorderdir = indexscandir;
2977
2978         return node;
2979 }
2980
2981 static IndexOnlyScan *
2982 make_indexonlyscan(List *qptlist,
2983                                    List *qpqual,
2984                                    Index scanrelid,
2985                                    Oid indexid,
2986                                    List *indexqual,
2987                                    List *indexorderby,
2988                                    List *indextlist,
2989                                    ScanDirection indexscandir)
2990 {
2991         IndexOnlyScan *node = makeNode(IndexOnlyScan);
2992         Plan       *plan = &node->scan.plan;
2993
2994         /* cost should be inserted by caller */
2995         plan->targetlist = qptlist;
2996         plan->qual = qpqual;
2997         plan->lefttree = NULL;
2998         plan->righttree = NULL;
2999         node->scan.scanrelid = scanrelid;
3000         node->indexid = indexid;
3001         node->indexqual = indexqual;
3002         node->indexorderby = indexorderby;
3003         node->indextlist = indextlist;
3004         node->indexorderdir = indexscandir;
3005
3006         return node;
3007 }
3008
3009 static BitmapIndexScan *
3010 make_bitmap_indexscan(Index scanrelid,
3011                                           Oid indexid,
3012                                           List *indexqual,
3013                                           List *indexqualorig)
3014 {
3015         BitmapIndexScan *node = makeNode(BitmapIndexScan);
3016         Plan       *plan = &node->scan.plan;
3017
3018         /* cost should be inserted by caller */
3019         plan->targetlist = NIL;         /* not used */
3020         plan->qual = NIL;                       /* not used */
3021         plan->lefttree = NULL;
3022         plan->righttree = NULL;
3023         node->scan.scanrelid = scanrelid;
3024         node->indexid = indexid;
3025         node->indexqual = indexqual;
3026         node->indexqualorig = indexqualorig;
3027
3028         return node;
3029 }
3030
3031 static BitmapHeapScan *
3032 make_bitmap_heapscan(List *qptlist,
3033                                          List *qpqual,
3034                                          Plan *lefttree,
3035                                          List *bitmapqualorig,
3036                                          Index scanrelid)
3037 {
3038         BitmapHeapScan *node = makeNode(BitmapHeapScan);
3039         Plan       *plan = &node->scan.plan;
3040
3041         /* cost should be inserted by caller */
3042         plan->targetlist = qptlist;
3043         plan->qual = qpqual;
3044         plan->lefttree = lefttree;
3045         plan->righttree = NULL;
3046         node->scan.scanrelid = scanrelid;
3047         node->bitmapqualorig = bitmapqualorig;
3048
3049         return node;
3050 }
3051
3052 static TidScan *
3053 make_tidscan(List *qptlist,
3054                          List *qpqual,
3055                          Index scanrelid,
3056                          List *tidquals)
3057 {
3058         TidScan    *node = makeNode(TidScan);
3059         Plan       *plan = &node->scan.plan;
3060
3061         /* cost should be inserted by caller */
3062         plan->targetlist = qptlist;
3063         plan->qual = qpqual;
3064         plan->lefttree = NULL;
3065         plan->righttree = NULL;
3066         node->scan.scanrelid = scanrelid;
3067         node->tidquals = tidquals;
3068
3069         return node;
3070 }
3071
3072 SubqueryScan *
3073 make_subqueryscan(List *qptlist,
3074                                   List *qpqual,
3075                                   Index scanrelid,
3076                                   Plan *subplan)
3077 {
3078         SubqueryScan *node = makeNode(SubqueryScan);
3079         Plan       *plan = &node->scan.plan;
3080
3081         /*
3082          * Cost is figured here for the convenience of prepunion.c.  Note this is
3083          * only correct for the case where qpqual is empty; otherwise caller
3084          * should overwrite cost with a better estimate.
3085          */
3086         copy_plan_costsize(plan, subplan);
3087         plan->total_cost += cpu_tuple_cost * subplan->plan_rows;
3088
3089         plan->targetlist = qptlist;
3090         plan->qual = qpqual;
3091         plan->lefttree = NULL;
3092         plan->righttree = NULL;
3093         node->scan.scanrelid = scanrelid;
3094         node->subplan = subplan;
3095
3096         return node;
3097 }
3098
3099 static FunctionScan *
3100 make_functionscan(List *qptlist,
3101                                   List *qpqual,
3102                                   Index scanrelid,
3103                                   Node *funcexpr,
3104                                   List *funccolnames,
3105                                   List *funccoltypes,
3106                                   List *funccoltypmods,
3107                                   List *funccolcollations)
3108 {
3109         FunctionScan *node = makeNode(FunctionScan);
3110         Plan       *plan = &node->scan.plan;
3111
3112         /* cost should be inserted by caller */
3113         plan->targetlist = qptlist;
3114         plan->qual = qpqual;
3115         plan->lefttree = NULL;
3116         plan->righttree = NULL;
3117         node->scan.scanrelid = scanrelid;
3118         node->funcexpr = funcexpr;
3119         node->funccolnames = funccolnames;
3120         node->funccoltypes = funccoltypes;
3121         node->funccoltypmods = funccoltypmods;
3122         node->funccolcollations = funccolcollations;
3123
3124         return node;
3125 }
3126
3127 static ValuesScan *
3128 make_valuesscan(List *qptlist,
3129                                 List *qpqual,
3130                                 Index scanrelid,
3131                                 List *values_lists)
3132 {
3133         ValuesScan *node = makeNode(ValuesScan);
3134         Plan       *plan = &node->scan.plan;
3135
3136         /* cost should be inserted by caller */
3137         plan->targetlist = qptlist;
3138         plan->qual = qpqual;
3139         plan->lefttree = NULL;
3140         plan->righttree = NULL;
3141         node->scan.scanrelid = scanrelid;
3142         node->values_lists = values_lists;
3143
3144         return node;
3145 }
3146
3147 static CteScan *
3148 make_ctescan(List *qptlist,
3149                          List *qpqual,
3150                          Index scanrelid,
3151                          int ctePlanId,
3152                          int cteParam)
3153 {
3154         CteScan    *node = makeNode(CteScan);
3155         Plan       *plan = &node->scan.plan;
3156
3157         /* cost should be inserted by caller */
3158         plan->targetlist = qptlist;
3159         plan->qual = qpqual;
3160         plan->lefttree = NULL;
3161         plan->righttree = NULL;
3162         node->scan.scanrelid = scanrelid;
3163         node->ctePlanId = ctePlanId;
3164         node->cteParam = cteParam;
3165
3166         return node;
3167 }
3168
3169 static WorkTableScan *
3170 make_worktablescan(List *qptlist,
3171                                    List *qpqual,
3172                                    Index scanrelid,
3173                                    int wtParam)
3174 {
3175         WorkTableScan *node = makeNode(WorkTableScan);
3176         Plan       *plan = &node->scan.plan;
3177
3178         /* cost should be inserted by caller */
3179         plan->targetlist = qptlist;
3180         plan->qual = qpqual;
3181         plan->lefttree = NULL;
3182         plan->righttree = NULL;
3183         node->scan.scanrelid = scanrelid;
3184         node->wtParam = wtParam;
3185
3186         return node;
3187 }
3188
3189 static ForeignScan *
3190 make_foreignscan(List *qptlist,
3191                                  List *qpqual,
3192                                  Index scanrelid,
3193                                  bool fsSystemCol,
3194                                  FdwPlan *fdwplan)
3195 {
3196         ForeignScan *node = makeNode(ForeignScan);
3197         Plan       *plan = &node->scan.plan;
3198
3199         /* cost should be inserted by caller */
3200         plan->targetlist = qptlist;
3201         plan->qual = qpqual;
3202         plan->lefttree = NULL;
3203         plan->righttree = NULL;
3204         node->scan.scanrelid = scanrelid;
3205         node->fsSystemCol = fsSystemCol;
3206         node->fdwplan = fdwplan;
3207
3208         return node;
3209 }
3210
3211 Append *
3212 make_append(List *appendplans, List *tlist)
3213 {
3214         Append     *node = makeNode(Append);
3215         Plan       *plan = &node->plan;
3216         double          total_size;
3217         ListCell   *subnode;
3218
3219         /*
3220          * Compute cost as sum of subplan costs.  We charge nothing extra for the
3221          * Append itself, which perhaps is too optimistic, but since it doesn't do
3222          * any selection or projection, it is a pretty cheap node.
3223          *
3224          * If you change this, see also create_append_path().  Also, the size
3225          * calculations should match set_append_rel_pathlist().  It'd be better
3226          * not to duplicate all this logic, but some callers of this function
3227          * aren't working from an appendrel or AppendPath, so there's noplace to
3228          * copy the data from.
3229          */
3230         plan->startup_cost = 0;
3231         plan->total_cost = 0;
3232         plan->plan_rows = 0;
3233         total_size = 0;
3234         foreach(subnode, appendplans)
3235         {
3236                 Plan       *subplan = (Plan *) lfirst(subnode);
3237
3238                 if (subnode == list_head(appendplans))  /* first node? */
3239                         plan->startup_cost = subplan->startup_cost;
3240                 plan->total_cost += subplan->total_cost;
3241                 plan->plan_rows += subplan->plan_rows;
3242                 total_size += subplan->plan_width * subplan->plan_rows;
3243         }
3244         if (plan->plan_rows > 0)
3245                 plan->plan_width = rint(total_size / plan->plan_rows);
3246         else
3247                 plan->plan_width = 0;
3248
3249         plan->targetlist = tlist;
3250         plan->qual = NIL;
3251         plan->lefttree = NULL;
3252         plan->righttree = NULL;
3253         node->appendplans = appendplans;
3254
3255         return node;
3256 }
3257
3258 RecursiveUnion *
3259 make_recursive_union(List *tlist,
3260                                          Plan *lefttree,
3261                                          Plan *righttree,
3262                                          int wtParam,
3263                                          List *distinctList,
3264                                          long numGroups)
3265 {
3266         RecursiveUnion *node = makeNode(RecursiveUnion);
3267         Plan       *plan = &node->plan;
3268         int                     numCols = list_length(distinctList);
3269
3270         cost_recursive_union(plan, lefttree, righttree);
3271
3272         plan->targetlist = tlist;
3273         plan->qual = NIL;
3274         plan->lefttree = lefttree;
3275         plan->righttree = righttree;
3276         node->wtParam = wtParam;
3277
3278         /*
3279          * convert SortGroupClause list into arrays of attr indexes and equality
3280          * operators, as wanted by executor
3281          */
3282         node->numCols = numCols;
3283         if (numCols > 0)
3284         {
3285                 int                     keyno = 0;
3286                 AttrNumber *dupColIdx;
3287                 Oid                *dupOperators;
3288                 ListCell   *slitem;
3289
3290                 dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3291                 dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3292
3293                 foreach(slitem, distinctList)
3294                 {
3295                         SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
3296                         TargetEntry *tle = get_sortgroupclause_tle(sortcl,
3297                                                                                                            plan->targetlist);
3298
3299                         dupColIdx[keyno] = tle->resno;
3300                         dupOperators[keyno] = sortcl->eqop;
3301                         Assert(OidIsValid(dupOperators[keyno]));
3302                         keyno++;
3303                 }
3304                 node->dupColIdx = dupColIdx;
3305                 node->dupOperators = dupOperators;
3306         }
3307         node->numGroups = numGroups;
3308
3309         return node;
3310 }
3311
3312 static BitmapAnd *
3313 make_bitmap_and(List *bitmapplans)
3314 {
3315         BitmapAnd  *node = makeNode(BitmapAnd);
3316         Plan       *plan = &node->plan;
3317
3318         /* cost should be inserted by caller */
3319         plan->targetlist = NIL;
3320         plan->qual = NIL;
3321         plan->lefttree = NULL;
3322         plan->righttree = NULL;
3323         node->bitmapplans = bitmapplans;
3324
3325         return node;
3326 }
3327
3328 static BitmapOr *
3329 make_bitmap_or(List *bitmapplans)
3330 {
3331         BitmapOr   *node = makeNode(BitmapOr);
3332         Plan       *plan = &node->plan;
3333
3334         /* cost should be inserted by caller */
3335         plan->targetlist = NIL;
3336         plan->qual = NIL;
3337         plan->lefttree = NULL;
3338         plan->righttree = NULL;
3339         node->bitmapplans = bitmapplans;
3340
3341         return node;
3342 }
3343
3344 static NestLoop *
3345 make_nestloop(List *tlist,
3346                           List *joinclauses,
3347                           List *otherclauses,
3348                           List *nestParams,
3349                           Plan *lefttree,
3350                           Plan *righttree,
3351                           JoinType jointype)
3352 {
3353         NestLoop   *node = makeNode(NestLoop);
3354         Plan       *plan = &node->join.plan;
3355
3356         /* cost should be inserted by caller */
3357         plan->targetlist = tlist;
3358         plan->qual = otherclauses;
3359         plan->lefttree = lefttree;
3360         plan->righttree = righttree;
3361         node->join.jointype = jointype;
3362         node->join.joinqual = joinclauses;
3363         node->nestParams = nestParams;
3364
3365         return node;
3366 }
3367
3368 static HashJoin *
3369 make_hashjoin(List *tlist,
3370                           List *joinclauses,
3371                           List *otherclauses,
3372                           List *hashclauses,
3373                           Plan *lefttree,
3374                           Plan *righttree,
3375                           JoinType jointype)
3376 {
3377         HashJoin   *node = makeNode(HashJoin);
3378         Plan       *plan = &node->join.plan;
3379
3380         /* cost should be inserted by caller */
3381         plan->targetlist = tlist;
3382         plan->qual = otherclauses;
3383         plan->lefttree = lefttree;
3384         plan->righttree = righttree;
3385         node->hashclauses = hashclauses;
3386         node->join.jointype = jointype;
3387         node->join.joinqual = joinclauses;
3388
3389         return node;
3390 }
3391
3392 static Hash *
3393 make_hash(Plan *lefttree,
3394                   Oid skewTable,
3395                   AttrNumber skewColumn,
3396                   bool skewInherit,
3397                   Oid skewColType,
3398                   int32 skewColTypmod)
3399 {
3400         Hash       *node = makeNode(Hash);
3401         Plan       *plan = &node->plan;
3402
3403         copy_plan_costsize(plan, lefttree);
3404
3405         /*
3406          * For plausibility, make startup & total costs equal total cost of input
3407          * plan; this only affects EXPLAIN display not decisions.
3408          */
3409         plan->startup_cost = plan->total_cost;
3410         plan->targetlist = lefttree->targetlist;
3411         plan->qual = NIL;
3412         plan->lefttree = lefttree;
3413         plan->righttree = NULL;
3414
3415         node->skewTable = skewTable;
3416         node->skewColumn = skewColumn;
3417         node->skewInherit = skewInherit;
3418         node->skewColType = skewColType;
3419         node->skewColTypmod = skewColTypmod;
3420
3421         return node;
3422 }
3423
3424 static MergeJoin *
3425 make_mergejoin(List *tlist,
3426                            List *joinclauses,
3427                            List *otherclauses,
3428                            List *mergeclauses,
3429                            Oid *mergefamilies,
3430                            Oid *mergecollations,
3431                            int *mergestrategies,
3432                            bool *mergenullsfirst,
3433                            Plan *lefttree,
3434                            Plan *righttree,
3435                            JoinType jointype)
3436 {
3437         MergeJoin  *node = makeNode(MergeJoin);
3438         Plan       *plan = &node->join.plan;
3439
3440         /* cost should be inserted by caller */
3441         plan->targetlist = tlist;
3442         plan->qual = otherclauses;
3443         plan->lefttree = lefttree;
3444         plan->righttree = righttree;
3445         node->mergeclauses = mergeclauses;
3446         node->mergeFamilies = mergefamilies;
3447         node->mergeCollations = mergecollations;
3448         node->mergeStrategies = mergestrategies;
3449         node->mergeNullsFirst = mergenullsfirst;
3450         node->join.jointype = jointype;
3451         node->join.joinqual = joinclauses;
3452
3453         return node;
3454 }
3455
3456 /*
3457  * make_sort --- basic routine to build a Sort plan node
3458  *
3459  * Caller must have built the sortColIdx, sortOperators, collations, and
3460  * nullsFirst arrays already.
3461  * limit_tuples is as for cost_sort (in particular, pass -1 if no limit)
3462  */
3463 static Sort *
3464 make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
3465                   AttrNumber *sortColIdx, Oid *sortOperators,
3466                   Oid *collations, bool *nullsFirst,
3467                   double limit_tuples)
3468 {
3469         Sort       *node = makeNode(Sort);
3470         Plan       *plan = &node->plan;
3471         Path            sort_path;              /* dummy for result of cost_sort */
3472
3473         copy_plan_costsize(plan, lefttree); /* only care about copying size */
3474         cost_sort(&sort_path, root, NIL,
3475                           lefttree->total_cost,
3476                           lefttree->plan_rows,
3477                           lefttree->plan_width,
3478                           0.0,
3479                           work_mem,
3480                           limit_tuples);
3481         plan->startup_cost = sort_path.startup_cost;
3482         plan->total_cost = sort_path.total_cost;
3483         plan->targetlist = lefttree->targetlist;
3484         plan->qual = NIL;
3485         plan->lefttree = lefttree;
3486         plan->righttree = NULL;
3487         node->numCols = numCols;
3488         node->sortColIdx = sortColIdx;
3489         node->sortOperators = sortOperators;
3490         node->collations = collations;
3491         node->nullsFirst = nullsFirst;
3492
3493         return node;
3494 }
3495
3496 /*
3497  * add_sort_column --- utility subroutine for building sort info arrays
3498  *
3499  * We need this routine because the same column might be selected more than
3500  * once as a sort key column; if so, the extra mentions are redundant.
3501  *
3502  * Caller is assumed to have allocated the arrays large enough for the
3503  * max possible number of columns.      Return value is the new column count.
3504  */
3505 static int
3506 add_sort_column(AttrNumber colIdx, Oid sortOp, Oid coll, bool nulls_first,
3507                                 int numCols, AttrNumber *sortColIdx,
3508                                 Oid *sortOperators, Oid *collations, bool *nullsFirst)
3509 {
3510         int                     i;
3511
3512         Assert(OidIsValid(sortOp));
3513
3514         for (i = 0; i < numCols; i++)
3515         {
3516                 /*
3517                  * Note: we check sortOp because it's conceivable that "ORDER BY foo
3518                  * USING <, foo USING <<<" is not redundant, if <<< distinguishes
3519                  * values that < considers equal.  We need not check nulls_first
3520                  * however because a lower-order column with the same sortop but
3521                  * opposite nulls direction is redundant.
3522                  *
3523                  * We could probably consider sort keys with the same sortop and
3524                  * different collations to be redundant too, but for the moment treat
3525                  * them as not redundant.  This will be needed if we ever support
3526                  * collations with different notions of equality.
3527                  */
3528                 if (sortColIdx[i] == colIdx &&
3529                         sortOperators[numCols] == sortOp &&
3530                         collations[numCols] == coll)
3531                 {
3532                         /* Already sorting by this col, so extra sort key is useless */
3533                         return numCols;
3534                 }
3535         }
3536
3537         /* Add the column */
3538         sortColIdx[numCols] = colIdx;
3539         sortOperators[numCols] = sortOp;
3540         collations[numCols] = coll;
3541         nullsFirst[numCols] = nulls_first;
3542         return numCols + 1;
3543 }
3544
3545 /*
3546  * prepare_sort_from_pathkeys
3547  *        Prepare to sort according to given pathkeys
3548  *
3549  * This is used to set up for both Sort and MergeAppend nodes.  It calculates
3550  * the executor's representation of the sort key information, and adjusts the
3551  * plan targetlist if needed to add resjunk sort columns.
3552  *
3553  * Input parameters:
3554  *        'lefttree' is the node which yields input tuples
3555  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
3556  *        'adjust_tlist_in_place' is TRUE if lefttree must be modified in-place
3557  *
3558  * We must convert the pathkey information into arrays of sort key column
3559  * numbers, sort operator OIDs, collation OIDs, and nulls-first flags,
3560  * which is the representation the executor wants.      These are returned into
3561  * the output parameters *p_numsortkeys etc.
3562  *
3563  * If the pathkeys include expressions that aren't simple Vars, we will
3564  * usually need to add resjunk items to the input plan's targetlist to
3565  * compute these expressions, since the Sort/MergeAppend node itself won't
3566  * do any such calculations.  If the input plan type isn't one that can do
3567  * projections, this means adding a Result node just to do the projection.
3568  * However, the caller can pass adjust_tlist_in_place = TRUE to force the
3569  * lefttree tlist to be modified in-place regardless of whether the node type
3570  * can project --- we use this for fixing the tlist of MergeAppend itself.
3571  *
3572  * Returns the node which is to be the input to the Sort (either lefttree,
3573  * or a Result stacked atop lefttree).
3574  */
3575 static Plan *
3576 prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
3577                                                    bool adjust_tlist_in_place,
3578                                                    int *p_numsortkeys,
3579                                                    AttrNumber **p_sortColIdx,
3580                                                    Oid **p_sortOperators,
3581                                                    Oid **p_collations,
3582                                                    bool **p_nullsFirst)
3583 {
3584         List       *tlist = lefttree->targetlist;
3585         ListCell   *i;
3586         int                     numsortkeys;
3587         AttrNumber *sortColIdx;
3588         Oid                *sortOperators;
3589         Oid                *collations;
3590         bool       *nullsFirst;
3591
3592         /*
3593          * We will need at most list_length(pathkeys) sort columns; possibly less
3594          */
3595         numsortkeys = list_length(pathkeys);
3596         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3597         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3598         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3599         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3600
3601         numsortkeys = 0;
3602
3603         foreach(i, pathkeys)
3604         {
3605                 PathKey    *pathkey = (PathKey *) lfirst(i);
3606                 EquivalenceClass *ec = pathkey->pk_eclass;
3607                 TargetEntry *tle = NULL;
3608                 Oid                     pk_datatype = InvalidOid;
3609                 Oid                     sortop;
3610                 ListCell   *j;
3611
3612                 if (ec->ec_has_volatile)
3613                 {
3614                         /*
3615                          * If the pathkey's EquivalenceClass is volatile, then it must
3616                          * have come from an ORDER BY clause, and we have to match it to
3617                          * that same targetlist entry.
3618                          */
3619                         if (ec->ec_sortref == 0)        /* can't happen */
3620                                 elog(ERROR, "volatile EquivalenceClass has no sortref");
3621                         tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
3622                         Assert(tle);
3623                         Assert(list_length(ec->ec_members) == 1);
3624                         pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
3625                 }
3626                 else
3627                 {
3628                         /*
3629                          * Otherwise, we can sort by any non-constant expression listed in
3630                          * the pathkey's EquivalenceClass.  For now, we take the first one
3631                          * that corresponds to an available item in the tlist.  If there
3632                          * isn't any, use the first one that is an expression in the
3633                          * input's vars.  (The non-const restriction only matters if the
3634                          * EC is below_outer_join; but if it isn't, it won't contain
3635                          * consts anyway, else we'd have discarded the pathkey as
3636                          * redundant.)
3637                          *
3638                          * XXX if we have a choice, is there any way of figuring out which
3639                          * might be cheapest to execute?  (For example, int4lt is likely
3640                          * much cheaper to execute than numericlt, but both might appear
3641                          * in the same equivalence class...)  Not clear that we ever will
3642                          * have an interesting choice in practice, so it may not matter.
3643                          */
3644                         foreach(j, ec->ec_members)
3645                         {
3646                                 EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
3647
3648                                 /*
3649                                  * We shouldn't be trying to sort by an equivalence class that
3650                                  * contains a constant, so no need to consider such cases any
3651                                  * further.
3652                                  */
3653                                 if (em->em_is_const)
3654                                         continue;
3655
3656                                 tle = tlist_member((Node *) em->em_expr, tlist);
3657                                 if (tle)
3658                                 {
3659                                         pk_datatype = em->em_datatype;
3660                                         break;          /* found expr already in tlist */
3661                                 }
3662
3663                                 /*
3664                                  * We can also use it if the pathkey expression is a relabel
3665                                  * of the tlist entry, or vice versa.  This is needed for
3666                                  * binary-compatible cases (cf. make_pathkey_from_sortinfo).
3667                                  * We prefer an exact match, though, so we do the basic search
3668                                  * first.
3669                                  */
3670                                 tle = tlist_member_ignore_relabel((Node *) em->em_expr, tlist);
3671                                 if (tle)
3672                                 {
3673                                         pk_datatype = em->em_datatype;
3674                                         break;          /* found expr already in tlist */
3675                                 }
3676                         }
3677
3678                         if (!tle)
3679                         {
3680                                 /*
3681                                  * No matching tlist item; look for a computable expression.
3682                                  * Note that we treat Aggrefs as if they were variables; this
3683                                  * is necessary when attempting to sort the output from an Agg
3684                                  * node for use in a WindowFunc (since grouping_planner will
3685                                  * have treated the Aggrefs as variables, too).
3686                                  */
3687                                 Expr       *sortexpr = NULL;
3688
3689                                 foreach(j, ec->ec_members)
3690                                 {
3691                                         EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
3692                                         List       *exprvars;
3693                                         ListCell   *k;
3694
3695                                         if (em->em_is_const)
3696                                                 continue;
3697                                         sortexpr = em->em_expr;
3698                                         exprvars = pull_var_clause((Node *) sortexpr,
3699                                                                                            PVC_INCLUDE_AGGREGATES,
3700                                                                                            PVC_INCLUDE_PLACEHOLDERS);
3701                                         foreach(k, exprvars)
3702                                         {
3703                                                 if (!tlist_member_ignore_relabel(lfirst(k), tlist))
3704                                                         break;
3705                                         }
3706                                         list_free(exprvars);
3707                                         if (!k)
3708                                         {
3709                                                 pk_datatype = em->em_datatype;
3710                                                 break;  /* found usable expression */
3711                                         }
3712                                 }
3713                                 if (!j)
3714                                         elog(ERROR, "could not find pathkey item to sort");
3715
3716                                 /*
3717                                  * Do we need to insert a Result node?
3718                                  */
3719                                 if (!adjust_tlist_in_place &&
3720                                         !is_projection_capable_plan(lefttree))
3721                                 {
3722                                         /* copy needed so we don't modify input's tlist below */
3723                                         tlist = copyObject(tlist);
3724                                         lefttree = (Plan *) make_result(root, tlist, NULL,
3725                                                                                                         lefttree);
3726                                 }
3727
3728                                 /* Don't bother testing is_projection_capable_plan again */
3729                                 adjust_tlist_in_place = true;
3730
3731                                 /*
3732                                  * Add resjunk entry to input's tlist
3733                                  */
3734                                 tle = makeTargetEntry(sortexpr,
3735                                                                           list_length(tlist) + 1,
3736                                                                           NULL,
3737                                                                           true);
3738                                 tlist = lappend(tlist, tle);
3739                                 lefttree->targetlist = tlist;   /* just in case NIL before */
3740                         }
3741                 }
3742
3743                 /*
3744                  * Look up the correct sort operator from the PathKey's slightly
3745                  * abstracted representation.
3746                  */
3747                 sortop = get_opfamily_member(pathkey->pk_opfamily,
3748                                                                          pk_datatype,
3749                                                                          pk_datatype,
3750                                                                          pathkey->pk_strategy);
3751                 if (!OidIsValid(sortop))        /* should not happen */
3752                         elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
3753                                  pathkey->pk_strategy, pk_datatype, pk_datatype,
3754                                  pathkey->pk_opfamily);
3755
3756                 /*
3757                  * The column might already be selected as a sort key, if the pathkeys
3758                  * contain duplicate entries.  (This can happen in scenarios where
3759                  * multiple mergejoinable clauses mention the same var, for example.)
3760                  * So enter it only once in the sort arrays.
3761                  */
3762                 numsortkeys = add_sort_column(tle->resno,
3763                                                                           sortop,
3764                                                                           pathkey->pk_eclass->ec_collation,
3765                                                                           pathkey->pk_nulls_first,
3766                                                                           numsortkeys,
3767                                                                           sortColIdx, sortOperators,
3768                                                                           collations, nullsFirst);
3769         }
3770
3771         Assert(numsortkeys > 0);
3772
3773         /* Return results */
3774         *p_numsortkeys = numsortkeys;
3775         *p_sortColIdx = sortColIdx;
3776         *p_sortOperators = sortOperators;
3777         *p_collations = collations;
3778         *p_nullsFirst = nullsFirst;
3779
3780         return lefttree;
3781 }
3782
3783 /*
3784  * make_sort_from_pathkeys
3785  *        Create sort plan to sort according to given pathkeys
3786  *
3787  *        'lefttree' is the node which yields input tuples
3788  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
3789  *        'limit_tuples' is the bound on the number of output tuples;
3790  *                              -1 if no bound
3791  */
3792 Sort *
3793 make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
3794                                                 double limit_tuples)
3795 {
3796         int                     numsortkeys;
3797         AttrNumber *sortColIdx;
3798         Oid                *sortOperators;
3799         Oid                *collations;
3800         bool       *nullsFirst;
3801
3802         /* Compute sort column info, and adjust lefttree as needed */
3803         lefttree = prepare_sort_from_pathkeys(root, lefttree, pathkeys,
3804                                                                                   false,
3805                                                                                   &numsortkeys,
3806                                                                                   &sortColIdx,
3807                                                                                   &sortOperators,
3808                                                                                   &collations,
3809                                                                                   &nullsFirst);
3810
3811         /* Now build the Sort node */
3812         return make_sort(root, lefttree, numsortkeys,
3813                                          sortColIdx, sortOperators, collations,
3814                                          nullsFirst, limit_tuples);
3815 }
3816
3817 /*
3818  * make_sort_from_sortclauses
3819  *        Create sort plan to sort according to given sortclauses
3820  *
3821  *        'sortcls' is a list of SortGroupClauses
3822  *        'lefttree' is the node which yields input tuples
3823  */
3824 Sort *
3825 make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
3826 {
3827         List       *sub_tlist = lefttree->targetlist;
3828         ListCell   *l;
3829         int                     numsortkeys;
3830         AttrNumber *sortColIdx;
3831         Oid                *sortOperators;
3832         Oid                *collations;
3833         bool       *nullsFirst;
3834
3835         /*
3836          * We will need at most list_length(sortcls) sort columns; possibly less
3837          */
3838         numsortkeys = list_length(sortcls);
3839         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3840         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3841         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3842         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3843
3844         numsortkeys = 0;
3845
3846         foreach(l, sortcls)
3847         {
3848                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
3849                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
3850
3851                 /*
3852                  * Check for the possibility of duplicate order-by clauses --- the
3853                  * parser should have removed 'em, but no point in sorting
3854                  * redundantly.
3855                  */
3856                 numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
3857                                                                           exprCollation((Node *) tle->expr),
3858                                                                           sortcl->nulls_first,
3859                                                                           numsortkeys,
3860                                                                           sortColIdx, sortOperators,
3861                                                                           collations, nullsFirst);
3862         }
3863
3864         Assert(numsortkeys > 0);
3865
3866         return make_sort(root, lefttree, numsortkeys,
3867                                          sortColIdx, sortOperators, collations,
3868                                          nullsFirst, -1.0);
3869 }
3870
3871 /*
3872  * make_sort_from_groupcols
3873  *        Create sort plan to sort based on grouping columns
3874  *
3875  * 'groupcls' is the list of SortGroupClauses
3876  * 'grpColIdx' gives the column numbers to use
3877  *
3878  * This might look like it could be merged with make_sort_from_sortclauses,
3879  * but presently we *must* use the grpColIdx[] array to locate sort columns,
3880  * because the child plan's tlist is not marked with ressortgroupref info
3881  * appropriate to the grouping node.  So, only the sort ordering info
3882  * is used from the SortGroupClause entries.
3883  */
3884 Sort *
3885 make_sort_from_groupcols(PlannerInfo *root,
3886                                                  List *groupcls,
3887                                                  AttrNumber *grpColIdx,
3888                                                  Plan *lefttree)
3889 {
3890         List       *sub_tlist = lefttree->targetlist;
3891         int                     grpno = 0;
3892         ListCell   *l;
3893         int                     numsortkeys;
3894         AttrNumber *sortColIdx;
3895         Oid                *sortOperators;
3896         Oid                *collations;
3897         bool       *nullsFirst;
3898
3899         /*
3900          * We will need at most list_length(groupcls) sort columns; possibly less
3901          */
3902         numsortkeys = list_length(groupcls);
3903         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3904         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3905         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3906         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3907
3908         numsortkeys = 0;
3909
3910         foreach(l, groupcls)
3911         {
3912                 SortGroupClause *grpcl = (SortGroupClause *) lfirst(l);
3913                 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
3914
3915                 /*
3916                  * Check for the possibility of duplicate group-by clauses --- the
3917                  * parser should have removed 'em, but no point in sorting
3918                  * redundantly.
3919                  */
3920                 numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
3921                                                                           exprCollation((Node *) tle->expr),
3922                                                                           grpcl->nulls_first,
3923                                                                           numsortkeys,
3924                                                                           sortColIdx, sortOperators,
3925                                                                           collations, nullsFirst);
3926                 grpno++;
3927         }
3928
3929         Assert(numsortkeys > 0);
3930
3931         return make_sort(root, lefttree, numsortkeys,
3932                                          sortColIdx, sortOperators, collations,
3933                                          nullsFirst, -1.0);
3934 }
3935
3936 static Material *
3937 make_material(Plan *lefttree)
3938 {
3939         Material   *node = makeNode(Material);
3940         Plan       *plan = &node->plan;
3941
3942         /* cost should be inserted by caller */
3943         plan->targetlist = lefttree->targetlist;
3944         plan->qual = NIL;
3945         plan->lefttree = lefttree;
3946         plan->righttree = NULL;
3947
3948         return node;
3949 }
3950
3951 /*
3952  * materialize_finished_plan: stick a Material node atop a completed plan
3953  *
3954  * There are a couple of places where we want to attach a Material node
3955  * after completion of subquery_planner().      This currently requires hackery.
3956  * Since subquery_planner has already run SS_finalize_plan on the subplan
3957  * tree, we have to kluge up parameter lists for the Material node.
3958  * Possibly this could be fixed by postponing SS_finalize_plan processing
3959  * until setrefs.c is run?
3960  */
3961 Plan *
3962 materialize_finished_plan(Plan *subplan)
3963 {
3964         Plan       *matplan;
3965         Path            matpath;                /* dummy for result of cost_material */
3966
3967         matplan = (Plan *) make_material(subplan);
3968
3969         /* Set cost data */
3970         cost_material(&matpath,
3971                                   subplan->startup_cost,
3972                                   subplan->total_cost,
3973                                   subplan->plan_rows,
3974                                   subplan->plan_width);
3975         matplan->startup_cost = matpath.startup_cost;
3976         matplan->total_cost = matpath.total_cost;
3977         matplan->plan_rows = subplan->plan_rows;
3978         matplan->plan_width = subplan->plan_width;
3979
3980         /* parameter kluge --- see comments above */
3981         matplan->extParam = bms_copy(subplan->extParam);
3982         matplan->allParam = bms_copy(subplan->allParam);
3983
3984         return matplan;
3985 }
3986
3987 Agg *
3988 make_agg(PlannerInfo *root, List *tlist, List *qual,
3989                  AggStrategy aggstrategy, const AggClauseCosts *aggcosts,
3990                  int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
3991                  long numGroups,
3992                  Plan *lefttree)
3993 {
3994         Agg                *node = makeNode(Agg);
3995         Plan       *plan = &node->plan;
3996         Path            agg_path;               /* dummy for result of cost_agg */
3997         QualCost        qual_cost;
3998
3999         node->aggstrategy = aggstrategy;
4000         node->numCols = numGroupCols;
4001         node->grpColIdx = grpColIdx;
4002         node->grpOperators = grpOperators;
4003         node->numGroups = numGroups;
4004
4005         copy_plan_costsize(plan, lefttree); /* only care about copying size */
4006         cost_agg(&agg_path, root,
4007                          aggstrategy, aggcosts,
4008                          numGroupCols, numGroups,
4009                          lefttree->startup_cost,
4010                          lefttree->total_cost,
4011                          lefttree->plan_rows);
4012         plan->startup_cost = agg_path.startup_cost;
4013         plan->total_cost = agg_path.total_cost;
4014
4015         /*
4016          * We will produce a single output tuple if not grouping, and a tuple per
4017          * group otherwise.
4018          */
4019         if (aggstrategy == AGG_PLAIN)
4020                 plan->plan_rows = 1;
4021         else
4022                 plan->plan_rows = numGroups;
4023
4024         /*
4025          * We also need to account for the cost of evaluation of the qual (ie, the
4026          * HAVING clause) and the tlist.  Note that cost_qual_eval doesn't charge
4027          * anything for Aggref nodes; this is okay since they are really
4028          * comparable to Vars.
4029          *
4030          * See notes in grouping_planner about why only make_agg, make_windowagg
4031          * and make_group worry about tlist eval cost.
4032          */
4033         if (qual)
4034         {
4035                 cost_qual_eval(&qual_cost, qual, root);
4036                 plan->startup_cost += qual_cost.startup;
4037                 plan->total_cost += qual_cost.startup;
4038                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4039         }
4040         cost_qual_eval(&qual_cost, tlist, root);
4041         plan->startup_cost += qual_cost.startup;
4042         plan->total_cost += qual_cost.startup;
4043         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4044
4045         plan->qual = qual;
4046         plan->targetlist = tlist;
4047         plan->lefttree = lefttree;
4048         plan->righttree = NULL;
4049
4050         return node;
4051 }
4052
4053 WindowAgg *
4054 make_windowagg(PlannerInfo *root, List *tlist,
4055                            List *windowFuncs, Index winref,
4056                            int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
4057                            int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators,
4058                            int frameOptions, Node *startOffset, Node *endOffset,
4059                            Plan *lefttree)
4060 {
4061         WindowAgg  *node = makeNode(WindowAgg);
4062         Plan       *plan = &node->plan;
4063         Path            windowagg_path; /* dummy for result of cost_windowagg */
4064         QualCost        qual_cost;
4065
4066         node->winref = winref;
4067         node->partNumCols = partNumCols;
4068         node->partColIdx = partColIdx;
4069         node->partOperators = partOperators;
4070         node->ordNumCols = ordNumCols;
4071         node->ordColIdx = ordColIdx;
4072         node->ordOperators = ordOperators;
4073         node->frameOptions = frameOptions;
4074         node->startOffset = startOffset;
4075         node->endOffset = endOffset;
4076
4077         copy_plan_costsize(plan, lefttree); /* only care about copying size */
4078         cost_windowagg(&windowagg_path, root,
4079                                    windowFuncs, partNumCols, ordNumCols,
4080                                    lefttree->startup_cost,
4081                                    lefttree->total_cost,
4082                                    lefttree->plan_rows);
4083         plan->startup_cost = windowagg_path.startup_cost;
4084         plan->total_cost = windowagg_path.total_cost;
4085
4086         /*
4087          * We also need to account for the cost of evaluation of the tlist.
4088          *
4089          * See notes in grouping_planner about why only make_agg, make_windowagg
4090          * and make_group worry about tlist eval cost.
4091          */
4092         cost_qual_eval(&qual_cost, tlist, root);
4093         plan->startup_cost += qual_cost.startup;
4094         plan->total_cost += qual_cost.startup;
4095         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4096
4097         plan->targetlist = tlist;
4098         plan->lefttree = lefttree;
4099         plan->righttree = NULL;
4100         /* WindowAgg nodes never have a qual clause */
4101         plan->qual = NIL;
4102
4103         return node;
4104 }
4105
4106 Group *
4107 make_group(PlannerInfo *root,
4108                    List *tlist,
4109                    List *qual,
4110                    int numGroupCols,
4111                    AttrNumber *grpColIdx,
4112                    Oid *grpOperators,
4113                    double numGroups,
4114                    Plan *lefttree)
4115 {
4116         Group      *node = makeNode(Group);
4117         Plan       *plan = &node->plan;
4118         Path            group_path;             /* dummy for result of cost_group */
4119         QualCost        qual_cost;
4120
4121         node->numCols = numGroupCols;
4122         node->grpColIdx = grpColIdx;
4123         node->grpOperators = grpOperators;
4124
4125         copy_plan_costsize(plan, lefttree); /* only care about copying size */
4126         cost_group(&group_path, root,
4127                            numGroupCols, numGroups,
4128                            lefttree->startup_cost,
4129                            lefttree->total_cost,
4130                            lefttree->plan_rows);
4131         plan->startup_cost = group_path.startup_cost;
4132         plan->total_cost = group_path.total_cost;
4133
4134         /* One output tuple per estimated result group */
4135         plan->plan_rows = numGroups;
4136
4137         /*
4138          * We also need to account for the cost of evaluation of the qual (ie, the
4139          * HAVING clause) and the tlist.
4140          *
4141          * XXX this double-counts the cost of evaluation of any expressions used
4142          * for grouping, since in reality those will have been evaluated at a
4143          * lower plan level and will only be copied by the Group node. Worth
4144          * fixing?
4145          *
4146          * See notes in grouping_planner about why only make_agg, make_windowagg
4147          * and make_group worry about tlist eval cost.
4148          */
4149         if (qual)
4150         {
4151                 cost_qual_eval(&qual_cost, qual, root);
4152                 plan->startup_cost += qual_cost.startup;
4153                 plan->total_cost += qual_cost.startup;
4154                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4155         }
4156         cost_qual_eval(&qual_cost, tlist, root);
4157         plan->startup_cost += qual_cost.startup;
4158         plan->total_cost += qual_cost.startup;
4159         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4160
4161         plan->qual = qual;
4162         plan->targetlist = tlist;
4163         plan->lefttree = lefttree;
4164         plan->righttree = NULL;
4165
4166         return node;
4167 }
4168
4169 /*
4170  * distinctList is a list of SortGroupClauses, identifying the targetlist items
4171  * that should be considered by the Unique filter.      The input path must
4172  * already be sorted accordingly.
4173  */
4174 Unique *
4175 make_unique(Plan *lefttree, List *distinctList)
4176 {
4177         Unique     *node = makeNode(Unique);
4178         Plan       *plan = &node->plan;
4179         int                     numCols = list_length(distinctList);
4180         int                     keyno = 0;
4181         AttrNumber *uniqColIdx;
4182         Oid                *uniqOperators;
4183         ListCell   *slitem;
4184
4185         copy_plan_costsize(plan, lefttree);
4186
4187         /*
4188          * Charge one cpu_operator_cost per comparison per input tuple. We assume
4189          * all columns get compared at most of the tuples.      (XXX probably this is
4190          * an overestimate.)
4191          */
4192         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
4193
4194         /*
4195          * plan->plan_rows is left as a copy of the input subplan's plan_rows; ie,
4196          * we assume the filter removes nothing.  The caller must alter this if he
4197          * has a better idea.
4198          */
4199
4200         plan->targetlist = lefttree->targetlist;
4201         plan->qual = NIL;
4202         plan->lefttree = lefttree;
4203         plan->righttree = NULL;
4204
4205         /*
4206          * convert SortGroupClause list into arrays of attr indexes and equality
4207          * operators, as wanted by executor
4208          */
4209         Assert(numCols > 0);
4210         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
4211         uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);
4212
4213         foreach(slitem, distinctList)
4214         {
4215                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
4216                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
4217
4218                 uniqColIdx[keyno] = tle->resno;
4219                 uniqOperators[keyno] = sortcl->eqop;
4220                 Assert(OidIsValid(uniqOperators[keyno]));
4221                 keyno++;
4222         }
4223
4224         node->numCols = numCols;
4225         node->uniqColIdx = uniqColIdx;
4226         node->uniqOperators = uniqOperators;
4227
4228         return node;
4229 }
4230
4231 /*
4232  * distinctList is a list of SortGroupClauses, identifying the targetlist
4233  * items that should be considered by the SetOp filter.  The input path must
4234  * already be sorted accordingly.
4235  */
4236 SetOp *
4237 make_setop(SetOpCmd cmd, SetOpStrategy strategy, Plan *lefttree,
4238                    List *distinctList, AttrNumber flagColIdx, int firstFlag,
4239                    long numGroups, double outputRows)
4240 {
4241         SetOp      *node = makeNode(SetOp);
4242         Plan       *plan = &node->plan;
4243         int                     numCols = list_length(distinctList);
4244         int                     keyno = 0;
4245         AttrNumber *dupColIdx;
4246         Oid                *dupOperators;
4247         ListCell   *slitem;
4248
4249         copy_plan_costsize(plan, lefttree);
4250         plan->plan_rows = outputRows;
4251
4252         /*
4253          * Charge one cpu_operator_cost per comparison per input tuple. We assume
4254          * all columns get compared at most of the tuples.
4255          */
4256         plan->total_cost += cpu_operator_cost * lefttree->plan_rows * numCols;
4257
4258         plan->targetlist = lefttree->targetlist;
4259         plan->qual = NIL;
4260         plan->lefttree = lefttree;
4261         plan->righttree = NULL;
4262
4263         /*
4264          * convert SortGroupClause list into arrays of attr indexes and equality
4265          * operators, as wanted by executor
4266          */
4267         Assert(numCols > 0);
4268         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
4269         dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
4270
4271         foreach(slitem, distinctList)
4272         {
4273                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
4274                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
4275
4276                 dupColIdx[keyno] = tle->resno;
4277                 dupOperators[keyno] = sortcl->eqop;
4278                 Assert(OidIsValid(dupOperators[keyno]));
4279                 keyno++;
4280         }
4281
4282         node->cmd = cmd;
4283         node->strategy = strategy;
4284         node->numCols = numCols;
4285         node->dupColIdx = dupColIdx;
4286         node->dupOperators = dupOperators;
4287         node->flagColIdx = flagColIdx;
4288         node->firstFlag = firstFlag;
4289         node->numGroups = numGroups;
4290
4291         return node;
4292 }
4293
4294 /*
4295  * make_lockrows
4296  *        Build a LockRows plan node
4297  */
4298 LockRows *
4299 make_lockrows(Plan *lefttree, List *rowMarks, int epqParam)
4300 {
4301         LockRows   *node = makeNode(LockRows);
4302         Plan       *plan = &node->plan;
4303
4304         copy_plan_costsize(plan, lefttree);
4305
4306         /* charge cpu_tuple_cost to reflect locking costs (underestimate?) */
4307         plan->total_cost += cpu_tuple_cost * plan->plan_rows;
4308
4309         plan->targetlist = lefttree->targetlist;
4310         plan->qual = NIL;
4311         plan->lefttree = lefttree;
4312         plan->righttree = NULL;
4313
4314         node->rowMarks = rowMarks;
4315         node->epqParam = epqParam;
4316
4317         return node;
4318 }
4319
4320 /*
4321  * Note: offset_est and count_est are passed in to save having to repeat
4322  * work already done to estimate the values of the limitOffset and limitCount
4323  * expressions.  Their values are as returned by preprocess_limit (0 means
4324  * "not relevant", -1 means "couldn't estimate").  Keep the code below in sync
4325  * with that function!
4326  */
4327 Limit *
4328 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount,
4329                    int64 offset_est, int64 count_est)
4330 {
4331         Limit      *node = makeNode(Limit);
4332         Plan       *plan = &node->plan;
4333
4334         copy_plan_costsize(plan, lefttree);
4335
4336         /*
4337          * Adjust the output rows count and costs according to the offset/limit.
4338          * This is only a cosmetic issue if we are at top level, but if we are
4339          * building a subquery then it's important to report correct info to the
4340          * outer planner.
4341          *
4342          * When the offset or count couldn't be estimated, use 10% of the
4343          * estimated number of rows emitted from the subplan.
4344          */
4345         if (offset_est != 0)
4346         {
4347                 double          offset_rows;
4348
4349                 if (offset_est > 0)
4350                         offset_rows = (double) offset_est;
4351                 else
4352                         offset_rows = clamp_row_est(lefttree->plan_rows * 0.10);
4353                 if (offset_rows > plan->plan_rows)
4354                         offset_rows = plan->plan_rows;
4355                 if (plan->plan_rows > 0)
4356                         plan->startup_cost +=
4357                                 (plan->total_cost - plan->startup_cost)
4358                                 * offset_rows / plan->plan_rows;
4359                 plan->plan_rows -= offset_rows;
4360                 if (plan->plan_rows < 1)
4361                         plan->plan_rows = 1;
4362         }
4363
4364         if (count_est != 0)
4365         {
4366                 double          count_rows;
4367
4368                 if (count_est > 0)
4369                         count_rows = (double) count_est;
4370                 else
4371                         count_rows = clamp_row_est(lefttree->plan_rows * 0.10);
4372                 if (count_rows > plan->plan_rows)
4373                         count_rows = plan->plan_rows;
4374                 if (plan->plan_rows > 0)
4375                         plan->total_cost = plan->startup_cost +
4376                                 (plan->total_cost - plan->startup_cost)
4377                                 * count_rows / plan->plan_rows;
4378                 plan->plan_rows = count_rows;
4379                 if (plan->plan_rows < 1)
4380                         plan->plan_rows = 1;
4381         }
4382
4383         plan->targetlist = lefttree->targetlist;
4384         plan->qual = NIL;
4385         plan->lefttree = lefttree;
4386         plan->righttree = NULL;
4387
4388         node->limitOffset = limitOffset;
4389         node->limitCount = limitCount;
4390
4391         return node;
4392 }
4393
4394 /*
4395  * make_result
4396  *        Build a Result plan node
4397  *
4398  * If we have a subplan, assume that any evaluation costs for the gating qual
4399  * were already factored into the subplan's startup cost, and just copy the
4400  * subplan cost.  If there's no subplan, we should include the qual eval
4401  * cost.  In either case, tlist eval cost is not to be included here.
4402  */
4403 Result *
4404 make_result(PlannerInfo *root,
4405                         List *tlist,
4406                         Node *resconstantqual,
4407                         Plan *subplan)
4408 {
4409         Result     *node = makeNode(Result);
4410         Plan       *plan = &node->plan;
4411
4412         if (subplan)
4413                 copy_plan_costsize(plan, subplan);
4414         else
4415         {
4416                 plan->startup_cost = 0;
4417                 plan->total_cost = cpu_tuple_cost;
4418                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
4419                 plan->plan_width = 0;   /* XXX is it worth being smarter? */
4420                 if (resconstantqual)
4421                 {
4422                         QualCost        qual_cost;
4423
4424                         cost_qual_eval(&qual_cost, (List *) resconstantqual, root);
4425                         /* resconstantqual is evaluated once at startup */
4426                         plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
4427                         plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
4428                 }
4429         }
4430
4431         plan->targetlist = tlist;
4432         plan->qual = NIL;
4433         plan->lefttree = subplan;
4434         plan->righttree = NULL;
4435         node->resconstantqual = resconstantqual;
4436
4437         return node;
4438 }
4439
4440 /*
4441  * make_modifytable
4442  *        Build a ModifyTable plan node
4443  *
4444  * Currently, we don't charge anything extra for the actual table modification
4445  * work, nor for the RETURNING expressions if any.      It would only be window
4446  * dressing, since these are always top-level nodes and there is no way for
4447  * the costs to change any higher-level planning choices.  But we might want
4448  * to make it look better sometime.
4449  */
4450 ModifyTable *
4451 make_modifytable(CmdType operation, bool canSetTag,
4452                                  List *resultRelations,
4453                                  List *subplans, List *returningLists,
4454                                  List *rowMarks, int epqParam)
4455 {
4456         ModifyTable *node = makeNode(ModifyTable);
4457         Plan       *plan = &node->plan;
4458         double          total_size;
4459         ListCell   *subnode;
4460
4461         Assert(list_length(resultRelations) == list_length(subplans));
4462         Assert(returningLists == NIL ||
4463                    list_length(resultRelations) == list_length(returningLists));
4464
4465         /*
4466          * Compute cost as sum of subplan costs.
4467          */
4468         plan->startup_cost = 0;
4469         plan->total_cost = 0;
4470         plan->plan_rows = 0;
4471         total_size = 0;
4472         foreach(subnode, subplans)
4473         {
4474                 Plan       *subplan = (Plan *) lfirst(subnode);
4475
4476                 if (subnode == list_head(subplans))             /* first node? */
4477                         plan->startup_cost = subplan->startup_cost;
4478                 plan->total_cost += subplan->total_cost;
4479                 plan->plan_rows += subplan->plan_rows;
4480                 total_size += subplan->plan_width * subplan->plan_rows;
4481         }
4482         if (plan->plan_rows > 0)
4483                 plan->plan_width = rint(total_size / plan->plan_rows);
4484         else
4485                 plan->plan_width = 0;
4486
4487         node->plan.lefttree = NULL;
4488         node->plan.righttree = NULL;
4489         node->plan.qual = NIL;
4490
4491         /*
4492          * Set up the visible plan targetlist as being the same as the first
4493          * RETURNING list.      This is for the use of EXPLAIN; the executor won't pay
4494          * any attention to the targetlist.
4495          */
4496         if (returningLists)
4497                 node->plan.targetlist = copyObject(linitial(returningLists));
4498         else
4499                 node->plan.targetlist = NIL;
4500
4501         node->operation = operation;
4502         node->canSetTag = canSetTag;
4503         node->resultRelations = resultRelations;
4504         node->resultRelIndex = -1;      /* will be set correctly in setrefs.c */
4505         node->plans = subplans;
4506         node->returningLists = returningLists;
4507         node->rowMarks = rowMarks;
4508         node->epqParam = epqParam;
4509
4510         return node;
4511 }
4512
4513 /*
4514  * is_projection_capable_plan
4515  *              Check whether a given Plan node is able to do projection.
4516  */
4517 bool
4518 is_projection_capable_plan(Plan *plan)
4519 {
4520         /* Most plan types can project, so just list the ones that can't */
4521         switch (nodeTag(plan))
4522         {
4523                 case T_Hash:
4524                 case T_Material:
4525                 case T_Sort:
4526                 case T_Unique:
4527                 case T_SetOp:
4528                 case T_LockRows:
4529                 case T_Limit:
4530                 case T_ModifyTable:
4531                 case T_Append:
4532                 case T_MergeAppend:
4533                 case T_RecursiveUnion:
4534                         return false;
4535                 default:
4536                         break;
4537         }
4538         return true;
4539 }