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-2007, PostgreSQL Global Development Group
   9  * Portions Copyright (c) 1994, Regents of the University of California
  10  *
  11  *
  12  * IDENTIFICATION
  13  *        $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.227 2007/02/25 17:44:01 tgl Exp $
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #include "postgres.h"
  18
  19 #include <limits.h>
  20
  21 #include "nodes/makefuncs.h"
  22 #include "optimizer/clauses.h"
  23 #include "optimizer/cost.h"
  24 #include "optimizer/plancat.h"
  25 #include "optimizer/planmain.h"
  26 #include "optimizer/predtest.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 "parser/parsetree.h"
  33 #include "utils/lsyscache.h"
  34
  35
  36 static Plan *create_scan_plan(PlannerInfo *root, Path *best_path);
  37 static List *build_relation_tlist(RelOptInfo *rel);
  38 static bool use_physical_tlist(RelOptInfo *rel);
  39 static void disuse_physical_tlist(Plan *plan, Path *path);
  40 static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals);
  41 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
  42 static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
  43 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
  44 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
  45 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
  46 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
  47                                         List *tlist, List *scan_clauses);
  48 static IndexScan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
  49                                           List *tlist, List *scan_clauses,
  50                                           List **nonlossy_clauses);
  51 static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
  52                                                 BitmapHeapPath *best_path,
  53                                                 List *tlist, List *scan_clauses);
  54 static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
  55                                           List **qual, List **indexqual);
  56 static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
  57                                         List *tlist, List *scan_clauses);
  58 static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
  59                                                  List *tlist, List *scan_clauses);
  60 static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
  61                                                  List *tlist, List *scan_clauses);
  62 static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
  63                                            List *tlist, List *scan_clauses);
  64 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
  65                                          Plan *outer_plan, Plan *inner_plan);
  66 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
  67                                           Plan *outer_plan, Plan *inner_plan);
  68 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
  69                                          Plan *outer_plan, Plan *inner_plan);
  70 static void fix_indexqual_references(List *indexquals, IndexPath *index_path,
  71                                                  List **fixed_indexquals,
  72                                                  List **nonlossy_indexquals,
  73                                                  List **indexstrategy,
  74                                                  List **indexsubtype);
  75 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index,
  76                                           Oid *opfamily);
  77 static List *get_switched_clauses(List *clauses, Relids outerrelids);
  78 static List *order_qual_clauses(PlannerInfo *root, List *clauses);
  79 static void copy_path_costsize(Plan *dest, Path *src);
  80 static void copy_plan_costsize(Plan *dest, Plan *src);
  81 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
  82 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
  83                            Oid indexid, List *indexqual, List *indexqualorig,
  84                            List *indexstrategy, List *indexsubtype,
  85                            ScanDirection indexscandir);
  86 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
  87                                           List *indexqual,
  88                                           List *indexqualorig,
  89                                           List *indexstrategy,
  90                                           List *indexsubtype);
  91 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
  92                                          List *qpqual,
  93                                          Plan *lefttree,
  94                                          List *bitmapqualorig,
  95                                          Index scanrelid);
  96 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
  97                          List *tidquals);
  98 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
  99                                   Index scanrelid, Node *funcexpr, List *funccolnames,
 100                                   List *funccoltypes, List *funccoltypmods);
 101 static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
 102                                 Index scanrelid, List *values_lists);
 103 static BitmapAnd *make_bitmap_and(List *bitmapplans);
 104 static BitmapOr *make_bitmap_or(List *bitmapplans);
 105 static NestLoop *make_nestloop(List *tlist,
 106                           List *joinclauses, List *otherclauses,
 107                           Plan *lefttree, Plan *righttree,
 108                           JoinType jointype);
 109 static HashJoin *make_hashjoin(List *tlist,
 110                           List *joinclauses, List *otherclauses,
 111                           List *hashclauses,
 112                           Plan *lefttree, Plan *righttree,
 113                           JoinType jointype);
 114 static Hash *make_hash(Plan *lefttree);
 115 static MergeJoin *make_mergejoin(List *tlist,
 116                            List *joinclauses, List *otherclauses,
 117                            List *mergeclauses,
 118                            Oid *mergefamilies,
 119                            int *mergestrategies,
 120                            bool *mergenullsfirst,
 121                            Plan *lefttree, Plan *righttree,
 122                            JoinType jointype);
 123 static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
 124                   AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst);
 125
 126
 127 /*
 128  * create_plan
 129  *        Creates the access plan for a query by tracing backwards through the
 130  *        desired chain of pathnodes, starting at the node 'best_path'.  For
 131  *        every pathnode found, we create a corresponding plan node containing
 132  *        appropriate id, target list, and qualification information.
 133  *
 134  *        The tlists and quals in the plan tree are still in planner format,
 135  *        ie, Vars still correspond to the parser's numbering.  This will be
 136  *        fixed later by setrefs.c.
 137  *
 138  *        best_path is the best access path
 139  *
 140  *        Returns a Plan tree.
 141  */
 142 Plan *
 143 create_plan(PlannerInfo *root, Path *best_path)
 144 {
 145         Plan       *plan;
 146
 147         switch (best_path->pathtype)
 148         {
 149                 case T_SeqScan:
 150                 case T_IndexScan:
 151                 case T_BitmapHeapScan:
 152                 case T_TidScan:
 153                 case T_SubqueryScan:
 154                 case T_FunctionScan:
 155                 case T_ValuesScan:
 156                         plan = create_scan_plan(root, best_path);
 157                         break;
 158                 case T_HashJoin:
 159                 case T_MergeJoin:
 160                 case T_NestLoop:
 161                         plan = create_join_plan(root,
 162                                                                         (JoinPath *) best_path);
 163                         break;
 164                 case T_Append:
 165                         plan = create_append_plan(root,
 166                                                                           (AppendPath *) best_path);
 167                         break;
 168                 case T_Result:
 169                         plan = (Plan *) create_result_plan(root,
 170                                                                                            (ResultPath *) best_path);
 171                         break;
 172                 case T_Material:
 173                         plan = (Plan *) create_material_plan(root,
 174                                                                                                  (MaterialPath *) best_path);
 175                         break;
 176                 case T_Unique:
 177                         plan = create_unique_plan(root,
 178                                                                           (UniquePath *) best_path);
 179                         break;
 180                 default:
 181                         elog(ERROR, "unrecognized node type: %d",
 182                                  (int) best_path->pathtype);
 183                         plan = NULL;            /* keep compiler quiet */
 184                         break;
 185         }
 186
 187         return plan;
 188 }
 189
 190 /*
 191  * create_scan_plan
 192  *       Create a scan plan for the parent relation of 'best_path'.
 193  */
 194 static Plan *
 195 create_scan_plan(PlannerInfo *root, Path *best_path)
 196 {
 197         RelOptInfo *rel = best_path->parent;
 198         List       *tlist;
 199         List       *scan_clauses;
 200         Plan       *plan;
 201
 202         /*
 203          * For table scans, rather than using the relation targetlist (which is
 204          * only those Vars actually needed by the query), we prefer to generate a
 205          * tlist containing all Vars in order.  This will allow the executor to
 206          * optimize away projection of the table tuples, if possible.  (Note that
 207          * planner.c may replace the tlist we generate here, forcing projection to
 208          * occur.)
 209          */
 210         if (use_physical_tlist(rel))
 211         {
 212                 tlist = build_physical_tlist(root, rel);
 213                 /* if fail because of dropped cols, use regular method */
 214                 if (tlist == NIL)
 215                         tlist = build_relation_tlist(rel);
 216         }
 217         else
 218                 tlist = build_relation_tlist(rel);
 219
 220         /*
 221          * Extract the relevant restriction clauses from the parent relation. The
 222          * executor must apply all these restrictions during the scan, except for
 223          * pseudoconstants which we'll take care of below.
 224          */
 225         scan_clauses = rel->baserestrictinfo;
 226
 227         switch (best_path->pathtype)
 228         {
 229                 case T_SeqScan:
 230                         plan = (Plan *) create_seqscan_plan(root,
 231                                                                                                 best_path,
 232                                                                                                 tlist,
 233                                                                                                 scan_clauses);
 234                         break;
 235
 236                 case T_IndexScan:
 237                         plan = (Plan *) create_indexscan_plan(root,
 238                                                                                                   (IndexPath *) best_path,
 239                                                                                                   tlist,
 240                                                                                                   scan_clauses,
 241                                                                                                   NULL);
 242                         break;
 243
 244                 case T_BitmapHeapScan:
 245                         plan = (Plan *) create_bitmap_scan_plan(root,
 246                                                                                                 (BitmapHeapPath *) best_path,
 247                                                                                                         tlist,
 248                                                                                                         scan_clauses);
 249                         break;
 250
 251                 case T_TidScan:
 252                         plan = (Plan *) create_tidscan_plan(root,
 253                                                                                                 (TidPath *) best_path,
 254                                                                                                 tlist,
 255                                                                                                 scan_clauses);
 256                         break;
 257
 258                 case T_SubqueryScan:
 259                         plan = (Plan *) create_subqueryscan_plan(root,
 260                                                                                                          best_path,
 261                                                                                                          tlist,
 262                                                                                                          scan_clauses);
 263                         break;
 264
 265                 case T_FunctionScan:
 266                         plan = (Plan *) create_functionscan_plan(root,
 267                                                                                                          best_path,
 268                                                                                                          tlist,
 269                                                                                                          scan_clauses);
 270                         break;
 271
 272                 case T_ValuesScan:
 273                         plan = (Plan *) create_valuesscan_plan(root,
 274                                                                                                    best_path,
 275                                                                                                    tlist,
 276                                                                                                    scan_clauses);
 277                         break;
 278
 279                 default:
 280                         elog(ERROR, "unrecognized node type: %d",
 281                                  (int) best_path->pathtype);
 282                         plan = NULL;            /* keep compiler quiet */
 283                         break;
 284         }
 285
 286         /*
 287          * If there are any pseudoconstant clauses attached to this node, insert a
 288          * gating Result node that evaluates the pseudoconstants as one-time
 289          * quals.
 290          */
 291         if (root->hasPseudoConstantQuals)
 292                 plan = create_gating_plan(root, plan, scan_clauses);
 293
 294         return plan;
 295 }
 296
 297 /*
 298  * Build a target list (ie, a list of TargetEntry) for a relation.
 299  */
 300 static List *
 301 build_relation_tlist(RelOptInfo *rel)
 302 {
 303         List       *tlist = NIL;
 304         int                     resno = 1;
 305         ListCell   *v;
 306
 307         foreach(v, rel->reltargetlist)
 308         {
 309                 /* Do we really need to copy here?      Not sure */
 310                 Var                *var = (Var *) copyObject(lfirst(v));
 311
 312                 tlist = lappend(tlist, makeTargetEntry((Expr *) var,
 313                                                                                            resno,
 314                                                                                            NULL,
 315                                                                                            false));
 316                 resno++;
 317         }
 318         return tlist;
 319 }
 320
 321 /*
 322  * use_physical_tlist
 323  *              Decide whether to use a tlist matching relation structure,
 324  *              rather than only those Vars actually referenced.
 325  */
 326 static bool
 327 use_physical_tlist(RelOptInfo *rel)
 328 {
 329         int                     i;
 330
 331         /*
 332          * We can do this for real relation scans, subquery scans, function scans,
 333          * and values scans (but not for, eg, joins).
 334          */
 335         if (rel->rtekind != RTE_RELATION &&
 336                 rel->rtekind != RTE_SUBQUERY &&
 337                 rel->rtekind != RTE_FUNCTION &&
 338                 rel->rtekind != RTE_VALUES)
 339                 return false;
 340
 341         /*
 342          * Can't do it with inheritance cases either (mainly because Append
 343          * doesn't project).
 344          */
 345         if (rel->reloptkind != RELOPT_BASEREL)
 346                 return false;
 347
 348         /*
 349          * Can't do it if any system columns or whole-row Vars are requested,
 350          * either.      (This could possibly be fixed but would take some fragile
 351          * assumptions in setrefs.c, I think.)
 352          */
 353         for (i = rel->min_attr; i <= 0; i++)
 354         {
 355                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
 356                         return false;
 357         }
 358
 359         return true;
 360 }
 361
 362 /*
 363  * disuse_physical_tlist
 364  *              Switch a plan node back to emitting only Vars actually referenced.
 365  *
 366  * If the plan node immediately above a scan would prefer to get only
 367  * needed Vars and not a physical tlist, it must call this routine to
 368  * undo the decision made by use_physical_tlist().      Currently, Hash, Sort,
 369  * and Material nodes want this, so they don't have to store useless columns.
 370  */
 371 static void
 372 disuse_physical_tlist(Plan *plan, Path *path)
 373 {
 374         /* Only need to undo it for path types handled by create_scan_plan() */
 375         switch (path->pathtype)
 376         {
 377                 case T_SeqScan:
 378                 case T_IndexScan:
 379                 case T_BitmapHeapScan:
 380                 case T_TidScan:
 381                 case T_SubqueryScan:
 382                 case T_FunctionScan:
 383                 case T_ValuesScan:
 384                         plan->targetlist = build_relation_tlist(path->parent);
 385                         break;
 386                 default:
 387                         break;
 388         }
 389 }
 390
 391 /*
 392  * create_gating_plan
 393  *        Deal with pseudoconstant qual clauses
 394  *
 395  * If the node's quals list includes any pseudoconstant quals, put them
 396  * into a gating Result node atop the already-built plan.  Otherwise,
 397  * return the plan as-is.
 398  *
 399  * Note that we don't change cost or size estimates when doing gating.
 400  * The costs of qual eval were already folded into the plan's startup cost.
 401  * Leaving the size alone amounts to assuming that the gating qual will
 402  * succeed, which is the conservative estimate for planning upper queries.
 403  * We certainly don't want to assume the output size is zero (unless the
 404  * gating qual is actually constant FALSE, and that case is dealt with in
 405  * clausesel.c).  Interpolating between the two cases is silly, because
 406  * it doesn't reflect what will really happen at runtime, and besides which
 407  * in most cases we have only a very bad idea of the probability of the gating
 408  * qual being true.
 409  */
 410 static Plan *
 411 create_gating_plan(PlannerInfo *root, Plan *plan, List *quals)
 412 {
 413         List       *pseudoconstants;
 414
 415         /* Sort into desirable execution order while still in RestrictInfo form */
 416         quals = order_qual_clauses(root, quals);
 417
 418         /* Pull out any pseudoconstant quals from the RestrictInfo list */
 419         pseudoconstants = extract_actual_clauses(quals, true);
 420
 421         if (!pseudoconstants)
 422                 return plan;
 423
 424         return (Plan *) make_result(root,
 425                                                                 plan->targetlist,
 426                                                                 (Node *) pseudoconstants,
 427                                                                 plan);
 428 }
 429
 430 /*
 431  * create_join_plan
 432  *        Create a join plan for 'best_path' and (recursively) plans for its
 433  *        inner and outer paths.
 434  */
 435 static Plan *
 436 create_join_plan(PlannerInfo *root, JoinPath *best_path)
 437 {
 438         Plan       *outer_plan;
 439         Plan       *inner_plan;
 440         Plan       *plan;
 441
 442         outer_plan = create_plan(root, best_path->outerjoinpath);
 443         inner_plan = create_plan(root, best_path->innerjoinpath);
 444
 445         switch (best_path->path.pathtype)
 446         {
 447                 case T_MergeJoin:
 448                         plan = (Plan *) create_mergejoin_plan(root,
 449                                                                                                   (MergePath *) best_path,
 450                                                                                                   outer_plan,
 451                                                                                                   inner_plan);
 452                         break;
 453                 case T_HashJoin:
 454                         plan = (Plan *) create_hashjoin_plan(root,
 455                                                                                                  (HashPath *) best_path,
 456                                                                                                  outer_plan,
 457                                                                                                  inner_plan);
 458                         break;
 459                 case T_NestLoop:
 460                         plan = (Plan *) create_nestloop_plan(root,
 461                                                                                                  (NestPath *) best_path,
 462                                                                                                  outer_plan,
 463                                                                                                  inner_plan);
 464                         break;
 465                 default:
 466                         elog(ERROR, "unrecognized node type: %d",
 467                                  (int) best_path->path.pathtype);
 468                         plan = NULL;            /* keep compiler quiet */
 469                         break;
 470         }
 471
 472         /*
 473          * If there are any pseudoconstant clauses attached to this node, insert a
 474          * gating Result node that evaluates the pseudoconstants as one-time
 475          * quals.
 476          */
 477         if (root->hasPseudoConstantQuals)
 478                 plan = create_gating_plan(root, plan, best_path->joinrestrictinfo);
 479
 480 #ifdef NOT_USED
 481
 482         /*
 483          * * Expensive function pullups may have pulled local predicates * into
 484          * this path node.      Put them in the qpqual of the plan node. * JMH,
 485          * 6/15/92
 486          */
 487         if (get_loc_restrictinfo(best_path) != NIL)
 488                 set_qpqual((Plan) plan,
 489                                    list_concat(get_qpqual((Plan) plan),
 490                                            get_actual_clauses(get_loc_restrictinfo(best_path))));
 491 #endif
 492
 493         return plan;
 494 }
 495
 496 /*
 497  * create_append_plan
 498  *        Create an Append plan for 'best_path' and (recursively) plans
 499  *        for its subpaths.
 500  *
 501  *        Returns a Plan node.
 502  */
 503 static Plan *
 504 create_append_plan(PlannerInfo *root, AppendPath *best_path)
 505 {
 506         Append     *plan;
 507         List       *tlist = build_relation_tlist(best_path->path.parent);
 508         List       *subplans = NIL;
 509         ListCell   *subpaths;
 510
 511         /*
 512          * It is possible for the subplans list to contain only one entry, or even
 513          * no entries.  Handle these cases specially.
 514          *
 515          * XXX ideally, if there's just one entry, we'd not bother to generate an
 516          * Append node but just return the single child.  At the moment this does
 517          * not work because the varno of the child scan plan won't match the
 518          * parent-rel Vars it'll be asked to emit.
 519          */
 520         if (best_path->subpaths == NIL)
 521         {
 522                 /* Generate a Result plan with constant-FALSE gating qual */
 523                 return (Plan *) make_result(root,
 524                                                                         tlist,
 525                                                                         (Node *) list_make1(makeBoolConst(false,
 526                                                                                                                                           false)),
 527                                                                         NULL);
 528         }
 529
 530         /* Normal case with multiple subpaths */
 531         foreach(subpaths, best_path->subpaths)
 532         {
 533                 Path       *subpath = (Path *) lfirst(subpaths);
 534
 535                 subplans = lappend(subplans, create_plan(root, subpath));
 536         }
 537
 538         plan = make_append(subplans, false, tlist);
 539
 540         return (Plan *) plan;
 541 }
 542
 543 /*
 544  * create_result_plan
 545  *        Create a Result plan for 'best_path'.
 546  *        This is only used for the case of a query with an empty jointree.
 547  *
 548  *        Returns a Plan node.
 549  */
 550 static Result *
 551 create_result_plan(PlannerInfo *root, ResultPath *best_path)
 552 {
 553         List       *tlist;
 554         List       *quals;
 555
 556         /* The tlist will be installed later, since we have no RelOptInfo */
 557         Assert(best_path->path.parent == NULL);
 558         tlist = NIL;
 559
 560         /* best_path->quals is just bare clauses */
 561
 562         quals = order_qual_clauses(root, best_path->quals);
 563
 564         return make_result(root, tlist, (Node *) quals, NULL);
 565 }
 566
 567 /*
 568  * create_material_plan
 569  *        Create a Material plan for 'best_path' and (recursively) plans
 570  *        for its subpaths.
 571  *
 572  *        Returns a Plan node.
 573  */
 574 static Material *
 575 create_material_plan(PlannerInfo *root, MaterialPath *best_path)
 576 {
 577         Material   *plan;
 578         Plan       *subplan;
 579
 580         subplan = create_plan(root, best_path->subpath);
 581
 582         /* We don't want any excess columns in the materialized tuples */
 583         disuse_physical_tlist(subplan, best_path->subpath);
 584
 585         plan = make_material(subplan);
 586
 587         copy_path_costsize(&plan->plan, (Path *) best_path);
 588
 589         return plan;
 590 }
 591
 592 /*
 593  * create_unique_plan
 594  *        Create a Unique plan for 'best_path' and (recursively) plans
 595  *        for its subpaths.
 596  *
 597  *        Returns a Plan node.
 598  */
 599 static Plan *
 600 create_unique_plan(PlannerInfo *root, UniquePath *best_path)
 601 {
 602         Plan       *plan;
 603         Plan       *subplan;
 604         List       *uniq_exprs;
 605         List       *in_operators;
 606         List       *newtlist;
 607         int                     nextresno;
 608         bool            newitems;
 609         int                     numGroupCols;
 610         AttrNumber *groupColIdx;
 611         int                     groupColPos;
 612         ListCell   *l;
 613
 614         subplan = create_plan(root, best_path->subpath);
 615
 616         /* Done if we don't need to do any actual unique-ifying */
 617         if (best_path->umethod == UNIQUE_PATH_NOOP)
 618                 return subplan;
 619
 620         /*----------
 621          * As constructed, the subplan has a "flat" tlist containing just the
 622          * Vars needed here and at upper levels.  The values we are supposed
 623          * to unique-ify may be expressions in these variables.  We have to
 624          * add any such expressions to the subplan's tlist.
 625          *
 626          * The subplan may have a "physical" tlist if it is a simple scan plan.
 627          * This should be left as-is if we don't need to add any expressions;
 628          * but if we do have to add expressions, then a projection step will be
 629          * needed at runtime anyway, and so we may as well remove unneeded items.
 630          * Therefore newtlist starts from build_relation_tlist() not just a
 631          * copy of the subplan's tlist; and we don't install it into the subplan
 632          * unless stuff has to be added.
 633          *
 634          * To find the correct list of values to unique-ify, we look in the
 635          * information saved for IN expressions.  If this code is ever used in
 636          * other scenarios, some other way of finding what to unique-ify will
 637          * be needed.  The IN clause's operators are needed too, since they
 638          * determine what the meaning of "unique" is in this context.
 639          *----------
 640          */
 641         uniq_exprs = NIL;                       /* just to keep compiler quiet */
 642         in_operators = NIL;
 643         foreach(l, root->in_info_list)
 644         {
 645                 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
 646
 647                 if (bms_equal(ininfo->righthand, best_path->path.parent->relids))
 648                 {
 649                         uniq_exprs = ininfo->sub_targetlist;
 650                         in_operators = ininfo->in_operators;
 651                         break;
 652                 }
 653         }
 654         if (l == NULL)                          /* fell out of loop? */
 655                 elog(ERROR, "could not find UniquePath in in_info_list");
 656
 657         /* initialize modified subplan tlist as just the "required" vars */
 658         newtlist = build_relation_tlist(best_path->path.parent);
 659         nextresno = list_length(newtlist) + 1;
 660         newitems = false;
 661
 662         foreach(l, uniq_exprs)
 663         {
 664                 Node       *uniqexpr = lfirst(l);
 665                 TargetEntry *tle;
 666
 667                 tle = tlist_member(uniqexpr, newtlist);
 668                 if (!tle)
 669                 {
 670                         tle = makeTargetEntry((Expr *) uniqexpr,
 671                                                                   nextresno,
 672                                                                   NULL,
 673                                                                   false);
 674                         newtlist = lappend(newtlist, tle);
 675                         nextresno++;
 676                         newitems = true;
 677                 }
 678         }
 679
 680         if (newitems)
 681         {
 682                 /*
 683                  * If the top plan node can't do projections, we need to add a Result
 684                  * node to help it along.
 685                  */
 686                 if (!is_projection_capable_plan(subplan))
 687                         subplan = (Plan *) make_result(root, newtlist, NULL, subplan);
 688                 else
 689                         subplan->targetlist = newtlist;
 690         }
 691
 692         /*
 693          * Build control information showing which subplan output columns are to
 694          * be examined by the grouping step.  Unfortunately we can't merge this
 695          * with the previous loop, since we didn't then know which version of the
 696          * subplan tlist we'd end up using.
 697          */
 698         newtlist = subplan->targetlist;
 699         numGroupCols = list_length(uniq_exprs);
 700         groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
 701
 702         groupColPos = 0;
 703         foreach(l, uniq_exprs)
 704         {
 705                 Node       *uniqexpr = lfirst(l);
 706                 TargetEntry *tle;
 707
 708                 tle = tlist_member(uniqexpr, newtlist);
 709                 if (!tle)                               /* shouldn't happen */
 710                         elog(ERROR, "failed to find unique expression in subplan tlist");
 711                 groupColIdx[groupColPos++] = tle->resno;
 712         }
 713
 714         if (best_path->umethod == UNIQUE_PATH_HASH)
 715         {
 716                 long            numGroups;
 717                 Oid                *groupOperators;
 718
 719                 numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
 720
 721                 /*
 722                  * Get the hashable equality operators for the Agg node to use.
 723                  * Normally these are the same as the IN clause operators, but if
 724                  * those are cross-type operators then the equality operators are
 725                  * the ones for the IN clause operators' RHS datatype.
 726                  */
 727                 groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
 728                 groupColPos = 0;
 729                 foreach(l, in_operators)
 730                 {
 731                         Oid                     in_oper = lfirst_oid(l);
 732                         Oid                     eq_oper;
 733
 734                         if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
 735                                 elog(ERROR, "could not find compatible hash operator for operator %u",
 736                                          in_oper);
 737                         groupOperators[groupColPos++] = eq_oper;
 738                 }
 739
 740                 /*
 741                  * Since the Agg node is going to project anyway, we can give it the
 742                  * minimum output tlist, without any stuff we might have added to the
 743                  * subplan tlist.
 744                  */
 745                 plan = (Plan *) make_agg(root,
 746                                                                  build_relation_tlist(best_path->path.parent),
 747                                                                  NIL,
 748                                                                  AGG_HASHED,
 749                                                                  numGroupCols,
 750                                                                  groupColIdx,
 751                                                                  groupOperators,
 752                                                                  numGroups,
 753                                                                  0,
 754                                                                  subplan);
 755         }
 756         else
 757         {
 758                 List       *sortList = NIL;
 759
 760                 /* Create an ORDER BY list to sort the input compatibly */
 761                 groupColPos = 0;
 762                 foreach(l, in_operators)
 763                 {
 764                         Oid                     in_oper = lfirst_oid(l);
 765                         Oid                     sortop;
 766                         TargetEntry *tle;
 767                         SortClause *sortcl;
 768
 769                         sortop = get_ordering_op_for_equality_op(in_oper, false);
 770                         if (!OidIsValid(sortop))                /* shouldn't happen */
 771                                 elog(ERROR, "could not find ordering operator for equality operator %u",
 772                                          in_oper);
 773                         tle = get_tle_by_resno(subplan->targetlist,
 774                                                                    groupColIdx[groupColPos]);
 775                         Assert(tle != NULL);
 776                         sortcl = makeNode(SortClause);
 777                         sortcl->tleSortGroupRef = assignSortGroupRef(tle,
 778                                                                                                                  subplan->targetlist);
 779                         sortcl->sortop = sortop;
 780                         sortcl->nulls_first = false;
 781                         sortList = lappend(sortList, sortcl);
 782                         groupColPos++;
 783                 }
 784                 plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
 785                 plan = (Plan *) make_unique(plan, sortList);
 786         }
 787
 788         /* Adjust output size estimate (other fields should be OK already) */
 789         plan->plan_rows = best_path->rows;
 790
 791         return plan;
 792 }
 793
 794
 795 /*****************************************************************************
 796  *
 797  *      BASE-RELATION SCAN METHODS
 798  *
 799  *****************************************************************************/
 800
 801
 802 /*
 803  * create_seqscan_plan
 804  *       Returns a seqscan plan for the base relation scanned by 'best_path'
 805  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 806  */
 807 static SeqScan *
 808 create_seqscan_plan(PlannerInfo *root, Path *best_path,
 809                                         List *tlist, List *scan_clauses)
 810 {
 811         SeqScan    *scan_plan;
 812         Index           scan_relid = best_path->parent->relid;
 813
 814         /* it should be a base rel... */
 815         Assert(scan_relid > 0);
 816         Assert(best_path->parent->rtekind == RTE_RELATION);
 817
 818         /* Sort clauses into best execution order */
 819         scan_clauses = order_qual_clauses(root, scan_clauses);
 820
 821         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 822         scan_clauses = extract_actual_clauses(scan_clauses, false);
 823
 824         scan_plan = make_seqscan(tlist,
 825                                                          scan_clauses,
 826                                                          scan_relid);
 827
 828         copy_path_costsize(&scan_plan->plan, best_path);
 829
 830         return scan_plan;
 831 }
 832
 833 /*
 834  * create_indexscan_plan
 835  *        Returns an indexscan plan for the base relation scanned by 'best_path'
 836  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 837  *
 838  * The indexquals list of the path contains implicitly-ANDed qual conditions.
 839  * The list can be empty --- then no index restrictions will be applied during
 840  * the scan.
 841  *
 842  * If nonlossy_clauses isn't NULL, *nonlossy_clauses receives a list of the
 843  * nonlossy indexquals.
 844  */
 845 static IndexScan *
 846 create_indexscan_plan(PlannerInfo *root,
 847                                           IndexPath *best_path,
 848                                           List *tlist,
 849                                           List *scan_clauses,
 850                                           List **nonlossy_clauses)
 851 {
 852         List       *indexquals = best_path->indexquals;
 853         Index           baserelid = best_path->path.parent->relid;
 854         Oid                     indexoid = best_path->indexinfo->indexoid;
 855         List       *qpqual;
 856         List       *stripped_indexquals;
 857         List       *fixed_indexquals;
 858         List       *nonlossy_indexquals;
 859         List       *indexstrategy;
 860         List       *indexsubtype;
 861         ListCell   *l;
 862         IndexScan  *scan_plan;
 863
 864         /* it should be a base rel... */
 865         Assert(baserelid > 0);
 866         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 867
 868         /*
 869          * Build "stripped" indexquals structure (no RestrictInfos) to pass to
 870          * executor as indexqualorig
 871          */
 872         stripped_indexquals = get_actual_clauses(indexquals);
 873
 874         /*
 875          * The executor needs a copy with the indexkey on the left of each clause
 876          * and with index attr numbers substituted for table ones. This pass also
 877          * gets strategy info and looks for "lossy" operators.
 878          */
 879         fix_indexqual_references(indexquals, best_path,
 880                                                          &fixed_indexquals,
 881                                                          &nonlossy_indexquals,
 882                                                          &indexstrategy,
 883                                                          &indexsubtype);
 884
 885         /* pass back nonlossy quals if caller wants 'em */
 886         if (nonlossy_clauses)
 887                 *nonlossy_clauses = nonlossy_indexquals;
 888
 889         /*
 890          * If this is an innerjoin scan, the indexclauses will contain join
 891          * clauses that are not present in scan_clauses (since the passed-in value
 892          * is just the rel's baserestrictinfo list).  We must add these clauses to
 893          * scan_clauses to ensure they get checked.  In most cases we will remove
 894          * the join clauses again below, but if a join clause contains a special
 895          * operator, we need to make sure it gets into the scan_clauses.
 896          *
 897          * Note: pointer comparison should be enough to determine RestrictInfo
 898          * matches.
 899          */
 900         if (best_path->isjoininner)
 901                 scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
 902
 903         /*
 904          * The qpqual list must contain all restrictions not automatically handled
 905          * by the index.  All the predicates in the indexquals will be checked
 906          * (either by the index itself, or by nodeIndexscan.c), but if there are
 907          * any "special" operators involved then they must be included in qpqual.
 908          * Also, any lossy index operators must be rechecked in the qpqual.  The
 909          * upshot is that qpqual must contain scan_clauses minus whatever appears
 910          * in nonlossy_indexquals.
 911          *
 912          * In normal cases simple pointer equality checks will be enough to spot
 913          * duplicate RestrictInfos, so we try that first.  In some situations
 914          * (particularly with OR'd index conditions) we may have scan_clauses that
 915          * are not equal to, but are logically implied by, the index quals; so we
 916          * also try a predicate_implied_by() check to see if we can discard quals
 917          * that way.  (predicate_implied_by assumes its first input contains only
 918          * immutable functions, so we have to check that.)
 919          *
 920          * We can also discard quals that are implied by a partial index's
 921          * predicate, but only in a plain SELECT; when scanning a target relation
 922          * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
 923          * plan so that they'll be properly rechecked by EvalPlanQual testing.
 924          */
 925         qpqual = NIL;
 926         foreach(l, scan_clauses)
 927         {
 928                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
 929
 930                 Assert(IsA(rinfo, RestrictInfo));
 931                 if (rinfo->pseudoconstant)
 932                         continue;                       /* we may drop pseudoconstants here */
 933                 if (list_member_ptr(nonlossy_indexquals, rinfo))
 934                         continue;
 935                 if (!contain_mutable_functions((Node *) rinfo->clause))
 936                 {
 937                         List       *clausel = list_make1(rinfo->clause);
 938
 939                         if (predicate_implied_by(clausel, nonlossy_indexquals))
 940                                 continue;
 941                         if (best_path->indexinfo->indpred)
 942                         {
 943                                 if (baserelid != root->parse->resultRelation &&
 944                                         get_rowmark(root->parse, baserelid) == NULL)
 945                                         if (predicate_implied_by(clausel,
 946                                                                                          best_path->indexinfo->indpred))
 947                                                 continue;
 948                         }
 949                 }
 950                 qpqual = lappend(qpqual, rinfo);
 951         }
 952
 953         /* Sort clauses into best execution order */
 954         qpqual = order_qual_clauses(root, qpqual);
 955
 956         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 957         qpqual = extract_actual_clauses(qpqual, false);
 958
 959         /* Finally ready to build the plan node */
 960         scan_plan = make_indexscan(tlist,
 961                                                            qpqual,
 962                                                            baserelid,
 963                                                            indexoid,
 964                                                            fixed_indexquals,
 965                                                            stripped_indexquals,
 966                                                            indexstrategy,
 967                                                            indexsubtype,
 968                                                            best_path->indexscandir);
 969
 970         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 971         /* use the indexscan-specific rows estimate, not the parent rel's */
 972         scan_plan->scan.plan.plan_rows = best_path->rows;
 973
 974         return scan_plan;
 975 }
 976
 977 /*
 978  * create_bitmap_scan_plan
 979  *        Returns a bitmap scan plan for the base relation scanned by 'best_path'
 980  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 981  */
 982 static BitmapHeapScan *
 983 create_bitmap_scan_plan(PlannerInfo *root,
 984                                                 BitmapHeapPath *best_path,
 985                                                 List *tlist,
 986                                                 List *scan_clauses)
 987 {
 988         Index           baserelid = best_path->path.parent->relid;
 989         Plan       *bitmapqualplan;
 990         List       *bitmapqualorig;
 991         List       *indexquals;
 992         List       *qpqual;
 993         ListCell   *l;
 994         BitmapHeapScan *scan_plan;
 995
 996         /* it should be a base rel... */
 997         Assert(baserelid > 0);
 998         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 999
1000         /* Process the bitmapqual tree into a Plan tree and qual lists */
1001         bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
1002                                                                                    &bitmapqualorig, &indexquals);
1003
1004         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1005         scan_clauses = extract_actual_clauses(scan_clauses, false);
1006
1007         /*
1008          * If this is a innerjoin scan, the indexclauses will contain join clauses
1009          * that are not present in scan_clauses (since the passed-in value is just
1010          * the rel's baserestrictinfo list).  We must add these clauses to
1011          * scan_clauses to ensure they get checked.  In most cases we will remove
1012          * the join clauses again below, but if a join clause contains a special
1013          * operator, we need to make sure it gets into the scan_clauses.
1014          */
1015         if (best_path->isjoininner)
1016         {
1017                 scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
1018         }
1019
1020         /*
1021          * The qpqual list must contain all restrictions not automatically handled
1022          * by the index.  All the predicates in the indexquals will be checked
1023          * (either by the index itself, or by nodeBitmapHeapscan.c), but if there
1024          * are any "special" or lossy operators involved then they must be added
1025          * to qpqual.  The upshot is that qpqual must contain scan_clauses minus
1026          * whatever appears in indexquals.
1027          *
1028          * In normal cases simple equal() checks will be enough to spot duplicate
1029          * clauses, so we try that first.  In some situations (particularly with
1030          * OR'd index conditions) we may have scan_clauses that are not equal to,
1031          * but are logically implied by, the index quals; so we also try a
1032          * predicate_implied_by() check to see if we can discard quals that way.
1033          * (predicate_implied_by assumes its first input contains only immutable
1034          * functions, so we have to check that.)
1035          *
1036          * Unlike create_indexscan_plan(), we need take no special thought here
1037          * for partial index predicates; this is because the predicate conditions
1038          * are already listed in bitmapqualorig and indexquals.  Bitmap scans have
1039          * to do it that way because predicate conditions need to be rechecked if
1040          * the scan becomes lossy.
1041          */
1042         qpqual = NIL;
1043         foreach(l, scan_clauses)
1044         {
1045                 Node       *clause = (Node *) lfirst(l);
1046
1047                 if (list_member(indexquals, clause))
1048                         continue;
1049                 if (!contain_mutable_functions(clause))
1050                 {
1051                         List       *clausel = list_make1(clause);
1052
1053                         if (predicate_implied_by(clausel, indexquals))
1054                                 continue;
1055                 }
1056                 qpqual = lappend(qpqual, clause);
1057         }
1058
1059         /* Sort clauses into best execution order */
1060         qpqual = order_qual_clauses(root, qpqual);
1061
1062         /*
1063          * When dealing with special or lossy operators, we will at this point
1064          * have duplicate clauses in qpqual and bitmapqualorig.  We may as well
1065          * drop 'em from bitmapqualorig, since there's no point in making the
1066          * tests twice.
1067          */
1068         bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
1069
1070         /* Finally ready to build the plan node */
1071         scan_plan = make_bitmap_heapscan(tlist,
1072                                                                          qpqual,
1073                                                                          bitmapqualplan,
1074                                                                          bitmapqualorig,
1075                                                                          baserelid);
1076
1077         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1078         /* use the indexscan-specific rows estimate, not the parent rel's */
1079         scan_plan->scan.plan.plan_rows = best_path->rows;
1080
1081         return scan_plan;
1082 }
1083
1084 /*
1085  * Given a bitmapqual tree, generate the Plan tree that implements it
1086  *
1087  * As byproducts, we also return in *qual and *indexqual the qual lists
1088  * (in implicit-AND form, without RestrictInfos) describing the original index
1089  * conditions and the generated indexqual conditions.  The latter is made to
1090  * exclude lossy index operators.  Both lists include partial-index predicates,
1091  * because we have to recheck predicates as well as index conditions if the
1092  * bitmap scan becomes lossy.
1093  *
1094  * Note: if you find yourself changing this, you probably need to change
1095  * make_restrictinfo_from_bitmapqual too.
1096  */
1097 static Plan *
1098 create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
1099                                           List **qual, List **indexqual)
1100 {
1101         Plan       *plan;
1102
1103         if (IsA(bitmapqual, BitmapAndPath))
1104         {
1105                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
1106                 List       *subplans = NIL;
1107                 List       *subquals = NIL;
1108                 List       *subindexquals = NIL;
1109                 ListCell   *l;
1110
1111                 /*
1112                  * There may well be redundant quals among the subplans, since a
1113                  * top-level WHERE qual might have gotten used to form several
1114                  * different index quals.  We don't try exceedingly hard to eliminate
1115                  * redundancies, but we do eliminate obvious duplicates by using
1116                  * list_concat_unique.
1117                  */
1118                 foreach(l, apath->bitmapquals)
1119                 {
1120                         Plan       *subplan;
1121                         List       *subqual;
1122                         List       *subindexqual;
1123
1124                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1125                                                                                         &subqual, &subindexqual);
1126                         subplans = lappend(subplans, subplan);
1127                         subquals = list_concat_unique(subquals, subqual);
1128                         subindexquals = list_concat_unique(subindexquals, subindexqual);
1129                 }
1130                 plan = (Plan *) make_bitmap_and(subplans);
1131                 plan->startup_cost = apath->path.startup_cost;
1132                 plan->total_cost = apath->path.total_cost;
1133                 plan->plan_rows =
1134                         clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
1135                 plan->plan_width = 0;   /* meaningless */
1136                 *qual = subquals;
1137                 *indexqual = subindexquals;
1138         }
1139         else if (IsA(bitmapqual, BitmapOrPath))
1140         {
1141                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
1142                 List       *subplans = NIL;
1143                 List       *subquals = NIL;
1144                 List       *subindexquals = NIL;
1145                 bool            const_true_subqual = false;
1146                 bool            const_true_subindexqual = false;
1147                 ListCell   *l;
1148
1149                 /*
1150                  * Here, we only detect qual-free subplans.  A qual-free subplan would
1151                  * cause us to generate "... OR true ..."  which we may as well reduce
1152                  * to just "true".      We do not try to eliminate redundant subclauses
1153                  * because (a) it's not as likely as in the AND case, and (b) we might
1154                  * well be working with hundreds or even thousands of OR conditions,
1155                  * perhaps from a long IN list.  The performance of list_append_unique
1156                  * would be unacceptable.
1157                  */
1158                 foreach(l, opath->bitmapquals)
1159                 {
1160                         Plan       *subplan;
1161                         List       *subqual;
1162                         List       *subindexqual;
1163
1164                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1165                                                                                         &subqual, &subindexqual);
1166                         subplans = lappend(subplans, subplan);
1167                         if (subqual == NIL)
1168                                 const_true_subqual = true;
1169                         else if (!const_true_subqual)
1170                                 subquals = lappend(subquals,
1171                                                                    make_ands_explicit(subqual));
1172                         if (subindexqual == NIL)
1173                                 const_true_subindexqual = true;
1174                         else if (!const_true_subindexqual)
1175                                 subindexquals = lappend(subindexquals,
1176                                                                                 make_ands_explicit(subindexqual));
1177                 }
1178
1179                 /*
1180                  * In the presence of ScalarArrayOpExpr quals, we might have built
1181                  * BitmapOrPaths with just one subpath; don't add an OR step.
1182                  */
1183                 if (list_length(subplans) == 1)
1184                 {
1185                         plan = (Plan *) linitial(subplans);
1186                 }
1187                 else
1188                 {
1189                         plan = (Plan *) make_bitmap_or(subplans);
1190                         plan->startup_cost = opath->path.startup_cost;
1191                         plan->total_cost = opath->path.total_cost;
1192                         plan->plan_rows =
1193                                 clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
1194                         plan->plan_width = 0;           /* meaningless */
1195                 }
1196
1197                 /*
1198                  * If there were constant-TRUE subquals, the OR reduces to constant
1199                  * TRUE.  Also, avoid generating one-element ORs, which could happen
1200                  * due to redundancy elimination or ScalarArrayOpExpr quals.
1201                  */
1202                 if (const_true_subqual)
1203                         *qual = NIL;
1204                 else if (list_length(subquals) <= 1)
1205                         *qual = subquals;
1206                 else
1207                         *qual = list_make1(make_orclause(subquals));
1208                 if (const_true_subindexqual)
1209                         *indexqual = NIL;
1210                 else if (list_length(subindexquals) <= 1)
1211                         *indexqual = subindexquals;
1212                 else
1213                         *indexqual = list_make1(make_orclause(subindexquals));
1214         }
1215         else if (IsA(bitmapqual, IndexPath))
1216         {
1217                 IndexPath  *ipath = (IndexPath *) bitmapqual;
1218                 IndexScan  *iscan;
1219                 List       *nonlossy_clauses;
1220                 ListCell   *l;
1221
1222                 /* Use the regular indexscan plan build machinery... */
1223                 iscan = create_indexscan_plan(root, ipath, NIL, NIL,
1224                                                                           &nonlossy_clauses);
1225                 /* then convert to a bitmap indexscan */
1226                 plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
1227                                                                                           iscan->indexid,
1228                                                                                           iscan->indexqual,
1229                                                                                           iscan->indexqualorig,
1230                                                                                           iscan->indexstrategy,
1231                                                                                           iscan->indexsubtype);
1232                 plan->startup_cost = 0.0;
1233                 plan->total_cost = ipath->indextotalcost;
1234                 plan->plan_rows =
1235                         clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
1236                 plan->plan_width = 0;   /* meaningless */
1237                 *qual = get_actual_clauses(ipath->indexclauses);
1238                 *indexqual = get_actual_clauses(nonlossy_clauses);
1239                 foreach(l, ipath->indexinfo->indpred)
1240                 {
1241                         Expr       *pred = (Expr *) lfirst(l);
1242
1243                         /*
1244                          * We know that the index predicate must have been implied by the
1245                          * query condition as a whole, but it may or may not be implied by
1246                          * the conditions that got pushed into the bitmapqual.  Avoid
1247                          * generating redundant conditions.
1248                          */
1249                         if (!predicate_implied_by(list_make1(pred), ipath->indexclauses))
1250                         {
1251                                 *qual = lappend(*qual, pred);
1252                                 *indexqual = lappend(*indexqual, pred);
1253                         }
1254                 }
1255         }
1256         else
1257         {
1258                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
1259                 plan = NULL;                    /* keep compiler quiet */
1260         }
1261
1262         return plan;
1263 }
1264
1265 /*
1266  * create_tidscan_plan
1267  *       Returns a tidscan plan for the base relation scanned by 'best_path'
1268  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1269  */
1270 static TidScan *
1271 create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
1272                                         List *tlist, List *scan_clauses)
1273 {
1274         TidScan    *scan_plan;
1275         Index           scan_relid = best_path->path.parent->relid;
1276         List       *ortidquals;
1277
1278         /* it should be a base rel... */
1279         Assert(scan_relid > 0);
1280         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1281
1282         /* Sort clauses into best execution order */
1283         scan_clauses = order_qual_clauses(root, scan_clauses);
1284
1285         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1286         scan_clauses = extract_actual_clauses(scan_clauses, false);
1287
1288         /*
1289          * Remove any clauses that are TID quals.  This is a bit tricky since the
1290          * tidquals list has implicit OR semantics.
1291          */
1292         ortidquals = best_path->tidquals;
1293         if (list_length(ortidquals) > 1)
1294                 ortidquals = list_make1(make_orclause(ortidquals));
1295         scan_clauses = list_difference(scan_clauses, ortidquals);
1296
1297         scan_plan = make_tidscan(tlist,
1298                                                          scan_clauses,
1299                                                          scan_relid,
1300                                                          best_path->tidquals);
1301
1302         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1303
1304         return scan_plan;
1305 }
1306
1307 /*
1308  * create_subqueryscan_plan
1309  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
1310  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1311  */
1312 static SubqueryScan *
1313 create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
1314                                                  List *tlist, List *scan_clauses)
1315 {
1316         SubqueryScan *scan_plan;
1317         Index           scan_relid = best_path->parent->relid;
1318
1319         /* it should be a subquery base rel... */
1320         Assert(scan_relid > 0);
1321         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
1322
1323         /* Sort clauses into best execution order */
1324         scan_clauses = order_qual_clauses(root, scan_clauses);
1325
1326         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1327         scan_clauses = extract_actual_clauses(scan_clauses, false);
1328
1329         scan_plan = make_subqueryscan(tlist,
1330                                                                   scan_clauses,
1331                                                                   scan_relid,
1332                                                                   best_path->parent->subplan,
1333                                                                   best_path->parent->subrtable);
1334
1335         copy_path_costsize(&scan_plan->scan.plan, best_path);
1336
1337         return scan_plan;
1338 }
1339
1340 /*
1341  * create_functionscan_plan
1342  *       Returns a functionscan plan for the base relation scanned by 'best_path'
1343  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1344  */
1345 static FunctionScan *
1346 create_functionscan_plan(PlannerInfo *root, Path *best_path,
1347                                                  List *tlist, List *scan_clauses)
1348 {
1349         FunctionScan *scan_plan;
1350         Index           scan_relid = best_path->parent->relid;
1351         RangeTblEntry *rte;
1352
1353         /* it should be a function base rel... */
1354         Assert(scan_relid > 0);
1355         rte = rt_fetch(scan_relid, root->parse->rtable);
1356         Assert(rte->rtekind == RTE_FUNCTION);
1357
1358         /* Sort clauses into best execution order */
1359         scan_clauses = order_qual_clauses(root, scan_clauses);
1360
1361         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1362         scan_clauses = extract_actual_clauses(scan_clauses, false);
1363
1364         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
1365                                                                   rte->funcexpr,
1366                                                                   rte->eref->colnames,
1367                                                                   rte->funccoltypes,
1368                                                                   rte->funccoltypmods);
1369
1370         copy_path_costsize(&scan_plan->scan.plan, best_path);
1371
1372         return scan_plan;
1373 }
1374
1375 /*
1376  * create_valuesscan_plan
1377  *       Returns a valuesscan plan for the base relation scanned by 'best_path'
1378  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1379  */
1380 static ValuesScan *
1381 create_valuesscan_plan(PlannerInfo *root, Path *best_path,
1382                                            List *tlist, List *scan_clauses)
1383 {
1384         ValuesScan *scan_plan;
1385         Index           scan_relid = best_path->parent->relid;
1386         RangeTblEntry *rte;
1387
1388         /* it should be a values base rel... */
1389         Assert(scan_relid > 0);
1390         rte = rt_fetch(scan_relid, root->parse->rtable);
1391         Assert(rte->rtekind == RTE_VALUES);
1392
1393         /* Sort clauses into best execution order */
1394         scan_clauses = order_qual_clauses(root, scan_clauses);
1395
1396         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1397         scan_clauses = extract_actual_clauses(scan_clauses, false);
1398
1399         scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
1400                                                                 rte->values_lists);
1401
1402         copy_path_costsize(&scan_plan->scan.plan, best_path);
1403
1404         return scan_plan;
1405 }
1406
1407 /*****************************************************************************
1408  *
1409  *      JOIN METHODS
1410  *
1411  *****************************************************************************/
1412
1413 static NestLoop *
1414 create_nestloop_plan(PlannerInfo *root,
1415                                          NestPath *best_path,
1416                                          Plan *outer_plan,
1417                                          Plan *inner_plan)
1418 {
1419         List       *tlist = build_relation_tlist(best_path->path.parent);
1420         List       *joinrestrictclauses = best_path->joinrestrictinfo;
1421         List       *joinclauses;
1422         List       *otherclauses;
1423         NestLoop   *join_plan;
1424
1425         if (IsA(best_path->innerjoinpath, IndexPath))
1426         {
1427                 /*
1428                  * An index is being used to reduce the number of tuples scanned in
1429                  * the inner relation.  If there are join clauses being used with the
1430                  * index, we may remove those join clauses from the list of clauses
1431                  * that have to be checked as qpquals at the join node.
1432                  *
1433                  * We can also remove any join clauses that are redundant with those
1434                  * being used in the index scan; this check is needed because
1435                  * find_eclass_clauses_for_index_join() may emit different clauses
1436                  * than generate_join_implied_equalities() did.
1437                  *
1438                  * We can skip this if the index path is an ordinary indexpath and not
1439                  * a special innerjoin path, since it then wouldn't be using any join
1440                  * clauses.
1441                  */
1442                 IndexPath  *innerpath = (IndexPath *) best_path->innerjoinpath;
1443
1444                 if (innerpath->isjoininner)
1445                         joinrestrictclauses =
1446                                 select_nonredundant_join_clauses(root,
1447                                                                                                  joinrestrictclauses,
1448                                                                                                  innerpath->indexclauses);
1449         }
1450         else if (IsA(best_path->innerjoinpath, BitmapHeapPath))
1451         {
1452                 /*
1453                  * Same deal for bitmapped index scans.
1454                  *
1455                  * Note: both here and above, we ignore any implicit index
1456                  * restrictions associated with the use of partial indexes.  This is
1457                  * OK because we're only trying to prove we can dispense with some
1458                  * join quals; failing to prove that doesn't result in an incorrect
1459                  * plan.  It is the right way to proceed because adding more quals to
1460                  * the stuff we got from the original query would just make it harder
1461                  * to detect duplication.  (Also, to change this we'd have to be wary
1462                  * of UPDATE/DELETE/SELECT FOR UPDATE target relations; see notes
1463                  * above about EvalPlanQual.)
1464                  */
1465                 BitmapHeapPath *innerpath = (BitmapHeapPath *) best_path->innerjoinpath;
1466
1467                 if (innerpath->isjoininner)
1468                 {
1469                         List       *bitmapclauses;
1470
1471                         bitmapclauses =
1472                                 make_restrictinfo_from_bitmapqual(innerpath->bitmapqual,
1473                                                                                                   true,
1474                                                                                                   false);
1475                         joinrestrictclauses =
1476                                 select_nonredundant_join_clauses(root,
1477                                                                                                  joinrestrictclauses,
1478                                                                                                  bitmapclauses);
1479                 }
1480         }
1481
1482         /* Sort join qual clauses into best execution order */
1483         joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
1484
1485         /* Get the join qual clauses (in plain expression form) */
1486         /* Any pseudoconstant clauses are ignored here */
1487         if (IS_OUTER_JOIN(best_path->jointype))
1488         {
1489                 extract_actual_join_clauses(joinrestrictclauses,
1490                                                                         &joinclauses, &otherclauses);
1491         }
1492         else
1493         {
1494                 /* We can treat all clauses alike for an inner join */
1495                 joinclauses = extract_actual_clauses(joinrestrictclauses, false);
1496                 otherclauses = NIL;
1497         }
1498
1499         join_plan = make_nestloop(tlist,
1500                                                           joinclauses,
1501                                                           otherclauses,
1502                                                           outer_plan,
1503                                                           inner_plan,
1504                                                           best_path->jointype);
1505
1506         copy_path_costsize(&join_plan->join.plan, &best_path->path);
1507
1508         return join_plan;
1509 }
1510
1511 static MergeJoin *
1512 create_mergejoin_plan(PlannerInfo *root,
1513                                           MergePath *best_path,
1514                                           Plan *outer_plan,
1515                                           Plan *inner_plan)
1516 {
1517         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1518         List       *joinclauses;
1519         List       *otherclauses;
1520         List       *mergeclauses;
1521         List       *outerpathkeys;
1522         List       *innerpathkeys;
1523         int                     nClauses;
1524         Oid                *mergefamilies;
1525         int                *mergestrategies;
1526         bool       *mergenullsfirst;
1527         MergeJoin  *join_plan;
1528         int                     i;
1529         EquivalenceClass *lastoeclass;
1530         EquivalenceClass *lastieclass;
1531         PathKey    *opathkey;
1532         PathKey    *ipathkey;
1533         ListCell   *lc;
1534         ListCell   *lop;
1535         ListCell   *lip;
1536
1537         /* Sort join qual clauses into best execution order */
1538         /* NB: do NOT reorder the mergeclauses */
1539         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
1540
1541         /* Get the join qual clauses (in plain expression form) */
1542         /* Any pseudoconstant clauses are ignored here */
1543         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1544         {
1545                 extract_actual_join_clauses(joinclauses,
1546                                                                         &joinclauses, &otherclauses);
1547         }
1548         else
1549         {
1550                 /* We can treat all clauses alike for an inner join */
1551                 joinclauses = extract_actual_clauses(joinclauses, false);
1552                 otherclauses = NIL;
1553         }
1554
1555         /*
1556          * Remove the mergeclauses from the list of join qual clauses, leaving the
1557          * list of quals that must be checked as qpquals.
1558          */
1559         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
1560         joinclauses = list_difference(joinclauses, mergeclauses);
1561
1562         /*
1563          * Rearrange mergeclauses, if needed, so that the outer variable is always
1564          * on the left; mark the mergeclause restrictinfos with correct
1565          * outer_is_left status.
1566          */
1567         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
1568                                                          best_path->jpath.outerjoinpath->parent->relids);
1569
1570         /*
1571          * Create explicit sort nodes for the outer and inner join paths if
1572          * necessary.  The sort cost was already accounted for in the path. Make
1573          * sure there are no excess columns in the inputs if sorting.
1574          */
1575         if (best_path->outersortkeys)
1576         {
1577                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
1578                 outer_plan = (Plan *)
1579                         make_sort_from_pathkeys(root,
1580                                                                         outer_plan,
1581                                                                         best_path->outersortkeys);
1582                 outerpathkeys = best_path->outersortkeys;
1583         }
1584         else
1585                 outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;
1586
1587         if (best_path->innersortkeys)
1588         {
1589                 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1590                 inner_plan = (Plan *)
1591                         make_sort_from_pathkeys(root,
1592                                                                         inner_plan,
1593                                                                         best_path->innersortkeys);
1594                 innerpathkeys = best_path->innersortkeys;
1595         }
1596         else
1597                 innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;
1598
1599         /*
1600          * Compute the opfamily/strategy/nullsfirst arrays needed by the executor.
1601          * The information is in the pathkeys for the two inputs, but we need to
1602          * be careful about the possibility of mergeclauses sharing a pathkey
1603          * (compare find_mergeclauses_for_pathkeys()).
1604          */
1605         nClauses = list_length(mergeclauses);
1606         Assert(nClauses == list_length(best_path->path_mergeclauses));
1607         mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
1608         mergestrategies = (int *) palloc(nClauses * sizeof(int));
1609         mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));
1610
1611         lastoeclass = NULL;
1612         lastieclass = NULL;
1613         opathkey = NULL;
1614         ipathkey = NULL;
1615         lop = list_head(outerpathkeys);
1616         lip = list_head(innerpathkeys);
1617         i = 0;
1618         foreach(lc, best_path->path_mergeclauses)
1619         {
1620                 RestrictInfo   *rinfo = (RestrictInfo *) lfirst(lc);
1621                 EquivalenceClass *oeclass;
1622                 EquivalenceClass *ieclass;
1623
1624                 /* fetch outer/inner eclass from mergeclause */
1625                 Assert(IsA(rinfo, RestrictInfo));
1626                 if (rinfo->outer_is_left)
1627                 {
1628                         oeclass = rinfo->left_ec;
1629                         ieclass = rinfo->right_ec;
1630                 }
1631                 else
1632                 {
1633                         oeclass = rinfo->right_ec;
1634                         ieclass = rinfo->left_ec;
1635                 }
1636                 Assert(oeclass != NULL);
1637                 Assert(ieclass != NULL);
1638
1639                 /* should match current or next pathkeys */
1640                 /* we check this carefully for debugging reasons */
1641                 if (oeclass != lastoeclass)
1642                 {
1643                         if (!lop)
1644                                 elog(ERROR, "too few pathkeys for mergeclauses");
1645                         opathkey = (PathKey *) lfirst(lop);
1646                         lop = lnext(lop);
1647                         lastoeclass = opathkey->pk_eclass;
1648                         if (oeclass != lastoeclass)
1649                                 elog(ERROR, "outer pathkeys do not match mergeclause");
1650                 }
1651                 if (ieclass != lastieclass)
1652                 {
1653                         if (!lip)
1654                                 elog(ERROR, "too few pathkeys for mergeclauses");
1655                         ipathkey = (PathKey *) lfirst(lip);
1656                         lip = lnext(lip);
1657                         lastieclass = ipathkey->pk_eclass;
1658                         if (ieclass != lastieclass)
1659                                 elog(ERROR, "inner pathkeys do not match mergeclause");
1660                 }
1661                 /* pathkeys should match each other too (more debugging) */
1662                 if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
1663                         opathkey->pk_strategy != ipathkey->pk_strategy ||
1664                         opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
1665                         elog(ERROR, "left and right pathkeys do not match in mergejoin");
1666
1667                 /* OK, save info for executor */
1668                 mergefamilies[i] = opathkey->pk_opfamily;
1669                 mergestrategies[i] = opathkey->pk_strategy;
1670                 mergenullsfirst[i] = opathkey->pk_nulls_first;
1671                 i++;
1672         }
1673
1674
1675         /*
1676          * Now we can build the mergejoin node.
1677          */
1678         join_plan = make_mergejoin(tlist,
1679                                                            joinclauses,
1680                                                            otherclauses,
1681                                                            mergeclauses,
1682                                                            mergefamilies,
1683                                                            mergestrategies,
1684                                                            mergenullsfirst,
1685                                                            outer_plan,
1686                                                            inner_plan,
1687                                                            best_path->jpath.jointype);
1688
1689         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1690
1691         return join_plan;
1692 }
1693
1694 static HashJoin *
1695 create_hashjoin_plan(PlannerInfo *root,
1696                                          HashPath *best_path,
1697                                          Plan *outer_plan,
1698                                          Plan *inner_plan)
1699 {
1700         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1701         List       *joinclauses;
1702         List       *otherclauses;
1703         List       *hashclauses;
1704         HashJoin   *join_plan;
1705         Hash       *hash_plan;
1706
1707         /* Sort join qual clauses into best execution order */
1708         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
1709         /* There's no point in sorting the hash clauses ... */
1710
1711         /* Get the join qual clauses (in plain expression form) */
1712         /* Any pseudoconstant clauses are ignored here */
1713         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1714         {
1715                 extract_actual_join_clauses(joinclauses,
1716                                                                         &joinclauses, &otherclauses);
1717         }
1718         else
1719         {
1720                 /* We can treat all clauses alike for an inner join */
1721                 joinclauses = extract_actual_clauses(joinclauses, false);
1722                 otherclauses = NIL;
1723         }
1724
1725         /*
1726          * Remove the hashclauses from the list of join qual clauses, leaving the
1727          * list of quals that must be checked as qpquals.
1728          */
1729         hashclauses = get_actual_clauses(best_path->path_hashclauses);
1730         joinclauses = list_difference(joinclauses, hashclauses);
1731
1732         /*
1733          * Rearrange hashclauses, if needed, so that the outer variable is always
1734          * on the left.
1735          */
1736         hashclauses = get_switched_clauses(best_path->path_hashclauses,
1737                                                          best_path->jpath.outerjoinpath->parent->relids);
1738
1739         /* We don't want any excess columns in the hashed tuples */
1740         disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1741
1742         /*
1743          * Build the hash node and hash join node.
1744          */
1745         hash_plan = make_hash(inner_plan);
1746         join_plan = make_hashjoin(tlist,
1747                                                           joinclauses,
1748                                                           otherclauses,
1749                                                           hashclauses,
1750                                                           outer_plan,
1751                                                           (Plan *) hash_plan,
1752                                                           best_path->jpath.jointype);
1753
1754         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
1755
1756         return join_plan;
1757 }
1758
1759
1760 /*****************************************************************************
1761  *
1762  *      SUPPORTING ROUTINES
1763  *
1764  *****************************************************************************/
1765
1766 /*
1767  * fix_indexqual_references
1768  *        Adjust indexqual clauses to the form the executor's indexqual
1769  *        machinery needs, and check for recheckable (lossy) index conditions.
1770  *
1771  * We have five tasks here:
1772  *      * Remove RestrictInfo nodes from the input clauses.
1773  *      * Index keys must be represented by Var nodes with varattno set to the
1774  *        index's attribute number, not the attribute number in the original rel.
1775  *      * If the index key is on the right, commute the clause to put it on the
1776  *        left.
1777  *      * We must construct lists of operator strategy numbers and subtypes
1778  *        for the top-level operators of each index clause.
1779  *      * We must detect any lossy index operators.  The API is that we return
1780  *        a list of the input clauses whose operators are NOT lossy.
1781  *
1782  * fixed_indexquals receives a modified copy of the indexquals list --- the
1783  * original is not changed.  Note also that the copy shares no substructure
1784  * with the original; this is needed in case there is a subplan in it (we need
1785  * two separate copies of the subplan tree, or things will go awry).
1786  *
1787  * nonlossy_indexquals receives a list of the original input clauses (with
1788  * RestrictInfos) that contain non-lossy operators.
1789  *
1790  * indexstrategy receives an integer list of strategy numbers.
1791  * indexsubtype receives an OID list of strategy subtypes.
1792  */
1793 static void
1794 fix_indexqual_references(List *indexquals, IndexPath *index_path,
1795                                                  List **fixed_indexquals,
1796                                                  List **nonlossy_indexquals,
1797                                                  List **indexstrategy,
1798                                                  List **indexsubtype)
1799 {
1800         IndexOptInfo *index = index_path->indexinfo;
1801         ListCell   *l;
1802
1803         *fixed_indexquals = NIL;
1804         *nonlossy_indexquals = NIL;
1805         *indexstrategy = NIL;
1806         *indexsubtype = NIL;
1807
1808         /*
1809          * For each qual clause, commute if needed to put the indexkey operand on
1810          * the left, and then fix its varattno.  (We do not need to change the
1811          * other side of the clause.)  Then determine the operator's strategy
1812          * number and subtype number, and check for lossy index behavior.
1813          */
1814         foreach(l, indexquals)
1815         {
1816                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1817                 Expr       *clause;
1818                 Oid                     clause_op;
1819                 Oid                     opfamily;
1820                 int                     stratno;
1821                 Oid                     stratlefttype;
1822                 Oid                     stratrighttype;
1823                 bool            recheck;
1824
1825                 Assert(IsA(rinfo, RestrictInfo));
1826
1827                 /*
1828                  * Make a copy that will become the fixed clause.
1829                  *
1830                  * We used to try to do a shallow copy here, but that fails if there
1831                  * is a subplan in the arguments of the opclause.  So just do a full
1832                  * copy.
1833                  */
1834                 clause = (Expr *) copyObject((Node *) rinfo->clause);
1835
1836                 if (IsA(clause, OpExpr))
1837                 {
1838                         OpExpr     *op = (OpExpr *) clause;
1839
1840                         if (list_length(op->args) != 2)
1841                                 elog(ERROR, "indexqual clause is not binary opclause");
1842
1843                         /*
1844                          * Check to see if the indexkey is on the right; if so, commute
1845                          * the clause. The indexkey should be the side that refers to
1846                          * (only) the base relation.
1847                          */
1848                         if (!bms_equal(rinfo->left_relids, index->rel->relids))
1849                                 CommuteOpExpr(op);
1850
1851                         /*
1852                          * Now, determine which index attribute this is, change the
1853                          * indexkey operand as needed, and get the index opfamily.
1854                          */
1855                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
1856                                                                                                            index,
1857                                                                                                            &opfamily);
1858                         clause_op = op->opno;
1859                 }
1860                 else if (IsA(clause, RowCompareExpr))
1861                 {
1862                         RowCompareExpr *rc = (RowCompareExpr *) clause;
1863                         ListCell   *lc;
1864
1865                         /*
1866                          * Check to see if the indexkey is on the right; if so, commute
1867                          * the clause. The indexkey should be the side that refers to
1868                          * (only) the base relation.
1869                          */
1870                         if (!bms_overlap(pull_varnos(linitial(rc->largs)),
1871                                                          index->rel->relids))
1872                                 CommuteRowCompareExpr(rc);
1873
1874                         /*
1875                          * For each column in the row comparison, determine which index
1876                          * attribute this is and change the indexkey operand as needed.
1877                          *
1878                          * Save the index opfamily for only the first column.  We will
1879                          * return the operator and opfamily info for just the first column
1880                          * of the row comparison; the executor will have to look up the
1881                          * rest if it needs them.
1882                          */
1883                         foreach(lc, rc->largs)
1884                         {
1885                                 Oid                     tmp_opfamily;
1886
1887                                 lfirst(lc) = fix_indexqual_operand(lfirst(lc),
1888                                                                                                    index,
1889                                                                                                    &tmp_opfamily);
1890                                 if (lc == list_head(rc->largs))
1891                                         opfamily = tmp_opfamily;
1892                         }
1893                         clause_op = linitial_oid(rc->opnos);
1894                 }
1895                 else if (IsA(clause, ScalarArrayOpExpr))
1896                 {
1897                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
1898
1899                         /* Never need to commute... */
1900
1901                         /*
1902                          * Now, determine which index attribute this is, change the
1903                          * indexkey operand as needed, and get the index opfamily.
1904                          */
1905                         linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
1906                                                                                                                  index,
1907                                                                                                                  &opfamily);
1908                         clause_op = saop->opno;
1909                 }
1910                 else
1911                 {
1912                         elog(ERROR, "unsupported indexqual type: %d",
1913                                  (int) nodeTag(clause));
1914                         continue;                       /* keep compiler quiet */
1915                 }
1916
1917                 *fixed_indexquals = lappend(*fixed_indexquals, clause);
1918
1919                 /*
1920                  * Look up the (possibly commuted) operator in the operator family to
1921                  * get its strategy number and the recheck indicator.   This also
1922                  * double-checks that we found an operator matching the index.
1923                  */
1924                 get_op_opfamily_properties(clause_op, opfamily,
1925                                                                    &stratno,
1926                                                                    &stratlefttype,
1927                                                                    &stratrighttype,
1928                                                                    &recheck);
1929
1930                 *indexstrategy = lappend_int(*indexstrategy, stratno);
1931                 *indexsubtype = lappend_oid(*indexsubtype, stratrighttype);
1932
1933                 /* If it's not lossy, add to nonlossy_indexquals */
1934                 if (!recheck)
1935                         *nonlossy_indexquals = lappend(*nonlossy_indexquals, rinfo);
1936         }
1937 }
1938
1939 static Node *
1940 fix_indexqual_operand(Node *node, IndexOptInfo *index, Oid *opfamily)
1941 {
1942         /*
1943          * We represent index keys by Var nodes having the varno of the base table
1944          * but varattno equal to the index's attribute number (index column
1945          * position).  This is a bit hokey ... would be cleaner to use a
1946          * special-purpose node type that could not be mistaken for a regular Var.
1947          * But it will do for now.
1948          */
1949         Var                *result;
1950         int                     pos;
1951         ListCell   *indexpr_item;
1952
1953         /*
1954          * Remove any binary-compatible relabeling of the indexkey
1955          */
1956         if (IsA(node, RelabelType))
1957                 node = (Node *) ((RelabelType *) node)->arg;
1958
1959         if (IsA(node, Var) &&
1960                 ((Var *) node)->varno == index->rel->relid)
1961         {
1962                 /* Try to match against simple index columns */
1963                 int                     varatt = ((Var *) node)->varattno;
1964
1965                 if (varatt != 0)
1966                 {
1967                         for (pos = 0; pos < index->ncolumns; pos++)
1968                         {
1969                                 if (index->indexkeys[pos] == varatt)
1970                                 {
1971                                         result = (Var *) copyObject(node);
1972                                         result->varattno = pos + 1;
1973                                         /* return the correct opfamily, too */
1974                                         *opfamily = index->opfamily[pos];
1975                                         return (Node *) result;
1976                                 }
1977                         }
1978                 }
1979         }
1980
1981         /* Try to match against index expressions */
1982         indexpr_item = list_head(index->indexprs);
1983         for (pos = 0; pos < index->ncolumns; pos++)
1984         {
1985                 if (index->indexkeys[pos] == 0)
1986                 {
1987                         Node       *indexkey;
1988
1989                         if (indexpr_item == NULL)
1990                                 elog(ERROR, "too few entries in indexprs list");
1991                         indexkey = (Node *) lfirst(indexpr_item);
1992                         if (indexkey && IsA(indexkey, RelabelType))
1993                                 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
1994                         if (equal(node, indexkey))
1995                         {
1996                                 /* Found a match */
1997                                 result = makeVar(index->rel->relid, pos + 1,
1998                                                                  exprType(lfirst(indexpr_item)), -1,
1999                                                                  0);
2000                                 /* return the correct opfamily, too */
2001                                 *opfamily = index->opfamily[pos];
2002                                 return (Node *) result;
2003                         }
2004                         indexpr_item = lnext(indexpr_item);
2005                 }
2006         }
2007
2008         /* Ooops... */
2009         elog(ERROR, "node is not an index attribute");
2010         *opfamily = InvalidOid;         /* keep compiler quiet */
2011         return NULL;
2012 }
2013
2014 /*
2015  * get_switched_clauses
2016  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
2017  *        extract the bare clauses, and rearrange the elements within the
2018  *        clauses, if needed, so the outer join variable is on the left and
2019  *        the inner is on the right.  The original clause data structure is not
2020  *        touched; a modified list is returned.  We do, however, set the transient
2021  *        outer_is_left field in each RestrictInfo to show which side was which.
2022  */
2023 static List *
2024 get_switched_clauses(List *clauses, Relids outerrelids)
2025 {
2026         List       *t_list = NIL;
2027         ListCell   *l;
2028
2029         foreach(l, clauses)
2030         {
2031                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2032                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
2033
2034                 Assert(is_opclause(clause));
2035                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
2036                 {
2037                         /*
2038                          * Duplicate just enough of the structure to allow commuting the
2039                          * clause without changing the original list.  Could use
2040                          * copyObject, but a complete deep copy is overkill.
2041                          */
2042                         OpExpr     *temp = makeNode(OpExpr);
2043
2044                         temp->opno = clause->opno;
2045                         temp->opfuncid = InvalidOid;
2046                         temp->opresulttype = clause->opresulttype;
2047                         temp->opretset = clause->opretset;
2048                         temp->args = list_copy(clause->args);
2049                         /* Commute it --- note this modifies the temp node in-place. */
2050                         CommuteOpExpr(temp);
2051                         t_list = lappend(t_list, temp);
2052                         restrictinfo->outer_is_left = false;
2053                 }
2054                 else
2055                 {
2056                         Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
2057                         t_list = lappend(t_list, clause);
2058                         restrictinfo->outer_is_left = true;
2059                 }
2060         }
2061         return t_list;
2062 }
2063
2064 /*
2065  * order_qual_clauses
2066  *              Given a list of qual clauses that will all be evaluated at the same
2067  *              plan node, sort the list into the order we want to check the quals
2068  *              in at runtime.
2069  *
2070  * Ideally the order should be driven by a combination of execution cost and
2071  * selectivity, but it's not immediately clear how to account for both,
2072  * and given the uncertainty of the estimates the reliability of the decisions
2073  * would be doubtful anyway.  So we just order by estimated per-tuple cost,
2074  * being careful not to change the order when (as is often the case) the
2075  * estimates are identical.
2076  *
2077  * Although this will work on either bare clauses or RestrictInfos, it's
2078  * much faster to apply it to RestrictInfos, since it can re-use cost
2079  * information that is cached in RestrictInfos.
2080  *
2081  * Note: some callers pass lists that contain entries that will later be
2082  * removed; this is the easiest way to let this routine see RestrictInfos
2083  * instead of bare clauses.  It's OK because we only sort by cost, but
2084  * a cost/selectivity combination would likely do the wrong thing.
2085  */
2086 static List *
2087 order_qual_clauses(PlannerInfo *root, List *clauses)
2088 {
2089         typedef struct
2090         {
2091                 Node   *clause;
2092                 Cost    cost;
2093         } QualItem;
2094         int                     nitems = list_length(clauses);
2095         QualItem   *items;
2096         ListCell   *lc;
2097         int                     i;
2098         List       *result;
2099
2100         /* No need to work hard for 0 or 1 clause */
2101         if (nitems <= 1)
2102                 return clauses;
2103
2104         /*
2105          * Collect the items and costs into an array.  This is to avoid repeated
2106          * cost_qual_eval work if the inputs aren't RestrictInfos.
2107          */
2108         items = (QualItem *) palloc(nitems * sizeof(QualItem));
2109         i = 0;
2110         foreach(lc, clauses)
2111         {
2112                 Node       *clause = (Node *) lfirst(lc);
2113                 QualCost        qcost;
2114
2115                 cost_qual_eval_node(&qcost, clause, root);
2116                 items[i].clause = clause;
2117                 items[i].cost = qcost.per_tuple;
2118                 i++;
2119         }
2120
2121         /*
2122          * Sort.  We don't use qsort() because it's not guaranteed stable for
2123          * equal keys.  The expected number of entries is small enough that
2124          * a simple insertion sort should be good enough.
2125          */
2126         for (i = 1; i < nitems; i++)
2127         {
2128                 QualItem        newitem = items[i];
2129                 int                     j;
2130
2131                 /* insert newitem into the already-sorted subarray */
2132                 for (j = i; j > 0; j--)
2133                 {
2134                         if (newitem.cost >= items[j-1].cost)
2135                                 break;
2136                         items[j] = items[j-1];
2137                 }
2138                 items[j] = newitem;
2139         }
2140
2141         /* Convert back to a list */
2142         result = NIL;
2143         for (i = 0; i < nitems; i++)
2144                 result = lappend(result, items[i].clause);
2145
2146         return result;
2147 }
2148
2149 /*
2150  * Copy cost and size info from a Path node to the Plan node created from it.
2151  * The executor won't use this info, but it's needed by EXPLAIN.
2152  */
2153 static void
2154 copy_path_costsize(Plan *dest, Path *src)
2155 {
2156         if (src)
2157         {
2158                 dest->startup_cost = src->startup_cost;
2159                 dest->total_cost = src->total_cost;
2160                 dest->plan_rows = src->parent->rows;
2161                 dest->plan_width = src->parent->width;
2162         }
2163         else
2164         {
2165                 dest->startup_cost = 0;
2166                 dest->total_cost = 0;
2167                 dest->plan_rows = 0;
2168                 dest->plan_width = 0;
2169         }
2170 }
2171
2172 /*
2173  * Copy cost and size info from a lower plan node to an inserted node.
2174  * This is not critical, since the decisions have already been made,
2175  * but it helps produce more reasonable-looking EXPLAIN output.
2176  * (Some callers alter the info after copying it.)
2177  */
2178 static void
2179 copy_plan_costsize(Plan *dest, Plan *src)
2180 {
2181         if (src)
2182         {
2183                 dest->startup_cost = src->startup_cost;
2184                 dest->total_cost = src->total_cost;
2185                 dest->plan_rows = src->plan_rows;
2186                 dest->plan_width = src->plan_width;
2187         }
2188         else
2189         {
2190                 dest->startup_cost = 0;
2191                 dest->total_cost = 0;
2192                 dest->plan_rows = 0;
2193                 dest->plan_width = 0;
2194         }
2195 }
2196
2197
2198 /*****************************************************************************
2199  *
2200  *      PLAN NODE BUILDING ROUTINES
2201  *
2202  * Some of these are exported because they are called to build plan nodes
2203  * in contexts where we're not deriving the plan node from a path node.
2204  *
2205  *****************************************************************************/
2206
2207 static SeqScan *
2208 make_seqscan(List *qptlist,
2209                          List *qpqual,
2210                          Index scanrelid)
2211 {
2212         SeqScan    *node = makeNode(SeqScan);
2213         Plan       *plan = &node->plan;
2214
2215         /* cost should be inserted by caller */
2216         plan->targetlist = qptlist;
2217         plan->qual = qpqual;
2218         plan->lefttree = NULL;
2219         plan->righttree = NULL;
2220         node->scanrelid = scanrelid;
2221
2222         return node;
2223 }
2224
2225 static IndexScan *
2226 make_indexscan(List *qptlist,
2227                            List *qpqual,
2228                            Index scanrelid,
2229                            Oid indexid,
2230                            List *indexqual,
2231                            List *indexqualorig,
2232                            List *indexstrategy,
2233                            List *indexsubtype,
2234                            ScanDirection indexscandir)
2235 {
2236         IndexScan  *node = makeNode(IndexScan);
2237         Plan       *plan = &node->scan.plan;
2238
2239         /* cost should be inserted by caller */
2240         plan->targetlist = qptlist;
2241         plan->qual = qpqual;
2242         plan->lefttree = NULL;
2243         plan->righttree = NULL;
2244         node->scan.scanrelid = scanrelid;
2245         node->indexid = indexid;
2246         node->indexqual = indexqual;
2247         node->indexqualorig = indexqualorig;
2248         node->indexstrategy = indexstrategy;
2249         node->indexsubtype = indexsubtype;
2250         node->indexorderdir = indexscandir;
2251
2252         return node;
2253 }
2254
2255 static BitmapIndexScan *
2256 make_bitmap_indexscan(Index scanrelid,
2257                                           Oid indexid,
2258                                           List *indexqual,
2259                                           List *indexqualorig,
2260                                           List *indexstrategy,
2261                                           List *indexsubtype)
2262 {
2263         BitmapIndexScan *node = makeNode(BitmapIndexScan);
2264         Plan       *plan = &node->scan.plan;
2265
2266         /* cost should be inserted by caller */
2267         plan->targetlist = NIL;         /* not used */
2268         plan->qual = NIL;                       /* not used */
2269         plan->lefttree = NULL;
2270         plan->righttree = NULL;
2271         node->scan.scanrelid = scanrelid;
2272         node->indexid = indexid;
2273         node->indexqual = indexqual;
2274         node->indexqualorig = indexqualorig;
2275         node->indexstrategy = indexstrategy;
2276         node->indexsubtype = indexsubtype;
2277
2278         return node;
2279 }
2280
2281 static BitmapHeapScan *
2282 make_bitmap_heapscan(List *qptlist,
2283                                          List *qpqual,
2284                                          Plan *lefttree,
2285                                          List *bitmapqualorig,
2286                                          Index scanrelid)
2287 {
2288         BitmapHeapScan *node = makeNode(BitmapHeapScan);
2289         Plan       *plan = &node->scan.plan;
2290
2291         /* cost should be inserted by caller */
2292         plan->targetlist = qptlist;
2293         plan->qual = qpqual;
2294         plan->lefttree = lefttree;
2295         plan->righttree = NULL;
2296         node->scan.scanrelid = scanrelid;
2297         node->bitmapqualorig = bitmapqualorig;
2298
2299         return node;
2300 }
2301
2302 static TidScan *
2303 make_tidscan(List *qptlist,
2304                          List *qpqual,
2305                          Index scanrelid,
2306                          List *tidquals)
2307 {
2308         TidScan    *node = makeNode(TidScan);
2309         Plan       *plan = &node->scan.plan;
2310
2311         /* cost should be inserted by caller */
2312         plan->targetlist = qptlist;
2313         plan->qual = qpqual;
2314         plan->lefttree = NULL;
2315         plan->righttree = NULL;
2316         node->scan.scanrelid = scanrelid;
2317         node->tidquals = tidquals;
2318
2319         return node;
2320 }
2321
2322 SubqueryScan *
2323 make_subqueryscan(List *qptlist,
2324                                   List *qpqual,
2325                                   Index scanrelid,
2326                                   Plan *subplan,
2327                                   List *subrtable)
2328 {
2329         SubqueryScan *node = makeNode(SubqueryScan);
2330         Plan       *plan = &node->scan.plan;
2331
2332         /*
2333          * Cost is figured here for the convenience of prepunion.c.  Note this is
2334          * only correct for the case where qpqual is empty; otherwise caller
2335          * should overwrite cost with a better estimate.
2336          */
2337         copy_plan_costsize(plan, subplan);
2338         plan->total_cost += cpu_tuple_cost * subplan->plan_rows;
2339
2340         plan->targetlist = qptlist;
2341         plan->qual = qpqual;
2342         plan->lefttree = NULL;
2343         plan->righttree = NULL;
2344         node->scan.scanrelid = scanrelid;
2345         node->subplan = subplan;
2346         node->subrtable = subrtable;
2347
2348         return node;
2349 }
2350
2351 static FunctionScan *
2352 make_functionscan(List *qptlist,
2353                                   List *qpqual,
2354                                   Index scanrelid,
2355                                   Node *funcexpr,
2356                                   List *funccolnames,
2357                                   List *funccoltypes,
2358                                   List *funccoltypmods)
2359 {
2360         FunctionScan *node = makeNode(FunctionScan);
2361         Plan       *plan = &node->scan.plan;
2362
2363         /* cost should be inserted by caller */
2364         plan->targetlist = qptlist;
2365         plan->qual = qpqual;
2366         plan->lefttree = NULL;
2367         plan->righttree = NULL;
2368         node->scan.scanrelid = scanrelid;
2369         node->funcexpr = funcexpr;
2370         node->funccolnames = funccolnames;
2371         node->funccoltypes = funccoltypes;
2372         node->funccoltypmods = funccoltypmods;
2373
2374         return node;
2375 }
2376
2377 static ValuesScan *
2378 make_valuesscan(List *qptlist,
2379                                 List *qpqual,
2380                                 Index scanrelid,
2381                                 List *values_lists)
2382 {
2383         ValuesScan *node = makeNode(ValuesScan);
2384         Plan       *plan = &node->scan.plan;
2385
2386         /* cost should be inserted by caller */
2387         plan->targetlist = qptlist;
2388         plan->qual = qpqual;
2389         plan->lefttree = NULL;
2390         plan->righttree = NULL;
2391         node->scan.scanrelid = scanrelid;
2392         node->values_lists = values_lists;
2393
2394         return node;
2395 }
2396
2397 Append *
2398 make_append(List *appendplans, bool isTarget, List *tlist)
2399 {
2400         Append     *node = makeNode(Append);
2401         Plan       *plan = &node->plan;
2402         ListCell   *subnode;
2403
2404         /*
2405          * Compute cost as sum of subplan costs.  We charge nothing extra for the
2406          * Append itself, which perhaps is too optimistic, but since it doesn't do
2407          * any selection or projection, it is a pretty cheap node.
2408          */
2409         plan->startup_cost = 0;
2410         plan->total_cost = 0;
2411         plan->plan_rows = 0;
2412         plan->plan_width = 0;
2413         foreach(subnode, appendplans)
2414         {
2415                 Plan       *subplan = (Plan *) lfirst(subnode);
2416
2417                 if (subnode == list_head(appendplans))  /* first node? */
2418                         plan->startup_cost = subplan->startup_cost;
2419                 plan->total_cost += subplan->total_cost;
2420                 plan->plan_rows += subplan->plan_rows;
2421                 if (plan->plan_width < subplan->plan_width)
2422                         plan->plan_width = subplan->plan_width;
2423         }
2424
2425         plan->targetlist = tlist;
2426         plan->qual = NIL;
2427         plan->lefttree = NULL;
2428         plan->righttree = NULL;
2429         node->appendplans = appendplans;
2430         node->isTarget = isTarget;
2431
2432         return node;
2433 }
2434
2435 static BitmapAnd *
2436 make_bitmap_and(List *bitmapplans)
2437 {
2438         BitmapAnd  *node = makeNode(BitmapAnd);
2439         Plan       *plan = &node->plan;
2440
2441         /* cost should be inserted by caller */
2442         plan->targetlist = NIL;
2443         plan->qual = NIL;
2444         plan->lefttree = NULL;
2445         plan->righttree = NULL;
2446         node->bitmapplans = bitmapplans;
2447
2448         return node;
2449 }
2450
2451 static BitmapOr *
2452 make_bitmap_or(List *bitmapplans)
2453 {
2454         BitmapOr   *node = makeNode(BitmapOr);
2455         Plan       *plan = &node->plan;
2456
2457         /* cost should be inserted by caller */
2458         plan->targetlist = NIL;
2459         plan->qual = NIL;
2460         plan->lefttree = NULL;
2461         plan->righttree = NULL;
2462         node->bitmapplans = bitmapplans;
2463
2464         return node;
2465 }
2466
2467 static NestLoop *
2468 make_nestloop(List *tlist,
2469                           List *joinclauses,
2470                           List *otherclauses,
2471                           Plan *lefttree,
2472                           Plan *righttree,
2473                           JoinType jointype)
2474 {
2475         NestLoop   *node = makeNode(NestLoop);
2476         Plan       *plan = &node->join.plan;
2477
2478         /* cost should be inserted by caller */
2479         plan->targetlist = tlist;
2480         plan->qual = otherclauses;
2481         plan->lefttree = lefttree;
2482         plan->righttree = righttree;
2483         node->join.jointype = jointype;
2484         node->join.joinqual = joinclauses;
2485
2486         return node;
2487 }
2488
2489 static HashJoin *
2490 make_hashjoin(List *tlist,
2491                           List *joinclauses,
2492                           List *otherclauses,
2493                           List *hashclauses,
2494                           Plan *lefttree,
2495                           Plan *righttree,
2496                           JoinType jointype)
2497 {
2498         HashJoin   *node = makeNode(HashJoin);
2499         Plan       *plan = &node->join.plan;
2500
2501         /* cost should be inserted by caller */
2502         plan->targetlist = tlist;
2503         plan->qual = otherclauses;
2504         plan->lefttree = lefttree;
2505         plan->righttree = righttree;
2506         node->hashclauses = hashclauses;
2507         node->join.jointype = jointype;
2508         node->join.joinqual = joinclauses;
2509
2510         return node;
2511 }
2512
2513 static Hash *
2514 make_hash(Plan *lefttree)
2515 {
2516         Hash       *node = makeNode(Hash);
2517         Plan       *plan = &node->plan;
2518
2519         copy_plan_costsize(plan, lefttree);
2520
2521         /*
2522          * For plausibility, make startup & total costs equal total cost of input
2523          * plan; this only affects EXPLAIN display not decisions.
2524          */
2525         plan->startup_cost = plan->total_cost;
2526         plan->targetlist = lefttree->targetlist;
2527         plan->qual = NIL;
2528         plan->lefttree = lefttree;
2529         plan->righttree = NULL;
2530
2531         return node;
2532 }
2533
2534 static MergeJoin *
2535 make_mergejoin(List *tlist,
2536                            List *joinclauses,
2537                            List *otherclauses,
2538                            List *mergeclauses,
2539                            Oid *mergefamilies,
2540                            int *mergestrategies,
2541                            bool *mergenullsfirst,
2542                            Plan *lefttree,
2543                            Plan *righttree,
2544                            JoinType jointype)
2545 {
2546         MergeJoin  *node = makeNode(MergeJoin);
2547         Plan       *plan = &node->join.plan;
2548
2549         /* cost should be inserted by caller */
2550         plan->targetlist = tlist;
2551         plan->qual = otherclauses;
2552         plan->lefttree = lefttree;
2553         plan->righttree = righttree;
2554         node->mergeclauses = mergeclauses;
2555         node->mergeFamilies = mergefamilies;
2556         node->mergeStrategies = mergestrategies;
2557         node->mergeNullsFirst = mergenullsfirst;
2558         node->join.jointype = jointype;
2559         node->join.joinqual = joinclauses;
2560
2561         return node;
2562 }
2563
2564 /*
2565  * make_sort --- basic routine to build a Sort plan node
2566  *
2567  * Caller must have built the sortColIdx, sortOperators, and nullsFirst
2568  * arrays already.
2569  */
2570 static Sort *
2571 make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
2572                   AttrNumber *sortColIdx, Oid *sortOperators, bool *nullsFirst)
2573 {
2574         Sort       *node = makeNode(Sort);
2575         Plan       *plan = &node->plan;
2576         Path            sort_path;              /* dummy for result of cost_sort */
2577
2578         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2579         cost_sort(&sort_path, root, NIL,
2580                           lefttree->total_cost,
2581                           lefttree->plan_rows,
2582                           lefttree->plan_width);
2583         plan->startup_cost = sort_path.startup_cost;
2584         plan->total_cost = sort_path.total_cost;
2585         plan->targetlist = lefttree->targetlist;
2586         plan->qual = NIL;
2587         plan->lefttree = lefttree;
2588         plan->righttree = NULL;
2589         node->numCols = numCols;
2590         node->sortColIdx = sortColIdx;
2591         node->sortOperators = sortOperators;
2592         node->nullsFirst = nullsFirst;
2593
2594         return node;
2595 }
2596
2597 /*
2598  * add_sort_column --- utility subroutine for building sort info arrays
2599  *
2600  * We need this routine because the same column might be selected more than
2601  * once as a sort key column; if so, the extra mentions are redundant.
2602  *
2603  * Caller is assumed to have allocated the arrays large enough for the
2604  * max possible number of columns.      Return value is the new column count.
2605  */
2606 static int
2607 add_sort_column(AttrNumber colIdx, Oid sortOp, bool nulls_first,
2608                                 int numCols, AttrNumber *sortColIdx,
2609                                 Oid *sortOperators, bool *nullsFirst)
2610 {
2611         int                     i;
2612
2613         for (i = 0; i < numCols; i++)
2614         {
2615                 /*
2616                  * Note: we check sortOp because it's conceivable that "ORDER BY
2617                  * foo USING <, foo USING <<<" is not redundant, if <<< distinguishes
2618                  * values that < considers equal.  We need not check nulls_first
2619                  * however because a lower-order column with the same sortop but
2620                  * opposite nulls direction is redundant.
2621                  */
2622                 if (sortColIdx[i] == colIdx &&
2623                         sortOperators[numCols] == sortOp)
2624                 {
2625                         /* Already sorting by this col, so extra sort key is useless */
2626                         return numCols;
2627                 }
2628         }
2629
2630         /* Add the column */
2631         sortColIdx[numCols] = colIdx;
2632         sortOperators[numCols] = sortOp;
2633         nullsFirst[numCols] = nulls_first;
2634         return numCols + 1;
2635 }
2636
2637 /*
2638  * make_sort_from_pathkeys
2639  *        Create sort plan to sort according to given pathkeys
2640  *
2641  *        'lefttree' is the node which yields input tuples
2642  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
2643  *
2644  * We must convert the pathkey information into arrays of sort key column
2645  * numbers and sort operator OIDs.
2646  *
2647  * If the pathkeys include expressions that aren't simple Vars, we will
2648  * usually need to add resjunk items to the input plan's targetlist to
2649  * compute these expressions (since the Sort node itself won't do it).
2650  * If the input plan type isn't one that can do projections, this means
2651  * adding a Result node just to do the projection.
2652  */
2653 Sort *
2654 make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys)
2655 {
2656         List       *tlist = lefttree->targetlist;
2657         ListCell   *i;
2658         int                     numsortkeys;
2659         AttrNumber *sortColIdx;
2660         Oid                *sortOperators;
2661         bool       *nullsFirst;
2662
2663         /*
2664          * We will need at most list_length(pathkeys) sort columns; possibly less
2665          */
2666         numsortkeys = list_length(pathkeys);
2667         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2668         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2669         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
2670
2671         numsortkeys = 0;
2672
2673         foreach(i, pathkeys)
2674         {
2675                 PathKey    *pathkey = (PathKey *) lfirst(i);
2676                 TargetEntry *tle = NULL;
2677                 Oid                     pk_datatype = InvalidOid;
2678                 Oid                     sortop;
2679                 ListCell   *j;
2680
2681                 /*
2682                  * We can sort by any non-constant expression listed in the pathkey's
2683                  * EquivalenceClass.  For now, we take the first one that corresponds
2684                  * to an available Var in the tlist. If there isn't any, use the first
2685                  * one that is an expression in the input's vars.  (The non-const
2686                  * restriction only matters if the EC is below_outer_join; but if it
2687                  * isn't, it won't contain consts anyway, else we'd have discarded
2688                  * the pathkey as redundant.)
2689                  *
2690                  * XXX if we have a choice, is there any way of figuring out which
2691                  * might be cheapest to execute?  (For example, int4lt is likely much
2692                  * cheaper to execute than numericlt, but both might appear in the
2693                  * same equivalence class...)  Not clear that we ever will have an
2694                  * interesting choice in practice, so it may not matter.
2695                  */
2696                 foreach(j, pathkey->pk_eclass->ec_members)
2697                 {
2698                         EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
2699
2700                         if (em->em_is_const || em->em_is_child)
2701                                 continue;
2702                         tle = tlist_member((Node *) em->em_expr, tlist);
2703                         if (tle)
2704                         {
2705                                 pk_datatype = em->em_datatype;
2706                                 break;                  /* found expr already in tlist */
2707                         }
2708                 }
2709                 if (!tle)
2710                 {
2711                         /* No matching Var; look for a computable expression */
2712                         Expr   *sortexpr = NULL;
2713
2714                         foreach(j, pathkey->pk_eclass->ec_members)
2715                         {
2716                                 EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
2717                                 List       *exprvars;
2718                                 ListCell   *k;
2719
2720                                 if (em->em_is_const || em->em_is_child)
2721                                         continue;
2722                                 sortexpr = em->em_expr;
2723                                 exprvars = pull_var_clause((Node *) sortexpr, false);
2724                                 foreach(k, exprvars)
2725                                 {
2726                                         if (!tlist_member(lfirst(k), tlist))
2727                                                 break;
2728                                 }
2729                                 list_free(exprvars);
2730                                 if (!k)
2731                                 {
2732                                         pk_datatype = em->em_datatype;
2733                                         break;          /* found usable expression */
2734                                 }
2735                         }
2736                         if (!j)
2737                                 elog(ERROR, "could not find pathkey item to sort");
2738
2739                         /*
2740                          * Do we need to insert a Result node?
2741                          */
2742                         if (!is_projection_capable_plan(lefttree))
2743                         {
2744                                 /* copy needed so we don't modify input's tlist below */
2745                                 tlist = copyObject(tlist);
2746                                 lefttree = (Plan *) make_result(root, tlist, NULL, lefttree);
2747                         }
2748
2749                         /*
2750                          * Add resjunk entry to input's tlist
2751                          */
2752                         tle = makeTargetEntry(sortexpr,
2753                                                                   list_length(tlist) + 1,
2754                                                                   NULL,
2755                                                                   true);
2756                         tlist = lappend(tlist, tle);
2757                         lefttree->targetlist = tlist;           /* just in case NIL before */
2758                 }
2759
2760                 /*
2761                  * Look up the correct sort operator from the PathKey's slightly
2762                  * abstracted representation.
2763                  */
2764                 sortop = get_opfamily_member(pathkey->pk_opfamily,
2765                                                                          pk_datatype,
2766                                                                          pk_datatype,
2767                                                                          pathkey->pk_strategy);
2768                 if (!OidIsValid(sortop))        /* should not happen */
2769                         elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
2770                                  pathkey->pk_strategy, pk_datatype, pk_datatype,
2771                                  pathkey->pk_opfamily);
2772
2773                 /*
2774                  * The column might already be selected as a sort key, if the pathkeys
2775                  * contain duplicate entries.  (This can happen in scenarios where
2776                  * multiple mergejoinable clauses mention the same var, for example.)
2777                  * So enter it only once in the sort arrays.
2778                  */
2779                 numsortkeys = add_sort_column(tle->resno,
2780                                                                           sortop,
2781                                                                           pathkey->pk_nulls_first,
2782                                                                           numsortkeys,
2783                                                                           sortColIdx, sortOperators, nullsFirst);
2784         }
2785
2786         Assert(numsortkeys > 0);
2787
2788         return make_sort(root, lefttree, numsortkeys,
2789                                          sortColIdx, sortOperators, nullsFirst);
2790 }
2791
2792 /*
2793  * make_sort_from_sortclauses
2794  *        Create sort plan to sort according to given sortclauses
2795  *
2796  *        'sortcls' is a list of SortClauses
2797  *        'lefttree' is the node which yields input tuples
2798  */
2799 Sort *
2800 make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
2801 {
2802         List       *sub_tlist = lefttree->targetlist;
2803         ListCell   *l;
2804         int                     numsortkeys;
2805         AttrNumber *sortColIdx;
2806         Oid                *sortOperators;
2807         bool       *nullsFirst;
2808
2809         /*
2810          * We will need at most list_length(sortcls) sort columns; possibly less
2811          */
2812         numsortkeys = list_length(sortcls);
2813         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2814         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2815         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
2816
2817         numsortkeys = 0;
2818
2819         foreach(l, sortcls)
2820         {
2821                 SortClause *sortcl = (SortClause *) lfirst(l);
2822                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
2823
2824                 /*
2825                  * Check for the possibility of duplicate order-by clauses --- the
2826                  * parser should have removed 'em, but no point in sorting
2827                  * redundantly.
2828                  */
2829                 numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
2830                                                                           sortcl->nulls_first,
2831                                                                           numsortkeys,
2832                                                                           sortColIdx, sortOperators, nullsFirst);
2833         }
2834
2835         Assert(numsortkeys > 0);
2836
2837         return make_sort(root, lefttree, numsortkeys,
2838                                          sortColIdx, sortOperators, nullsFirst);
2839 }
2840
2841 /*
2842  * make_sort_from_groupcols
2843  *        Create sort plan to sort based on grouping columns
2844  *
2845  * 'groupcls' is the list of GroupClauses
2846  * 'grpColIdx' gives the column numbers to use
2847  *
2848  * This might look like it could be merged with make_sort_from_sortclauses,
2849  * but presently we *must* use the grpColIdx[] array to locate sort columns,
2850  * because the child plan's tlist is not marked with ressortgroupref info
2851  * appropriate to the grouping node.  So, only the sort ordering info
2852  * is used from the GroupClause entries.
2853  */
2854 Sort *
2855 make_sort_from_groupcols(PlannerInfo *root,
2856                                                  List *groupcls,
2857                                                  AttrNumber *grpColIdx,
2858                                                  Plan *lefttree)
2859 {
2860         List       *sub_tlist = lefttree->targetlist;
2861         int                     grpno = 0;
2862         ListCell   *l;
2863         int                     numsortkeys;
2864         AttrNumber *sortColIdx;
2865         Oid                *sortOperators;
2866         bool       *nullsFirst;
2867
2868         /*
2869          * We will need at most list_length(groupcls) sort columns; possibly less
2870          */
2871         numsortkeys = list_length(groupcls);
2872         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
2873         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
2874         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
2875
2876         numsortkeys = 0;
2877
2878         foreach(l, groupcls)
2879         {
2880                 GroupClause *grpcl = (GroupClause *) lfirst(l);
2881                 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
2882
2883                 /*
2884                  * Check for the possibility of duplicate group-by clauses --- the
2885                  * parser should have removed 'em, but no point in sorting
2886                  * redundantly.
2887                  */
2888                 numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
2889                                                                           grpcl->nulls_first,
2890                                                                           numsortkeys,
2891                                                                           sortColIdx, sortOperators, nullsFirst);
2892                 grpno++;
2893         }
2894
2895         Assert(numsortkeys > 0);
2896
2897         return make_sort(root, lefttree, numsortkeys,
2898                                          sortColIdx, sortOperators, nullsFirst);
2899 }
2900
2901 Material *
2902 make_material(Plan *lefttree)
2903 {
2904         Material   *node = makeNode(Material);
2905         Plan       *plan = &node->plan;
2906
2907         /* cost should be inserted by caller */
2908         plan->targetlist = lefttree->targetlist;
2909         plan->qual = NIL;
2910         plan->lefttree = lefttree;
2911         plan->righttree = NULL;
2912
2913         return node;
2914 }
2915
2916 /*
2917  * materialize_finished_plan: stick a Material node atop a completed plan
2918  *
2919  * There are a couple of places where we want to attach a Material node
2920  * after completion of subquery_planner().      This currently requires hackery.
2921  * Since subquery_planner has already run SS_finalize_plan on the subplan
2922  * tree, we have to kluge up parameter lists for the Material node.
2923  * Possibly this could be fixed by postponing SS_finalize_plan processing
2924  * until setrefs.c is run?
2925  */
2926 Plan *
2927 materialize_finished_plan(Plan *subplan)
2928 {
2929         Plan       *matplan;
2930         Path            matpath;                /* dummy for result of cost_material */
2931
2932         matplan = (Plan *) make_material(subplan);
2933
2934         /* Set cost data */
2935         cost_material(&matpath,
2936                                   subplan->total_cost,
2937                                   subplan->plan_rows,
2938                                   subplan->plan_width);
2939         matplan->startup_cost = matpath.startup_cost;
2940         matplan->total_cost = matpath.total_cost;
2941         matplan->plan_rows = subplan->plan_rows;
2942         matplan->plan_width = subplan->plan_width;
2943
2944         /* parameter kluge --- see comments above */
2945         matplan->extParam = bms_copy(subplan->extParam);
2946         matplan->allParam = bms_copy(subplan->allParam);
2947
2948         return matplan;
2949 }
2950
2951 Agg *
2952 make_agg(PlannerInfo *root, List *tlist, List *qual,
2953                  AggStrategy aggstrategy,
2954                  int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
2955                  long numGroups, int numAggs,
2956                  Plan *lefttree)
2957 {
2958         Agg                *node = makeNode(Agg);
2959         Plan       *plan = &node->plan;
2960         Path            agg_path;               /* dummy for result of cost_agg */
2961         QualCost        qual_cost;
2962
2963         node->aggstrategy = aggstrategy;
2964         node->numCols = numGroupCols;
2965         node->grpColIdx = grpColIdx;
2966         node->grpOperators = grpOperators;
2967         node->numGroups = numGroups;
2968
2969         copy_plan_costsize(plan, lefttree); /* only care about copying size */
2970         cost_agg(&agg_path, root,
2971                          aggstrategy, numAggs,
2972                          numGroupCols, numGroups,
2973                          lefttree->startup_cost,
2974                          lefttree->total_cost,
2975                          lefttree->plan_rows);
2976         plan->startup_cost = agg_path.startup_cost;
2977         plan->total_cost = agg_path.total_cost;
2978
2979         /*
2980          * We will produce a single output tuple if not grouping, and a tuple per
2981          * group otherwise.
2982          */
2983         if (aggstrategy == AGG_PLAIN)
2984                 plan->plan_rows = 1;
2985         else
2986                 plan->plan_rows = numGroups;
2987
2988         /*
2989          * We also need to account for the cost of evaluation of the qual (ie, the
2990          * HAVING clause) and the tlist.  Note that cost_qual_eval doesn't charge
2991          * anything for Aggref nodes; this is okay since they are really
2992          * comparable to Vars.
2993          *
2994          * See notes in grouping_planner about why this routine and make_group are
2995          * the only ones in this file that worry about tlist eval cost.
2996          */
2997         if (qual)
2998         {
2999                 cost_qual_eval(&qual_cost, qual, root);
3000                 plan->startup_cost += qual_cost.startup;
3001                 plan->total_cost += qual_cost.startup;
3002                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3003         }
3004         cost_qual_eval(&qual_cost, tlist, root);
3005         plan->startup_cost += qual_cost.startup;
3006         plan->total_cost += qual_cost.startup;
3007         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3008
3009         plan->qual = qual;
3010         plan->targetlist = tlist;
3011         plan->lefttree = lefttree;
3012         plan->righttree = NULL;
3013
3014         return node;
3015 }
3016
3017 Group *
3018 make_group(PlannerInfo *root,
3019                    List *tlist,
3020                    List *qual,
3021                    int numGroupCols,
3022                    AttrNumber *grpColIdx,
3023                    Oid *grpOperators,
3024                    double numGroups,
3025                    Plan *lefttree)
3026 {
3027         Group      *node = makeNode(Group);
3028         Plan       *plan = &node->plan;
3029         Path            group_path;             /* dummy for result of cost_group */
3030         QualCost        qual_cost;
3031
3032         node->numCols = numGroupCols;
3033         node->grpColIdx = grpColIdx;
3034         node->grpOperators = grpOperators;
3035
3036         copy_plan_costsize(plan, lefttree); /* only care about copying size */
3037         cost_group(&group_path, root,
3038                            numGroupCols, numGroups,
3039                            lefttree->startup_cost,
3040                            lefttree->total_cost,
3041                            lefttree->plan_rows);
3042         plan->startup_cost = group_path.startup_cost;
3043         plan->total_cost = group_path.total_cost;
3044
3045         /* One output tuple per estimated result group */
3046         plan->plan_rows = numGroups;
3047
3048         /*
3049          * We also need to account for the cost of evaluation of the qual (ie, the
3050          * HAVING clause) and the tlist.
3051          *
3052          * XXX this double-counts the cost of evaluation of any expressions used
3053          * for grouping, since in reality those will have been evaluated at a
3054          * lower plan level and will only be copied by the Group node. Worth
3055          * fixing?
3056          *
3057          * See notes in grouping_planner about why this routine and make_agg are
3058          * the only ones in this file that worry about tlist eval cost.
3059          */
3060         if (qual)
3061         {
3062                 cost_qual_eval(&qual_cost, qual, root);
3063                 plan->startup_cost += qual_cost.startup;
3064                 plan->total_cost += qual_cost.startup;
3065                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3066         }
3067         cost_qual_eval(&qual_cost, tlist, root);
3068         plan->startup_cost += qual_cost.startup;
3069         plan->total_cost += qual_cost.startup;
3070         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3071
3072         plan->qual = qual;
3073         plan->targetlist = tlist;
3074         plan->lefttree = lefttree;
3075         plan->righttree = NULL;
3076
3077         return node;
3078 }
3079
3080 /*
3081  * distinctList is a list of SortClauses, identifying the targetlist items
3082  * that should be considered by the Unique filter.  The input path must
3083  * already be sorted accordingly.
3084  */
3085 Unique *
3086 make_unique(Plan *lefttree, List *distinctList)
3087 {
3088         Unique     *node = makeNode(Unique);
3089         Plan       *plan = &node->plan;
3090         int                     numCols = list_length(distinctList);
3091         int                     keyno = 0;
3092         AttrNumber *uniqColIdx;
3093         Oid                *uniqOperators;
3094         ListCell   *slitem;
3095
3096         copy_plan_costsize(plan, lefttree);
3097
3098         /*
3099          * Charge one cpu_operator_cost per comparison per input tuple. We assume
3100          * all columns get compared at most of the tuples.      (XXX probably this is
3101          * an overestimate.)
3102          */
3103         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
3104
3105         /*
3106          * plan->plan_rows is left as a copy of the input subplan's plan_rows; ie,
3107          * we assume the filter removes nothing.  The caller must alter this if he
3108          * has a better idea.
3109          */
3110
3111         plan->targetlist = lefttree->targetlist;
3112         plan->qual = NIL;
3113         plan->lefttree = lefttree;
3114         plan->righttree = NULL;
3115
3116         /*
3117          * convert SortClause list into arrays of attr indexes and equality
3118          * operators, as wanted by executor
3119          */
3120         Assert(numCols > 0);
3121         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3122         uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3123
3124         foreach(slitem, distinctList)
3125         {
3126                 SortClause *sortcl = (SortClause *) lfirst(slitem);
3127                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
3128
3129                 uniqColIdx[keyno] = tle->resno;
3130                 uniqOperators[keyno] = get_equality_op_for_ordering_op(sortcl->sortop);
3131                 if (!OidIsValid(uniqOperators[keyno]))          /* shouldn't happen */
3132                         elog(ERROR, "could not find equality operator for ordering operator %u",
3133                                  sortcl->sortop);
3134                 keyno++;
3135         }
3136
3137         node->numCols = numCols;
3138         node->uniqColIdx = uniqColIdx;
3139         node->uniqOperators = uniqOperators;
3140
3141         return node;
3142 }
3143
3144 /*
3145  * distinctList is a list of SortClauses, identifying the targetlist items
3146  * that should be considered by the SetOp filter.  The input path must
3147  * already be sorted accordingly.
3148  */
3149 SetOp *
3150 make_setop(SetOpCmd cmd, Plan *lefttree,
3151                    List *distinctList, AttrNumber flagColIdx)
3152 {
3153         SetOp      *node = makeNode(SetOp);
3154         Plan       *plan = &node->plan;
3155         int                     numCols = list_length(distinctList);
3156         int                     keyno = 0;
3157         AttrNumber *dupColIdx;
3158         Oid                *dupOperators;
3159         ListCell   *slitem;
3160
3161         copy_plan_costsize(plan, lefttree);
3162
3163         /*
3164          * Charge one cpu_operator_cost per comparison per input tuple. We assume
3165          * all columns get compared at most of the tuples.
3166          */
3167         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
3168
3169         /*
3170          * We make the unsupported assumption that there will be 10% as many
3171          * tuples out as in.  Any way to do better?
3172          */
3173         plan->plan_rows *= 0.1;
3174         if (plan->plan_rows < 1)
3175                 plan->plan_rows = 1;
3176
3177         plan->targetlist = lefttree->targetlist;
3178         plan->qual = NIL;
3179         plan->lefttree = lefttree;
3180         plan->righttree = NULL;
3181
3182         /*
3183          * convert SortClause list into arrays of attr indexes and equality
3184          * operators, as wanted by executor
3185          */
3186         Assert(numCols > 0);
3187         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3188         dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3189
3190         foreach(slitem, distinctList)
3191         {
3192                 SortClause *sortcl = (SortClause *) lfirst(slitem);
3193                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
3194
3195                 dupColIdx[keyno] = tle->resno;
3196                 dupOperators[keyno] = get_equality_op_for_ordering_op(sortcl->sortop);
3197                 if (!OidIsValid(dupOperators[keyno]))           /* shouldn't happen */
3198                         elog(ERROR, "could not find equality operator for ordering operator %u",
3199                                  sortcl->sortop);
3200                 keyno++;
3201         }
3202
3203         node->cmd = cmd;
3204         node->numCols = numCols;
3205         node->dupColIdx = dupColIdx;
3206         node->dupOperators = dupOperators;
3207         node->flagColIdx = flagColIdx;
3208
3209         return node;
3210 }
3211
3212 /*
3213  * Note: offset_est and count_est are passed in to save having to repeat
3214  * work already done to estimate the values of the limitOffset and limitCount
3215  * expressions.  Their values are as returned by preprocess_limit (0 means
3216  * "not relevant", -1 means "couldn't estimate").  Keep the code below in sync
3217  * with that function!
3218  */
3219 Limit *
3220 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount,
3221                    int64 offset_est, int64 count_est)
3222 {
3223         Limit      *node = makeNode(Limit);
3224         Plan       *plan = &node->plan;
3225
3226         copy_plan_costsize(plan, lefttree);
3227
3228         /*
3229          * Adjust the output rows count and costs according to the offset/limit.
3230          * This is only a cosmetic issue if we are at top level, but if we are
3231          * building a subquery then it's important to report correct info to the
3232          * outer planner.
3233          *
3234          * When the offset or count couldn't be estimated, use 10% of the
3235          * estimated number of rows emitted from the subplan.
3236          */
3237         if (offset_est != 0)
3238         {
3239                 double          offset_rows;
3240
3241                 if (offset_est > 0)
3242                         offset_rows = (double) offset_est;
3243                 else
3244                         offset_rows = clamp_row_est(lefttree->plan_rows * 0.10);
3245                 if (offset_rows > plan->plan_rows)
3246                         offset_rows = plan->plan_rows;
3247                 if (plan->plan_rows > 0)
3248                         plan->startup_cost +=
3249                                 (plan->total_cost - plan->startup_cost)
3250                                 * offset_rows / plan->plan_rows;
3251                 plan->plan_rows -= offset_rows;
3252                 if (plan->plan_rows < 1)
3253                         plan->plan_rows = 1;
3254         }
3255
3256         if (count_est != 0)
3257         {
3258                 double          count_rows;
3259
3260                 if (count_est > 0)
3261                         count_rows = (double) count_est;
3262                 else
3263                         count_rows = clamp_row_est(lefttree->plan_rows * 0.10);
3264                 if (count_rows > plan->plan_rows)
3265                         count_rows = plan->plan_rows;
3266                 if (plan->plan_rows > 0)
3267                         plan->total_cost = plan->startup_cost +
3268                                 (plan->total_cost - plan->startup_cost)
3269                                 * count_rows / plan->plan_rows;
3270                 plan->plan_rows = count_rows;
3271                 if (plan->plan_rows < 1)
3272                         plan->plan_rows = 1;
3273         }
3274
3275         plan->targetlist = lefttree->targetlist;
3276         plan->qual = NIL;
3277         plan->lefttree = lefttree;
3278         plan->righttree = NULL;
3279
3280         node->limitOffset = limitOffset;
3281         node->limitCount = limitCount;
3282
3283         return node;
3284 }
3285
3286 /*
3287  * make_result
3288  *        Build a Result plan node
3289  *
3290  * If we have a subplan, assume that any evaluation costs for the gating qual
3291  * were already factored into the subplan's startup cost, and just copy the
3292  * subplan cost.  If there's no subplan, we should include the qual eval
3293  * cost.  In either case, tlist eval cost is not to be included here.
3294  */
3295 Result *
3296 make_result(PlannerInfo *root,
3297                         List *tlist,
3298                         Node *resconstantqual,
3299                         Plan *subplan)
3300 {
3301         Result     *node = makeNode(Result);
3302         Plan       *plan = &node->plan;
3303
3304         if (subplan)
3305                 copy_plan_costsize(plan, subplan);
3306         else
3307         {
3308                 plan->startup_cost = 0;
3309                 plan->total_cost = cpu_tuple_cost;
3310                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
3311                 plan->plan_width = 0;   /* XXX is it worth being smarter? */
3312                 if (resconstantqual)
3313                 {
3314                         QualCost        qual_cost;
3315
3316                         cost_qual_eval(&qual_cost, (List *) resconstantqual, root);
3317                         /* resconstantqual is evaluated once at startup */
3318                         plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
3319                         plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
3320                 }
3321         }
3322
3323         plan->targetlist = tlist;
3324         plan->qual = NIL;
3325         plan->lefttree = subplan;
3326         plan->righttree = NULL;
3327         node->resconstantqual = resconstantqual;
3328
3329         return node;
3330 }
3331
3332 /*
3333  * is_projection_capable_plan
3334  *              Check whether a given Plan node is able to do projection.
3335  */
3336 bool
3337 is_projection_capable_plan(Plan *plan)
3338 {
3339         /* Most plan types can project, so just list the ones that can't */
3340         switch (nodeTag(plan))
3341         {
3342                 case T_Hash:
3343                 case T_Material:
3344                 case T_Sort:
3345                 case T_Unique:
3346                 case T_SetOp:
3347                 case T_Limit:
3348                 case T_Append:
3349                         return false;
3350                 default:
3351                         break;
3352         }
3353         return true;
3354 }