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