costsize.c

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

			{
				/* assume we need 50% of the tuples */
				total->per_tuple += 0.50 * plan_run_cost;
				/* also charge a cpu_operator_cost per row examined */
				total->per_tuple += 0.50 * plan->plan_rows * cpu_operator_cost;
			}
			else
			{
				/* assume we need all tuples */
				total->per_tuple += plan_run_cost;
			}

			/*
			 * Also account for subplan's startup cost. If the subplan is
			 * uncorrelated or undirect correlated, AND its topmost node
			 * is a Sort or Material node, assume that we'll only need to
			 * pay its startup cost once; otherwise assume we pay the
			 * startup cost every time.
			 */
			if (subplan->parParam == NIL &&
				(IsA(plan, Sort) ||
				 IsA(plan, Material)))
				total->startup += plan->startup_cost;
			else
				total->per_tuple += plan->startup_cost;
		}
	}

	return expression_tree_walker(node, cost_qual_eval_walker,
								  (void *) total);
}


/*
 * approx_selectivity
 *		Quick-and-dirty estimation of clause selectivities.
 *		The input can be either an implicitly-ANDed list of boolean
 *		expressions, or a list of RestrictInfo nodes (typically the latter).
 *
 * The "quick" part comes from caching the selectivity estimates so we can
 * avoid recomputing them later.  (Since the same clauses are typically
 * examined over and over in different possible join trees, this makes a
 * big difference.)
 *
 * The "dirty" part comes from the fact that the selectivities of multiple
 * clauses are estimated independently and multiplied together.  Now
 * clauselist_selectivity often can't do any better than that anyhow, but
 * for some situations (such as range constraints) it is smarter.
 *
 * Since we are only using the results to estimate how many potential
 * output tuples are generated and passed through qpqual checking, it
 * seems OK to live with the approximation.
 */
static Selectivity
approx_selectivity(Query *root, List *quals, JoinType jointype)
{
	Selectivity total = 1.0;
	List	   *l;

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

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

			if (restrictinfo->this_selec < 0)
				restrictinfo->this_selec =
					clause_selectivity(root,
									   (Node *) restrictinfo->clause,
									   0,
									   jointype);
			selec = restrictinfo->this_selec;
		}
		else
		{
			/* If it's a bare expression, must always do it the hard way */
			selec = clause_selectivity(root, qual, 0, jointype);
		}
		total *= selec;
	}
	return total;
}


/*
 * set_baserel_size_estimates
 *		Set the size estimates for the given base relation.
 *
 * The rel's targetlist and restrictinfo list must have been constructed
 * already.
 *
 * We set the following fields of the rel node:
 *	rows: the estimated number of output tuples (after applying
 *		  restriction clauses).
 *	width: the estimated average output tuple width in bytes.
 *	baserestrictcost: estimated cost of evaluating baserestrictinfo clauses.
 */
void
set_baserel_size_estimates(Query *root, RelOptInfo *rel)
{
	double		temp;

	/* Should only be applied to base relations */
	Assert(rel->relid > 0);

	temp = rel->tuples *
		restrictlist_selectivity(root,
								 rel->baserestrictinfo,
								 rel->relid,
								 JOIN_INNER);

	/*
	 * Force estimate to be at least one row, to make explain output look
	 * better and to avoid possible divide-by-zero when interpolating
	 * cost.  Make it an integer, too.
	 */
	if (temp < 1.0)
		temp = 1.0;
	else
		temp = ceil(temp);

	rel->rows = temp;

	cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo);

	set_rel_width(root, rel);
}

/*
 * set_joinrel_size_estimates
 *		Set the size estimates for the given join relation.
 *
 * The rel's targetlist must have been constructed already, and a
 * restriction clause list that matches the given component rels must
 * be provided.
 *
 * Since there is more than one way to make a joinrel for more than two
 * base relations, the results we get here could depend on which component
 * rel pair is provided.  In theory we should get the same answers no matter
 * which pair is provided; in practice, since the selectivity estimation
 * routines don't handle all cases equally well, we might not.  But there's
 * not much to be done about it.  (Would it make sense to repeat the
 * calculations for each pair of input rels that's encountered, and somehow
 * average the results?  Probably way more trouble than it's worth.)
 *
 * It's important that the results for symmetric JoinTypes be symmetric,
 * eg, (rel1, rel2, JOIN_LEFT) should produce the same result as (rel2,
 * rel1, JOIN_RIGHT).  Also, JOIN_IN should produce the same result as
 * JOIN_UNIQUE_INNER, likewise JOIN_REVERSE_IN == JOIN_UNIQUE_OUTER.
 *
 * We set the same relnode fields as set_baserel_size_estimates() does.
 */
