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-2008, 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.144 2008/08/02 21:32:00 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 "optimizer/cost.h"
  23 #include "optimizer/pathnode.h"
  24 #include "optimizer/paths.h"
  25 #include "optimizer/tlist.h"
  26 #include "parser/parse_expr.h"
  27 #include "parser/parse_oper.h"
  28 #include "parser/parsetree.h"
  29 #include "utils/selfuncs.h"
  30 #include "utils/lsyscache.h"
  31 #include "utils/syscache.h"
  32
  33
  34 static List *translate_sub_tlist(List *tlist, int relid);
  35 static bool query_is_distinct_for(Query *query, List *colnos, List *opids);
  36 static Oid      distinct_col_search(int colno, List *colnos, List *opids);
  37 static bool hash_safe_operators(List *opids);
  38
  39
  40 /*****************************************************************************
  41  *              MISC. PATH UTILITIES
  42  *****************************************************************************/
  43
  44 /*
  45  * compare_path_costs
  46  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
  47  *        or more expensive than path2 for the specified criterion.
  48  */
  49 int
  50 compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
  51 {
  52         if (criterion == STARTUP_COST)
  53         {
  54                 if (path1->startup_cost < path2->startup_cost)
  55                         return -1;
  56                 if (path1->startup_cost > path2->startup_cost)
  57                         return +1;
  58
  59                 /*
  60                  * If paths have the same startup cost (not at all unlikely), order
  61                  * them by total cost.
  62                  */
  63                 if (path1->total_cost < path2->total_cost)
  64                         return -1;
  65                 if (path1->total_cost > path2->total_cost)
  66                         return +1;
  67         }
  68         else
  69         {
  70                 if (path1->total_cost < path2->total_cost)
  71                         return -1;
  72                 if (path1->total_cost > path2->total_cost)
  73                         return +1;
  74
  75                 /*
  76                  * If paths have the same total cost, order them by startup cost.
  77                  */
  78                 if (path1->startup_cost < path2->startup_cost)
  79                         return -1;
  80                 if (path1->startup_cost > path2->startup_cost)
  81                         return +1;
  82         }
  83         return 0;
  84 }
  85
  86 /*
  87  * compare_fuzzy_path_costs
  88  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
  89  *        or more expensive than path2 for the specified criterion.
  90  *
  91  * This differs from compare_path_costs in that we consider the costs the
  92  * same if they agree to within a "fuzz factor".  This is used by add_path
  93  * to avoid keeping both of a pair of paths that really have insignificantly
  94  * different cost.
  95  */
  96 static int
  97 compare_fuzzy_path_costs(Path *path1, Path *path2, CostSelector criterion)
  98 {
  99         /*
 100          * We use a fuzz factor of 1% of the smaller cost.
 101          *
 102          * XXX does this percentage need to be user-configurable?
 103          */
 104         if (criterion == STARTUP_COST)
 105         {
 106                 if (path1->startup_cost > path2->startup_cost * 1.01)
 107                         return +1;
 108                 if (path2->startup_cost > path1->startup_cost * 1.01)
 109                         return -1;
 110
 111                 /*
 112                  * If paths have the same startup cost (not at all unlikely), order
 113                  * them by total cost.
 114                  */
 115                 if (path1->total_cost > path2->total_cost * 1.01)
 116                         return +1;
 117                 if (path2->total_cost > path1->total_cost * 1.01)
 118                         return -1;
 119         }
 120         else
 121         {
 122                 if (path1->total_cost > path2->total_cost * 1.01)
 123                         return +1;
 124                 if (path2->total_cost > path1->total_cost * 1.01)
 125                         return -1;
 126
 127                 /*
 128                  * If paths have the same total cost, order them by startup cost.
 129                  */
 130                 if (path1->startup_cost > path2->startup_cost * 1.01)
 131                         return +1;
 132                 if (path2->startup_cost > path1->startup_cost * 1.01)
 133                         return -1;
 134         }
 135         return 0;
 136 }
 137
 138 /*
 139  * compare_path_fractional_costs
 140  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
 141  *        or more expensive than path2 for fetching the specified fraction
 142  *        of the total tuples.
 143  *
 144  * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the
 145  * path with the cheaper total_cost.
 146  */
 147 int
 148 compare_fractional_path_costs(Path *path1, Path *path2,
 149                                                           double fraction)
 150 {
 151         Cost            cost1,
 152                                 cost2;
 153
 154         if (fraction <= 0.0 || fraction >= 1.0)
 155                 return compare_path_costs(path1, path2, TOTAL_COST);
 156         cost1 = path1->startup_cost +
 157                 fraction * (path1->total_cost - path1->startup_cost);
 158         cost2 = path2->startup_cost +
 159                 fraction * (path2->total_cost - path2->startup_cost);
 160         if (cost1 < cost2)
 161                 return -1;
 162         if (cost1 > cost2)
 163                 return +1;
 164         return 0;
 165 }
 166
 167 /*
 168  * set_cheapest
 169  *        Find the minimum-cost paths from among a relation's paths,
 170  *        and save them in the rel's cheapest-path fields.
 171  *
 172  * This is normally called only after we've finished constructing the path
 173  * list for the rel node.
 174  *
 175  * If we find two paths of identical costs, try to keep the better-sorted one.
 176  * The paths might have unrelated sort orderings, in which case we can only
 177  * guess which might be better to keep, but if one is superior then we
 178  * definitely should keep it.
 179  */
 180 void
 181 set_cheapest(RelOptInfo *parent_rel)
 182 {
 183         List       *pathlist = parent_rel->pathlist;
 184         ListCell   *p;
 185         Path       *cheapest_startup_path;
 186         Path       *cheapest_total_path;
 187
 188         Assert(IsA(parent_rel, RelOptInfo));
 189
 190         if (pathlist == NIL)
 191                 elog(ERROR, "could not devise a query plan for the given query");
 192
 193         cheapest_startup_path = cheapest_total_path = (Path *) linitial(pathlist);
 194
 195         for_each_cell(p, lnext(list_head(pathlist)))
 196         {
 197                 Path       *path = (Path *) lfirst(p);
 198                 int                     cmp;
 199
 200                 cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
 201                 if (cmp > 0 ||
 202                         (cmp == 0 &&
 203                          compare_pathkeys(cheapest_startup_path->pathkeys,
 204                                                           path->pathkeys) == PATHKEYS_BETTER2))
 205                         cheapest_startup_path = path;
 206
 207                 cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST);
 208                 if (cmp > 0 ||
 209                         (cmp == 0 &&
 210                          compare_pathkeys(cheapest_total_path->pathkeys,
 211                                                           path->pathkeys) == PATHKEYS_BETTER2))
 212                         cheapest_total_path = path;
 213         }
 214
 215         parent_rel->cheapest_startup_path = cheapest_startup_path;
 216         parent_rel->cheapest_total_path = cheapest_total_path;
 217         parent_rel->cheapest_unique_path = NULL;        /* computed only if needed */
 218 }
 219
 220 /*
 221  * add_path
 222  *        Consider a potential implementation path for the specified parent rel,
 223  *        and add it to the rel's pathlist if it is worthy of consideration.
 224  *        A path is worthy if it has either a better sort order (better pathkeys)
 225  *        or cheaper cost (on either dimension) than any of the existing old paths.
 226  *
 227  *        We also remove from the rel's pathlist any old paths that are dominated
 228  *        by new_path --- that is, new_path is both cheaper and at least as well
 229  *        ordered.
 230  *
 231  *        The pathlist is kept sorted by TOTAL_COST metric, with cheaper paths
 232  *        at the front.  No code depends on that for correctness; it's simply
 233  *        a speed hack within this routine.  Doing it that way makes it more
 234  *        likely that we will reject an inferior path after a few comparisons,
 235  *        rather than many comparisons.
 236  *
 237  *        NOTE: discarded Path objects are immediately pfree'd to reduce planner
 238  *        memory consumption.  We dare not try to free the substructure of a Path,
 239  *        since much of it may be shared with other Paths or the query tree itself;
 240  *        but just recycling discarded Path nodes is a very useful savings in
 241  *        a large join tree.  We can recycle the List nodes of pathlist, too.
 242  *
 243  *        BUT: we do not pfree IndexPath objects, since they may be referenced as
 244  *        children of BitmapHeapPaths as well as being paths in their own right.
 245  *
 246  * 'parent_rel' is the relation entry to which the path corresponds.
 247  * 'new_path' is a potential path for parent_rel.
 248  *
 249  * Returns nothing, but modifies parent_rel->pathlist.
 250  */
 251 void
 252 add_path(RelOptInfo *parent_rel, Path *new_path)
 253 {
 254         bool            accept_new = true;              /* unless we find a superior old path */
 255         ListCell   *insert_after = NULL;        /* where to insert new item */
 256         ListCell   *p1_prev = NULL;
 257         ListCell   *p1;
 258
 259         /*
 260          * This is a convenient place to check for query cancel --- no part of the
 261          * planner goes very long without calling add_path().
 262          */
 263         CHECK_FOR_INTERRUPTS();
 264
 265         /*
 266          * Loop to check proposed new path against old paths.  Note it is possible
 267          * for more than one old path to be tossed out because new_path dominates
 268          * it.
 269          */
 270         p1 = list_head(parent_rel->pathlist);           /* cannot use foreach here */
 271         while (p1 != NULL)
 272         {
 273                 Path       *old_path = (Path *) lfirst(p1);
 274                 bool            remove_old = false; /* unless new proves superior */
 275                 int                     costcmp;
 276
 277                 /*
 278                  * As of Postgres 8.0, we use fuzzy cost comparison to avoid wasting
 279                  * cycles keeping paths that are really not significantly different in
 280                  * cost.
 281                  */
 282                 costcmp = compare_fuzzy_path_costs(new_path, old_path, TOTAL_COST);
 283
 284                 /*
 285                  * If the two paths compare differently for startup and total cost,
 286                  * then we want to keep both, and we can skip the (much slower)
 287                  * comparison of pathkeys.      If they compare the same, proceed with the
 288                  * pathkeys comparison.  Note: this test relies on the fact that
 289                  * compare_fuzzy_path_costs will only return 0 if both costs are
 290                  * effectively equal (and, therefore, there's no need to call it twice
 291                  * in that case).
 292                  */
 293                 if (costcmp == 0 ||
 294                         costcmp == compare_fuzzy_path_costs(new_path, old_path,
 295                                                                                                 STARTUP_COST))
 296                 {
 297                         switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys))
 298                         {
 299                                 case PATHKEYS_EQUAL:
 300                                         if (costcmp < 0)
 301                                                 remove_old = true;              /* new dominates old */
 302                                         else if (costcmp > 0)
 303                                                 accept_new = false;             /* old dominates new */
 304                                         else
 305                                         {
 306                                                 /*
 307                                                  * Same pathkeys, and fuzzily the same cost, so keep
 308                                                  * just one --- but we'll do an exact cost comparison
 309                                                  * to decide which.
 310                                                  */
 311                                                 if (compare_path_costs(new_path, old_path,
 312                                                                                            TOTAL_COST) < 0)
 313                                                         remove_old = true;      /* new dominates old */
 314                                                 else
 315                                                         accept_new = false; /* old equals or dominates new */
 316                                         }
 317                                         break;
 318                                 case PATHKEYS_BETTER1:
 319                                         if (costcmp <= 0)
 320                                                 remove_old = true;              /* new dominates old */
 321                                         break;
 322                                 case PATHKEYS_BETTER2:
 323                                         if (costcmp >= 0)
 324                                                 accept_new = false;             /* old dominates new */
 325                                         break;
 326                                 case PATHKEYS_DIFFERENT:
 327                                         /* keep both paths, since they have different ordering */
 328                                         break;
 329                         }
 330                 }
 331
 332                 /*
 333                  * Remove current element from pathlist if dominated by new.
 334                  */
 335                 if (remove_old)
 336                 {
 337                         parent_rel->pathlist = list_delete_cell(parent_rel->pathlist,
 338                                                                                                         p1, p1_prev);
 339
 340                         /*
 341                          * Delete the data pointed-to by the deleted cell, if possible
 342                          */
 343                         if (!IsA(old_path, IndexPath))
 344                                 pfree(old_path);
 345                         /* Advance list pointer */
 346                         if (p1_prev)
 347                                 p1 = lnext(p1_prev);
 348                         else
 349                                 p1 = list_head(parent_rel->pathlist);
 350                 }
 351                 else
 352                 {
 353                         /* new belongs after this old path if it has cost >= old's */
 354                         if (costcmp >= 0)
 355                                 insert_after = p1;
 356                         /* Advance list pointers */
 357                         p1_prev = p1;
 358                         p1 = lnext(p1);
 359                 }
 360
 361                 /*
 362                  * If we found an old path that dominates new_path, we can quit
 363                  * scanning the pathlist; we will not add new_path, and we assume
 364                  * new_path cannot dominate any other elements of the pathlist.
 365                  */
 366                 if (!accept_new)
 367                         break;
 368         }
 369
 370         if (accept_new)
 371         {
 372                 /* Accept the new path: insert it at proper place in pathlist */
 373                 if (insert_after)
 374                         lappend_cell(parent_rel->pathlist, insert_after, new_path);
 375                 else
 376                         parent_rel->pathlist = lcons(new_path, parent_rel->pathlist);
 377         }
 378         else
 379         {
 380                 /* Reject and recycle the new path */
 381                 if (!IsA(new_path, IndexPath))
 382                         pfree(new_path);
 383         }
 384 }
 385
 386
 387 /*****************************************************************************
 388  *              PATH NODE CREATION ROUTINES
 389  *****************************************************************************/
 390
 391 /*
 392  * create_seqscan_path
 393  *        Creates a path corresponding to a sequential scan, returning the
 394  *        pathnode.
 395  */
 396 Path *
 397 create_seqscan_path(PlannerInfo *root, RelOptInfo *rel)
 398 {
 399         Path       *pathnode = makeNode(Path);
 400
 401         pathnode->pathtype = T_SeqScan;
 402         pathnode->parent = rel;
 403         pathnode->pathkeys = NIL;       /* seqscan has unordered result */
 404
 405         cost_seqscan(pathnode, root, rel);
 406
 407         return pathnode;
 408 }
 409
 410 /*
 411  * create_index_path
 412  *        Creates a path node for an index scan.
 413  *
 414  * 'index' is a usable index.
 415  * 'clause_groups' is a list of lists of RestrictInfo nodes
 416  *                      to be used as index qual conditions in the scan.
 417  * 'pathkeys' describes the ordering of the path.
 418  * 'indexscandir' is ForwardScanDirection or BackwardScanDirection
 419  *                      for an ordered index, or NoMovementScanDirection for
 420  *                      an unordered index.
 421  * 'outer_rel' is the outer relation if this is a join inner indexscan path.
 422  *                      (pathkeys and indexscandir are ignored if so.)  NULL if not.
 423  *
 424  * Returns the new path node.
 425  */
 426 IndexPath *
 427 create_index_path(PlannerInfo *root,
 428                                   IndexOptInfo *index,
 429                                   List *clause_groups,
 430                                   List *pathkeys,
 431                                   ScanDirection indexscandir,
 432                                   RelOptInfo *outer_rel)
 433 {
 434         IndexPath  *pathnode = makeNode(IndexPath);
 435         RelOptInfo *rel = index->rel;
 436         List       *indexquals,
 437                            *allclauses;
 438
 439         /*
 440          * For a join inner scan, there's no point in marking the path with any
 441          * pathkeys, since it will only ever be used as the inner path of a
 442          * nestloop, and so its ordering does not matter.  For the same reason we
 443          * don't really care what order it's scanned in.  (We could expect the
 444          * caller to supply the correct values, but it's easier to force it here.)
 445          */
 446         if (outer_rel != NULL)
 447         {
 448                 pathkeys = NIL;
 449                 indexscandir = NoMovementScanDirection;
 450         }
 451
 452         pathnode->path.pathtype = T_IndexScan;
 453         pathnode->path.parent = rel;
 454         pathnode->path.pathkeys = pathkeys;
 455
 456         /* Convert clauses to indexquals the executor can handle */
 457         indexquals = expand_indexqual_conditions(index, clause_groups);
 458
 459         /* Flatten the clause-groups list to produce indexclauses list */
 460         allclauses = flatten_clausegroups_list(clause_groups);
 461
 462         /* Fill in the pathnode */
 463         pathnode->indexinfo = index;
 464         pathnode->indexclauses = allclauses;
 465         pathnode->indexquals = indexquals;
 466
 467         pathnode->isjoininner = (outer_rel != NULL);
 468         pathnode->indexscandir = indexscandir;
 469
 470         if (outer_rel != NULL)
 471         {
 472                 /*
 473                  * We must compute the estimated number of output rows for the
 474                  * indexscan.  This is less than rel->rows because of the additional
 475                  * selectivity of the join clauses.  Since clause_groups may contain
 476                  * both restriction and join clauses, we have to do a set union to get
 477                  * the full set of clauses that must be considered to compute the
 478                  * correct selectivity.  (Without the union operation, we might have
 479                  * some restriction clauses appearing twice, which'd mislead
 480                  * clauselist_selectivity into double-counting their selectivity.
 481                  * However, since RestrictInfo nodes aren't copied when linking them
 482                  * into different lists, it should be sufficient to use pointer
 483                  * comparison to remove duplicates.)
 484                  *
 485                  * Always assume the join type is JOIN_INNER; even if some of the join
 486                  * clauses come from other contexts, that's not our problem.
 487                  */
 488                 allclauses = list_union_ptr(rel->baserestrictinfo, allclauses);
 489                 pathnode->rows = rel->tuples *
 490                         clauselist_selectivity(root,
 491                                                                    allclauses,
 492                                                                    rel->relid,  /* do not use 0! */
 493                                                                    JOIN_INNER);
 494                 /* Like costsize.c, force estimate to be at least one row */
 495                 pathnode->rows = clamp_row_est(pathnode->rows);
 496         }
 497         else
 498         {
 499                 /*
 500                  * The number of rows is the same as the parent rel's estimate, since
 501                  * this isn't a join inner indexscan.
 502                  */
 503                 pathnode->rows = rel->rows;
 504         }
 505
 506         cost_index(pathnode, root, index, indexquals, outer_rel);
 507
 508         return pathnode;
 509 }
 510
 511 /*
 512  * create_bitmap_heap_path
 513  *        Creates a path node for a bitmap scan.
 514  *
 515  * 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
 516  *
 517  * If this is a join inner indexscan path, 'outer_rel' is the outer relation,
 518  * and all the component IndexPaths should have been costed accordingly.
 519  */
 520 BitmapHeapPath *
 521 create_bitmap_heap_path(PlannerInfo *root,
 522                                                 RelOptInfo *rel,
 523                                                 Path *bitmapqual,
 524                                                 RelOptInfo *outer_rel)
 525 {
 526         BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
 527
 528         pathnode->path.pathtype = T_BitmapHeapScan;
 529         pathnode->path.parent = rel;
 530         pathnode->path.pathkeys = NIL;          /* always unordered */
 531
 532         pathnode->bitmapqual = bitmapqual;
 533         pathnode->isjoininner = (outer_rel != NULL);
 534
 535         if (pathnode->isjoininner)
 536         {
 537                 /*
 538                  * We must compute the estimated number of output rows for the
 539                  * indexscan.  This is less than rel->rows because of the additional
 540                  * selectivity of the join clauses.  We make use of the selectivity
 541                  * estimated for the bitmap to do this; this isn't really quite right
 542                  * since there may be restriction conditions not included in the
 543                  * bitmap ...
 544                  */
 545                 Cost            indexTotalCost;
 546                 Selectivity indexSelectivity;
 547
 548                 cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
 549                 pathnode->rows = rel->tuples * indexSelectivity;
 550                 if (pathnode->rows > rel->rows)
 551                         pathnode->rows = rel->rows;
 552                 /* Like costsize.c, force estimate to be at least one row */
 553                 pathnode->rows = clamp_row_est(pathnode->rows);
 554         }
 555         else
 556         {
 557                 /*
 558                  * The number of rows is the same as the parent rel's estimate, since
 559                  * this isn't a join inner indexscan.
 560                  */
 561                 pathnode->rows = rel->rows;
 562         }
 563
 564         cost_bitmap_heap_scan(&pathnode->path, root, rel, bitmapqual, outer_rel);
 565
 566         return pathnode;
 567 }
 568
 569 /*
 570  * create_bitmap_and_path
 571  *        Creates a path node representing a BitmapAnd.
 572  */
 573 BitmapAndPath *
 574 create_bitmap_and_path(PlannerInfo *root,
 575                                            RelOptInfo *rel,
 576                                            List *bitmapquals)
 577 {
 578         BitmapAndPath *pathnode = makeNode(BitmapAndPath);
 579
 580         pathnode->path.pathtype = T_BitmapAnd;
 581         pathnode->path.parent = rel;
 582         pathnode->path.pathkeys = NIL;          /* always unordered */
 583
 584         pathnode->bitmapquals = bitmapquals;
 585
 586         /* this sets bitmapselectivity as well as the regular cost fields: */
 587         cost_bitmap_and_node(pathnode, root);
 588
 589         return pathnode;
 590 }
 591
 592 /*
 593  * create_bitmap_or_path
 594  *        Creates a path node representing a BitmapOr.
 595  */
 596 BitmapOrPath *
 597 create_bitmap_or_path(PlannerInfo *root,
 598                                           RelOptInfo *rel,
 599                                           List *bitmapquals)
 600 {
 601         BitmapOrPath *pathnode = makeNode(BitmapOrPath);
 602
 603         pathnode->path.pathtype = T_BitmapOr;
 604         pathnode->path.parent = rel;
 605         pathnode->path.pathkeys = NIL;          /* always unordered */
 606
 607         pathnode->bitmapquals = bitmapquals;
 608
 609         /* this sets bitmapselectivity as well as the regular cost fields: */
 610         cost_bitmap_or_node(pathnode, root);
 611
 612         return pathnode;
 613 }
 614
 615 /*
 616  * create_tidscan_path
 617  *        Creates a path corresponding to a scan by TID, returning the pathnode.
 618  */
 619 TidPath *
 620 create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals)
 621 {
 622         TidPath    *pathnode = makeNode(TidPath);
 623
 624         pathnode->path.pathtype = T_TidScan;
 625         pathnode->path.parent = rel;
 626         pathnode->path.pathkeys = NIL;
 627
 628         pathnode->tidquals = tidquals;
 629
 630         cost_tidscan(&pathnode->path, root, rel, tidquals);
 631
 632         return pathnode;
 633 }
 634
 635 /*
 636  * create_append_path
 637  *        Creates a path corresponding to an Append plan, returning the
 638  *        pathnode.
 639  */
 640 AppendPath *
 641 create_append_path(RelOptInfo *rel, List *subpaths)
 642 {
 643         AppendPath *pathnode = makeNode(AppendPath);
 644         ListCell   *l;
 645
 646         pathnode->path.pathtype = T_Append;
 647         pathnode->path.parent = rel;
 648         pathnode->path.pathkeys = NIL;          /* result is always considered
 649                                                                                  * unsorted */
 650         pathnode->subpaths = subpaths;
 651
 652         pathnode->path.startup_cost = 0;
 653         pathnode->path.total_cost = 0;
 654         foreach(l, subpaths)
 655         {
 656                 Path       *subpath = (Path *) lfirst(l);
 657
 658                 if (l == list_head(subpaths))   /* first node? */
 659                         pathnode->path.startup_cost = subpath->startup_cost;
 660                 pathnode->path.total_cost += subpath->total_cost;
 661         }
 662
 663         return pathnode;
 664 }
 665
 666 /*
 667  * create_result_path
 668  *        Creates a path representing a Result-and-nothing-else plan.
 669  *        This is only used for the case of a query with an empty jointree.
 670  */
 671 ResultPath *
 672 create_result_path(List *quals)
 673 {
 674         ResultPath *pathnode = makeNode(ResultPath);
 675
 676         pathnode->path.pathtype = T_Result;
 677         pathnode->path.parent = NULL;
 678         pathnode->path.pathkeys = NIL;
 679         pathnode->quals = quals;
 680
 681         /* Ideally should define cost_result(), but I'm too lazy */
 682         pathnode->path.startup_cost = 0;
 683         pathnode->path.total_cost = cpu_tuple_cost;
 684
 685         /*
 686          * In theory we should include the qual eval cost as well, but at present
 687          * that doesn't accomplish much except duplicate work that will be done
 688          * again in make_result; since this is only used for degenerate cases,
 689          * nothing interesting will be done with the path cost values...
 690          */
 691
 692         return pathnode;
 693 }
 694
 695 /*
 696  * create_material_path
 697  *        Creates a path corresponding to a Material plan, returning the
 698  *        pathnode.
 699  */
 700 MaterialPath *
 701 create_material_path(RelOptInfo *rel, Path *subpath)
 702 {
 703         MaterialPath *pathnode = makeNode(MaterialPath);
 704
 705         pathnode->path.pathtype = T_Material;
 706         pathnode->path.parent = rel;
 707
 708         pathnode->path.pathkeys = subpath->pathkeys;
 709
 710         pathnode->subpath = subpath;
 711
 712         cost_material(&pathnode->path,
 713                                   subpath->total_cost,
 714                                   rel->rows,
 715                                   rel->width);
 716
 717         return pathnode;
 718 }
 719
 720 /*
 721  * create_unique_path
 722  *        Creates a path representing elimination of distinct rows from the
 723  *        input data.
 724  *
 725  * If used at all, this is likely to be called repeatedly on the same rel;
 726  * and the input subpath should always be the same (the cheapest_total path
 727  * for the rel).  So we cache the result.
 728  */
 729 UniquePath *
 730 create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath)
 731 {
 732         UniquePath *pathnode;
 733         Path            sort_path;              /* dummy for result of cost_sort */
 734         Path            agg_path;               /* dummy for result of cost_agg */
 735         MemoryContext oldcontext;
 736         List       *sub_targetlist;
 737         List       *in_operators;
 738         ListCell   *l;
 739         int                     numCols;
 740
 741         /* Caller made a mistake if subpath isn't cheapest_total */
 742         Assert(subpath == rel->cheapest_total_path);
 743
 744         /* If result already cached, return it */
 745         if (rel->cheapest_unique_path)
 746                 return (UniquePath *) rel->cheapest_unique_path;
 747
 748         /*
 749          * We must ensure path struct is allocated in main planning context;
 750          * otherwise GEQO memory management causes trouble.  (Compare
 751          * best_inner_indexscan().)
 752          */
 753         oldcontext = MemoryContextSwitchTo(root->planner_cxt);
 754
 755         pathnode = makeNode(UniquePath);
 756
 757         /* There is no substructure to allocate, so can switch back right away */
 758         MemoryContextSwitchTo(oldcontext);
 759
 760         pathnode->path.pathtype = T_Unique;
 761         pathnode->path.parent = rel;
 762
 763         /*
 764          * Treat the output as always unsorted, since we don't necessarily have
 765          * pathkeys to represent it.
 766          */
 767         pathnode->path.pathkeys = NIL;
 768
 769         pathnode->subpath = subpath;
 770
 771         /*
 772          * Try to identify the targetlist that will actually be unique-ified. In
 773          * current usage, this routine is only used for sub-selects of IN clauses,
 774          * so we should be able to find the tlist in in_info_list.      Get the IN
 775          * clause's operators, too, because they determine what "unique" means.
 776          */
 777         sub_targetlist = NIL;
 778         in_operators = NIL;
 779         foreach(l, root->in_info_list)
 780         {
 781                 InClauseInfo *ininfo = (InClauseInfo *) lfirst(l);
 782
 783                 if (bms_equal(ininfo->righthand, rel->relids))
 784                 {
 785                         sub_targetlist = ininfo->sub_targetlist;
 786                         in_operators = ininfo->in_operators;
 787                         break;
 788                 }
 789         }
 790
 791         /*
 792          * If the input is a subquery whose output must be unique already, then we
 793          * don't need to do anything.  The test for uniqueness has to consider
 794          * exactly which columns we are extracting; for example "SELECT DISTINCT
 795          * x,y" doesn't guarantee that x alone is distinct. So we cannot check for
 796          * this optimization unless we found our own targetlist above, and it
 797          * consists only of simple Vars referencing subquery outputs.  (Possibly
 798          * we could do something with expressions in the subquery outputs, too,
 799          * but for now keep it simple.)
 800          */
 801         if (sub_targetlist && rel->rtekind == RTE_SUBQUERY)
 802         {
 803                 RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
 804                 List       *sub_tlist_colnos;
 805
 806                 sub_tlist_colnos = translate_sub_tlist(sub_targetlist, rel->relid);
 807
 808                 if (sub_tlist_colnos &&
 809                         query_is_distinct_for(rte->subquery,
 810                                                                   sub_tlist_colnos, in_operators))
 811                 {
 812                         pathnode->umethod = UNIQUE_PATH_NOOP;
 813                         pathnode->rows = rel->rows;
 814                         pathnode->path.startup_cost = subpath->startup_cost;
 815                         pathnode->path.total_cost = subpath->total_cost;
 816                         pathnode->path.pathkeys = subpath->pathkeys;
 817
 818                         rel->cheapest_unique_path = (Path *) pathnode;
 819
 820                         return pathnode;
 821                 }
 822         }
 823
 824         /*
 825          * If we know the targetlist, try to estimate number of result rows;
 826          * otherwise punt.
 827          */
 828         if (sub_targetlist)
 829         {
 830                 pathnode->rows = estimate_num_groups(root, sub_targetlist, rel->rows);
 831                 numCols = list_length(sub_targetlist);
 832         }
 833         else
 834         {
 835                 pathnode->rows = rel->rows;
 836                 numCols = list_length(rel->reltargetlist);
 837         }
 838
 839         /*
 840          * Estimate cost for sort+unique implementation
 841          */
 842         cost_sort(&sort_path, root, NIL,
 843                           subpath->total_cost,
 844                           rel->rows,
 845                           rel->width,
 846                           -1.0);
 847
 848         /*
 849          * Charge one cpu_operator_cost per comparison per input tuple. We assume
 850          * all columns get compared at most of the tuples.      (XXX probably this is
 851          * an overestimate.)  This should agree with make_unique.
 852          */
 853         sort_path.total_cost += cpu_operator_cost * rel->rows * numCols;
 854
 855         /*
 856          * Is it safe to use a hashed implementation?  If so, estimate and compare
 857          * costs.  We only try this if we know the IN operators, else we can't
 858          * check their hashability.
 859          */
 860         pathnode->umethod = UNIQUE_PATH_SORT;
 861         if (enable_hashagg && in_operators && hash_safe_operators(in_operators))
 862         {
 863                 /*
 864                  * Estimate the overhead per hashtable entry at 64 bytes (same as in
 865                  * planner.c).
 866                  */
 867                 int                     hashentrysize = rel->width + 64;
 868
 869                 if (hashentrysize * pathnode->rows <= work_mem * 1024L)
 870                 {
 871                         cost_agg(&agg_path, root,
 872                                          AGG_HASHED, 0,
 873                                          numCols, pathnode->rows,
 874                                          subpath->startup_cost,
 875                                          subpath->total_cost,
 876                                          rel->rows);
 877                         if (agg_path.total_cost < sort_path.total_cost)
 878                                 pathnode->umethod = UNIQUE_PATH_HASH;
 879                 }
 880         }
 881
 882         if (pathnode->umethod == UNIQUE_PATH_HASH)
 883         {
 884                 pathnode->path.startup_cost = agg_path.startup_cost;
 885                 pathnode->path.total_cost = agg_path.total_cost;
 886         }
 887         else
 888         {
 889                 pathnode->path.startup_cost = sort_path.startup_cost;
 890                 pathnode->path.total_cost = sort_path.total_cost;
 891         }
 892
 893         rel->cheapest_unique_path = (Path *) pathnode;
 894
 895         return pathnode;
 896 }
 897
 898 /*
 899  * translate_sub_tlist - get subquery column numbers represented by tlist
 900  *
 901  * The given targetlist usually contains only Vars referencing the given relid.
 902  * Extract their varattnos (ie, the column numbers of the subquery) and return
 903  * as an integer List.
 904  *
 905  * If any of the tlist items is not a simple Var, we cannot determine whether
 906  * the subquery's uniqueness condition (if any) matches ours, so punt and
 907  * return NIL.
 908  */
 909 static List *
 910 translate_sub_tlist(List *tlist, int relid)
 911 {
 912         List       *result = NIL;
 913         ListCell   *l;
 914
 915         foreach(l, tlist)
 916         {
 917                 Var                *var = (Var *) lfirst(l);
 918
 919                 if (!var || !IsA(var, Var) ||
 920                         var->varno != relid)
 921                         return NIL;                     /* punt */
 922
 923                 result = lappend_int(result, var->varattno);
 924         }
 925         return result;
 926 }
 927
 928 /*
 929  * query_is_distinct_for - does query never return duplicates of the
 930  *              specified columns?
 931  *
 932  * colnos is an integer list of output column numbers (resno's).  We are
 933  * interested in whether rows consisting of just these columns are certain
 934  * to be distinct.      "Distinctness" is defined according to whether the
 935  * corresponding upper-level equality operators listed in opids would think
 936  * the values are distinct.  (Note: the opids entries could be cross-type
 937  * operators, and thus not exactly the equality operators that the subquery
 938  * would use itself.  We use equality_ops_are_compatible() to check
 939  * compatibility.  That looks at btree or hash opfamily membership, and so
 940  * should give trustworthy answers for all operators that we might need
 941  * to deal with here.)
 942  */
 943 static bool
 944 query_is_distinct_for(Query *query, List *colnos, List *opids)
 945 {
 946         ListCell   *l;
 947         Oid                     opid;
 948
 949         Assert(list_length(colnos) == list_length(opids));
 950
 951         /*
 952          * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
 953          * columns in the DISTINCT clause appear in colnos and operator semantics
 954          * match.
 955          */
 956         if (query->distinctClause)
 957         {
 958                 foreach(l, query->distinctClause)
 959                 {
 960                         SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
 961                         TargetEntry *tle = get_sortgroupclause_tle(sgc,
 962                                                                                                            query->targetList);
 963
 964                         opid = distinct_col_search(tle->resno, colnos, opids);
 965                         if (!OidIsValid(opid) ||
 966                                 !equality_ops_are_compatible(opid, sgc->eqop))
 967                                 break;                  /* exit early if no match */
 968                 }
 969                 if (l == NULL)                  /* had matches for all? */
 970                         return true;
 971         }
 972
 973         /*
 974          * Similarly, GROUP BY guarantees uniqueness if all the grouped columns
 975          * appear in colnos and operator semantics match.
 976          */
 977         if (query->groupClause)
 978         {
 979                 foreach(l, query->groupClause)
 980                 {
 981                         SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
 982                         TargetEntry *tle = get_sortgroupclause_tle(sgc,
 983                                                                                                            query->targetList);
 984
 985                         opid = distinct_col_search(tle->resno, colnos, opids);
 986                         if (!OidIsValid(opid) ||
 987                                 !equality_ops_are_compatible(opid, sgc->eqop))
 988                                 break;                  /* exit early if no match */
 989                 }
 990                 if (l == NULL)                  /* had matches for all? */
 991                         return true;
 992         }
 993         else
 994         {
 995                 /*
 996                  * If we have no GROUP BY, but do have aggregates or HAVING, then the
 997                  * result is at most one row so it's surely unique, for any operators.
 998                  */
 999                 if (query->hasAggs || query->havingQual)
1000                         return true;
1001         }
1002
1003         /*
1004          * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
1005          * except with ALL.
1006          *
1007          * XXX this code knows that prepunion.c will adopt the default sort/group
1008          * operators for each column datatype to determine uniqueness.  It'd
1009          * probably be better if these operators were chosen at parse time and
1010          * stored into the parsetree, instead of leaving bits of the planner to
1011          * decide semantics.
1012          */
1013         if (query->setOperations)
1014         {
1015                 SetOperationStmt *topop = (SetOperationStmt *) query->setOperations;
1016
1017                 Assert(IsA(topop, SetOperationStmt));
1018                 Assert(topop->op != SETOP_NONE);
1019
1020                 if (!topop->all)
1021                 {
1022                         /* We're good if all the nonjunk output columns are in colnos */
1023                         foreach(l, query->targetList)
1024                         {
1025                                 TargetEntry *tle = (TargetEntry *) lfirst(l);
1026                                 Oid             tle_eq_opr;
1027
1028                                 if (tle->resjunk)
1029                                         continue;       /* ignore resjunk columns */
1030
1031                                 opid = distinct_col_search(tle->resno, colnos, opids);
1032                                 if (!OidIsValid(opid))
1033                                         break;          /* exit early if no match */
1034                                 /* check for compatible semantics */
1035                                 get_sort_group_operators(exprType((Node *) tle->expr),
1036                                                                                  false, false, false,
1037                                                                                  NULL, &tle_eq_opr, NULL);
1038                                 if (!OidIsValid(tle_eq_opr) ||
1039                                         !equality_ops_are_compatible(opid, tle_eq_opr))
1040                                         break;          /* exit early if no match */
1041                         }
1042                         if (l == NULL)          /* had matches for all? */
1043                                 return true;
1044                 }
1045         }
1046
1047         /*
1048          * XXX Are there any other cases in which we can easily see the result
1049          * must be distinct?
1050          */
1051
1052         return false;
1053 }
1054
1055 /*
1056  * distinct_col_search - subroutine for query_is_distinct_for
1057  *
1058  * If colno is in colnos, return the corresponding element of opids,
1059  * else return InvalidOid.      (We expect colnos does not contain duplicates,
1060  * so the result is well-defined.)
1061  */
1062 static Oid
1063 distinct_col_search(int colno, List *colnos, List *opids)
1064 {
1065         ListCell   *lc1,
1066                            *lc2;
1067
1068         forboth(lc1, colnos, lc2, opids)
1069         {
1070                 if (colno == lfirst_int(lc1))
1071                         return lfirst_oid(lc2);
1072         }
1073         return InvalidOid;
1074 }
1075
1076 /*
1077  * hash_safe_operators - can all the specified IN operators be hashed?
1078  *
1079  * We assume hashed aggregation will work if each IN operator is marked
1080  * hashjoinable.  If the IN operators are cross-type, this could conceivably
1081  * fail: the aggregation will need a hashable equality operator for the RHS
1082  * datatype --- but it's pretty hard to conceive of a hash opfamily that has
1083  * cross-type hashing without support for hashing the individual types, so
1084  * we don't expend cycles here to support the case.  We could check
1085  * get_compatible_hash_operator() instead of just op_hashjoinable(), but the
1086  * former is a significantly more expensive test.
1087  */
1088 static bool
1089 hash_safe_operators(List *opids)
1090 {
1091         ListCell   *lc;
1092
1093         foreach(lc, opids)
1094         {
1095                 if (!op_hashjoinable(lfirst_oid(lc)))
1096                         return false;
1097         }
1098         return true;
1099 }
1100
1101 /*
1102  * create_subqueryscan_path
1103  *        Creates a path corresponding to a sequential scan of a subquery,
1104  *        returning the pathnode.
1105  */
1106 Path *
1107 create_subqueryscan_path(RelOptInfo *rel, List *pathkeys)
1108 {
1109         Path       *pathnode = makeNode(Path);
1110
1111         pathnode->pathtype = T_SubqueryScan;
1112         pathnode->parent = rel;
1113         pathnode->pathkeys = pathkeys;
1114
1115         cost_subqueryscan(pathnode, rel);
1116
1117         return pathnode;
1118 }
1119
1120 /*
1121  * create_functionscan_path
1122  *        Creates a path corresponding to a sequential scan of a function,
1123  *        returning the pathnode.
1124  */
1125 Path *
1126 create_functionscan_path(PlannerInfo *root, RelOptInfo *rel)
1127 {
1128         Path       *pathnode = makeNode(Path);
1129
1130         pathnode->pathtype = T_FunctionScan;
1131         pathnode->parent = rel;
1132         pathnode->pathkeys = NIL;       /* for now, assume unordered result */
1133
1134         cost_functionscan(pathnode, root, rel);
1135
1136         return pathnode;
1137 }
1138
1139 /*
1140  * create_valuesscan_path
1141  *        Creates a path corresponding to a scan of a VALUES list,
1142  *        returning the pathnode.
1143  */
1144 Path *
1145 create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel)
1146 {
1147         Path       *pathnode = makeNode(Path);
1148
1149         pathnode->pathtype = T_ValuesScan;
1150         pathnode->parent = rel;
1151         pathnode->pathkeys = NIL;       /* result is always unordered */
1152
1153         cost_valuesscan(pathnode, root, rel);
1154
1155         return pathnode;
1156 }
1157
1158 /*
1159  * create_nestloop_path
1160  *        Creates a pathnode corresponding to a nestloop join between two
1161  *        relations.
1162  *
1163  * 'joinrel' is the join relation.
1164  * 'jointype' is the type of join required
1165  * 'outer_path' is the outer path
1166  * 'inner_path' is the inner path
1167  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
1168  * 'pathkeys' are the path keys of the new join path
1169  *
1170  * Returns the resulting path node.
1171  */
1172 NestPath *
1173 create_nestloop_path(PlannerInfo *root,
1174                                          RelOptInfo *joinrel,
1175                                          JoinType jointype,
1176                                          Path *outer_path,
1177                                          Path *inner_path,
1178                                          List *restrict_clauses,
1179                                          List *pathkeys)
1180 {
1181         NestPath   *pathnode = makeNode(NestPath);
1182
1183         pathnode->path.pathtype = T_NestLoop;
1184         pathnode->path.parent = joinrel;
1185         pathnode->jointype = jointype;
1186         pathnode->outerjoinpath = outer_path;
1187         pathnode->innerjoinpath = inner_path;
1188         pathnode->joinrestrictinfo = restrict_clauses;
1189         pathnode->path.pathkeys = pathkeys;
1190
1191         cost_nestloop(pathnode, root);
1192
1193         return pathnode;
1194 }
1195
1196 /*
1197  * create_mergejoin_path
1198  *        Creates a pathnode corresponding to a mergejoin join between
1199  *        two relations
1200  *
1201  * 'joinrel' is the join relation
1202  * 'jointype' is the type of join required
1203  * 'outer_path' is the outer path
1204  * 'inner_path' is the inner path
1205  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
1206  * 'pathkeys' are the path keys of the new join path
1207  * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
1208  *              (this should be a subset of the restrict_clauses list)
1209  * 'outersortkeys' are the sort varkeys for the outer relation
1210  * 'innersortkeys' are the sort varkeys for the inner relation
1211  */
1212 MergePath *
1213 create_mergejoin_path(PlannerInfo *root,
1214                                           RelOptInfo *joinrel,
1215                                           JoinType jointype,
1216                                           Path *outer_path,
1217                                           Path *inner_path,
1218                                           List *restrict_clauses,
1219                                           List *pathkeys,
1220                                           List *mergeclauses,
1221                                           List *outersortkeys,
1222                                           List *innersortkeys)
1223 {
1224         MergePath  *pathnode = makeNode(MergePath);
1225
1226         /*
1227          * If the given paths are already well enough ordered, we can skip doing
1228          * an explicit sort.
1229          */
1230         if (outersortkeys &&
1231                 pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
1232                 outersortkeys = NIL;
1233         if (innersortkeys &&
1234                 pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
1235                 innersortkeys = NIL;
1236
1237         /*
1238          * If we are not sorting the inner path, we may need a materialize node to
1239          * ensure it can be marked/restored.  (Sort does support mark/restore, so
1240          * no materialize is needed in that case.)
1241          *
1242          * Since the inner side must be ordered, and only Sorts and IndexScans can
1243          * create order to begin with, you might think there's no problem --- but
1244          * you'd be wrong.  Nestloop and merge joins can *preserve* the order of
1245          * their inputs, so they can be selected as the input of a mergejoin, and
1246          * they don't support mark/restore at present.
1247          */
1248         if (innersortkeys == NIL &&
1249                 !ExecSupportsMarkRestore(inner_path->pathtype))
1250                 inner_path = (Path *)
1251                         create_material_path(inner_path->parent, inner_path);
1252
1253         pathnode->jpath.path.pathtype = T_MergeJoin;
1254         pathnode->jpath.path.parent = joinrel;
1255         pathnode->jpath.jointype = jointype;
1256         pathnode->jpath.outerjoinpath = outer_path;
1257         pathnode->jpath.innerjoinpath = inner_path;
1258         pathnode->jpath.joinrestrictinfo = restrict_clauses;
1259         pathnode->jpath.path.pathkeys = pathkeys;
1260         pathnode->path_mergeclauses = mergeclauses;
1261         pathnode->outersortkeys = outersortkeys;
1262         pathnode->innersortkeys = innersortkeys;
1263
1264         cost_mergejoin(pathnode, root);
1265
1266         return pathnode;
1267 }
1268
1269 /*
1270  * create_hashjoin_path
1271  *        Creates a pathnode corresponding to a hash join between two relations.
1272  *
1273  * 'joinrel' is the join relation
1274  * 'jointype' is the type of join required
1275  * 'outer_path' is the cheapest outer path
1276  * 'inner_path' is the cheapest inner path
1277  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
1278  * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
1279  *              (this should be a subset of the restrict_clauses list)
1280  */
1281 HashPath *
1282 create_hashjoin_path(PlannerInfo *root,
1283                                          RelOptInfo *joinrel,
1284                                          JoinType jointype,
1285                                          Path *outer_path,
1286                                          Path *inner_path,
1287                                          List *restrict_clauses,
1288                                          List *hashclauses)
1289 {
1290         HashPath   *pathnode = makeNode(HashPath);
1291
1292         pathnode->jpath.path.pathtype = T_HashJoin;
1293         pathnode->jpath.path.parent = joinrel;
1294         pathnode->jpath.jointype = jointype;
1295         pathnode->jpath.outerjoinpath = outer_path;
1296         pathnode->jpath.innerjoinpath = inner_path;
1297         pathnode->jpath.joinrestrictinfo = restrict_clauses;
1298         /* A hashjoin never has pathkeys, since its ordering is unpredictable */
1299         pathnode->jpath.path.pathkeys = NIL;
1300         pathnode->path_hashclauses = hashclauses;
1301
1302         cost_hashjoin(pathnode, root);
1303
1304         return pathnode;
1305 }