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