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

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