prepqual.c

来自「PostgreSQL7.4.6 for Linux」· C语言 代码 · 共 979 行 · 第 1/2 页

push_nots(Expr *qual)
{
	if (qual == NULL)
		return make_notclause(qual);	/* XXX is this right?  Or
										 * possible? */

	/*
	 * Negate an operator clause if possible: ("NOT" (< A B)) => (> A B)
	 * Otherwise, retain the clause as it is (the 'not' can't be pushed
	 * down any farther).
	 */
	if (is_opclause(qual))
	{
		OpExpr	   *opexpr = (OpExpr *) qual;
		Oid			negator = get_negator(opexpr->opno);

		if (negator)
			return make_opclause(negator,
								 opexpr->opresulttype,
								 opexpr->opretset,
								 (Expr *) get_leftop(qual),
								 (Expr *) get_rightop(qual));
		else
			return make_notclause(qual);
	}
	else if (and_clause((Node *) qual))
	{
		/*--------------------
		 * Apply DeMorgan's Laws:
		 *		("NOT" ("AND" A B)) => ("OR" ("NOT" A) ("NOT" B))
		 *		("NOT" ("OR" A B))	=> ("AND" ("NOT" A) ("NOT" B))
		 * i.e., swap AND for OR and negate all the subclauses.
		 *--------------------
		 */
		FastList	t_list;
		List	   *temp;

		FastListInit(&t_list);
		foreach(temp, ((BoolExpr *) qual)->args)
			FastAppend(&t_list, push_nots(lfirst(temp)));
		return make_orclause(pull_ors(FastListValue(&t_list)));
	}
	else if (or_clause((Node *) qual))
	{
		FastList	t_list;
		List	   *temp;

		FastListInit(&t_list);
		foreach(temp, ((BoolExpr *) qual)->args)
			FastAppend(&t_list, push_nots(lfirst(temp)));
		return make_andclause(pull_ands(FastListValue(&t_list)));
	}
	else if (not_clause((Node *) qual))
	{
		/*
		 * Another 'not' cancels this 'not', so eliminate the 'not' and
		 * stop negating this branch.  But search the subexpression for
		 * more 'not's to simplify.
		 */
		return find_nots(get_notclausearg(qual));
	}
	else
	{
		/*
		 * We don't know how to negate anything else, place a 'not' at
		 * this level.
		 */
		return make_notclause(qual);
	}
}

/*
 * find_ors
 *	  Given a qualification tree with the 'not's pushed down, convert it
 *	  to a tree in CNF by repeatedly applying the rule:
 *				("OR" A ("AND" B C))  => ("AND" ("OR" A B) ("OR" A C))
 *
 *	  Note that 'or' clauses will always be turned into 'and' clauses
 *	  if they contain any 'and' subclauses.
 *
 * Returns the modified qualification.	AND/OR flatness is preserved.
 */
static Expr *
find_ors(Expr *qual)
{
	if (qual == NULL)
		return NULL;

	/* We used to recurse into opclauses here, but I see no reason to... */
	if (and_clause((Node *) qual))
	{
		List	   *andlist = NIL;
		List	   *temp;

		foreach(temp, ((BoolExpr *) qual)->args)
			andlist = lappend(andlist, find_ors(lfirst(temp)));
		return make_andclause(pull_ands(andlist));
	}
	else if (or_clause((Node *) qual))
	{
		List	   *orlist = NIL;
		List	   *temp;

		foreach(temp, ((BoolExpr *) qual)->args)
			orlist = lappend(orlist, find_ors(lfirst(temp)));
		return or_normalize(pull_ors(orlist));
	}
	else if (not_clause((Node *) qual))
		return make_notclause(find_ors(get_notclausearg(qual)));
	else
		return qual;
}

