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