PostgreSQL Source Code  git master
costsize.c File Reference
#include "postgres.h"
#include <math.h>
#include "access/amapi.h"
#include "access/htup_details.h"
#include "access/tsmapi.h"
#include "executor/executor.h"
#include "executor/nodeAgg.h"
#include "executor/nodeHash.h"
#include "miscadmin.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/placeholder.h"
#include "optimizer/plancat.h"
#include "optimizer/planmain.h"
#include "optimizer/restrictinfo.h"
#include "parser/parsetree.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
#include "utils/spccache.h"
#include "utils/tuplesort.h"
Include dependency graph for costsize.c:

Go to the source code of this file.

Data Structures

struct  cost_qual_eval_context
 

Macros

#define LOG2(x)   (log(x) / 0.693147180559945)
 
#define APPEND_CPU_COST_MULTIPLIER   0.5
 

Functions

static Listextract_nonindex_conditions (List *qual_clauses, List *indexclauses)
 
static MergeScanSelCachecached_scansel (PlannerInfo *root, RestrictInfo *rinfo, PathKey *pathkey)
 
static void cost_rescan (PlannerInfo *root, Path *path, Cost *rescan_startup_cost, Cost *rescan_total_cost)
 
static bool cost_qual_eval_walker (Node *node, cost_qual_eval_context *context)
 
