granicus.if.org Git - postgresql/blob - src/backend/optimizer/geqo/geqo_paths.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * geqo_paths.c--
   4  *        Routines to process redundant paths and relations
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  * $Id: geqo_paths.c,v 1.13 1999/02/08 04:29:06 momjian Exp $
   9  *
  10  *-------------------------------------------------------------------------
  11  */
  12
  13 #include "postgres.h"
  14
  15 #include "nodes/pg_list.h"
  16 #include "nodes/relation.h"
  17 #include "nodes/primnodes.h"
  18
  19 #include "utils/palloc.h"
  20 #include "utils/elog.h"
  21
  22 #include "optimizer/internal.h"
  23 #include "optimizer/paths.h"
  24 #include "optimizer/pathnode.h"
  25 #include "optimizer/clauses.h"
  26 #include "optimizer/cost.h"
  27
  28 #include "optimizer/geqo_paths.h"
  29
  30
  31 static List *geqo_prune_rel(RelOptInfo * rel, List *other_rels);
  32 static Path *set_paths(RelOptInfo * rel, Path *unorderedpath);
  33
  34 /*
  35  * geqo-prune-rels--
  36  *        Removes any redundant relation entries from a list of rel nodes
  37  *        'rel-list'.
  38  *
  39  * Returns the resulting list.
  40  *
  41  */
  42 List *
  43 geqo_prune_rels(List *rel_list)
  44 {
  45         List       *temp_list = NIL;
  46
  47         if (rel_list != NIL)
  48         {
  49                 temp_list = lcons(lfirst(rel_list),
  50                   geqo_prune_rels(geqo_prune_rel((RelOptInfo *) lfirst(rel_list),
  51                                                                                  lnext(rel_list))));
  52         }
  53         return temp_list;
  54 }
  55
  56 /*
  57  * geqo-prune-rel--
  58  *        Prunes those relations from 'other-rels' that are redundant with
  59  *        'rel'.  A relation is redundant if it is built up of the same
  60  *        relations as 'rel'.  Paths for the redundant relation are merged into
  61  *        the pathlist of 'rel'.
  62  *
  63  * Returns a list of non-redundant relations, and sets the pathlist field
  64  * of 'rel' appropriately.
  65  *
  66  */
  67 static List *
  68 geqo_prune_rel(RelOptInfo * rel, List *other_rels)
  69 {
  70         List       *i = NIL;
  71         List       *t_list = NIL;
  72         List       *temp_node = NIL;
  73         RelOptInfo *other_rel = (RelOptInfo *) NULL;
  74
  75         foreach(i, other_rels)
  76         {
  77                 other_rel = (RelOptInfo *) lfirst(i);
  78                 if (same(rel->relids, other_rel->relids))
  79                 {
  80                         rel->pathlist = add_pathlist(rel,
  81                                                                                  rel->pathlist,
  82                                                                                  other_rel->pathlist);
  83                         t_list = nconc(t_list, NIL);            /* XXX is this right ? */
  84                 }
  85                 else
  86                 {
  87                         temp_node = lcons(other_rel, NIL);
  88                         t_list = nconc(t_list, temp_node);
  89                 }
  90         }
  91         return t_list;
  92 }
  93
  94 /*
  95  * geqo-rel-paths--
  96  *        For a relation 'rel' (which corresponds to a join
  97  *        relation), set pointers to the unordered path and cheapest paths
  98  *        (if the unordered path isn't the cheapest, it is pruned), and
  99  *        reset the relation's size field to reflect the join.
 100  *
 101  * Returns nothing of interest.
 102  *
 103  */
 104 void
 105 geqo_rel_paths(RelOptInfo * rel)
 106 {
 107         List       *y = NIL;
 108         Path       *path = (Path *) NULL;
 109         JoinPath   *cheapest = (JoinPath *) NULL;
 110
 111         rel->size = 0;
 112         foreach(y, rel->pathlist)
 113         {
 114                 path = (Path *) lfirst(y);
 115
 116                 if (!path->path_order.ord.sortop)
 117                         break;
 118         }
 119
 120         cheapest = (JoinPath *) set_paths(rel, path);
 121         if (IsA_JoinPath(cheapest))
 122                 rel->size = compute_joinrel_size(cheapest);
 123 }
 124
 125
 126 /*
 127  * set-path--
 128  *        Compares the unordered path for a relation with the cheapest path. If
 129  *        the unordered path is not cheapest, it is pruned.
 130  *
 131  *        Resets the pointers in 'rel' for unordered and cheapest paths.
 132  *
 133  * Returns the cheapest path.
 134  *
 135  */
 136 static Path *
 137 set_paths(RelOptInfo * rel, Path *unorderedpath)
 138 {
 139         Path       *cheapest = set_cheapest(rel, rel->pathlist);
 140
 141         /* don't prune if not pruneable  -- JMH, 11/23/92 */
 142         if (unorderedpath != cheapest
 143                 && rel->pruneable)
 144         {
 145
 146                 rel->unorderedpath = (Path *) NULL;
 147                 rel->pathlist = lremove(unorderedpath, rel->pathlist);
 148         }
 149         else
 150                 rel->unorderedpath = (Path *) unorderedpath;
 151
 152         return cheapest;
 153 }