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_incremental_sort = true
 
bool enable_hashagg = true
 
bool hashagg_avoid_disk_plan = true
 
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 1959 of file costsize.c.

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

Referenced by cost_append().

1960 {
1961  Cost *costarr;
1962  int arrlen;
1963  ListCell *l;
1964  ListCell *cell;
1965  int i;
1966  int path_index;
1967  int min_index;
1968  int max_index;
1969 
1970  if (numpaths == 0)
1971  return 0;
1972 
1973  /*
1974  * Array length is number of workers or number of relevant paths,
1975  * whichever is less.
1976  */
1977  arrlen = Min(parallel_workers, numpaths);
1978  costarr = (Cost *) palloc(sizeof(Cost) * arrlen);
1979 
1980  /* The first few paths will each be claimed by a different worker. */
1981  path_index = 0;
1982  foreach(cell, subpaths)
1983  {
1984  Path *subpath = (Path *) lfirst(cell);
1985 
1986  if (path_index == arrlen)
1987  break;
1988  costarr[path_index++] = subpath->total_cost;
1989  }
1990 
1991  /*
1992  * Since subpaths are sorted by decreasing cost, the last one will have
1993  * the minimum cost.
1994  */
1995  min_index = arrlen - 1;
1996 
1997  /*
1998  * For each of the remaining subpaths, add its cost to the array element
1999  * with minimum cost.
2000  */
2001  for_each_cell(l, subpaths, cell)
2002  {
2003  Path *subpath = (Path *) lfirst(l);
2004  int i;
2005 
2006  /* Consider only the non-partial paths */
2007  if (path_index++ == numpaths)
2008  break;
2009 
2010  costarr[min_index] += subpath->total_cost;
2011 
2012  /* Update the new min cost array index */
2013  for (min_index = i = 0; i < arrlen; i++)
2014  {
2015  if (costarr[i] < costarr[min_index])
2016  min_index = i;
2017  }
2018  }
2019 
2020  /* Return the highest cost from the array */
2021  for (max_index = i = 0; i < arrlen; i++)
2022  {
2023  if (costarr[i] > costarr[max_index])
2024  max_index = i;
2025  }
2026 
2027  return costarr[max_index];
2028 }
#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 4571 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().

4572 {
4573  double tuples;
4574  double outer_tuples = path->outerjoinpath->rows;
4575  double inner_tuples = path->innerjoinpath->rows;
4576  SpecialJoinInfo sjinfo;
4577  Selectivity selec = 1.0;
4578  ListCell *l;
4579 
4580  /*
4581  * Make up a SpecialJoinInfo for JOIN_INNER semantics.
4582  */
4583  sjinfo.type = T_SpecialJoinInfo;
4584  sjinfo.min_lefthand = path->outerjoinpath->parent->relids;
4585  sjinfo.min_righthand = path->innerjoinpath->parent->relids;
4586  sjinfo.syn_lefthand = path->outerjoinpath->parent->relids;
4587  sjinfo.syn_righthand = path->innerjoinpath->parent->relids;
4588  sjinfo.jointype = JOIN_INNER;
4589  /* we don't bother trying to make the remaining fields valid */
4590  sjinfo.lhs_strict = false;
4591  sjinfo.delay_upper_joins = false;
4592  sjinfo.semi_can_btree = false;
4593  sjinfo.semi_can_hash = false;
4594  sjinfo.semi_operators = NIL;
4595  sjinfo.semi_rhs_exprs = NIL;
4596 
4597  /* Get the approximate selectivity */
4598  foreach(l, quals)
4599  {
4600  Node *qual = (Node *) lfirst(l);
4601 
4602  /* Note that clause_selectivity will be able to cache its result */
4603  selec *= clause_selectivity(root, qual, 0, JOIN_INNER, &sjinfo);
4604  }
4605 
4606  /* Apply it to the input relation sizes */
4607  tuples = selec * outer_tuples * inner_tuples;
4608 
4609  return clamp_row_est(tuples);
4610 }
#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:190
Relids min_lefthand
Definition: pathnodes.h:2175

◆ cached_scansel()

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

Definition at line 3400 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().

3401 {
3402  MergeScanSelCache *cache;
3403  ListCell *lc;
3404  Selectivity leftstartsel,
3405  leftendsel,
3406  rightstartsel,
3407  rightendsel;
3408  MemoryContext oldcontext;
3409 
3410  /* Do we have this result already? */
3411  foreach(lc, rinfo->scansel_cache)
3412  {
3413  cache = (MergeScanSelCache *) lfirst(lc);
3414  if (cache->opfamily == pathkey->pk_opfamily &&
3415  cache->collation == pathkey->pk_eclass->ec_collation &&
3416  cache->strategy == pathkey->pk_strategy &&
3417  cache->nulls_first == pathkey->pk_nulls_first)
3418  return cache;
3419  }
3420 
3421  /* Nope, do the computation */
3422  mergejoinscansel(root,
3423  (Node *) rinfo->clause,
3424  pathkey->pk_opfamily,
3425  pathkey->pk_strategy,
3426  pathkey->pk_nulls_first,
3427  &leftstartsel,
3428  &leftendsel,
3429  &rightstartsel,
3430  &rightendsel);
3431 
3432  /* Cache the result in suitably long-lived workspace */
3433  oldcontext = MemoryContextSwitchTo(root->planner_cxt);
3434 
3435  cache = (MergeScanSelCache *) palloc(sizeof(MergeScanSelCache));
3436  cache->opfamily = pathkey->pk_opfamily;
3437  cache->collation = pathkey->pk_eclass->ec_collation;
3438  cache->strategy = pathkey->pk_strategy;
3439  cache->nulls_first = pathkey->pk_nulls_first;
3440  cache->leftstartsel = leftstartsel;
3441  cache->leftendsel = leftendsel;
3442  cache->rightstartsel = rightstartsel;
3443  cache->rightendsel = rightendsel;
3444 
3445  rinfo->scansel_cache = lappend(rinfo->scansel_cache, cache);
3446 
3447  MemoryContextSwitchTo(oldcontext);
3448 
3449  return cache;
3450 }
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:2901
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 4779 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().