static void get_restriction_qual_cost (PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
 
static bool has_indexed_join_quals (NestPath *joinpath)
 
static double approx_tuple_count (PlannerInfo *root, JoinPath *path, List *quals)
 
static double calc_joinrel_size_estimate (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outer_rel, RelOptInfo *inner_rel, double outer_rows, double inner_rows, SpecialJoinInfo *sjinfo, List *restrictlist)
 
static Selectivity get_foreign_key_join_selectivity (PlannerInfo *root, Relids outer_relids, Relids inner_relids, SpecialJoinInfo *sjinfo, List **restrictlist)
 
static Cost append_nonpartial_cost (List *subpaths, int numpaths, int parallel_workers)
 
static void set_rel_width (PlannerInfo *root, RelOptInfo *rel)
 
static double relation_byte_size (double tuples, int width)
 
static double page_size (double tuples, int width)
 
static double get_parallel_divisor (Path *path)
 
double clamp_row_est (double nrows)
 
void cost_seqscan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_samplescan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_gather (GatherPath *path, PlannerInfo *root, RelOptInfo *rel, ParamPathInfo *param_info, double *rows)
 
void cost_gather_merge (GatherMergePath *path, PlannerInfo *root, RelOptInfo *rel, ParamPathInfo *param_info, Cost input_startup_cost, Cost input_total_cost, double *rows)
 
void cost_index (IndexPath *path, PlannerInfo *root, double loop_count, bool partial_path)
 
double index_pages_fetched (double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
 
static double get_indexpath_pages (Path *bitmapqual)
 
void cost_bitmap_heap_scan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, Path *bitmapqual, double loop_count)
 
void cost_bitmap_tree_node (Path *path, Cost *cost, Selectivity *selec)
 
void cost_bitmap_and_node (BitmapAndPath *path, PlannerInfo *root)
 
void cost_bitmap_or_node (BitmapOrPath *path, PlannerInfo *root)
 
void cost_tidscan (Path *path, PlannerInfo *root, RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info)
 
void cost_subqueryscan (SubqueryScanPath *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_functionscan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_tablefuncscan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_valuesscan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_ctescan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_namedtuplestorescan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_resultscan (Path *path, PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info)
 
void cost_recursive_union (Path *runion, Path *nrterm, Path *rterm)
 
static void cost_tuplesort (Cost *startup_cost, Cost *run_cost, double tuples, int width, Cost comparison_cost, int sort_mem, double limit_tuples)
 
void cost_incremental_sort (Path *path, PlannerInfo *root, List *pathkeys, int presorted_keys, Cost input_startup_cost, Cost input_total_cost, double input_tuples, int width, Cost comparison_cost, int sort_mem, double limit_tuples)
 
void cost_sort (Path *path, PlannerInfo *root, List *pathkeys, Cost input_cost, double tuples, int width, Cost comparison_cost, int sort_mem, double limit_tuples)
 
void cost_append (AppendPath *apath)
 
void cost_merge_append (Path *path, PlannerInfo *root, List *pathkeys, int n_streams, Cost input_startup_cost, Cost input_total_cost, double tuples)
 
void cost_material (Path *path, Cost input_startup_cost, Cost input_total_cost, double tuples, int width)
 
void cost_agg (Path *path, PlannerInfo *root, AggStrategy aggstrategy, const AggClauseCosts *aggcosts, int numGroupCols, double numGroups, List *quals, Cost input_startup_cost, Cost input_total_cost, double input_tuples, double input_width)
 
void cost_windowagg (Path *path, PlannerInfo *root, List *windowFuncs, int numPartCols, int numOrderCols, Cost input_startup_cost, Cost input_total_cost, double input_tuples)
 
void cost_group (Path *path, PlannerInfo *root, int numGroupCols, double numGroups, List *quals, Cost input_startup_cost, Cost input_total_cost, double input_tuples)
 
void initial_cost_nestloop (PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, Path *outer_path, Path *inner_path, JoinPathExtraData *extra)
 
void final_cost_nestloop (PlannerInfo *root, NestPath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
 
void initial_cost_mergejoin (PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *mergeclauses, Path *outer_path, Path *inner_path, List *outersortkeys, List *innersortkeys, JoinPathExtraData *extra)
 
void final_cost_mergejoin (PlannerInfo *root, MergePath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
 
void initial_cost_hashjoin (PlannerInfo *root, JoinCostWorkspace *workspace, JoinType jointype, List *hashclauses, Path *outer_path, Path *inner_path, JoinPathExtraData *extra, bool parallel_hash)
 
void final_cost_hashjoin (PlannerInfo *root, HashPath *path, JoinCostWorkspace *workspace, JoinPathExtraData *extra)
 
void cost_subplan (PlannerInfo *root, SubPlan *subplan, Plan *plan)
 
void cost_qual_eval (QualCost *cost, List *quals, PlannerInfo *root)
 
void cost_qual_eval_node (QualCost *cost, Node *qual, PlannerInfo *root)
 
void compute_semi_anti_join_factors (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist, SemiAntiJoinFactors *semifactors)
 
void set_baserel_size_estimates (PlannerInfo *root, RelOptInfo *rel)
 
double get_parameterized_baserel_size (PlannerInfo *root, RelOptInfo *rel, List *param_clauses)
 
void set_joinrel_size_estimates (PlannerInfo *root, RelOptInfo *rel, RelOptInfo *outer_rel, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo, List *restrictlist)
 
double get_parameterized_joinrel_size (PlannerInfo *root, RelOptInfo *rel, Path *outer_path, Path *inner_path, SpecialJoinInfo *sjinfo, List *restrict_clauses)
 
void set_subquery_size_estimates (PlannerInfo *root, RelOptInfo *rel)
 
void set_function_size_estimates (PlannerInfo *root, RelOptInfo *rel)
 
void set_tablefunc_size_estimates (PlannerInfo *root, RelOptInfo *rel)
 
void set_values_size_estimates (PlannerInfo *root, RelOptInfo *rel)
 
void set_cte_size_estimates (PlannerInfo *root, RelOptInfo *rel, double cte_rows)
 
void set_namedtuplestore_size_estimates (PlannerInfo *root, RelOptInfo *rel)
 
void set_result_size_estimates (PlannerInfo *root, RelOptInfo *rel)
 
void set_foreign_size_estimates (PlannerInfo *root, RelOptInfo *rel)
 
PathTargetset_pathtarget_cost_width (PlannerInfo *root, PathTarget *target)
 
double compute_bitmap_pages (PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
 

Variables

double seq_page_cost = DEFAULT_SEQ_PAGE_COST
 
double random_page_cost = DEFAULT_RANDOM_PAGE_COST
 
double cpu_tuple_cost = DEFAULT_CPU_TUPLE_COST
 
double cpu_index_tuple_cost = DEFAULT_CPU_INDEX_TUPLE_COST
 
double cpu_operator_cost = DEFAULT_CPU_OPERATOR_COST
 
double parallel_tuple_cost = DEFAULT_PARALLEL_TUPLE_COST
 
double parallel_setup_cost = DEFAULT_PARALLEL_SETUP_COST
 
int effective_cache_size = DEFAULT_EFFECTIVE_CACHE_SIZE
 
Cost disable_cost = 1.0e10
 
int max_parallel_workers_per_gather = 2
 
bool enable_seqscan = true
 
bool enable_indexscan = true
 
bool enable_indexonlyscan = true
 
bool enable_bitmapscan = true
 
bool enable_tidscan = true
 
bool enable_sort = true
 
bool enable_incrementalsort = true
 
bool enable_hashagg = true
 
bool enable_hashagg_disk = true
 
bool enable_groupingsets_hash_disk = false
 
bool enable_nestloop = true
 
bool enable_material = true
 
bool enable_mergejoin = true
 
bool enable_hashjoin = true
 
bool enable_gathermerge = true
 
bool enable_partitionwise_join = false
 
bool enable_partitionwise_aggregate = false
 
bool enable_parallel_append = true
 
bool enable_parallel_hash = true
 
bool enable_partition_pruning = true
 

Macro Definition Documentation

◆ APPEND_CPU_COST_MULTIPLIER

#define APPEND_CPU_COST_MULTIPLIER   0.5

Definition at line 108 of file costsize.c.

Referenced by cost_append(), and cost_merge_append().

◆ LOG2

#define LOG2 (   x)    (log(x) / 0.693147180559945)

Definition at line 101 of file costsize.c.

Referenced by cost_gather_merge(), cost_merge_append(), and cost_tuplesort().

Function Documentation

◆ append_nonpartial_cost()

static Cost append_nonpartial_cost ( List subpaths,
int  numpaths,
int  parallel_workers 
)
static

Definition at line 1922 of file costsize.c.

References for_each_cell, i, lfirst, Min, palloc(), subpath(), and Path::total_cost.

Referenced by cost_append().

1923 {
1924  Cost *costarr;
1925  int arrlen;
1926  ListCell *l;
1927  ListCell *cell;
1928  int i;
1929  int path_index;
1930  int min_index;
1931  int max_index;
1932 
1933  if (numpaths == 0)
1934  return 0;
1935 
1936  /*
1937  * Array length is number of workers or number of relevant paths,
1938  * whichever is less.
1939  */
1940  arrlen = Min(parallel_workers, numpaths);
1941  costarr = (Cost *) palloc(sizeof(Cost) * arrlen);
1942 
1943  /* The first few paths will each be claimed by a different worker. */
1944  path_index = 0;
1945  foreach(cell, subpaths)
1946  {
1947  Path *subpath = (Path *) lfirst(cell);
1948 
1949  if (path_index == arrlen)
1950  break;
1951  costarr[path_index++] = subpath->total_cost;
1952  }
1953 
1954  /*
1955  * Since subpaths are sorted by decreasing cost, the last one will have
1956  * the minimum cost.
1957  */
1958  min_index = arrlen - 1;
1959 
1960  /*
1961  * For each of the remaining subpaths, add its cost to the array element
1962  * with minimum cost.
1963  */
1964  for_each_cell(l, subpaths, cell)
1965  {
1966  Path *subpath = (Path *) lfirst(l);
1967  int i;
1968 
1969  /* Consider only the non-partial paths */
1970  if (path_index++ == numpaths)
1971  break;
1972 
1973  costarr[min_index] += subpath->total_cost;
1974 
1975  /* Update the new min cost array index */
1976  for (min_index = i = 0; i < arrlen; i++)
1977  {
1978  if (costarr[i] < costarr[min_index])
1979  min_index = i;
1980  }
1981  }
1982 
1983  /* Return the highest cost from the array */
1984  for (max_index = i = 0; i < arrlen; i++)
1985  {
1986  if (costarr[i] > costarr[max_index])
1987  max_index = i;
1988  }
1989 
1990  return costarr[max_index];
1991 }
#define for_each_cell(cell, lst, initcell)
Definition: pg_list.h:390
#define Min(x, y)
Definition: c.h:920
Cost total_cost
Definition: pathnodes.h:1156
#define lfirst(lc)
Definition: pg_list.h:190
void * palloc(Size size)
Definition: mcxt.c:949
int i
double Cost
Definition: nodes.h:663
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241

◆ approx_tuple_count()

static double approx_tuple_count ( PlannerInfo root,
JoinPath path,
List quals 
)
static

Definition at line 4534 of file costsize.c.

References clamp_row_est(), clause_selectivity(), SpecialJoinInfo::delay_upper_joins, JoinPath::innerjoinpath, JOIN_INNER, SpecialJoinInfo::jointype, lfirst, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, JoinPath::outerjoinpath, Path::parent, RelOptInfo::relids, Path::rows, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, T_SpecialJoinInfo, and SpecialJoinInfo::type.

Referenced by final_cost_hashjoin(), and final_cost_mergejoin().

4535 {
4536  double tuples;
4537  double outer_tuples = path->outerjoinpath->rows;
4538  double inner_tuples = path->innerjoinpath->rows;
4539  SpecialJoinInfo sjinfo;
4540  Selectivity selec = 1.0;
4541  ListCell *l;
4542 
4543  /*
4544  * Make up a SpecialJoinInfo for JOIN_INNER semantics.
4545  */
4546  sjinfo.type = T_SpecialJoinInfo;
4547  sjinfo.min_lefthand = path->outerjoinpath->parent->relids;
4548  sjinfo.min_righthand = path->innerjoinpath->parent->relids;
4549  sjinfo.syn_lefthand = path->outerjoinpath->parent->relids;
4550  sjinfo.syn_righthand = path->innerjoinpath->parent->relids;
4551  sjinfo.jointype = JOIN_INNER;
4552  /* we don't bother trying to make the remaining fields valid */
4553  sjinfo.lhs_strict = false;
4554  sjinfo.delay_upper_joins = false;
4555  sjinfo.semi_can_btree = false;
4556  sjinfo.semi_can_hash = false;
4557  sjinfo.semi_operators = NIL;
4558  sjinfo.semi_rhs_exprs = NIL;
4559 
4560  /* Get the approximate selectivity */
4561  foreach(l, quals)
4562  {
4563  Node *qual = (Node *) lfirst(l);
4564 
4565  /* Note that clause_selectivity will be able to cache its result */
4566  selec *= clause_selectivity(root, qual, 0, JOIN_INNER, &sjinfo);
4567  }
4568 
4569  /* Apply it to the input relation sizes */
4570  tuples = selec * outer_tuples * inner_tuples;
4571 
4572  return clamp_row_est(tuples);
4573 }
#define NIL
Definition: pg_list.h:65
Relids min_righthand
Definition: pathnodes.h:2176
Path * innerjoinpath
Definition: pathnodes.h:1526
Definition: nodes.h:529
double Selectivity
Definition: nodes.h:662
Relids syn_lefthand
Definition: pathnodes.h:2177
Relids syn_righthand
Definition: pathnodes.h:2178
List * semi_rhs_exprs
Definition: pathnodes.h:2186
RelOptInfo * parent
Definition: pathnodes.h:1144
Selectivity clause_selectivity(PlannerInfo *root, Node *clause, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:600
Relids relids
Definition: pathnodes.h:665
Path * outerjoinpath
Definition: pathnodes.h:1525
bool delay_upper_joins
Definition: pathnodes.h:2181
#define lfirst(lc)
Definition: pg_list.h:190
double rows
Definition: pathnodes.h:1154
JoinType jointype
Definition: pathnodes.h:2179
List * semi_operators
Definition: pathnodes.h:2185
double clamp_row_est(double nrows)
Definition: costsize.c:191
Relids min_lefthand
Definition: pathnodes.h:2175

◆ cached_scansel()

static MergeScanSelCache * cached_scansel ( PlannerInfo root,
RestrictInfo rinfo,
PathKey pathkey 
)
static

Definition at line 3363 of file costsize.c.

References RestrictInfo::clause, MergeScanSelCache::collation, EquivalenceClass::ec_collation, lappend(), MergeScanSelCache::leftendsel, MergeScanSelCache::leftstartsel, lfirst, MemoryContextSwitchTo(), mergejoinscansel(), MergeScanSelCache::nulls_first, MergeScanSelCache::opfamily, palloc(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::planner_cxt, MergeScanSelCache::rightendsel, MergeScanSelCache::rightstartsel, RestrictInfo::scansel_cache, and MergeScanSelCache::strategy.

Referenced by initial_cost_mergejoin().

3364 {
3365  MergeScanSelCache *cache;
3366  ListCell *lc;
3367  Selectivity leftstartsel,
3368  leftendsel,
3369  rightstartsel,
3370  rightendsel;
3371  MemoryContext oldcontext;
3372 
3373  /* Do we have this result already? */
3374  foreach(lc, rinfo->scansel_cache)
3375  {
3376  cache = (MergeScanSelCache *) lfirst(lc);
3377  if (cache->opfamily == pathkey->pk_opfamily &&
3378  cache->collation == pathkey->pk_eclass->ec_collation &&
3379  cache->strategy == pathkey->pk_strategy &&
3380  cache->nulls_first == pathkey->pk_nulls_first)
3381  return cache;
3382  }
3383 
3384  /* Nope, do the computation */
3385  mergejoinscansel(root,
3386  (Node *) rinfo->clause,
3387  pathkey->pk_opfamily,
3388  pathkey->pk_strategy,
3389  pathkey->pk_nulls_first,
3390  &leftstartsel,
3391  &leftendsel,
3392  &rightstartsel,
3393  &rightendsel);
3394 
3395  /* Cache the result in suitably long-lived workspace */
3396  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
3397 
3398  cache = (MergeScanSelCache *) palloc(sizeof(MergeScanSelCache));
3399  cache->opfamily = pathkey->pk_opfamily;
3400  cache->collation = pathkey->pk_eclass->ec_collation;
3401  cache->strategy = pathkey->pk_strategy;
3402  cache->nulls_first = pathkey->pk_nulls_first;
3403  cache->leftstartsel = leftstartsel;
3404  cache->leftendsel = leftendsel;
3405  cache->rightstartsel = rightstartsel;
3406  cache->rightendsel = rightendsel;
3407 
3408  rinfo->scansel_cache = lappend(rinfo->scansel_cache, cache);
3409 
3410  MemoryContextSwitchTo(oldcontext);
3411 
3412  return cache;
3413 }
Selectivity leftendsel
Definition: pathnodes.h:2082
void mergejoinscansel(PlannerInfo *root, Node *clause, Oid opfamily, int strategy, bool nulls_first, Selectivity *leftstart, Selectivity *leftend, Selectivity *rightstart, Selectivity *rightend)
Definition: selfuncs.c:2752
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:109
Definition: nodes.h:529
double Selectivity
Definition: nodes.h:662
int pk_strategy
Definition: pathnodes.h:1043
bool pk_nulls_first
Definition: pathnodes.h:1044
Selectivity rightstartsel
Definition: pathnodes.h:2083
List * lappend(List *list, void *datum)
Definition: list.c:321
Expr * clause
Definition: pathnodes.h:1985
#define lfirst(lc)
Definition: pg_list.h:190
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
Oid pk_opfamily
Definition: pathnodes.h:1042
void * palloc(Size size)
Definition: mcxt.c:949
MemoryContext planner_cxt
Definition: pathnodes.h:331
Selectivity rightendsel
Definition: pathnodes.h:2084
List * scansel_cache
Definition: pathnodes.h:2037
Selectivity leftstartsel
Definition: pathnodes.h:2081

◆ calc_joinrel_size_estimate()

static double calc_joinrel_size_estimate ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outer_rel,
RelOptInfo inner_rel,
double  outer_rows,
double  inner_rows,
SpecialJoinInfo sjinfo,
List restrictlist 
)
static

Definition at line 4742 of file costsize.c.

References clamp_row_est(), clauselist_selectivity(), elog, ERROR, get_foreign_key_join_selectivity(), IS_OUTER_JOIN, JOIN_ANTI, JOIN_FULL, JOIN_INNER, JOIN_LEFT, JOIN_SEMI, SpecialJoinInfo::jointype, lappend(), lfirst_node, list_free(), NIL, RelOptInfo::relids, and RINFO_IS_PUSHED_DOWN.

Referenced by get_parameterized_joinrel_size(), and set_joinrel_size_estimates().

4750 {
4751  /* This apparently-useless variable dodges a compiler bug in VS2013: */
4752  List *restrictlist = restrictlist_in;
4753  JoinType jointype = sjinfo->jointype;
4754  Selectivity fkselec;
4755  Selectivity jselec;
4756  Selectivity pselec;
4757  double nrows;
4758 
4759  /*
4760  * Compute joinclause selectivity. Note that we are only considering
4761  * clauses that become restriction clauses at this join level; we are not
4762  * double-counting them because they were not considered in estimating the
4763  * sizes of the component rels.
4764  *
4765  * First, see whether any of the joinclauses can be matched to known FK
4766  * constraints. If so, drop those clauses from the restrictlist, and
4767  * instead estimate their selectivity using FK semantics. (We do this
4768  * without regard to whether said clauses are local or "pushed down".
4769  * Probably, an FK-matching clause could never be seen as pushed down at
4770  * an outer join, since it would be strict and hence would be grounds for
4771  * join strength reduction.) fkselec gets the net selectivity for
4772  * FK-matching clauses, or 1.0 if there are none.
4773  */
4774  fkselec = get_foreign_key_join_selectivity(root,
4775  outer_rel->relids,
4776  inner_rel->relids,
4777  sjinfo,
4778  &restrictlist);
4779 
4780  /*
4781  * For an outer join, we have to distinguish the selectivity of the join's
4782  * own clauses (JOIN/ON conditions) from any clauses that were "pushed
4783  * down". For inner joins we just count them all as joinclauses.
4784  */
4785  if (IS_OUTER_JOIN(jointype))
4786  {
4787  List *joinquals = NIL;
4788  List *pushedquals = NIL;
4789  ListCell *l;
4790 
4791  /* Grovel through the clauses to separate into two lists */
4792  foreach(l, restrictlist)
4793  {
4794  RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
4795 
4796  if (RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
4797  pushedquals = lappend(pushedquals, rinfo);
4798  else
4799  joinquals = lappend(joinquals, rinfo);
4800  }
4801 
4802  /* Get the separate selectivities */
4803  jselec = clauselist_selectivity(root,
4804  joinquals,
4805  0,
4806  jointype,
4807  sjinfo);
4808  pselec = clauselist_selectivity(root,
4809  pushedquals,
4810  0,
4811  jointype,
4812  sjinfo);
4813 
4814  /* Avoid leaking a lot of ListCells */
4815  list_free(joinquals);
4816  list_free(pushedquals);
4817  }
4818  else
4819  {
4820  jselec = clauselist_selectivity(root,
4821  restrictlist,
4822  0,
4823  jointype,
4824  sjinfo);
4825  pselec = 0.0; /* not used, keep compiler quiet */
4826  }
4827 
4828  /*
4829  * Basically, we multiply size of Cartesian product by selectivity.
4830  *
4831  * If we are doing an outer join, take that into account: the joinqual
4832  * selectivity has to be clamped using the knowledge that the output must
4833  * be at least as large as the non-nullable input. However, any
4834  * pushed-down quals are applied after the outer join, so their
4835  * selectivity applies fully.
4836  *
4837  * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the fraction
4838  * of LHS rows that have matches, and we apply that straightforwardly.
4839  */
4840  switch (jointype)
4841  {
4842  case JOIN_INNER:
4843  nrows = outer_rows * inner_rows * fkselec * jselec;
4844  /* pselec not used */
4845  break;
4846  case JOIN_LEFT:
4847  nrows = outer_rows * inner_rows * fkselec * jselec;
4848  if (nrows < outer_rows)
4849  nrows = outer_rows;
4850  nrows *= pselec;
4851  break;
4852  case JOIN_FULL:
4853  nrows = outer_rows * inner_rows * fkselec * jselec;
4854  if (nrows < outer_rows)
4855  nrows = outer_rows;
4856  if (nrows < inner_rows)
4857  nrows = inner_rows;
4858  nrows *= pselec;
4859  break;
4860  case JOIN_SEMI:
4861  nrows = outer_rows * fkselec * jselec;
4862  /* pselec not used */
4863  break;
4864  case JOIN_ANTI:
4865  nrows = outer_rows * (1.0 - fkselec * jselec);
4866  nrows *= pselec;
4867  break;
4868  default:
4869  /* other values not expected here */
4870  elog(ERROR, "unrecognized join type: %d", (int) jointype);
4871  nrows = 0; /* keep compiler quiet */
4872  break;
4873  }
4874 
4875  return clamp_row_est(nrows);
4876 }
#define NIL
Definition: pg_list.h:65
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:745
double Selectivity
Definition: nodes.h:662
JoinType
Definition: nodes.h:696
static Selectivity get_foreign_key_join_selectivity(PlannerInfo *root, Relids outer_relids, Relids inner_relids, SpecialJoinInfo *sjinfo, List **restrictlist)
Definition: costsize.c:4894
#define ERROR
Definition: elog.h:43
#define lfirst_node(type, lc)
Definition: pg_list.h:193
Relids relids
Definition: pathnodes.h:665
List * lappend(List *list, void *datum)
Definition: list.c:321
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2062
JoinType jointype
Definition: pathnodes.h:2179
void list_free(List *list)
Definition: list.c:1376
#define elog(elevel,...)
Definition: elog.h:214
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:69
double clamp_row_est(double nrows)
Definition: costsize.c:191
Definition: pg_list.h:50

◆ clamp_row_est()

double clamp_row_est ( double  nrows)

◆ compute_bitmap_pages()

double compute_bitmap_pages ( PlannerInfo root,
RelOptInfo baserel,
Path bitmapqual,
int  loop_count,
Cost cost,
double *  tuple 
)

Definition at line 5694 of file costsize.c.

References clamp_row_est(), cost_bitmap_tree_node(), get_indexpath_pages(), index_pages_fetched(), Max, Min, RelOptInfo::pages, T, tbm_calculate_entries(), RelOptInfo::tuples, and work_mem.

Referenced by cost_bitmap_heap_scan(), and create_partial_bitmap_paths().

5696 {
5697  Cost indexTotalCost;
5698  Selectivity indexSelectivity;
5699  double T;
5700  double pages_fetched;
5701  double tuples_fetched;
5702  double heap_pages;
5703  long maxentries;
5704 
5705  /*
5706  * Fetch total cost of obtaining the bitmap, as well as its total
5707  * selectivity.
5708  */
5709  cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
5710 
5711  /*
5712  * Estimate number of main-table pages fetched.
5713  */
5714  tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
5715 
5716  T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
5717 
5718  /*
5719  * For a single scan, the number of heap pages that need to be fetched is
5720  * the same as the Mackert and Lohman formula for the case T <= b (ie, no
5721  * re-reads needed).
5722  */
5723  pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);
5724 
5725  /*
5726  * Calculate the number of pages fetched from the heap. Then based on
5727  * current work_mem estimate get the estimated maxentries in the bitmap.
5728  * (Note that we always do this calculation based on the number of pages
5729  * that would be fetched in a single iteration, even if loop_count > 1.
5730  * That's correct, because only that number of entries will be stored in
5731  * the bitmap at one time.)
5732  */
5733  heap_pages = Min(pages_fetched, baserel->pages);
5734  maxentries = tbm_calculate_entries(work_mem * 1024L);
5735 
5736  if (loop_count > 1)
5737  {
5738  /*
5739  * For repeated bitmap scans, scale up the number of tuples fetched in
5740  * the Mackert and Lohman formula by the number of scans, so that we
5741  * estimate the number of pages fetched by all the scans. Then
5742  * pro-rate for one scan.
5743  */
5744  pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
5745  baserel->pages,
5746  get_indexpath_pages(bitmapqual),
5747  root);
5748  pages_fetched /= loop_count;
5749  }
5750 
5751  if (pages_fetched >= T)
5752  pages_fetched = T;
5753  else
5754  pages_fetched = ceil(pages_fetched);
5755 
5756  if (maxentries < heap_pages)
5757  {
5758  double exact_pages;
5759  double lossy_pages;
5760 
5761  /*
5762  * Crude approximation of the number of lossy pages. Because of the
5763  * way tbm_lossify() is coded, the number of lossy pages increases
5764  * very sharply as soon as we run short of memory; this formula has
5765  * that property and seems to perform adequately in testing, but it's
5766  * possible we could do better somehow.
5767  */
5768  lossy_pages = Max(0, heap_pages - maxentries / 2);
5769  exact_pages = heap_pages - lossy_pages;
5770 
5771  /*
5772  * If there are lossy pages then recompute the number of tuples
5773  * processed by the bitmap heap node. We assume here that the chance
5774  * of a given tuple coming from an exact page is the same as the
5775  * chance that a given page is exact. This might not be true, but
5776  * it's not clear how we can do any better.
5777  */
5778  if (lossy_pages > 0)
5779  tuples_fetched =
5780  clamp_row_est(indexSelectivity *
5781  (exact_pages / heap_pages) * baserel->tuples +
5782  (lossy_pages / heap_pages) * baserel->tuples);
5783  }
5784 
5785  if (cost)
5786  *cost = indexTotalCost;
5787  if (tuple)
5788  *tuple = tuples_fetched;
5789 
5790  return pages_fetched;
5791 }
double tuples
Definition: pathnodes.h:705
#define Min(x, y)
Definition: c.h:920
double Selectivity
Definition: nodes.h:662
static const uint32 T[65]
Definition: md5.c:101
int work_mem
Definition: globals.c:121
#define Max(x, y)
Definition: c.h:914
BlockNumber pages
Definition: pathnodes.h:704
static double get_indexpath_pages(Path *bitmapqual)
Definition: costsize.c:894
long tbm_calculate_entries(double maxbytes)
Definition: tidbitmap.c:1545
double clamp_row_est(double nrows)
Definition: costsize.c:191
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:829
double Cost
Definition: nodes.h:663
void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec)
Definition: costsize.c:1045

◆ compute_semi_anti_join_factors()

void compute_semi_anti_join_factors ( PlannerInfo root,
RelOptInfo joinrel,
RelOptInfo outerrel,
RelOptInfo innerrel,
JoinType  jointype,
SpecialJoinInfo sjinfo,
List restrictlist,
SemiAntiJoinFactors semifactors 
)

Definition at line 4333 of file costsize.c.

References clauselist_selectivity(), SpecialJoinInfo::delay_upper_joins, IS_OUTER_JOIN, JOIN_ANTI, JOIN_INNER, JOIN_SEMI, SpecialJoinInfo::jointype, lappend(), lfirst_node, SpecialJoinInfo::lhs_strict, list_free(), SemiAntiJoinFactors::match_count, Max, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SemiAntiJoinFactors::outer_match_frac, RelOptInfo::relids, RINFO_IS_PUSHED_DOWN, RelOptInfo::rows, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, T_SpecialJoinInfo, and SpecialJoinInfo::type.

Referenced by add_paths_to_joinrel().

4341 {
4342  Selectivity jselec;
4343  Selectivity nselec;
4344  Selectivity avgmatch;
4345  SpecialJoinInfo norm_sjinfo;
4346  List *joinquals;
4347  ListCell *l;
4348 
4349  /*
4350  * In an ANTI join, we must ignore clauses that are "pushed down", since
4351  * those won't affect the match logic. In a SEMI join, we do not
4352  * distinguish joinquals from "pushed down" quals, so just use the whole
4353  * restrictinfo list. For other outer join types, we should consider only
4354  * non-pushed-down quals, so that this devolves to an IS_OUTER_JOIN check.
4355  */
4356  if (IS_OUTER_JOIN(jointype))
4357  {
4358  joinquals = NIL;
4359  foreach(l, restrictlist)
4360  {
4361  RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
4362 
4363  if (!RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
4364  joinquals = lappend(joinquals, rinfo);
4365  }
4366  }
4367  else
4368  joinquals = restrictlist;
4369 
4370  /*
4371  * Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses.
4372  */
4373  jselec = clauselist_selectivity(root,
4374  joinquals,
4375  0,
4376  (jointype == JOIN_ANTI) ? JOIN_ANTI : JOIN_SEMI,
4377  sjinfo);
4378 
4379  /*
4380  * Also get the normal inner-join selectivity of the join clauses.
4381  */
4382  norm_sjinfo.type = T_SpecialJoinInfo;
4383  norm_sjinfo.min_lefthand = outerrel->relids;
4384  norm_sjinfo.min_righthand = innerrel->relids;
4385  norm_sjinfo.syn_lefthand = outerrel->relids;
4386  norm_sjinfo.syn_righthand = innerrel->relids;
4387  norm_sjinfo.jointype = JOIN_INNER;
4388  /* we don't bother trying to make the remaining fields valid */
4389  norm_sjinfo.lhs_strict = false;
4390  norm_sjinfo.delay_upper_joins = false;
4391  norm_sjinfo.semi_can_btree = false;
4392  norm_sjinfo.semi_can_hash = false;
4393  norm_sjinfo.semi_operators = NIL;
4394  norm_sjinfo.semi_rhs_exprs = NIL;
4395 
4396  nselec = clauselist_selectivity(root,
4397  joinquals,
4398  0,
4399  JOIN_INNER,
4400  &norm_sjinfo);
4401 
4402  /* Avoid leaking a lot of ListCells */
4403  if (IS_OUTER_JOIN(jointype))
4404  list_free(joinquals);
4405 
4406  /*
4407  * jselec can be interpreted as the fraction of outer-rel rows that have
4408  * any matches (this is true for both SEMI and ANTI cases). And nselec is
4409  * the fraction of the Cartesian product that matches. So, the average
4410  * number of matches for each outer-rel row that has at least one match is
4411  * nselec * inner_rows / jselec.
4412  *
4413  * Note: it is correct to use the inner rel's "rows" count here, even
4414  * though we might later be considering a parameterized inner path with
4415  * fewer rows. This is because we have included all the join clauses in
4416  * the selectivity estimate.
4417  */
4418  if (jselec > 0) /* protect against zero divide */
4419  {
4420  avgmatch = nselec * innerrel->rows / jselec;
4421  /* Clamp to sane range */
4422  avgmatch = Max(1.0, avgmatch);
4423  }
4424  else
4425  avgmatch = 1.0;
4426 
4427  semifactors->outer_match_frac = jselec;
4428  semifactors->match_count = avgmatch;
4429 }
#define NIL
Definition: pg_list.h:65
Relids min_righthand
Definition: pathnodes.h:2176
Selectivity outer_match_frac
Definition: pathnodes.h:2405
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:745
double Selectivity
Definition: nodes.h:662
Relids syn_lefthand
Definition: pathnodes.h:2177
Relids syn_righthand
Definition: pathnodes.h:2178
List * semi_rhs_exprs
Definition: pathnodes.h:2186
#define lfirst_node(type, lc)
Definition: pg_list.h:193
Relids relids
Definition: pathnodes.h:665
List * lappend(List *list, void *datum)
Definition: list.c:321
bool delay_upper_joins
Definition: pathnodes.h:2181
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2062
double rows
Definition: pathnodes.h:668
#define Max(x, y)
Definition: c.h:914
JoinType jointype
Definition: pathnodes.h:2179
Selectivity match_count
Definition: pathnodes.h:2406
List * semi_operators
Definition: pathnodes.h:2185
void list_free(List *list)
Definition: list.c:1376
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:69
Definition: pg_list.h:50
Relids min_lefthand
Definition: pathnodes.h:2175

◆ cost_agg()

void cost_agg ( Path path,
PlannerInfo root,
AggStrategy  aggstrategy,
const AggClauseCosts aggcosts,
int  numGroupCols,
double  numGroups,
List quals,
Cost  input_startup_cost,
Cost  input_total_cost,
double  input_tuples,
double  input_width 
)

Definition at line 2274 of file costsize.c.

References AGG_HASHED, AGG_MIXED, AGG_PLAIN, AGG_SORTED, Assert, clamp_row_est(), clauselist_selectivity(), cost_qual_eval(), cpu_operator_cost, cpu_tuple_cost, disable_cost, enable_hashagg, AggClauseCosts::finalCost, hash_agg_entry_size(), hash_agg_set_limits(), JOIN_INNER, Max, MemSet, AggClauseCosts::numAggs, QualCost::per_tuple, random_page_cost, relation_byte_size(), Path::rows, seq_page_cost, QualCost::startup, Path::startup_cost, Path::total_cost, AggClauseCosts::transCost, and AggClauseCosts::transitionSpace.

Referenced by choose_hashed_setop(), create_agg_path(), create_groupingsets_path(), and create_unique_path().

2280 {
2281  double output_tuples;
2282  Cost startup_cost;
2283  Cost total_cost;
2284  AggClauseCosts dummy_aggcosts;
2285 
2286  /* Use all-zero per-aggregate costs if NULL is passed */
2287  if (aggcosts == NULL)
2288  {
2289  Assert(aggstrategy == AGG_HASHED);
2290  MemSet(&dummy_aggcosts, 0, sizeof(AggClauseCosts));
2291  aggcosts = &dummy_aggcosts;
2292  }
2293 
2294  /*
2295  * The transCost.per_tuple component of aggcosts should be charged once
2296  * per input tuple, corresponding to the costs of evaluating the aggregate
2297  * transfns and their input expressions. The finalCost.per_tuple component
2298  * is charged once per output tuple, corresponding to the costs of
2299  * evaluating the finalfns. Startup costs are of course charged but once.
2300  *
2301  * If we are grouping, we charge an additional cpu_operator_cost per
2302  * grouping column per input tuple for grouping comparisons.
2303  *
2304  * We will produce a single output tuple if not grouping, and a tuple per
2305  * group otherwise. We charge cpu_tuple_cost for each output tuple.
2306  *
2307  * Note: in this cost model, AGG_SORTED and AGG_HASHED have exactly the
2308  * same total CPU cost, but AGG_SORTED has lower startup cost. If the
2309  * input path is already sorted appropriately, AGG_SORTED should be
2310  * preferred (since it has no risk of memory overflow). This will happen
2311  * as long as the computed total costs are indeed exactly equal --- but if
2312  * there's roundoff error we might do the wrong thing. So be sure that
2313  * the computations below form the same intermediate values in the same
2314  * order.
2315  */
2316  if (aggstrategy == AGG_PLAIN)
2317  {
2318  startup_cost = input_total_cost;
2319  startup_cost += aggcosts->transCost.startup;
2320  startup_cost += aggcosts->transCost.per_tuple * input_tuples;
2321  startup_cost += aggcosts->finalCost.startup;
2322  startup_cost += aggcosts->finalCost.per_tuple;
2323  /* we aren't grouping */
2324  total_cost = startup_cost + cpu_tuple_cost;
2325  output_tuples = 1;
2326  }
2327  else if (aggstrategy == AGG_SORTED || aggstrategy == AGG_MIXED)
2328  {
2329  /* Here we are able to deliver output on-the-fly */
2330  startup_cost = input_startup_cost;
2331  total_cost = input_total_cost;
2332  if (aggstrategy == AGG_MIXED && !enable_hashagg)
2333  {
2334  startup_cost += disable_cost;
2335  total_cost += disable_cost;
2336  }
2337  /* calcs phrased this way to match HASHED case, see note above */
2338  total_cost += aggcosts->transCost.startup;
2339  total_cost += aggcosts->transCost.per_tuple * input_tuples;
2340  total_cost += (cpu_operator_cost * numGroupCols) * input_tuples;
2341  total_cost += aggcosts->finalCost.startup;
2342  total_cost += aggcosts->finalCost.per_tuple * numGroups;
2343  total_cost += cpu_tuple_cost * numGroups;
2344  output_tuples = numGroups;
2345  }
2346  else
2347  {
2348  /* must be AGG_HASHED */
2349  startup_cost = input_total_cost;
2350  if (!enable_hashagg)
2351  startup_cost += disable_cost;
2352  startup_cost += aggcosts->transCost.startup;
2353  startup_cost += aggcosts->transCost.per_tuple * input_tuples;
2354  /* cost of computing hash value */
2355  startup_cost += (cpu_operator_cost * numGroupCols) * input_tuples;
2356  startup_cost += aggcosts->finalCost.startup;
2357 
2358  total_cost = startup_cost;
2359  total_cost += aggcosts->finalCost.per_tuple * numGroups;
2360  /* cost of retrieving from hash table */
2361  total_cost += cpu_tuple_cost * numGroups;
2362  output_tuples = numGroups;
2363  }
2364 
2365  /*
2366  * Add the disk costs of hash aggregation that spills to disk.
2367  *
2368  * Groups that go into the hash table stay in memory until finalized,
2369  * so spilling and reprocessing tuples doesn't incur additional
2370  * invocations of transCost or finalCost. Furthermore, the computed
2371  * hash value is stored with the spilled tuples, so we don't incur
2372  * extra invocations of the hash function.
2373  *
2374  * Hash Agg begins returning tuples after the first batch is
2375  * complete. Accrue writes (spilled tuples) to startup_cost and to
2376  * total_cost; accrue reads only to total_cost.
2377  */
2378  if (aggstrategy == AGG_HASHED || aggstrategy == AGG_MIXED)
2379  {
2380  double pages;
2381  double pages_written = 0.0;
2382  double pages_read = 0.0;
2383  double hashentrysize;
2384  double nbatches;
2385  Size mem_limit;
2386  uint64 ngroups_limit;
2387  int num_partitions;
2388  int depth;
2389 
2390  /*
2391  * Estimate number of batches based on the computed limits. If less
2392  * than or equal to one, all groups are expected to fit in memory;
2393  * otherwise we expect to spill.
2394  */
2395  hashentrysize = hash_agg_entry_size(
2396  aggcosts->numAggs, input_width, aggcosts->transitionSpace);
2397  hash_agg_set_limits(hashentrysize, numGroups, 0, &mem_limit,
2398  &ngroups_limit, &num_partitions);
2399 
2400  nbatches = Max( (numGroups * hashentrysize) / mem_limit,
2401  numGroups / ngroups_limit );
2402 
2403  nbatches = Max(ceil(nbatches), 1.0);
2404  num_partitions = Max(num_partitions, 2);
2405 
2406  /*
2407  * The number of partitions can change at different levels of
2408  * recursion; but for the purposes of this calculation assume it stays
2409  * constant.
2410  */
2411  depth = ceil( log(nbatches) / log(num_partitions) );
2412 
2413  /*
2414  * Estimate number of pages read and written. For each level of
2415  * recursion, a tuple must be written and then later read.
2416  */
2417  pages = relation_byte_size(input_tuples, input_width) / BLCKSZ;
2418  pages_written = pages_read = pages * depth;
2419 
2420  startup_cost += pages_written * random_page_cost;
2421  total_cost += pages_written * random_page_cost;
2422  total_cost += pages_read * seq_page_cost;
2423  }
2424 
2425  /*
2426  * If there are quals (HAVING quals), account for their cost and
2427  * selectivity.
2428  */
2429  if (quals)
2430  {
2431  QualCost qual_cost;
2432 
2433  cost_qual_eval(&qual_cost, quals, root);
2434  startup_cost += qual_cost.startup;
2435  total_cost += qual_cost.startup + output_tuples * qual_cost.per_tuple;
2436 
2437  output_tuples = clamp_row_est(output_tuples *
2439  quals,
2440  0,
2441  JOIN_INNER,
2442  NULL));
2443  }
2444 
2445  path->rows = output_tuples;
2446  path->startup_cost = startup_cost;
2447  path->total_cost = total_cost;
2448 }
QualCost finalCost
Definition: pathnodes.h:63
#define MemSet(start, val, len)
Definition: c.h:971
QualCost transCost
Definition: pathnodes.h:62
Cost startup
Definition: pathnodes.h:45
double random_page_cost
Definition: costsize.c:112
Size hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace)
Definition: nodeAgg.c:1648
Cost per_tuple
Definition: pathnodes.h:46
void cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
Definition: costsize.c:4005
Cost startup_cost
Definition: pathnodes.h:1155
Cost disable_cost
Definition: costsize.c:121
void hash_agg_set_limits(double hashentrysize, uint64 input_groups, int used_bits, Size *mem_limit, uint64 *ngroups_limit, int *num_partitions)
Definition: nodeAgg.c:1745
double cpu_operator_cost
Definition: costsize.c:115
static double relation_byte_size(double tuples, int width)
Definition: costsize.c:5640
Cost total_cost
Definition: pathnodes.h:1156
#define Max(x, y)
Definition: c.h:914
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
size_t Size
Definition: c.h:466
double cpu_tuple_cost
Definition: costsize.c:113
bool enable_hashagg
Definition: costsize.c:132
Size transitionSpace
Definition: pathnodes.h:64
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:69
double clamp_row_est(double nrows)
Definition: costsize.c:191
double seq_page_cost
Definition: costsize.c:111
double Cost
Definition: nodes.h:663

◆ cost_append()

void cost_append ( AppendPath apath)

Definition at line 1998 of file costsize.c.

References APPEND_CPU_COST_MULTIPLIER, append_nonpartial_cost(), Assert, clamp_row_est(), cost_sort(), cpu_tuple_cost, AppendPath::first_partial_path, get_parallel_divisor(), i, lfirst, AppendPath::limit_tuples, linitial, Min, NIL, Path::parallel_aware, Path::parallel_workers, AppendPath::path, Path::pathkeys, pathkeys_contained_in(), Path::pathtarget, Path::rows, Path::startup_cost, subpath(), AppendPath::subpaths, Path::total_cost, PathTarget::width, and work_mem.

Referenced by create_append_path().

1999 {
2000  ListCell *l;
2001 
2002  apath->path.startup_cost = 0;
2003  apath->path.total_cost = 0;
2004  apath->path.rows = 0;
2005 
2006  if (apath->subpaths == NIL)
2007  return;
2008 
2009  if (!apath->path.parallel_aware)
2010  {
2011  List *pathkeys = apath->path.pathkeys;
2012 
2013  if (pathkeys == NIL)
2014  {
2015  Path *subpath = (Path *) linitial(apath->subpaths);
2016 
2017  /*
2018  * For an unordered, non-parallel-aware Append we take the startup
2019  * cost as the startup cost of the first subpath.
2020  */
2021  apath->path.startup_cost = subpath->startup_cost;
2022 
2023  /* Compute rows and costs as sums of subplan rows and costs. */
2024  foreach(l, apath->subpaths)
2025  {
2026  Path *subpath = (Path *) lfirst(l);
2027 
2028  apath->path.rows += subpath->rows;
2029  apath->path.total_cost += subpath->total_cost;
2030  }
2031  }
2032  else
2033  {
2034  /*
2035  * For an ordered, non-parallel-aware Append we take the startup
2036  * cost as the sum of the subpath startup costs. This ensures
2037  * that we don't underestimate the startup cost when a query's
2038  * LIMIT is such that several of the children have to be run to
2039  * satisfy it. This might be overkill --- another plausible hack
2040  * would be to take the Append's startup cost as the maximum of
2041  * the child startup costs. But we don't want to risk believing
2042  * that an ORDER BY LIMIT query can be satisfied at small cost
2043  * when the first child has small startup cost but later ones
2044  * don't. (If we had the ability to deal with nonlinear cost
2045  * interpolation for partial retrievals, we would not need to be
2046  * so conservative about this.)
2047  *
2048  * This case is also different from the above in that we have to
2049  * account for possibly injecting sorts into subpaths that aren't
2050  * natively ordered.
2051  */
2052  foreach(l, apath->subpaths)
2053  {
2054  Path *subpath = (Path *) lfirst(l);
2055  Path sort_path; /* dummy for result of cost_sort */
2056 
2057  if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
2058  {
2059  /*
2060  * We'll need to insert a Sort node, so include costs for
2061  * that. We can use the parent's LIMIT if any, since we
2062  * certainly won't pull more than that many tuples from
2063  * any child.
2064  */
2065  cost_sort(&sort_path,
2066  NULL, /* doesn't currently need root */
2067  pathkeys,
2068  subpath->total_cost,
2069  subpath->rows,
2070  subpath->pathtarget->width,
2071  0.0,
2072  work_mem,
2073  apath->limit_tuples);
2074  subpath = &sort_path;
2075  }
2076 
2077  apath->path.rows += subpath->rows;
2078  apath->path.startup_cost += subpath->startup_cost;
2079  apath->path.total_cost += subpath->total_cost;
2080  }
2081  }
2082  }
2083  else /* parallel-aware */
2084  {
2085  int i = 0;
2086  double parallel_divisor = get_parallel_divisor(&apath->path);
2087 
2088  /* Parallel-aware Append never produces ordered output. */
2089  Assert(apath->path.pathkeys == NIL);
2090 
2091  /* Calculate startup cost. */
2092  foreach(l, apath->subpaths)
2093  {
2094  Path *subpath = (Path *) lfirst(l);
2095 
2096  /*
2097  * Append will start returning tuples when the child node having
2098  * lowest startup cost is done setting up. We consider only the
2099  * first few subplans that immediately get a worker assigned.
2100  */
2101  if (i == 0)
2102  apath->path.startup_cost = subpath->startup_cost;
2103  else if (i < apath->path.parallel_workers)
2104  apath->path.startup_cost = Min(apath->path.startup_cost,
2105  subpath->startup_cost);
2106 
2107  /*
2108  * Apply parallel divisor to subpaths. Scale the number of rows
2109  * for each partial subpath based on the ratio of the parallel
2110  * divisor originally used for the subpath to the one we adopted.
2111  * Also add the cost of partial paths to the total cost, but
2112  * ignore non-partial paths for now.
2113  */
2114  if (i < apath->first_partial_path)
2115  apath->path.rows += subpath->rows / parallel_divisor;
2116  else
2117  {
2118  double subpath_parallel_divisor;
2119 
2120  subpath_parallel_divisor = get_parallel_divisor(subpath);
2121  apath->path.rows += subpath->rows * (subpath_parallel_divisor /
2122  parallel_divisor);
2123  apath->path.total_cost += subpath->total_cost;
2124  }
2125 
2126  apath->path.rows = clamp_row_est(apath->path.rows);
2127 
2128  i++;
2129  }
2130 
2131  /* Add cost for non-partial subpaths. */
2132  apath->path.total_cost +=
2134  apath->first_partial_path,
2135  apath->path.parallel_workers);
2136  }
2137 
2138  /*
2139  * Although Append does not do any selection or projection, it's not free;
2140  * add a small per-tuple overhead.
2141  */
2142  apath->path.total_cost +=
2144 }
#define NIL
Definition: pg_list.h:65
PathTarget * pathtarget
Definition: pathnodes.h:1145
double limit_tuples
Definition: pathnodes.h:1407
#define Min(x, y)
Definition: c.h:920
int parallel_workers
Definition: pathnodes.h:1151
static Cost append_nonpartial_cost(List *subpaths, int numpaths, int parallel_workers)
Definition: costsize.c:1922
int first_partial_path
Definition: pathnodes.h:1406
List * subpaths
Definition: pathnodes.h:1404
#define linitial(l)
Definition: pg_list.h:195
Cost startup_cost
Definition: pathnodes.h:1155
static double get_parallel_divisor(Path *path)
Definition: costsize.c:5661
bool pathkeys_contained_in(List *keys1, List *keys2)
Definition: pathkeys.c:324
#define APPEND_CPU_COST_MULTIPLIER
Definition: costsize.c:108
void cost_sort(Path *path, PlannerInfo *root, List *pathkeys, Cost input_cost, double tuples, int width, Cost comparison_cost, int sort_mem, double limit_tuples)
Definition: costsize.c:1891
int work_mem
Definition: globals.c:121
Cost total_cost
Definition: pathnodes.h:1156
List * pathkeys
Definition: pathnodes.h:1158
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
double rows
Definition: pathnodes.h:1154
double cpu_tuple_cost
Definition: costsize.c:113
int i
bool parallel_aware
Definition: pathnodes.h:1149
double clamp_row_est(double nrows)
Definition: costsize.c:191
Definition: pg_list.h:50
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241

◆ cost_bitmap_and_node()

void cost_bitmap_and_node ( BitmapAndPath path,
PlannerInfo root 
)

Definition at line 1088 of file costsize.c.

References BitmapAndPath::bitmapquals, BitmapAndPath::bitmapselectivity, cost_bitmap_tree_node(), cpu_operator_cost, lfirst, list_head(), BitmapAndPath::path, Path::rows, Path::startup_cost, subpath(), and Path::total_cost.

Referenced by bitmap_and_cost_est(), and create_bitmap_and_path().

1089 {
1090  Cost totalCost;
1091  Selectivity selec;
1092  ListCell *l;
1093 
1094  /*
1095  * We estimate AND selectivity on the assumption that the inputs are
1096  * independent. This is probably often wrong, but we don't have the info
1097  * to do better.
1098  *
1099  * The runtime cost of the BitmapAnd itself is estimated at 100x
1100  * cpu_operator_cost for each tbm_intersect needed. Probably too small,
1101  * definitely too simplistic?
1102  */
1103  totalCost = 0.0;
1104  selec = 1.0;
1105  foreach(l, path->bitmapquals)
1106  {
1107  Path *subpath = (Path *) lfirst(l);
1108  Cost subCost;
1109  Selectivity subselec;
1110 
1111  cost_bitmap_tree_node(subpath, &subCost, &subselec);
1112 
1113  selec *= subselec;
1114 
1115  totalCost += subCost;
1116  if (l != list_head(path->bitmapquals))
1117  totalCost += 100.0 * cpu_operator_cost;
1118  }
1119  path->bitmapselectivity = selec;
1120  path->path.rows = 0; /* per above, not used */
1121  path->path.startup_cost = totalCost;
1122  path->path.total_cost = totalCost;
1123 }
double Selectivity
Definition: nodes.h:662
Selectivity bitmapselectivity
Definition: pathnodes.h:1293
List * bitmapquals
Definition: pathnodes.h:1292
Cost startup_cost
Definition: pathnodes.h:1155
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
double cpu_operator_cost
Definition: costsize.c:115
Cost total_cost
Definition: pathnodes.h:1156
#define lfirst(lc)
Definition: pg_list.h:190
double rows
Definition: pathnodes.h:1154
double Cost
Definition: nodes.h:663
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241
void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec)
Definition: costsize.c:1045

◆ cost_bitmap_heap_scan()

void cost_bitmap_heap_scan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info,
Path bitmapqual,
double  loop_count 
)

