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