void
set_joinrel_size_estimates(Query *root, RelOptInfo *rel,
						   RelOptInfo *outer_rel,
						   RelOptInfo *inner_rel,
						   JoinType jointype,
						   List *restrictlist)
{
	Selectivity selec;
	double		temp;
	UniquePath *upath;

	/*
	 * Compute joinclause selectivity.	Note that we are only considering
	 * clauses that become restriction clauses at this join level; we are
	 * not double-counting them because they were not considered in
	 * estimating the sizes of the component rels.
	 */
	selec = restrictlist_selectivity(root,
									 restrictlist,
									 0,
									 jointype);

	/*
	 * Basically, we multiply size of Cartesian product by selectivity.
	 *
	 * If we are doing an outer join, take that into account: the output must
	 * be at least as large as the non-nullable input.	(Is there any
	 * chance of being even smarter?)
	 *
	 * For JOIN_IN and variants, the Cartesian product is figured with
	 * respect to a unique-ified input, and then we can clamp to the size
	 * of the other input.
	 */
	switch (jointype)
	{
		case JOIN_INNER:
			temp = outer_rel->rows * inner_rel->rows * selec;
			break;
		case JOIN_LEFT:
			temp = outer_rel->rows * inner_rel->rows * selec;
			if (temp < outer_rel->rows)
				temp = outer_rel->rows;
			break;
		case JOIN_RIGHT:
			temp = outer_rel->rows * inner_rel->rows * selec;
			if (temp < inner_rel->rows)
				temp = inner_rel->rows;
			break;
		case JOIN_FULL:
			temp = outer_rel->rows * inner_rel->rows * selec;
			if (temp < outer_rel->rows)
				temp = outer_rel->rows;
			if (temp < inner_rel->rows)
				temp = inner_rel->rows;
			break;
		case JOIN_IN:
		case JOIN_UNIQUE_INNER:
			upath = create_unique_path(root, inner_rel,
									   inner_rel->cheapest_total_path);
			temp = outer_rel->rows * upath->rows * selec;
			if (temp > outer_rel->rows)
				temp = outer_rel->rows;
			break;
		case JOIN_REVERSE_IN:
		case JOIN_UNIQUE_OUTER:
			upath = create_unique_path(root, outer_rel,
									   outer_rel->cheapest_total_path);
			temp = upath->rows * inner_rel->rows * selec;
			if (temp > inner_rel->rows)
				temp = inner_rel->rows;
			break;
		default:
			elog(ERROR, "unrecognized join type: %d", (int) jointype);
			temp = 0;			/* keep compiler quiet */
			break;
	}

	/*
	 * Force estimate to be at least one row, to make explain output look
	 * better and to avoid possible divide-by-zero when interpolating
	 * cost.  Make it an integer, too.
	 */
	if (temp < 1.0)
		temp = 1.0;
	else
		temp = ceil(temp);

	rel->rows = temp;

	/*
	 * We need not compute the output width here, because
	 * build_joinrel_tlist already did.
	 */
}

/*
 * set_function_size_estimates
 *		Set the size estimates for a base relation that is a function call.
 *
 * The rel's targetlist and restrictinfo list must have been constructed
 * already.
 *
 * We set the following fields of the rel node:
 *	rows: the estimated number of output tuples (after applying
 *		  restriction clauses).
 *	width: the estimated average output tuple width in bytes.
 *	baserestrictcost: estimated cost of evaluating baserestrictinfo clauses.
 */
void
set_function_size_estimates(Query *root, RelOptInfo *rel)
{
	double		temp;

	/* Should only be applied to base relations that are functions */
	Assert(rel->relid > 0);
	Assert(rel->rtekind == RTE_FUNCTION);

	/*
	 * Estimate number of rows the function itself will return.
	 *
	 * XXX no idea how to do this yet; but should at least check whether
	 * function returns set or not...
	 */
	rel->tuples = 1000;

	/* Now estimate number of output rows */
	temp = rel->tuples *
		restrictlist_selectivity(root,
								 rel->baserestrictinfo,
								 rel->relid,
								 JOIN_INNER);

	/*
	 * Force estimate to be at least one row, to make explain output look
	 * better and to avoid possible divide-by-zero when interpolating
	 * cost.  Make it an integer, too.
	 */
	if (temp < 1.0)
		temp = 1.0;
	else
		temp = ceil(temp);

	rel->rows = temp;

	cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo);

	set_rel_width(root, rel);
}


/*
 * set_rel_width
 *		Set the estimated output width of a base relation.
 *
 * NB: this works best on plain relations because it prefers to look at
 * real Vars.  It will fail to make use of pg_statistic info when applied
 * to a subquery relation, even if the subquery outputs are simple vars
 * that we could have gotten info for.	Is it worth trying to be smarter
 * about subqueries?
 *
 * The per-attribute width estimates are cached for possible re-use while
 * building join relations.
 */
static void
set_rel_width(Query *root, RelOptInfo *rel)
{
	int32		tuple_width = 0;
	List	   *tllist;

	foreach(tllist, FastListValue(&rel->reltargetlist))
	{
		Var		   *var = (Var *) lfirst(tllist);
		int			ndx = var->varattno - rel->min_attr;
		Oid			relid;
		int32		item_width;

		Assert(IsA(var, Var));

		/*
		 * The width probably hasn't been cached yet, but may as well
		 * check
		 */
		if (rel->attr_widths[ndx] > 0)
		{
			tuple_width += rel->attr_widths[ndx];
			continue;
		}

		relid = getrelid(var->varno, root->rtable);
		if (relid != InvalidOid)
		{
			item_width = get_attavgwidth(relid, var->varattno);
			if (item_width > 0)
			{
				rel->attr_widths[ndx] = item_width;
				tuple_width += item_width;
				continue;
			}
		}

		/*
		 * Not a plain relation, or can't find statistics for it. Estimate
		 * using just the type info.
		 */
		item_width = get_typavgwidth(var->vartype, var->vartypmod);
		Assert(item_width > 0);
		rel->attr_widths[ndx] = item_width;
		tuple_width += item_width;
	}
	Assert(tuple_width >= 0);
	rel->width = tuple_width;
}

/*
 * relation_byte_size
 *	  Estimate the storage space in bytes for a given number of tuples
 *	  of a given width (size in bytes).
 */
static double
relation_byte_size(double tuples, int width)
{
	return tuples * (MAXALIGN(width) + MAXALIGN(sizeof(HeapTupleData)));
}

/*
 * page_size
 *	  Returns an estimate of the number of pages covered by a given
 *	  number of tuples of a given width (size in bytes).
 */
static double
page_size(double tuples, int width)
{
	return ceil(relation_byte_size(tuples, width) / BLCKSZ);
}