costsize.c

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

				thisbucketsize = restrictinfo->left_bucketsize;
				if (thisbucketsize < 0)
				{
					/* not cached yet */
					thisbucketsize =
						estimate_hash_bucketsize(root,
								(Var *) get_leftop(restrictinfo->clause),
												 virtualbuckets);
					restrictinfo->left_bucketsize = thisbucketsize;
				}
			}

			if (innerbucketsize > thisbucketsize)
				innerbucketsize = thisbucketsize;
		}
	}

	/*
	 * if inner relation is too big then we will need to "batch" the join,
	 * which implies writing and reading most of the tuples to disk an
	 * extra time.	Charge one cost unit per page of I/O (correct since it
	 * should be nice and sequential...).  Writing the inner rel counts as
	 * startup cost, all the rest as run cost.
	 */
	if (numbatches)
	{
		double		outerpages = page_size(outer_path_rows,
										   outer_path->parent->width);
		double		innerpages = page_size(inner_path_rows,
										   inner_path->parent->width);

		startup_cost += innerpages;
		run_cost += innerpages + 2 * outerpages;
	}

	/* CPU costs */

	/*
	 * If we're doing JOIN_IN then we will stop comparing inner tuples to
	 * an outer tuple as soon as we have one match.  Account for the
	 * effects of this by scaling down the cost estimates in proportion to
	 * the expected output size.  (This assumes that all the quals
	 * attached to the join are IN quals, which should be true.)
	 */
	if (path->jpath.jointype == JOIN_IN &&
		qptuples > path->jpath.path.parent->rows)
		joininfactor = path->jpath.path.parent->rows / qptuples;
	else
		joininfactor = 1.0;

	/*
	 * The number of tuple comparisons needed is the number of outer
	 * tuples times the typical number of tuples in a hash bucket, which
	 * is the inner relation size times its bucketsize fraction.  At each
	 * one, we need to evaluate the hashjoin quals.
	 */
	startup_cost += hash_qual_cost.startup;
	run_cost += hash_qual_cost.per_tuple *
		outer_path_rows * ceil(inner_path_rows * innerbucketsize) *
		joininfactor;

	/*
	 * For each tuple that gets through the hashjoin proper, we charge
	 * cpu_tuple_cost plus the cost of evaluating additional restriction
	 * clauses that are to be applied at the join.	(This is pessimistic
	 * since not all of the quals may get evaluated at each tuple.)
	 */
	startup_cost += qp_qual_cost.startup;
	cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
	run_cost += cpu_per_tuple * hashjointuples * joininfactor;

	/*
	 * Bias against putting larger relation on inside.	We don't want an
	 * absolute prohibition, though, since larger relation might have
	 * better bucketsize --- and we can't trust the size estimates
	 * unreservedly, anyway.  Instead, inflate the run cost by the square
	 * root of the size ratio.	(Why square root?  No real good reason,
	 * but it seems reasonable...)
	 *
	 * Note: before 7.4 we implemented this by inflating startup cost; but if
	 * there's a disable_cost component in the input paths' startup cost,
	 * that unfairly penalizes the hash.  Probably it'd be better to keep
	 * track of disable penalty separately from cost.
	 */
	if (innerbytes > outerbytes && outerbytes > 0)
		run_cost *= sqrt(innerbytes / outerbytes);

	path->jpath.path.startup_cost = startup_cost;
	path->jpath.path.total_cost = startup_cost + run_cost;
}

/*
 * Estimate hash bucketsize fraction (ie, number of entries in a bucket
 * divided by total tuples in relation) if the specified Var is used
 * as a hash key.
 *
 * XXX This is really pretty bogus since we're effectively assuming that the
 * distribution of hash keys will be the same after applying restriction
 * clauses as it was in the underlying relation.  However, we are not nearly
 * smart enough to figure out how the restrict clauses might change the
 * distribution, so this will have to do for now.
 *
 * We are passed the number of buckets the executor will use for the given
 * input relation.	If the data were perfectly distributed, with the same
 * number of tuples going into each available bucket, then the bucketsize
 * fraction would be 1/nbuckets.  But this happy state of affairs will occur
 * only if (a) there are at least nbuckets distinct data values, and (b)
 * we have a not-too-skewed data distribution.	Otherwise the buckets will
 * be nonuniformly occupied.  If the other relation in the join has a key
 * distribution similar to this one's, then the most-loaded buckets are
 * exactly those that will be probed most often.  Therefore, the "average"
 * bucket size for costing purposes should really be taken as something close
 * to the "worst case" bucket size.  We try to estimate this by adjusting the
 * fraction if there are too few distinct data values, and then scaling up
 * by the ratio of the most common value's frequency to the average frequency.
 *
 * If no statistics are available, use a default estimate of 0.1.  This will
 * discourage use of a hash rather strongly if the inner relation is large,
 * which is what we want.  We do not want to hash unless we know that the
 * inner rel is well-dispersed (or the alternatives seem much worse).
 */