4787 {
4788  /* This apparently-useless variable dodges a compiler bug in VS2013: */
4789  List *restrictlist = restrictlist_in;
4790  JoinType jointype = sjinfo->jointype;
4791  Selectivity fkselec;
4792  Selectivity jselec;
4793  Selectivity pselec;
4794  double nrows;
4795 
4796  /*
4797  * Compute joinclause selectivity. Note that we are only considering
4798  * clauses that become restriction clauses at this join level; we are not
4799  * double-counting them because they were not considered in estimating the
4800  * sizes of the component rels.
4801  *
4802  * First, see whether any of the joinclauses can be matched to known FK
4803  * constraints. If so, drop those clauses from the restrictlist, and
4804  * instead estimate their selectivity using FK semantics. (We do this
4805  * without regard to whether said clauses are local or "pushed down".
4806  * Probably, an FK-matching clause could never be seen as pushed down at
4807  * an outer join, since it would be strict and hence would be grounds for
4808  * join strength reduction.) fkselec gets the net selectivity for
4809  * FK-matching clauses, or 1.0 if there are none.
4810  */
4811  fkselec = get_foreign_key_join_selectivity(root,
4812  outer_rel->relids,
4813  inner_rel->relids,
4814  sjinfo,
4815  &restrictlist);
4816 
4817  /*
4818  * For an outer join, we have to distinguish the selectivity of the join's
4819  * own clauses (JOIN/ON conditions) from any clauses that were "pushed
4820  * down". For inner joins we just count them all as joinclauses.
4821  */
4822  if (IS_OUTER_JOIN(jointype))
4823  {
4824  List *joinquals = NIL;
4825  List *pushedquals = NIL;
4826  ListCell *l;
4827 
4828  /* Grovel through the clauses to separate into two lists */
4829  foreach(l, restrictlist)
4830  {
4831  RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
4832 
4833  if (RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
4834  pushedquals = lappend(pushedquals, rinfo);
4835  else
4836  joinquals = lappend(joinquals, rinfo);
4837  }
4838 
4839  /* Get the separate selectivities */
4840  jselec = clauselist_selectivity(root,
4841  joinquals,
4842  0,
4843  jointype,
4844  sjinfo);
4845  pselec = clauselist_selectivity(root,
4846  pushedquals,
4847  0,
4848  jointype,
4849  sjinfo);
4850 
4851  /* Avoid leaking a lot of ListCells */
4852  list_free(joinquals);
4853  list_free(pushedquals);
4854  }
4855  else
4856  {
4857  jselec = clauselist_selectivity(root,
4858  restrictlist,
4859  0,
4860  jointype,
4861  sjinfo);
4862  pselec = 0.0; /* not used, keep compiler quiet */
4863  }
4864 
4865  /*
4866  * Basically, we multiply size of Cartesian product by selectivity.
4867  *
4868  * If we are doing an outer join, take that into account: the joinqual
4869  * selectivity has to be clamped using the knowledge that the output must
4870  * be at least as large as the non-nullable input. However, any
4871  * pushed-down quals are applied after the outer join, so their
4872  * selectivity applies fully.
4873  *
4874  * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the fraction
4875  * of LHS rows that have matches, and we apply that straightforwardly.
4876  */
4877  switch (jointype)
4878  {
4879  case JOIN_INNER:
4880  nrows = outer_rows * inner_rows * fkselec * jselec;
4881  /* pselec not used */
4882  break;
4883  case JOIN_LEFT:
4884  nrows = outer_rows * inner_rows * fkselec * jselec;
4885  if (nrows < outer_rows)
4886  nrows = outer_rows;
4887  nrows *= pselec;
4888  break;
4889  case JOIN_FULL:
4890  nrows = outer_rows * inner_rows * fkselec * jselec;
4891  if (nrows < outer_rows)
4892  nrows = outer_rows;
4893  if (nrows < inner_rows)
4894  nrows = inner_rows;
4895  nrows *= pselec;
4896  break;
4897  case JOIN_SEMI:
4898  nrows = outer_rows * fkselec * jselec;
4899  /* pselec not used */
4900  break;
4901  case JOIN_ANTI:
4902  nrows = outer_rows * (1.0 - fkselec * jselec);
4903  nrows *= pselec;
4904  break;
4905  default:
4906  /* other values not expected here */
4907  elog(ERROR, "unrecognized join type: %d", (int) jointype);
4908  nrows = 0; /* keep compiler quiet */
4909  break;
4910  }
4911 
4912  return clamp_row_est(nrows);
4913 }
#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:4931
#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:190
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 5731 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().

5733 {
5734  Cost indexTotalCost;
5735  Selectivity indexSelectivity;
5736  double T;
5737  double pages_fetched;
5738  double tuples_fetched;
5739  double heap_pages;
5740  long maxentries;
5741 
5742  /*
5743  * Fetch total cost of obtaining the bitmap, as well as its total
5744  * selectivity.
5745  */
5746  cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
5747 
5748  /*
5749  * Estimate number of main-table pages fetched.
5750  */
5751  tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
5752 
5753  T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
5754 
5755  /*
5756  * For a single scan, the number of heap pages that need to be fetched is
5757  * the same as the Mackert and Lohman formula for the case T <= b (ie, no
5758  * re-reads needed).
5759  */
5760  pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);
5761 
5762  /*
5763  * Calculate the number of pages fetched from the heap. Then based on
5764  * current work_mem estimate get the estimated maxentries in the bitmap.
5765  * (Note that we always do this calculation based on the number of pages
5766  * that would be fetched in a single iteration, even if loop_count > 1.
5767  * That's correct, because only that number of entries will be stored in
5768  * the bitmap at one time.)
5769  */
5770  heap_pages = Min(pages_fetched, baserel->pages);
5771  maxentries = tbm_calculate_entries(work_mem * 1024L);
5772 
5773  if (loop_count > 1)
5774  {
5775  /*
5776  * For repeated bitmap scans, scale up the number of tuples fetched in
5777  * the Mackert and Lohman formula by the number of scans, so that we
5778  * estimate the number of pages fetched by all the scans. Then
5779  * pro-rate for one scan.
5780  */
5781  pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
5782  baserel->pages,
5783  get_indexpath_pages(bitmapqual),
5784  root);
5785  pages_fetched /= loop_count;
5786  }
5787 
5788  if (pages_fetched >= T)
5789  pages_fetched = T;
5790  else
5791  pages_fetched = ceil(pages_fetched);
5792 
5793  if (maxentries < heap_pages)
5794  {
5795  double exact_pages;
5796  double lossy_pages;
5797 
5798  /*
5799  * Crude approximation of the number of lossy pages. Because of the
5800  * way tbm_lossify() is coded, the number of lossy pages increases
5801  * very sharply as soon as we run short of memory; this formula has
5802  * that property and seems to perform adequately in testing, but it's
5803  * possible we could do better somehow.
5804  */
5805  lossy_pages = Max(0, heap_pages - maxentries / 2);
5806  exact_pages = heap_pages - lossy_pages;
5807 
5808  /*
5809  * If there are lossy pages then recompute the number of tuples
5810  * processed by the bitmap heap node. We assume here that the chance
5811  * of a given tuple coming from an exact page is the same as the
5812  * chance that a given page is exact. This might not be true, but
5813  * it's not clear how we can do any better.
5814  */
5815  if (lossy_pages > 0)
5816  tuples_fetched =
5817  clamp_row_est(indexSelectivity *
5818  (exact_pages / heap_pages) * baserel->tuples +
5819  (lossy_pages / heap_pages) * baserel->tuples);
5820  }
5821 
5822  if (cost)
5823  *cost = indexTotalCost;
5824  if (tuple)
5825  *tuple = tuples_fetched;
5826 
5827  return pages_fetched;
5828 }
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:893
long tbm_calculate_entries(double maxbytes)
Definition: tidbitmap.c:1545
double clamp_row_est(double nrows)
Definition: costsize.c:190
double index_pages_fetched(double tuples_fetched, BlockNumber pages, double index_pages, PlannerInfo *root)
Definition: costsize.c:828
double Cost
Definition: nodes.h:663
void cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec)
Definition: costsize.c:1044

◆ 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 4370 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().

4378 {
4379  Selectivity jselec;
4380  Selectivity nselec;
4381  Selectivity avgmatch;
4382  SpecialJoinInfo norm_sjinfo;
4383  List *joinquals;
4384  ListCell *l;
4385 
4386  /*
4387  * In an ANTI join, we must ignore clauses that are "pushed down", since
4388  * those won't affect the match logic. In a SEMI join, we do not
4389  * distinguish joinquals from "pushed down" quals, so just use the whole
4390  * restrictinfo list. For other outer join types, we should consider only
4391  * non-pushed-down quals, so that this devolves to an IS_OUTER_JOIN check.
4392  */
4393  if (IS_OUTER_JOIN(jointype))
4394  {
4395  joinquals = NIL;
4396  foreach(l, restrictlist)
4397  {
4398  RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
4399 
4400  if (!RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
4401  joinquals = lappend(joinquals, rinfo);
4402  }
4403  }
4404  else
4405  joinquals = restrictlist;
4406 
4407  /*
4408  * Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses.
4409  */
4410  jselec = clauselist_selectivity(root,
4411  joinquals,
4412  0,
4413  (jointype == JOIN_ANTI) ? JOIN_ANTI : JOIN_SEMI,
4414  sjinfo);
4415 
4416  /*
4417  * Also get the normal inner-join selectivity of the join clauses.
4418  */
4419  norm_sjinfo.type = T_SpecialJoinInfo;
4420  norm_sjinfo.min_lefthand = outerrel->relids;
4421  norm_sjinfo.min_righthand = innerrel->relids;
4422  norm_sjinfo.syn_lefthand = outerrel->relids;
4423  norm_sjinfo.syn_righthand = innerrel->relids;
4424  norm_sjinfo.jointype = JOIN_INNER;
4425  /* we don't bother trying to make the remaining fields valid */
4426  norm_sjinfo.lhs_strict = false;
4427  norm_sjinfo.delay_upper_joins = false;
4428  norm_sjinfo.semi_can_btree = false;
4429  norm_sjinfo.semi_can_hash = false;
4430  norm_sjinfo.semi_operators = NIL;
4431  norm_sjinfo.semi_rhs_exprs = NIL;
4432 
4433  nselec = clauselist_selectivity(root,
4434  joinquals,
4435  0,
4436  JOIN_INNER,
4437  &norm_sjinfo);
4438 
4439  /* Avoid leaking a lot of ListCells */
4440  if (IS_OUTER_JOIN(jointype))
4441  list_free(joinquals);
4442 
4443  /*
4444  * jselec can be interpreted as the fraction of outer-rel rows that have
4445  * any matches (this is true for both SEMI and ANTI cases). And nselec is
4446  * the fraction of the Cartesian product that matches. So, the average
4447  * number of matches for each outer-rel row that has at least one match is
4448  * nselec * inner_rows / jselec.
4449  *
4450  * Note: it is correct to use the inner rel's "rows" count here, even
4451  * though we might later be considering a parameterized inner path with
4452  * fewer rows. This is because we have included all the join clauses in
4453  * the selectivity estimate.
4454  */
4455  if (jselec > 0) /* protect against zero divide */
4456  {
4457  avgmatch = nselec * innerrel->rows / jselec;
4458  /* Clamp to sane range */
4459  avgmatch = Max(1.0, avgmatch);
4460  }
4461  else
4462  avgmatch = 1.0;
4463 
4464  semifactors->outer_match_frac = jselec;
4465  semifactors->match_count = avgmatch;
4466 }
#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 2311 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().

2317 {
2318  double output_tuples;
2319  Cost startup_cost;
2320  Cost total_cost;
2321  AggClauseCosts dummy_aggcosts;
2322 
2323  /* Use all-zero per-aggregate costs if NULL is passed */
2324  if (aggcosts == NULL)
2325  {
2326  Assert(aggstrategy == AGG_HASHED);
2327  MemSet(&dummy_aggcosts, 0, sizeof(AggClauseCosts));
2328  aggcosts = &dummy_aggcosts;
2329  }
2330 
2331  /*
2332  * The transCost.per_tuple component of aggcosts should be charged once
2333  * per input tuple, corresponding to the costs of evaluating the aggregate
2334  * transfns and their input expressions. The finalCost.per_tuple component
2335  * is charged once per output tuple, corresponding to the costs of
2336  * evaluating the finalfns. Startup costs are of course charged but once.
2337  *
2338  * If we are grouping, we charge an additional cpu_operator_cost per
2339  * grouping column per input tuple for grouping comparisons.
2340  *
2341  * We will produce a single output tuple if not grouping, and a tuple per
2342  * group otherwise. We charge cpu_tuple_cost for each output tuple.
2343  *
2344  * Note: in this cost model, AGG_SORTED and AGG_HASHED have exactly the
2345  * same total CPU cost, but AGG_SORTED has lower startup cost. If the
2346  * input path is already sorted appropriately, AGG_SORTED should be
2347  * preferred (since it has no risk of memory overflow). This will happen
2348  * as long as the computed total costs are indeed exactly equal --- but if
2349  * there's roundoff error we might do the wrong thing. So be sure that
2350  * the computations below form the same intermediate values in the same
2351  * order.
2352  */
2353  if (aggstrategy == AGG_PLAIN)
2354  {
2355  startup_cost = input_total_cost;
2356  startup_cost += aggcosts->transCost.startup;
2357  startup_cost += aggcosts->transCost.per_tuple * input_tuples;
2358  startup_cost += aggcosts->finalCost.startup;
2359  startup_cost += aggcosts->finalCost.per_tuple;
2360  /* we aren't grouping */
2361  total_cost = startup_cost + cpu_tuple_cost;
2362  output_tuples = 1;
2363  }
2364  else if (aggstrategy == AGG_SORTED || aggstrategy == AGG_MIXED)
2365  {
2366  /* Here we are able to deliver output on-the-fly */
2367  startup_cost = input_startup_cost;
2368  total_cost = input_total_cost;
2369  if (aggstrategy == AGG_MIXED && !enable_hashagg)
2370  {
2371  startup_cost += disable_cost;
2372  total_cost += disable_cost;
2373  }
2374  /* calcs phrased this way to match HASHED case, see note above */
2375  total_cost += aggcosts->transCost.startup;
2376  total_cost += aggcosts->transCost.per_tuple * input_tuples;
2377  total_cost += (cpu_operator_cost * numGroupCols) * input_tuples;
2378  total_cost += aggcosts->finalCost.startup;
2379  total_cost += aggcosts->finalCost.per_tuple * numGroups;
2380  total_cost += cpu_tuple_cost * numGroups;
2381  output_tuples = numGroups;
2382  }
2383  else
2384  {
2385  /* must be AGG_HASHED */
2386  startup_cost = input_total_cost;
2387  if (!enable_hashagg)
2388  startup_cost += disable_cost;
2389  startup_cost += aggcosts->transCost.startup;
2390  startup_cost += aggcosts->transCost.per_tuple * input_tuples;
2391  /* cost of computing hash value */
2392  startup_cost += (cpu_operator_cost * numGroupCols) * input_tuples;
2393  startup_cost += aggcosts->finalCost.startup;
2394 
2395  total_cost = startup_cost;
2396  total_cost += aggcosts->finalCost.per_tuple * numGroups;
2397  /* cost of retrieving from hash table */
2398  total_cost += cpu_tuple_cost * numGroups;
2399  output_tuples = numGroups;
2400  }
2401 
2402  /*
2403  * Add the disk costs of hash aggregation that spills to disk.
2404  *
2405  * Groups that go into the hash table stay in memory until finalized, so
2406  * spilling and reprocessing tuples doesn't incur additional invocations
2407  * of transCost or finalCost. Furthermore, the computed hash value is
2408  * stored with the spilled tuples, so we don't incur extra invocations of
2409  * the hash function.
2410  *
2411  * Hash Agg begins returning tuples after the first batch is complete.
2412  * Accrue writes (spilled tuples) to startup_cost and to total_cost;
2413  * accrue reads only to total_cost.
2414  */
2415  if (aggstrategy == AGG_HASHED || aggstrategy == AGG_MIXED)
2416  {
2417  double pages;
2418  double pages_written = 0.0;
2419  double pages_read = 0.0;
2420  double hashentrysize;
2421  double nbatches;
2422  Size mem_limit;
2423  uint64 ngroups_limit;
2424  int num_partitions;
2425  int depth;
2426 
2427  /*
2428  * Estimate number of batches based on the computed limits. If less
2429  * than or equal to one, all groups are expected to fit in memory;
2430  * otherwise we expect to spill.
2431  */
2432  hashentrysize = hash_agg_entry_size(aggcosts->numAggs, input_width,
2433  aggcosts->transitionSpace);
2434  hash_agg_set_limits(hashentrysize, numGroups, 0, &mem_limit,
2435  &ngroups_limit, &num_partitions);
2436 
2437  nbatches = Max((numGroups * hashentrysize) / mem_limit,
2438  numGroups / ngroups_limit);
2439 
2440  nbatches = Max(ceil(nbatches), 1.0);
2441  num_partitions = Max(num_partitions, 2);
2442 
2443  /*
2444  * The number of partitions can change at different levels of
2445  * recursion; but for the purposes of this calculation assume it stays
2446  * constant.
2447  */
2448  depth = ceil(log(nbatches) / log(num_partitions));
2449 
2450  /*
2451  * Estimate number of pages read and written. For each level of
2452  * recursion, a tuple must be written and then later read.
2453  */
2454  pages = relation_byte_size(input_tuples, input_width) / BLCKSZ;
2455  pages_written = pages_read = pages * depth;
2456 
2457  startup_cost += pages_written * random_page_cost;
2458  total_cost += pages_written * random_page_cost;
2459  total_cost += pages_read * seq_page_cost;
2460  }
2461 
2462  /*
2463  * If there are quals (HAVING quals), account for their cost and
2464  * selectivity.
2465  */
2466  if (quals)
2467  {
2468  QualCost qual_cost;
2469 
2470  cost_qual_eval(&qual_cost, quals, root);
2471  startup_cost += qual_cost.startup;
2472  total_cost += qual_cost.startup + output_tuples * qual_cost.per_tuple;
2473 
2474  output_tuples = clamp_row_est(output_tuples *
2476  quals,
2477  0,
2478  JOIN_INNER,
2479  NULL));
2480  }
2481 
2482  path->rows = output_tuples;
2483  path->startup_cost = startup_cost;
2484  path->total_cost = total_cost;
2485 }
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:1647
Cost per_tuple
Definition: pathnodes.h:46
void cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
Definition: costsize.c:4042
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:5677
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:190
double seq_page_cost
Definition: costsize.c:111
double Cost
Definition: nodes.h:663

