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