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-2005, 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.200 2005/10/13 00:06:46 tgl Exp $
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #include "postgres.h"
  18
  19 #include <limits.h>
  20
  21 #include "nodes/makefuncs.h"
  22 #include "nodes/nodeFuncs.h"
  23 #include "optimizer/clauses.h"
  24 #include "optimizer/cost.h"
  25 #include "optimizer/plancat.h"
  26 #include "optimizer/planmain.h"
  27 #include "optimizer/predtest.h"
  28 #include "optimizer/restrictinfo.h"
  29 #include "optimizer/tlist.h"
  30 #include "optimizer/var.h"
  31 #include "parser/parsetree.h"
  32 #include "parser/parse_clause.h"
  33 #include "parser/parse_expr.h"
  34 #include "utils/lsyscache.h"
  35 #include "utils/syscache.h"
  36
  37
  38 static Scan *create_scan_plan(PlannerInfo *root, Path *best_path);
  39 static List *build_relation_tlist(RelOptInfo *rel);
  40 static bool use_physical_tlist(RelOptInfo *rel);
  41 static void disuse_physical_tlist(Plan *plan, Path *path);
  42 static Join *create_join_plan(PlannerInfo *root, JoinPath *best_path);
  43 static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
  44 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
  45 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
  46 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
  47 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
  48                                         List *tlist, List *scan_clauses);
  49 static IndexScan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
  50                                           List *tlist, List *scan_clauses,
  51                                           List **nonlossy_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 NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
  64                                          Plan *outer_plan, Plan *inner_plan);
  65 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
  66                                           Plan *outer_plan, Plan *inner_plan);
  67 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
  68                                          Plan *outer_plan, Plan *inner_plan);
  69 static void fix_indexqual_references(List *indexquals, IndexPath *index_path,
  70                                                  List **fixed_indexquals,
  71                                                  List **nonlossy_indexquals,
  72                                                  List **indexstrategy,
  73                                                  List **indexsubtype);
  74 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index,
  75                                                                   Oid *opclass);
  76 static List *get_switched_clauses(List *clauses, Relids outerrelids);
  77 static void copy_path_costsize(Plan *dest, Path *src);
  78 static void copy_plan_costsize(Plan *dest, Plan *src);
  79 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
  80 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
  81                            Oid indexid, List *indexqual, List *indexqualorig,
  82                            List *indexstrategy, List *indexsubtype,
  83                            ScanDirection indexscandir);
  84 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
  85                                                                                           List *indexqual,
  86                                                                                           List *indexqualorig,
  87                                                                                           List *indexstrategy,
  88                                                                                           List *indexsubtype);
  89 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
  90                                                                                         List *qpqual,
  91                                                                                         Plan *lefttree,
  92                                                                                         List *bitmapqualorig,
  93                                                                                         Index scanrelid);
  94 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
  95                          List *tideval);
  96 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
  97                                   Index scanrelid);
  98 static BitmapAnd *make_bitmap_and(List *bitmapplans);
  99 static BitmapOr *make_bitmap_or(List *bitmapplans);
 100 static NestLoop *make_nestloop(List *tlist,
 101                           List *joinclauses, List *otherclauses,
 102                           Plan *lefttree, Plan *righttree,
 103                           JoinType jointype);
 104 static HashJoin *make_hashjoin(List *tlist,
 105                           List *joinclauses, List *otherclauses,
 106                           List *hashclauses,
 107                           Plan *lefttree, Plan *righttree,
 108                           JoinType jointype);
 109 static Hash *make_hash(Plan *lefttree);
 110 static MergeJoin *make_mergejoin(List *tlist,
 111                            List *joinclauses, List *otherclauses,
 112                            List *mergeclauses,
 113                            Plan *lefttree, Plan *righttree,
 114                            JoinType jointype);
 115 static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
 116                   AttrNumber *sortColIdx, Oid *sortOperators);
 117 static Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
 118                                                 List *pathkeys);
 119
 120
 121 /*
 122  * create_plan
 123  *        Creates the access plan for a query by tracing backwards through the
 124  *        desired chain of pathnodes, starting at the node 'best_path'.  For
 125  *        every pathnode found:
 126  *        (1) Create a corresponding plan node containing appropriate id,
 127  *                target list, and qualification information.
 128  *        (2) Modify qual clauses of join nodes so that subplan attributes are
 129  *                referenced using relative values.
 130  *        (3) Target lists are not modified, but will be in setrefs.c.
 131  *
 132  *        best_path is the best access path
 133  *
 134  *        Returns a Plan tree.
 135  */
 136 Plan *
 137 create_plan(PlannerInfo *root, Path *best_path)
 138 {
 139         Plan       *plan;
 140
 141         switch (best_path->pathtype)
 142         {
 143                 case T_SeqScan:
 144                 case T_IndexScan:
 145                 case T_BitmapHeapScan:
 146                 case T_TidScan:
 147                 case T_SubqueryScan:
 148                 case T_FunctionScan:
 149                         plan = (Plan *) create_scan_plan(root, best_path);
 150                         break;
 151                 case T_HashJoin:
 152                 case T_MergeJoin:
 153                 case T_NestLoop:
 154                         plan = (Plan *) create_join_plan(root,
 155                                                                                          (JoinPath *) best_path);
 156                         break;
 157                 case T_Append:
 158                         plan = (Plan *) create_append_plan(root,
 159                                                                                            (AppendPath *) best_path);
 160                         break;
 161                 case T_Result:
 162                         plan = (Plan *) create_result_plan(root,
 163                                                                                            (ResultPath *) best_path);
 164                         break;
 165                 case T_Material:
 166                         plan = (Plan *) create_material_plan(root,
 167                                                                                          (MaterialPath *) best_path);
 168                         break;
 169                 case T_Unique:
 170                         plan = (Plan *) create_unique_plan(root,
 171                                                                                            (UniquePath *) best_path);
 172                         break;
 173                 default:
 174                         elog(ERROR, "unrecognized node type: %d",
 175                                  (int) best_path->pathtype);
 176                         plan = NULL;            /* keep compiler quiet */
 177                         break;
 178         }
 179
 180         return plan;
 181 }
 182
 183 /*
 184  * create_scan_plan
 185  *       Create a scan plan for the parent relation of 'best_path'.
 186  *
 187  *       Returns a Plan node.
 188  */
 189 static Scan *
 190 create_scan_plan(PlannerInfo *root, Path *best_path)
 191 {
 192         RelOptInfo *rel = best_path->parent;
 193         List       *tlist;
 194         List       *scan_clauses;
 195         Scan       *plan;
 196
 197         /*
 198          * For table scans, rather than using the relation targetlist (which
 199          * is only those Vars actually needed by the query), we prefer to
 200          * generate a tlist containing all Vars in order.  This will allow the
 201          * executor to optimize away projection of the table tuples, if
 202          * possible.  (Note that planner.c may replace the tlist we generate
 203          * here, forcing projection to occur.)
 204          */
 205         if (use_physical_tlist(rel))
 206         {
 207                 tlist = build_physical_tlist(root, rel);
 208                 /* if fail because of dropped cols, use regular method */
 209                 if (tlist == NIL)
 210                         tlist = build_relation_tlist(rel);
 211         }
 212         else
 213                 tlist = build_relation_tlist(rel);
 214
 215         /*
 216          * Extract the relevant restriction clauses from the parent relation;
 217          * the executor must apply all these restrictions during the scan.
 218          */
 219         scan_clauses = rel->baserestrictinfo;
 220
 221         switch (best_path->pathtype)
 222         {
 223                 case T_SeqScan:
 224                         plan = (Scan *) create_seqscan_plan(root,
 225                                                                                                 best_path,
 226                                                                                                 tlist,
 227                                                                                                 scan_clauses);
 228                         break;
 229
 230                 case T_IndexScan:
 231                         plan = (Scan *) create_indexscan_plan(root,
 232                                                                                                   (IndexPath *) best_path,
 233                                                                                                   tlist,
 234                                                                                                   scan_clauses,
 235                                                                                                   NULL);
 236                         break;
 237
 238                 case T_BitmapHeapScan:
 239                         plan = (Scan *) create_bitmap_scan_plan(root,
 240                                                                                                         (BitmapHeapPath *) best_path,
 241                                                                                                         tlist,
 242                                                                                                         scan_clauses);
 243                         break;
 244
 245                 case T_TidScan:
 246                         plan = (Scan *) create_tidscan_plan(root,
 247                                                                                                 (TidPath *) best_path,
 248                                                                                                 tlist,
 249                                                                                                 scan_clauses);
 250                         break;
 251
 252                 case T_SubqueryScan:
 253                         plan = (Scan *) create_subqueryscan_plan(root,
 254                                                                                                          best_path,
 255                                                                                                          tlist,
 256                                                                                                          scan_clauses);
 257                         break;
 258
 259                 case T_FunctionScan:
 260                         plan = (Scan *) create_functionscan_plan(root,
 261                                                                                                          best_path,
 262                                                                                                          tlist,
 263                                                                                                          scan_clauses);
 264                         break;
 265
 266                 default:
 267                         elog(ERROR, "unrecognized node type: %d",
 268                                  (int) best_path->pathtype);
 269                         plan = NULL;            /* keep compiler quiet */
 270                         break;
 271         }
 272
 273         return plan;
 274 }
 275
 276 /*
 277  * Build a target list (ie, a list of TargetEntry) for a relation.
 278  */
 279 static List *
 280 build_relation_tlist(RelOptInfo *rel)
 281 {
 282         List       *tlist = NIL;
 283         int                     resno = 1;
 284         ListCell   *v;
 285
 286         foreach(v, rel->reltargetlist)
 287         {
 288                 /* Do we really need to copy here?      Not sure */
 289                 Var                *var = (Var *) copyObject(lfirst(v));
 290
 291                 tlist = lappend(tlist, makeTargetEntry((Expr *) var,
 292                                                                                            resno,
 293                                                                                            NULL,
 294                                                                                            false));
 295                 resno++;
 296         }
 297         return tlist;
 298 }
 299
 300 /*
 301  * use_physical_tlist
 302  *              Decide whether to use a tlist matching relation structure,
 303  *              rather than only those Vars actually referenced.
 304  */
 305 static bool
 306 use_physical_tlist(RelOptInfo *rel)
 307 {
 308         int                     i;
 309
 310         /*
 311          * OK for subquery and function scans; otherwise, can't do it for
 312          * anything except real relations.
 313          */
 314         if (rel->rtekind != RTE_RELATION)
 315         {
 316                 if (rel->rtekind == RTE_SUBQUERY)
 317                         return true;
 318                 if (rel->rtekind == RTE_FUNCTION)
 319                         return true;
 320                 return false;
 321         }
 322
 323         /*
 324          * Can't do it with inheritance cases either (mainly because Append
 325          * doesn't project).
 326          */
 327         if (rel->reloptkind != RELOPT_BASEREL)
 328                 return false;
 329
 330         /*
 331          * Can't do it if any system columns are requested, either.  (This
 332          * could possibly be fixed but would take some fragile assumptions in
 333          * setrefs.c, I think.)
 334          */
 335         for (i = rel->min_attr; i <= 0; i++)
 336         {
 337                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
 338                         return false;
 339         }
 340         return true;
 341 }
 342
 343 /*
 344  * disuse_physical_tlist
 345  *              Switch a plan node back to emitting only Vars actually referenced.
 346  *
 347  * If the plan node immediately above a scan would prefer to get only
 348  * needed Vars and not a physical tlist, it must call this routine to
 349  * undo the decision made by use_physical_tlist().      Currently, Hash, Sort,
 350  * and Material nodes want this, so they don't have to store useless columns.
 351  */
 352 static void
 353 disuse_physical_tlist(Plan *plan, Path *path)
 354 {
 355         /* Only need to undo it for path types handled by create_scan_plan() */
 356         switch (path->pathtype)
 357         {
 358                 case T_SeqScan:
 359                 case T_IndexScan:
 360                 case T_BitmapHeapScan:
 361                 case T_TidScan:
 362                 case T_SubqueryScan:
 363                 case T_FunctionScan:
 364                         plan->targetlist = build_relation_tlist(path->parent);
 365                         break;
 366                 default:
 367                         break;
 368         }
 369 }
 370
 371 /*
 372  * create_join_plan
 373  *        Create a join plan for 'best_path' and (recursively) plans for its
 374  *        inner and outer paths.
 375  *
 376  *        Returns a Plan node.
 377  */
 378 static Join *
 379 create_join_plan(PlannerInfo *root, JoinPath *best_path)
 380 {
 381         Plan       *outer_plan;
 382         Plan       *inner_plan;
 383         Join       *plan;
 384
 385         outer_plan = create_plan(root, best_path->outerjoinpath);
 386         inner_plan = create_plan(root, best_path->innerjoinpath);
 387
 388         switch (best_path->path.pathtype)
 389         {
 390                 case T_MergeJoin:
 391                         plan = (Join *) create_mergejoin_plan(root,
 392                                                                                                   (MergePath *) best_path,
 393                                                                                                   outer_plan,
 394                                                                                                   inner_plan);
 395                         break;
 396                 case T_HashJoin:
 397                         plan = (Join *) create_hashjoin_plan(root,
 398                                                                                                  (HashPath *) best_path,
 399                                                                                                  outer_plan,
 400                                                                                                  inner_plan);
 401                         break;
 402                 case T_NestLoop:
 403                         plan = (Join *) create_nestloop_plan(root,
 404                                                                                                  (NestPath *) best_path,
 405                                                                                                  outer_plan,
 406                                                                                                  inner_plan);
 407                         break;
 408                 default:
 409                         elog(ERROR, "unrecognized node type: %d",
 410                                  (int) best_path->path.pathtype);
 411                         plan = NULL;            /* keep compiler quiet */
 412                         break;
 413         }
 414
 415 #ifdef NOT_USED
 416
 417         /*
 418          * * Expensive function pullups may have pulled local predicates *
 419          * into this path node.  Put them in the qpqual of the plan node. *
 420          * JMH, 6/15/92
 421          */
 422         if (get_loc_restrictinfo(best_path) != NIL)
 423                 set_qpqual((Plan) plan,
 424                                    list_concat(get_qpqual((Plan) plan),
 425                                    get_actual_clauses(get_loc_restrictinfo(best_path))));
 426 #endif
 427
 428         return plan;
 429 }
 430
 431 /*
 432  * create_append_plan
 433  *        Create an Append plan for 'best_path' and (recursively) plans
 434  *        for its subpaths.
 435  *
 436  *        Returns a Plan node.
 437  */
 438 static Plan *
 439 create_append_plan(PlannerInfo *root, AppendPath *best_path)
 440 {
 441         Append     *plan;
 442         List       *tlist = build_relation_tlist(best_path->path.parent);
 443         List       *subplans = NIL;
 444         ListCell   *subpaths;
 445
 446         /*
 447          * It is possible for the subplans list to contain only one entry,
 448          * or even no entries.  Handle these cases specially.
 449          *
 450          * XXX ideally, if there's just one entry, we'd not bother to generate
 451          * an Append node but just return the single child.  At the moment this
 452          * does not work because the varno of the child scan plan won't match
 453          * the parent-rel Vars it'll be asked to emit.
 454          */
 455         if (best_path->subpaths == NIL)
 456         {
 457                 /* Generate a Result plan with constant-FALSE gating qual */
 458                 return (Plan *) make_result(tlist,
 459                                                                         (Node *) list_make1(makeBoolConst(false,
 460                                                                                                                                           false)),
 461                                                                         NULL);
 462         }
 463
 464         /* Normal case with multiple subpaths */
 465         foreach(subpaths, best_path->subpaths)
 466         {
 467                 Path       *subpath = (Path *) lfirst(subpaths);
 468
 469                 subplans = lappend(subplans, create_plan(root, subpath));
 470         }
 471
 472         plan = make_append(subplans, false, tlist);
 473
 474         return (Plan *) plan;
 475 }
 476
 477 /*
 478  * create_result_plan
 479  *        Create a Result plan for 'best_path' and (recursively) plans
 480  *        for its subpaths.
 481  *
 482  *        Returns a Plan node.
 483  */
 484 static Result *
 485 create_result_plan(PlannerInfo *root, ResultPath *best_path)
 486 {
 487         Result     *plan;
 488         List       *tlist;
 489         List       *constclauses;
 490         Plan       *subplan;
 491
 492         if (best_path->path.parent)
 493                 tlist = build_relation_tlist(best_path->path.parent);
 494         else
 495                 tlist = NIL;                    /* will be filled in later */
 496
 497         if (best_path->subpath)
 498                 subplan = create_plan(root, best_path->subpath);
 499         else
 500                 subplan = NULL;
 501
 502         constclauses = order_qual_clauses(root, best_path->constantqual);
 503
 504         plan = make_result(tlist, (Node *) constclauses, subplan);
 505
 506         return plan;
 507 }
 508
 509 /*
 510  * create_material_plan
 511  *        Create a Material plan for 'best_path' and (recursively) plans
 512  *        for its subpaths.
 513  *
 514  *        Returns a Plan node.
 515  */
 516 static Material *
 517 create_material_plan(PlannerInfo *root, MaterialPath *best_path)
 518 {
 519         Material   *plan;
 520         Plan       *subplan;
 521
 522         subplan = create_plan(root, best_path->subpath);
 523
 524         /* We don't want any excess columns in the materialized tuples */
 525         disuse_physical_tlist(subplan, best_path->subpath);
 526
 527         plan = make_material(subplan);
 528
 529         copy_path_costsize(&plan->plan, (Path *) best_path);
 530
 531         return plan;
 532 }
 533
 534 /*
 535  * create_unique_plan
 536  *        Create a Unique plan for 'best_path' and (recursively) plans
 537  *        for its subpaths.
 538  *
 539  *        Returns a Plan node.
 540  */
 541 static Plan *
 542 create_unique_plan(PlannerInfo *root, UniquePath *best_path)
 543 {
 544         Plan       *plan;
 545         Plan       *subplan;
 546         List       *uniq_exprs;
 547         List       *newtlist;
 548         int                     nextresno;
 549         bool            newitems;
 550         int                     numGroupCols;
 551         AttrNumber *groupColIdx;
 552         int                     groupColPos;
 553         ListCell   *l;
 554
 555         subplan = create_plan(root, best_path->subpath);
 556
 557         /* Done if we don't need to do any actual unique-ifying */
 558         if (best_path->umethod == UNIQUE_PATH_NOOP)
 559                 return subplan;
 560
 561         /*----------
 562          * As constructed, the subplan has a "flat" tlist containing just the
 563          * Vars needed here and at upper levels.  The values we are supposed
 564          * to unique-ify may be expressions in these variables.  We have to
 565          * add any such expressions to the subplan's tlist.
 566          *
 567          * The subplan may have a "physical" tlist if it is a simple scan plan.
 568          * This should be left as-is if we don't need to add any expressions;
 569          * but if we do have to add expressions, then a projection step will be
 570          * needed at runtime anyway, and so we may as well remove unneeded items.
 571          * Therefore newtlist starts from build_relation_tlist() not just a
 572          * copy of the subplan's tlist; and we don't install it into the subplan
 573          * unless stuff has to be added.
 574          *
 575          * To find the correct list of values to unique-ify, we look in the
 576          * information saved for IN expressions.  If this code is ever used in
 577          * other scenarios, some other way of finding what to unique-ify will
 578          * be needed.
 579          *----------
 580          */
 581         uniq_exprs = NIL;                       /* just to keep compiler quiet */
 582         foreach(l, root->in_info_list)
 583         {
 584                 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
 585
 586                 if (bms_equal(ininfo->righthand, best_path->path.parent->relids))
 587                 {
 588                         uniq_exprs = ininfo->sub_targetlist;
 589                         break;
 590                 }
 591         }
 592         if (l == NULL)                          /* fell out of loop? */
 593                 elog(ERROR, "could not find UniquePath in in_info_list");
 594
 595         /* initialize modified subplan tlist as just the "required" vars */
 596         newtlist = build_relation_tlist(best_path->path.parent);
 597         nextresno = list_length(newtlist) + 1;
 598         newitems = false;
 599
 600         foreach(l, uniq_exprs)
 601         {
 602                 Node       *uniqexpr = lfirst(l);
 603                 TargetEntry *tle;
 604
 605                 tle = tlist_member(uniqexpr, newtlist);
 606                 if (!tle)
 607                 {
 608                         tle = makeTargetEntry((Expr *) uniqexpr,
 609                                                                   nextresno,
 610                                                                   NULL,
 611                                                                   false);
 612                         newtlist = lappend(newtlist, tle);
 613                         nextresno++;
 614                         newitems = true;
 615                 }
 616         }
 617
 618         if (newitems)
 619         {
 620                 /*
 621                  * If the top plan node can't do projections, we need to add a
 622                  * Result node to help it along.
 623                  */
 624                 if (!is_projection_capable_plan(subplan))
 625                         subplan = (Plan *) make_result(newtlist, NULL, subplan);
 626                 else
 627                         subplan->targetlist = newtlist;
 628         }
 629
 630         /*
 631          * Build control information showing which subplan output columns are
 632          * to be examined by the grouping step.  Unfortunately we can't merge this
 633          * with the previous loop, since we didn't then know which version of the
 634          * subplan tlist we'd end up using.
 635          */
 636         newtlist = subplan->targetlist;
 637         numGroupCols = list_length(uniq_exprs);
 638         groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
 639         groupColPos = 0;
 640
 641         foreach(l, uniq_exprs)
 642         {
 643                 Node       *uniqexpr = lfirst(l);
 644                 TargetEntry *tle;
 645
 646                 tle = tlist_member(uniqexpr, newtlist);
 647                 if (!tle)                               /* shouldn't happen */
 648                         elog(ERROR, "failed to find unique expression in subplan tlist");
 649                 groupColIdx[groupColPos++] = tle->resno;
 650         }
 651
 652         if (best_path->umethod == UNIQUE_PATH_HASH)
 653         {
 654                 long            numGroups;
 655
 656                 numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
 657
 658                 /*
 659                  * Since the Agg node is going to project anyway, we can give it
 660                  * the minimum output tlist, without any stuff we might have added
 661                  * to the subplan tlist.
 662                  */
 663                 plan = (Plan *) make_agg(root,
 664                                                                  build_relation_tlist(best_path->path.parent),
 665                                                                  NIL,
 666                                                                  AGG_HASHED,
 667                                                                  numGroupCols,
 668                                                                  groupColIdx,
 669                                                                  numGroups,
 670                                                                  0,
 671                                                                  subplan);
 672         }
 673         else
 674         {
 675                 List       *sortList = NIL;
 676
 677                 for (groupColPos = 0; groupColPos < numGroupCols; groupColPos++)
 678                 {
 679                         TargetEntry *tle;
 680
 681                         tle = get_tle_by_resno(subplan->targetlist,
 682                                                                    groupColIdx[groupColPos]);
 683                         Assert(tle != NULL);
 684                         sortList = addTargetToSortList(NULL, tle,
 685                                                                                    sortList, subplan->targetlist,
 686                                                                                    SORTBY_ASC, NIL, false);
 687                 }
 688                 plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
 689                 plan = (Plan *) make_unique(plan, sortList);
 690         }
 691
 692         /* Adjust output size estimate (other fields should be OK already) */
 693         plan->plan_rows = best_path->rows;
 694
 695         return plan;
 696 }
 697
 698
 699 /*****************************************************************************
 700  *
 701  *      BASE-RELATION SCAN METHODS
 702  *
 703  *****************************************************************************/
 704
 705
 706 /*
 707  * create_seqscan_plan
 708  *       Returns a seqscan plan for the base relation scanned by 'best_path'
 709  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 710  */
 711 static SeqScan *
 712 create_seqscan_plan(PlannerInfo *root, Path *best_path,
 713                                         List *tlist, List *scan_clauses)
 714 {
 715         SeqScan    *scan_plan;
 716         Index           scan_relid = best_path->parent->relid;
 717
 718         /* it should be a base rel... */
 719         Assert(scan_relid > 0);
 720         Assert(best_path->parent->rtekind == RTE_RELATION);
 721
 722         /* Reduce RestrictInfo list to bare expressions */
 723         scan_clauses = get_actual_clauses(scan_clauses);
 724
 725         /* Sort clauses into best execution order */
 726         scan_clauses = order_qual_clauses(root, scan_clauses);
 727
 728         scan_plan = make_seqscan(tlist,
 729                                                          scan_clauses,
 730                                                          scan_relid);
 731
 732         copy_path_costsize(&scan_plan->plan, best_path);
 733
 734         return scan_plan;
 735 }
 736
 737 /*
 738  * create_indexscan_plan
 739  *        Returns an indexscan plan for the base relation scanned by 'best_path'
 740  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 741  *
 742  * The indexquals list of the path contains implicitly-ANDed qual conditions.
 743  * The list can be empty --- then no index restrictions will be applied during
 744  * the scan.
 745  *
 746  * If nonlossy_clauses isn't NULL, *nonlossy_clauses receives a list of the
 747  * nonlossy indexquals.
 748  */
 749 static IndexScan *
 750 create_indexscan_plan(PlannerInfo *root,
 751                                           IndexPath *best_path,
 752                                           List *tlist,
 753                                           List *scan_clauses,
 754                                           List **nonlossy_clauses)
 755 {
 756         List       *indexquals = best_path->indexquals;
 757         Index           baserelid = best_path->path.parent->relid;
 758         Oid                     indexoid = best_path->indexinfo->indexoid;
 759         List       *qpqual;
 760         List       *stripped_indexquals;
 761         List       *fixed_indexquals;
 762         List       *nonlossy_indexquals;
 763         List       *indexstrategy;
 764         List       *indexsubtype;
 765         ListCell   *l;
 766         IndexScan  *scan_plan;
 767
 768         /* it should be a base rel... */
 769         Assert(baserelid > 0);
 770         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 771
 772         /*
 773          * Build "stripped" indexquals structure (no RestrictInfos) to pass to
 774          * executor as indexqualorig
 775          */
 776         stripped_indexquals = get_actual_clauses(indexquals);
 777
 778         /*
 779          * The executor needs a copy with the indexkey on the left of each
 780          * clause and with index attr numbers substituted for table ones. This
 781          * pass also gets strategy info and looks for "lossy" operators.
 782          */
 783         fix_indexqual_references(indexquals, best_path,
 784                                                          &fixed_indexquals,
 785                                                          &nonlossy_indexquals,
 786                                                          &indexstrategy,
 787                                                          &indexsubtype);
 788
 789         /* pass back nonlossy quals if caller wants 'em */
 790         if (nonlossy_clauses)
 791                 *nonlossy_clauses = nonlossy_indexquals;
 792
 793         /*
 794          * If this is an innerjoin scan, the indexclauses will contain join
 795          * clauses that are not present in scan_clauses (since the passed-in
 796          * value is just the rel's baserestrictinfo list).  We must add these
 797          * clauses to scan_clauses to ensure they get checked.  In most cases
 798          * we will remove the join clauses again below, but if a join clause
 799          * contains a special operator, we need to make sure it gets into the
 800          * scan_clauses.
 801          *
 802          * Note: pointer comparison should be enough to determine RestrictInfo
 803          * matches.
 804          */
 805         if (best_path->isjoininner)
 806                 scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
 807
 808         /*
 809          * The qpqual list must contain all restrictions not automatically
 810          * handled by the index.  All the predicates in the indexquals will be
 811          * checked (either by the index itself, or by nodeIndexscan.c), but if
 812          * there are any "special" operators involved then they must be included
 813          * in qpqual.  Also, any lossy index operators must be rechecked in
 814          * the qpqual.  The upshot is that qpqual must contain scan_clauses
 815          * minus whatever appears in nonlossy_indexquals.
 816          *
 817          * In normal cases simple pointer equality checks will be enough to
 818          * spot duplicate RestrictInfos, so we try that first.  In some situations
 819          * (particularly with OR'd index conditions) we may have scan_clauses
 820          * that are not equal to, but are logically implied by, the index quals;
 821          * so we also try a predicate_implied_by() check to see if we can discard
 822          * quals that way.  (predicate_implied_by assumes its first input contains
 823          * only immutable functions, so we have to check that.)  We can also
 824          * discard quals that are implied by a partial index's predicate.
 825          *
 826          * While at it, we strip off the RestrictInfos to produce a list of
 827          * plain expressions.
 828          */
 829         qpqual = NIL;
 830         foreach(l, scan_clauses)
 831         {
 832                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 833
 834                 Assert(IsA(rinfo, RestrictInfo));
 835                 if (list_member_ptr(nonlossy_indexquals, rinfo))
 836                         continue;
 837                 if (!contain_mutable_functions((Node *) rinfo->clause))
 838                 {
 839                         List    *clausel = list_make1(rinfo->clause);
 840
 841                         if (predicate_implied_by(clausel, nonlossy_indexquals))
 842                                 continue;
 843                         if (predicate_implied_by(clausel, best_path->indexinfo->indpred))
 844                                 continue;
 845                 }
 846                 qpqual = lappend(qpqual, rinfo->clause);
 847         }
 848
 849         /* Sort clauses into best execution order */
 850         qpqual = order_qual_clauses(root, qpqual);
 851
 852         /* Finally ready to build the plan node */
 853         scan_plan = make_indexscan(tlist,
 854                                                            qpqual,
 855                                                            baserelid,
 856                                                            indexoid,
 857                                                            fixed_indexquals,
 858                                                            stripped_indexquals,
 859                                                            indexstrategy,
 860                                                            indexsubtype,
 861                                                            best_path->indexscandir);
 862
 863         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 864         /* use the indexscan-specific rows estimate, not the parent rel's */
 865         scan_plan->scan.plan.plan_rows = best_path->rows;
 866
 867         return scan_plan;
 868 }
 869
 870 /*
 871  * create_bitmap_scan_plan
 872  *        Returns a bitmap scan plan for the base relation scanned by 'best_path'
 873  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 874  */
 875 static BitmapHeapScan *
 876 create_bitmap_scan_plan(PlannerInfo *root,
 877                                                 BitmapHeapPath *best_path,
 878                                                 List *tlist,
 879                                                 List *scan_clauses)
 880 {
 881         Index           baserelid = best_path->path.parent->relid;
 882         Plan       *bitmapqualplan;
 883         List       *bitmapqualorig;
 884         List       *indexquals;
 885         List       *qpqual;
 886         ListCell   *l;
 887         BitmapHeapScan *scan_plan;
 888
 889         /* it should be a base rel... */
 890         Assert(baserelid > 0);
 891         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 892
 893         /* Process the bitmapqual tree into a Plan tree and qual lists */
 894         bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
 895                                                                                    &bitmapqualorig, &indexquals);
 896
 897         /* Reduce RestrictInfo list to bare expressions */
 898         scan_clauses = get_actual_clauses(scan_clauses);
 899
 900         /*
 901          * If this is a innerjoin scan, the indexclauses will contain join
 902          * clauses that are not present in scan_clauses (since the passed-in
 903          * value is just the rel's baserestrictinfo list).  We must add these
 904          * clauses to scan_clauses to ensure they get checked.  In most cases
 905          * we will remove the join clauses again below, but if a join clause
 906          * contains a special operator, we need to make sure it gets into the
 907          * scan_clauses.
 908          */
 909         if (best_path->isjoininner)
 910         {
 911                 scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
 912         }
 913
 914         /*
 915          * The qpqual list must contain all restrictions not automatically
 916          * handled by the index.  All the predicates in the indexquals will be
 917          * checked (either by the index itself, or by nodeBitmapHeapscan.c),
 918          * but if there are any "special" or lossy operators involved then they
 919          * must be added to qpqual.  The upshot is that qpquals must contain
 920          * scan_clauses minus whatever appears in indexquals.
 921          *
 922          * In normal cases simple equal() checks will be enough to spot duplicate
 923          * clauses, so we try that first.  In some situations (particularly with
 924          * OR'd index conditions) we may have scan_clauses that are not equal to,
 925          * but are logically implied by, the index quals; so we also try a
 926          * predicate_implied_by() check to see if we can discard quals that way.
 927          * (predicate_implied_by assumes its first input contains only immutable
 928          * functions, so we have to check that.)  We can also discard quals that
 929          * are implied by a partial index's predicate.
 930          *
 931          * XXX For the moment, we only consider partial index predicates in the
 932          * simple single-index-scan case.  Is it worth trying to be smart about
 933          * more complex cases?  Perhaps create_bitmap_subplan should be made to
 934          * include predicate info in what it constructs.
 935          */
 936         qpqual = NIL;
 937         foreach(l, scan_clauses)
 938         {
 939                 Node   *clause = (Node *) lfirst(l);
 940
 941                 if (list_member(indexquals, clause))
 942                         continue;
 943                 if (!contain_mutable_functions(clause))
 944                 {
 945                         List    *clausel = list_make1(clause);
 946
 947                         if (predicate_implied_by(clausel, indexquals))
 948                                 continue;
 949                         if (IsA(best_path->bitmapqual, IndexPath))
 950                         {
 951                                 IndexPath *ipath = (IndexPath *) best_path->bitmapqual;
 952
 953                                 if (predicate_implied_by(clausel, ipath->indexinfo->indpred))
 954                                         continue;
 955                         }
 956                 }
 957                 qpqual = lappend(qpqual, clause);
 958         }
 959
 960         /* Sort clauses into best execution order */
 961         qpqual = order_qual_clauses(root, qpqual);
 962
 963         /*
 964          * When dealing with special or lossy operators, we will at this point
 965          * have duplicate clauses in qpqual and bitmapqualorig.  We may as well
 966          * drop 'em from bitmapqualorig, since there's no point in making the
 967          * tests twice.
 968          */
 969         bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
 970
 971         /* Finally ready to build the plan node */
 972         scan_plan = make_bitmap_heapscan(tlist,
 973                                                                          qpqual,
 974                                                                          bitmapqualplan,
 975                                                                          bitmapqualorig,
 976                                                                          baserelid);
 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  * Given a bitmapqual tree, generate the Plan tree that implements it
 987  *
 988  * As byproducts, we also return in *qual and *indexqual the qual lists
 989  * (in implicit-AND form, without RestrictInfos) describing the original index
 990  * conditions and the generated indexqual conditions.  The latter is made to
 991  * exclude lossy index operators.
 992  *
 993  * Note: if you find yourself changing this, you probably need to change
 994  * make_restrictinfo_from_bitmapqual too.
 995  */
 996 static Plan *
 997 create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
 998                                           List **qual, List **indexqual)
 999 {
1000         Plan       *plan;
1001
1002         if (IsA(bitmapqual, BitmapAndPath))
1003         {
1004                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
1005                 List       *subplans = NIL;
1006                 List       *subquals = NIL;
1007                 List       *subindexquals = NIL;
1008                 ListCell   *l;
1009
1010                 /*
1011                  * There may well be redundant quals among the subplans, since a
1012                  * top-level WHERE qual might have gotten used to form several
1013                  * different index quals.  We don't try exceedingly hard to
1014                  * eliminate redundancies, but we do eliminate obvious duplicates
1015                  * by using list_concat_unique.
1016                  */
1017                 foreach(l, apath->bitmapquals)
1018                 {
1019                         Plan   *subplan;
1020                         List   *subqual;
1021                         List   *subindexqual;
1022
1023                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1024                                                                                         &subqual, &subindexqual);
1025                         subplans = lappend(subplans, subplan);
1026                         subquals = list_concat_unique(subquals, subqual);
1027                         subindexquals = list_concat_unique(subindexquals, subindexqual);
1028                 }
1029                 plan = (Plan *) make_bitmap_and(subplans);
1030                 plan->startup_cost = apath->path.startup_cost;
1031                 plan->total_cost = apath->path.total_cost;
1032                 plan->plan_rows =
1033                         clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
1034                 plan->plan_width = 0;   /* meaningless */
1035                 *qual = subquals;
1036                 *indexqual = subindexquals;
1037         }
1038         else if (IsA(bitmapqual, BitmapOrPath))
1039         {
1040                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
1041                 List       *subplans = NIL;
1042                 List       *subquals = NIL;
1043                 List       *subindexquals = NIL;
1044                 bool            const_true_subqual = false;
1045                 bool            const_true_subindexqual = false;
1046                 ListCell   *l;
1047
1048                 /*
1049                  * Here, we only detect qual-free subplans.  A qual-free subplan would
1050                  * cause us to generate "... OR true ..."  which we may as well reduce
1051                  * to just "true".  We do not try to eliminate redundant subclauses
1052                  * because (a) it's not as likely as in the AND case, and (b) we might
1053                  * well be working with hundreds or even thousands of OR conditions,
1054                  * perhaps from a long IN list.  The performance of list_append_unique
1055                  * would be unacceptable.
1056                  */
1057                 foreach(l, opath->bitmapquals)
1058                 {
1059                         Plan   *subplan;
1060                         List   *subqual;
1061                         List   *subindexqual;
1062
1063                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1064                                                                                         &subqual, &subindexqual);
1065                         subplans = lappend(subplans, subplan);
1066                         if (subqual == NIL)
1067                                 const_true_subqual = true;
1068                         else if (!const_true_subqual)
1069                                 subquals = lappend(subquals,
1070                                                                    make_ands_explicit(subqual));
1071                         if (subindexqual == NIL)
1072                                 const_true_subindexqual = true;
1073                         else if (!const_true_subindexqual)
1074                                 subindexquals = lappend(subindexquals,
1075                                                                                 make_ands_explicit(subindexqual));
1076                 }
1077                 plan = (Plan *) make_bitmap_or(subplans);
1078                 plan->startup_cost = opath->path.startup_cost;
1079                 plan->total_cost = opath->path.total_cost;
1080                 plan->plan_rows =
1081                         clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
1082                 plan->plan_width = 0;   /* meaningless */
1083                 /*
1084                  * If there were constant-TRUE subquals, the OR reduces to constant
1085                  * TRUE.  Also, avoid generating one-element ORs, which could happen
1086                  * due to redundancy elimination.
1087                  */
1088                 if (const_true_subqual)
1089                         *qual = NIL;
1090                 else if (list_length(subquals) <= 1)
1091                         *qual = subquals;
1092                 else
1093                         *qual = list_make1(make_orclause(subquals));
1094                 if (const_true_subindexqual)
1095                         *indexqual = NIL;
1096                 else if (list_length(subindexquals) <= 1)
1097                         *indexqual = subindexquals;
1098                 else
1099                         *indexqual = list_make1(make_orclause(subindexquals));
1100         }
1101         else if (IsA(bitmapqual, IndexPath))
1102         {
1103                 IndexPath *ipath = (IndexPath *) bitmapqual;
1104                 IndexScan *iscan;
1105                 List   *nonlossy_clauses;
1106
1107                 /* Use the regular indexscan plan build machinery... */
1108                 iscan = create_indexscan_plan(root, ipath, NIL, NIL,
1109                                                                           &nonlossy_clauses);
1110                 /* then convert to a bitmap indexscan */
1111                 plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
1112                                                                                           iscan->indexid,
1113                                                                                           iscan->indexqual,
1114                                                                                           iscan->indexqualorig,
1115                                                                                           iscan->indexstrategy,
1116                                                                                           iscan->indexsubtype);
1117                 plan->startup_cost = 0.0;
1118                 plan->total_cost = ipath->indextotalcost;
1119                 plan->plan_rows =
1120                         clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
1121                 plan->plan_width = 0;   /* meaningless */
1122                 *qual = get_actual_clauses(ipath->indexclauses);
1123                 *indexqual = get_actual_clauses(nonlossy_clauses);
1124         }
1125         else
1126         {
1127                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
1128                 plan = NULL;                    /* keep compiler quiet */
1129         }
1130
1131         return plan;
1132 }
1133
1134 /*
1135  * create_tidscan_plan
1136  *       Returns a tidscan plan for the base relation scanned by 'best_path'
1137  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1138  */
1139 static TidScan *
1140 create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
1141                                         List *tlist, List *scan_clauses)
1142 {
1143         TidScan    *scan_plan;
1144         Index           scan_relid = best_path->path.parent->relid;
1145
1146         /* it should be a base rel... */
1147         Assert(scan_relid > 0);
1148         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1149
1150         /* Reduce RestrictInfo list to bare expressions */
1151         scan_clauses = get_actual_clauses(scan_clauses);
1152
1153         /* Sort clauses into best execution order */
1154         scan_clauses = order_qual_clauses(root, scan_clauses);
1155
1156         scan_plan = make_tidscan(tlist,
1157                                                          scan_clauses,
1158                                                          scan_relid,
1159                                                          best_path->tideval);
1160
1161         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1162
1163         return scan_plan;
1164 }
1165
1166 /*
1167  * create_subqueryscan_plan
1168  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
1169  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1170  */
1171 static SubqueryScan *
1172 create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
1173                                                  List *tlist, List *scan_clauses)
1174 {
1175         SubqueryScan *scan_plan;
1176         Index           scan_relid = best_path->parent->relid;
1177
1178         /* it should be a subquery base rel... */
1179         Assert(scan_relid > 0);
1180         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
1181
1182         /* Reduce RestrictInfo list to bare expressions */
1183         scan_clauses = get_actual_clauses(scan_clauses);
1184
1185         /* Sort clauses into best execution order */
1186         scan_clauses = order_qual_clauses(root, scan_clauses);
1187
1188         scan_plan = make_subqueryscan(tlist,
1189                                                                   scan_clauses,
1190                                                                   scan_relid,
1191                                                                   best_path->parent->subplan);
1192
1193         copy_path_costsize(&scan_plan->scan.plan, best_path);
1194
1195         return scan_plan;
1196 }
1197
1198 /*
1199  * create_functionscan_plan
1200  *       Returns a functionscan plan for the base relation scanned by 'best_path'
1201  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1202  */
1203 static FunctionScan *
1204 create_functionscan_plan(PlannerInfo *root, Path *best_path,
1205                                                  List *tlist, List *scan_clauses)
1206 {
1207         FunctionScan *scan_plan;
1208         Index           scan_relid = best_path->parent->relid;
1209
1210         /* it should be a function base rel... */
1211         Assert(scan_relid > 0);
1212         Assert(best_path->parent->rtekind == RTE_FUNCTION);
1213
1214         /* Reduce RestrictInfo list to bare expressions */
1215         scan_clauses = get_actual_clauses(scan_clauses);
1216
1217         /* Sort clauses into best execution order */
1218         scan_clauses = order_qual_clauses(root, scan_clauses);
1219
1220         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid);
1221
1222         copy_path_costsize(&scan_plan->scan.plan, best_path);
1223
1224         return scan_plan;
1225 }
1226
1227 /*****************************************************************************
1228  *
1229  *      JOIN METHODS
1230  *
1231  *****************************************************************************/
1232
1233 static NestLoop *
1234 create_nestloop_plan(PlannerInfo *root,
1235                                          NestPath *best_path,
1236                                          Plan *outer_plan,
1237                                          Plan *inner_plan)
1238 {
1239         List       *tlist = build_relation_tlist(best_path->path.parent);
1240         List       *joinrestrictclauses = best_path->joinrestrictinfo;
1241         List       *joinclauses;
1242         List       *otherclauses;
1243         NestLoop   *join_plan;
1244
1245         if (IsA(best_path->innerjoinpath, IndexPath))
1246         {
1247                 /*
1248                  * An index is being used to reduce the number of tuples scanned
1249                  * in the inner relation.  If there are join clauses being used
1250                  * with the index, we may remove those join clauses from the list
1251                  * of clauses that have to be checked as qpquals at the join node.
1252                  *
1253                  * We can also remove any join clauses that are redundant with those
1254                  * being used in the index scan; prior redundancy checks will not
1255                  * have caught this case because the join clauses would never have
1256                  * been put in the same joininfo list.
1257                  *
1258                  * We can skip this if the index path is an ordinary indexpath and
1259                  * not a special innerjoin path.
1260                  */
1261                 IndexPath  *innerpath = (IndexPath *) best_path->innerjoinpath;
1262
1263                 if (innerpath->isjoininner)
1264                 {
1265                         joinrestrictclauses =
1266                                 select_nonredundant_join_clauses(root,
1267                                                                                                  joinrestrictclauses,
1268                                                                                                  innerpath->indexclauses,
1269                                                                                                  IS_OUTER_JOIN(best_path->jointype));
1270                 }
1271         }
1272         else if (IsA(best_path->innerjoinpath, BitmapHeapPath))
1273         {
1274                 /*
1275                  * Same deal for bitmapped index scans.
1276                  *
1277                  * Note: both here and above, we ignore any implicit index restrictions
1278                  * associated with the use of partial indexes.  This is OK because
1279                  * we're only trying to prove we can dispense with some join quals;
1280                  * failing to prove that doesn't result in an incorrect plan.  It is
1281                  * the right way to proceed because adding more quals to the stuff
1282                  * we got from the original query would just make it harder to detect
1283                  * duplication.
1284                  */
1285                 BitmapHeapPath *innerpath = (BitmapHeapPath *) best_path->innerjoinpath;
1286
1287                 if (innerpath->isjoininner)
1288                 {
1289                         List       *bitmapclauses;
1290
1291                         bitmapclauses =
1292                                 make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
1293                                                                                                   true,
1294                                                                                                   false);
1295                         joinrestrictclauses =
1296                                 select_nonredundant_join_clauses(root,
1297                                                                                                  joinrestrictclauses,
1298                                                                                                  bitmapclauses,
1299                                                                                                  IS_OUTER_JOIN(best_path->jointype));
1300                 }
1301         }
1302
1303         /* Get the join qual clauses (in plain expression form) */
1304         if (IS_OUTER_JOIN(best_path->jointype))
1305         {
1306                 get_actual_join_clauses(joinrestrictclauses,
1307                                                                 &joinclauses, &otherclauses);
1308         }
1309         else
1310         {
1311                 /* We can treat all clauses alike for an inner join */
1312                 joinclauses = get_actual_clauses(joinrestrictclauses);
1313                 otherclauses = NIL;
1314         }
1315
1316         /* Sort clauses into best execution order */
1317         joinclauses = order_qual_clauses(root, joinclauses);
1318         otherclauses = order_qual_clauses(root, otherclauses);
1319
1320         join_plan = make_nestloop(tlist,
1321                                                           joinclauses,
1322                                                           otherclauses,
1323                                                           outer_plan,
1324                                                           inner_plan,
1325                                                           best_path->jointype);
1326
1327         copy_path_costsize(&join_plan->join.plan, &best_path->path);
1328
1329         return join_plan;
1330 }
1331
1332 static MergeJoin *
1333 create_mergejoin_plan(PlannerInfo *root,
1334                                           MergePath *best_path,
1335                                           Plan *outer_plan,
1336                                           Plan *inner_plan)
1337 {
1338         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1339         List       *joinclauses;
1340         List       *otherclauses;
1341         List       *mergeclauses;
1342         MergeJoin  *join_plan;
1343
1344         /* Get the join qual clauses (in plain expression form) */
1345         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1346         {
1347                 get_actual_join_clauses(best_path->jpath.joinrestrictinfo,
1348                                                                 &joinclauses, &otherclauses);
1349         }
1350         else
1351         {
1352                 /* We can treat all clauses alike for an inner join */
1353                 joinclauses = get_actual_clauses(best_path->jpath.joinrestrictinfo);
1354                 otherclauses = NIL;
1355         }
1356
1357         /*
1358          * Remove the mergeclauses from the list of join qual clauses, leaving
1359          * the list of quals that must be checked as qpquals.
1360          */
1361         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
1362         joinclauses = list_difference(joinclauses, mergeclauses);
1363
1364         /*
1365          * Rearrange mergeclauses, if needed, so that the outer variable is
1366          * always on the left.
1367          */
1368         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
1369                                                  best_path->jpath.outerjoinpath->parent->relids);
1370
1371         /* Sort clauses into best execution order */
1372         /* NB: do NOT reorder the mergeclauses */
1373         joinclauses = order_qual_clauses(root, joinclauses);
1374         otherclauses = order_qual_clauses(root, otherclauses);
1375
1376         /*
1377          * Create explicit sort nodes for the outer and inner join paths if
1378          * necessary.  The sort cost was already accounted for in the path.
1379          * Make sure there are no excess columns in the inputs if sorting.
1380          */
1381         if (best_path->outersortkeys)
1382         {
1383                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
1384                 outer_plan = (Plan *)
1385                         make_sort_from_pathkeys(root,
1386                                                                         outer_plan,
1387                                                                         best_path->outersortkeys);
1388         }
1389
1390         if (best_path->innersortkeys)
1391         {
1392                 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1393                 inner_plan = (Plan *)
1394                         make_sort_from_pathkeys(root,
1395                                                                         inner_plan,
1396                                                                         best_path->innersortkeys);
1397         }
1398
1399         /*
1400          * Now we can build the mergejoin node.
1401          */
1402         join_plan = make_mergejoin(tlist,
1403                                                            joinclauses,
1404                                                            otherclauses,
1405                                                            mergeclauses,
1406                                                            outer_plan,
1407                                                            inner_plan,
1408                                                            best_path->jpath.jointype);
1409
1410         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1411
1412         return join_plan;
1413 }
1414
1415 static HashJoin *
1416 create_hashjoin_plan(PlannerInfo *root,
1417                                          HashPath *best_path,
1418                                          Plan *outer_plan,
1419                                          Plan *inner_plan)
1420 {
1421         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1422         List       *joinclauses;
1423         List       *otherclauses;
1424         List       *hashclauses;
1425         HashJoin   *join_plan;
1426         Hash       *hash_plan;
1427
1428         /* Get the join qual clauses (in plain expression form) */
1429         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1430         {
1431                 get_actual_join_clauses(best_path->jpath.joinrestrictinfo,
1432                                                                 &joinclauses, &otherclauses);
1433         }
1434         else
1435         {
1436                 /* We can treat all clauses alike for an inner join */
1437                 joinclauses = get_actual_clauses(best_path->jpath.joinrestrictinfo);
1438                 otherclauses = NIL;
1439         }
1440
1441         /*
1442          * Remove the hashclauses from the list of join qual clauses, leaving
1443          * the list of quals that must be checked as qpquals.
1444          */
1445         hashclauses = get_actual_clauses(best_path->path_hashclauses);
1446         joinclauses = list_difference(joinclauses, hashclauses);
1447
1448         /*
1449          * Rearrange hashclauses, if needed, so that the outer variable is
1450          * always on the left.
1451          */
1452         hashclauses = get_switched_clauses(best_path->path_hashclauses,
1453                                                  best_path->jpath.outerjoinpath->parent->relids);
1454
1455         /* Sort clauses into best execution order */
1456         joinclauses = order_qual_clauses(root, joinclauses);
1457         otherclauses = order_qual_clauses(root, otherclauses);
1458         hashclauses = order_qual_clauses(root, hashclauses);
1459
1460         /* We don't want any excess columns in the hashed tuples */
1461         disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1462
1463         /*
1464          * Build the hash node and hash join node.
1465          */
1466         hash_plan = make_hash(inner_plan);
1467         join_plan = make_hashjoin(tlist,
1468                                                           joinclauses,
1469                                                           otherclauses,
1470                                                           hashclauses,
1471                                                           outer_plan,
1472                                                           (Plan *) hash_plan,
1473                                                           best_path->jpath.jointype);
1474
1475         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1476
1477         return join_plan;
1478 }
1479
1480
1481 /*****************************************************************************
1482  *
1483  *      SUPPORTING ROUTINES
1484  *
1485  *****************************************************************************/
1486
1487 /*
1488  * fix_indexqual_references
1489  *        Adjust indexqual clauses to the form the executor's indexqual
1490  *        machinery needs, and check for recheckable (lossy) index conditions.
1491  *
1492  * We have five tasks here:
1493  *      * Remove RestrictInfo nodes from the input clauses.
1494  *      * Index keys must be represented by Var nodes with varattno set to the
1495  *        index's attribute number, not the attribute number in the original rel.
1496  *      * If the index key is on the right, commute the clause to put it on the
1497  *        left.
1498  *      * We must construct lists of operator strategy numbers and subtypes
1499  *        for the top-level operators of each index clause.
1500  *      * We must detect any lossy index operators.  The API is that we return
1501  *        a list of the input clauses whose operators are NOT lossy.
1502  *
1503  * fixed_indexquals receives a modified copy of the indexquals list --- the
1504  * original is not changed.  Note also that the copy shares no substructure
1505  * with the original; this is needed in case there is a subplan in it (we need
1506  * two separate copies of the subplan tree, or things will go awry).
1507  *
1508  * nonlossy_indexquals receives a list of the original input clauses (with
1509  * RestrictInfos) that contain non-lossy operators.
1510  *
1511  * indexstrategy receives an integer list of strategy numbers.
1512  * indexsubtype receives an OID list of strategy subtypes.
1513  */
1514 static void
1515 fix_indexqual_references(List *indexquals, IndexPath *index_path,
1516                                                  List **fixed_indexquals,
1517                                                  List **nonlossy_indexquals,
1518                                                  List **indexstrategy,
1519                                                  List **indexsubtype)
1520 {
1521         IndexOptInfo *index = index_path->indexinfo;
1522         ListCell   *l;
1523
1524         *fixed_indexquals = NIL;
1525         *nonlossy_indexquals = NIL;
1526         *indexstrategy = NIL;
1527         *indexsubtype = NIL;
1528
1529         /*
1530          * For each qual clause, commute if needed to put the indexkey operand on
1531          * the left, and then fix its varattno.  (We do not need to change the
1532          * other side of the clause.)  Then determine the operator's strategy
1533          * number and subtype number, and check for lossy index behavior.
1534          */
1535         foreach(l, indexquals)
1536         {
1537                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1538                 OpExpr     *clause;
1539                 OpExpr     *newclause;
1540                 Oid                     opclass;
1541                 int                     stratno;
1542                 Oid                     stratsubtype;
1543                 bool            recheck;
1544
1545                 Assert(IsA(rinfo, RestrictInfo));
1546                 clause = (OpExpr *) rinfo->clause;
1547                 if (!IsA(clause, OpExpr) ||
1548                         list_length(clause->args) != 2)
1549                         elog(ERROR, "indexqual clause is not binary opclause");
1550
1551                 /*
1552                  * Make a copy that will become the fixed clause.
1553                  *
1554                  * We used to try to do a shallow copy here, but that fails if there
1555                  * is a subplan in the arguments of the opclause.  So just do a
1556                  * full copy.
1557                  */
1558                 newclause = (OpExpr *) copyObject((Node *) clause);
1559
1560                 /*
1561                  * Check to see if the indexkey is on the right; if so, commute
1562                  * the clause.  The indexkey should be the side that refers to
1563                  * (only) the base relation.
1564                  */
1565                 if (!bms_equal(rinfo->left_relids, index->rel->relids))
1566                         CommuteClause(newclause);
1567
1568                 /*
1569                  * Now, determine which index attribute this is, change the
1570                  * indexkey operand as needed, and get the index opclass.
1571                  */
1572                 linitial(newclause->args) =
1573                         fix_indexqual_operand(linitial(newclause->args),
1574                                                                   index,
1575                                                                   &opclass);
1576
1577                 *fixed_indexquals = lappend(*fixed_indexquals, newclause);
1578
1579                 /*
1580                  * Look up the (possibly commuted) operator in the operator class
1581                  * to get its strategy numbers and the recheck indicator.  This
1582                  * also double-checks that we found an operator matching the
1583                  * index.
1584                  */
1585                 get_op_opclass_properties(newclause->opno, opclass,
1586                                                                   &stratno, &stratsubtype, &recheck);
1587
1588                 *indexstrategy = lappend_int(*indexstrategy, stratno);
1589                 *indexsubtype = lappend_oid(*indexsubtype, stratsubtype);
1590
1591                 /* If it's not lossy, add to nonlossy_indexquals */
1592                 if (!recheck)
1593                         *nonlossy_indexquals = lappend(*nonlossy_indexquals, rinfo);
1594         }
1595 }
1596
1597 static Node *
1598 fix_indexqual_operand(Node *node, IndexOptInfo *index, Oid *opclass)
1599 {
1600         /*
1601          * We represent index keys by Var nodes having the varno of the base
1602          * table but varattno equal to the index's attribute number (index
1603          * column position).  This is a bit hokey ... would be cleaner to use
1604          * a special-purpose node type that could not be mistaken for a
1605          * regular Var.  But it will do for now.
1606          */
1607         Var                *result;
1608         int                     pos;
1609         ListCell   *indexpr_item;
1610
1611         /*
1612          * Remove any binary-compatible relabeling of the indexkey
1613          */
1614         if (IsA(node, RelabelType))
1615                 node = (Node *) ((RelabelType *) node)->arg;
1616
1617         if (IsA(node, Var) &&
1618                 ((Var *) node)->varno == index->rel->relid)
1619         {
1620                 /* Try to match against simple index columns */
1621                 int                     varatt = ((Var *) node)->varattno;
1622
1623                 if (varatt != 0)
1624                 {
1625                         for (pos = 0; pos < index->ncolumns; pos++)
1626                         {
1627                                 if (index->indexkeys[pos] == varatt)
1628                                 {
1629                                         result = (Var *) copyObject(node);
1630                                         result->varattno = pos + 1;
1631                                         /* return the correct opclass, too */
1632                                         *opclass = index->classlist[pos];
1633                                         return (Node *) result;
1634                                 }
1635                         }
1636                 }
1637         }
1638
1639         /* Try to match against index expressions */
1640         indexpr_item = list_head(index->indexprs);
1641         for (pos = 0; pos < index->ncolumns; pos++)
1642         {
1643                 if (index->indexkeys[pos] == 0)
1644                 {
1645                         Node       *indexkey;
1646
1647                         if (indexpr_item == NULL)
1648                                 elog(ERROR, "too few entries in indexprs list");
1649                         indexkey = (Node *) lfirst(indexpr_item);
1650                         if (indexkey && IsA(indexkey, RelabelType))
1651                                 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
1652                         if (equal(node, indexkey))
1653                         {
1654                                 /* Found a match */
1655                                 result = makeVar(index->rel->relid, pos + 1,
1656                                                                  exprType(lfirst(indexpr_item)), -1,
1657                                                                  0);
1658                                 /* return the correct opclass, too */
1659                                 *opclass = index->classlist[pos];
1660                                 return (Node *) result;
1661                         }
1662                         indexpr_item = lnext(indexpr_item);
1663                 }
1664         }
1665
1666         /* Ooops... */
1667         elog(ERROR, "node is not an index attribute");
1668         *opclass = InvalidOid;          /* keep compiler quiet */
1669         return NULL;
1670 }
1671
1672 /*
1673  * get_switched_clauses
1674  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
1675  *        extract the bare clauses, and rearrange the elements within the
1676  *        clauses, if needed, so the outer join variable is on the left and
1677  *        the inner is on the right.  The original data structure is not touched;
1678  *        a modified list is returned.
1679  */
1680 static List *
1681 get_switched_clauses(List *clauses, Relids outerrelids)
1682 {
1683         List       *t_list = NIL;
1684         ListCell   *l;
1685
1686         foreach(l, clauses)
1687         {
1688                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1689                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
1690
1691                 Assert(is_opclause(clause));
1692                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
1693                 {
1694                         /*
1695                          * Duplicate just enough of the structure to allow commuting
1696                          * the clause without changing the original list.  Could use
1697                          * copyObject, but a complete deep copy is overkill.
1698                          */
1699                         OpExpr     *temp = makeNode(OpExpr);
1700
1701                         temp->opno = clause->opno;
1702                         temp->opfuncid = InvalidOid;
1703                         temp->opresulttype = clause->opresulttype;
1704                         temp->opretset = clause->opretset;
1705                         temp->args = list_copy(clause->args);
1706                         /* Commute it --- note this modifies the temp node in-place. */
1707                         CommuteClause(temp);
1708                         t_list = lappend(t_list, temp);
1709                 }
1710                 else
1711                         t_list = lappend(t_list, clause);
1712         }
1713         return t_list;
1714 }
1715
1716 /*
1717  * order_qual_clauses
1718  *              Given a list of qual clauses that will all be evaluated at the same
1719  *              plan node, sort the list into the order we want to check the quals
1720  *              in at runtime.
1721  *
1722  * Ideally the order should be driven by a combination of execution cost and
1723  * selectivity, but unfortunately we have so little information about
1724  * execution cost of operators that it's really hard to do anything smart.
1725  * For now, we just move any quals that contain SubPlan references (but not
1726  * InitPlan references) to the end of the list.
1727  */
1728 List *
1729 order_qual_clauses(PlannerInfo *root, List *clauses)
1730 {
1731         List       *nosubplans;
1732         List       *withsubplans;
1733         ListCell   *l;
1734
1735         /* No need to work hard if the query is subselect-free */
1736         if (!root->parse->hasSubLinks)
1737                 return clauses;
1738
1739         nosubplans = NIL;
1740         withsubplans = NIL;
1741         foreach(l, clauses)
1742         {
1743                 Node       *clause = (Node *) lfirst(l);
1744
1745                 if (contain_subplans(clause))
1746                         withsubplans = lappend(withsubplans, clause);
1747                 else
1748                         nosubplans = lappend(nosubplans, clause);
1749         }
1750
1751         return list_concat(nosubplans, withsubplans);
1752 }
1753
1754 /*
1755  * Copy cost and size info from a Path node to the Plan node created from it.
1756  * The executor won't use this info, but it's needed by EXPLAIN.
1757  */
1758 static void
1759 copy_path_costsize(Plan *dest, Path *src)
1760 {
1761         if (src)
1762         {
1763                 dest->startup_cost = src->startup_cost;
1764                 dest->total_cost = src->total_cost;
1765                 dest->plan_rows = src->parent->rows;
1766                 dest->plan_width = src->parent->width;
1767         }
1768         else
1769         {
1770                 dest->startup_cost = 0;
1771                 dest->total_cost = 0;
1772                 dest->plan_rows = 0;
1773                 dest->plan_width = 0;
1774         }
1775 }
1776
1777 /*
1778  * Copy cost and size info from a lower plan node to an inserted node.
1779  * This is not critical, since the decisions have already been made,
1780  * but it helps produce more reasonable-looking EXPLAIN output.
1781  * (Some callers alter the info after copying it.)
1782  */
1783 static void
1784 copy_plan_costsize(Plan *dest, Plan *src)
1785 {
1786         if (src)
1787         {
1788                 dest->startup_cost = src->startup_cost;
1789                 dest->total_cost = src->total_cost;
1790                 dest->plan_rows = src->plan_rows;
1791                 dest->plan_width = src->plan_width;
1792         }
1793         else
1794         {
1795                 dest->startup_cost = 0;
1796                 dest->total_cost = 0;
1797                 dest->plan_rows = 0;
1798                 dest->plan_width = 0;
1799         }
1800 }
1801
1802
1803 /*****************************************************************************
1804  *
1805  *      PLAN NODE BUILDING ROUTINES
1806  *
1807  * Some of these are exported because they are called to build plan nodes
1808  * in contexts where we're not deriving the plan node from a path node.
1809  *
1810  *****************************************************************************/
1811
1812 static SeqScan *
1813 make_seqscan(List *qptlist,
1814                          List *qpqual,
1815                          Index scanrelid)
1816 {
1817         SeqScan    *node = makeNode(SeqScan);
1818         Plan       *plan = &node->plan;
1819
1820         /* cost should be inserted by caller */
1821         plan->targetlist = qptlist;
1822         plan->qual = qpqual;
1823         plan->lefttree = NULL;
1824         plan->righttree = NULL;
1825         node->scanrelid = scanrelid;
1826
1827         return node;
1828 }
1829
1830 static IndexScan *
1831 make_indexscan(List *qptlist,
1832                            List *qpqual,
1833                            Index scanrelid,
1834                            Oid indexid,
1835                            List *indexqual,
1836                            List *indexqualorig,
1837                            List *indexstrategy,
1838                            List *indexsubtype,
1839                            ScanDirection indexscandir)
1840 {
1841         IndexScan  *node = makeNode(IndexScan);
1842         Plan       *plan = &node->scan.plan;
1843
1844         /* cost should be inserted by caller */
1845         plan->targetlist = qptlist;
1846         plan->qual = qpqual;
1847         plan->lefttree = NULL;
1848         plan->righttree = NULL;
1849         node->scan.scanrelid = scanrelid;
1850         node->indexid = indexid;
1851         node->indexqual = indexqual;
1852         node->indexqualorig = indexqualorig;
1853         node->indexstrategy = indexstrategy;
1854         node->indexsubtype = indexsubtype;
1855         node->indexorderdir = indexscandir;
1856
1857         return node;
1858 }
1859
1860 static BitmapIndexScan *
1861 make_bitmap_indexscan(Index scanrelid,
1862                                           Oid indexid,
1863                                           List *indexqual,
1864                                           List *indexqualorig,
1865                                           List *indexstrategy,
1866                                           List *indexsubtype)
1867 {
1868         BitmapIndexScan *node = makeNode(BitmapIndexScan);
1869         Plan       *plan = &node->scan.plan;
1870
1871         /* cost should be inserted by caller */
1872         plan->targetlist = NIL;         /* not used */
1873         plan->qual = NIL;                       /* not used */
1874         plan->lefttree = NULL;
1875         plan->righttree = NULL;
1876         node->scan.scanrelid = scanrelid;
1877         node->indexid = indexid;
1878         node->indexqual = indexqual;
1879         node->indexqualorig = indexqualorig;
1880         node->indexstrategy = indexstrategy;
1881         node->indexsubtype = indexsubtype;
1882
1883         return node;
1884 }
1885
1886 static BitmapHeapScan *
1887 make_bitmap_heapscan(List *qptlist,
1888                                          List *qpqual,
1889                                          Plan *lefttree,
1890                                          List *bitmapqualorig,
1891                                          Index scanrelid)
1892 {
1893         BitmapHeapScan *node = makeNode(BitmapHeapScan);
1894         Plan       *plan = &node->scan.plan;
1895
1896         /* cost should be inserted by caller */
1897         plan->targetlist = qptlist;
1898         plan->qual = qpqual;
1899         plan->lefttree = lefttree;
1900         plan->righttree = NULL;
1901         node->scan.scanrelid = scanrelid;
1902         node->bitmapqualorig = bitmapqualorig;
1903
1904         return node;
1905 }
1906
1907 static TidScan *
1908 make_tidscan(List *qptlist,
1909                          List *qpqual,
1910                          Index scanrelid,
1911                          List *tideval)
1912 {
1913         TidScan    *node = makeNode(TidScan);
1914         Plan       *plan = &node->scan.plan;
1915
1916         /* cost should be inserted by caller */
1917         plan->targetlist = qptlist;
1918         plan->qual = qpqual;
1919         plan->lefttree = NULL;
1920         plan->righttree = NULL;
1921         node->scan.scanrelid = scanrelid;
1922         node->tideval = tideval;
1923
1924         return node;
1925 }
1926
1927 SubqueryScan *
1928 make_subqueryscan(List *qptlist,
1929                                   List *qpqual,
1930                                   Index scanrelid,
1931                                   Plan *subplan)
1932 {
1933         SubqueryScan *node = makeNode(SubqueryScan);
1934         Plan       *plan = &node->scan.plan;
1935
1936         /*
1937          * Cost is figured here for the convenience of prepunion.c.  Note this
1938          * is only correct for the case where qpqual is empty; otherwise
1939          * caller should overwrite cost with a better estimate.
1940          */
1941         copy_plan_costsize(plan, subplan);
1942         plan->total_cost += cpu_tuple_cost * subplan->plan_rows;
1943
1944         plan->targetlist = qptlist;
1945         plan->qual = qpqual;
1946         plan->lefttree = NULL;
1947         plan->righttree = NULL;
1948         node->scan.scanrelid = scanrelid;
1949         node->subplan = subplan;
1950
1951         return node;
1952 }
1953
1954 static FunctionScan *
1955 make_functionscan(List *qptlist,
1956                                   List *qpqual,
1957                                   Index scanrelid)
1958 {
1959         FunctionScan *node = makeNode(FunctionScan);
1960         Plan       *plan = &node->scan.plan;
1961
1962         /* cost should be inserted by caller */
1963         plan->targetlist = qptlist;
1964         plan->qual = qpqual;
1965         plan->lefttree = NULL;
1966         plan->righttree = NULL;
1967         node->scan.scanrelid = scanrelid;
1968
1969         return node;
1970 }
1971
1972 Append *
1973 make_append(List *appendplans, bool isTarget, List *tlist)
1974 {
1975         Append     *node = makeNode(Append);
1976         Plan       *plan = &node->plan;
1977         ListCell   *subnode;
1978
1979         /*
1980          * Compute cost as sum of subplan costs.  We charge nothing extra for
1981          * the Append itself, which perhaps is too optimistic, but since it
1982          * doesn't do any selection or projection, it is a pretty cheap node.
1983          */
1984         plan->startup_cost = 0;
1985         plan->total_cost = 0;
1986         plan->plan_rows = 0;
1987         plan->plan_width = 0;
1988         foreach(subnode, appendplans)
1989         {
1990                 Plan       *subplan = (Plan *) lfirst(subnode);
1991
1992                 if (subnode == list_head(appendplans))  /* first node? */
1993                         plan->startup_cost = subplan->startup_cost;
1994                 plan->total_cost += subplan->total_cost;
1995                 plan->plan_rows += subplan->plan_rows;
1996                 if (plan->plan_width < subplan->plan_width)
1997                         plan->plan_width = subplan->plan_width;
1998         }
1999
2000         plan->targetlist = tlist;
2001         plan->qual = NIL;
2002         plan->lefttree = NULL;
2003         plan->righttree = NULL;
2004         node->appendplans = appendplans;
2005         node->isTarget = isTarget;
2006
2007         return node;
2008 }
2009
2010 static BitmapAnd *
2011 make_bitmap_and(List *bitmapplans)
2012 {
2013         BitmapAnd  *node = makeNode(BitmapAnd);
2014         Plan       *plan = &node->plan;
2015
2016         /* cost should be inserted by caller */
2017         plan->targetlist = NIL;
2018         plan->qual = NIL;
2019         plan->lefttree = NULL;
2020         plan->righttree = NULL;
2021         node->bitmapplans = bitmapplans;
2022
2023         return node;
2024 }
2025
2026 static BitmapOr *
2027 make_bitmap_or(List *bitmapplans)
2028 {
2029         BitmapOr   *node = makeNode(BitmapOr);
2030         Plan       *plan = &node->plan;
2031
2032         /* cost should be inserted by caller */
2033         plan->targetlist = NIL;
2034         plan->qual = NIL;
2035         plan->lefttree = NULL;
2036         plan->righttree = NULL;
2037         node->bitmapplans = bitmapplans;
2038
2039         return node;
2040 }
2041
2042 static NestLoop *
2043 make_nestloop(List *tlist,
2044                           List *joinclauses,
2045                           List *otherclauses,
2046                           Plan *lefttree,
2047                           Plan *righttree,
2048                           JoinType jointype)
2049 {
2050         NestLoop   *node = makeNode(NestLoop);
2051         Plan       *plan = &node->join.plan;
2052
2053         /* cost should be inserted by caller */
2054         plan->targetlist = tlist;
2055         plan->qual = otherclauses;
2056         plan->lefttree = lefttree;
2057         plan->righttree = righttree;
2058         node->join.jointype = jointype;
2059         node->join.joinqual = joinclauses;
2060
2061         return node;
2062 }
2063
2064 static HashJoin *
2065 make_hashjoin(List *tlist,
2066                           List *joinclauses,
2067                           List *otherclauses,
2068                           List *hashclauses,
2069                           Plan *lefttree,
2070                           Plan *righttree,
2071                           JoinType jointype)
2072 {
2073         HashJoin   *node = makeNode(HashJoin);
2074         Plan       *plan = &node->join.plan;
2075
2076         /* cost should be inserted by caller */
2077         plan->targetlist = tlist;
2078         plan->qual = otherclauses;
2079         plan->lefttree = lefttree;
2080         plan->righttree = righttree;
2081         node->hashclauses = hashclauses;
2082         node->join.jointype = jointype;
2083         node->join.joinqual = joinclauses;
2084
2085         return node;
2086 }
2087
2088 static Hash *
2089 make_hash(Plan *lefttree)
2090 {
2091         Hash       *node = makeNode(Hash);
2092         Plan       *plan = &node->plan;
2093
2094         copy_plan_costsize(plan, lefttree);
2095
2096         /*
2097          * For plausibility, make startup & total costs equal total cost of
2098          * input plan; this only affects EXPLAIN display not decisions.
2099          */
2100         plan->startup_cost = plan->total_cost;
2101         plan->targetlist = copyObject(lefttree->targetlist);
2102         plan->qual = NIL;
2103         plan->lefttree = lefttree;
2104         plan->righttree = NULL;
2105
2106         return node;
2107 }
2108
2109 static MergeJoin *
2110 make_mergejoin(List *tlist,
2111                            List *joinclauses,
2112                            List *otherclauses,
2113                            List *mergeclauses,
2114                            Plan *lefttree,
2115                            Plan *righttree,
2116                            JoinType jointype)
2117 {
2118         MergeJoin  *node = makeNode(MergeJoin);
2119         Plan       *plan = &node->join.plan;
2120
2121         /* cost should be inserted by caller */
2122         plan->targetlist = tlist;
2123         plan->qual = otherclauses;
2124         plan->lefttree = lefttree;
2125         plan->righttree = righttree;
2126         node->mergeclauses = mergeclauses;
2127         node->join.jointype = jointype;
2128         node->join.joinqual = joinclauses;
2129
2130         return node;
2131 }
2132
2133 /*
2134  * make_sort --- basic routine to build a Sort plan node
2135  *
2136  * Caller must have built the sortColIdx and sortOperators arrays already.
2137  */
2138 static Sort *
2139 make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
2140                   AttrNumber *sortColIdx, Oid *sortOperators)
2141 {
2142         Sort       *node = makeNode(Sort);
2143         Plan       *plan = &node->plan;
2144         Path            sort_path;              /* dummy for result of cost_sort */
2145
2146         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2147         cost_sort(&sort_path, root, NIL,
2148                           lefttree->total_cost,
2149                           lefttree->plan_rows,
2150                           lefttree->plan_width);
2151         plan->startup_cost = sort_path.startup_cost;
2152         plan->total_cost = sort_path.total_cost;
2153         plan->targetlist = copyObject(lefttree->targetlist);
2154         plan->qual = NIL;
2155         plan->lefttree = lefttree;
2156         plan->righttree = NULL;
2157         node->numCols = numCols;
2158         node->sortColIdx = sortColIdx;
2159         node->sortOperators = sortOperators;
2160
2161         return node;
2162 }
2163
2164 /*
2165  * add_sort_column --- utility subroutine for building sort info arrays
2166  *
2167  * We need this routine because the same column might be selected more than
2168  * once as a sort key column; if so, the extra mentions are redundant.
2169  *
2170  * Caller is assumed to have allocated the arrays large enough for the
2171  * max possible number of columns.      Return value is the new column count.
2172  */
2173 static int
2174 add_sort_column(AttrNumber colIdx, Oid sortOp,
2175                                 int numCols, AttrNumber *sortColIdx, Oid *sortOperators)
2176 {
2177         int                     i;
2178
2179         for (i = 0; i < numCols; i++)
2180         {
2181                 if (sortColIdx[i] == colIdx)
2182                 {
2183                         /* Already sorting by this col, so extra sort key is useless */
2184                         return numCols;
2185                 }
2186         }
2187
2188         /* Add the column */
2189         sortColIdx[numCols] = colIdx;
2190         sortOperators[numCols] = sortOp;
2191         return numCols + 1;
2192 }
2193
2194 /*
2195  * make_sort_from_pathkeys
2196  *        Create sort plan to sort according to given pathkeys
2197  *
2198  *        'lefttree' is the node which yields input tuples
2199  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
2200  *
2201  * We must convert the pathkey information into arrays of sort key column
2202  * numbers and sort operator OIDs.
2203  *
2204  * If the pathkeys include expressions that aren't simple Vars, we will
2205  * usually need to add resjunk items to the input plan's targetlist to
2206  * compute these expressions (since the Sort node itself won't do it).
2207  * If the input plan type isn't one that can do projections, this means
2208  * adding a Result node just to do the projection.
2209  */
2210 static Sort *
2211 make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
2212 {
2213         List       *tlist = lefttree->targetlist;
2214         ListCell   *i;
2215         int                     numsortkeys;
2216         AttrNumber *sortColIdx;
2217         Oid                *sortOperators;
2218
2219         /*
2220          * We will need at most list_length(pathkeys) sort columns; possibly
2221          * less
2222          */
2223         numsortkeys = list_length(pathkeys);
2224         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2225         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2226
2227         numsortkeys = 0;
2228
2229         foreach(i, pathkeys)
2230         {
2231                 List       *keysublist = (List *) lfirst(i);
2232                 PathKeyItem *pathkey = NULL;
2233                 TargetEntry *tle = NULL;
2234                 ListCell   *j;
2235
2236                 /*
2237                  * We can sort by any one of the sort key items listed in this
2238                  * sublist.  For now, we take the first one that corresponds to an
2239                  * available Var in the tlist.  If there isn't any, use the first
2240                  * one that is an expression in the input's vars.
2241                  *
2242                  * XXX if we have a choice, is there any way of figuring out which
2243                  * might be cheapest to execute?  (For example, int4lt is likely
2244                  * much cheaper to execute than numericlt, but both might appear
2245                  * in the same pathkey sublist...)      Not clear that we ever will
2246                  * have a choice in practice, so it may not matter.
2247                  */
2248                 foreach(j, keysublist)
2249                 {
2250                         pathkey = (PathKeyItem *) lfirst(j);
2251                         Assert(IsA(pathkey, PathKeyItem));
2252                         tle = tlist_member(pathkey->key, tlist);
2253                         if (tle)
2254                                 break;
2255                 }
2256                 if (!tle)
2257                 {
2258                         /* No matching Var; look for a computable expression */
2259                         foreach(j, keysublist)
2260                         {
2261                                 List       *exprvars;
2262                                 ListCell   *k;
2263
2264                                 pathkey = (PathKeyItem *) lfirst(j);
2265                                 exprvars = pull_var_clause(pathkey->key, false);
2266                                 foreach(k, exprvars)
2267                                 {
2268                                         if (!tlist_member(lfirst(k), tlist))
2269                                                 break;
2270                                 }
2271                                 list_free(exprvars);
2272                                 if (!k)
2273                                         break;          /* found usable expression */
2274                         }
2275                         if (!j)
2276                                 elog(ERROR, "could not find pathkey item to sort");
2277
2278                         /*
2279                          * Do we need to insert a Result node?
2280                          */
2281                         if (!is_projection_capable_plan(lefttree))
2282                         {
2283                                 tlist = copyObject(tlist);
2284                                 lefttree = (Plan *) make_result(tlist, NULL, lefttree);
2285                         }
2286
2287                         /*
2288                          * Add resjunk entry to input's tlist
2289                          */
2290                         tle = makeTargetEntry((Expr *) pathkey->key,
2291                                                                   list_length(tlist) + 1,
2292                                                                   NULL,
2293                                                                   true);
2294                         tlist = lappend(tlist, tle);
2295                         lefttree->targetlist = tlist;           /* just in case NIL before */
2296                 }
2297
2298                 /*
2299                  * The column might already be selected as a sort key, if the
2300                  * pathkeys contain duplicate entries.  (This can happen in
2301                  * scenarios where multiple mergejoinable clauses mention the same
2302                  * var, for example.)  So enter it only once in the sort arrays.
2303                  */
2304                 numsortkeys = add_sort_column(tle->resno, pathkey->sortop,
2305                                                                  numsortkeys, sortColIdx, sortOperators);
2306         }
2307
2308         Assert(numsortkeys > 0);
2309
2310         return make_sort(root, lefttree, numsortkeys,
2311                                          sortColIdx, sortOperators);
2312 }
2313
2314 /*
2315  * make_sort_from_sortclauses
2316  *        Create sort plan to sort according to given sortclauses
2317  *
2318  *        'sortcls' is a list of SortClauses
2319  *        'lefttree' is the node which yields input tuples
2320  */
2321 Sort *
2322 make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
2323 {
2324         List       *sub_tlist = lefttree->targetlist;
2325         ListCell   *l;
2326         int                     numsortkeys;
2327         AttrNumber *sortColIdx;
2328         Oid                *sortOperators;
2329
2330         /*
2331          * We will need at most list_length(sortcls) sort columns; possibly
2332          * less
2333          */
2334         numsortkeys = list_length(sortcls);
2335         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2336         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2337
2338         numsortkeys = 0;
2339
2340         foreach(l, sortcls)
2341         {
2342                 SortClause *sortcl = (SortClause *) lfirst(l);
2343                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
2344
2345                 /*
2346                  * Check for the possibility of duplicate order-by clauses --- the
2347                  * parser should have removed 'em, but no point in sorting
2348                  * redundantly.
2349                  */
2350                 numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
2351                                                                  numsortkeys, sortColIdx, sortOperators);
2352         }
2353
2354         Assert(numsortkeys > 0);
2355
2356         return make_sort(root, lefttree, numsortkeys,
2357                                          sortColIdx, sortOperators);
2358 }
2359
2360 /*
2361  * make_sort_from_groupcols
2362  *        Create sort plan to sort based on grouping columns
2363  *
2364  * 'groupcls' is the list of GroupClauses
2365  * 'grpColIdx' gives the column numbers to use
2366  *
2367  * This might look like it could be merged with make_sort_from_sortclauses,
2368  * but presently we *must* use the grpColIdx[] array to locate sort columns,
2369  * because the child plan's tlist is not marked with ressortgroupref info
2370  * appropriate to the grouping node.  So, only the sortop is used from the
2371  * GroupClause entries.
2372  */
2373 Sort *
2374 make_sort_from_groupcols(PlannerInfo *root,
2375                                                  List *groupcls,
2376                                                  AttrNumber *grpColIdx,
2377                                                  Plan *lefttree)
2378 {
2379         List       *sub_tlist = lefttree->targetlist;
2380         int                     grpno = 0;
2381         ListCell   *l;
2382         int                     numsortkeys;
2383         AttrNumber *sortColIdx;
2384         Oid                *sortOperators;
2385
2386         /*
2387          * We will need at most list_length(groupcls) sort columns; possibly
2388          * less
2389          */
2390         numsortkeys = list_length(groupcls);
2391         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2392         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2393
2394         numsortkeys = 0;
2395
2396         foreach(l, groupcls)
2397         {
2398                 GroupClause *grpcl = (GroupClause *) lfirst(l);
2399                 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
2400
2401                 /*
2402                  * Check for the possibility of duplicate group-by clauses --- the
2403                  * parser should have removed 'em, but no point in sorting
2404                  * redundantly.
2405                  */
2406                 numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
2407                                                                  numsortkeys, sortColIdx, sortOperators);
2408                 grpno++;
2409         }
2410
2411         Assert(numsortkeys > 0);
2412
2413         return make_sort(root, lefttree, numsortkeys,
2414                                          sortColIdx, sortOperators);
2415 }
2416
2417 Material *
2418 make_material(Plan *lefttree)
2419 {
2420         Material   *node = makeNode(Material);
2421         Plan       *plan = &node->plan;
2422
2423         /* cost should be inserted by caller */
2424         plan->targetlist = copyObject(lefttree->targetlist);
2425         plan->qual = NIL;
2426         plan->lefttree = lefttree;
2427         plan->righttree = NULL;
2428
2429         return node;
2430 }
2431
2432 /*
2433  * materialize_finished_plan: stick a Material node atop a completed plan
2434  *
2435  * There are a couple of places where we want to attach a Material node
2436  * after completion of subquery_planner().      This currently requires hackery.
2437  * Since subquery_planner has already run SS_finalize_plan on the subplan
2438  * tree, we have to kluge up parameter lists for the Material node.
2439  * Possibly this could be fixed by postponing SS_finalize_plan processing
2440  * until setrefs.c is run?
2441  */
2442 Plan *
2443 materialize_finished_plan(Plan *subplan)
2444 {
2445         Plan       *matplan;
2446         Path            matpath;                /* dummy for result of cost_material */
2447
2448         matplan = (Plan *) make_material(subplan);
2449
2450         /* Set cost data */
2451         cost_material(&matpath,
2452                                   subplan->total_cost,
2453                                   subplan->plan_rows,
2454                                   subplan->plan_width);
2455         matplan->startup_cost = matpath.startup_cost;
2456         matplan->total_cost = matpath.total_cost;
2457         matplan->plan_rows = subplan->plan_rows;
2458         matplan->plan_width = subplan->plan_width;
2459
2460         /* parameter kluge --- see comments above */
2461         matplan->extParam = bms_copy(subplan->extParam);
2462         matplan->allParam = bms_copy(subplan->allParam);
2463
2464         return matplan;
2465 }
2466
2467 Agg *
2468 make_agg(PlannerInfo *root, List *tlist, List *qual,
2469                  AggStrategy aggstrategy,
2470                  int numGroupCols, AttrNumber *grpColIdx,
2471                  long numGroups, int numAggs,
2472                  Plan *lefttree)
2473 {
2474         Agg                *node = makeNode(Agg);
2475         Plan       *plan = &node->plan;
2476         Path            agg_path;               /* dummy for result of cost_agg */
2477         QualCost        qual_cost;
2478
2479         node->aggstrategy = aggstrategy;
2480         node->numCols = numGroupCols;
2481         node->grpColIdx = grpColIdx;
2482         node->numGroups = numGroups;
2483
2484         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2485         cost_agg(&agg_path, root,
2486                          aggstrategy, numAggs,
2487                          numGroupCols, numGroups,
2488                          lefttree->startup_cost,
2489                          lefttree->total_cost,
2490                          lefttree->plan_rows);
2491         plan->startup_cost = agg_path.startup_cost;
2492         plan->total_cost = agg_path.total_cost;
2493
2494         /*
2495          * We will produce a single output tuple if not grouping, and a tuple
2496          * per group otherwise.
2497          */
2498         if (aggstrategy == AGG_PLAIN)
2499                 plan->plan_rows = 1;
2500         else
2501                 plan->plan_rows = numGroups;
2502
2503         /*
2504          * We also need to account for the cost of evaluation of the qual (ie,
2505          * the HAVING clause) and the tlist.  Note that cost_qual_eval doesn't
2506          * charge anything for Aggref nodes; this is okay since they are
2507          * really comparable to Vars.
2508          *
2509          * See notes in grouping_planner about why this routine and make_group
2510          * are the only ones in this file that worry about tlist eval cost.
2511          */
2512         if (qual)
2513         {
2514                 cost_qual_eval(&qual_cost, qual);
2515                 plan->startup_cost += qual_cost.startup;
2516                 plan->total_cost += qual_cost.startup;
2517                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2518         }
2519         cost_qual_eval(&qual_cost, tlist);
2520         plan->startup_cost += qual_cost.startup;
2521         plan->total_cost += qual_cost.startup;
2522         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2523
2524         plan->qual = qual;
2525         plan->targetlist = tlist;
2526         plan->lefttree = lefttree;
2527         plan->righttree = NULL;
2528
2529         return node;
2530 }
2531
2532 Group *
2533 make_group(PlannerInfo *root,
2534                    List *tlist,
2535                    List *qual,
2536                    int numGroupCols,
2537                    AttrNumber *grpColIdx,
2538                    double numGroups,
2539                    Plan *lefttree)
2540 {
2541         Group      *node = makeNode(Group);
2542         Plan       *plan = &node->plan;
2543         Path            group_path;             /* dummy for result of cost_group */
2544         QualCost        qual_cost;
2545
2546         node->numCols = numGroupCols;
2547         node->grpColIdx = grpColIdx;
2548
2549         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2550         cost_group(&group_path, root,
2551                            numGroupCols, numGroups,
2552                            lefttree->startup_cost,
2553                            lefttree->total_cost,
2554                            lefttree->plan_rows);
2555         plan->startup_cost = group_path.startup_cost;
2556         plan->total_cost = group_path.total_cost;
2557
2558         /* One output tuple per estimated result group */
2559         plan->plan_rows = numGroups;
2560
2561         /*
2562          * We also need to account for the cost of evaluation of the qual (ie,
2563          * the HAVING clause) and the tlist.
2564          *
2565          * XXX this double-counts the cost of evaluation of any expressions used
2566          * for grouping, since in reality those will have been evaluated at a
2567          * lower plan level and will only be copied by the Group node. Worth
2568          * fixing?
2569          *
2570          * See notes in grouping_planner about why this routine and make_agg are
2571          * the only ones in this file that worry about tlist eval cost.
2572          */
2573         if (qual)
2574         {
2575                 cost_qual_eval(&qual_cost, qual);
2576                 plan->startup_cost += qual_cost.startup;
2577                 plan->total_cost += qual_cost.startup;
2578                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2579         }
2580         cost_qual_eval(&qual_cost, tlist);
2581         plan->startup_cost += qual_cost.startup;
2582         plan->total_cost += qual_cost.startup;
2583         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2584
2585         plan->qual = qual;
2586         plan->targetlist = tlist;
2587         plan->lefttree = lefttree;
2588         plan->righttree = NULL;
2589
2590         return node;
2591 }
2592
2593 /*
2594  * distinctList is a list of SortClauses, identifying the targetlist items
2595  * that should be considered by the Unique filter.
2596  */
2597 Unique *
2598 make_unique(Plan *lefttree, List *distinctList)
2599 {
2600         Unique     *node = makeNode(Unique);
2601         Plan       *plan = &node->plan;
2602         int                     numCols = list_length(distinctList);
2603         int                     keyno = 0;
2604         AttrNumber *uniqColIdx;
2605         ListCell   *slitem;
2606
2607         copy_plan_costsize(plan, lefttree);
2608
2609         /*
2610          * Charge one cpu_operator_cost per comparison per input tuple. We
2611          * assume all columns get compared at most of the tuples.  (XXX
2612          * probably this is an overestimate.)
2613          */
2614         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
2615
2616         /*
2617          * plan->plan_rows is left as a copy of the input subplan's plan_rows;
2618          * ie, we assume the filter removes nothing.  The caller must alter
2619          * this if he has a better idea.
2620          */
2621
2622         plan->targetlist = copyObject(lefttree->targetlist);
2623         plan->qual = NIL;
2624         plan->lefttree = lefttree;
2625         plan->righttree = NULL;
2626
2627         /*
2628          * convert SortClause list into array of attr indexes, as wanted by
2629          * exec
2630          */
2631         Assert(numCols > 0);
2632         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2633
2634         foreach(slitem, distinctList)
2635         {
2636                 SortClause *sortcl = (SortClause *) lfirst(slitem);
2637                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
2638
2639                 uniqColIdx[keyno++] = tle->resno;
2640         }
2641
2642         node->numCols = numCols;
2643         node->uniqColIdx = uniqColIdx;
2644
2645         return node;
2646 }
2647
2648 /*
2649  * distinctList is a list of SortClauses, identifying the targetlist items
2650  * that should be considered by the SetOp filter.
2651  */
2652
2653 SetOp *
2654 make_setop(SetOpCmd cmd, Plan *lefttree,
2655                    List *distinctList, AttrNumber flagColIdx)
2656 {
2657         SetOp      *node = makeNode(SetOp);
2658         Plan       *plan = &node->plan;
2659         int                     numCols = list_length(distinctList);
2660         int                     keyno = 0;
2661         AttrNumber *dupColIdx;
2662         ListCell   *slitem;
2663
2664         copy_plan_costsize(plan, lefttree);
2665
2666         /*
2667          * Charge one cpu_operator_cost per comparison per input tuple. We
2668          * assume all columns get compared at most of the tuples.
2669          */
2670         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
2671
2672         /*
2673          * We make the unsupported assumption that there will be 10% as many
2674          * tuples out as in.  Any way to do better?
2675          */
2676         plan->plan_rows *= 0.1;
2677         if (plan->plan_rows < 1)
2678                 plan->plan_rows = 1;
2679
2680         plan->targetlist = copyObject(lefttree->targetlist);
2681         plan->qual = NIL;
2682         plan->lefttree = lefttree;
2683         plan->righttree = NULL;
2684
2685         /*
2686          * convert SortClause list into array of attr indexes, as wanted by
2687          * exec
2688          */
2689         Assert(numCols > 0);
2690         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2691
2692         foreach(slitem, distinctList)
2693         {
2694                 SortClause *sortcl = (SortClause *) lfirst(slitem);
2695                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
2696
2697                 dupColIdx[keyno++] = tle->resno;
2698         }
2699
2700         node->cmd = cmd;
2701         node->numCols = numCols;
2702         node->dupColIdx = dupColIdx;
2703         node->flagColIdx = flagColIdx;
2704
2705         return node;
2706 }
2707
2708 /*
2709  * Note: offset_est and count_est are passed in to save having to repeat
2710  * work already done to estimate the values of the limitOffset and limitCount
2711  * expressions.  Their values are as returned by preprocess_limit (0 means
2712  * "not relevant", -1 means "couldn't estimate").  Keep the code below in sync
2713  * with that function!
2714  */
2715 Limit *
2716 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount,
2717                    int offset_est, int count_est)
2718 {
2719         Limit      *node = makeNode(Limit);
2720         Plan       *plan = &node->plan;
2721
2722         copy_plan_costsize(plan, lefttree);
2723
2724         /*
2725          * Adjust the output rows count and costs according to the offset/limit.
2726          * This is only a cosmetic issue if we are at top level, but if we are
2727          * building a subquery then it's important to report correct info to the
2728          * outer planner.
2729          *
2730          * When the offset or count couldn't be estimated, use 10% of the
2731          * estimated number of rows emitted from the subplan.
2732          */
2733         if (offset_est != 0)
2734         {
2735                 double          offset_rows;
2736
2737                 if (offset_est > 0)
2738                         offset_rows = (double) offset_est;
2739                 else
2740                         offset_rows = clamp_row_est(lefttree->plan_rows * 0.10);
2741                 if (offset_rows > plan->plan_rows)
2742                         offset_rows = plan->plan_rows;
2743                 if (plan->plan_rows > 0)
2744                         plan->startup_cost +=
2745                                 (plan->total_cost - plan->startup_cost)
2746                                 * offset_rows / plan->plan_rows;
2747                 plan->plan_rows -= offset_rows;
2748                 if (plan->plan_rows < 1)
2749                         plan->plan_rows = 1;
2750         }
2751
2752         if (count_est != 0)
2753         {
2754                 double          count_rows;
2755
2756                 if (count_est > 0)
2757                         count_rows = (double) count_est;
2758                 else
2759                         count_rows = clamp_row_est(lefttree->plan_rows * 0.10);
2760                 if (count_rows > plan->plan_rows)
2761                         count_rows = plan->plan_rows;
2762                 if (plan->plan_rows > 0)
2763                         plan->total_cost = plan->startup_cost +
2764                                 (plan->total_cost - plan->startup_cost)
2765                                 * count_rows / plan->plan_rows;
2766                 plan->plan_rows = count_rows;
2767                 if (plan->plan_rows < 1)
2768                         plan->plan_rows = 1;
2769         }
2770
2771         plan->targetlist = copyObject(lefttree->targetlist);
2772         plan->qual = NIL;
2773         plan->lefttree = lefttree;
2774         plan->righttree = NULL;
2775
2776         node->limitOffset = limitOffset;
2777         node->limitCount = limitCount;
2778
2779         return node;
2780 }
2781
2782 Result *
2783 make_result(List *tlist,
2784                         Node *resconstantqual,
2785                         Plan *subplan)
2786 {
2787         Result     *node = makeNode(Result);
2788         Plan       *plan = &node->plan;
2789
2790         if (subplan)
2791                 copy_plan_costsize(plan, subplan);
2792         else
2793         {
2794                 plan->startup_cost = 0;
2795                 plan->total_cost = cpu_tuple_cost;
2796                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
2797                 plan->plan_width = 0;   /* XXX try to be smarter? */
2798         }
2799
2800         if (resconstantqual)
2801         {
2802                 QualCost        qual_cost;
2803
2804                 cost_qual_eval(&qual_cost, (List *) resconstantqual);
2805                 /* resconstantqual is evaluated once at startup */
2806                 plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
2807                 plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
2808         }
2809
2810         plan->targetlist = tlist;
2811         plan->qual = NIL;
2812         plan->lefttree = subplan;
2813         plan->righttree = NULL;
2814         node->resconstantqual = resconstantqual;
2815
2816         return node;
2817 }
2818
2819 /*
2820  * is_projection_capable_plan
2821  *              Check whether a given Plan node is able to do projection.
2822  */
2823 bool
2824 is_projection_capable_plan(Plan *plan)
2825 {
2826         /* Most plan types can project, so just list the ones that can't */
2827         switch (nodeTag(plan))
2828         {
2829                 case T_Hash:
2830                 case T_Material:
2831                 case T_Sort:
2832                 case T_Unique:
2833                 case T_SetOp:
2834                 case T_Limit:
2835                 case T_Append:
2836                         return false;
2837                 default:
2838                         break;
2839         }
2840         return true;
2841 }