◆ cost_append()

void cost_append ( AppendPath apath)

Definition at line 2035 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().

2036 {
2037  ListCell *l;
2038 
2039  apath->path.startup_cost = 0;
2040  apath->path.total_cost = 0;
2041  apath->path.rows = 0;
2042 
2043  if (apath->subpaths == NIL)
2044  return;
2045 
2046  if (!apath->path.parallel_aware)
2047  {
2048  List *pathkeys = apath->path.pathkeys;
2049 
2050  if (pathkeys == NIL)
2051  {
2052  Path *subpath = (Path *) linitial(apath->subpaths);
2053 
2054  /*
2055  * For an unordered, non-parallel-aware Append we take the startup
2056  * cost as the startup cost of the first subpath.
2057  */
2058  apath->path.startup_cost = subpath->startup_cost;
2059 
2060  /* Compute rows and costs as sums of subplan rows and costs. */
2061  foreach(l, apath->subpaths)
2062  {
2063  Path *subpath = (Path *) lfirst(l);
2064 
2065  apath->path.rows += subpath->rows;
2066  apath->path.total_cost += subpath->total_cost;
2067  }
2068  }
2069  else
2070  {
2071  /*
2072  * For an ordered, non-parallel-aware Append we take the startup
2073  * cost as the sum of the subpath startup costs. This ensures
2074  * that we don't underestimate the startup cost when a query's
2075  * LIMIT is such that several of the children have to be run to
2076  * satisfy it. This might be overkill --- another plausible hack
2077  * would be to take the Append's startup cost as the maximum of
2078  * the child startup costs. But we don't want to risk believing
2079  * that an ORDER BY LIMIT query can be satisfied at small cost
2080  * when the first child has small startup cost but later ones
2081  * don't. (If we had the ability to deal with nonlinear cost
2082  * interpolation for partial retrievals, we would not need to be
2083  * so conservative about this.)
2084  *
2085  * This case is also different from the above in that we have to
2086  * account for possibly injecting sorts into subpaths that aren't
2087  * natively ordered.
2088  */
2089  foreach(l, apath->subpaths)
2090  {
2091  Path *subpath = (Path *) lfirst(l);
2092  Path sort_path; /* dummy for result of cost_sort */
2093 
2094  if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
2095  {
2096  /*
2097  * We'll need to insert a Sort node, so include costs for
2098  * that. We can use the parent's LIMIT if any, since we
2099  * certainly won't pull more than that many tuples from
2100  * any child.
2101  */
2102  cost_sort(&sort_path,
2103  NULL, /* doesn't currently need root */
2104  pathkeys,
2105  subpath->total_cost,
2106  subpath->rows,
2107  subpath->pathtarget->width,
2108  0.0,
2109  work_mem,
2110  apath->limit_tuples);
2111  subpath = &sort_path;
2112  }
2113 
2114  apath->path.rows += subpath->rows;
2115  apath->path.startup_cost += subpath->startup_cost;
2116  apath->path.total_cost += subpath->total_cost;
2117  }
2118  }
2119  }
2120  else /* parallel-aware */
2121  {
2122  int i = 0;
2123  double parallel_divisor = get_parallel_divisor(&apath->path);
2124 
2125  /* Parallel-aware Append never produces ordered output. */
2126  Assert(apath->path.pathkeys == NIL);
2127 
2128  /* Calculate startup cost. */
2129  foreach(l, apath->subpaths)
2130  {
2131  Path *subpath = (Path *) lfirst(l);
2132 
2133  /*
2134  * Append will start returning tuples when the child node having
2135  * lowest startup cost is done setting up. We consider only the
2136  * first few subplans that immediately get a worker assigned.
2137  */
2138  if (i == 0)
2139  apath->path.startup_cost = subpath->startup_cost;
2140  else if (i < apath->path.parallel_workers)
2141  apath->path.startup_cost = Min(apath->path.startup_cost,
2142  subpath->startup_cost);
2143 
2144  /*
2145  * Apply parallel divisor to subpaths. Scale the number of rows
2146  * for each partial subpath based on the ratio of the parallel
2147  * divisor originally used for the subpath to the one we adopted.
2148  * Also add the cost of partial paths to the total cost, but
2149  * ignore non-partial paths for now.
2150  */
2151  if (i < apath->first_partial_path)
2152  apath->path.rows += subpath->rows / parallel_divisor;
2153  else
2154  {
2155  double subpath_parallel_divisor;
2156 
2157  subpath_parallel_divisor = get_parallel_divisor(subpath);
2158  apath->path.rows += subpath->rows * (subpath_parallel_divisor /
2159  parallel_divisor);
2160  apath->path.total_cost += subpath->total_cost;
2161  }
2162 
2163  apath->path.rows = clamp_row_est(apath->path.rows);
2164 
2165  i++;
2166  }
2167 
2168  /* Add cost for non-partial subpaths. */
2169  apath->path.total_cost +=
2171  apath->first_partial_path,
2172  apath->path.parallel_workers);
2173  }
2174 
2175  /*
2176  * Although Append does not do any selection or projection, it's not free;
2177  * add a small per-tuple overhead.
2178  */
2179  apath->path.total_cost +=
2181 }
#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:1959
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:5698
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:1928
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:190
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 1087 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().

