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-2011, PostgreSQL Global Development Group
   9  * Portions Copyright (c) 1994, Regents of the University of California
  10  *
  11  *
  12  * IDENTIFICATION
  13  *        src/backend/optimizer/plan/createplan.c
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #include "postgres.h"
  18
  19 #include <limits.h>
  20 #include <math.h>
  21
  22 #include "access/skey.h"
  23 #include "foreign/fdwapi.h"
  24 #include "miscadmin.h"
  25 #include "nodes/makefuncs.h"
  26 #include "nodes/nodeFuncs.h"
  27 #include "optimizer/clauses.h"
  28 #include "optimizer/cost.h"
  29 #include "optimizer/paths.h"
  30 #include "optimizer/plancat.h"
  31 #include "optimizer/planmain.h"
  32 #include "optimizer/predtest.h"
  33 #include "optimizer/restrictinfo.h"
  34 #include "optimizer/subselect.h"
  35 #include "optimizer/tlist.h"
  36 #include "optimizer/var.h"
  37 #include "parser/parse_clause.h"
  38 #include "parser/parsetree.h"
  39 #include "utils/lsyscache.h"
  40
  41
  42 static Plan *create_plan_recurse(PlannerInfo *root, Path *best_path);
  43 static Plan *create_scan_plan(PlannerInfo *root, Path *best_path);
  44 static List *build_relation_tlist(RelOptInfo *rel);
  45 static bool use_physical_tlist(PlannerInfo *root, RelOptInfo *rel);
  46 static void disuse_physical_tlist(Plan *plan, Path *path);
  47 static Plan *create_gating_plan(PlannerInfo *root, Plan *plan, List *quals);
  48 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
  49 static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
  50 static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path);
  51 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
  52 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path);
  53 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path);
  54 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
  55                                         List *tlist, List *scan_clauses);
  56 static IndexScan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
  57                                           List *tlist, List *scan_clauses);
  58 static BitmapHeapScan *create_bitmap_scan_plan(PlannerInfo *root,
  59                                                 BitmapHeapPath *best_path,
  60                                                 List *tlist, List *scan_clauses);
  61 static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
  62                                           List **qual, List **indexqual);
  63 static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
  64                                         List *tlist, List *scan_clauses);
  65 static SubqueryScan *create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
  66                                                  List *tlist, List *scan_clauses);
  67 static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
  68                                                  List *tlist, List *scan_clauses);
  69 static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
  70                                            List *tlist, List *scan_clauses);
  71 static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path,
  72                                         List *tlist, List *scan_clauses);
  73 static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path,
  74                                                   List *tlist, List *scan_clauses);
  75 static ForeignScan *create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
  76                                                 List *tlist, List *scan_clauses);
  77 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path,
  78                                          Plan *outer_plan, Plan *inner_plan);
  79 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path,
  80                                           Plan *outer_plan, Plan *inner_plan);
  81 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path,
  82                                          Plan *outer_plan, Plan *inner_plan);
  83 static Node *replace_nestloop_params(PlannerInfo *root, Node *expr);
  84 static Node *replace_nestloop_params_mutator(Node *node, PlannerInfo *root);
  85 static List *fix_indexqual_references(PlannerInfo *root, IndexPath *index_path,
  86                                                  List *indexquals);
  87 static List *fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path,
  88                                                         List *indexorderbys);
  89 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index);
  90 static List *get_switched_clauses(List *clauses, Relids outerrelids);
  91 static List *order_qual_clauses(PlannerInfo *root, List *clauses);
  92 static void copy_path_costsize(Plan *dest, Path *src);
  93 static void copy_plan_costsize(Plan *dest, Plan *src);
  94 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
  95 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
  96                            Oid indexid, List *indexqual, List *indexqualorig,
  97                            List *indexorderby, List *indexorderbyorig,
  98                            ScanDirection indexscandir, bool indexonly);
  99 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
 100                                           List *indexqual,
 101                                           List *indexqualorig);
 102 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
 103                                          List *qpqual,
 104                                          Plan *lefttree,
 105                                          List *bitmapqualorig,
 106                                          Index scanrelid);
 107 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
 108                          List *tidquals);
 109 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
 110                                   Index scanrelid, Node *funcexpr, List *funccolnames,
 111                                   List *funccoltypes, List *funccoltypmods,
 112                                   List *funccolcollations);
 113 static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
 114                                 Index scanrelid, List *values_lists);
 115 static CteScan *make_ctescan(List *qptlist, List *qpqual,
 116                          Index scanrelid, int ctePlanId, int cteParam);
 117 static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
 118                                    Index scanrelid, int wtParam);
 119 static ForeignScan *make_foreignscan(List *qptlist, List *qpqual,
 120                                  Index scanrelid, bool fsSystemCol, FdwPlan *fdwplan);
 121 static BitmapAnd *make_bitmap_and(List *bitmapplans);
 122 static BitmapOr *make_bitmap_or(List *bitmapplans);
 123 static NestLoop *make_nestloop(List *tlist,
 124                           List *joinclauses, List *otherclauses, List *nestParams,
 125                           Plan *lefttree, Plan *righttree,
 126                           JoinType jointype);
 127 static HashJoin *make_hashjoin(List *tlist,
 128                           List *joinclauses, List *otherclauses,
 129                           List *hashclauses,
 130                           Plan *lefttree, Plan *righttree,
 131                           JoinType jointype);
 132 static Hash *make_hash(Plan *lefttree,
 133                   Oid skewTable,
 134                   AttrNumber skewColumn,
 135                   bool skewInherit,
 136                   Oid skewColType,
 137                   int32 skewColTypmod);
 138 static MergeJoin *make_mergejoin(List *tlist,
 139                            List *joinclauses, List *otherclauses,
 140                            List *mergeclauses,
 141                            Oid *mergefamilies,
 142                            Oid *mergecollations,
 143                            int *mergestrategies,
 144                            bool *mergenullsfirst,
 145                            Plan *lefttree, Plan *righttree,
 146                            JoinType jointype);
 147 static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
 148                   AttrNumber *sortColIdx, Oid *sortOperators,
 149                   Oid *collations, bool *nullsFirst,
 150                   double limit_tuples);
 151 static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
 152                                                    Plan *lefttree, List *pathkeys,
 153                                                    bool adjust_tlist_in_place,
 154                                                    int *p_numsortkeys,
 155                                                    AttrNumber **p_sortColIdx,
 156                                                    Oid **p_sortOperators,
 157                                                    Oid **p_collations,
 158                                                    bool **p_nullsFirst);
 159 static Material *make_material(Plan *lefttree);
 160
 161
 162 /*
 163  * create_plan
 164  *        Creates the access plan for a query by recursively processing the
 165  *        desired tree of pathnodes, starting at the node 'best_path'.  For
 166  *        every pathnode found, we create a corresponding plan node containing
 167  *        appropriate id, target list, and qualification information.
 168  *
 169  *        The tlists and quals in the plan tree are still in planner format,
 170  *        ie, Vars still correspond to the parser's numbering.  This will be
 171  *        fixed later by setrefs.c.
 172  *
 173  *        best_path is the best access path
 174  *
 175  *        Returns a Plan tree.
 176  */
 177 Plan *
 178 create_plan(PlannerInfo *root, Path *best_path)
 179 {
 180         Plan       *plan;
 181
 182         /* Initialize this module's private workspace in PlannerInfo */
 183         root->curOuterRels = NULL;
 184         root->curOuterParams = NIL;
 185
 186         /* Recursively process the path tree */
 187         plan = create_plan_recurse(root, best_path);
 188
 189         /* Check we successfully assigned all NestLoopParams to plan nodes */
 190         if (root->curOuterParams != NIL)
 191                 elog(ERROR, "failed to assign all NestLoopParams to plan nodes");
 192
 193         return plan;
 194 }
 195
 196 /*
 197  * create_plan_recurse
 198  *        Recursive guts of create_plan().
 199  */
 200 static Plan *
 201 create_plan_recurse(PlannerInfo *root, Path *best_path)
 202 {
 203         Plan       *plan;
 204
 205         switch (best_path->pathtype)
 206         {
 207                 case T_SeqScan:
 208                 case T_IndexScan:
 209                 case T_BitmapHeapScan:
 210                 case T_TidScan:
 211                 case T_SubqueryScan:
 212                 case T_FunctionScan:
 213                 case T_ValuesScan:
 214                 case T_CteScan:
 215                 case T_WorkTableScan:
 216                 case T_ForeignScan:
 217                         plan = create_scan_plan(root, best_path);
 218                         break;
 219                 case T_HashJoin:
 220                 case T_MergeJoin:
 221                 case T_NestLoop:
 222                         plan = create_join_plan(root,
 223                                                                         (JoinPath *) best_path);
 224                         break;
 225                 case T_Append:
 226                         plan = create_append_plan(root,
 227                                                                           (AppendPath *) best_path);
 228                         break;
 229                 case T_MergeAppend:
 230                         plan = create_merge_append_plan(root,
 231                                                                                         (MergeAppendPath *) best_path);
 232                         break;
 233                 case T_Result:
 234                         plan = (Plan *) create_result_plan(root,
 235                                                                                            (ResultPath *) best_path);
 236                         break;
 237                 case T_Material:
 238                         plan = (Plan *) create_material_plan(root,
 239                                                                                                  (MaterialPath *) best_path);
 240                         break;
 241                 case T_Unique:
 242                         plan = create_unique_plan(root,
 243                                                                           (UniquePath *) best_path);
 244                         break;
 245                 default:
 246                         elog(ERROR, "unrecognized node type: %d",
 247                                  (int) best_path->pathtype);
 248                         plan = NULL;            /* keep compiler quiet */
 249                         break;
 250         }
 251
 252         return plan;
 253 }
 254
 255 /*
 256  * create_scan_plan
 257  *       Create a scan plan for the parent relation of 'best_path'.
 258  */
 259 static Plan *
 260 create_scan_plan(PlannerInfo *root, Path *best_path)
 261 {
 262         RelOptInfo *rel = best_path->parent;
 263         List       *tlist;
 264         List       *scan_clauses;
 265         Plan       *plan;
 266
 267         /*
 268          * For table scans, rather than using the relation targetlist (which is
 269          * only those Vars actually needed by the query), we prefer to generate a
 270          * tlist containing all Vars in order.  This will allow the executor to
 271          * optimize away projection of the table tuples, if possible.  (Note that
 272          * planner.c may replace the tlist we generate here, forcing projection to
 273          * occur.)
 274          */
 275         if (use_physical_tlist(root, rel))
 276         {
 277                 tlist = build_physical_tlist(root, rel);
 278                 /* if fail because of dropped cols, use regular method */
 279                 if (tlist == NIL)
 280                         tlist = build_relation_tlist(rel);
 281         }
 282         else
 283                 tlist = build_relation_tlist(rel);
 284
 285         /*
 286          * Extract the relevant restriction clauses from the parent relation. The
 287          * executor must apply all these restrictions during the scan, except for
 288          * pseudoconstants which we'll take care of below.
 289          */
 290         scan_clauses = rel->baserestrictinfo;
 291
 292         switch (best_path->pathtype)
 293         {
 294                 case T_SeqScan:
 295                         plan = (Plan *) create_seqscan_plan(root,
 296                                                                                                 best_path,
 297                                                                                                 tlist,
 298                                                                                                 scan_clauses);
 299                         break;
 300
 301                 case T_IndexScan:
 302                         plan = (Plan *) create_indexscan_plan(root,
 303                                                                                                   (IndexPath *) best_path,
 304                                                                                                   tlist,
 305                                                                                                   scan_clauses);
 306                         break;
 307
 308                 case T_BitmapHeapScan:
 309                         plan = (Plan *) create_bitmap_scan_plan(root,
 310                                                                                                 (BitmapHeapPath *) best_path,
 311                                                                                                         tlist,
 312                                                                                                         scan_clauses);
 313                         break;
 314
 315                 case T_TidScan:
 316                         plan = (Plan *) create_tidscan_plan(root,
 317                                                                                                 (TidPath *) best_path,
 318                                                                                                 tlist,
 319                                                                                                 scan_clauses);
 320                         break;
 321
 322                 case T_SubqueryScan:
 323                         plan = (Plan *) create_subqueryscan_plan(root,
 324                                                                                                          best_path,
 325                                                                                                          tlist,
 326                                                                                                          scan_clauses);
 327                         break;
 328
 329                 case T_FunctionScan:
 330                         plan = (Plan *) create_functionscan_plan(root,
 331                                                                                                          best_path,
 332                                                                                                          tlist,
 333                                                                                                          scan_clauses);
 334                         break;
 335
 336                 case T_ValuesScan:
 337                         plan = (Plan *) create_valuesscan_plan(root,
 338                                                                                                    best_path,
 339                                                                                                    tlist,
 340                                                                                                    scan_clauses);
 341                         break;
 342
 343                 case T_CteScan:
 344                         plan = (Plan *) create_ctescan_plan(root,
 345                                                                                                 best_path,
 346                                                                                                 tlist,
 347                                                                                                 scan_clauses);
 348                         break;
 349
 350                 case T_WorkTableScan:
 351                         plan = (Plan *) create_worktablescan_plan(root,
 352                                                                                                           best_path,
 353                                                                                                           tlist,
 354                                                                                                           scan_clauses);
 355                         break;
 356
 357                 case T_ForeignScan:
 358                         plan = (Plan *) create_foreignscan_plan(root,
 359                                                                                                         (ForeignPath *) best_path,
 360                                                                                                         tlist,
 361                                                                                                         scan_clauses);
 362                         break;
 363
 364                 default:
 365                         elog(ERROR, "unrecognized node type: %d",
 366                                  (int) best_path->pathtype);
 367                         plan = NULL;            /* keep compiler quiet */
 368                         break;
 369         }
 370
 371         /*
 372          * If there are any pseudoconstant clauses attached to this node, insert a
 373          * gating Result node that evaluates the pseudoconstants as one-time
 374          * quals.
 375          */
 376         if (root->hasPseudoConstantQuals)
 377                 plan = create_gating_plan(root, plan, scan_clauses);
 378
 379         return plan;
 380 }
 381
 382 /*
 383  * Build a target list (ie, a list of TargetEntry) for a relation.
 384  */
 385 static List *
 386 build_relation_tlist(RelOptInfo *rel)
 387 {
 388         List       *tlist = NIL;
 389         int                     resno = 1;
 390         ListCell   *v;
 391
 392         foreach(v, rel->reltargetlist)
 393         {
 394                 /* Do we really need to copy here?      Not sure */
 395                 Node       *node = (Node *) copyObject(lfirst(v));
 396
 397                 tlist = lappend(tlist, makeTargetEntry((Expr *) node,
 398                                                                                            resno,
 399                                                                                            NULL,
 400                                                                                            false));
 401                 resno++;
 402         }
 403         return tlist;
 404 }
 405
 406 /*
 407  * use_physical_tlist
 408  *              Decide whether to use a tlist matching relation structure,
 409  *              rather than only those Vars actually referenced.
 410  */
 411 static bool
 412 use_physical_tlist(PlannerInfo *root, RelOptInfo *rel)
 413 {
 414         int                     i;
 415         ListCell   *lc;
 416
 417         /*
 418          * We can do this for real relation scans, subquery scans, function scans,
 419          * values scans, and CTE scans (but not for, eg, joins).
 420          */
 421         if (rel->rtekind != RTE_RELATION &&
 422                 rel->rtekind != RTE_SUBQUERY &&
 423                 rel->rtekind != RTE_FUNCTION &&
 424                 rel->rtekind != RTE_VALUES &&
 425                 rel->rtekind != RTE_CTE)
 426                 return false;
 427
 428         /*
 429          * Can't do it with inheritance cases either (mainly because Append
 430          * doesn't project).
 431          */
 432         if (rel->reloptkind != RELOPT_BASEREL)
 433                 return false;
 434
 435         /*
 436          * Can't do it if any system columns or whole-row Vars are requested.
 437          * (This could possibly be fixed but would take some fragile assumptions
 438          * in setrefs.c, I think.)
 439          */
 440         for (i = rel->min_attr; i <= 0; i++)
 441         {
 442                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
 443                         return false;
 444         }
 445
 446         /*
 447          * Can't do it if the rel is required to emit any placeholder expressions,
 448          * either.
 449          */
 450         foreach(lc, root->placeholder_list)
 451         {
 452                 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 453
 454                 if (bms_nonempty_difference(phinfo->ph_needed, rel->relids) &&
 455                         bms_is_subset(phinfo->ph_eval_at, rel->relids))
 456                         return false;
 457         }
 458
 459         return true;
 460 }
 461
 462 /*
 463  * disuse_physical_tlist
 464  *              Switch a plan node back to emitting only Vars actually referenced.
 465  *
 466  * If the plan node immediately above a scan would prefer to get only
 467  * needed Vars and not a physical tlist, it must call this routine to
 468  * undo the decision made by use_physical_tlist().      Currently, Hash, Sort,
 469  * and Material nodes want this, so they don't have to store useless columns.
 470  */
 471 static void
 472 disuse_physical_tlist(Plan *plan, Path *path)
 473 {
 474         /* Only need to undo it for path types handled by create_scan_plan() */
 475         switch (path->pathtype)
 476         {
 477                 case T_SeqScan:
 478                 case T_IndexScan:
 479                 case T_BitmapHeapScan:
 480                 case T_TidScan:
 481                 case T_SubqueryScan:
 482                 case T_FunctionScan:
 483                 case T_ValuesScan:
 484                 case T_CteScan:
 485                 case T_WorkTableScan:
 486                 case T_ForeignScan:
 487                         plan->targetlist = build_relation_tlist(path->parent);
 488                         break;
 489                 default:
 490                         break;
 491         }
 492 }
 493
 494 /*
 495  * create_gating_plan
 496  *        Deal with pseudoconstant qual clauses
 497  *
 498  * If the node's quals list includes any pseudoconstant quals, put them
 499  * into a gating Result node atop the already-built plan.  Otherwise,
 500  * return the plan as-is.
 501  *
 502  * Note that we don't change cost or size estimates when doing gating.
 503  * The costs of qual eval were already folded into the plan's startup cost.
 504  * Leaving the size alone amounts to assuming that the gating qual will
 505  * succeed, which is the conservative estimate for planning upper queries.
 506  * We certainly don't want to assume the output size is zero (unless the
 507  * gating qual is actually constant FALSE, and that case is dealt with in
 508  * clausesel.c).  Interpolating between the two cases is silly, because
 509  * it doesn't reflect what will really happen at runtime, and besides which
 510  * in most cases we have only a very bad idea of the probability of the gating
 511  * qual being true.
 512  */
 513 static Plan *
 514 create_gating_plan(PlannerInfo *root, Plan *plan, List *quals)
 515 {
 516         List       *pseudoconstants;
 517
 518         /* Sort into desirable execution order while still in RestrictInfo form */
 519         quals = order_qual_clauses(root, quals);
 520
 521         /* Pull out any pseudoconstant quals from the RestrictInfo list */
 522         pseudoconstants = extract_actual_clauses(quals, true);
 523
 524         if (!pseudoconstants)
 525                 return plan;
 526
 527         return (Plan *) make_result(root,
 528                                                                 plan->targetlist,
 529                                                                 (Node *) pseudoconstants,
 530                                                                 plan);
 531 }
 532
 533 /*
 534  * create_join_plan
 535  *        Create a join plan for 'best_path' and (recursively) plans for its
 536  *        inner and outer paths.
 537  */
 538 static Plan *
 539 create_join_plan(PlannerInfo *root, JoinPath *best_path)
 540 {
 541         Plan       *outer_plan;
 542         Plan       *inner_plan;
 543         Plan       *plan;
 544         Relids          saveOuterRels = root->curOuterRels;
 545
 546         outer_plan = create_plan_recurse(root, best_path->outerjoinpath);
 547
 548         /* For a nestloop, include outer relids in curOuterRels for inner side */
 549         if (best_path->path.pathtype == T_NestLoop)
 550                 root->curOuterRels = bms_union(root->curOuterRels,
 551                                                                    best_path->outerjoinpath->parent->relids);
 552
 553         inner_plan = create_plan_recurse(root, best_path->innerjoinpath);
 554
 555         switch (best_path->path.pathtype)
 556         {
 557                 case T_MergeJoin:
 558                         plan = (Plan *) create_mergejoin_plan(root,
 559                                                                                                   (MergePath *) best_path,
 560                                                                                                   outer_plan,
 561                                                                                                   inner_plan);
 562                         break;
 563                 case T_HashJoin:
 564                         plan = (Plan *) create_hashjoin_plan(root,
 565                                                                                                  (HashPath *) best_path,
 566                                                                                                  outer_plan,
 567                                                                                                  inner_plan);
 568                         break;
 569                 case T_NestLoop:
 570                         /* Restore curOuterRels */
 571                         bms_free(root->curOuterRels);
 572                         root->curOuterRels = saveOuterRels;
 573
 574                         plan = (Plan *) create_nestloop_plan(root,
 575                                                                                                  (NestPath *) best_path,
 576                                                                                                  outer_plan,
 577                                                                                                  inner_plan);
 578                         break;
 579                 default:
 580                         elog(ERROR, "unrecognized node type: %d",
 581                                  (int) best_path->path.pathtype);
 582                         plan = NULL;            /* keep compiler quiet */
 583                         break;
 584         }
 585
 586         /*
 587          * If there are any pseudoconstant clauses attached to this node, insert a
 588          * gating Result node that evaluates the pseudoconstants as one-time
 589          * quals.
 590          */
 591         if (root->hasPseudoConstantQuals)
 592                 plan = create_gating_plan(root, plan, best_path->joinrestrictinfo);
 593
 594 #ifdef NOT_USED
 595
 596         /*
 597          * * Expensive function pullups may have pulled local predicates * into
 598          * this path node.      Put them in the qpqual of the plan node. * JMH,
 599          * 6/15/92
 600          */
 601         if (get_loc_restrictinfo(best_path) != NIL)
 602                 set_qpqual((Plan) plan,
 603                                    list_concat(get_qpqual((Plan) plan),
 604                                            get_actual_clauses(get_loc_restrictinfo(best_path))));
 605 #endif
 606
 607         return plan;
 608 }
 609
 610 /*
 611  * create_append_plan
 612  *        Create an Append plan for 'best_path' and (recursively) plans
 613  *        for its subpaths.
 614  *
 615  *        Returns a Plan node.
 616  */
 617 static Plan *
 618 create_append_plan(PlannerInfo *root, AppendPath *best_path)
 619 {
 620         Append     *plan;
 621         List       *tlist = build_relation_tlist(best_path->path.parent);
 622         List       *subplans = NIL;
 623         ListCell   *subpaths;
 624
 625         /*
 626          * It is possible for the subplans list to contain only one entry, or even
 627          * no entries.  Handle these cases specially.
 628          *
 629          * XXX ideally, if there's just one entry, we'd not bother to generate an
 630          * Append node but just return the single child.  At the moment this does
 631          * not work because the varno of the child scan plan won't match the
 632          * parent-rel Vars it'll be asked to emit.
 633          */
 634         if (best_path->subpaths == NIL)
 635         {
 636                 /* Generate a Result plan with constant-FALSE gating qual */
 637                 return (Plan *) make_result(root,
 638                                                                         tlist,
 639                                                                         (Node *) list_make1(makeBoolConst(false,
 640                                                                                                                                           false)),
 641                                                                         NULL);
 642         }
 643
 644         /* Normal case with multiple subpaths */
 645         foreach(subpaths, best_path->subpaths)
 646         {
 647                 Path       *subpath = (Path *) lfirst(subpaths);
 648
 649                 subplans = lappend(subplans, create_plan_recurse(root, subpath));
 650         }
 651
 652         plan = make_append(subplans, tlist);
 653
 654         return (Plan *) plan;
 655 }
 656
 657 /*
 658  * create_merge_append_plan
 659  *        Create a MergeAppend plan for 'best_path' and (recursively) plans
 660  *        for its subpaths.
 661  *
 662  *        Returns a Plan node.
 663  */
 664 static Plan *
 665 create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
 666 {
 667         MergeAppend *node = makeNode(MergeAppend);
 668         Plan       *plan = &node->plan;
 669         List       *tlist = build_relation_tlist(best_path->path.parent);
 670         List       *pathkeys = best_path->path.pathkeys;
 671         List       *subplans = NIL;
 672         ListCell   *subpaths;
 673
 674         /*
 675          * We don't have the actual creation of the MergeAppend node split out
 676          * into a separate make_xxx function.  This is because we want to run
 677          * prepare_sort_from_pathkeys on it before we do so on the individual
 678          * child plans, to make cross-checking the sort info easier.
 679          */
 680         copy_path_costsize(plan, (Path *) best_path);
 681         plan->targetlist = tlist;
 682         plan->qual = NIL;
 683         plan->lefttree = NULL;
 684         plan->righttree = NULL;
 685
 686         /* Compute sort column info, and adjust MergeAppend's tlist as needed */
 687         (void) prepare_sort_from_pathkeys(root, plan, pathkeys,
 688                                                                           true,
 689                                                                           &node->numCols,
 690                                                                           &node->sortColIdx,
 691                                                                           &node->sortOperators,
 692                                                                           &node->collations,
 693                                                                           &node->nullsFirst);
 694
 695         /*
 696          * Now prepare the child plans.  We must apply prepare_sort_from_pathkeys
 697          * even to subplans that don't need an explicit sort, to make sure they
 698          * are returning the same sort key columns the MergeAppend expects.
 699          */
 700         foreach(subpaths, best_path->subpaths)
 701         {
 702                 Path       *subpath = (Path *) lfirst(subpaths);
 703                 Plan       *subplan;
 704                 int                     numsortkeys;
 705                 AttrNumber *sortColIdx;
 706                 Oid                *sortOperators;
 707                 Oid                *collations;
 708                 bool       *nullsFirst;
 709
 710                 /* Build the child plan */
 711                 subplan = create_plan_recurse(root, subpath);
 712
 713                 /* Compute sort column info, and adjust subplan's tlist as needed */
 714                 subplan = prepare_sort_from_pathkeys(root, subplan, pathkeys,
 715                                                                                          false,
 716                                                                                          &numsortkeys,
 717                                                                                          &sortColIdx,
 718                                                                                          &sortOperators,
 719                                                                                          &collations,
 720                                                                                          &nullsFirst);
 721
 722                 /*
 723                  * Check that we got the same sort key information.  We just Assert
 724                  * that the sortops match, since those depend only on the pathkeys;
 725                  * but it seems like a good idea to check the sort column numbers
 726                  * explicitly, to ensure the tlists really do match up.
 727                  */
 728                 Assert(numsortkeys == node->numCols);
 729                 if (memcmp(sortColIdx, node->sortColIdx,
 730                                    numsortkeys * sizeof(AttrNumber)) != 0)
 731                         elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
 732                 Assert(memcmp(sortOperators, node->sortOperators,
 733                                           numsortkeys * sizeof(Oid)) == 0);
 734                 Assert(memcmp(collations, node->collations,
 735                                           numsortkeys * sizeof(Oid)) == 0);
 736                 Assert(memcmp(nullsFirst, node->nullsFirst,
 737                                           numsortkeys * sizeof(bool)) == 0);
 738
 739                 /* Now, insert a Sort node if subplan isn't sufficiently ordered */
 740                 if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
 741                         subplan = (Plan *) make_sort(root, subplan, numsortkeys,
 742                                                                                  sortColIdx, sortOperators,
 743                                                                                  collations, nullsFirst,
 744                                                                                  best_path->limit_tuples);
 745
 746                 subplans = lappend(subplans, subplan);
 747         }
 748
 749         node->mergeplans = subplans;
 750
 751         return (Plan *) node;
 752 }
 753
 754 /*
 755  * create_result_plan
 756  *        Create a Result plan for 'best_path'.
 757  *        This is only used for the case of a query with an empty jointree.
 758  *
 759  *        Returns a Plan node.
 760  */
 761 static Result *
 762 create_result_plan(PlannerInfo *root, ResultPath *best_path)
 763 {
 764         List       *tlist;
 765         List       *quals;
 766
 767         /* The tlist will be installed later, since we have no RelOptInfo */
 768         Assert(best_path->path.parent == NULL);
 769         tlist = NIL;
 770
 771         /* best_path->quals is just bare clauses */
 772
 773         quals = order_qual_clauses(root, best_path->quals);
 774
 775         return make_result(root, tlist, (Node *) quals, NULL);
 776 }
 777
 778 /*
 779  * create_material_plan
 780  *        Create a Material plan for 'best_path' and (recursively) plans
 781  *        for its subpaths.
 782  *
 783  *        Returns a Plan node.
 784  */
 785 static Material *
 786 create_material_plan(PlannerInfo *root, MaterialPath *best_path)
 787 {
 788         Material   *plan;
 789         Plan       *subplan;
 790
 791         subplan = create_plan_recurse(root, best_path->subpath);
 792
 793         /* We don't want any excess columns in the materialized tuples */
 794         disuse_physical_tlist(subplan, best_path->subpath);
 795
 796         plan = make_material(subplan);
 797
 798         copy_path_costsize(&plan->plan, (Path *) best_path);
 799
 800         return plan;
 801 }
 802
 803 /*
 804  * create_unique_plan
 805  *        Create a Unique plan for 'best_path' and (recursively) plans
 806  *        for its subpaths.
 807  *
 808  *        Returns a Plan node.
 809  */
 810 static Plan *
 811 create_unique_plan(PlannerInfo *root, UniquePath *best_path)
 812 {
 813         Plan       *plan;
 814         Plan       *subplan;
 815         List       *in_operators;
 816         List       *uniq_exprs;
 817         List       *newtlist;
 818         int                     nextresno;
 819         bool            newitems;
 820         int                     numGroupCols;
 821         AttrNumber *groupColIdx;
 822         int                     groupColPos;
 823         ListCell   *l;
 824
 825         subplan = create_plan_recurse(root, best_path->subpath);
 826
 827         /* Done if we don't need to do any actual unique-ifying */
 828         if (best_path->umethod == UNIQUE_PATH_NOOP)
 829                 return subplan;
 830
 831         /*
 832          * As constructed, the subplan has a "flat" tlist containing just the Vars
 833          * needed here and at upper levels.  The values we are supposed to
 834          * unique-ify may be expressions in these variables.  We have to add any
 835          * such expressions to the subplan's tlist.
 836          *
 837          * The subplan may have a "physical" tlist if it is a simple scan plan. If
 838          * we're going to sort, this should be reduced to the regular tlist, so
 839          * that we don't sort more data than we need to.  For hashing, the tlist
 840          * should be left as-is if we don't need to add any expressions; but if we
 841          * do have to add expressions, then a projection step will be needed at
 842          * runtime anyway, so we may as well remove unneeded items. Therefore
 843          * newtlist starts from build_relation_tlist() not just a copy of the
 844          * subplan's tlist; and we don't install it into the subplan unless we are
 845          * sorting or stuff has to be added.
 846          */
 847         in_operators = best_path->in_operators;
 848         uniq_exprs = best_path->uniq_exprs;
 849
 850         /* initialize modified subplan tlist as just the "required" vars */
 851         newtlist = build_relation_tlist(best_path->path.parent);
 852         nextresno = list_length(newtlist) + 1;
 853         newitems = false;
 854
 855         foreach(l, uniq_exprs)
 856         {
 857                 Node       *uniqexpr = lfirst(l);
 858                 TargetEntry *tle;
 859
 860                 tle = tlist_member(uniqexpr, newtlist);
 861                 if (!tle)
 862                 {
 863                         tle = makeTargetEntry((Expr *) uniqexpr,
 864                                                                   nextresno,
 865                                                                   NULL,
 866                                                                   false);
 867                         newtlist = lappend(newtlist, tle);
 868                         nextresno++;
 869                         newitems = true;
 870                 }
 871         }
 872
 873         if (newitems || best_path->umethod == UNIQUE_PATH_SORT)
 874         {
 875                 /*
 876                  * If the top plan node can't do projections, we need to add a Result
 877                  * node to help it along.
 878                  */
 879                 if (!is_projection_capable_plan(subplan))
 880                         subplan = (Plan *) make_result(root, newtlist, NULL, subplan);
 881                 else
 882                         subplan->targetlist = newtlist;
 883         }
 884
 885         /*
 886          * Build control information showing which subplan output columns are to
 887          * be examined by the grouping step.  Unfortunately we can't merge this
 888          * with the previous loop, since we didn't then know which version of the
 889          * subplan tlist we'd end up using.
 890          */
 891         newtlist = subplan->targetlist;
 892         numGroupCols = list_length(uniq_exprs);
 893         groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
 894
 895         groupColPos = 0;
 896         foreach(l, uniq_exprs)
 897         {
 898                 Node       *uniqexpr = lfirst(l);
 899                 TargetEntry *tle;
 900
 901                 tle = tlist_member(uniqexpr, newtlist);
 902                 if (!tle)                               /* shouldn't happen */
 903                         elog(ERROR, "failed to find unique expression in subplan tlist");
 904                 groupColIdx[groupColPos++] = tle->resno;
 905         }
 906
 907         if (best_path->umethod == UNIQUE_PATH_HASH)
 908         {
 909                 long            numGroups;
 910                 Oid                *groupOperators;
 911
 912                 numGroups = (long) Min(best_path->rows, (double) LONG_MAX);
 913
 914                 /*
 915                  * Get the hashable equality operators for the Agg node to use.
 916                  * Normally these are the same as the IN clause operators, but if
 917                  * those are cross-type operators then the equality operators are the
 918                  * ones for the IN clause operators' RHS datatype.
 919                  */
 920                 groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
 921                 groupColPos = 0;
 922                 foreach(l, in_operators)
 923                 {
 924                         Oid                     in_oper = lfirst_oid(l);
 925                         Oid                     eq_oper;
 926
 927                         if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
 928                                 elog(ERROR, "could not find compatible hash operator for operator %u",
 929                                          in_oper);
 930                         groupOperators[groupColPos++] = eq_oper;
 931                 }
 932
 933                 /*
 934                  * Since the Agg node is going to project anyway, we can give it the
 935                  * minimum output tlist, without any stuff we might have added to the
 936                  * subplan tlist.
 937                  */
 938                 plan = (Plan *) make_agg(root,
 939                                                                  build_relation_tlist(best_path->path.parent),
 940                                                                  NIL,
 941                                                                  AGG_HASHED,
 942                                                                  NULL,
 943                                                                  numGroupCols,
 944                                                                  groupColIdx,
 945                                                                  groupOperators,
 946                                                                  numGroups,
 947                                                                  subplan);
 948         }
 949         else
 950         {
 951                 List       *sortList = NIL;
 952
 953                 /* Create an ORDER BY list to sort the input compatibly */
 954                 groupColPos = 0;
 955                 foreach(l, in_operators)
 956                 {
 957                         Oid                     in_oper = lfirst_oid(l);
 958                         Oid                     sortop;
 959                         Oid                     eqop;
 960                         TargetEntry *tle;
 961                         SortGroupClause *sortcl;
 962
 963                         sortop = get_ordering_op_for_equality_op(in_oper, false);
 964                         if (!OidIsValid(sortop))        /* shouldn't happen */
 965                                 elog(ERROR, "could not find ordering operator for equality operator %u",
 966                                          in_oper);
 967
 968                         /*
 969                          * The Unique node will need equality operators.  Normally these
 970                          * are the same as the IN clause operators, but if those are
 971                          * cross-type operators then the equality operators are the ones
 972                          * for the IN clause operators' RHS datatype.
 973                          */
 974                         eqop = get_equality_op_for_ordering_op(sortop, NULL);
 975                         if (!OidIsValid(eqop))          /* shouldn't happen */
 976                                 elog(ERROR, "could not find equality operator for ordering operator %u",
 977                                          sortop);
 978
 979                         tle = get_tle_by_resno(subplan->targetlist,
 980                                                                    groupColIdx[groupColPos]);
 981                         Assert(tle != NULL);
 982
 983                         sortcl = makeNode(SortGroupClause);
 984                         sortcl->tleSortGroupRef = assignSortGroupRef(tle,
 985                                                                                                                  subplan->targetlist);
 986                         sortcl->eqop = eqop;
 987                         sortcl->sortop = sortop;
 988                         sortcl->nulls_first = false;
 989                         sortcl->hashable = false;       /* no need to make this accurate */
 990                         sortList = lappend(sortList, sortcl);
 991                         groupColPos++;
 992                 }
 993                 plan = (Plan *) make_sort_from_sortclauses(root, sortList, subplan);
 994                 plan = (Plan *) make_unique(plan, sortList);
 995         }
 996
 997         /* Adjust output size estimate (other fields should be OK already) */
 998         plan->plan_rows = best_path->rows;
 999
1000         return plan;
1001 }
1002
1003
1004 /*****************************************************************************
1005  *
1006  *      BASE-RELATION SCAN METHODS
1007  *
1008  *****************************************************************************/
1009
1010
1011 /*
1012  * create_seqscan_plan
1013  *       Returns a seqscan plan for the base relation scanned by 'best_path'
1014  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1015  */
1016 static SeqScan *
1017 create_seqscan_plan(PlannerInfo *root, Path *best_path,
1018                                         List *tlist, List *scan_clauses)
1019 {
1020         SeqScan    *scan_plan;
1021         Index           scan_relid = best_path->parent->relid;
1022
1023         /* it should be a base rel... */
1024         Assert(scan_relid > 0);
1025         Assert(best_path->parent->rtekind == RTE_RELATION);
1026
1027         /* Sort clauses into best execution order */
1028         scan_clauses = order_qual_clauses(root, scan_clauses);
1029
1030         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1031         scan_clauses = extract_actual_clauses(scan_clauses, false);
1032
1033         scan_plan = make_seqscan(tlist,
1034                                                          scan_clauses,
1035                                                          scan_relid);
1036
1037         copy_path_costsize(&scan_plan->plan, best_path);
1038
1039         return scan_plan;
1040 }
1041
1042 /*
1043  * create_indexscan_plan
1044  *        Returns an indexscan plan for the base relation scanned by 'best_path'
1045  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1046  *
1047  * The indexquals list of the path contains implicitly-ANDed qual conditions.
1048  * The list can be empty --- then no index restrictions will be applied during
1049  * the scan.
1050  */
1051 static IndexScan *
1052 create_indexscan_plan(PlannerInfo *root,
1053                                           IndexPath *best_path,
1054                                           List *tlist,
1055                                           List *scan_clauses)
1056 {
1057         List       *indexquals = best_path->indexquals;
1058         List       *indexorderbys = best_path->indexorderbys;
1059         Index           baserelid = best_path->path.parent->relid;
1060         Oid                     indexoid = best_path->indexinfo->indexoid;
1061         List       *qpqual;
1062         List       *stripped_indexquals;
1063         List       *fixed_indexquals;
1064         List       *fixed_indexorderbys;
1065         ListCell   *l;
1066         IndexScan  *scan_plan;
1067
1068         /* it should be a base rel... */
1069         Assert(baserelid > 0);
1070         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1071
1072         /*
1073          * Build "stripped" indexquals structure (no RestrictInfos) to pass to
1074          * executor as indexqualorig
1075          */
1076         stripped_indexquals = get_actual_clauses(indexquals);
1077
1078         /*
1079          * The executor needs a copy with the indexkey on the left of each clause
1080          * and with index attr numbers substituted for table ones.
1081          */
1082         fixed_indexquals = fix_indexqual_references(root, best_path, indexquals);
1083
1084         /*
1085          * Likewise fix up index attr references in the ORDER BY expressions.
1086          */
1087         fixed_indexorderbys = fix_indexorderby_references(root, best_path, indexorderbys);
1088
1089         /*
1090          * If this is an innerjoin scan, the indexclauses will contain join
1091          * clauses that are not present in scan_clauses (since the passed-in value
1092          * is just the rel's baserestrictinfo list).  We must add these clauses to
1093          * scan_clauses to ensure they get checked.  In most cases we will remove
1094          * the join clauses again below, but if a join clause contains a special
1095          * operator, we need to make sure it gets into the scan_clauses.
1096          *
1097          * Note: pointer comparison should be enough to determine RestrictInfo
1098          * matches.
1099          */
1100         if (best_path->isjoininner)
1101                 scan_clauses = list_union_ptr(scan_clauses, best_path->indexclauses);
1102
1103         /*
1104          * The qpqual list must contain all restrictions not automatically handled
1105          * by the index.  All the predicates in the indexquals will be checked
1106          * (either by the index itself, or by nodeIndexscan.c), but if there are
1107          * any "special" operators involved then they must be included in qpqual.
1108          * The upshot is that qpqual must contain scan_clauses minus whatever
1109          * appears in indexquals.
1110          *
1111          * In normal cases simple pointer equality checks will be enough to spot
1112          * duplicate RestrictInfos, so we try that first.  In some situations
1113          * (particularly with OR'd index conditions) we may have scan_clauses that
1114          * are not equal to, but are logically implied by, the index quals; so we
1115          * also try a predicate_implied_by() check to see if we can discard quals
1116          * that way.  (predicate_implied_by assumes its first input contains only
1117          * immutable functions, so we have to check that.)
1118          *
1119          * We can also discard quals that are implied by a partial index's
1120          * predicate, but only in a plain SELECT; when scanning a target relation
1121          * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
1122          * plan so that they'll be properly rechecked by EvalPlanQual testing.
1123          */
1124         qpqual = NIL;
1125         foreach(l, scan_clauses)
1126         {
1127                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1128
1129                 Assert(IsA(rinfo, RestrictInfo));
1130                 if (rinfo->pseudoconstant)
1131                         continue;                       /* we may drop pseudoconstants here */
1132                 if (list_member_ptr(indexquals, rinfo))
1133                         continue;
1134                 if (!contain_mutable_functions((Node *) rinfo->clause))
1135                 {
1136                         List       *clausel = list_make1(rinfo->clause);
1137
1138                         if (predicate_implied_by(clausel, indexquals))
1139                                 continue;
1140                         if (best_path->indexinfo->indpred)
1141                         {
1142                                 if (baserelid != root->parse->resultRelation &&
1143                                         get_parse_rowmark(root->parse, baserelid) == NULL)
1144                                         if (predicate_implied_by(clausel,
1145                                                                                          best_path->indexinfo->indpred))
1146                                                 continue;
1147                         }
1148                 }
1149                 qpqual = lappend(qpqual, rinfo);
1150         }
1151
1152         /* Sort clauses into best execution order */
1153         qpqual = order_qual_clauses(root, qpqual);
1154
1155         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1156         qpqual = extract_actual_clauses(qpqual, false);
1157
1158         /*
1159          * We have to replace any outer-relation variables with nestloop params in
1160          * the indexqualorig, qpqual, and indexorderbyorig expressions.  A bit
1161          * annoying to have to do this separately from the processing in
1162          * fix_indexqual_references --- rethink this when generalizing the inner
1163          * indexscan support.  But note we can't really do this earlier because
1164          * it'd break the comparisons to predicates above ... (or would it?  Those
1165          * wouldn't have outer refs)
1166          */
1167         if (best_path->isjoininner)
1168         {
1169                 stripped_indexquals = (List *)
1170                         replace_nestloop_params(root, (Node *) stripped_indexquals);
1171                 qpqual = (List *)
1172                         replace_nestloop_params(root, (Node *) qpqual);
1173                 indexorderbys = (List *)
1174                         replace_nestloop_params(root, (Node *) indexorderbys);
1175         }
1176
1177         /* Finally ready to build the plan node */
1178         scan_plan = make_indexscan(tlist,
1179                                                            qpqual,
1180                                                            baserelid,
1181                                                            indexoid,
1182                                                            fixed_indexquals,
1183                                                            stripped_indexquals,
1184                                                            fixed_indexorderbys,
1185                                                            indexorderbys,
1186                                                            best_path->indexscandir,
1187                                                            best_path->indexonly);
1188
1189         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1190         /* use the indexscan-specific rows estimate, not the parent rel's */
1191         scan_plan->scan.plan.plan_rows = best_path->rows;
1192
1193         return scan_plan;
1194 }
1195
1196 /*
1197  * create_bitmap_scan_plan
1198  *        Returns a bitmap scan plan for the base relation scanned by 'best_path'
1199  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1200  */
1201 static BitmapHeapScan *
1202 create_bitmap_scan_plan(PlannerInfo *root,
1203                                                 BitmapHeapPath *best_path,
1204                                                 List *tlist,
1205                                                 List *scan_clauses)
1206 {
1207         Index           baserelid = best_path->path.parent->relid;
1208         Plan       *bitmapqualplan;
1209         List       *bitmapqualorig;
1210         List       *indexquals;
1211         List       *qpqual;
1212         ListCell   *l;
1213         BitmapHeapScan *scan_plan;
1214
1215         /* it should be a base rel... */
1216         Assert(baserelid > 0);
1217         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1218
1219         /* Process the bitmapqual tree into a Plan tree and qual lists */
1220         bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
1221                                                                                    &bitmapqualorig, &indexquals);
1222
1223         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1224         scan_clauses = extract_actual_clauses(scan_clauses, false);
1225
1226         /*
1227          * If this is a innerjoin scan, the indexclauses will contain join clauses
1228          * that are not present in scan_clauses (since the passed-in value is just
1229          * the rel's baserestrictinfo list).  We must add these clauses to
1230          * scan_clauses to ensure they get checked.  In most cases we will remove
1231          * the join clauses again below, but if a join clause contains a special
1232          * operator, we need to make sure it gets into the scan_clauses.
1233          */
1234         if (best_path->isjoininner)
1235         {
1236                 scan_clauses = list_concat_unique(scan_clauses, bitmapqualorig);
1237         }
1238
1239         /*
1240          * The qpqual list must contain all restrictions not automatically handled
1241          * by the index.  All the predicates in the indexquals will be checked
1242          * (either by the index itself, or by nodeBitmapHeapscan.c), but if there
1243          * are any "special" operators involved then they must be added to qpqual.
1244          * The upshot is that qpqual must contain scan_clauses minus whatever
1245          * appears in indexquals.
1246          *
1247          * In normal cases simple equal() checks will be enough to spot duplicate
1248          * clauses, so we try that first.  In some situations (particularly with
1249          * OR'd index conditions) we may have scan_clauses that are not equal to,
1250          * but are logically implied by, the index quals; so we also try a
1251          * predicate_implied_by() check to see if we can discard quals that way.
1252          * (predicate_implied_by assumes its first input contains only immutable
1253          * functions, so we have to check that.)
1254          *
1255          * Unlike create_indexscan_plan(), we need take no special thought here
1256          * for partial index predicates; this is because the predicate conditions
1257          * are already listed in bitmapqualorig and indexquals.  Bitmap scans have
1258          * to do it that way because predicate conditions need to be rechecked if
1259          * the scan becomes lossy.
1260          */
1261         qpqual = NIL;
1262         foreach(l, scan_clauses)
1263         {
1264                 Node       *clause = (Node *) lfirst(l);
1265
1266                 if (list_member(indexquals, clause))
1267                         continue;
1268                 if (!contain_mutable_functions(clause))
1269                 {
1270                         List       *clausel = list_make1(clause);
1271
1272                         if (predicate_implied_by(clausel, indexquals))
1273                                 continue;
1274                 }
1275                 qpqual = lappend(qpqual, clause);
1276         }
1277
1278         /* Sort clauses into best execution order */
1279         qpqual = order_qual_clauses(root, qpqual);
1280
1281         /*
1282          * When dealing with special operators, we will at this point have
1283          * duplicate clauses in qpqual and bitmapqualorig.      We may as well drop
1284          * 'em from bitmapqualorig, since there's no point in making the tests
1285          * twice.
1286          */
1287         bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
1288
1289         /* Finally ready to build the plan node */
1290         scan_plan = make_bitmap_heapscan(tlist,
1291                                                                          qpqual,
1292                                                                          bitmapqualplan,
1293                                                                          bitmapqualorig,
1294                                                                          baserelid);
1295
1296         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1297         /* use the indexscan-specific rows estimate, not the parent rel's */
1298         scan_plan->scan.plan.plan_rows = best_path->rows;
1299
1300         return scan_plan;
1301 }
1302
1303 /*
1304  * Given a bitmapqual tree, generate the Plan tree that implements it
1305  *
1306  * As byproducts, we also return in *qual and *indexqual the qual lists
1307  * (in implicit-AND form, without RestrictInfos) describing the original index
1308  * conditions and the generated indexqual conditions.  (These are the same in
1309  * simple cases, but when special index operators are involved, the former
1310  * list includes the special conditions while the latter includes the actual
1311  * indexable conditions derived from them.)  Both lists include partial-index
1312  * predicates, because we have to recheck predicates as well as index
1313  * conditions if the bitmap scan becomes lossy.
1314  *
1315  * Note: if you find yourself changing this, you probably need to change
1316  * make_restrictinfo_from_bitmapqual too.
1317  */
1318 static Plan *
1319 create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
1320                                           List **qual, List **indexqual)
1321 {
1322         Plan       *plan;
1323
1324         if (IsA(bitmapqual, BitmapAndPath))
1325         {
1326                 BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
1327                 List       *subplans = NIL;
1328                 List       *subquals = NIL;
1329                 List       *subindexquals = NIL;
1330                 ListCell   *l;
1331
1332                 /*
1333                  * There may well be redundant quals among the subplans, since a
1334                  * top-level WHERE qual might have gotten used to form several
1335                  * different index quals.  We don't try exceedingly hard to eliminate
1336                  * redundancies, but we do eliminate obvious duplicates by using
1337                  * list_concat_unique.
1338                  */
1339                 foreach(l, apath->bitmapquals)
1340                 {
1341                         Plan       *subplan;
1342                         List       *subqual;
1343                         List       *subindexqual;
1344
1345                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1346                                                                                         &subqual, &subindexqual);
1347                         subplans = lappend(subplans, subplan);
1348                         subquals = list_concat_unique(subquals, subqual);
1349                         subindexquals = list_concat_unique(subindexquals, subindexqual);
1350                 }
1351                 plan = (Plan *) make_bitmap_and(subplans);
1352                 plan->startup_cost = apath->path.startup_cost;
1353                 plan->total_cost = apath->path.total_cost;
1354                 plan->plan_rows =
1355                         clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
1356                 plan->plan_width = 0;   /* meaningless */
1357                 *qual = subquals;
1358                 *indexqual = subindexquals;
1359         }
1360         else if (IsA(bitmapqual, BitmapOrPath))
1361         {
1362                 BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
1363                 List       *subplans = NIL;
1364                 List       *subquals = NIL;
1365                 List       *subindexquals = NIL;
1366                 bool            const_true_subqual = false;
1367                 bool            const_true_subindexqual = false;
1368                 ListCell   *l;
1369
1370                 /*
1371                  * Here, we only detect qual-free subplans.  A qual-free subplan would
1372                  * cause us to generate "... OR true ..."  which we may as well reduce
1373                  * to just "true".      We do not try to eliminate redundant subclauses
1374                  * because (a) it's not as likely as in the AND case, and (b) we might
1375                  * well be working with hundreds or even thousands of OR conditions,
1376                  * perhaps from a long IN list.  The performance of list_append_unique
1377                  * would be unacceptable.
1378                  */
1379                 foreach(l, opath->bitmapquals)
1380                 {
1381                         Plan       *subplan;
1382                         List       *subqual;
1383                         List       *subindexqual;
1384
1385                         subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
1386                                                                                         &subqual, &subindexqual);
1387                         subplans = lappend(subplans, subplan);
1388                         if (subqual == NIL)
1389                                 const_true_subqual = true;
1390                         else if (!const_true_subqual)
1391                                 subquals = lappend(subquals,
1392                                                                    make_ands_explicit(subqual));
1393                         if (subindexqual == NIL)
1394                                 const_true_subindexqual = true;
1395                         else if (!const_true_subindexqual)
1396                                 subindexquals = lappend(subindexquals,
1397                                                                                 make_ands_explicit(subindexqual));
1398                 }
1399
1400                 /*
1401                  * In the presence of ScalarArrayOpExpr quals, we might have built
1402                  * BitmapOrPaths with just one subpath; don't add an OR step.
1403                  */
1404                 if (list_length(subplans) == 1)
1405                 {
1406                         plan = (Plan *) linitial(subplans);
1407                 }
1408                 else
1409                 {
1410                         plan = (Plan *) make_bitmap_or(subplans);
1411                         plan->startup_cost = opath->path.startup_cost;
1412                         plan->total_cost = opath->path.total_cost;
1413                         plan->plan_rows =
1414                                 clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
1415                         plan->plan_width = 0;           /* meaningless */
1416                 }
1417
1418                 /*
1419                  * If there were constant-TRUE subquals, the OR reduces to constant
1420                  * TRUE.  Also, avoid generating one-element ORs, which could happen
1421                  * due to redundancy elimination or ScalarArrayOpExpr quals.
1422                  */
1423                 if (const_true_subqual)
1424                         *qual = NIL;
1425                 else if (list_length(subquals) <= 1)
1426                         *qual = subquals;
1427                 else
1428                         *qual = list_make1(make_orclause(subquals));
1429                 if (const_true_subindexqual)
1430                         *indexqual = NIL;
1431                 else if (list_length(subindexquals) <= 1)
1432                         *indexqual = subindexquals;
1433                 else
1434                         *indexqual = list_make1(make_orclause(subindexquals));
1435         }
1436         else if (IsA(bitmapqual, IndexPath))
1437         {
1438                 IndexPath  *ipath = (IndexPath *) bitmapqual;
1439                 IndexScan  *iscan;
1440                 ListCell   *l;
1441
1442                 /* Use the regular indexscan plan build machinery... */
1443                 iscan = create_indexscan_plan(root, ipath, NIL, NIL);
1444                 /* then convert to a bitmap indexscan */
1445                 plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
1446                                                                                           iscan->indexid,
1447                                                                                           iscan->indexqual,
1448                                                                                           iscan->indexqualorig);
1449                 plan->startup_cost = 0.0;
1450                 plan->total_cost = ipath->indextotalcost;
1451                 plan->plan_rows =
1452                         clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
1453                 plan->plan_width = 0;   /* meaningless */
1454                 *qual = get_actual_clauses(ipath->indexclauses);
1455                 *indexqual = get_actual_clauses(ipath->indexquals);
1456                 foreach(l, ipath->indexinfo->indpred)
1457                 {
1458                         Expr       *pred = (Expr *) lfirst(l);
1459
1460                         /*
1461                          * We know that the index predicate must have been implied by the
1462                          * query condition as a whole, but it may or may not be implied by
1463                          * the conditions that got pushed into the bitmapqual.  Avoid
1464                          * generating redundant conditions.
1465                          */
1466                         if (!predicate_implied_by(list_make1(pred), ipath->indexclauses))
1467                         {
1468                                 *qual = lappend(*qual, pred);
1469                                 *indexqual = lappend(*indexqual, pred);
1470                         }
1471                 }
1472
1473                 /*
1474                  * Replace outer-relation variables with nestloop params, but only
1475                  * after doing the above comparisons to index predicates.
1476                  */
1477                 if (ipath->isjoininner)
1478                 {
1479                         *qual = (List *)
1480                                 replace_nestloop_params(root, (Node *) *qual);
1481                         *indexqual = (List *)
1482                                 replace_nestloop_params(root, (Node *) *indexqual);
1483                 }
1484         }
1485         else
1486         {
1487                 elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
1488                 plan = NULL;                    /* keep compiler quiet */
1489         }
1490
1491         return plan;
1492 }
1493
1494 /*
1495  * create_tidscan_plan
1496  *       Returns a tidscan plan for the base relation scanned by 'best_path'
1497  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1498  */
1499 static TidScan *
1500 create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
1501                                         List *tlist, List *scan_clauses)
1502 {
1503         TidScan    *scan_plan;
1504         Index           scan_relid = best_path->path.parent->relid;
1505         List       *ortidquals;
1506
1507         /* it should be a base rel... */
1508         Assert(scan_relid > 0);
1509         Assert(best_path->path.parent->rtekind == RTE_RELATION);
1510
1511         /* Sort clauses into best execution order */
1512         scan_clauses = order_qual_clauses(root, scan_clauses);
1513
1514         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1515         scan_clauses = extract_actual_clauses(scan_clauses, false);
1516
1517         /*
1518          * Remove any clauses that are TID quals.  This is a bit tricky since the
1519          * tidquals list has implicit OR semantics.
1520          */
1521         ortidquals = best_path->tidquals;
1522         if (list_length(ortidquals) > 1)
1523                 ortidquals = list_make1(make_orclause(ortidquals));
1524         scan_clauses = list_difference(scan_clauses, ortidquals);
1525
1526         scan_plan = make_tidscan(tlist,
1527                                                          scan_clauses,
1528                                                          scan_relid,
1529                                                          best_path->tidquals);
1530
1531         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1532
1533         return scan_plan;
1534 }
1535
1536 /*
1537  * create_subqueryscan_plan
1538  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
1539  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1540  */
1541 static SubqueryScan *
1542 create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
1543                                                  List *tlist, List *scan_clauses)
1544 {
1545         SubqueryScan *scan_plan;
1546         Index           scan_relid = best_path->parent->relid;
1547
1548         /* it should be a subquery base rel... */
1549         Assert(scan_relid > 0);
1550         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
1551
1552         /* Sort clauses into best execution order */
1553         scan_clauses = order_qual_clauses(root, scan_clauses);
1554
1555         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1556         scan_clauses = extract_actual_clauses(scan_clauses, false);
1557
1558         scan_plan = make_subqueryscan(tlist,
1559                                                                   scan_clauses,
1560                                                                   scan_relid,
1561                                                                   best_path->parent->subplan);
1562
1563         copy_path_costsize(&scan_plan->scan.plan, best_path);
1564
1565         return scan_plan;
1566 }
1567
1568 /*
1569  * create_functionscan_plan
1570  *       Returns a functionscan plan for the base relation scanned by 'best_path'
1571  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1572  */
1573 static FunctionScan *
1574 create_functionscan_plan(PlannerInfo *root, Path *best_path,
1575                                                  List *tlist, List *scan_clauses)
1576 {
1577         FunctionScan *scan_plan;
1578         Index           scan_relid = best_path->parent->relid;
1579         RangeTblEntry *rte;
1580
1581         /* it should be a function base rel... */
1582         Assert(scan_relid > 0);
1583         rte = planner_rt_fetch(scan_relid, root);
1584         Assert(rte->rtekind == RTE_FUNCTION);
1585
1586         /* Sort clauses into best execution order */
1587         scan_clauses = order_qual_clauses(root, scan_clauses);
1588
1589         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1590         scan_clauses = extract_actual_clauses(scan_clauses, false);
1591
1592         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
1593                                                                   rte->funcexpr,
1594                                                                   rte->eref->colnames,
1595                                                                   rte->funccoltypes,
1596                                                                   rte->funccoltypmods,
1597                                                                   rte->funccolcollations);
1598
1599         copy_path_costsize(&scan_plan->scan.plan, best_path);
1600
1601         return scan_plan;
1602 }
1603
1604 /*
1605  * create_valuesscan_plan
1606  *       Returns a valuesscan plan for the base relation scanned by 'best_path'
1607  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1608  */
1609 static ValuesScan *
1610 create_valuesscan_plan(PlannerInfo *root, Path *best_path,
1611                                            List *tlist, List *scan_clauses)
1612 {
1613         ValuesScan *scan_plan;
1614         Index           scan_relid = best_path->parent->relid;
1615         RangeTblEntry *rte;
1616
1617         /* it should be a values base rel... */
1618         Assert(scan_relid > 0);
1619         rte = planner_rt_fetch(scan_relid, root);
1620         Assert(rte->rtekind == RTE_VALUES);
1621
1622         /* Sort clauses into best execution order */
1623         scan_clauses = order_qual_clauses(root, scan_clauses);
1624
1625         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1626         scan_clauses = extract_actual_clauses(scan_clauses, false);
1627
1628         scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
1629                                                                 rte->values_lists);
1630
1631         copy_path_costsize(&scan_plan->scan.plan, best_path);
1632
1633         return scan_plan;
1634 }
1635
1636 /*
1637  * create_ctescan_plan
1638  *       Returns a ctescan plan for the base relation scanned by 'best_path'
1639  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1640  */
1641 static CteScan *
1642 create_ctescan_plan(PlannerInfo *root, Path *best_path,
1643                                         List *tlist, List *scan_clauses)
1644 {
1645         CteScan    *scan_plan;
1646         Index           scan_relid = best_path->parent->relid;
1647         RangeTblEntry *rte;
1648         SubPlan    *ctesplan = NULL;
1649         int                     plan_id;
1650         int                     cte_param_id;
1651         PlannerInfo *cteroot;
1652         Index           levelsup;
1653         int                     ndx;
1654         ListCell   *lc;
1655
1656         Assert(scan_relid > 0);
1657         rte = planner_rt_fetch(scan_relid, root);
1658         Assert(rte->rtekind == RTE_CTE);
1659         Assert(!rte->self_reference);
1660
1661         /*
1662          * Find the referenced CTE, and locate the SubPlan previously made for it.
1663          */
1664         levelsup = rte->ctelevelsup;
1665         cteroot = root;
1666         while (levelsup-- > 0)
1667         {
1668                 cteroot = cteroot->parent_root;
1669                 if (!cteroot)                   /* shouldn't happen */
1670                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1671         }
1672
1673         /*
1674          * Note: cte_plan_ids can be shorter than cteList, if we are still working
1675          * on planning the CTEs (ie, this is a side-reference from another CTE).
1676          * So we mustn't use forboth here.
1677          */
1678         ndx = 0;
1679         foreach(lc, cteroot->parse->cteList)
1680         {
1681                 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
1682
1683                 if (strcmp(cte->ctename, rte->ctename) == 0)
1684                         break;
1685                 ndx++;
1686         }
1687         if (lc == NULL)                         /* shouldn't happen */
1688                 elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
1689         if (ndx >= list_length(cteroot->cte_plan_ids))
1690                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
1691         plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
1692         Assert(plan_id > 0);
1693         foreach(lc, cteroot->init_plans)
1694         {
1695                 ctesplan = (SubPlan *) lfirst(lc);
1696                 if (ctesplan->plan_id == plan_id)
1697                         break;
1698         }
1699         if (lc == NULL)                         /* shouldn't happen */
1700                 elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
1701
1702         /*
1703          * We need the CTE param ID, which is the sole member of the SubPlan's
1704          * setParam list.
1705          */
1706         cte_param_id = linitial_int(ctesplan->setParam);
1707
1708         /* Sort clauses into best execution order */
1709         scan_clauses = order_qual_clauses(root, scan_clauses);
1710
1711         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1712         scan_clauses = extract_actual_clauses(scan_clauses, false);
1713
1714         scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
1715                                                          plan_id, cte_param_id);
1716
1717         copy_path_costsize(&scan_plan->scan.plan, best_path);
1718
1719         return scan_plan;
1720 }
1721
1722 /*
1723  * create_worktablescan_plan
1724  *       Returns a worktablescan plan for the base relation scanned by 'best_path'
1725  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1726  */
1727 static WorkTableScan *
1728 create_worktablescan_plan(PlannerInfo *root, Path *best_path,
1729                                                   List *tlist, List *scan_clauses)
1730 {
1731         WorkTableScan *scan_plan;
1732         Index           scan_relid = best_path->parent->relid;
1733         RangeTblEntry *rte;
1734         Index           levelsup;
1735         PlannerInfo *cteroot;
1736
1737         Assert(scan_relid > 0);
1738         rte = planner_rt_fetch(scan_relid, root);
1739         Assert(rte->rtekind == RTE_CTE);
1740         Assert(rte->self_reference);
1741
1742         /*
1743          * We need to find the worktable param ID, which is in the plan level
1744          * that's processing the recursive UNION, which is one level *below* where
1745          * the CTE comes from.
1746          */
1747         levelsup = rte->ctelevelsup;
1748         if (levelsup == 0)                      /* shouldn't happen */
1749                 elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1750         levelsup--;
1751         cteroot = root;
1752         while (levelsup-- > 0)
1753         {
1754                 cteroot = cteroot->parent_root;
1755                 if (!cteroot)                   /* shouldn't happen */
1756                         elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
1757         }
1758         if (cteroot->wt_param_id < 0)           /* shouldn't happen */
1759                 elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename);
1760
1761         /* Sort clauses into best execution order */
1762         scan_clauses = order_qual_clauses(root, scan_clauses);
1763
1764         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1765         scan_clauses = extract_actual_clauses(scan_clauses, false);
1766
1767         scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
1768                                                                    cteroot->wt_param_id);
1769
1770         copy_path_costsize(&scan_plan->scan.plan, best_path);
1771
1772         return scan_plan;
1773 }
1774
1775 /*
1776  * create_foreignscan_plan
1777  *       Returns a foreignscan plan for the base relation scanned by 'best_path'
1778  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
1779  */
1780 static ForeignScan *
1781 create_foreignscan_plan(PlannerInfo *root, ForeignPath *best_path,
1782                                                 List *tlist, List *scan_clauses)
1783 {
1784         ForeignScan *scan_plan;
1785         RelOptInfo *rel = best_path->path.parent;
1786         Index           scan_relid = rel->relid;
1787         RangeTblEntry *rte;
1788         bool            fsSystemCol;
1789         int                     i;
1790
1791         /* it should be a base rel... */
1792         Assert(scan_relid > 0);
1793         Assert(rel->rtekind == RTE_RELATION);
1794         rte = planner_rt_fetch(scan_relid, root);
1795         Assert(rte->rtekind == RTE_RELATION);
1796
1797         /* Sort clauses into best execution order */
1798         scan_clauses = order_qual_clauses(root, scan_clauses);
1799
1800         /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
1801         scan_clauses = extract_actual_clauses(scan_clauses, false);
1802
1803         /* Detect whether any system columns are requested from rel */
1804         fsSystemCol = false;
1805         for (i = rel->min_attr; i < 0; i++)
1806         {
1807                 if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
1808                 {
1809                         fsSystemCol = true;
1810                         break;
1811                 }
1812         }
1813
1814         scan_plan = make_foreignscan(tlist,
1815                                                                  scan_clauses,
1816                                                                  scan_relid,
1817                                                                  fsSystemCol,
1818                                                                  best_path->fdwplan);
1819
1820         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
1821
1822         return scan_plan;
1823 }
1824
1825
1826 /*****************************************************************************
1827  *
1828  *      JOIN METHODS
1829  *
1830  *****************************************************************************/
1831
1832 static NestLoop *
1833 create_nestloop_plan(PlannerInfo *root,
1834                                          NestPath *best_path,
1835                                          Plan *outer_plan,
1836                                          Plan *inner_plan)
1837 {
1838         NestLoop   *join_plan;
1839         List       *tlist = build_relation_tlist(best_path->path.parent);
1840         List       *joinrestrictclauses = best_path->joinrestrictinfo;
1841         List       *joinclauses;
1842         List       *otherclauses;
1843         Relids          outerrelids;
1844         List       *nestParams;
1845         ListCell   *cell;
1846         ListCell   *prev;
1847         ListCell   *next;
1848
1849         /*
1850          * If the inner path is a nestloop inner indexscan, it might be using some
1851          * of the join quals as index quals, in which case we don't have to check
1852          * them again at the join node.  Remove any join quals that are redundant.
1853          */
1854         joinrestrictclauses =
1855                 select_nonredundant_join_clauses(root,
1856                                                                                  joinrestrictclauses,
1857                                                                                  best_path->innerjoinpath);
1858
1859         /* Sort join qual clauses into best execution order */
1860         joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
1861
1862         /* Get the join qual clauses (in plain expression form) */
1863         /* Any pseudoconstant clauses are ignored here */
1864         if (IS_OUTER_JOIN(best_path->jointype))
1865         {
1866                 extract_actual_join_clauses(joinrestrictclauses,
1867                                                                         &joinclauses, &otherclauses);
1868         }
1869         else
1870         {
1871                 /* We can treat all clauses alike for an inner join */
1872                 joinclauses = extract_actual_clauses(joinrestrictclauses, false);
1873                 otherclauses = NIL;
1874         }
1875
1876         /*
1877          * Identify any nestloop parameters that should be supplied by this join
1878          * node, and move them from root->curOuterParams to the nestParams list.
1879          */
1880         outerrelids = best_path->outerjoinpath->parent->relids;
1881         nestParams = NIL;
1882         prev = NULL;
1883         for (cell = list_head(root->curOuterParams); cell; cell = next)
1884         {
1885                 NestLoopParam *nlp = (NestLoopParam *) lfirst(cell);
1886
1887                 next = lnext(cell);
1888                 if (bms_is_member(nlp->paramval->varno, outerrelids))
1889                 {
1890                         root->curOuterParams = list_delete_cell(root->curOuterParams,
1891                                                                                                         cell, prev);
1892                         nestParams = lappend(nestParams, nlp);
1893                 }
1894                 else
1895                         prev = cell;
1896         }
1897
1898         join_plan = make_nestloop(tlist,
1899                                                           joinclauses,
1900                                                           otherclauses,
1901                                                           nestParams,
1902                                                           outer_plan,
1903                                                           inner_plan,
1904                                                           best_path->jointype);
1905
1906         copy_path_costsize(&join_plan->join.plan, &best_path->path);
1907
1908         return join_plan;
1909 }
1910
1911 static MergeJoin *
1912 create_mergejoin_plan(PlannerInfo *root,
1913                                           MergePath *best_path,
1914                                           Plan *outer_plan,
1915                                           Plan *inner_plan)
1916 {
1917         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
1918         List       *joinclauses;
1919         List       *otherclauses;
1920         List       *mergeclauses;
1921         List       *outerpathkeys;
1922         List       *innerpathkeys;
1923         int                     nClauses;
1924         Oid                *mergefamilies;
1925         Oid                *mergecollations;
1926         int                *mergestrategies;
1927         bool       *mergenullsfirst;
1928         MergeJoin  *join_plan;
1929         int                     i;
1930         ListCell   *lc;
1931         ListCell   *lop;
1932         ListCell   *lip;
1933
1934         /* Sort join qual clauses into best execution order */
1935         /* NB: do NOT reorder the mergeclauses */
1936         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
1937
1938         /* Get the join qual clauses (in plain expression form) */
1939         /* Any pseudoconstant clauses are ignored here */
1940         if (IS_OUTER_JOIN(best_path->jpath.jointype))
1941         {
1942                 extract_actual_join_clauses(joinclauses,
1943                                                                         &joinclauses, &otherclauses);
1944         }
1945         else
1946         {
1947                 /* We can treat all clauses alike for an inner join */
1948                 joinclauses = extract_actual_clauses(joinclauses, false);
1949                 otherclauses = NIL;
1950         }
1951
1952         /*
1953          * Remove the mergeclauses from the list of join qual clauses, leaving the
1954          * list of quals that must be checked as qpquals.
1955          */
1956         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
1957         joinclauses = list_difference(joinclauses, mergeclauses);
1958
1959         /*
1960          * Rearrange mergeclauses, if needed, so that the outer variable is always
1961          * on the left; mark the mergeclause restrictinfos with correct
1962          * outer_is_left status.
1963          */
1964         mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
1965                                                          best_path->jpath.outerjoinpath->parent->relids);
1966
1967         /*
1968          * Create explicit sort nodes for the outer and inner paths if necessary.
1969          * Make sure there are no excess columns in the inputs if sorting.
1970          */
1971         if (best_path->outersortkeys)
1972         {
1973                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
1974                 outer_plan = (Plan *)
1975                         make_sort_from_pathkeys(root,
1976                                                                         outer_plan,
1977                                                                         best_path->outersortkeys,
1978                                                                         -1.0);
1979                 outerpathkeys = best_path->outersortkeys;
1980         }
1981         else
1982                 outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;
1983
1984         if (best_path->innersortkeys)
1985         {
1986                 disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
1987                 inner_plan = (Plan *)
1988                         make_sort_from_pathkeys(root,
1989                                                                         inner_plan,
1990                                                                         best_path->innersortkeys,
1991                                                                         -1.0);
1992                 innerpathkeys = best_path->innersortkeys;
1993         }
1994         else
1995                 innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;
1996
1997         /*
1998          * If specified, add a materialize node to shield the inner plan from the
1999          * need to handle mark/restore.
2000          */
2001         if (best_path->materialize_inner)
2002         {
2003                 Plan       *matplan = (Plan *) make_material(inner_plan);
2004
2005                 /*
2006                  * We assume the materialize will not spill to disk, and therefore
2007                  * charge just cpu_operator_cost per tuple.  (Keep this estimate in
2008                  * sync with cost_mergejoin.)
2009                  */
2010                 copy_plan_costsize(matplan, inner_plan);
2011                 matplan->total_cost += cpu_operator_cost * matplan->plan_rows;
2012
2013                 inner_plan = matplan;
2014         }
2015
2016         /*
2017          * Compute the opfamily/collation/strategy/nullsfirst arrays needed by the
2018          * executor.  The information is in the pathkeys for the two inputs, but
2019          * we need to be careful about the possibility of mergeclauses sharing a
2020          * pathkey (compare find_mergeclauses_for_pathkeys()).
2021          */
2022         nClauses = list_length(mergeclauses);
2023         Assert(nClauses == list_length(best_path->path_mergeclauses));
2024         mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
2025         mergecollations = (Oid *) palloc(nClauses * sizeof(Oid));
2026         mergestrategies = (int *) palloc(nClauses * sizeof(int));
2027         mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));
2028
2029         lop = list_head(outerpathkeys);
2030         lip = list_head(innerpathkeys);
2031         i = 0;
2032         foreach(lc, best_path->path_mergeclauses)
2033         {
2034                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2035                 EquivalenceClass *oeclass;
2036                 EquivalenceClass *ieclass;
2037                 PathKey    *opathkey;
2038                 PathKey    *ipathkey;
2039                 EquivalenceClass *opeclass;
2040                 EquivalenceClass *ipeclass;
2041                 ListCell   *l2;
2042
2043                 /* fetch outer/inner eclass from mergeclause */
2044                 Assert(IsA(rinfo, RestrictInfo));
2045                 if (rinfo->outer_is_left)
2046                 {
2047                         oeclass = rinfo->left_ec;
2048                         ieclass = rinfo->right_ec;
2049                 }
2050                 else
2051                 {
2052                         oeclass = rinfo->right_ec;
2053                         ieclass = rinfo->left_ec;
2054                 }
2055                 Assert(oeclass != NULL);
2056                 Assert(ieclass != NULL);
2057
2058                 /*
2059                  * For debugging purposes, we check that the eclasses match the paths'
2060                  * pathkeys.  In typical cases the merge clauses are one-to-one with
2061                  * the pathkeys, but when dealing with partially redundant query
2062                  * conditions, we might have clauses that re-reference earlier path
2063                  * keys.  The case that we need to reject is where a pathkey is
2064                  * entirely skipped over.
2065                  *
2066                  * lop and lip reference the first as-yet-unused pathkey elements;
2067                  * it's okay to match them, or any element before them.  If they're
2068                  * NULL then we have found all pathkey elements to be used.
2069                  */
2070                 if (lop)
2071                 {
2072                         opathkey = (PathKey *) lfirst(lop);
2073                         opeclass = opathkey->pk_eclass;
2074                         if (oeclass == opeclass)
2075                         {
2076                                 /* fast path for typical case */
2077                                 lop = lnext(lop);
2078                         }
2079                         else
2080                         {
2081                                 /* redundant clauses ... must match something before lop */
2082                                 foreach(l2, outerpathkeys)
2083                                 {
2084                                         if (l2 == lop)
2085                                                 break;
2086                                         opathkey = (PathKey *) lfirst(l2);
2087                                         opeclass = opathkey->pk_eclass;
2088                                         if (oeclass == opeclass)
2089                                                 break;
2090                                 }
2091                                 if (oeclass != opeclass)
2092                                         elog(ERROR, "outer pathkeys do not match mergeclauses");
2093                         }
2094                 }
2095                 else
2096                 {
2097                         /* redundant clauses ... must match some already-used pathkey */
2098                         opathkey = NULL;
2099                         opeclass = NULL;
2100                         foreach(l2, outerpathkeys)
2101                         {
2102                                 opathkey = (PathKey *) lfirst(l2);
2103                                 opeclass = opathkey->pk_eclass;
2104                                 if (oeclass == opeclass)
2105                                         break;
2106                         }
2107                         if (l2 == NULL)
2108                                 elog(ERROR, "outer pathkeys do not match mergeclauses");
2109                 }
2110
2111                 if (lip)
2112                 {
2113                         ipathkey = (PathKey *) lfirst(lip);
2114                         ipeclass = ipathkey->pk_eclass;
2115                         if (ieclass == ipeclass)
2116                         {
2117                                 /* fast path for typical case */
2118                                 lip = lnext(lip);
2119                         }
2120                         else
2121                         {
2122                                 /* redundant clauses ... must match something before lip */
2123                                 foreach(l2, innerpathkeys)
2124                                 {
2125                                         if (l2 == lip)
2126                                                 break;
2127                                         ipathkey = (PathKey *) lfirst(l2);
2128                                         ipeclass = ipathkey->pk_eclass;
2129                                         if (ieclass == ipeclass)
2130                                                 break;
2131                                 }
2132                                 if (ieclass != ipeclass)
2133                                         elog(ERROR, "inner pathkeys do not match mergeclauses");
2134                         }
2135                 }
2136                 else
2137                 {
2138                         /* redundant clauses ... must match some already-used pathkey */
2139                         ipathkey = NULL;
2140                         ipeclass = NULL;
2141                         foreach(l2, innerpathkeys)
2142                         {
2143                                 ipathkey = (PathKey *) lfirst(l2);
2144                                 ipeclass = ipathkey->pk_eclass;
2145                                 if (ieclass == ipeclass)
2146                                         break;
2147                         }
2148                         if (l2 == NULL)
2149                                 elog(ERROR, "inner pathkeys do not match mergeclauses");
2150                 }
2151
2152                 /* pathkeys should match each other too (more debugging) */
2153                 if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
2154                         opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation ||
2155                         opathkey->pk_strategy != ipathkey->pk_strategy ||
2156                         opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
2157                         elog(ERROR, "left and right pathkeys do not match in mergejoin");
2158
2159                 /* OK, save info for executor */
2160                 mergefamilies[i] = opathkey->pk_opfamily;
2161                 mergecollations[i] = opathkey->pk_eclass->ec_collation;
2162                 mergestrategies[i] = opathkey->pk_strategy;
2163                 mergenullsfirst[i] = opathkey->pk_nulls_first;
2164                 i++;
2165         }
2166
2167         /*
2168          * Note: it is not an error if we have additional pathkey elements (i.e.,
2169          * lop or lip isn't NULL here).  The input paths might be better-sorted
2170          * than we need for the current mergejoin.
2171          */
2172
2173         /*
2174          * Now we can build the mergejoin node.
2175          */
2176         join_plan = make_mergejoin(tlist,
2177                                                            joinclauses,
2178                                                            otherclauses,
2179                                                            mergeclauses,
2180                                                            mergefamilies,
2181                                                            mergecollations,
2182                                                            mergestrategies,
2183                                                            mergenullsfirst,
2184                                                            outer_plan,
2185                                                            inner_plan,
2186                                                            best_path->jpath.jointype);
2187
2188         /* Costs of sort and material steps are included in path cost already */
2189         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
2190
2191         return join_plan;
2192 }
2193
2194 static HashJoin *
2195 create_hashjoin_plan(PlannerInfo *root,
2196                                          HashPath *best_path,
2197                                          Plan *outer_plan,
2198                                          Plan *inner_plan)
2199 {
2200         List       *tlist = build_relation_tlist(best_path->jpath.path.parent);
2201         List       *joinclauses;
2202         List       *otherclauses;
2203         List       *hashclauses;
2204         Oid                     skewTable = InvalidOid;
2205         AttrNumber      skewColumn = InvalidAttrNumber;
2206         bool            skewInherit = false;
2207         Oid                     skewColType = InvalidOid;
2208         int32           skewColTypmod = -1;
2209         HashJoin   *join_plan;
2210         Hash       *hash_plan;
2211
2212         /* Sort join qual clauses into best execution order */
2213         joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
2214         /* There's no point in sorting the hash clauses ... */
2215
2216         /* Get the join qual clauses (in plain expression form) */
2217         /* Any pseudoconstant clauses are ignored here */
2218         if (IS_OUTER_JOIN(best_path->jpath.jointype))
2219         {
2220                 extract_actual_join_clauses(joinclauses,
2221                                                                         &joinclauses, &otherclauses);
2222         }
2223         else
2224         {
2225                 /* We can treat all clauses alike for an inner join */
2226                 joinclauses = extract_actual_clauses(joinclauses, false);
2227                 otherclauses = NIL;
2228         }
2229
2230         /*
2231          * Remove the hashclauses from the list of join qual clauses, leaving the
2232          * list of quals that must be checked as qpquals.
2233          */
2234         hashclauses = get_actual_clauses(best_path->path_hashclauses);
2235         joinclauses = list_difference(joinclauses, hashclauses);
2236
2237         /*
2238          * Rearrange hashclauses, if needed, so that the outer variable is always
2239          * on the left.
2240          */
2241         hashclauses = get_switched_clauses(best_path->path_hashclauses,
2242                                                          best_path->jpath.outerjoinpath->parent->relids);
2243
2244         /* We don't want any excess columns in the hashed tuples */
2245         disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
2246
2247         /* If we expect batching, suppress excess columns in outer tuples too */
2248         if (best_path->num_batches > 1)
2249                 disuse_physical_tlist(outer_plan, best_path->jpath.outerjoinpath);
2250
2251         /*
2252          * If there is a single join clause and we can identify the outer variable
2253          * as a simple column reference, supply its identity for possible use in
2254          * skew optimization.  (Note: in principle we could do skew optimization
2255          * with multiple join clauses, but we'd have to be able to determine the
2256          * most common combinations of outer values, which we don't currently have
2257          * enough stats for.)
2258          */
2259         if (list_length(hashclauses) == 1)
2260         {
2261                 OpExpr     *clause = (OpExpr *) linitial(hashclauses);
2262                 Node       *node;
2263
2264                 Assert(is_opclause(clause));
2265                 node = (Node *) linitial(clause->args);
2266                 if (IsA(node, RelabelType))
2267                         node = (Node *) ((RelabelType *) node)->arg;
2268                 if (IsA(node, Var))
2269                 {
2270                         Var                *var = (Var *) node;
2271                         RangeTblEntry *rte;
2272
2273                         rte = root->simple_rte_array[var->varno];
2274                         if (rte->rtekind == RTE_RELATION)
2275                         {
2276                                 skewTable = rte->relid;
2277                                 skewColumn = var->varattno;
2278                                 skewInherit = rte->inh;
2279                                 skewColType = var->vartype;
2280                                 skewColTypmod = var->vartypmod;
2281                         }
2282                 }
2283         }
2284
2285         /*
2286          * Build the hash node and hash join node.
2287          */
2288         hash_plan = make_hash(inner_plan,
2289                                                   skewTable,
2290                                                   skewColumn,
2291                                                   skewInherit,
2292                                                   skewColType,
2293                                                   skewColTypmod);
2294         join_plan = make_hashjoin(tlist,
2295                                                           joinclauses,
2296                                                           otherclauses,
2297                                                           hashclauses,
2298                                                           outer_plan,
2299                                                           (Plan *) hash_plan,
2300                                                           best_path->jpath.jointype);
2301
2302         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
2303
2304         return join_plan;
2305 }
2306
2307
2308 /*****************************************************************************
2309  *
2310  *      SUPPORTING ROUTINES
2311  *
2312  *****************************************************************************/
2313
2314 /*
2315  * replace_nestloop_params
2316  *        Replace outer-relation Vars in the given expression with nestloop Params
2317  *
2318  * All Vars belonging to the relation(s) identified by root->curOuterRels
2319  * are replaced by Params, and entries are added to root->curOuterParams if
2320  * not already present.
2321  */
2322 static Node *
2323 replace_nestloop_params(PlannerInfo *root, Node *expr)
2324 {
2325         /* No setup needed for tree walk, so away we go */
2326         return replace_nestloop_params_mutator(expr, root);
2327 }
2328
2329 static Node *
2330 replace_nestloop_params_mutator(Node *node, PlannerInfo *root)
2331 {
2332         if (node == NULL)
2333                 return NULL;
2334         if (IsA(node, Var))
2335         {
2336                 Var                *var = (Var *) node;
2337                 Param      *param;
2338                 NestLoopParam *nlp;
2339                 ListCell   *lc;
2340
2341                 /* Upper-level Vars should be long gone at this point */
2342                 Assert(var->varlevelsup == 0);
2343                 /* If not to be replaced, we can just return the Var unmodified */
2344                 if (!bms_is_member(var->varno, root->curOuterRels))
2345                         return node;
2346                 /* Create a Param representing the Var */
2347                 param = assign_nestloop_param(root, var);
2348                 /* Is this param already listed in root->curOuterParams? */
2349                 foreach(lc, root->curOuterParams)
2350                 {
2351                         nlp = (NestLoopParam *) lfirst(lc);
2352                         if (nlp->paramno == param->paramid)
2353                         {
2354                                 Assert(equal(var, nlp->paramval));
2355                                 /* Present, so we can just return the Param */
2356                                 return (Node *) param;
2357                         }
2358                 }
2359                 /* No, so add it */
2360                 nlp = makeNode(NestLoopParam);
2361                 nlp->paramno = param->paramid;
2362                 nlp->paramval = var;
2363                 root->curOuterParams = lappend(root->curOuterParams, nlp);
2364                 /* And return the replacement Param */
2365                 return (Node *) param;
2366         }
2367         return expression_tree_mutator(node,
2368                                                                    replace_nestloop_params_mutator,
2369                                                                    (void *) root);
2370 }
2371
2372 /*
2373  * fix_indexqual_references
2374  *        Adjust indexqual clauses to the form the executor's indexqual
2375  *        machinery needs.
2376  *
2377  * We have four tasks here:
2378  *      * Remove RestrictInfo nodes from the input clauses.
2379  *      * Replace any outer-relation Var nodes with nestloop Params.
2380  *        (XXX eventually, that responsibility should go elsewhere?)
2381  *      * Index keys must be represented by Var nodes with varattno set to the
2382  *        index's attribute number, not the attribute number in the original rel.
2383  *      * If the index key is on the right, commute the clause to put it on the
2384  *        left.
2385  *
2386  * The result is a modified copy of the indexquals list --- the
2387  * original is not changed.  Note also that the copy shares no substructure
2388  * with the original; this is needed in case there is a subplan in it (we need
2389  * two separate copies of the subplan tree, or things will go awry).
2390  */
2391 static List *
2392 fix_indexqual_references(PlannerInfo *root, IndexPath *index_path,
2393                                                  List *indexquals)
2394 {
2395         IndexOptInfo *index = index_path->indexinfo;
2396         List       *fixed_indexquals;
2397         ListCell   *l;
2398
2399         fixed_indexquals = NIL;
2400
2401         foreach(l, indexquals)
2402         {
2403                 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
2404                 Node       *clause;
2405
2406                 Assert(IsA(rinfo, RestrictInfo));
2407
2408                 /*
2409                  * Replace any outer-relation variables with nestloop params.
2410                  *
2411                  * This also makes a copy of the clause, so it's safe to modify it
2412                  * in-place below.
2413                  */
2414                 clause = replace_nestloop_params(root, (Node *) rinfo->clause);
2415
2416                 if (IsA(clause, OpExpr))
2417                 {
2418                         OpExpr     *op = (OpExpr *) clause;
2419
2420                         if (list_length(op->args) != 2)
2421                                 elog(ERROR, "indexqual clause is not binary opclause");
2422
2423                         /*
2424                          * Check to see if the indexkey is on the right; if so, commute
2425                          * the clause. The indexkey should be the side that refers to
2426                          * (only) the base relation.
2427                          */
2428                         if (!bms_equal(rinfo->left_relids, index->rel->relids))
2429                                 CommuteOpExpr(op);
2430
2431                         /*
2432                          * Now, determine which index attribute this is and change the
2433                          * indexkey operand as needed.
2434                          */
2435                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
2436                                                                                                            index);
2437                 }
2438                 else if (IsA(clause, RowCompareExpr))
2439                 {
2440                         RowCompareExpr *rc = (RowCompareExpr *) clause;
2441                         ListCell   *lc;
2442
2443                         /*
2444                          * Check to see if the indexkey is on the right; if so, commute
2445                          * the clause. The indexkey should be the side that refers to
2446                          * (only) the base relation.
2447                          */
2448                         if (!bms_overlap(pull_varnos(linitial(rc->largs)),
2449                                                          index->rel->relids))
2450                                 CommuteRowCompareExpr(rc);
2451
2452                         /*
2453                          * For each column in the row comparison, determine which index
2454                          * attribute this is and change the indexkey operand as needed.
2455                          */
2456                         foreach(lc, rc->largs)
2457                         {
2458                                 lfirst(lc) = fix_indexqual_operand(lfirst(lc),
2459                                                                                                    index);
2460                         }
2461                 }
2462                 else if (IsA(clause, ScalarArrayOpExpr))
2463                 {
2464                         ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
2465
2466                         /* Never need to commute... */
2467
2468                         /*
2469                          * Determine which index attribute this is and change the indexkey
2470                          * operand as needed.
2471                          */
2472                         linitial(saop->args) = fix_indexqual_operand(linitial(saop->args),
2473                                                                                                                  index);
2474                 }
2475                 else if (IsA(clause, NullTest))
2476                 {
2477                         NullTest   *nt = (NullTest *) clause;
2478
2479                         nt->arg = (Expr *) fix_indexqual_operand((Node *) nt->arg,
2480                                                                                                          index);
2481                 }
2482                 else
2483                         elog(ERROR, "unsupported indexqual type: %d",
2484                                  (int) nodeTag(clause));
2485
2486                 fixed_indexquals = lappend(fixed_indexquals, clause);
2487         }
2488
2489         return fixed_indexquals;
2490 }
2491
2492 /*
2493  * fix_indexorderby_references
2494  *        Adjust indexorderby clauses to the form the executor's index
2495  *        machinery needs.
2496  *
2497  * This is a simplified version of fix_indexqual_references.  The input does
2498  * not have RestrictInfo nodes, and we assume that indxqual.c already
2499  * commuted the clauses to put the index keys on the left.      Also, we don't
2500  * bother to support any cases except simple OpExprs, since nothing else
2501  * is allowed for ordering operators.
2502  */
2503 static List *
2504 fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path,
2505                                                         List *indexorderbys)
2506 {
2507         IndexOptInfo *index = index_path->indexinfo;
2508         List       *fixed_indexorderbys;
2509         ListCell   *l;
2510
2511         fixed_indexorderbys = NIL;
2512
2513         foreach(l, indexorderbys)
2514         {
2515                 Node       *clause = (Node *) lfirst(l);
2516
2517                 /*
2518                  * Replace any outer-relation variables with nestloop params.
2519                  *
2520                  * This also makes a copy of the clause, so it's safe to modify it
2521                  * in-place below.
2522                  */
2523                 clause = replace_nestloop_params(root, clause);
2524
2525                 if (IsA(clause, OpExpr))
2526                 {
2527                         OpExpr     *op = (OpExpr *) clause;
2528
2529                         if (list_length(op->args) != 2)
2530                                 elog(ERROR, "indexorderby clause is not binary opclause");
2531
2532                         /*
2533                          * Now, determine which index attribute this is and change the
2534                          * indexkey operand as needed.
2535                          */
2536                         linitial(op->args) = fix_indexqual_operand(linitial(op->args),
2537                                                                                                            index);
2538                 }
2539                 else
2540                         elog(ERROR, "unsupported indexorderby type: %d",
2541                                  (int) nodeTag(clause));
2542
2543                 fixed_indexorderbys = lappend(fixed_indexorderbys, clause);
2544         }
2545
2546         return fixed_indexorderbys;
2547 }
2548
2549 /*
2550  * fix_indexqual_operand
2551  *        Convert an indexqual expression to a Var referencing the index column.
2552  */
2553 static Node *
2554 fix_indexqual_operand(Node *node, IndexOptInfo *index)
2555 {
2556         /*
2557          * We represent index keys by Var nodes having the varno of the base table
2558          * but varattno equal to the index's attribute number (index column
2559          * position).  This is a bit hokey ... would be cleaner to use a
2560          * special-purpose node type that could not be mistaken for a regular Var.
2561          * But it will do for now.
2562          */
2563         Var                *result;
2564         int                     pos;
2565         ListCell   *indexpr_item;
2566
2567         /*
2568          * Remove any binary-compatible relabeling of the indexkey
2569          */
2570         if (IsA(node, RelabelType))
2571                 node = (Node *) ((RelabelType *) node)->arg;
2572
2573         if (IsA(node, Var) &&
2574                 ((Var *) node)->varno == index->rel->relid)
2575         {
2576                 /* Try to match against simple index columns */
2577                 int                     varatt = ((Var *) node)->varattno;
2578
2579                 if (varatt != 0)
2580                 {
2581                         for (pos = 0; pos < index->ncolumns; pos++)
2582                         {
2583                                 if (index->indexkeys[pos] == varatt)
2584                                 {
2585                                         result = (Var *) copyObject(node);
2586                                         result->varattno = pos + 1;
2587                                         return (Node *) result;
2588                                 }
2589                         }
2590                 }
2591         }
2592
2593         /* Try to match against index expressions */
2594         indexpr_item = list_head(index->indexprs);
2595         for (pos = 0; pos < index->ncolumns; pos++)
2596         {
2597                 if (index->indexkeys[pos] == 0)
2598                 {
2599                         Node       *indexkey;
2600
2601                         if (indexpr_item == NULL)
2602                                 elog(ERROR, "too few entries in indexprs list");
2603                         indexkey = (Node *) lfirst(indexpr_item);
2604                         if (indexkey && IsA(indexkey, RelabelType))
2605                                 indexkey = (Node *) ((RelabelType *) indexkey)->arg;
2606                         if (equal(node, indexkey))
2607                         {
2608                                 /* Found a match */
2609                                 result = makeVar(index->rel->relid, pos + 1,
2610                                                                  exprType(lfirst(indexpr_item)), -1,
2611                                                                  exprCollation(lfirst(indexpr_item)),
2612                                                                  0);
2613                                 return (Node *) result;
2614                         }
2615                         indexpr_item = lnext(indexpr_item);
2616                 }
2617         }
2618
2619         /* Ooops... */
2620         elog(ERROR, "node is not an index attribute");
2621         return NULL;                            /* keep compiler quiet */
2622 }
2623
2624 /*
2625  * get_switched_clauses
2626  *        Given a list of merge or hash joinclauses (as RestrictInfo nodes),
2627  *        extract the bare clauses, and rearrange the elements within the
2628  *        clauses, if needed, so the outer join variable is on the left and
2629  *        the inner is on the right.  The original clause data structure is not
2630  *        touched; a modified list is returned.  We do, however, set the transient
2631  *        outer_is_left field in each RestrictInfo to show which side was which.
2632  */
2633 static List *
2634 get_switched_clauses(List *clauses, Relids outerrelids)
2635 {
2636         List       *t_list = NIL;
2637         ListCell   *l;
2638
2639         foreach(l, clauses)
2640         {
2641                 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
2642                 OpExpr     *clause = (OpExpr *) restrictinfo->clause;
2643
2644                 Assert(is_opclause(clause));
2645                 if (bms_is_subset(restrictinfo->right_relids, outerrelids))
2646                 {
2647                         /*
2648                          * Duplicate just enough of the structure to allow commuting the
2649                          * clause without changing the original list.  Could use
2650                          * copyObject, but a complete deep copy is overkill.
2651                          */
2652                         OpExpr     *temp = makeNode(OpExpr);
2653
2654                         temp->opno = clause->opno;
2655                         temp->opfuncid = InvalidOid;
2656                         temp->opresulttype = clause->opresulttype;
2657                         temp->opretset = clause->opretset;
2658                         temp->opcollid = clause->opcollid;
2659                         temp->inputcollid = clause->inputcollid;
2660                         temp->args = list_copy(clause->args);
2661                         temp->location = clause->location;
2662                         /* Commute it --- note this modifies the temp node in-place. */
2663                         CommuteOpExpr(temp);
2664                         t_list = lappend(t_list, temp);
2665                         restrictinfo->outer_is_left = false;
2666                 }
2667                 else
2668                 {
2669                         Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
2670                         t_list = lappend(t_list, clause);
2671                         restrictinfo->outer_is_left = true;
2672                 }
2673         }
2674         return t_list;
2675 }
2676
2677 /*
2678  * order_qual_clauses
2679  *              Given a list of qual clauses that will all be evaluated at the same
2680  *              plan node, sort the list into the order we want to check the quals
2681  *              in at runtime.
2682  *
2683  * Ideally the order should be driven by a combination of execution cost and
2684  * selectivity, but it's not immediately clear how to account for both,
2685  * and given the uncertainty of the estimates the reliability of the decisions
2686  * would be doubtful anyway.  So we just order by estimated per-tuple cost,
2687  * being careful not to change the order when (as is often the case) the
2688  * estimates are identical.
2689  *
2690  * Although this will work on either bare clauses or RestrictInfos, it's
2691  * much faster to apply it to RestrictInfos, since it can re-use cost
2692  * information that is cached in RestrictInfos.
2693  *
2694  * Note: some callers pass lists that contain entries that will later be
2695  * removed; this is the easiest way to let this routine see RestrictInfos
2696  * instead of bare clauses.  It's OK because we only sort by cost, but
2697  * a cost/selectivity combination would likely do the wrong thing.
2698  */
2699 static List *
2700 order_qual_clauses(PlannerInfo *root, List *clauses)
2701 {
2702         typedef struct
2703         {
2704                 Node       *clause;
2705                 Cost            cost;
2706         } QualItem;
2707         int                     nitems = list_length(clauses);
2708         QualItem   *items;
2709         ListCell   *lc;
2710         int                     i;
2711         List       *result;
2712
2713         /* No need to work hard for 0 or 1 clause */
2714         if (nitems <= 1)
2715                 return clauses;
2716
2717         /*
2718          * Collect the items and costs into an array.  This is to avoid repeated
2719          * cost_qual_eval work if the inputs aren't RestrictInfos.
2720          */
2721         items = (QualItem *) palloc(nitems * sizeof(QualItem));
2722         i = 0;
2723         foreach(lc, clauses)
2724         {
2725                 Node       *clause = (Node *) lfirst(lc);
2726                 QualCost        qcost;
2727
2728                 cost_qual_eval_node(&qcost, clause, root);
2729                 items[i].clause = clause;
2730                 items[i].cost = qcost.per_tuple;
2731                 i++;
2732         }
2733
2734         /*
2735          * Sort.  We don't use qsort() because it's not guaranteed stable for
2736          * equal keys.  The expected number of entries is small enough that a
2737          * simple insertion sort should be good enough.
2738          */
2739         for (i = 1; i < nitems; i++)
2740         {
2741                 QualItem        newitem = items[i];
2742                 int                     j;
2743
2744                 /* insert newitem into the already-sorted subarray */
2745                 for (j = i; j > 0; j--)
2746                 {
2747                         if (newitem.cost >= items[j - 1].cost)
2748                                 break;
2749                         items[j] = items[j - 1];
2750                 }
2751                 items[j] = newitem;
2752         }
2753
2754         /* Convert back to a list */
2755         result = NIL;
2756         for (i = 0; i < nitems; i++)
2757                 result = lappend(result, items[i].clause);
2758
2759         return result;
2760 }
2761
2762 /*
2763  * Copy cost and size info from a Path node to the Plan node created from it.
2764  * The executor usually won't use this info, but it's needed by EXPLAIN.
2765  */
2766 static void
2767 copy_path_costsize(Plan *dest, Path *src)
2768 {
2769         if (src)
2770         {
2771                 dest->startup_cost = src->startup_cost;
2772                 dest->total_cost = src->total_cost;
2773                 dest->plan_rows = src->parent->rows;
2774                 dest->plan_width = src->parent->width;
2775         }
2776         else
2777         {
2778                 dest->startup_cost = 0;
2779                 dest->total_cost = 0;
2780                 dest->plan_rows = 0;
2781                 dest->plan_width = 0;
2782         }
2783 }
2784
2785 /*
2786  * Copy cost and size info from a lower plan node to an inserted node.
2787  * (Most callers alter the info after copying it.)
2788  */
2789 static void
2790 copy_plan_costsize(Plan *dest, Plan *src)
2791 {
2792         if (src)
2793         {
2794                 dest->startup_cost = src->startup_cost;
2795                 dest->total_cost = src->total_cost;
2796                 dest->plan_rows = src->plan_rows;
2797                 dest->plan_width = src->plan_width;
2798         }
2799         else
2800         {
2801                 dest->startup_cost = 0;
2802                 dest->total_cost = 0;
2803                 dest->plan_rows = 0;
2804                 dest->plan_width = 0;
2805         }
2806 }
2807
2808
2809 /*****************************************************************************
2810  *
2811  *      PLAN NODE BUILDING ROUTINES
2812  *
2813  * Some of these are exported because they are called to build plan nodes
2814  * in contexts where we're not deriving the plan node from a path node.
2815  *
2816  *****************************************************************************/
2817
2818 static SeqScan *
2819 make_seqscan(List *qptlist,
2820                          List *qpqual,
2821                          Index scanrelid)
2822 {
2823         SeqScan    *node = makeNode(SeqScan);
2824         Plan       *plan = &node->plan;
2825
2826         /* cost should be inserted by caller */
2827         plan->targetlist = qptlist;
2828         plan->qual = qpqual;
2829         plan->lefttree = NULL;
2830         plan->righttree = NULL;
2831         node->scanrelid = scanrelid;
2832
2833         return node;
2834 }
2835
2836 static IndexScan *
2837 make_indexscan(List *qptlist,
2838                            List *qpqual,
2839                            Index scanrelid,
2840                            Oid indexid,
2841                            List *indexqual,
2842                            List *indexqualorig,
2843                            List *indexorderby,
2844                            List *indexorderbyorig,
2845                            ScanDirection indexscandir,
2846                            bool indexonly)
2847 {
2848         IndexScan  *node = makeNode(IndexScan);
2849         Plan       *plan = &node->scan.plan;
2850
2851         /* cost should be inserted by caller */
2852         plan->targetlist = qptlist;
2853         plan->qual = qpqual;
2854         plan->lefttree = NULL;
2855         plan->righttree = NULL;
2856         node->scan.scanrelid = scanrelid;
2857         node->indexid = indexid;
2858         node->indexqual = indexqual;
2859         node->indexqualorig = indexqualorig;
2860         node->indexorderby = indexorderby;
2861         node->indexorderbyorig = indexorderbyorig;
2862         node->indexorderdir = indexscandir;
2863         node->indexonly = indexonly;
2864
2865         return node;
2866 }
2867
2868 static BitmapIndexScan *
2869 make_bitmap_indexscan(Index scanrelid,
2870                                           Oid indexid,
2871                                           List *indexqual,
2872                                           List *indexqualorig)
2873 {
2874         BitmapIndexScan *node = makeNode(BitmapIndexScan);
2875         Plan       *plan = &node->scan.plan;
2876
2877         /* cost should be inserted by caller */
2878         plan->targetlist = NIL;         /* not used */
2879         plan->qual = NIL;                       /* not used */
2880         plan->lefttree = NULL;
2881         plan->righttree = NULL;
2882         node->scan.scanrelid = scanrelid;
2883         node->indexid = indexid;
2884         node->indexqual = indexqual;
2885         node->indexqualorig = indexqualorig;
2886
2887         return node;
2888 }
2889
2890 static BitmapHeapScan *
2891 make_bitmap_heapscan(List *qptlist,
2892                                          List *qpqual,
2893                                          Plan *lefttree,
2894                                          List *bitmapqualorig,
2895                                          Index scanrelid)
2896 {
2897         BitmapHeapScan *node = makeNode(BitmapHeapScan);
2898         Plan       *plan = &node->scan.plan;
2899
2900         /* cost should be inserted by caller */
2901         plan->targetlist = qptlist;
2902         plan->qual = qpqual;
2903         plan->lefttree = lefttree;
2904         plan->righttree = NULL;
2905         node->scan.scanrelid = scanrelid;
2906         node->bitmapqualorig = bitmapqualorig;
2907
2908         return node;
2909 }
2910
2911 static TidScan *
2912 make_tidscan(List *qptlist,
2913                          List *qpqual,
2914                          Index scanrelid,
2915                          List *tidquals)
2916 {
2917         TidScan    *node = makeNode(TidScan);
2918         Plan       *plan = &node->scan.plan;
2919
2920         /* cost should be inserted by caller */
2921         plan->targetlist = qptlist;
2922         plan->qual = qpqual;
2923         plan->lefttree = NULL;
2924         plan->righttree = NULL;
2925         node->scan.scanrelid = scanrelid;
2926         node->tidquals = tidquals;
2927
2928         return node;
2929 }
2930
2931 SubqueryScan *
2932 make_subqueryscan(List *qptlist,
2933                                   List *qpqual,
2934                                   Index scanrelid,
2935                                   Plan *subplan)
2936 {
2937         SubqueryScan *node = makeNode(SubqueryScan);
2938         Plan       *plan = &node->scan.plan;
2939
2940         /*
2941          * Cost is figured here for the convenience of prepunion.c.  Note this is
2942          * only correct for the case where qpqual is empty; otherwise caller
2943          * should overwrite cost with a better estimate.
2944          */
2945         copy_plan_costsize(plan, subplan);
2946         plan->total_cost += cpu_tuple_cost * subplan->plan_rows;
2947
2948         plan->targetlist = qptlist;
2949         plan->qual = qpqual;
2950         plan->lefttree = NULL;
2951         plan->righttree = NULL;
2952         node->scan.scanrelid = scanrelid;
2953         node->subplan = subplan;
2954
2955         return node;
2956 }
2957
2958 static FunctionScan *
2959 make_functionscan(List *qptlist,
2960                                   List *qpqual,
2961                                   Index scanrelid,
2962                                   Node *funcexpr,
2963                                   List *funccolnames,
2964                                   List *funccoltypes,
2965                                   List *funccoltypmods,
2966                                   List *funccolcollations)
2967 {
2968         FunctionScan *node = makeNode(FunctionScan);
2969         Plan       *plan = &node->scan.plan;
2970
2971         /* cost should be inserted by caller */
2972         plan->targetlist = qptlist;
2973         plan->qual = qpqual;
2974         plan->lefttree = NULL;
2975         plan->righttree = NULL;
2976         node->scan.scanrelid = scanrelid;
2977         node->funcexpr = funcexpr;
2978         node->funccolnames = funccolnames;
2979         node->funccoltypes = funccoltypes;
2980         node->funccoltypmods = funccoltypmods;
2981         node->funccolcollations = funccolcollations;
2982
2983         return node;
2984 }
2985
2986 static ValuesScan *
2987 make_valuesscan(List *qptlist,
2988                                 List *qpqual,
2989                                 Index scanrelid,
2990                                 List *values_lists)
2991 {
2992         ValuesScan *node = makeNode(ValuesScan);
2993         Plan       *plan = &node->scan.plan;
2994
2995         /* cost should be inserted by caller */
2996         plan->targetlist = qptlist;
2997         plan->qual = qpqual;
2998         plan->lefttree = NULL;
2999         plan->righttree = NULL;
3000         node->scan.scanrelid = scanrelid;
3001         node->values_lists = values_lists;
3002
3003         return node;
3004 }
3005
3006 static CteScan *
3007 make_ctescan(List *qptlist,
3008                          List *qpqual,
3009                          Index scanrelid,
3010                          int ctePlanId,
3011                          int cteParam)
3012 {
3013         CteScan    *node = makeNode(CteScan);
3014         Plan       *plan = &node->scan.plan;
3015
3016         /* cost should be inserted by caller */
3017         plan->targetlist = qptlist;
3018         plan->qual = qpqual;
3019         plan->lefttree = NULL;
3020         plan->righttree = NULL;
3021         node->scan.scanrelid = scanrelid;
3022         node->ctePlanId = ctePlanId;
3023         node->cteParam = cteParam;
3024
3025         return node;
3026 }
3027
3028 static WorkTableScan *
3029 make_worktablescan(List *qptlist,
3030                                    List *qpqual,
3031                                    Index scanrelid,
3032                                    int wtParam)
3033 {
3034         WorkTableScan *node = makeNode(WorkTableScan);
3035         Plan       *plan = &node->scan.plan;
3036
3037         /* cost should be inserted by caller */
3038         plan->targetlist = qptlist;
3039         plan->qual = qpqual;
3040         plan->lefttree = NULL;
3041         plan->righttree = NULL;
3042         node->scan.scanrelid = scanrelid;
3043         node->wtParam = wtParam;
3044
3045         return node;
3046 }
3047
3048 static ForeignScan *
3049 make_foreignscan(List *qptlist,
3050                                  List *qpqual,
3051                                  Index scanrelid,
3052                                  bool fsSystemCol,
3053                                  FdwPlan *fdwplan)
3054 {
3055         ForeignScan *node = makeNode(ForeignScan);
3056         Plan       *plan = &node->scan.plan;
3057
3058         /* cost should be inserted by caller */
3059         plan->targetlist = qptlist;
3060         plan->qual = qpqual;
3061         plan->lefttree = NULL;
3062         plan->righttree = NULL;
3063         node->scan.scanrelid = scanrelid;
3064         node->fsSystemCol = fsSystemCol;
3065         node->fdwplan = fdwplan;
3066
3067         return node;
3068 }
3069
3070 Append *
3071 make_append(List *appendplans, List *tlist)
3072 {
3073         Append     *node = makeNode(Append);
3074         Plan       *plan = &node->plan;
3075         double          total_size;
3076         ListCell   *subnode;
3077
3078         /*
3079          * Compute cost as sum of subplan costs.  We charge nothing extra for the
3080          * Append itself, which perhaps is too optimistic, but since it doesn't do
3081          * any selection or projection, it is a pretty cheap node.
3082          *
3083          * If you change this, see also create_append_path().  Also, the size
3084          * calculations should match set_append_rel_pathlist().  It'd be better
3085          * not to duplicate all this logic, but some callers of this function
3086          * aren't working from an appendrel or AppendPath, so there's noplace to
3087          * copy the data from.
3088          */
3089         plan->startup_cost = 0;
3090         plan->total_cost = 0;
3091         plan->plan_rows = 0;
3092         total_size = 0;
3093         foreach(subnode, appendplans)
3094         {
3095                 Plan       *subplan = (Plan *) lfirst(subnode);
3096
3097                 if (subnode == list_head(appendplans))  /* first node? */
3098                         plan->startup_cost = subplan->startup_cost;
3099                 plan->total_cost += subplan->total_cost;
3100                 plan->plan_rows += subplan->plan_rows;
3101                 total_size += subplan->plan_width * subplan->plan_rows;
3102         }
3103         if (plan->plan_rows > 0)
3104                 plan->plan_width = rint(total_size / plan->plan_rows);
3105         else
3106                 plan->plan_width = 0;
3107
3108         plan->targetlist = tlist;
3109         plan->qual = NIL;
3110         plan->lefttree = NULL;
3111         plan->righttree = NULL;
3112         node->appendplans = appendplans;
3113
3114         return node;
3115 }
3116
3117 RecursiveUnion *
3118 make_recursive_union(List *tlist,
3119                                          Plan *lefttree,
3120                                          Plan *righttree,
3121                                          int wtParam,
3122                                          List *distinctList,
3123                                          long numGroups)
3124 {
3125         RecursiveUnion *node = makeNode(RecursiveUnion);
3126         Plan       *plan = &node->plan;
3127         int                     numCols = list_length(distinctList);
3128
3129         cost_recursive_union(plan, lefttree, righttree);
3130
3131         plan->targetlist = tlist;
3132         plan->qual = NIL;
3133         plan->lefttree = lefttree;
3134         plan->righttree = righttree;
3135         node->wtParam = wtParam;
3136
3137         /*
3138          * convert SortGroupClause list into arrays of attr indexes and equality
3139          * operators, as wanted by executor
3140          */
3141         node->numCols = numCols;
3142         if (numCols > 0)
3143         {
3144                 int                     keyno = 0;
3145                 AttrNumber *dupColIdx;
3146                 Oid                *dupOperators;
3147                 ListCell   *slitem;
3148
3149                 dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
3150                 dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
3151
3152                 foreach(slitem, distinctList)
3153                 {
3154                         SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
3155                         TargetEntry *tle = get_sortgroupclause_tle(sortcl,
3156                                                                                                            plan->targetlist);
3157
3158                         dupColIdx[keyno] = tle->resno;
3159                         dupOperators[keyno] = sortcl->eqop;
3160                         Assert(OidIsValid(dupOperators[keyno]));
3161                         keyno++;
3162                 }
3163                 node->dupColIdx = dupColIdx;
3164                 node->dupOperators = dupOperators;
3165         }
3166         node->numGroups = numGroups;
3167
3168         return node;
3169 }
3170
3171 static BitmapAnd *
3172 make_bitmap_and(List *bitmapplans)
3173 {
3174         BitmapAnd  *node = makeNode(BitmapAnd);
3175         Plan       *plan = &node->plan;
3176
3177         /* cost should be inserted by caller */
3178         plan->targetlist = NIL;
3179         plan->qual = NIL;
3180         plan->lefttree = NULL;
3181         plan->righttree = NULL;
3182         node->bitmapplans = bitmapplans;
3183
3184         return node;
3185 }
3186
3187 static BitmapOr *
3188 make_bitmap_or(List *bitmapplans)
3189 {
3190         BitmapOr   *node = makeNode(BitmapOr);
3191         Plan       *plan = &node->plan;
3192
3193         /* cost should be inserted by caller */
3194         plan->targetlist = NIL;
3195         plan->qual = NIL;
3196         plan->lefttree = NULL;
3197         plan->righttree = NULL;
3198         node->bitmapplans = bitmapplans;
3199
3200         return node;
3201 }
3202
3203 static NestLoop *
3204 make_nestloop(List *tlist,
3205                           List *joinclauses,
3206                           List *otherclauses,
3207                           List *nestParams,
3208                           Plan *lefttree,
3209                           Plan *righttree,
3210                           JoinType jointype)
3211 {
3212         NestLoop   *node = makeNode(NestLoop);
3213         Plan       *plan = &node->join.plan;
3214
3215         /* cost should be inserted by caller */
3216         plan->targetlist = tlist;
3217         plan->qual = otherclauses;
3218         plan->lefttree = lefttree;
3219         plan->righttree = righttree;
3220         node->join.jointype = jointype;
3221         node->join.joinqual = joinclauses;
3222         node->nestParams = nestParams;
3223
3224         return node;
3225 }
3226
3227 static HashJoin *
3228 make_hashjoin(List *tlist,
3229                           List *joinclauses,
3230                           List *otherclauses,
3231                           List *hashclauses,
3232                           Plan *lefttree,
3233                           Plan *righttree,
3234                           JoinType jointype)
3235 {
3236         HashJoin   *node = makeNode(HashJoin);
3237         Plan       *plan = &node->join.plan;
3238
3239         /* cost should be inserted by caller */
3240         plan->targetlist = tlist;
3241         plan->qual = otherclauses;
3242         plan->lefttree = lefttree;
3243         plan->righttree = righttree;
3244         node->hashclauses = hashclauses;
3245         node->join.jointype = jointype;
3246         node->join.joinqual = joinclauses;
3247
3248         return node;
3249 }
3250
3251 static Hash *
3252 make_hash(Plan *lefttree,
3253                   Oid skewTable,
3254                   AttrNumber skewColumn,
3255                   bool skewInherit,
3256                   Oid skewColType,
3257                   int32 skewColTypmod)
3258 {
3259         Hash       *node = makeNode(Hash);
3260         Plan       *plan = &node->plan;
3261
3262         copy_plan_costsize(plan, lefttree);
3263
3264         /*
3265          * For plausibility, make startup & total costs equal total cost of input
3266          * plan; this only affects EXPLAIN display not decisions.
3267          */
3268         plan->startup_cost = plan->total_cost;
3269         plan->targetlist = lefttree->targetlist;
3270         plan->qual = NIL;
3271         plan->lefttree = lefttree;
3272         plan->righttree = NULL;
3273
3274         node->skewTable = skewTable;
3275         node->skewColumn = skewColumn;
3276         node->skewInherit = skewInherit;
3277         node->skewColType = skewColType;
3278         node->skewColTypmod = skewColTypmod;
3279
3280         return node;
3281 }
3282
3283 static MergeJoin *
3284 make_mergejoin(List *tlist,
3285                            List *joinclauses,
3286                            List *otherclauses,
3287                            List *mergeclauses,
3288                            Oid *mergefamilies,
3289                            Oid *mergecollations,
3290                            int *mergestrategies,
3291                            bool *mergenullsfirst,
3292                            Plan *lefttree,
3293                            Plan *righttree,
3294                            JoinType jointype)
3295 {
3296         MergeJoin  *node = makeNode(MergeJoin);
3297         Plan       *plan = &node->join.plan;
3298
3299         /* cost should be inserted by caller */
3300         plan->targetlist = tlist;
3301         plan->qual = otherclauses;
3302         plan->lefttree = lefttree;
3303         plan->righttree = righttree;
3304         node->mergeclauses = mergeclauses;
3305         node->mergeFamilies = mergefamilies;
3306         node->mergeCollations = mergecollations;
3307         node->mergeStrategies = mergestrategies;
3308         node->mergeNullsFirst = mergenullsfirst;
3309         node->join.jointype = jointype;
3310         node->join.joinqual = joinclauses;
3311
3312         return node;
3313 }
3314
3315 /*
3316  * make_sort --- basic routine to build a Sort plan node
3317  *
3318  * Caller must have built the sortColIdx, sortOperators, collations, and
3319  * nullsFirst arrays already.
3320  * limit_tuples is as for cost_sort (in particular, pass -1 if no limit)
3321  */
3322 static Sort *
3323 make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
3324                   AttrNumber *sortColIdx, Oid *sortOperators,
3325                   Oid *collations, bool *nullsFirst,
3326                   double limit_tuples)
3327 {
3328         Sort       *node = makeNode(Sort);
3329         Plan       *plan = &node->plan;
3330         Path            sort_path;              /* dummy for result of cost_sort */
3331
3332         copy_plan_costsize(plan, lefttree); /* only care about copying size */
3333         cost_sort(&sort_path, root, NIL,
3334                           lefttree->total_cost,
3335                           lefttree->plan_rows,
3336                           lefttree->plan_width,
3337                           0.0,
3338                           work_mem,
3339                           limit_tuples);
3340         plan->startup_cost = sort_path.startup_cost;
3341         plan->total_cost = sort_path.total_cost;
3342         plan->targetlist = lefttree->targetlist;
3343         plan->qual = NIL;
3344         plan->lefttree = lefttree;
3345         plan->righttree = NULL;
3346         node->numCols = numCols;
3347         node->sortColIdx = sortColIdx;
3348         node->sortOperators = sortOperators;
3349         node->collations = collations;
3350         node->nullsFirst = nullsFirst;
3351
3352         return node;
3353 }
3354
3355 /*
3356  * add_sort_column --- utility subroutine for building sort info arrays
3357  *
3358  * We need this routine because the same column might be selected more than
3359  * once as a sort key column; if so, the extra mentions are redundant.
3360  *
3361  * Caller is assumed to have allocated the arrays large enough for the
3362  * max possible number of columns.      Return value is the new column count.
3363  */
3364 static int
3365 add_sort_column(AttrNumber colIdx, Oid sortOp, Oid coll, bool nulls_first,
3366                                 int numCols, AttrNumber *sortColIdx,
3367                                 Oid *sortOperators, Oid *collations, bool *nullsFirst)
3368 {
3369         int                     i;
3370
3371         Assert(OidIsValid(sortOp));
3372
3373         for (i = 0; i < numCols; i++)
3374         {
3375                 /*
3376                  * Note: we check sortOp because it's conceivable that "ORDER BY foo
3377                  * USING <, foo USING <<<" is not redundant, if <<< distinguishes
3378                  * values that < considers equal.  We need not check nulls_first
3379                  * however because a lower-order column with the same sortop but
3380                  * opposite nulls direction is redundant.
3381                  *
3382                  * We could probably consider sort keys with the same sortop and
3383                  * different collations to be redundant too, but for the moment treat
3384                  * them as not redundant.  This will be needed if we ever support
3385                  * collations with different notions of equality.
3386                  */
3387                 if (sortColIdx[i] == colIdx &&
3388                         sortOperators[numCols] == sortOp &&
3389                         collations[numCols] == coll)
3390                 {
3391                         /* Already sorting by this col, so extra sort key is useless */
3392                         return numCols;
3393                 }
3394         }
3395
3396         /* Add the column */
3397         sortColIdx[numCols] = colIdx;
3398         sortOperators[numCols] = sortOp;
3399         collations[numCols] = coll;
3400         nullsFirst[numCols] = nulls_first;
3401         return numCols + 1;
3402 }
3403
3404 /*
3405  * prepare_sort_from_pathkeys
3406  *        Prepare to sort according to given pathkeys
3407  *
3408  * This is used to set up for both Sort and MergeAppend nodes.  It calculates
3409  * the executor's representation of the sort key information, and adjusts the
3410  * plan targetlist if needed to add resjunk sort columns.
3411  *
3412  * Input parameters:
3413  *        'lefttree' is the node which yields input tuples
3414  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
3415  *        'adjust_tlist_in_place' is TRUE if lefttree must be modified in-place
3416  *
3417  * We must convert the pathkey information into arrays of sort key column
3418  * numbers, sort operator OIDs, collation OIDs, and nulls-first flags,
3419  * which is the representation the executor wants.      These are returned into
3420  * the output parameters *p_numsortkeys etc.
3421  *
3422  * If the pathkeys include expressions that aren't simple Vars, we will
3423  * usually need to add resjunk items to the input plan's targetlist to
3424  * compute these expressions, since the Sort/MergeAppend node itself won't
3425  * do any such calculations.  If the input plan type isn't one that can do
3426  * projections, this means adding a Result node just to do the projection.
3427  * However, the caller can pass adjust_tlist_in_place = TRUE to force the
3428  * lefttree tlist to be modified in-place regardless of whether the node type
3429  * can project --- we use this for fixing the tlist of MergeAppend itself.
3430  *
3431  * Returns the node which is to be the input to the Sort (either lefttree,
3432  * or a Result stacked atop lefttree).
3433  */
3434 static Plan *
3435 prepare_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
3436                                                    bool adjust_tlist_in_place,
3437                                                    int *p_numsortkeys,
3438                                                    AttrNumber **p_sortColIdx,
3439                                                    Oid **p_sortOperators,
3440                                                    Oid **p_collations,
3441                                                    bool **p_nullsFirst)
3442 {
3443         List       *tlist = lefttree->targetlist;
3444         ListCell   *i;
3445         int                     numsortkeys;
3446         AttrNumber *sortColIdx;
3447         Oid                *sortOperators;
3448         Oid                *collations;
3449         bool       *nullsFirst;
3450
3451         /*
3452          * We will need at most list_length(pathkeys) sort columns; possibly less
3453          */
3454         numsortkeys = list_length(pathkeys);
3455         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3456         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3457         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3458         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3459
3460         numsortkeys = 0;
3461
3462         foreach(i, pathkeys)
3463         {
3464                 PathKey    *pathkey = (PathKey *) lfirst(i);
3465                 EquivalenceClass *ec = pathkey->pk_eclass;
3466                 TargetEntry *tle = NULL;
3467                 Oid                     pk_datatype = InvalidOid;
3468                 Oid                     sortop;
3469                 ListCell   *j;
3470
3471                 if (ec->ec_has_volatile)
3472                 {
3473                         /*
3474                          * If the pathkey's EquivalenceClass is volatile, then it must
3475                          * have come from an ORDER BY clause, and we have to match it to
3476                          * that same targetlist entry.
3477                          */
3478                         if (ec->ec_sortref == 0)        /* can't happen */
3479                                 elog(ERROR, "volatile EquivalenceClass has no sortref");
3480                         tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
3481                         Assert(tle);
3482                         Assert(list_length(ec->ec_members) == 1);
3483                         pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
3484                 }
3485                 else
3486                 {
3487                         /*
3488                          * Otherwise, we can sort by any non-constant expression listed in
3489                          * the pathkey's EquivalenceClass.  For now, we take the first one
3490                          * that corresponds to an available item in the tlist.  If there
3491                          * isn't any, use the first one that is an expression in the
3492                          * input's vars.  (The non-const restriction only matters if the
3493                          * EC is below_outer_join; but if it isn't, it won't contain
3494                          * consts anyway, else we'd have discarded the pathkey as
3495                          * redundant.)
3496                          *
3497                          * XXX if we have a choice, is there any way of figuring out which
3498                          * might be cheapest to execute?  (For example, int4lt is likely
3499                          * much cheaper to execute than numericlt, but both might appear
3500                          * in the same equivalence class...)  Not clear that we ever will
3501                          * have an interesting choice in practice, so it may not matter.
3502                          */
3503                         foreach(j, ec->ec_members)
3504                         {
3505                                 EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
3506
3507                                 /*
3508                                  * We shouldn't be trying to sort by an equivalence class that
3509                                  * contains a constant, so no need to consider such cases any
3510                                  * further.
3511                                  */
3512                                 if (em->em_is_const)
3513                                         continue;
3514
3515                                 tle = tlist_member((Node *) em->em_expr, tlist);
3516                                 if (tle)
3517                                 {
3518                                         pk_datatype = em->em_datatype;
3519                                         break;          /* found expr already in tlist */
3520                                 }
3521
3522                                 /*
3523                                  * We can also use it if the pathkey expression is a relabel
3524                                  * of the tlist entry, or vice versa.  This is needed for
3525                                  * binary-compatible cases (cf. make_pathkey_from_sortinfo).
3526                                  * We prefer an exact match, though, so we do the basic search
3527                                  * first.
3528                                  */
3529                                 tle = tlist_member_ignore_relabel((Node *) em->em_expr, tlist);
3530                                 if (tle)
3531                                 {
3532                                         pk_datatype = em->em_datatype;
3533                                         break;          /* found expr already in tlist */
3534                                 }
3535                         }
3536
3537                         if (!tle)
3538                         {
3539                                 /*
3540                                  * No matching tlist item; look for a computable expression.
3541                                  * Note that we treat Aggrefs as if they were variables; this
3542                                  * is necessary when attempting to sort the output from an Agg
3543                                  * node for use in a WindowFunc (since grouping_planner will
3544                                  * have treated the Aggrefs as variables, too).
3545                                  */
3546                                 Expr       *sortexpr = NULL;
3547
3548                                 foreach(j, ec->ec_members)
3549                                 {
3550                                         EquivalenceMember *em = (EquivalenceMember *) lfirst(j);
3551                                         List       *exprvars;
3552                                         ListCell   *k;
3553
3554                                         if (em->em_is_const)
3555                                                 continue;
3556                                         sortexpr = em->em_expr;
3557                                         exprvars = pull_var_clause((Node *) sortexpr,
3558                                                                                            PVC_INCLUDE_AGGREGATES,
3559                                                                                            PVC_INCLUDE_PLACEHOLDERS);
3560                                         foreach(k, exprvars)
3561                                         {
3562                                                 if (!tlist_member_ignore_relabel(lfirst(k), tlist))
3563                                                         break;
3564                                         }
3565                                         list_free(exprvars);
3566                                         if (!k)
3567                                         {
3568                                                 pk_datatype = em->em_datatype;
3569                                                 break;  /* found usable expression */
3570                                         }
3571                                 }
3572                                 if (!j)
3573                                         elog(ERROR, "could not find pathkey item to sort");
3574
3575                                 /*
3576                                  * Do we need to insert a Result node?
3577                                  */
3578                                 if (!adjust_tlist_in_place &&
3579                                         !is_projection_capable_plan(lefttree))
3580                                 {
3581                                         /* copy needed so we don't modify input's tlist below */
3582                                         tlist = copyObject(tlist);
3583                                         lefttree = (Plan *) make_result(root, tlist, NULL,
3584                                                                                                         lefttree);
3585                                 }
3586
3587                                 /* Don't bother testing is_projection_capable_plan again */
3588                                 adjust_tlist_in_place = true;
3589
3590                                 /*
3591                                  * Add resjunk entry to input's tlist
3592                                  */
3593                                 tle = makeTargetEntry(sortexpr,
3594                                                                           list_length(tlist) + 1,
3595                                                                           NULL,
3596                                                                           true);
3597                                 tlist = lappend(tlist, tle);
3598                                 lefttree->targetlist = tlist;   /* just in case NIL before */
3599                         }
3600                 }
3601
3602                 /*
3603                  * Look up the correct sort operator from the PathKey's slightly
3604                  * abstracted representation.
3605                  */
3606                 sortop = get_opfamily_member(pathkey->pk_opfamily,
3607                                                                          pk_datatype,
3608                                                                          pk_datatype,
3609                                                                          pathkey->pk_strategy);
3610                 if (!OidIsValid(sortop))        /* should not happen */
3611                         elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
3612                                  pathkey->pk_strategy, pk_datatype, pk_datatype,
3613                                  pathkey->pk_opfamily);
3614
3615                 /*
3616                  * The column might already be selected as a sort key, if the pathkeys
3617                  * contain duplicate entries.  (This can happen in scenarios where
3618                  * multiple mergejoinable clauses mention the same var, for example.)
3619                  * So enter it only once in the sort arrays.
3620                  */
3621                 numsortkeys = add_sort_column(tle->resno,
3622                                                                           sortop,
3623                                                                           pathkey->pk_eclass->ec_collation,
3624                                                                           pathkey->pk_nulls_first,
3625                                                                           numsortkeys,
3626                                                                           sortColIdx, sortOperators,
3627                                                                           collations, nullsFirst);
3628         }
3629
3630         Assert(numsortkeys > 0);
3631
3632         /* Return results */
3633         *p_numsortkeys = numsortkeys;
3634         *p_sortColIdx = sortColIdx;
3635         *p_sortOperators = sortOperators;
3636         *p_collations = collations;
3637         *p_nullsFirst = nullsFirst;
3638
3639         return lefttree;
3640 }
3641
3642 /*
3643  * make_sort_from_pathkeys
3644  *        Create sort plan to sort according to given pathkeys
3645  *
3646  *        'lefttree' is the node which yields input tuples
3647  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
3648  *        'limit_tuples' is the bound on the number of output tuples;
3649  *                              -1 if no bound
3650  */
3651 Sort *
3652 make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
3653                                                 double limit_tuples)
3654 {
3655         int                     numsortkeys;
3656         AttrNumber *sortColIdx;
3657         Oid                *sortOperators;
3658         Oid                *collations;
3659         bool       *nullsFirst;
3660
3661         /* Compute sort column info, and adjust lefttree as needed */
3662         lefttree = prepare_sort_from_pathkeys(root, lefttree, pathkeys,
3663                                                                                   false,
3664                                                                                   &numsortkeys,
3665                                                                                   &sortColIdx,
3666                                                                                   &sortOperators,
3667                                                                                   &collations,
3668                                                                                   &nullsFirst);
3669
3670         /* Now build the Sort node */
3671         return make_sort(root, lefttree, numsortkeys,
3672                                          sortColIdx, sortOperators, collations,
3673                                          nullsFirst, limit_tuples);
3674 }
3675
3676 /*
3677  * make_sort_from_sortclauses
3678  *        Create sort plan to sort according to given sortclauses
3679  *
3680  *        'sortcls' is a list of SortGroupClauses
3681  *        'lefttree' is the node which yields input tuples
3682  */
3683 Sort *
3684 make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
3685 {
3686         List       *sub_tlist = lefttree->targetlist;
3687         ListCell   *l;
3688         int                     numsortkeys;
3689         AttrNumber *sortColIdx;
3690         Oid                *sortOperators;
3691         Oid                *collations;
3692         bool       *nullsFirst;
3693
3694         /*
3695          * We will need at most list_length(sortcls) sort columns; possibly less
3696          */
3697         numsortkeys = list_length(sortcls);
3698         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3699         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3700         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3701         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3702
3703         numsortkeys = 0;
3704
3705         foreach(l, sortcls)
3706         {
3707                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
3708                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, sub_tlist);
3709
3710                 /*
3711                  * Check for the possibility of duplicate order-by clauses --- the
3712                  * parser should have removed 'em, but no point in sorting
3713                  * redundantly.
3714                  */
3715                 numsortkeys = add_sort_column(tle->resno, sortcl->sortop,
3716                                                                           exprCollation((Node *) tle->expr),
3717                                                                           sortcl->nulls_first,
3718                                                                           numsortkeys,
3719                                                                           sortColIdx, sortOperators,
3720                                                                           collations, nullsFirst);
3721         }
3722
3723         Assert(numsortkeys > 0);
3724
3725         return make_sort(root, lefttree, numsortkeys,
3726                                          sortColIdx, sortOperators, collations,
3727                                          nullsFirst, -1.0);
3728 }
3729
3730 /*
3731  * make_sort_from_groupcols
3732  *        Create sort plan to sort based on grouping columns
3733  *
3734  * 'groupcls' is the list of SortGroupClauses
3735  * 'grpColIdx' gives the column numbers to use
3736  *
3737  * This might look like it could be merged with make_sort_from_sortclauses,
3738  * but presently we *must* use the grpColIdx[] array to locate sort columns,
3739  * because the child plan's tlist is not marked with ressortgroupref info
3740  * appropriate to the grouping node.  So, only the sort ordering info
3741  * is used from the SortGroupClause entries.
3742  */
3743 Sort *
3744 make_sort_from_groupcols(PlannerInfo *root,
3745                                                  List *groupcls,
3746                                                  AttrNumber *grpColIdx,
3747                                                  Plan *lefttree)
3748 {
3749         List       *sub_tlist = lefttree->targetlist;
3750         int                     grpno = 0;
3751         ListCell   *l;
3752         int                     numsortkeys;
3753         AttrNumber *sortColIdx;
3754         Oid                *sortOperators;
3755         Oid                *collations;
3756         bool       *nullsFirst;
3757
3758         /*
3759          * We will need at most list_length(groupcls) sort columns; possibly less
3760          */
3761         numsortkeys = list_length(groupcls);
3762         sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
3763         sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
3764         collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
3765         nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
3766
3767         numsortkeys = 0;
3768
3769         foreach(l, groupcls)
3770         {
3771                 SortGroupClause *grpcl = (SortGroupClause *) lfirst(l);
3772                 TargetEntry *tle = get_tle_by_resno(sub_tlist, grpColIdx[grpno]);
3773
3774                 /*
3775                  * Check for the possibility of duplicate group-by clauses --- the
3776                  * parser should have removed 'em, but no point in sorting
3777                  * redundantly.
3778                  */
3779                 numsortkeys = add_sort_column(tle->resno, grpcl->sortop,
3780                                                                           exprCollation((Node *) tle->expr),
3781                                                                           grpcl->nulls_first,
3782                                                                           numsortkeys,
3783                                                                           sortColIdx, sortOperators,
3784                                                                           collations, nullsFirst);
3785                 grpno++;
3786         }
3787
3788         Assert(numsortkeys > 0);
3789
3790         return make_sort(root, lefttree, numsortkeys,
3791                                          sortColIdx, sortOperators, collations,
3792                                          nullsFirst, -1.0);
3793 }
3794
3795 static Material *
3796 make_material(Plan *lefttree)
3797 {
3798         Material   *node = makeNode(Material);
3799         Plan       *plan = &node->plan;
3800
3801         /* cost should be inserted by caller */
3802         plan->targetlist = lefttree->targetlist;
3803         plan->qual = NIL;
3804         plan->lefttree = lefttree;
3805         plan->righttree = NULL;
3806
3807         return node;
3808 }
3809
3810 /*
3811  * materialize_finished_plan: stick a Material node atop a completed plan
3812  *
3813  * There are a couple of places where we want to attach a Material node
3814  * after completion of subquery_planner().      This currently requires hackery.
3815  * Since subquery_planner has already run SS_finalize_plan on the subplan
3816  * tree, we have to kluge up parameter lists for the Material node.
3817  * Possibly this could be fixed by postponing SS_finalize_plan processing
3818  * until setrefs.c is run?
3819  */
3820 Plan *
3821 materialize_finished_plan(Plan *subplan)
3822 {
3823         Plan       *matplan;
3824         Path            matpath;                /* dummy for result of cost_material */
3825
3826         matplan = (Plan *) make_material(subplan);
3827
3828         /* Set cost data */
3829         cost_material(&matpath,
3830                                   subplan->startup_cost,
3831                                   subplan->total_cost,
3832                                   subplan->plan_rows,
3833                                   subplan->plan_width);
3834         matplan->startup_cost = matpath.startup_cost;
3835         matplan->total_cost = matpath.total_cost;
3836         matplan->plan_rows = subplan->plan_rows;
3837         matplan->plan_width = subplan->plan_width;
3838
3839         /* parameter kluge --- see comments above */
3840         matplan->extParam = bms_copy(subplan->extParam);
3841         matplan->allParam = bms_copy(subplan->allParam);
3842
3843         return matplan;
3844 }
3845
3846 Agg *
3847 make_agg(PlannerInfo *root, List *tlist, List *qual,
3848                  AggStrategy aggstrategy, const AggClauseCosts *aggcosts,
3849                  int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
3850                  long numGroups,
3851                  Plan *lefttree)
3852 {
3853         Agg                *node = makeNode(Agg);
3854         Plan       *plan = &node->plan;
3855         Path            agg_path;               /* dummy for result of cost_agg */
3856         QualCost        qual_cost;
3857
3858         node->aggstrategy = aggstrategy;
3859         node->numCols = numGroupCols;
3860         node->grpColIdx = grpColIdx;
3861         node->grpOperators = grpOperators;
3862         node->numGroups = numGroups;
3863
3864         copy_plan_costsize(plan, lefttree); /* only care about copying size */
3865         cost_agg(&agg_path, root,
3866                          aggstrategy, aggcosts,
3867                          numGroupCols, numGroups,
3868                          lefttree->startup_cost,
3869                          lefttree->total_cost,
3870                          lefttree->plan_rows);
3871         plan->startup_cost = agg_path.startup_cost;
3872         plan->total_cost = agg_path.total_cost;
3873
3874         /*
3875          * We will produce a single output tuple if not grouping, and a tuple per
3876          * group otherwise.
3877          */
3878         if (aggstrategy == AGG_PLAIN)
3879                 plan->plan_rows = 1;
3880         else
3881                 plan->plan_rows = numGroups;
3882
3883         /*
3884          * We also need to account for the cost of evaluation of the qual (ie, the
3885          * HAVING clause) and the tlist.  Note that cost_qual_eval doesn't charge
3886          * anything for Aggref nodes; this is okay since they are really
3887          * comparable to Vars.
3888          *
3889          * See notes in grouping_planner about why only make_agg, make_windowagg
3890          * and make_group worry about tlist eval cost.
3891          */
3892         if (qual)
3893         {
3894                 cost_qual_eval(&qual_cost, qual, root);
3895                 plan->startup_cost += qual_cost.startup;
3896                 plan->total_cost += qual_cost.startup;
3897                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3898         }
3899         cost_qual_eval(&qual_cost, tlist, root);
3900         plan->startup_cost += qual_cost.startup;
3901         plan->total_cost += qual_cost.startup;
3902         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3903
3904         plan->qual = qual;
3905         plan->targetlist = tlist;
3906         plan->lefttree = lefttree;
3907         plan->righttree = NULL;
3908
3909         return node;
3910 }
3911
3912 WindowAgg *
3913 make_windowagg(PlannerInfo *root, List *tlist,
3914                            List *windowFuncs, Index winref,
3915                            int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
3916                            int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators,
3917                            int frameOptions, Node *startOffset, Node *endOffset,
3918                            Plan *lefttree)
3919 {
3920         WindowAgg  *node = makeNode(WindowAgg);
3921         Plan       *plan = &node->plan;
3922         Path            windowagg_path; /* dummy for result of cost_windowagg */
3923         QualCost        qual_cost;
3924
3925         node->winref = winref;
3926         node->partNumCols = partNumCols;
3927         node->partColIdx = partColIdx;
3928         node->partOperators = partOperators;
3929         node->ordNumCols = ordNumCols;
3930         node->ordColIdx = ordColIdx;
3931         node->ordOperators = ordOperators;
3932         node->frameOptions = frameOptions;
3933         node->startOffset = startOffset;
3934         node->endOffset = endOffset;
3935
3936         copy_plan_costsize(plan, lefttree); /* only care about copying size */
3937         cost_windowagg(&windowagg_path, root,
3938                                    windowFuncs, partNumCols, ordNumCols,
3939                                    lefttree->startup_cost,
3940                                    lefttree->total_cost,
3941                                    lefttree->plan_rows);
3942         plan->startup_cost = windowagg_path.startup_cost;
3943         plan->total_cost = windowagg_path.total_cost;
3944
3945         /*
3946          * We also need to account for the cost of evaluation of the tlist.
3947          *
3948          * See notes in grouping_planner about why only make_agg, make_windowagg
3949          * and make_group worry about tlist eval cost.
3950          */
3951         cost_qual_eval(&qual_cost, tlist, root);
3952         plan->startup_cost += qual_cost.startup;
3953         plan->total_cost += qual_cost.startup;
3954         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
3955
3956         plan->targetlist = tlist;
3957         plan->lefttree = lefttree;
3958         plan->righttree = NULL;
3959         /* WindowAgg nodes never have a qual clause */
3960         plan->qual = NIL;
3961
3962         return node;
3963 }
3964
3965 Group *
3966 make_group(PlannerInfo *root,
3967                    List *tlist,
3968                    List *qual,
3969                    int numGroupCols,
3970                    AttrNumber *grpColIdx,
3971                    Oid *grpOperators,
3972                    double numGroups,
3973                    Plan *lefttree)
3974 {
3975         Group      *node = makeNode(Group);
3976         Plan       *plan = &node->plan;
3977         Path            group_path;             /* dummy for result of cost_group */
3978         QualCost        qual_cost;
3979
3980         node->numCols = numGroupCols;
3981         node->grpColIdx = grpColIdx;
3982         node->grpOperators = grpOperators;
3983
3984         copy_plan_costsize(plan, lefttree); /* only care about copying size */
3985         cost_group(&group_path, root,
3986                            numGroupCols, numGroups,
3987                            lefttree->startup_cost,
3988                            lefttree->total_cost,
3989                            lefttree->plan_rows);
3990         plan->startup_cost = group_path.startup_cost;
3991         plan->total_cost = group_path.total_cost;
3992
3993         /* One output tuple per estimated result group */
3994         plan->plan_rows = numGroups;
3995
3996         /*
3997          * We also need to account for the cost of evaluation of the qual (ie, the
3998          * HAVING clause) and the tlist.
3999          *
4000          * XXX this double-counts the cost of evaluation of any expressions used
4001          * for grouping, since in reality those will have been evaluated at a
4002          * lower plan level and will only be copied by the Group node. Worth
4003          * fixing?
4004          *
4005          * See notes in grouping_planner about why only make_agg, make_windowagg
4006          * and make_group worry about tlist eval cost.
4007          */
4008         if (qual)
4009         {
4010                 cost_qual_eval(&qual_cost, qual, root);
4011                 plan->startup_cost += qual_cost.startup;
4012                 plan->total_cost += qual_cost.startup;
4013                 plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4014         }
4015         cost_qual_eval(&qual_cost, tlist, root);
4016         plan->startup_cost += qual_cost.startup;
4017         plan->total_cost += qual_cost.startup;
4018         plan->total_cost += qual_cost.per_tuple * plan->plan_rows;
4019
4020         plan->qual = qual;
4021         plan->targetlist = tlist;
4022         plan->lefttree = lefttree;
4023         plan->righttree = NULL;
4024
4025         return node;
4026 }
4027
4028 /*
4029  * distinctList is a list of SortGroupClauses, identifying the targetlist items
4030  * that should be considered by the Unique filter.      The input path must
4031  * already be sorted accordingly.
4032  */
4033 Unique *
4034 make_unique(Plan *lefttree, List *distinctList)
4035 {
4036         Unique     *node = makeNode(Unique);
4037         Plan       *plan = &node->plan;
4038         int                     numCols = list_length(distinctList);
4039         int                     keyno = 0;
4040         AttrNumber *uniqColIdx;
4041         Oid                *uniqOperators;
4042         ListCell   *slitem;
4043
4044         copy_plan_costsize(plan, lefttree);
4045
4046         /*
4047          * Charge one cpu_operator_cost per comparison per input tuple. We assume
4048          * all columns get compared at most of the tuples.      (XXX probably this is
4049          * an overestimate.)
4050          */
4051         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
4052
4053         /*
4054          * plan->plan_rows is left as a copy of the input subplan's plan_rows; ie,
4055          * we assume the filter removes nothing.  The caller must alter this if he
4056          * has a better idea.
4057          */
4058
4059         plan->targetlist = lefttree->targetlist;
4060         plan->qual = NIL;
4061         plan->lefttree = lefttree;
4062         plan->righttree = NULL;
4063
4064         /*
4065          * convert SortGroupClause list into arrays of attr indexes and equality
4066          * operators, as wanted by executor
4067          */
4068         Assert(numCols > 0);
4069         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
4070         uniqOperators = (Oid *) palloc(sizeof(Oid) * numCols);
4071
4072         foreach(slitem, distinctList)
4073         {
4074                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
4075                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
4076
4077                 uniqColIdx[keyno] = tle->resno;
4078                 uniqOperators[keyno] = sortcl->eqop;
4079                 Assert(OidIsValid(uniqOperators[keyno]));
4080                 keyno++;
4081         }
4082
4083         node->numCols = numCols;
4084         node->uniqColIdx = uniqColIdx;
4085         node->uniqOperators = uniqOperators;
4086
4087         return node;
4088 }
4089
4090 /*
4091  * distinctList is a list of SortGroupClauses, identifying the targetlist
4092  * items that should be considered by the SetOp filter.  The input path must
4093  * already be sorted accordingly.
4094  */
4095 SetOp *
4096 make_setop(SetOpCmd cmd, SetOpStrategy strategy, Plan *lefttree,
4097                    List *distinctList, AttrNumber flagColIdx, int firstFlag,
4098                    long numGroups, double outputRows)
4099 {
4100         SetOp      *node = makeNode(SetOp);
4101         Plan       *plan = &node->plan;
4102         int                     numCols = list_length(distinctList);
4103         int                     keyno = 0;
4104         AttrNumber *dupColIdx;
4105         Oid                *dupOperators;
4106         ListCell   *slitem;
4107
4108         copy_plan_costsize(plan, lefttree);
4109         plan->plan_rows = outputRows;
4110
4111         /*
4112          * Charge one cpu_operator_cost per comparison per input tuple. We assume
4113          * all columns get compared at most of the tuples.
4114          */
4115         plan->total_cost += cpu_operator_cost * lefttree->plan_rows * numCols;
4116
4117         plan->targetlist = lefttree->targetlist;
4118         plan->qual = NIL;
4119         plan->lefttree = lefttree;
4120         plan->righttree = NULL;
4121
4122         /*
4123          * convert SortGroupClause list into arrays of attr indexes and equality
4124          * operators, as wanted by executor
4125          */
4126         Assert(numCols > 0);
4127         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
4128         dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
4129
4130         foreach(slitem, distinctList)
4131         {
4132                 SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
4133                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, plan->targetlist);
4134
4135                 dupColIdx[keyno] = tle->resno;
4136                 dupOperators[keyno] = sortcl->eqop;
4137                 Assert(OidIsValid(dupOperators[keyno]));
4138                 keyno++;
4139         }
4140
4141         node->cmd = cmd;
4142         node->strategy = strategy;
4143         node->numCols = numCols;
4144         node->dupColIdx = dupColIdx;
4145         node->dupOperators = dupOperators;
4146         node->flagColIdx = flagColIdx;
4147         node->firstFlag = firstFlag;
4148         node->numGroups = numGroups;
4149
4150         return node;
4151 }
4152
4153 /*
4154  * make_lockrows
4155  *        Build a LockRows plan node
4156  */
4157 LockRows *
4158 make_lockrows(Plan *lefttree, List *rowMarks, int epqParam)
4159 {
4160         LockRows   *node = makeNode(LockRows);
4161         Plan       *plan = &node->plan;
4162
4163         copy_plan_costsize(plan, lefttree);
4164
4165         /* charge cpu_tuple_cost to reflect locking costs (underestimate?) */
4166         plan->total_cost += cpu_tuple_cost * plan->plan_rows;
4167
4168         plan->targetlist = lefttree->targetlist;
4169         plan->qual = NIL;
4170         plan->lefttree = lefttree;
4171         plan->righttree = NULL;
4172
4173         node->rowMarks = rowMarks;
4174         node->epqParam = epqParam;
4175
4176         return node;
4177 }
4178
4179 /*
4180  * Note: offset_est and count_est are passed in to save having to repeat
4181  * work already done to estimate the values of the limitOffset and limitCount
4182  * expressions.  Their values are as returned by preprocess_limit (0 means
4183  * "not relevant", -1 means "couldn't estimate").  Keep the code below in sync
4184  * with that function!
4185  */
4186 Limit *
4187 make_limit(Plan *lefttree, Node *limitOffset, Node *limitCount,
4188                    int64 offset_est, int64 count_est)
4189 {
4190         Limit      *node = makeNode(Limit);
4191         Plan       *plan = &node->plan;
4192
4193         copy_plan_costsize(plan, lefttree);
4194
4195         /*
4196          * Adjust the output rows count and costs according to the offset/limit.
4197          * This is only a cosmetic issue if we are at top level, but if we are
4198          * building a subquery then it's important to report correct info to the
4199          * outer planner.
4200          *
4201          * When the offset or count couldn't be estimated, use 10% of the
4202          * estimated number of rows emitted from the subplan.
4203          */
4204         if (offset_est != 0)
4205         {
4206                 double          offset_rows;
4207
4208                 if (offset_est > 0)
4209                         offset_rows = (double) offset_est;
4210                 else
4211                         offset_rows = clamp_row_est(lefttree->plan_rows * 0.10);
4212                 if (offset_rows > plan->plan_rows)
4213                         offset_rows = plan->plan_rows;
4214                 if (plan->plan_rows > 0)
4215                         plan->startup_cost +=
4216                                 (plan->total_cost - plan->startup_cost)
4217                                 * offset_rows / plan->plan_rows;
4218                 plan->plan_rows -= offset_rows;
4219                 if (plan->plan_rows < 1)
4220                         plan->plan_rows = 1;
4221         }
4222
4223         if (count_est != 0)
4224         {
4225                 double          count_rows;
4226
4227                 if (count_est > 0)
4228                         count_rows = (double) count_est;
4229                 else
4230                         count_rows = clamp_row_est(lefttree->plan_rows * 0.10);
4231                 if (count_rows > plan->plan_rows)
4232                         count_rows = plan->plan_rows;
4233                 if (plan->plan_rows > 0)
4234                         plan->total_cost = plan->startup_cost +
4235                                 (plan->total_cost - plan->startup_cost)
4236                                 * count_rows / plan->plan_rows;
4237                 plan->plan_rows = count_rows;
4238                 if (plan->plan_rows < 1)
4239                         plan->plan_rows = 1;
4240         }
4241
4242         plan->targetlist = lefttree->targetlist;
4243         plan->qual = NIL;
4244         plan->lefttree = lefttree;
4245         plan->righttree = NULL;
4246
4247         node->limitOffset = limitOffset;
4248         node->limitCount = limitCount;
4249
4250         return node;
4251 }
4252
4253 /*
4254  * make_result
4255  *        Build a Result plan node
4256  *
4257  * If we have a subplan, assume that any evaluation costs for the gating qual
4258  * were already factored into the subplan's startup cost, and just copy the
4259  * subplan cost.  If there's no subplan, we should include the qual eval
4260  * cost.  In either case, tlist eval cost is not to be included here.
4261  */
4262 Result *
4263 make_result(PlannerInfo *root,
4264                         List *tlist,
4265                         Node *resconstantqual,
4266                         Plan *subplan)
4267 {
4268         Result     *node = makeNode(Result);
4269         Plan       *plan = &node->plan;
4270
4271         if (subplan)
4272                 copy_plan_costsize(plan, subplan);
4273         else
4274         {
4275                 plan->startup_cost = 0;
4276                 plan->total_cost = cpu_tuple_cost;
4277                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
4278                 plan->plan_width = 0;   /* XXX is it worth being smarter? */
4279                 if (resconstantqual)
4280                 {
4281                         QualCost        qual_cost;
4282
4283                         cost_qual_eval(&qual_cost, (List *) resconstantqual, root);
4284                         /* resconstantqual is evaluated once at startup */
4285                         plan->startup_cost += qual_cost.startup + qual_cost.per_tuple;
4286                         plan->total_cost += qual_cost.startup + qual_cost.per_tuple;
4287                 }
4288         }
4289
4290         plan->targetlist = tlist;
4291         plan->qual = NIL;
4292         plan->lefttree = subplan;
4293         plan->righttree = NULL;
4294         node->resconstantqual = resconstantqual;
4295
4296         return node;
4297 }
4298
4299 /*
4300  * make_modifytable
4301  *        Build a ModifyTable plan node
4302  *
4303  * Currently, we don't charge anything extra for the actual table modification
4304  * work, nor for the RETURNING expressions if any.      It would only be window
4305  * dressing, since these are always top-level nodes and there is no way for
4306  * the costs to change any higher-level planning choices.  But we might want
4307  * to make it look better sometime.
4308  */
4309 ModifyTable *
4310 make_modifytable(CmdType operation, bool canSetTag,
4311                                  List *resultRelations,
4312                                  List *subplans, List *returningLists,
4313                                  List *rowMarks, int epqParam)
4314 {
4315         ModifyTable *node = makeNode(ModifyTable);
4316         Plan       *plan = &node->plan;
4317         double          total_size;
4318         ListCell   *subnode;
4319
4320         Assert(list_length(resultRelations) == list_length(subplans));
4321         Assert(returningLists == NIL ||
4322                    list_length(resultRelations) == list_length(returningLists));
4323
4324         /*
4325          * Compute cost as sum of subplan costs.
4326          */
4327         plan->startup_cost = 0;
4328         plan->total_cost = 0;
4329         plan->plan_rows = 0;
4330         total_size = 0;
4331         foreach(subnode, subplans)
4332         {
4333                 Plan       *subplan = (Plan *) lfirst(subnode);
4334
4335                 if (subnode == list_head(subplans))             /* first node? */
4336                         plan->startup_cost = subplan->startup_cost;
4337                 plan->total_cost += subplan->total_cost;
4338                 plan->plan_rows += subplan->plan_rows;
4339                 total_size += subplan->plan_width * subplan->plan_rows;
4340         }
4341         if (plan->plan_rows > 0)
4342                 plan->plan_width = rint(total_size / plan->plan_rows);
4343         else
4344                 plan->plan_width = 0;
4345
4346         node->plan.lefttree = NULL;
4347         node->plan.righttree = NULL;
4348         node->plan.qual = NIL;
4349
4350         /*
4351          * Set up the visible plan targetlist as being the same as the first
4352          * RETURNING list.      This is for the use of EXPLAIN; the executor won't pay
4353          * any attention to the targetlist.
4354          */
4355         if (returningLists)
4356                 node->plan.targetlist = copyObject(linitial(returningLists));
4357         else
4358                 node->plan.targetlist = NIL;
4359
4360         node->operation = operation;
4361         node->canSetTag = canSetTag;
4362         node->resultRelations = resultRelations;
4363         node->resultRelIndex = -1;      /* will be set correctly in setrefs.c */
4364         node->plans = subplans;
4365         node->returningLists = returningLists;
4366         node->rowMarks = rowMarks;
4367         node->epqParam = epqParam;
4368
4369         return node;
4370 }
4371
4372 /*
4373  * is_projection_capable_plan
4374  *              Check whether a given Plan node is able to do projection.
4375  */
4376 bool
4377 is_projection_capable_plan(Plan *plan)
4378 {
4379         /* Most plan types can project, so just list the ones that can't */
4380         switch (nodeTag(plan))
4381         {
4382                 case T_Hash:
4383                 case T_Material:
4384                 case T_Sort:
4385                 case T_Unique:
4386                 case T_SetOp:
4387                 case T_LockRows:
4388                 case T_Limit:
4389                 case T_ModifyTable:
4390                 case T_Append:
4391                 case T_MergeAppend:
4392                 case T_RecursiveUnion:
4393                         return false;
4394                 default:
4395                         break;
4396         }
4397         return true;
4398 }