Logo Search packages:      
Sourcecode: postgresql-8.4 version File versions

relnode.c

/*-------------------------------------------------------------------------
 *
 * relnode.c
 *      Relation-node lookup/construction routines
 *
 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *      $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.93 2009/01/01 17:23:45 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/placeholder.h"
#include "optimizer/plancat.h"
#include "optimizer/restrictinfo.h"
#include "parser/parsetree.h"
#include "utils/hsearch.h"


typedef struct JoinHashEntry
{
      Relids            join_relids;      /* hash key --- MUST BE FIRST */
      RelOptInfo *join_rel;
} JoinHashEntry;

static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
                              RelOptInfo *input_rel);
static List *build_joinrel_restrictlist(PlannerInfo *root,
                                       RelOptInfo *joinrel,
                                       RelOptInfo *outer_rel,
                                       RelOptInfo *inner_rel);
static void build_joinrel_joinlist(RelOptInfo *joinrel,
                                 RelOptInfo *outer_rel,
                                 RelOptInfo *inner_rel);
static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
                                            List *joininfo_list,
                                            List *new_restrictlist);
static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
                                      List *joininfo_list,
                                      List *new_joininfo);


/*
 * build_simple_rel
 *      Construct a new RelOptInfo for a base relation or 'other' relation.
 */
RelOptInfo *
build_simple_rel(PlannerInfo *root, int relid, RelOptKind reloptkind)
{
      RelOptInfo *rel;
      RangeTblEntry *rte;

      /* Rel should not exist already */
      Assert(relid > 0 && relid < root->simple_rel_array_size);
      if (root->simple_rel_array[relid] != NULL)
            elog(ERROR, "rel %d already exists", relid);

      /* Fetch RTE for relation */
      rte = root->simple_rte_array[relid];
      Assert(rte != NULL);

      rel = makeNode(RelOptInfo);
      rel->reloptkind = reloptkind;
      rel->relids = bms_make_singleton(relid);
      rel->rows = 0;
      rel->width = 0;
      rel->reltargetlist = NIL;
      rel->pathlist = NIL;
      rel->cheapest_startup_path = NULL;
      rel->cheapest_total_path = NULL;
      rel->cheapest_unique_path = NULL;
      rel->relid = relid;
      rel->rtekind = rte->rtekind;
      /* min_attr, max_attr, attr_needed, attr_widths are set below */
      rel->indexlist = NIL;
      rel->pages = 0;
      rel->tuples = 0;
      rel->subplan = NULL;
      rel->subrtable = NIL;
      rel->baserestrictinfo = NIL;
      rel->baserestrictcost.startup = 0;
      rel->baserestrictcost.per_tuple = 0;
      rel->joininfo = NIL;
      rel->has_eclass_joins = false;
      rel->index_outer_relids = NULL;
      rel->index_inner_paths = NIL;

      /* Check type of rtable entry */
      switch (rte->rtekind)
      {
            case RTE_RELATION:
                  /* Table --- retrieve statistics from the system catalogs */
                  get_relation_info(root, rte->relid, rte->inh, rel);
                  break;
            case RTE_SUBQUERY:
            case RTE_FUNCTION:
            case RTE_VALUES:
            case RTE_CTE:

                  /*
                   * Subquery, function, or values list --- set up attr range and
                   * arrays
                   *
                   * Note: 0 is included in range to support whole-row Vars
                   */
                  rel->min_attr = 0;
                  rel->max_attr = list_length(rte->eref->colnames);
                  rel->attr_needed = (Relids *)
                        palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
                  rel->attr_widths = (int32 *)
                        palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
                  break;
            default:
                  elog(ERROR, "unrecognized RTE kind: %d",
                         (int) rte->rtekind);
                  break;
      }

      /* Save the finished struct in the query's simple_rel_array */
      root->simple_rel_array[relid] = rel;

      /*
       * If this rel is an appendrel parent, recurse to build "other rel"
       * RelOptInfos for its children.  They are "other rels" because they are
       * not in the main join tree, but we will need RelOptInfos to plan access
       * to them.
       */
      if (rte->inh)
      {
            ListCell   *l;

            foreach(l, root->append_rel_list)
            {
                  AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);

                  /* append_rel_list contains all append rels; ignore others */
                  if (appinfo->parent_relid != relid)
                        continue;

                  (void) build_simple_rel(root, appinfo->child_relid,
                                                      RELOPT_OTHER_MEMBER_REL);
            }
      }

      return rel;
}

/*
 * find_base_rel
 *      Find a base or other relation entry, which must already exist.
 */
