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

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