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