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-2000, PostgreSQL, Inc
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.63 2000/04/12 17:15:24 momjian Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include <math.h>
  16
  17 #include "postgres.h"
  18
  19 #include "optimizer/cost.h"
  20 #include "optimizer/pathnode.h"
  21 #include "optimizer/paths.h"
  22 #include "optimizer/plancat.h"
  23 #include "optimizer/restrictinfo.h"
  24 #include "parser/parsetree.h"
  25
  26
  27 /*****************************************************************************
  28  *              MISC. PATH UTILITIES
  29  *****************************************************************************/
  30
  31 /*
  32  * compare_path_costs
  33  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
  34  *        or more expensive than path2 for the specified criterion.
  35  */
  36 int
  37 compare_path_costs(Path *path1, Path *path2, CostSelector criterion)
  38 {
  39         if (criterion == STARTUP_COST)
  40         {
  41                 if (path1->startup_cost < path2->startup_cost)
  42                         return -1;
  43                 if (path1->startup_cost > path2->startup_cost)
  44                         return +1;
  45
  46                 /*
  47                  * If paths have the same startup cost (not at all unlikely),
  48                  * order them by total cost.
  49                  */
  50                 if (path1->total_cost < path2->total_cost)
  51                         return -1;
  52                 if (path1->total_cost > path2->total_cost)
  53                         return +1;
  54         }
  55         else
  56         {
  57                 if (path1->total_cost < path2->total_cost)
  58                         return -1;
  59                 if (path1->total_cost > path2->total_cost)
  60                         return +1;
  61
  62                 /*
  63                  * If paths have the same total cost, order them by 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         return 0;
  71 }
  72
  73 /*
  74  * compare_path_fractional_costs
  75  *        Return -1, 0, or +1 according as path1 is cheaper, the same cost,
  76  *        or more expensive than path2 for fetching the specified fraction
  77  *        of the total tuples.
  78  *
  79  * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the
  80  * path with the cheaper total_cost.
  81  */
  82 int
  83 compare_fractional_path_costs(Path *path1, Path *path2,
  84                                                           double fraction)
  85 {
  86         Cost            cost1,
  87                                 cost2;
  88
  89         if (fraction <= 0.0 || fraction >= 1.0)
  90                 return compare_path_costs(path1, path2, TOTAL_COST);
  91         cost1 = path1->startup_cost +
  92                 fraction * (path1->total_cost - path1->startup_cost);
  93         cost2 = path2->startup_cost +
  94                 fraction * (path2->total_cost - path2->startup_cost);
  95         if (cost1 < cost2)
  96                 return -1;
  97         if (cost1 > cost2)
  98                 return +1;
  99         return 0;
 100 }
 101
 102 /*
 103  * set_cheapest
 104  *        Find the minimum-cost paths from among a relation's paths,
 105  *        and save them in the rel's cheapest-path fields.
 106  *
 107  * This is normally called only after we've finished constructing the path
 108  * list for the rel node.
 109  *
 110  * If we find two paths of identical costs, try to keep the better-sorted one.
 111  * The paths might have unrelated sort orderings, in which case we can only
 112  * guess which might be better to keep, but if one is superior then we
 113  * definitely should keep it.
 114  */
 115 void
 116 set_cheapest(RelOptInfo *parent_rel)
 117 {
 118         List       *pathlist = parent_rel->pathlist;
 119         List       *p;
 120         Path       *cheapest_startup_path;
 121         Path       *cheapest_total_path;
 122
 123         Assert(IsA(parent_rel, RelOptInfo));
 124         Assert(pathlist != NIL);
 125
 126         cheapest_startup_path = cheapest_total_path = (Path *) lfirst(pathlist);
 127
 128         foreach(p, lnext(pathlist))
 129         {
 130                 Path       *path = (Path *) lfirst(p);
 131                 int                     cmp;
 132
 133                 cmp = compare_path_costs(cheapest_startup_path, path, STARTUP_COST);
 134                 if (cmp > 0 ||
 135                         (cmp == 0 &&
 136                          compare_pathkeys(cheapest_startup_path->pathkeys,
 137                                                           path->pathkeys) == PATHKEYS_BETTER2))
 138                         cheapest_startup_path = path;
 139
 140                 cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST);
 141                 if (cmp > 0 ||
 142                         (cmp == 0 &&
 143                          compare_pathkeys(cheapest_total_path->pathkeys,
 144                                                           path->pathkeys) == PATHKEYS_BETTER2))
 145                         cheapest_total_path = path;
 146         }
 147
 148         parent_rel->cheapest_startup_path = cheapest_startup_path;
 149         parent_rel->cheapest_total_path = cheapest_total_path;
 150 }
 151
 152 /*
 153  * add_path
 154  *        Consider a potential implementation path for the specified parent rel,
 155  *        and add it to the rel's pathlist if it is worthy of consideration.
 156  *        A path is worthy if it has either a better sort order (better pathkeys)
 157  *        or cheaper cost (on either dimension) than any of the existing old paths.
 158  *
 159  *        Unless parent_rel->pruneable is false, we also remove from the rel's
 160  *        pathlist any old paths that are dominated by new_path --- that is,
 161  *        new_path is both cheaper and at least as well ordered.
 162  *
 163  *        NOTE: discarded Path objects are immediately pfree'd to reduce planner
 164  *        memory consumption.  We dare not try to free the substructure of a Path,
 165  *        since much of it may be shared with other Paths or the query tree itself;
 166  *        but just recycling discarded Path nodes is a very useful savings in
 167  *        a large join tree.
 168  *
 169  * 'parent_rel' is the relation entry to which the path corresponds.
 170  * 'new_path' is a potential path for parent_rel.
 171  *
 172  * Returns nothing, but modifies parent_rel->pathlist.
 173  */
 174 void
 175 add_path(RelOptInfo *parent_rel, Path *new_path)
 176 {
 177         bool            accept_new = true;              /* unless we find a superior old
 178                                                                                  * path */
 179         List       *p1_prev = NIL;
 180         List       *p1;
 181
 182         /*
 183          * Loop to check proposed new path against old paths.  Note it is
 184          * possible for more than one old path to be tossed out because
 185          * new_path dominates it.
 186          */
 187         foreach(p1, parent_rel->pathlist)
 188         {
 189                 Path       *old_path = (Path *) lfirst(p1);
 190                 bool            remove_old = false; /* unless new proves superior */
 191                 int                     costcmp;
 192
 193                 costcmp = compare_path_costs(new_path, old_path, TOTAL_COST);
 194
 195                 /*
 196                  * If the two paths compare differently for startup and total
 197                  * cost, then we want to keep both, and we can skip the (much
 198                  * slower) comparison of pathkeys.      If they compare the same,
 199                  * proceed with the pathkeys comparison.  Note this test relies on
 200                  * the fact that compare_path_costs will only return 0 if both
 201                  * costs are equal (and, therefore, there's no need to call it
 202                  * twice in that case).
 203                  */
 204                 if (costcmp == 0 ||
 205                  costcmp == compare_path_costs(new_path, old_path, STARTUP_COST))
 206                 {
 207                         switch (compare_pathkeys(new_path->pathkeys, old_path->pathkeys))
 208                         {
 209                                 case PATHKEYS_EQUAL:
 210                                         if (costcmp < 0)
 211                                                 remove_old = true;              /* new dominates old */
 212                                         else
 213                                                 accept_new = false;             /* old equals or dominates
 214                                                                                                  * new */
 215                                         break;
 216                                 case PATHKEYS_BETTER1:
 217                                         if (costcmp <= 0)
 218                                                 remove_old = true;              /* new dominates old */
 219                                         break;
 220                                 case PATHKEYS_BETTER2:
 221                                         if (costcmp >= 0)
 222                                                 accept_new = false;             /* old dominates new */
 223                                         break;
 224                                 case PATHKEYS_DIFFERENT:
 225                                         /* keep both paths, since they have different ordering */
 226                                         break;
 227                         }
 228                 }
 229
 230                 /*
 231                  * Remove current element from pathlist if dominated by new,
 232                  * unless xfunc told us not to remove any paths.
 233                  */
 234                 if (remove_old && parent_rel->pruneable)
 235                 {
 236                         if (p1_prev)
 237                                 lnext(p1_prev) = lnext(p1);
 238                         else
 239                                 parent_rel->pathlist = lnext(p1);
 240                         pfree(old_path);
 241                 }
 242                 else
 243                         p1_prev = p1;
 244
 245                 /*
 246                  * If we found an old path that dominates new_path, we can quit
 247                  * scanning the pathlist; we will not add new_path, and we assume
 248                  * new_path cannot dominate any other elements of the pathlist.
 249                  */
 250                 if (!accept_new)
 251                         break;
 252         }
 253
 254         if (accept_new)
 255         {
 256                 /* Accept the path */
 257                 parent_rel->pathlist = lcons(new_path, parent_rel->pathlist);
 258         }
 259         else
 260         {
 261                 /* Reject and recycle the path */
 262                 pfree(new_path);
 263         }
 264 }
 265
 266
 267 /*****************************************************************************
 268  *              PATH NODE CREATION ROUTINES
 269  *****************************************************************************/
 270
 271 /*
 272  * create_seqscan_path
 273  *        Creates a path corresponding to a sequential scan, returning the
 274  *        pathnode.
 275  *
 276  */
 277 Path *
 278 create_seqscan_path(RelOptInfo *rel)
 279 {
 280         Path       *pathnode = makeNode(Path);
 281
 282         pathnode->pathtype = T_SeqScan;
 283         pathnode->parent = rel;
 284         pathnode->pathkeys = NIL;       /* seqscan has unordered result */
 285
 286         cost_seqscan(pathnode, rel);
 287
 288         return pathnode;
 289 }
 290
 291 /*
 292  * create_index_path
 293  *        Creates a path node for an index scan.
 294  *
 295  * 'rel' is the parent rel
 296  * 'index' is an index on 'rel'
 297  * 'restriction_clauses' is a list of RestrictInfo nodes
 298  *                      to be used as index qual conditions in the scan.
 299  * 'indexscandir' is ForwardScanDirection or BackwardScanDirection
 300  *                      if the caller expects a specific scan direction,
 301  *                      or NoMovementScanDirection if the caller is willing to accept
 302  *                      an unordered index.
 303  *
 304  * Returns the new path node.
 305  */
 306 IndexPath  *
 307 create_index_path(Query *root,
 308                                   RelOptInfo *rel,
 309                                   IndexOptInfo *index,
 310                                   List *restriction_clauses,
 311                                   ScanDirection indexscandir)
 312 {
 313         IndexPath  *pathnode = makeNode(IndexPath);
 314         List       *indexquals;
 315
 316         pathnode->path.pathtype = T_IndexScan;
 317         pathnode->path.parent = rel;
 318
 319         pathnode->path.pathkeys = build_index_pathkeys(root, rel, index,
 320                                                                                                    indexscandir);
 321         if (pathnode->path.pathkeys == NIL)
 322         {
 323                 /* No ordering available from index, is that OK? */
 324                 if (!ScanDirectionIsNoMovement(indexscandir))
 325                         elog(ERROR, "create_index_path: failed to create ordered index scan");
 326         }
 327         else
 328         {
 329
 330                 /*
 331                  * The index is ordered, and build_index_pathkeys defaulted to
 332                  * forward scan, so make sure we mark the pathnode properly.
 333                  */
 334                 if (ScanDirectionIsNoMovement(indexscandir))
 335                         indexscandir = ForwardScanDirection;
 336         }
 337
 338         indexquals = get_actual_clauses(restriction_clauses);
 339         /* expand special operators to indexquals the executor can handle */
 340         indexquals = expand_indexqual_conditions(indexquals);
 341
 342         /*
 343          * We are making a pathnode for a single-scan indexscan; therefore,
 344          * both indexid and indexqual should be single-element lists.
 345          */
 346         pathnode->indexid = lconsi(index->indexoid, NIL);
 347         pathnode->indexqual = lcons(indexquals, NIL);
 348
 349         pathnode->indexscandir = indexscandir;
 350
 351         /*
 352          * This routine is only used to generate "standalone" indexpaths, not
 353          * nestloop inner indexpaths.  So joinrelids is always NIL and the
 354          * number of rows is the same as the parent rel's estimate.
 355          */
 356         pathnode->joinrelids = NIL; /* no join clauses here */
 357         pathnode->rows = rel->rows;
 358
 359         cost_index(&pathnode->path, root, rel, index, indexquals, false);
 360
 361         return pathnode;
 362 }
 363
 364 /*
 365  * create_tidscan_path
 366  *        Creates a path corresponding to a tid_direct scan, returning the
 367  *        pathnode.
 368  *
 369  */
 370 TidPath    *
 371 create_tidscan_path(RelOptInfo *rel, List *tideval)
 372 {
 373         TidPath    *pathnode = makeNode(TidPath);
 374
 375         pathnode->path.pathtype = T_TidScan;
 376         pathnode->path.parent = rel;
 377         pathnode->path.pathkeys = NIL;
 378         pathnode->tideval = copyObject(tideval);        /* is copy really
 379                                                                                                  * necessary? */
 380         pathnode->unjoined_relids = NIL;
 381
 382         cost_tidscan(&pathnode->path, rel, tideval);
 383
 384         /*
 385          * divide selectivity for each clause to get an equal selectivity as
 386          * IndexScan does OK ?
 387          */
 388
 389         return pathnode;
 390 }
 391
 392 /*
 393  * create_nestloop_path
 394  *        Creates a pathnode corresponding to a nestloop join between two
 395  *        relations.
 396  *
 397  * 'joinrel' is the join relation.
 398  * 'outer_path' is the outer path
 399  * 'inner_path' is the inner path
 400  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
 401  * 'pathkeys' are the path keys of the new join path
 402  *
 403  * Returns the resulting path node.
 404  *
 405  */
 406 NestPath   *
 407 create_nestloop_path(RelOptInfo *joinrel,
 408                                          Path *outer_path,
 409                                          Path *inner_path,
 410                                          List *restrict_clauses,
 411                                          List *pathkeys)
 412 {
 413         NestPath   *pathnode = makeNode(NestPath);
 414
 415         pathnode->path.pathtype = T_NestLoop;
 416         pathnode->path.parent = joinrel;
 417         pathnode->outerjoinpath = outer_path;
 418         pathnode->innerjoinpath = inner_path;
 419         pathnode->joinrestrictinfo = restrict_clauses;
 420         pathnode->path.pathkeys = pathkeys;
 421
 422         cost_nestloop(&pathnode->path, outer_path, inner_path, restrict_clauses);
 423
 424         return pathnode;
 425 }
 426
 427 /*
 428  * create_mergejoin_path
 429  *        Creates a pathnode corresponding to a mergejoin join between
 430  *        two relations
 431  *
 432  * 'joinrel' is the join relation
 433  * 'outer_path' is the outer path
 434  * 'inner_path' is the inner path
 435  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
 436  * 'pathkeys' are the path keys of the new join path
 437  * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
 438  *              (this should be a subset of the restrict_clauses list)
 439  * 'outersortkeys' are the sort varkeys for the outer relation
 440  * 'innersortkeys' are the sort varkeys for the inner relation
 441  *
 442  */
 443 MergePath  *
 444 create_mergejoin_path(RelOptInfo *joinrel,
 445                                           Path *outer_path,
 446                                           Path *inner_path,
 447                                           List *restrict_clauses,
 448                                           List *pathkeys,
 449                                           List *mergeclauses,
 450                                           List *outersortkeys,
 451                                           List *innersortkeys)
 452 {
 453         MergePath  *pathnode = makeNode(MergePath);
 454
 455         /*
 456          * If the given paths are already well enough ordered, we can skip
 457          * doing an explicit sort.
 458          */
 459         if (outersortkeys &&
 460                 pathkeys_contained_in(outersortkeys, outer_path->pathkeys))
 461                 outersortkeys = NIL;
 462         if (innersortkeys &&
 463                 pathkeys_contained_in(innersortkeys, inner_path->pathkeys))
 464                 innersortkeys = NIL;
 465
 466         pathnode->jpath.path.pathtype = T_MergeJoin;
 467         pathnode->jpath.path.parent = joinrel;
 468         pathnode->jpath.outerjoinpath = outer_path;
 469         pathnode->jpath.innerjoinpath = inner_path;
 470         pathnode->jpath.joinrestrictinfo = restrict_clauses;
 471         pathnode->jpath.path.pathkeys = pathkeys;
 472         pathnode->path_mergeclauses = mergeclauses;
 473         pathnode->outersortkeys = outersortkeys;
 474         pathnode->innersortkeys = innersortkeys;
 475
 476         cost_mergejoin(&pathnode->jpath.path,
 477                                    outer_path,
 478                                    inner_path,
 479                                    restrict_clauses,
 480                                    outersortkeys,
 481                                    innersortkeys);
 482
 483         return pathnode;
 484 }
 485
 486 /*
 487  * create_hashjoin_path
 488  *        Creates a pathnode corresponding to a hash join between two relations.
 489  *
 490  * 'joinrel' is the join relation
 491  * 'outer_path' is the cheapest outer path
 492  * 'inner_path' is the cheapest inner path
 493  * 'restrict_clauses' are the RestrictInfo nodes to apply at the join
 494  * 'hashclauses' is a list of the hash join clause (always a 1-element list)
 495  *              (this should be a subset of the restrict_clauses list)
 496  * 'innerdisbursion' is an estimate of the disbursion of the inner hash key
 497  *
 498  */
 499 HashPath   *
 500 create_hashjoin_path(RelOptInfo *joinrel,
 501                                          Path *outer_path,
 502                                          Path *inner_path,
 503                                          List *restrict_clauses,
 504                                          List *hashclauses,
 505                                          Selectivity innerdisbursion)
 506 {
 507         HashPath   *pathnode = makeNode(HashPath);
 508
 509         pathnode->jpath.path.pathtype = T_HashJoin;
 510         pathnode->jpath.path.parent = joinrel;
 511         pathnode->jpath.outerjoinpath = outer_path;
 512         pathnode->jpath.innerjoinpath = inner_path;
 513         pathnode->jpath.joinrestrictinfo = restrict_clauses;
 514         /* A hashjoin never has pathkeys, since its ordering is unpredictable */
 515         pathnode->jpath.path.pathkeys = NIL;
 516         pathnode->path_hashclauses = hashclauses;
 517
 518         cost_hashjoin(&pathnode->jpath.path,
 519                                   outer_path,
 520                                   inner_path,
 521                                   restrict_clauses,
 522                                   innerdisbursion);
 523
 524         return pathnode;
 525 }