/*
 * or_normalize
 *	  Given a list of exprs which are 'or'ed together, try to apply
 *	  the distributive law
 *				("OR" A ("AND" B C))  => ("AND" ("OR" A B) ("OR" A C))
 *	  to convert the top-level OR clause to a top-level AND clause.
 *
 * Returns the resulting expression (could be an AND clause, an OR
 * clause, or maybe even a single subexpression).
 */
static Expr *
or_normalize(List *orlist)
{
	Expr	   *distributable = NULL;
	int			num_subclauses = 1;
	List	   *andclauses = NIL;
	List	   *temp;

	if (orlist == NIL)
		return NULL;			/* probably can't happen */
	if (lnext(orlist) == NIL)
		return lfirst(orlist);	/* single-expression OR (can this happen?) */

	/*
	 * If we have a choice of AND clauses, pick the one with the most
	 * subclauses.	Because we initialized num_subclauses = 1, any AND
	 * clauses with only one arg will be ignored as useless.
	 */
	foreach(temp, orlist)
	{
		Expr	   *clause = lfirst(temp);

		if (and_clause((Node *) clause))
		{
			int			nclauses = length(((BoolExpr *) clause)->args);

			if (nclauses > num_subclauses)
			{
				distributable = clause;
				num_subclauses = nclauses;
			}
		}
	}

	/* if there's no suitable AND clause, we can't transform the OR */
	if (!distributable)
		return make_orclause(orlist);

	/*
	 * Caution: lremove destructively modifies the input orlist. This
	 * should be OK, since or_normalize is only called with freshly
	 * constructed lists that are not referenced elsewhere.
	 */
	orlist = lremove(distributable, orlist);

	foreach(temp, ((BoolExpr *) distributable)->args)
	{
		Expr	   *andclause = lfirst(temp);
		List	   *neworlist;

		/*
		 * We are going to insert the orlist into multiple places in the
		 * result expression.  For most expression types, it'd be OK to
		 * just have multiple links to the same subtree, but this fails
		 * badly for SubLinks (and perhaps other cases?).  For safety, we
		 * make a distinct copy for each place the orlist is inserted.
		 */
		if (lnext(temp) == NIL)
			neworlist = orlist; /* can use original tree at the end */
		else
			neworlist = copyObject(orlist);

		/*
		 * pull_ors is needed here in case andclause has a top-level OR.
		 * Then we recursively apply or_normalize, since there might be an
		 * AND subclause in the resulting OR-list.
		 */
		andclause = or_normalize(pull_ors(lcons(andclause, neworlist)));
		andclauses = lappend(andclauses, andclause);
	}

	/* pull_ands is needed in case any sub-or_normalize succeeded */
	return make_andclause(pull_ands(andclauses));
}

/*
 * find_ands
 *	  Given a qualification tree with the 'not's pushed down, convert it
 *	  to a tree in DNF by repeatedly applying the rule:
 *				("AND" A ("OR" B C))  => ("OR" ("AND" A B) ("AND" A C))
 *
 *	  Note that 'and' clauses will always be turned into 'or' clauses
 *	  if they contain any 'or' subclauses.
 *
 * Returns the modified qualification.	AND/OR flatness is preserved.
 */
static Expr *
find_ands(Expr *qual)
{
	if (qual == NULL)
		return NULL;

	/* We used to recurse into opclauses here, but I see no reason to... */
	if (or_clause((Node *) qual))
	{
		List	   *orlist = NIL;
		List	   *temp;

		foreach(temp, ((BoolExpr *) qual)->args)
			orlist = lappend(orlist, find_ands(lfirst(temp)));
		return make_orclause(pull_ors(orlist));
	}
	else if (and_clause((Node *) qual))
	{
		List	   *andlist = NIL;
		List	   *temp;

		foreach(temp, ((BoolExpr *) qual)->args)
			andlist = lappend(andlist, find_ands(lfirst(temp)));
		return and_normalize(pull_ands(andlist));
	}
	else if (not_clause((Node *) qual))
		return make_notclause(find_ands(get_notclausearg(qual)));
	else
		return qual;
}

