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

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