Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * costsize.c
4 : * Routines to compute (and set) relation sizes and path costs
5 : *
6 : * Path costs are measured in arbitrary units established by these basic
7 : * parameters:
8 : *
9 : * seq_page_cost Cost of a sequential page fetch
10 : * random_page_cost Cost of a non-sequential page fetch
11 : * cpu_tuple_cost Cost of typical CPU time to process a tuple
12 : * cpu_index_tuple_cost Cost of typical CPU time to process an index tuple
13 : * cpu_operator_cost Cost of CPU time to execute an operator or function
14 : * parallel_tuple_cost Cost of CPU time to pass a tuple from worker to master backend
15 : * parallel_setup_cost Cost of setting up shared memory for parallelism
16 : *
17 : * We expect that the kernel will typically do some amount of read-ahead
18 : * optimization; this in conjunction with seek costs means that seq_page_cost
19 : * is normally considerably less than random_page_cost. (However, if the
20 : * database is fully cached in RAM, it is reasonable to set them equal.)
21 : *
22 : * We also use a rough estimate "effective_cache_size" of the number of
23 : * disk pages in Postgres + OS-level disk cache. (We can't simply use
24 : * NBuffers for this purpose because that would ignore the effects of
25 : * the kernel's disk cache.)
26 : *
27 : * Obviously, taking constants for these values is an oversimplification,
28 : * but it's tough enough to get any useful estimates even at this level of
29 : * detail. Note that all of these parameters are user-settable, in case
30 : * the default values are drastically off for a particular platform.
31 : *
32 : * seq_page_cost and random_page_cost can also be overridden for an individual
33 : * tablespace, in case some data is on a fast disk and other data is on a slow
34 : * disk. Per-tablespace overrides never apply to temporary work files such as
35 : * an external sort or a materialize node that overflows work_mem.
36 : *
37 : * We compute two separate costs for each path:
38 : * total_cost: total estimated cost to fetch all tuples
39 : * startup_cost: cost that is expended before first tuple is fetched
40 : * In some scenarios, such as when there is a LIMIT or we are implementing
41 : * an EXISTS(...) sub-select, it is not necessary to fetch all tuples of the
42 : * path's result. A caller can estimate the cost of fetching a partial
43 : * result by interpolating between startup_cost and total_cost. In detail:
44 : * actual_cost = startup_cost +
45 : * (total_cost - startup_cost) * tuples_to_fetch / path->rows;
46 : * Note that a base relation's rows count (and, by extension, plan_rows for
47 : * plan nodes below the LIMIT node) are set without regard to any LIMIT, so
48 : * that this equation works properly. (Note: while path->rows is never zero
49 : * for ordinary relations, it is zero for paths for provably-empty relations,
50 : * so beware of division-by-zero.) The LIMIT is applied as a top-level
51 : * plan node.
52 : *
53 : * For largely historical reasons, most of the routines in this module use
54 : * the passed result Path only to store their results (rows, startup_cost and
55 : * total_cost) into. All the input data they need is passed as separate
56 : * parameters, even though much of it could be extracted from the Path.
57 : * An exception is made for the cost_XXXjoin() routines, which expect all
58 : * the other fields of the passed XXXPath to be filled in, and similarly
59 : * cost_index() assumes the passed IndexPath is valid except for its output
60 : * values.
61 : *
62 : *
63 : * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
64 : * Portions Copyright (c) 1994, Regents of the University of California
65 : *
66 : * IDENTIFICATION
67 : * src/backend/optimizer/path/costsize.c
68 : *
69 : *-------------------------------------------------------------------------
70 : */
71 :
72 : #include "postgres.h"
73 :
74 : #include <math.h>
75 :
76 : #include "access/amapi.h"
77 : #include "access/htup_details.h"
78 : #include "access/tsmapi.h"
79 : #include "executor/executor.h"
80 : #include "executor/nodeAgg.h"
81 : #include "executor/nodeHash.h"
82 : #include "miscadmin.h"
83 : #include "nodes/makefuncs.h"
84 : #include "nodes/nodeFuncs.h"
85 : #include "optimizer/clauses.h"
86 : #include "optimizer/cost.h"
87 : #include "optimizer/optimizer.h"
88 : #include "optimizer/pathnode.h"
89 : #include "optimizer/paths.h"
90 : #include "optimizer/placeholder.h"
91 : #include "optimizer/plancat.h"
92 : #include "optimizer/planmain.h"
93 : #include "optimizer/restrictinfo.h"
94 : #include "parser/parsetree.h"
95 : #include "utils/lsyscache.h"
96 : #include "utils/selfuncs.h"
97 : #include "utils/spccache.h"
98 : #include "utils/tuplesort.h"
99 :
100 :
101 : #define LOG2(x) (log(x) / 0.693147180559945)
102 :
103 : /*
104 : * Append and MergeAppend nodes are less expensive than some other operations
105 : * which use cpu_tuple_cost; instead of adding a separate GUC, estimate the
106 : * per-tuple cost as cpu_tuple_cost multiplied by this value.
107 : */
108 : #define APPEND_CPU_COST_MULTIPLIER 0.5
109 :
110 :
111 : double seq_page_cost = DEFAULT_SEQ_PAGE_COST;
112 : double random_page_cost = DEFAULT_RANDOM_PAGE_COST;
113 : double cpu_tuple_cost = DEFAULT_CPU_TUPLE_COST;
114 : double cpu_index_tuple_cost = DEFAULT_CPU_INDEX_TUPLE_COST;
115 : double cpu_operator_cost = DEFAULT_CPU_OPERATOR_COST;
116 : double parallel_tuple_cost = DEFAULT_PARALLEL_TUPLE_COST;
117 : double parallel_setup_cost = DEFAULT_PARALLEL_SETUP_COST;
118 :
119 : int effective_cache_size = DEFAULT_EFFECTIVE_CACHE_SIZE;
120 :
121 : Cost disable_cost = 1.0e10;
122 :
123 : int max_parallel_workers_per_gather = 2;
124 :
125 : bool enable_seqscan = true;
126 : bool enable_indexscan = true;
127 : bool enable_indexonlyscan = true;
128 : bool enable_bitmapscan = true;
129 : bool enable_tidscan = true;
130 : bool enable_sort = true;
131 : bool enable_incrementalsort = true;
132 : bool enable_hashagg = true;
133 : bool enable_hashagg_disk = true;
134 : bool enable_groupingsets_hash_disk = false;
135 : bool enable_nestloop = true;
136 : bool enable_material = true;
137 : bool enable_mergejoin = true;
138 : bool enable_hashjoin = true;
139 : bool enable_gathermerge = true;
140 : bool enable_partitionwise_join = false;
141 : bool enable_partitionwise_aggregate = false;
142 : bool enable_parallel_append = true;
143 : bool enable_parallel_hash = true;
144 : bool enable_partition_pruning = true;
145 :
146 : typedef struct
147 : {
148 : PlannerInfo *root;
149 : QualCost total;
150 : } cost_qual_eval_context;
151 :
152 : static List *extract_nonindex_conditions(List *qual_clauses, List *indexclauses);
153 : static MergeScanSelCache *cached_scansel(PlannerInfo *root,
154 : RestrictInfo *rinfo,
155 : PathKey *pathkey);
156 : static void cost_rescan(PlannerInfo *root, Path *path,
157 : Cost *rescan_startup_cost, Cost *rescan_total_cost);
158 : static bool cost_qual_eval_walker(Node *node, cost_qual_eval_context *context);
159 : static void get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel,
160 : ParamPathInfo *param_info,
161 : QualCost *qpqual_cost);
162 : static bool has_indexed_join_quals(NestPath *joinpath);
163 : static double approx_tuple_count(PlannerInfo *root, JoinPath *path,
164 : List *quals);
165 : static double calc_joinrel_size_estimate(PlannerInfo *root,
166 : RelOptInfo *joinrel,
167 : RelOptInfo *outer_rel,
168 : RelOptInfo *inner_rel,
169 : double outer_rows,
170 : double inner_rows,
171 : SpecialJoinInfo *sjinfo,
172 : List *restrictlist);
173 : static Selectivity get_foreign_key_join_selectivity(PlannerInfo *root,
174 : Relids outer_relids,
175 : Relids inner_relids,
176 : SpecialJoinInfo *sjinfo,
177 : List **restrictlist);
178 : static Cost append_nonpartial_cost(List *subpaths, int numpaths,
179 : int parallel_workers);
180 : static void set_rel_width(PlannerInfo *root, RelOptInfo *rel);
181 : static double relation_byte_size(double tuples, int width);
182 : static double page_size(double tuples, int width);
183 : static double get_parallel_divisor(Path *path);
184 :
185 :
186 : /*
187 : * clamp_row_est
188 : * Force a row-count estimate to a sane value.
189 : */
190 : double
191 3538716 : clamp_row_est(double nrows)
192 : {
193 : /*
194 : * Force estimate to be at least one row, to make explain output look
195 : * better and to avoid possible divide-by-zero when interpolating costs.
196 : * Make it an integer, too.
197 : */
198 3538716 : if (nrows <= 1.0)
199 1432202 : nrows = 1.0;
200 : else
201 2106514 : nrows = rint(nrows);
202 :
203 3538716 : return nrows;
204 : }
205 :
206 :
207 : /*
208 : * cost_seqscan
209 : * Determines and returns the cost of scanning a relation sequentially.
210 : *
211 : * 'baserel' is the relation to be scanned
212 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
213 : */
214 : void
215 250632 : cost_seqscan(Path *path, PlannerInfo *root,
216 : RelOptInfo *baserel, ParamPathInfo *param_info)
217 : {
218 250632 : Cost startup_cost = 0;
219 : Cost cpu_run_cost;
220 : Cost disk_run_cost;
221 : double spc_seq_page_cost;
222 : QualCost qpqual_cost;
223 : Cost cpu_per_tuple;
224 :
225 : /* Should only be applied to base relations */
226 : Assert(baserel->relid > 0);
227 : Assert(baserel->rtekind == RTE_RELATION);
228 :
229 : /* Mark the path with the correct row estimate */
230 250632 : if (param_info)
231 356 : path->rows = param_info->ppi_rows;
232 : else
233 250276 : path->rows = baserel->rows;
234 :
235 250632 : if (!enable_seqscan)
236 7532 : startup_cost += disable_cost;
237 :
238 : /* fetch estimated page cost for tablespace containing table */
239 250632 : get_tablespace_page_costs(baserel->reltablespace,
240 : NULL,
241 : &spc_seq_page_cost);
242 :
243 : /*
244 : * disk costs
245 : */
246 250632 : disk_run_cost = spc_seq_page_cost * baserel->pages;
247 :
248 : /* CPU costs */
249 250632 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
250 :
251 250632 : startup_cost += qpqual_cost.startup;
252 250632 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
253 250632 : cpu_run_cost = cpu_per_tuple * baserel->tuples;
254 : /* tlist eval costs are paid per output row, not per tuple scanned */
255 250632 : startup_cost += path->pathtarget->cost.startup;
256 250632 : cpu_run_cost += path->pathtarget->cost.per_tuple * path->rows;
257 :
258 : /* Adjust costing for parallelism, if used. */
259 250632 : if (path->parallel_workers > 0)
260 : {
261 15698 : double parallel_divisor = get_parallel_divisor(path);
262 :
263 : /* The CPU cost is divided among all the workers. */
264 15698 : cpu_run_cost /= parallel_divisor;
265 :
266 : /*
267 : * It may be possible to amortize some of the I/O cost, but probably
268 : * not very much, because most operating systems already do aggressive
269 : * prefetching. For now, we assume that the disk run cost can't be
270 : * amortized at all.
271 : */
272 :
273 : /*
274 : * In the case of a parallel plan, the row count needs to represent
275 : * the number of tuples processed per worker.
276 : */
277 15698 : path->rows = clamp_row_est(path->rows / parallel_divisor);
278 : }
279 :
280 250632 : path->startup_cost = startup_cost;
281 250632 : path->total_cost = startup_cost + cpu_run_cost + disk_run_cost;
282 250632 : }
283 :
284 : /*
285 : * cost_samplescan
286 : * Determines and returns the cost of scanning a relation using sampling.
287 : *
288 : * 'baserel' is the relation to be scanned
289 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
290 : */
291 : void
292 180 : cost_samplescan(Path *path, PlannerInfo *root,
293 : RelOptInfo *baserel, ParamPathInfo *param_info)
294 : {
295 180 : Cost startup_cost = 0;
296 180 : Cost run_cost = 0;
297 : RangeTblEntry *rte;
298 : TableSampleClause *tsc;
299 : TsmRoutine *tsm;
300 : double spc_seq_page_cost,
301 : spc_random_page_cost,
302 : spc_page_cost;
303 : QualCost qpqual_cost;
304 : Cost cpu_per_tuple;
305 :
306 : /* Should only be applied to base relations with tablesample clauses */
307 : Assert(baserel->relid > 0);
308 180 : rte = planner_rt_fetch(baserel->relid, root);
309 : Assert(rte->rtekind == RTE_RELATION);
310 180 : tsc = rte->tablesample;
311 : Assert(tsc != NULL);
312 180 : tsm = GetTsmRoutine(tsc->tsmhandler);
313 :
314 : /* Mark the path with the correct row estimate */
315 180 : if (param_info)
316 12 : path->rows = param_info->ppi_rows;
317 : else
318 168 : path->rows = baserel->rows;
319 :
320 : /* fetch estimated page cost for tablespace containing table */
321 180 : get_tablespace_page_costs(baserel->reltablespace,
322 : &spc_random_page_cost,
323 : &spc_seq_page_cost);
324 :
325 : /* if NextSampleBlock is used, assume random access, else sequential */
326 360 : spc_page_cost = (tsm->NextSampleBlock != NULL) ?
327 180 : spc_random_page_cost : spc_seq_page_cost;
328 :
329 : /*
330 : * disk costs (recall that baserel->pages has already been set to the
331 : * number of pages the sampling method will visit)
332 : */
333 180 : run_cost += spc_page_cost * baserel->pages;
334 :
335 : /*
336 : * CPU costs (recall that baserel->tuples has already been set to the
337 : * number of tuples the sampling method will select). Note that we ignore
338 : * execution cost of the TABLESAMPLE parameter expressions; they will be
339 : * evaluated only once per scan, and in most usages they'll likely be
340 : * simple constants anyway. We also don't charge anything for the
341 : * calculations the sampling method might do internally.
342 : */
343 180 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
344 :
345 180 : startup_cost += qpqual_cost.startup;
346 180 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
347 180 : run_cost += cpu_per_tuple * baserel->tuples;
348 : /* tlist eval costs are paid per output row, not per tuple scanned */
349 180 : startup_cost += path->pathtarget->cost.startup;
350 180 : run_cost += path->pathtarget->cost.per_tuple * path->rows;
351 :
352 180 : path->startup_cost = startup_cost;
353 180 : path->total_cost = startup_cost + run_cost;
354 180 : }
355 :
356 : /*
357 : * cost_gather
358 : * Determines and returns the cost of gather path.
359 : *
360 : * 'rel' is the relation to be operated upon
361 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
362 : * 'rows' may be used to point to a row estimate; if non-NULL, it overrides
363 : * both 'rel' and 'param_info'. This is useful when the path doesn't exactly
364 : * correspond to any particular RelOptInfo.
365 : */
366 : void
367 10782 : cost_gather(GatherPath *path, PlannerInfo *root,
368 : RelOptInfo *rel, ParamPathInfo *param_info,
369 : double *rows)
370 : {
371 10782 : Cost startup_cost = 0;
372 10782 : Cost run_cost = 0;
373 :
374 : /* Mark the path with the correct row estimate */
375 10782 : if (rows)
376 966 : path->path.rows = *rows;
377 9816 : else if (param_info)
378 0 : path->path.rows = param_info->ppi_rows;
379 : else
380 9816 : path->path.rows = rel->rows;
381 :
382 10782 : startup_cost = path->subpath->startup_cost;
383 :
384 10782 : run_cost = path->subpath->total_cost - path->subpath->startup_cost;
385 :
386 : /* Parallel setup and communication cost. */
387 10782 : startup_cost += parallel_setup_cost;
388 10782 : run_cost += parallel_tuple_cost * path->path.rows;
389 :
390 10782 : path->path.startup_cost = startup_cost;
391 10782 : path->path.total_cost = (startup_cost + run_cost);
392 10782 : }
393 :
394 : /*
395 : * cost_gather_merge
396 : * Determines and returns the cost of gather merge path.
397 : *
398 : * GatherMerge merges several pre-sorted input streams, using a heap that at
399 : * any given instant holds the next tuple from each stream. If there are N
400 : * streams, we need about N*log2(N) tuple comparisons to construct the heap at
401 : * startup, and then for each output tuple, about log2(N) comparisons to
402 : * replace the top heap entry with the next tuple from the same stream.
403 : */
404 : void
405 3876 : cost_gather_merge(GatherMergePath *path, PlannerInfo *root,
406 : RelOptInfo *rel, ParamPathInfo *param_info,
407 : Cost input_startup_cost, Cost input_total_cost,
408 : double *rows)
409 : {
410 3876 : Cost startup_cost = 0;
411 3876 : Cost run_cost = 0;
412 : Cost comparison_cost;
413 : double N;
414 : double logN;
415 :
416 : /* Mark the path with the correct row estimate */
417 3876 : if (rows)
418 3330 : path->path.rows = *rows;
419 546 : else if (param_info)
420 0 : path->path.rows = param_info->ppi_rows;
421 : else
422 546 : path->path.rows = rel->rows;
423 :
424 3876 : if (!enable_gathermerge)
425 0 : startup_cost += disable_cost;
426 :
427 : /*
428 : * Add one to the number of workers to account for the leader. This might
429 : * be overgenerous since the leader will do less work than other workers
430 : * in typical cases, but we'll go with it for now.
431 : */
432 : Assert(path->num_workers > 0);
433 3876 : N = (double) path->num_workers + 1;
434 3876 : logN = LOG2(N);
435 :
436 : /* Assumed cost per tuple comparison */
437 3876 : comparison_cost = 2.0 * cpu_operator_cost;
438 :
439 : /* Heap creation cost */
440 3876 : startup_cost += comparison_cost * N * logN;
441 :
442 : /* Per-tuple heap maintenance cost */
443 3876 : run_cost += path->path.rows * comparison_cost * logN;
444 :
445 : /* small cost for heap management, like cost_merge_append */
446 3876 : run_cost += cpu_operator_cost * path->path.rows;
447 :
448 : /*
449 : * Parallel setup and communication cost. Since Gather Merge, unlike
450 : * Gather, requires us to block until a tuple is available from every
451 : * worker, we bump the IPC cost up a little bit as compared with Gather.
452 : * For lack of a better idea, charge an extra 5%.
453 : */
454 3876 : startup_cost += parallel_setup_cost;
455 3876 : run_cost += parallel_tuple_cost * path->path.rows * 1.05;
456 :
457 3876 : path->path.startup_cost = startup_cost + input_startup_cost;
458 3876 : path->path.total_cost = (startup_cost + run_cost + input_total_cost);
459 3876 : }
460 :
461 : /*
462 : * cost_index
463 : * Determines and returns the cost of scanning a relation using an index.
464 : *
465 : * 'path' describes the indexscan under consideration, and is complete
466 : * except for the fields to be set by this routine
467 : * 'loop_count' is the number of repetitions of the indexscan to factor into
468 : * estimates of caching behavior
469 : *
470 : * In addition to rows, startup_cost and total_cost, cost_index() sets the
471 : * path's indextotalcost and indexselectivity fields. These values will be
472 : * needed if the IndexPath is used in a BitmapIndexScan.
473 : *
474 : * NOTE: path->indexquals must contain only clauses usable as index
475 : * restrictions. Any additional quals evaluated as qpquals may reduce the
476 : * number of returned tuples, but they won't reduce the number of tuples
477 : * we have to fetch from the table, so they don't reduce the scan cost.
478 : */
479 : void
480 408156 : cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
481 : bool partial_path)
482 : {
483 408156 : IndexOptInfo *index = path->indexinfo;
484 408156 : RelOptInfo *baserel = index->rel;
485 408156 : bool indexonly = (path->path.pathtype == T_IndexOnlyScan);
486 : amcostestimate_function amcostestimate;
487 : List *qpquals;
488 408156 : Cost startup_cost = 0;
489 408156 : Cost run_cost = 0;
490 408156 : Cost cpu_run_cost = 0;
491 : Cost indexStartupCost;
492 : Cost indexTotalCost;
493 : Selectivity indexSelectivity;
494 : double indexCorrelation,
495 : csquared;
496 : double spc_seq_page_cost,
497 : spc_random_page_cost;
498 : Cost min_IO_cost,
499 : max_IO_cost;
500 : QualCost qpqual_cost;
501 : Cost cpu_per_tuple;
502 : double tuples_fetched;
503 : double pages_fetched;
504 : double rand_heap_pages;
505 : double index_pages;
506 :
507 : /* Should only be applied to base relations */
508 : Assert(IsA(baserel, RelOptInfo) &&
509 : IsA(index, IndexOptInfo));
510 : Assert(baserel->relid > 0);
511 : Assert(baserel->rtekind == RTE_RELATION);
512 :
513 : /*
514 : * Mark the path with the correct row estimate, and identify which quals
515 : * will need to be enforced as qpquals. We need not check any quals that
516 : * are implied by the index's predicate, so we can use indrestrictinfo not
517 : * baserestrictinfo as the list of relevant restriction clauses for the
518 : * rel.
519 : */
520 408156 : if (path->path.param_info)
521 : {
522 66508 : path->path.rows = path->path.param_info->ppi_rows;
523 : /* qpquals come from the rel's restriction clauses and ppi_clauses */
524 66508 : qpquals = list_concat(extract_nonindex_conditions(path->indexinfo->indrestrictinfo,
525 : path->indexclauses),
526 66508 : extract_nonindex_conditions(path->path.param_info->ppi_clauses,
527 : path->indexclauses));
528 : }
529 : else
530 : {
531 341648 : path->path.rows = baserel->rows;
532 : /* qpquals come from just the rel's restriction clauses */
533 341648 : qpquals = extract_nonindex_conditions(path->indexinfo->indrestrictinfo,
534 : path->indexclauses);
535 : }
536 :
537 408156 : if (!enable_indexscan)
538 2216 : startup_cost += disable_cost;
539 : /* we don't need to check enable_indexonlyscan; indxpath.c does that */
540 :
541 : /*
542 : * Call index-access-method-specific code to estimate the processing cost
543 : * for scanning the index, as well as the selectivity of the index (ie,
544 : * the fraction of main-table tuples we will have to retrieve) and its
545 : * correlation to the main-table tuple order. We need a cast here because
546 : * pathnodes.h uses a weak function type to avoid including amapi.h.
547 : */
548 408156 : amcostestimate = (amcostestimate_function) index->amcostestimate;
549 408156 : amcostestimate(root, path, loop_count,
550 : &indexStartupCost, &indexTotalCost,
551 : &indexSelectivity, &indexCorrelation,
552 : &index_pages);
553 :
554 : /*
555 : * Save amcostestimate's results for possible use in bitmap scan planning.
556 : * We don't bother to save indexStartupCost or indexCorrelation, because a
557 : * bitmap scan doesn't care about either.
558 : */
559 408156 : path->indextotalcost = indexTotalCost;
560 408156 : path->indexselectivity = indexSelectivity;
561 :
562 : /* all costs for touching index itself included here */
563 408156 : startup_cost += indexStartupCost;
564 408156 : run_cost += indexTotalCost - indexStartupCost;
565 :
566 : /* estimate number of main-table tuples fetched */
567 408156 : tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
568 :
569 : /* fetch estimated page costs for tablespace containing table */
570 408156 : get_tablespace_page_costs(baserel->reltablespace,
571 : &spc_random_page_cost,
572 : &spc_seq_page_cost);
573 :
574 : /*----------
575 : * Estimate number of main-table pages fetched, and compute I/O cost.
576 : *
577 : * When the index ordering is uncorrelated with the table ordering,
578 : * we use an approximation proposed by Mackert and Lohman (see
579 : * index_pages_fetched() for details) to compute the number of pages
580 : * fetched, and then charge spc_random_page_cost per page fetched.
581 : *
582 : * When the index ordering is exactly correlated with the table ordering
583 : * (just after a CLUSTER, for example), the number of pages fetched should
584 : * be exactly selectivity * table_size. What's more, all but the first
585 : * will be sequential fetches, not the random fetches that occur in the
586 : * uncorrelated case. So if the number of pages is more than 1, we
587 : * ought to charge
588 : * spc_random_page_cost + (pages_fetched - 1) * spc_seq_page_cost
589 : * For partially-correlated indexes, we ought to charge somewhere between
590 : * these two estimates. We currently interpolate linearly between the
591 : * estimates based on the correlation squared (XXX is that appropriate?).
592 : *
593 : * If it's an index-only scan, then we will not need to fetch any heap
594 : * pages for which the visibility map shows all tuples are visible.
595 : * Hence, reduce the estimated number of heap fetches accordingly.
596 : * We use the measured fraction of the entire heap that is all-visible,
597 : * which might not be particularly relevant to the subset of the heap
598 : * that this query will fetch; but it's not clear how to do better.
599 : *----------
600 : */
601 408156 : if (loop_count > 1)
602 : {
603 : /*
604 : * For repeated indexscans, the appropriate estimate for the
605 : * uncorrelated case is to scale up the number of tuples fetched in
606 : * the Mackert and Lohman formula by the number of scans, so that we
607 : * estimate the number of pages fetched by all the scans; then
608 : * pro-rate the costs for one scan. In this case we assume all the
609 : * fetches are random accesses.
610 : */
611 44988 : pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
612 : baserel->pages,
613 44988 : (double) index->pages,
614 : root);
615 :
616 44988 : if (indexonly)
617 5416 : pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
618 :
619 44988 : rand_heap_pages = pages_fetched;
620 :
621 44988 : max_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
622 :
623 : /*
624 : * In the perfectly correlated case, the number of pages touched by
625 : * each scan is selectivity * table_size, and we can use the Mackert
626 : * and Lohman formula at the page level to estimate how much work is
627 : * saved by caching across scans. We still assume all the fetches are
628 : * random, though, which is an overestimate that's hard to correct for
629 : * without double-counting the cache effects. (But in most cases
630 : * where such a plan is actually interesting, only one page would get
631 : * fetched per scan anyway, so it shouldn't matter much.)
632 : */
633 44988 : pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
634 :
635 44988 : pages_fetched = index_pages_fetched(pages_fetched * loop_count,
636 : baserel->pages,
637 44988 : (double) index->pages,
638 : root);
639 :
640 44988 : if (indexonly)
641 5416 : pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
642 :
643 44988 : min_IO_cost = (pages_fetched * spc_random_page_cost) / loop_count;
644 : }
645 : else
646 : {
647 : /*
648 : * Normal case: apply the Mackert and Lohman formula, and then
649 : * interpolate between that and the correlation-derived result.
650 : */
651 363168 : pages_fetched = index_pages_fetched(tuples_fetched,
652 : baserel->pages,
653 363168 : (double) index->pages,
654 : root);
655 :
656 363168 : if (indexonly)
657 29014 : pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
658 :
659 363168 : rand_heap_pages = pages_fetched;
660 :
661 : /* max_IO_cost is for the perfectly uncorrelated case (csquared=0) */
662 363168 : max_IO_cost = pages_fetched * spc_random_page_cost;
663 :
664 : /* min_IO_cost is for the perfectly correlated case (csquared=1) */
665 363168 : pages_fetched = ceil(indexSelectivity * (double) baserel->pages);
666 :
667 363168 : if (indexonly)
668 29014 : pages_fetched = ceil(pages_fetched * (1.0 - baserel->allvisfrac));
669 :
670 363168 : if (pages_fetched > 0)
671 : {
672 346326 : min_IO_cost = spc_random_page_cost;
673 346326 : if (pages_fetched > 1)
674 104440 : min_IO_cost += (pages_fetched - 1) * spc_seq_page_cost;
675 : }
676 : else
677 16842 : min_IO_cost = 0;
678 : }
679 :
680 408156 : if (partial_path)
681 : {
682 : /*
683 : * For index only scans compute workers based on number of index pages
684 : * fetched; the number of heap pages we fetch might be so small as to
685 : * effectively rule out parallelism, which we don't want to do.
686 : */
687 137482 : if (indexonly)
688 11142 : rand_heap_pages = -1;
689 :
690 : /*
691 : * Estimate the number of parallel workers required to scan index. Use
692 : * the number of heap pages computed considering heap fetches won't be
693 : * sequential as for parallel scans the pages are accessed in random
694 : * order.
695 : */
696 137482 : path->path.parallel_workers = compute_parallel_worker(baserel,
697 : rand_heap_pages,
698 : index_pages,
699 : max_parallel_workers_per_gather);
700 :
701 : /*
702 : * Fall out if workers can't be assigned for parallel scan, because in
703 : * such a case this path will be rejected. So there is no benefit in
704 : * doing extra computation.
705 : */
706 137482 : if (path->path.parallel_workers <= 0)
707 130676 : return;
708 :
709 6806 : path->path.parallel_aware = true;
710 : }
711 :
712 : /*
713 : * Now interpolate based on estimated index order correlation to get total
714 : * disk I/O cost for main table accesses.
715 : */
716 277480 : csquared = indexCorrelation * indexCorrelation;
717 :
718 277480 : run_cost += max_IO_cost + csquared * (min_IO_cost - max_IO_cost);
719 :
720 : /*
721 : * Estimate CPU costs per tuple.
722 : *
723 : * What we want here is cpu_tuple_cost plus the evaluation costs of any
724 : * qual clauses that we have to evaluate as qpquals.
725 : */
726 277480 : cost_qual_eval(&qpqual_cost, qpquals, root);
727 :
728 277480 : startup_cost += qpqual_cost.startup;
729 277480 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
730 :
731 277480 : cpu_run_cost += cpu_per_tuple * tuples_fetched;
732 :
733 : /* tlist eval costs are paid per output row, not per tuple scanned */
734 277480 : startup_cost += path->path.pathtarget->cost.startup;
735 277480 : cpu_run_cost += path->path.pathtarget->cost.per_tuple * path->path.rows;
736 :
737 : /* Adjust costing for parallelism, if used. */
738 277480 : if (path->path.parallel_workers > 0)
739 : {
740 6806 : double parallel_divisor = get_parallel_divisor(&path->path);
741 :
742 6806 : path->path.rows = clamp_row_est(path->path.rows / parallel_divisor);
743 :
744 : /* The CPU cost is divided among all the workers. */
745 6806 : cpu_run_cost /= parallel_divisor;
746 : }
747 :
748 277480 : run_cost += cpu_run_cost;
749 :
750 277480 : path->path.startup_cost = startup_cost;
751 277480 : path->path.total_cost = startup_cost + run_cost;
752 : }
753 :
754 : /*
755 : * extract_nonindex_conditions
756 : *
757 : * Given a list of quals to be enforced in an indexscan, extract the ones that
758 : * will have to be applied as qpquals (ie, the index machinery won't handle
759 : * them). Here we detect only whether a qual clause is directly redundant
760 : * with some indexclause. If the index path is chosen for use, createplan.c
761 : * will try a bit harder to get rid of redundant qual conditions; specifically
762 : * it will see if quals can be proven to be implied by the indexquals. But
763 : * it does not seem worth the cycles to try to factor that in at this stage,
764 : * since we're only trying to estimate qual eval costs. Otherwise this must
765 : * match the logic in create_indexscan_plan().
766 : *
767 : * qual_clauses, and the result, are lists of RestrictInfos.
768 : * indexclauses is a list of IndexClauses.
769 : */
770 : static List *
771 474664 : extract_nonindex_conditions(List *qual_clauses, List *indexclauses)
772 : {
773 474664 : List *result = NIL;
774 : ListCell *lc;
775 :
776 967212 : foreach(lc, qual_clauses)
777 : {
778 492548 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
779 :
780 492548 : if (rinfo->pseudoconstant)
781 1584 : continue; /* we may drop pseudoconstants here */
782 490964 : if (is_redundant_with_indexclauses(rinfo, indexclauses))
783 330392 : continue; /* dup or derived from same EquivalenceClass */
784 : /* ... skip the predicate proof attempt createplan.c will try ... */
785 160572 : result = lappend(result, rinfo);
786 : }
787 474664 : return result;
788 : }
789 :
790 : /*
791 : * index_pages_fetched
792 : * Estimate the number of pages actually fetched after accounting for
793 : * cache effects.
794 : *
795 : * We use an approximation proposed by Mackert and Lohman, "Index Scans
796 : * Using a Finite LRU Buffer: A Validated I/O Model", ACM Transactions
797 : * on Database Systems, Vol. 14, No. 3, September 1989, Pages 401-424.
798 : * The Mackert and Lohman approximation is that the number of pages
799 : * fetched is
800 : * PF =
801 : * min(2TNs/(2T+Ns), T) when T <= b
802 : * 2TNs/(2T+Ns) when T > b and Ns <= 2Tb/(2T-b)
803 : * b + (Ns - 2Tb/(2T-b))*(T-b)/T when T > b and Ns > 2Tb/(2T-b)
804 : * where
805 : * T = # pages in table
806 : * N = # tuples in table
807 : * s = selectivity = fraction of table to be scanned
808 : * b = # buffer pages available (we include kernel space here)
809 : *
810 : * We assume that effective_cache_size is the total number of buffer pages
811 : * available for the whole query, and pro-rate that space across all the
812 : * tables in the query and the index currently under consideration. (This
813 : * ignores space needed for other indexes used by the query, but since we
814 : * don't know which indexes will get used, we can't estimate that very well;
815 : * and in any case counting all the tables may well be an overestimate, since
816 : * depending on the join plan not all the tables may be scanned concurrently.)
817 : *
818 : * The product Ns is the number of tuples fetched; we pass in that
819 : * product rather than calculating it here. "pages" is the number of pages
820 : * in the object under consideration (either an index or a table).
821 : * "index_pages" is the amount to add to the total table space, which was
822 : * computed for us by make_one_rel.
823 : *
824 : * Caller is expected to have ensured that tuples_fetched is greater than zero
825 : * and rounded to integer (see clamp_row_est). The result will likewise be
826 : * greater than zero and integral.
827 : */
828 : double
829 576424 : index_pages_fetched(double tuples_fetched, BlockNumber pages,
830 : double index_pages, PlannerInfo *root)
831 : {
832 : double pages_fetched;
833 : double total_pages;
834 : double T,
835 : b;
836 :
837 : /* T is # pages in table, but don't allow it to be zero */
838 576424 : T = (pages > 1) ? (double) pages : 1.0;
839 :
840 : /* Compute number of pages assumed to be competing for cache space */
841 576424 : total_pages = root->total_table_pages + index_pages;
842 576424 : total_pages = Max(total_pages, 1.0);
843 : Assert(T <= total_pages);
844 :
845 : /* b is pro-rated share of effective_cache_size */
846 576424 : b = (double) effective_cache_size * T / total_pages;
847 :
848 : /* force it positive and integral */
849 576424 : if (b <= 1.0)
850 0 : b = 1.0;
851 : else
852 576424 : b = ceil(b);
853 :
854 : /* This part is the Mackert and Lohman formula */
855 576424 : if (T <= b)
856 : {
857 576424 : pages_fetched =
858 576424 : (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);
859 576424 : if (pages_fetched >= T)
860 294524 : pages_fetched = T;
861 : else
862 281900 : pages_fetched = ceil(pages_fetched);
863 : }
864 : else
865 : {
866 : double lim;
867 :
868 0 : lim = (2.0 * T * b) / (2.0 * T - b);
869 0 : if (tuples_fetched <= lim)
870 : {
871 0 : pages_fetched =
872 0 : (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);
873 : }
874 : else
875 : {
876 0 : pages_fetched =
877 0 : b + (tuples_fetched - lim) * (T - b) / T;
878 : }
879 0 : pages_fetched = ceil(pages_fetched);
880 : }
881 576424 : return pages_fetched;
882 : }
883 :
884 : /*
885 : * get_indexpath_pages
886 : * Determine the total size of the indexes used in a bitmap index path.
887 : *
888 : * Note: if the same index is used more than once in a bitmap tree, we will
889 : * count it multiple times, which perhaps is the wrong thing ... but it's
890 : * not completely clear, and detecting duplicates is difficult, so ignore it
891 : * for now.
892 : */
893 : static double
894 84310 : get_indexpath_pages(Path *bitmapqual)
895 : {
896 84310 : double result = 0;
897 : ListCell *l;
898 :
899 84310 : if (IsA(bitmapqual, BitmapAndPath))
900 : {
901 7306 : BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
902 :
903 21918 : foreach(l, apath->bitmapquals)
904 : {
905 14612 : result += get_indexpath_pages((Path *) lfirst(l));
906 : }
907 : }
908 77004 : else if (IsA(bitmapqual, BitmapOrPath))
909 : {
910 10 : BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
911 :
912 30 : foreach(l, opath->bitmapquals)
913 : {
914 20 : result += get_indexpath_pages((Path *) lfirst(l));
915 : }
916 : }
917 76994 : else if (IsA(bitmapqual, IndexPath))
918 : {
919 76994 : IndexPath *ipath = (IndexPath *) bitmapqual;
920 :
921 76994 : result = (double) ipath->indexinfo->pages;
922 : }
923 : else
924 0 : elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
925 :
926 84310 : return result;
927 : }
928 :
929 : /*
930 : * cost_bitmap_heap_scan
931 : * Determines and returns the cost of scanning a relation using a bitmap
932 : * index-then-heap plan.
933 : *
934 : * 'baserel' is the relation to be scanned
935 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
936 : * 'bitmapqual' is a tree of IndexPaths, BitmapAndPaths, and BitmapOrPaths
937 : * 'loop_count' is the number of repetitions of the indexscan to factor into
938 : * estimates of caching behavior
939 : *
940 : * Note: the component IndexPaths in bitmapqual should have been costed
941 : * using the same loop_count.
942 : */
943 : void
944 274658 : cost_bitmap_heap_scan(Path *path, PlannerInfo *root, RelOptInfo *baserel,
945 : ParamPathInfo *param_info,
946 : Path *bitmapqual, double loop_count)
947 : {
948 274658 : Cost startup_cost = 0;
949 274658 : Cost run_cost = 0;
950 : Cost indexTotalCost;
951 : QualCost qpqual_cost;
952 : Cost cpu_per_tuple;
953 : Cost cost_per_page;
954 : Cost cpu_run_cost;
955 : double tuples_fetched;
956 : double pages_fetched;
957 : double spc_seq_page_cost,
958 : spc_random_page_cost;
959 : double T;
960 :
961 : /* Should only be applied to base relations */
962 : Assert(IsA(baserel, RelOptInfo));
963 : Assert(baserel->relid > 0);
964 : Assert(baserel->rtekind == RTE_RELATION);
965 :
966 : /* Mark the path with the correct row estimate */
967 274658 : if (param_info)
968 93792 : path->rows = param_info->ppi_rows;
969 : else
970 180866 : path->rows = baserel->rows;
971 :
972 274658 : if (!enable_bitmapscan)
973 4004 : startup_cost += disable_cost;
974 :
975 274658 : pages_fetched = compute_bitmap_pages(root, baserel, bitmapqual,
976 : loop_count, &indexTotalCost,
977 : &tuples_fetched);
978 :
979 274658 : startup_cost += indexTotalCost;
980 274658 : T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
981 :
982 : /* Fetch estimated page costs for tablespace containing table. */
983 274658 : get_tablespace_page_costs(baserel->reltablespace,
984 : &spc_random_page_cost,
985 : &spc_seq_page_cost);
986 :
987 : /*
988 : * For small numbers of pages we should charge spc_random_page_cost
989 : * apiece, while if nearly all the table's pages are being read, it's more
990 : * appropriate to charge spc_seq_page_cost apiece. The effect is
991 : * nonlinear, too. For lack of a better idea, interpolate like this to
992 : * determine the cost per page.
993 : */
994 274658 : if (pages_fetched >= 2.0)
995 161716 : cost_per_page = spc_random_page_cost -
996 80858 : (spc_random_page_cost - spc_seq_page_cost)
997 80858 : * sqrt(pages_fetched / T);
998 : else
999 193800 : cost_per_page = spc_random_page_cost;
1000 :
1001 274658 : run_cost += pages_fetched * cost_per_page;
1002 :
1003 : /*
1004 : * Estimate CPU costs per tuple.
1005 : *
1006 : * Often the indexquals don't need to be rechecked at each tuple ... but
1007 : * not always, especially not if there are enough tuples involved that the
1008 : * bitmaps become lossy. For the moment, just assume they will be
1009 : * rechecked always. This means we charge the full freight for all the
1010 : * scan clauses.
1011 : */
1012 274658 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1013 :
1014 274658 : startup_cost += qpqual_cost.startup;
1015 274658 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1016 274658 : cpu_run_cost = cpu_per_tuple * tuples_fetched;
1017 :
1018 : /* Adjust costing for parallelism, if used. */
1019 274658 : if (path->parallel_workers > 0)
1020 : {
1021 3324 : double parallel_divisor = get_parallel_divisor(path);
1022 :
1023 : /* The CPU cost is divided among all the workers. */
1024 3324 : cpu_run_cost /= parallel_divisor;
1025 :
1026 3324 : path->rows = clamp_row_est(path->rows / parallel_divisor);
1027 : }
1028 :
1029 :
1030 274658 : run_cost += cpu_run_cost;
1031 :
1032 : /* tlist eval costs are paid per output row, not per tuple scanned */
1033 274658 : startup_cost += path->pathtarget->cost.startup;
1034 274658 : run_cost += path->pathtarget->cost.per_tuple * path->rows;
1035 :
1036 274658 : path->startup_cost = startup_cost;
1037 274658 : path->total_cost = startup_cost + run_cost;
1038 274658 : }
1039 :
1040 : /*
1041 : * cost_bitmap_tree_node
1042 : * Extract cost and selectivity from a bitmap tree node (index/and/or)
1043 : */
1044 : void
1045 472082 : cost_bitmap_tree_node(Path *path, Cost *cost, Selectivity *selec)
1046 : {
1047 472082 : if (IsA(path, IndexPath))
1048 : {
1049 457682 : *cost = ((IndexPath *) path)->indextotalcost;
1050 457682 : *selec = ((IndexPath *) path)->indexselectivity;
1051 :
1052 : /*
1053 : * Charge a small amount per retrieved tuple to reflect the costs of
1054 : * manipulating the bitmap. This is mostly to make sure that a bitmap
1055 : * scan doesn't look to be the same cost as an indexscan to retrieve a
1056 : * single tuple.
1057 : */
1058 457682 : *cost += 0.1 * cpu_operator_cost * path->rows;
1059 : }
1060 14400 : else if (IsA(path, BitmapAndPath))
1061 : {
1062 13168 : *cost = path->total_cost;
1063 13168 : *selec = ((BitmapAndPath *) path)->bitmapselectivity;
1064 : }
1065 1232 : else if (IsA(path, BitmapOrPath))
1066 : {
1067 1232 : *cost = path->total_cost;
1068 1232 : *selec = ((BitmapOrPath *) path)->bitmapselectivity;
1069 : }
1070 : else
1071 : {
1072 0 : elog(ERROR, "unrecognized node type: %d", nodeTag(path));
1073 : *cost = *selec = 0; /* keep compiler quiet */
1074 : }
1075 472082 : }
1076 :
1077 : /*
1078 : * cost_bitmap_and_node
1079 : * Estimate the cost of a BitmapAnd node
1080 : *
1081 : * Note that this considers only the costs of index scanning and bitmap
1082 : * creation, not the eventual heap access. In that sense the object isn't
1083 : * truly a Path, but it has enough path-like properties (costs in particular)
1084 : * to warrant treating it as one. We don't bother to set the path rows field,
1085 : * however.
1086 : */
1087 : void
1088 13124 : cost_bitmap_and_node(BitmapAndPath *path, PlannerInfo *root)
1089 : {
1090 : Cost totalCost;
1091 : Selectivity selec;
1092 : ListCell *l;
1093 :
1094 : /*
1095 : * We estimate AND selectivity on the assumption that the inputs are
1096 : * independent. This is probably often wrong, but we don't have the info
1097 : * to do better.
1098 : *
1099 : * The runtime cost of the BitmapAnd itself is estimated at 100x
1100 : * cpu_operator_cost for each tbm_intersect needed. Probably too small,
1101 : * definitely too simplistic?
1102 : */
1103 13124 : totalCost = 0.0;
1104 13124 : selec = 1.0;
1105 39372 : foreach(l, path->bitmapquals)
1106 : {
1107 26248 : Path *subpath = (Path *) lfirst(l);
1108 : Cost subCost;
1109 : Selectivity subselec;
1110 :
1111 26248 : cost_bitmap_tree_node(subpath, &subCost, &subselec);
1112 :
1113 26248 : selec *= subselec;
1114 :
1115 26248 : totalCost += subCost;
1116 26248 : if (l != list_head(path->bitmapquals))
1117 13124 : totalCost += 100.0 * cpu_operator_cost;
1118 : }
1119 13124 : path->bitmapselectivity = selec;
1120 13124 : path->path.rows = 0; /* per above, not used */
1121 13124 : path->path.startup_cost = totalCost;
1122 13124 : path->path.total_cost = totalCost;
1123 13124 : }
1124 :
1125 : /*
1126 : * cost_bitmap_or_node
1127 : * Estimate the cost of a BitmapOr node
1128 : *
1129 : * See comments for cost_bitmap_and_node.
1130 : */
1131 : void
1132 370 : cost_bitmap_or_node(BitmapOrPath *path, PlannerInfo *root)
1133 : {
1134 : Cost totalCost;
1135 : Selectivity selec;
1136 : ListCell *l;
1137 :
1138 : /*
1139 : * We estimate OR selectivity on the assumption that the inputs are
1140 : * non-overlapping, since that's often the case in "x IN (list)" type
1141 : * situations. Of course, we clamp to 1.0 at the end.
1142 : *
1143 : * The runtime cost of the BitmapOr itself is estimated at 100x
1144 : * cpu_operator_cost for each tbm_union needed. Probably too small,
1145 : * definitely too simplistic? We are aware that the tbm_unions are
1146 : * optimized out when the inputs are BitmapIndexScans.
1147 : */
1148 370 : totalCost = 0.0;
1149 370 : selec = 0.0;
1150 1150 : foreach(l, path->bitmapquals)
1151 : {
1152 780 : Path *subpath = (Path *) lfirst(l);
1153 : Cost subCost;
1154 : Selectivity subselec;
1155 :
1156 780 : cost_bitmap_tree_node(subpath, &subCost, &subselec);
1157 :
1158 780 : selec += subselec;
1159 :
1160 780 : totalCost += subCost;
1161 780 : if (l != list_head(path->bitmapquals) &&
1162 410 : !IsA(subpath, IndexPath))
1163 20 : totalCost += 100.0 * cpu_operator_cost;
1164 : }
1165 370 : path->bitmapselectivity = Min(selec, 1.0);
1166 370 : path->path.rows = 0; /* per above, not used */
1167 370 : path->path.startup_cost = totalCost;
1168 370 : path->path.total_cost = totalCost;
1169 370 : }
1170 :
1171 : /*
1172 : * cost_tidscan
1173 : * Determines and returns the cost of scanning a relation using TIDs.
1174 : *
1175 : * 'baserel' is the relation to be scanned
1176 : * 'tidquals' is the list of TID-checkable quals
1177 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
1178 : */
1179 : void
1180 616 : cost_tidscan(Path *path, PlannerInfo *root,
1181 : RelOptInfo *baserel, List *tidquals, ParamPathInfo *param_info)
1182 : {
1183 616 : Cost startup_cost = 0;
1184 616 : Cost run_cost = 0;
1185 616 : bool isCurrentOf = false;
1186 : QualCost qpqual_cost;
1187 : Cost cpu_per_tuple;
1188 : QualCost tid_qual_cost;
1189 : int ntuples;
1190 : ListCell *l;
1191 : double spc_random_page_cost;
1192 :
1193 : /* Should only be applied to base relations */
1194 : Assert(baserel->relid > 0);
1195 : Assert(baserel->rtekind == RTE_RELATION);
1196 :
1197 : /* Mark the path with the correct row estimate */
1198 616 : if (param_info)
1199 78 : path->rows = param_info->ppi_rows;
1200 : else
1201 538 : path->rows = baserel->rows;
1202 :
1203 : /* Count how many tuples we expect to retrieve */
1204 616 : ntuples = 0;
1205 1248 : foreach(l, tidquals)
1206 : {
1207 632 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
1208 632 : Expr *qual = rinfo->clause;
1209 :
1210 632 : if (IsA(qual, ScalarArrayOpExpr))
1211 : {
1212 : /* Each element of the array yields 1 tuple */
1213 20 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) qual;
1214 20 : Node *arraynode = (Node *) lsecond(saop->args);
1215 :
1216 20 : ntuples += estimate_array_length(arraynode);
1217 : }
1218 612 : else if (IsA(qual, CurrentOfExpr))
1219 : {
1220 : /* CURRENT OF yields 1 tuple */
1221 380 : isCurrentOf = true;
1222 380 : ntuples++;
1223 : }
1224 : else
1225 : {
1226 : /* It's just CTID = something, count 1 tuple */
1227 232 : ntuples++;
1228 : }
1229 : }
1230 :
1231 : /*
1232 : * We must force TID scan for WHERE CURRENT OF, because only nodeTidscan.c
1233 : * understands how to do it correctly. Therefore, honor enable_tidscan
1234 : * only when CURRENT OF isn't present. Also note that cost_qual_eval
1235 : * counts a CurrentOfExpr as having startup cost disable_cost, which we
1236 : * subtract off here; that's to prevent other plan types such as seqscan
1237 : * from winning.
1238 : */
1239 616 : if (isCurrentOf)
1240 : {
1241 : Assert(baserel->baserestrictcost.startup >= disable_cost);
1242 380 : startup_cost -= disable_cost;
1243 : }
1244 236 : else if (!enable_tidscan)
1245 0 : startup_cost += disable_cost;
1246 :
1247 : /*
1248 : * The TID qual expressions will be computed once, any other baserestrict
1249 : * quals once per retrieved tuple.
1250 : */
1251 616 : cost_qual_eval(&tid_qual_cost, tidquals, root);
1252 :
1253 : /* fetch estimated page cost for tablespace containing table */
1254 616 : get_tablespace_page_costs(baserel->reltablespace,
1255 : &spc_random_page_cost,
1256 : NULL);
1257 :
1258 : /* disk costs --- assume each tuple on a different page */
1259 616 : run_cost += spc_random_page_cost * ntuples;
1260 :
1261 : /* Add scanning CPU costs */
1262 616 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1263 :
1264 : /* XXX currently we assume TID quals are a subset of qpquals */
1265 616 : startup_cost += qpqual_cost.startup + tid_qual_cost.per_tuple;
1266 1232 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple -
1267 616 : tid_qual_cost.per_tuple;
1268 616 : run_cost += cpu_per_tuple * ntuples;
1269 :
1270 : /* tlist eval costs are paid per output row, not per tuple scanned */
1271 616 : startup_cost += path->pathtarget->cost.startup;
1272 616 : run_cost += path->pathtarget->cost.per_tuple * path->rows;
1273 :
1274 616 : path->startup_cost = startup_cost;
1275 616 : path->total_cost = startup_cost + run_cost;
1276 616 : }
1277 :
1278 : /*
1279 : * cost_subqueryscan
1280 : * Determines and returns the cost of scanning a subquery RTE.
1281 : *
1282 : * 'baserel' is the relation to be scanned
1283 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
1284 : */
1285 : void
1286 9498 : cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root,
1287 : RelOptInfo *baserel, ParamPathInfo *param_info)
1288 : {
1289 : Cost startup_cost;
1290 : Cost run_cost;
1291 : QualCost qpqual_cost;
1292 : Cost cpu_per_tuple;
1293 :
1294 : /* Should only be applied to base relations that are subqueries */
1295 : Assert(baserel->relid > 0);
1296 : Assert(baserel->rtekind == RTE_SUBQUERY);
1297 :
1298 : /* Mark the path with the correct row estimate */
1299 9498 : if (param_info)
1300 256 : path->path.rows = param_info->ppi_rows;
1301 : else
1302 9242 : path->path.rows = baserel->rows;
1303 :
1304 : /*
1305 : * Cost of path is cost of evaluating the subplan, plus cost of evaluating
1306 : * any restriction clauses and tlist that will be attached to the
1307 : * SubqueryScan node, plus cpu_tuple_cost to account for selection and
1308 : * projection overhead.
1309 : */
1310 9498 : path->path.startup_cost = path->subpath->startup_cost;
1311 9498 : path->path.total_cost = path->subpath->total_cost;
1312 :
1313 9498 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1314 :
1315 9498 : startup_cost = qpqual_cost.startup;
1316 9498 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1317 9498 : run_cost = cpu_per_tuple * baserel->tuples;
1318 :
1319 : /* tlist eval costs are paid per output row, not per tuple scanned */
1320 9498 : startup_cost += path->path.pathtarget->cost.startup;
1321 9498 : run_cost += path->path.pathtarget->cost.per_tuple * path->path.rows;
1322 :
1323 9498 : path->path.startup_cost += startup_cost;
1324 9498 : path->path.total_cost += startup_cost + run_cost;
1325 9498 : }
1326 :
1327 : /*
1328 : * cost_functionscan
1329 : * Determines and returns the cost of scanning a function RTE.
1330 : *
1331 : * 'baserel' is the relation to be scanned
1332 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
1333 : */
1334 : void
1335 30506 : cost_functionscan(Path *path, PlannerInfo *root,
1336 : RelOptInfo *baserel, ParamPathInfo *param_info)
1337 : {
1338 30506 : Cost startup_cost = 0;
1339 30506 : Cost run_cost = 0;
1340 : QualCost qpqual_cost;
1341 : Cost cpu_per_tuple;
1342 : RangeTblEntry *rte;
1343 : QualCost exprcost;
1344 :
1345 : /* Should only be applied to base relations that are functions */
1346 : Assert(baserel->relid > 0);
1347 30506 : rte = planner_rt_fetch(baserel->relid, root);
1348 : Assert(rte->rtekind == RTE_FUNCTION);
1349 :
1350 : /* Mark the path with the correct row estimate */
1351 30506 : if (param_info)
1352 366 : path->rows = param_info->ppi_rows;
1353 : else
1354 30140 : path->rows = baserel->rows;
1355 :
1356 : /*
1357 : * Estimate costs of executing the function expression(s).
1358 : *
1359 : * Currently, nodeFunctionscan.c always executes the functions to
1360 : * completion before returning any rows, and caches the results in a
1361 : * tuplestore. So the function eval cost is all startup cost, and per-row
1362 : * costs are minimal.
1363 : *
1364 : * XXX in principle we ought to charge tuplestore spill costs if the
1365 : * number of rows is large. However, given how phony our rowcount
1366 : * estimates for functions tend to be, there's not a lot of point in that
1367 : * refinement right now.
1368 : */
1369 30506 : cost_qual_eval_node(&exprcost, (Node *) rte->functions, root);
1370 :
1371 30506 : startup_cost += exprcost.startup + exprcost.per_tuple;
1372 :
1373 : /* Add scanning CPU costs */
1374 30506 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1375 :
1376 30506 : startup_cost += qpqual_cost.startup;
1377 30506 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1378 30506 : run_cost += cpu_per_tuple * baserel->tuples;
1379 :
1380 : /* tlist eval costs are paid per output row, not per tuple scanned */
1381 30506 : startup_cost += path->pathtarget->cost.startup;
1382 30506 : run_cost += path->pathtarget->cost.per_tuple * path->rows;
1383 :
1384 30506 : path->startup_cost = startup_cost;
1385 30506 : path->total_cost = startup_cost + run_cost;
1386 30506 : }
1387 :
1388 : /*
1389 : * cost_tablefuncscan
1390 : * Determines and returns the cost of scanning a table function.
1391 : *
1392 : * 'baserel' is the relation to be scanned
1393 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
1394 : */
1395 : void
1396 144 : cost_tablefuncscan(Path *path, PlannerInfo *root,
1397 : RelOptInfo *baserel, ParamPathInfo *param_info)
1398 : {
1399 144 : Cost startup_cost = 0;
1400 144 : Cost run_cost = 0;
1401 : QualCost qpqual_cost;
1402 : Cost cpu_per_tuple;
1403 : RangeTblEntry *rte;
1404 : QualCost exprcost;
1405 :
1406 : /* Should only be applied to base relations that are functions */
1407 : Assert(baserel->relid > 0);
1408 144 : rte = planner_rt_fetch(baserel->relid, root);
1409 : Assert(rte->rtekind == RTE_TABLEFUNC);
1410 :
1411 : /* Mark the path with the correct row estimate */
1412 144 : if (param_info)
1413 96 : path->rows = param_info->ppi_rows;
1414 : else
1415 48 : path->rows = baserel->rows;
1416 :
1417 : /*
1418 : * Estimate costs of executing the table func expression(s).
1419 : *
1420 : * XXX in principle we ought to charge tuplestore spill costs if the
1421 : * number of rows is large. However, given how phony our rowcount
1422 : * estimates for tablefuncs tend to be, there's not a lot of point in that
1423 : * refinement right now.
1424 : */
1425 144 : cost_qual_eval_node(&exprcost, (Node *) rte->tablefunc, root);
1426 :
1427 144 : startup_cost += exprcost.startup + exprcost.per_tuple;
1428 :
1429 : /* Add scanning CPU costs */
1430 144 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1431 :
1432 144 : startup_cost += qpqual_cost.startup;
1433 144 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1434 144 : run_cost += cpu_per_tuple * baserel->tuples;
1435 :
1436 : /* tlist eval costs are paid per output row, not per tuple scanned */
1437 144 : startup_cost += path->pathtarget->cost.startup;
1438 144 : run_cost += path->pathtarget->cost.per_tuple * path->rows;
1439 :
1440 144 : path->startup_cost = startup_cost;
1441 144 : path->total_cost = startup_cost + run_cost;
1442 144 : }
1443 :
1444 : /*
1445 : * cost_valuesscan
1446 : * Determines and returns the cost of scanning a VALUES RTE.
1447 : *
1448 : * 'baserel' is the relation to be scanned
1449 : * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
1450 : */
1451 : void
1452 3950 : cost_valuesscan(Path *path, PlannerInfo *root,
1453 : RelOptInfo *baserel, ParamPathInfo *param_info)
1454 : {
1455 3950 : Cost startup_cost = 0;
1456 3950 : Cost run_cost = 0;
1457 : QualCost qpqual_cost;
1458 : Cost cpu_per_tuple;
1459 :
1460 : /* Should only be applied to base relations that are values lists */
1461 : Assert(baserel->relid > 0);
1462 : Assert(baserel->rtekind == RTE_VALUES);
1463 :
1464 : /* Mark the path with the correct row estimate */
1465 3950 : if (param_info)
1466 28 : path->rows = param_info->ppi_rows;
1467 : else
1468 3922 : path->rows = baserel->rows;
1469 :
1470 : /*
1471 : * For now, estimate list evaluation cost at one operator eval per list
1472 : * (probably pretty bogus, but is it worth being smarter?)
1473 : */
1474 3950 : cpu_per_tuple = cpu_operator_cost;
1475 :
1476 : /* Add scanning CPU costs */
1477 3950 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1478 :
1479 3950 : startup_cost += qpqual_cost.startup;
1480 3950 : cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1481 3950 : run_cost += cpu_per_tuple * baserel->tuples;
1482 :
1483 : /* tlist eval costs are paid per output row, not per tuple scanned */
1484 3950 : startup_cost += path->pathtarget->cost.startup;
1485 3950 : run_cost += path->pathtarget->cost.per_tuple * path->rows;
1486 :
1487 3950 : path->startup_cost = startup_cost;
1488 3950 : path->total_cost = startup_cost + run_cost;
1489 3950 : }
1490 :
1491 : /*
1492 : * cost_ctescan
1493 : * Determines and returns the cost of scanning a CTE RTE.
1494 : *
1495 : * Note: this is used for both self-reference and regular CTEs; the
1496 : * possible cost differences are below the threshold of what we could
1497 : * estimate accurately anyway. Note that the costs of evaluating the
1498 : * referenced CTE query are added into the final plan as initplan costs,
1499 : * and should NOT be counted here.
1500 : */
1501 : void
1502 1244 : cost_ctescan(Path *path, PlannerInfo *root,
1503 : RelOptInfo *baserel, ParamPathInfo *param_info)
1504 : {
1505 1244 : Cost startup_cost = 0;
1506 1244 : Cost run_cost = 0;
1507 : QualCost qpqual_cost;
1508 : Cost cpu_per_tuple;
1509 :
1510 : /* Should only be applied to base relations that are CTEs */
1511 : Assert(baserel->relid > 0);
1512 : Assert(baserel->rtekind == RTE_CTE);
1513 :
1514 : /* Mark the path with the correct row estimate */
1515 1244 : if (param_info)
1516 0 : path->rows = param_info->ppi_rows;
1517 : else
1518 1244 : path->rows = baserel->rows;
1519 :
1520 : /* Charge one CPU tuple cost per row for tuplestore manipulation */
1521 1244 : cpu_per_tuple = cpu_tuple_cost;
1522 :
1523 : /* Add scanning CPU costs */
1524 1244 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1525 :
1526 1244 : startup_cost += qpqual_cost.startup;
1527 1244 : cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1528 1244 : run_cost += cpu_per_tuple * baserel->tuples;
1529 :
1530 : /* tlist eval costs are paid per output row, not per tuple scanned */
1531 1244 : startup_cost += path->pathtarget->cost.startup;
1532 1244 : run_cost += path->pathtarget->cost.per_tuple * path->rows;
1533 :
1534 1244 : path->startup_cost = startup_cost;
1535 1244 : path->total_cost = startup_cost + run_cost;
1536 1244 : }
1537 :
1538 : /*
1539 : * cost_namedtuplestorescan
1540 : * Determines and returns the cost of scanning a named tuplestore.
1541 : */
1542 : void
1543 260 : cost_namedtuplestorescan(Path *path, PlannerInfo *root,
1544 : RelOptInfo *baserel, ParamPathInfo *param_info)
1545 : {
1546 260 : Cost startup_cost = 0;
1547 260 : Cost run_cost = 0;
1548 : QualCost qpqual_cost;
1549 : Cost cpu_per_tuple;
1550 :
1551 : /* Should only be applied to base relations that are Tuplestores */
1552 : Assert(baserel->relid > 0);
1553 : Assert(baserel->rtekind == RTE_NAMEDTUPLESTORE);
1554 :
1555 : /* Mark the path with the correct row estimate */
1556 260 : if (param_info)
1557 0 : path->rows = param_info->ppi_rows;
1558 : else
1559 260 : path->rows = baserel->rows;
1560 :
1561 : /* Charge one CPU tuple cost per row for tuplestore manipulation */
1562 260 : cpu_per_tuple = cpu_tuple_cost;
1563 :
1564 : /* Add scanning CPU costs */
1565 260 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1566 :
1567 260 : startup_cost += qpqual_cost.startup;
1568 260 : cpu_per_tuple += cpu_tuple_cost + qpqual_cost.per_tuple;
1569 260 : run_cost += cpu_per_tuple * baserel->tuples;
1570 :
1571 260 : path->startup_cost = startup_cost;
1572 260 : path->total_cost = startup_cost + run_cost;
1573 260 : }
1574 :
1575 : /*
1576 : * cost_resultscan
1577 : * Determines and returns the cost of scanning an RTE_RESULT relation.
1578 : */
1579 : void
1580 702 : cost_resultscan(Path *path, PlannerInfo *root,
1581 : RelOptInfo *baserel, ParamPathInfo *param_info)
1582 : {
1583 702 : Cost startup_cost = 0;
1584 702 : Cost run_cost = 0;
1585 : QualCost qpqual_cost;
1586 : Cost cpu_per_tuple;
1587 :
1588 : /* Should only be applied to RTE_RESULT base relations */
1589 : Assert(baserel->relid > 0);
1590 : Assert(baserel->rtekind == RTE_RESULT);
1591 :
1592 : /* Mark the path with the correct row estimate */
1593 702 : if (param_info)
1594 60 : path->rows = param_info->ppi_rows;
1595 : else
1596 642 : path->rows = baserel->rows;
1597 :
1598 : /* We charge qual cost plus cpu_tuple_cost */
1599 702 : get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);
1600 :
1601 702 : startup_cost += qpqual_cost.startup;
1602 702 : cpu_per_tuple = cpu_tuple_cost + qpqual_cost.per_tuple;
1603 702 : run_cost += cpu_per_tuple * baserel->tuples;
1604 :
1605 702 : path->startup_cost = startup_cost;
1606 702 : path->total_cost = startup_cost + run_cost;
1607 702 : }
1608 :
1609 : /*
1610 : * cost_recursive_union
1611 : * Determines and returns the cost of performing a recursive union,
1612 : * and also the estimated output size.
1613 : *
1614 : * We are given Paths for the nonrecursive and recursive terms.
1615 : */
1616 : void
1617 332 : cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
1618 : {
1619 : Cost startup_cost;
1620 : Cost total_cost;
1621 : double total_rows;
1622 :
1623 : /* We probably have decent estimates for the non-recursive term */
1624 332 : startup_cost = nrterm->startup_cost;
1625 332 : total_cost = nrterm->total_cost;
1626 332 : total_rows = nrterm->rows;
1627 :
1628 : /*
1629 : * We arbitrarily assume that about 10 recursive iterations will be
1630 : * needed, and that we've managed to get a good fix on the cost and output
1631 : * size of each one of them. These are mighty shaky assumptions but it's
1632 : * hard to see how to do better.
1633 : */
1634 332 : total_cost += 10 * rterm->total_cost;
1635 332 : total_rows += 10 * rterm->rows;
1636 :
1637 : /*
1638 : * Also charge cpu_tuple_cost per row to account for the costs of
1639 : * manipulating the tuplestores. (We don't worry about possible
1640 : * spill-to-disk costs.)
1641 : */
1642 332 : total_cost += cpu_tuple_cost * total_rows;
1643 :
1644 332 : runion->startup_cost = startup_cost;
1645 332 : runion->total_cost = total_cost;
1646 332 : runion->rows = total_rows;
1647 332 : runion->pathtarget->width = Max(nrterm->pathtarget->width,
1648 : rterm->pathtarget->width);
1649 332 : }
1650 :
1651 : /*
1652 : * cost_tuplesort
1653 : * Determines and returns the cost of sorting a relation using tuplesort,
1654 : * not including the cost of reading the input data.
1655 : *
1656 : * If the total volume of data to sort is less than sort_mem, we will do
1657 : * an in-memory sort, which requires no I/O and about t*log2(t) tuple
1658 : * comparisons for t tuples.
1659 : *
1660 : * If the total volume exceeds sort_mem, we switch to a tape-style merge
1661 : * algorithm. There will still be about t*log2(t) tuple comparisons in
1662 : * total, but we will also need to write and read each tuple once per
1663 : * merge pass. We expect about ceil(logM(r)) merge passes where r is the
1664 : * number of initial runs formed and M is the merge order used by tuplesort.c.
1665 : * Since the average initial run should be about sort_mem, we have
1666 : * disk traffic = 2 * relsize * ceil(logM(p / sort_mem))
1667 : * cpu = comparison_cost * t * log2(t)
1668 : *
1669 : * If the sort is bounded (i.e., only the first k result tuples are needed)
1670 : * and k tuples can fit into sort_mem, we use a heap method that keeps only
1671 : * k tuples in the heap; this will require about t*log2(k) tuple comparisons.
1672 : *
1673 : * The disk traffic is assumed to be 3/4ths sequential and 1/4th random
1674 : * accesses (XXX can't we refine that guess?)
1675 : *
1676 : * By default, we charge two operator evals per tuple comparison, which should
1677 : * be in the right ballpark in most cases. The caller can tweak this by
1678 : * specifying nonzero comparison_cost; typically that's used for any extra
1679 : * work that has to be done to prepare the inputs to the comparison operators.
1680 : *
1681 : * 'tuples' is the number of tuples in the relation
1682 : * 'width' is the average tuple width in bytes
1683 : * 'comparison_cost' is the extra cost per comparison, if any
1684 : * 'sort_mem' is the number of kilobytes of work memory allowed for the sort
1685 : * 'limit_tuples' is the bound on the number of output tuples; -1 if no bound
1686 : */
1687 : static void
1688 698710 : cost_tuplesort(Cost *startup_cost, Cost *run_cost,
1689 : double tuples, int width,
1690 : Cost comparison_cost, int sort_mem,
1691 : double limit_tuples)
1692 : {
1693 698710 : double input_bytes = relation_byte_size(tuples, width);
1694 : double output_bytes;
1695 : double output_tuples;
1696 698710 : long sort_mem_bytes = sort_mem * 1024L;
1697 :
1698 : /*
1699 : * We want to be sure the cost of a sort is never estimated as zero, even
1700 : * if passed-in tuple count is zero. Besides, mustn't do log(0)...
1701 : */
1702 698710 : if (tuples < 2.0)
1703 217130 : tuples = 2.0;
1704 :
1705 : /* Include the default cost-per-comparison */
1706 698710 : comparison_cost += 2.0 * cpu_operator_cost;
1707 :
1708 : /* Do we have a useful LIMIT? */
1709 698710 : if (limit_tuples > 0 && limit_tuples < tuples)
1710 : {
1711 1548 : output_tuples = limit_tuples;
1712 1548 : output_bytes = relation_byte_size(output_tuples, width);
1713 : }
1714 : else
1715 : {
1716 697162 : output_tuples = tuples;
1717 697162 : output_bytes = input_bytes;
1718 : }
1719 :
1720 698710 : if (output_bytes > sort_mem_bytes)
1721 : {
1722 : /*
1723 : * We'll have to use a disk-based sort of all the tuples
1724 : */
1725 7366 : double npages = ceil(input_bytes / BLCKSZ);
1726 7366 : double nruns = input_bytes / sort_mem_bytes;
1727 7366 : double mergeorder = tuplesort_merge_order(sort_mem_bytes);
1728 : double log_runs;
1729 : double npageaccesses;
1730 :
1731 : /*
1732 : * CPU costs
1733 : *
1734 : * Assume about N log2 N comparisons
1735 : */
1736 7366 : *startup_cost = comparison_cost * tuples * LOG2(tuples);
1737 :
1738 : /* Disk costs */
1739 :
1740 : /* Compute logM(r) as log(r) / log(M) */
1741 7366 : if (nruns > mergeorder)
1742 3540 : log_runs = ceil(log(nruns) / log(mergeorder));
1743 : else
1744 3826 : log_runs = 1.0;
1745 7366 : npageaccesses = 2.0 * npages * log_runs;
1746 : /* Assume 3/4ths of accesses are sequential, 1/4th are not */
1747 14732 : *startup_cost += npageaccesses *
1748 7366 : (seq_page_cost * 0.75 + random_page_cost * 0.25);
1749 : }
1750 691344 : else if (tuples > 2 * output_tuples || input_bytes > sort_mem_bytes)
1751 : {
1752 : /*
1753 : * We'll use a bounded heap-sort keeping just K tuples in memory, for
1754 : * a total number of tuple comparisons of N log2 K; but the constant
1755 : * factor is a bit higher than for quicksort. Tweak it so that the
1756 : * cost curve is continuous at the crossover point.
1757 : */
1758 1086 : *startup_cost = comparison_cost * tuples * LOG2(2.0 * output_tuples);
1759 : }
1760 : else
1761 : {
1762 : /* We'll use plain quicksort on all the input tuples */
1763 690258 : *startup_cost = comparison_cost * tuples * LOG2(tuples);
1764 : }
1765 :
1766 : /*
1767 : * Also charge a small amount (arbitrarily set equal to operator cost) per
1768 : * extracted tuple. We don't charge cpu_tuple_cost because a Sort node
1769 : * doesn't do qual-checking or projection, so it has less overhead than
1770 : * most plan nodes. Note it's correct to use tuples not output_tuples
1771 : * here --- the upper LIMIT will pro-rate the run cost so we'd be double
1772 : * counting the LIMIT otherwise.
1773 : */
1774 698710 : *run_cost = cpu_operator_cost * tuples;
1775 698710 : }
1776 :
1777 : /*
1778 : * cost_incremental_sort
1779 : * Determines and returns the cost of sorting a relation incrementally, when
1780 : * the input path is presorted by a prefix of the pathkeys.
1781 : *
1782 : * 'presorted_keys' is the number of leading pathkeys by which the input path
1783 : * is sorted.
1784 : *
1785 : * We estimate the number of groups into which the relation is divided by the
1786 : * leading pathkeys, and then calculate the cost of sorting a single group
1787 : * with tuplesort using cost_tuplesort().
1788 : */
1789 : void
1790 1504 : cost_incremental_sort(Path *path,
1791 : PlannerInfo *root, List *pathkeys, int presorted_keys,
1792 : Cost input_startup_cost, Cost input_total_cost,
1793 : double input_tuples, int width, Cost comparison_cost, int sort_mem,
1794 : double limit_tuples)
1795 : {
1796 1504 : Cost startup_cost = 0,
1797 1504 : run_cost = 0,
1798 1504 : input_run_cost = input_total_cost - input_startup_cost;
1799 : double group_tuples,
1800 : input_groups;
1801 : Cost group_startup_cost,
1802 : group_run_cost,
1803 : group_input_run_cost;
1804 1504 : List *presortedExprs = NIL;
1805 : ListCell *l;
1806 1504 : int i = 0;
1807 1504 : bool unknown_varno = false;
1808 :
1809 : Assert(presorted_keys != 0);
1810 :
1811 : /*
1812 : * We want to be sure the cost of a sort is never estimated as zero, even
1813 : * if passed-in tuple count is zero. Besides, mustn't do log(0)...
1814 : */
1815 1504 : if (input_tuples < 2.0)
1816 520 : input_tuples = 2.0;
1817 :
1818 : /* Default estimate of number of groups, capped to one group per row. */
1819 1504 : input_groups = Min(input_tuples, DEFAULT_NUM_DISTINCT);
1820 :
1821 : /*
1822 : * Extract presorted keys as list of expressions.
1823 : *
1824 : * We need to be careful about Vars containing "varno 0" which might have
1825 : * been introduced by generate_append_tlist, which would confuse
1826 : * estimate_num_groups (in fact it'd fail for such expressions). See
1827 : * recurse_set_operations which has to deal with the same issue.
1828 : *
1829 : * Unlike recurse_set_operations we can't access the original target list
1830 : * here, and even if we could it's not very clear how useful would that be
1831 : * for a set operation combining multiple tables. So we simply detect if
1832 : * there are any expressions with "varno 0" and use the default
1833 : * DEFAULT_NUM_DISTINCT in that case.
1834 : *
1835 : * We might also use either 1.0 (a single group) or input_tuples (each row
1836 : * being a separate group), pretty much the worst and best case for
1837 : * incremental sort. But those are extreme cases and using something in
1838 : * between seems reasonable. Furthermore, generate_append_tlist is used
1839 : * for set operations, which are likely to produce mostly unique output
1840 : * anyway - from that standpoint the DEFAULT_NUM_DISTINCT is defensive
1841 : * while maintaining lower startup cost.
1842 : */
1843 1532 : foreach(l, pathkeys)
1844 : {
1845 1532 : PathKey *key = (PathKey *) lfirst(l);
1846 1532 : EquivalenceMember *member = (EquivalenceMember *)
1847 1532 : linitial(key->pk_eclass->ec_members);
1848 :
1849 : /*
1850 : * Check if the expression contains Var with "varno 0" so that we
1851 : * don't call estimate_num_groups in that case.
1852 : */
1853 1532 : if (bms_is_member(0, pull_varnos((Node *) member->em_expr)))
1854 : {
1855 4 : unknown_varno = true;
1856 4 : break;
1857 : }
1858 :
1859 : /* expression not containing any Vars with "varno 0" */
1860 1528 : presortedExprs = lappend(presortedExprs, member->em_expr);
1861 :
1862 1528 : i++;
1863 1528 : if (i >= presorted_keys)
1864 1500 : break;
1865 : }
1866 :
1867 : /* Estimate number of groups with equal presorted keys. */
1868 1504 : if (!unknown_varno)
1869 1500 : input_groups = estimate_num_groups(root, presortedExprs, input_tuples, NULL);
1870 :
1871 1504 : group_tuples = input_tuples / input_groups;
1872 1504 : group_input_run_cost = input_run_cost / input_groups;
1873 :
1874 : /*
1875 : * Estimate average cost of sorting of one group where presorted keys are
1876 : * equal. Incremental sort is sensitive to distribution of tuples to the
1877 : * groups, where we're relying on quite rough assumptions. Thus, we're
1878 : * pessimistic about incremental sort performance and increase its average
1879 : * group size by half.
1880 : */
1881 1504 : cost_tuplesort(&group_startup_cost, &group_run_cost,
1882 : 1.5 * group_tuples, width, comparison_cost, sort_mem,
1883 : limit_tuples);
1884 :
1885 : /*
1886 : * Startup cost of incremental sort is the startup cost of its first group
1887 : * plus the cost of its input.
1888 : */
1889 1504 : startup_cost += group_startup_cost
1890 1504 : + input_startup_cost + group_input_run_cost;
1891 :
1892 : /*
1893 : * After we started producing tuples from the first group, the cost of
1894 : * producing all the tuples is given by the cost to finish processing this
1895 : * group, plus the total cost to process the remaining groups, plus the
1896 : * remaining cost of input.
1897 : */
1898 1504 : run_cost += group_run_cost
1899 1504 : + (group_run_cost + group_startup_cost) * (input_groups - 1)
1900 1504 : + group_input_run_cost * (input_groups - 1);
1901 :
1902 : /*
1903 : * Incremental sort adds some overhead by itself. Firstly, it has to
1904 : * detect the sort groups. This is roughly equal to one extra copy and
1905 : * comparison per tuple. Secondly, it has to reset the tuplesort context
1906 : * for every group.
1907 : */
1908 1504 : run_cost += (cpu_tuple_cost + comparison_cost) * input_tuples;
1909 1504 : run_cost += 2.0 * cpu_tuple_cost * input_groups;
1910 :
1911 1504 : path->rows = input_tuples;
1912 1504 : path->startup_cost = startup_cost;
1913 1504 : path->total_cost = startup_cost + run_cost;
1914 1504 : }
1915 :
1916 : /*
1917 : * cost_sort
1918 : * Determines and returns the cost of sorting a relation, including
1919 : * the cost of reading the input data.
1920 : *
1921 : * NOTE: some callers currently pass NIL for pathkeys because they
1922 : * can't conveniently supply the sort keys. Since this routine doesn't
1923 : * currently do anything with pathkeys anyway, that doesn't matter...
1924 : * but if it ever does, it should react gracefully to lack of key data.
1925 : * (Actually, the thing we'd most likely be interested in is just the number
1926 : * of sort keys, which all callers *could* supply.)
1927 : */
1928 : void
1929 697206 : cost_sort(Path *path, PlannerInfo *root,
1930 : List *pathkeys, Cost input_cost, double tuples, int width,
1931 : Cost comparison_cost, int sort_mem,
1932 : double limit_tuples)
1933 :
1934 : {
1935 : Cost startup_cost;
1936 : Cost run_cost;
1937 :
1938 697206 : cost_tuplesort(&startup_cost, &run_cost,
1939 : tuples, width,
1940 : comparison_cost, sort_mem,
1941 : limit_tuples);
1942 :
1943 697206 : if (!enable_sort)
1944 638 : startup_cost += disable_cost;
1945 :
1946 697206 : startup_cost += input_cost;
1947 :
1948 697206 : path->rows = tuples;
1949 697206 : path->startup_cost = startup_cost;
1950 697206 : path->total_cost = startup_cost + run_cost;
1951 697206 : }
1952 :
1953 : /*
1954 : * append_nonpartial_cost
1955 : * Estimate the cost of the non-partial paths in a Parallel Append.
1956 : * The non-partial paths are assumed to be the first "numpaths" paths
1957 : * from the subpaths list, and to be in order of decreasing cost.
1958 : */
1959 : static Cost
1960 9500 : append_nonpartial_cost(List *subpaths, int numpaths, int parallel_workers)
1961 : {
1962 : Cost *costarr;
1963 : int arrlen;
1964 : ListCell *l;
1965 : ListCell *cell;
1966 : int i;
1967 : int path_index;
1968 : int min_index;
1969 : int max_index;
1970 :
1971 9500 : if (numpaths == 0)
1972 7478 : return 0;
1973 :
1974 : /*
1975 : * Array length is number of workers or number of relevant paths,
1976 : * whichever is less.
1977 : */
1978 2022 : arrlen = Min(parallel_workers, numpaths);
1979 2022 : costarr = (Cost *) palloc(sizeof(Cost) * arrlen);
1980 :
1981 : /* The first few paths will each be claimed by a different worker. */
1982 2022 : path_index = 0;
1983 5850 : foreach(cell, subpaths)
1984 : {
1985 4496 : Path *subpath = (Path *) lfirst(cell);
1986 :
1987 4496 : if (path_index == arrlen)
1988 668 : break;
1989 3828 : costarr[path_index++] = subpath->total_cost;
1990 : }
1991 :
1992 : /*
1993 : * Since subpaths are sorted by decreasing cost, the last one will have
1994 : * the minimum cost.
1995 : */
1996 2022 : min_index = arrlen - 1;
1997 :
1998 : /*
1999 : * For each of the remaining subpaths, add its cost to the array element
2000 : * with minimum cost.
2001 : */
2002 2544 : for_each_cell(l, subpaths, cell)
2003 : {
2004 794 : Path *subpath = (Path *) lfirst(l);
2005 : int i;
2006 :
2007 : /* Consider only the non-partial paths */
2008 794 : if (path_index++ == numpaths)
2009 272 : break;
2010 :
2011 522 : costarr[min_index] += subpath->total_cost;
2012 :
2013 : /* Update the new min cost array index */
2014 1590 : for (min_index = i = 0; i < arrlen; i++)
2015 : {
2016 1068 : if (costarr[i] < costarr[min_index])
2017 130 : min_index = i;
2018 : }
2019 : }
2020 :
2021 : /* Return the highest cost from the array */
2022 5850 : for (max_index = i = 0; i < arrlen; i++)
2023 : {
2024 3828 : if (costarr[i] > costarr[max_index])
2025 314 : max_index = i;
2026 : }
2027 :
2028 2022 : return costarr[max_index];
2029 : }
2030 :
2031 : /*
2032 : * cost_append
2033 : * Determines and returns the cost of an Append node.
2034 : */
2035 : void
2036 26774 : cost_append(AppendPath *apath)
2037 : {
2038 : ListCell *l;
2039 :
2040 26774 : apath->path.startup_cost = 0;
2041 26774 : apath->path.total_cost = 0;
2042 26774 : apath->path.rows = 0;
2043 :
2044 26774 : if (apath->subpaths == NIL)
2045 780 : return;
2046 :
2047 25994 : if (!apath->path.parallel_aware)
2048 : {
2049 16494 : List *pathkeys = apath->path.pathkeys;
2050 :
2051 16494 : if (pathkeys == NIL)
2052 : {
2053 15362 : Path *subpath = (Path *) linitial(apath->subpaths);
2054 :
2055 : /*
2056 : * For an unordered, non-parallel-aware Append we take the startup
2057 : * cost as the startup cost of the first subpath.
2058 : */
2059 15362 : apath->path.startup_cost = subpath->startup_cost;
2060 :
2061 : /* Compute rows and costs as sums of subplan rows and costs. */
2062 60292 : foreach(l, apath->subpaths)
2063 : {
2064 44930 : Path *subpath = (Path *) lfirst(l);
2065 :
2066 44930 : apath->path.rows += subpath->rows;
2067 44930 : apath->path.total_cost += subpath->total_cost;
2068 : }
2069 : }
2070 : else
2071 : {
2072 : /*
2073 : * For an ordered, non-parallel-aware Append we take the startup
2074 : * cost as the sum of the subpath startup costs. This ensures
2075 : * that we don't underestimate the startup cost when a query's
2076 : * LIMIT is such that several of the children have to be run to
2077 : * satisfy it. This might be overkill --- another plausible hack
2078 : * would be to take the Append's startup cost as the maximum of
2079 : * the child startup costs. But we don't want to risk believing
2080 : * that an ORDER BY LIMIT query can be satisfied at small cost
2081 : * when the first child has small startup cost but later ones
2082 : * don't. (If we had the ability to deal with nonlinear cost
2083 : * interpolation for partial retrievals, we would not need to be
2084 : * so conservative about this.)
2085 : *
2086 : * This case is also different from the above in that we have to
2087 : * account for possibly injecting sorts into subpaths that aren't
2088 : * natively ordered.
2089 : */
2090 4456 : foreach(l, apath->subpaths)
2091 : {
2092 3324 : Path *subpath = (Path *) lfirst(l);
2093 : Path sort_path; /* dummy for result of cost_sort */
2094 :
2095 3324 : if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
2096 : {
2097 : /*
2098 : * We'll need to insert a Sort node, so include costs for
2099 : * that. We can use the parent's LIMIT if any, since we
2100 : * certainly won't pull more than that many tuples from
2101 : * any child.
2102 : */
2103 40 : cost_sort(&sort_path,
2104 : NULL, /* doesn't currently need root */
2105 : pathkeys,
2106 : subpath->total_cost,
2107 : subpath->rows,
2108 20 : subpath->pathtarget->width,
2109 : 0.0,
2110 : work_mem,
2111 : apath->limit_tuples);
2112 20 : subpath = &sort_path;
2113 : }
2114 :
2115 3324 : apath->path.rows += subpath->rows;
2116 3324 : apath->path.startup_cost += subpath->startup_cost;
2117 3324 : apath->path.total_cost += subpath->total_cost;
2118 : }
2119 : }
2120 : }
2121 : else /* parallel-aware */
2122 : {
2123 9500 : int i = 0;
2124 9500 : double parallel_divisor = get_parallel_divisor(&apath->path);
2125 :
2126 : /* Parallel-aware Append never produces ordered output. */
2127 : Assert(apath->path.pathkeys == NIL);
2128 :
2129 : /* Calculate startup cost. */
2130 38642 : foreach(l, apath->subpaths)
2131 : {
2132 29142 : Path *subpath = (Path *) lfirst(l);
2133 :
2134 : /*
2135 : * Append will start returning tuples when the child node having
2136 : * lowest startup cost is done setting up. We consider only the
2137 : * first few subplans that immediately get a worker assigned.
2138 : */
2139 29142 : if (i == 0)
2140 9500 : apath->path.startup_cost = subpath->startup_cost;
2141 19642 : else if (i < apath->path.parallel_workers)
2142 9436 : apath->path.startup_cost = Min(apath->path.startup_cost,
2143 : subpath->startup_cost);
2144 :
2145 : /*
2146 : * Apply parallel divisor to subpaths. Scale the number of rows
2147 : * for each partial subpath based on the ratio of the parallel
2148 : * divisor originally used for the subpath to the one we adopted.
2149 : * Also add the cost of partial paths to the total cost, but
2150 : * ignore non-partial paths for now.
2151 : */
2152 29142 : if (i < apath->first_partial_path)
2153 4350 : apath->path.rows += subpath->rows / parallel_divisor;
2154 : else
2155 : {
2156 : double subpath_parallel_divisor;
2157 :
2158 24792 : subpath_parallel_divisor = get_parallel_divisor(subpath);
2159 24792 : apath->path.rows += subpath->rows * (subpath_parallel_divisor /
2160 : parallel_divisor);
2161 24792 : apath->path.total_cost += subpath->total_cost;
2162 : }
2163 :
2164 29142 : apath->path.rows = clamp_row_est(apath->path.rows);
2165 :
2166 29142 : i++;
2167 : }
2168 :
2169 : /* Add cost for non-partial subpaths. */
2170 9500 : apath->path.total_cost +=
2171 9500 : append_nonpartial_cost(apath->subpaths,
2172 : apath->first_partial_path,
2173 : apath->path.parallel_workers);
2174 : }
2175 :
2176 : /*
2177 : * Although Append does not do any selection or projection, it's not free;
2178 : * add a small per-tuple overhead.
2179 : */
2180 51988 : apath->path.total_cost +=
2181 25994 : cpu_tuple_cost * APPEND_CPU_COST_MULTIPLIER * apath->path.rows;
2182 : }
2183 :
2184 : /*
2185 : * cost_merge_append
2186 : * Determines and returns the cost of a MergeAppend node.
2187 : *
2188 : * MergeAppend merges several pre-sorted input streams, using a heap that
2189 : * at any given instant holds the next tuple from each stream. If there
2190 : * are N streams, we need about N*log2(N) tuple comparisons to construct
2191 : * the heap at startup, and then for each output tuple, about log2(N)
2192 : * comparisons to replace the top entry.
2193 : *
2194 : * (The effective value of N will drop once some of the input streams are
2195 : * exhausted, but it seems unlikely to be worth trying to account for that.)
2196 : *
2197 : * The heap is never spilled to disk, since we assume N is not very large.
2198 : * So this is much simpler than cost_sort.
2199 : *
2200 : * As in cost_sort, we charge two operator evals per tuple comparison.
2201 : *
2202 : * 'pathkeys' is a list of sort keys
2203 : * 'n_streams' is the number of input streams
2204 : * 'input_startup_cost' is the sum of the input streams' startup costs
2205 : * 'input_total_cost' is the sum of the input streams' total costs
2206 : * 'tuples' is the number of tuples in all the streams
2207 : */
2208 : void
2209 2232 : cost_merge_append(Path *path, PlannerInfo *root,
2210 : List *pathkeys, int n_streams,
2211 : Cost input_startup_cost, Cost input_total_cost,
2212 : double tuples)
2213 : {
2214 2232 : Cost startup_cost = 0;
2215 2232 : Cost run_cost = 0;
2216 : Cost comparison_cost;
2217 : double N;
2218 : double logN;
2219 :
2220 : /*
2221 : * Avoid log(0)...
2222 : */
2223 2232 : N = (n_streams < 2) ? 2.0 : (double) n_streams;
2224 2232 : logN = LOG2(N);
2225 :
2226 : /* Assumed cost per tuple comparison */
2227 2232 : comparison_cost = 2.0 * cpu_operator_cost;
2228 :
2229 : /* Heap creation cost */
2230 2232 : startup_cost += comparison_cost * N * logN;
2231 :
2232 : /* Per-tuple heap maintenance cost */
2233 2232 : run_cost += tuples * comparison_cost * logN;
2234 :
2235 : /*
2236 : * Although MergeAppend does not do any selection or projection, it's not
2237 : * free; add a small per-tuple overhead.
2238 : */
2239 2232 : run_cost += cpu_tuple_cost * APPEND_CPU_COST_MULTIPLIER * tuples;
2240 :
2241 2232 : path->startup_cost = startup_cost + input_startup_cost;
2242 2232 : path->total_cost = startup_cost + run_cost + input_total_cost;
2243 2232 : }
2244 :
2245 : /*
2246 : * cost_material
2247 : * Determines and returns the cost of materializing a relation, including
2248 : * the cost of reading the input data.
2249 : *
2250 : * If the total volume of data to materialize exceeds work_mem, we will need
2251 : * to write it to disk, so the cost is much higher in that case.
2252 : *
2253 : * Note that here we are estimating the costs for the first scan of the
2254 : * relation, so the materialization is all overhead --- any savings will
2255 : * occur only on rescan, which is estimated in cost_rescan.
2256 : */
2257 : void
2258 230854 : cost_material(Path *path,
2259 : Cost input_startup_cost, Cost input_total_cost,
2260 : double tuples, int width)
2261 : {
2262 230854 : Cost startup_cost = input_startup_cost;
2263 230854 : Cost run_cost = input_total_cost - input_startup_cost;
2264 230854 : double nbytes = relation_byte_size(tuples, width);
2265 230854 : long work_mem_bytes = work_mem * 1024L;
2266 :
2267 230854 : path->rows = tuples;
2268 :
2269 : /*
2270 : * Whether spilling or not, charge 2x cpu_operator_cost per tuple to
2271 : * reflect bookkeeping overhead. (This rate must be more than what
2272 : * cost_rescan charges for materialize, ie, cpu_operator_cost per tuple;
2273 : * if it is exactly the same then there will be a cost tie between
2274 : * nestloop with A outer, materialized B inner and nestloop with B outer,
2275 : * materialized A inner. The extra cost ensures we'll prefer
2276 : * materializing the smaller rel.) Note that this is normally a good deal
2277 : * less than cpu_tuple_cost; which is OK because a Material plan node
2278 : * doesn't do qual-checking or projection, so it's got less overhead than
2279 : * most plan nodes.
2280 : */
2281 230854 : run_cost += 2 * cpu_operator_cost * tuples;
2282 :
2283 : /*
2284 : * If we will spill to disk, charge at the rate of seq_page_cost per page.
2285 : * This cost is assumed to be evenly spread through the plan run phase,
2286 : * which isn't exactly accurate but our cost model doesn't allow for
2287 : * nonuniform costs within the run phase.
2288 : */
2289 230854 : if (nbytes > work_mem_bytes)
2290 : {
2291 1992 : double npages = ceil(nbytes / BLCKSZ);
2292 :
2293 1992 : run_cost += seq_page_cost * npages;
2294 : }
2295 :
2296 230854 : path->startup_cost = startup_cost;
2297 230854 : path->total_cost = startup_cost + run_cost;
2298 230854 : }
2299 :
2300 : /*
2301 : * cost_agg
2302 : * Determines and returns the cost of performing an Agg plan node,
2303 : * including the cost of its input.
2304 : *
2305 : * aggcosts can be NULL when there are no actual aggregate functions (i.e.,
2306 : * we are using a hashed Agg node just to do grouping).
2307 : *
2308 : * Note: when aggstrategy == AGG_SORTED, caller must ensure that input costs
2309 : * are for appropriately-sorted input.
2310 : */
2311 : void
2312 38264 : cost_agg(Path *path, PlannerInfo *root,
2313 : AggStrategy aggstrategy, const AggClauseCosts *aggcosts,
2314 : int numGroupCols, double numGroups,
2315 : List *quals,
2316 : Cost input_startup_cost, Cost input_total_cost,
2317 : double input_tuples, double input_width)
2318 : {
2319 : double output_tuples;
2320 : Cost startup_cost;
2321 : Cost total_cost;
2322 : AggClauseCosts dummy_aggcosts;
2323 :
2324 : /* Use all-zero per-aggregate costs if NULL is passed */
2325 38264 : if (aggcosts == NULL)
2326 : {
2327 : Assert(aggstrategy == AGG_HASHED);
2328 26080 : MemSet(&dummy_aggcosts, 0, sizeof(AggClauseCosts));
2329 3260 : aggcosts = &dummy_aggcosts;
2330 : }
2331 :
2332 : /*
2333 : * The transCost.per_tuple component of aggcosts should be charged once
2334 : * per input tuple, corresponding to the costs of evaluating the aggregate
2335 : * transfns and their input expressions. The finalCost.per_tuple component
2336 : * is charged once per output tuple, corresponding to the costs of
2337 : * evaluating the finalfns. Startup costs are of course charged but once.
2338 : *
2339 : * If we are grouping, we charge an additional cpu_operator_cost per
2340 : * grouping column per input tuple for grouping comparisons.
2341 : *
2342 : * We will produce a single output tuple if not grouping, and a tuple per
2343 : * group otherwise. We charge cpu_tuple_cost for each output tuple.
2344 : *
2345 : * Note: in this cost model, AGG_SORTED and AGG_HASHED have exactly the
2346 : * same total CPU cost, but AGG_SORTED has lower startup cost. If the
2347 : * input path is already sorted appropriately, AGG_SORTED should be
2348 : * preferred (since it has no risk of memory overflow). This will happen
2349 : * as long as the computed total costs are indeed exactly equal --- but if
2350 : * there's roundoff error we might do the wrong thing. So be sure that
2351 : * the computations below form the same intermediate values in the same
2352 : * order.
2353 : */
2354 38264 : if (aggstrategy == AGG_PLAIN)
2355 : {
2356 24506 : startup_cost = input_total_cost;
2357 24506 : startup_cost += aggcosts->transCost.startup;
2358 24506 : startup_cost += aggcosts->transCost.per_tuple * input_tuples;
2359 24506 : startup_cost += aggcosts->finalCost.startup;
2360 24506 : startup_cost += aggcosts->finalCost.per_tuple;
2361 : /* we aren't grouping */
2362 24506 : total_cost = startup_cost + cpu_tuple_cost;
2363 24506 : output_tuples = 1;
2364 : }
2365 13758 : else if (aggstrategy == AGG_SORTED || aggstrategy == AGG_MIXED)
2366 : {
2367 : /* Here we are able to deliver output on-the-fly */
2368 6048 : startup_cost = input_startup_cost;
2369 6048 : total_cost = input_total_cost;
2370 6048 : if (aggstrategy == AGG_MIXED && !enable_hashagg)
2371 : {
2372 276 : startup_cost += disable_cost;
2373 276 : total_cost += disable_cost;
2374 : }
2375 : /* calcs phrased this way to match HASHED case, see note above */
2376 6048 : total_cost += aggcosts->transCost.startup;
2377 6048 : total_cost += aggcosts->transCost.per_tuple * input_tuples;
2378 6048 : total_cost += (cpu_operator_cost * numGroupCols) * input_tuples;
2379 6048 : total_cost += aggcosts->finalCost.startup;
2380 6048 : total_cost += aggcosts->finalCost.per_tuple * numGroups;
2381 6048 : total_cost += cpu_tuple_cost * numGroups;
2382 6048 : output_tuples = numGroups;
2383 : }
2384 : else
2385 : {
2386 : /* must be AGG_HASHED */
2387 7710 : startup_cost = input_total_cost;
2388 7710 : if (!enable_hashagg)
2389 878 : startup_cost += disable_cost;
2390 7710 : startup_cost += aggcosts->transCost.startup;
2391 7710 : startup_cost += aggcosts->transCost.per_tuple * input_tuples;
2392 : /* cost of computing hash value */
2393 7710 : startup_cost += (cpu_operator_cost * numGroupCols) * input_tuples;
2394 7710 : startup_cost += aggcosts->finalCost.startup;
2395 :
2396 7710 : total_cost = startup_cost;
2397 7710 : total_cost += aggcosts->finalCost.per_tuple * numGroups;
2398 : /* cost of retrieving from hash table */
2399 7710 : total_cost += cpu_tuple_cost * numGroups;
2400 7710 : output_tuples = numGroups;
2401 : }
2402 :
2403 : /*
2404 : * Add the disk costs of hash aggregation that spills to disk.
2405 : *
2406 : * Groups that go into the hash table stay in memory until finalized, so
2407 : * spilling and reprocessing tuples doesn't incur additional invocations
2408 : * of transCost or finalCost. Furthermore, the computed hash value is
2409 : * stored with the spilled tuples, so we don't incur extra invocations of
2410 : * the hash function.
2411 : *
2412 : * Hash Agg begins returning tuples after the first batch is complete.
2413 : * Accrue writes (spilled tuples) to startup_cost and to total_cost;
2414 : * accrue reads only to total_cost.
2415 : */
2416 38264 : if (aggstrategy == AGG_HASHED || aggstrategy == AGG_MIXED)
2417 : {
2418 : double pages;
2419 8186 : double pages_written = 0.0;
2420 8186 : double pages_read = 0.0;
2421 : double hashentrysize;
2422 : double nbatches;
2423 : Size mem_limit;
2424 : uint64 ngroups_limit;
2425 : int num_partitions;
2426 : int depth;
2427 :
2428 : /*
2429 : * Estimate number of batches based on the computed limits. If less
2430 : * than or equal to one, all groups are expected to fit in memory;
2431 : * otherwise we expect to spill.
2432 : */
2433 8186 : hashentrysize = hash_agg_entry_size(aggcosts->numAggs, input_width,
2434 : aggcosts->transitionSpace);
2435 8186 : hash_agg_set_limits(hashentrysize, numGroups, 0, &mem_limit,
2436 : &ngroups_limit, &num_partitions);
2437 :
2438 8186 : nbatches = Max((numGroups * hashentrysize) / mem_limit,
2439 : numGroups / ngroups_limit);
2440 :
2441 8186 : nbatches = Max(ceil(nbatches), 1.0);
2442 8186 : num_partitions = Max(num_partitions, 2);
2443 :
2444 : /*
2445 : * The number of partitions can change at different levels of
2446 : * recursion; but for the purposes of this calculation assume it stays
2447 : * constant.
2448 : */
2449 8186 : depth = ceil(log(nbatches) / log(num_partitions));
2450 :
2451 : /*
2452 : * Estimate number of pages read and written. For each level of
2453 : * recursion, a tuple must be written and then later read.
2454 : */
2455 8186 : pages = relation_byte_size(input_tuples, input_width) / BLCKSZ;
2456 8186 : pages_written = pages_read = pages * depth;
2457 :
2458 8186 : startup_cost += pages_written * random_page_cost;
2459 8186 : total_cost += pages_written * random_page_cost;
2460 8186 : total_cost += pages_read * seq_page_cost;
2461 : }
2462 :
2463 : /*
2464 : * If there are quals (HAVING quals), account for their cost and
2465 : * selectivity.
2466 : */
2467 38264 : if (quals)
2468 : {
2469 : QualCost qual_cost;
2470 :
2471 2390 : cost_qual_eval(&qual_cost, quals, root);
2472 2390 : startup_cost += qual_cost.startup;
2473 2390 : total_cost += qual_cost.startup + output_tuples * qual_cost.per_tuple;
2474 :
2475 2390 : output_tuples = clamp_row_est(output_tuples *
2476 2390 : clauselist_selectivity(root,
2477 : quals,
2478 : 0,
2479 : JOIN_INNER,
2480 : NULL));
2481 : }
2482 :
2483 38264 : path->rows = output_tuples;
2484 38264 : path->startup_cost = startup_cost;
2485 38264 : path->total_cost = total_cost;
2486 38264 : }
2487 :
2488 : /*
2489 : * cost_windowagg
2490 : * Determines and returns the cost of performing a WindowAgg plan node,
2491 : * including the cost of its input.
2492 : *
2493 : * Input is assumed already properly sorted.
2494 : */
2495 : void
2496 1204 : cost_windowagg(Path *path, PlannerInfo *root,
2497 : List *windowFuncs, int numPartCols, int numOrderCols,
2498 : Cost input_startup_cost, Cost input_total_cost,
2499 : double input_tuples)
2500 : {
2501 : Cost startup_cost;
2502 : Cost total_cost;
2503 : ListCell *lc;
2504 :
2505 1204 : startup_cost = input_startup_cost;
2506 1204 : total_cost = input_total_cost;
2507 :
2508 : /*
2509 : * Window functions are assumed to cost their stated execution cost, plus
2510 : * the cost of evaluating their input expressions, per tuple. Since they
2511 : * may in fact evaluate their inputs at multiple rows during each cycle,
2512 : * this could be a drastic underestimate; but without a way to know how
2513 : * many rows the window function will fetch, it's hard to do better. In
2514 : * any case, it's a good estimate for all the built-in window functions,
2515 : * so we'll just do this for now.
2516 : */
2517 2660 : foreach(lc, windowFuncs)
2518 : {
2519 1456 : WindowFunc *wfunc = lfirst_node(WindowFunc, lc);
2520 : Cost wfunccost;
2521 : QualCost argcosts;
2522 :
2523 1456 : argcosts.startup = argcosts.per_tuple = 0;
2524 1456 : add_function_cost(root, wfunc->winfnoid, (Node *) wfunc,
2525 : &argcosts);
2526 1456 : startup_cost += argcosts.startup;
2527 1456 : wfunccost = argcosts.per_tuple;
2528 :
2529 : /* also add the input expressions' cost to per-input-row costs */
2530 1456 : cost_qual_eval_node(&argcosts, (Node *) wfunc->args, root);
2531 1456 : startup_cost += argcosts.startup;
2532 1456 : wfunccost += argcosts.per_tuple;
2533 :
2534 : /*
2535 : * Add the filter's cost to per-input-row costs. XXX We should reduce
2536 : * input expression costs according to filter selectivity.
2537 : */
2538 1456 : cost_qual_eval_node(&argcosts, (Node *) wfunc->aggfilter, root);
2539 1456 : startup_cost += argcosts.startup;
2540 1456 : wfunccost += argcosts.per_tuple;
2541 :
2542 1456 : total_cost += wfunccost * input_tuples;
2543 : }
2544 :
2545 : /*
2546 : * We also charge cpu_operator_cost per grouping column per tuple for
2547 : * grouping comparisons, plus cpu_tuple_cost per tuple for general
2548 : * overhead.
2549 : *
2550 : * XXX this neglects costs of spooling the data to disk when it overflows
2551 : * work_mem. Sooner or later that should get accounted for.
2552 : */
2553 1204 : total_cost += cpu_operator_cost * (numPartCols + numOrderCols) * input_tuples;
2554 1204 : total_cost += cpu_tuple_cost * input_tuples;
2555 :
2556 1204 : path->rows = input_tuples;
2557 1204 : path->startup_cost = startup_cost;
2558 1204 : path->total_cost = total_cost;
2559 1204 : }
2560 :
2561 : /*
2562 : * cost_group
2563 : * Determines and returns the cost of performing a Group plan node,
2564 : * including the cost of its input.
2565 : *
2566 : * Note: caller must ensure that input costs are for appropriately-sorted
2567 : * input.
2568 : */
2569 : void
2570 1016 : cost_group(Path *path, PlannerInfo *root,
2571 : int numGroupCols, double numGroups,
2572 : List *quals,
2573 : Cost input_startup_cost, Cost input_total_cost,
2574 : double input_tuples)
2575 : {
2576 : double output_tuples;
2577 : Cost startup_cost;
2578 : Cost total_cost;
2579 :
2580 1016 : output_tuples = numGroups;
2581 1016 : startup_cost = input_startup_cost;
2582 1016 : total_cost = input_total_cost;
2583 :
2584 : /*
2585 : * Charge one cpu_operator_cost per comparison per input tuple. We assume
2586 : * all columns get compared at most of the tuples.
2587 : */
2588 1016 : total_cost += cpu_operator_cost * input_tuples * numGroupCols;
2589 :
2590 : /*
2591 : * If there are quals (HAVING quals), account for their cost and
2592 : * selectivity.
2593 : */
2594 1016 : if (quals)
2595 : {
2596 : QualCost qual_cost;
2597 :
2598 0 : cost_qual_eval(&qual_cost, quals, root);
2599 0 : startup_cost += qual_cost.startup;
2600 0 : total_cost += qual_cost.startup + output_tuples * qual_cost.per_tuple;
2601 :
2602 0 : output_tuples = clamp_row_est(output_tuples *
2603 0 : clauselist_selectivity(root,
2604 : quals,
2605 : 0,
2606 : JOIN_INNER,
2607 : NULL));
2608 : }
2609 :
2610 1016 : path->rows = output_tuples;
2611 1016 : path->startup_cost = startup_cost;
2612 1016 : path->total_cost = total_cost;
2613 1016 : }
2614 :
2615 : /*
2616 : * initial_cost_nestloop
2617 : * Preliminary estimate of the cost of a nestloop join path.
2618 : *
2619 : * This must quickly produce lower-bound estimates of the path's startup and
2620 : * total costs. If we are unable to eliminate the proposed path from
2621 : * consideration using the lower bounds, final_cost_nestloop will be called
2622 : * to obtain the final estimates.
2623 : *
2624 : * The exact division of labor between this function and final_cost_nestloop
2625 : * is private to them, and represents a tradeoff between speed of the initial
2626 : * estimate and getting a tight lower bound. We choose to not examine the
2627 : * join quals here, since that's by far the most expensive part of the
2628 : * calculations. The end result is that CPU-cost considerations must be
2629 : * left for the second phase; and for SEMI/ANTI joins, we must also postpone
2630 : * incorporation of the inner path's run cost.
2631 : *
2632 : * 'workspace' is to be filled with startup_cost, total_cost, and perhaps
2633 : * other data to be used by final_cost_nestloop
2634 : * 'jointype' is the type of join to be performed
2635 : * 'outer_path' is the outer input to the join
2636 : * 'inner_path' is the inner input to the join
2637 : * 'extra' contains miscellaneous information about the join
2638 : */
2639 : void
2640 1113022 : initial_cost_nestloop(PlannerInfo *root, JoinCostWorkspace *workspace,
2641 : JoinType jointype,
2642 : Path *outer_path, Path *inner_path,
2643 : JoinPathExtraData *extra)
2644 : {
2645 1113022 : Cost startup_cost = 0;
2646 1113022 : Cost run_cost = 0;
2647 1113022 : double outer_path_rows = outer_path->rows;
2648 : Cost inner_rescan_start_cost;
2649 : Cost inner_rescan_total_cost;
2650 : Cost inner_run_cost;
2651 : Cost inner_rescan_run_cost;
2652 :
2653 : /* estimate costs to rescan the inner relation */
2654 1113022 : cost_rescan(root, inner_path,
2655 : &inner_rescan_start_cost,
2656 : &inner_rescan_total_cost);
2657 :
2658 : /* cost of source data */
2659 :
2660 : /*
2661 : * NOTE: clearly, we must pay both outer and inner paths' startup_cost
2662 : * before we can start returning tuples, so the join's startup cost is
2663 : * their sum. We'll also pay the inner path's rescan startup cost
2664 : * multiple times.
2665 : */
2666 1113022 : startup_cost += outer_path->startup_cost + inner_path->startup_cost;
2667 1113022 : run_cost += outer_path->total_cost - outer_path->startup_cost;
2668 1113022 : if (outer_path_rows > 1)
2669 666648 : run_cost += (outer_path_rows - 1) * inner_rescan_start_cost;
2670 :
2671 1113022 : inner_run_cost = inner_path->total_cost - inner_path->startup_cost;
2672 1113022 : inner_rescan_run_cost = inner_rescan_total_cost - inner_rescan_start_cost;
2673 :
2674 1113022 : if (jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
2675 1075122 : extra->inner_unique)
2676 : {
2677 : /*
2678 : * With a SEMI or ANTI join, or if the innerrel is known unique, the
2679 : * executor will stop after the first match.
2680 : *
2681 : * Getting decent estimates requires inspection of the join quals,
2682 : * which we choose to postpone to final_cost_nestloop.
2683 : */
2684 :
2685 : /* Save private data for final_cost_nestloop */
2686 520018 : workspace->inner_run_cost = inner_run_cost;
2687 520018 : workspace->inner_rescan_run_cost = inner_rescan_run_cost;
2688 : }
2689 : else
2690 : {
2691 : /* Normal case; we'll scan whole input rel for each outer row */
2692 593004 : run_cost += inner_run_cost;
2693 593004 : if (outer_path_rows > 1)
2694 339402 : run_cost += (outer_path_rows - 1) * inner_rescan_run_cost;
2695 : }
2696 :
2697 : /* CPU costs left for later */
2698 :
2699 : /* Public result fields */
2700 1113022 : workspace->startup_cost = startup_cost;
2701 1113022 : workspace->total_cost = startup_cost + run_cost;
2702 : /* Save private data for final_cost_nestloop */
2703 1113022 : workspace->run_cost = run_cost;
2704 1113022 : }
2705 :
2706 : /*
2707 : * final_cost_nestloop
2708 : * Final estimate of the cost and result size of a nestloop join path.
2709 : *
2710 : * 'path' is already filled in except for the rows and cost fields
2711 : * 'workspace' is the result from initial_cost_nestloop
2712 : * 'extra' contains miscellaneous information about the join
2713 : */
2714 : void
2715 622054 : final_cost_nestloop(PlannerInfo *root, NestPath *path,
2716 : JoinCostWorkspace *workspace,
2717 : JoinPathExtraData *extra)
2718 : {
2719 622054 : Path *outer_path = path->outerjoinpath;
2720 622054 : Path *inner_path = path->innerjoinpath;
2721 622054 : double outer_path_rows = outer_path->rows;
2722 622054 : double inner_path_rows = inner_path->rows;
2723 622054 : Cost startup_cost = workspace->startup_cost;
2724 622054 : Cost run_cost = workspace->run_cost;
2725 : Cost cpu_per_tuple;
2726 : QualCost restrict_qual_cost;
2727 : double ntuples;
2728 :
2729 : /* Protect some assumptions below that rowcounts aren't zero or NaN */
2730 622054 : if (outer_path_rows <= 0 || isnan(outer_path_rows))
2731 0 : outer_path_rows = 1;
2732 622054 : if (inner_path_rows <= 0 || isnan(inner_path_rows))
2733 88 : inner_path_rows = 1;
2734 :
2735 : /* Mark the path with the correct row estimate */
2736 622054 : if (path->path.param_info)
2737 5124 : path->path.rows = path->path.param_info->ppi_rows;
2738 : else
2739 616930 : path->path.rows = path->path.parent->rows;
2740 :
2741 : /* For partial paths, scale row estimate. */
2742 622054 : if (path->path.parallel_workers > 0)
2743 : {
2744 3780 : double parallel_divisor = get_parallel_divisor(&path->path);
2745 :
2746 3780 : path->path.rows =
2747 3780 : clamp_row_est(path->path.rows / parallel_divisor);
2748 : }
2749 :
2750 : /*
2751 : * We could include disable_cost in the preliminary estimate, but that
2752 : * would amount to optimizing for the case where the join method is
2753 : * disabled, which doesn't seem like the way to bet.
2754 : */
2755 622054 : if (!enable_nestloop)
2756 1812 : startup_cost += disable_cost;
2757 :
2758 : /* cost of inner-relation source data (we already dealt with outer rel) */
2759 :
2760 622054 : if (path->jointype == JOIN_SEMI || path->jointype == JOIN_ANTI ||
2761 597656 : extra->inner_unique)
2762 390940 : {
2763 : /*
2764 : * With a SEMI or ANTI join, or if the innerrel is known unique, the
2765 : * executor will stop after the first match.
2766 : */
2767 390940 : Cost inner_run_cost = workspace->inner_run_cost;
2768 390940 : Cost inner_rescan_run_cost = workspace->inner_rescan_run_cost;
2769 : double outer_matched_rows;
2770 : double outer_unmatched_rows;
2771 : Selectivity inner_scan_frac;
2772 :
2773 : /*
2774 : * For an outer-rel row that has at least one match, we can expect the
2775 : * inner scan to stop after a fraction 1/(match_count+1) of the inner
2776 : * rows, if the matches are evenly distributed. Since they probably
2777 : * aren't quite evenly distributed, we apply a fuzz factor of 2.0 to
2778 : * that fraction. (If we used a larger fuzz factor, we'd have to
2779 : * clamp inner_scan_frac to at most 1.0; but since match_count is at
2780 : * least 1, no such clamp is needed now.)
2781 : */
2782 390940 : outer_matched_rows = rint(outer_path_rows * extra->semifactors.outer_match_frac);
2783 390940 : outer_unmatched_rows = outer_path_rows - outer_matched_rows;
2784 390940 : inner_scan_frac = 2.0 / (extra->semifactors.match_count + 1.0);
2785 :
2786 : /*
2787 : * Compute number of tuples processed (not number emitted!). First,
2788 : * account for successfully-matched outer rows.
2789 : */
2790 390940 : ntuples = outer_matched_rows * inner_path_rows * inner_scan_frac;
2791 :
2792 : /*
2793 : * Now we need to estimate the actual costs of scanning the inner
2794 : * relation, which may be quite a bit less than N times inner_run_cost
2795 : * due to early scan stops. We consider two cases. If the inner path
2796 : * is an indexscan using all the joinquals as indexquals, then an
2797 : * unmatched outer row results in an indexscan returning no rows,
2798 : * which is probably quite cheap. Otherwise, the executor will have
2799 : * to scan the whole inner rel for an unmatched row; not so cheap.
2800 : */
2801 390940 : if (has_indexed_join_quals(path))
2802 : {
2803 : /*
2804 : * Successfully-matched outer rows will only require scanning
2805 : * inner_scan_frac of the inner relation. In this case, we don't
2806 : * need to charge the full inner_run_cost even when that's more
2807 : * than inner_rescan_run_cost, because we can assume that none of
2808 : * the inner scans ever scan the whole inner relation. So it's
2809 : * okay to assume that all the inner scan executions can be
2810 : * fractions of the full cost, even if materialization is reducing
2811 : * the rescan cost. At this writing, it's impossible to get here
2812 : * for a materialized inner scan, so inner_run_cost and
2813 : * inner_rescan_run_cost will be the same anyway; but just in
2814 : * case, use inner_run_cost for the first matched tuple and
2815 : * inner_rescan_run_cost for additional ones.
2816 : */
2817 83396 : run_cost += inner_run_cost * inner_scan_frac;
2818 83396 : if (outer_matched_rows > 1)
2819 4576 : run_cost += (outer_matched_rows - 1) * inner_rescan_run_cost * inner_scan_frac;
2820 :
2821 : /*
2822 : * Add the cost of inner-scan executions for unmatched outer rows.
2823 : * We estimate this as the same cost as returning the first tuple
2824 : * of a nonempty scan. We consider that these are all rescans,
2825 : * since we used inner_run_cost once already.
2826 : */
2827 166792 : run_cost += outer_unmatched_rows *
2828 83396 : inner_rescan_run_cost / inner_path_rows;
2829 :
2830 : /*
2831 : * We won't be evaluating any quals at all for unmatched rows, so
2832 : * don't add them to ntuples.
2833 : */
2834 : }
2835 : else
2836 : {
2837 : /*
2838 : * Here, a complicating factor is that rescans may be cheaper than
2839 : * first scans. If we never scan all the way to the end of the
2840 : * inner rel, it might be (depending on the plan type) that we'd
2841 : * never pay the whole inner first-scan run cost. However it is
2842 : * difficult to estimate whether that will happen (and it could
2843 : * not happen if there are any unmatched outer rows!), so be
2844 : * conservative and always charge the whole first-scan cost once.
2845 : * We consider this charge to correspond to the first unmatched
2846 : * outer row, unless there isn't one in our estimate, in which
2847 : * case blame it on the first matched row.
2848 : */
2849 :
2850 : /* First, count all unmatched join tuples as being processed */
2851 307544 : ntuples += outer_unmatched_rows * inner_path_rows;
2852 :
2853 : /* Now add the forced full scan, and decrement appropriate count */
2854 307544 : run_cost += inner_run_cost;
2855 307544 : if (outer_unmatched_rows >= 1)
2856 236544 : outer_unmatched_rows -= 1;
2857 : else
2858 71000 : outer_matched_rows -= 1;
2859 :
2860 : /* Add inner run cost for additional outer tuples having matches */
2861 307544 : if (outer_matched_rows > 0)
2862 90454 : run_cost += outer_matched_rows * inner_rescan_run_cost * inner_scan_frac;
2863 :
2864 : /* Add inner run cost for additional unmatched outer tuples */
2865 307544 : if (outer_unmatched_rows > 0)
2866 146600 : run_cost += outer_unmatched_rows * inner_rescan_run_cost;
2867 : }
2868 : }
2869 : else
2870 : {
2871 : /* Normal-case source costs were included in preliminary estimate */
2872 :
2873 : /* Compute number of tuples processed (not number emitted!) */
2874 231114 : ntuples = outer_path_rows * inner_path_rows;
2875 : }
2876 :
2877 : /* CPU costs */
2878 622054 : cost_qual_eval(&restrict_qual_cost, path->joinrestrictinfo, root);
2879 622054 : startup_cost += restrict_qual_cost.startup;
2880 622054 : cpu_per_tuple = cpu_tuple_cost + restrict_qual_cost.per_tuple;
2881 622054 : run_cost += cpu_per_tuple * ntuples;
2882 :
2883 : /* tlist eval costs are paid per output row, not per tuple scanned */
2884 622054 : startup_cost += path->path.pathtarget->cost.startup;
2885 622054 : run_cost += path->path.pathtarget->cost.per_tuple * path->path.rows;
2886 :
2887 622054 : path->path.startup_cost = startup_cost;
2888 622054 : path->path.total_cost = startup_cost + run_cost;
2889 622054 : }
2890 :
2891 : /*
2892 : * initial_cost_mergejoin
2893 : * Preliminary estimate of the cost of a mergejoin path.
2894 : *
2895 : * This must quickly produce lower-bound estimates of the path's startup and
2896 : * total costs. If we are unable to eliminate the proposed path from
2897 : * consideration using the lower bounds, final_cost_mergejoin will be called
2898 : * to obtain the final estimates.
2899 : *
2900 : * The exact division of labor between this function and final_cost_mergejoin
2901 : * is private to them, and represents a tradeoff between speed of the initial
2902 : * estimate and getting a tight lower bound. We choose to not examine the
2903 : * join quals here, except for obtaining the scan selectivity estimate which
2904 : * is really essential (but fortunately, use of caching keeps the cost of
2905 : * getting that down to something reasonable).
2906 : * We also assume that cost_sort is cheap enough to use here.
2907 : *
2908 : * 'workspace' is to be filled with startup_cost, total_cost, and perhaps
2909 : * other data to be used by final_cost_mergejoin
2910 : * 'jointype' is the type of join to be performed
2911 : * 'mergeclauses' is the list of joinclauses to be used as merge clauses
2912 : * 'outer_path' is the outer input to the join
2913 : * 'inner_path' is the inner input to the join
2914 : * 'outersortkeys' is the list of sort keys for the outer path
2915 : * 'innersortkeys' is the list of sort keys for the inner path
2916 : * 'extra' contains miscellaneous information about the join
2917 : *
2918 : * Note: outersortkeys and innersortkeys should be NIL if no explicit
2919 : * sort is needed because the respective source path is already ordered.
2920 : */
2921 : void
2922 533864 : initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
2923 : JoinType jointype,
2924 : List *mergeclauses,
2925 : Path *outer_path, Path *inner_path,
2926 : List *outersortkeys, List *innersortkeys,
2927 : JoinPathExtraData *extra)
2928 : {
2929 533864 : Cost startup_cost = 0;
2930 533864 : Cost run_cost = 0;
2931 533864 : double outer_path_rows = outer_path->rows;
2932 533864 : double inner_path_rows = inner_path->rows;
2933 : Cost inner_run_cost;
2934 : double outer_rows,
2935 : inner_rows,
2936 : outer_skip_rows,
2937 : inner_skip_rows;
2938 : Selectivity outerstartsel,
2939 : outerendsel,
2940 : innerstartsel,
2941 : innerendsel;
2942 : Path sort_path; /* dummy for result of cost_sort */
2943 :
2944 : /* Protect some assumptions below that rowcounts aren't zero or NaN */
2945 533864 : if (outer_path_rows <= 0 || isnan(outer_path_rows))
2946 32 : outer_path_rows = 1;
2947 533864 : if (inner_path_rows <= 0 || isnan(inner_path_rows))
2948 76 : inner_path_rows = 1;
2949 :
2950 : /*
2951 : * A merge join will stop as soon as it exhausts either input stream
2952 : * (unless it's an outer join, in which case the outer side has to be
2953 : * scanned all the way anyway). Estimate fraction of the left and right
2954 : * inputs that will actually need to be scanned. Likewise, we can
2955 : * estimate the number of rows that will be skipped before the first join
2956 : * pair is found, which should be factored into startup cost. We use only
2957 : * the first (most significant) merge clause for this purpose. Since
2958 : * mergejoinscansel() is a fairly expensive computation, we cache the
2959 : * results in the merge clause RestrictInfo.
2960 : */
2961 533864 : if (mergeclauses && jointype != JOIN_FULL)
2962 529858 : {
2963 529858 : RestrictInfo *firstclause = (RestrictInfo *) linitial(mergeclauses);
2964 : List *opathkeys;
2965 : List *ipathkeys;
2966 : PathKey *opathkey;
2967 : PathKey *ipathkey;
2968 : MergeScanSelCache *cache;
2969 :
2970 : /* Get the input pathkeys to determine the sort-order details */
2971 529858 : opathkeys = outersortkeys ? outersortkeys : outer_path->pathkeys;
2972 529858 : ipathkeys = innersortkeys ? innersortkeys : inner_path->pathkeys;
2973 : Assert(opathkeys);
2974 : Assert(ipathkeys);
2975 529858 : opathkey = (PathKey *) linitial(opathkeys);
2976 529858 : ipathkey = (PathKey *) linitial(ipathkeys);
2977 : /* debugging check */
2978 529858 : if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
2979 529858 : opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation ||
2980 529858 : opathkey->pk_strategy != ipathkey->pk_strategy ||
2981 529858 : opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
2982 0 : elog(ERROR, "left and right pathkeys do not match in mergejoin");
2983 :
2984 : /* Get the selectivity with caching */
2985 529858 : cache = cached_scansel(root, firstclause, opathkey);
2986 :
2987 529858 : if (bms_is_subset(firstclause->left_relids,
2988 529858 : outer_path->parent->relids))
2989 : {
2990 : /* left side of clause is outer */
2991 266338 : outerstartsel = cache->leftstartsel;
2992 266338 : outerendsel = cache->leftendsel;
2993 266338 : innerstartsel = cache->rightstartsel;
2994 266338 : innerendsel = cache->rightendsel;
2995 : }
2996 : else
2997 : {
2998 : /* left side of clause is inner */
2999 263520 : outerstartsel = cache->rightstartsel;
3000 263520 : outerendsel = cache->rightendsel;
3001 263520 : innerstartsel = cache->leftstartsel;
3002 263520 : innerendsel = cache->leftendsel;
3003 : }
3004 529858 : if (jointype == JOIN_LEFT ||
3005 : jointype == JOIN_ANTI)
3006 : {
3007 127464 : outerstartsel = 0.0;
3008 127464 : outerendsel = 1.0;
3009 : }
3010 402394 : else if (jointype == JOIN_RIGHT)
3011 : {
3012 93878 : innerstartsel = 0.0;
3013 93878 : innerendsel = 1.0;
3014 : }
3015 : }
3016 : else
3017 : {
3018 : /* cope with clauseless or full mergejoin */
3019 4006 : outerstartsel = innerstartsel = 0.0;
3020 4006 : outerendsel = innerendsel = 1.0;
3021 : }
3022 :
3023 : /*
3024 : * Convert selectivities to row counts. We force outer_rows and
3025 : * inner_rows to be at least 1, but the skip_rows estimates can be zero.
3026 : */
3027 533864 : outer_skip_rows = rint(outer_path_rows * outerstartsel);
3028 533864 : inner_skip_rows = rint(inner_path_rows * innerstartsel);
3029 533864 : outer_rows = clamp_row_est(outer_path_rows * outerendsel);
3030 533864 : inner_rows = clamp_row_est(inner_path_rows * innerendsel);
3031 :
3032 : Assert(outer_skip_rows <= outer_rows);
3033 : Assert(inner_skip_rows <= inner_rows);
3034 :
3035 : /*
3036 : * Readjust scan selectivities to account for above rounding. This is
3037 : * normally an insignificant effect, but when there are only a few rows in
3038 : * the inputs, failing to do this makes for a large percentage error.
3039 : */
3040 533864 : outerstartsel = outer_skip_rows / outer_path_rows;
3041 533864 : innerstartsel = inner_skip_rows / inner_path_rows;
3042 533864 : outerendsel = outer_rows / outer_path_rows;
3043 533864 : innerendsel = inner_rows / inner_path_rows;
3044 :
3045 : Assert(outerstartsel <= outerendsel);
3046 : Assert(innerstartsel <= innerendsel);
3047 :
3048 : /* cost of source data */
3049 :
3050 533864 : if (outersortkeys) /* do we need to sort outer? */
3051 : {
3052 480552 : cost_sort(&sort_path,
3053 : root,
3054 : outersortkeys,
3055 : outer_path->total_cost,
3056 : outer_path_rows,
3057 240276 : outer_path->pathtarget->width,
3058 : 0.0,
3059 : work_mem,
3060 : -1.0);
3061 240276 : startup_cost += sort_path.startup_cost;
3062 480552 : startup_cost += (sort_path.total_cost - sort_path.startup_cost)
3063 240276 : * outerstartsel;
3064 480552 : run_cost += (sort_path.total_cost - sort_path.startup_cost)
3065 240276 : * (outerendsel - outerstartsel);
3066 : }
3067 : else
3068 : {
3069 293588 : startup_cost += outer_path->startup_cost;
3070 587176 : startup_cost += (outer_path->total_cost - outer_path->startup_cost)
3071 293588 : * outerstartsel;
3072 587176 : run_cost += (outer_path->total_cost - outer_path->startup_cost)
3073 293588 : * (outerendsel - outerstartsel);
3074 : }
3075 :
3076 533864 : if (innersortkeys) /* do we need to sort inner? */
3077 : {
3078 821340 : cost_sort(&sort_path,
3079 : root,
3080 : innersortkeys,
3081 : inner_path->total_cost,
3082 : inner_path_rows,
3083 410670 : inner_path->pathtarget->width,
3084 : 0.0,
3085 : work_mem,
3086 : -1.0);
3087 410670 : startup_cost += sort_path.startup_cost;
3088 821340 : startup_cost += (sort_path.total_cost - sort_path.startup_cost)
3089 410670 : * innerstartsel;
3090 821340 : inner_run_cost = (sort_path.total_cost - sort_path.startup_cost)
3091 410670 : * (innerendsel - innerstartsel);
3092 : }
3093 : else
3094 : {
3095 123194 : startup_cost += inner_path->startup_cost;
3096 246388 : startup_cost += (inner_path->total_cost - inner_path->startup_cost)
3097 123194 : * innerstartsel;
3098 246388 : inner_run_cost = (inner_path->total_cost - inner_path->startup_cost)
3099 123194 : * (innerendsel - innerstartsel);
3100 : }
3101 :
3102 : /*
3103 : * We can't yet determine whether rescanning occurs, or whether
3104 : * materialization of the inner input should be done. The minimum
3105 : * possible inner input cost, regardless of rescan and materialization
3106 : * considerations, is inner_run_cost. We include that in
3107 : * workspace->total_cost, but not yet in run_cost.
3108 : */
3109 :
3110 : /* CPU costs left for later */
3111 :
3112 : /* Public result fields */
3113 533864 : workspace->startup_cost = startup_cost;
3114 533864 : workspace->total_cost = startup_cost + run_cost + inner_run_cost;
3115 : /* Save private data for final_cost_mergejoin */
3116 533864 : workspace->run_cost = run_cost;
3117 533864 : workspace->inner_run_cost = inner_run_cost;
3118 533864 : workspace->outer_rows = outer_rows;
3119 533864 : workspace->inner_rows = inner_rows;
3120 533864 : workspace->outer_skip_rows = outer_skip_rows;
3121 533864 : workspace->inner_skip_rows = inner_skip_rows;
3122 533864 : }
3123 :
3124 : /*
3125 : * final_cost_mergejoin
3126 : * Final estimate of the cost and result size of a mergejoin path.
3127 : *
3128 : * Unlike other costsize functions, this routine makes two actual decisions:
3129 : * whether the executor will need to do mark/restore, and whether we should
3130 : * materialize the inner path. It would be logically cleaner to build
3131 : * separate paths testing these alternatives, but that would require repeating
3132 : * most of the cost calculations, which are not all that cheap. Since the
3133 : * choice will not affect output pathkeys or startup cost, only total cost,
3134 : * there is no possibility of wanting to keep more than one path. So it seems
3135 : * best to make the decisions here and record them in the path's
3136 : * skip_mark_restore and materialize_inner fields.
3137 : *
3138 : * Mark/restore overhead is usually required, but can be skipped if we know
3139 : * that the executor need find only one match per outer tuple, and that the
3140 : * mergeclauses are sufficient to identify a match.
3141 : *
3142 : * We materialize the inner path if we need mark/restore and either the inner
3143 : * path can't support mark/restore, or it's cheaper to use an interposed
3144 : * Material node to handle mark/restore.
3145 : *
3146 : * 'path' is already filled in except for the rows and cost fields and
3147 : * skip_mark_restore and materialize_inner
3148 : * 'workspace' is the result from initial_cost_mergejoin
3149 : * 'extra' contains miscellaneous information about the join
3150 : */
3151 : void
3152 135724 : final_cost_mergejoin(PlannerInfo *root, MergePath *path,
3153 : JoinCostWorkspace *workspace,
3154 : JoinPathExtraData *extra)
3155 : {
3156 135724 : Path *outer_path = path->jpath.outerjoinpath;
3157 135724 : Path *inner_path = path->jpath.innerjoinpath;
3158 135724 : double inner_path_rows = inner_path->rows;
3159 135724 : List *mergeclauses = path->path_mergeclauses;
3160 135724 : List *innersortkeys = path->innersortkeys;
3161 135724 : Cost startup_cost = workspace->startup_cost;
3162 135724 : Cost run_cost = workspace->run_cost;
3163 135724 : Cost inner_run_cost = workspace->inner_run_cost;
3164 135724 : double outer_rows = workspace->outer_rows;
3165 135724 : double inner_rows = workspace->inner_rows;
3166 135724 : double outer_skip_rows = workspace->outer_skip_rows;
3167 135724 : double inner_skip_rows = workspace->inner_skip_rows;
3168 : Cost cpu_per_tuple,
3169 : bare_inner_cost,
3170 : mat_inner_cost;
3171 : QualCost merge_qual_cost;
3172 : QualCost qp_qual_cost;
3173 : double mergejointuples,
3174 : rescannedtuples;
3175 : double rescanratio;
3176 :
3177 : /* Protect some assumptions below that rowcounts aren't zero or NaN */
3178 135724 : if (inner_path_rows <= 0 || isnan(inner_path_rows))
3179 52 : inner_path_rows = 1;
3180 :
3181 : /* Mark the path with the correct row estimate */
3182 135724 : if (path->jpath.path.param_info)
3183 412 : path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
3184 : else
3185 135312 : path->jpath.path.rows = path->jpath.path.parent->rows;
3186 :
3187 : /* For partial paths, scale row estimate. */
3188 135724 : if (path->jpath.path.parallel_workers > 0)
3189 : {
3190 5924 : double parallel_divisor = get_parallel_divisor(&path->jpath.path);
3191 :
3192 5924 : path->jpath.path.rows =
3193 5924 : clamp_row_est(path->jpath.path.rows / parallel_divisor);
3194 : }
3195 :
3196 : /*
3197 : * We could include disable_cost in the preliminary estimate, but that
3198 : * would amount to optimizing for the case where the join method is
3199 : * disabled, which doesn't seem like the way to bet.
3200 : */
3201 135724 : if (!enable_mergejoin)
3202 0 : startup_cost += disable_cost;
3203 :
3204 : /*
3205 : * Compute cost of the mergequals and qpquals (other restriction clauses)
3206 : * separately.
3207 : */
3208 135724 : cost_qual_eval(&merge_qual_cost, mergeclauses, root);
3209 135724 : cost_qual_eval(&qp_qual_cost, path->jpath.joinrestrictinfo, root);
3210 135724 : qp_qual_cost.startup -= merge_qual_cost.startup;
3211 135724 : qp_qual_cost.per_tuple -= merge_qual_cost.per_tuple;
3212 :
3213 : /*
3214 : * With a SEMI or ANTI join, or if the innerrel is known unique, the
3215 : * executor will stop scanning for matches after the first match. When
3216 : * all the joinclauses are merge clauses, this means we don't ever need to
3217 : * back up the merge, and so we can skip mark/restore overhead.
3218 : */
3219 135724 : if ((path->jpath.jointype == JOIN_SEMI ||
3220 134154 : path->jpath.jointype == JOIN_ANTI ||
3221 191578 : extra->inner_unique) &&
3222 62392 : (list_length(path->jpath.joinrestrictinfo) ==
3223 62392 : list_length(path->path_mergeclauses)))
3224 55964 : path->skip_mark_restore = true;
3225 : else
3226 79760 : path->skip_mark_restore = false;
3227 :
3228 : /*
3229 : * Get approx # tuples passing the mergequals. We use approx_tuple_count
3230 : * here because we need an estimate done with JOIN_INNER semantics.
3231 : */
3232 135724 : mergejointuples = approx_tuple_count(root, &path->jpath, mergeclauses);
3233 :
3234 : /*
3235 : * When there are equal merge keys in the outer relation, the mergejoin
3236 : * must rescan any matching tuples in the inner relation. This means
3237 : * re-fetching inner tuples; we have to estimate how often that happens.
3238 : *
3239 : * For regular inner and outer joins, the number of re-fetches can be
3240 : * estimated approximately as size of merge join output minus size of
3241 : * inner relation. Assume that the distinct key values are 1, 2, ..., and
3242 : * denote the number of values of each key in the outer relation as m1,
3243 : * m2, ...; in the inner relation, n1, n2, ... Then we have
3244 : *
3245 : * size of join = m1 * n1 + m2 * n2 + ...
3246 : *
3247 : * number of rescanned tuples = (m1 - 1) * n1 + (m2 - 1) * n2 + ... = m1 *
3248 : * n1 + m2 * n2 + ... - (n1 + n2 + ...) = size of join - size of inner
3249 : * relation
3250 : *
3251 : * This equation works correctly for outer tuples having no inner match
3252 : * (nk = 0), but not for inner tuples having no outer match (mk = 0); we
3253 : * are effectively subtracting those from the number of rescanned tuples,
3254 : * when we should not. Can we do better without expensive selectivity
3255 : * computations?
3256 : *
3257 : * The whole issue is moot if we are working from a unique-ified outer
3258 : * input, or if we know we don't need to mark/restore at all.
3259 : */
3260 135724 : if (IsA(outer_path, UniquePath) || path->skip_mark_restore)
3261 56278 : rescannedtuples = 0;
3262 : else
3263 : {
3264 79446 : rescannedtuples = mergejointuples - inner_path_rows;
3265 : /* Must clamp because of possible underestimate */
3266 79446 : if (rescannedtuples < 0)
3267 39874 : rescannedtuples = 0;
3268 : }
3269 :
3270 : /*
3271 : * We'll inflate various costs this much to account for rescanning. Note
3272 : * that this is to be multiplied by something involving inner_rows, or
3273 : * another number related to the portion of the inner rel we'll scan.
3274 : */
3275 135724 : rescanratio = 1.0 + (rescannedtuples / inner_rows);
3276 :
3277 : /*
3278 : * Decide whether we want to materialize the inner input to shield it from
3279 : * mark/restore and performing re-fetches. Our cost model for regular
3280 : * re-fetches is that a re-fetch costs the same as an original fetch,
3281 : * which is probably an overestimate; but on the other hand we ignore the
3282 : * bookkeeping costs of mark/restore. Not clear if it's worth developing
3283 : * a more refined model. So we just need to inflate the inner run cost by
3284 : * rescanratio.
3285 : */
3286 135724 : bare_inner_cost = inner_run_cost * rescanratio;
3287 :
3288 : /*
3289 : * When we interpose a Material node the re-fetch cost is assumed to be
3290 : * just cpu_operator_cost per tuple, independently of the underlying
3291 : * plan's cost; and we charge an extra cpu_operator_cost per original
3292 : * fetch as well. Note that we're assuming the materialize node will
3293 : * never spill to disk, since it only has to remember tuples back to the
3294 : * last mark. (If there are a huge number of duplicates, our other cost
3295 : * factors will make the path so expensive that it probably won't get
3296 : * chosen anyway.) So we don't use cost_rescan here.
3297 : *
3298 : * Note: keep this estimate in sync with create_mergejoin_plan's labeling
3299 : * of the generated Material node.
3300 : */
3301 135724 : mat_inner_cost = inner_run_cost +
3302 135724 : cpu_operator_cost * inner_rows * rescanratio;
3303 :
3304 : /*
3305 : * If we don't need mark/restore at all, we don't need materialization.
3306 : */
3307 135724 : if (path->skip_mark_restore)
3308 55964 : path->materialize_inner = false;
3309 :
3310 : /*
3311 : * Prefer materializing if it looks cheaper, unless the user has asked to
3312 : * suppress materialization.
3313 : */
3314 79760 : else if (enable_material && mat_inner_cost < bare_inner_cost)
3315 1004 : path->materialize_inner = true;
3316 :
3317 : /*
3318 : * Even if materializing doesn't look cheaper, we *must* do it if the
3319 : * inner path is to be used directly (without sorting) and it doesn't
3320 : * support mark/restore.
3321 : *
3322 : * Since the inner side must be ordered, and only Sorts and IndexScans can
3323 : * create order to begin with, and they both support mark/restore, you
3324 : * might think there's no problem --- but you'd be wrong. Nestloop and
3325 : * merge joins can *preserve* the order of their inputs, so they can be
3326 : * selected as the input of a mergejoin, and they don't support
3327 : * mark/restore at present.
3328 : *
3329 : * We don't test the value of enable_material here, because
3330 : * materialization is required for correctness in this case, and turning
3331 : * it off does not entitle us to deliver an invalid plan.
3332 : */
3333 78756 : else if (innersortkeys == NIL &&
3334 3102 : !ExecSupportsMarkRestore(inner_path))
3335 838 : path->materialize_inner = true;
3336 :
3337 : /*
3338 : * Also, force materializing if the inner path is to be sorted and the
3339 : * sort is expected to spill to disk. This is because the final merge
3340 : * pass can be done on-the-fly if it doesn't have to support mark/restore.
3341 : * We don't try to adjust the cost estimates for this consideration,
3342 : * though.
3343 : *
3344 : * Since materialization is a performance optimization in this case,
3345 : * rather than necessary for correctness, we skip it if enable_material is
3346 : * off.
3347 : */
3348 77918 : else if (enable_material && innersortkeys != NIL &&
3349 75622 : relation_byte_size(inner_path_rows,
3350 75622 : inner_path->pathtarget->width) >
3351 75622 : (work_mem * 1024L))
3352 140 : path->materialize_inner = true;
3353 : else
3354 77778 : path->materialize_inner = false;
3355 :
3356 : /* Charge the right incremental cost for the chosen case */
3357 135724 : if (path->materialize_inner)
3358 1982 : run_cost += mat_inner_cost;
3359 : else
3360 133742 : run_cost += bare_inner_cost;
3361 :
3362 : /* CPU costs */
3363 :
3364 : /*
3365 : * The number of tuple comparisons needed is approximately number of outer
3366 : * rows plus number of inner rows plus number of rescanned tuples (can we
3367 : * refine this?). At each one, we need to evaluate the mergejoin quals.
3368 : */
3369 135724 : startup_cost += merge_qual_cost.startup;
3370 271448 : startup_cost += merge_qual_cost.per_tuple *
3371 135724 : (outer_skip_rows + inner_skip_rows * rescanratio);
3372 271448 : run_cost += merge_qual_cost.per_tuple *
3373 271448 : ((outer_rows - outer_skip_rows) +
3374 135724 : (inner_rows - inner_skip_rows) * rescanratio);
3375 :
3376 : /*
3377 : * For each tuple that gets through the mergejoin proper, we charge
3378 : * cpu_tuple_cost plus the cost of evaluating additional restriction
3379 : * clauses that are to be applied at the join. (This is pessimistic since
3380 : * not all of the quals may get evaluated at each tuple.)
3381 : *
3382 : * Note: we could adjust for SEMI/ANTI joins skipping some qual
3383 : * evaluations here, but it's probably not worth the trouble.
3384 : */
3385 135724 : startup_cost += qp_qual_cost.startup;
3386 135724 : cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
3387 135724 : run_cost += cpu_per_tuple * mergejointuples;
3388 :
3389 : /* tlist eval costs are paid per output row, not per tuple scanned */
3390 135724 : startup_cost += path->jpath.path.pathtarget->cost.startup;
3391 135724 : run_cost += path->jpath.path.pathtarget->cost.per_tuple * path->jpath.path.rows;
3392 :
3393 135724 : path->jpath.path.startup_cost = startup_cost;
3394 135724 : path->jpath.path.total_cost = startup_cost + run_cost;
3395 135724 : }
3396 :
3397 : /*
3398 : * run mergejoinscansel() with caching
3399 : */
3400 : static MergeScanSelCache *
3401 529858 : cached_scansel(PlannerInfo *root, RestrictInfo *rinfo, PathKey *pathkey)
3402 : {
3403 : MergeScanSelCache *cache;
3404 : ListCell *lc;
3405 : Selectivity leftstartsel,
3406 : leftendsel,
3407 : rightstartsel,
3408 : rightendsel;
3409 : MemoryContext oldcontext;
3410 :
3411 : /* Do we have this result already? */
3412 529862 : foreach(lc, rinfo->scansel_cache)
3413 : {
3414 471480 : cache = (MergeScanSelCache *) lfirst(lc);
3415 471480 : if (cache->opfamily == pathkey->pk_opfamily &&
3416 471480 : cache->collation == pathkey->pk_eclass->ec_collation &&
3417 471480 : cache->strategy == pathkey->pk_strategy &&
3418 471476 : cache->nulls_first == pathkey->pk_nulls_first)
3419 471476 : return cache;
3420 : }
3421 :
3422 : /* Nope, do the computation */
3423 116764 : mergejoinscansel(root,
3424 58382 : (Node *) rinfo->clause,
3425 : pathkey->pk_opfamily,
3426 : pathkey->pk_strategy,
3427 58382 : pathkey->pk_nulls_first,
3428 : &leftstartsel,
3429 : &leftendsel,
3430 : &rightstartsel,
3431 : &rightendsel);
3432 :
3433 : /* Cache the result in suitably long-lived workspace */
3434 58382 : oldcontext = MemoryContextSwitchTo(root->planner_cxt);
3435 :
3436 58382 : cache = (MergeScanSelCache *) palloc(sizeof(MergeScanSelCache));
3437 58382 : cache->opfamily = pathkey->pk_opfamily;
3438 58382 : cache->collation = pathkey->pk_eclass->ec_collation;
3439 58382 : cache->strategy = pathkey->pk_strategy;
3440 58382 : cache->nulls_first = pathkey->pk_nulls_first;
3441 58382 : cache->leftstartsel = leftstartsel;
3442 58382 : cache->leftendsel = leftendsel;
3443 58382 : cache->rightstartsel = rightstartsel;
3444 58382 : cache->rightendsel = rightendsel;
3445 :
3446 58382 : rinfo->scansel_cache = lappend(rinfo->scansel_cache, cache);
3447 :
3448 58382 : MemoryContextSwitchTo(oldcontext);
3449 :
3450 58382 : return cache;
3451 : }
3452 :
3453 : /*
3454 : * initial_cost_hashjoin
3455 : * Preliminary estimate of the cost of a hashjoin path.
3456 : *
3457 : * This must quickly produce lower-bound estimates of the path's startup and
3458 : * total costs. If we are unable to eliminate the proposed path from
3459 : * consideration using the lower bounds, final_cost_hashjoin will be called
3460 : * to obtain the final estimates.
3461 : *
3462 : * The exact division of labor between this function and final_cost_hashjoin
3463 : * is private to them, and represents a tradeoff between speed of the initial
3464 : * estimate and getting a tight lower bound. We choose to not examine the
3465 : * join quals here (other than by counting the number of hash clauses),
3466 : * so we can't do much with CPU costs. We do assume that
3467 : * ExecChooseHashTableSize is cheap enough to use here.
3468 : *
3469 : * 'workspace' is to be filled with startup_cost, total_cost, and perhaps
3470 : * other data to be used by final_cost_hashjoin
3471 : * 'jointype' is the type of join to be performed
3472 : * 'hashclauses' is the list of joinclauses to be used as hash clauses
3473 : * 'outer_path' is the outer input to the join
3474 : * 'inner_path' is the inner input to the join
3475 : * 'extra' contains miscellaneous information about the join
3476 : * 'parallel_hash' indicates that inner_path is partial and that a shared
3477 : * hash table will be built in parallel
3478 : */
3479 : void
3480 289506 : initial_cost_hashjoin(PlannerInfo *root, JoinCostWorkspace *workspace,
3481 : JoinType jointype,
3482 : List *hashclauses,
3483 : Path *outer_path, Path *inner_path,
3484 : JoinPathExtraData *extra,
3485 : bool parallel_hash)
3486 : {
3487 289506 : Cost startup_cost = 0;
3488 289506 : Cost run_cost = 0;
3489 289506 : double outer_path_rows = outer_path->rows;
3490 289506 : double inner_path_rows = inner_path->rows;
3491 289506 : double inner_path_rows_total = inner_path_rows;
3492 289506 : int num_hashclauses = list_length(hashclauses);
3493 : int numbuckets;
3494 : int numbatches;
3495 : int num_skew_mcvs;
3496 : size_t space_allowed; /* unused */
3497 :
3498 : /* cost of source data */
3499 289506 : startup_cost += outer_path->startup_cost;
3500 289506 : run_cost += outer_path->total_cost - outer_path->startup_cost;
3501 289506 : startup_cost += inner_path->total_cost;
3502 :
3503 : /*
3504 : * Cost of computing hash function: must do it once per input tuple. We
3505 : * charge one cpu_operator_cost for each column's hash function. Also,
3506 : * tack on one cpu_tuple_cost per inner row, to model the costs of
3507 : * inserting the row into the hashtable.
3508 : *
3509 : * XXX when a hashclause is more complex than a single operator, we really
3510 : * should charge the extra eval costs of the left or right side, as
3511 : * appropriate, here. This seems more work than it's worth at the moment.
3512 : */
3513 579012 : startup_cost += (cpu_operator_cost * num_hashclauses + cpu_tuple_cost)
3514 289506 : * inner_path_rows;
3515 289506 : run_cost += cpu_operator_cost * num_hashclauses * outer_path_rows;
3516 :
3517 : /*
3518 : * If this is a parallel hash build, then the value we have for
3519 : * inner_rows_total currently refers only to the rows returned by each
3520 : * participant. For shared hash table size estimation, we need the total
3521 : * number, so we need to undo the division.
3522 : */
3523 289506 : if (parallel_hash)
3524 4828 : inner_path_rows_total *= get_parallel_divisor(inner_path);
3525 :
3526 : /*
3527 : * Get hash table size that executor would use for inner relation.
3528 : *
3529 : * XXX for the moment, always assume that skew optimization will be
3530 : * performed. As long as SKEW_WORK_MEM_PERCENT is small, it's not worth
3531 : * trying to determine that for sure.
3532 : *
3533 : * XXX at some point it might be interesting to try to account for skew
3534 : * optimization in the cost estimate, but for now, we don't.
3535 : */
3536 579012 : ExecChooseHashTableSize(inner_path_rows_total,
3537 289506 : inner_path->pathtarget->width,
3538 : true, /* useskew */
3539 : parallel_hash, /* try_combined_work_mem */
3540 : outer_path->parallel_workers,
3541 : &space_allowed,
3542 : &numbuckets,
3543 : &numbatches,
3544 : &num_skew_mcvs);
3545 :
3546 : /*
3547 : * If inner relation is too big then we will need to "batch" the join,
3548 : * which implies writing and reading most of the tuples to disk an extra
3549 : * time. Charge seq_page_cost per page, since the I/O should be nice and
3550 : * sequential. Writing the inner rel counts as startup cost, all the rest
3551 : * as run cost.
3552 : */
3553 289506 : if (numbatches > 1)
3554 : {
3555 2120 : double outerpages = page_size(outer_path_rows,
3556 2120 : outer_path->pathtarget->width);
3557 2120 : double innerpages = page_size(inner_path_rows,
3558 2120 : inner_path->pathtarget->width);
3559 :
3560 2120 : startup_cost += seq_page_cost * innerpages;
3561 2120 : run_cost += seq_page_cost * (innerpages + 2 * outerpages);
3562 : }
3563 :
3564 : /* CPU costs left for later */
3565 :
3566 : /* Public result fields */
3567 289506 : workspace->startup_cost = startup_cost;
3568 289506 : workspace->total_cost = startup_cost + run_cost;
3569 : /* Save private data for final_cost_hashjoin */
3570 289506 : workspace->run_cost = run_cost;
3571 289506 : workspace->numbuckets = numbuckets;
3572 289506 : workspace->numbatches = numbatches;
3573 289506 : workspace->inner_rows_total = inner_path_rows_total;
3574 289506 : }
3575 :
3576 : /*
3577 : * final_cost_hashjoin
3578 : * Final estimate of the cost and result size of a hashjoin path.
3579 : *
3580 : * Note: the numbatches estimate is also saved into 'path' for use later
3581 : *
3582 : * 'path' is already filled in except for the rows and cost fields and
3583 : * num_batches
3584 : * 'workspace' is the result from initial_cost_hashjoin
3585 : * 'extra' contains miscellaneous information about the join
3586 : */
3587 : void
3588 148994 : final_cost_hashjoin(PlannerInfo *root, HashPath *path,
3589 : JoinCostWorkspace *workspace,
3590 : JoinPathExtraData *extra)
3591 : {
3592 148994 : Path *outer_path = path->jpath.outerjoinpath;
3593 148994 : Path *inner_path = path->jpath.innerjoinpath;
3594 148994 : double outer_path_rows = outer_path->rows;
3595 148994 : double inner_path_rows = inner_path->rows;
3596 148994 : double inner_path_rows_total = workspace->inner_rows_total;
3597 148994 : List *hashclauses = path->path_hashclauses;
3598 148994 : Cost startup_cost = workspace->startup_cost;
3599 148994 : Cost run_cost = workspace->run_cost;
3600 148994 : int numbuckets = workspace->numbuckets;
3601 148994 : int numbatches = workspace->numbatches;
3602 : Cost cpu_per_tuple;
3603 : QualCost hash_qual_cost;
3604 : QualCost qp_qual_cost;
3605 : double hashjointuples;
3606 : double virtualbuckets;
3607 : Selectivity innerbucketsize;
3608 : Selectivity innermcvfreq;
3609 : ListCell *hcl;
3610 :
3611 : /* Mark the path with the correct row estimate */
3612 148994 : if (path->jpath.path.param_info)
3613 802 : path->jpath.path.rows = path->jpath.path.param_info->ppi_rows;
3614 : else
3615 148192 : path->jpath.path.rows = path->jpath.path.parent->rows;
3616 :
3617 : /* For partial paths, scale row estimate. */
3618 148994 : if (path->jpath.path.parallel_workers > 0)
3619 : {
3620 4508 : double parallel_divisor = get_parallel_divisor(&path->jpath.path);
3621 :
3622 4508 : path->jpath.path.rows =
3623 4508 : clamp_row_est(path->jpath.path.rows / parallel_divisor);
3624 : }
3625 :
3626 : /*
3627 : * We could include disable_cost in the preliminary estimate, but that
3628 : * would amount to optimizing for the case where the join method is
3629 : * disabled, which doesn't seem like the way to bet.
3630 : */
3631 148994 : if (!enable_hashjoin)
3632 76 : startup_cost += disable_cost;
3633 :
3634 : /* mark the path with estimated # of batches */
3635 148994 : path->num_batches = numbatches;
3636 :
3637 : /* store the total number of tuples (sum of partial row estimates) */
3638 148994 : path->inner_rows_total = inner_path_rows_total;
3639 :
3640 : /* and compute the number of "virtual" buckets in the whole join */
3641 148994 : virtualbuckets = (double) numbuckets * (double) numbatches;
3642 :
3643 : /*
3644 : * Determine bucketsize fraction and MCV frequency for the inner relation.
3645 : * We use the smallest bucketsize or MCV frequency estimated for any
3646 : * individual hashclause; this is undoubtedly conservative.
3647 : *
3648 : * BUT: if inner relation has been unique-ified, we can assume it's good
3649 : * for hashing. This is important both because it's the right answer, and
3650 : * because we avoid contaminating the cache with a value that's wrong for
3651 : * non-unique-ified paths.
3652 : */
3653 148994 : if (IsA(inner_path, UniquePath))
3654 : {
3655 430 : innerbucketsize = 1.0 / virtualbuckets;
3656 430 : innermcvfreq = 0.0;
3657 : }
3658 : else
3659 : {
3660 148564 : innerbucketsize = 1.0;
3661 148564 : innermcvfreq = 1.0;
3662 338958 : foreach(hcl, hashclauses)
3663 : {
3664 190394 : RestrictInfo *restrictinfo = lfirst_node(RestrictInfo, hcl);
3665 : Selectivity thisbucketsize;
3666 : Selectivity thismcvfreq;
3667 :
3668 : /*
3669 : * First we have to figure out which side of the hashjoin clause
3670 : * is the inner side.
3671 : *
3672 : * Since we tend to visit the same clauses over and over when
3673 : * planning a large query, we cache the bucket stats estimates in
3674 : * the RestrictInfo node to avoid repeated lookups of statistics.
3675 : */
3676 190394 : if (bms_is_subset(restrictinfo->right_relids,
3677 190394 : inner_path->parent->relids))
3678 : {
3679 : /* righthand side is inner */
3680 103014 : thisbucketsize = restrictinfo->right_bucketsize;
3681 103014 : if (thisbucketsize < 0)
3682 : {
3683 : /* not cached yet */
3684 49366 : estimate_hash_bucket_stats(root,
3685 49366 : get_rightop(restrictinfo->clause),
3686 : virtualbuckets,
3687 : &restrictinfo->right_mcvfreq,
3688 : &restrictinfo->right_bucketsize);
3689 49366 : thisbucketsize = restrictinfo->right_bucketsize;
3690 : }
3691 103014 : thismcvfreq = restrictinfo->right_mcvfreq;
3692 : }
3693 : else
3694 : {
3695 : Assert(bms_is_subset(restrictinfo->left_relids,
3696 : inner_path->parent->relids));
3697 : /* lefthand side is inner */
3698 87380 : thisbucketsize = restrictinfo->left_bucketsize;
3699 87380 : if (thisbucketsize < 0)
3700 : {
3701 : /* not cached yet */
3702 37600 : estimate_hash_bucket_stats(root,
3703 37600 : get_leftop(restrictinfo->clause),
3704 : virtualbuckets,
3705 : &restrictinfo->left_mcvfreq,
3706 : &restrictinfo->left_bucketsize);
3707 37600 : thisbucketsize = restrictinfo->left_bucketsize;
3708 : }
3709 87380 : thismcvfreq = restrictinfo->left_mcvfreq;
3710 : }
3711 :
3712 190394 : if (innerbucketsize > thisbucketsize)
3713 87572 : innerbucketsize = thisbucketsize;
3714 190394 : if (innermcvfreq > thismcvfreq)
3715 158910 : innermcvfreq = thismcvfreq;
3716 : }
3717 : }
3718 :
3719 : /*
3720 : * If the bucket holding the inner MCV would exceed work_mem, we don't
3721 : * want to hash unless there is really no other alternative, so apply
3722 : * disable_cost. (The executor normally copes with excessive memory usage
3723 : * by splitting batches, but obviously it cannot separate equal values
3724 : * that way, so it will be unable to drive the batch size below work_mem
3725 : * when this is true.)
3726 : */
3727 148994 : if (relation_byte_size(clamp_row_est(inner_path_rows * innermcvfreq),
3728 148994 : inner_path->pathtarget->width) >
3729 148994 : (work_mem * 1024L))
3730 0 : startup_cost += disable_cost;
3731 :
3732 : /*
3733 : * Compute cost of the hashquals and qpquals (other restriction clauses)
3734 : * separately.
3735 : */
3736 148994 : cost_qual_eval(&hash_qual_cost, hashclauses, root);
3737 148994 : cost_qual_eval(&qp_qual_cost, path->jpath.joinrestrictinfo, root);
3738 148994 : qp_qual_cost.startup -= hash_qual_cost.startup;
3739 148994 : qp_qual_cost.per_tuple -= hash_qual_cost.per_tuple;
3740 :
3741 : /* CPU costs */
3742 :
3743 148994 : if (path->jpath.jointype == JOIN_SEMI ||
3744 147926 : path->jpath.jointype == JOIN_ANTI ||
3745 137684 : extra->inner_unique)
3746 59980 : {
3747 : double outer_matched_rows;
3748 : Selectivity inner_scan_frac;
3749 :
3750 : /*
3751 : * With a SEMI or ANTI join, or if the innerrel is known unique, the
3752 : * executor will stop after the first match.
3753 : *
3754 : * For an outer-rel row that has at least one match, we can expect the
3755 : * bucket scan to stop after a fraction 1/(match_count+1) of the
3756 : * bucket's rows, if the matches are evenly distributed. Since they
3757 : * probably aren't quite evenly distributed, we apply a fuzz factor of
3758 : * 2.0 to that fraction. (If we used a larger fuzz factor, we'd have
3759 : * to clamp inner_scan_frac to at most 1.0; but since match_count is
3760 : * at least 1, no such clamp is needed now.)
3761 : */
3762 59980 : outer_matched_rows = rint(outer_path_rows * extra->semifactors.outer_match_frac);
3763 59980 : inner_scan_frac = 2.0 / (extra->semifactors.match_count + 1.0);
3764 :
3765 59980 : startup_cost += hash_qual_cost.startup;
3766 179940 : run_cost += hash_qual_cost.per_tuple * outer_matched_rows *
3767 59980 : clamp_row_est(inner_path_rows * innerbucketsize * inner_scan_frac) * 0.5;
3768 :
3769 : /*
3770 : * For unmatched outer-rel rows, the picture is quite a lot different.
3771 : * In the first place, there is no reason to assume that these rows
3772 : * preferentially hit heavily-populated buckets; instead assume they
3773 : * are uncorrelated with the inner distribution and so they see an
3774 : * average bucket size of inner_path_rows / virtualbuckets. In the
3775 : * second place, it seems likely that they will have few if any exact
3776 : * hash-code matches and so very few of the tuples in the bucket will
3777 : * actually require eval of the hash quals. We don't have any good
3778 : * way to estimate how many will, but for the moment assume that the
3779 : * effective cost per bucket entry is one-tenth what it is for
3780 : * matchable tuples.
3781 : */
3782 179940 : run_cost += hash_qual_cost.per_tuple *
3783 119960 : (outer_path_rows - outer_matched_rows) *
3784 59980 : clamp_row_est(inner_path_rows / virtualbuckets) * 0.05;
3785 :
3786 : /* Get # of tuples that will pass the basic join */
3787 59980 : if (path->jpath.jointype == JOIN_ANTI)
3788 10242 : hashjointuples = outer_path_rows - outer_matched_rows;
3789 : else
3790 49738 : hashjointuples = outer_matched_rows;
3791 : }
3792 : else
3793 : {
3794 : /*
3795 : * The number of tuple comparisons needed is the number of outer
3796 : * tuples times the typical number of tuples in a hash bucket, which
3797 : * is the inner relation size times its bucketsize fraction. At each
3798 : * one, we need to evaluate the hashjoin quals. But actually,
3799 : * charging the full qual eval cost at each tuple is pessimistic,
3800 : * since we don't evaluate the quals unless the hash values match
3801 : * exactly. For lack of a better idea, halve the cost estimate to
3802 : * allow for that.
3803 : */
3804 89014 : startup_cost += hash_qual_cost.startup;
3805 267042 : run_cost += hash_qual_cost.per_tuple * outer_path_rows *
3806 89014 : clamp_row_est(inner_path_rows * innerbucketsize) * 0.5;
3807 :
3808 : /*
3809 : * Get approx # tuples passing the hashquals. We use
3810 : * approx_tuple_count here because we need an estimate done with
3811 : * JOIN_INNER semantics.
3812 : */
3813 89014 : hashjointuples = approx_tuple_count(root, &path->jpath, hashclauses);
3814 : }
3815 :
3816 : /*
3817 : * For each tuple that gets through the hashjoin proper, we charge
3818 : * cpu_tuple_cost plus the cost of evaluating additional restriction
3819 : * clauses that are to be applied at the join. (This is pessimistic since
3820 : * not all of the quals may get evaluated at each tuple.)
3821 : */
3822 148994 : startup_cost += qp_qual_cost.startup;
3823 148994 : cpu_per_tuple = cpu_tuple_cost + qp_qual_cost.per_tuple;
3824 148994 : run_cost += cpu_per_tuple * hashjointuples;
3825 :
3826 : /* tlist eval costs are paid per output row, not per tuple scanned */
3827 148994 : startup_cost += path->jpath.path.pathtarget->cost.startup;
3828 148994 : run_cost += path->jpath.path.pathtarget->cost.per_tuple * path->jpath.path.rows;
3829 :
3830 148994 : path->jpath.path.startup_cost = startup_cost;
3831 148994 : path->jpath.path.total_cost = startup_cost + run_cost;
3832 148994 : }
3833 :
3834 :
3835 : /*
3836 : * cost_subplan
3837 : * Figure the costs for a SubPlan (or initplan).
3838 : *
3839 : * Note: we could dig the subplan's Plan out of the root list, but in practice
3840 : * all callers have it handy already, so we make them pass it.
3841 : */
3842 : void
3843 48862 : cost_subplan(PlannerInfo *root, SubPlan *subplan, Plan *plan)
3844 : {
3845 : QualCost sp_cost;
3846 :
3847 : /* Figure any cost for evaluating the testexpr */
3848 48862 : cost_qual_eval(&sp_cost,
3849 48862 : make_ands_implicit((Expr *) subplan->testexpr),
3850 : root);
3851 :
3852 48862 : if (subplan->useHashTable)
3853 : {
3854 : /*
3855 : * If we are using a hash table for the subquery outputs, then the
3856 : * cost of evaluating the query is a one-time cost. We charge one
3857 : * cpu_operator_cost per tuple for the work of loading the hashtable,
3858 : * too.
3859 : */
3860 2656 : sp_cost.startup += plan->total_cost +
3861 1328 : cpu_operator_cost * plan->plan_rows;
3862 :
3863 : /*
3864 : * The per-tuple costs include the cost of evaluating the lefthand
3865 : * expressions, plus the cost of probing the hashtable. We already
3866 : * accounted for the lefthand expressions as part of the testexpr, and
3867 : * will also have counted one cpu_operator_cost for each comparison
3868 : * operator. That is probably too low for the probing cost, but it's
3869 : * hard to make a better estimate, so live with it for now.
3870 : */
3871 : }
3872 : else
3873 : {
3874 : /*
3875 : * Otherwise we will be rescanning the subplan output on each
3876 : * evaluation. We need to estimate how much of the output we will
3877 : * actually need to scan. NOTE: this logic should agree with the
3878 : * tuple_fraction estimates used by make_subplan() in
3879 : * plan/subselect.c.
3880 : */
3881 47534 : Cost plan_run_cost = plan->total_cost - plan->startup_cost;
3882 :
3883 47534 : if (subplan->subLinkType == EXISTS_SUBLINK)
3884 : {
3885 : /* we only need to fetch 1 tuple; clamp to avoid zero divide */
3886 1678 : sp_cost.per_tuple += plan_run_cost / clamp_row_est(plan->plan_rows);
3887 : }
3888 45856 : else if (subplan->subLinkType == ALL_SUBLINK ||
3889 45844 : subplan->subLinkType == ANY_SUBLINK)
3890 : {
3891 : /* assume we need 50% of the tuples */
3892 60 : sp_cost.per_tuple += 0.50 * plan_run_cost;
3893 : /* also charge a cpu_operator_cost per row examined */
3894 60 : sp_cost.per_tuple += 0.50 * plan->plan_rows * cpu_operator_cost;
3895 : }
3896 : else
3897 : {
3898 : /* assume we need all tuples */
3899 45796 : sp_cost.per_tuple += plan_run_cost;
3900 : }
3901 :
3902 : /*
3903 : * Also account for subplan's startup cost. If the subplan is
3904 : * uncorrelated or undirect correlated, AND its topmost node is one
3905 : * that materializes its output, assume that we'll only need to pay
3906 : * its startup cost once; otherwise assume we pay the startup cost
3907 : * every time.
3908 : */
3909 57830 : if (subplan->parParam == NIL &&
3910 10296 : ExecMaterializesOutput(nodeTag(plan)))
3911 176 : sp_cost.startup += plan->startup_cost;
3912 : else
3913 47358 : sp_cost.per_tuple += plan->startup_cost;
3914 : }
3915 :
3916 48862 : subplan->startup_cost = sp_cost.startup;
3917 48862 : subplan->per_call_cost = sp_cost.per_tuple;
3918 48862 : }
3919 :
3920 :
3921 : /*
3922 : * cost_rescan
3923 : * Given a finished Path, estimate the costs of rescanning it after
3924 : * having done so the first time. For some Path types a rescan is
3925 : * cheaper than an original scan (if no parameters change), and this
3926 : * function embodies knowledge about that. The default is to return
3927 : * the same costs stored in the Path. (Note that the cost estimates
3928 : * actually stored in Paths are always for first scans.)
3929 : *
3930 : * This function is not currently intended to model effects such as rescans
3931 : * being cheaper due to disk block caching; what we are concerned with is
3932 : * plan types wherein the executor caches results explicitly, or doesn't
3933 : * redo startup calculations, etc.
3934 : */
3935 : static void
3936 1113022 : cost_rescan(PlannerInfo *root, Path *path,
3937 : Cost *rescan_startup_cost, /* output parameters */
3938 : Cost *rescan_total_cost)
3939 : {
3940 1113022 : switch (path->pathtype)
3941 : {
3942 10492 : case T_FunctionScan:
3943 :
3944 : /*
3945 : * Currently, nodeFunctionscan.c always executes the function to
3946 : * completion before returning any rows, and caches the results in
3947 : * a tuplestore. So the function eval cost is all startup cost
3948 : * and isn't paid over again on rescans. However, all run costs
3949 : * will be paid over again.
3950 : */
3951 10492 : *rescan_startup_cost = 0;
3952 10492 : *rescan_total_cost = path->total_cost - path->startup_cost;
3953 10492 : break;
3954 36724 : case T_HashJoin:
3955 :
3956 : /*
3957 : * If it's a single-batch join, we don't need to rebuild the hash
3958 : * table during a rescan.
3959 : */
3960 36724 : if (((HashPath *) path)->num_batches == 1)
3961 : {
3962 : /* Startup cost is exactly the cost of hash table building */
3963 36724 : *rescan_startup_cost = 0;
3964 36724 : *rescan_total_cost = path->total_cost - path->startup_cost;
3965 : }
3966 : else
3967 : {
3968 : /* Otherwise, no special treatment */
3969 0 : *rescan_startup_cost = path->startup_cost;
3970 0 : *rescan_total_cost = path->total_cost;
3971 : }
3972 36724 : break;
3973 1974 : case T_CteScan:
3974 : case T_WorkTableScan:
3975 : {
3976 : /*
3977 : * These plan types materialize their final result in a
3978 : * tuplestore or tuplesort object. So the rescan cost is only
3979 : * cpu_tuple_cost per tuple, unless the result is large enough
3980 : * to spill to disk.
3981 : */
3982 1974 : Cost run_cost = cpu_tuple_cost * path->rows;
3983 1974 : double nbytes = relation_byte_size(path->rows,
3984 1974 : path->pathtarget->width);
3985 1974 : long work_mem_bytes = work_mem * 1024L;
3986 :
3987 1974 : if (nbytes > work_mem_bytes)
3988 : {
3989 : /* It will spill, so account for re-read cost */
3990 0 : double npages = ceil(nbytes / BLCKSZ);
3991 :
3992 0 : run_cost += seq_page_cost * npages;
3993 : }
3994 1974 : *rescan_startup_cost = 0;
3995 1974 : *rescan_total_cost = run_cost;
3996 : }
3997 1974 : break;
3998 429344 : case T_Material:
3999 : case T_Sort:
4000 : {
4001 : /*
4002 : * These plan types not only materialize their results, but do
4003 : * not implement qual filtering or projection. So they are
4004 : * even cheaper to rescan than the ones above. We charge only
4005 : * cpu_operator_cost per tuple. (Note: keep that in sync with
4006 : * the run_cost charge in cost_sort, and also see comments in
4007 : * cost_material before you change it.)
4008 : */
4009 429344 : Cost run_cost = cpu_operator_cost * path->rows;
4010 429344 : double nbytes = relation_byte_size(path->rows,
4011 429344 : path->pathtarget->width);
4012 429344 : long work_mem_bytes = work_mem * 1024L;
4013 :
4014 429344 : if (nbytes > work_mem_bytes)
4015 : {
4016 : /* It will spill, so account for re-read cost */
4017 3760 : double npages = ceil(nbytes / BLCKSZ);
4018 :
4019 3760 : run_cost += seq_page_cost * npages;
4020 : }
4021 429344 : *rescan_startup_cost = 0;
4022 429344 : *rescan_total_cost = run_cost;
4023 : }
4024 429344 : break;
4025 634488 : default:
4026 634488 : *rescan_startup_cost = path->startup_cost;
4027 634488 : *rescan_total_cost = path->total_cost;
4028 634488 : break;
4029 : }
4030 1113022 : }
4031 :
4032 :
4033 : /*
4034 : * cost_qual_eval
4035 : * Estimate the CPU costs of evaluating a WHERE clause.
4036 : * The input can be either an implicitly-ANDed list of boolean
4037 : * expressions, or a list of RestrictInfo nodes. (The latter is
4038 : * preferred since it allows caching of the results.)
4039 : * The result includes both a one-time (startup) component,
4040 : * and a per-evaluation component.
4041 : */
4042 : void
4043 1904820 : cost_qual_eval(QualCost *cost, List *quals, PlannerInfo *root)
4044 : {
4045 : cost_qual_eval_context context;
4046 : ListCell *l;
4047 :
4048 1904820 : context.root = root;
4049 1904820 : context.total.startup = 0;
4050 1904820 : context.total.per_tuple = 0;
4051 :
4052 : /* We don't charge any cost for the implicit ANDing at top level ... */
4053 :
4054 3589664 : foreach(l, quals)
4055 : {
4056 1684844 : Node *qual = (Node *) lfirst(l);
4057 :
4058 1684844 : cost_qual_eval_walker(qual, &context);
4059 : }
4060 :
4061 1904820 : *cost = context.total;
4062 1904820 : }
4063 :
4064 : /*
4065 : * cost_qual_eval_node
4066 : * As above, for a single RestrictInfo or expression.
4067 : */
4068 : void
4069 1177150 : cost_qual_eval_node(QualCost *cost, Node *qual, PlannerInfo *root)
4070 : {
4071 : cost_qual_eval_context context;
4072 :
4073 1177150 : context.root = root;
4074 1177150 : context.total.startup = 0;
4075 1177150 : context.total.per_tuple = 0;
4076 :
4077 1177150 : cost_qual_eval_walker(qual, &context);
4078 :
4079 1177150 : *cost = context.total;
4080 1177150 : }
4081 :
4082 : static bool
4083 4879316 : cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
4084 : {
4085 4879316 : if (node == NULL)
4086 52870 : return false;
4087 :
4088 : /*
4089 : * RestrictInfo nodes contain an eval_cost field reserved for this
4090 : * routine's use, so that it's not necessary to evaluate the qual clause's
4091 : * cost more than once. If the clause's cost hasn't been computed yet,
4092 : * the field's startup value will contain -1.
4093 : */
4094 4826446 : if (IsA(node, RestrictInfo))
4095 : {
4096 1759152 : RestrictInfo *rinfo = (RestrictInfo *) node;
4097 :
4098 1759152 : if (rinfo->eval_cost.startup < 0)
4099 : {
4100 : cost_qual_eval_context locContext;
4101 :
4102 322508 : locContext.root = context->root;
4103 322508 : locContext.total.startup = 0;
4104 322508 : locContext.total.per_tuple = 0;
4105 :
4106 : /*
4107 : * For an OR clause, recurse into the marked-up tree so that we
4108 : * set the eval_cost for contained RestrictInfos too.
4109 : */
4110 322508 : if (rinfo->orclause)
4111 5418 : cost_qual_eval_walker((Node *) rinfo->orclause, &locContext);
4112 : else
4113 317090 : cost_qual_eval_walker((Node *) rinfo->clause, &locContext);
4114 :
4115 : /*
4116 : * If the RestrictInfo is marked pseudoconstant, it will be tested
4117 : * only once, so treat its cost as all startup cost.
4118 : */
4119 322508 : if (rinfo->pseudoconstant)
4120 : {
4121 : /* count one execution during startup */
4122 2816 : locContext.total.startup += locContext.total.per_tuple;
4123 2816 : locContext.total.per_tuple = 0;
4124 : }
4125 322508 : rinfo->eval_cost = locContext.total;
4126 : }
4127 1759152 : context->total.startup += rinfo->eval_cost.startup;
4128 1759152 : context->total.per_tuple += rinfo->eval_cost.per_tuple;
4129 : /* do NOT recurse into children */
4130 1759152 : return false;
4131 : }
4132 :
4133 : /*
4134 : * For each operator or function node in the given tree, we charge the
4135 : * estimated execution cost given by pg_proc.procost (remember to multiply
4136 : * this by cpu_operator_cost).
4137 : *
4138 : * Vars and Consts are charged zero, and so are boolean operators (AND,
4139 : * OR, NOT). Simplistic, but a lot better than no model at all.
4140 : *
4141 : * Should we try to account for the possibility of short-circuit
4142 : * evaluation of AND/OR? Probably *not*, because that would make the
4143 : * results depend on the clause ordering, and we are not in any position
4144 : * to expect that the current ordering of the clauses is the one that's
4145 : * going to end up being used. The above per-RestrictInfo caching would
4146 : * not mix well with trying to re-order clauses anyway.
4147 : *
4148 : * Another issue that is entirely ignored here is that if a set-returning
4149 : * function is below top level in the tree, the functions/operators above
4150 : * it will need to be evaluated multiple times. In practical use, such
4151 : * cases arise so seldom as to not be worth the added complexity needed;
4152 : * moreover, since our rowcount estimates for functions tend to be pretty
4153 : * phony, the results would also be pretty phony.
4154 : */
4155 3067294 : if (IsA(node, FuncExpr))
4156 : {
4157 259444 : add_function_cost(context->root, ((FuncExpr *) node)->funcid, node,
4158 : &context->total);
4159 : }
4160 2807850 : else if (IsA(node, OpExpr) ||
4161 2435690 : IsA(node, DistinctExpr) ||
4162 2435224 : IsA(node, NullIfExpr))
4163 : {
4164 : /* rely on struct equivalence to treat these all alike */
4165 372786 : set_opfuncid((OpExpr *) node);
4166 372786 : add_function_cost(context->root, ((OpExpr *) node)->opfuncid, node,
4167 : &context->total);
4168 : }
4169 2435064 : else if (IsA(node, ScalarArrayOpExpr))
4170 : {
4171 : /*
4172 : * Estimate that the operator will be applied to about half of the
4173 : * array elements before the answer is determined.
4174 : */
4175 23598 : ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) node;
4176 23598 : Node *arraynode = (Node *) lsecond(saop->args);
4177 : QualCost sacosts;
4178 :
4179 23598 : set_sa_opfuncid(saop);
4180 23598 : sacosts.startup = sacosts.per_tuple = 0;
4181 23598 : add_function_cost(context->root, saop->opfuncid, NULL,
4182 : &sacosts);
4183 23598 : context->total.startup += sacosts.startup;
4184 70794 : context->total.per_tuple += sacosts.per_tuple *
4185 23598 : estimate_array_length(arraynode) * 0.5;
4186 : }
4187 2411466 : else if (IsA(node, Aggref) ||
4188 2377574 : IsA(node, WindowFunc))
4189 : {
4190 : /*
4191 : * Aggref and WindowFunc nodes are (and should be) treated like Vars,
4192 : * ie, zero execution cost in the current model, because they behave
4193 : * essentially like Vars at execution. We disregard the costs of
4194 : * their input expressions for the same reason. The actual execution
4195 : * costs of the aggregate/window functions and their arguments have to
4196 : * be factored into plan-node-specific costing of the Agg or WindowAgg
4197 : * plan node.
4198 : */
4199 35412 : return false; /* don't recurse into children */
4200 : }
4201 2376054 : else if (IsA(node, CoerceViaIO))
4202 : {
4203 7624 : CoerceViaIO *iocoerce = (CoerceViaIO *) node;
4204 : Oid iofunc;
4205 : Oid typioparam;
4206 : bool typisvarlena;
4207 :
4208 : /* check the result type's input function */
4209 7624 : getTypeInputInfo(iocoerce->resulttype,
4210 : &iofunc, &typioparam);
4211 7624 : add_function_cost(context->root, iofunc, NULL,
4212 : &context->total);
4213 : /* check the input type's output function */
4214 7624 : getTypeOutputInfo(exprType((Node *) iocoerce->arg),
4215 : &iofunc, &typisvarlena);
4216 7624 : add_function_cost(context->root, iofunc, NULL,
4217 : &context->total);
4218 : }
4219 2368430 : else if (IsA(node, ArrayCoerceExpr))
4220 : {
4221 334 : ArrayCoerceExpr *acoerce = (ArrayCoerceExpr *) node;
4222 : QualCost perelemcost;
4223 :
4224 334 : cost_qual_eval_node(&perelemcost, (Node *) acoerce->elemexpr,
4225 : context->root);
4226 334 : context->total.startup += perelemcost.startup;
4227 334 : if (perelemcost.per_tuple > 0)
4228 38 : context->total.per_tuple += perelemcost.per_tuple *
4229 38 : estimate_array_length((Node *) acoerce->arg);
4230 : }
4231 2368096 : else if (IsA(node, RowCompareExpr))
4232 : {
4233 : /* Conservatively assume we will check all the columns */
4234 104 : RowCompareExpr *rcexpr = (RowCompareExpr *) node;
4235 : ListCell *lc;
4236 :
4237 348 : foreach(lc, rcexpr->opnos)
4238 : {
4239 244 : Oid opid = lfirst_oid(lc);
4240 :
4241 244 : add_function_cost(context->root, get_opcode(opid), NULL,
4242 : &context->total);
4243 : }
4244 : }
4245 2367992 : else if (IsA(node, MinMaxExpr) ||
4246 2367894 : IsA(node, SQLValueFunction) ||
4247 2365994 : IsA(node, XmlExpr) ||
4248 2365638 : IsA(node, CoerceToDomain) ||
4249 2338954 : IsA(node, NextValueExpr))
4250 : {
4251 : /* Treat all these as having cost 1 */
4252 29188 : context->total.per_tuple += cpu_operator_cost;
4253 : }
4254 2338804 : else if (IsA(node, CurrentOfExpr))
4255 : {
4256 : /* Report high cost to prevent selection of anything but TID scan */
4257 384 : context->total.startup += disable_cost;
4258 : }
4259 2338420 : else if (IsA(node, SubLink))
4260 : {
4261 : /* This routine should not be applied to un-planned expressions */
4262 0 : elog(ERROR, "cannot handle unplanned sub-select");
4263 : }
4264 2338420 : else if (IsA(node, SubPlan))
4265 : {
4266 : /*
4267 : * A subplan node in an expression typically indicates that the
4268 : * subplan will be executed on each evaluation, so charge accordingly.
4269 : * (Sub-selects that can be executed as InitPlans have already been
4270 : * removed from the expression.)
4271 : */
4272 56250 : SubPlan *subplan = (SubPlan *) node;
4273 :
4274 56250 : context->total.startup += subplan->startup_cost;
4275 56250 : context->total.per_tuple += subplan->per_call_cost;
4276 :
4277 : /*
4278 : * We don't want to recurse into the testexpr, because it was already
4279 : * counted in the SubPlan node's costs. So we're done.
4280 : */
4281 56250 : return false;
4282 : }
4283 2282170 : else if (IsA(node, AlternativeSubPlan))
4284 : {
4285 : /*
4286 : * Arbitrarily use the first alternative plan for costing. (We should
4287 : * certainly only include one alternative, and we don't yet have
4288 : * enough information to know which one the executor is most likely to
4289 : * use.)
4290 : */
4291 1488 : AlternativeSubPlan *asplan = (AlternativeSubPlan *) node;
4292 :
4293 1488 : return cost_qual_eval_walker((Node *) linitial(asplan->subplans),
4294 : context);
4295 : }
4296 2280682 : else if (IsA(node, PlaceHolderVar))
4297 : {
4298 : /*
4299 : * A PlaceHolderVar should be given cost zero when considering general
4300 : * expression evaluation costs. The expense of doing the contained
4301 : * expression is charged as part of the tlist eval costs of the scan
4302 : * or join where the PHV is first computed (see set_rel_width and
4303 : * add_placeholders_to_joinrel). If we charged it again here, we'd be
4304 : * double-counting the cost for each level of plan that the PHV
4305 : * bubbles up through. Hence, return without recursing into the
4306 : * phexpr.
4307 : */
4308 1240 : return false;
4309 : }
4310 :
4311 : /* recurse into children */
4312 2972904 : return expression_tree_walker(node, cost_qual_eval_walker,
4313 : (void *) context);
4314 : }
4315 :
4316 : /*
4317 : * get_restriction_qual_cost
4318 : * Compute evaluation costs of a baserel's restriction quals, plus any
4319 : * movable join quals that have been pushed down to the scan.
4320 : * Results are returned into *qpqual_cost.
4321 : *
4322 : * This is a convenience subroutine that works for seqscans and other cases
4323 : * where all the given quals will be evaluated the hard way. It's not useful
4324 : * for cost_index(), for example, where the index machinery takes care of
4325 : * some of the quals. We assume baserestrictcost was previously set by
4326 : * set_baserel_size_estimates().
4327 : */
4328 : static void
4329 572390 : get_restriction_qual_cost(PlannerInfo *root, RelOptInfo *baserel,
4330 : ParamPathInfo *param_info,
4331 : QualCost *qpqual_cost)
4332 : {
4333 572390 : if (param_info)
4334 : {
4335 : /* Include costs of pushed-down clauses */
4336 95044 : cost_qual_eval(qpqual_cost, param_info->ppi_clauses, root);
4337 :
4338 95044 : qpqual_cost->startup += baserel->baserestrictcost.startup;
4339 95044 : qpqual_cost->per_tuple += baserel->baserestrictcost.per_tuple;
4340 : }
4341 : else
4342 477346 : *qpqual_cost = baserel->baserestrictcost;
4343 572390 : }
4344 :
4345 :
4346 : /*
4347 : * compute_semi_anti_join_factors
4348 : * Estimate how much of the inner input a SEMI, ANTI, or inner_unique join
4349 : * can be expected to scan.
4350 : *
4351 : * In a hash or nestloop SEMI/ANTI join, the executor will stop scanning
4352 : * inner rows as soon as it finds a match to the current outer row.
4353 : * The same happens if we have detected the inner rel is unique.
4354 : * We should therefore adjust some of the cost components for this effect.
4355 : * This function computes some estimates needed for these adjustments.
4356 : * These estimates will be the same regardless of the particular paths used
4357 : * for the outer and inner relation, so we compute these once and then pass
4358 : * them to all the join cost estimation functions.
4359 : *
4360 : * Input parameters:
4361 : * joinrel: join relation under consideration
4362 : * outerrel: outer relation under consideration
4363 : * innerrel: inner relation under consideration
4364 : * jointype: if not JOIN_SEMI or JOIN_ANTI, we assume it's inner_unique
4365 : * sjinfo: SpecialJoinInfo relevant to this join
4366 : * restrictlist: join quals
4367 : * Output parameters:
4368 : * *semifactors is filled in (see pathnodes.h for field definitions)
4369 : */
4370 : void
4371 116714 : compute_semi_anti_join_factors(PlannerInfo *root,
4372 : RelOptInfo *joinrel,
4373 : RelOptInfo *outerrel,
4374 : RelOptInfo *innerrel,
4375 : JoinType jointype,
4376 : SpecialJoinInfo *sjinfo,
4377 : List *restrictlist,
4378 : SemiAntiJoinFactors *semifactors)
4379 : {
4380 : Selectivity jselec;
4381 : Selectivity nselec;
4382 : Selectivity avgmatch;
4383 : SpecialJoinInfo norm_sjinfo;
4384 : List *joinquals;
4385 : ListCell *l;
4386 :
4387 : /*
4388 : * In an ANTI join, we must ignore clauses that are "pushed down", since
4389 : * those won't affect the match logic. In a SEMI join, we do not
4390 : * distinguish joinquals from "pushed down" quals, so just use the whole
4391 : * restrictinfo list. For other outer join types, we should consider only
4392 : * non-pushed-down quals, so that this devolves to an IS_OUTER_JOIN check.
4393 : */
4394 116714 : if (IS_OUTER_JOIN(jointype))
4395 : {
4396 47142 : joinquals = NIL;
4397 105292 : foreach(l, restrictlist)
4398 : {
4399 58150 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
4400 :
4401 58150 : if (!RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
4402 56292 : joinquals = lappend(joinquals, rinfo);
4403 : }
4404 : }
4405 : else
4406 69572 : joinquals = restrictlist;
4407 :
4408 : /*
4409 : * Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses.
4410 : */
4411 116714 : jselec = clauselist_selectivity(root,
4412 : joinquals,
4413 : 0,
4414 : (jointype == JOIN_ANTI) ? JOIN_ANTI : JOIN_SEMI,
4415 : sjinfo);
4416 :
4417 : /*
4418 : * Also get the normal inner-join selectivity of the join clauses.
4419 : */
4420 116714 : norm_sjinfo.type = T_SpecialJoinInfo;
4421 116714 : norm_sjinfo.min_lefthand = outerrel->relids;
4422 116714 : norm_sjinfo.min_righthand = innerrel->relids;
4423 116714 : norm_sjinfo.syn_lefthand = outerrel->relids;
4424 116714 : norm_sjinfo.syn_righthand = innerrel->relids;
4425 116714 : norm_sjinfo.jointype = JOIN_INNER;
4426 : /* we don't bother trying to make the remaining fields valid */
4427 116714 : norm_sjinfo.lhs_strict = false;
4428 116714 : norm_sjinfo.delay_upper_joins = false;
4429 116714 : norm_sjinfo.semi_can_btree = false;
4430 116714 : norm_sjinfo.semi_can_hash = false;
4431 116714 : norm_sjinfo.semi_operators = NIL;
4432 116714 : norm_sjinfo.semi_rhs_exprs = NIL;
4433 :
4434 116714 : nselec = clauselist_selectivity(root,
4435 : joinquals,
4436 : 0,
4437 : JOIN_INNER,
4438 : &norm_sjinfo);
4439 :
4440 : /* Avoid leaking a lot of ListCells */
4441 116714 : if (IS_OUTER_JOIN(jointype))
4442 47142 : list_free(joinquals);
4443 :
4444 : /*
4445 : * jselec can be interpreted as the fraction of outer-rel rows that have
4446 : * any matches (this is true for both SEMI and ANTI cases). And nselec is
4447 : * the fraction of the Cartesian product that matches. So, the average
4448 : * number of matches for each outer-rel row that has at least one match is
4449 : * nselec * inner_rows / jselec.
4450 : *
4451 : * Note: it is correct to use the inner rel's "rows" count here, even
4452 : * though we might later be considering a parameterized inner path with
4453 : * fewer rows. This is because we have included all the join clauses in
4454 : * the selectivity estimate.
4455 : */
4456 116714 : if (jselec > 0) /* protect against zero divide */
4457 : {
4458 116714 : avgmatch = nselec * innerrel->rows / jselec;
4459 : /* Clamp to sane range */
4460 116714 : avgmatch = Max(1.0, avgmatch);
4461 : }
4462 : else
4463 0 : avgmatch = 1.0;
4464 :
4465 116714 : semifactors->outer_match_frac = jselec;
4466 116714 : semifactors->match_count = avgmatch;
4467 116714 : }
4468 :
4469 : /*
4470 : * has_indexed_join_quals
4471 : * Check whether all the joinquals of a nestloop join are used as
4472 : * inner index quals.
4473 : *
4474 : * If the inner path of a SEMI/ANTI join is an indexscan (including bitmap
4475 : * indexscan) that uses all the joinquals as indexquals, we can assume that an
4476 : * unmatched outer tuple is cheap to process, whereas otherwise it's probably
4477 : * expensive.
4478 : */
4479 : static bool
4480 390940 : has_indexed_join_quals(NestPath *joinpath)
4481 : {
4482 390940 : Relids joinrelids = joinpath->path.parent->relids;
4483 390940 : Path *innerpath = joinpath->innerjoinpath;
4484 : List *indexclauses;
4485 : bool found_one;
4486 : ListCell *lc;
4487 :
4488 : /* If join still has quals to evaluate, it's not fast */
4489 390940 : if (joinpath->joinrestrictinfo != NIL)
4490 302784 : return false;
4491 : /* Nor if the inner path isn't parameterized at all */
4492 88156 : if (innerpath->param_info == NULL)
4493 3200 : return false;
4494 :
4495 : /* Find the indexclauses list for the inner scan */
4496 84956 : switch (innerpath->pathtype)
4497 : {
4498 84388 : case T_IndexScan:
4499 : case T_IndexOnlyScan:
4500 84388 : indexclauses = ((IndexPath *) innerpath)->indexclauses;
4501 84388 : break;
4502 132 : case T_BitmapHeapScan:
4503 : {
4504 : /* Accept only a simple bitmap scan, not AND/OR cases */
4505 132 : Path *bmqual = ((BitmapHeapPath *) innerpath)->bitmapqual;
4506 :
4507 132 : if (IsA(bmqual, IndexPath))
4508 132 : indexclauses = ((IndexPath *) bmqual)->indexclauses;
4509 : else
4510 0 : return false;
4511 132 : break;
4512 : }
4513 436 : default:
4514 :
4515 : /*
4516 : * If it's not a simple indexscan, it probably doesn't run quickly
4517 : * for zero rows out, even if it's a parameterized path using all
4518 : * the joinquals.
4519 : */
4520 436 : return false;
4521 : }
4522 :
4523 : /*
4524 : * Examine the inner path's param clauses. Any that are from the outer
4525 : * path must be found in the indexclauses list, either exactly or in an
4526 : * equivalent form generated by equivclass.c. Also, we must find at least
4527 : * one such clause, else it's a clauseless join which isn't fast.
4528 : */
4529 84520 : found_one = false;
4530 169686 : foreach(lc, innerpath->param_info->ppi_clauses)
4531 : {
4532 86290 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
4533 :
4534 86290 : if (join_clause_is_movable_into(rinfo,
4535 86290 : innerpath->parent->relids,
4536 : joinrelids))
4537 : {
4538 86290 : if (!is_redundant_with_indexclauses(rinfo, indexclauses))
4539 1124 : return false;
4540 85166 : found_one = true;
4541 : }
4542 : }
4543 83396 : return found_one;
4544 : }
4545 :
4546 :
4547 : /*
4548 : * approx_tuple_count
4549 : * Quick-and-dirty estimation of the number of join rows passing
4550 : * a set of qual conditions.
4551 : *
4552 : * The quals can be either an implicitly-ANDed list of boolean expressions,
4553 : * or a list of RestrictInfo nodes (typically the latter).
4554 : *
4555 : * We intentionally compute the selectivity under JOIN_INNER rules, even
4556 : * if it's some type of outer join. This is appropriate because we are
4557 : * trying to figure out how many tuples pass the initial merge or hash
4558 : * join step.
4559 : *
4560 : * This is quick-and-dirty because we bypass clauselist_selectivity, and
4561 : * simply multiply the independent clause selectivities together. Now
4562 : * clauselist_selectivity often can't do any better than that anyhow, but
4563 : * for some situations (such as range constraints) it is smarter. However,
4564 : * we can't effectively cache the results of clauselist_selectivity, whereas
4565 : * the individual clause selectivities can be and are cached.
4566 : *
4567 : * Since we are only using the results to estimate how many potential
4568 : * output tuples are generated and passed through qpqual checking, it
4569 : * seems OK to live with the approximation.
4570 : */
4571 : static double
4572 224738 : approx_tuple_count(PlannerInfo *root, JoinPath *path, List *quals)
4573 : {
4574 : double tuples;
4575 224738 : double outer_tuples = path->outerjoinpath->rows;
4576 224738 : double inner_tuples = path->innerjoinpath->rows;
4577 : SpecialJoinInfo sjinfo;
4578 224738 : Selectivity selec = 1.0;
4579 : ListCell *l;
4580 :
4581 : /*
4582 : * Make up a SpecialJoinInfo for JOIN_INNER semantics.
4583 : */
4584 224738 : sjinfo.type = T_SpecialJoinInfo;
4585 224738 : sjinfo.min_lefthand = path->outerjoinpath->parent->relids;
4586 224738 : sjinfo.min_righthand = path->innerjoinpath->parent->relids;
4587 224738 : sjinfo.syn_lefthand = path->outerjoinpath->parent->relids;
4588 224738 : sjinfo.syn_righthand = path->innerjoinpath->parent->relids;
4589 224738 : sjinfo.jointype = JOIN_INNER;
4590 : /* we don't bother trying to make the remaining fields valid */
4591 224738 : sjinfo.lhs_strict = false;
4592 224738 : sjinfo.delay_upper_joins = false;
4593 224738 : sjinfo.semi_can_btree = false;
4594 224738 : sjinfo.semi_can_hash = false;
4595 224738 : sjinfo.semi_operators = NIL;
4596 224738 : sjinfo.semi_rhs_exprs = NIL;
4597 :
4598 : /* Get the approximate selectivity */
4599 501762 : foreach(l, quals)
4600 : {
4601 277024 : Node *qual = (Node *) lfirst(l);
4602 :
4603 : /* Note that clause_selectivity will be able to cache its result */
4604 277024 : selec *= clause_selectivity(root, qual, 0, JOIN_INNER, &sjinfo);
4605 : }
4606 :
4607 : /* Apply it to the input relation sizes */
4608 224738 : tuples = selec * outer_tuples * inner_tuples;
4609 :
4610 224738 : return clamp_row_est(tuples);
4611 : }
4612 :
4613 :
4614 : /*
4615 : * set_baserel_size_estimates
4616 : * Set the size estimates for the given base relation.
4617 : *
4618 : * The rel's targetlist and restrictinfo list must have been constructed
4619 : * already, and rel->tuples must be set.
4620 : *
4621 : * We set the following fields of the rel node:
4622 : * rows: the estimated number of output tuples (after applying
4623 : * restriction clauses).
4624 : * width: the estimated average output tuple width in bytes.
4625 : * baserestrictcost: estimated cost of evaluating baserestrictinfo clauses.
4626 : */
4627 : void
4628 282200 : set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel)
4629 : {
4630 : double nrows;
4631 :
4632 : /* Should only be applied to base relations */
4633 : Assert(rel->relid > 0);
4634 :
4635 564400 : nrows = rel->tuples *
4636 282200 : clauselist_selectivity(root,
4637 : rel->baserestrictinfo,
4638 : 0,
4639 : JOIN_INNER,
4640 : NULL);
4641 :
4642 282200 : rel->rows = clamp_row_est(nrows);
4643 :
4644 282200 : cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo, root);
4645 :
4646 282200 : set_rel_width(root, rel);
4647 282200 : }
4648 :
4649 : /*
4650 : * get_parameterized_baserel_size
4651 : * Make a size estimate for a parameterized scan of a base relation.
4652 : *
4653 : * 'param_clauses' lists the additional join clauses to be used.
4654 : *
4655 : * set_baserel_size_estimates must have been applied already.
4656 : */
4657 : double
4658 67318 : get_parameterized_baserel_size(PlannerInfo *root, RelOptInfo *rel,
4659 : List *param_clauses)
4660 : {
4661 : List *allclauses;
4662 : double nrows;
4663 :
4664 : /*
4665 : * Estimate the number of rows returned by the parameterized scan, knowing
4666 : * that it will apply all the extra join clauses as well as the rel's own
4667 : * restriction clauses. Note that we force the clauses to be treated as
4668 : * non-join clauses during selectivity estimation.
4669 : */
4670 67318 : allclauses = list_concat_copy(param_clauses, rel->baserestrictinfo);
4671 134636 : nrows = rel->tuples *
4672 67318 : clauselist_selectivity(root,
4673 : allclauses,
4674 67318 : rel->relid, /* do not use 0! */
4675 : JOIN_INNER,
4676 : NULL);
4677 67318 : nrows = clamp_row_est(nrows);
4678 : /* For safety, make sure result is not more than the base estimate */
4679 67318 : if (nrows > rel->rows)
4680 0 : nrows = rel->rows;
4681 67318 : return nrows;
4682 : }
4683 :
4684 : /*
4685 : * set_joinrel_size_estimates
4686 : * Set the size estimates for the given join relation.
4687 : *
4688 : * The rel's targetlist must have been constructed already, and a
4689 : * restriction clause list that matches the given component rels must
4690 : * be provided.
4691 : *
4692 : * Since there is more than one way to make a joinrel for more than two
4693 : * base relations, the results we get here could depend on which component
4694 : * rel pair is provided. In theory we should get the same answers no matter
4695 : * which pair is provided; in practice, since the selectivity estimation
4696 : * routines don't handle all cases equally well, we might not. But there's
4697 : * not much to be done about it. (Would it make sense to repeat the
4698 : * calculations for each pair of input rels that's encountered, and somehow
4699 : * average the results? Probably way more trouble than it's worth, and
4700 : * anyway we must keep the rowcount estimate the same for all paths for the
4701 : * joinrel.)
4702 : *
4703 : * We set only the rows field here. The reltarget field was already set by
4704 : * build_joinrel_tlist, and baserestrictcost is not used for join rels.
4705 : */
4706 : void
4707 102328 : set_joinrel_size_estimates(PlannerInfo *root, RelOptInfo *rel,
4708 : RelOptInfo *outer_rel,
4709 : RelOptInfo *inner_rel,
4710 : SpecialJoinInfo *sjinfo,
4711 : List *restrictlist)
4712 : {
4713 102328 : rel->rows = calc_joinrel_size_estimate(root,
4714 : rel,
4715 : outer_rel,
4716 : inner_rel,
4717 : outer_rel->rows,
4718 : inner_rel->rows,
4719 : sjinfo,
4720 : restrictlist);
4721 102328 : }
4722 :
4723 : /*
4724 : * get_parameterized_joinrel_size
4725 : * Make a size estimate for a parameterized scan of a join relation.
4726 : *
4727 : * 'rel' is the joinrel under consideration.
4728 : * 'outer_path', 'inner_path' are (probably also parameterized) Paths that
4729 : * produce the relations being joined.
4730 : * 'sjinfo' is any SpecialJoinInfo relevant to this join.
4731 : * 'restrict_clauses' lists the join clauses that need to be applied at the
4732 : * join node (including any movable clauses that were moved down to this join,
4733 : * and not including any movable clauses that were pushed down into the
4734 : * child paths).
4735 : *
4736 : * set_joinrel_size_estimates must have been applied already.
4737 : */
4738 : double
4739 1932 : get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
4740 : Path *outer_path,
4741 : Path *inner_path,
4742 : SpecialJoinInfo *sjinfo,
4743 : List *restrict_clauses)
4744 : {
4745 : double nrows;
4746 :
4747 : /*
4748 : * Estimate the number of rows returned by the parameterized join as the
4749 : * sizes of the input paths times the selectivity of the clauses that have
4750 : * ended up at this join node.
4751 : *
4752 : * As with set_joinrel_size_estimates, the rowcount estimate could depend
4753 : * on the pair of input paths provided, though ideally we'd get the same
4754 : * estimate for any pair with the same parameterization.
4755 : */
4756 1932 : nrows = calc_joinrel_size_estimate(root,
4757 : rel,
4758 : outer_path->parent,
4759 : inner_path->parent,
4760 : outer_path->rows,
4761 : inner_path->rows,
4762 : sjinfo,
4763 : restrict_clauses);
4764 : /* For safety, make sure result is not more than the base estimate */
4765 1932 : if (nrows > rel->rows)
4766 40 : nrows = rel->rows;
4767 1932 : return nrows;
4768 : }
4769 :
4770 : /*
4771 : * calc_joinrel_size_estimate
4772 : * Workhorse for set_joinrel_size_estimates and
4773 : * get_parameterized_joinrel_size.
4774 : *
4775 : * outer_rel/inner_rel are the relations being joined, but they should be
4776 : * assumed to have sizes outer_rows/inner_rows; those numbers might be less
4777 : * than what rel->rows says, when we are considering parameterized paths.
4778 : */
4779 : static double
4780 104260 : calc_joinrel_size_estimate(PlannerInfo *root,
4781 : RelOptInfo *joinrel,
4782 : RelOptInfo *outer_rel,
4783 : RelOptInfo *inner_rel,
4784 : double outer_rows,
4785 : double inner_rows,
4786 : SpecialJoinInfo *sjinfo,
4787 : List *restrictlist_in)
4788 : {
4789 : /* This apparently-useless variable dodges a compiler bug in VS2013: */
4790 104260 : List *restrictlist = restrictlist_in;
4791 104260 : JoinType jointype = sjinfo->jointype;
4792 : Selectivity fkselec;
4793 : Selectivity jselec;
4794 : Selectivity pselec;
4795 : double nrows;
4796 :
4797 : /*
4798 : * Compute joinclause selectivity. Note that we are only considering
4799 : * clauses that become restriction clauses at this join level; we are not
4800 : * double-counting them because they were not considered in estimating the
4801 : * sizes of the component rels.
4802 : *
4803 : * First, see whether any of the joinclauses can be matched to known FK
4804 : * constraints. If so, drop those clauses from the restrictlist, and
4805 : * instead estimate their selectivity using FK semantics. (We do this
4806 : * without regard to whether said clauses are local or "pushed down".
4807 : * Probably, an FK-matching clause could never be seen as pushed down at
4808 : * an outer join, since it would be strict and hence would be grounds for
4809 : * join strength reduction.) fkselec gets the net selectivity for
4810 : * FK-matching clauses, or 1.0 if there are none.
4811 : */
4812 104260 : fkselec = get_foreign_key_join_selectivity(root,
4813 : outer_rel->relids,
4814 : inner_rel->relids,
4815 : sjinfo,
4816 : &restrictlist);
4817 :
4818 : /*
4819 : * For an outer join, we have to distinguish the selectivity of the join's
4820 : * own clauses (JOIN/ON conditions) from any clauses that were "pushed
4821 : * down". For inner joins we just count them all as joinclauses.
4822 : */
4823 104260 : if (IS_OUTER_JOIN(jointype))
4824 : {
4825 57160 : List *joinquals = NIL;
4826 57160 : List *pushedquals = NIL;
4827 : ListCell *l;
4828 :
4829 : /* Grovel through the clauses to separate into two lists */
4830 128154 : foreach(l, restrictlist)
4831 : {
4832 70994 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
4833 :
4834 70994 : if (RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
4835 1896 : pushedquals = lappend(pushedquals, rinfo);
4836 : else
4837 69098 : joinquals = lappend(joinquals, rinfo);
4838 : }
4839 :
4840 : /* Get the separate selectivities */
4841 57160 : jselec = clauselist_selectivity(root,
4842 : joinquals,
4843 : 0,
4844 : jointype,
4845 : sjinfo);
4846 57160 : pselec = clauselist_selectivity(root,
4847 : pushedquals,
4848 : 0,
4849 : jointype,
4850 : sjinfo);
4851 :
4852 : /* Avoid leaking a lot of ListCells */
4853 57160 : list_free(joinquals);
4854 57160 : list_free(pushedquals);
4855 : }
4856 : else
4857 : {
4858 47100 : jselec = clauselist_selectivity(root,
4859 : restrictlist,
4860 : 0,
4861 : jointype,
4862 : sjinfo);
4863 47100 : pselec = 0.0; /* not used, keep compiler quiet */
4864 : }
4865 :
4866 : /*
4867 : * Basically, we multiply size of Cartesian product by selectivity.
4868 : *
4869 : * If we are doing an outer join, take that into account: the joinqual
4870 : * selectivity has to be clamped using the knowledge that the output must
4871 : * be at least as large as the non-nullable input. However, any
4872 : * pushed-down quals are applied after the outer join, so their
4873 : * selectivity applies fully.
4874 : *
4875 : * For JOIN_SEMI and JOIN_ANTI, the selectivity is defined as the fraction
4876 : * of LHS rows that have matches, and we apply that straightforwardly.
4877 : */
4878 104260 : switch (jointype)
4879 : {
4880 45006 : case JOIN_INNER:
4881 45006 : nrows = outer_rows * inner_rows * fkselec * jselec;
4882 : /* pselec not used */
4883 45006 : break;
4884 46190 : case JOIN_LEFT:
4885 46190 : nrows = outer_rows * inner_rows * fkselec * jselec;
4886 46190 : if (nrows < outer_rows)
4887 27970 : nrows = outer_rows;
4888 46190 : nrows *= pselec;
4889 46190 : break;
4890 1038 : case JOIN_FULL:
4891 1038 : nrows = outer_rows * inner_rows * fkselec * jselec;
4892 1038 : if (nrows < outer_rows)
4893 716 : nrows = outer_rows;
4894 1038 : if (nrows < inner_rows)
4895 58 : nrows = inner_rows;
4896 1038 : nrows *= pselec;
4897 1038 : break;
4898 2094 : case JOIN_SEMI:
4899 2094 : nrows = outer_rows * fkselec * jselec;
4900 : /* pselec not used */
4901 2094 : break;
4902 9932 : case JOIN_ANTI:
4903 9932 : nrows = outer_rows * (1.0 - fkselec * jselec);
4904 9932 : nrows *= pselec;
4905 9932 : break;
4906 0 : default:
4907 : /* other values not expected here */
4908 0 : elog(ERROR, "unrecognized join type: %d", (int) jointype);
4909 : nrows = 0; /* keep compiler quiet */
4910 : break;
4911 : }
4912 :
4913 104260 : return clamp_row_est(nrows);
4914 : }
4915 :
4916 : /*
4917 : * get_foreign_key_join_selectivity
4918 : * Estimate join selectivity for foreign-key-related clauses.
4919 : *
4920 : * Remove any clauses that can be matched to FK constraints from *restrictlist,
4921 : * and return a substitute estimate of their selectivity. 1.0 is returned
4922 : * when there are no such clauses.
4923 : *
4924 : * The reason for treating such clauses specially is that we can get better
4925 : * estimates this way than by relying on clauselist_selectivity(), especially
4926 : * for multi-column FKs where that function's assumption that the clauses are
4927 : * independent falls down badly. But even with single-column FKs, we may be
4928 : * able to get a better answer when the pg_statistic stats are missing or out
4929 : * of date.
4930 : */
4931 : static Selectivity
4932 104260 : get_foreign_key_join_selectivity(PlannerInfo *root,
4933 : Relids outer_relids,
4934 : Relids inner_relids,
4935 : SpecialJoinInfo *sjinfo,
4936 : List **restrictlist)
4937 : {
4938 104260 : Selectivity fkselec = 1.0;
4939 104260 : JoinType jointype = sjinfo->jointype;
4940 104260 : List *worklist = *restrictlist;
4941 : ListCell *lc;
4942 :
4943 : /* Consider each FK constraint that is known to match the query */
4944 105512 : foreach(lc, root->fkey_list)
4945 : {
4946 1252 : ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
4947 : bool ref_is_outer;
4948 : List *removedlist;
4949 : ListCell *cell;
4950 :
4951 : /*
4952 : * This FK is not relevant unless it connects a baserel on one side of
4953 : * this join to a baserel on the other side.
4954 : */
4955 2278 : if (bms_is_member(fkinfo->con_relid, outer_relids) &&
4956 1026 : bms_is_member(fkinfo->ref_relid, inner_relids))
4957 906 : ref_is_outer = false;
4958 568 : else if (bms_is_member(fkinfo->ref_relid, outer_relids) &&
4959 222 : bms_is_member(fkinfo->con_relid, inner_relids))
4960 82 : ref_is_outer = true;
4961 : else
4962 264 : continue;
4963 :
4964 : /*
4965 : * If we're dealing with a semi/anti join, and the FK's referenced
4966 : * relation is on the outside, then knowledge of the FK doesn't help
4967 : * us figure out what we need to know (which is the fraction of outer
4968 : * rows that have matches). On the other hand, if the referenced rel
4969 : * is on the inside, then all outer rows must have matches in the
4970 : * referenced table (ignoring nulls). But any restriction or join
4971 : * clauses that filter that table will reduce the fraction of matches.
4972 : * We can account for restriction clauses, but it's too hard to guess
4973 : * how many table rows would get through a join that's inside the RHS.
4974 : * Hence, if either case applies, punt and ignore the FK.
4975 : */
4976 988 : if ((jointype == JOIN_SEMI || jointype == JOIN_ANTI) &&
4977 678 : (ref_is_outer || bms_membership(inner_relids) != BMS_SINGLETON))
4978 0 : continue;
4979 :
4980 : /*
4981 : * Modify the restrictlist by removing clauses that match the FK (and
4982 : * putting them into removedlist instead). It seems unsafe to modify
4983 : * the originally-passed List structure, so we make a shallow copy the
4984 : * first time through.
4985 : */
4986 988 : if (worklist == *restrictlist)
4987 834 : worklist = list_copy(worklist);
4988 :
4989 988 : removedlist = NIL;
4990 2012 : foreach(cell, worklist)
4991 : {
4992 1024 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
4993 1024 : bool remove_it = false;
4994 : int i;
4995 :
4996 : /* Drop this clause if it matches any column of the FK */
4997 1234 : for (i = 0; i < fkinfo->nkeys; i++)
4998 : {
4999 1214 : if (rinfo->parent_ec)
5000 : {
5001 : /*
5002 : * EC-derived clauses can only match by EC. It is okay to
5003 : * consider any clause derived from the same EC as
5004 : * matching the FK: even if equivclass.c chose to generate
5005 : * a clause equating some other pair of Vars, it could
5006 : * have generated one equating the FK's Vars. So for
5007 : * purposes of estimation, we can act as though it did so.
5008 : *
5009 : * Note: checking parent_ec is a bit of a cheat because
5010 : * there are EC-derived clauses that don't have parent_ec
5011 : * set; but such clauses must compare expressions that
5012 : * aren't just Vars, so they cannot match the FK anyway.
5013 : */
5014 198 : if (fkinfo->eclass[i] == rinfo->parent_ec)
5015 : {
5016 198 : remove_it = true;
5017 198 : break;
5018 : }
5019 : }
5020 : else
5021 : {
5022 : /*
5023 : * Otherwise, see if rinfo was previously matched to FK as
5024 : * a "loose" clause.
5025 : */
5026 1016 : if (list_member_ptr(fkinfo->rinfos[i], rinfo))
5027 : {
5028 806 : remove_it = true;
5029 806 : break;
5030 : }
5031 : }
5032 : }
5033 1024 : if (remove_it)
5034 : {
5035 1004 : worklist = foreach_delete_current(worklist, cell);
5036 1004 : removedlist = lappend(removedlist, rinfo);
5037 : }
5038 : }
5039 :
5040 : /*
5041 : * If we failed to remove all the matching clauses we expected to
5042 : * find, chicken out and ignore this FK; applying its selectivity
5043 : * might result in double-counting. Put any clauses we did manage to
5044 : * remove back into the worklist.
5045 : *
5046 : * Since the matching clauses are known not outerjoin-delayed, they
5047 : * should certainly have appeared in the initial joinclause list. If
5048 : * we didn't find them, they must have been matched to, and removed
5049 : * by, some other FK in a previous iteration of this loop. (A likely
5050 : * case is that two FKs are matched to the same EC; there will be only
5051 : * one EC-derived clause in the initial list, so the first FK will
5052 : * consume it.) Applying both FKs' selectivity independently risks
5053 : * underestimating the join size; in particular, this would undo one
5054 : * of the main things that ECs were invented for, namely to avoid
5055 : * double-counting the selectivity of redundant equality conditions.
5056 : * Later we might think of a reasonable way to combine the estimates,
5057 : * but for now, just punt, since this is a fairly uncommon situation.
5058 : */
5059 988 : if (list_length(removedlist) !=
5060 988 : (fkinfo->nmatched_ec + fkinfo->nmatched_ri))
5061 : {
5062 162 : worklist = list_concat(worklist, removedlist);
5063 162 : continue;
5064 : }
5065 :
5066 : /*
5067 : * Finally we get to the payoff: estimate selectivity using the
5068 : * knowledge that each referencing row will match exactly one row in
5069 : * the referenced table.
5070 : *
5071 : * XXX that's not true in the presence of nulls in the referencing
5072 : * column(s), so in principle we should derate the estimate for those.
5073 : * However (1) if there are any strict restriction clauses for the
5074 : * referencing column(s) elsewhere in the query, derating here would
5075 : * be double-counting the null fraction, and (2) it's not very clear
5076 : * how to combine null fractions for multiple referencing columns. So
5077 : * we do nothing for now about correcting for nulls.
5078 : *
5079 : * XXX another point here is that if either side of an FK constraint
5080 : * is an inheritance parent, we estimate as though the constraint
5081 : * covers all its children as well. This is not an unreasonable
5082 : * assumption for a referencing table, ie the user probably applied
5083 : * identical constraints to all child tables (though perhaps we ought
5084 : * to check that). But it's not possible to have done that for a
5085 : * referenced table. Fortunately, precisely because that doesn't
5086 : * work, it is uncommon in practice to have an FK referencing a parent
5087 : * table. So, at least for now, disregard inheritance here.
5088 : */
5089 826 : if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
5090 524 : {
5091 : /*
5092 : * For JOIN_SEMI and JOIN_ANTI, we only get here when the FK's
5093 : * referenced table is exactly the inside of the join. The join
5094 : * selectivity is defined as the fraction of LHS rows that have
5095 : * matches. The FK implies that every LHS row has a match *in the
5096 : * referenced table*; but any restriction clauses on it will
5097 : * reduce the number of matches. Hence we take the join
5098 : * selectivity as equal to the selectivity of the table's
5099 : * restriction clauses, which is rows / tuples; but we must guard
5100 : * against tuples == 0.
5101 : */
5102 524 : RelOptInfo *ref_rel = find_base_rel(root, fkinfo->ref_relid);
5103 524 : double ref_tuples = Max(ref_rel->tuples, 1.0);
5104 :
5105 524 : fkselec *= ref_rel->rows / ref_tuples;
5106 : }
5107 : else
5108 : {
5109 : /*
5110 : * Otherwise, selectivity is exactly 1/referenced-table-size; but
5111 : * guard against tuples == 0. Note we should use the raw table
5112 : * tuple count, not any estimate of its filtered or joined size.
5113 : */
5114 302 : RelOptInfo *ref_rel = find_base_rel(root, fkinfo->ref_relid);
5115 302 : double ref_tuples = Max(ref_rel->tuples, 1.0);
5116 :
5117 302 : fkselec *= 1.0 / ref_tuples;
5118 : }
5119 : }
5120 :
5121 104260 : *restrictlist = worklist;
5122 104260 : return fkselec;
5123 : }
5124 :
5125 : /*
5126 : * set_subquery_size_estimates
5127 : * Set the size estimates for a base relation that is a subquery.
5128 : *
5129 : * The rel's targetlist and restrictinfo list must have been constructed
5130 : * already, and the Paths for the subquery must have been completed.
5131 : * We look at the subquery's PlannerInfo to extract data.
5132 : *
5133 : * We set the same fields as set_baserel_size_estimates.
5134 : */
5135 : void
5136 9244 : set_subquery_size_estimates(PlannerInfo *root, RelOptInfo *rel)
5137 : {
5138 9244 : PlannerInfo *subroot = rel->subroot;
5139 : RelOptInfo *sub_final_rel;
5140 : ListCell *lc;
5141 :
5142 : /* Should only be applied to base relations that are subqueries */
5143 : Assert(rel->relid > 0);
5144 : Assert(planner_rt_fetch(rel->relid, root)->rtekind == RTE_SUBQUERY);
5145 :
5146 : /*
5147 : * Copy raw number of output rows from subquery. All of its paths should
5148 : * have the same output rowcount, so just look at cheapest-total.
5149 : */
5150 9244 : sub_final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
5151 9244 : rel->tuples = sub_final_rel->cheapest_total_path->rows;
5152 :
5153 : /*
5154 : * Compute per-output-column width estimates by examining the subquery's
5155 : * targetlist. For any output that is a plain Var, get the width estimate
5156 : * that was made while planning the subquery. Otherwise, we leave it to
5157 : * set_rel_width to fill in a datatype-based default estimate.
5158 : */
5159 31026 : foreach(lc, subroot->parse->targetList)
5160 : {
5161 21782 : TargetEntry *te = lfirst_node(TargetEntry, lc);
5162 21782 : Node *texpr = (Node *) te->expr;
5163 21782 : int32 item_width = 0;
5164 :
5165 : /* junk columns aren't visible to upper query */
5166 21782 : if (te->resjunk)
5167 1000 : continue;
5168 :
5169 : /*
5170 : * The subquery could be an expansion of a view that's had columns
5171 : * added to it since the current query was parsed, so that there are
5172 : * non-junk tlist columns in it that don't correspond to any column
5173 : * visible at our query level. Ignore such columns.
5174 : */
5175 20782 : if (te->resno < rel->min_attr || te->resno > rel->max_attr)
5176 0 : continue;
5177 :
5178 : /*
5179 : * XXX This currently doesn't work for subqueries containing set
5180 : * operations, because the Vars in their tlists are bogus references
5181 : * to the first leaf subquery, which wouldn't give the right answer
5182 : * even if we could still get to its PlannerInfo.
5183 : *
5184 : * Also, the subquery could be an appendrel for which all branches are
5185 : * known empty due to constraint exclusion, in which case
5186 : * set_append_rel_pathlist will have left the attr_widths set to zero.
5187 : *
5188 : * In either case, we just leave the width estimate zero until
5189 : * set_rel_width fixes it.
5190 : */
5191 20782 : if (IsA(texpr, Var) &&
5192 10478 : subroot->parse->setOperations == NULL)
5193 : {
5194 9808 : Var *var = (Var *) texpr;
5195 9808 : RelOptInfo *subrel = find_base_rel(subroot, var->varno);
5196 :
5197 9808 : item_width = subrel->attr_widths[var->varattno - subrel->min_attr];
5198 : }
5199 20782 : rel->attr_widths[te->resno - rel->min_attr] = item_width;
5200 : }
5201 :
5202 : /* Now estimate number of output rows, etc */
5203 9244 : set_baserel_size_estimates(root, rel);
5204 9244 : }
5205 :
5206 : /*
5207 : * set_function_size_estimates
5208 : * Set the size estimates for a base relation that is a function call.
5209 : *
5210 : * The rel's targetlist and restrictinfo list must have been constructed
5211 : * already.
5212 : *
5213 : * We set the same fields as set_baserel_size_estimates.
5214 : */
5215 : void
5216 30506 : set_function_size_estimates(PlannerInfo *root, RelOptInfo *rel)
5217 : {
5218 : RangeTblEntry *rte;
5219 : ListCell *lc;
5220 :
5221 : /* Should only be applied to base relations that are functions */
5222 : Assert(rel->relid > 0);
5223 30506 : rte = planner_rt_fetch(rel->relid, root);
5224 : Assert(rte->rtekind == RTE_FUNCTION);
5225 :
5226 : /*
5227 : * Estimate number of rows the functions will return. The rowcount of the
5228 : * node is that of the largest function result.
5229 : */
5230 30506 : rel->tuples = 0;
5231 61204 : foreach(lc, rte->functions)
5232 : {
5233 30698 : RangeTblFunction *rtfunc = (RangeTblFunction *) lfirst(lc);
5234 30698 : double ntup = expression_returns_set_rows(root, rtfunc->funcexpr);
5235 :
5236 30698 : if (ntup > rel->tuples)
5237 30522 : rel->tuples = ntup;
5238 : }
5239 :
5240 : /* Now estimate number of output rows, etc */
5241 30506 : set_baserel_size_estimates(root, rel);
5242 30506 : }
5243 :
5244 : /*
5245 : * set_function_size_estimates
5246 : * Set the size estimates for a base relation that is a function call.
5247 : *
5248 : * The rel's targetlist and restrictinfo list must have been constructed
5249 : * already.
5250 : *
5251 : * We set the same fields as set_tablefunc_size_estimates.
5252 : */
5253 : void
5254 144 : set_tablefunc_size_estimates(PlannerInfo *root, RelOptInfo *rel)
5255 : {
5256 : /* Should only be applied to base relations that are functions */
5257 : Assert(rel->relid > 0);
5258 : Assert(planner_rt_fetch(rel->relid, root)->rtekind == RTE_TABLEFUNC);
5259 :
5260 144 : rel->tuples = 100;
5261 :
5262 : /* Now estimate number of output rows, etc */
5263 144 : set_baserel_size_estimates(root, rel);
5264 144 : }
5265 :
5266 : /*
5267 : * set_values_size_estimates
5268 : * Set the size estimates for a base relation that is a values list.
5269 : *
5270 : * The rel's targetlist and restrictinfo list must have been constructed
5271 : * already.
5272 : *
5273 : * We set the same fields as set_baserel_size_estimates.
5274 : */
5275 : void
5276 3950 : set_values_size_estimates(PlannerInfo *root, RelOptInfo *rel)
5277 : {
5278 : RangeTblEntry *rte;
5279 :
5280 : /* Should only be applied to base relations that are values lists */
5281 : Assert(rel->relid > 0);
5282 3950 : rte = planner_rt_fetch(rel->relid, root);
5283 : Assert(rte->rtekind == RTE_VALUES);
5284 :
5285 : /*
5286 : * Estimate number of rows the values list will return. We know this
5287 : * precisely based on the list length (well, barring set-returning
5288 : * functions in list items, but that's a refinement not catered for
5289 : * anywhere else either).
5290 : */
5291 3950 : rel->tuples = list_length(rte->values_lists);
5292 :
5293 : /* Now estimate number of output rows, etc */
5294 3950 : set_baserel_size_estimates(root, rel);
5295 3950 : }
5296 :
5297 : /*
5298 : * set_cte_size_estimates
5299 : * Set the size estimates for a base relation that is a CTE reference.
5300 : *
5301 : * The rel's targetlist and restrictinfo list must have been constructed
5302 : * already, and we need an estimate of the number of rows returned by the CTE
5303 : * (if a regular CTE) or the non-recursive term (if a self-reference).
5304 : *
5305 : * We set the same fields as set_baserel_size_estimates.
5306 : */
5307 : void
5308 1244 : set_cte_size_estimates(PlannerInfo *root, RelOptInfo *rel, double cte_rows)
5309 : {
5310 : RangeTblEntry *rte;
5311 :
5312 : /* Should only be applied to base relations that are CTE references */
5313 : Assert(rel->relid > 0);
5314 1244 : rte = planner_rt_fetch(rel->relid, root);
5315 : Assert(rte->rtekind == RTE_CTE);
5316 :
5317 1244 : if (rte->self_reference)
5318 : {
5319 : /*
5320 : * In a self-reference, arbitrarily assume the average worktable size
5321 : * is about 10 times the nonrecursive term's size.
5322 : */
5323 332 : rel->tuples = 10 * cte_rows;
5324 : }
5325 : else
5326 : {
5327 : /* Otherwise just believe the CTE's rowcount estimate */
5328 912 : rel->tuples = cte_rows;
5329 : }
5330 :
5331 : /* Now estimate number of output rows, etc */
5332 1244 : set_baserel_size_estimates(root, rel);
5333 1244 : }
5334 :
5335 : /*
5336 : * set_namedtuplestore_size_estimates
5337 : * Set the size estimates for a base relation that is a tuplestore reference.
5338 : *
5339 : * The rel's targetlist and restrictinfo list must have been constructed
5340 : * already.
5341 : *
5342 : * We set the same fields as set_baserel_size_estimates.
5343 : */
5344 : void
5345 260 : set_namedtuplestore_size_estimates(PlannerInfo *root, RelOptInfo *rel)
5346 : {
5347 : RangeTblEntry *rte;
5348 :
5349 : /* Should only be applied to base relations that are tuplestore references */
5350 : Assert(rel->relid > 0);
5351 260 : rte = planner_rt_fetch(rel->relid, root);
5352 : Assert(rte->rtekind == RTE_NAMEDTUPLESTORE);
5353 :
5354 : /*
5355 : * Use the estimate provided by the code which is generating the named
5356 : * tuplestore. In some cases, the actual number might be available; in
5357 : * others the same plan will be re-used, so a "typical" value might be
5358 : * estimated and used.
5359 : */
5360 260 : rel->tuples = rte->enrtuples;
5361 260 : if (rel->tuples < 0)
5362 0 : rel->tuples = 1000;
5363 :
5364 : /* Now estimate number of output rows, etc */
5365 260 : set_baserel_size_estimates(root, rel);
5366 260 : }
5367 :
5368 : /*
5369 : * set_result_size_estimates
5370 : * Set the size estimates for an RTE_RESULT base relation
5371 : *
5372 : * The rel's targetlist and restrictinfo list must have been constructed
5373 : * already.
5374 : *
5375 : * We set the same fields as set_baserel_size_estimates.
5376 : */
5377 : void
5378 670 : set_result_size_estimates(PlannerInfo *root, RelOptInfo *rel)
5379 : {
5380 : /* Should only be applied to RTE_RESULT base relations */
5381 : Assert(rel->relid > 0);
5382 : Assert(planner_rt_fetch(rel->relid, root)->rtekind == RTE_RESULT);
5383 :
5384 : /* RTE_RESULT always generates a single row, natively */
5385 670 : rel->tuples = 1;
5386 :
5387 : /* Now estimate number of output rows, etc */
5388 670 : set_baserel_size_estimates(root, rel);
5389 670 : }
5390 :
5391 : /*
5392 : * set_foreign_size_estimates
5393 : * Set the size estimates for a base relation that is a foreign table.
5394 : *
5395 : * There is not a whole lot that we can do here; the foreign-data wrapper
5396 : * is responsible for producing useful estimates. We can do a decent job
5397 : * of estimating baserestrictcost, so we set that, and we also set up width
5398 : * using what will be purely datatype-driven estimates from the targetlist.
5399 : * There is no way to do anything sane with the rows value, so we just put
5400 : * a default estimate and hope that the wrapper can improve on it. The
5401 : * wrapper's GetForeignRelSize function will be called momentarily.
5402 : *
5403 : * The rel's targetlist and restrictinfo list must have been constructed
5404 : * already.
5405 : */
5406 : void
5407 1822 : set_foreign_size_estimates(PlannerInfo *root, RelOptInfo *rel)
5408 : {
5409 : /* Should only be applied to base relations */
5410 : Assert(rel->relid > 0);
5411 :
5412 1822 : rel->rows = 1000; /* entirely bogus default estimate */
5413 :
5414 1822 : cost_qual_eval(&rel->baserestrictcost, rel->baserestrictinfo, root);
5415 :
5416 1822 : set_rel_width(root, rel);
5417 1822 : }
5418 :
5419 :
5420 : /*
5421 : * set_rel_width
5422 : * Set the estimated output width of a base relation.
5423 : *
5424 : * The estimated output width is the sum of the per-attribute width estimates
5425 : * for the actually-referenced columns, plus any PHVs or other expressions
5426 : * that have to be calculated at this relation. This is the amount of data
5427 : * we'd need to pass upwards in case of a sort, hash, etc.
5428 : *
5429 : * This function also sets reltarget->cost, so it's a bit misnamed now.
5430 : *
5431 : * NB: this works best on plain relations because it prefers to look at
5432 : * real Vars. For subqueries, set_subquery_size_estimates will already have
5433 : * copied up whatever per-column estimates were made within the subquery,
5434 : * and for other types of rels there isn't much we can do anyway. We fall
5435 : * back on (fairly stupid) datatype-based width estimates if we can't get
5436 : * any better number.
5437 : *
5438 : * The per-attribute width estimates are cached for possible re-use while
5439 : * building join relations or post-scan/join pathtargets.
5440 : */
5441 : static void
5442 284022 : set_rel_width(PlannerInfo *root, RelOptInfo *rel)
5443 : {
5444 284022 : Oid reloid = planner_rt_fetch(rel->relid, root)->relid;
5445 284022 : int32 tuple_width = 0;
5446 284022 : bool have_wholerow_var = false;
5447 : ListCell *lc;
5448 :
5449 : /* Vars are assumed to have cost zero, but other exprs do not */
5450 284022 : rel->reltarget->cost.startup = 0;
5451 284022 : rel->reltarget->cost.per_tuple = 0;
5452 :
5453 1191370 : foreach(lc, rel->reltarget->exprs)
5454 : {
5455 907348 : Node *node = (Node *) lfirst(lc);
5456 :
5457 : /*
5458 : * Ordinarily, a Var in a rel's targetlist must belong to that rel;
5459 : * but there are corner cases involving LATERAL references where that
5460 : * isn't so. If the Var has the wrong varno, fall through to the
5461 : * generic case (it doesn't seem worth the trouble to be any smarter).
5462 : */
5463 907348 : if (IsA(node, Var) &&
5464 902832 : ((Var *) node)->varno == rel->relid)
5465 190346 : {
5466 902792 : Var *var = (Var *) node;
5467 : int ndx;
5468 : int32 item_width;
5469 :
5470 : Assert(var->varattno >= rel->min_attr);
5471 : Assert(var->varattno <= rel->max_attr);
5472 :
5473 902792 : ndx = var->varattno - rel->min_attr;
5474 :
5475 : /*
5476 : * If it's a whole-row Var, we'll deal with it below after we have
5477 : * already cached as many attr widths as possible.
5478 : */
5479 902792 : if (var->varattno == 0)
5480 : {
5481 1722 : have_wholerow_var = true;
5482 1722 : continue;
5483 : }
5484 :
5485 : /*
5486 : * The width may have been cached already (especially if it's a
5487 : * subquery), so don't duplicate effort.
5488 : */
5489 901070 : if (rel->attr_widths[ndx] > 0)
5490 : {
5491 184562 : tuple_width += rel->attr_widths[ndx];
5492 184562 : continue;
5493 : }
5494 :
5495 : /* Try to get column width from statistics */
5496 716508 : if (reloid != InvalidOid && var->varattno > 0)
5497 : {
5498 595302 : item_width = get_attavgwidth(reloid, var->varattno);
5499 595302 : if (item_width > 0)
5500 : {
5501 526162 : rel->attr_widths[ndx] = item_width;
5502 526162 : tuple_width += item_width;
5503 526162 : continue;
5504 : }
5505 : }
5506 :
5507 : /*
5508 : * Not a plain relation, or can't find statistics for it. Estimate
5509 : * using just the type info.
5510 : */
5511 190346 : item_width = get_typavgwidth(var->vartype, var->vartypmod);
5512 : Assert(item_width > 0);
5513 190346 : rel->attr_widths[ndx] = item_width;
5514 190346 : tuple_width += item_width;
5515 : }
5516 4556 : else if (IsA(node, PlaceHolderVar))
5517 : {
5518 : /*
5519 : * We will need to evaluate the PHV's contained expression while
5520 : * scanning this rel, so be sure to include it in reltarget->cost.
5521 : */
5522 564 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
5523 564 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv, false);
5524 : QualCost cost;
5525 :
5526 564 : tuple_width += phinfo->ph_width;
5527 564 : cost_qual_eval_node(&cost, (Node *) phv->phexpr, root);
5528 564 : rel->reltarget->cost.startup += cost.startup;
5529 564 : rel->reltarget->cost.per_tuple += cost.per_tuple;
5530 : }
5531 : else
5532 : {
5533 : /*
5534 : * We could be looking at an expression pulled up from a subquery,
5535 : * or a ROW() representing a whole-row child Var, etc. Do what we
5536 : * can using the expression type information.
5537 : */
5538 : int32 item_width;
5539 : QualCost cost;
5540 :
5541 3992 : item_width = get_typavgwidth(exprType(node), exprTypmod(node));
5542 : Assert(item_width > 0);
5543 3992 : tuple_width += item_width;
5544 : /* Not entirely clear if we need to account for cost, but do so */
5545 3992 : cost_qual_eval_node(&cost, node, root);
5546 3992 : rel->reltarget->cost.startup += cost.startup;
5547 3992 : rel->reltarget->cost.per_tuple += cost.per_tuple;
5548 : }
5549 : }
5550 :
5551 : /*
5552 : * If we have a whole-row reference, estimate its width as the sum of
5553 : * per-column widths plus heap tuple header overhead.
5554 : */
5555 284022 : if (have_wholerow_var)
5556 : {
5557 1722 : int32 wholerow_width = MAXALIGN(SizeofHeapTupleHeader);
5558 :
5559 1722 : if (reloid != InvalidOid)
5560 : {
5561 : /* Real relation, so estimate true tuple width */
5562 1324 : wholerow_width += get_relation_data_width(reloid,
5563 1324 : rel->attr_widths - rel->min_attr);
5564 : }
5565 : else
5566 : {
5567 : /* Do what we can with info for a phony rel */
5568 : AttrNumber i;
5569 :
5570 1050 : for (i = 1; i <= rel->max_attr; i++)
5571 652 : wholerow_width += rel->attr_widths[i - rel->min_attr];
5572 : }
5573 :
5574 1722 : rel->attr_widths[0 - rel->min_attr] = wholerow_width;
5575 :
5576 : /*
5577 : * Include the whole-row Var as part of the output tuple. Yes, that
5578 : * really is what happens at runtime.
5579 : */
5580 1722 : tuple_width += wholerow_width;
5581 : }
5582 :
5583 : Assert(tuple_width >= 0);
5584 284022 : rel->reltarget->width = tuple_width;
5585 284022 : }
5586 :
5587 : /*
5588 : * set_pathtarget_cost_width
5589 : * Set the estimated eval cost and output width of a PathTarget tlist.
5590 : *
5591 : * As a notational convenience, returns the same PathTarget pointer passed in.
5592 : *
5593 : * Most, though not quite all, uses of this function occur after we've run
5594 : * set_rel_width() for base relations; so we can usually obtain cached width
5595 : * estimates for Vars. If we can't, fall back on datatype-based width
5596 : * estimates. Present early-planning uses of PathTargets don't need accurate
5597 : * widths badly enough to justify going to the catalogs for better data.
5598 : */
5599 : PathTarget *
5600 356758 : set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target)
5601 : {
5602 356758 : int32 tuple_width = 0;
5603 : ListCell *lc;
5604 :
5605 : /* Vars are assumed to have cost zero, but other exprs do not */
5606 356758 : target->cost.startup = 0;
5607 356758 : target->cost.per_tuple = 0;
5608 :
5609 1478258 : foreach(lc, target->exprs)
5610 : {
5611 1121500 : Node *node = (Node *) lfirst(lc);
5612 :
5613 1121500 : if (IsA(node, Var))
5614 : {
5615 629462 : Var *var = (Var *) node;
5616 : int32 item_width;
5617 :
5618 : /* We should not see any upper-level Vars here */
5619 : Assert(var->varlevelsup == 0);
5620 :
5621 : /* Try to get data from RelOptInfo cache */
5622 629462 : if (var->varno < root->simple_rel_array_size)
5623 : {
5624 629406 : RelOptInfo *rel = root->simple_rel_array[var->varno];
5625 :
5626 629406 : if (rel != NULL &&
5627 625412 : var->varattno >= rel->min_attr &&
5628 625412 : var->varattno <= rel->max_attr)
5629 : {
5630 625412 : int ndx = var->varattno - rel->min_attr;
5631 :
5632 625412 : if (rel->attr_widths[ndx] > 0)
5633 : {
5634 619780 : tuple_width += rel->attr_widths[ndx];
5635 619780 : continue;
5636 : }
5637 : }
5638 : }
5639 :
5640 : /*
5641 : * No cached data available, so estimate using just the type info.
5642 : */
5643 9682 : item_width = get_typavgwidth(var->vartype, var->vartypmod);
5644 : Assert(item_width > 0);
5645 9682 : tuple_width += item_width;
5646 : }
5647 : else
5648 : {
5649 : /*
5650 : * Handle general expressions using type info.
5651 : */
5652 : int32 item_width;
5653 : QualCost cost;
5654 :
5655 492038 : item_width = get_typavgwidth(exprType(node), exprTypmod(node));
5656 : Assert(item_width > 0);
5657 492038 : tuple_width += item_width;
5658 :
5659 : /* Account for cost, too */
5660 492038 : cost_qual_eval_node(&cost, node, root);
5661 492038 : target->cost.startup += cost.startup;
5662 492038 : target->cost.per_tuple += cost.per_tuple;
5663 : }
5664 : }
5665 :
5666 : Assert(tuple_width >= 0);
5667 356758 : target->width = tuple_width;
5668 :
5669 356758 : return target;
5670 : }
5671 :
5672 : /*
5673 : * relation_byte_size
5674 : * Estimate the storage space in bytes for a given number of tuples
5675 : * of a given width (size in bytes).
5676 : */
5677 : static double
5678 1599472 : relation_byte_size(double tuples, int width)
5679 : {
5680 1599472 : return tuples * (MAXALIGN(width) + MAXALIGN(SizeofHeapTupleHeader));
5681 : }
5682 :
5683 : /*
5684 : * page_size
5685 : * Returns an estimate of the number of pages covered by a given
5686 : * number of tuples of a given width (size in bytes).
5687 : */
5688 : static double
5689 4240 : page_size(double tuples, int width)
5690 : {
5691 4240 : return ceil(relation_byte_size(tuples, width) / BLCKSZ);
5692 : }
5693 :
5694 : /*
5695 : * Estimate the fraction of the work that each worker will do given the
5696 : * number of workers budgeted for the path.
5697 : */
5698 : static double
5699 79160 : get_parallel_divisor(Path *path)
5700 : {
5701 79160 : double parallel_divisor = path->parallel_workers;
5702 :
5703 : /*
5704 : * Early experience with parallel query suggests that when there is only
5705 : * one worker, the leader often makes a very substantial contribution to
5706 : * executing the parallel portion of the plan, but as more workers are
5707 : * added, it does less and less, because it's busy reading tuples from the
5708 : * workers and doing whatever non-parallel post-processing is needed. By
5709 : * the time we reach 4 workers, the leader no longer makes a meaningful
5710 : * contribution. Thus, for now, estimate that the leader spends 30% of
5711 : * its time servicing each worker, and the remainder executing the
5712 : * parallel plan.
5713 : */
5714 79160 : if (parallel_leader_participation)
5715 : {
5716 : double leader_contribution;
5717 :
5718 78806 : leader_contribution = 1.0 - (0.3 * path->parallel_workers);
5719 78806 : if (leader_contribution > 0)
5720 78258 : parallel_divisor += leader_contribution;
5721 : }
5722 :
5723 79160 : return parallel_divisor;
5724 : }
5725 :
5726 : /*
5727 : * compute_bitmap_pages
5728 : *
5729 : * compute number of pages fetched from heap in bitmap heap scan.
5730 : */
5731 : double
5732 353490 : compute_bitmap_pages(PlannerInfo *root, RelOptInfo *baserel, Path *bitmapqual,
5733 : int loop_count, Cost *cost, double *tuple)
5734 : {
5735 : Cost indexTotalCost;
5736 : Selectivity indexSelectivity;
5737 : double T;
5738 : double pages_fetched;
5739 : double tuples_fetched;
5740 : double heap_pages;
5741 : long maxentries;
5742 :
5743 : /*
5744 : * Fetch total cost of obtaining the bitmap, as well as its total
5745 : * selectivity.
5746 : */
5747 353490 : cost_bitmap_tree_node(bitmapqual, &indexTotalCost, &indexSelectivity);
5748 :
5749 : /*
5750 : * Estimate number of main-table pages fetched.
5751 : */
5752 353490 : tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
5753 :
5754 353490 : T = (baserel->pages > 1) ? (double) baserel->pages : 1.0;
5755 :
5756 : /*
5757 : * For a single scan, the number of heap pages that need to be fetched is
5758 : * the same as the Mackert and Lohman formula for the case T <= b (ie, no
5759 : * re-reads needed).
5760 : */
5761 353490 : pages_fetched = (2.0 * T * tuples_fetched) / (2.0 * T + tuples_fetched);
5762 :
5763 : /*
5764 : * Calculate the number of pages fetched from the heap. Then based on
5765 : * current work_mem estimate get the estimated maxentries in the bitmap.
5766 : * (Note that we always do this calculation based on the number of pages
5767 : * that would be fetched in a single iteration, even if loop_count > 1.
5768 : * That's correct, because only that number of entries will be stored in
5769 : * the bitmap at one time.)
5770 : */
5771 353490 : heap_pages = Min(pages_fetched, baserel->pages);
5772 353490 : maxentries = tbm_calculate_entries(work_mem * 1024L);
5773 :
5774 353490 : if (loop_count > 1)
5775 : {
5776 : /*
5777 : * For repeated bitmap scans, scale up the number of tuples fetched in
5778 : * the Mackert and Lohman formula by the number of scans, so that we
5779 : * estimate the number of pages fetched by all the scans. Then
5780 : * pro-rate for one scan.
5781 : */
5782 69678 : pages_fetched = index_pages_fetched(tuples_fetched * loop_count,
5783 : baserel->pages,
5784 : get_indexpath_pages(bitmapqual),
5785 : root);
5786 69678 : pages_fetched /= loop_count;
5787 : }
5788 :
5789 353490 : if (pages_fetched >= T)
5790 26852 : pages_fetched = T;
5791 : else
5792 326638 : pages_fetched = ceil(pages_fetched);
5793 :
5794 353490 : if (maxentries < heap_pages)
5795 : {
5796 : double exact_pages;
5797 : double lossy_pages;
5798 :
5799 : /*
5800 : * Crude approximation of the number of lossy pages. Because of the
5801 : * way tbm_lossify() is coded, the number of lossy pages increases
5802 : * very sharply as soon as we run short of memory; this formula has
5803 : * that property and seems to perform adequately in testing, but it's
5804 : * possible we could do better somehow.
5805 : */
5806 12 : lossy_pages = Max(0, heap_pages - maxentries / 2);
5807 12 : exact_pages = heap_pages - lossy_pages;
5808 :
5809 : /*
5810 : * If there are lossy pages then recompute the number of tuples
5811 : * processed by the bitmap heap node. We assume here that the chance
5812 : * of a given tuple coming from an exact page is the same as the
5813 : * chance that a given page is exact. This might not be true, but
5814 : * it's not clear how we can do any better.
5815 : */
5816 12 : if (lossy_pages > 0)
5817 : tuples_fetched =
5818 24 : clamp_row_est(indexSelectivity *
5819 24 : (exact_pages / heap_pages) * baserel->tuples +
5820 12 : (lossy_pages / heap_pages) * baserel->tuples);
5821 : }
5822 :
5823 353490 : if (cost)
5824 274658 : *cost = indexTotalCost;
5825 353490 : if (tuple)
5826 274658 : *tuple = tuples_fetched;
5827 :
5828 353490 : return pages_fetched;
5829 : }
|
