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