static Selectivity
estimate_hash_bucketsize(Query *root, Var *var, int nbuckets)
{
	Oid			relid;
	RelOptInfo *rel;
	HeapTuple	tuple;
	Form_pg_statistic stats;
	double		estfract,
				ndistinct,
				mcvfreq,
				avgfreq;
	float4	   *numbers;
	int			nnumbers;

	/* Ignore any binary-compatible relabeling */
	if (var && IsA(var, RelabelType))
		var = (Var *) ((RelabelType *) var)->arg;

	/*
	 * Lookup info about var's relation and attribute; if none available,
	 * return default estimate.
	 */
	if (var == NULL || !IsA(var, Var))
		return 0.1;

	relid = getrelid(var->varno, root->rtable);
	if (relid == InvalidOid)
		return 0.1;

	rel = find_base_rel(root, var->varno);

	if (rel->tuples <= 0.0 || rel->rows <= 0.0)
		return 0.1;				/* ensure we can divide below */

	tuple = SearchSysCache(STATRELATT,
						   ObjectIdGetDatum(relid),
						   Int16GetDatum(var->varattno),
						   0, 0);
	if (!HeapTupleIsValid(tuple))
	{
		/*
		 * If the attribute is known unique because of an index,
		 * we can treat it as well-distributed.
		 */
		if (has_unique_index(rel, var->varattno))
			return 1.0 / (double) nbuckets;

		/*
		 * Perhaps the Var is a system attribute; if so, it will have no
		 * entry in pg_statistic, but we may be able to guess something
		 * about its distribution anyway.
		 */
		switch (var->varattno)
		{
			case ObjectIdAttributeNumber:
			case SelfItemPointerAttributeNumber:
				/* these are unique, so buckets should be well-distributed */
				return 1.0 / (double) nbuckets;
			case TableOidAttributeNumber:
				/* hashing this is a terrible idea... */
				return 1.0;
		}
		return 0.1;
	}
	stats = (Form_pg_statistic) GETSTRUCT(tuple);

	/*
	 * Obtain number of distinct data values in raw relation.
	 */
	ndistinct = stats->stadistinct;
	if (ndistinct < 0.0)
		ndistinct = -ndistinct * rel->tuples;

	if (ndistinct <= 0.0)		/* ensure we can divide */
	{
		ReleaseSysCache(tuple);
		return 0.1;
	}

	/* Also compute avg freq of all distinct data values in raw relation */
	avgfreq = (1.0 - stats->stanullfrac) / ndistinct;

	/*
	 * Adjust ndistinct to account for restriction clauses.  Observe we
	 * are assuming that the data distribution is affected uniformly by
	 * the restriction clauses!
	 *
	 * XXX Possibly better way, but much more expensive: multiply by
	 * selectivity of rel's restriction clauses that mention the target
	 * Var.
	 */
	ndistinct *= rel->rows / rel->tuples;

	/*
	 * Initial estimate of bucketsize fraction is 1/nbuckets as long as
	 * the number of buckets is less than the expected number of distinct
	 * values; otherwise it is 1/ndistinct.
	 */
	if (ndistinct > (double) nbuckets)
		estfract = 1.0 / (double) nbuckets;
	else
		estfract = 1.0 / ndistinct;

	/*
	 * Look up the frequency of the most common value, if available.
	 */
	mcvfreq = 0.0;

	if (get_attstatsslot(tuple, var->vartype, var->vartypmod,
						 STATISTIC_KIND_MCV, InvalidOid,
						 NULL, NULL, &numbers, &nnumbers))
	{
		/*
		 * The first MCV stat is for the most common value.
		 */
		if (nnumbers > 0)
			mcvfreq = numbers[0];
		free_attstatsslot(var->vartype, NULL, 0,
						  numbers, nnumbers);
	}

	/*
	 * Adjust estimated bucketsize upward to account for skewed
	 * distribution.
	 */
	if (avgfreq > 0.0 && mcvfreq > avgfreq)
		estfract *= mcvfreq / avgfreq;

	/*
	 * Clamp bucketsize to sane range (the above adjustment could easily
	 * produce an out-of-range result).  We set the lower bound a little
	 * above zero, since zero isn't a very sane result.
	 */
	if (estfract < 1.0e-6)
		estfract = 1.0e-6;
	else if (estfract > 1.0)
		estfract = 1.0;

	ReleaseSysCache(tuple);

	return (Selectivity) estfract;
}


