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