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