/*
 * cost_qual_eval
 *		Estimate the CPU costs of evaluating a WHERE clause.
 *		The input can be either an implicitly-ANDed list of boolean
 *		expressions, or a list of RestrictInfo nodes.
 *		The result includes both a one-time (startup) component,
 *		and a per-evaluation component.
 */
void
cost_qual_eval(QualCost *cost, List *quals)
{
	List	   *l;

	cost->startup = 0;
	cost->per_tuple = 0;

	/* We don't charge any cost for the implicit ANDing at top level ... */

	foreach(l, quals)
	{
		Node	   *qual = (Node *) lfirst(l);

		/*
		 * RestrictInfo nodes contain an eval_cost field reserved for this
		 * routine's use, so that it's not necessary to evaluate the qual
		 * clause's cost more than once.  If the clause's cost hasn't been
		 * computed yet, the field's startup value will contain -1.
		 */
		if (qual && IsA(qual, RestrictInfo))
		{
			RestrictInfo *restrictinfo = (RestrictInfo *) qual;

			if (restrictinfo->eval_cost.startup < 0)
			{
				restrictinfo->eval_cost.startup = 0;
				restrictinfo->eval_cost.per_tuple = 0;
				cost_qual_eval_walker((Node *) restrictinfo->clause,
									  &restrictinfo->eval_cost);
			}
			cost->startup += restrictinfo->eval_cost.startup;
			cost->per_tuple += restrictinfo->eval_cost.per_tuple;
		}
		else
		{
			/* If it's a bare expression, must always do it the hard way */
			cost_qual_eval_walker(qual, cost);
		}
	}
}

static bool
cost_qual_eval_walker(Node *node, QualCost *total)
{
	if (node == NULL)
		return false;

	/*
	 * Our basic strategy is to charge one cpu_operator_cost for each
	 * operator or function node in the given tree.  Vars and Consts are
	 * charged zero, and so are boolean operators (AND, OR, NOT).
	 * Simplistic, but a lot better than no model at all.
	 *
	 * Should we try to account for the possibility of short-circuit
	 * evaluation of AND/OR?
	 */
	if (IsA(node, FuncExpr) ||
		IsA(node, OpExpr) ||
		IsA(node, DistinctExpr) ||
		IsA(node, NullIfExpr))
		total->per_tuple += cpu_operator_cost;
	else if (IsA(node, ScalarArrayOpExpr))
	{
		/* should charge more than 1 op cost, but how many? */
		total->per_tuple += cpu_operator_cost * 10;
	}
	else if (IsA(node, SubLink))
	{
		/* This routine should not be applied to un-planned expressions */
		elog(ERROR, "cannot handle unplanned sub-select");
	}
	else if (IsA(node, SubPlan))
	{
		/*
		 * A subplan node in an expression typically indicates that the
		 * subplan will be executed on each evaluation, so charge
		 * accordingly. (Sub-selects that can be executed as InitPlans
		 * have already been removed from the expression.)
		 *
		 * An exception occurs when we have decided we can implement the
		 * subplan by hashing.
		 *
		 */
		SubPlan    *subplan = (SubPlan *) node;
		Plan	   *plan = subplan->plan;

		if (subplan->useHashTable)
		{
			/*
			 * If we are using a hash table for the subquery outputs, then
			 * the cost of evaluating the query is a one-time cost. We
			 * charge one cpu_operator_cost per tuple for the work of
			 * loading the hashtable, too.
			 */
			total->startup += plan->total_cost +
				cpu_operator_cost * plan->plan_rows;

			/*
			 * The per-tuple costs include the cost of evaluating the
			 * lefthand expressions, plus the cost of probing the
			 * hashtable. Recursion into the exprs list will handle the
			 * lefthand expressions properly, and will count one
			 * cpu_operator_cost for each comparison operator.	That is
			 * probably too low for the probing cost, but it's hard to
			 * make a better estimate, so live with it for now.
			 */
		}
		else
		{
			/*
			 * Otherwise we will be rescanning the subplan output on each
			 * evaluation.	We need to estimate how much of the output we
			 * will actually need to scan.	NOTE: this logic should agree
			 * with the estimates used by make_subplan() in
			 * plan/subselect.c.
			 */
			Cost		plan_run_cost = plan->total_cost - plan->startup_cost;

			if (subplan->subLinkType == EXISTS_SUBLINK)
			{
				/* we only need to fetch 1 tuple */
				total->per_tuple += plan_run_cost / plan->plan_rows;
			}
			else if (subplan->subLinkType == ALL_SUBLINK ||
					 subplan->subLinkType == ANY_SUBLINK)