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