granicus.if.org Git - postgresql/blob - src/backend/optimizer/util/pathnode.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * pathnode.c
   4  *        Routines to manipulate pathlists and create path nodes
   5  *
   6  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.103 2004/03/29 19:58:04 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include <math.h>
  18
  19 #include "catalog/pg_operator.h"
  20 #include "executor/executor.h"
  21 #include "miscadmin.h"
  22 #include "nodes/plannodes.h"
  23 #include "optimizer/clauses.h"
  24 #include "optimizer/cost.h"
  25 #include "optimizer/pathnode.h"
  26 #include "optimizer/paths.h"
  27 #include "optimizer/restrictinfo.h"
  28 #include "optimizer/tlist.h"
  29 #include "parser/parse_expr.h"
  30 #include "parser/parse_oper.h"
  31 #include "parser/parsetree.h"
  32 #include "utils/memutils.h"
  33 #include "utils/selfuncs.h"
  34 #include "utils/syscache.h"
  35
  36
  37 static bool is_distinct_query(Query *query);
  38 static bool hash_safe_tlist(List *tlist);
  39
  40
  41 /*****************************************************************************
  42  *              MISC. PATH UTILITIES
  43  *****************************************************************************/
  44
  45 /*
  46  * compare_path_costs
  47  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
  48  *        or more expensive than path2 for the specified criterion.
  49  */
  50 int
  51 compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
  52 {
  53         if (criterion == STARTUP_COST)
  54         {
  55                 if (path1->startup_cost < path2->startup_cost)
  56                         return -1;
  57                 if (path1->startup_cost > path2->startup_cost)
  58                         return +1;
  59
  60                 /*
  61                  * If paths have the same startup cost (not at all unlikely),
  62                  * order them by total cost.
  63                  */
  64                 if (path1->total_cost < path2->total_cost)
  65                         return -1;
  66                 if (path1->total_cost > path2->total_cost)
  67                         return +1;
  68         }
  69         else
  70         {
  71                 if (path1->total_cost < path2->total_cost)
  72                         return -1;
  73                 if (path1->total_cost > path2->total_cost)
  74                         return +1;
  75
  76                 /*
  77                  * If paths have the same total cost, order them by startup cost.
  78                  */
  79                 if (path1->startup_cost < path2->startup_cost)
  80                         return -1;
  81                 if (path1->startup_cost > path2->startup_cost)
  82                         return +1;
  83         }
  84         return 0;
  85 }
  86
  87 /*
  88  * compare_fuzzy_path_costs
  89  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
  90  *        or more expensive than path2 for the specified criterion.
  91  *
  92  * This differs from compare_path_costs in that we consider the costs the
  93  * same if they agree to within a "fuzz factor".  This is used by add_path
  94  * to avoid keeping both of a pair of paths that really have insignificantly
  95  * different cost.
  96  */
  97 static int
  98 compare_fuzzy_path_costs(Path *path1, Path *path2, CostSelector criterion)
  99 {
 100         Cost            fuzz;
 101
 102         /*
 103          * The fuzz factor is set at one percent of the smaller total_cost, but
 104          * not less than 0.01 cost units (just in case total cost is zero).
 105          *
 106          * XXX does this percentage need to be user-configurable?
 107          */
 108         fuzz = Min(path1->total_cost, path2->total_cost) * 0.01;
 109         fuzz = Max(fuzz, 0.01);
 110
 111         if (criterion == STARTUP_COST)
 112         {
 113                 if (Abs(path1->startup_cost - path2->startup_cost) > fuzz)
 114                 {
 115                         if (path1->startup_cost < path2->startup_cost)
 116                                 return -1;
 117                         else
 118                                 return +1;
 119                 }
 120
 121                 /*
 122                  * If paths have the same startup cost (not at all unlikely),
 123                  * order them by total cost.
 124                  */
 125                 if (Abs(path1->total_cost - path2->total_cost) > fuzz)
 126                 {
 127                         if (path1->total_cost < path2->total_cost)
 128                                 return -1;
 129                         else
 130                                 return +1;
 131                 }
 132         }
 133         else
 134         {
 135                 if (Abs(path1->total_cost - path2->total_cost) > fuzz)
 136                 {
 137                         if (path1->total_cost < path2->total_cost)
 138                                 return -1;
 139                         else
 140                                 return +1;
 141                 }
 142
 143                 /*
 144                  * If paths have the same total cost, order them by startup cost.
 145                  */
 146                 if (Abs(path1->startup_cost - path2->startup_cost) > fuzz)
 147                 {
 148                         if (path1->startup_cost < path2->startup_cost)
 149                                 return -1;
 150                         else
 151                                 return +1;
 152                 }
 153         }
 154         return 0;
 155 }
 156
 157 /*
 158  * compare_path_fractional_costs
 159  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
 160  *        or more expensive than path2 for fetching the specified fraction
 161  *        of the total tuples.
 162  *
 163  * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the
 164  * path with the cheaper total_cost.
 165  */
 166 int
 167 compare_fractional_path_costs(Path *path1, Path *path2,
 168                                                           double fraction)
 169 {
 170         Cost            cost1,
 171                                 cost2;
 172
 173         if (fraction <= 0.0 || fraction >= 1.0)
 174                 return compare_path_costs(path1, path2, TOTAL_COST);
 175         cost1 = path1->startup_cost +
 176                 fraction * (path1->total_cost - path1->startup_cost);
 177         cost2 = path2->startup_cost +
 178                 fraction * (path2->total_cost - path2->startup_cost);
 179         if (cost1 < cost2)
 180                 return -1;
 181         if (cost1 > cost2)
 182                 return +1;
 183         return 0;
 184 }
 185
 186 /*
 187  * set_cheapest
 188  *        Find the minimum-cost paths from among a relation's paths,
 189  *        and save them in the rel's cheapest-path fields.
 190  *
 191  * This is normally called only after we've finished constructing the path
 192  * list for the rel node.
 193  *
 194  * If we find two paths of identical costs, try to keep the better-sorted one.
 195  * The paths might have unrelated sort orderings, in which case we can only
 196  * guess which might be better to keep, but if one is superior then we
 197  * definitely should keep it.
 198  */
 199 void
 200 set_cheapest(RelOptInfo *parent_rel)
 201 {
 202         List       *pathlist = parent_rel->pathlist;
 203         List       *p;
 204         Path       *cheapest_startup_path;
 205         Path       *cheapest_total_path;
 206
 207         Assert(IsA(parent_rel, RelOptInfo));
 208
 209         if (pathlist == NIL)
 210                 elog(ERROR, "could not devise a query plan for the given query");
 211
 212         cheapest_startup_path = cheapest_total_path = (Path *) lfirst(pathlist);
 213
 214         foreach(p, lnext(pathlist))
 215         {
 216                 Path       *path = (Path *) lfirst(p);
 217                 int                     cmp;
 218
 219                 cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
 220                 if (cmp > 0 ||
 221                         (cmp == 0 &&
 222                          compare_pathkeys(cheapest_startup_path->pathkeys,
 223                                                           path->pathkeys) == PATHKEYS_BETTER2))
 224                         cheapest_startup_path = path;
 225
 226                 cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST);
 227                 if (cmp > 0 ||
 228                         (cmp == 0 &&
 229                          compare_pathkeys(cheapest_total_path->pathkeys,
 230                                                           path->pathkeys) == PATHKEYS_BETTER2))
 231                         cheapest_total_path = path;
 232         }
 233
 234         parent_rel->cheapest_startup_path = cheapest_startup_path;
 235         parent_rel->cheapest_total_path = cheapest_total_path;
 236         parent_rel->cheapest_unique_path = NULL;        /* computed only if needed */
 237 }
 238
 239 /*
 240  * add_path
 241  *        Consider a potential implementation path for the specified parent rel,
 242  *        and add it to the rel's pathlist if it is worthy of consideration.
 243  *        A path is worthy if it has either a better sort order (better pathkeys)
 244  *        or cheaper cost (on either dimension) than any of the existing old paths.
 245  *
 246  *        Unless parent_rel->pruneable is false, we also remove from the rel's
 247  *        pathlist any old paths that are dominated by new_path --- that is,
 248  *        new_path is both cheaper and at least as well ordered.
 249  *
 250  *        The pathlist is kept sorted by TOTAL_COST metric, with cheaper paths
 251  *        at the front.  No code depends on that for correctness; it's simply
 252  *        a speed hack within this routine.  Doing it that way makes it more
 253  *        likely that we will reject an inferior path after a few comparisons,
 254  *        rather than many comparisons.
 255  *
 256  *        NOTE: discarded Path objects are immediately pfree'd to reduce planner
 257  *        memory consumption.  We dare not try to free the substructure of a Path,
 258  *        since much of it may be shared with other Paths or the query tree itself;
 259  *        but just recycling discarded Path nodes is a very useful savings in
 260  *        a large join tree.  We can recycle the List nodes of pathlist, too.
 261  *
 262  * 'parent_rel' is the relation entry to which the path corresponds.
 263  * 'new_path' is a potential path for parent_rel.
 264  *
 265  * Returns nothing, but modifies parent_rel->pathlist.
 266  */
 267 void
 268 add_path(RelOptInfo *parent_rel, Path *new_path)
 269 {
 270         bool            accept_new = true;              /* unless we find a superior old
 271                                                                                  * path */
 272         List       *insert_after = NIL;         /* where to insert new item */
 273         List       *p1_prev = NIL;
 274         List       *p1;
 275
 276         /*
 277          * Loop to check proposed new path against old paths.  Note it is
 278          * possible for more than one old path to be tossed out because
 279          * new_path dominates it.
 280          */
 281         p1 = parent_rel->pathlist;      /* cannot use foreach here */
 282         while (p1 != NIL)
 283         {
 284                 Path       *old_path = (Path *) lfirst(p1);
 285                 bool            remove_old = false; /* unless new proves superior */
 286                 int                     costcmp;
 287
 288                 /*
 289                  * As of Postgres 7.5, we use fuzzy cost comparison to avoid wasting
 290                  * cycles keeping paths that are really not significantly different
 291                  * in cost.
 292                  */
 293                 costcmp = compare_fuzzy_path_costs(new_path, old_path, TOTAL_COST);
 294
 295                 /*
 296                  * If the two paths compare differently for startup and total
 297                  * cost, then we want to keep both, and we can skip the (much
 298                  * slower) comparison of pathkeys.      If they compare the same,
 299                  * proceed with the pathkeys comparison.  Note: this test relies
 300                  * on the fact that compare_fuzzy_path_costs will only return 0 if
 301                  * both costs are effectively equal (and, therefore, there's no need
 302                  * to call it twice in that case).
 303                  */
 304                 if (costcmp == 0 ||
 305                         costcmp == compare_fuzzy_path_costs(new_path, old_path,
 306                                                                                                 STARTUP_COST))
 307                 {
 308                         switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys))
 309                         {
 310                                 case PATHKEYS_EQUAL:
 311                                         if (costcmp < 0)
 312                                                 remove_old = true;              /* new dominates old */
 313                                         else if (costcmp > 0)
 314                                                 accept_new = false;             /* old dominates new */
 315                                         else
 316                                         {
 317                                                 /*
 318                                                  * Same pathkeys, and fuzzily the same cost, so
 319                                                  * keep just one --- but we'll do an exact cost
 320                                                  * comparison to decide which.
 321                                                  */
 322                                                 if (compare_path_costs(new_path, old_path,
 323                                                                                            TOTAL_COST) < 0)
 324                                                         remove_old = true; /* new dominates old */
 325                                                 else
 326                                                         accept_new = false;     /* old equals or dominates
 327                                                                                                  * new */
 328                                         }
 329                                         break;
 330                                 case PATHKEYS_BETTER1:
 331                                         if (costcmp <= 0)
 332                                                 remove_old = true;              /* new dominates old */
 333                                         break;
 334                                 case PATHKEYS_BETTER2:
 335                                         if (costcmp >= 0)
 336                                                 accept_new = false;             /* old dominates new */
 337                                         break;
 338                                 case PATHKEYS_DIFFERENT:
 339                                         /* keep both paths, since they have different ordering */
 340                                         break;
 341                         }
 342                 }
 343
 344                 /*
 345                  * Remove current element from pathlist if dominated by new,
 346                  * unless xfunc told us not to remove any paths.
 347                  */
 348                 if (remove_old && parent_rel->pruneable)
 349                 {
 350                         List       *p1_next = lnext(p1);
 351
 352                         if (p1_prev)
 353                                 lnext(p1_prev) = p1_next;
 354                         else
 355                                 parent_rel->pathlist = p1_next;
 356                         pfree(old_path);
 357                         pfree(p1);                      /* this is why we can't use foreach */
 358                         p1 = p1_next;
 359                 }
 360                 else
 361                 {
 362                         /* new belongs after this old path if it has cost >= old's */
 363                         if (costcmp >= 0)
 364                                 insert_after = p1;
 365                         p1_prev = p1;
 366                         p1 = lnext(p1);
 367                 }
 368
 369                 /*
 370                  * If we found an old path that dominates new_path, we can quit
 371                  * scanning the pathlist; we will not add new_path, and we assume
 372                  * new_path cannot dominate any other elements of the pathlist.
 373                  */
 374                 if (!accept_new)
 375                         break;
 376         }
 377
 378         if (accept_new)
 379         {
 380                 /* Accept the new path: insert it at proper place in pathlist */
 381                 if (insert_after)
 382                         lnext(insert_after) = lcons(new_path, lnext(insert_after));
 383                 else
 384                         parent_rel->pathlist = lcons(new_path, parent_rel->pathlist);
 385         }
 386         else
 387         {
 388                 /* Reject and recycle the new path */
 389                 pfree(new_path);
 390         }
 391 }
 392
 393
 394 /*****************************************************************************
 395  *              PATH NODE CREATION ROUTINES
 396  *****************************************************************************/
 397
 398 /*
 399  * create_seqscan_path
 400  *        Creates a path corresponding to a sequential scan, returning the
 401  *        pathnode.
 402  */
 403 Path *
 404 create_seqscan_path(Query *root, RelOptInfo *rel)
 405 {
 406         Path       *pathnode = makeNode(Path);
 407
 408         pathnode->pathtype = T_SeqScan;
 409         pathnode->parent = rel;
 410         pathnode->pathkeys = NIL;       /* seqscan has unordered result */
 411
 412         cost_seqscan(pathnode, root, rel);
 413
 414         return pathnode;
 415 }
 416
 417 /*
 418  * create_index_path
 419  *        Creates a path node for an index scan.
 420  *
 421  * 'rel' is the parent rel
 422  * 'index' is an index on 'rel'
 423  * 'restriction_clauses' is a list of lists of RestrictInfo nodes
 424  *                      to be used as index qual conditions in the scan.
 425  * 'pathkeys' describes the ordering of the path.
 426  * 'indexscandir' is ForwardScanDirection or BackwardScanDirection
 427  *                      for an ordered index, or NoMovementScanDirection for
 428  *                      an unordered index.
 429  *
 430  * Returns the new path node.
 431  */
 432 IndexPath *
 433 create_index_path(Query *root,
 434                                   RelOptInfo *rel,
 435                                   IndexOptInfo *index,
 436                                   List *restriction_clauses,
 437                                   List *pathkeys,
 438                                   ScanDirection indexscandir)
 439 {
 440         IndexPath  *pathnode = makeNode(IndexPath);
 441         List       *indexquals;
 442
 443         pathnode->path.pathtype = T_IndexScan;
 444         pathnode->path.parent = rel;
 445         pathnode->path.pathkeys = pathkeys;
 446
 447         /* Convert clauses to indexquals the executor can handle */
 448         indexquals = expand_indexqual_conditions(index, restriction_clauses);
 449
 450         /* Flatten the clause-groups list to produce indexclauses list */
 451         restriction_clauses = flatten_clausegroups_list(restriction_clauses);
 452
 453         /*
 454          * We are making a pathnode for a single-scan indexscan; therefore,
 455          * indexinfo etc should be single-element lists.
 456          */
 457         pathnode->indexinfo = makeList1(index);
 458         pathnode->indexclauses = makeList1(restriction_clauses);
 459         pathnode->indexquals = makeList1(indexquals);
 460
 461         /* It's not an innerjoin path. */
 462         pathnode->isjoininner = false;
 463
 464         pathnode->indexscandir = indexscandir;
 465
 466         /*
 467          * The number of rows is the same as the parent rel's estimate, since
 468          * this isn't a join inner indexscan.
 469          */
 470         pathnode->rows = rel->rows;
 471
 472         cost_index(&pathnode->path, root, rel, index, indexquals, false);
 473
 474         return pathnode;
 475 }
 476
 477 /*
 478  * create_tidscan_path
 479  *        Creates a path corresponding to a tid_direct scan, returning the
 480  *        pathnode.
 481  */
 482 TidPath *
 483 create_tidscan_path(Query *root, RelOptInfo *rel, List *tideval)
 484 {
 485         TidPath    *pathnode = makeNode(TidPath);
 486
 487         pathnode->path.pathtype = T_TidScan;
 488         pathnode->path.parent = rel;
 489         pathnode->path.pathkeys = NIL;
 490
 491         pathnode->tideval = tideval;
 492
 493         cost_tidscan(&pathnode->path, root, rel, tideval);
 494
 495         /*
 496          * divide selectivity for each clause to get an equal selectivity as
 497          * IndexScan does OK ?
 498          */
 499
 500         return pathnode;
 501 }
 502
 503 /*
 504  * create_append_path
 505  *        Creates a path corresponding to an Append plan, returning the
 506  *        pathnode.
 507  */
 508 AppendPath *
 509 create_append_path(RelOptInfo *rel, List *subpaths)
 510 {
 511         AppendPath *pathnode = makeNode(AppendPath);
 512         List       *l;
 513
 514         pathnode->path.pathtype = T_Append;
 515         pathnode->path.parent = rel;
 516         pathnode->path.pathkeys = NIL;          /* result is always considered
 517                                                                                  * unsorted */
 518         pathnode->subpaths = subpaths;
 519
 520         pathnode->path.startup_cost = 0;
 521         pathnode->path.total_cost = 0;
 522         foreach(l, subpaths)
 523         {
 524                 Path       *subpath = (Path *) lfirst(l);
 525
 526                 if (l == subpaths)              /* first node? */
 527                         pathnode->path.startup_cost = subpath->startup_cost;
 528                 pathnode->path.total_cost += subpath->total_cost;
 529         }
 530
 531         return pathnode;
 532 }
 533
 534 /*
 535  * create_result_path
 536  *        Creates a path corresponding to a Result plan, returning the
 537  *        pathnode.
 538  */
 539 ResultPath *
 540 create_result_path(RelOptInfo *rel, Path *subpath, List *constantqual)
 541 {
 542         ResultPath *pathnode = makeNode(ResultPath);
 543
 544         pathnode->path.pathtype = T_Result;
 545         pathnode->path.parent = rel;    /* may be NULL */
 546
 547         if (subpath)
 548                 pathnode->path.pathkeys = subpath->pathkeys;
 549         else
 550                 pathnode->path.pathkeys = NIL;
 551
 552         pathnode->subpath = subpath;
 553         pathnode->constantqual = constantqual;
 554
 555         /* Ideally should define cost_result(), but I'm too lazy */
 556         if (subpath)
 557         {
 558                 pathnode->path.startup_cost = subpath->startup_cost;
 559                 pathnode->path.total_cost = subpath->total_cost;
 560         }
 561         else
 562         {
 563                 pathnode->path.startup_cost = 0;
 564                 pathnode->path.total_cost = cpu_tuple_cost;
 565         }
 566
 567         return pathnode;
 568 }
 569
 570 /*
 571  * create_material_path
 572  *        Creates a path corresponding to a Material plan, returning the
 573  *        pathnode.
 574  */
 575 MaterialPath *
 576 create_material_path(RelOptInfo *rel, Path *subpath)
 577 {
 578         MaterialPath *pathnode = makeNode(MaterialPath);
 579
 580         pathnode->path.pathtype = T_Material;
 581         pathnode->path.parent = rel;
 582
 583         pathnode->path.pathkeys = subpath->pathkeys;
 584
 585         pathnode->subpath = subpath;
 586
 587         cost_material(&pathnode->path,
 588                                   subpath->total_cost,
 589                                   rel->rows,
 590                                   rel->width);
 591
 592         return pathnode;
 593 }
 594
 595 /*
 596  * create_unique_path
 597  *        Creates a path representing elimination of distinct rows from the
 598  *        input data.
 599  *
 600  * If used at all, this is likely to be called repeatedly on the same rel;
 601  * and the input subpath should always be the same (the cheapest_total path
 602  * for the rel).  So we cache the result.
 603  */
 604 UniquePath *
 605 create_unique_path(Query *root, RelOptInfo *rel, Path *subpath)
 606 {
 607         UniquePath *pathnode;
 608         Path            sort_path;              /* dummy for result of cost_sort */
 609         Path            agg_path;               /* dummy for result of cost_agg */
 610         MemoryContext oldcontext;
 611         List       *sub_targetlist;
 612         List       *l;
 613         int                     numCols;
 614
 615         /* Caller made a mistake if subpath isn't cheapest_total */
 616         Assert(subpath == rel->cheapest_total_path);
 617
 618         /* If result already cached, return it */
 619         if (rel->cheapest_unique_path)
 620                 return (UniquePath *) rel->cheapest_unique_path;
 621
 622         /*
 623          * We must ensure path struct is allocated in same context as parent
 624          * rel; otherwise GEQO memory management causes trouble.  (Compare
 625          * best_inner_indexscan().)
 626          */
 627         oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
 628
 629         pathnode = makeNode(UniquePath);
 630
 631         /* There is no substructure to allocate, so can switch back right away */
 632         MemoryContextSwitchTo(oldcontext);
 633
 634         pathnode->path.pathtype = T_Unique;
 635         pathnode->path.parent = rel;
 636
 637         /*
 638          * Treat the output as always unsorted, since we don't necessarily
 639          * have pathkeys to represent it.
 640          */
 641         pathnode->path.pathkeys = NIL;
 642
 643         pathnode->subpath = subpath;
 644
 645         /*
 646          * If the input is a subquery whose output must be unique already,
 647          * we don't need to do anything.
 648          */
 649         if (rel->rtekind == RTE_SUBQUERY)
 650         {
 651                 RangeTblEntry *rte = rt_fetch(rel->relid, root->rtable);
 652
 653                 if (is_distinct_query(rte->subquery))
 654                 {
 655                         pathnode->umethod = UNIQUE_PATH_NOOP;
 656                         pathnode->rows = rel->rows;
 657                         pathnode->path.startup_cost = subpath->startup_cost;
 658                         pathnode->path.total_cost = subpath->total_cost;
 659                         pathnode->path.pathkeys = subpath->pathkeys;
 660
 661                         rel->cheapest_unique_path = (Path *) pathnode;
 662
 663                         return pathnode;
 664                 }
 665         }
 666
 667         /*
 668          * Try to identify the targetlist that will actually be unique-ified.
 669          * In current usage, this routine is only used for sub-selects of IN
 670          * clauses, so we should be able to find the tlist in in_info_list.
 671          */
 672         sub_targetlist = NIL;
 673         foreach(l, root->in_info_list)
 674         {
 675                 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
 676
 677                 if (bms_equal(ininfo->righthand, rel->relids))
 678                 {
 679                         sub_targetlist = ininfo->sub_targetlist;
 680                         break;
 681                 }
 682         }
 683
 684         /*
 685          * If we know the targetlist, try to estimate number of result rows;
 686          * otherwise punt.
 687          */
 688         if (sub_targetlist)
 689         {
 690                 pathnode->rows = estimate_num_groups(root, sub_targetlist, rel->rows);
 691                 numCols = length(sub_targetlist);
 692         }
 693         else
 694         {
 695                 pathnode->rows = rel->rows;
 696                 numCols = length(FastListValue(&rel->reltargetlist));
 697         }
 698
 699         /*
 700          * Estimate cost for sort+unique implementation
 701          */
 702         cost_sort(&sort_path, root, NIL,
 703                           subpath->total_cost,
 704                           rel->rows,
 705                           rel->width);
 706
 707         /*
 708          * Charge one cpu_operator_cost per comparison per input tuple. We
 709          * assume all columns get compared at most of the tuples.  (XXX
 710          * probably this is an overestimate.)  This should agree with
 711          * make_unique.
 712          */
 713         sort_path.total_cost += cpu_operator_cost * rel->rows * numCols;
 714
 715         /*
 716          * Is it safe to use a hashed implementation?  If so, estimate and
 717          * compare costs.  We only try this if we know the targetlist for sure
 718          * (else we can't be sure about the datatypes involved).
 719          */
 720         pathnode->umethod = UNIQUE_PATH_SORT;
 721         if (enable_hashagg && sub_targetlist && hash_safe_tlist(sub_targetlist))
 722         {
 723                 /*
 724                  * Estimate the overhead per hashtable entry at 64 bytes (same as
 725                  * in planner.c).
 726                  */
 727                 int                     hashentrysize = rel->width + 64;
 728
 729                 if (hashentrysize * pathnode->rows <= work_mem * 1024L)
 730                 {
 731                         cost_agg(&agg_path, root,
 732                                          AGG_HASHED, 0,
 733                                          numCols, pathnode->rows,
 734                                          subpath->startup_cost,
 735                                          subpath->total_cost,
 736                                          rel->rows);
 737                         if (agg_path.total_cost < sort_path.total_cost)
 738                                 pathnode->umethod = UNIQUE_PATH_HASH;
 739                 }
 740         }
 741
 742         if (pathnode->umethod == UNIQUE_PATH_HASH)
 743         {
 744                 pathnode->path.startup_cost = agg_path.startup_cost;
 745                 pathnode->path.total_cost = agg_path.total_cost;
 746         }
 747         else
 748         {
 749                 pathnode->path.startup_cost = sort_path.startup_cost;
 750                 pathnode->path.total_cost = sort_path.total_cost;
 751         }
 752
 753         rel->cheapest_unique_path = (Path *) pathnode;
 754
 755         return pathnode;
 756 }
 757
 758 /*
 759  * is_distinct_query - does query never return duplicate rows?
 760  */
 761 static bool
 762 is_distinct_query(Query *query)
 763 {
 764         /* DISTINCT (but not DISTINCT ON) guarantees uniqueness */
 765         if (has_distinct_clause(query))
 766                 return true;
 767
 768         /* UNION, INTERSECT, EXCEPT guarantee uniqueness, except with ALL */
 769         if (query->setOperations)
 770         {
 771                 SetOperationStmt *topop = (SetOperationStmt *) query->setOperations;
 772
 773                 Assert(IsA(topop, SetOperationStmt));
 774                 Assert(topop->op != SETOP_NONE);
 775
 776                 if (!topop->all)
 777                         return true;
 778         }
 779
 780         /*
 781          * GROUP BY guarantees uniqueness if all the grouped columns appear in
 782          * the output.  In our implementation this means checking they are non
 783          * resjunk columns.
 784          */
 785         if (query->groupClause)
 786         {
 787                 List   *gl;
 788
 789                 foreach(gl, query->groupClause)
 790                 {
 791                         GroupClause *grpcl = (GroupClause *) lfirst(gl);
 792                         TargetEntry *tle = get_sortgroupclause_tle(grpcl,
 793                                                                                                            query->targetList);
 794
 795                         if (tle->resdom->resjunk)
 796                                 break;
 797                 }
 798                 if (!gl)                                /* got to the end? */
 799                         return true;
 800         }
 801
 802         /*
 803          * XXX Are there any other cases in which we can easily see the result
 804          * must be distinct?
 805          */
 806
 807         return false;
 808 }
 809
 810 /*
 811  * hash_safe_tlist - can datatypes of given tlist be hashed?
 812  *
 813  * We assume hashed aggregation will work if the datatype's equality operator
 814  * is marked hashjoinable.
 815  *
 816  * XXX this probably should be somewhere else.  See also hash_safe_grouping
 817  * in plan/planner.c.
 818  */
 819 static bool
 820 hash_safe_tlist(List *tlist)
 821 {
 822         List       *tl;
 823
 824         foreach(tl, tlist)
 825         {
 826                 Node       *expr = (Node *) lfirst(tl);
 827                 Operator        optup;
 828                 bool            oprcanhash;
 829
 830                 optup = equality_oper(exprType(expr), true);
 831                 if (!optup)
 832                         return false;
 833                 oprcanhash = ((Form_pg_operator) GETSTRUCT(optup))->oprcanhash;
 834                 ReleaseSysCache(optup);
 835                 if (!oprcanhash)
 836                         return false;
 837         }
 838         return true;
 839 }
 840
 841 /*
 842  * create_subqueryscan_path
 843  *        Creates a path corresponding to a sequential scan of a subquery,
 844  *        returning the pathnode.
 845  */
 846 Path *
 847 create_subqueryscan_path(RelOptInfo *rel, List *pathkeys)
 848 {
 849         Path       *pathnode = makeNode(Path);
 850
 851         pathnode->pathtype = T_SubqueryScan;
 852         pathnode->parent = rel;
 853         pathnode->pathkeys = pathkeys;
 854
 855         cost_subqueryscan(pathnode, rel);
 856
 857         return pathnode;
 858 }
 859
 860 /*
 861  * create_functionscan_path
 862  *        Creates a path corresponding to a sequential scan of a function,
 863  *        returning the pathnode.
 864  */
 865 Path *
 866 create_functionscan_path(Query *root, RelOptInfo *rel)
 867 {
 868         Path       *pathnode = makeNode(Path);
 869
 870         pathnode->pathtype = T_FunctionScan;
 871         pathnode->parent = rel;
 872         pathnode->pathkeys = NIL;       /* for now, assume unordered result */
 873
 874         cost_functionscan(pathnode, root, rel);
 875
 876         return pathnode;
 877 }
 878
 879 /*
 880  * create_nestloop_path
 881  *        Creates a pathnode corresponding to a nestloop join between two
 882  *        relations.
 883  *
 884  * 'joinrel' is the join relation.
 885  * 'jointype' is the type of join required
 886  * 'outer_path' is the outer path
 887  * 'inner_path' is the inner path
 888  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
 889  * 'pathkeys' are the path keys of the new join path
 890  *
 891  * Returns the resulting path node.
 892  */
 893 NestPath *
 894 create_nestloop_path(Query *root,
 895                                          RelOptInfo *joinrel,
 896                                          JoinType jointype,
 897                                          Path *outer_path,
 898                                          Path *inner_path,
 899                                          List *restrict_clauses,
 900                                          List *pathkeys)
 901 {
 902         NestPath   *pathnode = makeNode(NestPath);
 903
 904         pathnode->path.pathtype = T_NestLoop;
 905         pathnode->path.parent = joinrel;
 906         pathnode->jointype = jointype;
 907         pathnode->outerjoinpath = outer_path;
 908         pathnode->innerjoinpath = inner_path;
 909         pathnode->joinrestrictinfo = restrict_clauses;
 910         pathnode->path.pathkeys = pathkeys;
 911
 912         cost_nestloop(pathnode, root);
 913
 914         return pathnode;
 915 }
 916
 917 /*
 918  * create_mergejoin_path
 919  *        Creates a pathnode corresponding to a mergejoin join between
 920  *        two relations
 921  *
 922  * 'joinrel' is the join relation
 923  * 'jointype' is the type of join required
 924  * 'outer_path' is the outer path
 925  * 'inner_path' is the inner path
 926  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
 927  * 'pathkeys' are the path keys of the new join path
 928  * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
 929  *              (this should be a subset of the restrict_clauses list)
 930  * 'outersortkeys' are the sort varkeys for the outer relation
 931  * 'innersortkeys' are the sort varkeys for the inner relation
 932  */
 933 MergePath *
 934 create_mergejoin_path(Query *root,
 935                                           RelOptInfo *joinrel,
 936                                           JoinType jointype,
 937                                           Path *outer_path,
 938                                           Path *inner_path,
 939                                           List *restrict_clauses,
 940                                           List *pathkeys,
 941                                           List *mergeclauses,
 942                                           List *outersortkeys,
 943                                           List *innersortkeys)
 944 {
 945         MergePath  *pathnode = makeNode(MergePath);
 946
 947         /*
 948          * If the given paths are already well enough ordered, we can skip
 949          * doing an explicit sort.
 950          */
 951         if (outersortkeys &&
 952                 pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
 953                 outersortkeys = NIL;
 954         if (innersortkeys &&
 955                 pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
 956                 innersortkeys = NIL;
 957
 958         /*
 959          * If we are not sorting the inner path, we may need a materialize
 960          * node to ensure it can be marked/restored.  (Sort does support
 961          * mark/restore, so no materialize is needed in that case.)
 962          *
 963          * Since the inner side must be ordered, and only Sorts and IndexScans
 964          * can create order to begin with, you might think there's no problem
 965          * --- but you'd be wrong.  Nestloop and merge joins can *preserve*
 966          * the order of their inputs, so they can be selected as the input of
 967          * a mergejoin, and they don't support mark/restore at present.
 968          */
 969         if (innersortkeys == NIL &&
 970                 !ExecSupportsMarkRestore(inner_path->pathtype))
 971                 inner_path = (Path *)
 972                         create_material_path(inner_path->parent, inner_path);
 973
 974         pathnode->jpath.path.pathtype = T_MergeJoin;
 975         pathnode->jpath.path.parent = joinrel;
 976         pathnode->jpath.jointype = jointype;
 977         pathnode->jpath.outerjoinpath = outer_path;
 978         pathnode->jpath.innerjoinpath = inner_path;
 979         pathnode->jpath.joinrestrictinfo = restrict_clauses;
 980         pathnode->jpath.path.pathkeys = pathkeys;
 981         pathnode->path_mergeclauses = mergeclauses;
 982         pathnode->outersortkeys = outersortkeys;
 983         pathnode->innersortkeys = innersortkeys;
 984
 985         cost_mergejoin(pathnode, root);
 986
 987         return pathnode;
 988 }
 989
 990 /*
 991  * create_hashjoin_path
 992  *        Creates a pathnode corresponding to a hash join between two relations.
 993  *
 994  * 'joinrel' is the join relation
 995  * 'jointype' is the type of join required
 996  * 'outer_path' is the cheapest outer path
 997  * 'inner_path' is the cheapest inner path
 998  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
 999  * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
1000  *              (this should be a subset of the restrict_clauses list)
1001  */
1002 HashPath *
1003 create_hashjoin_path(Query *root,
1004                                          RelOptInfo *joinrel,
1005                                          JoinType jointype,
1006                                          Path *outer_path,
1007                                          Path *inner_path,
1008                                          List *restrict_clauses,
1009                                          List *hashclauses)
1010 {
1011         HashPath   *pathnode = makeNode(HashPath);
1012
1013         pathnode->jpath.path.pathtype = T_HashJoin;
1014         pathnode->jpath.path.parent = joinrel;
1015         pathnode->jpath.jointype = jointype;
1016         pathnode->jpath.outerjoinpath = outer_path;
1017         pathnode->jpath.innerjoinpath = inner_path;
1018         pathnode->jpath.joinrestrictinfo = restrict_clauses;
1019         /* A hashjoin never has pathkeys, since its ordering is unpredictable */
1020         pathnode->jpath.path.pathkeys = NIL;
1021         pathnode->path_hashclauses = hashclauses;
1022
1023         cost_hashjoin(pathnode, root);
1024
1025         return pathnode;
1026 }