Definition at line 944 of file costsize.c.

References Assert, clamp_row_est(), compute_bitmap_pages(), PathTarget::cost, cpu_tuple_cost, disable_cost, enable_bitmapscan, get_parallel_divisor(), get_restriction_qual_cost(), get_tablespace_page_costs(), IsA, RelOptInfo::pages, Path::parallel_workers, Path::pathtarget, QualCost::per_tuple, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::reltablespace, RelOptInfo::rows, Path::rows, RTE_RELATION, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, T, and Path::total_cost.

Referenced by bitmap_and_cost_est(), bitmap_scan_cost_est(), and create_bitmap_heap_path().

947 {
948  Cost startup_cost = 0;
949  Cost run_cost = 0;
950  Cost indexTotalCost;
951  QualCost qpqual_cost;
952  Cost cpu_per_tuple;
953  Cost cost_per_page;
954  Cost cpu_run_cost;
955  double tuples_fetched;
956  double pages_fetched;
957  double spc_seq_page_cost,
958  spc_random_page_cost;
959  double T;
960 
961  /* Should only be applied to base relations */
962  Assert(IsA(baserel, RelOptInfo));
963  Assert(baserel->relid > 0);
964  Assert(baserel->rtekind == RTE_RELATION);
965 
966  /* Mark the path with the correct row estimate */
967  if (param_info)
968  path->rows = param_info->ppi_rows;
969  else
970  path->rows = baserel->rows;
971 
972  if (!enable_bitmapscan)
973  startup_cost += disable_cost;
974 
975  pages_fetched = compute_bitmap_pages(root, baserel, bitmapqual,
976  loop_count, &indexTotalCost,
977  &tuples_fetched);
978 
979  startup_cost += indexTotalCost;
980  T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
981 
982  /* Fetch estimated page costs for tablespace containing table. */
984  &spc_random_page_cost,
985  &spc_seq_page_cost);
986 
987  /*
988  * For small numbers of pages we should charge spc_random_page_cost
989  * apiece, while if nearly all the table's pages are being read, it's more
990  * appropriate to charge spc_seq_page_cost apiece. The effect is
991  * nonlinear, too. For lack of a better idea, interpolate like this to
992  * determine the cost per page.
993  */
994  if (pages_fetched >= 2.0)
995  cost_per_page = spc_random_page_cost -
996  (spc_random_page_cost - spc_seq_page_cost)
997  * sqrt(pages_fetched / T);
998  else
999  cost_per_page = spc_random_page_cost;
1000 
1001  run_cost += pages_fetched * cost_per_page;
1002 
1003  /*
1004  * Estimate CPU costs per tuple.
1005  *
1006  * Often the indexquals don't need to be rechecked at each tuple ... but
1007  * not always, especially not if there are enough tuples involved that the
1008  * bitmaps become lossy. For the moment, just assume they will be
1009  * rechecked always. This means we charge the full freight for all the
1010  * scan clauses.
1011  */
1012  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1013 
1014  startup_cost += qpqual_cost.startup;
1015  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1016  cpu_run_cost = cpu_per_tuple * tuples_fetched;
1017 
1018  /* Adjust costing for parallelism, if used. */
1019  if (path->parallel_workers > 0)
1020  {
1021  double parallel_divisor = get_parallel_divisor(path);
1022 
1023  /* The CPU cost is divided among all the workers. */
1024  cpu_run_cost /= parallel_divisor;
1025 
1026  path->rows = clamp_row_est(path->rows / parallel_divisor);
1027  }
1028 
1029 
1030  run_cost += cpu_run_cost;
1031 
1032  /* tlist eval costs are paid per output row, not per tuple scanned */
1033  startup_cost += path->pathtarget->cost.startup;
1034  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1035 
1036  path->startup_cost = startup_cost;
1037  path->total_cost = startup_cost + run_cost;
1038 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
PathTarget * pathtarget
Definition: pathnodes.h:1145
Oid reltablespace
Definition: pathnodes.h:694
int parallel_workers
Definition: pathnodes.h:1151
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
Cost disable_cost
Definition: costsize.c:121
static const uint32 T[65]
Definition: md5.c:101
static double get_parallel_divisor(Path *path)
Definition: costsize.c:5661
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:693
bool enable_bitmapscan
Definition: costsize.c:128
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
BlockNumber pages
Definition: pathnodes.h:704
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
double clamp_row_est(double nrows)
Definition: costsize.c:191
double compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual, int loop_count, Cost *cost, double *tuple)
Definition: costsize.c:5694
double Cost
Definition: nodes.h:663

◆ cost_bitmap_or_node()

void cost_bitmap_or_node ( BitmapOrPath path,
PlannerInfo root 
)

Definition at line 1132 of file costsize.c.

References BitmapOrPath::bitmapquals, BitmapOrPath::bitmapselectivity, cost_bitmap_tree_node(), cpu_operator_cost, IsA, lfirst, list_head(), Min, BitmapOrPath::path, Path::rows, Path::startup_cost, subpath(), and Path::total_cost.

Referenced by create_bitmap_or_path().

1133 {
1134  Cost totalCost;
1135  Selectivity selec;
1136  ListCell *l;
1137 
1138  /*
1139  * We estimate OR selectivity on the assumption that the inputs are
1140  * non-overlapping, since that's often the case in "x IN (list)" type
1141  * situations. Of course, we clamp to 1.0 at the end.
1142  *
1143  * The runtime cost of the BitmapOr itself is estimated at 100x
1144  * cpu_operator_cost for each tbm_union needed. Probably too small,
1145  * definitely too simplistic? We are aware that the tbm_unions are
1146  * optimized out when the inputs are BitmapIndexScans.
1147  */
1148  totalCost = 0.0;
1149  selec = 0.0;
1150  foreach(l, path->bitmapquals)
1151  {
1152  Path *subpath = (Path *) lfirst(l);
1153  Cost subCost;
1154  Selectivity subselec;
1155 
1156  cost_bitmap_tree_node(subpath, &subCost, &subselec);
1157 
1158  selec += subselec;
1159 
1160  totalCost += subCost;
1161  if (l != list_head(path->bitmapquals) &&
1162  !IsA(subpath, IndexPath))
1163  totalCost += 100.0 * cpu_operator_cost;
1164  }
1165  path->bitmapselectivity = Min(selec, 1.0);
1166  path->path.rows = 0; /* per above, not used */
1167  path->path.startup_cost = totalCost;
1168  path->path.total_cost = totalCost;
1169 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
#define Min(x, y)
Definition: c.h:920
double Selectivity
Definition: nodes.h:662
List * bitmapquals
Definition: pathnodes.h:1305
Cost startup_cost
Definition: pathnodes.h:1155
static ListCell * list_head(const List *l)
Definition: pg_list.h:125
double cpu_operator_cost
Definition: costsize.c:115
Selectivity bitmapselectivity
Definition: pathnodes.h:1306
Cost total_cost
Definition: pathnodes.h:1156
#define lfirst(lc)
Definition: pg_list.h:190
double rows
Definition: pathnodes.h:1154
double Cost
Definition: nodes.h:663
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241
void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec)
Definition: costsize.c:1045

◆ cost_bitmap_tree_node()

void cost_bitmap_tree_node ( Path path,
Cost cost,
Selectivity selec 
)

Definition at line 1045 of file costsize.c.

References cpu_operator_cost, elog, ERROR, IsA, nodeTag, Path::rows, and Path::total_cost.

Referenced by choose_bitmap_and(), compute_bitmap_pages(), cost_bitmap_and_node(), cost_bitmap_or_node(), and path_usage_comparator().

