xfunc.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * xfunc.c
 *	  Utility routines to handle expensive function optimization.
 *	  Includes xfunc_trypullup(), which attempts early pullup of predicates
 *	  to allow for maximal pruning.
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/optimizer/path/_deadcode/xfunc.c,v 1.5 1999/07/03 00:32:42 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
#include <math.h>				/* for MAXFLOAT on most systems */

#include <values.h>				/* for MAXFLOAT on SunOS */
#include <string.h>

#include "postgres.h"

#include "access/htup.h"
#include "access/heapam.h"
#include "catalog/pg_language.h"
#include "catalog/pg_proc.h"
#include "catalog/pg_type.h"
#include "lib/lispsort.h"
#include "nodes/nodes.h"
#include "nodes/pg_list.h"
#include "nodes/primnodes.h"
#include "nodes/relation.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/internal.h"
#include "optimizer/keys.h"
#include "optimizer/pathnode.h"
#include "optimizer/tlist.h"	/* for get_expr */
#include "optimizer/xfunc.h"
#include "storage/buf_internals.h"		/* for NBuffers */
#include "tcop/dest.h"
#include "utils/syscache.h"

#define ever ; 1 ;

/* local funcs */
static int xfunc_card_unreferenced(Query *queryInfo,
						Expr *clause, Relids referenced);

*/

/*
** xfunc_trypullup
**	  Preliminary pullup of predicates, to allow for maximal pruning.
** Given a relation, check each of its paths and see if you can
** pullup clauses from its inner and outer.
*/

void
xfunc_trypullup(RelOptInfo rel)
{
	LispValue	y;				/* list ptr */
	RestrictInfo maxcinfo;		/* The RestrictInfo to pull up, as
								 * calculated by xfunc_shouldpull() */
	JoinPath	curpath;		/* current path in list */
	int			progress;		/* has progress been made this time
								 * through? */
	int			clausetype;

	do
	{
		progress = false;		/* no progress yet in this iteration */
		foreach(y, get_pathlist(rel))
		{
			curpath = (JoinPath) lfirst(y);

			/*
			 * * for each operand, attempt to pullup predicates until
			 * first * failure.
			 */
			for (ever)
			{
				/* No, the following should NOT be '=='  !! */
				if (clausetype = xfunc_shouldpull((Path) get_innerjoinpath(curpath),
											  curpath, INNER, &maxcinfo))
				{

					xfunc_pullup((Path) get_innerjoinpath(curpath),
								 curpath, maxcinfo, INNER, clausetype);
					progress = true;
				}
				else
					break;
			}
			for (ever)
			{

				/* No, the following should NOT be '=='  !! */
				if (clausetype = xfunc_shouldpull((Path) get_outerjoinpath(curpath),
											  curpath, OUTER, &maxcinfo))
				{

					xfunc_pullup((Path) get_outerjoinpath(curpath),
								 curpath, maxcinfo, OUTER, clausetype);
					progress = true;
				}
				else
					break;
			}

			/*
			 * * make sure the unpruneable flag bubbles up, i.e. * if
			 * anywhere below us in the path pruneable is false, * then
			 * pruneable should be false here
			 */
			if (get_pruneable(get_parent(curpath)) &&
				(!get_pruneable(get_parent
								((Path) get_innerjoinpath(curpath))) ||
				 !get_pruneable(get_parent((Path)
										   get_outerjoinpath(curpath)))))
			{

				set_pruneable(get_parent(curpath), false);
				progress = true;
			}
		}
	} while (progress);
}

/*
 ** xfunc_shouldpull
 **    find clause with highest rank, and decide whether to pull it up
 ** from child to parent.  Currently we only pullup secondary join clauses
 ** that are in the pathrestrictinfo.  Secondary hash and sort clauses are
 ** left where they are.
 **    If we find an expensive function but decide *not* to pull it up,
 ** we'd better set the unpruneable flag.  -- JMH, 11/11/92
 **
 ** Returns:  0 if nothing left to pullup
 **			  XFUNC_LOCPRD if a local predicate is to be pulled up
 **			  XFUNC_JOINPRD if a secondary join predicate is to be pulled up
 */
