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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * createplan.c
   4  *        Routines to create the desired plan for processing a query.
   5  *        Planning is complete, we just need to convert the selected
   6  *        Path into a Plan.
   7  *
   8  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
   9  * Portions Copyright (c) 1994, Regents of the University of California
  10  *
  11  *
  12  * IDENTIFICATION
  13  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.117 2002/09/02 02:47:02 momjian Exp $
  14  *
  15  *-------------------------------------------------------------------------
  16  */
  17 #include "postgres.h"
  18
  19
  20 #include "nodes/makefuncs.h"
  21 #include "nodes/nodeFuncs.h"
  22 #include "optimizer/clauses.h"
  23 #include "optimizer/cost.h"
  24 #include "optimizer/paths.h"
  25 #include "optimizer/planmain.h"
  26 #include "optimizer/restrictinfo.h"
  27 #include "optimizer/tlist.h"
  28 #include "optimizer/var.h"
  29 #include "parser/parse_expr.h"
  30 #include "utils/lsyscache.h"
  31 #include "utils/syscache.h"
  32
  33
  34 static Scan *create_scan_plan(Query *root, Path *best_path);
  35 static Join *create_join_plan(Query *root, JoinPath *best_path);
  36 static Append *create_append_plan(Query *root, AppendPath *best_path);
  37 static SeqScan *create_seqscan_plan(Path *best_path, List *tlist,
  38                                         List *scan_clauses);
  39 static IndexScan *create_indexscan_plan(Query *root, IndexPath *best_path,
  40                                           List *tlist, List *scan_clauses);
  41 static TidScan *create_tidscan_plan(TidPath *best_path, List *tlist,
  42                                         List *scan_clauses);
  43 static SubqueryScan *create_subqueryscan_plan(Path *best_path,
  44                                                  List *tlist, List *scan_clauses);
  45 static FunctionScan *create_functionscan_plan(Path *best_path,
  46                                                  List *tlist, List *scan_clauses);
  47 static NestLoop *create_nestloop_plan(Query *root,
  48                                          NestPath *best_path, List *tlist,
  49                                          List *joinclauses, List *otherclauses,
  50                                          Plan *outer_plan, List *outer_tlist,
  51                                          Plan *inner_plan, List *inner_tlist);
  52 static MergeJoin *create_mergejoin_plan(Query *root,
  53                                           MergePath *best_path, List *tlist,
  54                                           List *joinclauses, List *otherclauses,
  55                                           Plan *outer_plan, List *outer_tlist,
  56                                           Plan *inner_plan, List *inner_tlist);
  57 static HashJoin *create_hashjoin_plan(Query *root,
  58                                          HashPath *best_path, List *tlist,
  59                                          List *joinclauses, List *otherclauses,
  60                                          Plan *outer_plan, List *outer_tlist,
  61                                          Plan *inner_plan, List *inner_tlist);
  62 static void fix_indxqual_references(List *indexquals, IndexPath *index_path,
  63                                                 List **fixed_indexquals,
  64                                                 List **recheck_indexquals);
  65 static void fix_indxqual_sublist(List *indexqual, int baserelid,
  66                                          IndexOptInfo *index,
  67                                          List **fixed_quals, List **recheck_quals);
  68 static Node *fix_indxqual_operand(Node *node, int baserelid,
  69                                          IndexOptInfo *index,
  70                                          Oid *opclass);
  71 static List *switch_outer(List *clauses);
  72 static void copy_path_costsize(Plan *dest, Path *src);
  73 static void copy_plan_costsize(Plan *dest, Plan *src);
  74 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
  75 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
  76                            List *indxid, List *indxqual,
  77                            List *indxqualorig,
  78                            ScanDirection indexscandir);
  79 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
  80                          List *tideval);
  81 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
  82                                                                            Index scanrelid);
  83 static NestLoop *make_nestloop(List *tlist,
  84                           List *joinclauses, List *otherclauses,
  85                           Plan *lefttree, Plan *righttree,
  86                           JoinType jointype);
  87 static HashJoin *make_hashjoin(List *tlist,
  88                           List *joinclauses, List *otherclauses,
  89                           List *hashclauses,
  90                           Plan *lefttree, Plan *righttree,
  91                           JoinType jointype);
  92 static Hash *make_hash(List *tlist, Node *hashkey, Plan *lefttree);
  93 static MergeJoin *make_mergejoin(List *tlist,
  94                            List *joinclauses, List *otherclauses,
  95                            List *mergeclauses,
  96                            Plan *lefttree, Plan *righttree,
  97                            JoinType jointype);
  98
  99 /*
 100  * create_plan
 101  *        Creates the access plan for a query by tracing backwards through the
 102  *        desired chain of pathnodes, starting at the node 'best_path'.  For
 103  *        every pathnode found:
 104  *        (1) Create a corresponding plan node containing appropriate id,
 105  *                target list, and qualification information.
 106  *        (2) Modify qual clauses of join nodes so that subplan attributes are
 107  *                referenced using relative values.
 108  *        (3) Target lists are not modified, but will be in setrefs.c.
 109  *
 110  *        best_path is the best access path
 111  *
 112  *        Returns a Plan tree.
 113  */
 114 Plan *
 115 create_plan(Query *root, Path *best_path)
 116 {
 117         Plan       *plan;
 118
 119         switch (best_path->pathtype)
 120         {
 121                 case T_IndexScan:
 122                 case T_SeqScan:
 123                 case T_TidScan:
 124                 case T_SubqueryScan:
 125                 case T_FunctionScan:
 126                         plan = (Plan *) create_scan_plan(root, best_path);
 127                         break;
 128                 case T_HashJoin:
 129                 case T_MergeJoin:
 130                 case T_NestLoop:
 131                         plan = (Plan *) create_join_plan(root,
 132                                                                                          (JoinPath *) best_path);
 133                         break;
 134                 case T_Append:
 135                         plan = (Plan *) create_append_plan(root,
 136                                                                                            (AppendPath *) best_path);
 137                         break;
 138                 default:
 139                         elog(ERROR, "create_plan: unknown pathtype %d",
 140                                  best_path->pathtype);
 141                         plan = NULL;            /* keep compiler quiet */
 142                         break;
 143         }
 144
 145 #ifdef NOT_USED                                 /* fix xfunc */
 146         /* sort clauses by cost/(1-selectivity) -- JMH 2/26/92 */
 147         if (XfuncMode != XFUNC_OFF)
 148         {
 149                 set_qpqual((Plan) plan,
 150                                    lisp_qsort(get_qpqual((Plan) plan),
 151                                                           xfunc_clause_compare));
 152                 if (XfuncMode != XFUNC_NOR)
 153                         /* sort the disjuncts within each clause by cost -- JMH 3/4/92 */
 154                         xfunc_disjunct_sort(plan->qpqual);
 155         }
 156 #endif
 157
 158         return plan;
 159 }
 160
 161 /*
 162  * create_scan_plan
 163  *       Create a scan plan for the parent relation of 'best_path'.
 164  *
 165  *       Returns a Plan node.
 166  */
 167 static Scan *
 168 create_scan_plan(Query *root, Path *best_path)
 169 {
 170         Scan       *plan;
 171         List       *tlist = best_path->parent->targetlist;
 172         List       *scan_clauses;
 173
 174         /*
 175          * Extract the relevant restriction clauses from the parent relation;
 176          * the executor must apply all these restrictions during the scan.
 177          */
 178         scan_clauses = get_actual_clauses(best_path->parent->baserestrictinfo);
 179
 180         switch (best_path->pathtype)
 181         {
 182                 case T_SeqScan:
 183                         plan = (Scan *) create_seqscan_plan(best_path,
 184                                                                                                 tlist,
 185                                                                                                 scan_clauses);
 186                         break;
 187
 188                 case T_IndexScan:
 189                         plan = (Scan *) create_indexscan_plan(root,
 190                                                                                                   (IndexPath *) best_path,
 191                                                                                                   tlist,
 192                                                                                                   scan_clauses);
 193                         break;
 194
 195                 case T_TidScan:
 196                         plan = (Scan *) create_tidscan_plan((TidPath *) best_path,
 197                                                                                                 tlist,
 198                                                                                                 scan_clauses);
 199                         break;
 200
 201                 case T_SubqueryScan:
 202                         plan = (Scan *) create_subqueryscan_plan(best_path,
 203                                                                                                          tlist,
 204                                                                                                          scan_clauses);
 205                         break;
 206
 207                 case T_FunctionScan:
 208                         plan = (Scan *) create_functionscan_plan(best_path,
 209                                                                                                 tlist,
 210                                                                                                 scan_clauses);
 211                         break;
 212
 213                 default:
 214                         elog(ERROR, "create_scan_plan: unknown node type: %d",
 215                                  best_path->pathtype);
 216                         plan = NULL;            /* keep compiler quiet */
 217                         break;
 218         }
 219
 220         return plan;
 221 }
 222
 223 /*
 224  * create_join_plan
 225  *        Create a join plan for 'best_path' and (recursively) plans for its
 226  *        inner and outer paths.
 227  *
 228  *        Returns a Plan node.
 229  */
 230 static Join *
 231 create_join_plan(Query *root, JoinPath *best_path)
 232 {
 233         List       *join_tlist = best_path->path.parent->targetlist;
 234         Plan       *outer_plan;
 235         List       *outer_tlist;
 236         Plan       *inner_plan;
 237         List       *inner_tlist;
 238         List       *joinclauses;
 239         List       *otherclauses;
 240         Join       *plan;
 241
 242         outer_plan = create_plan(root, best_path->outerjoinpath);
 243         outer_tlist = outer_plan->targetlist;
 244
 245         inner_plan = create_plan(root, best_path->innerjoinpath);
 246         inner_tlist = inner_plan->targetlist;
 247
 248         if (IS_OUTER_JOIN(best_path->jointype))
 249         {
 250                 get_actual_join_clauses(best_path->joinrestrictinfo,
 251                                                                 &joinclauses, &otherclauses);
 252         }
 253         else
 254         {
 255                 /* We can treat all clauses alike for an inner join */
 256                 joinclauses = get_actual_clauses(best_path->joinrestrictinfo);
 257                 otherclauses = NIL;
 258         }
 259
 260         switch (best_path->path.pathtype)
 261         {
 262                 case T_MergeJoin:
 263                         plan = (Join *) create_mergejoin_plan(root,
 264                                                                                                   (MergePath *) best_path,
 265                                                                                                   join_tlist,
 266                                                                                                   joinclauses,
 267                                                                                                   otherclauses,
 268                                                                                                   outer_plan,
 269                                                                                                   outer_tlist,
 270                                                                                                   inner_plan,
 271                                                                                                   inner_tlist);
 272                         break;
 273                 case T_HashJoin:
 274                         plan = (Join *) create_hashjoin_plan(root,
 275                                                                                                  (HashPath *) best_path,
 276                                                                                                  join_tlist,
 277                                                                                                  joinclauses,
 278                                                                                                  otherclauses,
 279                                                                                                  outer_plan,
 280                                                                                                  outer_tlist,
 281                                                                                                  inner_plan,
 282                                                                                                  inner_tlist);
 283                         break;
 284                 case T_NestLoop:
 285                         plan = (Join *) create_nestloop_plan(root,
 286                                                                                                  (NestPath *) best_path,
 287                                                                                                  join_tlist,
 288                                                                                                  joinclauses,
 289                                                                                                  otherclauses,
 290                                                                                                  outer_plan,
 291                                                                                                  outer_tlist,
 292                                                                                                  inner_plan,
 293                                                                                                  inner_tlist);
 294                         break;
 295                 default:
 296                         elog(ERROR, "create_join_plan: unknown node type: %d",
 297                                  best_path->path.pathtype);
 298                         plan = NULL;            /* keep compiler quiet */
 299                         break;
 300         }
 301
 302 #ifdef NOT_USED
 303
 304         /*
 305          * * Expensive function pullups may have pulled local predicates *
 306          * into this path node.  Put them in the qpqual of the plan node. *
 307          * JMH, 6/15/92
 308          */
 309         if (get_loc_restrictinfo(best_path) != NIL)
 310                 set_qpqual((Plan) plan,
 311                                    nconc(get_qpqual((Plan) plan),
 312                                    get_actual_clauses(get_loc_restrictinfo(best_path))));
 313 #endif
 314
 315         return plan;
 316 }
 317
 318 /*
 319  * create_append_plan
 320  *        Create an Append plan for 'best_path' and (recursively) plans
 321  *        for its subpaths.
 322  *
 323  *        Returns a Plan node.
 324  */
 325 static Append *
 326 create_append_plan(Query *root, AppendPath *best_path)
 327 {
 328         Append     *plan;
 329         List       *tlist = best_path->path.parent->targetlist;
 330         List       *subplans = NIL;
 331         List       *subpaths;
 332
 333         foreach(subpaths, best_path->subpaths)
 334         {
 335                 Path       *subpath = (Path *) lfirst(subpaths);
 336
 337                 subplans = lappend(subplans, create_plan(root, subpath));
 338         }
 339
 340         plan = make_append(subplans, false, tlist);
 341
 342         return plan;
 343 }
 344
 345
 346 /*****************************************************************************
 347  *
 348  *      BASE-RELATION SCAN METHODS
 349  *
 350  *****************************************************************************/
 351
 352
 353 /*
 354  * create_seqscan_plan
 355  *       Returns a seqscan plan for the base relation scanned by 'best_path'
 356  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 357  */
 358 static SeqScan *
 359 create_seqscan_plan(Path *best_path, List *tlist, List *scan_clauses)
 360 {
 361         SeqScan    *scan_plan;
 362         Index           scan_relid;
 363
 364         /* there should be exactly one base rel involved... */
 365         Assert(length(best_path->parent->relids) == 1);
 366         Assert(best_path->parent->rtekind == RTE_RELATION);
 367
 368         scan_relid = (Index) lfirsti(best_path->parent->relids);
 369
 370         scan_plan = make_seqscan(tlist,
 371                                                          scan_clauses,
 372                                                          scan_relid);
 373
 374         copy_path_costsize(&scan_plan->plan, best_path);
 375
 376         return scan_plan;
 377 }
 378
 379 /*
 380  * create_indexscan_plan
 381  *        Returns a indexscan plan for the base relation scanned by 'best_path'
 382  *        with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 383  *
 384  * The indexqual of the path contains a sublist of implicitly-ANDed qual
 385  * conditions for each scan of the index(es); if there is more than one
 386  * scan then the retrieved tuple sets are ORed together.  The indexqual
 387  * and indexinfo lists must have the same length, ie, the number of scans
 388  * that will occur.  Note it is possible for a qual condition sublist
 389  * to be empty --- then no index restrictions will be applied during that
 390  * scan.
 391  */
 392 static IndexScan *
 393 create_indexscan_plan(Query *root,
 394                                           IndexPath *best_path,
 395                                           List *tlist,
 396                                           List *scan_clauses)
 397 {
 398         List       *indxqual = best_path->indexqual;
 399         Index           baserelid;
 400         List       *qpqual;
 401         Expr       *indxqual_or_expr = NULL;
 402         List       *fixed_indxqual;
 403         List       *recheck_indxqual;
 404         List       *indexids;
 405         List       *ixinfo;
 406         IndexScan  *scan_plan;
 407
 408         /* there should be exactly one base rel involved... */
 409         Assert(length(best_path->path.parent->relids) == 1);
 410         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 411
 412         baserelid = lfirsti(best_path->path.parent->relids);
 413
 414         /*
 415          * Build list of index OIDs.
 416          */
 417         indexids = NIL;
 418         foreach(ixinfo, best_path->indexinfo)
 419         {
 420                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ixinfo);
 421
 422                 indexids = lappendi(indexids, index->indexoid);
 423         }
 424
 425         /*
 426          * The qpqual list must contain all restrictions not automatically
 427          * handled by the index.  Normally the predicates in the indxqual are
 428          * checked fully by the index, but if the index is "lossy" for a
 429          * particular operator (as signaled by the amopreqcheck flag in
 430          * pg_amop), then we need to double-check that predicate in qpqual,
 431          * because the index may return more tuples than match the predicate.
 432          *
 433          * Since the indexquals were generated from the restriction clauses given
 434          * by scan_clauses, there will normally be some duplications between
 435          * the lists.  We get rid of the duplicates, then add back if lossy.
 436          */
 437         if (length(indxqual) > 1)
 438         {
 439                 /*
 440                  * Build an expression representation of the indexqual, expanding
 441                  * the implicit OR and AND semantics of the first- and
 442                  * second-level lists.
 443                  */
 444                 List       *orclauses = NIL;
 445                 List       *orclause;
 446
 447                 foreach(orclause, indxqual)
 448                 {
 449                         orclauses = lappend(orclauses,
 450                                                                 make_ands_explicit(lfirst(orclause)));
 451                 }
 452                 indxqual_or_expr = make_orclause(orclauses);
 453
 454                 qpqual = set_difference(scan_clauses, makeList1(indxqual_or_expr));
 455         }
 456         else if (indxqual != NIL)
 457         {
 458                 /*
 459                  * Here, we can simply treat the first sublist as an independent
 460                  * set of qual expressions, since there is no top-level OR
 461                  * behavior.
 462                  */
 463                 qpqual = set_difference(scan_clauses, lfirst(indxqual));
 464         }
 465         else
 466                 qpqual = scan_clauses;
 467
 468         /*
 469          * The executor needs a copy with the indexkey on the left of each
 470          * clause and with index attr numbers substituted for table ones. This
 471          * pass also looks for "lossy" operators.
 472          */
 473         fix_indxqual_references(indxqual, best_path,
 474                                                         &fixed_indxqual, &recheck_indxqual);
 475
 476         /*
 477          * If there were any "lossy" operators, need to add back the
 478          * appropriate qual clauses to the qpqual.      When there is just one
 479          * indexscan being performed (ie, we have simple AND semantics), we
 480          * can just add the lossy clauses themselves to qpqual.  If we have
 481          * OR-of-ANDs, we'd better add the entire original indexqual to make
 482          * sure that the semantics are correct.
 483          */
 484         if (recheck_indxqual != NIL)
 485         {
 486                 if (indxqual_or_expr)
 487                 {
 488                         /* Better do a deep copy of the original scanclauses */
 489                         qpqual = lappend(qpqual, copyObject(indxqual_or_expr));
 490                 }
 491                 else
 492                 {
 493                         /* Subroutine already copied quals, so just append to list */
 494                         Assert(length(recheck_indxqual) == 1);
 495                         qpqual = nconc(qpqual, (List *) lfirst(recheck_indxqual));
 496                 }
 497         }
 498
 499         /* Finally ready to build the plan node */
 500         scan_plan = make_indexscan(tlist,
 501                                                            qpqual,
 502                                                            baserelid,
 503                                                            indexids,
 504                                                            fixed_indxqual,
 505                                                            indxqual,
 506                                                            best_path->indexscandir);
 507
 508         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 509         /* use the indexscan-specific rows estimate, not the parent rel's */
 510         scan_plan->scan.plan.plan_rows = best_path->rows;
 511
 512         return scan_plan;
 513 }
 514
 515 /*
 516  * create_tidscan_plan
 517  *       Returns a tidscan plan for the base relation scanned by 'best_path'
 518  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 519  */
 520 static TidScan *
 521 create_tidscan_plan(TidPath *best_path, List *tlist, List *scan_clauses)
 522 {
 523         TidScan    *scan_plan;
 524         Index           scan_relid;
 525
 526         /* there should be exactly one base rel involved... */
 527         Assert(length(best_path->path.parent->relids) == 1);
 528         Assert(best_path->path.parent->rtekind == RTE_RELATION);
 529
 530         scan_relid = (Index) lfirsti(best_path->path.parent->relids);
 531
 532         scan_plan = make_tidscan(tlist,
 533                                                          scan_clauses,
 534                                                          scan_relid,
 535                                                          best_path->tideval);
 536
 537         if (best_path->unjoined_relids)
 538                 scan_plan->needRescan = true;
 539
 540         copy_path_costsize(&scan_plan->scan.plan, &best_path->path);
 541
 542         return scan_plan;
 543 }
 544
 545 /*
 546  * create_subqueryscan_plan
 547  *       Returns a subqueryscan plan for the base relation scanned by 'best_path'
 548  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 549  */
 550 static SubqueryScan *
 551 create_subqueryscan_plan(Path *best_path, List *tlist, List *scan_clauses)
 552 {
 553         SubqueryScan *scan_plan;
 554         Index           scan_relid;
 555
 556         /* there should be exactly one base rel involved... */
 557         Assert(length(best_path->parent->relids) == 1);
 558         /* and it must be a subquery */
 559         Assert(best_path->parent->rtekind == RTE_SUBQUERY);
 560
 561         scan_relid = (Index) lfirsti(best_path->parent->relids);
 562
 563         scan_plan = make_subqueryscan(tlist,
 564                                                                   scan_clauses,
 565                                                                   scan_relid,
 566                                                                   best_path->parent->subplan);
 567
 568         return scan_plan;
 569 }
 570
 571 /*
 572  * create_functionscan_plan
 573  *       Returns a functionscan plan for the base relation scanned by 'best_path'
 574  *       with restriction clauses 'scan_clauses' and targetlist 'tlist'.
 575  */
 576 static FunctionScan *
 577 create_functionscan_plan(Path *best_path, List *tlist, List *scan_clauses)
 578 {
 579         FunctionScan *scan_plan;
 580         Index           scan_relid;
 581
 582         /* there should be exactly one base rel involved... */
 583         Assert(length(best_path->parent->relids) == 1);
 584         /* and it must be a function */
 585         Assert(best_path->parent->rtekind == RTE_FUNCTION);
 586
 587         scan_relid = (Index) lfirsti(best_path->parent->relids);
 588
 589         scan_plan = make_functionscan(tlist, scan_clauses, scan_relid);
 590
 591         copy_path_costsize(&scan_plan->scan.plan, best_path);
 592
 593         return scan_plan;
 594 }
 595
 596 /*****************************************************************************
 597  *
 598  *      JOIN METHODS
 599  *
 600  * A general note about join_references() processing in these routines:
 601  * once we have changed a Var node to refer to a subplan output rather than
 602  * the original relation, it is no longer equal() to an unmodified Var node
 603  * for the same var.  So, we cannot easily compare reference-adjusted qual
 604  * clauses to clauses that have not been adjusted.      Fortunately, that
 605  * doesn't seem to be necessary; all the decisions are made before we do
 606  * the reference adjustments.
 607  *
 608  * A cleaner solution would be to not call join_references() here at all,
 609  * but leave it for setrefs.c to do at the end of plan tree construction.
 610  * But that would make switch_outer() much more complicated, and some care
 611  * would be needed to get setrefs.c to do the right thing with nestloop
 612  * inner indexscan quals.  So, we do subplan reference adjustment here for
 613  * quals of join nodes (and *only* for quals of join nodes).
 614  *
 615  *****************************************************************************/
 616
 617 static NestLoop *
 618 create_nestloop_plan(Query *root,
 619                                          NestPath *best_path,
 620                                          List *tlist,
 621                                          List *joinclauses,
 622                                          List *otherclauses,
 623                                          Plan *outer_plan,
 624                                          List *outer_tlist,
 625                                          Plan *inner_plan,
 626                                          List *inner_tlist)
 627 {
 628         NestLoop   *join_plan;
 629
 630         if (IsA(inner_plan, IndexScan))
 631         {
 632                 /*
 633                  * An index is being used to reduce the number of tuples scanned
 634                  * in the inner relation.  If there are join clauses being used
 635                  * with the index, we must update their outer-rel var nodes to
 636                  * refer to the outer side of the join.
 637                  *
 638                  * We can also remove those join clauses from the list of clauses
 639                  * that have to be checked as qpquals at the join node, but only
 640                  * if there's just one indexscan in the inner path (otherwise,
 641                  * several different sets of clauses are being ORed together).
 642                  *
 643                  * Note: if the index is lossy, the same clauses may also be getting
 644                  * checked as qpquals in the indexscan.  We can still remove them
 645                  * from the nestloop's qpquals, but we gotta update the outer-rel
 646                  * vars in the indexscan's qpquals too.
 647                  *
 648                  * Note: we can safely do set_difference() against my clauses and
 649                  * join_references() because the innerscan is a primitive plan,
 650                  * and therefore has not itself done join_references renumbering
 651                  * of the vars in its quals.
 652                  */
 653                 IndexScan  *innerscan = (IndexScan *) inner_plan;
 654                 List       *indxqualorig = innerscan->indxqualorig;
 655
 656                 /* No work needed if indxqual refers only to its own relation... */
 657                 if (NumRelids((Node *) indxqualorig) > 1)
 658                 {
 659                         Index           innerrel = innerscan->scan.scanrelid;
 660
 661                         /*
 662                          * Remove redundant tests from my clauses, if possible. Note
 663                          * we must compare against indxqualorig not the "fixed"
 664                          * indxqual (which has index attnos instead of relation
 665                          * attnos, and may have been commuted as well).
 666                          */
 667                         if (length(indxqualorig) == 1)          /* single indexscan? */
 668                                 joinclauses = set_difference(joinclauses,
 669                                                                                          lfirst(indxqualorig));
 670
 671                         /* only refs to outer vars get changed in the inner indexqual */
 672                         innerscan->indxqualorig = join_references(indxqualorig,
 673                                                                                                           root->rtable,
 674                                                                                                           outer_tlist,
 675                                                                                                           NIL,
 676                                                                                                           innerrel);
 677                         innerscan->indxqual = join_references(innerscan->indxqual,
 678                                                                                                   root->rtable,
 679                                                                                                   outer_tlist,
 680                                                                                                   NIL,
 681                                                                                                   innerrel);
 682                         /* fix the inner qpqual too, if it has join clauses */
 683                         if (NumRelids((Node *) inner_plan->qual) > 1)
 684                                 inner_plan->qual = join_references(inner_plan->qual,
 685                                                                                                    root->rtable,
 686                                                                                                    outer_tlist,
 687                                                                                                    NIL,
 688                                                                                                    innerrel);
 689                 }
 690         }
 691         else if (IsA(inner_plan, TidScan))
 692         {
 693                 TidScan    *innerscan = (TidScan *) inner_plan;
 694
 695                 innerscan->tideval = join_references(innerscan->tideval,
 696                                                                                          root->rtable,
 697                                                                                          outer_tlist,
 698                                                                                          inner_tlist,
 699                                                                                          innerscan->scan.scanrelid);
 700         }
 701         else if (IsA_Join(inner_plan))
 702         {
 703                 /*
 704                  * Materialize the inner join for speed reasons.
 705                  *
 706                  * XXX It is probably *not* always fastest to materialize an inner
 707                  * join --- how can we estimate whether this is a good thing to
 708                  * do?
 709                  */
 710                 inner_plan = (Plan *) make_material(inner_tlist,
 711                                                                                         inner_plan);
 712         }
 713
 714         /*
 715          * Set quals to contain INNER/OUTER var references.
 716          */
 717         joinclauses = join_references(joinclauses,
 718                                                                   root->rtable,
 719                                                                   outer_tlist,
 720                                                                   inner_tlist,
 721                                                                   (Index) 0);
 722         otherclauses = join_references(otherclauses,
 723                                                                    root->rtable,
 724                                                                    outer_tlist,
 725                                                                    inner_tlist,
 726                                                                    (Index) 0);
 727
 728         join_plan = make_nestloop(tlist,
 729                                                           joinclauses,
 730                                                           otherclauses,
 731                                                           outer_plan,
 732                                                           inner_plan,
 733                                                           best_path->jointype);
 734
 735         copy_path_costsize(&join_plan->join.plan, &best_path->path);
 736
 737         return join_plan;
 738 }
 739
 740 static MergeJoin *
 741 create_mergejoin_plan(Query *root,
 742                                           MergePath *best_path,
 743                                           List *tlist,
 744                                           List *joinclauses,
 745                                           List *otherclauses,
 746                                           Plan *outer_plan,
 747                                           List *outer_tlist,
 748                                           Plan *inner_plan,
 749                                           List *inner_tlist)
 750 {
 751         List       *mergeclauses;
 752         MergeJoin  *join_plan;
 753
 754         mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
 755
 756         /*
 757          * Remove the mergeclauses from the list of join qual clauses, leaving
 758          * the list of quals that must be checked as qpquals. Set those
 759          * clauses to contain INNER/OUTER var references.
 760          */
 761         joinclauses = join_references(set_difference(joinclauses, mergeclauses),
 762                                                                   root->rtable,
 763                                                                   outer_tlist,
 764                                                                   inner_tlist,
 765                                                                   (Index) 0);
 766
 767         /*
 768          * Fix the additional qpquals too.
 769          */
 770         otherclauses = join_references(otherclauses,
 771                                                                    root->rtable,
 772                                                                    outer_tlist,
 773                                                                    inner_tlist,
 774                                                                    (Index) 0);
 775
 776         /*
 777          * Now set the references in the mergeclauses and rearrange them so
 778          * that the outer variable is always on the left.
 779          */
 780         mergeclauses = switch_outer(join_references(mergeclauses,
 781                                                                                                 root->rtable,
 782                                                                                                 outer_tlist,
 783                                                                                                 inner_tlist,
 784                                                                                                 (Index) 0));
 785
 786         /*
 787          * Create explicit sort nodes for the outer and inner join paths if
 788          * necessary.  The sort cost was already accounted for in the path.
 789          */
 790         if (best_path->outersortkeys)
 791                 outer_plan = (Plan *)
 792                         make_sort_from_pathkeys(root,
 793                                                                         outer_tlist,
 794                                                                         outer_plan,
 795                                                                         best_path->outersortkeys);
 796
 797         if (best_path->innersortkeys)
 798                 inner_plan = (Plan *)
 799                         make_sort_from_pathkeys(root,
 800                                                                         inner_tlist,
 801                                                                         inner_plan,
 802                                                                         best_path->innersortkeys);
 803
 804         /*
 805          * The executor requires the inner side of a mergejoin to support
 806          * "mark" and "restore" operations.  Not all plan types do, so we must
 807          * be careful not to generate an invalid plan.  If necessary, an
 808          * invalid inner plan can be handled by inserting a Materialize node.
 809          *
 810          * Since the inner side must be ordered, and only Sorts and IndexScans
 811          * can create order to begin with, you might think there's no problem
 812          * --- but you'd be wrong.  Nestloop and merge joins can *preserve*
 813          * the order of their inputs, so they can be selected as the input of
 814          * a mergejoin, and that won't work in the present executor.
 815          *
 816          * Doing this here is a bit of a kluge since the cost of the Materialize
 817          * wasn't taken into account in our earlier decisions.  But
 818          * Materialize is hard to estimate a cost for, and the above
 819          * consideration shows that this is a rare case anyway, so this seems
 820          * an acceptable way to proceed.
 821          *
 822          * This check must agree with ExecMarkPos/ExecRestrPos in
 823          * executor/execAmi.c!
 824          */
 825         switch (nodeTag(inner_plan))
 826         {
 827                 case T_SeqScan:
 828                 case T_IndexScan:
 829                 case T_FunctionScan:
 830                 case T_Material:
 831                 case T_Sort:
 832                         /* OK, these inner plans support mark/restore */
 833                         break;
 834
 835                 default:
 836                         /* Ooops, need to materialize the inner plan */
 837                         inner_plan = (Plan *) make_material(inner_tlist,
 838                                                                                                 inner_plan);
 839                         break;
 840         }
 841
 842         /*
 843          * Now we can build the mergejoin node.
 844          */
 845         join_plan = make_mergejoin(tlist,
 846                                                            joinclauses,
 847                                                            otherclauses,
 848                                                            mergeclauses,
 849                                                            outer_plan,
 850                                                            inner_plan,
 851                                                            best_path->jpath.jointype);
 852
 853         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
 854
 855         return join_plan;
 856 }
 857
 858 static HashJoin *
 859 create_hashjoin_plan(Query *root,
 860                                          HashPath *best_path,
 861                                          List *tlist,
 862                                          List *joinclauses,
 863                                          List *otherclauses,
 864                                          Plan *outer_plan,
 865                                          List *outer_tlist,
 866                                          Plan *inner_plan,
 867                                          List *inner_tlist)
 868 {
 869         List       *hashclauses;
 870         HashJoin   *join_plan;
 871         Hash       *hash_plan;
 872         Node       *innerhashkey;
 873
 874         /*
 875          * NOTE: there will always be exactly one hashclause in the list
 876          * best_path->path_hashclauses (cf. hash_inner_and_outer()). We
 877          * represent it as a list anyway, for convenience with routines that
 878          * want to work on lists of clauses.
 879          */
 880         hashclauses = get_actual_clauses(best_path->path_hashclauses);
 881
 882         /*
 883          * Remove the hashclauses from the list of join qual clauses, leaving
 884          * the list of quals that must be checked as qpquals. Set those
 885          * clauses to contain INNER/OUTER var references.
 886          */
 887         joinclauses = join_references(set_difference(joinclauses, hashclauses),
 888                                                                   root->rtable,
 889                                                                   outer_tlist,
 890                                                                   inner_tlist,
 891                                                                   (Index) 0);
 892
 893         /*
 894          * Fix the additional qpquals too.
 895          */
 896         otherclauses = join_references(otherclauses,
 897                                                                    root->rtable,
 898                                                                    outer_tlist,
 899                                                                    inner_tlist,
 900                                                                    (Index) 0);
 901
 902         /*
 903          * Now set the references in the hashclauses and rearrange them so
 904          * that the outer variable is always on the left.
 905          */
 906         hashclauses = switch_outer(join_references(hashclauses,
 907                                                                                            root->rtable,
 908                                                                                            outer_tlist,
 909                                                                                            inner_tlist,
 910                                                                                            (Index) 0));
 911
 912         /* Now the righthand op of the sole hashclause is the inner hash key. */
 913         innerhashkey = (Node *) get_rightop(lfirst(hashclauses));
 914
 915         /*
 916          * Build the hash node and hash join node.
 917          */
 918         hash_plan = make_hash(inner_tlist, innerhashkey, inner_plan);
 919         join_plan = make_hashjoin(tlist,
 920                                                           joinclauses,
 921                                                           otherclauses,
 922                                                           hashclauses,
 923                                                           outer_plan,
 924                                                           (Plan *) hash_plan,
 925                                                           best_path->jpath.jointype);
 926
 927         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
 928
 929         return join_plan;
 930 }
 931
 932
 933 /*****************************************************************************
 934  *
 935  *      SUPPORTING ROUTINES
 936  *
 937  *****************************************************************************/
 938
 939 /*
 940  * fix_indxqual_references
 941  *        Adjust indexqual clauses to the form the executor's indexqual
 942  *        machinery needs, and check for recheckable (lossy) index conditions.
 943  *
 944  * We have four tasks here:
 945  *      * Index keys must be represented by Var nodes with varattno set to the
 946  *        index's attribute number, not the attribute number in the original rel.
 947  *      * indxpath.c may have selected an index that is binary-compatible with
 948  *        the actual expression operator, but not exactly the same datatype.
 949  *        We must replace the expression's operator with the binary-compatible
 950  *        equivalent operator that the index will recognize.
 951  *      * If the index key is on the right, commute the clause to put it on the
 952  *        left.  (Someday the executor might not need this, but for now it does.)
 953  *      * If the indexable operator is marked 'amopreqcheck' in pg_amop, then
 954  *        the index is "lossy" for this operator: it may return more tuples than
 955  *        actually satisfy the operator condition.      For each such operator, we
 956  *        must add (the original form of) the indexqual clause to the "qpquals"
 957  *        of the indexscan node, where the operator will be re-evaluated to
 958  *        ensure it passes.
 959  *
 960  * This code used to be entirely bogus for multi-index scans.  Now it keeps
 961  * track of which index applies to each subgroup of index qual clauses...
 962  *
 963  * Both the input list and the output lists have the form of lists of sublists
 964  * of qual clauses --- the top-level list has one entry for each indexscan
 965  * to be performed.  The semantics are OR-of-ANDs.
 966  *
 967  * fixed_indexquals receives a modified copy of the indexqual list --- the
 968  * original is not changed.  Note also that the copy shares no substructure
 969  * with the original; this is needed in case there is a subplan in it (we need
 970  * two separate copies of the subplan tree, or things will go awry).
 971  *
 972  * recheck_indexquals similarly receives a full copy of whichever clauses
 973  * need rechecking.
 974  */
 975 static void
 976 fix_indxqual_references(List *indexquals, IndexPath *index_path,
 977                                           List **fixed_indexquals, List **recheck_indexquals)
 978 {
 979         List       *fixed_quals = NIL;
 980         List       *recheck_quals = NIL;
 981         int                     baserelid = lfirsti(index_path->path.parent->relids);
 982         List       *ixinfo = index_path->indexinfo;
 983         List       *i;
 984
 985         foreach(i, indexquals)
 986         {
 987                 List       *indexqual = lfirst(i);
 988                 IndexOptInfo *index = (IndexOptInfo *) lfirst(ixinfo);
 989                 List       *fixed_qual;
 990                 List       *recheck_qual;
 991
 992                 fix_indxqual_sublist(indexqual, baserelid, index,
 993                                                          &fixed_qual, &recheck_qual);
 994                 fixed_quals = lappend(fixed_quals, fixed_qual);
 995                 if (recheck_qual != NIL)
 996                         recheck_quals = lappend(recheck_quals, recheck_qual);
 997
 998                 ixinfo = lnext(ixinfo);
 999         }
1000
1001         *fixed_indexquals = fixed_quals;
1002         *recheck_indexquals = recheck_quals;
1003 }
1004
1005 /*
1006  * Fix the sublist of indexquals to be used in a particular scan.
1007  *
1008  * For each qual clause, commute if needed to put the indexkey operand on the
1009  * left, and then fix its varattno.  (We do not need to change the other side
1010  * of the clause.)      Also change the operator if necessary, and check for
1011  * lossy index behavior.
1012  *
1013  * Returns two lists: the list of fixed indexquals, and the list (usually
1014  * empty) of original clauses that must be rechecked as qpquals because
1015  * the index is lossy for this operator type.
1016  */
1017 static void
1018 fix_indxqual_sublist(List *indexqual, int baserelid, IndexOptInfo *index,
1019                                          List **fixed_quals, List **recheck_quals)
1020 {
1021         List       *fixed_qual = NIL;
1022         List       *recheck_qual = NIL;
1023         List       *i;
1024
1025         foreach(i, indexqual)
1026         {
1027                 Expr       *clause = (Expr *) lfirst(i);
1028                 Expr       *newclause;
1029                 List       *leftvarnos;
1030                 Oid                     opclass,
1031                                         newopno;
1032
1033                 if (!is_opclause((Node *) clause) || length(clause->args) != 2)
1034                         elog(ERROR, "fix_indxqual_sublist: indexqual clause is not binary opclause");
1035
1036                 /*
1037                  * Make a copy that will become the fixed clause.
1038                  *
1039                  * We used to try to do a shallow copy here, but that fails if there
1040                  * is a subplan in the arguments of the opclause.  So just do a
1041                  * full copy.
1042                  */
1043                 newclause = (Expr *) copyObject((Node *) clause);
1044
1045                 /*
1046                  * Check to see if the indexkey is on the right; if so, commute
1047                  * the clause.  The indexkey should be the side that refers to
1048                  * (only) the base relation.
1049                  */
1050                 leftvarnos = pull_varnos((Node *) lfirst(newclause->args));
1051                 if (length(leftvarnos) != 1 || lfirsti(leftvarnos) != baserelid)
1052                         CommuteClause(newclause);
1053                 freeList(leftvarnos);
1054
1055                 /*
1056                  * Now, determine which index attribute this is, change the
1057                  * indexkey operand as needed, and get the index opclass.
1058                  */
1059                 lfirst(newclause->args) = fix_indxqual_operand(lfirst(newclause->args),
1060                                                                                                            baserelid,
1061                                                                                                            index,
1062                                                                                                            &opclass);
1063
1064                 /*
1065                  * Substitute the appropriate operator if the expression operator
1066                  * is merely binary-compatible with the index.  This shouldn't
1067                  * fail, since indxpath.c found it before...
1068                  */
1069                 newopno = indexable_operator(newclause, opclass, true);
1070                 if (newopno == InvalidOid)
1071                         elog(ERROR, "fix_indxqual_sublist: failed to find substitute op");
1072                 ((Oper *) newclause->oper)->opno = newopno;
1073
1074                 fixed_qual = lappend(fixed_qual, newclause);
1075
1076                 /*
1077                  * Finally, check to see if index is lossy for this operator. If
1078                  * so, add (a copy of) original form of clause to recheck list.
1079                  */
1080                 if (op_requires_recheck(newopno, opclass))
1081                         recheck_qual = lappend(recheck_qual,
1082                                                                    copyObject((Node *) clause));
1083         }
1084
1085         *fixed_quals = fixed_qual;
1086         *recheck_quals = recheck_qual;
1087 }
1088
1089 static Node *
1090 fix_indxqual_operand(Node *node, int baserelid, IndexOptInfo *index,
1091                                          Oid *opclass)
1092 {
1093         /*
1094          * Remove any binary-compatible relabeling of the indexkey
1095          */
1096         if (IsA(node, RelabelType))
1097                 node = ((RelabelType *) node)->arg;
1098
1099         /*
1100          * We represent index keys by Var nodes having the varno of the base
1101          * table but varattno equal to the index's attribute number (index
1102          * column position).  This is a bit hokey ... would be cleaner to use
1103          * a special-purpose node type that could not be mistaken for a
1104          * regular Var.  But it will do for now.
1105          */
1106         if (IsA(node, Var))
1107         {
1108                 /* If it's a var, find which index key position it occupies */
1109                 Assert(index->indproc == InvalidOid);
1110
1111                 if (((Var *) node)->varno == baserelid)
1112                 {
1113                         int                     varatt = ((Var *) node)->varattno;
1114                         int                     pos;
1115
1116                         for (pos = 0; pos < index->nkeys; pos++)
1117                         {
1118                                 if (index->indexkeys[pos] == varatt)
1119                                 {
1120                                         Node       *newnode = copyObject(node);
1121
1122                                         ((Var *) newnode)->varattno = pos + 1;
1123                                         /* return the correct opclass, too */
1124                                         *opclass = index->classlist[pos];
1125                                         return newnode;
1126                                 }
1127                         }
1128                 }
1129
1130                 /*
1131                  * Oops, this Var isn't an indexkey!
1132                  */
1133                 elog(ERROR, "fix_indxqual_operand: var is not index attribute");
1134         }
1135
1136         /*
1137          * Else, it must be a func expression matching a functional index.
1138          * Since we currently only support single-column functional indexes,
1139          * the returned varattno must be 1.
1140          */
1141         Assert(index->indproc != InvalidOid);
1142         Assert(is_funcclause(node));    /* not a very thorough check, but easy */
1143
1144         /* classlist[0] is the only class of a functional index */
1145         *opclass = index->classlist[0];
1146
1147         return (Node *) makeVar(baserelid, 1, exprType(node), -1, 0);
1148 }
1149
1150 /*
1151  * switch_outer
1152  *        Given a list of merge or hash joinclauses, rearrange the elements within
1153  *        the clauses so the outer join variable is on the left and the inner is
1154  *        on the right.  The original list is not touched; a modified list
1155  *        is returned.
1156  */
1157 static List *
1158 switch_outer(List *clauses)
1159 {
1160         List       *t_list = NIL;
1161         List       *i;
1162
1163         foreach(i, clauses)
1164         {
1165                 Expr       *clause = (Expr *) lfirst(i);
1166                 Var                *op;
1167
1168                 Assert(is_opclause((Node *) clause));
1169                 op = get_rightop(clause);
1170                 Assert(op && IsA(op, Var));
1171                 if (var_is_outer(op))
1172                 {
1173                         /*
1174                          * Duplicate just enough of the structure to allow commuting
1175                          * the clause without changing the original list.  Could use
1176                          * copyObject, but a complete deep copy is overkill.
1177                          */
1178                         Expr       *temp;
1179
1180                         temp = make_clause(clause->opType, clause->oper,
1181                                                            listCopy(clause->args));
1182                         /* Commute it --- note this modifies the temp node in-place. */
1183                         CommuteClause(temp);
1184                         t_list = lappend(t_list, temp);
1185                 }
1186                 else
1187                         t_list = lappend(t_list, clause);
1188         }
1189         return t_list;
1190 }
1191
1192 /*
1193  * Copy cost and size info from a Path node to the Plan node created from it.
1194  * The executor won't use this info, but it's needed by EXPLAIN.
1195  */
1196 static void
1197 copy_path_costsize(Plan *dest, Path *src)
1198 {
1199         if (src)
1200         {
1201                 dest->startup_cost = src->startup_cost;
1202                 dest->total_cost = src->total_cost;
1203                 dest->plan_rows = src->parent->rows;
1204                 dest->plan_width = src->parent->width;
1205         }
1206         else
1207         {
1208                 dest->startup_cost = 0;
1209                 dest->total_cost = 0;
1210                 dest->plan_rows = 0;
1211                 dest->plan_width = 0;
1212         }
1213 }
1214
1215 /*
1216  * Copy cost and size info from a lower plan node to an inserted node.
1217  * This is not critical, since the decisions have already been made,
1218  * but it helps produce more reasonable-looking EXPLAIN output.
1219  * (Some callers alter the info after copying it.)
1220  */
1221 static void
1222 copy_plan_costsize(Plan *dest, Plan *src)
1223 {
1224         if (src)
1225         {
1226                 dest->startup_cost = src->startup_cost;
1227                 dest->total_cost = src->total_cost;
1228                 dest->plan_rows = src->plan_rows;
1229                 dest->plan_width = src->plan_width;
1230         }
1231         else
1232         {
1233                 dest->startup_cost = 0;
1234                 dest->total_cost = 0;
1235                 dest->plan_rows = 0;
1236                 dest->plan_width = 0;
1237         }
1238 }
1239
1240
1241 /*****************************************************************************
1242  *
1243  *      PLAN NODE BUILDING ROUTINES
1244  *
1245  * Some of these are exported because they are called to build plan nodes
1246  * in contexts where we're not deriving the plan node from a path node.
1247  *
1248  *****************************************************************************/
1249
1250 static SeqScan *
1251 make_seqscan(List *qptlist,
1252                          List *qpqual,
1253                          Index scanrelid)
1254 {
1255         SeqScan    *node = makeNode(SeqScan);
1256         Plan       *plan = &node->plan;
1257
1258         /* cost should be inserted by caller */
1259         plan->state = (EState *) NULL;
1260         plan->targetlist = qptlist;
1261         plan->qual = qpqual;
1262         plan->lefttree = NULL;
1263         plan->righttree = NULL;
1264         node->scanrelid = scanrelid;
1265         node->scanstate = (CommonScanState *) NULL;
1266
1267         return node;
1268 }
1269
1270 static IndexScan *
1271 make_indexscan(List *qptlist,
1272                            List *qpqual,
1273                            Index scanrelid,
1274                            List *indxid,
1275                            List *indxqual,
1276                            List *indxqualorig,
1277                            ScanDirection indexscandir)
1278 {
1279         IndexScan  *node = makeNode(IndexScan);
1280         Plan       *plan = &node->scan.plan;
1281
1282         /* cost should be inserted by caller */
1283         plan->state = (EState *) NULL;
1284         plan->targetlist = qptlist;
1285         plan->qual = qpqual;
1286         plan->lefttree = NULL;
1287         plan->righttree = NULL;
1288         node->scan.scanrelid = scanrelid;
1289         node->indxid = indxid;
1290         node->indxqual = indxqual;
1291         node->indxqualorig = indxqualorig;
1292         node->indxorderdir = indexscandir;
1293         node->scan.scanstate = (CommonScanState *) NULL;
1294
1295         return node;
1296 }
1297
1298 static TidScan *
1299 make_tidscan(List *qptlist,
1300                          List *qpqual,
1301                          Index scanrelid,
1302                          List *tideval)
1303 {
1304         TidScan    *node = makeNode(TidScan);
1305         Plan       *plan = &node->scan.plan;
1306
1307         /* cost should be inserted by caller */
1308         plan->state = (EState *) NULL;
1309         plan->targetlist = qptlist;
1310         plan->qual = qpqual;
1311         plan->lefttree = NULL;
1312         plan->righttree = NULL;
1313         node->scan.scanrelid = scanrelid;
1314         node->tideval = copyObject(tideval);            /* XXX do we really need a
1315                                                                                                  * copy? */
1316         node->needRescan = false;
1317         node->scan.scanstate = (CommonScanState *) NULL;
1318
1319         return node;
1320 }
1321
1322 SubqueryScan *
1323 make_subqueryscan(List *qptlist,
1324                                   List *qpqual,
1325                                   Index scanrelid,
1326                                   Plan *subplan)
1327 {
1328         SubqueryScan *node = makeNode(SubqueryScan);
1329         Plan       *plan = &node->scan.plan;
1330
1331         copy_plan_costsize(plan, subplan);
1332         plan->state = (EState *) NULL;
1333         plan->targetlist = qptlist;
1334         plan->qual = qpqual;
1335         plan->lefttree = NULL;
1336         plan->righttree = NULL;
1337         node->scan.scanrelid = scanrelid;
1338         node->subplan = subplan;
1339         node->scan.scanstate = (CommonScanState *) NULL;
1340
1341         return node;
1342 }
1343
1344 static FunctionScan *
1345 make_functionscan(List *qptlist,
1346                                   List *qpqual,
1347                                   Index scanrelid)
1348 {
1349         FunctionScan   *node = makeNode(FunctionScan);
1350         Plan               *plan = &node->scan.plan;
1351
1352         /* cost should be inserted by caller */
1353         plan->state = (EState *) NULL;
1354         plan->targetlist = qptlist;
1355         plan->qual = qpqual;
1356         plan->lefttree = NULL;
1357         plan->righttree = NULL;
1358         node->scan.scanrelid = scanrelid;
1359         node->scan.scanstate = (CommonScanState *) NULL;
1360
1361         return node;
1362 }
1363
1364 Append *
1365 make_append(List *appendplans, bool isTarget, List *tlist)
1366 {
1367         Append     *node = makeNode(Append);
1368         Plan       *plan = &node->plan;
1369         List       *subnode;
1370
1371         /* compute costs from subplan costs */
1372         plan->startup_cost = 0;
1373         plan->total_cost = 0;
1374         plan->plan_rows = 0;
1375         plan->plan_width = 0;
1376         foreach(subnode, appendplans)
1377         {
1378                 Plan       *subplan = (Plan *) lfirst(subnode);
1379
1380                 if (subnode == appendplans)             /* first node? */
1381                         plan->startup_cost = subplan->startup_cost;
1382                 plan->total_cost += subplan->total_cost;
1383                 plan->plan_rows += subplan->plan_rows;
1384                 if (plan->plan_width < subplan->plan_width)
1385                         plan->plan_width = subplan->plan_width;
1386         }
1387         plan->state = (EState *) NULL;
1388         plan->targetlist = tlist;
1389         plan->qual = NIL;
1390         plan->lefttree = NULL;
1391         plan->righttree = NULL;
1392         node->appendplans = appendplans;
1393         node->isTarget = isTarget;
1394
1395         return node;
1396 }
1397
1398 static NestLoop *
1399 make_nestloop(List *tlist,
1400                           List *joinclauses,
1401                           List *otherclauses,
1402                           Plan *lefttree,
1403                           Plan *righttree,
1404                           JoinType jointype)
1405 {
1406         NestLoop   *node = makeNode(NestLoop);
1407         Plan       *plan = &node->join.plan;
1408
1409         /* cost should be inserted by caller */
1410         plan->state = (EState *) NULL;
1411         plan->targetlist = tlist;
1412         plan->qual = otherclauses;
1413         plan->lefttree = lefttree;
1414         plan->righttree = righttree;
1415         node->join.jointype = jointype;
1416         node->join.joinqual = joinclauses;
1417
1418         return node;
1419 }
1420
1421 static HashJoin *
1422 make_hashjoin(List *tlist,
1423                           List *joinclauses,
1424                           List *otherclauses,
1425                           List *hashclauses,
1426                           Plan *lefttree,
1427                           Plan *righttree,
1428                           JoinType jointype)
1429 {
1430         HashJoin   *node = makeNode(HashJoin);
1431         Plan       *plan = &node->join.plan;
1432
1433         /* cost should be inserted by caller */
1434         plan->state = (EState *) NULL;
1435         plan->targetlist = tlist;
1436         plan->qual = otherclauses;
1437         plan->lefttree = lefttree;
1438         plan->righttree = righttree;
1439         node->hashclauses = hashclauses;
1440         node->join.jointype = jointype;
1441         node->join.joinqual = joinclauses;
1442
1443         return node;
1444 }
1445
1446 static Hash *
1447 make_hash(List *tlist, Node *hashkey, Plan *lefttree)
1448 {
1449         Hash       *node = makeNode(Hash);
1450         Plan       *plan = &node->plan;
1451
1452         copy_plan_costsize(plan, lefttree);
1453
1454         /*
1455          * For plausibility, make startup & total costs equal total cost of
1456          * input plan; this only affects EXPLAIN display not decisions.
1457          */
1458         plan->startup_cost = plan->total_cost;
1459         plan->state = (EState *) NULL;
1460         plan->targetlist = tlist;
1461         plan->qual = NULL;
1462         plan->lefttree = lefttree;
1463         plan->righttree = NULL;
1464         node->hashkey = hashkey;
1465
1466         return node;
1467 }
1468
1469 static MergeJoin *
1470 make_mergejoin(List *tlist,
1471                            List *joinclauses,
1472                            List *otherclauses,
1473                            List *mergeclauses,
1474                            Plan *lefttree,
1475                            Plan *righttree,
1476                            JoinType jointype)
1477 {
1478         MergeJoin  *node = makeNode(MergeJoin);
1479         Plan       *plan = &node->join.plan;
1480
1481         /* cost should be inserted by caller */
1482         plan->state = (EState *) NULL;
1483         plan->targetlist = tlist;
1484         plan->qual = otherclauses;
1485         plan->lefttree = lefttree;
1486         plan->righttree = righttree;
1487         node->mergeclauses = mergeclauses;
1488         node->join.jointype = jointype;
1489         node->join.joinqual = joinclauses;
1490
1491         return node;
1492 }
1493
1494 /*
1495  * To use make_sort directly, you must already have marked the tlist
1496  * with reskey and reskeyop information.  The keys had better be
1497  * non-redundant, too (ie, there had better be tlist items marked with
1498  * each key number from 1 to keycount), or the executor will get confused!
1499  */
1500 Sort *
1501 make_sort(Query *root, List *tlist, Plan *lefttree, int keycount)
1502 {
1503         Sort       *node = makeNode(Sort);
1504         Plan       *plan = &node->plan;
1505         Path            sort_path;              /* dummy for result of cost_sort */
1506
1507         copy_plan_costsize(plan, lefttree); /* only care about copying size */
1508         cost_sort(&sort_path, root, NIL,
1509                           lefttree->plan_rows, lefttree->plan_width);
1510         plan->startup_cost = sort_path.startup_cost + lefttree->total_cost;
1511         plan->total_cost = sort_path.total_cost + lefttree->total_cost;
1512         plan->state = (EState *) NULL;
1513         plan->targetlist = tlist;
1514         plan->qual = NIL;
1515         plan->lefttree = lefttree;
1516         plan->righttree = NULL;
1517         node->keycount = keycount;
1518
1519         return node;
1520 }
1521
1522 /*
1523  * make_sort_from_pathkeys
1524  *        Create sort plan to sort according to given pathkeys
1525  *
1526  *        'tlist' is the target list of the input plan
1527  *        'lefttree' is the node which yields input tuples
1528  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
1529  *
1530  * We must convert the pathkey information into reskey and reskeyop fields
1531  * of resdom nodes in the sort plan's target list.
1532  */
1533 Sort *
1534 make_sort_from_pathkeys(Query *root, List *tlist,
1535                                                 Plan *lefttree, List *pathkeys)
1536 {
1537         List       *sort_tlist;
1538         List       *i;
1539         int                     numsortkeys = 0;
1540
1541         /* Create a new target list for the sort, with sort keys set. */
1542         sort_tlist = new_unsorted_tlist(tlist);
1543
1544         foreach(i, pathkeys)
1545         {
1546                 List       *keysublist = (List *) lfirst(i);
1547                 PathKeyItem *pathkey = NULL;
1548                 Resdom     *resdom = NULL;
1549                 List       *j;
1550
1551                 /*
1552                  * We can sort by any one of the sort key items listed in this
1553                  * sublist.  For now, we take the first one that corresponds to an
1554                  * available Var in the sort_tlist.
1555                  *
1556                  * XXX if we have a choice, is there any way of figuring out which
1557                  * might be cheapest to execute?  (For example, int4lt is likely
1558                  * much cheaper to execute than numericlt, but both might appear
1559                  * in the same pathkey sublist...)      Not clear that we ever will
1560                  * have a choice in practice, so it may not matter.
1561                  */
1562                 foreach(j, keysublist)
1563                 {
1564                         pathkey = lfirst(j);
1565                         Assert(IsA(pathkey, PathKeyItem));
1566                         resdom = tlist_member(pathkey->key, sort_tlist);
1567                         if (resdom)
1568                                 break;
1569                 }
1570                 if (!resdom)
1571                         elog(ERROR, "make_sort_from_pathkeys: cannot find tlist item to sort");
1572
1573                 /*
1574                  * The resdom might be already marked as a sort key, if the
1575                  * pathkeys contain duplicate entries.  (This can happen in
1576                  * scenarios where multiple mergejoinable clauses mention the same
1577                  * var, for example.) In that case the current pathkey is
1578                  * essentially a no-op, because only one value can be seen within
1579                  * any subgroup where it would be consulted.  We can ignore it.
1580                  */
1581                 if (resdom->reskey == 0)
1582                 {
1583                         /* OK, mark it as a sort key and set the sort operator */
1584                         resdom->reskey = ++numsortkeys;
1585                         resdom->reskeyop = pathkey->sortop;
1586                 }
1587         }
1588
1589         Assert(numsortkeys > 0);
1590
1591         return make_sort(root, sort_tlist, lefttree, numsortkeys);
1592 }
1593
1594 Material *
1595 make_material(List *tlist, Plan *lefttree)
1596 {
1597         Material   *node = makeNode(Material);
1598         Plan       *plan = &node->plan;
1599
1600         copy_plan_costsize(plan, lefttree);
1601
1602         /*
1603          * For plausibility, make startup & total costs equal total cost of
1604          * input plan; this only affects EXPLAIN display not decisions.
1605          *
1606          * XXX shouldn't we charge some additional cost for materialization?
1607          */
1608         plan->startup_cost = plan->total_cost;
1609         plan->state = (EState *) NULL;
1610         plan->targetlist = tlist;
1611         plan->qual = NIL;
1612         plan->lefttree = lefttree;
1613         plan->righttree = NULL;
1614
1615         return node;
1616 }
1617
1618 Agg *
1619 make_agg(List *tlist, List *qual, Plan *lefttree)
1620 {
1621         Agg                *node = makeNode(Agg);
1622         Plan       *plan = &node->plan;
1623
1624         copy_plan_costsize(plan, lefttree);
1625
1626         /*
1627          * Charge one cpu_operator_cost per aggregate function per input
1628          * tuple.
1629          */
1630         plan->total_cost += cpu_operator_cost * plan->plan_rows *
1631                 (length(pull_agg_clause((Node *) tlist)) +
1632                  length(pull_agg_clause((Node *) qual)));
1633
1634         /*
1635          * We will produce a single output tuple if the input is not a Group,
1636          * and a tuple per group otherwise.  For now, estimate the number of
1637          * groups as 10% of the number of tuples --- bogus, but how to do
1638          * better? (Note we assume the input Group node is in "tuplePerGroup"
1639          * mode, so it didn't reduce its row count already.)
1640          */
1641         if (IsA(lefttree, Group))
1642         {
1643                 plan->plan_rows *= 0.1;
1644                 if (plan->plan_rows < 1)
1645                         plan->plan_rows = 1;
1646         }
1647         else
1648         {
1649                 plan->plan_rows = 1;
1650                 plan->startup_cost = plan->total_cost;
1651         }
1652
1653         plan->state = (EState *) NULL;
1654         plan->qual = qual;
1655         plan->targetlist = tlist;
1656         plan->lefttree = lefttree;
1657         plan->righttree = (Plan *) NULL;
1658
1659         return node;
1660 }
1661
1662 Group *
1663 make_group(List *tlist,
1664                    bool tuplePerGroup,
1665                    int ngrp,
1666                    AttrNumber *grpColIdx,
1667                    Plan *lefttree)
1668 {
1669         Group      *node = makeNode(Group);
1670         Plan       *plan = &node->plan;
1671
1672         copy_plan_costsize(plan, lefttree);
1673
1674         /*
1675          * Charge one cpu_operator_cost per comparison per input tuple. We
1676          * assume all columns get compared at most of the tuples.
1677          */
1678         plan->total_cost += cpu_operator_cost * plan->plan_rows * ngrp;
1679
1680         /*
1681          * If tuplePerGroup (which is named exactly backwards) is true, we
1682          * will return all the input tuples, so the input node's row count is
1683          * OK.  Otherwise, we'll return only one tuple from each group. For
1684          * now, estimate the number of groups as 10% of the number of tuples
1685          * --- bogus, but how to do better?
1686          */
1687         if (!tuplePerGroup)
1688         {
1689                 plan->plan_rows *= 0.1;
1690                 if (plan->plan_rows < 1)
1691                         plan->plan_rows = 1;
1692         }
1693
1694         plan->state = (EState *) NULL;
1695         plan->qual = NULL;
1696         plan->targetlist = tlist;
1697         plan->lefttree = lefttree;
1698         plan->righttree = (Plan *) NULL;
1699         node->tuplePerGroup = tuplePerGroup;
1700         node->numCols = ngrp;
1701         node->grpColIdx = grpColIdx;
1702
1703         return node;
1704 }
1705
1706 /*
1707  * distinctList is a list of SortClauses, identifying the targetlist items
1708  * that should be considered by the Unique filter.
1709  */
1710
1711 Unique *
1712 make_unique(List *tlist, Plan *lefttree, List *distinctList)
1713 {
1714         Unique     *node = makeNode(Unique);
1715         Plan       *plan = &node->plan;
1716         int                     numCols = length(distinctList);
1717         int                     keyno = 0;
1718         AttrNumber *uniqColIdx;
1719         List       *slitem;
1720
1721         copy_plan_costsize(plan, lefttree);
1722
1723         /*
1724          * Charge one cpu_operator_cost per comparison per input tuple. We
1725          * assume all columns get compared at most of the tuples.
1726          */
1727         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
1728
1729         /*
1730          * As for Group, we make the unsupported assumption that there will be
1731          * 10% as many tuples out as in.
1732          */
1733         plan->plan_rows *= 0.1;
1734         if (plan->plan_rows < 1)
1735                 plan->plan_rows = 1;
1736
1737         plan->state = (EState *) NULL;
1738         plan->targetlist = tlist;
1739         plan->qual = NIL;
1740         plan->lefttree = lefttree;
1741         plan->righttree = NULL;
1742
1743         /*
1744          * convert SortClause list into array of attr indexes, as wanted by
1745          * exec
1746          */
1747         Assert(numCols > 0);
1748         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
1749
1750         foreach(slitem, distinctList)
1751         {
1752                 SortClause *sortcl = (SortClause *) lfirst(slitem);
1753                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, tlist);
1754
1755                 uniqColIdx[keyno++] = tle->resdom->resno;
1756         }
1757
1758         node->numCols = numCols;
1759         node->uniqColIdx = uniqColIdx;
1760
1761         return node;
1762 }
1763
1764 /*
1765  * distinctList is a list of SortClauses, identifying the targetlist items
1766  * that should be considered by the SetOp filter.
1767  */
1768
1769 SetOp *
1770 make_setop(SetOpCmd cmd, List *tlist, Plan *lefttree,
1771                    List *distinctList, AttrNumber flagColIdx)
1772 {
1773         SetOp      *node = makeNode(SetOp);
1774         Plan       *plan = &node->plan;
1775         int                     numCols = length(distinctList);
1776         int                     keyno = 0;
1777         AttrNumber *dupColIdx;
1778         List       *slitem;
1779
1780         copy_plan_costsize(plan, lefttree);
1781
1782         /*
1783          * Charge one cpu_operator_cost per comparison per input tuple. We
1784          * assume all columns get compared at most of the tuples.
1785          */
1786         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
1787
1788         /*
1789          * As for Group, we make the unsupported assumption that there will be
1790          * 10% as many tuples out as in.
1791          */
1792         plan->plan_rows *= 0.1;
1793         if (plan->plan_rows < 1)
1794                 plan->plan_rows = 1;
1795
1796         plan->state = (EState *) NULL;
1797         plan->targetlist = tlist;
1798         plan->qual = NIL;
1799         plan->lefttree = lefttree;
1800         plan->righttree = NULL;
1801
1802         /*
1803          * convert SortClause list into array of attr indexes, as wanted by
1804          * exec
1805          */
1806         Assert(numCols > 0);
1807         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
1808
1809         foreach(slitem, distinctList)
1810         {
1811                 SortClause *sortcl = (SortClause *) lfirst(slitem);
1812                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, tlist);
1813
1814                 dupColIdx[keyno++] = tle->resdom->resno;
1815         }
1816
1817         node->cmd = cmd;
1818         node->numCols = numCols;
1819         node->dupColIdx = dupColIdx;
1820         node->flagColIdx = flagColIdx;
1821
1822         return node;
1823 }
1824
1825 Limit *
1826 make_limit(List *tlist, Plan *lefttree,
1827                    Node *limitOffset, Node *limitCount)
1828 {
1829         Limit      *node = makeNode(Limit);
1830         Plan       *plan = &node->plan;
1831
1832         copy_plan_costsize(plan, lefttree);
1833
1834         /*
1835          * If offset/count are constants, adjust the output rows count and
1836          * costs accordingly.  This is only a cosmetic issue if we are at top
1837          * level, but if we are building a subquery then it's important to
1838          * report correct info to the outer planner.
1839          */
1840         if (limitOffset && IsA(limitOffset, Const))
1841         {
1842                 Const      *limito = (Const *) limitOffset;
1843                 int32           offset = DatumGetInt32(limito->constvalue);
1844
1845                 if (!limito->constisnull && offset > 0)
1846                 {
1847                         if (offset > plan->plan_rows)
1848                                 offset = (int32) plan->plan_rows;
1849                         if (plan->plan_rows > 0)
1850                                 plan->startup_cost +=
1851                                         (plan->total_cost - plan->startup_cost)
1852                                         * ((double) offset) / plan->plan_rows;
1853                         plan->plan_rows -= offset;
1854                         if (plan->plan_rows < 1)
1855                                 plan->plan_rows = 1;
1856                 }
1857         }
1858         if (limitCount && IsA(limitCount, Const))
1859         {
1860                 Const      *limitc = (Const *) limitCount;
1861                 int32           count = DatumGetInt32(limitc->constvalue);
1862
1863                 if (!limitc->constisnull && count >= 0)
1864                 {
1865                         if (count > plan->plan_rows)
1866                                 count = (int32) plan->plan_rows;
1867                         if (plan->plan_rows > 0)
1868                                 plan->total_cost = plan->startup_cost +
1869                                         (plan->total_cost - plan->startup_cost)
1870                                         * ((double) count) / plan->plan_rows;
1871                         plan->plan_rows = count;
1872                         if (plan->plan_rows < 1)
1873                                 plan->plan_rows = 1;
1874                 }
1875         }
1876
1877         plan->state = (EState *) NULL;
1878         plan->targetlist = tlist;
1879         plan->qual = NIL;
1880         plan->lefttree = lefttree;
1881         plan->righttree = NULL;
1882
1883         node->limitOffset = limitOffset;
1884         node->limitCount = limitCount;
1885
1886         return node;
1887 }
1888
1889 Result *
1890 make_result(List *tlist,
1891                         Node *resconstantqual,
1892                         Plan *subplan)
1893 {
1894         Result     *node = makeNode(Result);
1895         Plan       *plan = &node->plan;
1896
1897 #ifdef NOT_USED
1898         tlist = generate_fjoin(tlist);
1899 #endif
1900         if (subplan)
1901                 copy_plan_costsize(plan, subplan);
1902         else
1903         {
1904                 plan->startup_cost = 0;
1905                 plan->total_cost = cpu_tuple_cost;
1906                 plan->plan_rows = 1;    /* wrong if we have a set-valued function? */
1907                 plan->plan_width = 0;   /* XXX try to be smarter? */
1908         }
1909
1910         plan->state = (EState *) NULL;
1911         plan->targetlist = tlist;
1912         plan->qual = NIL;
1913         plan->lefttree = subplan;
1914         plan->righttree = NULL;
1915         node->resconstantqual = resconstantqual;
1916         node->resstate = NULL;
1917
1918         return node;
1919 }
1920
1921 #ifdef NOT_USED
1922 List *
1923 generate_fjoin(List *tlist)
1924 {
1925         List            tlistP;
1926         List            newTlist = NIL;
1927         List            fjoinList = NIL;
1928         int                     nIters = 0;
1929
1930         /*
1931          * Break the target list into elements with Iter nodes, and those
1932          * without them.
1933          */
1934         foreach(tlistP, tlist)
1935         {
1936                 List            tlistElem;
1937
1938                 tlistElem = lfirst(tlistP);
1939                 if (IsA(lsecond(tlistElem), Iter))
1940                 {
1941                         nIters++;
1942                         fjoinList = lappend(fjoinList, tlistElem);
1943                 }
1944                 else
1945                         newTlist = lappend(newTlist, tlistElem);
1946         }
1947
1948         /*
1949          * if we have an Iter node then we need to flatten.
1950          */
1951         if (nIters > 0)
1952         {
1953                 List       *inner;
1954                 List       *tempList;
1955                 Fjoin      *fjoinNode;
1956                 DatumPtr        results = (DatumPtr) palloc(nIters * sizeof(Datum));
1957                 BoolPtr         alwaysDone = (BoolPtr) palloc(nIters * sizeof(bool));
1958
1959                 inner = lfirst(fjoinList);
1960                 fjoinList = lnext(fjoinList);
1961                 fjoinNode = (Fjoin) MakeFjoin(false,
1962                                                                           nIters,
1963                                                                           inner,
1964                                                                           results,
1965                                                                           alwaysDone);
1966                 tempList = lcons(fjoinNode, fjoinList);
1967                 newTlist = lappend(newTlist, tempList);
1968         }
1969         return newTlist;
1970         return tlist;                           /* do nothing for now - ay 10/94 */
1971 }
1972
1973 #endif