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  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.20 1999/02/08 04:29:21 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include <math.h>
  15
  16 #include "postgres.h"
  17
  18 #include "nodes/relation.h"
  19 #include "utils/elog.h"
  20
  21 #include "optimizer/internal.h"
  22 #include "optimizer/pathnode.h"
  23 #include "optimizer/restrictinfo.h"
  24 #include "optimizer/plancat.h"
  25 #include "optimizer/cost.h"
  26 #include "optimizer/keys.h"
  27 #include "optimizer/xfunc.h"
  28 #include "optimizer/ordering.h"
  29
  30 #include "parser/parsetree.h"   /* for getrelid() */
  31
  32 static Path *better_path(Path *new_path, List *unique_paths, bool *noOther);
  33
  34
  35 /*****************************************************************************
  36  *              MISC. PATH UTILITIES
  37  *****************************************************************************/
  38
  39 /*
  40  * path-is-cheaper--
  41  *        Returns t iff 'path1' is cheaper than 'path2'.
  42  *
  43  */
  44 bool
  45 path_is_cheaper(Path *path1, Path *path2)
  46 {
  47         Cost            cost1 = path1->path_cost;
  48         Cost            cost2 = path2->path_cost;
  49
  50         return (bool) (cost1 < cost2);
  51 }
  52
  53 /*
  54  * set_cheapest--
  55  *        Finds the minimum cost path from among a relation's paths.
  56  *
  57  * 'parent-rel' is the parent relation
  58  * 'pathlist' is a list of path nodes corresponding to 'parent-rel'
  59  *
  60  * Returns and sets the relation entry field with the pathnode that
  61  * is minimum.
  62  *
  63  */
  64 Path *
  65 set_cheapest(RelOptInfo *parent_rel, List *pathlist)
  66 {
  67         List       *p;
  68         Path       *cheapest_so_far;
  69
  70         Assert(pathlist != NIL);
  71         Assert(IsA(parent_rel, RelOptInfo));
  72
  73         cheapest_so_far = (Path *) lfirst(pathlist);
  74
  75         foreach(p, lnext(pathlist))
  76         {
  77                 Path       *path = (Path *) lfirst(p);
  78
  79                 if (path_is_cheaper(path, cheapest_so_far))
  80                         cheapest_so_far = path;
  81         }
  82
  83         parent_rel->cheapestpath = cheapest_so_far;
  84
  85         return cheapest_so_far;
  86 }
  87
  88 /*
  89  * add_pathlist--
  90  *        For each path in the list 'new-paths', add to the list 'unique-paths'
  91  *        only those paths that are unique (i.e., unique ordering and ordering
  92  *        keys).  Should a conflict arise, the more expensive path is thrown out,
  93  *        thereby pruning the plan space.  But we don't prune if xfunc
  94  *        told us not to.
  95  *
  96  * 'parent-rel' is the relation entry to which these paths correspond.
  97  *
  98  * Returns the list of unique pathnodes.
  99  *
 100  */
 101 List *
 102 add_pathlist(RelOptInfo *parent_rel, List *unique_paths, List *new_paths)
 103 {
 104         List       *p1;
 105
 106         foreach(p1, new_paths)
 107         {
 108                 Path       *new_path = (Path *) lfirst(p1);
 109                 Path       *old_path;
 110                 bool            noOther;
 111
 112                 /* Is this new path already in unique_paths? */
 113                 if (member(new_path, unique_paths))
 114                         continue;
 115
 116                 /* Find best matching path */
 117                 old_path = better_path(new_path, unique_paths, &noOther);
 118
 119                 if (noOther)
 120                 {
 121                         /* This is a brand new path.  */
 122                         new_path->parent = parent_rel;
 123                         unique_paths = lcons(new_path, unique_paths);
 124                 }
 125                 else if (old_path == NULL)
 126                 {
 127                         ;                                       /* do nothing if path is not cheaper */
 128                 }
 129                 else if (old_path != NULL)
 130                 {                                               /* (IsA(old_path,Path)) { */
 131                         new_path->parent = parent_rel;
 132                         if (!parent_rel->pruneable)
 133                                 unique_paths = lcons(new_path, unique_paths);
 134                         else
 135                                 unique_paths = lcons(new_path,
 136                                                                          LispRemove(old_path, unique_paths));
 137                 }
 138         }
 139         return unique_paths;
 140 }
 141
 142 /*
 143  * better_path--
 144  *        Determines whether 'new-path' has the same ordering and keys as some
 145  *        path in the list 'unique-paths'.      If there is a redundant path,
 146  *        eliminate the more expensive path.
 147  *
 148  * Returns:
 149  *        The old path - if 'new-path' matches some path in 'unique-paths' and is
 150  *                              cheaper
 151  *        nil - if 'new-path' matches but isn't cheaper
 152  *        t - if there is no path in the list with the same ordering and keys
 153  *
 154  */
 155 static Path *
 156 better_path(Path *new_path, List *unique_paths, bool *noOther)
 157 {
 158         Path       *old_path = (Path *) NULL;
 159         Path       *path = (Path *) NULL;
 160         List       *temp = NIL;
 161         Path       *retval = NULL;
 162
 163         foreach(temp, unique_paths)
 164         {
 165                 path = (Path *) lfirst(temp);
 166
 167                 if (samekeys(path->keys, new_path->keys) &&
 168                         equal_path_ordering(&path->path_order,
 169                                                                 &new_path->path_order))
 170                 {
 171                         old_path = path;
 172                         break;
 173                 }
 174         }
 175
 176         if (old_path == NULL)
 177                 *noOther = true;
 178         else
 179         {
 180                 *noOther = false;
 181                 if (path_is_cheaper(new_path, old_path))
 182                         retval = old_path;
 183         }
 184
 185         return retval;
 186 }
 187
 188
 189
 190 /*****************************************************************************
 191  *              PATH NODE CREATION ROUTINES
 192  *****************************************************************************/
 193
 194 /*
 195  * create_seqscan_path--
 196  *        Creates a path corresponding to a sequential scan, returning the
 197  *        pathnode.
 198  *
 199  */
 200 Path *
 201 create_seqscan_path(RelOptInfo * rel)
 202 {
 203         int                     relid = 0;
 204
 205         Path       *pathnode = makeNode(Path);
 206
 207         pathnode->pathtype = T_SeqScan;
 208         pathnode->parent = rel;
 209         pathnode->path_cost = 0.0;
 210         pathnode->path_order.ordtype = SORTOP_ORDER;
 211         pathnode->path_order.ord.sortop = NULL;
 212         pathnode->keys = NIL;
 213
 214         /*
 215          * copy restrictinfo list into path for expensive function processing --
 216          * JMH, 7/7/92
 217          */
 218         pathnode->loc_restrictinfo = (List *) copyObject((Node *) rel->restrictinfo);
 219
 220         if (rel->relids != NULL)
 221                 relid = lfirsti(rel->relids);
 222
 223         pathnode->path_cost = cost_seqscan(relid,
 224                                                                            rel->pages, rel->tuples);
 225         /* add in expensive functions cost!  -- JMH, 7/7/92 */
 226 #if 0
 227         if (XfuncMode != XFUNC_OFF)
 228         {
 229                 pathnode->path_cost += xfunc_get_path_cost(pathnode);
 230         }
 231 #endif
 232         return pathnode;
 233 }
 234
 235 /*
 236  * create_index_path--
 237  *        Creates a single path node for an index scan.
 238  *
 239  * 'rel' is the parent rel
 240  * 'index' is the pathnode for the index on 'rel'
 241  * 'restriction-clauses' is a list of restriction clause nodes.
 242  * 'is-join-scan' is a flag indicating whether or not the index is being
 243  *              considered because of its sort order.
 244  *
 245  * Returns the new path node.
 246  *
 247  */
 248 IndexPath  *
 249 create_index_path(Query *root,
 250                                   RelOptInfo * rel,
 251                                   RelOptInfo * index,
 252                                   List *restriction_clauses,
 253                                   bool is_join_scan)
 254 {
 255         IndexPath  *pathnode = makeNode(IndexPath);
 256
 257         pathnode->path.pathtype = T_IndexScan;
 258         pathnode->path.parent = rel;
 259         pathnode->path.path_order.ordtype = SORTOP_ORDER;
 260         pathnode->path.path_order.ord.sortop = index->ordering;
 261
 262         pathnode->indexid = index->relids;
 263         pathnode->indexkeys = index->indexkeys;
 264         pathnode->indexqual = NIL;
 265
 266         /*
 267          * copy restrictinfo list into path for expensive function processing --
 268          * JMH, 7/7/92
 269          */
 270         pathnode->path.loc_restrictinfo = set_difference((List *) copyObject((Node *) rel->restrictinfo),
 271                                            (List *) restriction_clauses);
 272
 273         /*
 274          * The index must have an ordering for the path to have (ordering)
 275          * keys, and vice versa.
 276          */
 277         if (pathnode->path.path_order.ord.sortop)
 278         {
 279                 pathnode->path.keys = collect_index_pathkeys(index->indexkeys,
 280                                                                                                          rel->targetlist);
 281
 282                 /*
 283                  * Check that the keys haven't 'disappeared', since they may no
 284                  * longer be in the target list (i.e., index keys that are not
 285                  * relevant to the scan are not applied to the scan path node, so
 286                  * if no index keys were found, we can't order the path).
 287                  */
 288                 if (pathnode->path.keys == NULL)
 289                         pathnode->path.path_order.ord.sortop = NULL;
 290         }
 291         else
 292                 pathnode->path.keys = NULL;
 293
 294         if (is_join_scan || restriction_clauses == NULL)
 295         {
 296
 297                 /*
 298                  * Indices used for joins or sorting result nodes don't restrict
 299                  * the result at all, they simply order it, so compute the scan
 300                  * cost accordingly -- use a selectivity of 1.0.
 301                  */
 302 /* is the statement above really true?  what about IndexScan as the
 303    inner of a join? */
 304                 pathnode->path.path_cost = cost_index(lfirsti(index->relids),
 305                                            index->pages,
 306                                            1.0,
 307                                            rel->pages,
 308                                            rel->tuples,
 309                                            index->pages,
 310                                            index->tuples,
 311                                            false);
 312                 /* add in expensive functions cost!  -- JMH, 7/7/92 */
 313 #if 0
 314                 if (XfuncMode != XFUNC_OFF)
 315                 {
 316                         pathnode->path_cost = (pathnode->path_cost +
 317                                  xfunc_get_path_cost((Path *) pathnode));
 318                 }
 319 #endif
 320         }
 321         else
 322         {
 323
 324                 /*
 325                  * Compute scan cost for the case when 'index' is used with a
 326                  * restriction clause.
 327                  */
 328                 List       *attnos;
 329                 List       *values;
 330                 List       *flags;
 331                 float           npages;
 332                 float           selec;
 333                 Cost            clausesel;
 334
 335                 get_relattvals(restriction_clauses,
 336                                            &attnos,
 337                                            &values,
 338                                            &flags);
 339                 index_selectivity(lfirsti(index->relids),
 340                                                   index->classlist,
 341                                                   get_opnos(restriction_clauses),
 342                                                   getrelid(lfirsti(rel->relids),
 343                                                                    root->rtable),
 344                                                   attnos,
 345                                                   values,
 346                                                   flags,
 347                                                   length(restriction_clauses),
 348                                                   &npages,
 349                                                   &selec);
 350                 /* each clause gets an equal selectivity */
 351                 clausesel =     pow(selec, 1.0 / (double) length(restriction_clauses));
 352
 353                 pathnode->indexqual = restriction_clauses;
 354                 pathnode->path.path_cost = cost_index(lfirsti(index->relids),
 355                                                                                            (int) npages,
 356                                                                                            selec,
 357                                                                                            rel->pages,
 358                                                                                            rel->tuples,
 359                                                                                            index->pages,
 360                                                                                            index->tuples,
 361                                                                                            false);
 362
 363 #if 0
 364                 /* add in expensive functions cost!  -- JMH, 7/7/92 */
 365                 if (XfuncMode != XFUNC_OFF)
 366                 {
 367                         pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
 368                 }
 369 #endif
 370
 371                 /*
 372                  * Set selectivities of clauses used with index to the selectivity
 373                  * of this index, subdividing the selectivity equally over each of
 374                  * the clauses.
 375                  */
 376
 377                 /* XXX Can this divide the selectivities in a better way? */
 378                 set_clause_selectivities(restriction_clauses, clausesel);
 379         }
 380         return pathnode;
 381 }
 382
 383 /*
 384  * create_nestloop_path--
 385  *        Creates a pathnode corresponding to a nestloop join between two
 386  *        relations.
 387  *
 388  * 'joinrel' is the join relation.
 389  * 'outer_rel' is the outer join relation
 390  * 'outer_path' is the outer join path.
 391  * 'inner_path' is the inner join path.
 392  * 'keys' are the keys of the path
 393  *
 394  * Returns the resulting path node.
 395  *
 396  */
 397 JoinPath   *
 398 create_nestloop_path(RelOptInfo * joinrel,
 399                                          RelOptInfo * outer_rel,
 400                                          Path *outer_path,
 401                                          Path *inner_path,
 402                                          List *keys)
 403 {
 404         JoinPath   *pathnode = makeNode(JoinPath);
 405
 406         pathnode->path.pathtype = T_NestLoop;
 407         pathnode->path.parent = joinrel;
 408         pathnode->outerjoinpath = outer_path;
 409         pathnode->innerjoinpath = inner_path;
 410         pathnode->pathinfo = joinrel->restrictinfo;
 411         pathnode->path.keys = keys;
 412         pathnode->path.joinid = NIL;
 413         pathnode->path.outerjoincost = (Cost) 0.0;
 414         pathnode->path.loc_restrictinfo = NIL;
 415
 416         if (keys)
 417         {
 418                 pathnode->path.path_order.ordtype = outer_path->path_order.ordtype;
 419                 if (outer_path->path_order.ordtype == SORTOP_ORDER)
 420                 {
 421                         pathnode->path.path_order.ord.sortop = outer_path->path_order.ord.sortop;
 422                 }
 423                 else
 424                 {
 425                         pathnode->path.path_order.ord.merge = outer_path->path_order.ord.merge;
 426                 }
 427         }
 428         else
 429         {
 430                 pathnode->path.path_order.ordtype = SORTOP_ORDER;
 431                 pathnode->path.path_order.ord.sortop = NULL;
 432         }
 433
 434         pathnode->path.path_cost = cost_nestloop(outer_path->path_cost,
 435                                           inner_path->path_cost,
 436                                           outer_rel->size,
 437                                           inner_path->parent->size,
 438                                           page_size(outer_rel->size,
 439                                                                 outer_rel->width),
 440                                           IsA(inner_path, IndexPath));
 441         /* add in expensive function costs -- JMH 7/7/92 */
 442 #if 0
 443         if (XfuncMode != XFUNC_OFF)
 444                 pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
 445 #endif
 446         return pathnode;
 447 }
 448
 449 /*
 450  * create_mergejoin_path--
 451  *        Creates a pathnode corresponding to a mergejoin join between
 452  *        two relations
 453  *
 454  * 'joinrel' is the join relation
 455  * 'outersize' is the number of tuples in the outer relation
 456  * 'innersize' is the number of tuples in the inner relation
 457  * 'outerwidth' is the number of bytes per tuple in the outer relation
 458  * 'innerwidth' is the number of bytes per tuple in the inner relation
 459  * 'outer_path' is the outer path
 460  * 'inner_path' is the inner path
 461  * 'keys' are the new keys of the join relation
 462  * 'order' is the sort order required for the merge
 463  * 'mergeclauses' are the applicable join/restriction clauses
 464  * 'outersortkeys' are the sort varkeys for the outer relation
 465  * 'innersortkeys' are the sort varkeys for the inner relation
 466  *
 467  */
 468 MergePath  *
 469 create_mergejoin_path(RelOptInfo * joinrel,
 470                                           int outersize,
 471                                           int innersize,
 472                                           int outerwidth,
 473                                           int innerwidth,
 474                                           Path *outer_path,
 475                                           Path *inner_path,
 476                                           List *keys,
 477                                           MergeOrder *order,
 478                                           List *mergeclauses,
 479                                           List *outersortkeys,
 480                                           List *innersortkeys)
 481 {
 482         MergePath  *pathnode = makeNode(MergePath);
 483
 484         pathnode->jpath.path.pathtype = T_MergeJoin;
 485         pathnode->jpath.path.parent = joinrel;
 486         pathnode->jpath.outerjoinpath = outer_path;
 487         pathnode->jpath.innerjoinpath = inner_path;
 488         pathnode->jpath.pathinfo = joinrel->restrictinfo;
 489         pathnode->jpath.path.keys = keys;
 490         pathnode->jpath.path.path_order.ordtype = MERGE_ORDER;
 491         pathnode->jpath.path.path_order.ord.merge = order;
 492         pathnode->path_mergeclauses = mergeclauses;
 493         pathnode->jpath.path.loc_restrictinfo = NIL;
 494         pathnode->outersortkeys = outersortkeys;
 495         pathnode->innersortkeys = innersortkeys;
 496         pathnode->jpath.path.path_cost = cost_mergejoin(outer_path->path_cost,
 497                                            inner_path->path_cost,
 498                                            outersortkeys,
 499                                            innersortkeys,
 500                                            outersize,
 501                                            innersize,
 502                                            outerwidth,
 503                                            innerwidth);
 504         /* add in expensive function costs -- JMH 7/7/92 */
 505 #if 0
 506         if (XfuncMode != XFUNC_OFF)
 507         {
 508                 pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
 509         }
 510 #endif
 511         return pathnode;
 512 }
 513
 514 /*
 515  * create_hashjoin_path--                                               XXX HASH
 516  *        Creates a pathnode corresponding to a hash join between two relations.
 517  *
 518  * 'joinrel' is the join relation
 519  * 'outersize' is the number of tuples in the outer relation
 520  * 'innersize' is the number of tuples in the inner relation
 521  * 'outerwidth' is the number of bytes per tuple in the outer relation
 522  * 'innerwidth' is the number of bytes per tuple in the inner relation
 523  * 'outer_path' is the outer path
 524  * 'inner_path' is the inner path
 525  * 'keys' are the new keys of the join relation
 526  * 'operator' is the hashjoin operator
 527  * 'hashclauses' are the applicable join/restriction clauses
 528  * 'outerkeys' are the sort varkeys for the outer relation
 529  * 'innerkeys' are the sort varkeys for the inner relation
 530  *
 531  */
 532 HashPath   *
 533 create_hashjoin_path(RelOptInfo * joinrel,
 534                                          int outersize,
 535                                          int innersize,
 536                                          int outerwidth,
 537                                          int innerwidth,
 538                                          Path *outer_path,
 539                                          Path *inner_path,
 540                                          List *keys,
 541                                          Oid operator,
 542                                          List *hashclauses,
 543                                          List *outerkeys,
 544                                          List *innerkeys)
 545 {
 546         HashPath   *pathnode = makeNode(HashPath);
 547
 548         pathnode->jpath.path.pathtype = T_HashJoin;
 549         pathnode->jpath.path.parent = joinrel;
 550         pathnode->jpath.outerjoinpath = outer_path;
 551         pathnode->jpath.innerjoinpath = inner_path;
 552         pathnode->jpath.pathinfo = joinrel->restrictinfo;
 553         pathnode->jpath.path.loc_restrictinfo = NIL;
 554         pathnode->jpath.path.keys = keys;
 555         pathnode->jpath.path.path_order.ordtype = SORTOP_ORDER;
 556         pathnode->jpath.path.path_order.ord.sortop = NULL;
 557         pathnode->jpath.path.outerjoincost = (Cost) 0.0;
 558         pathnode->jpath.path.joinid = (Relid) NULL;
 559         /* pathnode->hashjoinoperator = operator;  */
 560         pathnode->path_hashclauses = hashclauses;
 561         pathnode->outerhashkeys = outerkeys;
 562         pathnode->innerhashkeys = innerkeys;
 563         pathnode->jpath.path.path_cost = cost_hashjoin(outer_path->path_cost,
 564                                           inner_path->path_cost,
 565                                           outerkeys,
 566                                           innerkeys,
 567                                           outersize, innersize,
 568                                           outerwidth, innerwidth);
 569         /* add in expensive function costs -- JMH 7/7/92 */
 570 #if 0
 571         if (XfuncMode != XFUNC_OFF)
 572         {
 573                 pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
 574         }
 575 #endif
 576         return pathnode;
 577 }