initsplan.c

PostgreSQL 8.1.4的源码 适用于Linux下的开源数据库系统

/*-------------------------------------------------------------------------
 *
 * initsplan.c
 *	  Target list, qualification, joininfo initialization routines
 *
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/initsplan.c,v 1.110.2.2 2005/11/22 18:23:11 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "catalog/pg_operator.h"
#include "catalog/pg_type.h"
#include "nodes/makefuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/restrictinfo.h"
#include "optimizer/tlist.h"
#include "optimizer/var.h"
#include "parser/parsetree.h"
#include "parser/parse_expr.h"
#include "parser/parse_oper.h"
#include "utils/builtins.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"


static void mark_baserels_for_outer_join(PlannerInfo *root, Relids rels,
							 Relids outerrels);
static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
						bool is_pushed_down,
						bool is_deduced,
						bool below_outer_join,
						Relids outerjoin_nonnullable,
						Relids qualscope);
static void add_vars_to_targetlist(PlannerInfo *root, List *vars,
					   Relids where_needed);
static bool qual_is_redundant(PlannerInfo *root, RestrictInfo *restrictinfo,
				  List *restrictlist);
static void check_mergejoinable(RestrictInfo *restrictinfo);
static void check_hashjoinable(RestrictInfo *restrictinfo);


/*****************************************************************************
 *
 *	 JOIN TREES
 *
 *****************************************************************************/

/*
 * add_base_rels_to_query
 *
 *	  Scan the query's jointree and create baserel RelOptInfos for all
 *	  the base relations (ie, table, subquery, and function RTEs)
 *	  appearing in the jointree.
 *
 * At the end of this process, there should be one baserel RelOptInfo for
 * every non-join RTE that is used in the query.  Therefore, this routine
 * is the only place that should call build_base_rel.  But build_other_rel
 * will be used later to build rels for inheritance children.
 */
