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