1046 {
1047  if (IsA(path, IndexPath))
1048  {
1049  *cost = ((IndexPath *) path)->indextotalcost;
1050  *selec = ((IndexPath *) path)->indexselectivity;
1051 
1052  /*
1053  * Charge a small amount per retrieved tuple to reflect the costs of
1054  * manipulating the bitmap. This is mostly to make sure that a bitmap
1055  * scan doesn't look to be the same cost as an indexscan to retrieve a
1056  * single tuple.
1057  */
1058  *cost += 0.1 * cpu_operator_cost * path->rows;
1059  }
1060  else if (IsA(path, BitmapAndPath))
1061  {
1062  *cost = path->total_cost;
1063  *selec = ((BitmapAndPath *) path)->bitmapselectivity;
1064  }
1065  else if (IsA(path, BitmapOrPath))
1066  {
1067  *cost = path->total_cost;
1068  *selec = ((BitmapOrPath *) path)->bitmapselectivity;
1069  }
1070  else
1071  {
1072  elog(ERROR, "unrecognized node type: %d", nodeTag(path));
1073  *cost = *selec = 0; /* keep compiler quiet */
1074  }
1075 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
#define ERROR
Definition: elog.h:43
double cpu_operator_cost
Definition: costsize.c:115
Cost total_cost
Definition: pathnodes.h:1156
double rows
Definition: pathnodes.h:1154
#define nodeTag(nodeptr)
Definition: nodes.h:534
#define elog(elevel,...)
Definition: elog.h:214

◆ cost_ctescan()

void cost_ctescan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 1502 of file costsize.c.

References Assert, PathTarget::cost, cpu_tuple_cost, get_restriction_qual_cost(), Path::pathtarget, QualCost::per_tuple, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::rows, Path::rows, RTE_CTE, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_ctescan_path(), and create_worktablescan_path().

1504 {
1505  Cost startup_cost = 0;
1506  Cost run_cost = 0;
1507  QualCost qpqual_cost;
1508  Cost cpu_per_tuple;
1509 
1510  /* Should only be applied to base relations that are CTEs */
1511  Assert(baserel->relid > 0);
1512  Assert(baserel->rtekind == RTE_CTE);
1513 
1514  /* Mark the path with the correct row estimate */
1515  if (param_info)
1516  path->rows = param_info->ppi_rows;
1517  else
1518  path->rows = baserel->rows;
1519 
1520  /* Charge one CPU tuple cost per row for tuplestore manipulation */
1521  cpu_per_tuple = cpu_tuple_cost;
1522 
1523  /* Add scanning CPU costs */
1524  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1525 
1526  startup_cost += qpqual_cost.startup;
1527  cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1528  run_cost += cpu_per_tuple * baserel->tuples;
1529 
1530  /* tlist eval costs are paid per output row, not per tuple scanned */
1531  startup_cost += path->pathtarget->cost.startup;
1532  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1533 
1534  path->startup_cost = startup_cost;
1535  path->total_cost = startup_cost + run_cost;
1536 }
PathTarget * pathtarget
Definition: pathnodes.h:1145
double tuples
Definition: pathnodes.h:705
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
Index relid
Definition: pathnodes.h:693
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
double Cost
Definition: nodes.h:663

◆ cost_functionscan()

void cost_functionscan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 1335 of file costsize.c.

References Assert, PathTarget::cost, cost_qual_eval_node(), cpu_tuple_cost, RangeTblEntry::functions, get_restriction_qual_cost(), Path::pathtarget, QualCost::per_tuple, planner_rt_fetch, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::rows, Path::rows, RTE_FUNCTION, RangeTblEntry::rtekind, QualCost::startup, Path::startup_cost, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_functionscan_path().

1337 {
1338  Cost startup_cost = 0;
1339  Cost run_cost = 0;
1340  QualCost qpqual_cost;
1341  Cost cpu_per_tuple;
1342  RangeTblEntry *rte;
1343  QualCost exprcost;
1344 
1345  /* Should only be applied to base relations that are functions */
1346  Assert(baserel->relid > 0);
1347  rte = planner_rt_fetch(baserel->relid, root);
1348  Assert(rte->rtekind == RTE_FUNCTION);
1349 
1350  /* Mark the path with the correct row estimate */
1351  if (param_info)
1352  path->rows = param_info->ppi_rows;
1353  else
1354  path->rows = baserel->rows;
1355 
1356  /*
1357  * Estimate costs of executing the function expression(s).
1358  *
1359  * Currently, nodeFunctionscan.c always executes the functions to
1360  * completion before returning any rows, and caches the results in a
1361  * tuplestore. So the function eval cost is all startup cost, and per-row
1362  * costs are minimal.
1363  *
1364  * XXX in principle we ought to charge tuplestore spill costs if the
1365  * number of rows is large. However, given how phony our rowcount
1366  * estimates for functions tend to be, there's not a lot of point in that
1367  * refinement right now.
1368  */
1369  cost_qual_eval_node(&exprcost, (Node *) rte->functions, root);
1370 
1371  startup_cost += exprcost.startup + exprcost.per_tuple;
1372 
1373  /* Add scanning CPU costs */
1374  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1375 
1376  startup_cost += qpqual_cost.startup;
1377  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1378  run_cost += cpu_per_tuple * baserel->tuples;
1379 
1380  /* tlist eval costs are paid per output row, not per tuple scanned */
1381  startup_cost += path->pathtarget->cost.startup;
1382  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1383 
1384  path->startup_cost = startup_cost;
1385  path->total_cost = startup_cost + run_cost;
1386 }
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4031
PathTarget * pathtarget
Definition: pathnodes.h:1145
double tuples
Definition: pathnodes.h:705
Definition: nodes.h:529
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:373
Index relid
Definition: pathnodes.h:693
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
#define Assert(condition)
Definition: c.h:738
List * functions
Definition: parsenodes.h:1063
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
RTEKind rtekind
Definition: parsenodes.h:976
double Cost
Definition: nodes.h:663

◆ cost_gather()

void cost_gather ( GatherPath path,
PlannerInfo root,
RelOptInfo rel,
ParamPathInfo param_info,
double *  rows 
)

Definition at line 367 of file costsize.c.

References parallel_setup_cost, parallel_tuple_cost, GatherPath::path, ParamPathInfo::ppi_rows, RelOptInfo::rows, Path::rows, Path::startup_cost, GatherPath::subpath, and Path::total_cost.

Referenced by create_gather_path().

370 {
371  Cost startup_cost = 0;
372  Cost run_cost = 0;
373 
374  /* Mark the path with the correct row estimate */
375  if (rows)
376  path->path.rows = *rows;
377  else if (param_info)
378  path->path.rows = param_info->ppi_rows;
379  else
380  path->path.rows = rel->rows;
381 
382  startup_cost = path->subpath->startup_cost;
383 
384  run_cost = path->subpath->total_cost - path->subpath->startup_cost;
385 
386  /* Parallel setup and communication cost. */
387  startup_cost += parallel_setup_cost;
388  run_cost += parallel_tuple_cost * path->path.rows;
389 
390  path->path.startup_cost = startup_cost;
391  path->path.total_cost = (startup_cost + run_cost);
392 }
double parallel_setup_cost
Definition: costsize.c:117
Cost startup_cost
Definition: pathnodes.h:1155
Path * subpath
Definition: pathnodes.h:1495
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
double rows
Definition: pathnodes.h:1154
double ppi_rows
Definition: pathnodes.h:1104
double Cost
Definition: nodes.h:663
double parallel_tuple_cost
Definition: costsize.c:116

◆ cost_gather_merge()

void cost_gather_merge ( GatherMergePath path,
PlannerInfo root,
RelOptInfo rel,
ParamPathInfo param_info,
Cost  input_startup_cost,
Cost  input_total_cost,
double *  rows 
)

Definition at line 405 of file costsize.c.

References Assert, cpu_operator_cost, disable_cost, enable_gathermerge, LOG2, GatherMergePath::num_workers, parallel_setup_cost, parallel_tuple_cost, GatherMergePath::path, ParamPathInfo::ppi_rows, RelOptInfo::rows, Path::rows, Path::startup_cost, and Path::total_cost.

Referenced by create_gather_merge_path().

409 {
410  Cost startup_cost = 0;
411  Cost run_cost = 0;
412  Cost comparison_cost;
413  double N;
414  double logN;
415 
416  /* Mark the path with the correct row estimate */
417  if (rows)
418  path->path.rows = *rows;
419  else if (param_info)
420  path->path.rows = param_info->ppi_rows;
421  else
422  path->path.rows = rel->rows;
423 
424  if (!enable_gathermerge)
425  startup_cost += disable_cost;
426 
427  /*
428  * Add one to the number of workers to account for the leader. This might
429  * be overgenerous since the leader will do less work than other workers
430  * in typical cases, but we'll go with it for now.
431  */
432  Assert(path->num_workers > 0);
433  N = (double) path->num_workers + 1;
434  logN = LOG2(N);
435 
436  /* Assumed cost per tuple comparison */
437  comparison_cost = 2.0 * cpu_operator_cost;
438 
439  /* Heap creation cost */
440  startup_cost += comparison_cost * N * logN;
441 
442  /* Per-tuple heap maintenance cost */
443  run_cost += path->path.rows * comparison_cost * logN;
444 
445  /* small cost for heap management, like cost_merge_append */
446  run_cost += cpu_operator_cost * path->path.rows;
447 
448  /*
449  * Parallel setup and communication cost. Since Gather Merge, unlike
450  * Gather, requires us to block until a tuple is available from every
451  * worker, we bump the IPC cost up a little bit as compared with Gather.
452  * For lack of a better idea, charge an extra 5%.
453  */
454  startup_cost += parallel_setup_cost;
455  run_cost += parallel_tuple_cost * path->path.rows * 1.05;
456 
457  path->path.startup_cost = startup_cost + input_startup_cost;
458  path->path.total_cost = (startup_cost + run_cost + input_total_cost);
459 }
double parallel_setup_cost
Definition: costsize.c:117
Cost startup_cost
Definition: pathnodes.h:1155
Cost disable_cost
Definition: costsize.c:121
double cpu_operator_cost
Definition: costsize.c:115
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
#define LOG2(x)
Definition: costsize.c:101
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
double ppi_rows
Definition: pathnodes.h:1104
bool enable_gathermerge
Definition: costsize.c:139
double Cost
Definition: nodes.h:663
double parallel_tuple_cost
Definition: costsize.c:116

◆ cost_group()

void cost_group ( Path path,
PlannerInfo root,
int  numGroupCols,
double  numGroups,
List quals,
Cost  input_startup_cost,
Cost  input_total_cost,
double  input_tuples 
)

Definition at line 2532 of file costsize.c.

References clamp_row_est(), clauselist_selectivity(), cost_qual_eval(), cpu_operator_cost, JOIN_INNER, QualCost::per_tuple, Path::rows, QualCost::startup, Path::startup_cost, and Path::total_cost.

Referenced by choose_hashed_setop(), and create_group_path().

2537 {
2538  double output_tuples;
2539  Cost startup_cost;
2540  Cost total_cost;
2541 
2542  output_tuples = numGroups;
2543  startup_cost = input_startup_cost;
2544  total_cost = input_total_cost;
2545 
2546  /*
2547  * Charge one cpu_operator_cost per comparison per input tuple. We assume
2548  * all columns get compared at most of the tuples.
2549  */
2550  total_cost += cpu_operator_cost * input_tuples * numGroupCols;
2551 
2552  /*
2553  * If there are quals (HAVING quals), account for their cost and
2554  * selectivity.
2555  */
2556  if (quals)
2557  {
2558  QualCost qual_cost;
2559 
2560  cost_qual_eval(&qual_cost, quals, root);
2561  startup_cost += qual_cost.startup;
2562  total_cost += qual_cost.startup + output_tuples * qual_cost.per_tuple;
2563 
2564  output_tuples = clamp_row_est(output_tuples *
2566  quals,
2567  0,
2568  JOIN_INNER,
2569  NULL));
2570  }
2571 
2572  path->rows = output_tuples;
2573  path->startup_cost = startup_cost;
2574  path->total_cost = total_cost;
2575 }
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
void cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
Definition: costsize.c:4005
Cost startup_cost
Definition: pathnodes.h:1155
double cpu_operator_cost
Definition: costsize.c:115
Cost total_cost
Definition: pathnodes.h:1156
double rows
Definition: pathnodes.h:1154
Selectivity clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo)
Definition: clausesel.c:69
double clamp_row_est(double nrows)
Definition: costsize.c:191
double Cost
Definition: nodes.h:663

◆ cost_incremental_sort()

void cost_incremental_sort ( Path path,
PlannerInfo root,
List pathkeys,
int  presorted_keys,
Cost  input_startup_cost,
Cost  input_total_cost,
double  input_tuples,
int  width,
Cost  comparison_cost,
int  sort_mem,
double  limit_tuples 
)

Definition at line 1790 of file costsize.c.

References Assert, cost_tuplesort(), cpu_tuple_cost, EquivalenceClass::ec_members, EquivalenceMember::em_expr, estimate_num_groups(), i, sort-test::key, lappend(), lfirst, linitial, member, NIL, PathKey::pk_eclass, Path::rows, Path::startup_cost, and Path::total_cost.

Referenced by create_incremental_sort_path().

1795 {
1796  Cost startup_cost = 0,
1797  run_cost = 0,
1798  input_run_cost = input_total_cost - input_startup_cost;
1799  double group_tuples,
1800  input_groups;
1801  Cost group_startup_cost,
1802  group_run_cost,
1803  group_input_run_cost;
1804  List *presortedExprs = NIL;
1805  ListCell *l;
1806  int i = 0;
1807 
1808  Assert(presorted_keys != 0);
1809 
1810  /*
1811  * We want to be sure the cost of a sort is never estimated as zero, even
1812  * if passed-in tuple count is zero. Besides, mustn't do log(0)...
1813  */
1814  if (input_tuples < 2.0)
1815  input_tuples = 2.0;
1816 
1817  /* Extract presorted keys as list of expressions */
1818  foreach(l, pathkeys)
1819  {
1820  PathKey *key = (PathKey *) lfirst(l);
1822  linitial(key->pk_eclass->ec_members);
1823 
1824  presortedExprs = lappend(presortedExprs, member->em_expr);
1825 
1826  i++;
1827  if (i >= presorted_keys)
1828  break;
1829  }
1830 
1831  /* Estimate number of groups with equal presorted keys */
1832  input_groups = estimate_num_groups(root, presortedExprs, input_tuples, NULL);
1833  group_tuples = input_tuples / input_groups;
1834  group_input_run_cost = input_run_cost / input_groups;
1835 
1836  /*
1837  * Estimate average cost of sorting of one group where presorted keys are
1838  * equal. Incremental sort is sensitive to distribution of tuples to the
1839  * groups, where we're relying on quite rough assumptions. Thus, we're
1840  * pessimistic about incremental sort performance and increase its average
1841  * group size by half.
1842  */
1843  cost_tuplesort(&group_startup_cost, &group_run_cost,
1844  1.5 * group_tuples, width, comparison_cost, sort_mem,
1845  limit_tuples);
1846 
1847  /*
1848  * Startup cost of incremental sort is the startup cost of its first group
1849  * plus the cost of its input.
1850  */
1851  startup_cost += group_startup_cost
1852  + input_startup_cost + group_input_run_cost;
1853 
1854  /*
1855  * After we started producing tuples from the first group, the cost of
1856  * producing all the tuples is given by the cost to finish processing this
1857  * group, plus the total cost to process the remaining groups, plus the
1858  * remaining cost of input.
1859  */
1860  run_cost += group_run_cost
1861  + (group_run_cost + group_startup_cost) * (input_groups - 1)
1862  + group_input_run_cost * (input_groups - 1);
1863 
1864  /*
1865  * Incremental sort adds some overhead by itself. Firstly, it has to
1866  * detect the sort groups. This is roughly equal to one extra copy and
1867  * comparison per tuple. Secondly, it has to reset the tuplesort context
1868  * for every group.
1869  */
1870  run_cost += (cpu_tuple_cost + comparison_cost) * input_tuples;
1871  run_cost += 2.0 * cpu_tuple_cost * input_groups;
1872 
1873  path->rows = input_tuples;
1874  path->startup_cost = startup_cost;
1875  path->total_cost = startup_cost + run_cost;
1876 }
#define NIL
Definition: pg_list.h:65
double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset)
Definition: selfuncs.c:3205
Oid member
#define linitial(l)
Definition: pg_list.h:195
Cost startup_cost
Definition: pathnodes.h:1155
static void cost_tuplesort(Cost *startup_cost, Cost *run_cost, double tuples, int width, Cost comparison_cost, int sort_mem, double limit_tuples)
Definition: costsize.c:1688
List * lappend(List *list, void *datum)
Definition: list.c:321
Cost total_cost
Definition: pathnodes.h:1156
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
double rows
Definition: pathnodes.h:1154
EquivalenceClass * pk_eclass
Definition: pathnodes.h:1041
double cpu_tuple_cost
Definition: costsize.c:113
int i
Definition: pg_list.h:50
double Cost
Definition: nodes.h:663
List * ec_members
Definition: pathnodes.h:964

◆ cost_index()

void cost_index ( IndexPath path,
PlannerInfo root,
double  loop_count,
bool  partial_path 
)

Definition at line 480 of file costsize.c.

References RelOptInfo::allvisfrac, IndexOptInfo::amcostestimate, Assert, clamp_row_est(), compute_parallel_worker(), PathTarget::cost, cost_qual_eval(), cpu_tuple_cost, disable_cost, enable_indexscan, extract_nonindex_conditions(), get_parallel_divisor(), get_tablespace_page_costs(), index_pages_fetched(), IndexPath::indexclauses, IndexPath::indexinfo, IndexPath::indexselectivity, IndexPath::indextotalcost, IndexOptInfo::indrestrictinfo, IsA, list_concat(), max_parallel_workers_per_gather, RelOptInfo::pages, IndexOptInfo::pages, Path::parallel_aware, Path::parallel_workers, Path::param_info, IndexPath::path, Path::pathtarget, Path::pathtype, QualCost::per_tuple, ParamPathInfo::ppi_clauses, ParamPathInfo::ppi_rows, IndexOptInfo::rel, RelOptInfo::relid, RelOptInfo::reltablespace, RelOptInfo::rows, Path::rows, RTE_RELATION, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, T_IndexOnlyScan, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_index_path(), and reparameterize_path().

