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