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