482 {
483  IndexOptInfo *index = path->indexinfo;
484  RelOptInfo *baserel = index->rel;
485  bool indexonly = (path->path.pathtype == T_IndexOnlyScan);
486  amcostestimate_function amcostestimate;
487  List *qpquals;
488  Cost startup_cost = 0;
489  Cost run_cost = 0;
490  Cost cpu_run_cost = 0;
491  Cost indexStartupCost;
492  Cost indexTotalCost;
493  Selectivity indexSelectivity;
494  double indexCorrelation,
495  csquared;
496  double spc_seq_page_cost,
497  spc_random_page_cost;
498  Cost min_IO_cost,
499  max_IO_cost;
500  QualCost qpqual_cost;
501  Cost cpu_per_tuple;
502  double tuples_fetched;
503  double pages_fetched;
504  double rand_heap_pages;
505  double index_pages;
506 
507  /* Should only be applied to base relations */
508  Assert(IsA(baserel, RelOptInfo) &&
509  IsA(index, IndexOptInfo));
510  Assert(baserel->relid > 0);
511  Assert(baserel->rtekind == RTE_RELATION);
512 
513  /*
514  * Mark the path with the correct row estimate, and identify which quals
515  * will need to be enforced as qpquals. We need not check any quals that
516  * are implied by the index's predicate, so we can use indrestrictinfo not
517  * baserestrictinfo as the list of relevant restriction clauses for the
518  * rel.
519  */
520  if (path->path.param_info)
521  {
522  path->path.rows = path->path.param_info->ppi_rows;
523  /* qpquals come from the rel's restriction clauses and ppi_clauses */
525  path->indexclauses),
527  path->indexclauses));
528  }
529  else
530  {
531  path->path.rows = baserel->rows;
532  /* qpquals come from just the rel's restriction clauses */
534  path->indexclauses);
535  }
536 
537  if (!enable_indexscan)
538  startup_cost += disable_cost;
539  /* we don't need to check enable_indexonlyscan; indxpath.c does that */
540 
541  /*
542  * Call index-access-method-specific code to estimate the processing cost
543  * for scanning the index, as well as the selectivity of the index (ie,
544  * the fraction of main-table tuples we will have to retrieve) and its
545  * correlation to the main-table tuple order. We need a cast here because
546  * pathnodes.h uses a weak function type to avoid including amapi.h.
547  */
548  amcostestimate = (amcostestimate_function) index->amcostestimate;
549  amcostestimate(root, path, loop_count,
550  &indexStartupCost, &indexTotalCost,
551  &indexSelectivity, &indexCorrelation,
552  &index_pages);
553 
554  /*
555  * Save amcostestimate's results for possible use in bitmap scan planning.
556  * We don't bother to save indexStartupCost or indexCorrelation, because a
557  * bitmap scan doesn't care about either.
558  */
559  path->indextotalcost = indexTotalCost;
560  path->indexselectivity = indexSelectivity;
561 
562  /* all costs for touching index itself included here */
563  startup_cost += indexStartupCost;
564  run_cost += indexTotalCost - indexStartupCost;
565 
566  /* estimate number of main-table tuples fetched */
567  tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
568 
569  /* fetch estimated page costs for tablespace containing table */
571  &spc_random_page_cost,
572  &spc_seq_page_cost);
573 
574  /*----------
575  * Estimate number of main-table pages fetched, and compute I/O cost.
576  *
577  * When the index ordering is uncorrelated with the table ordering,
578  * we use an approximation proposed by Mackert and Lohman (see
579  * index_pages_fetched() for details) to compute the number of pages
580  * fetched, and then charge spc_random_page_cost per page fetched.
581  *
582  * When the index ordering is exactly correlated with the table ordering
583  * (just after a CLUSTER, for example), the number of pages fetched should
584  * be exactly selectivity * table_size. What's more, all but the first
585  * will be sequential fetches, not the random fetches that occur in the
586  * uncorrelated case. So if the number of pages is more than 1, we
587  * ought to charge
588  * spc_random_page_cost + (pages_fetched - 1) * spc_seq_page_cost
589  * For partially-correlated indexes, we ought to charge somewhere between
590  * these two estimates. We currently interpolate linearly between the
591  * estimates based on the correlation squared (XXX is that appropriate?).
592  *
593  * If it's an index-only scan, then we will not need to fetch any heap
594  * pages for which the visibility map shows all tuples are visible.
595  * Hence, reduce the estimated number of heap fetches accordingly.
596  * We use the measured fraction of the entire heap that is all-visible,
597  * which might not be particularly relevant to the subset of the heap
598  * that this query will fetch; but it's not clear how to do better.
599  *----------
600  */
601  if (loop_count > 1)
602  {
603  /*
604  * For repeated indexscans, the appropriate estimate for the
605  * uncorrelated case is to scale up the number of tuples fetched in
606  * the Mackert and Lohman formula by the number of scans, so that we
607  * estimate the number of pages fetched by all the scans; then
608  * pro-rate the costs for one scan. In this case we assume all the
609  * fetches are random accesses.
610  */
611  pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
612  baserel->pages,
613  (double) index->pages,
614  root);
615 
616  if (indexonly)
617  pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
618 
619  rand_heap_pages = pages_fetched;
620 
621  max_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
622 
623  /*
624  * In the perfectly correlated case, the number of pages touched by
625  * each scan is selectivity * table_size, and we can use the Mackert
626  * and Lohman formula at the page level to estimate how much work is
627  * saved by caching across scans. We still assume all the fetches are
628  * random, though, which is an overestimate that's hard to correct for
629  * without double-counting the cache effects. (But in most cases
630  * where such a plan is actually interesting, only one page would get
631  * fetched per scan anyway, so it shouldn't matter much.)
632  */
633  pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
634 
635  pages_fetched = index_pages_fetched(pages_fetched * loop_count,
636  baserel->pages,
637  (double) index->pages,
638  root);
639 
640  if (indexonly)
641  pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
642 
643  min_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
644  }
645  else
646  {
647  /*
648  * Normal case: apply the Mackert and Lohman formula, and then
649  * interpolate between that and the correlation-derived result.
650  */
651  pages_fetched = index_pages_fetched(tuples_fetched,
652  baserel->pages,
653  (double) index->pages,
654  root);
655 
656  if (indexonly)
657  pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
658 
659  rand_heap_pages = pages_fetched;
660 
661  /* max_IO_cost is for the perfectly uncorrelated case (csquared=0) */
662  max_IO_cost = pages_fetched * spc_random_page_cost;
663 
664  /* min_IO_cost is for the perfectly correlated case (csquared=1) */
665  pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
666 
667  if (indexonly)
668  pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
669 
670  if (pages_fetched > 0)
671  {
672  min_IO_cost = spc_random_page_cost;
673  if (pages_fetched > 1)
674  min_IO_cost += (pages_fetched - 1) * spc_seq_page_cost;
675  }
676  else
677  min_IO_cost = 0;
678  }
679 
680  if (partial_path)
681  {
682  /*
683  * For index only scans compute workers based on number of index pages
684  * fetched; the number of heap pages we fetch might be so small as to
685  * effectively rule out parallelism, which we don't want to do.
686  */
687  if (indexonly)
688  rand_heap_pages = -1;
689 
690  /*
691  * Estimate the number of parallel workers required to scan index. Use
692  * the number of heap pages computed considering heap fetches won't be
693  * sequential as for parallel scans the pages are accessed in random
694  * order.
695  */
697  rand_heap_pages,
698  index_pages,
700 
701  /*
702  * Fall out if workers can't be assigned for parallel scan, because in
703  * such a case this path will be rejected. So there is no benefit in
704  * doing extra computation.
705  */
706  if (path->path.parallel_workers <= 0)
707  return;
708 
709  path->path.parallel_aware = true;
710  }
711 
712  /*
713  * Now interpolate based on estimated index order correlation to get total
714  * disk I/O cost for main table accesses.
715  */
716  csquared = indexCorrelation * indexCorrelation;
717 
718  run_cost += max_IO_cost + csquared * (min_IO_cost - max_IO_cost);
719 
720  /*
721  * Estimate CPU costs per tuple.
722  *
723  * What we want here is cpu_tuple_cost plus the evaluation costs of any
724  * qual clauses that we have to evaluate as qpquals.
725  */
726  cost_qual_eval(&qpqual_cost, qpquals, root);
727 
728  startup_cost += qpqual_cost.startup;
729  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
730 
731  cpu_run_cost += cpu_per_tuple * tuples_fetched;
732 
733  /* tlist eval costs are paid per output row, not per tuple scanned */
734  startup_cost += path->path.pathtarget->cost.startup;
735  cpu_run_cost += path->path.pathtarget->cost.per_tuple * path->path.rows;
736 
737  /* Adjust costing for parallelism, if used. */
738  if (path->path.parallel_workers > 0)
739  {
740  double parallel_divisor = get_parallel_divisor(&path->path);
741 
742  path->path.rows = clamp_row_est(path->path.rows / parallel_divisor);
743 
744  /* The CPU cost is divided among all the workers. */
745  cpu_run_cost /= parallel_divisor;
746  }
747 
748  run_cost += cpu_run_cost;
749 
750  path->path.startup_cost = startup_cost;
751  path->path.total_cost = startup_cost + run_cost;
752 }
static List * extract_nonindex_conditions(List *qual_clauses, List *indexclauses)
Definition: costsize.c:771
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
PathTarget * pathtarget
Definition: pathnodes.h:1145
Path path
Definition: pathnodes.h:1206
IndexOptInfo * indexinfo
Definition: pathnodes.h:1207
int compute_parallel_worker(RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
Definition: allpaths.c:3788
double tuples
Definition: pathnodes.h:705
Oid reltablespace
Definition: pathnodes.h:694
int parallel_workers
Definition: pathnodes.h:1151
ParamPathInfo * param_info
Definition: pathnodes.h:1147
List * list_concat(List *list1, const List *list2)
Definition: list.c:515
List * indexclauses
Definition: pathnodes.h:1208
double Selectivity
Definition: nodes.h:662
Cost startup
Definition: pathnodes.h:45
double allvisfrac
Definition: pathnodes.h:706
Definition: type.h:89
BlockNumber pages
Definition: pathnodes.h:823
NodeTag pathtype
Definition: pathnodes.h:1142
Cost per_tuple
Definition: pathnodes.h:46
RelOptInfo * rel
Definition: pathnodes.h:820
void cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
Definition: costsize.c:4005
Cost startup_cost
Definition: pathnodes.h:1155
Cost indextotalcost
Definition: pathnodes.h:1212
Cost disable_cost
Definition: costsize.c:121
Selectivity indexselectivity
Definition: pathnodes.h:1213
static double get_parallel_divisor(Path *path)
Definition: costsize.c:5661
void(* amcostestimate)()
Definition: pathnodes.h:868
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:693
List * indrestrictinfo
Definition: pathnodes.h:848
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
BlockNumber pages
Definition: pathnodes.h:704
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
List * ppi_clauses
Definition: pathnodes.h:1105
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
void(* amcostestimate_function)(struct PlannerInfo *root, struct IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
Definition: amapi.h:93
bool parallel_aware
Definition: pathnodes.h:1149
double clamp_row_est(double nrows)
Definition: costsize.c:191
int max_parallel_workers_per_gather
Definition: costsize.c:123
Definition: pg_list.h:50
bool enable_indexscan
Definition: costsize.c:126
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:829
double Cost
Definition: nodes.h:663

◆ cost_material()

void cost_material ( Path path,
Cost  input_startup_cost,
Cost  input_total_cost,
double  tuples,
int  width 
)

Definition at line 2220 of file costsize.c.

References cpu_operator_cost, relation_byte_size(), Path::rows, seq_page_cost, Path::startup_cost, Path::total_cost, and work_mem.

Referenced by create_material_path(), and materialize_finished_plan().

2223 {
2224  Cost startup_cost = input_startup_cost;
2225  Cost run_cost = input_total_cost - input_startup_cost;
2226  double nbytes = relation_byte_size(tuples, width);
2227  long work_mem_bytes = work_mem * 1024L;
2228 
2229  path->rows = tuples;
2230 
2231  /*
2232  * Whether spilling or not, charge 2x cpu_operator_cost per tuple to
2233  * reflect bookkeeping overhead. (This rate must be more than what
2234  * cost_rescan charges for materialize, ie, cpu_operator_cost per tuple;
2235  * if it is exactly the same then there will be a cost tie between
2236  * nestloop with A outer, materialized B inner and nestloop with B outer,
2237  * materialized A inner. The extra cost ensures we'll prefer
2238  * materializing the smaller rel.) Note that this is normally a good deal
2239  * less than cpu_tuple_cost; which is OK because a Material plan node
2240  * doesn't do qual-checking or projection, so it's got less overhead than
2241  * most plan nodes.
2242  */
2243  run_cost += 2 * cpu_operator_cost * tuples;
2244 
2245  /*
2246  * If we will spill to disk, charge at the rate of seq_page_cost per page.
2247  * This cost is assumed to be evenly spread through the plan run phase,
2248  * which isn't exactly accurate but our cost model doesn't allow for
2249  * nonuniform costs within the run phase.
2250  */
2251  if (nbytes > work_mem_bytes)
2252  {
2253  double npages = ceil(nbytes / BLCKSZ);
2254 
2255  run_cost += seq_page_cost * npages;
2256  }
2257 
2258  path->startup_cost = startup_cost;
2259  path->total_cost = startup_cost + run_cost;
2260 }
Cost startup_cost
Definition: pathnodes.h:1155
double cpu_operator_cost
Definition: costsize.c:115
static double relation_byte_size(double tuples, int width)
Definition: costsize.c:5640
int work_mem
Definition: globals.c:121
Cost total_cost
Definition: pathnodes.h:1156
double rows
Definition: pathnodes.h:1154
double seq_page_cost
Definition: costsize.c:111
double Cost
Definition: nodes.h:663

◆ cost_merge_append()

void cost_merge_append ( Path path,
PlannerInfo root,
List pathkeys,
int  n_streams,
Cost  input_startup_cost,
Cost  input_total_cost,
double  tuples 
)

Definition at line 2171 of file costsize.c.

References APPEND_CPU_COST_MULTIPLIER, cpu_operator_cost, cpu_tuple_cost, LOG2, Path::startup_cost, and Path::total_cost.

Referenced by create_merge_append_path().

2175 {
2176  Cost startup_cost = 0;
2177  Cost run_cost = 0;
2178  Cost comparison_cost;
2179  double N;
2180  double logN;
2181 
2182  /*
2183  * Avoid log(0)...
2184  */
2185  N = (n_streams < 2) ? 2.0 : (double) n_streams;
2186  logN = LOG2(N);
2187 
2188  /* Assumed cost per tuple comparison */
2189  comparison_cost = 2.0 * cpu_operator_cost;
2190 
2191  /* Heap creation cost */
2192  startup_cost += comparison_cost * N * logN;
2193 
2194  /* Per-tuple heap maintenance cost */
2195  run_cost += tuples * comparison_cost * logN;
2196 
2197  /*
2198  * Although MergeAppend does not do any selection or projection, it's not
2199  * free; add a small per-tuple overhead.
2200  */
2201  run_cost += cpu_tuple_cost * APPEND_CPU_COST_MULTIPLIER * tuples;
2202 
2203  path->startup_cost = startup_cost + input_startup_cost;
2204  path->total_cost = startup_cost + run_cost + input_total_cost;
2205 }
Cost startup_cost
Definition: pathnodes.h:1155
double cpu_operator_cost
Definition: costsize.c:115
#define APPEND_CPU_COST_MULTIPLIER
Definition: costsize.c:108
Cost total_cost
Definition: pathnodes.h:1156
#define LOG2(x)
Definition: costsize.c:101
double cpu_tuple_cost
Definition: costsize.c:113
double Cost
Definition: nodes.h:663

◆ cost_namedtuplestorescan()

void cost_namedtuplestorescan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 1543 of file costsize.c.

References Assert, cpu_tuple_cost, get_restriction_qual_cost(), QualCost::per_tuple, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::rows, Path::rows, RTE_NAMEDTUPLESTORE, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_namedtuplestorescan_path().

1545 {
1546  Cost startup_cost = 0;
1547  Cost run_cost = 0;
1548  QualCost qpqual_cost;
1549  Cost cpu_per_tuple;
1550 
1551  /* Should only be applied to base relations that are Tuplestores */
1552  Assert(baserel->relid > 0);
1553  Assert(baserel->rtekind == RTE_NAMEDTUPLESTORE);
1554 
1555  /* Mark the path with the correct row estimate */
1556  if (param_info)
1557  path->rows = param_info->ppi_rows;
1558  else
1559  path->rows = baserel->rows;
1560 
1561  /* Charge one CPU tuple cost per row for tuplestore manipulation */
1562  cpu_per_tuple = cpu_tuple_cost;
1563 
1564  /* Add scanning CPU costs */
1565  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1566 
1567  startup_cost += qpqual_cost.startup;
1568  cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1569  run_cost += cpu_per_tuple * baserel->tuples;
1570 
1571  path->startup_cost = startup_cost;
1572  path->total_cost = startup_cost + run_cost;
1573 }
double tuples
Definition: pathnodes.h:705
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
Index relid
Definition: pathnodes.h:693
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
double Cost
Definition: nodes.h:663

◆ cost_qual_eval()

void cost_qual_eval ( QualCost cost,
List quals,
PlannerInfo root 
)

Definition at line 4005 of file costsize.c.

References cost_qual_eval_walker(), lfirst, QualCost::per_tuple, cost_qual_eval_context::root, QualCost::startup, and cost_qual_eval_context::total.

Referenced by add_foreign_grouping_paths(), cost_agg(), cost_group(), cost_index(), cost_subplan(), cost_tidscan(), create_group_result_path(), create_minmaxagg_path(), estimate_path_cost_size(), final_cost_hashjoin(), final_cost_mergejoin(), final_cost_nestloop(), get_restriction_qual_cost(), inline_function(), plan_cluster_use_sort(), postgresGetForeignJoinPaths(), postgresGetForeignRelSize(), set_baserel_size_estimates(), and set_foreign_size_estimates().

4006 {
4007  cost_qual_eval_context context;
4008  ListCell *l;
4009 
4010  context.root = root;
4011  context.total.startup = 0;
4012  context.total.per_tuple = 0;
4013 
4014  /* We don't charge any cost for the implicit ANDing at top level ... */
4015 
4016  foreach(l, quals)
4017  {
4018  Node *qual = (Node *) lfirst(l);
4019 
4020  cost_qual_eval_walker(qual, &context);
4021  }
4022 
4023  *cost = context.total;
4024 }
PlannerInfo * root
Definition: costsize.c:148
Definition: nodes.h:529
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
static bool cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
Definition: costsize.c:4045
#define lfirst(lc)
Definition: pg_list.h:190

◆ cost_qual_eval_node()

void cost_qual_eval_node ( QualCost cost,
Node qual,
PlannerInfo root 
)

Definition at line 4031 of file costsize.c.

References cost_qual_eval_walker(), QualCost::per_tuple, cost_qual_eval_context::root, QualCost::startup, and cost_qual_eval_context::total.

Referenced by add_placeholders_to_joinrel(), cost_functionscan(), cost_qual_eval_walker(), cost_tablefuncscan(), cost_windowagg(), get_agg_clause_costs_walker(), index_other_operands_eval_cost(), make_sort_input_target(), order_qual_clauses(), set_pathtarget_cost_width(), and set_rel_width().

4032 {
4033  cost_qual_eval_context context;
4034 
4035  context.root = root;
4036  context.total.startup = 0;
4037  context.total.per_tuple = 0;
4038 
4039  cost_qual_eval_walker(qual, &context);
4040 
4041  *cost = context.total;
4042 }
PlannerInfo * root
Definition: costsize.c:148
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
static bool cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
Definition: costsize.c:4045

◆ cost_qual_eval_walker()

static bool cost_qual_eval_walker ( Node node,
cost_qual_eval_context context 
)
static

Definition at line 4045 of file costsize.c.

References add_function_cost(), CoerceViaIO::arg, ArrayCoerceExpr::arg, ScalarArrayOpExpr::args, RestrictInfo::clause, cost_qual_eval_node(), cpu_operator_cost, disable_cost, ArrayCoerceExpr::elemexpr, elog, ERROR, estimate_array_length(), RestrictInfo::eval_cost, expression_tree_walker(), exprType(), get_opcode(), getTypeInputInfo(), getTypeOutputInfo(), IsA, lfirst_oid, linitial, lsecond, ScalarArrayOpExpr::opfuncid, RowCompareExpr::opnos, RestrictInfo::orclause, SubPlan::per_call_cost, QualCost::per_tuple, RestrictInfo::pseudoconstant, CoerceViaIO::resulttype, cost_qual_eval_context::root, set_opfuncid(), set_sa_opfuncid(), QualCost::startup, SubPlan::startup_cost, AlternativeSubPlan::subplans, and cost_qual_eval_context::total.

Referenced by cost_qual_eval(), and cost_qual_eval_node().

4046 {
4047  if (node == NULL)
4048  return false;
4049 
4050  /*
4051  * RestrictInfo nodes contain an eval_cost field reserved for this
4052  * routine's use, so that it's not necessary to evaluate the qual clause's
4053  * cost more than once. If the clause's cost hasn't been computed yet,
4054  * the field's startup value will contain -1.
4055  */
4056  if (IsA(node, RestrictInfo))
4057  {
4058  RestrictInfo *rinfo = (RestrictInfo *) node;
4059 
4060  if (rinfo->eval_cost.startup < 0)
4061  {
4062  cost_qual_eval_context locContext;
4063 
4064  locContext.root = context->root;
4065  locContext.total.startup = 0;
4066  locContext.total.per_tuple = 0;
4067 
4068  /*
4069  * For an OR clause, recurse into the marked-up tree so that we
4070  * set the eval_cost for contained RestrictInfos too.
4071  */
4072  if (rinfo->orclause)
4073  cost_qual_eval_walker((Node *) rinfo->orclause, &locContext);
4074  else
4075  cost_qual_eval_walker((Node *) rinfo->clause, &locContext);
4076 
4077  /*
4078  * If the RestrictInfo is marked pseudoconstant, it will be tested
4079  * only once, so treat its cost as all startup cost.
4080  */
4081  if (rinfo->pseudoconstant)
4082  {
4083  /* count one execution during startup */
4084  locContext.total.startup += locContext.total.per_tuple;
4085  locContext.total.per_tuple = 0;
4086  }
4087  rinfo->eval_cost = locContext.total;
4088  }
4089  context->total.startup += rinfo->eval_cost.startup;
4090  context->total.per_tuple += rinfo->eval_cost.per_tuple;
4091  /* do NOT recurse into children */
4092  return false;
4093  }
4094 
4095  /*
4096  * For each operator or function node in the given tree, we charge the
4097  * estimated execution cost given by pg_proc.procost (remember to multiply
4098  * this by cpu_operator_cost).
4099  *
4100  * Vars and Consts are charged zero, and so are boolean operators (AND,
4101  * OR, NOT). Simplistic, but a lot better than no model at all.
4102  *
4103  * Should we try to account for the possibility of short-circuit
4104  * evaluation of AND/OR? Probably *not*, because that would make the
4105  * results depend on the clause ordering, and we are not in any position
4106  * to expect that the current ordering of the clauses is the one that's
4107  * going to end up being used. The above per-RestrictInfo caching would
4108  * not mix well with trying to re-order clauses anyway.
4109  *
4110  * Another issue that is entirely ignored here is that if a set-returning
4111  * function is below top level in the tree, the functions/operators above
4112  * it will need to be evaluated multiple times. In practical use, such
4113  * cases arise so seldom as to not be worth the added complexity needed;
4114  * moreover, since our rowcount estimates for functions tend to be pretty
4115  * phony, the results would also be pretty phony.
4116  */
4117  if (IsA(node, FuncExpr))
4118  {
4119  add_function_cost(context->root, ((FuncExpr *) node)->funcid, node,
4120  &context->total);
4121  }
4122  else if (IsA(node, OpExpr) ||
4123  IsA(node, DistinctExpr) ||
4124  IsA(node, NullIfExpr))
4125  {
4126  /* rely on struct equivalence to treat these all alike */
4127  set_opfuncid((OpExpr *) node);
4128  add_function_cost(context->root, ((OpExpr *) node)->opfuncid, node,
4129  &context->total);
4130  }
4131  else if (IsA(node, ScalarArrayOpExpr))
4132  {
4133  /*
4134  * Estimate that the operator will be applied to about half of the
4135  * array elements before the answer is determined.
4136  */
4137  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) node;
4138  Node *arraynode = (Node *) lsecond(saop->args);
4139  QualCost sacosts;
4140 
4141  set_sa_opfuncid(saop);
4142  sacosts.startup = sacosts.per_tuple = 0;
4143  add_function_cost(context->root, saop->opfuncid, NULL,
4144  &sacosts);
4145  context->total.startup += sacosts.startup;
4146  context->total.per_tuple += sacosts.per_tuple *
4147  estimate_array_length(arraynode) * 0.5;
4148  }
4149  else if (IsA(node, Aggref) ||
4150  IsA(node, WindowFunc))
4151  {
4152  /*
4153  * Aggref and WindowFunc nodes are (and should be) treated like Vars,
4154  * ie, zero execution cost in the current model, because they behave
4155  * essentially like Vars at execution. We disregard the costs of
4156  * their input expressions for the same reason. The actual execution
4157  * costs of the aggregate/window functions and their arguments have to
4158  * be factored into plan-node-specific costing of the Agg or WindowAgg
4159  * plan node.
4160  */
4161  return false; /* don't recurse into children */
4162  }
4163  else if (IsA(node, CoerceViaIO))
4164  {
4165  CoerceViaIO *iocoerce = (CoerceViaIO *) node;
4166  Oid iofunc;
4167  Oid typioparam;
4168  bool typisvarlena;
4169 
4170  /* check the result type's input function */
4171  getTypeInputInfo(iocoerce->resulttype,
4172  &iofunc, &typioparam);
4173  add_function_cost(context->root, iofunc, NULL,
4174  &context->total);
4175  /* check the input type's output function */
4176  getTypeOutputInfo(exprType((Node *) iocoerce->arg),
4177  &iofunc, &typisvarlena);
4178  add_function_cost(context->root, iofunc, NULL,
4179  &context->total);
4180  }
4181  else if (IsA(node, ArrayCoerceExpr))
4182  {
4183  ArrayCoerceExpr *acoerce = (ArrayCoerceExpr *) node;
4184  QualCost perelemcost;
4185 
4186  cost_qual_eval_node(&perelemcost, (Node *) acoerce->elemexpr,
4187  context->root);
4188  context->total.startup += perelemcost.startup;
4189  if (perelemcost.per_tuple > 0)
4190  context->total.per_tuple += perelemcost.per_tuple *
4191  estimate_array_length((Node *) acoerce->arg);
4192  }
4193  else if (IsA(node, RowCompareExpr))
4194  {
4195  /* Conservatively assume we will check all the columns */
4196  RowCompareExpr *rcexpr = (RowCompareExpr *) node;
4197  ListCell *lc;
4198 
4199  foreach(lc, rcexpr->opnos)
4200  {
4201  Oid opid = lfirst_oid(lc);
4202 
4203  add_function_cost(context->root, get_opcode(opid), NULL,
4204  &context->total);
4205  }
4206  }
4207  else if (IsA(node, MinMaxExpr) ||
4208  IsA(node, SQLValueFunction) ||
4209  IsA(node, XmlExpr) ||
4210  IsA(node, CoerceToDomain) ||
4211  IsA(node, NextValueExpr))
4212  {
4213  /* Treat all these as having cost 1 */
4214  context->total.per_tuple += cpu_operator_cost;
4215  }
4216  else if (IsA(node, CurrentOfExpr))
4217  {
4218  /* Report high cost to prevent selection of anything but TID scan */
4219  context->total.startup += disable_cost;
4220  }
4221  else if (IsA(node, SubLink))
4222  {
4223  /* This routine should not be applied to un-planned expressions */
4224  elog(ERROR, "cannot handle unplanned sub-select");
4225  }
4226  else if (IsA(node, SubPlan))
4227  {
4228  /*
4229  * A subplan node in an expression typically indicates that the
4230  * subplan will be executed on each evaluation, so charge accordingly.
4231  * (Sub-selects that can be executed as InitPlans have already been
4232  * removed from the expression.)
4233  */
4234  SubPlan *subplan = (SubPlan *) node;
4235 
4236  context->total.startup += subplan->startup_cost;
4237  context->total.per_tuple += subplan->per_call_cost;
4238 
4239  /*
4240  * We don't want to recurse into the testexpr, because it was already
4241  * counted in the SubPlan node's costs. So we're done.
4242  */
4243  return false;
4244  }
4245  else if (IsA(node, AlternativeSubPlan))
4246  {
4247  /*
4248  * Arbitrarily use the first alternative plan for costing. (We should
4249  * certainly only include one alternative, and we don't yet have
4250  * enough information to know which one the executor is most likely to
4251  * use.)
4252  */
4253  AlternativeSubPlan *asplan = (AlternativeSubPlan *) node;
4254 
4255  return cost_qual_eval_walker((Node *) linitial(asplan->subplans),
4256  context);
4257  }
4258  else if (IsA(node, PlaceHolderVar))
4259  {
4260  /*
4261  * A PlaceHolderVar should be given cost zero when considering general
4262  * expression evaluation costs. The expense of doing the contained
4263  * expression is charged as part of the tlist eval costs of the scan
4264  * or join where the PHV is first computed (see set_rel_width and
4265  * add_placeholders_to_joinrel). If we charged it again here, we'd be
4266  * double-counting the cost for each level of plan that the PHV
4267  * bubbles up through. Hence, return without recursing into the
4268  * phexpr.
4269  */
4270  return false;
4271  }
4272 
4273  /* recurse into children */
4275  (void *) context);
4276 }
QualCost eval_cost
Definition: pathnodes.h:2022
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4031
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
PlannerInfo * root
Definition: costsize.c:148
void getTypeOutputInfo(Oid type, Oid *typOutput, bool *typIsVarlena)
Definition: lsyscache.c:2735
Expr * orclause
Definition: pathnodes.h:2016
Oid resulttype
Definition: primnodes.h:835
bool pseudoconstant
Definition: pathnodes.h:1993
Definition: nodes.h:529
void add_function_cost(PlannerInfo *root, Oid funcid, Node *node, QualCost *cost)
Definition: plancat.c:1908
unsigned int Oid
Definition: postgres_ext.h:31
#define lsecond(l)
Definition: pg_list.h:200
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2018
#define linitial(l)
Definition: pg_list.h:195
#define ERROR
Definition: elog.h:43
Cost disable_cost
Definition: costsize.c:121
double cpu_operator_cost
Definition: costsize.c:115
Expr * arg
Definition: primnodes.h:834
Expr * elemexpr
Definition: primnodes.h:859
void getTypeInputInfo(Oid type, Oid *typInput, Oid *typIOParam)
Definition: lsyscache.c:2702
Expr * clause
Definition: pathnodes.h:1985
Cost per_call_cost
Definition: primnodes.h:733
RegProcedure get_opcode(Oid opno)
Definition: lsyscache.c:1153
static bool cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
Definition: costsize.c:4045
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:41
bool expression_tree_walker(Node *node, bool(*walker)(), void *context)
Definition: nodeFuncs.c:1839
void set_opfuncid(OpExpr *opexpr)
Definition: nodeFuncs.c:1618
#define elog(elevel,...)
Definition: elog.h:214
Cost startup_cost
Definition: primnodes.h:732
void set_sa_opfuncid(ScalarArrayOpExpr *opexpr)
Definition: nodeFuncs.c:1629
#define lfirst_oid(lc)
Definition: pg_list.h:192

