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-2003, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.55 2004/02/17 00:52:53 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "optimizer/cost.h"
  18 #include "optimizer/joininfo.h"
  19 #include "optimizer/pathnode.h"
  20 #include "optimizer/plancat.h"
  21 #include "optimizer/restrictinfo.h"
  22 #include "optimizer/tlist.h"
  23 #include "parser/parsetree.h"
  24
  25
  26 static RelOptInfo *make_base_rel(Query *root, int relid);
  27 static void build_joinrel_tlist(Query *root, RelOptInfo *joinrel);
  28 static List *build_joinrel_restrictlist(Query *root,
  29                                                    RelOptInfo *joinrel,
  30                                                    RelOptInfo *outer_rel,
  31                                                    RelOptInfo *inner_rel,
  32                                                    JoinType jointype);
  33 static void build_joinrel_joinlist(RelOptInfo *joinrel,
  34                                            RelOptInfo *outer_rel,
  35                                            RelOptInfo *inner_rel);
  36 static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
  37                                                           List *joininfo_list);
  38 static void subbuild_joinrel_joinlist(RelOptInfo *joinrel,
  39                                                   List *joininfo_list);
  40
  41
  42 /*
  43  * build_base_rel
  44  *        Construct a new base relation RelOptInfo, and put it in the query's
  45  *        base_rel_list.
  46  */
  47 void
  48 build_base_rel(Query *root, int relid)
  49 {
  50         List       *rels;
  51         RelOptInfo *rel;
  52
  53         /* Rel should not exist already */
  54         foreach(rels, root->base_rel_list)
  55         {
  56                 rel = (RelOptInfo *) lfirst(rels);
  57                 if (relid == rel->relid)
  58                         elog(ERROR, "rel already exists");
  59         }
  60
  61         /* It should not exist as an "other" rel, either */
  62         foreach(rels, root->other_rel_list)
  63         {
  64                 rel = (RelOptInfo *) lfirst(rels);
  65                 if (relid == rel->relid)
  66                         elog(ERROR, "rel already exists as \"other\" rel");
  67         }
  68
  69         /* No existing RelOptInfo for this base rel, so make a new one */
  70         rel = make_base_rel(root, relid);
  71
  72         /* and add it to the list */
  73         root->base_rel_list = lcons(rel, root->base_rel_list);
  74 }
  75
  76 /*
  77  * build_other_rel
  78  *        Returns relation entry corresponding to 'relid', creating a new one
  79  *        if necessary.  This is for 'other' relations, which are much like
  80  *        base relations except that they live in a different list.
  81  */
  82 RelOptInfo *
  83 build_other_rel(Query *root, int relid)
  84 {
  85         List       *rels;
  86         RelOptInfo *rel;
  87
  88         /* Already made? */
  89         foreach(rels, root->other_rel_list)
  90         {
  91                 rel = (RelOptInfo *) lfirst(rels);
  92                 if (relid == rel->relid)
  93                         return rel;
  94         }
  95
  96         /* It should not exist as a base rel */
  97         foreach(rels, root->base_rel_list)
  98         {
  99                 rel = (RelOptInfo *) lfirst(rels);
 100                 if (relid == rel->relid)
 101                         elog(ERROR, "rel already exists as base rel");
 102         }
 103
 104         /* No existing RelOptInfo for this other rel, so make a new one */
 105         rel = make_base_rel(root, relid);
 106
 107         /* presently, must be an inheritance child rel */
 108         Assert(rel->reloptkind == RELOPT_BASEREL);
 109         rel->reloptkind = RELOPT_OTHER_CHILD_REL;
 110
 111         /* and add it to the list */
 112         root->other_rel_list = lcons(rel, root->other_rel_list);
 113
 114         return rel;
 115 }
 116
 117 /*
 118  * make_base_rel
 119  *        Construct a base-relation RelOptInfo for the specified rangetable index.
 120  *
 121  * Common code for build_base_rel and build_other_rel.
 122  */
 123 static RelOptInfo *
 124 make_base_rel(Query *root, int relid)
 125 {
 126         RelOptInfo *rel = makeNode(RelOptInfo);
 127         RangeTblEntry *rte = rt_fetch(relid, root->rtable);
 128
 129         rel->reloptkind = RELOPT_BASEREL;
 130         rel->relids = bms_make_singleton(relid);
 131         rel->rows = 0;
 132         rel->width = 0;
 133         FastListInit(&rel->reltargetlist);
 134         rel->pathlist = NIL;
 135         rel->cheapest_startup_path = NULL;
 136         rel->cheapest_total_path = NULL;
 137         rel->cheapest_unique_path = NULL;
 138         rel->pruneable = true;
 139         rel->relid = relid;
 140         rel->rtekind = rte->rtekind;
 141         /* min_attr, max_attr, attr_needed, attr_widths are set below */
 142         rel->indexlist = NIL;
 143         rel->pages = 0;
 144         rel->tuples = 0;
 145         rel->subplan = NULL;
 146         rel->baserestrictinfo = NIL;
 147         rel->baserestrictcost.startup = 0;
 148         rel->baserestrictcost.per_tuple = 0;
 149         rel->outerjoinset = NULL;
 150         rel->joininfo = NIL;
 151         rel->index_outer_relids = NULL;
 152         rel->index_inner_paths = NIL;
 153
 154         /* Check type of rtable entry */
 155         switch (rte->rtekind)
 156         {
 157                 case RTE_RELATION:
 158                         /* Table --- retrieve statistics from the system catalogs */
 159                         get_relation_info(rte->relid, rel);
 160                         break;
 161                 case RTE_SUBQUERY:
 162                 case RTE_FUNCTION:
 163                         /* Subquery or function --- need only set up attr range */
 164                         /* Note: 0 is included in range to support whole-row Vars */
 165                         rel->min_attr = 0;
 166                         rel->max_attr = length(rte->eref->colnames);
 167                         break;
 168                 default:
 169                         elog(ERROR, "unrecognized RTE kind: %d",
 170                                  (int) rte->rtekind);
 171                         break;
 172         }
 173
 174         Assert(rel->max_attr >= rel->min_attr);
 175         rel->attr_needed = (Relids *)
 176                 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
 177         rel->attr_widths = (int32 *)
 178                 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
 179
 180         return rel;
 181 }
 182
 183 /*
 184  * find_base_rel
 185  *        Find a base or other relation entry, which must already exist
 186  *        (since we'd have no idea which list to add it to).
 187  */
 188 RelOptInfo *
 189 find_base_rel(Query *root, int relid)
 190 {
 191         List       *rels;
 192         RelOptInfo *rel;
 193
 194         foreach(rels, root->base_rel_list)
 195         {
 196                 rel = (RelOptInfo *) lfirst(rels);
 197                 if (relid == rel->relid)
 198                         return rel;
 199         }
 200
 201         foreach(rels, root->other_rel_list)
 202         {
 203                 rel = (RelOptInfo *) lfirst(rels);
 204                 if (relid == rel->relid)
 205                         return rel;
 206         }
 207
 208         elog(ERROR, "no relation entry for relid %d", relid);
 209
 210         return NULL;                            /* keep compiler quiet */
 211 }
 212
 213 /*
 214  * find_join_rel
 215  *        Returns relation entry corresponding to 'relids' (a set of RT indexes),
 216  *        or NULL if none exists.  This is for join relations.
 217  */
 218 RelOptInfo *
 219 find_join_rel(Query *root, Relids relids)
 220 {
 221         List       *joinrels;
 222
 223         foreach(joinrels, root->join_rel_list)
 224         {
 225                 RelOptInfo *rel = (RelOptInfo *) lfirst(joinrels);
 226
 227                 if (bms_equal(rel->relids, relids))
 228                         return rel;
 229         }
 230
 231         return NULL;
 232 }
 233
 234 /*
 235  * build_join_rel
 236  *        Returns relation entry corresponding to the union of two given rels,
 237  *        creating a new relation entry if none already exists.
 238  *
 239  * 'joinrelids' is the Relids set that uniquely identifies the join
 240  * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
 241  *              joined
 242  * 'jointype': type of join (inner/outer)
 243  * 'restrictlist_ptr': result variable.  If not NULL, *restrictlist_ptr
 244  *              receives the list of RestrictInfo nodes that apply to this
 245  *              particular pair of joinable relations.
 246  *
 247  * restrictlist_ptr makes the routine's API a little grotty, but it saves
 248  * duplicated calculation of the restrictlist...
 249  */
 250 RelOptInfo *
 251 build_join_rel(Query *root,
 252                            Relids joinrelids,
 253                            RelOptInfo *outer_rel,
 254                            RelOptInfo *inner_rel,
 255                            JoinType jointype,
 256                            List **restrictlist_ptr)
 257 {
 258         RelOptInfo *joinrel;
 259         List       *restrictlist;
 260
 261         /*
 262          * See if we already have a joinrel for this set of base rels.
 263          */
 264         joinrel = find_join_rel(root, joinrelids);
 265
 266         if (joinrel)
 267         {
 268                 /*
 269                  * Yes, so we only need to figure the restrictlist for this
 270                  * particular pair of component relations.
 271                  */
 272                 if (restrictlist_ptr)
 273                         *restrictlist_ptr = build_joinrel_restrictlist(root,
 274                                                                                                                    joinrel,
 275                                                                                                                    outer_rel,
 276                                                                                                                    inner_rel,
 277                                                                                                                    jointype);
 278                 return joinrel;
 279         }
 280
 281         /*
 282          * Nope, so make one.
 283          */
 284         joinrel = makeNode(RelOptInfo);
 285         joinrel->reloptkind = RELOPT_JOINREL;
 286         joinrel->relids = bms_copy(joinrelids);
 287         joinrel->rows = 0;
 288         joinrel->width = 0;
 289         FastListInit(&joinrel->reltargetlist);
 290         joinrel->pathlist = NIL;
 291         joinrel->cheapest_startup_path = NULL;
 292         joinrel->cheapest_total_path = NULL;
 293         joinrel->cheapest_unique_path = NULL;
 294         joinrel->pruneable = true;
 295         joinrel->relid = 0;                     /* indicates not a baserel */
 296         joinrel->rtekind = RTE_JOIN;
 297         joinrel->min_attr = 0;
 298         joinrel->max_attr = 0;
 299         joinrel->attr_needed = NULL;
 300         joinrel->attr_widths = NULL;
 301         joinrel->indexlist = NIL;
 302         joinrel->pages = 0;
 303         joinrel->tuples = 0;
 304         joinrel->subplan = NULL;
 305         joinrel->baserestrictinfo = NIL;
 306         joinrel->baserestrictcost.startup = 0;
 307         joinrel->baserestrictcost.per_tuple = 0;
 308         joinrel->outerjoinset = NULL;
 309         joinrel->joininfo = NIL;
 310         joinrel->index_outer_relids = NULL;
 311         joinrel->index_inner_paths = NIL;
 312
 313         /*
 314          * Create a new tlist containing just the vars that need to be output
 315          * from this join (ie, are needed for higher joinclauses or final
 316          * output).
 317          */
 318         build_joinrel_tlist(root, joinrel);
 319
 320         /*
 321          * Construct restrict and join clause lists for the new joinrel. (The
 322          * caller might or might not need the restrictlist, but I need it
 323          * anyway for set_joinrel_size_estimates().)
 324          */
 325         restrictlist = build_joinrel_restrictlist(root,
 326                                                                                           joinrel,
 327                                                                                           outer_rel,
 328                                                                                           inner_rel,
 329                                                                                           jointype);
 330         if (restrictlist_ptr)
 331                 *restrictlist_ptr = restrictlist;
 332         build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
 333
 334         /*
 335          * Set estimates of the joinrel's size.
 336          */
 337         set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
 338                                                            jointype, restrictlist);
 339
 340         /*
 341          * Add the joinrel to the query's joinrel list.
 342          */
 343         root->join_rel_list = lcons(joinrel, root->join_rel_list);
 344
 345         return joinrel;
 346 }
 347
 348 /*
 349  * build_joinrel_tlist
 350  *        Builds a join relation's target list.
 351  *
 352  * The join's targetlist includes all Vars of its member relations that
 353  * will still be needed above the join.
 354  *
 355  * In a former lifetime, this just merged the tlists of the two member
 356  * relations first presented.  While we could still do that, working from
 357  * lists of Vars would mean doing a find_base_rel lookup for each Var.
 358  * It seems more efficient to scan the list of base rels and collect the
 359  * needed vars directly from there.
 360  *
 361  * We also compute the expected width of the join's output, making use
 362  * of data that was cached at the baserel level by set_rel_width().
 363  */
 364 static void
 365 build_joinrel_tlist(Query *root, RelOptInfo *joinrel)
 366 {
 367         Relids          relids = joinrel->relids;
 368         List       *rels;
 369         List       *vars;
 370
 371         FastListInit(&joinrel->reltargetlist);
 372         joinrel->width = 0;
 373
 374         foreach(rels, root->base_rel_list)
 375         {
 376                 RelOptInfo *baserel = (RelOptInfo *) lfirst(rels);
 377
 378                 if (!bms_is_member(baserel->relid, relids))
 379                         continue;
 380
 381                 foreach(vars, FastListValue(&baserel->reltargetlist))
 382                 {
 383                         Var                *var = (Var *) lfirst(vars);
 384                         int                     ndx = var->varattno - baserel->min_attr;
 385
 386                         if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
 387                         {
 388                                 FastAppend(&joinrel->reltargetlist, var);
 389                                 Assert(baserel->attr_widths[ndx] > 0);
 390                                 joinrel->width += baserel->attr_widths[ndx];
 391                         }
 392                 }
 393         }
 394 }
 395
 396 /*
 397  * build_joinrel_restrictlist
 398  * build_joinrel_joinlist
 399  *        These routines build lists of restriction and join clauses for a
 400  *        join relation from the joininfo lists of the relations it joins.
 401  *
 402  *        These routines are separate because the restriction list must be
 403  *        built afresh for each pair of input sub-relations we consider, whereas
 404  *        the join lists need only be computed once for any join RelOptInfo.
 405  *        The join lists are fully determined by the set of rels making up the
 406  *        joinrel, so we should get the same results (up to ordering) from any
 407  *        candidate pair of sub-relations.      But the restriction list is whatever
 408  *        is not handled in the sub-relations, so it depends on which
 409  *        sub-relations are considered.
 410  *
 411  *        If a join clause from an input relation refers to base rels still not
 412  *        present in the joinrel, then it is still a join clause for the joinrel;
 413  *        we put it into an appropriate JoinInfo list for the joinrel.  Otherwise,
 414  *        the clause is now a restrict clause for the joined relation, and we
 415  *        return it to the caller of build_joinrel_restrictlist() to be stored in
 416  *        join paths made from this pair of sub-relations.      (It will not need to
 417  *        be considered further up the join tree.)
 418  *
 419  *        When building a restriction list, we eliminate redundant clauses.
 420  *        We don't try to do that for join clause lists, since the join clauses
 421  *        aren't really doing anything, just waiting to become part of higher
 422  *        levels' restriction lists.
 423  *
 424  * 'joinrel' is a join relation node
 425  * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
 426  *              to form joinrel.
 427  * 'jointype' is the type of join used.
 428  *
 429  * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
 430  * whereas build_joinrel_joinlist() stores its results in the joinrel's
 431  * joininfo lists.      One or the other must accept each given clause!
 432  *
 433  * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
 434  * up to the join relation.  I believe this is no longer necessary, because
 435  * RestrictInfo nodes are no longer context-dependent.  Instead, just include
 436  * the original nodes in the lists made for the join relation.
 437  */
 438 static List *
 439 build_joinrel_restrictlist(Query *root,
 440                                                    RelOptInfo *joinrel,
 441                                                    RelOptInfo *outer_rel,
 442                                                    RelOptInfo *inner_rel,
 443                                                    JoinType jointype)
 444 {
 445         List       *result;
 446         List       *rlist;
 447
 448         /*
 449          * Collect all the clauses that syntactically belong at this level.
 450          */
 451         rlist = nconc(subbuild_joinrel_restrictlist(joinrel,
 452                                                                                                 outer_rel->joininfo),
 453                                   subbuild_joinrel_restrictlist(joinrel,
 454                                                                                                 inner_rel->joininfo));
 455
 456         /*
 457          * Eliminate duplicate and redundant clauses.
 458          *
 459          * We must eliminate duplicates, since we will see many of the same
 460          * clauses arriving from both input relations.  Also, if a clause is a
 461          * mergejoinable clause, it's possible that it is redundant with
 462          * previous clauses (see optimizer/README for discussion).      We detect
 463          * that case and omit the redundant clause from the result list.
 464          */
 465         result = remove_redundant_join_clauses(root, rlist, jointype);
 466
 467         freeList(rlist);
 468
 469         return result;
 470 }
 471
 472 static void
 473 build_joinrel_joinlist(RelOptInfo *joinrel,
 474                                            RelOptInfo *outer_rel,
 475                                            RelOptInfo *inner_rel)
 476 {
 477         subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo);
 478         subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo);
 479 }
 480
 481 static List *
 482 subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
 483                                                           List *joininfo_list)
 484 {
 485         List       *restrictlist = NIL;
 486         List       *xjoininfo;
 487
 488         foreach(xjoininfo, joininfo_list)
 489         {
 490                 JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
 491
 492                 if (bms_is_subset(joininfo->unjoined_relids, joinrel->relids))
 493                 {
 494                         /*
 495                          * Clauses in this JoinInfo list become restriction clauses
 496                          * for the joinrel, since they refer to no outside rels.
 497                          *
 498                          * We must copy the list to avoid disturbing the input relation,
 499                          * but we can use a shallow copy.
 500                          */
 501                         restrictlist = nconc(restrictlist,
 502                                                                  listCopy(joininfo->jinfo_restrictinfo));
 503                 }
 504                 else
 505                 {
 506                         /*
 507                          * These clauses are still join clauses at this level, so we
 508                          * ignore them in this routine.
 509                          */
 510                 }
 511         }
 512
 513         return restrictlist;
 514 }
 515
 516 static void
 517 subbuild_joinrel_joinlist(RelOptInfo *joinrel,
 518                                                   List *joininfo_list)
 519 {
 520         List       *xjoininfo;
 521
 522         foreach(xjoininfo, joininfo_list)
 523         {
 524                 JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
 525                 Relids          new_unjoined_relids;
 526
 527                 new_unjoined_relids = bms_difference(joininfo->unjoined_relids,
 528                                                                                          joinrel->relids);
 529                 if (bms_is_empty(new_unjoined_relids))
 530                 {
 531                         /*
 532                          * Clauses in this JoinInfo list become restriction clauses
 533                          * for the joinrel, since they refer to no outside rels. So we
 534                          * can ignore them in this routine.
 535                          */
 536                         bms_free(new_unjoined_relids);
 537                 }
 538                 else
 539                 {
 540                         /*
 541                          * These clauses are still join clauses at this level, so find
 542                          * or make the appropriate JoinInfo item for the joinrel, and
 543                          * add the clauses to it, eliminating duplicates.  (Since
 544                          * RestrictInfo nodes are normally multiply-linked rather than
 545                          * copied, pointer equality should be a sufficient test.  If
 546                          * two equal() nodes should happen to sneak in, no great harm
 547                          * is done --- they'll be detected by redundant-clause testing
 548                          * when they reach a restriction list.)
 549                          */
 550                         JoinInfo   *new_joininfo;
 551
 552                         new_joininfo = make_joininfo_node(joinrel, new_unjoined_relids);
 553                         new_joininfo->jinfo_restrictinfo =
 554                                 set_ptrUnion(new_joininfo->jinfo_restrictinfo,
 555                                                          joininfo->jinfo_restrictinfo);
 556                 }
 557         }
 558 }