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