xfunc.c

/*-------------------------------------------------------------------------
 *
 * 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: /cvsroot/pgsql/src/backend/optimizer/path/Attic/xfunc.c,v 1.17 1998/08/04 16:44:11 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/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, Relid 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 */
	CInfo		maxcinfo;		/* The CInfo 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 pathclauseinfo.  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,
				 CInfo *maxcinfopt)		/* Out: pointer to clause to
										 * pullup */
{
	LispValue	clauselist,
				tmplist;		/* lists of clauses */
	CInfo		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_locclauseinfo(childpath);

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

			if ((tmprank = xfunc_rank(get_clause((CInfo) lfirst(tmplist))))
				> maxrank)
			{
				maxcinfo = (CInfo) 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_pathclauseinfo((JoinPath) childpath);
			 tmplist != LispNil;
			 tmplist = lnext(tmplist))
		{

			if (tmplist != LispNil &&
			  (tmprank = xfunc_rank(get_clause((CInfo) lfirst(tmplist))))
				> maxrank)
			{
				maxcinfo = (CInfo) 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, JoinPath)
				  &&!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 CInfo. -- JMH, 11/18/92
 */
CInfo
xfunc_pullup(Query *queryInfo,
			 Path childpath,
			 JoinPath parentpath,
			 CInfo 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;
	CInfo		newinfo;

	/* remove clause from childpath */
	newkid = (Path) copyObject((Node) childpath);
	if (clausetype == XFUNC_LOCPRD)
	{
		set_locclauseinfo(newkid,
						  xfunc_LispRemove((LispValue) cinfo,
									  (List) get_locclauseinfo(newkid)));
	}
	else
	{
		set_pathclauseinfo
			((JoinPath) newkid,
			 xfunc_LispRemove((LispValue) cinfo,
						  (List) get_pathclauseinfo((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 = (CInfo) 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_locclauseinfo(parentpath,
					  lispCons((LispValue) newinfo,
							 (LispValue) get_locclauseinfo(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 */
	tupl = SearchSysCacheTuple(PROOID, ObjectIdGetDatum(funcid), 0, 0, 0);
	if (!HeapTupleIsValid(tupl))
		elog(ERROR, "Cache lookup failed for procedure %d", funcid);
	proc = (Form_pg_proc) GETSTRUCT(tupl);

	/*
	 * * if it's a Postquel function, its cost is stored in the *
	 * associated plan.
	 */
	if (proc->prolang == SQLlanguageId)
	{
		LispValue	tmpplan;
		List		planlist;

		if (IsA(node, Oper) ||get_func_planlist((Func) node) == LispNil)
		{
			Oid		   *argOidVect;		/* vector of argtypes */
			char	   *pq_src; /* text of PQ function */
			int			nargs;	/* num args to PQ function */
			QueryTreeList *queryTree_list;		/* dummy variable */

			/*
			 * * plan the function, storing it in the Func node for later *
			 * use by the executor.
			 */
			pq_src = (char *) textout(&(proc->prosrc));
			nargs = proc->pronargs;
			if (nargs > 0)
				argOidVect = proc->proargtypes;
			planlist = (List) pg_parse_and_plan(pq_src, argOidVect, nargs,
												&parseTree_list, None);
			if (IsA(node, Func))
				set_func_planlist((Func) node, planlist);

		}
		else
		{						/* plan has been cached inside the Func
								 * node already */
			planlist = get_func_planlist((Func) node);
		}

		/*
		 * * Return the sum of the costs of the plans (the PQ function *
		 * may have many queries in its body).
		 */
		foreach(tmpplan, planlist)
			cost += get_cost((Plan) lfirst(tmpplan));
		return (cost);
	}
	else
	{							/* it's a C function */

		/*
		 * *  find the cost of evaluating the function's arguments *  and
		 * the width of the operands
		 */
		for (tmpclause = args; tmpclause != LispNil;
			 tmpclause = lnext(tmpclause))
		{

			if ((operand = lfirst(tmpclause)) != LispNil)
			{
				cost += xfunc_local_expense(operand);
				width += xfunc_width(operand);
			}
		}

		/*
		 * * when stats become available, add in cost of accessing
		 * secondary * and tertiary storage here.
		 */
		return (cost +
				(Cost) proc->propercall_cpu +
		(Cost) proc->properbyte_cpu * (Cost) proc->probyte_pct / 100.00 *
				(Cost) width

		/*
		 * Pct_of_obj_in_mem DISK_COST * proc->probyte_pct/100.00 * width
		 * Pct_of_obj_on_disk + ARCH_COST * proc->probyte_pct/100.00 *
		 * width Pct_of_obj_on_arch
		 */
			);
	}
}

/*
 ** xfunc_width --
 **    recursively find the width of a expression
 */

int
xfunc_width(LispValue clause)
{
	Relation	rd;				/* Relation Descriptor */
	HeapTuple	tupl;			/* structure to hold a cached tuple */
	TypeTupleForm type;			/* structure to hold a type tuple */
	int			retval = 0;

	if (IsA(clause, Const))
	{
		/* base case: width is the width of this constant */
		retval = get_constlen((Const) clause);
		goto exit;
	}
	else if (IsA(clause, ArrayRef))
	{
		/* base case: width is width of the refelem within the array */
		retval = get_refelemlength((ArrayRef) clause);
		goto exit;
	}
	else if (IsA(clause, Var))
	{
		/* base case: width is width of this attribute */
		tupl = SearchSysCacheTuple(TYPOID,
							  PointerGetDatum(get_vartype((Var) clause)),
								   0, 0, 0);
		if (!HeapTupleIsValid(tupl))
			elog(ERROR, "Cache lookup failed for type %d",
				 get_vartype((Var) clause));
		type = (TypeTupleForm) GETSTRUCT(tupl);
		if (get_varattno((Var) clause) == 0)
		{
			/* clause is a tuple.  Get its width */
			rd = heap_open(type->typrelid);
			retval = xfunc_tuple_width(rd);
			heap_close(rd);
		}
		else
		{
			/* attribute is a base type */
			retval = type->typlen;
		}
		goto exit;
	}
	else if (IsA(clause, Param))
	{
		if (typeidTypeRelid(get_paramtype((Param) clause)))
		{
			/* Param node returns a tuple.	Find its width */
			rd = heap_open(typeidTypeRelid(get_paramtype((Param) clause)));
			retval = xfunc_tuple_width(rd);
			heap_close(rd);
		}
		else if (get_param_tlist((Param) clause) != LispNil)
		{
			/* Param node projects a complex type */
			Assert(length(get_param_tlist((Param) clause)) == 1);		/* sanity */
			retval =
				xfunc_width((LispValue)
					  get_expr(lfirst(get_param_tlist((Param) clause))));
		}
		else
		{
			/* Param node returns a base type */
			retval = typeLen(typeidType(get_paramtype((Param) clause)));
		}
		goto exit;
	}
	else if (IsA(clause, Iter))
	{

		/*
		 * * An Iter returns a setof things, so return the width of a
		 * single * thing. * Note:	THIS MAY NOT WORK RIGHT WHEN AGGS GET
		 * FIXED, * SINCE AGG FUNCTIONS CHEW ON THE WHOLE SETOF THINGS!!!! *
		 * This whole Iter business is bogus, anyway.
		 */
		retval = xfunc_width(get_iterexpr((Iter) clause));
		goto exit;
	}
	else if (fast_is_clause(clause))
	{

		/*
		 * * get function associated with this Oper, and treat this as * a
		 * Func
		 */
		tupl = SearchSysCacheTuple(OPROID,
					   ObjectIdGetDatum(get_opno((Oper) get_op(clause))),
								   0, 0, 0);
		if (!HeapTupleIsValid(tupl))
			elog(ERROR, "Cache lookup failed for procedure %d",
				 get_opno((Oper) get_op(clause)));
		return (xfunc_func_width
				((RegProcedure) (((OperatorTupleForm) (GETSTRUCT(tupl)))->oprcode),
				 (LispValue) get_opargs(clause)));
	}
	else if (fast_is_funcclause(clause))
	{
		Func		func = (Func) get_function(clause);

		if (get_func_tlist(func) != LispNil)
		{

			/*
			 * this function has a projection on it.  Get the length of
			 * the projected attribute
			 */
			Assert(length(get_func_tlist(func)) == 1);	/* sanity */
			retval =
				xfunc_width((LispValue)
							get_expr(lfirst(get_func_tlist(func))));
			goto exit;
		}
		else
		{
			return (xfunc_func_width((RegProcedure) get_funcid(func),
									 (LispValue) get_funcargs(clause)));
		}
	}
	else
	{
		elog(ERROR, "Clause node of undetermined type");
		return (-1);
	}

exit:
	if (retval == -1)
		retval = VARLEN_DEFAULT;
	return (retval);
}

/*
 ** xfunc_card_unreferenced:
 **   find all relations not referenced in clause, and multiply their
 ** cardinalities.	Ignore relation of cardinality 0.
 ** User may pass in referenced list, if they know it (useful
 ** for joins).
 */
static Count
xfunc_card_unreferenced(Query *queryInfo,
						LispValue clause, Relid referenced)
{
	Relid		unreferenced,
				allrelids = LispNil;
	LispValue	temp;

	/* find all relids of base relations referenced in query */
	foreach(temp, queryInfo->base_relation_list_)
	{
		Assert(lnext(get_relids((RelOptInfo) lfirst(temp))) == LispNil);
		allrelids = lappend(allrelids,
							lfirst(get_relids((RelOptInfo) lfirst(temp))));
	}

	/* find all relids referenced in query but not in clause */
	if (!referenced)
		referenced = xfunc_find_references(clause);
	unreferenced = set_difference(allrelids, referenced);

	return (xfunc_card_product(unreferenced));
}

/*
 ** xfunc_card_product
 **   multiple together cardinalities of a list relations.
 */
Count
xfunc_card_product(Query *queryInfo, Relid relids)
{
	LispValue	cinfonode;
	LispValue	temp;
	RelOptInfo			currel;
	Cost		tuples;
	Count		retval = 0;

	foreach(temp, relids)
	{
		currel = get_rel(lfirst(temp));
		tuples = get_tuples(currel);

		if (tuples)
		{						/* not of cardinality 0 */
			/* factor in the selectivity of all zero-cost clauses */
			foreach(cinfonode, get_clauseinfo(currel))
			{
				if (!xfunc_expense(queryInfo, get_clause((CInfo) lfirst(cinfonode))))
					tuples *=
						compute_clause_selec(queryInfo,
								   get_clause((CInfo) lfirst(cinfonode)),
											 LispNil);
			}

			if (retval == 0)
				retval = tuples;
			else
				retval *= tuples;
		}
	}
	if (retval == 0)
		retval = 1;				/* saves caller from dividing by zero */
	return (retval);
}


/*
 ** xfunc_find_references:
 **   Traverse a clause and find all relids referenced in the clause.
 */
List
xfunc_find_references(LispValue clause)
{
	List		retval = (List) LispNil;
	LispValue	tmpclause;

	/* Base cases */
	if (IsA(clause, Var))
		return (lispCons(lfirst(get_varid((Var) clause)), LispNil));
	else if (IsA(clause, Const) ||IsA(clause, Param))
		return ((List) LispNil);

	/* recursion */
	else if (IsA(clause, Iter))

		/*
		 * Too low. Should multiply by the expected number of iterations.
		 * maybe
		 */
		return (xfunc_find_references(get_iterexpr((Iter) clause)));
	else if (IsA(clause, ArrayRef))
		return (xfunc_find_references(get_refexpr((ArrayRef) clause)));
	else if (fast_is_clause(clause))
	{
		/* string together result of all operands of Oper */
		for (tmpclause = (LispValue) get_opargs(clause); tmpclause != LispNil;
			 tmpclause = lnext(tmpclause))
			retval = nconc(retval, xfunc_find_references(lfirst(tmpclause)));
		return (retval);
	}
	else if (fast_is_funcclause(clause))
	{
		/* string together result of all args of Func */
		for (tmpclause = (LispValue) get_funcargs(clause);
			 tmpclause != LispNil;
			 tmpclause = lnext(tmpclause))
			retval = nconc(retval, xfunc_find_references(lfirst(tmpclause)));
		return (retval);
	}
	else if (fast_not_clause(clause))
		return (xfunc_find_references(lsecond(clause)));
	else if (fast_or_clause(clause) || fast_and_clause(clause))
	{
		/* string together result of all operands of OR */
		for (tmpclause = lnext(clause); tmpclause != LispNil;
			 tmpclause = lnext(tmpclause))
			retval = nconc(retval, xfunc_find_references(lfirst(tmpclause)));
		return (retval);
	}
	else
	{
		elog(ERROR, "Clause node of undetermined type");
		return ((List) LispNil);
	}
}

/*
 ** xfunc_primary_join:
 **   Find the primary join clause: for Hash and Merge Joins, this is the
 ** min rank Hash or Merge clause, while for Nested Loop it's the
 ** min rank pathclause
 */
LispValue
xfunc_primary_join(JoinPath pathnode)
{
	LispValue	joinclauselist = get_pathclauseinfo(pathnode);
	CInfo		mincinfo;
	LispValue	tmplist;
	LispValue	minclause = LispNil;
	Cost		minrank,
				tmprank;

	if (IsA(pathnode, MergePath))
	{
		for (tmplist = get_path_mergeclauses((MergePath) pathnode),
			 minclause = lfirst(tmplist),
			 minrank = xfunc_rank(minclause);
			 tmplist != LispNil;
			 tmplist = lnext(tmplist))
			if ((tmprank = xfunc_rank(lfirst(tmplist)))
				< minrank)
			{
				minrank = tmprank;
				minclause = lfirst(tmplist);
			}
		return (minclause);
	}
	else if (IsA(pathnode, HashPath))
	{
		for (tmplist = get_path_hashclauses((HashPath) pathnode),
			 minclause = lfirst(tmplist),
			 minrank = xfunc_rank(minclause);
			 tmplist != LispNil;
			 tmplist = lnext(tmplist))
			if ((tmprank = xfunc_rank(lfirst(tmplist)))
				< minrank)
			{
				minrank = tmprank;
				minclause = lfirst(tmplist);
			}
		return (minclause);
	}

	/* if we drop through, it's nested loop join */
	if (joinclauselist == LispNil)
		return (LispNil);

	for (tmplist = joinclauselist, mincinfo = (CInfo) lfirst(joinclauselist),
		 minrank = xfunc_rank(get_clause((CInfo) lfirst(tmplist)));
		 tmplist != LispNil;
		 tmplist = lnext(tmplist))
		if ((tmprank = xfunc_rank(get_clause((CInfo) lfirst(tmplist))))
			< minrank)
		{
			minrank = tmprank;
			mincinfo = (CInfo) lfirst(tmplist);
		}
	return ((LispValue) get_clause(mincinfo));
}

/*
 ** xfunc_get_path_cost
 **   get the expensive function costs of the path
 */
Cost
xfunc_get_path_cost(Query *queryInfo, Path pathnode)
{
	Cost		cost = 0;
	LispValue	tmplist;
	Cost		selec = 1.0;

	/*
	 * * first add in the expensive local function costs. * We ensure that
	 * the clauses are sorted by rank, so that we * know (via
	 * selectivities) the number of tuples that will be checked * by each
	 * function.  If we're not doing any optimization of expensive *
	 * functions, we don't sort.
	 */
	if (XfuncMode != XFUNC_OFF)
		set_locclauseinfo(pathnode, lisp_qsort(get_locclauseinfo(pathnode),
											   xfunc_cinfo_compare));
	for (tmplist = get_locclauseinfo(pathnode), selec = 1.0;
		 tmplist != LispNil;
		 tmplist = lnext(tmplist))
	{
		cost += (Cost) (xfunc_local_expense(get_clause((CInfo) lfirst(tmplist)))
					  * (Cost) get_tuples(get_parent(pathnode)) * selec);
		selec *= compute_clause_selec(queryInfo,
									  get_clause((CInfo) lfirst(tmplist)),
									  LispNil);
	}

	/*
	 * * Now add in any node-specific expensive function costs. * Again,
	 * we must ensure that the clauses are sorted by rank.
	 */
	if (IsA(pathnode, JoinPath))
	{
		if (XfuncMode != XFUNC_OFF)
			set_pathclauseinfo((JoinPath) pathnode, lisp_qsort
							   (get_pathclauseinfo((JoinPath) pathnode),
								xfunc_cinfo_compare));
		for (tmplist = get_pathclauseinfo((JoinPath) pathnode), selec = 1.0;
			 tmplist != LispNil;
			 tmplist = lnext(tmplist))
		{
			cost += (Cost) (xfunc_local_expense(get_clause((CInfo) lfirst(tmplist)))
					  * (Cost) get_tuples(get_parent(pathnode)) * selec);
			selec *= compute_clause_selec(queryInfo,
									 get_clause((CInfo) lfirst(tmplist)),
										  LispNil);
		}
	}
	if (IsA(pathnode, HashPath))
	{
		if (XfuncMode != XFUNC_OFF)
			set_path_hashclauses
				((HashPath) pathnode,
				 lisp_qsort(get_path_hashclauses((HashPath) pathnode),
							xfunc_clause_compare));
		for (tmplist = get_path_hashclauses((HashPath) pathnode), selec = 1.0;
			 tmplist != LispNil;
			 tmplist = lnext(tmplist))
		{
			cost += (Cost) (xfunc_local_expense(lfirst(tmplist))
					  * (Cost) get_tuples(get_parent(pathnode)) * selec);
			selec *= compute_clause_selec(queryInfo,
										  lfirst(tmplist), LispNil);
		}
	}
	if (IsA(pathnode, MergePath))
	{
		if (XfuncMode != XFUNC_OFF)
			set_path_mergeclauses
				((MergePath) pathnode,
				 lisp_qsort(get_path_mergeclauses((MergePath) pathnode),
							xfunc_clause_compare));
		for (tmplist = get_path_mergeclauses((MergePath) pathnode), selec = 1.0;
			 tmplist != LispNil;
			 tmplist = lnext(tmplist))
		{
			cost += (Cost) (xfunc_local_expense(lfirst(tmplist))
					  * (Cost) get_tuples(get_parent(pathnode)) * selec);
			selec *= compute_clause_selec(queryInfo,
										  lfirst(tmplist), LispNil);
		}
	}
	Assert(cost >= 0);
	return (cost);
}

/*
 ** Recalculate the cost of a path node.  This includes the basic cost of the
 ** node, as well as the cost of its expensive functions.
 ** We need to do this to the parent after pulling a clause from a child into a
 ** parent.  Thus we should only be calling this function on JoinPaths.
 */
Cost
xfunc_total_path_cost(JoinPath pathnode)
{
	Cost		cost = xfunc_get_path_cost((Path) pathnode);

	Assert(IsA(pathnode, JoinPath));
	if (IsA(pathnode, MergePath))
	{
		MergePath	mrgnode = (MergePath) pathnode;

		cost += cost_mergejoin(get_path_cost((Path) get_outerjoinpath(mrgnode)),
						get_path_cost((Path) get_innerjoinpath(mrgnode)),
							   get_outersortkeys(mrgnode),
							   get_innersortkeys(mrgnode),
						   get_tuples(get_parent((Path) get_outerjoinpath
												 (mrgnode))),
						   get_tuples(get_parent((Path) get_innerjoinpath
												 (mrgnode))),
							get_width(get_parent((Path) get_outerjoinpath
												 (mrgnode))),
							get_width(get_parent((Path) get_innerjoinpath
												 (mrgnode))));
		Assert(cost >= 0);
		return (cost);
	}
	else if (IsA(pathnode, HashPath))
	{
		HashPath hashnode = (HashPath) pathnode;

		cost += cost_hashjoin(get_path_cost((Path) get_outerjoinpath(hashnode)),
					   get_path_cost((Path) get_innerjoinpath(hashnode)),
							  get_outerhashkeys(hashnode),
							  get_innerhashkeys(hashnode),
						   get_tuples(get_parent((Path) get_outerjoinpath
												 (hashnode))),
						   get_tuples(get_parent((Path) get_innerjoinpath
												 (hashnode))),
							get_width(get_parent((Path) get_outerjoinpath
												 (hashnode))),
							get_width(get_parent((Path) get_innerjoinpath
												 (hashnode))));
		Assert(cost >= 0);
		return (cost);
	}
	else
/* Nested Loop Join */
	{
		cost += cost_nestloop(get_path_cost((Path) get_outerjoinpath(pathnode)),
					   get_path_cost((Path) get_innerjoinpath(pathnode)),
						   get_tuples(get_parent((Path) get_outerjoinpath
												 (pathnode))),
						   get_tuples(get_parent((Path) get_innerjoinpath
												 (pathnode))),
							get_pages(get_parent((Path) get_outerjoinpath
												 (pathnode))),
							IsA(get_innerjoinpath(pathnode), IndexPath));
		Assert(cost >= 0);
		return (cost);
	}
}


/*
 ** xfunc_expense_per_tuple --
 **    return the expense of the join *per-tuple* of the input relation.
 ** The cost model here is that a join costs
 **		k*card(outer)*card(inner) + l*card(outer) + m*card(inner) + n
 **
 ** We treat the l and m terms by considering them to be like restrictions
 ** constrained to be right under the join.  Thus the cost per inner and
 ** cost per outer of the join is different, reflecting these virtual nodes.
 **
 ** The cost per tuple of outer is k + l/referenced(inner).  Cost per tuple
 ** of inner is k + m/referenced(outer).
 ** The constants k, l, m and n depend on the join method.	Measures here are
 ** based on the costs in costsize.c, with fudging for HashJoin and Sorts to
 ** make it fit our model (the 'q' in HashJoin results in a
 ** card(outer)/card(inner) term, and sorting results in a log term.

 */
Cost
xfunc_expense_per_tuple(JoinPath joinnode, int whichchild)
{
	RelOptInfo			outerrel = get_parent((Path) get_outerjoinpath(joinnode));
	RelOptInfo			innerrel = get_parent((Path) get_innerjoinpath(joinnode));
	Count		outerwidth = get_width(outerrel);
	Count		outers_per_page = ceil(BLCKSZ / (outerwidth + sizeof(HeapTupleData)));

	if (IsA(joinnode, HashPath))
	{
		if (whichchild == INNER)
			return ((1 + _CPU_PAGE_WEIGHT_) * outers_per_page / NBuffers);
		else
			return (((1 + _CPU_PAGE_WEIGHT_) * outers_per_page / NBuffers)
					+ _CPU_PAGE_WEIGHT_
					/ xfunc_card_product(get_relids(innerrel)));
	}
	else if (IsA(joinnode, MergePath))
	{
		/* assumes sort exists, and costs one (I/O + CPU) per tuple */
		if (whichchild == INNER)
			return ((2 * _CPU_PAGE_WEIGHT_ + 1)
					/ xfunc_card_product(get_relids(outerrel)));
		else
			return ((2 * _CPU_PAGE_WEIGHT_ + 1)
					/ xfunc_card_product(get_relids(innerrel)));
	}
	else
/* nestloop */
	{
		Assert(IsA(joinnode, JoinPath));
		return (_CPU_PAGE_WEIGHT_);
	}
}

/*
 ** xfunc_fixvars --
 ** After pulling up a clause, we must walk its expression tree, fixing Var
 ** nodes to point to the correct varno (either INNER or OUTER, depending
 ** on which child the clause was pulled from), and the right varattno in the
 ** target list of the child's former relation.  If the target list of the
 ** child RelOptInfo does not contain the attribute we need, we add it.
 */
void
xfunc_fixvars(LispValue clause, /* clause being pulled up */
			  RelOptInfo rel,			/* rel it's being pulled from */
			  int varno)		/* whether rel is INNER or OUTER of join */
{
	LispValue	tmpclause;		/* temporary variable */
	TargetEntry *tle;			/* tlist member corresponding to var */


	if (IsA(clause, Const) ||IsA(clause, Param))
		return;
	else if (IsA(clause, Var))
	{
		/* here's the meat */
		tle = tlistentry_member((Var) clause, get_targetlist(rel));
		if (tle == LispNil)
		{

			/*
			 * * The attribute we need is not in the target list, * so we
			 * have to add it. *
			 *
			 */
			add_tl_element(rel, (Var) clause);
			tle = tlistentry_member((Var) clause, get_targetlist(rel));
		}
		set_varno(((Var) clause), varno);
		set_varattno(((Var) clause), get_resno(get_resdom(get_entry(tle))));
	}
	else if (IsA(clause, Iter))
		xfunc_fixvars(get_iterexpr((Iter) clause), rel, varno);
	else if (fast_is_clause(clause))
	{
		xfunc_fixvars(lfirst(lnext(clause)), rel, varno);
		xfunc_fixvars(lfirst(lnext(lnext(clause))), rel, varno);
	}
	else if (fast_is_funcclause(clause))
		for (tmpclause = lnext(clause); tmpclause != LispNil;
			 tmpclause = lnext(tmpclause))
			xfunc_fixvars(lfirst(tmpclause), rel, varno);
	else if (fast_not_clause(clause))
		xfunc_fixvars(lsecond(clause), rel, varno);
	else if (fast_or_clause(clause) || fast_and_clause(clause))
		for (tmpclause = lnext(clause); tmpclause != LispNil;
			 tmpclause = lnext(tmpclause))
			xfunc_fixvars(lfirst(tmpclause), rel, varno);
	else
		elog(ERROR, "Clause node of undetermined type");
}


/*
 ** Comparison function for lisp_qsort() on a list of CInfo's.
 ** arg1 and arg2 should really be of type (CInfo *).
 */
int
xfunc_cinfo_compare(void *arg1, void *arg2)
{
	CInfo		info1 = *(CInfo *) arg1;
	CInfo		info2 = *(CInfo *) arg2;

	LispValue	clause1 = (LispValue) get_clause(info1),
				clause2 = (LispValue) get_clause(info2);

	return (xfunc_clause_compare((void *) &clause1, (void *) &clause2));
}

/*
 ** xfunc_clause_compare: comparison function for lisp_qsort() that compares two
 ** clauses based on expense/(1 - selectivity)
 ** arg1 and arg2 are really pointers to clauses.
 */
int
xfunc_clause_compare(void *arg1, void *arg2)
{
	LispValue	clause1 = *(LispValue *) arg1;
	LispValue	clause2 = *(LispValue *) arg2;
	Cost		rank1,			/* total xfunc rank of clause1 */
				rank2;			/* total xfunc rank of clause2 */

	rank1 = xfunc_rank(clause1);
	rank2 = xfunc_rank(clause2);

	if (rank1 < rank2)
		return (-1);
	else if (rank1 == rank2)
		return (0);
	else
		return (1);
}

/*
 ** xfunc_disjunct_sort --
 **   given a list of clauses, for each clause sort the disjuncts by cost
 **   (this assumes the predicates have been converted to Conjunctive NF)
 **   Modifies the clause list!
 */
void
xfunc_disjunct_sort(LispValue clause_list)
{
	LispValue	temp;

	foreach(temp, clause_list)
		if (or_clause(lfirst(temp)))
		lnext(lfirst(temp)) =
			lisp_qsort(lnext(lfirst(temp)), xfunc_disjunct_compare);
}


/*
 ** xfunc_disjunct_compare: comparison function for qsort() that compares two
 ** disjuncts based on cost/selec.
 ** arg1 and arg2 are really pointers to disjuncts
 */
int
xfunc_disjunct_compare(Query *queryInfo, void *arg1, void *arg2)
{
	LispValue	disjunct1 = *(LispValue *) arg1;
	LispValue	disjunct2 = *(LispValue *) arg2;
	Cost		cost1,			/* total cost of disjunct1 */
				cost2,			/* total cost of disjunct2 */
				selec1,
				selec2;
	Cost		rank1,
				rank2;

	cost1 = xfunc_expense(queryInfo, disjunct1);
	cost2 = xfunc_expense(queryInfo, disjunct2);
	selec1 = compute_clause_selec(queryInfo,
								  disjunct1, LispNil);
	selec2 = compute_clause_selec(queryInfo,
								  disjunct2, LispNil);

	if (selec1 == 0)
		rank1 = MAXFLOAT;
	else if (cost1 == 0)
		rank1 = 0;
	else
		rank1 = cost1 / selec1;

	if (selec2 == 0)
		rank2 = MAXFLOAT;
	else if (cost2 == 0)
		rank2 = 0;
	else
		rank2 = cost2 / selec2;

	if (rank1 < rank2)
		return (-1);
	else if (rank1 == rank2)
		return (0);
	else
		return (1);
}

/* ------------------------ UTILITY FUNCTIONS ------------------------------- */
/*
 ** xfunc_func_width --
 **    Given a function OID and operands, find the width of the return value.
 */
int
xfunc_func_width(RegProcedure funcid, LispValue args)
{
	Relation	rd;				/* Relation Descriptor */
	HeapTuple	tupl;			/* structure to hold a cached tuple */
	Form_pg_proc proc;			/* structure to hold the pg_proc tuple */
	TypeTupleForm type;			/* structure to hold the pg_type tuple */
	LispValue	tmpclause;
	int			retval;

	/* lookup function and find its return type */
	Assert(RegProcedureIsValid(funcid));
	tupl = SearchSysCacheTuple(PROOID, ObjectIdGetDatum(funcid), 0, 0, 0);
	if (!HeapTupleIsValid(tupl))
		elog(ERROR, "Cache lookup failed for procedure %d", funcid);
	proc = (Form_pg_proc) GETSTRUCT(tupl);

	/* if function returns a tuple, get the width of that */
	if (typeidTypeRelid(proc->prorettype))
	{
		rd = heap_open(typeidTypeRelid(proc->prorettype));
		retval = xfunc_tuple_width(rd);
		heap_close(rd);
		goto exit;
	}
	else
/* function returns a base type */
	{
		tupl = SearchSysCacheTuple(TYPOID,
								   ObjectIdGetDatum(proc->prorettype),
								   0, 0, 0);
		if (!HeapTupleIsValid(tupl))
			elog(ERROR, "Cache lookup failed for type %d", proc->prorettype);
		type = (TypeTupleForm) GETSTRUCT(tupl);
		/* if the type length is known, return that */
		if (type->typlen != -1)
		{
			retval = type->typlen;
			goto exit;
		}
		else
/* estimate the return size */
		{
			/* find width of the function's arguments */
			for (tmpclause = args; tmpclause != LispNil;
				 tmpclause = lnext(tmpclause))
				retval += xfunc_width(lfirst(tmpclause));
			/* multiply by outin_ratio */
			retval = (int) (proc->prooutin_ratio / 100.0 * retval);
			goto exit;
		}
	}
exit:
	return (retval);
}

/*
 ** xfunc_tuple_width --
 **		Return the sum of the lengths of all the attributes of a given relation
 */
int
xfunc_tuple_width(Relation rd)
{
	int			i;
	int			retval = 0;
	TupleDesc	tdesc = RelationGetTupleDescriptor(rd);

	for (i = 0; i < tdesc->natts; i++)
	{
		if (tdesc->attrs[i]->attlen != -1)
			retval += tdesc->attrs[i]->attlen;
		else
			retval += VARLEN_DEFAULT;
	}

	return (retval);
}

/*
 ** xfunc_num_join_clauses --
 **   Find the number of join clauses associated with this join path
 */
int
xfunc_num_join_clauses(JoinPath path)
{
	int			num = length(get_pathclauseinfo(path));

	if (IsA(path, MergePath))
		return (num + length(get_path_mergeclauses((MergePath) path)));
	else if (IsA(path, HashPath))
		return (num + length(get_path_hashclauses((HashPath) path)));
	else
		return (num);
}

/*
 ** xfunc_LispRemove --
 **   Just like LispRemove, but it whines if the item to be removed ain't there
 */
LispValue
xfunc_LispRemove(LispValue foo, List bar)
{
	LispValue	temp = LispNil;
	LispValue	result = LispNil;
	int			sanity = false;

	for (temp = bar; !null(temp); temp = lnext(temp))
		if (!equal((Node) (foo), (Node) (lfirst(temp))))
			result = lappend(result, lfirst(temp));
		else
			sanity = true;		/* found a matching item to remove! */

	if (!sanity)
		elog(ERROR, "xfunc_LispRemove: didn't find a match!");

	return (result);
}

#define Node_Copy(a, b, c, d) \
do { \
	if (NodeCopy((Node)((a)->d), (Node*)&((b)->d), c) != true) \
	{ \
		return false; \
	} \
} while(0)

/*
 ** xfunc_copyrel --
 **   Just like _copyRel, but doesn't copy the paths
 */
bool
xfunc_copyrel(RelOptInfo from, RelOptInfo *to)
{
	RelOptInfo			newnode;

	Pointer		(*alloc) () = palloc;

	/* COPY_CHECKARGS() */
	if (to == NULL)
		return false;

	/* COPY_CHECKNULL() */
	if (from == NULL)
	{
		(*to) = NULL;
		return true;
	}

	/* COPY_NEW(c) */
	newnode = (RelOptInfo) (*alloc) (classSize(RelOptInfo));
	if (newnode == NULL)
		return false;

	/* ----------------
	 *	copy node superclass fields
	 * ----------------
	 */
	CopyNodeFields((Node) from, (Node) newnode, alloc);

	/* ----------------
	 *	copy remainder of node
	 * ----------------
	 */
	Node_Copy(from, newnode, alloc, relids);

	newnode->indexed = from->indexed;
	newnode->pages = from->pages;
	newnode->tuples = from->tuples;
	newnode->size = from->size;
	newnode->width = from->width;

	Node_Copy(from, newnode, alloc, targetlist);

	/*
	 * No!!!!	 Node_Copy(from, newnode, alloc, pathlist);
	 * Node_Copy(from, newnode, alloc, unorderedpath); Node_Copy(from,
	 * newnode, alloc, cheapestpath);
	 */
#if 0							/* can't use Node_copy now. 2/95 -ay */
	Node_Copy(from, newnode, alloc, classlist);
	Node_Copy(from, newnode, alloc, indexkeys);
	Node_Copy(from, newnode, alloc, ordering);
#endif
	Node_Copy(from, newnode, alloc, clauseinfo);
	Node_Copy(from, newnode, alloc, joininfo);
	Node_Copy(from, newnode, alloc, innerjoin);
	Node_Copy(from, newnode, alloc, superrels);

	(*to) = newnode;
	return true;
}