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