int
xfunc_shouldpull(Query *queryInfo,
				 Path childpath,
				 JoinPath parentpath,
				 int whichchild,
				 RestrictInfo *maxcinfopt)		/* Out: pointer to clause
												 * to pullup */
{
	LispValue	clauselist,
				tmplist;		/* lists of clauses */
	RestrictInfo maxcinfo;		/* clause to pullup */
	LispValue	primjoinclause	/* primary join clause */
	= xfunc_primary_join(parentpath);
	Cost		tmprank,
				maxrank = (-1 * MAXFLOAT);		/* ranks of clauses */
	Cost		joinselec = 0;	/* selectivity of the join predicate */
	Cost		joincost = 0;	/* join cost + primjoinclause cost */
	int			retval = XFUNC_LOCPRD;

	clauselist = get_loc_restrictinfo(childpath);

	if (clauselist != LispNil)
	{
		/* find local predicate with maximum rank */
		for (tmplist = clauselist,
			 maxcinfo = (RestrictInfo) lfirst(tmplist),
			 maxrank = xfunc_rank(get_clause(maxcinfo));
			 tmplist != LispNil;
			 tmplist = lnext(tmplist))
		{

			if ((tmprank = xfunc_rank(get_clause((RestrictInfo) lfirst(tmplist))))
				> maxrank)
			{
				maxcinfo = (RestrictInfo) lfirst(tmplist);
				maxrank = tmprank;
			}
		}
	}

	/*
	 * * If child is a join path, and there are multiple join clauses, *
	 * see if any join clause has even higher rank than the highest *
	 * local predicate
	 */
	if (is_join(childpath) && xfunc_num_join_clauses((JoinPath) childpath) > 1)
		for (tmplist = get_pathrestrictinfo((JoinPath) childpath);
			 tmplist != LispNil;
			 tmplist = lnext(tmplist))
		{

			if (tmplist != LispNil &&
				(tmprank = xfunc_rank(get_clause((RestrictInfo) lfirst(tmplist))))
				> maxrank)
			{
				maxcinfo = (RestrictInfo) lfirst(tmplist);
				maxrank = tmprank;
				retval = XFUNC_JOINPRD;
			}
		}
	if (maxrank == (-1 * MAXFLOAT))		/* no expensive clauses */
		return 0;

	/*
	 * * Pullup over join if clause is higher rank than join, or if * join
	 * is nested loop and current path is inner child (note that *
	 * restrictions on the inner of a nested loop don't buy you anything
	 * -- * you still have to scan the entire inner relation each time). *
	 * Note that the cost of a secondary join clause is only what's *
	 * calculated by xfunc_expense(), since the actual joining * (i.e. the
	 * usual path_cost) is paid for by the primary join clause.
	 */
	if (primjoinclause != LispNil)
	{
		joinselec = compute_clause_selec(queryInfo, primjoinclause, LispNil);
		joincost = xfunc_join_expense(parentpath, whichchild);

		if (XfuncMode == XFUNC_PULLALL ||
			(XfuncMode != XFUNC_WAIT &&
			 ((joincost != 0 &&
			   (maxrank = xfunc_rank(get_clause(maxcinfo))) >
			   ((joinselec - 1.0) / joincost))
			  || (joincost == 0 && joinselec < 1)
			  || (!is_join(childpath)
				  && (whichchild == INNER)
				  && IsA(parentpath, NestPath)
				  &&!IsA(parentpath, HashPath)
				  &&!IsA(parentpath, MergePath)))))
		{

			*maxcinfopt = maxcinfo;
			return retval;

		}
		else if (maxrank != -(MAXFLOAT))
		{

			/*
			 * * we've left an expensive restriction below a join.  Since *
			 * we may pullup this restriction in predmig.c, we'd best *
			 * set the RelOptInfo of this join to be unpruneable
			 */
			set_pruneable(get_parent(parentpath), false);
			/* and fall through */
		}
	}
	return 0;
}