◆ cost_recursive_union()

void cost_recursive_union ( Path runion,
Path nrterm,
Path rterm 
)

Definition at line 1617 of file costsize.c.

References cpu_tuple_cost, Max, Path::pathtarget, Path::rows, Path::startup_cost, Path::total_cost, and PathTarget::width.

Referenced by create_recursiveunion_path().

1618 {
1619  Cost startup_cost;
1620  Cost total_cost;
1621  double total_rows;
1622 
1623  /* We probably have decent estimates for the non-recursive term */
1624  startup_cost = nrterm->startup_cost;
1625  total_cost = nrterm->total_cost;
1626  total_rows = nrterm->rows;
1627 
1628  /*
1629  * We arbitrarily assume that about 10 recursive iterations will be
1630  * needed, and that we've managed to get a good fix on the cost and output
1631  * size of each one of them. These are mighty shaky assumptions but it's
1632  * hard to see how to do better.
1633  */
1634  total_cost += 10 * rterm->total_cost;
1635  total_rows += 10 * rterm->rows;
1636 
1637  /*
1638  * Also charge cpu_tuple_cost per row to account for the costs of
1639  * manipulating the tuplestores. (We don't worry about possible
1640  * spill-to-disk costs.)
1641  */
1642  total_cost += cpu_tuple_cost * total_rows;
1643 
1644  runion->startup_cost = startup_cost;
1645  runion->total_cost = total_cost;
1646  runion->rows = total_rows;
1647  runion->pathtarget->width = Max(nrterm->pathtarget->width,
1648  rterm->pathtarget->width);
1649 }
PathTarget * pathtarget
Definition: pathnodes.h:1145
Cost startup_cost
Definition: pathnodes.h:1155
Cost total_cost
Definition: pathnodes.h:1156
#define Max(x, y)
Definition: c.h:914
double rows
Definition: pathnodes.h:1154
double cpu_tuple_cost
Definition: costsize.c:113
double Cost
Definition: nodes.h:663

◆ cost_rescan()

static void cost_rescan ( PlannerInfo root,
Path path,
Cost rescan_startup_cost,
Cost rescan_total_cost 
)
static

Definition at line 3898 of file costsize.c.

References cpu_operator_cost, cpu_tuple_cost, Path::pathtype, relation_byte_size(), seq_page_cost, Path::startup_cost, T_CteScan, T_FunctionScan, T_HashJoin, T_Material, T_Sort, T_WorkTableScan, Path::total_cost, and work_mem.

Referenced by initial_cost_nestloop().

3901 {
3902  switch (path->pathtype)
3903  {
3904  case T_FunctionScan:
3905 
3906  /*
3907  * Currently, nodeFunctionscan.c always executes the function to
3908  * completion before returning any rows, and caches the results in
3909  * a tuplestore. So the function eval cost is all startup cost
3910  * and isn't paid over again on rescans. However, all run costs
3911  * will be paid over again.
3912  */
3913  *rescan_startup_cost = 0;
3914  *rescan_total_cost = path->total_cost - path->startup_cost;
3915  break;
3916  case T_HashJoin:
3917 
3918  /*
3919  * If it's a single-batch join, we don't need to rebuild the hash
3920  * table during a rescan.
3921  */
3922  if (((HashPath *) path)->num_batches == 1)
3923  {
3924  /* Startup cost is exactly the cost of hash table building */
3925  *rescan_startup_cost = 0;
3926  *rescan_total_cost = path->total_cost - path->startup_cost;
3927  }
3928  else
3929  {
3930  /* Otherwise, no special treatment */
3931  *rescan_startup_cost = path->startup_cost;
3932  *rescan_total_cost = path->total_cost;
3933  }
3934  break;
3935  case T_CteScan:
3936  case T_WorkTableScan:
3937  {
3938  /*
3939  * These plan types materialize their final result in a
3940  * tuplestore or tuplesort object. So the rescan cost is only
3941  * cpu_tuple_cost per tuple, unless the result is large enough
3942  * to spill to disk.
3943  */
3944  Cost run_cost = cpu_tuple_cost * path->rows;
3945  double nbytes = relation_byte_size(path->rows,
3946  path->pathtarget->width);
3947  long work_mem_bytes = work_mem * 1024L;
3948 
3949  if (nbytes > work_mem_bytes)
3950  {
3951  /* It will spill, so account for re-read cost */
3952  double npages = ceil(nbytes / BLCKSZ);
3953 
3954  run_cost += seq_page_cost * npages;
3955  }
3956  *rescan_startup_cost = 0;
3957  *rescan_total_cost = run_cost;
3958  }
3959  break;
3960  case T_Material:
3961  case T_Sort:
3962  {
3963  /*
3964  * These plan types not only materialize their results, but do
3965  * not implement qual filtering or projection. So they are
3966  * even cheaper to rescan than the ones above. We charge only
3967  * cpu_operator_cost per tuple. (Note: keep that in sync with
3968  * the run_cost charge in cost_sort, and also see comments in
3969  * cost_material before you change it.)
3970  */
3971  Cost run_cost = cpu_operator_cost * path->rows;
3972  double nbytes = relation_byte_size(path->rows,
3973  path->pathtarget->width);
3974  long work_mem_bytes = work_mem * 1024L;
3975 
3976  if (nbytes > work_mem_bytes)
3977  {
3978  /* It will spill, so account for re-read cost */
3979  double npages = ceil(nbytes / BLCKSZ);
3980 
3981  run_cost += seq_page_cost * npages;
3982  }
3983  *rescan_startup_cost = 0;
3984  *rescan_total_cost = run_cost;
3985  }
3986  break;
3987  default:
3988  *rescan_startup_cost = path->startup_cost;
3989  *rescan_total_cost = path->total_cost;
3990  break;
3991  }
3992 }
Definition: nodes.h:76
NodeTag pathtype
Definition: pathnodes.h:1142
Cost startup_cost
Definition: pathnodes.h:1155
double cpu_operator_cost
Definition: costsize.c:115
static double relation_byte_size(double tuples, int width)
Definition: costsize.c:5640
int work_mem
Definition: globals.c:121
Cost total_cost
Definition: pathnodes.h:1156
double cpu_tuple_cost
Definition: costsize.c:113
double seq_page_cost
Definition: costsize.c:111
double Cost
Definition: nodes.h:663

◆ cost_resultscan()

void cost_resultscan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 1580 of file costsize.c.

References Assert, cpu_tuple_cost, get_restriction_qual_cost(), QualCost::per_tuple, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::rows, Path::rows, RTE_RESULT, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_resultscan_path().

1582 {
1583  Cost startup_cost = 0;
1584  Cost run_cost = 0;
1585  QualCost qpqual_cost;
1586  Cost cpu_per_tuple;
1587 
1588  /* Should only be applied to RTE_RESULT base relations */
1589  Assert(baserel->relid > 0);
1590  Assert(baserel->rtekind == RTE_RESULT);
1591 
1592  /* Mark the path with the correct row estimate */
1593  if (param_info)
1594  path->rows = param_info->ppi_rows;
1595  else
1596  path->rows = baserel->rows;
1597 
1598  /* We charge qual cost plus cpu_tuple_cost */
1599  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1600 
1601  startup_cost += qpqual_cost.startup;
1602  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1603  run_cost += cpu_per_tuple * baserel->tuples;
1604 
1605  path->startup_cost = startup_cost;
1606  path->total_cost = startup_cost + run_cost;
1607 }
double tuples
Definition: pathnodes.h:705
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
Index relid
Definition: pathnodes.h:693
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
double Cost
Definition: nodes.h:663

◆ cost_samplescan()

void cost_samplescan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 292 of file costsize.c.

References Assert, PathTarget::cost, cpu_tuple_cost, get_restriction_qual_cost(), get_tablespace_page_costs(), GetTsmRoutine(), TsmRoutine::NextSampleBlock, RelOptInfo::pages, Path::pathtarget, QualCost::per_tuple, planner_rt_fetch, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::reltablespace, RelOptInfo::rows, Path::rows, RTE_RELATION, RangeTblEntry::rtekind, QualCost::startup, Path::startup_cost, RangeTblEntry::tablesample, Path::total_cost, TableSampleClause::tsmhandler, and RelOptInfo::tuples.

Referenced by create_samplescan_path().

294 {
295  Cost startup_cost = 0;
296  Cost run_cost = 0;
297  RangeTblEntry *rte;
298  TableSampleClause *tsc;
299  TsmRoutine *tsm;
300  double spc_seq_page_cost,
301  spc_random_page_cost,
302  spc_page_cost;
303  QualCost qpqual_cost;
304  Cost cpu_per_tuple;
305 
306  /* Should only be applied to base relations with tablesample clauses */
307  Assert(baserel->relid > 0);
308  rte = planner_rt_fetch(baserel->relid, root);
309  Assert(rte->rtekind == RTE_RELATION);
310  tsc = rte->tablesample;
311  Assert(tsc != NULL);
312  tsm = GetTsmRoutine(tsc->tsmhandler);
313 
314  /* Mark the path with the correct row estimate */
315  if (param_info)
316  path->rows = param_info->ppi_rows;
317  else
318  path->rows = baserel->rows;
319 
320  /* fetch estimated page cost for tablespace containing table */
322  &spc_random_page_cost,
323  &spc_seq_page_cost);
324 
325  /* if NextSampleBlock is used, assume random access, else sequential */
326  spc_page_cost = (tsm->NextSampleBlock != NULL) ?
327  spc_random_page_cost : spc_seq_page_cost;
328 
329  /*
330  * disk costs (recall that baserel->pages has already been set to the
331  * number of pages the sampling method will visit)
332  */
333  run_cost += spc_page_cost * baserel->pages;
334 
335  /*
336  * CPU costs (recall that baserel->tuples has already been set to the
337  * number of tuples the sampling method will select). Note that we ignore
338  * execution cost of the TABLESAMPLE parameter expressions; they will be
339  * evaluated only once per scan, and in most usages they'll likely be
340  * simple constants anyway. We also don't charge anything for the
341  * calculations the sampling method might do internally.
342  */
343  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
344 
345  startup_cost += qpqual_cost.startup;
346  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
347  run_cost += cpu_per_tuple * baserel->tuples;
348  /* tlist eval costs are paid per output row, not per tuple scanned */
349  startup_cost += path->pathtarget->cost.startup;
350  run_cost += path->pathtarget->cost.per_tuple * path->rows;
351 
352  path->startup_cost = startup_cost;
353  path->total_cost = startup_cost + run_cost;
354 }
PathTarget * pathtarget
Definition: pathnodes.h:1145
double tuples
Definition: pathnodes.h:705
Oid reltablespace
Definition: pathnodes.h:694
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:373
NextSampleBlock_function NextSampleBlock
Definition: tsmapi.h:73
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:693
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
TsmRoutine * GetTsmRoutine(Oid tsmhandler)
Definition: tablesample.c:27
BlockNumber pages
Definition: pathnodes.h:704
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
RTEKind rtekind
Definition: parsenodes.h:976
struct TableSampleClause * tablesample
Definition: parsenodes.h:1006
double Cost
Definition: nodes.h:663

◆ cost_seqscan()

void cost_seqscan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 215 of file costsize.c.

References Assert, clamp_row_est(), PathTarget::cost, cpu_tuple_cost, disable_cost, enable_seqscan, get_parallel_divisor(), get_restriction_qual_cost(), get_tablespace_page_costs(), RelOptInfo::pages, Path::parallel_workers, Path::pathtarget, QualCost::per_tuple, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::reltablespace, RelOptInfo::rows, Path::rows, RTE_RELATION, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_seqscan_path().

217 {
218  Cost startup_cost = 0;
219  Cost cpu_run_cost;
220  Cost disk_run_cost;
221  double spc_seq_page_cost;
222  QualCost qpqual_cost;
223  Cost cpu_per_tuple;
224 
225  /* Should only be applied to base relations */
226  Assert(baserel->relid > 0);
227  Assert(baserel->rtekind == RTE_RELATION);
228 
229  /* Mark the path with the correct row estimate */
230  if (param_info)
231  path->rows = param_info->ppi_rows;
232  else
233  path->rows = baserel->rows;
234 
235  if (!enable_seqscan)
236  startup_cost += disable_cost;
237 
238  /* fetch estimated page cost for tablespace containing table */
240  NULL,
241  &spc_seq_page_cost);
242 
243  /*
244  * disk costs
245  */
246  disk_run_cost = spc_seq_page_cost * baserel->pages;
247 
248  /* CPU costs */
249  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
250 
251  startup_cost += qpqual_cost.startup;
252  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
253  cpu_run_cost = cpu_per_tuple * baserel->tuples;
254  /* tlist eval costs are paid per output row, not per tuple scanned */
255  startup_cost += path->pathtarget->cost.startup;
256  cpu_run_cost += path->pathtarget->cost.per_tuple * path->rows;
257 
258  /* Adjust costing for parallelism, if used. */
259  if (path->parallel_workers > 0)
260  {
261  double parallel_divisor = get_parallel_divisor(path);
262 
263  /* The CPU cost is divided among all the workers. */
264  cpu_run_cost /= parallel_divisor;
265 
266  /*
267  * It may be possible to amortize some of the I/O cost, but probably
268  * not very much, because most operating systems already do aggressive
269  * prefetching. For now, we assume that the disk run cost can't be
270  * amortized at all.
271  */
272 
273  /*
274  * In the case of a parallel plan, the row count needs to represent
275  * the number of tuples processed per worker.
276  */
277  path->rows = clamp_row_est(path->rows / parallel_divisor);
278  }
279 
280  path->startup_cost = startup_cost;
281  path->total_cost = startup_cost + cpu_run_cost + disk_run_cost;
282 }
PathTarget * pathtarget
Definition: pathnodes.h:1145
double tuples
Definition: pathnodes.h:705
Oid reltablespace
Definition: pathnodes.h:694
int parallel_workers
Definition: pathnodes.h:1151
bool enable_seqscan
Definition: costsize.c:125
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
Cost disable_cost
Definition: costsize.c:121
static double get_parallel_divisor(Path *path)
Definition: costsize.c:5661
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:693
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
BlockNumber pages
Definition: pathnodes.h:704
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
double clamp_row_est(double nrows)
Definition: costsize.c:191
double Cost
Definition: nodes.h:663

◆ cost_sort()

void cost_sort ( Path path,
PlannerInfo root,
List pathkeys,
Cost  input_cost,
double  tuples,
int  width,
Cost  comparison_cost,
int  sort_mem,
double  limit_tuples 
)

Definition at line 1891 of file costsize.c.

References cost_tuplesort(), disable_cost, enable_sort, Path::rows, Path::startup_cost, and Path::total_cost.

Referenced by adjust_foreign_grouping_path_cost(), choose_hashed_setop(), cost_append(), create_gather_merge_path(), create_groupingsets_path(), create_merge_append_path(), create_sort_path(), create_unique_path(), initial_cost_mergejoin(), label_sort_with_costsize(), and plan_cluster_use_sort().

1896 {
1897  Cost startup_cost;
1898  Cost run_cost;
1899 
1900  cost_tuplesort(&startup_cost, &run_cost,
1901  tuples, width,
1902  comparison_cost, sort_mem,
1903  limit_tuples);
1904 
1905  if (!enable_sort)
1906  startup_cost += disable_cost;
1907 
1908  startup_cost += input_cost;
1909 
1910  path->rows = tuples;
1911  path->startup_cost = startup_cost;
1912  path->total_cost = startup_cost + run_cost;
1913 }
bool enable_sort
Definition: costsize.c:130
Cost startup_cost
Definition: pathnodes.h:1155
Cost disable_cost
Definition: costsize.c:121
static void cost_tuplesort(Cost *startup_cost, Cost *run_cost, double tuples, int width, Cost comparison_cost, int sort_mem, double limit_tuples)
Definition: costsize.c:1688
Cost total_cost
Definition: pathnodes.h:1156
double rows
Definition: pathnodes.h:1154
double Cost
Definition: nodes.h:663

◆ cost_subplan()

void cost_subplan ( PlannerInfo root,
SubPlan subplan,
Plan plan 
)

Definition at line 3805 of file costsize.c.

References ALL_SUBLINK, ANY_SUBLINK, clamp_row_est(), cost_qual_eval(), cpu_operator_cost, ExecMaterializesOutput(), EXISTS_SUBLINK, make_ands_implicit(), NIL, nodeTag, SubPlan::parParam, SubPlan::per_call_cost, QualCost::per_tuple, Plan::plan_rows, QualCost::startup, Plan::startup_cost, SubPlan::startup_cost, SubPlan::subLinkType, SubPlan::testexpr, Plan::total_cost, and SubPlan::useHashTable.

Referenced by build_subplan(), SS_make_initplan_from_plan(), and SS_process_ctes().

