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