/*
 ** xfunc_pullup
 **    move clause from child pathnode to parent pathnode.	 This operation
 ** makes the child pathnode produce a larger relation than it used to.
 ** This means that we must construct a new RelOptInfo just for the childpath,
 ** although this RelOptInfo will not be added to the list of Rels to be joined up
 ** in the query; it's merely a parent for the new childpath.
 **    We also have to fix up the path costs of the child and parent.
 **
 ** Now returns a pointer to the new pulled-up RestrictInfo. -- JMH, 11/18/92
 */
RestrictInfo
xfunc_pullup(Query *queryInfo,
			 Path childpath,
			 JoinPath parentpath,
			 RestrictInfo cinfo,/* clause to pull up */
			 int whichchild,	/* whether child is INNER or OUTER of join */
			 int clausetype)	/* whether clause to pull is join or local */
{
	Path		newkid;
	RelOptInfo	newrel;
	Cost		pulled_selec;
	Cost		cost;
	RestrictInfo newinfo;

	/* remove clause from childpath */
	newkid = (Path) copyObject((Node) childpath);
	if (clausetype == XFUNC_LOCPRD)
	{
		set_locrestrictinfo(newkid,
							xfunc_LispRemove((LispValue) cinfo,
								   (List) get_loc_restrictinfo(newkid)));
	}
	else
	{
		set_pathrestrictinfo
			((JoinPath) newkid,
			 xfunc_LispRemove((LispValue) cinfo,
						(List) get_pathrestrictinfo((JoinPath) newkid)));
	}

	/*
	 * * give the new child path its own RelOptInfo node that reflects the *
	 * lack of the pulled-up predicate
	 */
	pulled_selec = compute_clause_selec(queryInfo,
										get_clause(cinfo), LispNil);
	xfunc_copyrel(get_parent(newkid), &newrel);
	set_parent(newkid, newrel);
	set_pathlist(newrel, lcons(newkid, NIL));
	set_unorderedpath(newrel, (PathPtr) newkid);
	set_cheapestpath(newrel, (PathPtr) newkid);
	set_size(newrel,
		(Count) ((Cost) get_size(get_parent(childpath)) / pulled_selec));

	/*
	 * * fix up path cost of newkid.  To do this we subtract away all the *
	 * xfunc_costs of childpath, then recompute the xfunc_costs of newkid
	 */
	cost = get_path_cost(newkid) - xfunc_get_path_cost(childpath);
	Assert(cost >= 0);
	set_path_cost(newkid, cost);
	cost = get_path_cost(newkid) + xfunc_get_path_cost(newkid);
	set_path_cost(newkid, cost);

	/*
	 * * We copy the cinfo, since it may appear in other plans, and we're
	 * going * to munge it.  -- JMH, 7/22/92
	 */
	newinfo = (RestrictInfo) copyObject((Node) cinfo);

	/*
	 * * Fix all vars in the clause * to point to the right varno and
	 * varattno in parentpath
	 */
	xfunc_fixvars(get_clause(newinfo), newrel, whichchild);

	/* add clause to parentpath, and fix up its cost. */
	set_locrestrictinfo(parentpath,
						lispCons((LispValue) newinfo,
						  (LispValue) get_loc_restrictinfo(parentpath)));
	/* put new childpath into the path tree */
	if (whichchild == INNER)
		set_innerjoinpath(parentpath, (pathPtr) newkid);
	else
		set_outerjoinpath(parentpath, (pathPtr) newkid);

	/*
	 * * recompute parentpath cost from scratch -- the cost * of the join
	 * method has changed
	 */
	cost = xfunc_total_path_cost(parentpath);
	set_path_cost(parentpath, cost);

	return newinfo;
}

/*
 ** calculate (selectivity-1)/cost.
 */
Cost
xfunc_rank(Query *queryInfo, LispValue clause)
{
	Cost		selec = compute_clause_selec(queryInfo, clause, LispNil);
	Cost		cost = xfunc_expense(queryInfo, clause);

	if (cost == 0)
		if (selec > 1)
			return MAXFLOAT;
		else
			return -(MAXFLOAT);
	return (selec - 1) / cost;
}

/*
 ** Find the "global" expense of a clause; i.e. the local expense divided
 ** by the cardinalities of all the base relations of the query that are *not*
 ** referenced in the clause.
 */