3806 {
3807  QualCost sp_cost;
3808 
3809  /* Figure any cost for evaluating the testexpr */
3810  cost_qual_eval(&sp_cost,
3811  make_ands_implicit((Expr *) subplan->testexpr),
3812  root);
3813 
3814  if (subplan->useHashTable)
3815  {
3816  /*
3817  * If we are using a hash table for the subquery outputs, then the
3818  * cost of evaluating the query is a one-time cost. We charge one
3819  * cpu_operator_cost per tuple for the work of loading the hashtable,
3820  * too.
3821  */
3822  sp_cost.startup += plan->total_cost +
3823  cpu_operator_cost * plan->plan_rows;
3824 
3825  /*
3826  * The per-tuple costs include the cost of evaluating the lefthand
3827  * expressions, plus the cost of probing the hashtable. We already
3828  * accounted for the lefthand expressions as part of the testexpr, and
3829  * will also have counted one cpu_operator_cost for each comparison
3830  * operator. That is probably too low for the probing cost, but it's
3831  * hard to make a better estimate, so live with it for now.
3832  */
3833  }
3834  else
3835  {
3836  /*
3837  * Otherwise we will be rescanning the subplan output on each
3838  * evaluation. We need to estimate how much of the output we will
3839  * actually need to scan. NOTE: this logic should agree with the
3840  * tuple_fraction estimates used by make_subplan() in
3841  * plan/subselect.c.
3842  */
3843  Cost plan_run_cost = plan->total_cost - plan->startup_cost;
3844 
3845  if (subplan->subLinkType == EXISTS_SUBLINK)
3846  {
3847  /* we only need to fetch 1 tuple; clamp to avoid zero divide */
3848  sp_cost.per_tuple += plan_run_cost / clamp_row_est(plan->plan_rows);
3849  }
3850  else if (subplan->subLinkType == ALL_SUBLINK ||
3851  subplan->subLinkType == ANY_SUBLINK)
3852  {
3853  /* assume we need 50% of the tuples */
3854  sp_cost.per_tuple += 0.50 * plan_run_cost;
3855  /* also charge a cpu_operator_cost per row examined */
3856  sp_cost.per_tuple += 0.50 * plan->plan_rows * cpu_operator_cost;
3857  }
3858  else
3859  {
3860  /* assume we need all tuples */
3861  sp_cost.per_tuple += plan_run_cost;
3862  }
3863 
3864  /*
3865  * Also account for subplan's startup cost. If the subplan is
3866  * uncorrelated or undirect correlated, AND its topmost node is one
3867  * that materializes its output, assume that we'll only need to pay
3868  * its startup cost once; otherwise assume we pay the startup cost
3869  * every time.
3870  */
3871  if (subplan->parParam == NIL &&
3873  sp_cost.startup += plan->startup_cost;
3874  else
3875  sp_cost.per_tuple += plan->startup_cost;
3876  }
3877 
3878  subplan->startup_cost = sp_cost.startup;
3879  subplan->per_call_cost = sp_cost.per_tuple;
3880 }
#define NIL
Definition: pg_list.h:65
double plan_rows
Definition: plannodes.h:129
SubLinkType subLinkType
Definition: primnodes.h:704
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
void cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
Definition: costsize.c:4005
Cost startup_cost
Definition: plannodes.h:123
double cpu_operator_cost
Definition: costsize.c:115
List * make_ands_implicit(Expr *clause)
Definition: makefuncs.c:716
Node * testexpr
Definition: primnodes.h:706
Cost per_call_cost
Definition: primnodes.h:733
List * parParam
Definition: primnodes.h:729
#define nodeTag(nodeptr)
Definition: nodes.h:534
Cost total_cost
Definition: plannodes.h:124
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:623
bool useHashTable
Definition: primnodes.h:718
Cost startup_cost
Definition: primnodes.h:732
double clamp_row_est(double nrows)
Definition: costsize.c:191
double Cost
Definition: nodes.h:663

◆ cost_subqueryscan()

void cost_subqueryscan ( SubqueryScanPath path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 1286 of file costsize.c.

References Assert, PathTarget::cost, cpu_tuple_cost, get_restriction_qual_cost(), SubqueryScanPath::path, Path::pathtarget, QualCost::per_tuple, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::rows, Path::rows, RTE_SUBQUERY, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, SubqueryScanPath::subpath, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_subqueryscan_path().

1288 {
1289  Cost startup_cost;
1290  Cost run_cost;
1291  QualCost qpqual_cost;
1292  Cost cpu_per_tuple;
1293 
1294  /* Should only be applied to base relations that are subqueries */
1295  Assert(baserel->relid > 0);
1296  Assert(baserel->rtekind == RTE_SUBQUERY);
1297 
1298  /* Mark the path with the correct row estimate */
1299  if (param_info)
1300  path->path.rows = param_info->ppi_rows;
1301  else
1302  path->path.rows = baserel->rows;
1303 
1304  /*
1305  * Cost of path is cost of evaluating the subplan, plus cost of evaluating
1306  * any restriction clauses and tlist that will be attached to the
1307  * SubqueryScan node, plus cpu_tuple_cost to account for selection and
1308  * projection overhead.
1309  */
1310  path->path.startup_cost = path->subpath->startup_cost;
1311  path->path.total_cost = path->subpath->total_cost;
1312 
1313  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1314 
1315  startup_cost = qpqual_cost.startup;
1316  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1317  run_cost = cpu_per_tuple * baserel->tuples;
1318 
1319  /* tlist eval costs are paid per output row, not per tuple scanned */
1320  startup_cost += path->path.pathtarget->cost.startup;
1321  run_cost += path->path.pathtarget->cost.per_tuple * path->path.rows;
1322 
1323  path->path.startup_cost += startup_cost;
1324  path->path.total_cost += startup_cost + run_cost;
1325 }
PathTarget * pathtarget
Definition: pathnodes.h:1145
double tuples
Definition: pathnodes.h:705
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
Index relid
Definition: pathnodes.h:693
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
double Cost
Definition: nodes.h:663

◆ cost_tablefuncscan()

void cost_tablefuncscan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 1396 of file costsize.c.

References Assert, PathTarget::cost, cost_qual_eval_node(), cpu_tuple_cost, get_restriction_qual_cost(), Path::pathtarget, QualCost::per_tuple, planner_rt_fetch, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::rows, Path::rows, RTE_TABLEFUNC, RangeTblEntry::rtekind, QualCost::startup, Path::startup_cost, RangeTblEntry::tablefunc, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_tablefuncscan_path().

1398 {
1399  Cost startup_cost = 0;
1400  Cost run_cost = 0;
1401  QualCost qpqual_cost;
1402  Cost cpu_per_tuple;
1403  RangeTblEntry *rte;
1404  QualCost exprcost;
1405 
1406  /* Should only be applied to base relations that are functions */
1407  Assert(baserel->relid > 0);
1408  rte = planner_rt_fetch(baserel->relid, root);
1409  Assert(rte->rtekind == RTE_TABLEFUNC);
1410 
1411  /* Mark the path with the correct row estimate */
1412  if (param_info)
1413  path->rows = param_info->ppi_rows;
1414  else
1415  path->rows = baserel->rows;
1416 
1417  /*
1418  * Estimate costs of executing the table func expression(s).
1419  *
1420  * XXX in principle we ought to charge tuplestore spill costs if the
1421  * number of rows is large. However, given how phony our rowcount
1422  * estimates for tablefuncs tend to be, there's not a lot of point in that
1423  * refinement right now.
1424  */
1425  cost_qual_eval_node(&exprcost, (Node *) rte->tablefunc, root);
1426 
1427  startup_cost += exprcost.startup + exprcost.per_tuple;
1428 
1429  /* Add scanning CPU costs */
1430  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1431 
1432  startup_cost += qpqual_cost.startup;
1433  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1434  run_cost += cpu_per_tuple * baserel->tuples;
1435 
1436  /* tlist eval costs are paid per output row, not per tuple scanned */
1437  startup_cost += path->pathtarget->cost.startup;
1438  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1439 
1440  path->startup_cost = startup_cost;
1441  path->total_cost = startup_cost + run_cost;
1442 }
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4031
PathTarget * pathtarget
Definition: pathnodes.h:1145
double tuples
Definition: pathnodes.h:705
Definition: nodes.h:529
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
TableFunc * tablefunc
Definition: parsenodes.h:1069
Cost startup_cost
Definition: pathnodes.h:1155
#define planner_rt_fetch(rti, root)
Definition: pathnodes.h:373
Index relid
Definition: pathnodes.h:693
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
RTEKind rtekind
Definition: parsenodes.h:976
double Cost
Definition: nodes.h:663

◆ cost_tidscan()

void cost_tidscan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
List tidquals,
ParamPathInfo param_info 
)

Definition at line 1180 of file costsize.c.

References ScalarArrayOpExpr::args, Assert, RelOptInfo::baserestrictcost, RestrictInfo::clause, PathTarget::cost, cost_qual_eval(), cpu_tuple_cost, disable_cost, enable_tidscan, estimate_array_length(), get_restriction_qual_cost(), get_tablespace_page_costs(), IsA, lfirst_node, lsecond, Path::pathtarget, QualCost::per_tuple, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::reltablespace, RelOptInfo::rows, Path::rows, RTE_RELATION, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, and Path::total_cost.

Referenced by create_tidscan_path().

1182 {
1183  Cost startup_cost = 0;
1184  Cost run_cost = 0;
1185  bool isCurrentOf = false;
1186  QualCost qpqual_cost;
1187  Cost cpu_per_tuple;
1188  QualCost tid_qual_cost;
1189  int ntuples;
1190  ListCell *l;
1191  double spc_random_page_cost;
1192 
1193  /* Should only be applied to base relations */
1194  Assert(baserel->relid > 0);
1195  Assert(baserel->rtekind == RTE_RELATION);
1196 
1197  /* Mark the path with the correct row estimate */
1198  if (param_info)
1199  path->rows = param_info->ppi_rows;
1200  else
1201  path->rows = baserel->rows;
1202 
1203  /* Count how many tuples we expect to retrieve */
1204  ntuples = 0;
1205  foreach(l, tidquals)
1206  {
1207  RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
1208  Expr *qual = rinfo->clause;
1209 
1210  if (IsA(qual, ScalarArrayOpExpr))
1211  {
1212  /* Each element of the array yields 1 tuple */
1213  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) qual;
1214  Node *arraynode = (Node *) lsecond(saop->args);
1215 
1216  ntuples += estimate_array_length(arraynode);
1217  }
1218  else if (IsA(qual, CurrentOfExpr))
1219  {
1220  /* CURRENT OF yields 1 tuple */
1221  isCurrentOf = true;
1222  ntuples++;
1223  }
1224  else
1225  {
1226  /* It's just CTID = something, count 1 tuple */
1227  ntuples++;
1228  }
1229  }
1230 
1231  /*
1232  * We must force TID scan for WHERE CURRENT OF, because only nodeTidscan.c
1233  * understands how to do it correctly. Therefore, honor enable_tidscan
1234  * only when CURRENT OF isn't present. Also note that cost_qual_eval
1235  * counts a CurrentOfExpr as having startup cost disable_cost, which we
1236  * subtract off here; that's to prevent other plan types such as seqscan
1237  * from winning.
1238  */
1239  if (isCurrentOf)
1240  {
1242  startup_cost -= disable_cost;
1243  }
1244  else if (!enable_tidscan)
1245  startup_cost += disable_cost;
1246 
1247  /*
1248  * The TID qual expressions will be computed once, any other baserestrict
1249  * quals once per retrieved tuple.
1250  */
1251  cost_qual_eval(&tid_qual_cost, tidquals, root);
1252 
1253  /* fetch estimated page cost for tablespace containing table */
1255  &spc_random_page_cost,
1256  NULL);
1257 
1258  /* disk costs --- assume each tuple on a different page */
1259  run_cost += spc_random_page_cost * ntuples;
1260 
1261  /* Add scanning CPU costs */
1262  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1263 
1264  /* XXX currently we assume TID quals are a subset of qpquals */
1265  startup_cost += qpqual_cost.startup + tid_qual_cost.per_tuple;
1266  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple -
1267  tid_qual_cost.per_tuple;
1268  run_cost += cpu_per_tuple * ntuples;
1269 
1270  /* tlist eval costs are paid per output row, not per tuple scanned */
1271  startup_cost += path->pathtarget->cost.startup;
1272  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1273 
1274  path->startup_cost = startup_cost;
1275  path->total_cost = startup_cost + run_cost;
1276 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
PathTarget * pathtarget
Definition: pathnodes.h:1145
bool enable_tidscan
Definition: costsize.c:129
Oid reltablespace
Definition: pathnodes.h:694
Definition: nodes.h:529
#define lsecond(l)
Definition: pg_list.h:200
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
int estimate_array_length(Node *arrayexpr)
Definition: selfuncs.c:2018
void cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
Definition: costsize.c:4005
Cost startup_cost
Definition: pathnodes.h:1155
Cost disable_cost
Definition: costsize.c:121
#define lfirst_node(type, lc)
Definition: pg_list.h:193
void get_tablespace_page_costs(Oid spcid, double *spc_random_page_cost, double *spc_seq_page_cost)
Definition: spccache.c:182
Index relid
Definition: pathnodes.h:693
Expr * clause
Definition: pathnodes.h:1985
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
QualCost baserestrictcost
Definition: pathnodes.h:728
double Cost
Definition: nodes.h:663

◆ cost_tuplesort()

static void cost_tuplesort ( Cost startup_cost,
Cost run_cost,
double  tuples,
int  width,
Cost  comparison_cost,
int  sort_mem,
double  limit_tuples 
)
static

Definition at line 1688 of file costsize.c.

References cpu_operator_cost, LOG2, random_page_cost, relation_byte_size(), seq_page_cost, and tuplesort_merge_order().

Referenced by cost_incremental_sort(), and cost_sort().

1692 {
1693  double input_bytes = relation_byte_size(tuples, width);
1694  double output_bytes;
1695  double output_tuples;
1696  long sort_mem_bytes = sort_mem * 1024L;
1697 
1698  /*
1699  * We want to be sure the cost of a sort is never estimated as zero, even
1700  * if passed-in tuple count is zero. Besides, mustn't do log(0)...
1701  */
1702  if (tuples < 2.0)
1703  tuples = 2.0;
1704 
1705  /* Include the default cost-per-comparison */
1706  comparison_cost += 2.0 * cpu_operator_cost;
1707 
1708  /* Do we have a useful LIMIT? */
1709  if (limit_tuples > 0 && limit_tuples < tuples)
1710  {
1711  output_tuples = limit_tuples;
1712  output_bytes = relation_byte_size(output_tuples, width);
1713  }
1714  else
1715  {
1716  output_tuples = tuples;
1717  output_bytes = input_bytes;
1718  }
1719 
1720  if (output_bytes > sort_mem_bytes)
1721  {
1722  /*
1723  * We'll have to use a disk-based sort of all the tuples
1724  */
1725  double npages = ceil(input_bytes / BLCKSZ);
1726  double nruns = input_bytes / sort_mem_bytes;
1727  double mergeorder = tuplesort_merge_order(sort_mem_bytes);
1728  double log_runs;
1729  double npageaccesses;
1730 
1731  /*
1732  * CPU costs
1733  *
1734  * Assume about N log2 N comparisons
1735  */
1736  *startup_cost = comparison_cost * tuples * LOG2(tuples);
1737 
1738  /* Disk costs */
1739 
1740  /* Compute logM(r) as log(r) / log(M) */
1741  if (nruns > mergeorder)
1742  log_runs = ceil(log(nruns) / log(mergeorder));
1743  else
1744  log_runs = 1.0;
1745  npageaccesses = 2.0 * npages * log_runs;
1746  /* Assume 3/4ths of accesses are sequential, 1/4th are not */
1747  *startup_cost += npageaccesses *
1748  (seq_page_cost * 0.75 + random_page_cost * 0.25);
1749  }
1750  else if (tuples > 2 * output_tuples || input_bytes > sort_mem_bytes)
1751  {
1752  /*
1753  * We'll use a bounded heap-sort keeping just K tuples in memory, for
1754  * a total number of tuple comparisons of N log2 K; but the constant
1755  * factor is a bit higher than for quicksort. Tweak it so that the
1756  * cost curve is continuous at the crossover point.
1757  */
1758  *startup_cost = comparison_cost * tuples * LOG2(2.0 * output_tuples);
1759  }
1760  else
1761  {
1762  /* We'll use plain quicksort on all the input tuples */
1763  *startup_cost = comparison_cost * tuples * LOG2(tuples);
1764  }
1765 
1766  /*
1767  * Also charge a small amount (arbitrarily set equal to operator cost) per
1768  * extracted tuple. We don't charge cpu_tuple_cost because a Sort node
1769  * doesn't do qual-checking or projection, so it has less overhead than
1770  * most plan nodes. Note it's correct to use tuples not output_tuples
1771  * here --- the upper LIMIT will pro-rate the run cost so we'd be double
1772  * counting the LIMIT otherwise.
1773  */
1774  *run_cost = cpu_operator_cost * tuples;
1775 }
double random_page_cost
Definition: costsize.c:112
double cpu_operator_cost
Definition: costsize.c:115
static double relation_byte_size(double tuples, int width)
Definition: costsize.c:5640
#define LOG2(x)
Definition: costsize.c:101
int tuplesort_merge_order(int64 allowedMem)
Definition: tuplesort.c:2526
double seq_page_cost
Definition: costsize.c:111

◆ cost_valuesscan()

void cost_valuesscan ( Path path,
PlannerInfo root,
RelOptInfo baserel,
ParamPathInfo param_info 
)

Definition at line 1452 of file costsize.c.

References Assert, PathTarget::cost, cpu_operator_cost, cpu_tuple_cost, get_restriction_qual_cost(), Path::pathtarget, QualCost::per_tuple, ParamPathInfo::ppi_rows, RelOptInfo::relid, RelOptInfo::rows, Path::rows, RTE_VALUES, RelOptInfo::rtekind, QualCost::startup, Path::startup_cost, Path::total_cost, and RelOptInfo::tuples.

Referenced by create_valuesscan_path().

1454 {
1455  Cost startup_cost = 0;
1456  Cost run_cost = 0;
1457  QualCost qpqual_cost;
1458  Cost cpu_per_tuple;
1459 
1460  /* Should only be applied to base relations that are values lists */
1461  Assert(baserel->relid > 0);
1462  Assert(baserel->rtekind == RTE_VALUES);
1463 
1464  /* Mark the path with the correct row estimate */
1465  if (param_info)
1466  path->rows = param_info->ppi_rows;
1467  else
1468  path->rows = baserel->rows;
1469 
1470  /*
1471  * For now, estimate list evaluation cost at one operator eval per list
1472  * (probably pretty bogus, but is it worth being smarter?)
1473  */
1474  cpu_per_tuple = cpu_operator_cost;
1475 
1476  /* Add scanning CPU costs */
1477  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1478 
1479  startup_cost += qpqual_cost.startup;
1480  cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1481  run_cost += cpu_per_tuple * baserel->tuples;
1482 
1483  /* tlist eval costs are paid per output row, not per tuple scanned */
1484  startup_cost += path->pathtarget->cost.startup;
1485  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1486 
1487  path->startup_cost = startup_cost;
1488  path->total_cost = startup_cost + run_cost;
1489 }
PathTarget * pathtarget
Definition: pathnodes.h:1145
double tuples
Definition: pathnodes.h:705
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
double cpu_operator_cost
Definition: costsize.c:115
Index relid
Definition: pathnodes.h:693
RTEKind rtekind
Definition: pathnodes.h:695
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel, ParamPathInfo *param_info, QualCost *qpqual_cost)
Definition: costsize.c:4291
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
double Cost
Definition: nodes.h:663

◆ cost_windowagg()

void cost_windowagg ( Path path,
PlannerInfo root,
List windowFuncs,
int  numPartCols,
int  numOrderCols,
Cost  input_startup_cost,
Cost  input_total_cost,
double  input_tuples 
)

Definition at line 2458 of file costsize.c.

References add_function_cost(), cost_qual_eval_node(), cpu_operator_cost, cpu_tuple_cost, lfirst_node, QualCost::per_tuple, Path::rows, QualCost::startup, Path::startup_cost, Path::total_cost, and WindowFunc::winfnoid.

Referenced by create_windowagg_path().

2462 {
2463  Cost startup_cost;
2464  Cost total_cost;
2465  ListCell *lc;
2466 
2467  startup_cost = input_startup_cost;
2468  total_cost = input_total_cost;
2469 
2470  /*
2471  * Window functions are assumed to cost their stated execution cost, plus
2472  * the cost of evaluating their input expressions, per tuple. Since they
2473  * may in fact evaluate their inputs at multiple rows during each cycle,
2474  * this could be a drastic underestimate; but without a way to know how
2475  * many rows the window function will fetch, it's hard to do better. In
2476  * any case, it's a good estimate for all the built-in window functions,
2477  * so we'll just do this for now.
2478  */
2479  foreach(lc, windowFuncs)
2480  {
2481  WindowFunc *wfunc = lfirst_node(WindowFunc, lc);
2482  Cost wfunccost;
2483  QualCost argcosts;
2484 
2485  argcosts.startup = argcosts.per_tuple = 0;
2486  add_function_cost(root, wfunc->winfnoid, (Node *) wfunc,
2487  &argcosts);
2488  startup_cost += argcosts.startup;
2489  wfunccost = argcosts.per_tuple;
2490 
2491  /* also add the input expressions' cost to per-input-row costs */
2492  cost_qual_eval_node(&argcosts, (Node *) wfunc->args, root);
2493  startup_cost += argcosts.startup;
2494  wfunccost += argcosts.per_tuple;
2495 
2496  /*
2497  * Add the filter's cost to per-input-row costs. XXX We should reduce
2498  * input expression costs according to filter selectivity.
2499  */
2500  cost_qual_eval_node(&argcosts, (Node *) wfunc->aggfilter, root);
2501  startup_cost += argcosts.startup;
2502  wfunccost += argcosts.per_tuple;
2503 
2504  total_cost += wfunccost * input_tuples;
2505  }
2506 
2507  /*
2508  * We also charge cpu_operator_cost per grouping column per tuple for
2509  * grouping comparisons, plus cpu_tuple_cost per tuple for general
2510  * overhead.
2511  *
2512  * XXX this neglects costs of spooling the data to disk when it overflows
2513  * work_mem. Sooner or later that should get accounted for.
2514  */
2515  total_cost += cpu_operator_cost * (numPartCols + numOrderCols) * input_tuples;
2516  total_cost += cpu_tuple_cost * input_tuples;
2517 
2518  path->rows = input_tuples;
2519  path->startup_cost = startup_cost;
2520  path->total_cost = total_cost;
2521 }
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4031
List * args
Definition: primnodes.h:377
Definition: nodes.h:529
void add_function_cost(PlannerInfo *root, Oid funcid, Node *node, QualCost *cost)
Definition: plancat.c:1908
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
Cost startup_cost
Definition: pathnodes.h:1155
#define lfirst_node(type, lc)
Definition: pg_list.h:193
double cpu_operator_cost
Definition: costsize.c:115
Oid winfnoid
Definition: primnodes.h:373
Cost total_cost
Definition: pathnodes.h:1156
Expr * aggfilter
Definition: primnodes.h:378
double rows
Definition: pathnodes.h:1154
double cpu_tuple_cost
Definition: costsize.c:113
double Cost
Definition: nodes.h:663

◆ extract_nonindex_conditions()

static List * extract_nonindex_conditions ( List qual_clauses,
List indexclauses 
)
static

Definition at line 771 of file costsize.c.

References is_redundant_with_indexclauses(), lappend(), lfirst_node, NIL, and RestrictInfo::pseudoconstant.

Referenced by cost_index().

772 {
773  List *result = NIL;
774  ListCell *lc;
775 
776  foreach(lc, qual_clauses)
777  {
778  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
779 
780  if (rinfo->pseudoconstant)
781  continue; /* we may drop pseudoconstants here */
782  if (is_redundant_with_indexclauses(rinfo, indexclauses))
783  continue; /* dup or derived from same EquivalenceClass */
784  /* ... skip the predicate proof attempt createplan.c will try ... */
785  result = lappend(result, rinfo);
786  }
787  return result;
788 }
#define NIL
Definition: pg_list.h:65
bool pseudoconstant
Definition: pathnodes.h:1993
bool is_redundant_with_indexclauses(RestrictInfo *rinfo, List *indexclauses)
Definition: equivclass.c:2851
#define lfirst_node(type, lc)
Definition: pg_list.h:193
List * lappend(List *list, void *datum)
Definition: list.c:321
Definition: pg_list.h:50

◆ final_cost_hashjoin()

void final_cost_hashjoin ( PlannerInfo root,
HashPath path,
JoinCostWorkspace workspace,
JoinPathExtraData extra 
)

Definition at line 3550 of file costsize.c.

References approx_tuple_count(), Assert, bms_is_subset(), clamp_row_est(), RestrictInfo::clause, PathTarget::cost, cost_qual_eval(), cpu_tuple_cost, disable_cost, enable_hashjoin, estimate_hash_bucket_stats(), get_leftop(), get_parallel_divisor(), get_rightop(), HashPath::inner_rows_total, JoinCostWorkspace::inner_rows_total, JoinPathExtraData::inner_unique, JoinPath::innerjoinpath, IsA, JOIN_ANTI, JOIN_SEMI, JoinPath::joinrestrictinfo, JoinPath::jointype, HashPath::jpath, RestrictInfo::left_bucketsize, RestrictInfo::left_mcvfreq, RestrictInfo::left_relids, lfirst_node, SemiAntiJoinFactors::match_count, HashPath::num_batches, JoinCostWorkspace::numbatches, JoinCostWorkspace::numbuckets, SemiAntiJoinFactors::outer_match_frac, JoinPath::outerjoinpath, Path::parallel_workers, Path::param_info, Path::parent, JoinPath::path, HashPath::path_hashclauses, Path::pathtarget, QualCost::per_tuple, ParamPathInfo::ppi_rows, relation_byte_size(), RelOptInfo::relids, RestrictInfo::right_bucketsize, RestrictInfo::right_mcvfreq, RestrictInfo::right_relids, RelOptInfo::rows, Path::rows, JoinCostWorkspace::run_cost, JoinPathExtraData::semifactors, QualCost::startup, Path::startup_cost, JoinCostWorkspace::startup_cost, Path::total_cost, PathTarget::width, and work_mem.

Referenced by create_hashjoin_path().

