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