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