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