void
add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
{
	if (jtnode == NULL)
		return;
	if (IsA(jtnode, RangeTblRef))
	{
		int			varno = ((RangeTblRef *) jtnode)->rtindex;

		build_base_rel(root, varno);
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		foreach(l, f->fromlist)
			add_base_rels_to_query(root, lfirst(l));
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		add_base_rels_to_query(root, j->larg);
		add_base_rels_to_query(root, j->rarg);
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
}


/*****************************************************************************
 *
 *	 TARGET LISTS
 *
 *****************************************************************************/

/*
 * build_base_rel_tlists
 *	  Add targetlist entries for each var needed in the query's final tlist
 *	  to the appropriate base relations.
 *
 * We mark such vars as needed by "relation 0" to ensure that they will
 * propagate up through all join plan steps.
 */
void
build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
{
	List	   *tlist_vars = pull_var_clause((Node *) final_tlist, false);

	if (tlist_vars != NIL)
	{
		add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
		list_free(tlist_vars);
	}
}

/*
 * add_vars_to_targetlist
 *	  For each variable appearing in the list, add it to the owning
 *	  relation's targetlist if not already present, and mark the variable
 *	  as being needed for the indicated join (or for final output if
 *	  where_needed includes "relation 0").
 */
static void
add_vars_to_targetlist(PlannerInfo *root, List *vars, Relids where_needed)
{
	ListCell   *temp;

	Assert(!bms_is_empty(where_needed));

	foreach(temp, vars)
	{
		Var		   *var = (Var *) lfirst(temp);
		RelOptInfo *rel = find_base_rel(root, var->varno);
		int			attrno = var->varattno;

		Assert(attrno >= rel->min_attr && attrno <= rel->max_attr);
		attrno -= rel->min_attr;
		if (bms_is_empty(rel->attr_needed[attrno]))
		{
			/* Variable not yet requested, so add to reltargetlist */
			/* XXX is copyObject necessary here? */
			rel->reltargetlist = lappend(rel->reltargetlist, copyObject(var));
		}
		rel->attr_needed[attrno] = bms_add_members(rel->attr_needed[attrno],
												   where_needed);
	}
}


/*****************************************************************************
 *
 *	  QUALIFICATIONS
 *
 *****************************************************************************/


/*
 * distribute_quals_to_rels
 *	  Recursively scan the query's join tree for WHERE and JOIN/ON qual
 *	  clauses, and add these to the appropriate restrictinfo and joininfo
 *	  lists belonging to base RelOptInfos.	Also, base RelOptInfos are marked
 *	  with outerjoinset information, to aid in proper positioning of qual
 *	  clauses that appear above outer joins.
 *
 * jtnode is the jointree node currently being examined.  below_outer_join
 * is TRUE if this node is within the nullable side of a higher-level outer
 * join.
 *
 * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
 * be evaluated at the lowest level where all the variables it mentions are
 * available.  However, we cannot push a qual down into the nullable side(s)
 * of an outer join since the qual might eliminate matching rows and cause a
 * NULL row to be incorrectly emitted by the join.	Therefore, rels appearing
 * within the nullable side(s) of an outer join are marked with
 *		outerjoinset = set of Relids used at the outer join node.
 * This set will be added to the set of rels referenced by quals using such
 * a rel, thereby forcing them up the join tree to the right level.
 *
 * To ease the calculation of these values, distribute_quals_to_rels() returns
 * the set of base Relids involved in its own level of join.  This is just an
 * internal convenience; no outside callers pay attention to the result.
 */
Relids
distribute_quals_to_rels(PlannerInfo *root, Node *jtnode,
						 bool below_outer_join)
{
	Relids		result = NULL;

	if (jtnode == NULL)
		return result;
	if (IsA(jtnode, RangeTblRef))
	{
		int			varno = ((RangeTblRef *) jtnode)->rtindex;

		/* No quals to deal with, just return correct result */
		result = bms_make_singleton(varno);
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		/*
		 * First, recurse to handle child joins.
		 */
		foreach(l, f->fromlist)
		{
			result = bms_add_members(result,
									 distribute_quals_to_rels(root,
															  lfirst(l),
														  below_outer_join));
		}

		/*
		 * Now process the top-level quals.  These are always marked as
		 * "pushed down", since they clearly didn't come from a JOIN expr.
		 */
		foreach(l, (List *) f->quals)
			distribute_qual_to_rels(root, (Node *) lfirst(l),
									true, false, below_outer_join,
									NULL, result);
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;
		Relids		leftids,
					rightids,
					nonnullable_rels,
					nullable_rels;
		ListCell   *qual;

		/*
		 * Order of operations here is subtle and critical.  First we recurse
		 * to handle sub-JOINs.  Their join quals will be placed without
		 * regard for whether this level is an outer join, which is correct.
		 * Then we place our own join quals, which are restricted by lower
		 * outer joins in any case, and are forced to this level if this is an
		 * outer join and they mention the outer side.	Finally, if this is an
		 * outer join, we mark baserels contained within the inner side(s)
		 * with our own rel set; this will prevent quals above us in the join
		 * tree that use those rels from being pushed down below this level.
		 * (It's okay for upper quals to be pushed down to the outer side,
		 * however.)
		 */
		switch (j->jointype)
		{
			case JOIN_INNER:
				leftids = distribute_quals_to_rels(root, j->larg,
												   below_outer_join);
				rightids = distribute_quals_to_rels(root, j->rarg,
													below_outer_join);

				result = bms_union(leftids, rightids);
				/* Inner join adds no restrictions for quals */
				nonnullable_rels = NULL;
				nullable_rels = NULL;
				break;
			case JOIN_LEFT:
				leftids = distribute_quals_to_rels(root, j->larg,
												   below_outer_join);
				rightids = distribute_quals_to_rels(root, j->rarg,
													true);

				result = bms_union(leftids, rightids);
				nonnullable_rels = leftids;
				nullable_rels = rightids;
				break;
			case JOIN_FULL:
				leftids = distribute_quals_to_rels(root, j->larg,
												   true);
				rightids = distribute_quals_to_rels(root, j->rarg,
													true);

				result = bms_union(leftids, rightids);
				/* each side is both outer and inner */
				nonnullable_rels = result;
				nullable_rels = result;
				break;
			case JOIN_RIGHT:
				leftids = distribute_quals_to_rels(root, j->larg,
												   true);
				rightids = distribute_quals_to_rels(root, j->rarg,
													below_outer_join);

				result = bms_union(leftids, rightids);
				nonnullable_rels = rightids;
				nullable_rels = leftids;
				break;
			case JOIN_UNION:

				/*
				 * This is where we fail if upper levels of planner haven't
				 * rewritten UNION JOIN as an Append ...
				 */
				ereport(ERROR,
						(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
						 errmsg("UNION JOIN is not implemented")));
				nonnullable_rels = NULL;		/* keep compiler quiet */
				nullable_rels = NULL;
				break;
			default:
				elog(ERROR, "unrecognized join type: %d",
					 (int) j->jointype);
				nonnullable_rels = NULL;		/* keep compiler quiet */
				nullable_rels = NULL;
				break;
		}

		foreach(qual, (List *) j->quals)
			distribute_qual_to_rels(root, (Node *) lfirst(qual),
									false, false, below_outer_join,
									nonnullable_rels, result);

		if (nullable_rels != NULL)
			mark_baserels_for_outer_join(root, nullable_rels, result);
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
	return result;
}

/*
 * mark_baserels_for_outer_join
 *	  Mark all base rels listed in 'rels' as having the given outerjoinset.
 */
static void
mark_baserels_for_outer_join(PlannerInfo *root, Relids rels, Relids outerrels)
{
	Relids		tmprelids;
	int			relno;

	tmprelids = bms_copy(rels);
	while ((relno = bms_first_member(tmprelids)) >= 0)
	{
		RelOptInfo *rel = find_base_rel(root, relno);