* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.116 2003/11/29 19:51:50 pgsql Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.129 2004/06/01 03:02:52 tgl Exp $
*
*-------------------------------------------------------------------------
*/
bool enable_hashjoin = true;
-static Selectivity estimate_hash_bucketsize(Query *root, Var *var,
- int nbuckets);
static bool cost_qual_eval_walker(Node *node, QualCost *total);
static Selectivity approx_selectivity(Query *root, List *quals,
JoinType jointype);
+static Selectivity join_in_selectivity(JoinPath *path, Query *root);
static void set_rel_width(Query *root, RelOptInfo *rel);
static double relation_byte_size(double tuples, int width);
static double page_size(double tuples, int width);
+/*
+ * clamp_row_est
+ * Force a row-count estimate to a sane value.
+ */
+double
+clamp_row_est(double nrows)
+{
+ /*
+ * Force estimate to be at least one row, to make explain output look
+ * better and to avoid possible divide-by-zero when interpolating
+ * costs. Make it an integer, too.
+ */
+ if (nrows < 1.0)
+ nrows = 1.0;
+ else
+ nrows = ceil(nrows);
+
+ return nrows;
+}
+
+
/*
* cost_seqscan
* Determines and returns the cost of scanning a relation sequentially.
* Any additional quals evaluated as qpquals may reduce the number of returned
* tuples, but they won't reduce the number of tuples we have to fetch from
* the table, so they don't reduce the scan cost.
+ *
+ * NOTE: as of 7.5, indexQuals is a list of RestrictInfo nodes, where formerly
+ * it was a list of bare clause expressions.
*/
void
cost_index(Path *path, Query *root,
*----------
*/
- tuples_fetched = indexSelectivity * baserel->tuples;
- /* Don't believe estimates less than 1... */
- if (tuples_fetched < 1.0)
- tuples_fetched = 1.0;
+ tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
/* This part is the Mackert and Lohman formula */
* some of the indexquals are join clauses and shouldn't be
* subtracted. Rather than work out exactly how much to subtract, we
* don't subtract anything.
- *
- * XXX For a lossy index, not all the quals will be removed and so we
- * really shouldn't subtract their costs; but detecting that seems
- * more expensive than it's worth.
*/
startup_cost += baserel->baserestrictcost.startup;
cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
QualCost index_qual_cost;
cost_qual_eval(&index_qual_cost, indexQuals);
+ /* any startup cost still has to be paid ... */
cpu_per_tuple -= index_qual_cost.per_tuple;
}
Cost startup_cost = 0;
Cost run_cost = 0;
Cost cpu_per_tuple;
- int ntuples = length(tideval);
+ int ntuples = list_length(tideval);
/* Should only be applied to base relations */
Assert(baserel->relid > 0);
* Determines and returns the cost of sorting a relation, including
* the cost of reading the input data.
*
- * If the total volume of data to sort is less than SortMem, we will do
+ * If the total volume of data to sort is less than work_mem, we will do
* an in-memory sort, which requires no I/O and about t*log2(t) tuple
* comparisons for t tuples.
*
- * If the total volume exceeds SortMem, we switch to a tape-style merge
+ * If the total volume exceeds work_mem, we switch to a tape-style merge
* algorithm. There will still be about t*log2(t) tuple comparisons in
* total, but we will also need to write and read each tuple once per
* merge pass. We expect about ceil(log6(r)) merge passes where r is the
* number of initial runs formed (log6 because tuplesort.c uses six-tape
- * merging). Since the average initial run should be about twice SortMem,
+ * merging). Since the average initial run should be about twice work_mem,
* we have
- * disk traffic = 2 * relsize * ceil(log6(p / (2*SortMem)))
+ * disk traffic = 2 * relsize * ceil(log6(p / (2*work_mem)))
* cpu = comparison_cost * t * log2(t)
*
* The disk traffic is assumed to be half sequential and half random
Cost startup_cost = input_cost;
Cost run_cost = 0;
double nbytes = relation_byte_size(tuples, width);
- long sortmembytes = SortMem * 1024L;
+ long work_mem_bytes = work_mem * 1024L;
if (!enable_sort)
startup_cost += disable_cost;
startup_cost += 2.0 * cpu_operator_cost * tuples * LOG2(tuples);
/* disk costs */
- if (nbytes > sortmembytes)
+ if (nbytes > work_mem_bytes)
{
double npages = ceil(nbytes / BLCKSZ);
- double nruns = nbytes / (sortmembytes * 2);
+ double nruns = nbytes / (work_mem_bytes * 2);
double log_runs = ceil(LOG6(nruns));
double npageaccesses;
* Determines and returns the cost of materializing a relation, including
* the cost of reading the input data.
*
- * If the total volume of data to materialize exceeds SortMem, we will need
+ * If the total volume of data to materialize exceeds work_mem, we will need
* to write it to disk, so the cost is much higher in that case.
*/
void
Cost startup_cost = input_cost;
Cost run_cost = 0;
double nbytes = relation_byte_size(tuples, width);
- long sortmembytes = SortMem * 1024L;
+ long work_mem_bytes = work_mem * 1024L;
/* disk costs */
- if (nbytes > sortmembytes)
+ if (nbytes > work_mem_bytes)
{
double npages = ceil(nbytes / BLCKSZ);
{
Path *outer_path = path->outerjoinpath;
Path *inner_path = path->innerjoinpath;
- List *restrictlist = path->joinrestrictinfo;
Cost startup_cost = 0;
Cost run_cost = 0;
Cost cpu_per_tuple;
double ntuples;
Selectivity joininfactor;
+ /*
+ * If inner path is an indexscan, be sure to use its estimated output row
+ * count, which may be lower than the restriction-clause-only row count of
+ * its parent. (We don't include this case in the PATH_ROWS macro because
+ * it applies *only* to a nestloop's inner relation.)
+ */
+ if (IsA(inner_path, IndexPath))
+ inner_path_rows = ((IndexPath *) inner_path)->rows;
+
if (!enable_nestloop)
startup_cost += disable_cost;
* If we're doing JOIN_IN then we will stop scanning inner tuples for
* 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
+ * the JOIN_IN selectivity. (This assumes that all the quals
* attached to the join are IN quals, which should be true.)
- *
- * Note: it's probably bogus to use the normal selectivity calculation
- * here when either the outer or inner path is a UniquePath.
*/
- if (path->jointype == JOIN_IN)
- {
- Selectivity qual_selec = approx_selectivity(root, restrictlist,
- path->jointype);
- double qptuples;
-
- qptuples = ceil(qual_selec * outer_path_rows * inner_path_rows);
- if (qptuples > path->path.parent->rows)
- joininfactor = path->path.parent->rows / qptuples;
- else
- joininfactor = 1.0;
- }
- else
- joininfactor = 1.0;
+ joininfactor = join_in_selectivity(path, root);
/* cost of source data */
(inner_path->total_cost - inner_path->startup_cost) * joininfactor;
/*
- * Compute number of tuples processed (not number emitted!). If inner
- * path is an indexscan, be sure to use its estimated output row
- * count, which may be lower than the restriction-clause-only row
- * count of its parent. (We don't include this case in the PATH_ROWS
- * macro because it applies *only* to a nestloop's inner relation.)
- * Note: it is correct to use the unadjusted inner_path_rows in the
- * above calculation for joininfactor, since otherwise we'd be
- * double-counting the selectivity of the join clause being used for
- * the index.
+ * Compute number of tuples processed (not number emitted!)
*/
- if (IsA(inner_path, IndexPath))
- inner_path_rows = ((IndexPath *) inner_path)->rows;
-
- ntuples = inner_path_rows * outer_path_rows;
+ ntuples = outer_path_rows * inner_path_rows * joininfactor;
/* CPU costs */
- cost_qual_eval(&restrict_qual_cost, restrictlist);
+ cost_qual_eval(&restrict_qual_cost, path->joinrestrictinfo);
startup_cost += restrict_qual_cost.startup;
cpu_per_tuple = cpu_tuple_cost + restrict_qual_cost.per_tuple;
run_cost += cpu_per_tuple * ntuples;
{
Path *outer_path = path->jpath.outerjoinpath;
Path *inner_path = path->jpath.innerjoinpath;
- List *restrictlist = path->jpath.joinrestrictinfo;
List *mergeclauses = path->path_mergeclauses;
List *outersortkeys = path->outersortkeys;
List *innersortkeys = path->innersortkeys;
Cost run_cost = 0;
Cost cpu_per_tuple;
Selectivity merge_selec;
- Selectivity qp_selec;
QualCost merge_qual_cost;
QualCost qp_qual_cost;
RestrictInfo *firstclause;
- List *qpquals;
double outer_path_rows = PATH_ROWS(outer_path);
double inner_path_rows = PATH_ROWS(inner_path);
double outer_rows,
inner_rows;
double mergejointuples,
rescannedtuples;
- double qptuples;
double rescanratio;
Selectivity outerscansel,
innerscansel;
merge_selec = approx_selectivity(root, mergeclauses,
path->jpath.jointype);
cost_qual_eval(&merge_qual_cost, mergeclauses);
- qpquals = set_ptrDifference(restrictlist, mergeclauses);
- qp_selec = approx_selectivity(root, qpquals,
- path->jpath.jointype);
- cost_qual_eval(&qp_qual_cost, qpquals);
- freeList(qpquals);
+ cost_qual_eval(&qp_qual_cost, path->jpath.joinrestrictinfo);
+ qp_qual_cost.startup -= merge_qual_cost.startup;
+ qp_qual_cost.per_tuple -= merge_qual_cost.per_tuple;
/* approx # tuples passing the merge quals */
- mergejointuples = ceil(merge_selec * outer_path_rows * inner_path_rows);
- /* approx # tuples passing qpquals as well */
- qptuples = ceil(mergejointuples * qp_selec);
+ mergejointuples = clamp_row_est(merge_selec * outer_path_rows * inner_path_rows);
/*
* When there are equal merge keys in the outer relation, the
* all mergejoin paths associated with the merge clause, we cache the
* results in the RestrictInfo node.
*/
- firstclause = (RestrictInfo *) lfirst(mergeclauses);
- if (firstclause->left_mergescansel < 0) /* not computed yet? */
- mergejoinscansel(root, (Node *) firstclause->clause,
- &firstclause->left_mergescansel,
- &firstclause->right_mergescansel);
-
- if (bms_is_subset(firstclause->left_relids, outer_path->parent->relids))
+ if (mergeclauses)
{
- /* left side of clause is outer */
- outerscansel = firstclause->left_mergescansel;
- innerscansel = firstclause->right_mergescansel;
+ firstclause = (RestrictInfo *) linitial(mergeclauses);
+ if (firstclause->left_mergescansel < 0) /* not computed yet? */
+ mergejoinscansel(root, (Node *) firstclause->clause,
+ &firstclause->left_mergescansel,
+ &firstclause->right_mergescansel);
+
+ if (bms_is_subset(firstclause->left_relids, outer_path->parent->relids))
+ {
+ /* left side of clause is outer */
+ outerscansel = firstclause->left_mergescansel;
+ innerscansel = firstclause->right_mergescansel;
+ }
+ else
+ {
+ /* left side of clause is inner */
+ outerscansel = firstclause->right_mergescansel;
+ innerscansel = firstclause->left_mergescansel;
+ }
}
else
{
- /* left side of clause is inner */
- outerscansel = firstclause->right_mergescansel;
- innerscansel = firstclause->left_mergescansel;
+ /* cope with clauseless mergejoin */
+ outerscansel = innerscansel = 1.0;
}
/* convert selectivity to row count; must scan at least one row */
-
- outer_rows = ceil(outer_path_rows * outerscansel);
- if (outer_rows < 1)
- outer_rows = 1;
- inner_rows = ceil(inner_path_rows * innerscansel);
- if (inner_rows < 1)
- inner_rows = 1;
+ outer_rows = clamp_row_est(outer_path_rows * outerscansel);
+ inner_rows = clamp_row_est(inner_path_rows * innerscansel);
/*
* Readjust scan selectivities to account for above rounding. This is
* 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;
+ joininfactor = join_in_selectivity(&path->jpath, root);
/*
* The number of tuple comparisons needed is approximately number of
{
Path *outer_path = path->jpath.outerjoinpath;
Path *inner_path = path->jpath.innerjoinpath;
- List *restrictlist = path->jpath.joinrestrictinfo;
List *hashclauses = path->path_hashclauses;
Cost startup_cost = 0;
Cost run_cost = 0;
Cost cpu_per_tuple;
Selectivity hash_selec;
- Selectivity qp_selec;
QualCost hash_qual_cost;
QualCost qp_qual_cost;
double hashjointuples;
- double qptuples;
double outer_path_rows = PATH_ROWS(outer_path);
double inner_path_rows = PATH_ROWS(inner_path);
double outerbytes = relation_byte_size(outer_path_rows,
outer_path->parent->width);
double innerbytes = relation_byte_size(inner_path_rows,
inner_path->parent->width);
- int num_hashclauses = length(hashclauses);
+ int num_hashclauses = list_length(hashclauses);
int virtualbuckets;
int physicalbuckets;
int numbatches;
Selectivity innerbucketsize;
Selectivity joininfactor;
- List *hcl;
- List *qpquals;
+ ListCell *hcl;
if (!enable_hashjoin)
startup_cost += disable_cost;
hash_selec = approx_selectivity(root, hashclauses,
path->jpath.jointype);
cost_qual_eval(&hash_qual_cost, hashclauses);
- qpquals = set_ptrDifference(restrictlist, hashclauses);
- qp_selec = approx_selectivity(root, qpquals,
- path->jpath.jointype);
- cost_qual_eval(&qp_qual_cost, qpquals);
- freeList(qpquals);
+ cost_qual_eval(&qp_qual_cost, path->jpath.joinrestrictinfo);
+ qp_qual_cost.startup -= hash_qual_cost.startup;
+ qp_qual_cost.per_tuple -= hash_qual_cost.per_tuple;
/* approx # tuples passing the hash quals */
- hashjointuples = ceil(hash_selec * outer_path_rows * inner_path_rows);
- /* approx # tuples passing qpquals as well */
- qptuples = ceil(hashjointuples * qp_selec);
+ hashjointuples = clamp_row_est(hash_selec * outer_path_rows * inner_path_rows);
/* cost of source data */
startup_cost += outer_path->startup_cost;
/* not cached yet */
thisbucketsize =
estimate_hash_bucketsize(root,
- (Var *) get_rightop(restrictinfo->clause),
+ get_rightop(restrictinfo->clause),
virtualbuckets);
restrictinfo->right_bucketsize = thisbucketsize;
}
/* not cached yet */
thisbucketsize =
estimate_hash_bucketsize(root,
- (Var *) get_leftop(restrictinfo->clause),
+ get_leftop(restrictinfo->clause),
virtualbuckets);
restrictinfo->left_bucketsize = thisbucketsize;
}
* 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;
+ joininfactor = join_in_selectivity(&path->jpath, root);
/*
* The number of tuple comparisons needed is the number of outer
*/
startup_cost += hash_qual_cost.startup;
run_cost += hash_qual_cost.per_tuple *
- outer_path_rows * ceil(inner_path_rows * innerbucketsize) *
+ outer_path_rows * clamp_row_est(inner_path_rows * innerbucketsize) *
joininfactor;
/*
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;
-
- /*
- * 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
void
cost_qual_eval(QualCost *cost, List *quals)
{
- List *l;
+ ListCell *l;
cost->startup = 0;
cost->per_tuple = 0;
* 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
+ * This is quick-and-dirty because we bypass clauselist_selectivity, and
+ * simply multiply the independent clause selectivities together. Now
* clauselist_selectivity often can't do any better than that anyhow, but
- * for some situations (such as range constraints) it is smarter.
+ * for some situations (such as range constraints) it is smarter. However,
+ * we can't effectively cache the results of clauselist_selectivity, whereas
+ * the individual clause selectivities can be and are cached.
*
* Since we are only using the results to estimate how many potential
* output tuples are generated and passed through qpqual checking, it
approx_selectivity(Query *root, List *quals, JoinType jointype)
{
Selectivity total = 1.0;
- List *l;
+ ListCell *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;
+ /* Note that clause_selectivity will be able to cache its result */
+ total *= clause_selectivity(root, qual, 0, jointype);
}
return total;
}
void
set_baserel_size_estimates(Query *root, RelOptInfo *rel)
{
- double temp;
+ double nrows;
/* Should only be applied to base relations */
Assert(rel->relid > 0);
- temp = rel->tuples *
- restrictlist_selectivity(root,
- rel->baserestrictinfo,
- rel->relid,
- JOIN_INNER);
+ nrows = rel->tuples *
+ clauselist_selectivity(root,
+ rel->baserestrictinfo,
+ 0,
+ 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;
+ rel->rows = clamp_row_est(nrows);
cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo);
* 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.
+ * We set only the rows field here. The width field was already set by
+ * build_joinrel_tlist, and baserestrictcost is not used for join rels.
*/
void
set_joinrel_size_estimates(Query *root, RelOptInfo *rel,
List *restrictlist)
{
Selectivity selec;
- double temp;
+ double nrows;
UniquePath *upath;
/*
* not double-counting them because they were not considered in
* estimating the sizes of the component rels.
*/
- selec = restrictlist_selectivity(root,
- restrictlist,
- 0,
- jointype);
+ selec = clauselist_selectivity(root,
+ restrictlist,
+ 0,
+ jointype);
/*
* Basically, we multiply size of Cartesian product by selectivity.
switch (jointype)
{
case JOIN_INNER:
- temp = outer_rel->rows * inner_rel->rows * selec;
+ nrows = 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;
+ nrows = outer_rel->rows * inner_rel->rows * selec;
+ if (nrows < outer_rel->rows)
+ nrows = outer_rel->rows;
break;
case JOIN_RIGHT:
- temp = outer_rel->rows * inner_rel->rows * selec;
- if (temp < inner_rel->rows)
- temp = inner_rel->rows;
+ nrows = outer_rel->rows * inner_rel->rows * selec;
+ if (nrows < inner_rel->rows)
+ nrows = 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;
+ nrows = outer_rel->rows * inner_rel->rows * selec;
+ if (nrows < outer_rel->rows)
+ nrows = outer_rel->rows;
+ if (nrows < inner_rel->rows)
+ nrows = 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;
+ nrows = outer_rel->rows * upath->rows * selec;
+ if (nrows > outer_rel->rows)
+ nrows = 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;
+ nrows = upath->rows * inner_rel->rows * selec;
+ if (nrows > inner_rel->rows)
+ nrows = inner_rel->rows;
break;
default:
elog(ERROR, "unrecognized join type: %d", (int) jointype);
- temp = 0; /* keep compiler quiet */
+ nrows = 0; /* keep compiler quiet */
break;
}
+ rel->rows = clamp_row_est(nrows);
+}
+
+/*
+ * join_in_selectivity
+ * Determines the factor by which a JOIN_IN join's result is expected
+ * to be smaller than an ordinary inner join.
+ *
+ * 'path' is already filled in except for the cost fields
+ */
+static Selectivity
+join_in_selectivity(JoinPath *path, Query *root)
+{
+ RelOptInfo *innerrel;
+ UniquePath *innerunique;
+ Selectivity selec;
+ double nrows;
+
+ /* Return 1.0 whenever it's not JOIN_IN */
+ if (path->jointype != JOIN_IN)
+ return 1.0;
+
/*
- * 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.
+ * Return 1.0 if the inner side is already known unique. The case where
+ * the inner path is already a UniquePath probably cannot happen in
+ * current usage, but check it anyway for completeness. The interesting
+ * case is where we've determined the inner relation itself is unique,
+ * which we can check by looking at the rows estimate for its UniquePath.
*/
- if (temp < 1.0)
- temp = 1.0;
- else
- temp = ceil(temp);
-
- rel->rows = temp;
+ if (IsA(path->innerjoinpath, UniquePath))
+ return 1.0;
+ innerrel = path->innerjoinpath->parent;
+ innerunique = create_unique_path(root,
+ innerrel,
+ innerrel->cheapest_total_path);
+ if (innerunique->rows >= innerrel->rows)
+ return 1.0;
/*
- * We need not compute the output width here, because
- * build_joinrel_tlist already did.
+ * Compute same result set_joinrel_size_estimates would compute
+ * for JOIN_INNER. Note that we use the input rels' absolute size
+ * estimates, not PATH_ROWS() which might be less; if we used PATH_ROWS()
+ * we'd be double-counting the effects of any join clauses used in
+ * input scans.
*/
+ selec = clauselist_selectivity(root,
+ path->joinrestrictinfo,
+ 0,
+ JOIN_INNER);
+ nrows = path->outerjoinpath->parent->rows * innerrel->rows * selec;
+
+ nrows = clamp_row_est(nrows);
+
+ /* See if it's larger than the actual JOIN_IN size estimate */
+ if (nrows > path->path.parent->rows)
+ return path->path.parent->rows / nrows;
+ else
+ return 1.0;
}
/*
* 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.
+ * We set the same fields as set_baserel_size_estimates.
*/
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);
*/
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);
+ /* Now estimate number of output rows, etc */
+ set_baserel_size_estimates(root, rel);
}
set_rel_width(Query *root, RelOptInfo *rel)
{
int32 tuple_width = 0;
- List *tllist;
+ ListCell *tllist;
- foreach(tllist, FastListValue(&rel->reltargetlist))
+ foreach(tllist, rel->reltargetlist)
{
Var *var = (Var *) lfirst(tllist);
int ndx = var->varattno - rel->min_attr;
static double
relation_byte_size(double tuples, int width)
{
- return tuples * (MAXALIGN(width) + MAXALIGN(sizeof(HeapTupleData)));
+ return tuples * (MAXALIGN(width) + MAXALIGN(sizeof(HeapTupleHeaderData)));
}
/*