3553 {
3554  Path *outer_path = path->jpath.outerjoinpath;
3555  Path *inner_path = path->jpath.innerjoinpath;
3556  double outer_path_rows = outer_path->rows;
3557  double inner_path_rows = inner_path->rows;
3558  double inner_path_rows_total = workspace->inner_rows_total;
3559  List *hashclauses = path->path_hashclauses;
3560  Cost startup_cost = workspace->startup_cost;
3561  Cost run_cost = workspace->run_cost;
3562  int numbuckets = workspace->numbuckets;
3563  int numbatches = workspace->numbatches;
3564  Cost cpu_per_tuple;
3565  QualCost hash_qual_cost;
3566  QualCost qp_qual_cost;
3567  double hashjointuples;
3568  double virtualbuckets;
3569  Selectivity innerbucketsize;
3570  Selectivity innermcvfreq;
3571  ListCell *hcl;
3572 
3573  /* Mark the path with the correct row estimate */
3574  if (path->jpath.path.param_info)
3575  path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
3576  else
3577  path->jpath.path.rows = path->jpath.path.parent->rows;
3578 
3579  /* For partial paths, scale row estimate. */
3580  if (path->jpath.path.parallel_workers > 0)
3581  {
3582  double parallel_divisor = get_parallel_divisor(&path->jpath.path);
3583 
3584  path->jpath.path.rows =
3585  clamp_row_est(path->jpath.path.rows / parallel_divisor);
3586  }
3587 
3588  /*
3589  * We could include disable_cost in the preliminary estimate, but that
3590  * would amount to optimizing for the case where the join method is
3591  * disabled, which doesn't seem like the way to bet.
3592  */
3593  if (!enable_hashjoin)
3594  startup_cost += disable_cost;
3595 
3596  /* mark the path with estimated # of batches */
3597  path->num_batches = numbatches;
3598 
3599  /* store the total number of tuples (sum of partial row estimates) */
3600  path->inner_rows_total = inner_path_rows_total;
3601 
3602  /* and compute the number of "virtual" buckets in the whole join */
3603  virtualbuckets = (double) numbuckets * (double) numbatches;
3604 
3605  /*
3606  * Determine bucketsize fraction and MCV frequency for the inner relation.
3607  * We use the smallest bucketsize or MCV frequency estimated for any
3608  * individual hashclause; this is undoubtedly conservative.
3609  *
3610  * BUT: if inner relation has been unique-ified, we can assume it's good
3611  * for hashing. This is important both because it's the right answer, and
3612  * because we avoid contaminating the cache with a value that's wrong for
3613  * non-unique-ified paths.
3614  */
3615  if (IsA(inner_path, UniquePath))
3616  {
3617  innerbucketsize = 1.0 / virtualbuckets;
3618  innermcvfreq = 0.0;
3619  }
3620  else
3621  {
3622  innerbucketsize = 1.0;
3623  innermcvfreq = 1.0;
3624  foreach(hcl, hashclauses)
3625  {
3626  RestrictInfo *restrictinfo = lfirst_node(RestrictInfo, hcl);
3627  Selectivity thisbucketsize;
3628  Selectivity thismcvfreq;
3629 
3630  /*
3631  * First we have to figure out which side of the hashjoin clause
3632  * is the inner side.
3633  *
3634  * Since we tend to visit the same clauses over and over when
3635  * planning a large query, we cache the bucket stats estimates in
3636  * the RestrictInfo node to avoid repeated lookups of statistics.
3637  */
3638  if (bms_is_subset(restrictinfo->right_relids,
3639  inner_path->parent->relids))
3640  {
3641  /* righthand side is inner */
3642  thisbucketsize = restrictinfo->right_bucketsize;
3643  if (thisbucketsize < 0)
3644  {
3645  /* not cached yet */
3647  get_rightop(restrictinfo->clause),
3648  virtualbuckets,
3649  &restrictinfo->right_mcvfreq,
3650  &restrictinfo->right_bucketsize);
3651  thisbucketsize = restrictinfo->right_bucketsize;
3652  }
3653  thismcvfreq = restrictinfo->right_mcvfreq;
3654  }
3655  else
3656  {
3657  Assert(bms_is_subset(restrictinfo->left_relids,
3658  inner_path->parent->relids));
3659  /* lefthand side is inner */
3660  thisbucketsize = restrictinfo->left_bucketsize;
3661  if (thisbucketsize < 0)
3662  {
3663  /* not cached yet */
3665  get_leftop(restrictinfo->clause),
3666  virtualbuckets,
3667  &restrictinfo->left_mcvfreq,
3668  &restrictinfo->left_bucketsize);
3669  thisbucketsize = restrictinfo->left_bucketsize;
3670  }
3671  thismcvfreq = restrictinfo->left_mcvfreq;
3672  }
3673 
3674  if (innerbucketsize > thisbucketsize)
3675  innerbucketsize = thisbucketsize;
3676  if (innermcvfreq > thismcvfreq)
3677  innermcvfreq = thismcvfreq;
3678  }
3679  }
3680 
3681  /*
3682  * If the bucket holding the inner MCV would exceed work_mem, we don't
3683  * want to hash unless there is really no other alternative, so apply
3684  * disable_cost. (The executor normally copes with excessive memory usage
3685  * by splitting batches, but obviously it cannot separate equal values
3686  * that way, so it will be unable to drive the batch size below work_mem
3687  * when this is true.)
3688  */
3689  if (relation_byte_size(clamp_row_est(inner_path_rows * innermcvfreq),
3690  inner_path->pathtarget->width) >
3691  (work_mem * 1024L))
3692  startup_cost += disable_cost;
3693 
3694  /*
3695  * Compute cost of the hashquals and qpquals (other restriction clauses)
3696  * separately.
3697  */
3698  cost_qual_eval(&hash_qual_cost, hashclauses, root);
3699  cost_qual_eval(&qp_qual_cost, path->jpath.joinrestrictinfo, root);
3700  qp_qual_cost.startup -= hash_qual_cost.startup;
3701  qp_qual_cost.per_tuple -= hash_qual_cost.per_tuple;
3702 
3703  /* CPU costs */
3704 
3705  if (path->jpath.jointype == JOIN_SEMI ||
3706  path->jpath.jointype == JOIN_ANTI ||
3707  extra->inner_unique)
3708  {
3709  double outer_matched_rows;
3710  Selectivity inner_scan_frac;
3711 
3712  /*
3713  * With a SEMI or ANTI join, or if the innerrel is known unique, the
3714  * executor will stop after the first match.
3715  *
3716  * For an outer-rel row that has at least one match, we can expect the
3717  * bucket scan to stop after a fraction 1/(match_count+1) of the
3718  * bucket's rows, if the matches are evenly distributed. Since they
3719  * probably aren't quite evenly distributed, we apply a fuzz factor of
3720  * 2.0 to that fraction. (If we used a larger fuzz factor, we'd have
3721  * to clamp inner_scan_frac to at most 1.0; but since match_count is
3722  * at least 1, no such clamp is needed now.)
3723  */
3724  outer_matched_rows = rint(outer_path_rows * extra->semifactors.outer_match_frac);
3725  inner_scan_frac = 2.0 / (extra->semifactors.match_count + 1.0);
3726 
3727  startup_cost += hash_qual_cost.startup;
3728  run_cost += hash_qual_cost.per_tuple * outer_matched_rows *
3729  clamp_row_est(inner_path_rows * innerbucketsize * inner_scan_frac) * 0.5;
3730 
3731  /*
3732  * For unmatched outer-rel rows, the picture is quite a lot different.
3733  * In the first place, there is no reason to assume that these rows
3734  * preferentially hit heavily-populated buckets; instead assume they
3735  * are uncorrelated with the inner distribution and so they see an
3736  * average bucket size of inner_path_rows / virtualbuckets. In the
3737  * second place, it seems likely that they will have few if any exact
3738  * hash-code matches and so very few of the tuples in the bucket will
3739  * actually require eval of the hash quals. We don't have any good
3740  * way to estimate how many will, but for the moment assume that the
3741  * effective cost per bucket entry is one-tenth what it is for
3742  * matchable tuples.
3743  */
3744  run_cost += hash_qual_cost.per_tuple *
3745  (outer_path_rows - outer_matched_rows) *
3746  clamp_row_est(inner_path_rows / virtualbuckets) * 0.05;
3747 
3748  /* Get # of tuples that will pass the basic join */
3749  if (path->jpath.jointype == JOIN_ANTI)
3750  hashjointuples = outer_path_rows - outer_matched_rows;
3751  else
3752  hashjointuples = outer_matched_rows;
3753  }
3754  else
3755  {
3756  /*
3757  * The number of tuple comparisons needed is the number of outer
3758  * tuples times the typical number of tuples in a hash bucket, which
3759  * is the inner relation size times its bucketsize fraction. At each
3760  * one, we need to evaluate the hashjoin quals. But actually,
3761  * charging the full qual eval cost at each tuple is pessimistic,
3762  * since we don't evaluate the quals unless the hash values match
3763  * exactly. For lack of a better idea, halve the cost estimate to
3764  * allow for that.
3765  */
3766  startup_cost += hash_qual_cost.startup;
3767  run_cost += hash_qual_cost.per_tuple * outer_path_rows *
3768  clamp_row_est(inner_path_rows * innerbucketsize) * 0.5;
3769 
3770  /*
3771  * Get approx # tuples passing the hashquals. We use
3772  * approx_tuple_count here because we need an estimate done with
3773  * JOIN_INNER semantics.
3774  */
3775  hashjointuples = approx_tuple_count(root, &path->jpath, hashclauses);
3776  }
3777 
3778  /*
3779  * For each tuple that gets through the hashjoin proper, we charge
3780  * cpu_tuple_cost plus the cost of evaluating additional restriction
3781  * clauses that are to be applied at the join. (This is pessimistic since
3782  * not all of the quals may get evaluated at each tuple.)
3783  */
3784  startup_cost += qp_qual_cost.startup;
3785  cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
3786  run_cost += cpu_per_tuple * hashjointuples;
3787 
3788  /* tlist eval costs are paid per output row, not per tuple scanned */
3789  startup_cost += path->jpath.path.pathtarget->cost.startup;
3790  run_cost += path->jpath.path.pathtarget->cost.per_tuple * path->jpath.path.rows;
3791 
3792  path->jpath.path.startup_cost = startup_cost;
3793  path->jpath.path.total_cost = startup_cost + run_cost;
3794 }
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
JoinPath jpath
Definition: pathnodes.h:1599
PathTarget * pathtarget
Definition: pathnodes.h:1145
SemiAntiJoinFactors semifactors
Definition: pathnodes.h:2428
int num_batches
Definition: pathnodes.h:1601
Selectivity right_mcvfreq
Definition: pathnodes.h:2049
Selectivity outer_match_frac
Definition: pathnodes.h:2405
Path * innerjoinpath
Definition: pathnodes.h:1526
static double approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals)
Definition: costsize.c:4534
int parallel_workers
Definition: pathnodes.h:1151
ParamPathInfo * param_info
Definition: pathnodes.h:1147
Relids left_relids
Definition: pathnodes.h:2012
double Selectivity
Definition: nodes.h:662
double inner_rows_total
Definition: pathnodes.h:1602
Cost startup
Definition: pathnodes.h:45
Cost per_tuple
Definition: pathnodes.h:46
void cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
Definition: costsize.c:4005
Cost startup_cost
Definition: pathnodes.h:1155
Cost disable_cost
Definition: costsize.c:121
List * joinrestrictinfo
Definition: pathnodes.h:1528
RelOptInfo * parent
Definition: pathnodes.h:1144
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:315
#define lfirst_node(type, lc)
Definition: pg_list.h:193
static double get_parallel_divisor(Path *path)
Definition: costsize.c:5661
Relids relids
Definition: pathnodes.h:665
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:70
Expr * clause
Definition: pathnodes.h:1985
static double relation_byte_size(double tuples, int width)
Definition: costsize.c:5640
Path * outerjoinpath
Definition: pathnodes.h:1525
double inner_rows_total
Definition: pathnodes.h:2549
int work_mem
Definition: globals.c:121
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:82
double rows
Definition: pathnodes.h:668
Cost total_cost
Definition: pathnodes.h:1156
Selectivity left_bucketsize
Definition: pathnodes.h:2046
Relids right_relids
Definition: pathnodes.h:2013
Path path
Definition: pathnodes.h:1518
#define Assert(condition)
Definition: c.h:738
double rows
Definition: pathnodes.h:1154
Selectivity left_mcvfreq
Definition: pathnodes.h:2048
QualCost cost
Definition: pathnodes.h:1076
double cpu_tuple_cost
Definition: costsize.c:113
double ppi_rows
Definition: pathnodes.h:1104
bool enable_hashjoin
Definition: costsize.c:138
Selectivity match_count
Definition: pathnodes.h:2406
Selectivity right_bucketsize
Definition: pathnodes.h:2047
JoinType jointype
Definition: pathnodes.h:1520
void estimate_hash_bucket_stats(PlannerInfo *root, Node *hashkey, double nbuckets, Selectivity *mcv_freq, Selectivity *bucketsize_frac)
Definition: selfuncs.c:3568
List * path_hashclauses
Definition: pathnodes.h:1600
double clamp_row_est(double nrows)
Definition: costsize.c:191
Definition: pg_list.h:50
double Cost
Definition: nodes.h:663

◆ final_cost_mergejoin()

void final_cost_mergejoin ( PlannerInfo root,
MergePath path,
JoinCostWorkspace workspace,
JoinPathExtraData extra 
)

Definition at line 3114 of file costsize.c.

References approx_tuple_count(), clamp_row_est(), PathTarget::cost, cost_qual_eval(), cpu_operator_cost, cpu_tuple_cost, disable_cost, enable_material, enable_mergejoin, ExecSupportsMarkRestore(), get_parallel_divisor(), JoinCostWorkspace::inner_rows, JoinCostWorkspace::inner_run_cost, JoinCostWorkspace::inner_skip_rows, JoinPathExtraData::inner_unique, JoinPath::innerjoinpath, MergePath::innersortkeys, IsA, JOIN_ANTI, JOIN_SEMI, JoinPath::joinrestrictinfo, JoinPath::jointype, MergePath::jpath, list_length(), MergePath::materialize_inner, NIL, JoinCostWorkspace::outer_rows, JoinCostWorkspace::outer_skip_rows, JoinPath::outerjoinpath, Path::parallel_workers, Path::param_info, Path::parent, JoinPath::path, MergePath::path_mergeclauses, Path::pathtarget, QualCost::per_tuple, ParamPathInfo::ppi_rows, relation_byte_size(), RelOptInfo::rows, Path::rows, JoinCostWorkspace::run_cost, MergePath::skip_mark_restore, QualCost::startup, Path::startup_cost, JoinCostWorkspace::startup_cost, Path::total_cost, PathTarget::width, and work_mem.

Referenced by create_mergejoin_path().

3117 {
3118  Path *outer_path = path->jpath.outerjoinpath;
3119  Path *inner_path = path->jpath.innerjoinpath;
3120  double inner_path_rows = inner_path->rows;
3121  List *mergeclauses = path->path_mergeclauses;
3122  List *innersortkeys = path->innersortkeys;
3123  Cost startup_cost = workspace->startup_cost;
3124  Cost run_cost = workspace->run_cost;
3125  Cost inner_run_cost = workspace->inner_run_cost;
3126  double outer_rows = workspace->outer_rows;
3127  double inner_rows = workspace->inner_rows;
3128  double outer_skip_rows = workspace->outer_skip_rows;
3129  double inner_skip_rows = workspace->inner_skip_rows;
3130  Cost cpu_per_tuple,
3131  bare_inner_cost,
3132  mat_inner_cost;
3133  QualCost merge_qual_cost;
3134  QualCost qp_qual_cost;
3135  double mergejointuples,
3136  rescannedtuples;
3137  double rescanratio;
3138 
3139  /* Protect some assumptions below that rowcounts aren't zero or NaN */
3140  if (inner_path_rows <= 0 || isnan(inner_path_rows))
3141  inner_path_rows = 1;
3142 
3143  /* Mark the path with the correct row estimate */
3144  if (path->jpath.path.param_info)
3145  path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
3146  else
3147  path->jpath.path.rows = path->jpath.path.parent->rows;
3148 
3149  /* For partial paths, scale row estimate. */
3150  if (path->jpath.path.parallel_workers > 0)
3151  {
3152  double parallel_divisor = get_parallel_divisor(&path->jpath.path);
3153 
3154  path->jpath.path.rows =
3155  clamp_row_est(path->jpath.path.rows / parallel_divisor);
3156  }
3157 
3158  /*
3159  * We could include disable_cost in the preliminary estimate, but that
3160  * would amount to optimizing for the case where the join method is
3161  * disabled, which doesn't seem like the way to bet.
3162  */
3163  if (!enable_mergejoin)
3164  startup_cost += disable_cost;
3165 
3166  /*
3167  * Compute cost of the mergequals and qpquals (other restriction clauses)
3168  * separately.
3169  */
3170  cost_qual_eval(&merge_qual_cost, mergeclauses, root);
3171  cost_qual_eval(&qp_qual_cost, path->jpath.joinrestrictinfo, root);
3172  qp_qual_cost.startup -= merge_qual_cost.startup;
3173  qp_qual_cost.per_tuple -= merge_qual_cost.per_tuple;
3174 
3175  /*
3176  * With a SEMI or ANTI join, or if the innerrel is known unique, the
3177  * executor will stop scanning for matches after the first match. When
3178  * all the joinclauses are merge clauses, this means we don't ever need to
3179  * back up the merge, and so we can skip mark/restore overhead.
3180  */
3181  if ((path->jpath.jointype == JOIN_SEMI ||
3182  path->jpath.jointype == JOIN_ANTI ||
3183  extra->inner_unique) &&
3186  path->skip_mark_restore = true;
3187  else
3188  path->skip_mark_restore = false;
3189 
3190  /*
3191  * Get approx # tuples passing the mergequals. We use approx_tuple_count
3192  * here because we need an estimate done with JOIN_INNER semantics.
3193  */
3194  mergejointuples = approx_tuple_count(root, &path->jpath, mergeclauses);
3195 
3196  /*
3197  * When there are equal merge keys in the outer relation, the mergejoin
3198  * must rescan any matching tuples in the inner relation. This means
3199  * re-fetching inner tuples; we have to estimate how often that happens.
3200  *
3201  * For regular inner and outer joins, the number of re-fetches can be
3202  * estimated approximately as size of merge join output minus size of
3203  * inner relation. Assume that the distinct key values are 1, 2, ..., and
3204  * denote the number of values of each key in the outer relation as m1,
3205  * m2, ...; in the inner relation, n1, n2, ... Then we have
3206  *
3207  * size of join = m1 * n1 + m2 * n2 + ...
3208  *
3209  * number of rescanned tuples = (m1 - 1) * n1 + (m2 - 1) * n2 + ... = m1 *
3210  * n1 + m2 * n2 + ... - (n1 + n2 + ...) = size of join - size of inner
3211  * relation
3212  *
3213  * This equation works correctly for outer tuples having no inner match
3214  * (nk = 0), but not for inner tuples having no outer match (mk = 0); we
3215  * are effectively subtracting those from the number of rescanned tuples,
3216  * when we should not. Can we do better without expensive selectivity
3217  * computations?
3218  *
3219  * The whole issue is moot if we are working from a unique-ified outer
3220  * input, or if we know we don't need to mark/restore at all.
3221  */
3222  if (IsA(outer_path, UniquePath) ||path->skip_mark_restore)
3223  rescannedtuples = 0;
3224  else
3225  {
3226  rescannedtuples = mergejointuples - inner_path_rows;
3227  /* Must clamp because of possible underestimate */
3228  if (rescannedtuples < 0)
3229  rescannedtuples = 0;
3230  }
3231 
3232  /*
3233  * We'll inflate various costs this much to account for rescanning. Note
3234  * that this is to be multiplied by something involving inner_rows, or
3235  * another number related to the portion of the inner rel we'll scan.
3236  */
3237  rescanratio = 1.0 + (rescannedtuples / inner_rows);
3238 
3239  /*
3240  * Decide whether we want to materialize the inner input to shield it from
3241  * mark/restore and performing re-fetches. Our cost model for regular
3242  * re-fetches is that a re-fetch costs the same as an original fetch,
3243  * which is probably an overestimate; but on the other hand we ignore the
3244  * bookkeeping costs of mark/restore. Not clear if it's worth developing
3245  * a more refined model. So we just need to inflate the inner run cost by
3246  * rescanratio.
3247  */
3248  bare_inner_cost = inner_run_cost * rescanratio;
3249 
3250  /*
3251  * When we interpose a Material node the re-fetch cost is assumed to be
3252  * just cpu_operator_cost per tuple, independently of the underlying
3253  * plan's cost; and we charge an extra cpu_operator_cost per original
3254  * fetch as well. Note that we're assuming the materialize node will
3255  * never spill to disk, since it only has to remember tuples back to the
3256  * last mark. (If there are a huge number of duplicates, our other cost
3257  * factors will make the path so expensive that it probably won't get
3258  * chosen anyway.) So we don't use cost_rescan here.
3259  *
3260  * Note: keep this estimate in sync with create_mergejoin_plan's labeling
3261  * of the generated Material node.
3262  */
3263  mat_inner_cost = inner_run_cost +
3264  cpu_operator_cost * inner_rows * rescanratio;
3265 
3266  /*
3267  * If we don't need mark/restore at all, we don't need materialization.
3268  */
3269  if (path->skip_mark_restore)
3270  path->materialize_inner = false;
3271 
3272  /*
3273  * Prefer materializing if it looks cheaper, unless the user has asked to
3274  * suppress materialization.
3275  */
3276  else if (enable_material && mat_inner_cost < bare_inner_cost)
3277  path->materialize_inner = true;
3278 
3279  /*
3280  * Even if materializing doesn't look cheaper, we *must* do it if the
3281  * inner path is to be used directly (without sorting) and it doesn't
3282  * support mark/restore.
3283  *
3284  * Since the inner side must be ordered, and only Sorts and IndexScans can
3285  * create order to begin with, and they both support mark/restore, you
3286  * might think there's no problem --- but you'd be wrong. Nestloop and
3287  * merge joins can *preserve* the order of their inputs, so they can be
3288  * selected as the input of a mergejoin, and they don't support
3289  * mark/restore at present.
3290  *
3291  * We don't test the value of enable_material here, because
3292  * materialization is required for correctness in this case, and turning
3293  * it off does not entitle us to deliver an invalid plan.
3294  */
3295  else if (innersortkeys == NIL &&
3296  !ExecSupportsMarkRestore(inner_path))
3297  path->materialize_inner = true;
3298 
3299  /*
3300  * Also, force materializing if the inner path is to be sorted and the
3301  * sort is expected to spill to disk. This is because the final merge
3302  * pass can be done on-the-fly if it doesn't have to support mark/restore.
3303  * We don't try to adjust the cost estimates for this consideration,
3304  * though.
3305  *
3306  * Since materialization is a performance optimization in this case,
3307  * rather than necessary for correctness, we skip it if enable_material is
3308  * off.
3309  */
3310  else if (enable_material && innersortkeys != NIL &&
3311  relation_byte_size(inner_path_rows,
3312  inner_path->pathtarget->width) >
3313  (work_mem * 1024L))