RelOptInfo *
find_base_rel(PlannerInfo *root, int relid)
{
      RelOptInfo *rel;

      Assert(relid > 0);

      if (relid < root->simple_rel_array_size)
      {
            rel = root->simple_rel_array[relid];
            if (rel)
                  return rel;
      }

      elog(ERROR, "no relation entry for relid %d", relid);

      return NULL;                        /* keep compiler quiet */
}

/*
 * build_join_rel_hash
 *      Construct the auxiliary hash table for join relations.
 */
static void
build_join_rel_hash(PlannerInfo *root)
{
      HTAB     *hashtab;
      HASHCTL           hash_ctl;
      ListCell   *l;

      /* Create the hash table */
      MemSet(&hash_ctl, 0, sizeof(hash_ctl));
      hash_ctl.keysize = sizeof(Relids);
      hash_ctl.entrysize = sizeof(JoinHashEntry);
      hash_ctl.hash = bitmap_hash;
      hash_ctl.match = bitmap_match;
      hash_ctl.hcxt = CurrentMemoryContext;
      hashtab = hash_create("JoinRelHashTable",
                                      256L,
                                      &hash_ctl,
                              HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);

      /* Insert all the already-existing joinrels */
      foreach(l, root->join_rel_list)
      {
            RelOptInfo *rel = (RelOptInfo *) lfirst(l);
            JoinHashEntry *hentry;
            bool        found;

            hentry = (JoinHashEntry *) hash_search(hashtab,
                                                                     &(rel->relids),
                                                                     HASH_ENTER,
                                                                     &found);
            Assert(!found);
            hentry->join_rel = rel;
      }

      root->join_rel_hash = hashtab;
}

/*
 * find_join_rel
 *      Returns relation entry corresponding to 'relids' (a set of RT indexes),
 *      or NULL if none exists.  This is for join relations.
 */
RelOptInfo *
find_join_rel(PlannerInfo *root, Relids relids)
{
      /*
       * Switch to using hash lookup when list grows "too long".  The threshold
       * is arbitrary and is known only here.
       */
      if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
            build_join_rel_hash(root);

      /*
       * Use either hashtable lookup or linear search, as appropriate.
       *
       * Note: the seemingly redundant hashkey variable is used to avoid taking
       * the address of relids; unless the compiler is exceedingly smart, doing
       * so would force relids out of a register and thus probably slow down the
       * list-search case.
       */
      if (root->join_rel_hash)
      {
            Relids            hashkey = relids;
            JoinHashEntry *hentry;

            hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
                                                                     &hashkey,
                                                                     HASH_FIND,
                                                                     NULL);
            if (hentry)
                  return hentry->join_rel;
      }
      else
      {
            ListCell   *l;

            foreach(l, root->join_rel_list)
            {
                  RelOptInfo *rel = (RelOptInfo *) lfirst(l);

                  if (bms_equal(rel->relids, relids))
                        return rel;
            }
      }

      return NULL;
}

/*
 * build_join_rel
 *      Returns relation entry corresponding to the union of two given rels,
 *      creating a new relation entry if none already exists.
 *
 * 'joinrelids' is the Relids set that uniquely identifies the join
 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
 *          joined
 * 'sjinfo': join context info
 * 'restrictlist_ptr': result variable.  If not NULL, *restrictlist_ptr
 *          receives the list of RestrictInfo nodes that apply to this
 *          particular pair of joinable relations.
 *
 * restrictlist_ptr makes the routine's API a little grotty, but it saves
 * duplicated calculation of the restrictlist...
 */
