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