granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/prune.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * prune.c--
   4  *        Routines to prune redundant paths and relations
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/path/Attic/prune.c,v 1.27 1999/02/11 14:58:54 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "nodes/pg_list.h"
  17 #include "nodes/relation.h"
  18
  19 #include "optimizer/internal.h"
  20 #include "optimizer/cost.h"
  21 #include "optimizer/paths.h"
  22 #include "optimizer/pathnode.h"
  23
  24 #include "utils/elog.h"
  25
  26
  27 static List *prune_joinrel(RelOptInfo *rel, List *other_rels);
  28
  29 /*
  30  * prune-joinrels--
  31  *        Removes any redundant relation entries from a list of rel nodes
  32  *        'rel-list'.  Obviously, the first relation can't be a duplicate.
  33  *
  34  * Returns the resulting list.
  35  *
  36  */
  37 void
  38 prune_joinrels(List *rel_list)
  39 {
  40         List       *i;
  41
  42         /*
  43          * rel_list can shorten while running as duplicate relations are
  44          * deleted
  45          */
  46         foreach(i, rel_list)
  47                 lnext(i) = prune_joinrel((RelOptInfo *) lfirst(i), lnext(i));
  48 }
  49
  50 /*
  51  * prune-joinrel--
  52  *        Prunes those relations from 'other-rels' that are redundant with
  53  *        'rel'.  A relation is redundant if it is built up of the same
  54  *        relations as 'rel'.  Paths for the redundant relation are merged into
  55  *        the pathlist of 'rel'.
  56  *
  57  * Returns a list of non-redundant relations, and sets the pathlist field
  58  * of 'rel' appropriately.
  59  *
  60  */
  61 static List *
  62 prune_joinrel(RelOptInfo *rel, List *other_rels)
  63 {
  64         List       *i = NIL;
  65         List       *result = NIL;
  66
  67         foreach(i, other_rels)
  68         {
  69                 RelOptInfo *other_rel = (RelOptInfo *) lfirst(i);
  70
  71                 if (same(rel->relids, other_rel->relids))
  72                         /*
  73                          *      This are on the same relations,
  74                          *      so get the best of their pathlists.
  75                          */
  76                         rel->pathlist = add_pathlist(rel,
  77                                                                                  rel->pathlist,
  78                                                                                  other_rel->pathlist);
  79                 else
  80                         result = nconc(result, lcons(other_rel, NIL));
  81         }
  82         return result;
  83 }
  84
  85 /*
  86  * prune-rel-paths--
  87  *        For each relation entry in 'rel-list' (which corresponds to a join
  88  *        relation), set pointers to the unordered path and cheapest paths
  89  *        (if the unordered path isn't the cheapest, it is pruned), and
  90  *        reset the relation's size field to reflect the join.
  91  *
  92  * Returns nothing of interest.
  93  *
  94  */
  95 void
  96 prune_rel_paths(List *rel_list)
  97 {
  98         List       *x = NIL;
  99         List       *y = NIL;
 100         Path       *path = NULL;
 101         RelOptInfo *rel = (RelOptInfo *) NULL;
 102         JoinPath   *cheapest = (JoinPath *) NULL;
 103
 104         foreach(x, rel_list)
 105         {
 106                 rel = (RelOptInfo *) lfirst(x);
 107                 rel->size = 0;
 108                 foreach(y, rel->pathlist)
 109                 {
 110                         path = (Path *) lfirst(y);
 111
 112                         if (!path->pathorder->ord.sortop)
 113                                 break;
 114                 }
 115                 cheapest = (JoinPath *) prune_rel_path(rel, path);
 116                 if (IsA_JoinPath(cheapest))
 117                         rel->size = compute_joinrel_size(cheapest);
 118                 else
 119                         elog(ERROR, "non JoinPath called");
 120         }
 121 }
 122
 123
 124 /*
 125  * prune-rel-path--
 126  *        Compares the unordered path for a relation with the cheapest path. If
 127  *        the unordered path is not cheapest, it is pruned.
 128  *
 129  *        Resets the pointers in 'rel' for unordered and cheapest paths.
 130  *
 131  * Returns the cheapest path.
 132  *
 133  */
 134 Path *
 135 prune_rel_path(RelOptInfo *rel, Path *unorderedpath)
 136 {
 137         Path       *cheapest = set_cheapest(rel, rel->pathlist);
 138
 139         /* don't prune if not pruneable  -- JMH, 11/23/92 */
 140         if (unorderedpath != cheapest && rel->pruneable)
 141         {
 142                 rel->unorderedpath = (Path *) NULL;
 143                 rel->pathlist = lremove(unorderedpath, rel->pathlist);
 144         }
 145         else
 146                 rel->unorderedpath = (Path *) unorderedpath;
 147
 148         return cheapest;
 149 }
 150
 151 /*
 152  * merge-joinrels--
 153  *        Given two lists of rel nodes that are already
 154  *        pruned, merge them into one pruned rel node list
 155  *
 156  * 'rel-list1' and
 157  * 'rel-list2' are the rel node lists
 158  *
 159  * Returns one pruned rel node list
 160  */
 161 List *
 162 merge_joinrels(List *rel_list1, List *rel_list2)
 163 {
 164         List       *xrel = NIL;
 165
 166         foreach(xrel, rel_list1)
 167         {
 168                 RelOptInfo *rel = (RelOptInfo *) lfirst(xrel);
 169
 170                 rel_list2 = prune_joinrel(rel, rel_list2);
 171         }
 172         return append(rel_list1, rel_list2);
 173 }
 174
 175 /*
 176  * prune_oldrels--
 177  *        If all the joininfo's in a rel node are inactive,
 178  *        that means that this node has been joined into
 179  *        other nodes in all possible ways, therefore
 180  *        this node can be discarded.  If not, it will cause
 181  *        extra complexity of the optimizer.
 182  *
 183  * old_rels is a list of rel nodes
 184  *
 185  * Returns a new list of rel nodes
 186  */
 187 List *
 188 prune_oldrels(List *old_rels)
 189 {
 190         RelOptInfo *rel;
 191         List       *joininfo_list,
 192                            *xjoininfo,
 193                            *i,
 194                            *temp_list = NIL;
 195
 196         foreach(i, old_rels)
 197         {
 198                 rel = (RelOptInfo *) lfirst(i);
 199                 joininfo_list = rel->joininfo;
 200
 201                 if (joininfo_list == NIL)
 202                         temp_list = lcons(rel, temp_list);
 203                 else
 204                 {
 205                         foreach(xjoininfo, joininfo_list)
 206                         {
 207                                 JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
 208
 209                                 if (!joininfo->inactive)
 210                                 {
 211                                         temp_list = lcons(rel, temp_list);
 212                                         break;
 213                                 }
 214                         }
 215                 }
 216         }
 217         return temp_list;
 218 }