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

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