* set the rows count to zero, so there will be no zero divide.) The LIMIT is
* applied as a top-level plan node.
*
+ * For largely historical reasons, most of the routines in this module use
+ * the passed result Path only to store their startup_cost and total_cost
+ * results into. All the input data they need is passed as separate
+ * parameters, even though much of it could be extracted from the Path.
+ * An exception is made for the cost_XXXjoin() routines, which expect all
+ * the non-cost fields of the passed XXXPath to be filled in.
+ *
*
- * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.92 2002/11/30 00:08:16 tgl Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.129 2004/06/01 03:02:52 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
+#include "optimizer/plancat.h"
#include "parser/parsetree.h"
#include "utils/selfuncs.h"
#include "utils/lsyscache.h"
#define LOG2(x) (log(x) / 0.693147180559945)
#define LOG6(x) (log(x) / 1.79175946922805)
+/*
+ * Some Paths return less than the nominal number of rows of their parent
+ * relations; join nodes need to do this to get the correct input count:
+ */
+#define PATH_ROWS(path) \
+ (IsA(path, UniquePath) ? \
+ ((UniquePath *) (path))->rows : \
+ (path)->parent->rows)
+
double effective_cache_size = DEFAULT_EFFECTIVE_CACHE_SIZE;
double random_page_cost = DEFAULT_RANDOM_PAGE_COST;
bool enable_hashjoin = true;
-static Selectivity estimate_hash_bucketsize(Query *root, Var *var);
-static bool cost_qual_eval_walker(Node *node, Cost *total);
-static Selectivity approx_selectivity(Query *root, List *quals);
+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.
- *
- * Note: for historical reasons, this routine and the others in this module
- * use the passed result Path only to store their startup_cost and total_cost
- * results into. All the input data they need is passed as separate
- * parameters, even though much of it could be extracted from the Path.
*/
void
cost_seqscan(Path *path, Query *root,
Cost cpu_per_tuple;
/* Should only be applied to base relations */
- Assert(length(baserel->relids) == 1);
+ Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_RELATION);
if (!enable_seqscan)
run_cost += baserel->pages; /* sequential fetches with cost 1.0 */
/* CPU costs */
- cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost;
+ startup_cost += baserel->baserestrictcost.startup;
+ cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
run_cost += cpu_per_tuple * baserel->tuples;
path->startup_cost = startup_cost;
* 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,
/* Should only be applied to base relations */
Assert(IsA(baserel, RelOptInfo) &&
IsA(index, IndexOptInfo));
- Assert(length(baserel->relids) == 1);
+ Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_RELATION);
- if (!enable_indexscan && !is_injoin)
+ if (!enable_indexscan)
startup_cost += disable_cost;
/*
*----------
*/
- 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 */
*
* Normally the indexquals will be removed from the list of restriction
* clauses that we have to evaluate as qpquals, so we should subtract
- * their costs from baserestrictcost. 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.
- * Also, if we are doing a join then 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.
+ * their costs from baserestrictcost. But if we are doing a join then
+ * 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.
*/
- cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost;
+ startup_cost += baserel->baserestrictcost.startup;
+ cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
if (!is_injoin)
- cpu_per_tuple -= cost_qual_eval(indexQuals);
+ {
+ 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;
+ }
run_cost += cpu_per_tuple * tuples_fetched;
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(length(baserel->relids) == 1);
+ Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_RELATION);
if (!enable_tidscan)
run_cost += random_page_cost * ntuples;
/* CPU costs */
- cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost;
+ startup_cost += baserel->baserestrictcost.startup;
+ cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
run_cost += cpu_per_tuple * ntuples;
path->startup_cost = startup_cost;
path->total_cost = startup_cost + run_cost;
}
+/*
+ * cost_subqueryscan
+ * Determines and returns the cost of scanning a subquery RTE.
+ */
+void
+cost_subqueryscan(Path *path, RelOptInfo *baserel)
+{
+ Cost startup_cost;
+ Cost run_cost;
+ Cost cpu_per_tuple;
+
+ /* Should only be applied to base relations that are subqueries */
+ Assert(baserel->relid > 0);
+ Assert(baserel->rtekind == RTE_SUBQUERY);
+
+ /*
+ * Cost of path is cost of evaluating the subplan, plus cost of
+ * evaluating any restriction clauses that will be attached to the
+ * SubqueryScan node, plus cpu_tuple_cost to account for selection and
+ * projection overhead.
+ */
+ path->startup_cost = baserel->subplan->startup_cost;
+ path->total_cost = baserel->subplan->total_cost;
+
+ startup_cost = baserel->baserestrictcost.startup;
+ cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
+ run_cost = cpu_per_tuple * baserel->tuples;
+
+ path->startup_cost += startup_cost;
+ path->total_cost += startup_cost + run_cost;
+}
+
/*
* cost_functionscan
* Determines and returns the cost of scanning a function RTE.
Cost cpu_per_tuple;
/* Should only be applied to base relations that are functions */
- Assert(length(baserel->relids) == 1);
+ Assert(baserel->relid > 0);
Assert(baserel->rtekind == RTE_FUNCTION);
/*
cpu_per_tuple = cpu_operator_cost;
/* Add scanning CPU costs */
- cpu_per_tuple += cpu_tuple_cost + baserel->baserestrictcost;
+ startup_cost += baserel->baserestrictcost.startup;
+ cpu_per_tuple += cpu_tuple_cost + baserel->baserestrictcost.per_tuple;
run_cost += cpu_per_tuple * baserel->tuples;
path->startup_cost = startup_cost;
* 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;
path->total_cost = startup_cost + run_cost;
}
+/*
+ * cost_material
+ * 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 work_mem, we will need
+ * to write it to disk, so the cost is much higher in that case.
+ */
+void
+cost_material(Path *path,
+ Cost input_cost, double tuples, int width)
+{
+ Cost startup_cost = input_cost;
+ Cost run_cost = 0;
+ double nbytes = relation_byte_size(tuples, width);
+ long work_mem_bytes = work_mem * 1024L;
+
+ /* disk costs */
+ if (nbytes > work_mem_bytes)
+ {
+ double npages = ceil(nbytes / BLCKSZ);
+
+ /* We'll write during startup and read during retrieval */
+ startup_cost += npages;
+ run_cost += npages;
+ }
+
+ /*
+ * Also charge a small amount per extracted tuple. We use
+ * cpu_tuple_cost so that it doesn't appear worthwhile to materialize
+ * a bare seqscan.
+ */
+ run_cost += cpu_tuple_cost * tuples;
+
+ path->startup_cost = startup_cost;
+ path->total_cost = startup_cost + run_cost;
+}
+
/*
* cost_agg
* Determines and returns the cost of performing an Agg plan node,
* additional cpu_operator_cost per grouping column per input tuple
* for grouping comparisons.
*
- * We will produce a single output tuple if not grouping,
- * and a tuple per group otherwise.
+ * We will produce a single output tuple if not grouping, and a tuple per
+ * group otherwise.
+ *
+ * Note: in this cost model, AGG_SORTED and AGG_HASHED have exactly the
+ * same total CPU cost, but AGG_SORTED has lower startup cost. If the
+ * input path is already sorted appropriately, AGG_SORTED should be
+ * preferred (since it has no risk of memory overflow). This will
+ * happen as long as the computed total costs are indeed exactly equal
+ * --- but if there's roundoff error we might do the wrong thing. So
+ * be sure that the computations below form the same intermediate
+ * values in the same order.
*/
if (aggstrategy == AGG_PLAIN)
{
/* Here we are able to deliver output on-the-fly */
startup_cost = input_startup_cost;
total_cost = input_total_cost;
- total_cost += cpu_operator_cost * (input_tuples + numGroups) * numAggs;
+ /* calcs phrased this way to match HASHED case, see note above */
total_cost += cpu_operator_cost * input_tuples * numGroupCols;
+ total_cost += cpu_operator_cost * input_tuples * numAggs;
+ total_cost += cpu_operator_cost * numGroups * numAggs;
}
else
{
/* must be AGG_HASHED */
startup_cost = input_total_cost;
- startup_cost += cpu_operator_cost * input_tuples * numAggs;
startup_cost += cpu_operator_cost * input_tuples * numGroupCols;
+ startup_cost += cpu_operator_cost * input_tuples * numAggs;
total_cost = startup_cost;
total_cost += cpu_operator_cost * numGroups * numAggs;
}
* Determines and returns the cost of joining two relations using the
* nested loop algorithm.
*
- * 'outer_path' is the path for the outer relation
- * 'inner_path' is the path for the inner relation
- * 'restrictlist' are the RestrictInfo nodes to be applied at the join
+ * 'path' is already filled in except for the cost fields
*/
void
-cost_nestloop(Path *path, Query *root,
- Path *outer_path,
- Path *inner_path,
- List *restrictlist)
+cost_nestloop(NestPath *path, Query *root)
{
+ Path *outer_path = path->outerjoinpath;
+ Path *inner_path = path->innerjoinpath;
Cost startup_cost = 0;
Cost run_cost = 0;
Cost cpu_per_tuple;
+ QualCost restrict_qual_cost;
+ double outer_path_rows = PATH_ROWS(outer_path);
+ double inner_path_rows = PATH_ROWS(inner_path);
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 JOIN_IN selectivity. (This assumes that all the quals
+ * attached to the join are IN quals, which should be true.)
+ */
+ joininfactor = join_in_selectivity(path, root);
+
/* cost of source data */
/*
* before we can start returning tuples, so the join's startup cost is
* their sum. What's not so clear is whether the inner path's
* startup_cost must be paid again on each rescan of the inner path.
- * This is not true if the inner path is materialized, but probably is
- * true otherwise. Since we don't yet have clean handling of the
- * decision whether to materialize a path, we can't tell here which
- * will happen. As a compromise, charge 50% of the inner startup cost
- * for each restart.
+ * This is not true if the inner path is materialized or is a
+ * hashjoin, but probably is true otherwise.
*/
startup_cost += outer_path->startup_cost + inner_path->startup_cost;
run_cost += outer_path->total_cost - outer_path->startup_cost;
- run_cost += outer_path->parent->rows *
- (inner_path->total_cost - inner_path->startup_cost);
- if (outer_path->parent->rows > 1)
- run_cost += (outer_path->parent->rows - 1) *
- inner_path->startup_cost * 0.5;
+ if (IsA(inner_path, MaterialPath) ||
+ IsA(inner_path, HashPath))
+ {
+ /* charge only run cost for each iteration of inner path */
+ }
+ else
+ {
+ /*
+ * charge startup cost for each iteration of inner path, except we
+ * already charged the first startup_cost in our own startup
+ */
+ run_cost += (outer_path_rows - 1) * inner_path->startup_cost;
+ }
+ run_cost += outer_path_rows *
+ (inner_path->total_cost - inner_path->startup_cost) * joininfactor;
/*
- * 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.
+ * Compute number of tuples processed (not number emitted!)
*/
- if (IsA(inner_path, IndexPath))
- ntuples = ((IndexPath *) inner_path)->rows;
- else
- ntuples = inner_path->parent->rows;
- ntuples *= outer_path->parent->rows;
+ ntuples = outer_path_rows * inner_path_rows * joininfactor;
/* CPU costs */
- cpu_per_tuple = cpu_tuple_cost + cost_qual_eval(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->startup_cost = startup_cost;
- path->total_cost = startup_cost + run_cost;
+ path->path.startup_cost = startup_cost;
+ path->path.total_cost = startup_cost + run_cost;
}
/*
* Determines and returns the cost of joining two relations using the
* merge join algorithm.
*
- * 'outer_path' is the path for the outer relation
- * 'inner_path' is the path for the inner relation
- * 'restrictlist' are the RestrictInfo nodes to be applied at the join
- * 'mergeclauses' are the RestrictInfo nodes to use as merge clauses
- * (this should be a subset of the restrictlist)
- * 'outersortkeys' and 'innersortkeys' are lists of the keys to be used
- * to sort the outer and inner relations, or NIL if no explicit
- * sort is needed because the source path is already ordered
+ * 'path' is already filled in except for the cost fields
+ *
+ * Notes: path's mergeclauses should be a subset of the joinrestrictinfo list;
+ * outersortkeys and innersortkeys are lists of the keys to be used
+ * to sort the outer and inner relations, or NIL if no explicit
+ * sort is needed because the source path is already ordered.
*/
void
-cost_mergejoin(Path *path, Query *root,
- Path *outer_path,
- Path *inner_path,
- List *restrictlist,
- List *mergeclauses,
- List *outersortkeys,
- List *innersortkeys)
+cost_mergejoin(MergePath *path, Query *root)
{
+ Path *outer_path = path->jpath.outerjoinpath;
+ Path *inner_path = path->jpath.innerjoinpath;
+ List *mergeclauses = path->path_mergeclauses;
+ List *outersortkeys = path->outersortkeys;
+ List *innersortkeys = path->innersortkeys;
Cost startup_cost = 0;
Cost run_cost = 0;
Cost cpu_per_tuple;
+ Selectivity merge_selec;
+ QualCost merge_qual_cost;
+ QualCost qp_qual_cost;
RestrictInfo *firstclause;
- Var *leftvar;
+ double outer_path_rows = PATH_ROWS(outer_path);
+ double inner_path_rows = PATH_ROWS(inner_path);
double outer_rows,
inner_rows;
- double ntuples;
+ double mergejointuples,
+ rescannedtuples;
+ double rescanratio;
Selectivity outerscansel,
innerscansel;
+ Selectivity joininfactor;
Path sort_path; /* dummy for result of cost_sort */
if (!enable_mergejoin)
startup_cost += disable_cost;
+ /*
+ * Compute cost and selectivity of the mergequals and qpquals (other
+ * restriction clauses) separately. We use approx_selectivity here
+ * for speed --- in most cases, any errors won't affect the result
+ * much.
+ *
+ * Note: it's probably bogus to use the normal selectivity calculation
+ * here when either the outer or inner path is a UniquePath.
+ */
+ merge_selec = approx_selectivity(root, mergeclauses,
+ path->jpath.jointype);
+ cost_qual_eval(&merge_qual_cost, mergeclauses);
+ 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 = clamp_row_est(merge_selec * outer_path_rows * inner_path_rows);
+
+ /*
+ * When there are equal merge keys in the outer relation, the
+ * mergejoin must rescan any matching tuples in the inner relation.
+ * This means re-fetching inner tuples. Our cost model for this is
+ * that a re-fetch costs the same as an original fetch, which is
+ * probably an overestimate; but on the other hand we ignore the
+ * bookkeeping costs of mark/restore. Not clear if it's worth
+ * developing a more refined model.
+ *
+ * The number of re-fetches can be estimated approximately as size of
+ * merge join output minus size of inner relation. Assume that the
+ * distinct key values are 1, 2, ..., and denote the number of values
+ * of each key in the outer relation as m1, m2, ...; in the inner
+ * relation, n1, n2, ... Then we have
+ *
+ * size of join = m1 * n1 + m2 * n2 + ...
+ *
+ * number of rescanned tuples = (m1 - 1) * n1 + (m2 - 1) * n2 + ... = m1 *
+ * n1 + m2 * n2 + ... - (n1 + n2 + ...) = size of join - size of inner
+ * relation
+ *
+ * This equation works correctly for outer tuples having no inner match
+ * (nk = 0), but not for inner tuples having no outer match (mk = 0);
+ * we are effectively subtracting those from the number of rescanned
+ * tuples, when we should not. Can we do better without expensive
+ * selectivity computations?
+ */
+ if (IsA(outer_path, UniquePath))
+ rescannedtuples = 0;
+ else
+ {
+ rescannedtuples = mergejointuples - inner_path_rows;
+ /* Must clamp because of possible underestimate */
+ if (rescannedtuples < 0)
+ rescannedtuples = 0;
+ }
+ /* We'll inflate inner run cost this much to account for rescanning */
+ rescanratio = 1.0 + (rescannedtuples / inner_path_rows);
+
/*
* A merge join will stop as soon as it exhausts either input stream.
* Estimate fraction of the left and right inputs that will actually
* 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);
-
- leftvar = get_leftop(firstclause->clause);
- Assert(IsA(leftvar, Var));
- if (VARISRELMEMBER(leftvar->varno, outer_path->parent))
+ 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;
}
- outer_rows = outer_path->parent->rows * outerscansel;
- inner_rows = inner_path->parent->rows * innerscansel;
-
- /* cost of source data */
+ /* convert selectivity to row count; must scan at least one row */
+ outer_rows = clamp_row_est(outer_path_rows * outerscansel);
+ inner_rows = clamp_row_est(inner_path_rows * innerscansel);
/*
- * Note we are assuming that each source tuple is fetched just once,
- * which is not right in the presence of equal keys. If we had a way
- * of estimating the proportion of equal keys, we could apply a
- * correction factor...
+ * Readjust scan selectivities to account for above rounding. This is
+ * normally an insignificant effect, but when there are only a few
+ * rows in the inputs, failing to do this makes for a large percentage
+ * error.
*/
+ outerscansel = outer_rows / outer_path_rows;
+ innerscansel = inner_rows / inner_path_rows;
+
+ /* cost of source data */
+
if (outersortkeys) /* do we need to sort outer? */
{
cost_sort(&sort_path,
root,
outersortkeys,
outer_path->total_cost,
- outer_path->parent->rows,
+ outer_path_rows,
outer_path->parent->width);
startup_cost += sort_path.startup_cost;
run_cost += (sort_path.total_cost - sort_path.startup_cost)
root,
innersortkeys,
inner_path->total_cost,
- inner_path->parent->rows,
+ inner_path_rows,
inner_path->parent->width);
startup_cost += sort_path.startup_cost;
run_cost += (sort_path.total_cost - sort_path.startup_cost)
- * innerscansel;
+ * innerscansel * rescanratio;
}
else
{
startup_cost += inner_path->startup_cost;
run_cost += (inner_path->total_cost - inner_path->startup_cost)
- * innerscansel;
+ * innerscansel * rescanratio;
}
+ /* CPU costs */
+
/*
- * The number of tuple comparisons needed depends drastically on the
- * number of equal keys in the two source relations, which we have no
- * good way of estimating. (XXX could the MCV statistics help?)
- * Somewhat arbitrarily, we charge one tuple comparison (one
- * cpu_operator_cost) for each tuple in the two source relations.
- * This is probably a lower bound.
+ * If we're doing JOIN_IN then we will stop outputting 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
+ * attached to the join are IN quals, which should be true.)
*/
- run_cost += cpu_operator_cost * (outer_rows + inner_rows);
+ joininfactor = join_in_selectivity(&path->jpath, root);
+
+ /*
+ * The number of tuple comparisons needed is approximately number of
+ * outer rows plus number of inner rows plus number of rescanned
+ * tuples (can we refine this?). At each one, we need to evaluate the
+ * mergejoin quals. NOTE: JOIN_IN mode does not save any work here,
+ * so do NOT include joininfactor.
+ */
+ startup_cost += merge_qual_cost.startup;
+ run_cost += merge_qual_cost.per_tuple *
+ (outer_rows + inner_rows * rescanratio);
/*
* For each tuple that gets through the mergejoin proper, we charge
* cpu_tuple_cost plus the cost of evaluating additional restriction
- * clauses that are to be applied at the join. It's OK to use an
- * approximate selectivity here, since in most cases this is a minor
- * component of the cost. NOTE: it's correct to use the unscaled rows
- * counts here, not the scaled-down counts we obtained above.
+ * clauses that are to be applied at the join. (This is pessimistic
+ * since not all of the quals may get evaluated at each tuple.) This
+ * work is skipped in JOIN_IN mode, so apply the factor.
*/
- ntuples = approx_selectivity(root, mergeclauses) *
- outer_path->parent->rows * inner_path->parent->rows;
-
- /* CPU costs */
- cpu_per_tuple = cpu_tuple_cost + cost_qual_eval(restrictlist);
- run_cost += cpu_per_tuple * ntuples;
+ startup_cost += qp_qual_cost.startup;
+ cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
+ run_cost += cpu_per_tuple * mergejointuples * joininfactor;
- path->startup_cost = startup_cost;
- path->total_cost = startup_cost + run_cost;
+ path->jpath.path.startup_cost = startup_cost;
+ path->jpath.path.total_cost = startup_cost + run_cost;
}
/*
* Determines and returns the cost of joining two relations using the
* hash join algorithm.
*
- * 'outer_path' is the path for the outer relation
- * 'inner_path' is the path for the inner relation
- * 'restrictlist' are the RestrictInfo nodes to be applied at the join
- * 'hashclauses' are the RestrictInfo nodes to use as hash clauses
- * (this should be a subset of the restrictlist)
+ * 'path' is already filled in except for the cost fields
+ *
+ * Note: path's hashclauses should be a subset of the joinrestrictinfo list
*/
void
-cost_hashjoin(Path *path, Query *root,
- Path *outer_path,
- Path *inner_path,
- List *restrictlist,
- List *hashclauses)
+cost_hashjoin(HashPath *path, Query *root)
{
+ Path *outer_path = path->jpath.outerjoinpath;
+ Path *inner_path = path->jpath.innerjoinpath;
+ List *hashclauses = path->path_hashclauses;
Cost startup_cost = 0;
Cost run_cost = 0;
Cost cpu_per_tuple;
- double ntuples;
- double outerbytes = relation_byte_size(outer_path->parent->rows,
+ Selectivity hash_selec;
+ QualCost hash_qual_cost;
+ QualCost qp_qual_cost;
+ double hashjointuples;
+ 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->parent->rows,
+ double innerbytes = relation_byte_size(inner_path_rows,
inner_path->parent->width);
- long hashtablebytes = SortMem * 1024L;
+ int num_hashclauses = list_length(hashclauses);
+ int virtualbuckets;
+ int physicalbuckets;
+ int numbatches;
Selectivity innerbucketsize;
- List *hcl;
+ Selectivity joininfactor;
+ ListCell *hcl;
if (!enable_hashjoin)
startup_cost += disable_cost;
+ /*
+ * Compute cost and selectivity of the hashquals and qpquals (other
+ * restriction clauses) separately. We use approx_selectivity here
+ * for speed --- in most cases, any errors won't affect the result
+ * much.
+ *
+ * Note: it's probably bogus to use the normal selectivity calculation
+ * here when either the outer or inner path is a UniquePath.
+ */
+ hash_selec = approx_selectivity(root, hashclauses,
+ path->jpath.jointype);
+ cost_qual_eval(&hash_qual_cost, hashclauses);
+ 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 = clamp_row_est(hash_selec * outer_path_rows * inner_path_rows);
+
/* cost of source data */
startup_cost += outer_path->startup_cost;
run_cost += outer_path->total_cost - outer_path->startup_cost;
startup_cost += inner_path->total_cost;
- /* cost of computing hash function: must do it once per input tuple */
- startup_cost += cpu_operator_cost * inner_path->parent->rows;
- run_cost += cpu_operator_cost * outer_path->parent->rows;
+ /*
+ * Cost of computing hash function: must do it once per input tuple.
+ * We charge one cpu_operator_cost for each column's hash function.
+ *
+ * XXX when a hashclause is more complex than a single operator, we
+ * really should charge the extra eval costs of the left or right
+ * side, as appropriate, here. This seems more work than it's worth
+ * at the moment.
+ */
+ startup_cost += cpu_operator_cost * num_hashclauses * inner_path_rows;
+ run_cost += cpu_operator_cost * num_hashclauses * outer_path_rows;
+
+ /* Get hash table size that executor would use for inner relation */
+ ExecChooseHashTableSize(inner_path_rows,
+ inner_path->parent->width,
+ &virtualbuckets,
+ &physicalbuckets,
+ &numbatches);
/*
* Determine bucketsize fraction for inner relation. We use the
- * smallest bucketsize estimated for any individual hashclause;
- * this is undoubtedly conservative.
+ * smallest bucketsize estimated for any individual hashclause; this
+ * is undoubtedly conservative.
+ *
+ * BUT: if inner relation has been unique-ified, we can assume it's good
+ * for hashing. This is important both because it's the right answer,
+ * and because we avoid contaminating the cache with a value that's
+ * wrong for non-unique-ified paths.
*/
- innerbucketsize = 1.0;
- foreach(hcl, hashclauses)
+ if (IsA(inner_path, UniquePath))
+ innerbucketsize = 1.0 / virtualbuckets;
+ else
{
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(hcl);
- Var *left,
- *right;
- Selectivity thisbucketsize;
-
- Assert(IsA(restrictinfo, RestrictInfo));
- /* these must be OK, since check_hashjoinable accepted the clause */
- left = get_leftop(restrictinfo->clause);
- right = get_rightop(restrictinfo->clause);
-
- /*
- * First we have to figure out which side of the hashjoin clause is the
- * inner side.
- *
- * Since we tend to visit the same clauses over and over when planning
- * a large query, we cache the bucketsize estimate in the RestrictInfo
- * node to avoid repeated lookups of statistics.
- */
- if (VARISRELMEMBER(right->varno, inner_path->parent))
+ innerbucketsize = 1.0;
+ foreach(hcl, hashclauses)
{
- /* righthand side is inner */
- thisbucketsize = restrictinfo->right_bucketsize;
- if (thisbucketsize < 0)
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(hcl);
+ Selectivity thisbucketsize;
+
+ Assert(IsA(restrictinfo, RestrictInfo));
+
+ /*
+ * First we have to figure out which side of the hashjoin
+ * clause is the inner side.
+ *
+ * Since we tend to visit the same clauses over and over when
+ * planning a large query, we cache the bucketsize estimate in
+ * the RestrictInfo node to avoid repeated lookups of
+ * statistics.
+ */
+ if (bms_is_subset(restrictinfo->right_relids,
+ inner_path->parent->relids))
{
- /* not cached yet */
- thisbucketsize = estimate_hash_bucketsize(root, right);
- restrictinfo->right_bucketsize = thisbucketsize;
+ /* righthand side is inner */
+ thisbucketsize = restrictinfo->right_bucketsize;
+ if (thisbucketsize < 0)
+ {
+ /* not cached yet */
+ thisbucketsize =
+ estimate_hash_bucketsize(root,
+ get_rightop(restrictinfo->clause),
+ virtualbuckets);
+ restrictinfo->right_bucketsize = thisbucketsize;
+ }
}
- }
- else
- {
- Assert(VARISRELMEMBER(left->varno, inner_path->parent));
- /* lefthand side is inner */
- thisbucketsize = restrictinfo->left_bucketsize;
- if (thisbucketsize < 0)
+ else
{
- /* not cached yet */
- thisbucketsize = estimate_hash_bucketsize(root, left);
- restrictinfo->left_bucketsize = thisbucketsize;
+ Assert(bms_is_subset(restrictinfo->left_relids,
+ inner_path->parent->relids));
+ /* lefthand side is inner */
+ thisbucketsize = restrictinfo->left_bucketsize;
+ if (thisbucketsize < 0)
+ {
+ /* not cached yet */
+ thisbucketsize =
+ estimate_hash_bucketsize(root,
+ get_leftop(restrictinfo->clause),
+ virtualbuckets);
+ restrictinfo->left_bucketsize = thisbucketsize;
+ }
}
- }
- if (innerbucketsize > thisbucketsize)
- innerbucketsize = thisbucketsize;
+ if (innerbucketsize > thisbucketsize)
+ innerbucketsize = thisbucketsize;
+ }
}
- /*
- * 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. We charge
- * one cpu_operator_cost per tuple comparison.
- */
- run_cost += cpu_operator_cost * outer_path->parent->rows *
- ceil(inner_path->parent->rows * innerbucketsize);
-
- /*
- * 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. It's OK to use an
- * approximate selectivity here, since in most cases this is a minor
- * component of the cost.
- */
- ntuples = approx_selectivity(root, hashclauses) *
- outer_path->parent->rows * inner_path->parent->rows;
-
- /* CPU costs */
- cpu_per_tuple = cpu_tuple_cost + cost_qual_eval(restrictlist);
- run_cost += cpu_per_tuple * ntuples;
-
/*
* 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
* should be nice and sequential...). Writing the inner rel counts as
* startup cost, all the rest as run cost.
*/
- if (innerbytes > hashtablebytes)
+ if (numbatches)
{
- double outerpages = page_size(outer_path->parent->rows,
+ double outerpages = page_size(outer_path_rows,
outer_path->parent->width);
- double innerpages = page_size(inner_path->parent->rows,
+ double innerpages = page_size(inner_path_rows,
inner_path->parent->width);
startup_cost += innerpages;
run_cost += innerpages + 2 * outerpages;
}
- /*
- * 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 startup cost by the
- * square root of the size ratio. (Why square root? No real good
- * reason, but it seems reasonable...)
- */
- if (innerbytes > outerbytes && outerbytes > 0)
- startup_cost *= sqrt(innerbytes / outerbytes);
-
- path->startup_cost = startup_cost;
- 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 can get 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)
-{
- Oid relid;
- RelOptInfo *rel;
- int virtualbuckets;
- int physicalbuckets;
- int numbatches;
- 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 (!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 */
-
- /* Get hash table size that executor would use for this relation */
- ExecChooseHashTableSize(rel->rows, rel->width,
- &virtualbuckets,
- &physicalbuckets,
- &numbatches);
-
- tuple = SearchSysCache(STATRELATT,
- ObjectIdGetDatum(relid),
- Int16GetDatum(var->varattno),
- 0, 0);
- if (!HeapTupleIsValid(tuple))
- {
- /*
- * 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) virtualbuckets;
- 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;
+ /* CPU costs */
/*
- * 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.
+ * 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.)
*/
- ndistinct *= rel->rows / rel->tuples;
+ joininfactor = join_in_selectivity(&path->jpath, root);
/*
- * 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.
+ * 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.
*/
- if (ndistinct > (double) virtualbuckets)
- estfract = 1.0 / (double) virtualbuckets;
- else
- estfract = 1.0 / ndistinct;
+ startup_cost += hash_qual_cost.startup;
+ run_cost += hash_qual_cost.per_tuple *
+ outer_path_rows * clamp_row_est(inner_path_rows * innerbucketsize) *
+ joininfactor;
/*
- * Look up the frequency of the most common value, if available.
+ * 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.)
*/
- 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);
- }
+ startup_cost += qp_qual_cost.startup;
+ cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
+ run_cost += cpu_per_tuple * hashjointuples * joininfactor;
/*
- * Adjust estimated bucketsize upward to account for skewed
- * distribution.
+ * 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 (avgfreq > 0.0 && mcvfreq > avgfreq)
- estfract *= mcvfreq / avgfreq;
-
- ReleaseSysCache(tuple);
+ if (innerbytes > outerbytes && outerbytes > 0)
+ run_cost *= sqrt(innerbytes / outerbytes);
- return (Selectivity) estfract;
+ path->jpath.path.startup_cost = startup_cost;
+ path->jpath.path.total_cost = startup_cost + run_cost;
}
/*
* cost_qual_eval
- * Estimate the CPU cost of evaluating a WHERE clause (once).
+ * 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.
*/
-Cost
-cost_qual_eval(List *quals)
+void
+cost_qual_eval(QualCost *cost, List *quals)
{
- Cost total = 0;
- List *l;
+ ListCell *l;
+
+ cost->startup = 0;
+ cost->per_tuple = 0;
/* We don't charge any cost for the implicit ANDing at top level ... */
* 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 will contain -1.
+ * computed yet, the field's startup value will contain -1.
*/
if (qual && IsA(qual, RestrictInfo))
{
RestrictInfo *restrictinfo = (RestrictInfo *) qual;
- if (restrictinfo->eval_cost < 0)
+ if (restrictinfo->eval_cost.startup < 0)
{
- restrictinfo->eval_cost = 0;
+ restrictinfo->eval_cost.startup = 0;
+ restrictinfo->eval_cost.per_tuple = 0;
cost_qual_eval_walker((Node *) restrictinfo->clause,
&restrictinfo->eval_cost);
}
- total += 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, &total);
+ cost_qual_eval_walker(qual, cost);
}
}
- return total;
}
static bool
-cost_qual_eval_walker(Node *node, Cost *total)
+cost_qual_eval_walker(Node *node, QualCost *total)
{
if (node == NULL)
return false;
* Should we try to account for the possibility of short-circuit
* evaluation of AND/OR?
*/
- if (IsA(node, Expr))
+ 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))
{
- Expr *expr = (Expr *) node;
+ /*
+ * 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;
- switch (expr->opType)
+ if (subplan->useHashTable)
{
- case OP_EXPR:
- case DISTINCT_EXPR:
- case FUNC_EXPR:
- *total += cpu_operator_cost;
- break;
- case OR_EXPR:
- case AND_EXPR:
- case NOT_EXPR:
- break;
- case SUBPLAN_EXPR:
-
- /*
- * A subplan node in an expression indicates that the
- * subplan will be executed on each evaluation, so charge
- * accordingly. (We assume that sub-selects that can be
- * executed as InitPlans have already been removed from
- * the expression.)
- *
- * NOTE: this logic should agree with the estimates used by
- * make_subplan() in plan/subselect.c.
- */
- {
- SubPlan *subplan = (SubPlan *) expr->oper;
- Plan *plan = subplan->plan;
- Cost subcost;
-
- if (subplan->sublink->subLinkType == EXISTS_SUBLINK)
- {
- /* we only need to fetch 1 tuple */
- subcost = plan->startup_cost +
- (plan->total_cost - plan->startup_cost) / plan->plan_rows;
- }
- else if (subplan->sublink->subLinkType == ALL_SUBLINK ||
- subplan->sublink->subLinkType == ANY_SUBLINK)
- {
- /* assume we need 50% of the tuples */
- subcost = plan->startup_cost +
- 0.50 * (plan->total_cost - plan->startup_cost);
- /* XXX what if subplan has been materialized? */
- }
- else
- {
- /* assume we need all tuples */
- subcost = plan->total_cost;
- }
- *total += subcost;
- }
- break;
+ /*
+ * 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)
+ {
+ /* 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;
}
- /* fall through to examine args of Expr node */
}
+
return expression_tree_walker(node, cost_qual_eval_walker,
(void *) total);
}
* 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
* seems OK to live with the approximation.
*/
static Selectivity
-approx_selectivity(Query *root, List *quals)
+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);
- selec = restrictinfo->this_selec;
- }
- else
- {
- /* If it's a bare expression, must always do it the hard way */
- selec = clause_selectivity(root, qual, 0);
- }
- 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 nrows;
+
/* Should only be applied to base relations */
- Assert(length(rel->relids) == 1);
+ Assert(rel->relid > 0);
- rel->rows = rel->tuples *
- restrictlist_selectivity(root,
- rel->baserestrictinfo,
- lfirsti(rel->relids));
+ 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.
- */
- if (rel->rows < 1.0)
- rel->rows = 1.0;
+ rel->rows = clamp_row_est(nrows);
- rel->baserestrictcost = cost_qual_eval(rel->baserestrictinfo);
+ cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo);
set_rel_width(root, rel);
}
* calculations for each pair of input rels that's encountered, and somehow
* average the results? Probably way more trouble than it's worth.)
*
- * We set the same relnode fields as set_baserel_size_estimates() does.
+ * 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 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,
JoinType jointype,
List *restrictlist)
{
- double temp;
-
- /* Start with the Cartesian product */
- temp = outer_rel->rows * inner_rel->rows;
+ Selectivity selec;
+ double nrows;
+ UniquePath *upath;
/*
- * Apply join restrictivity. Note that we are only considering
+ * 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.
*/
- temp *= restrictlist_selectivity(root,
- restrictlist,
- 0);
+ selec = clauselist_selectivity(root,
+ restrictlist,
+ 0,
+ jointype);
/*
- * 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
+ * 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:
+ nrows = outer_rel->rows * inner_rel->rows * selec;
break;
case JOIN_LEFT:
- 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:
- 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:
- 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);
+ 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);
+ nrows = upath->rows * inner_rel->rows * selec;
+ if (nrows > inner_rel->rows)
+ nrows = inner_rel->rows;
break;
default:
- elog(ERROR, "set_joinrel_size_estimates: unsupported join type %d",
- (int) jointype);
+ elog(ERROR, "unrecognized join type: %d", (int) jointype);
+ 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.
+ * 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;
-
- 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 could apply set_rel_width() to compute the output tuple width
- * from scratch, but at present it's always just the sum of the input
- * widths, so why work harder than necessary? If relnode.c is ever
- * taught to remove unneeded columns from join targetlists, go back to
- * using set_rel_width here.
+ * 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.
*/
- rel->width = outer_rel->width + inner_rel->width;
+ 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)
{
/* Should only be applied to base relations that are functions */
- Assert(length(rel->relids) == 1);
+ Assert(rel->relid > 0);
Assert(rel->rtekind == RTE_FUNCTION);
/*
*/
rel->tuples = 1000;
- /* Now estimate number of output rows */
- rel->rows = rel->tuples *
- restrictlist_selectivity(root,
- rel->baserestrictinfo,
- lfirsti(rel->relids));
-
- /*
- * Force estimate to be at least one row, to make explain output look
- * better and to avoid possible divide-by-zero when interpolating
- * cost.
- */
- if (rel->rows < 1.0)
- rel->rows = 1.0;
-
- rel->baserestrictcost = cost_qual_eval(rel->baserestrictinfo);
-
- set_rel_width(root, rel);
+ /* Now estimate number of output rows, etc */
+ set_baserel_size_estimates(root, rel);
}
/*
* set_rel_width
- * Set the estimated output width of the relation.
+ * Set the estimated output width of a base relation.
*
- * NB: this works best on base relations because it prefers to look at
+ * 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;
+ ListCell *tllist;
- foreach(tllist, rel->targetlist)
+ foreach(tllist, rel->reltargetlist)
{
- TargetEntry *tle = (TargetEntry *) lfirst(tllist);
+ Var *var = (Var *) lfirst(tllist);
+ int ndx = var->varattno - rel->min_attr;
+ Oid relid;
int32 item_width;
+ Assert(IsA(var, Var));
+
/*
- * If it's a Var, try to get statistical info from pg_statistic.
+ * The width probably hasn't been cached yet, but may as well
+ * check
*/
- if (tle->expr && IsA(tle->expr, Var))
+ if (rel->attr_widths[ndx] > 0)
{
- Var *var = (Var *) tle->expr;
- Oid relid;
+ tuple_width += rel->attr_widths[ndx];
+ continue;
+ }
- relid = getrelid(var->varno, root->rtable);
- if (relid != InvalidOid)
+ relid = getrelid(var->varno, root->rtable);
+ if (relid != InvalidOid)
+ {
+ item_width = get_attavgwidth(relid, var->varattno);
+ if (item_width > 0)
{
- item_width = get_attavgwidth(relid, var->varattno);
- if (item_width > 0)
- {
- tuple_width += item_width;
- continue;
- }
+ rel->attr_widths[ndx] = item_width;
+ tuple_width += item_width;
+ continue;
}
}
/*
- * Not a Var, or can't find statistics for it. Estimate using
- * just the type info.
+ * Not a plain relation, or can't find statistics for it. Estimate
+ * using just the type info.
*/
- item_width = get_typavgwidth(tle->resdom->restype,
- tle->resdom->restypmod);
+ 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);
static double
relation_byte_size(double tuples, int width)
{
- return tuples * ((double) MAXALIGN(width + sizeof(HeapTupleData)));
+ return tuples * (MAXALIGN(width) + MAXALIGN(sizeof(HeapTupleHeaderData)));
}
/*
projects / postgresql / blobdiff