Cost
xfunc_expense(Query *queryInfo, clause)
LispValue	clause;
{
	Cost		cost = xfunc_local_expense(clause);

	if (cost)
	{
		Count		card = xfunc_card_unreferenced(queryInfo, clause, LispNil);

		if (card)
			cost /= card;
	}

	return cost;
}

/*
 ** xfunc_join_expense
 **    Find global expense of a join clause
 */
Cost
xfunc_join_expense(Query *queryInfo, JoinPath path, int whichchild)
{
	LispValue	primjoinclause = xfunc_primary_join(path);

	/*
	 * * the second argument to xfunc_card_unreferenced reflects all the *
	 * relations involved in the join clause, i.e. all the relids in the
	 * RelOptInfo * of the join clause
	 */
	Count		card = 0;
	Cost		cost = xfunc_expense_per_tuple(path, whichchild);

	card = xfunc_card_unreferenced(queryInfo,
								   primjoinclause,
								   get_relids(get_parent(path)));
	if (primjoinclause)
		cost += xfunc_local_expense(primjoinclause);

	if (card)
		cost /= card;

	return cost;
}

/*
 ** Recursively find the per-tuple expense of a clause.  See
 ** xfunc_func_expense for more discussion.
 */
Cost
xfunc_local_expense(LispValue clause)
{
	Cost		cost = 0;		/* running expense */
	LispValue	tmpclause;

	/* First handle the base case */
	if (IsA(clause, Const) ||IsA(clause, Var) ||IsA(clause, Param))
		return 0;
	/* now other stuff */
	else if (IsA(clause, Iter))
		/* Too low. Should multiply by the expected number of iterations. */
		return xfunc_local_expense(get_iterexpr((Iter) clause));
	else if (IsA(clause, ArrayRef))
		return xfunc_local_expense(get_refexpr((ArrayRef) clause));
	else if (fast_is_clause(clause))
		return (xfunc_func_expense((LispValue) get_op(clause),
								   (LispValue) get_opargs(clause)));
	else if (fast_is_funcclause(clause))
		return (xfunc_func_expense((LispValue) get_function(clause),
								   (LispValue) get_funcargs(clause)));
	else if (fast_not_clause(clause))
		return xfunc_local_expense(lsecond(clause));
	else if (fast_or_clause(clause) || fast_and_clause(clause))
	{
		/* find cost of evaluating each disjunct */
		for (tmpclause = lnext(clause); tmpclause != LispNil;
			 tmpclause = lnext(tmpclause))
			cost += xfunc_local_expense(lfirst(tmpclause));
		return cost;
	}
	else
	{
		elog(ERROR, "Clause node of undetermined type");
		return -1;
	}
}

/*
 ** xfunc_func_expense
 **    given a Func or Oper and its args, find its expense.
 ** Note: in Stonebraker's SIGMOD '91 paper, he uses a more complicated metric
 ** than the one here.	We can ignore the expected number of tuples for
 ** our calculations; we just need the per-tuple expense.  But he also
 ** proposes components to take into account the costs of accessing disk and
 ** archive.  We didn't adopt that scheme here; eventually the vacuum
 ** cleaner should be able to tell us what percentage of bytes to find on
 ** which storage level, and that should be multiplied in appropriately
 ** in the cost function below.  Right now we don't model the cost of
 ** accessing secondary or tertiary storage, since we don't have sufficient
 ** stats to do it right.
 */
Cost
xfunc_func_expense(LispValue node, LispValue args)
{
	HeapTuple	tupl;			/* the pg_proc tuple for each function */
	Form_pg_proc proc;			/* a data structure to hold the pg_proc
								 * tuple */
	int			width = 0;		/* byte width of the field referenced by
								 * each clause */
	RegProcedure funcid;		/* ID of function associate with node */
	Cost		cost = 0;		/* running expense */
	LispValue	tmpclause;
	LispValue	operand;		/* one operand of an operator */

	if (IsA(node, Oper))
	{
		/* don't trust the opid in the Oper node.  Use the opno. */
		if (!(funcid = get_opcode(get_opno((Oper) node))))
			elog(ERROR, "Oper's function is undefined");
	}
	else
		funcid = get_funcid((Func) node);

	/* look up tuple in cache */