1088 {
1089  Cost totalCost;
1090  Selectivity selec;
1091  ListCell *l;
1092 
1093  /*
1094  * We estimate AND selectivity on the assumption that the inputs are
1095  * independent. This is probably often wrong, but we don't have the info
1096  * to do better.
1097  *
1098  * The runtime cost of the BitmapAnd itself is estimated at 100x
1099  * cpu_operator_cost for each tbm_intersect needed. Probably too small,
1100  * definitely too simplistic?
1101  */
1102  totalCost = 0.0;
1103  selec = 1.0;
1104  foreach(l, path->bitmapquals)
1105  {
1106  Path *subpath = (Path *) lfirst(l);
1107  Cost subCost;
1108  Selectivity subselec;
1109 
1110  cost_bitmap_tree_node(subpath, &subCost, &subselec);
1111 
1112  selec *= subselec;
1113 
1114  totalCost += subCost;
1115  if (l != list_head(path->bitmapquals))
1116  totalCost += 100.0 * cpu_operator_cost;
1117  }
1118  path->bitmapselectivity = selec;
1119  path->path.rows = 0; /* per above, not used */
1120  path->path.startup_cost = totalCost;
1121  path->path.total_cost = totalCost;
1122 }
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:1044

◆ 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 943 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().

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

◆ cost_bitmap_or_node()

void cost_bitmap_or_node ( BitmapOrPath path,
PlannerInfo root 
)

Definition at line 1131 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().

1132 {
1133  Cost totalCost;
1134  Selectivity selec;
1135  ListCell *l;
1136 
1137  /*
1138  * We estimate OR selectivity on the assumption that the inputs are
1139  * non-overlapping, since that's often the case in "x IN (list)" type
1140  * situations. Of course, we clamp to 1.0 at the end.
1141  *
1142  * The runtime cost of the BitmapOr itself is estimated at 100x
1143  * cpu_operator_cost for each tbm_union needed. Probably too small,
1144  * definitely too simplistic? We are aware that the tbm_unions are
1145  * optimized out when the inputs are BitmapIndexScans.
1146  */
1147  totalCost = 0.0;
1148  selec = 0.0;
1149  foreach(l, path->bitmapquals)
1150  {
1151  Path *subpath = (Path *) lfirst(l);
1152  Cost subCost;
1153  Selectivity subselec;
1154 
1155  cost_bitmap_tree_node(subpath, &subCost, &subselec);
1156 
1157  selec += subselec;
1158 
1159  totalCost += subCost;
1160  if (l != list_head(path->bitmapquals) &&
1161  !IsA(subpath, IndexPath))
1162  totalCost += 100.0 * cpu_operator_cost;
1163  }
1164  path->bitmapselectivity = Min(selec, 1.0);
1165  path->path.rows = 0; /* per above, not used */
1166  path->path.startup_cost = totalCost;
1167  path->path.total_cost = totalCost;
1168 }
#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:1044

◆ cost_bitmap_tree_node()

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

Definition at line 1044 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().

1045 {
1046  if (IsA(path, IndexPath))
1047  {
1048  *cost = ((IndexPath *) path)->indextotalcost;
1049  *selec = ((IndexPath *) path)->indexselectivity;
1050 
1051  /*
1052  * Charge a small amount per retrieved tuple to reflect the costs of
1053  * manipulating the bitmap. This is mostly to make sure that a bitmap
1054  * scan doesn't look to be the same cost as an indexscan to retrieve a
1055  * single tuple.
1056  */
1057  *cost += 0.1 * cpu_operator_cost * path->rows;
1058  }
1059  else if (IsA(path, BitmapAndPath))
1060  {
1061  *cost = path->total_cost;
1062  *selec = ((BitmapAndPath *) path)->bitmapselectivity;
1063  }
1064  else if (IsA(path, BitmapOrPath))
1065  {
1066  *cost = path->total_cost;
1067  *selec = ((BitmapOrPath *) path)->bitmapselectivity;
1068  }
1069  else
1070  {
1071  elog(ERROR, "unrecognized node type: %d", nodeTag(path));
1072  *cost = *selec = 0; /* keep compiler quiet */
1073  }
1074 }
#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 1501 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().

1503 {
1504  Cost startup_cost = 0;
1505  Cost run_cost = 0;
1506  QualCost qpqual_cost;
1507  Cost cpu_per_tuple;
1508 
1509  /* Should only be applied to base relations that are CTEs */
1510  Assert(baserel->relid > 0);
1511  Assert(baserel->rtekind == RTE_CTE);
1512 
1513  /* Mark the path with the correct row estimate */
1514  if (param_info)
1515  path->rows = param_info->ppi_rows;
1516  else
1517  path->rows = baserel->rows;
1518 
1519  /* Charge one CPU tuple cost per row for tuplestore manipulation */
1520  cpu_per_tuple = cpu_tuple_cost;
1521 
1522  /* Add scanning CPU costs */
1523  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1524 
1525  startup_cost += qpqual_cost.startup;
1526  cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1527  run_cost += cpu_per_tuple * baserel->tuples;
1528 
1529  /* tlist eval costs are paid per output row, not per tuple scanned */
1530  startup_cost += path->pathtarget->cost.startup;
1531  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1532 
1533  path->startup_cost = startup_cost;
1534  path->total_cost = startup_cost + run_cost;
1535 }
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:4328
#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 1334 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().

1336 {
1337  Cost startup_cost = 0;
1338  Cost run_cost = 0;
1339  QualCost qpqual_cost;
1340  Cost cpu_per_tuple;
1341  RangeTblEntry *rte;
1342  QualCost exprcost;
1343 
1344  /* Should only be applied to base relations that are functions */
1345  Assert(baserel->relid > 0);
1346  rte = planner_rt_fetch(baserel->relid, root);
1347  Assert(rte->rtekind == RTE_FUNCTION);
1348 
1349  /* Mark the path with the correct row estimate */
1350  if (param_info)
1351  path->rows = param_info->ppi_rows;
1352  else
1353  path->rows = baserel->rows;
1354 
1355  /*
1356  * Estimate costs of executing the function expression(s).
1357  *
1358  * Currently, nodeFunctionscan.c always executes the functions to
1359  * completion before returning any rows, and caches the results in a
1360  * tuplestore. So the function eval cost is all startup cost, and per-row
1361  * costs are minimal.
1362  *
1363  * XXX in principle we ought to charge tuplestore spill costs if the
1364  * number of rows is large. However, given how phony our rowcount
1365  * estimates for functions tend to be, there's not a lot of point in that
1366  * refinement right now.
1367  */
1368  cost_qual_eval_node(&exprcost, (Node *) rte->functions, root);
1369 
1370  startup_cost += exprcost.startup + exprcost.per_tuple;
1371 
1372  /* Add scanning CPU costs */
1373  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1374 
1375  startup_cost += qpqual_cost.startup;
1376  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1377  run_cost += cpu_per_tuple * baserel->tuples;
1378 
1379  /* tlist eval costs are paid per output row, not per tuple scanned */
1380  startup_cost += path->pathtarget->cost.startup;
1381  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1382 
1383  path->startup_cost = startup_cost;
1384  path->total_cost = startup_cost + run_cost;
1385 }
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4068
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:4328
#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 366 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().

369 {
370  Cost startup_cost = 0;
371  Cost run_cost = 0;
372 
373  /* Mark the path with the correct row estimate */
374  if (rows)
375  path->path.rows = *rows;
376  else if (param_info)
377  path->path.rows = param_info->ppi_rows;
378  else
379  path->path.rows = rel->rows;
380 
381  startup_cost = path->subpath->startup_cost;
382 
383  run_cost = path->subpath->total_cost - path->subpath->startup_cost;
384 
385  /* Parallel setup and communication cost. */
386  startup_cost += parallel_setup_cost;
387  run_cost += parallel_tuple_cost * path->path.rows;
388 
389  path->path.startup_cost = startup_cost;
390  path->path.total_cost = (startup_cost + run_cost);
391 }
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 404 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().

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

2574 {
2575  double output_tuples;
2576  Cost startup_cost;
2577  Cost total_cost;
2578 
2579  output_tuples = numGroups;
2580  startup_cost = input_startup_cost;
2581  total_cost = input_total_cost;
2582 
2583  /*
2584  * Charge one cpu_operator_cost per comparison per input tuple. We assume
2585  * all columns get compared at most of the tuples.
2586  */
2587  total_cost += cpu_operator_cost * input_tuples * numGroupCols;
2588 
2589  /*
2590  * If there are quals (HAVING quals), account for their cost and
2591  * selectivity.
2592  */
2593  if (quals)
2594  {
2595  QualCost qual_cost;
2596 
2597  cost_qual_eval(&qual_cost, quals, root);
2598  startup_cost += qual_cost.startup;
2599  total_cost += qual_cost.startup + output_tuples * qual_cost.per_tuple;
2600 
2601  output_tuples = clamp_row_est(output_tuples *
2603  quals,
2604  0,
2605  JOIN_INNER,
2606  NULL));
2607  }
2608 
2609  path->rows = output_tuples;
2610  path->startup_cost = startup_cost;
2611  path->total_cost = total_cost;
2612 }
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:4042
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:190
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 1789 of file costsize.c.

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

Referenced by create_incremental_sort_path().