RelOptInfo *
build_join_rel(PlannerInfo *root,
                     Relids joinrelids,
                     RelOptInfo *outer_rel,
                     RelOptInfo *inner_rel,
                     SpecialJoinInfo *sjinfo,
                     List **restrictlist_ptr)
{
      RelOptInfo *joinrel;
      List     *restrictlist;

      /*
       * See if we already have a joinrel for this set of base rels.
       */
      joinrel = find_join_rel(root, joinrelids);

      if (joinrel)
      {
            /*
             * Yes, so we only need to figure the restrictlist for this particular
             * pair of component relations.
             */
            if (restrictlist_ptr)
                  *restrictlist_ptr = build_joinrel_restrictlist(root,
                                                                                       joinrel,
                                                                                       outer_rel,
                                                                                       inner_rel);
            return joinrel;
      }

      /*
       * Nope, so make one.
       */
      joinrel = makeNode(RelOptInfo);
      joinrel->reloptkind = RELOPT_JOINREL;
      joinrel->relids = bms_copy(joinrelids);
      joinrel->rows = 0;
      joinrel->width = 0;
      joinrel->reltargetlist = NIL;
      joinrel->pathlist = NIL;
      joinrel->cheapest_startup_path = NULL;
      joinrel->cheapest_total_path = NULL;
      joinrel->cheapest_unique_path = NULL;
      joinrel->relid = 0;                 /* indicates not a baserel */
      joinrel->rtekind = RTE_JOIN;
      joinrel->min_attr = 0;
      joinrel->max_attr = 0;
      joinrel->attr_needed = NULL;
      joinrel->attr_widths = NULL;
      joinrel->indexlist = NIL;
      joinrel->pages = 0;
      joinrel->tuples = 0;
      joinrel->subplan = NULL;
      joinrel->subrtable = NIL;
      joinrel->baserestrictinfo = NIL;
      joinrel->baserestrictcost.startup = 0;
      joinrel->baserestrictcost.per_tuple = 0;
      joinrel->joininfo = NIL;
      joinrel->has_eclass_joins = false;
      joinrel->index_outer_relids = NULL;
      joinrel->index_inner_paths = NIL;

      /*
       * Create a new tlist containing just the vars that need to be output from
       * this join (ie, are needed for higher joinclauses or final output).
       *
       * NOTE: the tlist order for a join rel will depend on which pair of outer
       * and inner rels we first try to build it from.  But the contents should
       * be the same regardless.
       */
      build_joinrel_tlist(root, joinrel, outer_rel);
      build_joinrel_tlist(root, joinrel, inner_rel);
      add_placeholders_to_joinrel(root, joinrel);

      /*
       * Construct restrict and join clause lists for the new joinrel. (The
       * caller might or might not need the restrictlist, but I need it anyway
       * for set_joinrel_size_estimates().)
       */
      restrictlist = build_joinrel_restrictlist(root, joinrel,
                                                                    outer_rel, inner_rel);
      if (restrictlist_ptr)
            *restrictlist_ptr = restrictlist;
      build_joinrel_joinlist(joinrel, outer_rel, inner_rel);

      /*
       * This is also the right place to check whether the joinrel has any
       * pending EquivalenceClass joins.
       */
      joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);

      /*
       * Set estimates of the joinrel's size.
       */
      set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
                                             sjinfo, restrictlist);

      /*
       * Add the joinrel to the query's joinrel list, and store it into the
       * auxiliary hashtable if there is one.  NB: GEQO requires us to append
       * the new joinrel to the end of the list!
       */
      root->join_rel_list = lappend(root->join_rel_list, joinrel);

      if (root->join_rel_hash)
      {
            JoinHashEntry *hentry;
            bool        found;

            hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
                                                                     &(joinrel->relids),
                                                                     HASH_ENTER,
                                                                     &found);
            Assert(!found);
            hentry->join_rel = joinrel;
      }

      return joinrel;
}

/*
 * build_joinrel_tlist
 *      Builds a join relation's target list from an input relation.
 *      (This is invoked twice to handle the two input relations.)
 *
 * The join's targetlist includes all Vars of its member relations that
 * will still be needed above the join.  This subroutine adds all such
 * Vars from the specified input rel's tlist to the join rel's tlist.
 *
 * We also compute the expected width of the join's output, making use
 * of data that was cached at the baserel level by set_rel_width().
 */
static void
build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
                              RelOptInfo *input_rel)
{
      Relids            relids = joinrel->relids;
      ListCell   *vars;

      foreach(vars, input_rel->reltargetlist)
      {
            Node     *origvar = (Node *) lfirst(vars);
            Var            *var;
            RelOptInfo *baserel;
            int               ndx;

            /*
             * Ignore PlaceHolderVars in the input tlists; we'll make our
             * own decisions about whether to copy them.
             */
            if (IsA(origvar, PlaceHolderVar))
                  continue;

            /*
             * We can't run into any child RowExprs here, but we could find a
             * whole-row Var with a ConvertRowtypeExpr atop it.
             */
            var = (Var *) origvar;
            while (!IsA(var, Var))
            {
                  if (IsA(var, ConvertRowtypeExpr))
                        var = (Var *) ((ConvertRowtypeExpr *) var)->arg;
                  else
                        elog(ERROR, "unexpected node type in reltargetlist: %d",
                               (int) nodeTag(var));
            }

            /* Get the Var's original base rel */
            baserel = find_base_rel(root, var->varno);

            /* Is it still needed above this joinrel? */
            ndx = var->varattno - baserel->min_attr;
            if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
            {
                  /* Yup, add it to the output */
                  joinrel->reltargetlist = lappend(joinrel->reltargetlist, origvar);
                  joinrel->width += baserel->attr_widths[ndx];
            }
      }
}

