granicus.if.org Git - postgresql/blob - src/backend/optimizer/util/relnode.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * relnode.c
   4  *        Relation-node lookup/construction routines
   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/relnode.c,v 1.25 2000/02/18 23:47:31 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "optimizer/cost.h"
  18 #include "optimizer/internal.h"
  19 #include "optimizer/joininfo.h"
  20 #include "optimizer/pathnode.h"
  21 #include "optimizer/plancat.h"
  22 #include "optimizer/tlist.h"
  23
  24
  25 static List *new_join_tlist(List *tlist, int first_resdomno);
  26 static List *build_joinrel_restrictlist(RelOptInfo *joinrel,
  27                                                                                 RelOptInfo *outer_rel,
  28                                                                                 RelOptInfo *inner_rel);
  29 static void build_joinrel_joinlist(RelOptInfo *joinrel,
  30                                                                    RelOptInfo *outer_rel,
  31                                                                    RelOptInfo *inner_rel);
  32 static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
  33                                                                                    List *joininfo_list);
  34 static void subbuild_joinrel_joinlist(RelOptInfo *joinrel,
  35                                                                           List *joininfo_list);
  36
  37
  38 /*
  39  * get_base_rel
  40  *        Returns relation entry corresponding to 'relid', creating a new one
  41  *        if necessary.  This is for base relations.
  42  */
  43 RelOptInfo *
  44 get_base_rel(Query *root, int relid)
  45 {
  46         List       *baserels;
  47         RelOptInfo *rel;
  48
  49         foreach(baserels, root->base_rel_list)
  50         {
  51                 rel = (RelOptInfo *) lfirst(baserels);
  52
  53                 /* We know length(rel->relids) == 1 for all members of base_rel_list */
  54                 if (lfirsti(rel->relids) == relid)
  55                         return rel;
  56         }
  57
  58         /* No existing RelOptInfo for this base rel, so make a new one */
  59         rel = makeNode(RelOptInfo);
  60         rel->relids = lconsi(relid, NIL);
  61         rel->rows = 0;
  62         rel->width = 0;
  63         rel->targetlist = NIL;
  64         rel->pathlist = NIL;
  65         rel->cheapest_startup_path = NULL;
  66         rel->cheapest_total_path = NULL;
  67         rel->pruneable = true;
  68         rel->indexed = false;
  69         rel->pages = 0;
  70         rel->tuples = 0;
  71         rel->baserestrictinfo = NIL;
  72         rel->baserestrictcost = 0;
  73         rel->joininfo = NIL;
  74         rel->innerjoin = NIL;
  75
  76         if (relid < 0)
  77         {
  78                 /*
  79                  * If the relation is a materialized relation, assume
  80                  * constants for sizes.
  81                  */
  82                 rel->pages = _NONAME_RELATION_PAGES_;
  83                 rel->tuples = _NONAME_RELATION_TUPLES_;
  84         }
  85         else
  86         {
  87                 /*
  88                  * Otherwise, retrieve relation statistics from the
  89                  * system catalogs.
  90                  */
  91                 relation_info(root, relid,
  92                                           &rel->indexed, &rel->pages, &rel->tuples);
  93         }
  94
  95         root->base_rel_list = lcons(rel, root->base_rel_list);
  96
  97         return rel;
  98 }
  99
 100 /*
 101  * find_join_rel
 102  *        Returns relation entry corresponding to 'relids' (a list of RT indexes),
 103  *        or NULL if none exists.  This is for join relations.
 104  *
 105  * Note: there is probably no good reason for this to be called from
 106  * anywhere except get_join_rel, but keep it as a separate routine
 107  * just in case.
 108  */
 109 static RelOptInfo *
 110 find_join_rel(Query *root, Relids relids)
 111 {
 112         List       *joinrels;
 113
 114         foreach(joinrels, root->join_rel_list)
 115         {
 116                 RelOptInfo *rel = (RelOptInfo *) lfirst(joinrels);
 117
 118                 if (sameseti(rel->relids, relids))
 119                         return rel;
 120         }
 121
 122         return NULL;
 123 }
 124
 125 /*
 126  * get_join_rel
 127  *        Returns relation entry corresponding to the union of two given rels,
 128  *        creating a new relation entry if none already exists.
 129  *
 130  * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
 131  *              joined
 132  * 'restrictlist_ptr': result variable.  If not NULL, *restrictlist_ptr
 133  *              receives the list of RestrictInfo nodes that apply to this
 134  *              particular pair of joinable relations.
 135  *
 136  * restrictlist_ptr makes the routine's API a little grotty, but it saves
 137  * duplicated calculation of the restrictlist...
 138  */
 139 RelOptInfo *
 140 get_join_rel(Query *root,
 141                          RelOptInfo *outer_rel,
 142                          RelOptInfo *inner_rel,
 143                          List **restrictlist_ptr)
 144 {
 145         List       *joinrelids;
 146         RelOptInfo *joinrel;
 147         List       *restrictlist;
 148         List       *new_outer_tlist;
 149         List       *new_inner_tlist;
 150
 151         /* We should never try to join two overlapping sets of rels. */
 152         Assert(nonoverlap_setsi(outer_rel->relids, inner_rel->relids));
 153
 154         /*
 155          * See if we already have a joinrel for this set of base rels.
 156          *
 157          * nconc(listCopy(x), y) is an idiom for making a new list without
 158          * changing either input list.
 159          */
 160         joinrelids = nconc(listCopy(outer_rel->relids), inner_rel->relids);
 161         joinrel = find_join_rel(root, joinrelids);
 162
 163         if (joinrel)
 164         {
 165                 /*
 166                  * Yes, so we only need to figure the restrictlist for this
 167                  * particular pair of component relations.
 168                  */
 169                 if (restrictlist_ptr)
 170                         *restrictlist_ptr = build_joinrel_restrictlist(joinrel,
 171                                                                                                                    outer_rel,
 172                                                                                                                    inner_rel);
 173                 return joinrel;
 174         }
 175
 176         /*
 177          * Nope, so make one.
 178          */
 179         joinrel = makeNode(RelOptInfo);
 180         joinrel->relids = joinrelids;
 181         joinrel->rows = 0;
 182         joinrel->width = 0;
 183         joinrel->targetlist = NIL;
 184         joinrel->pathlist = NIL;
 185         joinrel->cheapest_startup_path = NULL;
 186         joinrel->cheapest_total_path = NULL;
 187         joinrel->pruneable = true;
 188         joinrel->indexed = false;
 189         joinrel->pages = 0;
 190         joinrel->tuples = 0;
 191         joinrel->baserestrictinfo = NIL;
 192         joinrel->baserestrictcost = 0;
 193         joinrel->joininfo = NIL;
 194         joinrel->innerjoin = NIL;
 195
 196         /*
 197          * Create a new tlist by removing irrelevant elements from both tlists
 198          * of the outer and inner join relations and then merging the results
 199          * together.
 200          *
 201          * NOTE: the tlist order for a join rel will depend on which pair
 202          * of outer and inner rels we first try to build it from.  But the
 203          * contents should be the same regardless.
 204          *
 205          * XXX someday: consider pruning vars from the join's targetlist
 206          * if they are needed only to evaluate restriction clauses of this
 207          * join, and will never be accessed at higher levels of the plantree.
 208          */
 209         new_outer_tlist = new_join_tlist(outer_rel->targetlist, 1);
 210         new_inner_tlist = new_join_tlist(inner_rel->targetlist,
 211                                                                          length(new_outer_tlist) + 1);
 212         joinrel->targetlist = nconc(new_outer_tlist, new_inner_tlist);
 213
 214         /*
 215          * Construct restrict and join clause lists for the new joinrel.
 216          * (The caller might or might not need the restrictlist, but
 217          * I need it anyway for set_joinrel_size_estimates().)
 218          */
 219         restrictlist = build_joinrel_restrictlist(joinrel, outer_rel, inner_rel);
 220         if (restrictlist_ptr)
 221                 *restrictlist_ptr = restrictlist;
 222         build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
 223
 224         /*
 225          * Set estimates of the joinrel's size.
 226          */
 227         set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
 228                                                            restrictlist);
 229
 230         /*
 231          * Add the joinrel to the front of the query's joinrel list.
 232          * (allpaths.c depends on this ordering!)
 233          */
 234         root->join_rel_list = lcons(joinrel, root->join_rel_list);
 235
 236         return joinrel;
 237 }
 238
 239 /*
 240  * new_join_tlist
 241  *        Builds a join relation's target list by keeping those elements that
 242  *        will be in the final target list and any other elements that are still
 243  *        needed for future joins.      For a target list entry to still be needed
 244  *        for future joins, its 'joinlist' field must not be empty after removal
 245  *        of all relids in 'other_relids'.
 246  *
 247  *        XXX the above comment refers to code that is long dead and gone;
 248  *        we don't keep track of joinlists for individual targetlist entries
 249  *        anymore.  For now, all vars present in either input tlist will be
 250  *        emitted in the join's tlist.
 251  *
 252  * 'tlist' is the target list of one of the join relations
 253  * 'first_resdomno' is the resdom number to use for the first created
 254  *                              target list entry
 255  *
 256  * Returns the new target list.
 257  */
 258 static List *
 259 new_join_tlist(List *tlist,
 260                            int first_resdomno)
 261 {
 262         int                     resdomno = first_resdomno - 1;
 263         List       *t_list = NIL;
 264         List       *i;
 265
 266         foreach(i, tlist)
 267         {
 268                 TargetEntry *xtl = lfirst(i);
 269
 270                 resdomno += 1;
 271                 t_list = lappend(t_list,
 272                                                  create_tl_element(get_expr(xtl), resdomno));
 273         }
 274
 275         return t_list;
 276 }
 277
 278 /*
 279  * build_joinrel_restrictlist
 280  * build_joinrel_joinlist
 281  *        These routines build lists of restriction and join clauses for a
 282  *        join relation from the joininfo lists of the relations it joins.
 283  *
 284  *        These routines are separate because the restriction list must be
 285  *        built afresh for each pair of input sub-relations we consider, whereas
 286  *        the join lists need only be computed once for any join RelOptInfo.
 287  *        The join lists are fully determined by the set of rels making up the
 288  *        joinrel, so we should get the same results (up to ordering) from any
 289  *        candidate pair of sub-relations.  But the restriction list is whatever
 290  *        is not handled in the sub-relations, so it depends on which
 291  *        sub-relations are considered.
 292  *
 293  *        If a join clause from an input relation refers to base rels still not
 294  *        present in the joinrel, then it is still a join clause for the joinrel;
 295  *        we put it into an appropriate JoinInfo list for the joinrel.  Otherwise,
 296  *        the clause is now a restrict clause for the joined relation, and we
 297  *        return it to the caller of build_joinrel_restrictlist() to be stored in
 298  *        join paths made from this pair of sub-relations.  (It will not need to
 299  *        be considered further up the join tree.)
 300  *
 301  * 'joinrel' is a join relation node
 302  * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
 303  *              to form joinrel.
 304  *
 305  * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
 306  * whereas build_joinrel_joinlist() stores its results in the joinrel's
 307  * joininfo lists.  One or the other must accept each given clause!
 308  *
 309  * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
 310  * up to the join relation.  I believe this is no longer necessary, because
 311  * RestrictInfo nodes are no longer context-dependent.  Instead, just include
 312  * the original nodes in the lists made for the join relation.
 313  */
 314 static List *
 315 build_joinrel_restrictlist(RelOptInfo *joinrel,
 316                                                    RelOptInfo *outer_rel,
 317                                                    RelOptInfo *inner_rel)
 318 {
 319         /*
 320          * We must eliminate duplicates, since we will see the
 321          * same clauses arriving from both input relations...
 322          */
 323         return LispUnion(subbuild_joinrel_restrictlist(joinrel,
 324                                                                                                    outer_rel->joininfo),
 325                                          subbuild_joinrel_restrictlist(joinrel,
 326                                                                                                    inner_rel->joininfo));
 327 }
 328
 329 static void
 330 build_joinrel_joinlist(RelOptInfo *joinrel,
 331                                            RelOptInfo *outer_rel,
 332                                            RelOptInfo *inner_rel)
 333 {
 334         subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo);
 335         subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo);
 336 }
 337
 338 static List *
 339 subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
 340                                                           List *joininfo_list)
 341 {
 342         List       *restrictlist = NIL;
 343         List       *xjoininfo;
 344
 345         foreach(xjoininfo, joininfo_list)
 346         {
 347                 JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
 348
 349                 if (is_subseti(joininfo->unjoined_relids, joinrel->relids))
 350                 {
 351                         /*
 352                          * Clauses in this JoinInfo list become restriction clauses
 353                          * for the joinrel, since they refer to no outside rels.
 354                          *
 355                          * We must copy the list to avoid disturbing the input relation,
 356                          * but we can use a shallow copy.
 357                          */
 358                         restrictlist = nconc(restrictlist,
 359                                                                  listCopy(joininfo->jinfo_restrictinfo));
 360                 }
 361                 else
 362                 {
 363                         /*
 364                          * These clauses are still join clauses at this level,
 365                          * so we ignore them in this routine.
 366                          */
 367                 }
 368         }
 369
 370         return restrictlist;
 371 }
 372
 373 static void
 374 subbuild_joinrel_joinlist(RelOptInfo *joinrel,
 375                                                   List *joininfo_list)
 376 {
 377         List       *xjoininfo;
 378
 379         foreach(xjoininfo, joininfo_list)
 380         {
 381                 JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
 382                 Relids          new_unjoined_relids;
 383
 384                 new_unjoined_relids = set_differencei(joininfo->unjoined_relids,
 385                                                                                           joinrel->relids);
 386                 if (new_unjoined_relids == NIL)
 387                 {
 388                         /*
 389                          * Clauses in this JoinInfo list become restriction clauses
 390                          * for the joinrel, since they refer to no outside rels.
 391                          * So we can ignore them in this routine.
 392                          */
 393                 }
 394                 else
 395                 {
 396                         /*
 397                          * These clauses are still join clauses at this level,
 398                          * so find or make the appropriate JoinInfo item for the joinrel,
 399                          * and add the clauses to it (eliminating duplicates).
 400                          */
 401                         JoinInfo   *new_joininfo;
 402
 403                         new_joininfo = find_joininfo_node(joinrel, new_unjoined_relids);
 404                         new_joininfo->jinfo_restrictinfo =
 405                                 LispUnion(new_joininfo->jinfo_restrictinfo,
 406                                                   joininfo->jinfo_restrictinfo);
 407                 }
 408         }
 409 }