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-2015, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/optimizer/util/pathnode.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include <math.h>
  18
  19 #include "miscadmin.h"
  20 #include "nodes/nodeFuncs.h"
  21 #include "optimizer/clauses.h"
  22 #include "optimizer/cost.h"
  23 #include "optimizer/pathnode.h"
  24 #include "optimizer/paths.h"
  25 #include "optimizer/planmain.h"
  26 #include "optimizer/restrictinfo.h"
  27 #include "optimizer/var.h"
  28 #include "parser/parsetree.h"
  29 #include "utils/lsyscache.h"
  30 #include "utils/selfuncs.h"
  31
  32
  33 typedef enum
  34 {
  35         COSTS_EQUAL,                            /* path costs are fuzzily equal */
  36         COSTS_BETTER1,                          /* first path is cheaper than second */
  37         COSTS_BETTER2,                          /* second path is cheaper than first */
  38         COSTS_DIFFERENT                         /* neither path dominates the other on cost */
  39 } PathCostComparison;
  40
  41 /*
  42  * STD_FUZZ_FACTOR is the normal fuzz factor for compare_path_costs_fuzzily.
  43  * XXX is it worth making this user-controllable?  It provides a tradeoff
  44  * between planner runtime and the accuracy of path cost comparisons.
  45  */
  46 #define STD_FUZZ_FACTOR 1.01
  47
  48 static List *translate_sub_tlist(List *tlist, int relid);
  49
  50
  51 /*****************************************************************************
  52  *              MISC. PATH UTILITIES
  53  *****************************************************************************/
  54
  55 /*
  56  * compare_path_costs
  57  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
  58  *        or more expensive than path2 for the specified criterion.
  59  */
  60 int
  61 compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
  62 {
  63         if (criterion == STARTUP_COST)
  64         {
  65                 if (path1->startup_cost < path2->startup_cost)
  66                         return -1;
  67                 if (path1->startup_cost > path2->startup_cost)
  68                         return +1;
  69
  70                 /*
  71                  * If paths have the same startup cost (not at all unlikely), order
  72                  * them by total cost.
  73                  */
  74                 if (path1->total_cost < path2->total_cost)
  75                         return -1;
  76                 if (path1->total_cost > path2->total_cost)
  77                         return +1;
  78         }
  79         else
  80         {
  81                 if (path1->total_cost < path2->total_cost)
  82                         return -1;
  83                 if (path1->total_cost > path2->total_cost)
  84                         return +1;
  85
  86                 /*
  87                  * If paths have the same total cost, order them by startup cost.
  88                  */
  89                 if (path1->startup_cost < path2->startup_cost)
  90                         return -1;
  91                 if (path1->startup_cost > path2->startup_cost)
  92                         return +1;
  93         }
  94         return 0;
  95 }
  96
  97 /*
  98  * compare_path_fractional_costs
  99  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
 100  *        or more expensive than path2 for fetching the specified fraction
 101  *        of the total tuples.
 102  *
 103  * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the
 104  * path with the cheaper total_cost.
 105  */
 106 int
 107 compare_fractional_path_costs(Path *path1, Path *path2,
 108                                                           double fraction)
 109 {
 110         Cost            cost1,
 111                                 cost2;
 112
 113         if (fraction <= 0.0 || fraction >= 1.0)
 114                 return compare_path_costs(path1, path2, TOTAL_COST);
 115         cost1 = path1->startup_cost +
 116                 fraction * (path1->total_cost - path1->startup_cost);
 117         cost2 = path2->startup_cost +
 118                 fraction * (path2->total_cost - path2->startup_cost);
 119         if (cost1 < cost2)
 120                 return -1;
 121         if (cost1 > cost2)
 122                 return +1;
 123         return 0;
 124 }
 125
 126 /*
 127  * compare_path_costs_fuzzily
 128  *        Compare the costs of two paths to see if either can be said to
 129  *        dominate the other.
 130  *
 131  * We use fuzzy comparisons so that add_path() can avoid keeping both of
 132  * a pair of paths that really have insignificantly different cost.
 133  *
 134  * The fuzz_factor argument must be 1.0 plus delta, where delta is the
 135  * fraction of the smaller cost that is considered to be a significant
 136  * difference.  For example, fuzz_factor = 1.01 makes the fuzziness limit
 137  * be 1% of the smaller cost.
 138  *
 139  * The two paths are said to have "equal" costs if both startup and total
 140  * costs are fuzzily the same.  Path1 is said to be better than path2 if
 141  * it has fuzzily better startup cost and fuzzily no worse total cost,
 142  * or if it has fuzzily better total cost and fuzzily no worse startup cost.
 143  * Path2 is better than path1 if the reverse holds.  Finally, if one path
 144  * is fuzzily better than the other on startup cost and fuzzily worse on
 145  * total cost, we just say that their costs are "different", since neither
 146  * dominates the other across the whole performance spectrum.
 147  *
 148  * This function also enforces a policy rule that paths for which the relevant
 149  * one of parent->consider_startup and parent->consider_param_startup is false
 150  * cannot survive comparisons solely on the grounds of good startup cost, so
 151  * we never return COSTS_DIFFERENT when that is true for the total-cost loser.
 152  * (But if total costs are fuzzily equal, we compare startup costs anyway,
 153  * in hopes of eliminating one path or the other.)
 154  */
 155 static PathCostComparison
 156 compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor)
 157 {
 158 #define CONSIDER_PATH_STARTUP_COST(p)  \
 159         ((p)->param_info == NULL ? (p)->parent->consider_startup : (p)->parent->consider_param_startup)
 160
 161         /*
 162          * Check total cost first since it's more likely to be different; many
 163          * paths have zero startup cost.
 164          */
 165         if (path1->total_cost > path2->total_cost * fuzz_factor)
 166         {
 167                 /* path1 fuzzily worse on total cost */
 168                 if (CONSIDER_PATH_STARTUP_COST(path1) &&
 169                         path2->startup_cost > path1->startup_cost * fuzz_factor)
 170                 {
 171                         /* ... but path2 fuzzily worse on startup, so DIFFERENT */
 172                         return COSTS_DIFFERENT;
 173                 }
 174                 /* else path2 dominates */
 175                 return COSTS_BETTER2;
 176         }
 177         if (path2->total_cost > path1->total_cost * fuzz_factor)
 178         {
 179                 /* path2 fuzzily worse on total cost */
 180                 if (CONSIDER_PATH_STARTUP_COST(path2) &&
 181                         path1->startup_cost > path2->startup_cost * fuzz_factor)
 182                 {
 183                         /* ... but path1 fuzzily worse on startup, so DIFFERENT */
 184                         return COSTS_DIFFERENT;
 185                 }
 186                 /* else path1 dominates */
 187                 return COSTS_BETTER1;
 188         }
 189         /* fuzzily the same on total cost ... */
 190         if (path1->startup_cost > path2->startup_cost * fuzz_factor)
 191         {
 192                 /* ... but path1 fuzzily worse on startup, so path2 wins */
 193                 return COSTS_BETTER2;
 194         }
 195         if (path2->startup_cost > path1->startup_cost * fuzz_factor)
 196         {
 197                 /* ... but path2 fuzzily worse on startup, so path1 wins */
 198                 return COSTS_BETTER1;
 199         }
 200         /* fuzzily the same on both costs */
 201         return COSTS_EQUAL;
 202
 203 #undef CONSIDER_PATH_STARTUP_COST
 204 }
 205
 206 /*
 207  * set_cheapest
 208  *        Find the minimum-cost paths from among a relation's paths,
 209  *        and save them in the rel's cheapest-path fields.
 210  *
 211  * cheapest_total_path is normally the cheapest-total-cost unparameterized
 212  * path; but if there are no unparameterized paths, we assign it to be the
 213  * best (cheapest least-parameterized) parameterized path.  However, only
 214  * unparameterized paths are considered candidates for cheapest_startup_path,
 215  * so that will be NULL if there are no unparameterized paths.
 216  *
 217  * The cheapest_parameterized_paths list collects all parameterized paths
 218  * that have survived the add_path() tournament for this relation.  (Since
 219  * add_path ignores pathkeys for a parameterized path, these will be paths
 220  * that have best cost or best row count for their parameterization.)
 221  * cheapest_parameterized_paths always includes the cheapest-total
 222  * unparameterized path, too, if there is one; the users of that list find
 223  * it more convenient if that's included.
 224  *
 225  * This is normally called only after we've finished constructing the path
 226  * list for the rel node.
 227  */
 228 void
 229 set_cheapest(RelOptInfo *parent_rel)
 230 {
 231         Path       *cheapest_startup_path;
 232         Path       *cheapest_total_path;
 233         Path       *best_param_path;
 234         List       *parameterized_paths;
 235         ListCell   *p;
 236
 237         Assert(IsA(parent_rel, RelOptInfo));
 238
 239         if (parent_rel->pathlist == NIL)
 240                 elog(ERROR, "could not devise a query plan for the given query");
 241
 242         cheapest_startup_path = cheapest_total_path = best_param_path = NULL;
 243         parameterized_paths = NIL;
 244
 245         foreach(p, parent_rel->pathlist)
 246         {
 247                 Path       *path = (Path *) lfirst(p);
 248                 int                     cmp;
 249
 250                 if (path->param_info)
 251                 {
 252                         /* Parameterized path, so add it to parameterized_paths */
 253                         parameterized_paths = lappend(parameterized_paths, path);
 254
 255                         /*
 256                          * If we have an unparameterized cheapest-total, we no longer care
 257                          * about finding the best parameterized path, so move on.
 258                          */
 259                         if (cheapest_total_path)
 260                                 continue;
 261
 262                         /*
 263                          * Otherwise, track the best parameterized path, which is the one
 264                          * with least total cost among those of the minimum
 265                          * parameterization.
 266                          */
 267                         if (best_param_path == NULL)
 268                                 best_param_path = path;
 269                         else
 270                         {
 271                                 switch (bms_subset_compare(PATH_REQ_OUTER(path),
 272                                                                                    PATH_REQ_OUTER(best_param_path)))
 273                                 {
 274                                         case BMS_EQUAL:
 275                                                 /* keep the cheaper one */
 276                                                 if (compare_path_costs(path, best_param_path,
 277                                                                                            TOTAL_COST) < 0)
 278                                                         best_param_path = path;
 279                                                 break;
 280                                         case BMS_SUBSET1:
 281                                                 /* new path is less-parameterized */
 282                                                 best_param_path = path;
 283                                                 break;
 284                                         case BMS_SUBSET2:
 285                                                 /* old path is less-parameterized, keep it */
 286                                                 break;
 287                                         case BMS_DIFFERENT:
 288
 289                                                 /*
 290                                                  * This means that neither path has the least possible
 291                                                  * parameterization for the rel.  We'll sit on the old
 292                                                  * path until something better comes along.
 293                                                  */
 294                                                 break;
 295                                 }
 296                         }
 297                 }
 298                 else
 299                 {
 300                         /* Unparameterized path, so consider it for cheapest slots */
 301                         if (cheapest_total_path == NULL)
 302                         {
 303                                 cheapest_startup_path = cheapest_total_path = path;
 304                                 continue;
 305                         }
 306
 307                         /*
 308                          * If we find two paths of identical costs, try to keep the
 309                          * better-sorted one.  The paths might have unrelated sort
 310                          * orderings, in which case we can only guess which might be
 311                          * better to keep, but if one is superior then we definitely
 312                          * should keep that one.
 313                          */
 314                         cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
 315                         if (cmp > 0 ||
 316                                 (cmp == 0 &&
 317                                  compare_pathkeys(cheapest_startup_path->pathkeys,
 318                                                                   path->pathkeys) == PATHKEYS_BETTER2))
 319                                 cheapest_startup_path = path;
 320
 321                         cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST);
 322                         if (cmp > 0 ||
 323                                 (cmp == 0 &&
 324                                  compare_pathkeys(cheapest_total_path->pathkeys,
 325                                                                   path->pathkeys) == PATHKEYS_BETTER2))
 326                                 cheapest_total_path = path;
 327                 }
 328         }
 329
 330         /* Add cheapest unparameterized path, if any, to parameterized_paths */
 331         if (cheapest_total_path)
 332                 parameterized_paths = lcons(cheapest_total_path, parameterized_paths);
 333
 334         /*
 335          * If there is no unparameterized path, use the best parameterized path as
 336          * cheapest_total_path (but not as cheapest_startup_path).
 337          */
 338         if (cheapest_total_path == NULL)
 339                 cheapest_total_path = best_param_path;
 340         Assert(cheapest_total_path != NULL);
 341
 342         parent_rel->cheapest_startup_path = cheapest_startup_path;
 343         parent_rel->cheapest_total_path = cheapest_total_path;
 344         parent_rel->cheapest_unique_path = NULL;        /* computed only if needed */
 345         parent_rel->cheapest_parameterized_paths = parameterized_paths;
 346 }
 347
 348 /*
 349  * add_path
 350  *        Consider a potential implementation path for the specified parent rel,
 351  *        and add it to the rel's pathlist if it is worthy of consideration.
 352  *        A path is worthy if it has a better sort order (better pathkeys) or
 353  *        cheaper cost (on either dimension), or generates fewer rows, than any
 354  *        existing path that has the same or superset parameterization rels.
 355  *
 356  *        We also remove from the rel's pathlist any old paths that are dominated
 357  *        by new_path --- that is, new_path is cheaper, at least as well ordered,
 358  *        generates no more rows, and requires no outer rels not required by the
 359  *        old path.
 360  *
 361  *        In most cases, a path with a superset parameterization will generate
 362  *        fewer rows (since it has more join clauses to apply), so that those two
 363  *        figures of merit move in opposite directions; this means that a path of
 364  *        one parameterization can seldom dominate a path of another.  But such
 365  *        cases do arise, so we make the full set of checks anyway.
 366  *
 367  *        There are two policy decisions embedded in this function, along with
 368  *        its sibling add_path_precheck.  First, we treat all parameterized paths
 369  *        as having NIL pathkeys, so that they cannot win comparisons on the
 370  *        basis of sort order.  This is to reduce the number of parameterized
 371  *        paths that are kept; see discussion in src/backend/optimizer/README.
 372  *
 373  *        Second, we only consider cheap startup cost to be interesting if
 374  *        parent_rel->consider_startup is true for an unparameterized path, or
 375  *        parent_rel->consider_param_startup is true for a parameterized one.
 376  *        Again, this allows discarding useless paths sooner.
 377  *
 378  *        The pathlist is kept sorted by total_cost, with cheaper paths
 379  *        at the front.  Within this routine, that's simply a speed hack:
 380  *        doing it that way makes it more likely that we will reject an inferior
 381  *        path after a few comparisons, rather than many comparisons.
 382  *        However, add_path_precheck relies on this ordering to exit early
 383  *        when possible.
 384  *
 385  *        NOTE: discarded Path objects are immediately pfree'd to reduce planner
 386  *        memory consumption.  We dare not try to free the substructure of a Path,
 387  *        since much of it may be shared with other Paths or the query tree itself;
 388  *        but just recycling discarded Path nodes is a very useful savings in
 389  *        a large join tree.  We can recycle the List nodes of pathlist, too.
 390  *
 391  *        BUT: we do not pfree IndexPath objects, since they may be referenced as
 392  *        children of BitmapHeapPaths as well as being paths in their own right.
 393  *
 394  * 'parent_rel' is the relation entry to which the path corresponds.
 395  * 'new_path' is a potential path for parent_rel.
 396  *
 397  * Returns nothing, but modifies parent_rel->pathlist.
 398  */
 399 void
 400 add_path(RelOptInfo *parent_rel, Path *new_path)
 401 {
 402         bool            accept_new = true;              /* unless we find a superior old path */
 403         ListCell   *insert_after = NULL;        /* where to insert new item */
 404         List       *new_path_pathkeys;
 405         ListCell   *p1;
 406         ListCell   *p1_prev;
 407         ListCell   *p1_next;
 408
 409         /*
 410          * This is a convenient place to check for query cancel --- no part of the
 411          * planner goes very long without calling add_path().
 412          */
 413         CHECK_FOR_INTERRUPTS();
 414
 415         /* Pretend parameterized paths have no pathkeys, per comment above */
 416         new_path_pathkeys = new_path->param_info ? NIL : new_path->pathkeys;
 417
 418         /*
 419          * Loop to check proposed new path against old paths.  Note it is possible
 420          * for more than one old path to be tossed out because new_path dominates
 421          * it.
 422          *
 423          * We can't use foreach here because the loop body may delete the current
 424          * list cell.
 425          */
 426         p1_prev = NULL;
 427         for (p1 = list_head(parent_rel->pathlist); p1 != NULL; p1 = p1_next)
 428         {
 429                 Path       *old_path = (Path *) lfirst(p1);
 430                 bool            remove_old = false; /* unless new proves superior */
 431                 PathCostComparison costcmp;
 432                 PathKeysComparison keyscmp;
 433                 BMS_Comparison outercmp;
 434
 435                 p1_next = lnext(p1);
 436
 437                 /*
 438                  * Do a fuzzy cost comparison with standard fuzziness limit.
 439                  */
 440                 costcmp = compare_path_costs_fuzzily(new_path, old_path,
 441                                                                                          STD_FUZZ_FACTOR);
 442
 443                 /*
 444                  * If the two paths compare differently for startup and total cost,
 445                  * then we want to keep both, and we can skip comparing pathkeys and
 446                  * required_outer rels.  If they compare the same, proceed with the
 447                  * other comparisons.  Row count is checked last.  (We make the tests
 448                  * in this order because the cost comparison is most likely to turn
 449                  * out "different", and the pathkeys comparison next most likely.  As
 450                  * explained above, row count very seldom makes a difference, so even
 451                  * though it's cheap to compare there's not much point in checking it
 452                  * earlier.)
 453                  */
 454                 if (costcmp != COSTS_DIFFERENT)
 455                 {
 456                         /* Similarly check to see if either dominates on pathkeys */
 457                         List       *old_path_pathkeys;
 458
 459                         old_path_pathkeys = old_path->param_info ? NIL : old_path->pathkeys;
 460                         keyscmp = compare_pathkeys(new_path_pathkeys,
 461                                                                            old_path_pathkeys);
 462                         if (keyscmp != PATHKEYS_DIFFERENT)
 463                         {
 464                                 switch (costcmp)
 465                                 {
 466                                         case COSTS_EQUAL:
 467                                                 outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
 468                                                                                                    PATH_REQ_OUTER(old_path));
 469                                                 if (keyscmp == PATHKEYS_BETTER1)
 470                                                 {
 471                                                         if ((outercmp == BMS_EQUAL ||
 472                                                                  outercmp == BMS_SUBSET1) &&
 473                                                                 new_path->rows <= old_path->rows)
 474                                                                 remove_old = true;              /* new dominates old */
 475                                                 }
 476                                                 else if (keyscmp == PATHKEYS_BETTER2)
 477                                                 {
 478                                                         if ((outercmp == BMS_EQUAL ||
 479                                                                  outercmp == BMS_SUBSET2) &&
 480                                                                 new_path->rows >= old_path->rows)
 481                                                                 accept_new = false;             /* old dominates new */
 482                                                 }
 483                                                 else    /* keyscmp == PATHKEYS_EQUAL */
 484                                                 {
 485                                                         if (outercmp == BMS_EQUAL)
 486                                                         {
 487                                                                 /*
 488                                                                  * Same pathkeys and outer rels, and fuzzily
 489                                                                  * the same cost, so keep just one; to decide
 490                                                                  * which, first check rows and then do a fuzzy
 491                                                                  * cost comparison with very small fuzz limit.
 492                                                                  * (We used to do an exact cost comparison,
 493                                                                  * but that results in annoying
 494                                                                  * platform-specific plan variations due to
 495                                                                  * roundoff in the cost estimates.)  If things
 496                                                                  * are still tied, arbitrarily keep only the
 497                                                                  * old path.  Notice that we will keep only
 498                                                                  * the old path even if the less-fuzzy
 499                                                                  * comparison decides the startup and total
 500                                                                  * costs compare differently.
 501                                                                  */
 502                                                                 if (new_path->rows < old_path->rows)
 503                                                                         remove_old = true;      /* new dominates old */
 504                                                                 else if (new_path->rows > old_path->rows)
 505                                                                         accept_new = false; /* old dominates new */
 506                                                                 else if (compare_path_costs_fuzzily(new_path,
 507                                                                                                                                         old_path,
 508                                                                                           1.0000000001) == COSTS_BETTER1)
 509                                                                         remove_old = true;      /* new dominates old */
 510                                                                 else
 511                                                                         accept_new = false; /* old equals or
 512                                                                                                                  * dominates new */
 513                                                         }
 514                                                         else if (outercmp == BMS_SUBSET1 &&
 515                                                                          new_path->rows <= old_path->rows)
 516                                                                 remove_old = true;              /* new dominates old */
 517                                                         else if (outercmp == BMS_SUBSET2 &&
 518                                                                          new_path->rows >= old_path->rows)
 519                                                                 accept_new = false;             /* old dominates new */
 520                                                         /* else different parameterizations, keep both */
 521                                                 }
 522                                                 break;
 523                                         case COSTS_BETTER1:
 524                                                 if (keyscmp != PATHKEYS_BETTER2)
 525                                                 {
 526                                                         outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
 527                                                                                                    PATH_REQ_OUTER(old_path));
 528                                                         if ((outercmp == BMS_EQUAL ||
 529                                                                  outercmp == BMS_SUBSET1) &&
 530                                                                 new_path->rows <= old_path->rows)
 531                                                                 remove_old = true;              /* new dominates old */
 532                                                 }
 533                                                 break;
 534                                         case COSTS_BETTER2:
 535                                                 if (keyscmp != PATHKEYS_BETTER1)
 536                                                 {
 537                                                         outercmp = bms_subset_compare(PATH_REQ_OUTER(new_path),
 538                                                                                                    PATH_REQ_OUTER(old_path));
 539                                                         if ((outercmp == BMS_EQUAL ||
 540                                                                  outercmp == BMS_SUBSET2) &&
 541                                                                 new_path->rows >= old_path->rows)
 542                                                                 accept_new = false;             /* old dominates new */
 543                                                 }
 544                                                 break;
 545                                         case COSTS_DIFFERENT:
 546
 547                                                 /*
 548                                                  * can't get here, but keep this case to keep compiler
 549                                                  * quiet
 550                                                  */
 551                                                 break;
 552                                 }
 553                         }
 554                 }
 555
 556                 /*
 557                  * Remove current element from pathlist if dominated by new.
 558                  */
 559                 if (remove_old)
 560                 {
 561                         parent_rel->pathlist = list_delete_cell(parent_rel->pathlist,
 562                                                                                                         p1, p1_prev);
 563
 564                         /*
 565                          * Delete the data pointed-to by the deleted cell, if possible
 566                          */
 567                         if (!IsA(old_path, IndexPath))
 568                                 pfree(old_path);
 569                         /* p1_prev does not advance */
 570                 }
 571                 else
 572                 {
 573                         /* new belongs after this old path if it has cost >= old's */
 574                         if (new_path->total_cost >= old_path->total_cost)
 575                                 insert_after = p1;
 576                         /* p1_prev advances */
 577                         p1_prev = p1;
 578                 }
 579
 580                 /*
 581                  * If we found an old path that dominates new_path, we can quit
 582                  * scanning the pathlist; we will not add new_path, and we assume
 583                  * new_path cannot dominate any other elements of the pathlist.
 584                  */
 585                 if (!accept_new)
 586                         break;
 587         }
 588
 589         if (accept_new)
 590         {
 591                 /* Accept the new path: insert it at proper place in pathlist */
 592                 if (insert_after)
 593                         lappend_cell(parent_rel->pathlist, insert_after, new_path);
 594                 else
 595                         parent_rel->pathlist = lcons(new_path, parent_rel->pathlist);
 596         }
 597         else
 598         {
 599                 /* Reject and recycle the new path */
 600                 if (!IsA(new_path, IndexPath))
 601                         pfree(new_path);
 602         }
 603 }
 604
 605 /*
 606  * add_path_precheck
 607  *        Check whether a proposed new path could possibly get accepted.
 608  *        We assume we know the path's pathkeys and parameterization accurately,
 609  *        and have lower bounds for its costs.
 610  *
 611  * Note that we do not know the path's rowcount, since getting an estimate for
 612  * that is too expensive to do before prechecking.  We assume here that paths
 613  * of a superset parameterization will generate fewer rows; if that holds,
 614  * then paths with different parameterizations cannot dominate each other
 615  * and so we can simply ignore existing paths of another parameterization.
 616  * (In the infrequent cases where that rule of thumb fails, add_path will
 617  * get rid of the inferior path.)
 618  *
 619  * At the time this is called, we haven't actually built a Path structure,
 620  * so the required information has to be passed piecemeal.
 621  */
 622 bool
 623 add_path_precheck(RelOptInfo *parent_rel,
 624                                   Cost startup_cost, Cost total_cost,
 625                                   List *pathkeys, Relids required_outer)
 626 {
 627         List       *new_path_pathkeys;
 628         bool            consider_startup;
 629         ListCell   *p1;
 630
 631         /* Pretend parameterized paths have no pathkeys, per add_path policy */
 632         new_path_pathkeys = required_outer ? NIL : pathkeys;
 633
 634         /* Decide whether new path's startup cost is interesting */
 635         consider_startup = required_outer ? parent_rel->consider_param_startup : parent_rel->consider_startup;
 636
 637         foreach(p1, parent_rel->pathlist)
 638         {
 639                 Path       *old_path = (Path *) lfirst(p1);
 640                 PathKeysComparison keyscmp;
 641
 642                 /*
 643                  * We are looking for an old_path with the same parameterization (and
 644                  * by assumption the same rowcount) that dominates the new path on
 645                  * pathkeys as well as both cost metrics.  If we find one, we can
 646                  * reject the new path.
 647                  *
 648                  * Cost comparisons here should match compare_path_costs_fuzzily.
 649                  */
 650                 if (total_cost > old_path->total_cost * STD_FUZZ_FACTOR)
 651                 {
 652                         /* new path can win on startup cost only if consider_startup */
 653                         if (startup_cost > old_path->startup_cost * STD_FUZZ_FACTOR ||
 654                                 !consider_startup)
 655                         {
 656                                 /* new path loses on cost, so check pathkeys... */
 657                                 List       *old_path_pathkeys;
 658
 659                                 old_path_pathkeys = old_path->param_info ? NIL : old_path->pathkeys;
 660                                 keyscmp = compare_pathkeys(new_path_pathkeys,
 661                                                                                    old_path_pathkeys);
 662                                 if (keyscmp == PATHKEYS_EQUAL ||
 663                                         keyscmp == PATHKEYS_BETTER2)
 664                                 {
 665                                         /* new path does not win on pathkeys... */
 666                                         if (bms_equal(required_outer, PATH_REQ_OUTER(old_path)))
 667                                         {
 668                                                 /* Found an old path that dominates the new one */
 669                                                 return false;
 670                                         }
 671                                 }
 672                         }
 673                 }
 674                 else
 675                 {
 676                         /*
 677                          * Since the pathlist is sorted by total_cost, we can stop looking
 678                          * once we reach a path with a total_cost larger than the new
 679                          * path's.
 680                          */
 681                         break;
 682                 }
 683         }
 684
 685         return true;
 686 }
 687
 688
 689 /*****************************************************************************
 690  *              PATH NODE CREATION ROUTINES
 691  *****************************************************************************/
 692
 693 /*
 694  * create_seqscan_path
 695  *        Creates a path corresponding to a sequential scan, returning the
 696  *        pathnode.
 697  */
 698 Path *
 699 create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
 700 {
 701         Path       *pathnode = makeNode(Path);
 702
 703         pathnode->pathtype = T_SeqScan;
 704         pathnode->parent = rel;
 705         pathnode->param_info = get_baserel_parampathinfo(root, rel,
 706                                                                                                          required_outer);
 707         pathnode->pathkeys = NIL;       /* seqscan has unordered result */
 708
 709         cost_seqscan(pathnode, root, rel, pathnode->param_info);
 710
 711         return pathnode;
 712 }
 713
 714 /*
 715  * create_samplescan_path
 716  *        Creates a path node for a sampled table scan.
 717  */
 718 Path *
 719 create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
 720 {
 721         Path       *pathnode = makeNode(Path);
 722
 723         pathnode->pathtype = T_SampleScan;
 724         pathnode->parent = rel;
 725         pathnode->param_info = get_baserel_parampathinfo(root, rel,
 726                                                                                                          required_outer);
 727         pathnode->pathkeys = NIL;       /* samplescan has unordered result */
 728
 729         cost_samplescan(pathnode, root, rel, pathnode->param_info);
 730
 731         return pathnode;
 732 }
 733
 734 /*
 735  * create_index_path
 736  *        Creates a path node for an index scan.
 737  *
 738  * 'index' is a usable index.
 739  * 'indexclauses' is a list of RestrictInfo nodes representing clauses
 740  *                      to be used as index qual conditions in the scan.
 741  * 'indexclausecols' is an integer list of index column numbers (zero based)
 742  *                      the indexclauses can be used with.
 743  * 'indexorderbys' is a list of bare expressions (no RestrictInfos)
 744  *                      to be used as index ordering operators in the scan.
 745  * 'indexorderbycols' is an integer list of index column numbers (zero based)
 746  *                      the ordering operators can be used with.
 747  * 'pathkeys' describes the ordering of the path.
 748  * 'indexscandir' is ForwardScanDirection or BackwardScanDirection
 749  *                      for an ordered index, or NoMovementScanDirection for
 750  *                      an unordered index.
 751  * 'indexonly' is true if an index-only scan is wanted.
 752  * 'required_outer' is the set of outer relids for a parameterized path.
 753  * 'loop_count' is the number of repetitions of the indexscan to factor into
 754  *              estimates of caching behavior.
 755  *
 756  * Returns the new path node.
 757  */
 758 IndexPath *
 759 create_index_path(PlannerInfo *root,
 760                                   IndexOptInfo *index,
 761                                   List *indexclauses,
 762                                   List *indexclausecols,
 763                                   List *indexorderbys,
 764                                   List *indexorderbycols,
 765                                   List *pathkeys,
 766                                   ScanDirection indexscandir,
 767                                   bool indexonly,
 768                                   Relids required_outer,
 769                                   double loop_count)
 770 {
 771         IndexPath  *pathnode = makeNode(IndexPath);
 772         RelOptInfo *rel = index->rel;
 773         List       *indexquals,
 774                            *indexqualcols;
 775
 776         pathnode->path.pathtype = indexonly ? T_IndexOnlyScan : T_IndexScan;
 777         pathnode->path.parent = rel;
 778         pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
 779                                                                                                                   required_outer);
 780         pathnode->path.pathkeys = pathkeys;
 781
 782         /* Convert clauses to indexquals the executor can handle */
 783         expand_indexqual_conditions(index, indexclauses, indexclausecols,
 784                                                                 &indexquals, &indexqualcols);
 785
 786         /* Fill in the pathnode */
 787         pathnode->indexinfo = index;
 788         pathnode->indexclauses = indexclauses;
 789         pathnode->indexquals = indexquals;
 790         pathnode->indexqualcols = indexqualcols;
 791         pathnode->indexorderbys = indexorderbys;
 792         pathnode->indexorderbycols = indexorderbycols;
 793         pathnode->indexscandir = indexscandir;
 794
 795         cost_index(pathnode, root, loop_count);
 796
 797         return pathnode;
 798 }
 799
 800 /*
 801  * create_bitmap_heap_path
 802  *        Creates a path node for a bitmap scan.
 803  *
 804  * 'bitmapqual' is a tree of IndexPath, BitmapAndPath, and BitmapOrPath nodes.
 805  * 'required_outer' is the set of outer relids for a parameterized path.
 806  * 'loop_count' is the number of repetitions of the indexscan to factor into
 807  *              estimates of caching behavior.
 808  *
 809  * loop_count should match the value used when creating the component
 810  * IndexPaths.
 811  */
 812 BitmapHeapPath *
 813 create_bitmap_heap_path(PlannerInfo *root,
 814                                                 RelOptInfo *rel,
 815                                                 Path *bitmapqual,
 816                                                 Relids required_outer,
 817                                                 double loop_count)
 818 {
 819         BitmapHeapPath *pathnode = makeNode(BitmapHeapPath);
 820
 821         pathnode->path.pathtype = T_BitmapHeapScan;
 822         pathnode->path.parent = rel;
 823         pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
 824                                                                                                                   required_outer);
 825         pathnode->path.pathkeys = NIL;          /* always unordered */
 826
 827         pathnode->bitmapqual = bitmapqual;
 828
 829         cost_bitmap_heap_scan(&pathnode->path, root, rel,
 830                                                   pathnode->path.param_info,
 831                                                   bitmapqual, loop_count);
 832
 833         return pathnode;
 834 }
 835
 836 /*
 837  * create_bitmap_and_path
 838  *        Creates a path node representing a BitmapAnd.
 839  */
 840 BitmapAndPath *
 841 create_bitmap_and_path(PlannerInfo *root,
 842                                            RelOptInfo *rel,
 843                                            List *bitmapquals)
 844 {
 845         BitmapAndPath *pathnode = makeNode(BitmapAndPath);
 846
 847         pathnode->path.pathtype = T_BitmapAnd;
 848         pathnode->path.parent = rel;
 849         pathnode->path.param_info = NULL;       /* not used in bitmap trees */
 850         pathnode->path.pathkeys = NIL;          /* always unordered */
 851
 852         pathnode->bitmapquals = bitmapquals;
 853
 854         /* this sets bitmapselectivity as well as the regular cost fields: */
 855         cost_bitmap_and_node(pathnode, root);
 856
 857         return pathnode;
 858 }
 859
 860 /*
 861  * create_bitmap_or_path
 862  *        Creates a path node representing a BitmapOr.
 863  */
 864 BitmapOrPath *
 865 create_bitmap_or_path(PlannerInfo *root,
 866                                           RelOptInfo *rel,
 867                                           List *bitmapquals)
 868 {
 869         BitmapOrPath *pathnode = makeNode(BitmapOrPath);
 870
 871         pathnode->path.pathtype = T_BitmapOr;
 872         pathnode->path.parent = rel;
 873         pathnode->path.param_info = NULL;       /* not used in bitmap trees */
 874         pathnode->path.pathkeys = NIL;          /* always unordered */
 875
 876         pathnode->bitmapquals = bitmapquals;
 877
 878         /* this sets bitmapselectivity as well as the regular cost fields: */
 879         cost_bitmap_or_node(pathnode, root);
 880
 881         return pathnode;
 882 }
 883
 884 /*
 885  * create_tidscan_path
 886  *        Creates a path corresponding to a scan by TID, returning the pathnode.
 887  */
 888 TidPath *
 889 create_tidscan_path(PlannerInfo *root, RelOptInfo *rel, List *tidquals,
 890                                         Relids required_outer)
 891 {
 892         TidPath    *pathnode = makeNode(TidPath);
 893
 894         pathnode->path.pathtype = T_TidScan;
 895         pathnode->path.parent = rel;
 896         pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
 897                                                                                                                   required_outer);
 898         pathnode->path.pathkeys = NIL;          /* always unordered */
 899
 900         pathnode->tidquals = tidquals;
 901
 902         cost_tidscan(&pathnode->path, root, rel, tidquals,
 903                                  pathnode->path.param_info);
 904
 905         return pathnode;
 906 }
 907
 908 /*
 909  * create_append_path
 910  *        Creates a path corresponding to an Append plan, returning the
 911  *        pathnode.
 912  *
 913  * Note that we must handle subpaths = NIL, representing a dummy access path.
 914  */
 915 AppendPath *
 916 create_append_path(RelOptInfo *rel, List *subpaths, Relids required_outer)
 917 {
 918         AppendPath *pathnode = makeNode(AppendPath);
 919         ListCell   *l;
 920
 921         pathnode->path.pathtype = T_Append;
 922         pathnode->path.parent = rel;
 923         pathnode->path.param_info = get_appendrel_parampathinfo(rel,
 924                                                                                                                         required_outer);
 925         pathnode->path.pathkeys = NIL;          /* result is always considered
 926                                                                                  * unsorted */
 927         pathnode->subpaths = subpaths;
 928
 929         /*
 930          * We don't bother with inventing a cost_append(), but just do it here.
 931          *
 932          * Compute rows and costs as sums of subplan rows and costs.  We charge
 933          * nothing extra for the Append itself, which perhaps is too optimistic,
 934          * but since it doesn't do any selection or projection, it is a pretty
 935          * cheap node.  If you change this, see also make_append().
 936          */
 937         pathnode->path.rows = 0;
 938         pathnode->path.startup_cost = 0;
 939         pathnode->path.total_cost = 0;
 940         foreach(l, subpaths)
 941         {
 942                 Path       *subpath = (Path *) lfirst(l);
 943
 944                 pathnode->path.rows += subpath->rows;
 945
 946                 if (l == list_head(subpaths))   /* first node? */
 947                         pathnode->path.startup_cost = subpath->startup_cost;
 948                 pathnode->path.total_cost += subpath->total_cost;
 949
 950                 /* All child paths must have same parameterization */
 951                 Assert(bms_equal(PATH_REQ_OUTER(subpath), required_outer));
 952         }
 953
 954         return pathnode;
 955 }
 956
 957 /*
 958  * create_merge_append_path
 959  *        Creates a path corresponding to a MergeAppend plan, returning the
 960  *        pathnode.
 961  */
 962 MergeAppendPath *
 963 create_merge_append_path(PlannerInfo *root,
 964                                                  RelOptInfo *rel,
 965                                                  List *subpaths,
 966                                                  List *pathkeys,
 967                                                  Relids required_outer)
 968 {
 969         MergeAppendPath *pathnode = makeNode(MergeAppendPath);
 970         Cost            input_startup_cost;
 971         Cost            input_total_cost;
 972         ListCell   *l;
 973
 974         pathnode->path.pathtype = T_MergeAppend;
 975         pathnode->path.parent = rel;
 976         pathnode->path.param_info = get_appendrel_parampathinfo(rel,
 977                                                                                                                         required_outer);
 978         pathnode->path.pathkeys = pathkeys;
 979         pathnode->subpaths = subpaths;
 980
 981         /*
 982          * Apply query-wide LIMIT if known and path is for sole base relation.
 983          * (Handling this at this low level is a bit klugy.)
 984          */
 985         if (bms_equal(rel->relids, root->all_baserels))
 986                 pathnode->limit_tuples = root->limit_tuples;
 987         else
 988                 pathnode->limit_tuples = -1.0;
 989
 990         /*
 991          * Add up the sizes and costs of the input paths.
 992          */
 993         pathnode->path.rows = 0;
 994         input_startup_cost = 0;
 995         input_total_cost = 0;
 996         foreach(l, subpaths)
 997         {
 998                 Path       *subpath = (Path *) lfirst(l);
 999
1000                 pathnode->path.rows += subpath->rows;
1001
1002                 if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
1003                 {
1004                         /* Subpath is adequately ordered, we won't need to sort it */
1005                         input_startup_cost += subpath->startup_cost;
1006                         input_total_cost += subpath->total_cost;
1007                 }
1008                 else
1009                 {
1010                         /* We'll need to insert a Sort node, so include cost for that */
1011                         Path            sort_path;              /* dummy for result of cost_sort */
1012
1013                         cost_sort(&sort_path,
1014                                           root,
1015                                           pathkeys,
1016                                           subpath->total_cost,
1017                                           subpath->parent->tuples,
1018                                           subpath->parent->width,
1019                                           0.0,
1020                                           work_mem,
1021                                           pathnode->limit_tuples);
1022                         input_startup_cost += sort_path.startup_cost;
1023                         input_total_cost += sort_path.total_cost;
1024                 }
1025
1026                 /* All child paths must have same parameterization */
1027                 Assert(bms_equal(PATH_REQ_OUTER(subpath), required_outer));
1028         }
1029
1030         /* Now we can compute total costs of the MergeAppend */
1031         cost_merge_append(&pathnode->path, root,
1032                                           pathkeys, list_length(subpaths),
1033                                           input_startup_cost, input_total_cost,
1034                                           rel->tuples);
1035
1036         return pathnode;
1037 }
1038
1039 /*
1040  * create_result_path
1041  *        Creates a path representing a Result-and-nothing-else plan.
1042  *        This is only used for the case of a query with an empty jointree.
1043  */
1044 ResultPath *
1045 create_result_path(List *quals)
1046 {
1047         ResultPath *pathnode = makeNode(ResultPath);
1048
1049         pathnode->path.pathtype = T_Result;
1050         pathnode->path.parent = NULL;
1051         pathnode->path.param_info = NULL;       /* there are no other rels... */
1052         pathnode->path.pathkeys = NIL;
1053         pathnode->quals = quals;
1054
1055         /* Hardly worth defining a cost_result() function ... just do it */
1056         pathnode->path.rows = 1;
1057         pathnode->path.startup_cost = 0;
1058         pathnode->path.total_cost = cpu_tuple_cost;
1059
1060         /*
1061          * In theory we should include the qual eval cost as well, but at present
1062          * that doesn't accomplish much except duplicate work that will be done
1063          * again in make_result; since this is only used for degenerate cases,
1064          * nothing interesting will be done with the path cost values...
1065          */
1066
1067         return pathnode;
1068 }
1069
1070 /*
1071  * create_material_path
1072  *        Creates a path corresponding to a Material plan, returning the
1073  *        pathnode.
1074  */
1075 MaterialPath *
1076 create_material_path(RelOptInfo *rel, Path *subpath)
1077 {
1078         MaterialPath *pathnode = makeNode(MaterialPath);
1079
1080         Assert(subpath->parent == rel);
1081
1082         pathnode->path.pathtype = T_Material;
1083         pathnode->path.parent = rel;
1084         pathnode->path.param_info = subpath->param_info;
1085         pathnode->path.pathkeys = subpath->pathkeys;
1086
1087         pathnode->subpath = subpath;
1088
1089         cost_material(&pathnode->path,
1090                                   subpath->startup_cost,
1091                                   subpath->total_cost,
1092                                   subpath->rows,
1093                                   rel->width);
1094
1095         return pathnode;
1096 }
1097
1098 /*
1099  * create_unique_path
1100  *        Creates a path representing elimination of distinct rows from the
1101  *        input data.  Distinct-ness is defined according to the needs of the
1102  *        semijoin represented by sjinfo.  If it is not possible to identify
1103  *        how to make the data unique, NULL is returned.
1104  *
1105  * If used at all, this is likely to be called repeatedly on the same rel;
1106  * and the input subpath should always be the same (the cheapest_total path
1107  * for the rel).  So we cache the result.
1108  */
1109 UniquePath *
1110 create_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1111                                    SpecialJoinInfo *sjinfo)
1112 {
1113         UniquePath *pathnode;
1114         Path            sort_path;              /* dummy for result of cost_sort */
1115         Path            agg_path;               /* dummy for result of cost_agg */
1116         MemoryContext oldcontext;
1117         int                     numCols;
1118
1119         /* Caller made a mistake if subpath isn't cheapest_total ... */
1120         Assert(subpath == rel->cheapest_total_path);
1121         Assert(subpath->parent == rel);
1122         /* ... or if SpecialJoinInfo is the wrong one */
1123         Assert(sjinfo->jointype == JOIN_SEMI);
1124         Assert(bms_equal(rel->relids, sjinfo->syn_righthand));
1125
1126         /* If result already cached, return it */
1127         if (rel->cheapest_unique_path)
1128                 return (UniquePath *) rel->cheapest_unique_path;
1129
1130         /* If it's not possible to unique-ify, return NULL */
1131         if (!(sjinfo->semi_can_btree || sjinfo->semi_can_hash))
1132                 return NULL;
1133
1134         /*
1135          * We must ensure path struct and subsidiary data are allocated in main
1136          * planning context; otherwise GEQO memory management causes trouble.
1137          */
1138         oldcontext = MemoryContextSwitchTo(root->planner_cxt);
1139
1140         pathnode = makeNode(UniquePath);
1141
1142         pathnode->path.pathtype = T_Unique;
1143         pathnode->path.parent = rel;
1144         pathnode->path.param_info = subpath->param_info;
1145
1146         /*
1147          * Assume the output is unsorted, since we don't necessarily have pathkeys
1148          * to represent it.  (This might get overridden below.)
1149          */
1150         pathnode->path.pathkeys = NIL;
1151
1152         pathnode->subpath = subpath;
1153         pathnode->in_operators = sjinfo->semi_operators;
1154         pathnode->uniq_exprs = sjinfo->semi_rhs_exprs;
1155
1156         /*
1157          * If the input is a relation and it has a unique index that proves the
1158          * semi_rhs_exprs are unique, then we don't need to do anything.  Note
1159          * that relation_has_unique_index_for automatically considers restriction
1160          * clauses for the rel, as well.
1161          */
1162         if (rel->rtekind == RTE_RELATION && sjinfo->semi_can_btree &&
1163                 relation_has_unique_index_for(root, rel, NIL,
1164                                                                           sjinfo->semi_rhs_exprs,
1165                                                                           sjinfo->semi_operators))
1166         {
1167                 pathnode->umethod = UNIQUE_PATH_NOOP;
1168                 pathnode->path.rows = rel->rows;
1169                 pathnode->path.startup_cost = subpath->startup_cost;
1170                 pathnode->path.total_cost = subpath->total_cost;
1171                 pathnode->path.pathkeys = subpath->pathkeys;
1172
1173                 rel->cheapest_unique_path = (Path *) pathnode;
1174
1175                 MemoryContextSwitchTo(oldcontext);
1176
1177                 return pathnode;
1178         }
1179
1180         /*
1181          * If the input is a subquery whose output must be unique already, then we
1182          * don't need to do anything.  The test for uniqueness has to consider
1183          * exactly which columns we are extracting; for example "SELECT DISTINCT
1184          * x,y" doesn't guarantee that x alone is distinct. So we cannot check for
1185          * this optimization unless semi_rhs_exprs consists only of simple Vars
1186          * referencing subquery outputs.  (Possibly we could do something with
1187          * expressions in the subquery outputs, too, but for now keep it simple.)
1188          */
1189         if (rel->rtekind == RTE_SUBQUERY)
1190         {
1191                 RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
1192
1193                 if (query_supports_distinctness(rte->subquery))
1194                 {
1195                         List       *sub_tlist_colnos;
1196
1197                         sub_tlist_colnos = translate_sub_tlist(sjinfo->semi_rhs_exprs,
1198                                                                                                    rel->relid);
1199
1200                         if (sub_tlist_colnos &&
1201                                 query_is_distinct_for(rte->subquery,
1202                                                                           sub_tlist_colnos,
1203                                                                           sjinfo->semi_operators))
1204                         {
1205                                 pathnode->umethod = UNIQUE_PATH_NOOP;
1206                                 pathnode->path.rows = rel->rows;
1207                                 pathnode->path.startup_cost = subpath->startup_cost;
1208                                 pathnode->path.total_cost = subpath->total_cost;
1209                                 pathnode->path.pathkeys = subpath->pathkeys;
1210
1211                                 rel->cheapest_unique_path = (Path *) pathnode;
1212
1213                                 MemoryContextSwitchTo(oldcontext);
1214
1215                                 return pathnode;
1216                         }
1217                 }
1218         }
1219
1220         /* Estimate number of output rows */
1221         pathnode->path.rows = estimate_num_groups(root,
1222                                                                                           sjinfo->semi_rhs_exprs,
1223                                                                                           rel->rows,
1224                                                                                           NULL);
1225         numCols = list_length(sjinfo->semi_rhs_exprs);
1226
1227         if (sjinfo->semi_can_btree)
1228         {
1229                 /*
1230                  * Estimate cost for sort+unique implementation
1231                  */
1232                 cost_sort(&sort_path, root, NIL,
1233                                   subpath->total_cost,
1234                                   rel->rows,
1235                                   rel->width,
1236                                   0.0,
1237                                   work_mem,
1238                                   -1.0);
1239
1240                 /*
1241                  * Charge one cpu_operator_cost per comparison per input tuple. We
1242                  * assume all columns get compared at most of the tuples. (XXX
1243                  * probably this is an overestimate.)  This should agree with
1244                  * make_unique.
1245                  */
1246                 sort_path.total_cost += cpu_operator_cost * rel->rows * numCols;
1247         }
1248
1249         if (sjinfo->semi_can_hash)
1250         {
1251                 /*
1252                  * Estimate the overhead per hashtable entry at 64 bytes (same as in
1253                  * planner.c).
1254                  */
1255                 int                     hashentrysize = rel->width + 64;
1256
1257                 if (hashentrysize * pathnode->path.rows > work_mem * 1024L)
1258                 {
1259                         /*
1260                          * We should not try to hash.  Hack the SpecialJoinInfo to
1261                          * remember this, in case we come through here again.
1262                          */
1263                         sjinfo->semi_can_hash = false;
1264                 }
1265                 else
1266                         cost_agg(&agg_path, root,
1267                                          AGG_HASHED, NULL,
1268                                          numCols, pathnode->path.rows,
1269                                          subpath->startup_cost,
1270                                          subpath->total_cost,
1271                                          rel->rows);
1272         }
1273
1274         if (sjinfo->semi_can_btree && sjinfo->semi_can_hash)
1275         {
1276                 if (agg_path.total_cost < sort_path.total_cost)
1277                         pathnode->umethod = UNIQUE_PATH_HASH;
1278                 else
1279                         pathnode->umethod = UNIQUE_PATH_SORT;
1280         }
1281         else if (sjinfo->semi_can_btree)
1282                 pathnode->umethod = UNIQUE_PATH_SORT;
1283         else if (sjinfo->semi_can_hash)
1284                 pathnode->umethod = UNIQUE_PATH_HASH;
1285         else
1286         {
1287                 /* we can get here only if we abandoned hashing above */
1288                 MemoryContextSwitchTo(oldcontext);
1289                 return NULL;
1290         }
1291
1292         if (pathnode->umethod == UNIQUE_PATH_HASH)
1293         {
1294                 pathnode->path.startup_cost = agg_path.startup_cost;
1295                 pathnode->path.total_cost = agg_path.total_cost;
1296         }
1297         else
1298         {
1299                 pathnode->path.startup_cost = sort_path.startup_cost;
1300                 pathnode->path.total_cost = sort_path.total_cost;
1301         }
1302
1303         rel->cheapest_unique_path = (Path *) pathnode;
1304
1305         MemoryContextSwitchTo(oldcontext);
1306
1307         return pathnode;
1308 }
1309
1310 /*
1311  * create_gather_path
1312  *
1313  *        Creates a path corresponding to a gather scan, returning the
1314  *        pathnode.
1315  */
1316 GatherPath *
1317 create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
1318                                    Relids required_outer, int nworkers)
1319 {
1320         GatherPath *pathnode = makeNode(GatherPath);
1321
1322         pathnode->path.pathtype = T_Gather;
1323         pathnode->path.parent = rel;
1324         pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1325                                                                                                                   required_outer);
1326         pathnode->path.pathkeys = NIL;          /* Gather has unordered result */
1327
1328         pathnode->subpath = subpath;
1329         pathnode->num_workers = nworkers;
1330
1331         cost_gather(pathnode, root, rel, pathnode->path.param_info);
1332
1333         return pathnode;
1334 }
1335
1336 /*
1337  * translate_sub_tlist - get subquery column numbers represented by tlist
1338  *
1339  * The given targetlist usually contains only Vars referencing the given relid.
1340  * Extract their varattnos (ie, the column numbers of the subquery) and return
1341  * as an integer List.
1342  *
1343  * If any of the tlist items is not a simple Var, we cannot determine whether
1344  * the subquery's uniqueness condition (if any) matches ours, so punt and
1345  * return NIL.
1346  */
1347 static List *
1348 translate_sub_tlist(List *tlist, int relid)
1349 {
1350         List       *result = NIL;
1351         ListCell   *l;
1352
1353         foreach(l, tlist)
1354         {
1355                 Var                *var = (Var *) lfirst(l);
1356
1357                 if (!var || !IsA(var, Var) ||
1358                         var->varno != relid)
1359                         return NIL;                     /* punt */
1360
1361                 result = lappend_int(result, var->varattno);
1362         }
1363         return result;
1364 }
1365
1366 /*
1367  * create_subqueryscan_path
1368  *        Creates a path corresponding to a sequential scan of a subquery,
1369  *        returning the pathnode.
1370  */
1371 Path *
1372 create_subqueryscan_path(PlannerInfo *root, RelOptInfo *rel,
1373                                                  List *pathkeys, Relids required_outer)
1374 {
1375         Path       *pathnode = makeNode(Path);
1376
1377         pathnode->pathtype = T_SubqueryScan;
1378         pathnode->parent = rel;
1379         pathnode->param_info = get_baserel_parampathinfo(root, rel,
1380                                                                                                          required_outer);
1381         pathnode->pathkeys = pathkeys;
1382
1383         cost_subqueryscan(pathnode, root, rel, pathnode->param_info);
1384
1385         return pathnode;
1386 }
1387
1388 /*
1389  * create_functionscan_path
1390  *        Creates a path corresponding to a sequential scan of a function,
1391  *        returning the pathnode.
1392  */
1393 Path *
1394 create_functionscan_path(PlannerInfo *root, RelOptInfo *rel,
1395                                                  List *pathkeys, Relids required_outer)
1396 {
1397         Path       *pathnode = makeNode(Path);
1398
1399         pathnode->pathtype = T_FunctionScan;
1400         pathnode->parent = rel;
1401         pathnode->param_info = get_baserel_parampathinfo(root, rel,
1402                                                                                                          required_outer);
1403         pathnode->pathkeys = pathkeys;
1404
1405         cost_functionscan(pathnode, root, rel, pathnode->param_info);
1406
1407         return pathnode;
1408 }
1409
1410 /*
1411  * create_valuesscan_path
1412  *        Creates a path corresponding to a scan of a VALUES list,
1413  *        returning the pathnode.
1414  */
1415 Path *
1416 create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
1417                                            Relids required_outer)
1418 {
1419         Path       *pathnode = makeNode(Path);
1420
1421         pathnode->pathtype = T_ValuesScan;
1422         pathnode->parent = rel;
1423         pathnode->param_info = get_baserel_parampathinfo(root, rel,
1424                                                                                                          required_outer);
1425         pathnode->pathkeys = NIL;       /* result is always unordered */
1426
1427         cost_valuesscan(pathnode, root, rel, pathnode->param_info);
1428
1429         return pathnode;
1430 }
1431
1432 /*
1433  * create_ctescan_path
1434  *        Creates a path corresponding to a scan of a non-self-reference CTE,
1435  *        returning the pathnode.
1436  */
1437 Path *
1438 create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer)
1439 {
1440         Path       *pathnode = makeNode(Path);
1441
1442         pathnode->pathtype = T_CteScan;
1443         pathnode->parent = rel;
1444         pathnode->param_info = get_baserel_parampathinfo(root, rel,
1445                                                                                                          required_outer);
1446         pathnode->pathkeys = NIL;       /* XXX for now, result is always unordered */
1447
1448         cost_ctescan(pathnode, root, rel, pathnode->param_info);
1449
1450         return pathnode;
1451 }
1452
1453 /*
1454  * create_worktablescan_path
1455  *        Creates a path corresponding to a scan of a self-reference CTE,
1456  *        returning the pathnode.
1457  */
1458 Path *
1459 create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel,
1460                                                   Relids required_outer)
1461 {
1462         Path       *pathnode = makeNode(Path);
1463
1464         pathnode->pathtype = T_WorkTableScan;
1465         pathnode->parent = rel;
1466         pathnode->param_info = get_baserel_parampathinfo(root, rel,
1467                                                                                                          required_outer);
1468         pathnode->pathkeys = NIL;       /* result is always unordered */
1469
1470         /* Cost is the same as for a regular CTE scan */
1471         cost_ctescan(pathnode, root, rel, pathnode->param_info);
1472
1473         return pathnode;
1474 }
1475
1476 /*
1477  * create_foreignscan_path
1478  *        Creates a path corresponding to a scan of a foreign table or
1479  *        a foreign join, returning the pathnode.
1480  *
1481  * This function is never called from core Postgres; rather, it's expected
1482  * to be called by the GetForeignPaths or GetForeignJoinPaths function of
1483  * a foreign data wrapper.  We make the FDW supply all fields of the path,
1484  * since we do not have any way to calculate them in core.
1485  */
1486 ForeignPath *
1487 create_foreignscan_path(PlannerInfo *root, RelOptInfo *rel,
1488                                                 double rows, Cost startup_cost, Cost total_cost,
1489                                                 List *pathkeys,
1490                                                 Relids required_outer,
1491                                                 List *fdw_private)
1492 {
1493         ForeignPath *pathnode = makeNode(ForeignPath);
1494
1495         pathnode->path.pathtype = T_ForeignScan;
1496         pathnode->path.parent = rel;
1497         pathnode->path.param_info = get_baserel_parampathinfo(root, rel,
1498                                                                                                                   required_outer);
1499         pathnode->path.rows = rows;
1500         pathnode->path.startup_cost = startup_cost;
1501         pathnode->path.total_cost = total_cost;
1502         pathnode->path.pathkeys = pathkeys;
1503
1504         pathnode->fdw_private = fdw_private;
1505
1506         return pathnode;
1507 }
1508
1509 /*
1510  * calc_nestloop_required_outer
1511  *        Compute the required_outer set for a nestloop join path
1512  *
1513  * Note: result must not share storage with either input
1514  */
1515 Relids
1516 calc_nestloop_required_outer(Path *outer_path, Path *inner_path)
1517 {
1518         Relids          outer_paramrels = PATH_REQ_OUTER(outer_path);
1519         Relids          inner_paramrels = PATH_REQ_OUTER(inner_path);
1520         Relids          required_outer;
1521
1522         /* inner_path can require rels from outer path, but not vice versa */
1523         Assert(!bms_overlap(outer_paramrels, inner_path->parent->relids));
1524         /* easy case if inner path is not parameterized */
1525         if (!inner_paramrels)
1526                 return bms_copy(outer_paramrels);
1527         /* else, form the union ... */
1528         required_outer = bms_union(outer_paramrels, inner_paramrels);
1529         /* ... and remove any mention of now-satisfied outer rels */
1530         required_outer = bms_del_members(required_outer,
1531                                                                          outer_path->parent->relids);
1532         /* maintain invariant that required_outer is exactly NULL if empty */
1533         if (bms_is_empty(required_outer))
1534         {
1535                 bms_free(required_outer);
1536                 required_outer = NULL;
1537         }
1538         return required_outer;
1539 }
1540
1541 /*
1542  * calc_non_nestloop_required_outer
1543  *        Compute the required_outer set for a merge or hash join path
1544  *
1545  * Note: result must not share storage with either input
1546  */
1547 Relids
1548 calc_non_nestloop_required_outer(Path *outer_path, Path *inner_path)
1549 {
1550         Relids          outer_paramrels = PATH_REQ_OUTER(outer_path);
1551         Relids          inner_paramrels = PATH_REQ_OUTER(inner_path);
1552         Relids          required_outer;
1553
1554         /* neither path can require rels from the other */
1555         Assert(!bms_overlap(outer_paramrels, inner_path->parent->relids));
1556         Assert(!bms_overlap(inner_paramrels, outer_path->parent->relids));
1557         /* form the union ... */
1558         required_outer = bms_union(outer_paramrels, inner_paramrels);
1559         /* we do not need an explicit test for empty; bms_union gets it right */
1560         return required_outer;
1561 }
1562
1563 /*
1564  * create_nestloop_path
1565  *        Creates a pathnode corresponding to a nestloop join between two
1566  *        relations.
1567  *
1568  * 'joinrel' is the join relation.
1569  * 'jointype' is the type of join required
1570  * 'workspace' is the result from initial_cost_nestloop
1571  * 'sjinfo' is extra info about the join for selectivity estimation
1572  * 'semifactors' contains valid data if jointype is SEMI or ANTI
1573  * 'outer_path' is the outer path
1574  * 'inner_path' is the inner path
1575  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
1576  * 'pathkeys' are the path keys of the new join path
1577  * 'required_outer' is the set of required outer rels
1578  *
1579  * Returns the resulting path node.
1580  */
1581 NestPath *
1582 create_nestloop_path(PlannerInfo *root,
1583                                          RelOptInfo *joinrel,
1584                                          JoinType jointype,
1585                                          JoinCostWorkspace *workspace,
1586                                          SpecialJoinInfo *sjinfo,
1587                                          SemiAntiJoinFactors *semifactors,
1588                                          Path *outer_path,
1589                                          Path *inner_path,
1590                                          List *restrict_clauses,
1591                                          List *pathkeys,
1592                                          Relids required_outer)
1593 {
1594         NestPath   *pathnode = makeNode(NestPath);
1595         Relids          inner_req_outer = PATH_REQ_OUTER(inner_path);
1596
1597         /*
1598          * If the inner path is parameterized by the outer, we must drop any
1599          * restrict_clauses that are due to be moved into the inner path.  We have
1600          * to do this now, rather than postpone the work till createplan time,
1601          * because the restrict_clauses list can affect the size and cost
1602          * estimates for this path.
1603          */
1604         if (bms_overlap(inner_req_outer, outer_path->parent->relids))
1605         {
1606                 Relids          inner_and_outer = bms_union(inner_path->parent->relids,
1607                                                                                                 inner_req_outer);
1608                 List       *jclauses = NIL;
1609                 ListCell   *lc;
1610
1611                 foreach(lc, restrict_clauses)
1612                 {
1613                         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1614
1615                         if (!join_clause_is_movable_into(rinfo,
1616                                                                                          inner_path->parent->relids,
1617                                                                                          inner_and_outer))
1618                                 jclauses = lappend(jclauses, rinfo);
1619                 }
1620                 restrict_clauses = jclauses;
1621         }
1622
1623         pathnode->path.pathtype = T_NestLoop;
1624         pathnode->path.parent = joinrel;
1625         pathnode->path.param_info =
1626                 get_joinrel_parampathinfo(root,
1627                                                                   joinrel,
1628                                                                   outer_path,
1629                                                                   inner_path,
1630                                                                   sjinfo,
1631                                                                   required_outer,
1632                                                                   &restrict_clauses);
1633         pathnode->path.pathkeys = pathkeys;
1634         pathnode->jointype = jointype;
1635         pathnode->outerjoinpath = outer_path;
1636         pathnode->innerjoinpath = inner_path;
1637         pathnode->joinrestrictinfo = restrict_clauses;
1638
1639         final_cost_nestloop(root, pathnode, workspace, sjinfo, semifactors);
1640
1641         return pathnode;
1642 }
1643
1644 /*
1645  * create_mergejoin_path
1646  *        Creates a pathnode corresponding to a mergejoin join between
1647  *        two relations
1648  *
1649  * 'joinrel' is the join relation
1650  * 'jointype' is the type of join required
1651  * 'workspace' is the result from initial_cost_mergejoin
1652  * 'sjinfo' is extra info about the join for selectivity estimation
1653  * 'outer_path' is the outer path
1654  * 'inner_path' is the inner path
1655  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
1656  * 'pathkeys' are the path keys of the new join path
1657  * 'required_outer' is the set of required outer rels
1658  * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
1659  *              (this should be a subset of the restrict_clauses list)
1660  * 'outersortkeys' are the sort varkeys for the outer relation
1661  * 'innersortkeys' are the sort varkeys for the inner relation
1662  */
1663 MergePath *
1664 create_mergejoin_path(PlannerInfo *root,
1665                                           RelOptInfo *joinrel,
1666                                           JoinType jointype,
1667                                           JoinCostWorkspace *workspace,
1668                                           SpecialJoinInfo *sjinfo,
1669                                           Path *outer_path,
1670                                           Path *inner_path,
1671                                           List *restrict_clauses,
1672                                           List *pathkeys,
1673                                           Relids required_outer,
1674                                           List *mergeclauses,
1675                                           List *outersortkeys,
1676                                           List *innersortkeys)
1677 {
1678         MergePath  *pathnode = makeNode(MergePath);
1679
1680         pathnode->jpath.path.pathtype = T_MergeJoin;
1681         pathnode->jpath.path.parent = joinrel;
1682         pathnode->jpath.path.param_info =
1683                 get_joinrel_parampathinfo(root,
1684                                                                   joinrel,
1685                                                                   outer_path,
1686                                                                   inner_path,
1687                                                                   sjinfo,
1688                                                                   required_outer,
1689                                                                   &restrict_clauses);
1690         pathnode->jpath.path.pathkeys = pathkeys;
1691         pathnode->jpath.jointype = jointype;
1692         pathnode->jpath.outerjoinpath = outer_path;
1693         pathnode->jpath.innerjoinpath = inner_path;
1694         pathnode->jpath.joinrestrictinfo = restrict_clauses;
1695         pathnode->path_mergeclauses = mergeclauses;
1696         pathnode->outersortkeys = outersortkeys;
1697         pathnode->innersortkeys = innersortkeys;
1698         /* pathnode->materialize_inner will be set by final_cost_mergejoin */
1699
1700         final_cost_mergejoin(root, pathnode, workspace, sjinfo);
1701
1702         return pathnode;
1703 }
1704
1705 /*
1706  * create_hashjoin_path
1707  *        Creates a pathnode corresponding to a hash join between two relations.
1708  *
1709  * 'joinrel' is the join relation
1710  * 'jointype' is the type of join required
1711  * 'workspace' is the result from initial_cost_hashjoin
1712  * 'sjinfo' is extra info about the join for selectivity estimation
1713  * 'semifactors' contains valid data if jointype is SEMI or ANTI
1714  * 'outer_path' is the cheapest outer path
1715  * 'inner_path' is the cheapest inner path
1716  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
1717  * 'required_outer' is the set of required outer rels
1718  * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
1719  *              (this should be a subset of the restrict_clauses list)
1720  */
1721 HashPath *
1722 create_hashjoin_path(PlannerInfo *root,
1723                                          RelOptInfo *joinrel,
1724                                          JoinType jointype,
1725                                          JoinCostWorkspace *workspace,
1726                                          SpecialJoinInfo *sjinfo,
1727                                          SemiAntiJoinFactors *semifactors,
1728                                          Path *outer_path,
1729                                          Path *inner_path,
1730                                          List *restrict_clauses,
1731                                          Relids required_outer,
1732                                          List *hashclauses)
1733 {
1734         HashPath   *pathnode = makeNode(HashPath);
1735
1736         pathnode->jpath.path.pathtype = T_HashJoin;
1737         pathnode->jpath.path.parent = joinrel;
1738         pathnode->jpath.path.param_info =
1739                 get_joinrel_parampathinfo(root,
1740                                                                   joinrel,
1741                                                                   outer_path,
1742                                                                   inner_path,
1743                                                                   sjinfo,
1744                                                                   required_outer,
1745                                                                   &restrict_clauses);
1746
1747         /*
1748          * A hashjoin never has pathkeys, since its output ordering is
1749          * unpredictable due to possible batching.  XXX If the inner relation is
1750          * small enough, we could instruct the executor that it must not batch,
1751          * and then we could assume that the output inherits the outer relation's
1752          * ordering, which might save a sort step.  However there is considerable
1753          * downside if our estimate of the inner relation size is badly off. For
1754          * the moment we don't risk it.  (Note also that if we wanted to take this
1755          * seriously, joinpath.c would have to consider many more paths for the
1756          * outer rel than it does now.)
1757          */
1758         pathnode->jpath.path.pathkeys = NIL;
1759         pathnode->jpath.jointype = jointype;
1760         pathnode->jpath.outerjoinpath = outer_path;
1761         pathnode->jpath.innerjoinpath = inner_path;
1762         pathnode->jpath.joinrestrictinfo = restrict_clauses;
1763         pathnode->path_hashclauses = hashclauses;
1764         /* final_cost_hashjoin will fill in pathnode->num_batches */
1765
1766         final_cost_hashjoin(root, pathnode, workspace, sjinfo, semifactors);
1767
1768         return pathnode;
1769 }
1770
1771 /*
1772  * reparameterize_path
1773  *              Attempt to modify a Path to have greater parameterization
1774  *
1775  * We use this to attempt to bring all child paths of an appendrel to the
1776  * same parameterization level, ensuring that they all enforce the same set
1777  * of join quals (and thus that that parameterization can be attributed to
1778  * an append path built from such paths).  Currently, only a few path types
1779  * are supported here, though more could be added at need.  We return NULL
1780  * if we can't reparameterize the given path.
1781  *
1782  * Note: we intentionally do not pass created paths to add_path(); it would
1783  * possibly try to delete them on the grounds of being cost-inferior to the
1784  * paths they were made from, and we don't want that.  Paths made here are
1785  * not necessarily of general-purpose usefulness, but they can be useful
1786  * as members of an append path.
1787  */
1788 Path *
1789 reparameterize_path(PlannerInfo *root, Path *path,
1790                                         Relids required_outer,
1791                                         double loop_count)
1792 {
1793         RelOptInfo *rel = path->parent;
1794
1795         /* Can only increase, not decrease, path's parameterization */
1796         if (!bms_is_subset(PATH_REQ_OUTER(path), required_outer))
1797                 return NULL;
1798         switch (path->pathtype)
1799         {
1800                 case T_SeqScan:
1801                         return create_seqscan_path(root, rel, required_outer);
1802                 case T_SampleScan:
1803                         return (Path *) create_samplescan_path(root, rel, required_outer);
1804                 case T_IndexScan:
1805                 case T_IndexOnlyScan:
1806                         {
1807                                 IndexPath  *ipath = (IndexPath *) path;
1808                                 IndexPath  *newpath = makeNode(IndexPath);
1809
1810                                 /*
1811                                  * We can't use create_index_path directly, and would not want
1812                                  * to because it would re-compute the indexqual conditions
1813                                  * which is wasted effort.  Instead we hack things a bit:
1814                                  * flat-copy the path node, revise its param_info, and redo
1815                                  * the cost estimate.
1816                                  */
1817                                 memcpy(newpath, ipath, sizeof(IndexPath));
1818                                 newpath->path.param_info =
1819                                         get_baserel_parampathinfo(root, rel, required_outer);
1820                                 cost_index(newpath, root, loop_count);
1821                                 return (Path *) newpath;
1822                         }
1823                 case T_BitmapHeapScan:
1824                         {
1825                                 BitmapHeapPath *bpath = (BitmapHeapPath *) path;
1826
1827                                 return (Path *) create_bitmap_heap_path(root,
1828                                                                                                                 rel,
1829                                                                                                                 bpath->bitmapqual,
1830                                                                                                                 required_outer,
1831                                                                                                                 loop_count);
1832                         }
1833                 case T_SubqueryScan:
1834                         return create_subqueryscan_path(root, rel, path->pathkeys,
1835                                                                                         required_outer);
1836                 default:
1837                         break;
1838         }
1839         return NULL;
1840 }