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.103 2001/01/24 19:42:58 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 "mark"
 741          * and "restore" operations.  Not all plan types do, so we must be careful
 742          * not to generate an invalid plan.  If necessary, an invalid inner plan
 743          * can be handled by inserting a Materialize node.
 744          *
 745          * Since the inner side must be ordered, and only Sorts and IndexScans can
 746          * create order to begin with, you might think there's no problem --- but
 747          * you'd be wrong.  Nestloop and merge joins can *preserve* the order of
 748          * their inputs, so they can be selected as the input of a mergejoin,
 749          * 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 Materialize
 753          * is hard to estimate a cost for, and the above consideration shows that
 754          * this is a rare case anyway, so this seems an acceptable way to proceed.
 755          *
 756          * This check must agree with ExecMarkPos/ExecRestrPos in
 757          * executor/execAmi.c!
 758          */
 759         switch (nodeTag(inner_plan))
 760         {
 761                 case T_SeqScan:
 762                 case T_IndexScan:
 763                 case T_Material:
 764                 case T_Sort:
 765                         /* OK, these inner plans support mark/restore */
 766                         break;
 767
 768                 default:
 769                         /* Ooops, need to materialize the inner plan */
 770                         inner_plan = (Plan *) make_material(inner_tlist,
 771                                                                                                 inner_plan);
 772                         break;
 773         }
 774
 775         /*
 776          * Now we can build the mergejoin node.
 777          */
 778         join_plan = make_mergejoin(tlist,
 779                                                            joinclauses,
 780                                                            otherclauses,
 781                                                            mergeclauses,
 782                                                            outer_plan,
 783                                                            inner_plan,
 784                                                            best_path->jpath.jointype);
 785
 786         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
 787
 788         return join_plan;
 789 }
 790
 791 static HashJoin *
 792 create_hashjoin_plan(HashPath *best_path,
 793                                          List *tlist,
 794                                          List *joinclauses,
 795                                          List *otherclauses,
 796                                          Plan *outer_plan,
 797                                          List *outer_tlist,
 798                                          Plan *inner_plan,
 799                                          List *inner_tlist)
 800 {
 801         List       *hashclauses;
 802         HashJoin   *join_plan;
 803         Hash       *hash_plan;
 804         Node       *innerhashkey;
 805
 806         /*
 807          * NOTE: there will always be exactly one hashclause in the list
 808          * best_path->path_hashclauses (cf. hash_inner_and_outer()). We
 809          * represent it as a list anyway, for convenience with routines that
 810          * want to work on lists of clauses.
 811          */
 812         hashclauses = get_actual_clauses(best_path->path_hashclauses);
 813
 814         /*
 815          * Remove the hashclauses from the list of join qual clauses, leaving
 816          * the list of quals that must be checked as qpquals. Set those
 817          * clauses to contain INNER/OUTER var references.
 818          */
 819         joinclauses = join_references(set_difference(joinclauses, hashclauses),
 820                                                                   outer_tlist,
 821                                                                   inner_tlist,
 822                                                                   (Index) 0);
 823
 824         /*
 825          * Fix the additional qpquals too.
 826          */
 827         otherclauses = join_references(otherclauses,
 828                                                                    outer_tlist,
 829                                                                    inner_tlist,
 830                                                                    (Index) 0);
 831
 832         /*
 833          * Now set the references in the hashclauses and rearrange them so
 834          * that the outer variable is always on the left.
 835          */
 836         hashclauses = switch_outer(join_references(hashclauses,
 837                                                                                            outer_tlist,
 838                                                                                            inner_tlist,
 839                                                                                            (Index) 0));
 840
 841         /* Now the righthand op of the sole hashclause is the inner hash key. */
 842         innerhashkey = (Node *) get_rightop(lfirst(hashclauses));
 843
 844         /*
 845          * Build the hash node and hash join node.
 846          */
 847         hash_plan = make_hash(inner_tlist, innerhashkey, inner_plan);
 848         join_plan = make_hashjoin(tlist,
 849                                                           joinclauses,
 850                                                           otherclauses,
 851                                                           hashclauses,
 852                                                           outer_plan,
 853                                                           (Plan *) hash_plan,
 854                                                           best_path->jpath.jointype);
 855
 856         copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path);
 857
 858         return join_plan;
 859 }
 860
 861
 862 /*****************************************************************************
 863  *
 864  *      SUPPORTING ROUTINES
 865  *
 866  *****************************************************************************/
 867
 868 /*
 869  * fix_indxqual_references
 870  *        Adjust indexqual clauses to the form the executor's indexqual
 871  *        machinery needs.
 872  *
 873  * We have three tasks here:
 874  *      * Index keys must be represented by Var nodes with varattno set to the
 875  *        index's attribute number, not the attribute number in the original rel.
 876  *      * indxpath.c may have selected an index that is binary-compatible with
 877  *        the actual expression operator, but not exactly the same datatype.
 878  *        We must replace the expression's operator with the binary-compatible
 879  *        equivalent operator that the index will recognize.
 880  *      * If the index key is on the right, commute the clause to put it on the
 881  *        left.  (Someday the executor might not need this, but for now it does.)
 882  *
 883  * This code used to be entirely bogus for multi-index scans.  Now it keeps
 884  * track of which index applies to each subgroup of index qual clauses...
 885  *
 886  * Returns a modified copy of the indexqual list --- the original is not
 887  * changed.  Note also that the copy shares no substructure with the
 888  * original; this is needed in case there is a subplan in it (we need
 889  * two separate copies of the subplan tree, or things will go awry).
 890  */
 891
 892 static List *
 893 fix_indxqual_references(List *indexquals, IndexPath *index_path)
 894 {
 895         List       *fixed_quals = NIL;
 896         int                     baserelid = lfirsti(index_path->path.parent->relids);
 897         List       *indexids = index_path->indexid;
 898         List       *i;
 899
 900         foreach(i, indexquals)
 901         {
 902                 List       *indexqual = lfirst(i);
 903                 Oid                     indexid = lfirsti(indexids);
 904                 HeapTuple       indexTuple;
 905                 Oid                     relam;
 906                 Form_pg_index index;
 907
 908                 /* Get the relam from the index's pg_class entry */
 909                 indexTuple = SearchSysCache(RELOID,
 910                                                                         ObjectIdGetDatum(indexid),
 911                                                                         0, 0, 0);
 912                 if (!HeapTupleIsValid(indexTuple))
 913                         elog(ERROR, "fix_indxqual_references: index %u not found in pg_class",
 914                                  indexid);
 915                 relam = ((Form_pg_class) GETSTRUCT(indexTuple))->relam;
 916                 ReleaseSysCache(indexTuple);
 917
 918                 /* Need the index's pg_index entry for other stuff */
 919                 indexTuple = SearchSysCache(INDEXRELID,
 920                                                                         ObjectIdGetDatum(indexid),
 921                                                                         0, 0, 0);
 922                 if (!HeapTupleIsValid(indexTuple))
 923                         elog(ERROR, "fix_indxqual_references: index %u not found in pg_index",
 924                                  indexid);
 925                 index = (Form_pg_index) GETSTRUCT(indexTuple);
 926
 927                 fixed_quals = lappend(fixed_quals,
 928                                                           fix_indxqual_sublist(indexqual,
 929                                                                                                    baserelid,
 930                                                                                                    relam,
 931                                                                                                    index));
 932
 933                 ReleaseSysCache(indexTuple);
 934
 935                 indexids = lnext(indexids);
 936         }
 937         return fixed_quals;
 938 }
 939
 940 /*
 941  * Fix the sublist of indexquals to be used in a particular scan.
 942  *
 943  * For each qual clause, commute if needed to put the indexkey operand on the
 944  * left, and then fix its varattno.  (We do not need to change the other side
 945  * of the clause.)      Also change the operator if necessary.
 946  */
 947 static List *
 948 fix_indxqual_sublist(List *indexqual, int baserelid, Oid relam,
 949                                          Form_pg_index index)
 950 {
 951         List       *fixed_qual = NIL;
 952         List       *i;
 953
 954         foreach(i, indexqual)
 955         {
 956                 Expr       *clause = (Expr *) lfirst(i);
 957                 int                     relid;
 958                 AttrNumber      attno;
 959                 Datum           constval;
 960                 int                     flag;
 961                 Expr       *newclause;
 962                 Oid                     opclass,
 963                                         newopno;
 964
 965                 if (!is_opclause((Node *) clause) ||
 966                         length(clause->args) != 2)
 967                         elog(ERROR, "fix_indxqual_sublist: indexqual clause is not binary opclause");
 968
 969                 /*
 970                  * Which side is the indexkey on?
 971                  *
 972                  * get_relattval sets flag&SEL_RIGHT if the indexkey is on the LEFT.
 973                  */
 974                 get_relattval((Node *) clause, baserelid,
 975                                           &relid, &attno, &constval, &flag);
 976
 977                 /*
 978                  * Make a copy that will become the fixed clause.
 979                  *
 980                  * We used to try to do a shallow copy here, but that fails if there
 981                  * is a subplan in the arguments of the opclause.  So just do a
 982                  * full copy.
 983                  */
 984                 newclause = (Expr *) copyObject((Node *) clause);
 985
 986                 /* If the indexkey is on the right, commute the clause. */
 987                 if ((flag & SEL_RIGHT) == 0)
 988                         CommuteClause(newclause);
 989
 990                 /*
 991                  * Now, determine which index attribute this is, change the
 992                  * indexkey operand as needed, and get the index opclass.
 993                  */
 994                 lfirst(newclause->args) = fix_indxqual_operand(lfirst(newclause->args),
 995                                                                                                            baserelid,
 996                                                                                                            index,
 997                                                                                                            &opclass);
 998
 999                 /*
1000                  * Substitute the appropriate operator if the expression operator
1001                  * is merely binary-compatible with the index.  This shouldn't
1002                  * fail, since indxpath.c found it before...
1003                  */
1004                 newopno = indexable_operator(newclause, opclass, relam, true);
1005                 if (newopno == InvalidOid)
1006                         elog(ERROR, "fix_indxqual_sublist: failed to find substitute op");
1007                 ((Oper *) newclause->oper)->opno = newopno;
1008
1009                 fixed_qual = lappend(fixed_qual, newclause);
1010         }
1011         return fixed_qual;
1012 }
1013
1014 static Node *
1015 fix_indxqual_operand(Node *node, int baserelid, Form_pg_index index,
1016                                          Oid *opclass)
1017 {
1018         /*
1019          * Remove any binary-compatible relabeling of the indexkey
1020          */
1021         if (IsA(node, RelabelType))
1022                 node = ((RelabelType *) node)->arg;
1023
1024         /*
1025          * We represent index keys by Var nodes having the varno of the base
1026          * table but varattno equal to the index's attribute number (index
1027          * column position).  This is a bit hokey ... would be cleaner to use
1028          * a special-purpose node type that could not be mistaken for a regular
1029          * Var.  But it will do for now.
1030          */
1031         if (IsA(node, Var))
1032         {
1033                 /* If it's a var, find which index key position it occupies */
1034                 if (((Var *) node)->varno == baserelid)
1035                 {
1036                         int                     varatt = ((Var *) node)->varattno;
1037                         int                     pos;
1038
1039                         for (pos = 0; pos < INDEX_MAX_KEYS; pos++)
1040                         {
1041                                 if (index->indkey[pos] == varatt)
1042                                 {
1043                                         Node       *newnode = copyObject(node);
1044
1045                                         ((Var *) newnode)->varattno = pos + 1;
1046                                         /* return the correct opclass, too */
1047                                         *opclass = index->indclass[pos];
1048                                         return newnode;
1049                                 }
1050                         }
1051                 }
1052
1053                 /*
1054                  * Oops, this Var isn't the indexkey!
1055                  */
1056                 elog(ERROR, "fix_indxqual_operand: var is not index attribute");
1057         }
1058
1059         /*
1060          * Else, it must be a func expression matching a functional index.
1061          * Since we currently only support single-column functional indexes,
1062          * the returned varattno must be 1.
1063          */
1064
1065         Assert(is_funcclause(node)); /* not a very thorough check, but easy */
1066
1067         /* indclass[0] is the only class of a functional index */
1068         *opclass = index->indclass[0];
1069
1070         return (Node *) makeVar(baserelid, 1, exprType(node), -1, 0);
1071 }
1072
1073 /*
1074  * switch_outer
1075  *        Given a list of merge or hash joinclauses, rearrange the elements within
1076  *        the clauses so the outer join variable is on the left and the inner is
1077  *        on the right.  The original list is not touched; a modified list
1078  *        is returned.
1079  */
1080 static List *
1081 switch_outer(List *clauses)
1082 {
1083         List       *t_list = NIL;
1084         List       *i;
1085
1086         foreach(i, clauses)
1087         {
1088                 Expr       *clause = (Expr *) lfirst(i);
1089                 Var                *op;
1090
1091                 Assert(is_opclause((Node *) clause));
1092                 op = get_rightop(clause);
1093                 Assert(op && IsA(op, Var));
1094                 if (var_is_outer(op))
1095                 {
1096
1097                         /*
1098                          * Duplicate just enough of the structure to allow commuting
1099                          * the clause without changing the original list.  Could use
1100                          * copyObject, but a complete deep copy is overkill.
1101                          */
1102                         Expr       *temp;
1103
1104                         temp = make_clause(clause->opType, clause->oper,
1105                                                            listCopy(clause->args));
1106                         /* Commute it --- note this modifies the temp node in-place. */
1107                         CommuteClause(temp);
1108                         t_list = lappend(t_list, temp);
1109                 }
1110                 else
1111                         t_list = lappend(t_list, clause);
1112         }
1113         return t_list;
1114 }
1115
1116 /*
1117  * Copy cost and size info from a Path node to the Plan node created from it.
1118  * The executor won't use this info, but it's needed by EXPLAIN.
1119  */
1120 static void
1121 copy_path_costsize(Plan *dest, Path *src)
1122 {
1123         if (src)
1124         {
1125                 dest->startup_cost = src->startup_cost;
1126                 dest->total_cost = src->total_cost;
1127                 dest->plan_rows = src->parent->rows;
1128                 dest->plan_width = src->parent->width;
1129         }
1130         else
1131         {
1132                 dest->startup_cost = 0;
1133                 dest->total_cost = 0;
1134                 dest->plan_rows = 0;
1135                 dest->plan_width = 0;
1136         }
1137 }
1138
1139 /*
1140  * Copy cost and size info from a lower plan node to an inserted node.
1141  * This is not critical, since the decisions have already been made,
1142  * but it helps produce more reasonable-looking EXPLAIN output.
1143  * (Some callers alter the info after copying it.)
1144  */
1145 static void
1146 copy_plan_costsize(Plan *dest, Plan *src)
1147 {
1148         if (src)
1149         {
1150                 dest->startup_cost = src->startup_cost;
1151                 dest->total_cost = src->total_cost;
1152                 dest->plan_rows = src->plan_rows;
1153                 dest->plan_width = src->plan_width;
1154         }
1155         else
1156         {
1157                 dest->startup_cost = 0;
1158                 dest->total_cost = 0;
1159                 dest->plan_rows = 0;
1160                 dest->plan_width = 0;
1161         }
1162 }
1163
1164
1165 /*****************************************************************************
1166  *
1167  *      PLAN NODE BUILDING ROUTINES
1168  *
1169  * Some of these are exported because they are called to build plan nodes
1170  * in contexts where we're not deriving the plan node from a path node.
1171  *
1172  *****************************************************************************/
1173
1174 static SeqScan *
1175 make_seqscan(List *qptlist,
1176                          List *qpqual,
1177                          Index scanrelid)
1178 {
1179         SeqScan    *node = makeNode(SeqScan);
1180         Plan       *plan = &node->plan;
1181
1182         /* cost should be inserted by caller */
1183         plan->state = (EState *) NULL;
1184         plan->targetlist = qptlist;
1185         plan->qual = qpqual;
1186         plan->lefttree = NULL;
1187         plan->righttree = NULL;
1188         node->scanrelid = scanrelid;
1189         node->scanstate = (CommonScanState *) NULL;
1190
1191         return node;
1192 }
1193
1194 static IndexScan *
1195 make_indexscan(List *qptlist,
1196                            List *qpqual,
1197                            Index scanrelid,
1198                            List *indxid,
1199                            List *indxqual,
1200                            List *indxqualorig,
1201                            ScanDirection indexscandir)
1202 {
1203         IndexScan  *node = makeNode(IndexScan);
1204         Plan       *plan = &node->scan.plan;
1205
1206         /* cost should be inserted by caller */
1207         plan->state = (EState *) NULL;
1208         plan->targetlist = qptlist;
1209         plan->qual = qpqual;
1210         plan->lefttree = NULL;
1211         plan->righttree = NULL;
1212         node->scan.scanrelid = scanrelid;
1213         node->indxid = indxid;
1214         node->indxqual = indxqual;
1215         node->indxqualorig = indxqualorig;
1216         node->indxorderdir = indexscandir;
1217         node->scan.scanstate = (CommonScanState *) NULL;
1218
1219         return node;
1220 }
1221
1222 static TidScan *
1223 make_tidscan(List *qptlist,
1224                          List *qpqual,
1225                          Index scanrelid,
1226                          List *tideval)
1227 {
1228         TidScan    *node = makeNode(TidScan);
1229         Plan       *plan = &node->scan.plan;
1230
1231         /* cost should be inserted by caller */
1232         plan->state = (EState *) NULL;
1233         plan->targetlist = qptlist;
1234         plan->qual = qpqual;
1235         plan->lefttree = NULL;
1236         plan->righttree = NULL;
1237         node->scan.scanrelid = scanrelid;
1238         node->tideval = copyObject(tideval);            /* XXX do we really need a
1239                                                                                                  * copy? */
1240         node->needRescan = false;
1241         node->scan.scanstate = (CommonScanState *) NULL;
1242
1243         return node;
1244 }
1245
1246 SubqueryScan *
1247 make_subqueryscan(List *qptlist,
1248                                   List *qpqual,
1249                                   Index scanrelid,
1250                                   Plan *subplan)
1251 {
1252         SubqueryScan *node = makeNode(SubqueryScan);
1253         Plan       *plan = &node->scan.plan;
1254
1255         copy_plan_costsize(plan, subplan);
1256         plan->state = (EState *) NULL;
1257         plan->targetlist = qptlist;
1258         plan->qual = qpqual;
1259         plan->lefttree = NULL;
1260         plan->righttree = NULL;
1261         node->scan.scanrelid = scanrelid;
1262         node->subplan = subplan;
1263         node->scan.scanstate = (CommonScanState *) NULL;
1264
1265         return node;
1266 }
1267
1268 Append *
1269 make_append(List *appendplans, bool isTarget, List *tlist)
1270 {
1271         Append     *node = makeNode(Append);
1272         Plan       *plan = &node->plan;
1273         List       *subnode;
1274
1275         /* compute costs from subplan costs */
1276         plan->startup_cost = 0;
1277         plan->total_cost = 0;
1278         plan->plan_rows = 0;
1279         plan->plan_width = 0;
1280         foreach(subnode, appendplans)
1281         {
1282                 Plan       *subplan = (Plan *) lfirst(subnode);
1283
1284                 if (subnode == appendplans)             /* first node? */
1285                         plan->startup_cost = subplan->startup_cost;
1286                 plan->total_cost += subplan->total_cost;
1287                 plan->plan_rows += subplan->plan_rows;
1288                 if (plan->plan_width < subplan->plan_width)
1289                         plan->plan_width = subplan->plan_width;
1290         }
1291         plan->state = (EState *) NULL;
1292         plan->targetlist = tlist;
1293         plan->qual = NIL;
1294         plan->lefttree = NULL;
1295         plan->righttree = NULL;
1296         node->appendplans = appendplans;
1297         node->isTarget = isTarget;
1298
1299         return node;
1300 }
1301
1302 static NestLoop *
1303 make_nestloop(List *tlist,
1304                           List *joinclauses,
1305                           List *otherclauses,
1306                           Plan *lefttree,
1307                           Plan *righttree,
1308                           JoinType jointype)
1309 {
1310         NestLoop   *node = makeNode(NestLoop);
1311         Plan       *plan = &node->join.plan;
1312
1313         /* cost should be inserted by caller */
1314         plan->state = (EState *) NULL;
1315         plan->targetlist = tlist;
1316         plan->qual = otherclauses;
1317         plan->lefttree = lefttree;
1318         plan->righttree = righttree;
1319         node->join.jointype = jointype;
1320         node->join.joinqual = joinclauses;
1321
1322         return node;
1323 }
1324
1325 static HashJoin *
1326 make_hashjoin(List *tlist,
1327                           List *joinclauses,
1328                           List *otherclauses,
1329                           List *hashclauses,
1330                           Plan *lefttree,
1331                           Plan *righttree,
1332                           JoinType jointype)
1333 {
1334         HashJoin   *node = makeNode(HashJoin);
1335         Plan       *plan = &node->join.plan;
1336
1337         /* cost should be inserted by caller */
1338         plan->state = (EState *) NULL;
1339         plan->targetlist = tlist;
1340         plan->qual = otherclauses;
1341         plan->lefttree = lefttree;
1342         plan->righttree = righttree;
1343         node->hashclauses = hashclauses;
1344         node->join.jointype = jointype;
1345         node->join.joinqual = joinclauses;
1346
1347         return node;
1348 }
1349
1350 static Hash *
1351 make_hash(List *tlist, Node *hashkey, Plan *lefttree)
1352 {
1353         Hash       *node = makeNode(Hash);
1354         Plan       *plan = &node->plan;
1355
1356         copy_plan_costsize(plan, lefttree);
1357
1358         /*
1359          * For plausibility, make startup & total costs equal total cost of
1360          * input plan; this only affects EXPLAIN display not decisions.
1361          */
1362         plan->startup_cost = plan->total_cost;
1363         plan->state = (EState *) NULL;
1364         plan->targetlist = tlist;
1365         plan->qual = NULL;
1366         plan->lefttree = lefttree;
1367         plan->righttree = NULL;
1368         node->hashkey = hashkey;
1369
1370         return node;
1371 }
1372
1373 static MergeJoin *
1374 make_mergejoin(List *tlist,
1375                            List *joinclauses,
1376                            List *otherclauses,
1377                            List *mergeclauses,
1378                            Plan *lefttree,
1379                            Plan *righttree,
1380                            JoinType jointype)
1381 {
1382         MergeJoin  *node = makeNode(MergeJoin);
1383         Plan       *plan = &node->join.plan;
1384
1385         /* cost should be inserted by caller */
1386         plan->state = (EState *) NULL;
1387         plan->targetlist = tlist;
1388         plan->qual = otherclauses;
1389         plan->lefttree = lefttree;
1390         plan->righttree = righttree;
1391         node->mergeclauses = mergeclauses;
1392         node->join.jointype = jointype;
1393         node->join.joinqual = joinclauses;
1394
1395         return node;
1396 }
1397
1398 /*
1399  * To use make_sort directly, you must already have marked the tlist
1400  * with reskey and reskeyop information.  The keys had better be
1401  * non-redundant, too (ie, there had better be tlist items marked with
1402  * each key number from 1 to keycount), or the executor will get confused!
1403  */
1404 Sort *
1405 make_sort(List *tlist, Plan *lefttree, int keycount)
1406 {
1407         Sort       *node = makeNode(Sort);
1408         Plan       *plan = &node->plan;
1409         Path            sort_path;              /* dummy for result of cost_sort */
1410
1411         copy_plan_costsize(plan, lefttree); /* only care about copying size */
1412         cost_sort(&sort_path, NIL, lefttree->plan_rows, lefttree->plan_width);
1413         plan->startup_cost = sort_path.startup_cost + lefttree->total_cost;
1414         plan->total_cost = sort_path.total_cost + lefttree->total_cost;
1415         plan->state = (EState *) NULL;
1416         plan->targetlist = tlist;
1417         plan->qual = NIL;
1418         plan->lefttree = lefttree;
1419         plan->righttree = NULL;
1420         node->keycount = keycount;
1421
1422         return node;
1423 }
1424
1425 /*
1426  * make_sort_from_pathkeys
1427  *        Create sort plan to sort according to given pathkeys
1428  *
1429  *        'tlist' is the target list of the input plan
1430  *        'lefttree' is the node which yields input tuples
1431  *        'pathkeys' is the list of pathkeys by which the result is to be sorted
1432  *
1433  * We must convert the pathkey information into reskey and reskeyop fields
1434  * of resdom nodes in the sort plan's target list.
1435  */
1436 Sort *
1437 make_sort_from_pathkeys(List *tlist, Plan *lefttree, List *pathkeys)
1438 {
1439         List       *sort_tlist;
1440         List       *i;
1441         int                     numsortkeys = 0;
1442
1443         /* Create a new target list for the sort, with sort keys set. */
1444         sort_tlist = new_unsorted_tlist(tlist);
1445
1446         foreach(i, pathkeys)
1447         {
1448                 List       *keysublist = (List *) lfirst(i);
1449                 PathKeyItem *pathkey = NULL;
1450                 Resdom     *resdom = NULL;
1451                 List       *j;
1452
1453                 /*
1454                  * We can sort by any one of the sort key items listed in this
1455                  * sublist.  For now, we take the first one that corresponds to an
1456                  * available Var in the sort_tlist.
1457                  *
1458                  * XXX if we have a choice, is there any way of figuring out which
1459                  * might be cheapest to execute?  (For example, int4lt is likely
1460                  * much cheaper to execute than numericlt, but both might appear
1461                  * in the same pathkey sublist...)      Not clear that we ever will
1462                  * have a choice in practice, so it may not matter.
1463                  */
1464                 foreach(j, keysublist)
1465                 {
1466                         pathkey = lfirst(j);
1467                         Assert(IsA(pathkey, PathKeyItem));
1468                         resdom = tlist_member(pathkey->key, sort_tlist);
1469                         if (resdom)
1470                                 break;
1471                 }
1472                 if (!resdom)
1473                         elog(ERROR, "make_sort_from_pathkeys: cannot find tlist item to sort");
1474
1475                 /*
1476                  * The resdom might be already marked as a sort key, if the
1477                  * pathkeys contain duplicate entries.  (This can happen in
1478                  * scenarios where multiple mergejoinable clauses mention the same
1479                  * var, for example.) In that case the current pathkey is
1480                  * essentially a no-op, because only one value can be seen within
1481                  * any subgroup where it would be consulted.  We can ignore it.
1482                  */
1483                 if (resdom->reskey == 0)
1484                 {
1485                         /* OK, mark it as a sort key and set the sort operator regproc */
1486                         resdom->reskey = ++numsortkeys;
1487                         resdom->reskeyop = get_opcode(pathkey->sortop);
1488                 }
1489         }
1490
1491         Assert(numsortkeys > 0);
1492
1493         return make_sort(sort_tlist, lefttree, numsortkeys);
1494 }
1495
1496 Material *
1497 make_material(List *tlist, Plan *lefttree)
1498 {
1499         Material   *node = makeNode(Material);
1500         Plan       *plan = &node->plan;
1501
1502         copy_plan_costsize(plan, lefttree);
1503
1504         /*
1505          * For plausibility, make startup & total costs equal total cost of
1506          * input plan; this only affects EXPLAIN display not decisions.
1507          *
1508          * XXX shouldn't we charge some additional cost for materialization?
1509          */
1510         plan->startup_cost = plan->total_cost;
1511         plan->state = (EState *) NULL;
1512         plan->targetlist = tlist;
1513         plan->qual = NIL;
1514         plan->lefttree = lefttree;
1515         plan->righttree = NULL;
1516
1517         return node;
1518 }
1519
1520 Agg *
1521 make_agg(List *tlist, List *qual, Plan *lefttree)
1522 {
1523         Agg                *node = makeNode(Agg);
1524         Plan       *plan = &node->plan;
1525
1526         copy_plan_costsize(plan, lefttree);
1527
1528         /*
1529          * Charge one cpu_operator_cost per aggregate function per input
1530          * tuple.
1531          */
1532         plan->total_cost += cpu_operator_cost * plan->plan_rows *
1533                 (length(pull_agg_clause((Node *) tlist)) +
1534                  length(pull_agg_clause((Node *) qual)));
1535
1536         /*
1537          * We will produce a single output tuple if the input is not a Group,
1538          * and a tuple per group otherwise.  For now, estimate the number of
1539          * groups as 10% of the number of tuples --- bogus, but how to do
1540          * better? (Note we assume the input Group node is in "tuplePerGroup"
1541          * mode, so it didn't reduce its row count already.)
1542          */
1543         if (IsA(lefttree, Group))
1544         {
1545                 plan->plan_rows *= 0.1;
1546                 if (plan->plan_rows < 1)
1547                         plan->plan_rows = 1;
1548         }
1549         else
1550         {
1551                 plan->plan_rows = 1;
1552                 plan->startup_cost = plan->total_cost;
1553         }
1554
1555         plan->state = (EState *) NULL;
1556         plan->qual = qual;
1557         plan->targetlist = tlist;
1558         plan->lefttree = lefttree;
1559         plan->righttree = (Plan *) NULL;
1560
1561         return node;
1562 }
1563
1564 Group *
1565 make_group(List *tlist,
1566                    bool tuplePerGroup,
1567                    int ngrp,
1568                    AttrNumber *grpColIdx,
1569                    Plan *lefttree)
1570 {
1571         Group      *node = makeNode(Group);
1572         Plan       *plan = &node->plan;
1573
1574         copy_plan_costsize(plan, lefttree);
1575
1576         /*
1577          * Charge one cpu_operator_cost per comparison per input tuple. We
1578          * assume all columns get compared at most of the tuples.
1579          */
1580         plan->total_cost += cpu_operator_cost * plan->plan_rows * ngrp;
1581
1582         /*
1583          * If tuplePerGroup (which is named exactly backwards) is true, we
1584          * will return all the input tuples, so the input node's row count is
1585          * OK.  Otherwise, we'll return only one tuple from each group. For
1586          * now, estimate the number of groups as 10% of the number of tuples
1587          * --- bogus, but how to do better?
1588          */
1589         if (!tuplePerGroup)
1590         {
1591                 plan->plan_rows *= 0.1;
1592                 if (plan->plan_rows < 1)
1593                         plan->plan_rows = 1;
1594         }
1595
1596         plan->state = (EState *) NULL;
1597         plan->qual = NULL;
1598         plan->targetlist = tlist;
1599         plan->lefttree = lefttree;
1600         plan->righttree = (Plan *) NULL;
1601         node->tuplePerGroup = tuplePerGroup;
1602         node->numCols = ngrp;
1603         node->grpColIdx = grpColIdx;
1604
1605         return node;
1606 }
1607
1608 /*
1609  * distinctList is a list of SortClauses, identifying the targetlist items
1610  * that should be considered by the Unique filter.
1611  */
1612
1613 Unique *
1614 make_unique(List *tlist, Plan *lefttree, List *distinctList)
1615 {
1616         Unique     *node = makeNode(Unique);
1617         Plan       *plan = &node->plan;
1618         int                     numCols = length(distinctList);
1619         int                     keyno = 0;
1620         AttrNumber *uniqColIdx;
1621         List       *slitem;
1622
1623         copy_plan_costsize(plan, lefttree);
1624
1625         /*
1626          * Charge one cpu_operator_cost per comparison per input tuple. We
1627          * assume all columns get compared at most of the tuples.
1628          */
1629         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
1630
1631         /*
1632          * As for Group, we make the unsupported assumption that there will be
1633          * 10% as many tuples out as in.
1634          */
1635         plan->plan_rows *= 0.1;
1636         if (plan->plan_rows < 1)
1637                 plan->plan_rows = 1;
1638
1639         plan->state = (EState *) NULL;
1640         plan->targetlist = tlist;
1641         plan->qual = NIL;
1642         plan->lefttree = lefttree;
1643         plan->righttree = NULL;
1644
1645         /*
1646          * convert SortClause list into array of attr indexes, as wanted by
1647          * exec
1648          */
1649         Assert(numCols > 0);
1650         uniqColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
1651
1652         foreach(slitem, distinctList)
1653         {
1654                 SortClause *sortcl = (SortClause *) lfirst(slitem);
1655                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, tlist);
1656
1657                 uniqColIdx[keyno++] = tle->resdom->resno;
1658         }
1659
1660         node->numCols = numCols;
1661         node->uniqColIdx = uniqColIdx;
1662
1663         return node;
1664 }
1665
1666 /*
1667  * distinctList is a list of SortClauses, identifying the targetlist items
1668  * that should be considered by the SetOp filter.
1669  */
1670
1671 SetOp *
1672 make_setop(SetOpCmd cmd, List *tlist, Plan *lefttree,
1673                    List *distinctList, AttrNumber flagColIdx)
1674 {
1675         SetOp      *node = makeNode(SetOp);
1676         Plan       *plan = &node->plan;
1677         int                     numCols = length(distinctList);
1678         int                     keyno = 0;
1679         AttrNumber *dupColIdx;
1680         List       *slitem;
1681
1682         copy_plan_costsize(plan, lefttree);
1683
1684         /*
1685          * Charge one cpu_operator_cost per comparison per input tuple. We
1686          * assume all columns get compared at most of the tuples.
1687          */
1688         plan->total_cost += cpu_operator_cost * plan->plan_rows * numCols;
1689
1690         /*
1691          * As for Group, we make the unsupported assumption that there will be
1692          * 10% as many tuples out as in.
1693          */
1694         plan->plan_rows *= 0.1;
1695         if (plan->plan_rows < 1)
1696                 plan->plan_rows = 1;
1697
1698         plan->state = (EState *) NULL;
1699         plan->targetlist = tlist;
1700         plan->qual = NIL;
1701         plan->lefttree = lefttree;
1702         plan->righttree = NULL;
1703
1704         /*
1705          * convert SortClause list into array of attr indexes, as wanted by
1706          * exec
1707          */
1708         Assert(numCols > 0);
1709         dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
1710
1711         foreach(slitem, distinctList)
1712         {
1713                 SortClause *sortcl = (SortClause *) lfirst(slitem);
1714                 TargetEntry *tle = get_sortgroupclause_tle(sortcl, tlist);
1715
1716                 dupColIdx[keyno++] = tle->resdom->resno;
1717         }
1718
1719         node->cmd = cmd;
1720         node->numCols = numCols;
1721         node->dupColIdx = dupColIdx;
1722         node->flagColIdx = flagColIdx;
1723
1724         return node;
1725 }
1726
1727 Limit *
1728 make_limit(List *tlist, Plan *lefttree,
1729                    Node *limitOffset, Node *limitCount)
1730 {
1731         Limit      *node = makeNode(Limit);
1732         Plan       *plan = &node->plan;
1733
1734         copy_plan_costsize(plan, lefttree);
1735
1736         /*
1737          * If offset/count are constants, adjust the output rows count and costs
1738          * accordingly.  This is only a cosmetic issue if we are at top level,
1739          * but if we are building a subquery then it's important to report
1740          * correct info to the outer planner.
1741          */
1742         if (limitOffset && IsA(limitOffset, Const))
1743         {
1744                 Const      *limito = (Const *) limitOffset;
1745                 int32           offset = DatumGetInt32(limito->constvalue);
1746
1747                 if (!limito->constisnull && offset > 0)
1748                 {
1749                         if (offset > plan->plan_rows)
1750                                 offset = (int32) plan->plan_rows;
1751                         if (plan->plan_rows > 0)
1752                                 plan->startup_cost +=
1753                                         (plan->total_cost - plan->startup_cost)
1754                                         * ((double) offset) / plan->plan_rows;
1755                         plan->plan_rows -= offset;
1756                         if (plan->plan_rows < 1)
1757                                 plan->plan_rows = 1;
1758                 }
1759         }
1760         if (limitCount && IsA(limitCount, Const))
1761         {
1762                 Const      *limitc = (Const *) limitCount;
1763                 int32           count = DatumGetInt32(limitc->constvalue);
1764
1765                 if (!limitc->constisnull && count >= 0)
1766                 {
1767                         if (count > plan->plan_rows)
1768                                 count = (int32) plan->plan_rows;
1769                         if (plan->plan_rows > 0)
1770                                 plan->total_cost = plan->startup_cost +
1771                                         (plan->total_cost - plan->startup_cost)
1772                                         * ((double) count) / plan->plan_rows;
1773                         plan->plan_rows = count;
1774                         if (plan->plan_rows < 1)
1775                                 plan->plan_rows = 1;
1776                 }
1777         }
1778
1779         plan->state = (EState *) NULL;
1780         plan->targetlist = tlist;
1781         plan->qual = NIL;
1782         plan->lefttree = lefttree;
1783         plan->righttree = NULL;
1784
1785         node->limitOffset = limitOffset;
1786         node->limitCount = limitCount;
1787
1788         return node;
1789 }
1790
1791 Result *
1792 make_result(List *tlist,
1793                         Node *resconstantqual,
1794                         Plan *subplan)
1795 {
1796         Result     *node = makeNode(Result);
1797         Plan       *plan = &node->plan;
1798
1799 #ifdef NOT_USED
1800         tlist = generate_fjoin(tlist);
1801 #endif
1802         copy_plan_costsize(plan, subplan);
1803         plan->state = (EState *) NULL;
1804         plan->targetlist = tlist;
1805         plan->qual = NIL;
1806         plan->lefttree = subplan;
1807         plan->righttree = NULL;
1808         node->resconstantqual = resconstantqual;
1809         node->resstate = NULL;
1810
1811         return node;
1812 }
1813
1814 #ifdef NOT_USED
1815 List *
1816 generate_fjoin(List *tlist)
1817 {
1818         List            tlistP;
1819         List            newTlist = NIL;
1820         List            fjoinList = NIL;
1821         int                     nIters = 0;
1822
1823         /*
1824          * Break the target list into elements with Iter nodes, and those
1825          * without them.
1826          */
1827         foreach(tlistP, tlist)
1828         {
1829                 List            tlistElem;
1830
1831                 tlistElem = lfirst(tlistP);
1832                 if (IsA(lsecond(tlistElem), Iter))
1833                 {
1834                         nIters++;
1835                         fjoinList = lappend(fjoinList, tlistElem);
1836                 }
1837                 else
1838                         newTlist = lappend(newTlist, tlistElem);
1839         }
1840
1841         /*
1842          * if we have an Iter node then we need to flatten.
1843          */
1844         if (nIters > 0)
1845         {
1846                 List       *inner;
1847                 List       *tempList;
1848                 Fjoin      *fjoinNode;
1849                 DatumPtr        results = (DatumPtr) palloc(nIters * sizeof(Datum));
1850                 BoolPtr         alwaysDone = (BoolPtr) palloc(nIters * sizeof(bool));
1851
1852                 inner = lfirst(fjoinList);
1853                 fjoinList = lnext(fjoinList);
1854                 fjoinNode = (Fjoin) MakeFjoin(false,
1855                                                                           nIters,
1856                                                                           inner,
1857                                                                           results,
1858                                                                           alwaysDone);
1859                 tempList = lcons(fjoinNode, fjoinList);
1860                 newTlist = lappend(newTlist, tempList);
1861         }
1862         return newTlist;
1863         return tlist;                           /* do nothing for now - ay 10/94 */
1864 }
1865
1866 #endif