/*
 * and_normalize
 *	  Given a list of exprs which are 'and'ed together, try to apply
 *	  the distributive law
 *				("AND" A ("OR" B C))  => ("OR" ("AND" A B) ("AND" A C))
 *	  to convert the top-level AND clause to a top-level OR clause.
 *
 * Returns the resulting expression (could be an AND clause, an OR
 * clause, or maybe even a single subexpression).
 */
static Expr *
and_normalize(List *andlist)
{
	Expr	   *distributable = NULL;
	int			num_subclauses = 1;
	List	   *orclauses = NIL;
	List	   *temp;

	if (andlist == NIL)
		return NULL;			/* probably can't happen */
	if (lnext(andlist) == NIL)
		return lfirst(andlist); /* single-expression AND (can this
								 * happen?) */

	/*
	 * If we have a choice of OR clauses, pick the one with the most
	 * subclauses.	Because we initialized num_subclauses = 1, any OR
	 * clauses with only one arg will be ignored as useless.
	 */
	foreach(temp, andlist)
	{
		Expr	   *clause = lfirst(temp);

		if (or_clause((Node *) clause))
		{
			int			nclauses = length(((BoolExpr *) clause)->args);

			if (nclauses > num_subclauses)
			{
				distributable = clause;
				num_subclauses = nclauses;
			}
		}
	}

	/* if there's no suitable OR clause, we can't transform the AND */
	if (!distributable)
		return make_andclause(andlist);

	/*
	 * Caution: lremove destructively modifies the input andlist. This
	 * should be OK, since and_normalize is only called with freshly
	 * constructed lists that are not referenced elsewhere.
	 */
	andlist = lremove(distributable, andlist);

	foreach(temp, ((BoolExpr *) distributable)->args)
	{
		Expr	   *orclause = lfirst(temp);
		List	   *newandlist;

		/*
		 * We are going to insert the andlist into multiple places in the
		 * result expression.  For most expression types, it'd be OK to
		 * just have multiple links to the same subtree, but this fails
		 * badly for SubLinks (and perhaps other cases?).  For safety, we
		 * make a distinct copy for each place the andlist is inserted.
		 */
		if (lnext(temp) == NIL)
			newandlist = andlist;		/* can use original tree at the
										 * end */
		else
			newandlist = copyObject(andlist);

		/*
		 * pull_ands is needed here in case orclause has a top-level AND.
		 * Then we recursively apply and_normalize, since there might be
		 * an OR subclause in the resulting AND-list.
		 */
		orclause = and_normalize(pull_ands(lcons(orclause, newandlist)));
		orclauses = lappend(orclauses, orclause);
	}

	/* pull_ors is needed in case any sub-and_normalize succeeded */
	return make_orclause(pull_ors(orclauses));
}

/*
 * qual_cleanup
 *	  Fix up a qualification by removing duplicate entries (which could be
 *	  created during normalization, if identical subexpressions from different
 *	  parts of the tree are brought together).	Also, check for AND and OR
 *	  clauses with only one remaining subexpression, and simplify.
 *
 * Returns the modified qualification.
 */
static Expr *
qual_cleanup(Expr *qual)
{
	if (qual == NULL)
		return NULL;

	if (and_clause((Node *) qual))
	{
		List	   *andlist = NIL;
		List	   *temp;

		foreach(temp, ((BoolExpr *) qual)->args)
			andlist = lappend(andlist, qual_cleanup(lfirst(temp)));

		andlist = remove_duplicates(pull_ands(andlist));

		if (length(andlist) > 1)
			return make_andclause(andlist);
		else
			return lfirst(andlist);
	}
	else if (or_clause((Node *) qual))
	{
		List	   *orlist = NIL;
		List	   *temp;

		foreach(temp, ((BoolExpr *) qual)->args)
			orlist = lappend(orlist, qual_cleanup(lfirst(temp)));

		orlist = remove_duplicates(pull_ors(orlist));

		if (length(orlist) > 1)
			return make_orclause(orlist);
		else
			return lfirst(orlist);
	}
	else if (not_clause((Node *) qual))
		return make_notclause(qual_cleanup(get_notclausearg(qual)));
	else
		return qual;
}