1794 {
1795  Cost startup_cost = 0,
1796  run_cost = 0,
1797  input_run_cost = input_total_cost - input_startup_cost;
1798  double group_tuples,
1799  input_groups;
1800  Cost group_startup_cost,
1801  group_run_cost,
1802  group_input_run_cost;
1803  List *presortedExprs = NIL;
1804  ListCell *l;
1805  int i = 0;
1806  bool unknown_varno = false;
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  /* Default estimate of number of groups, capped to one group per row. */
1818  input_groups = Min(input_tuples, DEFAULT_NUM_DISTINCT);
1819 
1820  /*
1821  * Extract presorted keys as list of expressions.
1822  *
1823  * We need to be careful about Vars containing "varno 0" which might have
1824  * been introduced by generate_append_tlist, which would confuse
1825  * estimate_num_groups (in fact it'd fail for such expressions). See
1826  * recurse_set_operations which has to deal with the same issue.
1827  *
1828  * Unlike recurse_set_operations we can't access the original target list
1829  * here, and even if we could it's not very clear how useful would that be
1830  * for a set operation combining multiple tables. So we simply detect if
1831  * there are any expressions with "varno 0" and use the default
1832  * DEFAULT_NUM_DISTINCT in that case.
1833  *
1834  * We might also use either 1.0 (a single group) or input_tuples (each row
1835  * being a separate group), pretty much the worst and best case for
1836  * incremental sort. But those are extreme cases and using something in
1837  * between seems reasonable. Furthermore, generate_append_tlist is used
1838  * for set operations, which are likely to produce mostly unique output
1839  * anyway - from that standpoint the DEFAULT_NUM_DISTINCT is defensive
1840  * while maintaining lower startup cost.
1841  */
1842  foreach(l, pathkeys)
1843  {
1844  PathKey *key = (PathKey *) lfirst(l);
1846  linitial(key->pk_eclass->ec_members);
1847 
1848  /*
1849  * Check if the expression contains Var with "varno 0" so that we
1850  * don't call estimate_num_groups in that case.
1851  */
1852  if (bms_is_member(0, pull_varnos((Node *) member->em_expr)))
1853  {
1854  unknown_varno = true;
1855  break;
1856  }
1857 
1858  /* expression not containing any Vars with "varno 0" */
1859  presortedExprs = lappend(presortedExprs, member->em_expr);
1860 
1861  i++;
1862  if (i >= presorted_keys)
1863  break;
1864  }
1865 
1866  /* Estimate number of groups with equal presorted keys. */
1867  if (!unknown_varno)
1868  input_groups = estimate_num_groups(root, presortedExprs, input_tuples, NULL);
1869 
1870  group_tuples = input_tuples / input_groups;
1871  group_input_run_cost = input_run_cost / input_groups;
1872 
1873  /*
1874  * Estimate average cost of sorting of one group where presorted keys are
1875  * equal. Incremental sort is sensitive to distribution of tuples to the
1876  * groups, where we're relying on quite rough assumptions. Thus, we're
1877  * pessimistic about incremental sort performance and increase its average
1878  * group size by half.
1879  */
1880  cost_tuplesort(&group_startup_cost, &group_run_cost,
1881  1.5 * group_tuples, width, comparison_cost, sort_mem,
1882  limit_tuples);
1883 
1884  /*
1885  * Startup cost of incremental sort is the startup cost of its first group
1886  * plus the cost of its input.
1887  */
1888  startup_cost += group_startup_cost
1889  + input_startup_cost + group_input_run_cost;
1890 
1891  /*
1892  * After we started producing tuples from the first group, the cost of
1893  * producing all the tuples is given by the cost to finish processing this
1894  * group, plus the total cost to process the remaining groups, plus the
1895  * remaining cost of input.
1896  */
1897  run_cost += group_run_cost
1898  + (group_run_cost + group_startup_cost) * (input_groups - 1)
1899  + group_input_run_cost * (input_groups - 1);
1900 
1901  /*
1902  * Incremental sort adds some overhead by itself. Firstly, it has to
1903  * detect the sort groups. This is roughly equal to one extra copy and
1904  * comparison per tuple. Secondly, it has to reset the tuplesort context
1905  * for every group.
1906  */
1907  run_cost += (cpu_tuple_cost + comparison_cost) * input_tuples;
1908  run_cost += 2.0 * cpu_tuple_cost * input_groups;
1909 
1910  path->rows = input_tuples;
1911  path->startup_cost = startup_cost;
1912  path->total_cost = startup_cost + run_cost;
1913 }
#define NIL
Definition: pg_list.h:65
double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset)
Definition: selfuncs.c:3357
#define Min(x, y)
Definition: c.h:920
Definition: nodes.h:529
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:1687
Relids pull_varnos(Node *node)
Definition: var.c:95
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
#define DEFAULT_NUM_DISTINCT
Definition: selfuncs.h:49
int i
Definition: pg_list.h:50
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:427
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 479 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().

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

2260 {
2261  Cost startup_cost = input_startup_cost;
2262  Cost run_cost = input_total_cost - input_startup_cost;
2263  double nbytes = relation_byte_size(tuples, width);
2264  long work_mem_bytes = work_mem * 1024L;
2265 
2266  path->rows = tuples;
2267 
2268  /*
2269  * Whether spilling or not, charge 2x cpu_operator_cost per tuple to
2270  * reflect bookkeeping overhead. (This rate must be more than what
2271  * cost_rescan charges for materialize, ie, cpu_operator_cost per tuple;
2272  * if it is exactly the same then there will be a cost tie between
2273  * nestloop with A outer, materialized B inner and nestloop with B outer,
2274  * materialized A inner. The extra cost ensures we'll prefer
2275  * materializing the smaller rel.) Note that this is normally a good deal
2276  * less than cpu_tuple_cost; which is OK because a Material plan node
2277  * doesn't do qual-checking or projection, so it's got less overhead than
2278  * most plan nodes.
2279  */
2280  run_cost += 2 * cpu_operator_cost * tuples;
2281 
2282  /*
2283  * If we will spill to disk, charge at the rate of seq_page_cost per page.
2284  * This cost is assumed to be evenly spread through the plan run phase,
2285  * which isn't exactly accurate but our cost model doesn't allow for
2286  * nonuniform costs within the run phase.
2287  */
2288  if (nbytes > work_mem_bytes)
2289  {
2290  double npages = ceil(nbytes / BLCKSZ);
2291 
2292  run_cost += seq_page_cost * npages;
2293  }
2294 
2295  path->startup_cost = startup_cost;
2296  path->total_cost = startup_cost + run_cost;
2297 }
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:5677
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 2208 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().

2212 {
2213  Cost startup_cost = 0;
2214  Cost run_cost = 0;
2215  Cost comparison_cost;
2216  double N;
2217  double logN;
2218 
2219  /*
2220  * Avoid log(0)...
2221  */
2222  N = (n_streams < 2) ? 2.0 : (double) n_streams;
2223  logN = LOG2(N);
2224 
2225  /* Assumed cost per tuple comparison */
2226  comparison_cost = 2.0 * cpu_operator_cost;
2227 
2228  /* Heap creation cost */
2229  startup_cost += comparison_cost * N * logN;
2230 
2231  /* Per-tuple heap maintenance cost */
2232  run_cost += tuples * comparison_cost * logN;
2233 
2234  /*
2235  * Although MergeAppend does not do any selection or projection, it's not
2236  * free; add a small per-tuple overhead.
2237  */
2238  run_cost += cpu_tuple_cost * APPEND_CPU_COST_MULTIPLIER * tuples;
2239 
2240  path->startup_cost = startup_cost + input_startup_cost;
2241  path->total_cost = startup_cost + run_cost + input_total_cost;
2242 }
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 1542 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().

1544 {
1545  Cost startup_cost = 0;
1546  Cost run_cost = 0;
1547  QualCost qpqual_cost;
1548  Cost cpu_per_tuple;
1549 
1550  /* Should only be applied to base relations that are Tuplestores */
1551  Assert(baserel->relid > 0);
1552  Assert(baserel->rtekind == RTE_NAMEDTUPLESTORE);
1553 
1554  /* Mark the path with the correct row estimate */
1555  if (param_info)
1556  path->rows = param_info->ppi_rows;
1557  else
1558  path->rows = baserel->rows;
1559 
1560  /* Charge one CPU tuple cost per row for tuplestore manipulation */
1561  cpu_per_tuple = cpu_tuple_cost;
1562 
1563  /* Add scanning CPU costs */
1564  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1565 
1566  startup_cost += qpqual_cost.startup;
1567  cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1568  run_cost += cpu_per_tuple * baserel->tuples;
1569 
1570  path->startup_cost = startup_cost;
1571  path->total_cost = startup_cost + run_cost;
1572 }
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:4328
#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 4042 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().

4043 {
4044  cost_qual_eval_context context;
4045  ListCell *l;
4046 
4047  context.root = root;
4048  context.total.startup = 0;
4049  context.total.per_tuple = 0;
4050 
4051  /* We don't charge any cost for the implicit ANDing at top level ... */
4052 
4053  foreach(l, quals)
4054  {
4055  Node *qual = (Node *) lfirst(l);
4056 
4057  cost_qual_eval_walker(qual, &context);
4058  }
4059 
4060  *cost = context.total;
4061 }
PlannerInfo * root
Definition: costsize.c:147
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:4082
#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 4068 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().

4069 {
4070  cost_qual_eval_context context;
4071 
4072  context.root = root;
4073  context.total.startup = 0;
4074  context.total.per_tuple = 0;
4075 
4076  cost_qual_eval_walker(qual, &context);
4077 
4078  *cost = context.total;
4079 }
PlannerInfo * root
Definition: costsize.c:147
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:4082

◆ cost_qual_eval_walker()

static bool cost_qual_eval_walker ( Node node,
cost_qual_eval_context context 
)
static

Definition at line 4082 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().

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

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