/*
 * build_joinrel_restrictlist
 * build_joinrel_joinlist
 *      These routines build lists of restriction and join clauses for a
 *      join relation from the joininfo lists of the relations it joins.
 *
 *      These routines are separate because the restriction list must be
 *      built afresh for each pair of input sub-relations we consider, whereas
 *      the join list need only be computed once for any join RelOptInfo.
 *      The join list is fully determined by the set of rels making up the
 *      joinrel, so we should get the same results (up to ordering) from any
 *      candidate pair of sub-relations.  But the restriction list is whatever
 *      is not handled in the sub-relations, so it depends on which
 *      sub-relations are considered.
 *
 *      If a join clause from an input relation refers to base rels still not
 *      present in the joinrel, then it is still a join clause for the joinrel;
 *      we put it into the joininfo list for the joinrel.  Otherwise,
 *      the clause is now a restrict clause for the joined relation, and we
 *      return it to the caller of build_joinrel_restrictlist() to be stored in
 *      join paths made from this pair of sub-relations.    (It will not need to
 *      be considered further up the join tree.)
 *
 *      In many case we will find the same RestrictInfos in both input
 *      relations' joinlists, so be careful to eliminate duplicates.
 *      Pointer equality should be a sufficient test for dups, since all
 *      the various joinlist entries ultimately refer to RestrictInfos
 *      pushed into them by distribute_restrictinfo_to_rels().
 *
 * 'joinrel' is a join relation node
 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
 *          to form joinrel.
 *
 * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
 * whereas build_joinrel_joinlist() stores its results in the joinrel's
 * joininfo list.  One or the other must accept each given clause!
 *
 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
 * up to the join relation.  I believe this is no longer necessary, because
 * RestrictInfo nodes are no longer context-dependent.      Instead, just include
 * the original nodes in the lists made for the join relation.
 */
static List *
build_joinrel_restrictlist(PlannerInfo *root,
                                       RelOptInfo *joinrel,
                                       RelOptInfo *outer_rel,
                                       RelOptInfo *inner_rel)
{
      List     *result;

      /*
       * Collect all the clauses that syntactically belong at this level,
       * eliminating any duplicates (important since we will see many of the
       * same clauses arriving from both input relations).
       */
      result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
      result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result);

      /*
       * Add on any clauses derived from EquivalenceClasses.      These cannot be
       * redundant with the clauses in the joininfo lists, so don't bother
       * checking.
       */
      result = list_concat(result,
                                     generate_join_implied_equalities(root,
                                                                                      joinrel,
                                                                                      outer_rel,
                                                                                      inner_rel));

      return result;
}

static void
build_joinrel_joinlist(RelOptInfo *joinrel,
                                 RelOptInfo *outer_rel,
                                 RelOptInfo *inner_rel)
{
      List     *result;

      /*
       * Collect all the clauses that syntactically belong above this level,
       * eliminating any duplicates (important since we will see many of the
       * same clauses arriving from both input relations).
       */
      result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
      result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);

      joinrel->joininfo = result;
}

static List *
subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
                                            List *joininfo_list,
                                            List *new_restrictlist)
{
      ListCell   *l;

      foreach(l, joininfo_list)
      {
            RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

            if (bms_is_subset(rinfo->required_relids, joinrel->relids))
            {
                  /*
                   * This clause becomes a restriction clause for the joinrel, since
                   * it refers to no outside rels.  Add it to the list, being
                   * careful to eliminate duplicates. (Since RestrictInfo nodes in
                   * different joinlists will have been multiply-linked rather than
                   * copied, pointer equality should be a sufficient test.)
                   */
                  new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo);
            }
            else
            {
                  /*
                   * This clause is still a join clause at this level, so we ignore
                   * it in this routine.
                   */
            }
      }

      return new_restrictlist;
}

static List *
subbuild_joinrel_joinlist(RelOptInfo *joinrel,
                                      List *joininfo_list,
                                      List *new_joininfo)
{
      ListCell   *l;

      foreach(l, joininfo_list)
      {
            RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

            if (bms_is_subset(rinfo->required_relids, joinrel->relids))
            {
                  /*
                   * This clause becomes a restriction clause for the joinrel, since
                   * it refers to no outside rels.  So we can ignore it in this
                   * routine.
                   */
            }
            else
            {
                  /*
                   * This clause is still a join clause at this level, so add it to
                   * the new joininfo list, being careful to eliminate duplicates.
                   * (Since RestrictInfo nodes in different joinlists will have been
                   * multiply-linked rather than copied, pointer equality should be
                   * a sufficient test.)
                   */
                  new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
            }
      }

      return new_joininfo;
}

Generated by  Doxygen 1.6.0   Back to index