Debian Codegraph @

src/backend/optimizer/path/costsize.c

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