3938 {
3939  switch (path->pathtype)
3940  {
3941  case T_FunctionScan:
3942 
3943  /*
3944  * Currently, nodeFunctionscan.c always executes the function to
3945  * completion before returning any rows, and caches the results in
3946  * a tuplestore. So the function eval cost is all startup cost
3947  * and isn't paid over again on rescans. However, all run costs
3948  * will be paid over again.
3949  */
3950  *rescan_startup_cost = 0;
3951  *rescan_total_cost = path->total_cost - path->startup_cost;
3952  break;
3953  case T_HashJoin:
3954 
3955  /*
3956  * If it's a single-batch join, we don't need to rebuild the hash
3957  * table during a rescan.
3958  */
3959  if (((HashPath *) path)->num_batches == 1)
3960  {
3961  /* Startup cost is exactly the cost of hash table building */
3962  *rescan_startup_cost = 0;
3963  *rescan_total_cost = path->total_cost - path->startup_cost;
3964  }
3965  else
3966  {
3967  /* Otherwise, no special treatment */
3968  *rescan_startup_cost = path->startup_cost;
3969  *rescan_total_cost = path->total_cost;
3970  }
3971  break;
3972  case T_CteScan:
3973  case T_WorkTableScan:
3974  {
3975  /*
3976  * These plan types materialize their final result in a
3977  * tuplestore or tuplesort object. So the rescan cost is only
3978  * cpu_tuple_cost per tuple, unless the result is large enough
3979  * to spill to disk.
3980  */
3981  Cost run_cost = cpu_tuple_cost * path->rows;
3982  double nbytes = relation_byte_size(path->rows,
3983  path->pathtarget->width);
3984  long work_mem_bytes = work_mem * 1024L;
3985 
3986  if (nbytes > work_mem_bytes)
3987  {
3988  /* It will spill, so account for re-read cost */
3989  double npages = ceil(nbytes / BLCKSZ);
3990 
3991  run_cost += seq_page_cost * npages;
3992  }
3993  *rescan_startup_cost = 0;
3994  *rescan_total_cost = run_cost;
3995  }
3996  break;
3997  case T_Material:
3998  case T_Sort:
3999  {
4000  /*
4001  * These plan types not only materialize their results, but do
4002  * not implement qual filtering or projection. So they are
4003  * even cheaper to rescan than the ones above. We charge only
4004  * cpu_operator_cost per tuple. (Note: keep that in sync with
4005  * the run_cost charge in cost_sort, and also see comments in
4006  * cost_material before you change it.)
4007  */
4008  Cost run_cost = cpu_operator_cost * path->rows;
4009  double nbytes = relation_byte_size(path->rows,
4010  path->pathtarget->width);
4011  long work_mem_bytes = work_mem * 1024L;
4012 
4013  if (nbytes > work_mem_bytes)
4014  {
4015  /* It will spill, so account for re-read cost */
4016  double npages = ceil(nbytes / BLCKSZ);
4017 
4018  run_cost += seq_page_cost * npages;
4019  }
4020  *rescan_startup_cost = 0;
4021  *rescan_total_cost = run_cost;
4022  }
4023  break;
4024  default:
4025  *rescan_startup_cost = path->startup_cost;
4026  *rescan_total_cost = path->total_cost;
4027  break;
4028  }
4029 }
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:5677
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 1579 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().

1581 {
1582  Cost startup_cost = 0;
1583  Cost run_cost = 0;
1584  QualCost qpqual_cost;
1585  Cost cpu_per_tuple;
1586 
1587  /* Should only be applied to RTE_RESULT base relations */
1588  Assert(baserel->relid > 0);
1589  Assert(baserel->rtekind == RTE_RESULT);
1590 
1591  /* Mark the path with the correct row estimate */
1592  if (param_info)
1593  path->rows = param_info->ppi_rows;
1594  else
1595  path->rows = baserel->rows;
1596 
1597  /* We charge qual cost plus cpu_tuple_cost */
1598  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1599 
1600  startup_cost += qpqual_cost.startup;
1601  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1602  run_cost += cpu_per_tuple * baserel->tuples;
1603 
1604  path->startup_cost = startup_cost;
1605  path->total_cost = startup_cost + run_cost;
1606 }
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:4328
#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 291 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().

293 {
294  Cost startup_cost = 0;
295  Cost run_cost = 0;
296  RangeTblEntry *rte;
297  TableSampleClause *tsc;
298  TsmRoutine *tsm;
299  double spc_seq_page_cost,
300  spc_random_page_cost,
301  spc_page_cost;
302  QualCost qpqual_cost;
303  Cost cpu_per_tuple;
304 
305  /* Should only be applied to base relations with tablesample clauses */
306  Assert(baserel->relid > 0);
307  rte = planner_rt_fetch(baserel->relid, root);
308  Assert(rte->rtekind == RTE_RELATION);
309  tsc = rte->tablesample;
310  Assert(tsc != NULL);
311  tsm = GetTsmRoutine(tsc->tsmhandler);
312 
313  /* Mark the path with the correct row estimate */
314  if (param_info)
315  path->rows = param_info->ppi_rows;
316  else
317  path->rows = baserel->rows;
318 
319  /* fetch estimated page cost for tablespace containing table */
321  &spc_random_page_cost,
322  &spc_seq_page_cost);
323 
324  /* if NextSampleBlock is used, assume random access, else sequential */
325  spc_page_cost = (tsm->NextSampleBlock != NULL) ?
326  spc_random_page_cost : spc_seq_page_cost;
327 
328  /*
329  * disk costs (recall that baserel->pages has already been set to the
330  * number of pages the sampling method will visit)
331  */
332  run_cost += spc_page_cost * baserel->pages;
333 
334  /*
335  * CPU costs (recall that baserel->tuples has already been set to the
336  * number of tuples the sampling method will select). Note that we ignore
337  * execution cost of the TABLESAMPLE parameter expressions; they will be
338  * evaluated only once per scan, and in most usages they'll likely be
339  * simple constants anyway. We also don't charge anything for the
340  * calculations the sampling method might do internally.
341  */
342  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
343 
344  startup_cost += qpqual_cost.startup;
345  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
346  run_cost += cpu_per_tuple * baserel->tuples;
347  /* tlist eval costs are paid per output row, not per tuple scanned */
348  startup_cost += path->pathtarget->cost.startup;
349  run_cost += path->pathtarget->cost.per_tuple * path->rows;
350 
351  path->startup_cost = startup_cost;
352  path->total_cost = startup_cost + run_cost;
353 }
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:4328
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 214 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().

216 {
217  Cost startup_cost = 0;
218  Cost cpu_run_cost;
219  Cost disk_run_cost;
220  double spc_seq_page_cost;
221  QualCost qpqual_cost;
222  Cost cpu_per_tuple;
223 
224  /* Should only be applied to base relations */
225  Assert(baserel->relid > 0);
226  Assert(baserel->rtekind == RTE_RELATION);
227 
228  /* Mark the path with the correct row estimate */
229  if (param_info)
230  path->rows = param_info->ppi_rows;
231  else
232  path->rows = baserel->rows;
233 
234  if (!enable_seqscan)
235  startup_cost += disable_cost;
236 
237  /* fetch estimated page cost for tablespace containing table */
239  NULL,
240  &spc_seq_page_cost);
241 
242  /*
243  * disk costs
244  */
245  disk_run_cost = spc_seq_page_cost * baserel->pages;
246 
247  /* CPU costs */
248  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
249 
250  startup_cost += qpqual_cost.startup;
251  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
252  cpu_run_cost = cpu_per_tuple * baserel->tuples;
253  /* tlist eval costs are paid per output row, not per tuple scanned */
254  startup_cost += path->pathtarget->cost.startup;
255  cpu_run_cost += path->pathtarget->cost.per_tuple * path->rows;
256 
257  /* Adjust costing for parallelism, if used. */
258  if (path->parallel_workers > 0)
259  {
260  double parallel_divisor = get_parallel_divisor(path);
261 
262  /* The CPU cost is divided among all the workers. */
263  cpu_run_cost /= parallel_divisor;
264 
265  /*
266  * It may be possible to amortize some of the I/O cost, but probably
267  * not very much, because most operating systems already do aggressive
268  * prefetching. For now, we assume that the disk run cost can't be
269  * amortized at all.
270  */
271 
272  /*
273  * In the case of a parallel plan, the row count needs to represent
274  * the number of tuples processed per worker.
275  */
276  path->rows = clamp_row_est(path->rows / parallel_divisor);
277  }
278 
279  path->startup_cost = startup_cost;
280  path->total_cost = startup_cost + cpu_run_cost + disk_run_cost;
281 }
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:5698
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:4328
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:190
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 1928 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().

1933 {
1934  Cost startup_cost;
1935  Cost run_cost;
1936 
1937  cost_tuplesort(&startup_cost, &run_cost,
1938  tuples, width,
1939  comparison_cost, sort_mem,
1940  limit_tuples);
1941 
1942  if (!enable_sort)
1943  startup_cost += disable_cost;
1944 
1945  startup_cost += input_cost;
1946 
1947  path->rows = tuples;
1948  path->startup_cost = startup_cost;
1949  path->total_cost = startup_cost + run_cost;
1950 }
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:1687
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 3842 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().