/*
 * remove_duplicates
 */
static List *
remove_duplicates(List *list)
{
	List	   *result = NIL;
	List	   *i;

	if (length(list) <= 1)
		return list;

	foreach(i, list)
	{
		if (!member(lfirst(i), result))
			result = lappend(result, lfirst(i));
	}
	return result;
}

/*
 * count_bool_nodes
 *		Support for heuristics in canonicalize_qual(): count the
 *		number of nodes that are inputs to the top level AND/OR/NOT
 *		part of a qual tree, and estimate how many nodes will appear
 *		in the CNF'ified or DNF'ified equivalent of the expression.
 *
 * This is just an approximate calculation; it doesn't deal with NOTs
 * very well, and of course it cannot detect possible simplifications
 * from eliminating duplicate subclauses.  The idea is just to cheaply
 * determine whether CNF will be markedly worse than DNF or vice versa.
 *
 * The counts/estimates are represented as doubles to avoid risk of overflow.
 */
static void
count_bool_nodes(Expr *qual,
				 double *nodes,
				 double *cnfnodes,
				 double *dnfnodes)
{
	List	   *temp;
	double		subnodes,
				subcnfnodes,
				subdnfnodes;

	if (and_clause((Node *) qual))
	{
		*nodes = *cnfnodes = 0.0;
		*dnfnodes = 1.0;		/* DNF nodes will be product of sub-counts */

		foreach(temp, ((BoolExpr *) qual)->args)
		{
			count_bool_nodes(lfirst(temp),
							 &subnodes, &subcnfnodes, &subdnfnodes);
			*nodes += subnodes;
			*cnfnodes += subcnfnodes;
			*dnfnodes *= subdnfnodes;
		}

		/*
		 * we could get dnfnodes < cnfnodes here, if all the sub-nodes are
		 * simple ones with count 1.  Make sure dnfnodes isn't too small.
		 */
		if (*dnfnodes < *cnfnodes)
			*dnfnodes = *cnfnodes;
	}
	else if (or_clause((Node *) qual))
	{
		*nodes = *dnfnodes = 0.0;
		*cnfnodes = 1.0;		/* CNF nodes will be product of sub-counts */

		foreach(temp, ((BoolExpr *) qual)->args)
		{
			count_bool_nodes(lfirst(temp),
							 &subnodes, &subcnfnodes, &subdnfnodes);
			*nodes += subnodes;
			*cnfnodes *= subcnfnodes;
			*dnfnodes += subdnfnodes;
		}

		/*
		 * we could get cnfnodes < dnfnodes here, if all the sub-nodes are
		 * simple ones with count 1.  Make sure cnfnodes isn't too small.
		 */
		if (*cnfnodes < *dnfnodes)
			*cnfnodes = *dnfnodes;
	}
	else if (not_clause((Node *) qual))
	{
		count_bool_nodes(get_notclausearg(qual),
						 nodes, cnfnodes, dnfnodes);
	}
	else if (contain_subplans((Node *) qual))
	{
		/*
		 * charge extra for subexpressions containing sub-SELECTs, to
		 * discourage us from rearranging them in a way that might
		 * generate N copies of a subselect rather than one.  The magic
		 * constant here interacts with the "4x maximum growth" heuristic
		 * in canonicalize_qual().
		 */
		*nodes = 1.0;
		*cnfnodes = *dnfnodes = 25.0;
	}
	else
	{
		/* anything else counts 1 for my purposes */
		*nodes = *cnfnodes = *dnfnodes = 1.0;
	}
}