granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/createplan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * createplan.c
   4  *        Routines to create the desired plan for processing a query.
   5  *        Planning is complete, we just need to convert the selected
   6  *        Path into a Plan.
   7  *
   8  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
   9  * Portions Copyright (c) 1994, Regents of the University of California
  10  *
  11  *
  12  * IDENTIFICATION
  13  *        $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.175 2004/12/31 22:00:08 pgsql 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         List       *tlist = NIL;
 265         int                     resdomno = 1;
 266         ListCell   *v;
 267
 268         foreach(v, rel->reltargetlist)
 269         {
 270                 /* Do we really need to copy here?      Not sure */
 271                 Var                *var = (Var *) copyObject(lfirst(v));
 272
 273                 tlist = lappend(tlist, create_tl_element(var, resdomno));
 274                 resdomno++;
 275         }
 276         return tlist;
 277 }
 278
 279 /*
 280  * use_physical_tlist
 281  *              Decide whether to use a tlist matching relation structure,
 282  *              rather than only those Vars actually referenced.
 283  */
 284 static bool
 285 use_physical_tlist(RelOptInfo *rel)
 286 {
 287         int                     i;
 288
 289         /*
 290          * Currently, can't do this for subquery or function scans.  (This is
 291          * mainly because we don't have an equivalent of build_physical_tlist
 292          * for them; worth adding?)
 293          */
 294         if (rel->rtekind != RTE_RELATION)
 295                 return false;
 296
 297         /*
 298          * Can't do it with inheritance cases either (mainly because Append
 299          * doesn't project).
 300          */
 301         if (rel->reloptkind != RELOPT_BASEREL)
 302                 return false;
 303
 304         /*
 305          * Can't do it if any system columns are requested, either.  (This
 306          * could possibly be fixed but would take some fragile assumptions in
 307          * setrefs.c, I think.)
 308          */
 309         for (i = rel->min_attr; i <= 0; i++)
 310         {
 311                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
 312                         return false;
 313         }
 314         return true;
 315 }
 316
 317 /*
 318  * disuse_physical_tlist
 319  *              Switch a plan node back to emitting only Vars actually referenced.
 320  *
 321  * If the plan node immediately above a scan would prefer to get only
 322  * needed Vars and not a physical tlist, it must call this routine to
 323  * undo the decision made by use_physical_tlist().      Currently, Hash, Sort,
 324  * and Material nodes want this, so they don't have to store useless columns.
 325  */
 326 static void
 327 disuse_physical_tlist(Plan *plan, Path *path)
 328 {
 329         /* Only need to undo it for path types handled by create_scan_plan() */
 330         switch (path->pathtype)
 331         {
 332                 case T_IndexScan:
 333                 case T_SeqScan:
 334                 case T_TidScan:
 335                 case T_SubqueryScan:
 336                 case T_FunctionScan:
 337                         plan->targetlist = build_relation_tlist(path->parent);
 338                         break;
 339                 default:
 340                         break;
 341         }
 342 }
 343
 344 /*
 345  * create_join_plan
 346  *        Create a join plan for 'best_path' and (recursively) plans for its
 347  *        inner and outer paths.
 348  *
 349  *        Returns a Plan node.
 350  */
 351 static Join *
 352 create_join_plan(Query *root, JoinPath *best_path)
 353 {
 354         Plan       *outer_plan;
 355         Plan       *inner_plan;
 356         Join       *plan;
 357
 358         outer_plan = create_plan(root, best_path->outerjoinpath);
 359         inner_plan = create_plan(root, best_path->innerjoinpath);
 360
 361         switch (best_path->path.pathtype)
 362         {
 363                 case T_MergeJoin:
 364                         plan = (Join *) create_mergejoin_plan(root,
 365                                                                                                   (MergePath *) best_path,
 366                                                                                                   outer_plan,
 367                                                                                                   inner_plan);
 368                         break;
 369                 case T_HashJoin:
 370                         plan = (Join *) create_hashjoin_plan(root,
 371                                                                                                  (HashPath *) best_path,
 372                                                                                                  outer_plan,
 373                                                                                                  inner_plan);
 374                         break;
 375                 case T_NestLoop:
 376                         plan = (Join *) create_nestloop_plan(root,
 377                                                                                                  (NestPath *) best_path,
 378                                                                                                  outer_plan,
 379                                                                                                  inner_plan);
 380                         break;
 381                 default:
 382                         elog(ERROR, "unrecognized node type: %d",
 383                                  (int) best_path->path.pathtype);
 384                         plan = NULL;            /* keep compiler quiet */
 385                         break;
 386         }
 387
 388 #ifdef NOT_USED
 389
 390         /*
 391          * * Expensive function pullups may have pulled local predicates *
 392          * into this path node.  Put them in the qpqual of the plan node. *
 393          * JMH, 6/15/92
 394          */
 395         if (get_loc_restrictinfo(best_path) != NIL)
 396                 set_qpqual((Plan) plan,
 397                                    list_concat(get_qpqual((Plan) plan),
 398                                    get_actual_clauses(get_loc_restrictinfo(best_path))));
 399 #endif
 400
 401         return plan;
 402 }
 403
 404 /*
 405  * create_append_plan
 406  *        Create an Append plan for 'best_path' and (recursively) plans
 407  *        for its subpaths.
 408  *
 409  *        Returns a Plan node.
 410  */
 411 static Append *
 412 create_append_plan(Query *root, AppendPath *best_path)
 413 {
 414         Append     *plan;
 415         List       *tlist = build_relation_tlist(best_path->path.parent);
 416         List       *subplans = NIL;
 417         ListCell   *subpaths;
 418
 419         foreach(subpaths, best_path->subpaths)
 420         {
 421                 Path       *subpath = (Path *) lfirst(subpaths);
 422
 423                 subplans = lappend(subplans, create_plan(root, subpath));
 424         }
 425
 426         plan = make_append(subplans, false, tlist);
 427
 428         return plan;
 429 }
 430
 431 /*
 432  * create_result_plan
 433  *        Create a Result plan for 'best_path' and (recursively) plans
 434  *        for its subpaths.
 435  *
 436  *        Returns a Plan node.
 437  */
 438 static Result *
 439 create_result_plan(Query *root, ResultPath *best_path)
 440 {
 441         Result     *plan;
 442         List       *tlist;
 443         List       *constclauses;
 444         Plan       *subplan;
 445
 446         if (best_path->path.parent)
 447                 tlist = build_relation_tlist(best_path->path.parent);
 448         else
 449                 tlist = NIL;                    /* will be filled in later */
 450
 451         if (best_path->subpath)
 452                 subplan = create_plan(root, best_path->subpath);
 453         else
 454                 subplan = NULL;
 455
 456         constclauses = order_qual_clauses(root, best_path->constantqual);
 457
 458         plan = make_result(tlist, (Node *) constclauses, subplan);
 459
 460         return plan;
 461 }
 462
 463 /*
 464  * create_material_plan
 465  *        Create a Material plan for 'best_path' and (recursively) plans
 466  *        for its subpaths.
 467  *
 468  *        Returns a Plan node.
 469  */
 470 static Material *
 471 create_material_plan(Query *root, MaterialPath *best_path)
 472 {
 473         Material   *plan;
 474         Plan       *subplan;
 475
 476         subplan = create_plan(root, best_path->subpath);
 477
 478         /* We don't want any excess columns in the materialized tuples */
 479         disuse_physical_tlist(subplan, best_path->subpath);
 480
 481         plan = make_material(subplan);
 482
 483         copy_path_costsize(&plan->plan, (Path *) best_path);
 484
 485         return plan;
 486 }
 487
 488 /*
 489  * create_unique_plan
 490  *        Create a Unique plan for 'best_path' and (recursively) plans
 491  *        for its subpaths.
 492  *
 493  *        Returns a Plan node.
 494  */
 495 static Plan *
 496 create_unique_plan(Query *root, UniquePath *best_path)
 497 {
 498         Plan       *plan;
 499         Plan       *subplan;
 500         List       *uniq_exprs;
 501         int                     numGroupCols;
 502         AttrNumber *groupColIdx;
 503         int                     groupColPos;
 504         List       *newtlist;
 505         int                     nextresno;
 506         bool            newitems;
 507         ListCell   *l;
 508
 509         subplan = create_plan(root, best_path->subpath);
 510
 511         /*
 512          * As constructed, the subplan has a "flat" tlist containing just the
 513          * Vars needed here and at upper levels.  The values we are supposed
 514          * to unique-ify may be expressions in these variables.  We have to
 515          * add any such expressions to the subplan's tlist.  We then build
 516          * control information showing which subplan output columns are to be
 517          * examined by the grouping step.  (Since we do not remove any
 518          * existing subplan outputs, not all the output columns may be used
 519          * for grouping.)
 520          *
 521          * Note: the reason we don't remove any subplan outputs is that there are
 522          * scenarios where a Var is needed at higher levels even though it is
 523          * not one of the nominal outputs of an IN clause.      Consider WHERE x
 524          * IN (SELECT y FROM t1,t2 WHERE y = z) Implied equality deduction
 525          * will generate an "x = z" clause, which may get used instead of "x =
 526          * y" in the upper join step.  Therefore the sub-select had better
 527          * deliver both y and z in its targetlist.      It is sufficient to
 528          * unique-ify on y, however.
 529          *
 530          * To find the correct list of values to unique-ify, we look in the
 531          * information saved for IN expressions.  If this code is ever used in
 532          * other scenarios, some other way of finding what to unique-ify will
 533          * be needed.
 534          */
 535         uniq_exprs = NIL;                       /* just to keep compiler quiet */
 536         foreach(l, root->in_info_list)
 537         {
 538                 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
 539
 540                 if (bms_equal(ininfo->righthand, best_path->path.parent->relids))
 541                 {
 542                         uniq_exprs = ininfo->sub_targetlist;
 543                         break;
 544                 }
 545         }
 546         if (l == NULL)                          /* fell out of loop? */
 547                 elog(ERROR, "could not find UniquePath in in_info_list");
 548
 549         /* set up to record positions of unique columns */
 550         numGroupCols = list_length(uniq_exprs);
 551         groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
 552         groupColPos = 0;
 553         /* not sure if tlist might be shared with other nodes, so copy */
 554         newtlist = copyObject(subplan->targetlist);
 555         nextresno = list_length(newtlist) + 1;
 556         newitems = false;
 557
 558         foreach(l, uniq_exprs)
 559         {
 560                 Node       *uniqexpr = lfirst(l);
 561                 TargetEntry *tle;
 562
 563                 tle = tlistentry_member(uniqexpr, newtlist);
 564                 if (!tle)
 565                 {
 566                         tle = makeTargetEntry(makeResdom(nextresno,
 567                                                                                          exprType(uniqexpr),
 568                                                                                          exprTypmod(uniqexpr),
 569                                                                                          NULL,
 570                                                                                          false),
 571                                                                   (Expr *) uniqexpr);
 572                         newtlist = lappend(newtlist, tle);
 573                         nextresno++;
 574                         newitems = true;
 575                 }
 576                 groupColIdx[groupColPos++] = tle->resdom->resno;
 577         }
 578
 579         if (newitems)
 580         {
 581                 /*
 582                  * If the top plan node can't do projections, we need to add a
 583                  * Result node to help it along.
 584                  */
 585                 if (!is_projection_capable_plan(subplan))
 586                         subplan = (Plan *) make_result(newtlist, NULL, subplan);
 587                 else
 588                         subplan->targetlist = newtlist;
 589         }
 590
 591         /* Done if we don't need to do any actual unique-ifying */
 592         if (best_path->umethod == UNIQUE_PATH_NOOP)
 593                 return subplan;
 594
 595         if (best_path->umethod == UNIQUE_PATH_HASH)
 596         {
 597                 long            numGroups;
 598
 599                 numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
 600
 601                 plan = (Plan *) make_agg(root,
 602                                                                  copyObject(subplan->targetlist),
 603                                                                  NIL,
 604                                                                  AGG_HASHED,
 605                                                                  numGroupCols,
 606                                                                  groupColIdx,
 607                                                                  numGroups,
 608                                                                  0,
 609                                                                  subplan);
 610         }
 611         else
 612         {
 613                 List       *sortList = NIL;
 614
 615                 for (groupColPos = 0; groupColPos < numGroupCols; groupColPos++)
 616                 {
 617                         TargetEntry *tle;
 618
 619                         tle = get_tle_by_resno(subplan->targetlist,
 620                                                                    groupColIdx[groupColPos]);
 621                         Assert(tle != NULL);
 622                         sortList = addTargetToSortList(NULL, tle,
 623                                                                                    sortList, subplan->targetlist,
 624                                                                                    SORTBY_ASC, NIL, false);
 625                 }
 626                 plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
 627                 plan = (Plan *) make_unique(plan, sortList);
 628         }
 629
 630         /* Adjust output size estimate (other fields should be OK already) */
 631         plan->plan_rows = best_path->rows;
 632
 633         return plan;
 634 }
 635
 636
 637 /*****************************************************************************
 638  *
 639  *      BASE-RELATION SCAN METHODS
 640  *
 641  *****************************************************************************/
 642
 643
 644 /*
 645  * create_seqscan_plan
 646  *       Returns a seqscan plan for the base relation scanned by 'best_path'
 647  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 648  */
 649 static SeqScan *
 650 create_seqscan_plan(Query *root, Path *best_path,
 651                                         List *tlist, List *scan_clauses)
 652 {
 653         SeqScan    *scan_plan;
 654         Index           scan_relid = best_path->parent->relid;
 655
 656         /* it should be a base rel... */
 657         Assert(scan_relid > 0);
 658         Assert(best_path->parent->rtekind == RTE_RELATION);
 659
 660         /* Reduce RestrictInfo list to bare expressions */
 661         scan_clauses = get_actual_clauses(scan_clauses);
 662
 663         /* Sort clauses into best execution order */
 664         scan_clauses = order_qual_clauses(root, scan_clauses);
 665
 666         scan_plan = make_seqscan(tlist,
 667                                                          scan_clauses,
 668                                                          scan_relid);
 669
 670         copy_path_costsize(&scan_plan->plan, best_path);
 671
 672         return scan_plan;
 673 }
 674
 675 /*
 676  * create_indexscan_plan
 677  *        Returns a indexscan plan for the base relation scanned by 'best_path'
 678  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 679  *
 680  * The indexquals list of the path contains a sublist of implicitly-ANDed
 681  * qual conditions for each scan of the index(es); if there is more than one
 682  * scan then the retrieved tuple sets are ORed together.  The indexquals
 683  * and indexinfo lists must have the same length, ie, the number of scans
 684  * that will occur.  Note it is possible for a qual condition sublist
 685  * to be empty --- then no index restrictions will be applied during that
 686  * scan.
 687  */
 688 static IndexScan *
 689 create_indexscan_plan(Query *root,
 690                                           IndexPath *best_path,
 691                                           List *tlist,
 692                                           List *scan_clauses)
 693 {
 694         List       *indxquals = best_path->indexquals;
 695         Index           baserelid = best_path->path.parent->relid;
 696         List       *qpqual;
 697         Expr       *indxqual_or_expr = NULL;
 698         List       *stripped_indxquals;
 699         List       *fixed_indxquals;
 700         List       *indxstrategy;
 701         List       *indxsubtype;
 702         List       *indxlossy;
 703         List       *indexids;
 704         ListCell   *l;
 705         IndexScan  *scan_plan;
 706
 707         /* it should be a base rel... */
 708         Assert(baserelid > 0);
 709         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 710
 711         /*
 712          * If this is a innerjoin scan, the indexclauses will contain join
 713          * clauses that are not present in scan_clauses (since the passed-in
 714          * value is just the rel's baserestrictinfo list).  We must add these
 715          * clauses to scan_clauses to ensure they get checked.  In most cases
 716          * we will remove the join clauses again below, but if a join clause
 717          * contains a special operator, we need to make sure it gets into the
 718          * scan_clauses.
 719          */
 720         if (best_path->isjoininner)
 721         {
 722                 /*
 723                  * We don't currently support OR indexscans in joins, so we only
 724                  * need to worry about the plain AND case.      Also, pointer
 725                  * comparison should be enough to determine RestrictInfo matches.
 726                  */
 727                 Assert(list_length(best_path->indexclauses) == 1);
 728                 scan_clauses = list_union_ptr(scan_clauses,
 729                                                          (List *) linitial(best_path->indexclauses));
 730         }
 731
 732         /* Reduce RestrictInfo list to bare expressions */
 733         scan_clauses = get_actual_clauses(scan_clauses);
 734
 735         /* Sort clauses into best execution order */
 736         scan_clauses = order_qual_clauses(root, scan_clauses);
 737
 738         /* Build list of index OIDs */
 739         indexids = NIL;
 740         foreach(l, best_path->indexinfo)
 741         {
 742                 IndexOptInfo *index = (IndexOptInfo *) lfirst(l);
 743
 744                 indexids = lappend_oid(indexids, index->indexoid);
 745         }
 746
 747         /*
 748          * Build "stripped" indexquals structure (no RestrictInfos) to pass to
 749          * executor as indxqualorig
 750          */
 751         stripped_indxquals = NIL;
 752         foreach(l, indxquals)
 753         {
 754                 List       *andlist = (List *) lfirst(l);
 755
 756                 stripped_indxquals = lappend(stripped_indxquals,
 757                                                                          get_actual_clauses(andlist));
 758         }
 759
 760         /*
 761          * The qpqual list must contain all restrictions not automatically
 762          * handled by the index.  All the predicates in the indexquals will be
 763          * checked (either by the index itself, or by nodeIndexscan.c), but if
 764          * there are any "special" operators involved then they must be added
 765          * to qpqual.  The upshot is that qpquals must contain scan_clauses
 766          * minus whatever appears in indxquals.
 767          */
 768         if (list_length(indxquals) > 1)
 769         {
 770                 /*
 771                  * Build an expression representation of the indexqual, expanding
 772                  * the implicit OR and AND semantics of the first- and
 773                  * second-level lists.  (The odds that this will exactly match any
 774                  * scan_clause are not great; perhaps we need more smarts here.)
 775                  */
 776                 indxqual_or_expr = make_expr_from_indexclauses(indxquals);
 777                 qpqual = list_difference(scan_clauses, list_make1(indxqual_or_expr));
 778         }
 779         else
 780         {
 781                 /*
 782                  * Here, we can simply treat the first sublist as an independent
 783                  * set of qual expressions, since there is no top-level OR
 784                  * behavior.
 785                  */
 786                 Assert(stripped_indxquals != NIL);
 787                 qpqual = list_difference(scan_clauses, linitial(stripped_indxquals));
 788         }
 789
 790         /*
 791          * The executor needs a copy with the indexkey on the left of each
 792          * clause and with index attr numbers substituted for table ones. This
 793          * pass also gets strategy info and looks for "lossy" operators.
 794          */
 795         fix_indxqual_references(indxquals, best_path,
 796                                                         &fixed_indxquals,
 797                                                         &indxstrategy, &indxsubtype, &indxlossy);
 798
 799         /* Finally ready to build the plan node */
 800         scan_plan = make_indexscan(tlist,
 801                                                            qpqual,
 802                                                            baserelid,
 803                                                            indexids,
 804                                                            fixed_indxquals,
 805                                                            stripped_indxquals,
 806                                                            indxstrategy,
 807                                                            indxsubtype,
 808                                                            indxlossy,
 809                                                            best_path->indexscandir);
 810
 811         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 812         /* use the indexscan-specific rows estimate, not the parent rel's */
 813         scan_plan->scan.plan.plan_rows = best_path->rows;
 814
 815         return scan_plan;
 816 }
 817
 818 /*
 819  * create_tidscan_plan
 820  *       Returns a tidscan plan for the base relation scanned by 'best_path'
 821  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 822  */
 823 static TidScan *
 824 create_tidscan_plan(Query *root, TidPath *best_path,
 825                                         List *tlist, List *scan_clauses)
 826 {
 827         TidScan    *scan_plan;
 828         Index           scan_relid = best_path->path.parent->relid;
 829
 830         /* it should be a base rel... */
 831         Assert(scan_relid > 0);
 832         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 833
 834         /* Reduce RestrictInfo list to bare expressions */
 835         scan_clauses = get_actual_clauses(scan_clauses);
 836
 837         /* Sort clauses into best execution order */
 838         scan_clauses = order_qual_clauses(root, scan_clauses);
 839
 840         scan_plan = make_tidscan(tlist,
 841                                                          scan_clauses,
 842                                                          scan_relid,
 843                                                          best_path->tideval);
 844
 845         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 846
 847         return scan_plan;
 848 }
 849
 850 /*
 851  * create_subqueryscan_plan
 852  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
 853  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 854  */
 855 static SubqueryScan *
 856 create_subqueryscan_plan(Query *root, Path *best_path,
 857                                                  List *tlist, List *scan_clauses)
 858 {
 859         SubqueryScan *scan_plan;
 860         Index           scan_relid = best_path->parent->relid;
 861
 862         /* it should be a subquery base rel... */
 863         Assert(scan_relid > 0);
 864         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
 865
 866         /* Reduce RestrictInfo list to bare expressions */
 867         scan_clauses = get_actual_clauses(scan_clauses);
 868
 869         /* Sort clauses into best execution order */
 870         scan_clauses = order_qual_clauses(root, scan_clauses);
 871
 872         scan_plan = make_subqueryscan(tlist,
 873                                                                   scan_clauses,
 874                                                                   scan_relid,
 875                                                                   best_path->parent->subplan);
 876
 877         copy_path_costsize(&scan_plan->scan.plan, best_path);
 878
 879         return scan_plan;
 880 }
 881
 882 /*
 883  * create_functionscan_plan
 884  *       Returns a functionscan plan for the base relation scanned by 'best_path'
 885  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 886  */
 887 static FunctionScan *
 888 create_functionscan_plan(Query *root, Path *best_path,
 889                                                  List *tlist, List *scan_clauses)
 890 {
 891         FunctionScan *scan_plan;
 892         Index           scan_relid = best_path->parent->relid;
 893
 894         /* it should be a function base rel... */
 895         Assert(scan_relid > 0);
 896         Assert(best_path->parent->rtekind == RTE_FUNCTION);
 897
 898         /* Reduce RestrictInfo list to bare expressions */
 899         scan_clauses = get_actual_clauses(scan_clauses);
 900
 901         /* Sort clauses into best execution order */
 902         scan_clauses = order_qual_clauses(root, scan_clauses);
 903
 904         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid);
 905
 906         copy_path_costsize(&scan_plan->scan.plan, best_path);
 907
 908         return scan_plan;
 909 }
 910
 911 /*****************************************************************************
 912  *
 913  *      JOIN METHODS
 914  *
 915  *****************************************************************************/
 916
 917 static NestLoop *
 918 create_nestloop_plan(Query *root,
 919                                          NestPath *best_path,
 920                                          Plan *outer_plan,
 921                                          Plan *inner_plan)
 922 {
 923         List       *tlist = build_relation_tlist(best_path->path.parent);
 924         List       *joinrestrictclauses = best_path->joinrestrictinfo;
 925         List       *joinclauses;
 926         List       *otherclauses;
 927         NestLoop   *join_plan;
 928
 929         if (IsA(best_path->innerjoinpath, IndexPath))
 930         {
 931                 /*
 932                  * An index is being used to reduce the number of tuples scanned
 933                  * in the inner relation.  If there are join clauses being used
 934                  * with the index, we may remove those join clauses from the list
 935                  * of clauses that have to be checked as qpquals at the join node
 936                  * --- but only if there's just one indexscan in the inner path
 937                  * (otherwise, several different sets of clauses are being ORed
 938                  * together).
 939                  *
 940                  * We can also remove any join clauses that are redundant with those
 941                  * being used in the index scan; prior redundancy checks will not
 942                  * have caught this case because the join clauses would never have
 943                  * been put in the same joininfo list.
 944                  *
 945                  * We can skip this if the index path is an ordinary indexpath and
 946                  * not a special innerjoin path.
 947                  */
 948                 IndexPath  *innerpath = (IndexPath *) best_path->innerjoinpath;
 949                 List       *indexclauses = innerpath->indexclauses;
 950
 951                 if (innerpath->isjoininner &&
 952                         list_length(indexclauses) == 1)         /* single indexscan? */
 953                 {
 954                         joinrestrictclauses =
 955                                 select_nonredundant_join_clauses(root,
 956                                                                                                  joinrestrictclauses,
 957                                                                                                  linitial(indexclauses),
 958                                                                                                  best_path->jointype);
 959                 }
 960         }
 961
 962         /* Get the join qual clauses (in plain expression form) */
 963         if (IS_OUTER_JOIN(best_path->jointype))
 964         {
 965                 get_actual_join_clauses(joinrestrictclauses,
 966                                                                 &joinclauses, &otherclauses);
 967         }
 968         else
 969         {
 970                 /* We can treat all clauses alike for an inner join */
 971                 joinclauses = get_actual_clauses(joinrestrictclauses);
 972                 otherclauses = NIL;
 973         }
 974
 975         /* Sort clauses into best execution order */
 976         joinclauses = order_qual_clauses(root, joinclauses);
 977         otherclauses = order_qual_clauses(root, otherclauses);
 978
 979         join_plan = make_nestloop(tlist,
 980                                                           joinclauses,
 981                                                           otherclauses,
 982                                                           outer_plan,
 983                                                           inner_plan,
 984                                                           best_path->jointype);
 985
 986         copy_path_costsize(&join_plan->join.plan, &best_path->path);
 987
 988         return join_plan;
 989 }
 990
 991 static MergeJoin *
 992 create_mergejoin_plan(Query *root,
 993                                           MergePath *best_path,
 994                                           Plan *outer_plan,
 995                                           Plan *inner_plan)
 996 {
 997         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
 998         List       *joinclauses;
 999         List       *otherclauses;
1000         List       *mergeclauses;
1001         MergeJoin  *join_plan;
1002
1003         /* Get the join qual clauses (in plain expression form) */
1004         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1005         {
1006                 get_actual_join_clauses(best_path->jpath.joinrestrictinfo,
1007                                                                 &joinclauses, &otherclauses);
1008         }
1009         else
1010         {
1011                 /* We can treat all clauses alike for an inner join */
1012                 joinclauses = get_actual_clauses(best_path->jpath.joinrestrictinfo);
1013                 otherclauses = NIL;
1014         }
1015
1016         /*
1017          * Remove the mergeclauses from the list of join qual clauses, leaving
1018          * the list of quals that must be checked as qpquals.
1019          */
1020         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
1021         joinclauses = list_difference(joinclauses, mergeclauses);
1022
1023         /*
1024          * Rearrange mergeclauses, if needed, so that the outer variable is
1025          * always on the left.
1026          */
1027         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
1028                                                  best_path->jpath.outerjoinpath->parent->relids);
1029
1030         /* Sort clauses into best execution order */
1031         /* NB: do NOT reorder the mergeclauses */
1032         joinclauses = order_qual_clauses(root, joinclauses);
1033         otherclauses = order_qual_clauses(root, otherclauses);
1034
1035         /*
1036          * Create explicit sort nodes for the outer and inner join paths if
1037          * necessary.  The sort cost was already accounted for in the path.
1038          * Make sure there are no excess columns in the inputs if sorting.
1039          */
1040         if (best_path->outersortkeys)
1041         {
1042                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
1043                 outer_plan = (Plan *)
1044                         make_sort_from_pathkeys(root,
1045                                                                         outer_plan,
1046                                                                         best_path->outersortkeys);
1047         }
1048
1049         if (best_path->innersortkeys)
1050         {
1051                 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1052                 inner_plan = (Plan *)
1053                         make_sort_from_pathkeys(root,
1054                                                                         inner_plan,
1055                                                                         best_path->innersortkeys);
1056         }
1057
1058         /*
1059          * Now we can build the mergejoin node.
1060          */
1061         join_plan = make_mergejoin(tlist,
1062                                                            joinclauses,
1063                                                            otherclauses,
1064                                                            mergeclauses,
1065                                                            outer_plan,
1066                                                            inner_plan,
1067                                                            best_path->jpath.jointype);
1068
1069         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1070
1071         return join_plan;
1072 }
1073
1074 static HashJoin *
1075 create_hashjoin_plan(Query *root,
1076                                          HashPath *best_path,
1077                                          Plan *outer_plan,
1078                                          Plan *inner_plan)
1079 {
1080         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1081         List       *joinclauses;
1082         List       *otherclauses;
1083         List       *hashclauses;
1084         HashJoin   *join_plan;
1085         Hash       *hash_plan;
1086
1087         /* Get the join qual clauses (in plain expression form) */
1088         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1089         {
1090                 get_actual_join_clauses(best_path->jpath.joinrestrictinfo,
1091                                                                 &joinclauses, &otherclauses);
1092         }
1093         else
1094         {
1095                 /* We can treat all clauses alike for an inner join */
1096                 joinclauses = get_actual_clauses(best_path->jpath.joinrestrictinfo);
1097                 otherclauses = NIL;
1098         }
1099
1100         /*
1101          * Remove the hashclauses from the list of join qual clauses, leaving
1102          * the list of quals that must be checked as qpquals.
1103          */
1104         hashclauses = get_actual_clauses(best_path->path_hashclauses);
1105         joinclauses = list_difference(joinclauses, hashclauses);
1106
1107         /*
1108          * Rearrange hashclauses, if needed, so that the outer variable is
1109          * always on the left.
1110          */
1111         hashclauses = get_switched_clauses(best_path->path_hashclauses,
1112                                                  best_path->jpath.outerjoinpath->parent->relids);
1113
1114         /* Sort clauses into best execution order */
1115         joinclauses = order_qual_clauses(root, joinclauses);
1116         otherclauses = order_qual_clauses(root, otherclauses);
1117         hashclauses = order_qual_clauses(root, hashclauses);
1118
1119         /* We don't want any excess columns in the hashed tuples */
1120         disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1121
1122         /*
1123          * Build the hash node and hash join node.
1124          */
1125         hash_plan = make_hash(inner_plan);
1126         join_plan = make_hashjoin(tlist,
1127                                                           joinclauses,
1128                                                           otherclauses,
1129                                                           hashclauses,
1130                                                           outer_plan,
1131                                                           (Plan *) hash_plan,
1132                                                           best_path->jpath.jointype);
1133
1134         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1135
1136         return join_plan;
1137 }
1138
1139
1140 /*****************************************************************************
1141  *
1142  *      SUPPORTING ROUTINES
1143  *
1144  *****************************************************************************/
1145
1146 /*
1147  * fix_indxqual_references
1148  *        Adjust indexqual clauses to the form the executor's indexqual
1149  *        machinery needs, and check for recheckable (lossy) index conditions.
1150  *
1151  * We have four tasks here:
1152  *      * Remove RestrictInfo nodes from the input clauses.
1153  *      * Index keys must be represented by Var nodes with varattno set to the
1154  *        index's attribute number, not the attribute number in the original rel.
1155  *      * If the index key is on the right, commute the clause to put it on the
1156  *        left.  (Someday the executor might not need this, but for now it does.)
1157  *      * We must construct lists of operator strategy numbers, subtypes, and
1158  *        recheck (lossy-operator) flags for the top-level operators of each
1159  *        index clause.
1160  *
1161  * Both the input list and the "fixed" output list have the form of lists of
1162  * sublists of qual clauses --- the top-level list has one entry for each
1163  * indexscan to be performed.  The semantics are OR-of-ANDs.  Note however
1164  * that the input list contains RestrictInfos, while the output list doesn't.
1165  *
1166  * fixed_indexquals receives a modified copy of the indexqual list --- the
1167  * original is not changed.  Note also that the copy shares no substructure
1168  * with the original; this is needed in case there is a subplan in it (we need
1169  * two separate copies of the subplan tree, or things will go awry).
1170  *
1171  * indxstrategy receives a list of integer sublists of strategy numbers.
1172  * indxsubtype receives a list of OID sublists of strategy subtypes.
1173  * indxlossy receives a list of integer sublists of lossy-operator booleans.
1174  */
1175 static void
1176 fix_indxqual_references(List *indexquals, IndexPath *index_path,
1177                                                 List **fixed_indexquals,
1178                                                 List **indxstrategy,
1179                                                 List **indxsubtype,
1180                                                 List **indxlossy)
1181 {
1182         Relids          baserelids = index_path->path.parent->relids;
1183         int                     baserelid = index_path->path.parent->relid;
1184         List       *index_info = index_path->indexinfo;
1185         ListCell   *iq,
1186                            *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
1284                  * to get its strategy numbers and the recheck indicator.  This
1285                  * also double-checks that we found an operator matching the
1286                  * index.
1287                  */
1288                 get_op_opclass_properties(newclause->opno, opclass,
1289                                                                   &stratno, &stratsubtype, &recheck);
1290
1291                 *strategy = lappend_int(*strategy, stratno);
1292                 *subtype = lappend_oid(*subtype, stratsubtype);
1293                 *lossy = lappend_int(*lossy, (int) recheck);
1294         }
1295 }
1296
1297 static Node *
1298 fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index,
1299                                          Oid *opclass)
1300 {
1301         /*
1302          * We represent index keys by Var nodes having the varno of the base
1303          * table but varattno equal to the index's attribute number (index
1304          * column position).  This is a bit hokey ... would be cleaner to use
1305          * a special-purpose node type that could not be mistaken for a
1306          * regular Var.  But it will do for now.
1307          */
1308         Var                *result;
1309         int                     pos;
1310         ListCell   *indexpr_item;
1311
1312         /*
1313          * Remove any binary-compatible relabeling of the indexkey
1314          */
1315         if (IsA(node, RelabelType))
1316                 node = (Node *) ((RelabelType *) node)->arg;
1317
1318         if (IsA(node, Var) &&
1319                 ((Var *) node)->varno == baserelid)
1320         {
1321                 /* Try to match against simple index columns */
1322                 int                     varatt = ((Var *) node)->varattno;
1323
1324                 if (varatt != 0)
1325                 {
1326                         for (pos = 0; pos < index->ncolumns; pos++)
1327                         {
1328                                 if (index->indexkeys[pos] == varatt)
1329                                 {
1330                                         result = (Var *) copyObject(node);
1331                                         result->varattno = pos + 1;
1332                                         /* return the correct opclass, too */
1333                                         *opclass = index->classlist[pos];
1334                                         return (Node *) result;
1335                                 }
1336                         }
1337                 }
1338         }
1339
1340         /* Try to match against index expressions */
1341         indexpr_item = list_head(index->indexprs);
1342         for (pos = 0; pos < index->ncolumns; pos++)
1343         {
1344                 if (index->indexkeys[pos] == 0)
1345                 {
1346                         Node       *indexkey;
1347
1348                         if (indexpr_item == NULL)
1349                                 elog(ERROR, "too few entries in indexprs list");
1350                         indexkey = (Node *) lfirst(indexpr_item);
1351                         if (indexkey && IsA(indexkey, RelabelType))
1352                                 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
1353                         if (equal(node, indexkey))
1354                         {
1355                                 /* Found a match */
1356                                 result = makeVar(baserelid, pos + 1,
1357                                                                  exprType(lfirst(indexpr_item)), -1,
1358                                                                  0);
1359                                 /* return the correct opclass, too */
1360                                 *opclass = index->classlist[pos];
1361                                 return (Node *) result;
1362                         }
1363                         indexpr_item = lnext(indexpr_item);
1364                 }
1365         }
1366
1367         /* Ooops... */
1368         elog(ERROR, "node is not an index attribute");
1369         return NULL;                            /* keep compiler quiet */
1370 }
1371
1372 /*
1373  * get_switched_clauses
1374  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
1375  *        extract the bare clauses, and rearrange the elements within the
1376  *        clauses, if needed, so the outer join variable is on the left and
1377  *        the inner is on the right.  The original data structure is not touched;
1378  *        a modified list is returned.
1379  */
1380 static List *
1381 get_switched_clauses(List *clauses, Relids outerrelids)
1382 {
1383         List       *t_list = NIL;
1384         ListCell   *l;
1385
1386         foreach(l, clauses)
1387         {
1388                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
1389                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
1390
1391                 Assert(is_opclause(clause));
1392                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
1393                 {
1394                         /*
1395                          * Duplicate just enough of the structure to allow commuting
1396                          * the clause without changing the original list.  Could use
1397                          * copyObject, but a complete deep copy is overkill.
1398                          */
1399                         OpExpr     *temp = makeNode(OpExpr);
1400
1401                         temp->opno = clause->opno;
1402                         temp->opfuncid = InvalidOid;
1403                         temp->opresulttype = clause->opresulttype;
1404                         temp->opretset = clause->opretset;
1405                         temp->args = list_copy(clause->args);
1406                         /* Commute it --- note this modifies the temp node in-place. */
1407                         CommuteClause(temp);
1408                         t_list = lappend(t_list, temp);
1409                 }
1410                 else
1411                         t_list = lappend(t_list, clause);
1412         }
1413         return t_list;
1414 }
1415
1416 /*
1417  * order_qual_clauses
1418  *              Given a list of qual clauses that will all be evaluated at the same
1419  *              plan node, sort the list into the order we want to check the quals
1420  *              in at runtime.
1421  *
1422  * Ideally the order should be driven by a combination of execution cost and
1423  * selectivity, but unfortunately we have so little information about
1424  * execution cost of operators that it's really hard to do anything smart.
1425  * For now, we just move any quals that contain SubPlan references (but not
1426  * InitPlan references) to the end of the list.
1427  */
1428 static List *
1429 order_qual_clauses(Query *root, List *clauses)
1430 {
1431         List       *nosubplans;
1432         List       *withsubplans;
1433         ListCell   *l;
1434
1435         /* No need to work hard if the query is subselect-free */
1436         if (!root->hasSubLinks)
1437                 return clauses;
1438
1439         nosubplans = NIL;
1440         withsubplans = NIL;
1441         foreach(l, clauses)
1442         {
1443                 Node       *clause = (Node *) lfirst(l);
1444
1445                 if (contain_subplans(clause))
1446                         withsubplans = lappend(withsubplans, clause);
1447                 else
1448                         nosubplans = lappend(nosubplans, clause);
1449         }
1450
1451         return list_concat(nosubplans, withsubplans);
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         /*
1843          * We will need at most list_length(pathkeys) sort columns; possibly
1844          * less
1845          */
1846         numsortkeys = list_length(pathkeys);
1847         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
1848         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
1849
1850         numsortkeys = 0;
1851
1852         foreach(i, pathkeys)
1853         {
1854                 List       *keysublist = (List *) lfirst(i);
1855                 PathKeyItem *pathkey = NULL;
1856                 Resdom     *resdom = NULL;
1857                 ListCell   *j;
1858
1859                 /*
1860                  * We can sort by any one of the sort key items listed in this
1861                  * sublist.  For now, we take the first one that corresponds to an
1862                  * available Var in the tlist.  If there isn't any, use the first
1863                  * one that is an expression in the input's vars.
1864                  *
1865                  * XXX if we have a choice, is there any way of figuring out which
1866                  * might be cheapest to execute?  (For example, int4lt is likely
1867                  * much cheaper to execute than numericlt, but both might appear
1868                  * in the same pathkey sublist...)      Not clear that we ever will
1869                  * have a choice in practice, so it may not matter.
1870                  */
1871                 foreach(j, keysublist)
1872                 {
1873                         pathkey = (PathKeyItem *) lfirst(j);
1874                         Assert(IsA(pathkey, PathKeyItem));
1875                         resdom = tlist_member(pathkey->key, tlist);
1876                         if (resdom)
1877                                 break;
1878                 }
1879                 if (!resdom)
1880                 {
1881                         /* No matching Var; look for a computable expression */
1882                         foreach(j, keysublist)
1883                         {
1884                                 List       *exprvars;
1885                                 ListCell   *k;
1886
1887                                 pathkey = (PathKeyItem *) lfirst(j);
1888                                 exprvars = pull_var_clause(pathkey->key, false);
1889                                 foreach(k, exprvars)
1890                                 {
1891                                         if (!tlist_member(lfirst(k), tlist))
1892                                                 break;
1893                                 }
1894                                 list_free(exprvars);
1895                                 if (!k)
1896                                         break;          /* found usable expression */
1897                         }
1898                         if (!j)
1899                                 elog(ERROR, "could not find pathkey item to sort");
1900
1901                         /*
1902                          * Do we need to insert a Result node?
1903                          */
1904                         if (!is_projection_capable_plan(lefttree))
1905                         {
1906                                 tlist = copyObject(tlist);
1907                                 lefttree = (Plan *) make_result(tlist, NULL, lefttree);
1908                         }
1909
1910                         /*
1911                          * Add resjunk entry to input's tlist
1912                          */
1913                         resdom = makeResdom(list_length(tlist) + 1,
1914                                                                 exprType(pathkey->key),
1915                                                                 exprTypmod(pathkey->key),
1916                                                                 NULL,
1917                                                                 true);
1918                         tlist = lappend(tlist,
1919                                                         makeTargetEntry(resdom,
1920                                                                                         (Expr *) pathkey->key));
1921                         lefttree->targetlist = tlist;           /* just in case NIL before */
1922                 }
1923
1924                 /*
1925                  * The column might already be selected as a sort key, if the
1926                  * pathkeys contain duplicate entries.  (This can happen in
1927                  * scenarios where multiple mergejoinable clauses mention the same
1928                  * var, for example.)  So enter it only once in the sort arrays.
1929                  */
1930                 numsortkeys = add_sort_column(resdom->resno, pathkey->sortop,
1931                                                                  numsortkeys, sortColIdx, sortOperators);
1932         }
1933
1934         Assert(numsortkeys > 0);
1935
1936         return make_sort(root, lefttree, numsortkeys,
1937                                          sortColIdx, sortOperators);
1938 }
1939
1940 /*
1941  * make_sort_from_sortclauses
1942  *        Create sort plan to sort according to given sortclauses
1943  *
1944  *        'sortcls' is a list of SortClauses
1945  *        'lefttree' is the node which yields input tuples
1946  */
1947 Sort *
1948 make_sort_from_sortclauses(Query *root, List *sortcls, Plan *lefttree)
1949 {
1950         List       *sub_tlist = lefttree->targetlist;
1951         ListCell   *l;
1952         int                     numsortkeys;
1953         AttrNumber *sortColIdx;
1954         Oid                *sortOperators;
1955
1956         /*
1957          * We will need at most list_length(sortcls) sort columns; possibly
1958          * less
1959          */
1960         numsortkeys = list_length(sortcls);
1961         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
1962         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
1963
1964         numsortkeys = 0;
1965
1966         foreach(l, sortcls)
1967         {
1968                 SortClause *sortcl = (SortClause *) lfirst(l);
1969                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
1970
1971                 /*
1972                  * Check for the possibility of duplicate order-by clauses --- the
1973                  * parser should have removed 'em, but no point in sorting
1974                  * redundantly.
1975                  */
1976                 numsortkeys = add_sort_column(tle->resdom->resno, sortcl->sortop,
1977                                                                  numsortkeys, sortColIdx, sortOperators);
1978         }
1979
1980         Assert(numsortkeys > 0);
1981
1982         return make_sort(root, lefttree, numsortkeys,
1983                                          sortColIdx, sortOperators);
1984 }
1985
1986 /*
1987  * make_sort_from_groupcols
1988  *        Create sort plan to sort based on grouping columns
1989  *
1990  * 'groupcls' is the list of GroupClauses
1991  * 'grpColIdx' gives the column numbers to use
1992  *
1993  * This might look like it could be merged with make_sort_from_sortclauses,
1994  * but presently we *must* use the grpColIdx[] array to locate sort columns,
1995  * because the child plan's tlist is not marked with ressortgroupref info
1996  * appropriate to the grouping node.  So, only the sortop is used from the
1997  * GroupClause entries.
1998  */
1999 Sort *
2000 make_sort_from_groupcols(Query *root,
2001                                                  List *groupcls,
2002                                                  AttrNumber *grpColIdx,
2003                                                  Plan *lefttree)
2004 {
2005         List       *sub_tlist = lefttree->targetlist;
2006         int                     grpno = 0;
2007         ListCell   *l;
2008         int                     numsortkeys;
2009         AttrNumber *sortColIdx;
2010         Oid                *sortOperators;
2011
2012         /*
2013          * We will need at most list_length(groupcls) sort columns; possibly
2014          * less
2015          */
2016         numsortkeys = list_length(groupcls);
2017         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2018         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2019
2020         numsortkeys = 0;
2021
2022         foreach(l, groupcls)
2023         {
2024                 GroupClause *grpcl = (GroupClause *) lfirst(l);
2025                 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
2026
2027                 /*
2028                  * Check for the possibility of duplicate group-by clauses --- the
2029                  * parser should have removed 'em, but no point in sorting
2030                  * redundantly.
2031                  */
2032                 numsortkeys = add_sort_column(tle->resdom->resno, grpcl->sortop,
2033                                                                  numsortkeys, sortColIdx, sortOperators);
2034                 grpno++;
2035         }
2036
2037         Assert(numsortkeys > 0);
2038
2039         return make_sort(root, lefttree, numsortkeys,
2040                                          sortColIdx, sortOperators);
2041 }
2042
2043 Material *
2044 make_material(Plan *lefttree)
2045 {
2046         Material   *node = makeNode(Material);
2047         Plan       *plan = &node->plan;
2048
2049         /* cost should be inserted by caller */
2050         plan->targetlist = copyObject(lefttree->targetlist);
2051         plan->qual = NIL;
2052         plan->lefttree = lefttree;
2053         plan->righttree = NULL;
2054
2055         return node;
2056 }
2057
2058 /*
2059  * materialize_finished_plan: stick a Material node atop a completed plan
2060  *
2061  * There are a couple of places where we want to attach a Material node
2062  * after completion of subquery_planner().      This currently requires hackery.
2063  * Since subquery_planner has already run SS_finalize_plan on the subplan
2064  * tree, we have to kluge up parameter lists for the Material node.
2065  * Possibly this could be fixed by postponing SS_finalize_plan processing
2066  * until setrefs.c is run?
2067  */
2068 Plan *
2069 materialize_finished_plan(Plan *subplan)
2070 {
2071         Plan       *matplan;
2072         Path            matpath;                /* dummy for result of cost_material */
2073
2074         matplan = (Plan *) make_material(subplan);
2075
2076         /* Set cost data */
2077         cost_material(&matpath,
2078                                   subplan->total_cost,
2079                                   subplan->plan_rows,
2080                                   subplan->plan_width);
2081         matplan->startup_cost = matpath.startup_cost;
2082         matplan->total_cost = matpath.total_cost;
2083         matplan->plan_rows = subplan->plan_rows;
2084         matplan->plan_width = subplan->plan_width;
2085
2086         /* parameter kluge --- see comments above */
2087         matplan->extParam = bms_copy(subplan->extParam);
2088         matplan->allParam = bms_copy(subplan->allParam);
2089
2090         return matplan;
2091 }
2092
2093 Agg *
2094 make_agg(Query *root, List *tlist, List *qual,
2095                  AggStrategy aggstrategy,
2096                  int numGroupCols, AttrNumber *grpColIdx,
2097                  long numGroups, int numAggs,
2098                  Plan *lefttree)
2099 {
2100         Agg                *node = makeNode(Agg);
2101         Plan       *plan = &node->plan;
2102         Path            agg_path;               /* dummy for result of cost_agg */
2103         QualCost        qual_cost;
2104
2105         node->aggstrategy = aggstrategy;
2106         node->numCols = numGroupCols;
2107         node->grpColIdx = grpColIdx;
2108         node->numGroups = numGroups;
2109
2110         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2111         cost_agg(&agg_path, root,
2112                          aggstrategy, numAggs,
2113                          numGroupCols, numGroups,
2114                          lefttree->startup_cost,
2115                          lefttree->total_cost,
2116                          lefttree->plan_rows);
2117         plan->startup_cost = agg_path.startup_cost;
2118         plan->total_cost = agg_path.total_cost;
2119
2120         /*
2121          * We will produce a single output tuple if not grouping, and a tuple
2122          * per group otherwise.
2123          */
2124         if (aggstrategy == AGG_PLAIN)
2125                 plan->plan_rows = 1;
2126         else
2127                 plan->plan_rows = numGroups;
2128
2129         /*
2130          * We also need to account for the cost of evaluation of the qual (ie,
2131          * the HAVING clause) and the tlist.  Note that cost_qual_eval doesn't
2132          * charge anything for Aggref nodes; this is okay since they are
2133          * really comparable to Vars.
2134          *
2135          * See notes in grouping_planner about why this routine and make_group
2136          * are the only ones in this file that worry about tlist eval cost.
2137          */
2138         if (qual)
2139         {
2140                 cost_qual_eval(&qual_cost, qual);
2141                 plan->startup_cost += qual_cost.startup;
2142                 plan->total_cost += qual_cost.startup;
2143                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2144         }
2145         cost_qual_eval(&qual_cost, tlist);
2146         plan->startup_cost += qual_cost.startup;
2147         plan->total_cost += qual_cost.startup;
2148         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2149
2150         plan->qual = qual;
2151         plan->targetlist = tlist;
2152         plan->lefttree = lefttree;
2153         plan->righttree = NULL;
2154
2155         return node;
2156 }
2157
2158 Group *
2159 make_group(Query *root,
2160                    List *tlist,
2161                    int numGroupCols,
2162                    AttrNumber *grpColIdx,
2163                    double numGroups,
2164                    Plan *lefttree)
2165 {
2166         Group      *node = makeNode(Group);
2167         Plan       *plan = &node->plan;
2168         Path            group_path;             /* dummy for result of cost_group */
2169         QualCost        qual_cost;
2170
2171         node->numCols = numGroupCols;
2172         node->grpColIdx = grpColIdx;
2173
2174         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2175         cost_group(&group_path, root,
2176                            numGroupCols, numGroups,
2177                            lefttree->startup_cost,
2178                            lefttree->total_cost,
2179                            lefttree->plan_rows);
2180         plan->startup_cost = group_path.startup_cost;
2181         plan->total_cost = group_path.total_cost;
2182
2183         /* One output tuple per estimated result group */
2184         plan->plan_rows = numGroups;
2185
2186         /*
2187          * We also need to account for the cost of evaluation of the tlist.
2188          *
2189          * XXX this double-counts the cost of evaluation of any expressions used
2190          * for grouping, since in reality those will have been evaluated at a
2191          * lower plan level and will only be copied by the Group node. Worth
2192          * fixing?
2193          *
2194          * See notes in grouping_planner about why this routine and make_agg are
2195          * the only ones in this file that worry about tlist eval cost.
2196          */
2197         cost_qual_eval(&qual_cost, tlist);
2198         plan->startup_cost += qual_cost.startup;
2199         plan->total_cost += qual_cost.startup;
2200         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
2201
2202         plan->qual = NIL;
2203         plan->targetlist = tlist;
2204         plan->lefttree = lefttree;
2205         plan->righttree = NULL;
2206
2207         return node;
2208 }
2209
2210 /*
2211  * distinctList is a list of SortClauses, identifying the targetlist items
2212  * that should be considered by the Unique filter.
2213  */
2214 Unique *
2215 make_unique(Plan *lefttree, List *distinctList)
2216 {
2217         Unique     *node = makeNode(Unique);
2218         Plan       *plan = &node->plan;
2219         int                     numCols = list_length(distinctList);
2220         int                     keyno = 0;
2221         AttrNumber *uniqColIdx;
2222         ListCell   *slitem;
2223
2224         copy_plan_costsize(plan, lefttree);
2225
2226         /*
2227          * Charge one cpu_operator_cost per comparison per input tuple. We
2228          * assume all columns get compared at most of the tuples.  (XXX
2229          * probably this is an overestimate.)
2230          */
2231         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
2232
2233         /*
2234          * plan->plan_rows is left as a copy of the input subplan's plan_rows;
2235          * ie, we assume the filter removes nothing.  The caller must alter
2236          * this if he has a better idea.
2237          */
2238
2239         plan->targetlist = copyObject(lefttree->targetlist);
2240         plan->qual = NIL;
2241         plan->lefttree = lefttree;
2242         plan->righttree = NULL;
2243
2244         /*
2245          * convert SortClause list into array of attr indexes, as wanted by
2246          * exec
2247          */
2248         Assert(numCols > 0);
2249         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2250
2251         foreach(slitem, distinctList)
2252         {
2253                 SortClause *sortcl = (SortClause *) lfirst(slitem);
2254                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
2255
2256                 uniqColIdx[keyno++] = tle->resdom->resno;
2257         }
2258
2259         node->numCols = numCols;
2260         node->uniqColIdx = uniqColIdx;
2261
2262         return node;
2263 }
2264
2265 /*
2266  * distinctList is a list of SortClauses, identifying the targetlist items
2267  * that should be considered by the SetOp filter.
2268  */
2269
2270 SetOp *
2271 make_setop(SetOpCmd cmd, Plan *lefttree,
2272                    List *distinctList, AttrNumber flagColIdx)
2273 {
2274         SetOp      *node = makeNode(SetOp);
2275         Plan       *plan = &node->plan;
2276         int                     numCols = list_length(distinctList);
2277         int                     keyno = 0;
2278         AttrNumber *dupColIdx;
2279         ListCell   *slitem;
2280
2281         copy_plan_costsize(plan, lefttree);
2282
2283         /*
2284          * Charge one cpu_operator_cost per comparison per input tuple. We
2285          * assume all columns get compared at most of the tuples.
2286          */
2287         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
2288
2289         /*
2290          * We make the unsupported assumption that there will be 10% as many
2291          * tuples out as in.  Any way to do better?
2292          */
2293         plan->plan_rows *= 0.1;
2294         if (plan->plan_rows < 1)
2295                 plan->plan_rows = 1;
2296
2297         plan->targetlist = copyObject(lefttree->targetlist);
2298         plan->qual = NIL;
2299         plan->lefttree = lefttree;
2300         plan->righttree = NULL;
2301
2302         /*
2303          * convert SortClause list into array of attr indexes, as wanted by
2304          * exec
2305          */
2306         Assert(numCols > 0);
2307         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
2308
2309         foreach(slitem, distinctList)
2310         {
2311                 SortClause *sortcl = (SortClause *) lfirst(slitem);
2312                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
2313
2314                 dupColIdx[keyno++] = tle->resdom->resno;
2315         }
2316
2317         node->cmd = cmd;
2318         node->numCols = numCols;
2319         node->dupColIdx = dupColIdx;
2320         node->flagColIdx = flagColIdx;
2321
2322         return node;
2323 }
2324
2325 Limit *
2326 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount)
2327 {
2328         Limit      *node = makeNode(Limit);
2329         Plan       *plan = &node->plan;
2330
2331         copy_plan_costsize(plan, lefttree);
2332
2333         /*
2334          * If offset/count are constants, adjust the output rows count and
2335          * costs accordingly.  This is only a cosmetic issue if we are at top
2336          * level, but if we are building a subquery then it's important to
2337          * report correct info to the outer planner.
2338          */
2339         if (limitOffset && IsA(limitOffset, Const))
2340         {
2341                 Const      *limito = (Const *) limitOffset;
2342                 int32           offset = DatumGetInt32(limito->constvalue);
2343
2344                 if (!limito->constisnull && offset > 0)
2345                 {
2346                         if (offset > plan->plan_rows)
2347                                 offset = (int32) plan->plan_rows;
2348                         if (plan->plan_rows > 0)
2349                                 plan->startup_cost +=
2350                                         (plan->total_cost - plan->startup_cost)
2351                                         * ((double) offset) / plan->plan_rows;
2352                         plan->plan_rows -= offset;
2353                         if (plan->plan_rows < 1)
2354                                 plan->plan_rows = 1;
2355                 }
2356         }
2357         if (limitCount && IsA(limitCount, Const))
2358         {
2359                 Const      *limitc = (Const *) limitCount;
2360                 int32           count = DatumGetInt32(limitc->constvalue);
2361
2362                 if (!limitc->constisnull && count >= 0)
2363                 {
2364                         if (count > plan->plan_rows)
2365                                 count = (int32) plan->plan_rows;
2366                         if (plan->plan_rows > 0)
2367                                 plan->total_cost = plan->startup_cost +
2368                                         (plan->total_cost - plan->startup_cost)
2369                                         * ((double) count) / plan->plan_rows;
2370                         plan->plan_rows = count;
2371                         if (plan->plan_rows < 1)
2372                                 plan->plan_rows = 1;
2373                 }
2374         }
2375
2376         plan->targetlist = copyObject(lefttree->targetlist);
2377         plan->qual = NIL;
2378         plan->lefttree = lefttree;
2379         plan->righttree = NULL;
2380
2381         node->limitOffset = limitOffset;
2382         node->limitCount = limitCount;
2383
2384         return node;
2385 }
2386
2387 Result *
2388 make_result(List *tlist,
2389                         Node *resconstantqual,
2390                         Plan *subplan)
2391 {
2392         Result     *node = makeNode(Result);
2393         Plan       *plan = &node->plan;
2394
2395         if (subplan)
2396                 copy_plan_costsize(plan, subplan);
2397         else
2398         {
2399                 plan->startup_cost = 0;
2400                 plan->total_cost = cpu_tuple_cost;
2401                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
2402                 plan->plan_width = 0;   /* XXX try to be smarter? */
2403         }
2404
2405         if (resconstantqual)
2406         {
2407                 QualCost        qual_cost;
2408
2409                 cost_qual_eval(&qual_cost, (List *) resconstantqual);
2410                 /* resconstantqual is evaluated once at startup */
2411                 plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
2412                 plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
2413         }
2414
2415         plan->targetlist = tlist;
2416         plan->qual = NIL;
2417         plan->lefttree = subplan;
2418         plan->righttree = NULL;
2419         node->resconstantqual = resconstantqual;
2420
2421         return node;
2422 }
2423
2424 /*
2425  * is_projection_capable_plan
2426  *              Check whether a given Plan node is able to do projection.
2427  */
2428 bool
2429 is_projection_capable_plan(Plan *plan)
2430 {
2431         /* Most plan types can project, so just list the ones that can't */
2432         switch (nodeTag(plan))
2433         {
2434                 case T_Hash:
2435                 case T_Material:
2436                 case T_Sort:
2437                 case T_Unique:
2438                 case T_SetOp:
2439                 case T_Limit:
2440                 case T_Append:
2441                         return false;
2442                 default:
2443                         break;
2444         }
2445         return true;
2446 }