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