3843 {
3844  QualCost sp_cost;
3845 
3846  /* Figure any cost for evaluating the testexpr */
3847  cost_qual_eval(&sp_cost,
3848  make_ands_implicit((Expr *) subplan->testexpr),
3849  root);
3850 
3851  if (subplan->useHashTable)
3852  {
3853  /*
3854  * If we are using a hash table for the subquery outputs, then the
3855  * cost of evaluating the query is a one-time cost. We charge one
3856  * cpu_operator_cost per tuple for the work of loading the hashtable,
3857  * too.
3858  */
3859  sp_cost.startup += plan->total_cost +
3860  cpu_operator_cost * plan->plan_rows;
3861 
3862  /*
3863  * The per-tuple costs include the cost of evaluating the lefthand
3864  * expressions, plus the cost of probing the hashtable. We already
3865  * accounted for the lefthand expressions as part of the testexpr, and
3866  * will also have counted one cpu_operator_cost for each comparison
3867  * operator. That is probably too low for the probing cost, but it's
3868  * hard to make a better estimate, so live with it for now.
3869  */
3870  }
3871  else
3872  {
3873  /*
3874  * Otherwise we will be rescanning the subplan output on each
3875  * evaluation. We need to estimate how much of the output we will
3876  * actually need to scan. NOTE: this logic should agree with the
3877  * tuple_fraction estimates used by make_subplan() in
3878  * plan/subselect.c.
3879  */
3880  Cost plan_run_cost = plan->total_cost - plan->startup_cost;
3881 
3882  if (subplan->subLinkType == EXISTS_SUBLINK)
3883  {
3884  /* we only need to fetch 1 tuple; clamp to avoid zero divide */
3885  sp_cost.per_tuple += plan_run_cost / clamp_row_est(plan->plan_rows);
3886  }
3887  else if (subplan->subLinkType == ALL_SUBLINK ||
3888  subplan->subLinkType == ANY_SUBLINK)
3889  {
3890  /* assume we need 50% of the tuples */
3891  sp_cost.per_tuple += 0.50 * plan_run_cost;
3892  /* also charge a cpu_operator_cost per row examined */
3893  sp_cost.per_tuple += 0.50 * plan->plan_rows * cpu_operator_cost;
3894  }
3895  else
3896  {
3897  /* assume we need all tuples */
3898  sp_cost.per_tuple += plan_run_cost;
3899  }
3900 
3901  /*
3902  * Also account for subplan's startup cost. If the subplan is
3903  * uncorrelated or undirect correlated, AND its topmost node is one
3904  * that materializes its output, assume that we'll only need to pay
3905  * its startup cost once; otherwise assume we pay the startup cost
3906  * every time.
3907  */
3908  if (subplan->parParam == NIL &&
3910  sp_cost.startup += plan->startup_cost;
3911  else
3912  sp_cost.per_tuple += plan->startup_cost;
3913  }
3914 
3915  subplan->startup_cost = sp_cost.startup;
3916  subplan->per_call_cost = sp_cost.per_tuple;
3917 }
#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:4042
Cost startup_cost
Definition: plannodes.h:123
double cpu_operator_cost
Definition: costsize.c:115
List * make_ands_implicit(Expr *clause)
Definition: makefuncs.c:718
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:190
double Cost
Definition: nodes.h:663

◆ cost_subqueryscan()

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

Definition at line 1285 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().

1287 {
1288  Cost startup_cost;
1289  Cost run_cost;
1290  QualCost qpqual_cost;
1291  Cost cpu_per_tuple;
1292 
1293  /* Should only be applied to base relations that are subqueries */
1294  Assert(baserel->relid > 0);
1295  Assert(baserel->rtekind == RTE_SUBQUERY);
1296 
1297  /* Mark the path with the correct row estimate */
1298  if (param_info)
1299  path->path.rows = param_info->ppi_rows;
1300  else
1301  path->path.rows = baserel->rows;
1302 
1303  /*
1304  * Cost of path is cost of evaluating the subplan, plus cost of evaluating
1305  * any restriction clauses and tlist that will be attached to the
1306  * SubqueryScan node, plus cpu_tuple_cost to account for selection and
1307  * projection overhead.
1308  */
1309  path->path.startup_cost = path->subpath->startup_cost;
1310  path->path.total_cost = path->subpath->total_cost;
1311 
1312  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1313 
1314  startup_cost = qpqual_cost.startup;
1315  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1316  run_cost = cpu_per_tuple * baserel->tuples;
1317 
1318  /* tlist eval costs are paid per output row, not per tuple scanned */
1319  startup_cost += path->path.pathtarget->cost.startup;
1320  run_cost += path->path.pathtarget->cost.per_tuple * path->path.rows;
1321 
1322  path->path.startup_cost += startup_cost;
1323  path->path.total_cost += startup_cost + run_cost;
1324 }
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:4328
#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 1395 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().

1397 {
1398  Cost startup_cost = 0;
1399  Cost run_cost = 0;
1400  QualCost qpqual_cost;
1401  Cost cpu_per_tuple;
1402  RangeTblEntry *rte;
1403  QualCost exprcost;
1404 
1405  /* Should only be applied to base relations that are functions */
1406  Assert(baserel->relid > 0);
1407  rte = planner_rt_fetch(baserel->relid, root);
1408  Assert(rte->rtekind == RTE_TABLEFUNC);
1409 
1410  /* Mark the path with the correct row estimate */
1411  if (param_info)
1412  path->rows = param_info->ppi_rows;
1413  else
1414  path->rows = baserel->rows;
1415 
1416  /*
1417  * Estimate costs of executing the table func expression(s).
1418  *
1419  * XXX in principle we ought to charge tuplestore spill costs if the
1420  * number of rows is large. However, given how phony our rowcount
1421  * estimates for tablefuncs tend to be, there's not a lot of point in that
1422  * refinement right now.
1423  */
1424  cost_qual_eval_node(&exprcost, (Node *) rte->tablefunc, root);
1425 
1426  startup_cost += exprcost.startup + exprcost.per_tuple;
1427 
1428  /* Add scanning CPU costs */
1429  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1430 
1431  startup_cost += qpqual_cost.startup;
1432  cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1433  run_cost += cpu_per_tuple * baserel->tuples;
1434 
1435  /* tlist eval costs are paid per output row, not per tuple scanned */
1436  startup_cost += path->pathtarget->cost.startup;
1437  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1438 
1439  path->startup_cost = startup_cost;
1440  path->total_cost = startup_cost + run_cost;
1441 }
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4068
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:4328
#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 1179 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().

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

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

1453 {
1454  Cost startup_cost = 0;
1455  Cost run_cost = 0;
1456  QualCost qpqual_cost;
1457  Cost cpu_per_tuple;
1458 
1459  /* Should only be applied to base relations that are values lists */
1460  Assert(baserel->relid > 0);
1461  Assert(baserel->rtekind == RTE_VALUES);
1462 
1463  /* Mark the path with the correct row estimate */
1464  if (param_info)
1465  path->rows = param_info->ppi_rows;
1466  else
1467  path->rows = baserel->rows;
1468 
1469  /*
1470  * For now, estimate list evaluation cost at one operator eval per list
1471  * (probably pretty bogus, but is it worth being smarter?)
1472  */
1473  cpu_per_tuple = cpu_operator_cost;
1474 
1475  /* Add scanning CPU costs */
1476  get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1477 
1478  startup_cost += qpqual_cost.startup;
1479  cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1480  run_cost += cpu_per_tuple * baserel->tuples;
1481 
1482  /* tlist eval costs are paid per output row, not per tuple scanned */
1483  startup_cost += path->pathtarget->cost.startup;
1484  run_cost += path->pathtarget->cost.per_tuple * path->rows;
1485 
1486  path->startup_cost = startup_cost;
1487  path->total_cost = startup_cost + run_cost;
1488 }
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:4328
#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 2495 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().

2499 {
2500  Cost startup_cost;
2501  Cost total_cost;
2502  ListCell *lc;
2503 
2504  startup_cost = input_startup_cost;
2505  total_cost = input_total_cost;
2506 
2507  /*
2508  * Window functions are assumed to cost their stated execution cost, plus
2509  * the cost of evaluating their input expressions, per tuple. Since they
2510  * may in fact evaluate their inputs at multiple rows during each cycle,
2511  * this could be a drastic underestimate; but without a way to know how
2512  * many rows the window function will fetch, it's hard to do better. In
2513  * any case, it's a good estimate for all the built-in window functions,
2514  * so we'll just do this for now.
2515  */
2516  foreach(lc, windowFuncs)
2517  {
2518  WindowFunc *wfunc = lfirst_node(WindowFunc, lc);
2519  Cost wfunccost;
2520  QualCost argcosts;
2521 
2522  argcosts.startup = argcosts.per_tuple = 0;
2523  add_function_cost(root, wfunc->winfnoid, (Node *) wfunc,
2524  &argcosts);
2525  startup_cost += argcosts.startup;
2526  wfunccost = argcosts.per_tuple;
2527 
2528  /* also add the input expressions' cost to per-input-row costs */
2529  cost_qual_eval_node(&argcosts, (Node *) wfunc->args, root);
2530  startup_cost += argcosts.startup;
2531  wfunccost += argcosts.per_tuple;
2532 
2533  /*
2534  * Add the filter's cost to per-input-row costs. XXX We should reduce
2535  * input expression costs according to filter selectivity.
2536  */
2537  cost_qual_eval_node(&argcosts, (Node *) wfunc->aggfilter, root);
2538  startup_cost += argcosts.startup;
2539  wfunccost += argcosts.per_tuple;
2540 
2541  total_cost += wfunccost * input_tuples;
2542  }
2543 
2544  /*
2545  * We also charge cpu_operator_cost per grouping column per tuple for
2546  * grouping comparisons, plus cpu_tuple_cost per tuple for general
2547  * overhead.
2548  *
2549  * XXX this neglects costs of spooling the data to disk when it overflows
2550  * work_mem. Sooner or later that should get accounted for.
2551  */
2552  total_cost += cpu_operator_cost * (numPartCols + numOrderCols) * input_tuples;
2553  total_cost += cpu_tuple_cost * input_tuples;
2554 
2555  path->rows = input_tuples;
2556  path->startup_cost = startup_cost;
2557  path->total_cost = total_cost;
2558 }
void cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
Definition: costsize.c:4068
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 770 of file costsize.c.

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

Referenced by cost_index().

771 {
772  List *result = NIL;
773  ListCell *lc;
774 
775  foreach(lc, qual_clauses)
776  {
777  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
778 
779  if (rinfo->pseudoconstant)
780  continue; /* we may drop pseudoconstants here */
781  if (is_redundant_with_indexclauses(rinfo, indexclauses))
782  continue; /* dup or derived from same EquivalenceClass */
783  /* ... skip the predicate proof attempt createplan.c will try ... */
784  result = lappend(result, rinfo);
785  }
786  return result;
787 }
#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 3587 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().

3590 {
3591  Path *outer_path = path->jpath.outerjoinpath;
3592  Path *inner_path = path->jpath.innerjoinpath;
3593  double outer_path_rows = outer_path->rows;
3594  double inner_path_rows = inner_path->rows;
3595  double inner_path_rows_total = workspace->inner_rows_total;
3596  List *hashclauses = path->path_hashclauses;
3597  Cost startup_cost = workspace->startup_cost;
3598  Cost run_cost = workspace->run_cost;
3599  int numbuckets = workspace->numbuckets;
3600  int numbatches = workspace->numbatches;
3601  Cost cpu_per_tuple;
3602  QualCost hash_qual_cost;
3603  QualCost qp_qual_cost;
3604  double hashjointuples;
3605  double virtualbuckets;
3606  Selectivity innerbucketsize;
3607  Selectivity innermcvfreq;
3608  ListCell *hcl;
3609 
3610  /* Mark the path with the correct row estimate */
3611  if (path->jpath.path.param_info)
3612  path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
3613  else
3614  path->jpath.path.rows = path->jpath.path.parent->rows;
3615 
3616  /* For partial paths, scale row estimate. */
3617  if (path->jpath.path.parallel_workers > 0)
3618  {
3619  double parallel_divisor = get_parallel_divisor(&path->jpath.path);
3620 
3621  path->jpath.path.rows =
3622  clamp_row_est(path->jpath.path.rows / parallel_divisor);
3623  }
3624 
3625  /*
3626  * We could include disable_cost in the preliminary estimate, but that
3627  * would amount to optimizing for the case where the join method is
3628  * disabled, which doesn't seem like the way to bet.
3629  */
3630  if (!enable_hashjoin)
3631  startup_cost += disable_cost;
3632 
3633  /* mark the path with estimated # of batches */
3634  path->num_batches = numbatches;
3635 
3636  /* store the total number of tuples (sum of partial row estimates) */
3637  path->inner_rows_total = inner_path_rows_total;
3638 
3639  /* and compute the number of "virtual" buckets in the whole join */
3640  virtualbuckets = (double) numbuckets * (double) numbatches;
3641 
3642  /*
3643  * Determine bucketsize fraction and MCV frequency for the inner relation.
3644  * We use the smallest bucketsize or MCV frequency estimated for any
3645  * individual hashclause; this is undoubtedly conservative.
3646  *
3647  * BUT: if inner relation has been unique-ified, we can assume it's good
3648  * for hashing. This is important both because it's the right answer, and
3649  * because we avoid contaminating the cache with a value that's wrong for
3650  * non-unique-ified paths.
3651  */
3652  if (IsA(inner_path, UniquePath))
3653  {
3654  innerbucketsize = 1.0 / virtualbuckets;
3655  innermcvfreq = 0.0;
3656  }
3657  else
3658  {
3659  innerbucketsize = 1.0;
3660  innermcvfreq = 1.0;
3661  foreach(hcl, hashclauses)
3662  {
3663  RestrictInfo *restrictinfo = lfirst_node(RestrictInfo, hcl);
3664  Selectivity thisbucketsize;
3665  Selectivity thismcvfreq;
3666 
3667  /*
3668  * First we have to figure out which side of the hashjoin clause
3669  * is the inner side.
3670  *
3671  * Since we tend to visit the same clauses over and over when
3672  * planning a large query, we cache the bucket stats estimates in
3673  * the RestrictInfo node to avoid repeated lookups of statistics.
3674  */
3675  if (bms_is_subset(restrictinfo->right_relids,
3676  inner_path->parent->relids))
3677  {
3678  /* righthand side is inner */
3679  thisbucketsize = restrictinfo->right_bucketsize;
3680  if (thisbucketsize < 0)
3681  {
3682  /* not cached yet */
3684  get_rightop(restrictinfo->clause),
3685  virtualbuckets,
3686  &restrictinfo->right_mcvfreq,
3687  &restrictinfo->right_bucketsize);
3688  thisbucketsize = restrictinfo->right_bucketsize;
3689  }
3690  thismcvfreq = restrictinfo->right_mcvfreq;
3691  }
3692  else
3693  {
3694  Assert(bms_is_subset(restrictinfo->left_relids,
3695  inner_path->parent->relids));
3696  /* lefthand side is inner */
3697  thisbucketsize = restrictinfo->left_bucketsize;
3698  if (thisbucketsize < 0)
3699  {
3700  /* not cached yet */
3702  get_leftop(restrictinfo->clause),
3703  virtualbuckets,
3704  &restrictinfo->left_mcvfreq,
3705  &restrictinfo->left_bucketsize);
3706  thisbucketsize = restrictinfo->left_bucketsize;
3707  }
3708  thismcvfreq = restrictinfo->left_mcvfreq;
3709  }
3710 
3711  if (innerbucketsize > thisbucketsize)
3712  innerbucketsize = thisbucketsize;
3713  if (innermcvfreq > thismcvfreq)
3714  innermcvfreq = thismcvfreq;
3715  }
3716  }
3717 
3718  /*
3719  * If the bucket holding the inner MCV would exceed work_mem, we don't
3720  * want to hash unless there is really no other alternative, so apply
3721  * disable_cost. (The executor normally copes with excessive memory usage
3722  * by splitting batches, but obviously it cannot separate equal values
3723  * that way, so it will be unable to drive the batch size below work_mem
3724  * when this is true.)
3725  */
3726  if (relation_byte_size(clamp_row_est(inner_path_rows * innermcvfreq),
3727  inner_path->pathtarget->width) >
3728  (work_mem * 1024L))
3729  startup_cost += disable_cost;
3730 
3731  /*
3732  * Compute cost of the hashquals and qpquals (other restriction clauses)
3733  * separately.
3734  */
3735  cost_qual_eval(&hash_qual_cost, hashclauses, root);
3736  cost_qual_eval(&qp_qual_cost, path->jpath.joinrestrictinfo, root);
3737  qp_qual_cost.startup -= hash_qual_cost.startup;
3738  qp_qual_cost.per_tuple -= hash_qual_cost.per_tuple;
3739 
3740  /* CPU costs */
3741 
3742  if (path->jpath.jointype == JOIN_SEMI ||
3743  path->jpath.jointype == JOIN_ANTI ||
3744  extra->inner_unique)
3745  {
3746  double outer_matched_rows;
3747  Selectivity inner_scan_frac;
3748 
3749  /*
3750  * With a SEMI or ANTI join, or if the innerrel is known unique, the
3751  * executor will stop after the first match.
3752  *
3753  * For an outer-rel row that has at least one match, we can expect the
3754  * bucket scan to stop after a fraction 1/(match_count+1) of the
3755  * bucket's rows, if the matches are evenly distributed. Since they
3756  * probably aren't quite evenly distributed, we apply a fuzz factor of
3757  * 2.0 to that fraction. (If we used a larger fuzz factor, we'd have
3758  * to clamp inner_scan_frac to at most 1.0; but since match_count is
3759  * at least 1, no such clamp is needed now.)
3760  */
3761  outer_matched_rows = rint(outer_path_rows * extra->semifactors.outer_match_frac);
3762  inner_scan_frac = 2.0 / (extra->semifactors.match_count + 1.0);
3763 
3764  startup_cost += hash_qual_cost.startup;
3765  run_cost += hash_qual_cost.per_tuple * outer_matched_rows *
3766  clamp_row_est(inner_path_rows * innerbucketsize * inner_scan_frac) * 0.5;
3767 
3768  /*
3769  * For unmatched outer-rel rows, the picture is quite a lot different.
3770  * In the first place, there is no reason to assume that these rows
3771  * preferentially hit heavily-populated buckets; instead assume they
3772  * are uncorrelated with the inner distribution and so they see an
3773  * average bucket size of inner_path_rows / virtualbuckets. In the
3774  * second place, it seems likely that they will have few if any exact
3775  * hash-code matches and so very few of the tuples in the bucket will
3776  * actually require eval of the hash quals. We don't have any good
3777  * way to estimate how many will, but for the moment assume that the
3778  * effective cost per bucket entry is one-tenth what it is for
3779  * matchable tuples.
3780  */
3781  run_cost += hash_qual_cost.per_tuple *
3782  (outer_path_rows - outer_matched_rows) *
3783  clamp_row_est(inner_path_rows / virtualbuckets) * 0.05;
3784 
3785  /* Get # of tuples that will pass the basic join */
3786  if (path->jpath.jointype == JOIN_ANTI)
3787  hashjointuples = outer_path_rows - outer_matched_rows;
3788  else
3789  hashjointuples = outer_matched_rows;
3790  }
3791  else
3792  {
3793  /*
3794  * The number of tuple comparisons needed is the number of outer
3795  * tuples times the typical number of tuples in a hash bucket, which
3796  * is the inner relation size times its bucketsize fraction. At each
3797  * one, we need to evaluate the hashjoin quals. But actually,
3798  * charging the full qual eval cost at each tuple is pessimistic,
3799  * since we don't evaluate the quals unless the hash values match
3800  * exactly. For lack of a better idea, halve the cost estimate to
3801  * allow for that.
3802  */
3803  startup_cost += hash_qual_cost.startup;
3804  run_cost += hash_qual_cost.per_tuple * outer_path_rows *
3805  clamp_row_est(inner_path_rows * innerbucketsize) * 0.5;
3806 
3807  /*
3808  * Get approx # tuples passing the hashquals. We use
3809  * approx_tuple_count here because we need an estimate done with
3810  * JOIN_INNER semantics.
3811  */
3812  hashjointuples = approx_tuple_count(root, &path->jpath, hashclauses);
3813  }
3814 
3815  /*
3816  * For each tuple that gets through the hashjoin proper, we charge
3817  * cpu_tuple_cost plus the cost of evaluating additional restriction
3818  * clauses that are to be applied at the join. (This is pessimistic since
3819  * not all of the quals may get evaluated at each tuple.)
3820  */
3821  startup_cost += qp_qual_cost.startup;
3822  cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
3823  run_cost += cpu_per_tuple * hashjointuples;
3824 
3825  /* tlist eval costs are paid per output row, not per tuple scanned */
3826  startup_cost += path->jpath.path.pathtarget->cost.startup;
3827  run_cost += path->jpath.path.pathtarget->cost.per_tuple * path->jpath.path.rows;
3828 
3829  path->jpath.path.startup_cost = startup_cost;
3830  path->jpath.path.total_cost = startup_cost + run_cost;
3831 }
#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:4571
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:4042
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:5698
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:5677
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:137
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:3720
List * path_hashclauses
Definition: pathnodes.h:1600
double clamp_row_est(double nrows)
Definition: costsize.c:190
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 3151 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().

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