| blob | 10aeebc2c1d6e620cf371075ba6060b8c682312c |
1 /*-------------------------------------------------------------------------
2 *
3 * allpaths.c
4 * Routines to find possible search paths for processing a query
5 *
6 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/optimizer/path/allpaths.c
12 *
13 *-------------------------------------------------------------------------
14 */
18 #include <limits.h>
19 #include <math.h>
31 #ifdef OPTIMIZER_DEBUG
33 #endif
52 /* Bitmask flags for pushdown_safety_info.unsafeFlags */
53 #define UNSAFE_HAS_VOLATILE_FUNC (1 << 0)
54 #define UNSAFE_HAS_SET_FUNC (1 << 1)
55 #define UNSAFE_NOTIN_DISTINCTON_CLAUSE (1 << 2)
56 #define UNSAFE_NOTIN_PARTITIONBY_CLAUSE (1 << 3)
57 #define UNSAFE_TYPE_MISMATCH (1 << 4)
59 /* results of subquery_is_pushdown_safe */
61 {
63 * column is unsafe for qual pushdown, or 0 if
64 * no reason. */
69 /* Return type for qual_is_pushdown_safe */
71 {
75 * run condition */
78 /* These parameters are set by GUC */
84 /* Hook for plugins to get control in set_rel_pathlist() */
87 /* Hook for plugins to replace standard_join_search() */
122 Relids required_outer);
165 /*
166 * make_one_rel
167 * Finds all possible access paths for executing a query, returning a
168 * single rel that represents the join of all base rels in the query.
169 */
170 RelOptInfo *
172 {
174 Index rti;
177 /* Mark base rels as to whether we care about fast-start plans */
180 /*
181 * Compute size estimates and consider_parallel flags for each base rel.
182 */
185 /*
186 * We should now have size estimates for every actual table involved in
187 * the query, and we also know which if any have been deleted from the
188 * query by join removal, pruned by partition pruning, or eliminated by
189 * constraint exclusion. So we can now compute total_table_pages.
190 *
191 * Note that appendrels are not double-counted here, even though we don't
192 * bother to distinguish RelOptInfos for appendrel parents, because the
193 * parents will have pages = 0.
194 *
195 * XXX if a table is self-joined, we will count it once per appearance,
196 * which perhaps is the wrong thing ... but that's not completely clear,
197 * and detecting self-joins here is difficult, so ignore it for now.
198 */
201 {
204 /* there may be empty slots corresponding to non-baserel RTEs */
215 }
218 /*
219 * Generate access paths for each base rel.
220 */
223 /*
224 * Generate access paths for the entire join tree.
225 */
228 /*
229 * The result should join all and only the query's base + outer-join rels.
230 */
234 }
236 /*
237 * set_base_rel_consider_startup
238 * Set the consider_[param_]startup flags for each base-relation entry.
239 *
240 * For the moment, we only deal with consider_param_startup here; because the
241 * logic for consider_startup is pretty trivial and is the same for every base
242 * relation, we just let build_simple_rel() initialize that flag correctly to
243 * start with. If that logic ever gets more complicated it would probably
244 * be better to move it here.
245 */
246 static void
248 {
249 /*
250 * Since parameterized paths can only be used on the inside of a nestloop
251 * join plan, there is usually little value in considering fast-start
252 * plans for them. However, for relations that are on the RHS of a SEMI
253 * or ANTI join, a fast-start plan can be useful because we're only going
254 * to care about fetching one tuple anyway.
255 *
256 * To minimize growth of planning time, we currently restrict this to
257 * cases where the RHS is a single base relation, not a join; there is no
258 * provision for consider_param_startup to get set at all on joinrels.
259 * Also we don't worry about appendrels. costsize.c's costing rules for
260 * nestloop semi/antijoins don't consider such cases either.
261 */
265 {
271 {
275 }
276 }
277 }
279 /*
280 * set_base_rel_sizes
281 * Set the size estimates (rows and widths) for each base-relation entry.
282 * Also determine whether to consider parallel paths for base relations.
283 *
284 * We do this in a separate pass over the base rels so that rowcount
285 * estimates are available for parameterized path generation, and also so
286 * that each rel's consider_parallel flag is set correctly before we begin to
287 * generate paths.
288 */
289 static void
291 {
292 Index rti;
295 {
299 /* there may be empty slots corresponding to non-baserel RTEs */
305 /* ignore RTEs that are "other rels" */
311 /*
312 * If parallelism is allowable for this query in general, see whether
313 * it's allowable for this rel in particular. We have to do this
314 * before set_rel_size(), because (a) if this rel is an inheritance
315 * parent, set_append_rel_size() will use and perhaps change the rel's
316 * consider_parallel flag, and (b) for some RTE types, set_rel_size()
317 * goes ahead and makes paths immediately.
318 */
323 }
324 }
326 /*
327 * set_base_rel_pathlists
328 * Finds all paths available for scanning each base-relation entry.
329 * Sequential scan and any available indices are considered.
330 * Each useful path is attached to its relation's 'pathlist' field.
331 */
332 static void
334 {
335 Index rti;
338 {
341 /* there may be empty slots corresponding to non-baserel RTEs */
347 /* ignore RTEs that are "other rels" */
352 }
353 }
355 /*
356 * set_rel_size
357 * Set size estimates for a base relation
358 */
359 static void
362 {
365 {
366 /*
367 * We proved we don't need to scan the rel via constraint exclusion,
368 * so set up a single dummy path for it. Here we only check this for
369 * regular baserels; if it's an otherrel, CE was already checked in
370 * set_append_rel_size().
371 *
372 * In this case, we go ahead and set up the relation's path right away
373 * instead of leaving it for set_rel_pathlist to do. This is because
374 * we don't have a convention for marking a rel as dummy except by
375 * assigning a dummy path to it.
376 */
378 }
380 {
381 /* It's an "append relation", process accordingly */
383 }
384 else
385 {
387 {
390 {
391 /* Foreign table */
393 }
395 {
396 /*
397 * We could get here if asked to scan a partitioned table
398 * with ONLY. In that case we shouldn't scan any of the
399 * partitions, so mark it as a dummy rel.
400 */
402 }
404 {
405 /* Sampled relation */
407 }
408 else
409 {
410 /* Plain relation */
412 }
416 /*
417 * Subqueries don't support making a choice between
418 * parameterized and unparameterized paths, so just go ahead
419 * and build their paths immediately.
420 */
434 /*
435 * CTEs don't support making a choice between parameterized
436 * and unparameterized paths, so just go ahead and build their
437 * paths immediately.
438 */
441 else
445 /* Might as well just build the path immediately */
449 /* Might as well just build the path immediately */
455 }
456 }
458 /*
459 * We insist that all non-dummy rels have a nonzero rowcount estimate.
460 */
462 }
464 /*
465 * set_rel_pathlist
466 * Build access paths for a base relation
467 */
468 static void
471 {
473 {
474 /* We already proved the relation empty, so nothing more to do */
475 }
477 {
478 /* It's an "append relation", process accordingly */
480 }
481 else
482 {
484 {
487 {
488 /* Foreign table */
490 }
492 {
493 /* Sampled relation */
495 }
496 else
497 {
498 /* Plain relation */
500 }
503 /* Subquery --- fully handled during set_rel_size */
506 /* RangeFunction */
510 /* Table Function */
514 /* Values list */
518 /* CTE reference --- fully handled during set_rel_size */
521 /* tuplestore reference --- fully handled during set_rel_size */
524 /* simple Result --- fully handled during set_rel_size */
529 }
530 }
532 /*
533 * Allow a plugin to editorialize on the set of Paths for this base
534 * relation. It could add new paths (such as CustomPaths) by calling
535 * add_path(), or add_partial_path() if parallel aware. It could also
536 * delete or modify paths added by the core code.
537 */
541 /*
542 * If this is a baserel, we should normally consider gathering any partial
543 * paths we may have created for it. We have to do this after calling the
544 * set_rel_pathlist_hook, else it cannot add partial paths to be included
545 * here.
546 *
547 * However, if this is an inheritance child, skip it. Otherwise, we could
548 * end up with a very large number of gather nodes, each trying to grab
549 * its own pool of workers. Instead, we'll consider gathering partial
550 * paths for the parent appendrel.
551 *
552 * Also, if this is the topmost scan/join rel, we postpone gathering until
553 * the final scan/join targetlist is available (see grouping_planner).
554 */
559 /* Now find the cheapest of the paths for this rel */
562 #ifdef OPTIMIZER_DEBUG
564 #endif
565 }
567 /*
568 * set_plain_rel_size
569 * Set size estimates for a plain relation (no subquery, no inheritance)
570 */
571 static void
573 {
574 /*
575 * Test any partial indexes of rel for applicability. We must do this
576 * first since partial unique indexes can affect size estimates.
577 */
580 /* Mark rel with estimated output rows, width, etc */
582 }
584 /*
585 * If this relation could possibly be scanned from within a worker, then set
586 * its consider_parallel flag.
587 */
588 static void
591 {
592 /*
593 * The flag has previously been initialized to false, so we can just
594 * return if it becomes clear that we can't safely set it.
595 */
598 /* Don't call this if parallelism is disallowed for the entire query. */
601 /* This should only be called for baserels and appendrel children. */
604 /* Assorted checks based on rtekind. */
606 {
609 /*
610 * Currently, parallel workers can't access the leader's temporary
611 * tables. We could possibly relax this if we wrote all of its
612 * local buffers at the start of the query and made no changes
613 * thereafter (maybe we could allow hint bit changes), and if we
614 * taught the workers to read them. Writing a large number of
615 * temporary buffers could be expensive, though, and we don't have
616 * the rest of the necessary infrastructure right now anyway. So
617 * for now, bail out if we see a temporary table.
618 */
622 /*
623 * Table sampling can be pushed down to workers if the sample
624 * function and its arguments are safe.
625 */
627 {
634 }
636 /*
637 * Ask FDWs whether they can support performing a ForeignScan
638 * within a worker. Most often, the answer will be no. For
639 * example, if the nature of the FDW is such that it opens a TCP
640 * connection with a remote server, each parallel worker would end
641 * up with a separate connection, and these connections might not
642 * be appropriately coordinated between workers and the leader.
643 */
645 {
651 }
653 /*
654 * There are additional considerations for appendrels, which we'll
655 * deal with in set_append_rel_size and set_append_rel_pathlist.
656 * For now, just set consider_parallel based on the rel's own
657 * quals and targetlist.
658 */
663 /*
664 * There's no intrinsic problem with scanning a subquery-in-FROM
665 * (as distinct from a SubPlan or InitPlan) in a parallel worker.
666 * If the subquery doesn't happen to have any parallel-safe paths,
667 * then flagging it as consider_parallel won't change anything,
668 * but that's true for plain tables, too. We must set
669 * consider_parallel based on the rel's own quals and targetlist,
670 * so that if a subquery path is parallel-safe but the quals and
671 * projection we're sticking onto it are not, we correctly mark
672 * the SubqueryScanPath as not parallel-safe. (Note that
673 * set_subquery_pathlist() might push some of these quals down
674 * into the subquery itself, but that doesn't change anything.)
675 *
676 * We can't push sub-select containing LIMIT/OFFSET to workers as
677 * there is no guarantee that the row order will be fully
678 * deterministic, and applying LIMIT/OFFSET will lead to
679 * inconsistent results at the top-level. (In some cases, where
680 * the result is ordered, we could relax this restriction. But it
681 * doesn't currently seem worth expending extra effort to do so.)
682 */
683 {
688 }
692 /* Shouldn't happen; we're only considering baserels here. */
697 /* Check for parallel-restricted functions. */
703 /* not parallel safe */
707 /* Check for parallel-restricted functions. */
714 /*
715 * CTE tuplestores aren't shared among parallel workers, so we
716 * force all CTE scans to happen in the leader. Also, populating
717 * the CTE would require executing a subplan that's not available
718 * in the worker, might be parallel-restricted, and must get
719 * executed only once.
720 */
725 /*
726 * tuplestore cannot be shared, at least without more
727 * infrastructure to support that.
728 */
732 /* RESULT RTEs, in themselves, are no problem. */
734 }
736 /*
737 * If there's anything in baserestrictinfo that's parallel-restricted, we
738 * give up on parallelizing access to this relation. We could consider
739 * instead postponing application of the restricted quals until we're
740 * above all the parallelism in the plan tree, but it's not clear that
741 * that would be a win in very many cases, and it might be tricky to make
742 * outer join clauses work correctly. It would likely break equivalence
743 * classes, too.
744 */
748 /*
749 * Likewise, if the relation's outputs are not parallel-safe, give up.
750 * (Usually, they're just Vars, but sometimes they're not.)
751 */
755 /* We have a winner. */
757 }
759 /*
760 * set_plain_rel_pathlist
761 * Build access paths for a plain relation (no subquery, no inheritance)
762 */
763 static void
765 {
766 Relids required_outer;
768 /*
769 * We don't support pushing join clauses into the quals of a seqscan, but
770 * it could still have required parameterization due to LATERAL refs in
771 * its tlist.
772 */
775 /* Consider sequential scan */
778 /* If appropriate, consider parallel sequential scan */
782 /* Consider index scans */
785 /* Consider TID scans */
787 }
789 /*
790 * create_plain_partial_paths
791 * Build partial access paths for parallel scan of a plain relation
792 */
793 static void
795 {
799 max_parallel_workers_per_gather);
801 /* If any limit was set to zero, the user doesn't want a parallel scan. */
805 /* Add an unordered partial path based on a parallel sequential scan. */
807 }
809 /*
810 * set_tablesample_rel_size
811 * Set size estimates for a sampled relation
812 */
813 static void
815 {
818 BlockNumber pages;
821 /*
822 * Test any partial indexes of rel for applicability. We must do this
823 * first since partial unique indexes can affect size estimates.
824 */
827 /*
828 * Call the sampling method's estimation function to estimate the number
829 * of pages it will read and the number of tuples it will return. (Note:
830 * we assume the function returns sane values.)
831 */
836 /*
837 * For the moment, because we will only consider a SampleScan path for the
838 * rel, it's okay to just overwrite the pages and tuples estimates for the
839 * whole relation. If we ever consider multiple path types for sampled
840 * rels, we'll need more complication.
841 */
845 /* Mark rel with estimated output rows, width, etc */
847 }
849 /*
850 * set_tablesample_rel_pathlist
851 * Build access paths for a sampled relation
852 */
853 static void
855 {
856 Relids required_outer;
859 /*
860 * We don't support pushing join clauses into the quals of a samplescan,
861 * but it could still have required parameterization due to LATERAL refs
862 * in its tlist or TABLESAMPLE arguments.
863 */
866 /* Consider sampled scan */
869 /*
870 * If the sampling method does not support repeatable scans, we must avoid
871 * plans that would scan the rel multiple times. Ideally, we'd simply
872 * avoid putting the rel on the inside of a nestloop join; but adding such
873 * a consideration to the planner seems like a great deal of complication
874 * to support an uncommon usage of second-rate sampling methods. Instead,
875 * if there is a risk that the query might perform an unsafe join, just
876 * wrap the SampleScan in a Materialize node. We can check for joins by
877 * counting the membership of all_query_rels (note that this correctly
878 * counts inheritance trees as single rels). If we're inside a subquery,
879 * we can't easily check whether a join might occur in the outer query, so
880 * just assume one is possible.
881 *
882 * GetTsmRoutine is relatively expensive compared to the other tests here,
883 * so check repeatable_across_scans last, even though that's a bit odd.
884 */
888 {
890 }
894 /* For the moment, at least, there are no other paths to consider */
895 }
897 /*
898 * set_foreign_size
899 * Set size estimates for a foreign table RTE
900 */
901 static void
903 {
904 /* Mark rel with estimated output rows, width, etc */
907 /* Let FDW adjust the size estimates, if it can */
910 /* ... but do not let it set the rows estimate to zero */
913 /*
914 * Also, make sure rel->tuples is not insane relative to rel->rows.
915 * Notably, this ensures sanity if pg_class.reltuples contains -1 and the
916 * FDW doesn't do anything to replace that.
917 */
919 }
921 /*
922 * set_foreign_pathlist
923 * Build access paths for a foreign table RTE
924 */
925 static void
927 {
928 /* Call the FDW's GetForeignPaths function to generate path(s) */
930 }
932 /*
933 * set_append_rel_size
934 * Set size estimates for a simple "append relation"
935 *
936 * The passed-in rel and RTE represent the entire append relation. The
937 * relation's contents are computed by appending together the output of the
938 * individual member relations. Note that in the non-partitioned inheritance
939 * case, the first member relation is actually the same table as is mentioned
940 * in the parent RTE ... but it has a different RTE and RelOptInfo. This is
941 * a good thing because their outputs are not the same size.
942 */
943 static void
946 {
955 /* Guard against stack overflow due to overly deep inheritance tree. */
960 /*
961 * If this is a partitioned baserel, set the consider_partitionwise_join
962 * flag; currently, we only consider partitionwise joins with the baserel
963 * if its targetlist doesn't contain a whole-row Var.
964 */
971 /*
972 * Initialize to compute size estimates for whole append relation.
973 *
974 * We handle width estimates by weighting the widths of different child
975 * rels proportionally to their number of rows. This is sensible because
976 * the use of width estimates is mainly to compute the total relation
977 * "footprint" if we have to sort or hash it. To do this, we sum the
978 * total equivalent size (in "double" arithmetic) and then divide by the
979 * total rowcount estimate. This is done separately for the total rel
980 * width and each attribute.
981 *
982 * Note: if you consider changing this logic, beware that child rels could
983 * have zero rows and/or width, if they were excluded by constraints.
984 */
992 {
1002 /* append_rel_list contains all append rels; ignore others */
1009 /*
1010 * The child rel's RelOptInfo was already created during
1011 * add_other_rels_to_query.
1012 */
1016 /* We may have already proven the child to be dummy. */
1020 /*
1021 * We have to copy the parent's targetlist and quals to the child,
1022 * with appropriate substitution of variables. However, the
1023 * baserestrictinfo quals were already copied/substituted when the
1024 * child RelOptInfo was built. So we don't need any additional setup
1025 * before applying constraint exclusion.
1026 */
1028 {
1029 /*
1030 * This child need not be scanned, so we can omit it from the
1031 * appendrel.
1032 */
1035 }
1037 /*
1038 * Constraint exclusion failed, so copy the parent's join quals and
1039 * targetlist to the child, with appropriate variable substitutions.
1040 *
1041 * We skip join quals that came from above outer joins that can null
1042 * this rel, since they would be of no value while generating paths
1043 * for the child. This saves some effort while processing the child
1044 * rel, and it also avoids an implementation restriction in
1045 * adjust_appendrel_attrs (it can't apply nullingrels to a non-Var).
1046 */
1049 {
1057 }
1060 /*
1061 * Now for the child's targetlist.
1062 *
1063 * NB: the resulting childrel->reltarget->exprs may contain arbitrary
1064 * expressions, which otherwise would not occur in a rel's targetlist.
1065 * Code that might be looking at an appendrel child must cope with
1066 * such. (Normally, a rel's targetlist would only include Vars and
1067 * PlaceHolderVars.) XXX we do not bother to update the cost or width
1068 * fields of childrel->reltarget; not clear if that would be useful.
1069 */
1075 /*
1076 * We have to make child entries in the EquivalenceClass data
1077 * structures as well. This is needed either if the parent
1078 * participates in some eclass joins (because we will want to consider
1079 * inner-indexscan joins on the individual children) or if the parent
1080 * has useful pathkeys (because we should try to build MergeAppend
1081 * paths that produce those sort orderings).
1082 */
1087 /*
1088 * Note: we could compute appropriate attr_needed data for the child's
1089 * variables, by transforming the parent's attr_needed through the
1090 * translated_vars mapping. However, currently there's no need
1091 * because attr_needed is only examined for base relations not
1092 * otherrels. So we just leave the child's attr_needed empty.
1093 */
1095 /*
1096 * If we consider partitionwise joins with the parent rel, do the same
1097 * for partitioned child rels.
1098 *
1099 * Note: here we abuse the consider_partitionwise_join flag by setting
1100 * it for child rels that are not themselves partitioned. We do so to
1101 * tell try_partitionwise_join() that the child rel is sufficiently
1102 * valid to be used as a per-partition input, even if it later gets
1103 * proven to be dummy. (It's not usable until we've set up the
1104 * reltarget and EC entries, which we just did.)
1105 */
1109 /*
1110 * If parallelism is allowable for this query in general, see whether
1111 * it's allowable for this childrel in particular. But if we've
1112 * already decided the appendrel is not parallel-safe as a whole,
1113 * there's no point in considering parallelism for this child. For
1114 * consistency, do this before calling set_rel_size() for the child.
1115 */
1119 /*
1120 * Compute the child's size.
1121 */
1124 /*
1125 * It is possible that constraint exclusion detected a contradiction
1126 * within a child subquery, even though we didn't prove one above. If
1127 * so, we can skip this child.
1128 */
1132 /* We have at least one live child. */
1135 /*
1136 * If any live child is not parallel-safe, treat the whole appendrel
1137 * as not parallel-safe. In future we might be able to generate plans
1138 * in which some children are farmed out to workers while others are
1139 * not; but we don't have that today, so it's a waste to consider
1140 * partial paths anywhere in the appendrel unless it's all safe.
1141 * (Child rels visited before this one will be unmarked in
1142 * set_append_rel_pathlist().)
1143 */
1147 /*
1148 * Accumulate size information from each live child.
1149 */
1155 /*
1156 * Accumulate per-column estimates too. We need not do anything for
1157 * PlaceHolderVars in the parent list. If child expression isn't a
1158 * Var, or we didn't record a width estimate for it, we have to fall
1159 * back on a datatype-based estimate.
1160 *
1161 * By construction, child's targetlist is 1-to-1 with parent's.
1162 */
1165 {
1170 {
1176 {
1180 }
1186 }
1187 }
1188 }
1191 {
1192 /*
1193 * Save the finished size estimates.
1194 */
1203 /*
1204 * Set "raw tuples" count equal to "rows" for the appendrel; needed
1205 * because some places assume rel->tuples is valid for any baserel.
1206 */
1209 /*
1210 * Note that we leave rel->pages as zero; this is important to avoid
1211 * double-counting the appendrel tree in total_table_pages.
1212 */
1213 }
1214 else
1215 {
1216 /*
1217 * All children were excluded by constraints, so mark the whole
1218 * appendrel dummy. We must do this in this phase so that the rel's
1219 * dummy-ness is visible when we generate paths for other rels.
1220 */
1222 }
1225 }
1227 /*
1228 * set_append_rel_pathlist
1229 * Build access paths for an "append relation"
1230 */
1231 static void
1234 {
1239 /*
1240 * Generate access paths for each member relation, and remember the
1241 * non-dummy children.
1242 */
1244 {
1250 /* append_rel_list contains all append rels; ignore others */
1254 /* Re-locate the child RTE and RelOptInfo */
1259 /*
1260 * If set_append_rel_size() decided the parent appendrel was
1261 * parallel-unsafe at some point after visiting this child rel, we
1262 * need to propagate the unsafety marking down to the child, so that
1263 * we don't generate useless partial paths for it.
1264 */
1268 /*
1269 * Compute the child's access paths.
1270 */
1273 /*
1274 * If child is dummy, ignore it.
1275 */
1279 /*
1280 * Child is live, so add it to the live_childrels list for use below.
1281 */
1283 }
1285 /* Add paths to the append relation. */
1287 }
1290 /*
1291 * add_paths_to_append_rel
1292 * Generate paths for the given append relation given the set of non-dummy
1293 * child rels.
1294 *
1295 * The function collects all parameterizations and orderings supported by the
1296 * non-dummy children. For every such parameterization or ordering, it creates
1297 * an append path collecting one path from each non-dummy child with given
1298 * parameterization or ordering. Similarly it collects partial paths from
1299 * non-dummy children to create partial append paths.
1300 */
1301 void
1304 {
1319 /* If appropriate, consider parallel append */
1322 /*
1323 * For every non-dummy child, remember the cheapest path. Also, identify
1324 * all pathkeys (orderings) and parameterizations (required_outer sets)
1325 * available for the non-dummy member relations.
1326 */
1328 {
1333 /*
1334 * If child has an unparameterized cheapest-total path, add that to
1335 * the unparameterized Append path we are constructing for the parent.
1336 * If not, there's no workable unparameterized path.
1337 *
1338 * With partitionwise aggregates, the child rel's pathlist may be
1339 * empty, so don't assume that a path exists here.
1340 */
1345 else
1348 /*
1349 * When the planner is considering cheap startup plans, we'll also
1350 * collect all the cheapest_startup_paths (if set) and build an
1351 * AppendPath containing those as subpaths.
1352 */
1354 {
1355 /* cheapest_startup_path must not be a parameterized path. */
1359 NULL);
1360 }
1361 else
1365 /* Same idea, but for a partial plan. */
1367 {
1371 }
1372 else
1375 /*
1376 * Same idea, but for a parallel append mixing partial and non-partial
1377 * paths.
1378 */
1380 {
1383 nppath =
1387 {
1388 /* Neither a partial nor a parallel-safe path? Forget it. */
1390 }
1394 {
1395 /* Partial path is cheaper or the only option. */
1400 }
1401 else
1402 {
1403 /*
1404 * Either we've got only a non-partial path, or we think that
1405 * a single backend can execute the best non-partial path
1406 * faster than all the parallel backends working together can
1407 * execute the best partial path.
1408 *
1409 * It might make sense to be more aggressive here. Even if
1410 * the best non-partial path is more expensive than the best
1411 * partial path, it could still be better to choose the
1412 * non-partial path if there are several such paths that can
1413 * be given to different workers. For now, we don't try to
1414 * figure that out.
1415 */
1418 NULL);
1419 }
1420 }
1422 /*
1423 * Collect lists of all the available path orderings and
1424 * parameterizations for all the children. We use these as a
1425 * heuristic to indicate which sort orderings and parameterizations we
1426 * should build Append and MergeAppend paths for.
1427 */
1429 {
1434 /* Unsorted paths don't contribute to pathkey list */
1436 {
1440 /* Have we already seen this ordering? */
1442 {
1447 {
1450 }
1451 }
1453 {
1454 /* No, so add it to all_child_pathkeys */
1456 childkeys);
1457 }
1458 }
1460 /* Unparameterized paths don't contribute to param-set list */
1462 {
1466 /* Have we already seen this param set? */
1468 {
1472 {
1475 }
1476 }
1478 {
1479 /* No, so add it to all_child_outers */
1481 childouter);
1482 }
1483 }
1484 }
1485 }
1487 /*
1488 * If we found unparameterized paths for all children, build an unordered,
1489 * unparameterized Append path for the rel. (Note: this is correct even
1490 * if we have zero or one live subpath due to constraint exclusion.)
1491 */
1497 /* build an AppendPath for the cheap startup paths, if valid */
1502 /*
1503 * Consider an append of unordered, unparameterized partial paths. Make
1504 * it parallel-aware if possible.
1505 */
1507 {
1512 /* Find the highest number of workers requested for any subpath. */
1514 {
1518 }
1521 /*
1522 * If the use of parallel append is permitted, always request at least
1523 * log2(# of children) workers. We assume it can be useful to have
1524 * extra workers in this case because they will be spread out across
1525 * the children. The precise formula is just a guess, but we don't
1526 * want to end up with a radically different answer for a table with N
1527 * partitions vs. an unpartitioned table with the same data, so the
1528 * use of some kind of log-scaling here seems to make some sense.
1529 */
1531 {
1535 max_parallel_workers_per_gather);
1536 }
1539 /* Generate a partial append path. */
1542 enable_parallel_append,
1545 /*
1546 * Make sure any subsequent partial paths use the same row count
1547 * estimate.
1548 */
1551 /* Add the path. */
1553 }
1555 /*
1556 * Consider a parallel-aware append using a mix of partial and non-partial
1557 * paths. (This only makes sense if there's at least one child which has
1558 * a non-partial path that is substantially cheaper than any partial path;
1559 * otherwise, we should use the append path added in the previous step.)
1560 */
1562 {
1567 /*
1568 * Find the highest number of workers requested for any partial
1569 * subpath.
1570 */
1572 {
1576 }
1578 /*
1579 * Same formula here as above. It's even more important in this
1580 * instance because the non-partial paths won't contribute anything to
1581 * the planned number of parallel workers.
1582 */
1586 max_parallel_workers_per_gather);
1590 pa_partial_subpaths,
1592 partial_rows);
1594 }
1596 /*
1597 * Also build unparameterized ordered append paths based on the collected
1598 * list of child pathkeys.
1599 */
1602 all_child_pathkeys);
1604 /*
1605 * Build Append paths for each parameterization seen among the child rels.
1606 * (This may look pretty expensive, but in most cases of practical
1607 * interest, the child rels will expose mostly the same parameterizations,
1608 * so that not that many cases actually get considered here.)
1609 *
1610 * The Append node itself cannot enforce quals, so all qual checking must
1611 * be done in the child paths. This means that to have a parameterized
1612 * Append path, we must have the exact same parameterization for each
1613 * child path; otherwise some children might be failing to check the
1614 * moved-down quals. To make them match up, we can try to increase the
1615 * parameterization of lesser-parameterized paths.
1616 */
1618 {
1622 /* Select the child paths for an Append with this parameterization */
1626 {
1631 {
1632 /* failed to make a suitable path for this child */
1635 }
1638 childrel,
1639 required_outer);
1641 {
1642 /* failed to make a suitable path for this child */
1645 }
1647 }
1654 }
1656 /*
1657 * When there is only a single child relation, the Append path can inherit
1658 * any ordering available for the child rel's path, so that it's useful to
1659 * consider ordered partial paths. Above we only considered the cheapest
1660 * partial path for each child, but let's also make paths using any
1661 * partial paths that have pathkeys.
1662 */
1664 {
1667 /* skip the cheapest partial path, since we already used that above */
1669 {
1673 /* skip paths with no pathkeys. */
1680 partial_rows);
1682 }
1683 }
1684 }
1686 /*
1687 * generate_orderedappend_paths
1688 * Generate ordered append paths for an append relation
1689 *
1690 * Usually we generate MergeAppend paths here, but there are some special
1691 * cases where we can generate simple Append paths, because the subpaths
1692 * can provide tuples in the required order already.
1693 *
1694 * We generate a path for each ordering (pathkey list) appearing in
1695 * all_child_pathkeys.
1696 *
1697 * We consider both cheapest-startup and cheapest-total cases, ie, for each
1698 * interesting ordering, collect all the cheapest startup subpaths and all the
1699 * cheapest total paths, and build a suitable path for each case.
1700 *
1701 * We don't currently generate any parameterized ordered paths here. While
1702 * it would not take much more code here to do so, it's very unclear that it
1703 * is worth the planning cycles to investigate such paths: there's little
1704 * use for an ordered path on the inside of a nestloop. In fact, it's likely
1705 * that the current coding of add_path would reject such paths out of hand,
1706 * because add_path gives no credit for sort ordering of parameterized paths,
1707 * and a parameterized MergeAppend is going to be more expensive than the
1708 * corresponding parameterized Append path. If we ever try harder to support
1709 * parameterized mergejoin plans, it might be worth adding support for
1710 * parameterized paths here to feed such joins. (See notes in
1711 * optimizer/README for why that might not ever happen, though.)
1712 */
1713 static void
1717 {
1724 /*
1725 * Some partitioned table setups may allow us to use an Append node
1726 * instead of a MergeAppend. This is possible in cases such as RANGE
1727 * partitioned tables where it's guaranteed that an earlier partition must
1728 * contain rows which come earlier in the sort order. To detect whether
1729 * this is relevant, build pathkey descriptions of the partition ordering,
1730 * for both forward and reverse scans.
1731 */
1734 {
1736 ForwardScanDirection,
1740 BackwardScanDirection,
1743 /*
1744 * You might think we should truncate_useless_pathkeys here, but
1745 * allowing partition keys which are a subset of the query's pathkeys
1746 * can often be useful. For example, consider a table partitioned by
1747 * RANGE (a, b), and a query with ORDER BY a, b, c. If we have child
1748 * paths that can produce the a, b, c ordering (perhaps via indexes on
1749 * (a, b, c)) then it works to consider the appendrel output as
1750 * ordered by a, b, c.
1751 */
1752 }
1754 /* Now consider each interesting sort ordering */
1756 {
1768 /*
1769 * Determine if this sort ordering matches any partition pathkeys we
1770 * have, for both ascending and descending partition order. If the
1771 * partition pathkeys happen to be contained in pathkeys then it still
1772 * works, as described above, providing that the partition pathkeys
1773 * are complete and not just a prefix of the partition keys. (In such
1774 * cases we'll be relying on the child paths to have sorted the
1775 * lower-order columns of the required pathkeys.)
1776 */
1777 match_partition_order =
1787 /*
1788 * When the required pathkeys match the reverse of the partition
1789 * order, we must build the list of paths in reverse starting with the
1790 * last matching partition first. We can get away without making any
1791 * special cases for this in the loop below by just looping backward
1792 * over the child relations in this case.
1793 */
1795 {
1796 /* loop backward */
1801 /*
1802 * Set this to true to save us having to check for
1803 * match_partition_order_desc in the loop below.
1804 */
1806 }
1807 else
1808 {
1809 /* for all other case, loop forward */
1813 }
1815 /* Select the child paths for this ordering... */
1817 {
1823 /* Locate the right paths, if they are available. */
1824 cheapest_startup =
1826 pathkeys,
1827 NULL,
1828 STARTUP_COST,
1830 cheapest_total =
1832 pathkeys,
1833 NULL,
1834 TOTAL_COST,
1837 /*
1838 * If we can't find any paths with the right order just use the
1839 * cheapest-total path; we'll have to sort it later.
1840 */
1842 {
1845 /* Assert we do have an unparameterized path for this child */
1847 }
1849 /*
1850 * When building a fractional path, determine a cheapest
1851 * fractional path for each child relation too. Looking at startup
1852 * and total costs is not enough, because the cheapest fractional
1853 * path may be dominated by two separate paths (one for startup,
1854 * one for total).
1855 *
1856 * When needed (building fractional path), determine the cheapest
1857 * fractional path too.
1858 */
1860 {
1863 cheapest_fractional =
1865 pathkeys,
1866 NULL,
1867 path_fraction);
1869 /*
1870 * If we found no path with matching pathkeys, use the
1871 * cheapest total path instead.
1872 *
1873 * XXX We might consider partially sorted paths too (with an
1874 * incremental sort on top). But we'd have to build all the
1875 * incremental paths, do the costing etc.
1876 */
1879 }
1881 /*
1882 * Notice whether we actually have different paths for the
1883 * "cheapest" and "total" cases; frequently there will be no point
1884 * in two create_merge_append_path() calls.
1885 */
1889 /*
1890 * Collect the appropriate child paths. The required logic varies
1891 * for the Append and MergeAppend cases.
1892 */
1894 {
1895 /*
1896 * We're going to make a plain Append path. We don't need
1897 * most of what accumulate_append_subpath would do, but we do
1898 * want to cut out child Appends or MergeAppends if they have
1899 * just a single subpath (and hence aren't doing anything
1900 * useful).
1901 */
1909 {
1912 }
1913 }
1914 else
1915 {
1916 /*
1917 * Otherwise, rely on accumulate_append_subpath to collect the
1918 * child paths for the MergeAppend.
1919 */
1928 }
1929 }
1931 /* ... and build the Append or MergeAppend paths */
1933 {
1934 /* We only need Append */
1936 rel,
1937 startup_subpaths,
1938 NIL,
1939 pathkeys,
1940 NULL,
1946 rel,
1947 total_subpaths,
1948 NIL,
1949 pathkeys,
1950 NULL,
1957 rel,
1958 fractional_subpaths,
1959 NIL,
1960 pathkeys,
1961 NULL,
1965 }
1966 else
1967 {
1968 /* We need MergeAppend */
1970 rel,
1971 startup_subpaths,
1972 pathkeys,
1973 NULL));
1976 rel,
1977 total_subpaths,
1978 pathkeys,
1979 NULL));
1983 rel,
1984 fractional_subpaths,
1985 pathkeys,
1986 NULL));
1987 }
1988 }
1989 }
1991 /*
1992 * get_cheapest_parameterized_child_path
1993 * Get cheapest path for this relation that has exactly the requested
1994 * parameterization.
1995 *
1996 * Returns NULL if unable to create such a path.
1997 */
2000 Relids required_outer)
2001 {
2005 /*
2006 * Look up the cheapest existing path with no more than the needed
2007 * parameterization. If it has exactly the needed parameterization, we're
2008 * done.
2009 */
2011 NIL,
2012 required_outer,
2013 TOTAL_COST,
2019 /*
2020 * Otherwise, we can "reparameterize" an existing path to match the given
2021 * parameterization, which effectively means pushing down additional
2022 * joinquals to be checked within the path's scan. However, some existing
2023 * paths might check the available joinquals already while others don't;
2024 * therefore, it's not clear which existing path will be cheapest after
2025 * reparameterization. We have to go through them all and find out.
2026 */
2029 {
2032 /* Can't use it if it needs more than requested parameterization */
2036 /*
2037 * Reparameterization can only increase the path's cost, so if it's
2038 * already more expensive than the current cheapest, forget it.
2039 */
2044 /* Reparameterize if needed, then recheck cost */
2046 {
2055 }
2057 /* We have a new best path */
2059 }
2061 /* Return the best path, or NULL if we found no suitable candidate */
2063 }
2065 /*
2066 * accumulate_append_subpath
2067 * Add a subpath to the list being built for an Append or MergeAppend.
2068 *
2069 * It's possible that the child is itself an Append or MergeAppend path, in
2070 * which case we can "cut out the middleman" and just add its child paths to
2071 * our own list. (We don't try to do this earlier because we need to apply
2072 * both levels of transformation to the quals.)
2073 *
2074 * Note that if we omit a child MergeAppend in this way, we are effectively
2075 * omitting a sort step, which seems fine: if the parent is to be an Append,
2076 * its result would be unsorted anyway, while if the parent is to be a
2077 * MergeAppend, there's no point in a separate sort on a child.
2078 *
2079 * Normally, either path is a partial path and subpaths is a list of partial
2080 * paths, or else path is a non-partial plan and subpaths is a list of those.
2081 * However, if path is a parallel-aware Append, then we add its partial path
2082 * children to subpaths and the rest to special_subpaths. If the latter is
2083 * NULL, we don't flatten the path at all (unless it contains only partial
2084 * paths).
2085 */
2086 static void
2088 {
2090 {
2094 {
2097 }
2099 {
2102 /* Split Parallel Append into partial and non-partial subpaths */
2109 new_special_subpaths);
2111 }
2112 }
2114 {
2119 }
2122 }
2124 /*
2125 * get_singleton_append_subpath
2126 * Returns the single subpath of an Append/MergeAppend, or just
2127 * return 'path' if it's not a single sub-path Append/MergeAppend.
2128 *
2129 * Note: 'path' must not be a parallel-aware path.
2130 */
2133 {
2137 {
2142 }
2144 {
2149 }
2152 }
2154 /*
2155 * set_dummy_rel_pathlist
2156 * Build a dummy path for a relation that's been excluded by constraints
2157 *
2158 * Rather than inventing a special "dummy" path type, we represent this as an
2159 * AppendPath with no members (see also IS_DUMMY_APPEND/IS_DUMMY_REL macros).
2160 *
2161 * (See also mark_dummy_rel, which does basically the same thing, but is
2162 * typically used to change a rel into dummy state after we already made
2163 * paths for it.)
2164 */
2165 static void
2167 {
2168 /* Set dummy size estimates --- we leave attr_widths[] as zeroes */
2172 /* Discard any pre-existing paths; no further need for them */
2176 /* Set up the dummy path */
2181 /*
2182 * We set the cheapest-path fields immediately, just in case they were
2183 * pointing at some discarded path. This is redundant in current usage
2184 * because set_rel_pathlist will do it later, but it's cheap so we keep it
2185 * for safety and consistency with mark_dummy_rel.
2186 */
2188 }
2190 /*
2191 * find_window_run_conditions
2192 * Determine if 'wfunc' is really a WindowFunc and call its prosupport
2193 * function to determine the function's monotonic properties. We then
2194 * see if 'opexpr' can be used to short-circuit execution.
2195 *
2196 * For example row_number() over (order by ...) always produces a value one
2197 * higher than the previous. If someone has a window function in a subquery
2198 * and has a WHERE clause in the outer query to filter rows <= 10, then we may
2199 * as well stop processing the windowagg once the row number reaches 11. Here
2200 * we check if 'opexpr' might help us to stop doing needless extra processing
2201 * in WindowAgg nodes.
2202 *
2203 * '*keep_original' is set to true if the caller should also use 'opexpr' for
2204 * its original purpose. This is set to false if the caller can assume that
2205 * the run condition will handle all of the required filtering.
2206 *
2207 * Returns true if 'opexpr' was found to be useful and was added to the
2208 * WindowFunc's runCondition. We also set *keep_original accordingly and add
2209 * 'attno' to *run_cond_attrs offset by FirstLowInvalidHeapAttributeNumber.
2210 * If the 'opexpr' cannot be used then we set *keep_original to true and
2211 * return false.
2212 */
2213 static bool
2218 {
2219 Oid prosupport;
2221 SupportRequestWFuncMonotonic req;
2226 Oid runoperator;
2234 /* we can only work with window functions */
2238 /* can't use it if there are subplans in the WindowFunc */
2244 /* Check if there's a support function for 'wfunc' */
2248 /* get the Expr from the other side of the OpExpr */
2251 else
2254 /*
2255 * The value being compared must not change during the evaluation of the
2256 * window partition.
2257 */
2261 /* find the window clause belonging to the window function */
2269 /* call the support function */
2274 /*
2275 * Nothing to do if the function is neither monotonically increasing nor
2276 * monotonically decreasing.
2277 */
2286 {
2290 /* handle < / <= */
2293 {
2294 /*
2295 * < / <= is supported for monotonically increasing functions in
2296 * the form <wfunc> op <pseudoconst> and <pseudoconst> op <wfunc>
2297 * for monotonically decreasing functions.
2298 */
2301 {
2305 }
2307 }
2308 /* handle > / >= */
2311 {
2312 /*
2313 * > / >= is supported for monotonically decreasing functions in
2314 * the form <wfunc> op <pseudoconst> and <pseudoconst> op <wfunc>
2315 * for monotonically increasing functions.
2316 */
2319 {
2323 }
2325 }
2326 /* handle = */
2328 {
2329 int16 newstrategy;
2331 /*
2332 * When both monotonically increasing and decreasing then the
2333 * return value of the window function will be the same each time.
2334 * We can simply use 'opexpr' as the run condition without
2335 * modifying it.
2336 */
2338 {
2343 }
2345 /*
2346 * When monotonically increasing we make a qual with <wfunc> <=
2347 * <value> or <value> >= <wfunc> in order to filter out values
2348 * which are above the value in the equality condition. For
2349 * monotonically decreasing functions we want to filter values
2350 * below the value in the equality condition.
2351 */
2354 else
2357 /* We must keep the original equality qual */
2361 /* determine the operator to use for the WindowFuncRunCondition */
2365 newstrategy);
2367 }
2368 }
2371 {
2382 /* record that this attno was used in a run condition */
2386 }
2388 /* unsupported OpExpr */
2390 }
2392 /*
2393 * check_and_push_window_quals
2394 * Check if 'clause' is a qual that can be pushed into a WindowFunc
2395 * as a 'runCondition' qual. These, when present, allow some unnecessary
2396 * work to be skipped during execution.
2397 *
2398 * 'run_cond_attrs' will be populated with all targetlist resnos of subquery
2399 * targets (offset by FirstLowInvalidHeapAttributeNumber) that we pushed
2400 * window quals for.
2401 *
2402 * Returns true if the caller still must keep the original qual or false if
2403 * the caller can safely ignore the original qual because the WindowAgg node
2404 * will use the runCondition to stop returning tuples.
2405 */
2406 static bool
2409 {
2415 /* We're only able to use OpExprs with 2 operands */
2422 /*
2423 * Currently, we restrict this optimization to strict OpExprs. The reason
2424 * for this is that during execution, once the runcondition becomes false,
2425 * we stop evaluating WindowFuncs. To avoid leaving around stale window
2426 * function result values, we set them to NULL. Having only strict
2427 * OpExprs here ensures that we properly filter out the tuples with NULLs
2428 * in the top-level WindowAgg.
2429 */
2434 /*
2435 * Check for plain Vars that reference window functions in the subquery.
2436 * If we find any, we'll ask find_window_run_conditions() if 'opexpr' can
2437 * be used as part of the run condition.
2438 */
2440 /* Check the left side of the OpExpr */
2443 {
2449 run_cond_attrs))
2451 }
2453 /* and check the right side */
2456 {
2462 run_cond_attrs))
2464 }
2467 }
2469 /*
2470 * set_subquery_pathlist
2471 * Generate SubqueryScan access paths for a subquery RTE
2472 *
2473 * We don't currently support generating parameterized paths for subqueries
2474 * by pushing join clauses down into them; it seems too expensive to re-plan
2475 * the subquery multiple times to consider different alternatives.
2476 * (XXX that could stand to be reconsidered, now that we use Paths.)
2477 * So the paths made here will be parameterized if the subquery contains
2478 * LATERAL references, otherwise not. As long as that's true, there's no need
2479 * for a separate set_subquery_size phase: just make the paths right away.
2480 */
2481 static void
2484 {
2488 Relids required_outer;
2489 pushdown_safety_info safetyInfo;
2495 /*
2496 * Must copy the Query so that planning doesn't mess up the RTE contents
2497 * (really really need to fix the planner to not scribble on its input,
2498 * someday ... but see remove_unused_subquery_outputs to start with).
2499 */
2502 /*
2503 * If it's a LATERAL subquery, it might contain some Vars of the current
2504 * query level, requiring it to be treated as parameterized, even though
2505 * we don't support pushing down join quals into subqueries.
2506 */
2509 /*
2510 * Zero out result area for subquery_is_pushdown_safe, so that it can set
2511 * flags as needed while recursing. In particular, we need a workspace
2512 * for keeping track of the reasons why columns are unsafe to reference.
2513 * These reasons are stored in the bits inside unsafeFlags[i] when we
2514 * discover reasons that column i of the subquery is unsafe to be used in
2515 * a pushed-down qual.
2516 */
2521 /*
2522 * If the subquery has the "security_barrier" flag, it means the subquery
2523 * originated from a view that must enforce row-level security. Then we
2524 * must not push down quals that contain leaky functions. (Ideally this
2525 * would be checked inside subquery_is_pushdown_safe, but since we don't
2526 * currently pass the RTE to that function, we must do it here.)
2527 */
2530 /*
2531 * If there are any restriction clauses that have been attached to the
2532 * subquery relation, consider pushing them down to become WHERE or HAVING
2533 * quals of the subquery itself. This transformation is useful because it
2534 * may allow us to generate a better plan for the subquery than evaluating
2535 * all the subquery output rows and then filtering them.
2536 *
2537 * There are several cases where we cannot push down clauses. Restrictions
2538 * involving the subquery are checked by subquery_is_pushdown_safe().
2539 * Restrictions on individual clauses are checked by
2540 * qual_is_pushdown_safe(). Also, we don't want to push down
2541 * pseudoconstant clauses; better to have the gating node above the
2542 * subquery.
2543 *
2544 * Non-pushed-down clauses will get evaluated as qpquals of the
2545 * SubqueryScan node.
2546 *
2547 * XXX Are there any cases where we want to make a policy decision not to
2548 * push down a pushable qual, because it'd result in a worse plan?
2549 */
2552 {
2553 /* OK to consider pushing down individual quals */
2558 {
2563 {
2566 }
2569 {
2571 /* Push it down */
2577 /*
2578 * Since we can't push the qual down into the subquery,
2579 * check if it happens to reference a window function. If
2580 * so then it might be useful to use for the WindowAgg's
2581 * runCondition.
2582 */
2586 {
2587 /*
2588 * subquery has no window funcs or the clause is not a
2589 * suitable window run condition qual or it is, but
2590 * the original must also be kept in the upper query.
2591 */
2593 }
2599 }
2600 }
2602 /* We don't bother recomputing baserestrict_min_security */
2603 }
2607 /*
2608 * The upper query might not use all the subquery's output columns; if
2609 * not, we can simplify. Pass the attributes that were pushed down into
2610 * WindowAgg run conditions to ensure we don't accidentally think those
2611 * are unused.
2612 */
2615 /*
2616 * We can safely pass the outer tuple_fraction down to the subquery if the
2617 * outer level has no joining, aggregation, or sorting to do. Otherwise
2618 * we'd better tell the subquery to plan for full retrieval. (XXX This
2619 * could probably be made more intelligent ...)
2620 */
2629 else
2632 /* plan_params should not be in use in current query level */
2635 /* Generate a subroot and Paths for the subquery */
2637 root,
2640 /* Isolate the params needed by this specific subplan */
2644 /*
2645 * It's possible that constraint exclusion proved the subquery empty. If
2646 * so, it's desirable to produce an unadorned dummy path so that we will
2647 * recognize appropriate optimizations at this query level.
2648 */
2652 {
2655 }
2657 /*
2658 * Mark rel with estimated output rows, width, etc. Note that we have to
2659 * do this before generating outer-query paths, else cost_subqueryscan is
2660 * not happy.
2661 */
2664 /*
2665 * Also detect whether the reltarget is trivial, so that we can pass that
2666 * info to cost_subqueryscan (rather than re-deriving it multiple times).
2667 * It's trivial if it fetches all the subplan output columns in order.
2668 */
2671 else
2672 {
2675 {
2680 {
2683 }
2687 {
2690 }
2691 }
2692 }
2694 /*
2695 * For each Path that subquery_planner produced, make a SubqueryScanPath
2696 * in the outer query.
2697 */
2699 {
2703 /* Convert subpath's pathkeys to outer representation */
2705 rel,
2709 /* Generate outer path using this subpath */
2712 trivial_pathtarget,
2714 }
2716 /* If outer rel allows parallelism, do same for partial paths. */
2718 {
2719 /* If consider_parallel is false, there should be no partial paths. */
2723 /* Same for partial paths. */
2725 {
2729 /* Convert subpath's pathkeys to outer representation */
2731 rel,
2735 /* Generate outer path using this subpath */
2738 trivial_pathtarget,
2739 pathkeys,
2740 required_outer));
2741 }
2742 }
2743 }
2745 /*
2746 * set_function_pathlist
2747 * Build the (single) access path for a function RTE
2748 */
2749 static void
2751 {
2752 Relids required_outer;
2755 /*
2756 * We don't support pushing join clauses into the quals of a function
2757 * scan, but it could still have required parameterization due to LATERAL
2758 * refs in the function expression.
2759 */
2762 /*
2763 * The result is considered unordered unless ORDINALITY was used, in which
2764 * case it is ordered by the ordinal column (the last one). See if we
2765 * care, by checking for uses of that Var in equivalence classes.
2766 */
2768 {
2773 /*
2774 * Is there a Var for it in rel's targetlist? If not, the query did
2775 * not reference the ordinality column, or at least not in any way
2776 * that would be interesting for sorting.
2777 */
2779 {
2782 /* checking varno/varlevelsup is just paranoia */
2787 {
2790 }
2791 }
2793 /*
2794 * Try to build pathkeys for this Var with int8 sorting. We tell
2795 * build_expression_pathkey not to build any new equivalence class; if
2796 * the Var isn't already mentioned in some EC, it means that nothing
2797 * cares about the ordering.
2798 */
2802 Int8LessOperator,
2805 }
2807 /* Generate appropriate path */
2810 }
2812 /*
2813 * set_values_pathlist
2814 * Build the (single) access path for a VALUES RTE
2815 */
2816 static void
2818 {
2819 Relids required_outer;
2821 /*
2822 * We don't support pushing join clauses into the quals of a values scan,
2823 * but it could still have required parameterization due to LATERAL refs
2824 * in the values expressions.
2825 */
2828 /* Generate appropriate path */
2830 }
2832 /*
2833 * set_tablefunc_pathlist
2834 * Build the (single) access path for a table func RTE
2835 */
2836 static void
2838 {
2839 Relids required_outer;
2841 /*
2842 * We don't support pushing join clauses into the quals of a tablefunc
2843 * scan, but it could still have required parameterization due to LATERAL
2844 * refs in the function expression.
2845 */
2848 /* Generate appropriate path */
2850 required_outer));
2851 }
2853 /*
2854 * set_cte_pathlist
2855 * Build the (single) access path for a non-self-reference CTE RTE
2856 *
2857 * There's no need for a separate set_cte_size phase, since we don't
2858 * support join-qual-parameterized paths for CTEs.
2859 */
2860 static void
2862 {
2866 Index levelsup;
2871 Relids required_outer;
2873 /*
2874 * Find the referenced CTE, and locate the path and plan previously made
2875 * for it.
2876 */
2880 {
2884 }
2886 /*
2887 * Note: cte_plan_ids can be shorter than cteList, if we are still working
2888 * on planning the CTEs (ie, this is a side-reference from another CTE).
2889 * So we mustn't use forboth here.
2890 */
2893 {
2898 ndx++;
2899 }
2912 /* Mark rel with estimated output rows, width, etc */
2915 /* Convert the ctepath's pathkeys to outer query's representation */
2917 rel,
2921 /*
2922 * We don't support pushing join clauses into the quals of a CTE scan, but
2923 * it could still have required parameterization due to LATERAL refs in
2924 * its tlist.
2925 */
2928 /* Generate appropriate path */
2930 }
2932 /*
2933 * set_namedtuplestore_pathlist
2934 * Build the (single) access path for a named tuplestore RTE
2935 *
2936 * There's no need for a separate set_namedtuplestore_size phase, since we
2937 * don't support join-qual-parameterized paths for tuplestores.
2938 */
2939 static void
2942 {
2943 Relids required_outer;
2945 /* Mark rel with estimated output rows, width, etc */
2948 /*
2949 * We don't support pushing join clauses into the quals of a tuplestore
2950 * scan, but it could still have required parameterization due to LATERAL
2951 * refs in its tlist.
2952 */
2955 /* Generate appropriate path */
2957 }
2959 /*
2960 * set_result_pathlist
2961 * Build the (single) access path for an RTE_RESULT RTE
2962 *
2963 * There's no need for a separate set_result_size phase, since we
2964 * don't support join-qual-parameterized paths for these RTEs.
2965 */
2966 static void
2969 {
2970 Relids required_outer;
2972 /* Mark rel with estimated output rows, width, etc */
2975 /*
2976 * We don't support pushing join clauses into the quals of a Result scan,
2977 * but it could still have required parameterization due to LATERAL refs
2978 * in its tlist.
2979 */
2982 /* Generate appropriate path */
2984 }
2986 /*
2987 * set_worktable_pathlist
2988 * Build the (single) access path for a self-reference CTE RTE
2989 *
2990 * There's no need for a separate set_worktable_size phase, since we don't
2991 * support join-qual-parameterized paths for CTEs.
2992 */
2993 static void
2995 {
2998 Index levelsup;
2999 Relids required_outer;
3001 /*
3002 * We need to find the non-recursive term's path, which is in the plan
3003 * level that's processing the recursive UNION, which is one level *below*
3004 * where the CTE comes from.
3005 */
3009 levelsup--;
3012 {
3016 }
3021 /* Mark rel with estimated output rows, width, etc */
3024 /*
3025 * We don't support pushing join clauses into the quals of a worktable
3026 * scan, but it could still have required parameterization due to LATERAL
3027 * refs in its tlist. (I'm not sure this is actually possible given the
3028 * restrictions on recursive references, but it's easy enough to support.)
3029 */
3032 /* Generate appropriate path */
3034 }
3036 /*
3037 * generate_gather_paths
3038 * Generate parallel access paths for a relation by pushing a Gather or
3039 * Gather Merge on top of a partial path.
3040 *
3041 * This must not be called until after we're done creating all partial paths
3042 * for the specified relation. (Otherwise, add_partial_path might delete a
3043 * path that some GatherPath or GatherMergePath has a reference to.)
3044 *
3045 * If we're generating paths for a scan or join relation, override_rows will
3046 * be false, and we'll just use the relation's size estimate. When we're
3047 * being called for a partially-grouped or partially-distinct path, though, we
3048 * need to override the rowcount estimate. (It's not clear that the
3049 * particular value we're using here is actually best, but the underlying rel
3050 * has no estimate so we must do something.)
3051 */
3052 void
3054 {
3061 /* If there are no partial paths, there's nothing to do here. */
3065 /* Should we override the rel's rowcount estimate? */
3069 /*
3070 * The output of Gather is always unsorted, so there's only one partial
3071 * path of interest: the cheapest one. That will be the one at the front
3072 * of partial_pathlist because of the way add_partial_path works.
3073 */
3075 rows =
3082 /*
3083 * For each useful ordering, we can consider an order-preserving Gather
3084 * Merge.
3085 */
3087 {
3098 }
3099 }
3101 /*
3102 * get_useful_pathkeys_for_relation
3103 * Determine which orderings of a relation might be useful.
3104 *
3105 * Getting data in sorted order can be useful either because the requested
3106 * order matches the final output ordering for the overall query we're
3107 * planning, or because it enables an efficient merge join. Here, we try
3108 * to figure out which pathkeys to consider.
3109 *
3110 * This allows us to do incremental sort on top of an index scan under a gather
3111 * merge node, i.e. parallelized.
3112 *
3113 * If the require_parallel_safe is true, we also require the expressions to
3114 * be parallel safe (which allows pushing the sort below Gather Merge).
3115 *
3116 * XXX At the moment this can only ever return a list with a single element,
3117 * because it looks at query_pathkeys only. So we might return the pathkeys
3118 * directly, but it seems plausible we'll want to consider other orderings
3119 * in the future. For example, we might want to consider pathkeys useful for
3120 * merge joins.
3121 */
3125 {
3128 /*
3129 * Considering query_pathkeys is always worth it, because it might allow
3130 * us to avoid a total sort when we have a partially presorted path
3131 * available or to push the total sort into the parallel portion of the
3132 * query.
3133 */
3135 {
3140 {
3144 /*
3145 * We can only build a sort for pathkeys that contain a
3146 * safe-to-compute-early EC member computable from the current
3147 * relation's reltarget, so ignore the remainder of the list as
3148 * soon as we find a pathkey without such a member.
3149 *
3150 * It's still worthwhile to return any prefix of the pathkeys list
3151 * that meets this requirement, as we may be able to do an
3152 * incremental sort.
3153 *
3154 * If requested, ensure the sort expression is parallel-safe too.
3155 */
3157 require_parallel_safe))
3160 npathkeys++;
3161 }
3163 /*
3164 * The whole query_pathkeys list matches, so append it directly, to
3165 * allow comparing pathkeys easily by comparing list pointer. If we
3166 * have to truncate the pathkeys, we gotta do a copy though.
3167 */
3174 npathkeys));
3175 }
3178 }
3180 /*
3181 * generate_useful_gather_paths
3182 * Generate parallel access paths for a relation by pushing a Gather or
3183 * Gather Merge on top of a partial path.
3184 *
3185 * Unlike plain generate_gather_paths, this looks both at pathkeys of input
3186 * paths (aiming to preserve the ordering), but also considers ordering that
3187 * might be useful for nodes above the gather merge node, and tries to add
3188 * a sort (regular or incremental) to provide that.
3189 */
3190 void
3192 {
3199 /* If there are no partial paths, there's nothing to do here. */
3203 /* Should we override the rel's rowcount estimate? */
3207 /* generate the regular gather (merge) paths */
3210 /* consider incremental sort for interesting orderings */
3213 /* used for explicit (full) sort paths */
3216 /*
3217 * Consider sorted paths for each interesting ordering. We generate both
3218 * incremental and full sort.
3219 */
3221 {
3228 {
3236 /*
3237 * We don't need to consider the case where a subpath is already
3238 * fully sorted because generate_gather_paths already creates a
3239 * gather merge path for every subpath that has pathkeys present.
3240 *
3241 * But since the subpath is already sorted, we know we don't need
3242 * to consider adding a sort (full or incremental) on top of it,
3243 * so we can continue here.
3244 */
3248 /*
3249 * Try at least sorting the cheapest path and also try
3250 * incrementally sorting any path which is partially sorted
3251 * already (no need to deal with paths which have presorted keys
3252 * when incremental sort is disabled unless it's the cheapest
3253 * input path).
3254 */
3259 /*
3260 * Consider regular sort for any path that's not presorted or if
3261 * incremental sort is disabled. We've no need to consider both
3262 * sort and incremental sort on the same path. We assume that
3263 * incremental sort is always faster when there are presorted
3264 * keys.
3265 *
3266 * This is not redundant with the gather paths created in
3267 * generate_gather_paths, because that doesn't generate ordered
3268 * output. Here we add an explicit sort to match the useful
3269 * ordering.
3270 */
3272 {
3274 rel,
3275 subpath,
3276 useful_pathkeys,
3279 }
3280 else
3282 rel,
3283 subpath,
3284 useful_pathkeys,
3285 presorted_keys,
3288 subpath,
3291 NULL,
3292 rowsp);
3295 }
3296 }
3297 }
3299 /*
3300 * make_rel_from_joinlist
3301 * Build access paths using a "joinlist" to guide the join path search.
3302 *
3303 * See comments for deconstruct_jointree() for definition of the joinlist
3304 * data structure.
3305 */
3308 {
3313 /*
3314 * Count the number of child joinlist nodes. This is the depth of the
3315 * dynamic-programming algorithm we must employ to consider all ways of
3316 * joining the child nodes.
3317 */
3323 /*
3324 * Construct a list of rels corresponding to the child joinlist nodes.
3325 * This may contain both base rels and rels constructed according to
3326 * sub-joinlists.
3327 */
3330 {
3335 {
3339 }
3341 {
3342 /* Recurse to handle subproblem */
3344 }
3345 else
3346 {
3350 }
3353 }
3356 {
3357 /*
3358 * Single joinlist node, so we're done.
3359 */
3361 }
3362 else
3363 {
3364 /*
3365 * Consider the different orders in which we could join the rels,
3366 * using a plugin, GEQO, or the regular join search code.
3367 *
3368 * We put the initial_rels list into a PlannerInfo field because
3369 * has_legal_joinclause() needs to look at it (ugly :-().
3370 */
3377 else
3379 }
3380 }
3382 /*
3383 * standard_join_search
3384 * Find possible joinpaths for a query by successively finding ways
3385 * to join component relations into join relations.
3386 *
3387 * 'levels_needed' is the number of iterations needed, ie, the number of
3388 * independent jointree items in the query. This is > 1.
3389 *
3390 * 'initial_rels' is a list of RelOptInfo nodes for each independent
3391 * jointree item. These are the components to be joined together.
3392 * Note that levels_needed == list_length(initial_rels).
3393 *
3394 * Returns the final level of join relations, i.e., the relation that is
3395 * the result of joining all the original relations together.
3396 * At least one implementation path must be provided for this relation and
3397 * all required sub-relations.
3398 *
3399 * To support loadable plugins that modify planner behavior by changing the
3400 * join searching algorithm, we provide a hook variable that lets a plugin
3401 * replace or supplement this function. Any such hook must return the same
3402 * final join relation as the standard code would, but it might have a
3403 * different set of implementation paths attached, and only the sub-joinrels
3404 * needed for these paths need have been instantiated.
3405 *
3406 * Note to plugin authors: the functions invoked during standard_join_search()
3407 * modify root->join_rel_list and root->join_rel_hash. If you want to do more
3408 * than one join-order search, you'll probably need to save and restore the
3409 * original states of those data structures. See geqo_eval() for an example.
3410 */
3411 RelOptInfo *
3413 {
3417 /*
3418 * This function cannot be invoked recursively within any one planning
3419 * problem, so join_rel_level[] can't be in use already.
3420 */
3423 /*
3424 * We employ a simple "dynamic programming" algorithm: we first find all
3425 * ways to build joins of two jointree items, then all ways to build joins
3426 * of three items (from two-item joins and single items), then four-item
3427 * joins, and so on until we have considered all ways to join all the
3428 * items into one rel.
3429 *
3430 * root->join_rel_level[j] is a list of all the j-item rels. Initially we
3431 * set root->join_rel_level[1] to represent all the single-jointree-item
3432 * relations.
3433 */
3439 {
3442 /*
3443 * Determine all possible pairs of relations to be joined at this
3444 * level, and build paths for making each one from every available
3445 * pair of lower-level relations.
3446 */
3449 /*
3450 * Run generate_partitionwise_join_paths() and
3451 * generate_useful_gather_paths() for each just-processed joinrel. We
3452 * could not do this earlier because both regular and partial paths
3453 * can get added to a particular joinrel at multiple times within
3454 * join_search_one_level.
3455 *
3456 * After that, we're done creating paths for the joinrel, so run
3457 * set_cheapest().
3458 */
3460 {
3463 /* Create paths for partitionwise joins. */
3466 /*
3467 * Except for the topmost scan/join rel, consider gathering
3468 * partial paths. We'll do the same for the topmost scan/join rel
3469 * once we know the final targetlist (see grouping_planner's and
3470 * its call to apply_scanjoin_target_to_paths).
3471 */
3475 /* Find and save the cheapest paths for this rel */
3478 #ifdef OPTIMIZER_DEBUG
3480 #endif
3481 }
3482 }
3484 /*
3485 * We should have a single rel at the final level.
3486 */
3496 }
3498 /*****************************************************************************
3499 * PUSHING QUALS DOWN INTO SUBQUERIES
3500 *****************************************************************************/
3502 /*
3503 * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
3504 *
3505 * subquery is the particular component query being checked. topquery
3506 * is the top component of a set-operations tree (the same Query if no
3507 * set-op is involved).
3508 *
3509 * Conditions checked here:
3510 *
3511 * 1. If the subquery has a LIMIT clause, we must not push down any quals,
3512 * since that could change the set of rows returned.
3513 *
3514 * 2. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
3515 * quals into it, because that could change the results.
3516 *
3517 * 3. If the subquery uses DISTINCT, we cannot push volatile quals into it.
3518 * This is because upper-level quals should semantically be evaluated only
3519 * once per distinct row, not once per original row, and if the qual is
3520 * volatile then extra evaluations could change the results. (This issue
3521 * does not apply to other forms of aggregation such as GROUP BY, because
3522 * when those are present we push into HAVING not WHERE, so that the quals
3523 * are still applied after aggregation.)
3524 *
3525 * 4. If the subquery contains window functions, we cannot push volatile quals
3526 * into it. The issue here is a bit different from DISTINCT: a volatile qual
3527 * might succeed for some rows of a window partition and fail for others,
3528 * thereby changing the partition contents and thus the window functions'
3529 * results for rows that remain.
3530 *
3531 * 5. If the subquery contains any set-returning functions in its targetlist,
3532 * we cannot push volatile quals into it. That would push them below the SRFs
3533 * and thereby change the number of times they are evaluated. Also, a
3534 * volatile qual could succeed for some SRF output rows and fail for others,
3535 * a behavior that cannot occur if it's evaluated before SRF expansion.
3536 *
3537 * 6. If the subquery has nonempty grouping sets, we cannot push down any
3538 * quals. The concern here is that a qual referencing a "constant" grouping
3539 * column could get constant-folded, which would be improper because the value
3540 * is potentially nullable by grouping-set expansion. This restriction could
3541 * be removed if we had a parsetree representation that shows that such
3542 * grouping columns are not really constant. (There are other ideas that
3543 * could be used to relax this restriction, but that's the approach most
3544 * likely to get taken in the future. Note that there's not much to be gained
3545 * so long as subquery_planner can't move HAVING clauses to WHERE within such
3546 * a subquery.)
3547 *
3548 * In addition, we make several checks on the subquery's output columns to see
3549 * if it is safe to reference them in pushed-down quals. If output column k
3550 * is found to be unsafe to reference, we set the reason for that inside
3551 * safetyInfo->unsafeFlags[k], but we don't reject the subquery overall since
3552 * column k might not be referenced by some/all quals. The unsafeFlags[]
3553 * array will be consulted later by qual_is_pushdown_safe(). It's better to
3554 * do it this way than to make the checks directly in qual_is_pushdown_safe(),
3555 * because when the subquery involves set operations we have to check the
3556 * output expressions in each arm of the set op.
3557 *
3558 * Note: pushing quals into a DISTINCT subquery is theoretically dubious:
3559 * we're effectively assuming that the quals cannot distinguish values that
3560 * the DISTINCT's equality operator sees as equal, yet there are many
3561 * counterexamples to that assumption. However use of such a qual with a
3562 * DISTINCT subquery would be unsafe anyway, since there's no guarantee which
3563 * "equal" value will be chosen as the output value by the DISTINCT operation.
3564 * So we don't worry too much about that. Another objection is that if the
3565 * qual is expensive to evaluate, running it for each original row might cost
3566 * more than we save by eliminating rows before the DISTINCT step. But it
3567 * would be very hard to estimate that at this stage, and in practice pushdown
3568 * seldom seems to make things worse, so we ignore that problem too.
3569 *
3570 * Note: likewise, pushing quals into a subquery with window functions is a
3571 * bit dubious: the quals might remove some rows of a window partition while
3572 * leaving others, causing changes in the window functions' results for the
3573 * surviving rows. We insist that such a qual reference only partitioning
3574 * columns, but again that only protects us if the qual does not distinguish
3575 * values that the partitioning equality operator sees as equal. The risks
3576 * here are perhaps larger than for DISTINCT, since no de-duplication of rows
3577 * occurs and thus there is no theoretical problem with such a qual. But
3578 * we'll do this anyway because the potential performance benefits are very
3579 * large, and we've seen no field complaints about the longstanding comparable
3580 * behavior with DISTINCT.
3581 */
3582 static bool
3585 {
3588 /* Check point 1 */
3592 /* Check point 6 */
3596 /* Check points 3, 4, and 5 */
3602 /*
3603 * If we're at a leaf query, check for unsafe expressions in its target
3604 * list, and mark any reasons why they're unsafe in unsafeFlags[].
3605 * (Non-leaf nodes in setop trees have only simple Vars in their tlists,
3606 * so no need to check them.)
3607 */
3611 /* Are we at top level, or looking at a setop component? */
3613 {
3614 /* Top level, so check any component queries */
3617 safetyInfo))
3619 }
3620 else
3621 {
3622 /* Setop component must not have more components (too weird) */
3625 /* Check whether setop component output types match top level */
3630 safetyInfo);
3631 }
3633 }
3635 /*
3636 * Helper routine to recurse through setOperations tree
3637 */
3638 static bool
3641 {
3643 {
3650 }
3652 {
3655 /* EXCEPT is no good (point 2 for subquery_is_pushdown_safe) */
3658 /* Else recurse */
3663 }
3664 else
3665 {
3668 }
3670 }
3672 /*
3673 * check_output_expressions - check subquery's output expressions for safety
3674 *
3675 * There are several cases in which it's unsafe to push down an upper-level
3676 * qual if it references a particular output column of a subquery. We check
3677 * each output column of the subquery and set flags in unsafeFlags[k] when we
3678 * see that column is unsafe for a pushed-down qual to reference. The
3679 * conditions checked here are:
3680 *
3681 * 1. We must not push down any quals that refer to subselect outputs that
3682 * return sets, else we'd introduce functions-returning-sets into the
3683 * subquery's WHERE/HAVING quals.
3684 *
3685 * 2. We must not push down any quals that refer to subselect outputs that
3686 * contain volatile functions, for fear of introducing strange results due
3687 * to multiple evaluation of a volatile function.
3688 *
3689 * 3. If the subquery uses DISTINCT ON, we must not push down any quals that
3690 * refer to non-DISTINCT output columns, because that could change the set
3691 * of rows returned. (This condition is vacuous for DISTINCT, because then
3692 * there are no non-DISTINCT output columns, so we needn't check. Note that
3693 * subquery_is_pushdown_safe already reported that we can't use volatile
3694 * quals if there's DISTINCT or DISTINCT ON.)
3695 *
3696 * 4. If the subquery has any window functions, we must not push down quals
3697 * that reference any output columns that are not listed in all the subquery's
3698 * window PARTITION BY clauses. We can push down quals that use only
3699 * partitioning columns because they should succeed or fail identically for
3700 * every row of any one window partition, and totally excluding some
3701 * partitions will not change a window function's results for remaining
3702 * partitions. (Again, this also requires nonvolatile quals, but
3703 * subquery_is_pushdown_safe handles that.). Subquery columns marked as
3704 * unsafe for this reason can still have WindowClause run conditions pushed
3705 * down.
3706 */
3707 static void
3709 {
3713 {
3719 /* Functions returning sets are unsafe (point 1) */
3724 {
3727 }
3729 /* Volatile functions are unsafe (point 2) */
3733 {
3736 }
3738 /* If subquery uses DISTINCT ON, check point 3 */
3743 {
3744 /* non-DISTINCT column, so mark it unsafe */
3747 }
3749 /* If subquery uses window functions, check point 4 */
3754 {
3755 /* not present in all PARTITION BY clauses, so mark it unsafe */
3758 }
3759 }
3760 }
3762 /*
3763 * For subqueries using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can
3764 * push quals into each component query, but the quals can only reference
3765 * subquery columns that suffer no type coercions in the set operation.
3766 * Otherwise there are possible semantic gotchas. So, we check the
3767 * component queries to see if any of them have output types different from
3768 * the top-level setop outputs. We set the UNSAFE_TYPE_MISMATCH bit in
3769 * unsafeFlags[k] if column k has different type in any component.
3770 *
3771 * We don't have to care about typmods here: the only allowed difference
3772 * between set-op input and output typmods is input is a specific typmod
3773 * and output is -1, and that does not require a coercion.
3774 *
3775 * tlist is a subquery tlist.
3776 * colTypes is an OID list of the top-level setop's output column types.
3777 * safetyInfo is the pushdown_safety_info to set unsafeFlags[] for.
3778 */
3779 static void
3782 {
3787 {
3797 }
3800 }
3802 /*
3803 * targetIsInAllPartitionLists
3804 * True if the TargetEntry is listed in the PARTITION BY clause
3805 * of every window defined in the query.
3806 *
3807 * It would be safe to ignore windows not actually used by any window
3808 * function, but it's not easy to get that info at this stage; and it's
3809 * unlikely to be useful to spend any extra cycles getting it, since
3810 * unreferenced window definitions are probably infrequent in practice.
3811 */
3812 static bool
3814 {
3818 {
3823 }
3825 }
3827 /*
3828 * qual_is_pushdown_safe - is a particular rinfo safe to push down?
3829 *
3830 * rinfo is a restriction clause applying to the given subquery (whose RTE
3831 * has index rti in the parent query).
3832 *
3833 * Conditions checked here:
3834 *
3835 * 1. rinfo's clause must not contain any SubPlans (mainly because it's
3836 * unclear that it will work correctly: SubLinks will already have been
3837 * transformed into SubPlans in the qual, but not in the subquery). Note that
3838 * SubLinks that transform to initplans are safe, and will be accepted here
3839 * because what we'll see in the qual is just a Param referencing the initplan
3840 * output.
3841 *
3842 * 2. If unsafeVolatile is set, rinfo's clause must not contain any volatile
3843 * functions.
3844 *
3845 * 3. If unsafeLeaky is set, rinfo's clause must not contain any leaky
3846 * functions that are passed Var nodes, and therefore might reveal values from
3847 * the subquery as side effects.
3848 *
3849 * 4. rinfo's clause must not refer to the whole-row output of the subquery
3850 * (since there is no easy way to name that within the subquery itself).
3851 *
3852 * 5. rinfo's clause must not refer to any subquery output columns that were
3853 * found to be unsafe to reference by subquery_is_pushdown_safe().
3854 */
3855 static pushdown_safe_type
3858 {
3864 /* Refuse subselects (point 1) */
3868 /* Refuse volatile quals if we found they'd be unsafe (point 2) */
3873 /* Refuse leaky quals if told to (point 3) */
3878 /*
3879 * Examine all Vars used in clause. Since it's a restriction clause, all
3880 * such Vars must refer to subselect output columns ... unless this is
3881 * part of a LATERAL subquery, in which case there could be lateral
3882 * references.
3883 *
3884 * By omitting the relevant flags, this also gives us a cheap sanity check
3885 * that no aggregates or window functions appear in the qual. Those would
3886 * be unsafe to push down, but at least for the moment we could never see
3887 * any in a qual anyhow.
3888 */
3891 {
3894 /*
3895 * XXX Punt if we find any PlaceHolderVars in the restriction clause.
3896 * It's not clear whether a PHV could safely be pushed down, and even
3897 * less clear whether such a situation could arise in any cases of
3898 * practical interest anyway. So for the moment, just refuse to push
3899 * down.
3900 */
3902 {
3905 }
3907 /*
3908 * Punt if we find any lateral references. It would be safe to push
3909 * these down, but we'd have to convert them into outer references,
3910 * which subquery_push_qual lacks the infrastructure to do. The case
3911 * arises so seldom that it doesn't seem worth working hard on.
3912 */
3914 {
3917 }
3919 /* Subqueries have no system columns */
3922 /* Check point 4 */
3924 {
3927 }
3929 /* Check point 5 */
3931 {
3935 {
3938 }
3939 else
3940 {
3941 /* UNSAFE_NOTIN_PARTITIONBY_CLAUSE is ok for run conditions */
3943 /* don't break, we might find another Var that's unsafe */
3944 }
3945 }
3946 }
3951 }
3953 /*
3954 * subquery_push_qual - push down a qual that we have determined is safe
3955 */
3956 static void
3958 {
3960 {
3961 /* Recurse to push it separately to each component query */
3964 }
3965 else
3966 {
3967 /*
3968 * We need to replace Vars in the qual (which must refer to outputs of
3969 * the subquery) with copies of the subquery's targetlist expressions.
3970 * Note that at this point, any uplevel Vars in the qual should have
3971 * been replaced with Params, so they need no work.
3972 *
3973 * This step also ensures that when we are pushing into a setop tree,
3974 * each component query gets its own copy of the qual.
3975 */
3981 /*
3982 * Now attach the qual to the proper place: normally WHERE, but if the
3983 * subquery uses grouping or aggregation, put it in HAVING (since the
3984 * qual really refers to the group-result rows).
3985 */
3986 if (subquery->hasAggs || subquery->groupClause || subquery->groupingSets || subquery->havingQual)
3988 else
3992 /*
3993 * We need not change the subquery's hasAggs or hasSubLinks flags,
3994 * since we can't be pushing down any aggregates that weren't there
3995 * before, and we don't push down subselects at all.
3996 */
3997 }
3998 }
4000 /*
4001 * Helper routine to recurse through setOperations tree
4002 */
4003 static void
4006 {
4008 {
4015 }
4017 {
4022 }
4023 else
4024 {
4027 }
4028 }
4030 /*****************************************************************************
4031 * SIMPLIFYING SUBQUERY TARGETLISTS
4032 *****************************************************************************/
4034 /*
4035 * remove_unused_subquery_outputs
4036 * Remove subquery targetlist items we don't need
4037 *
4038 * It's possible, even likely, that the upper query does not read all the
4039 * output columns of the subquery. We can remove any such outputs that are
4040 * not needed by the subquery itself (e.g., as sort/group columns) and do not
4041 * affect semantics otherwise (e.g., volatile functions can't be removed).
4042 * This is useful not only because we might be able to remove expensive-to-
4043 * compute expressions, but because deletion of output columns might allow
4044 * optimizations such as join removal to occur within the subquery.
4045 *
4046 * extra_used_attrs can be passed as non-NULL to mark any columns (offset by
4047 * FirstLowInvalidHeapAttributeNumber) that we should not remove. This
4048 * parameter is modified by the function, so callers must make a copy if they
4049 * need to use the passed in Bitmapset after calling this function.
4050 *
4051 * To avoid affecting column numbering in the targetlist, we don't physically
4052 * remove unused tlist entries, but rather replace their expressions with NULL
4053 * constants. This is implemented by modifying subquery->targetList.
4054 */
4055 static void
4058 {
4062 /*
4063 * Just point directly to extra_used_attrs. No need to bms_copy as none of
4064 * the current callers use the Bitmapset after calling this function.
4065 */
4068 /*
4069 * Do nothing if subquery has UNION/INTERSECT/EXCEPT: in principle we
4070 * could update all the child SELECTs' tlists, but it seems not worth the
4071 * trouble presently.
4072 */
4076 /*
4077 * If subquery has regular DISTINCT (not DISTINCT ON), we're wasting our
4078 * time: all its output columns must be used in the distinctClause.
4079 */
4083 /*
4084 * Collect a bitmap of all the output column numbers used by the upper
4085 * query.
4086 *
4087 * Add all the attributes needed for joins or final output. Note: we must
4088 * look at rel's targetlist, not the attr_needed data, because attr_needed
4089 * isn't computed for inheritance child rels, cf set_append_rel_size().
4090 * (XXX might be worth changing that sometime.)
4091 */
4094 /* Add all the attributes used by un-pushed-down restriction clauses. */
4096 {
4100 }
4102 /*
4103 * If there's a whole-row reference to the subquery, we can't remove
4104 * anything.
4105 */
4109 /*
4110 * Run through the tlist and zap entries we don't need. It's okay to
4111 * modify the tlist items in-place because set_subquery_pathlist made a
4112 * copy of the subquery.
4113 */
4115 {
4119 /*
4120 * If it has a sortgroupref number, it's used in some sort/group
4121 * clause so we'd better not remove it. Also, don't remove any
4122 * resjunk columns, since their reason for being has nothing to do
4123 * with anybody reading the subquery's output. (It's likely that
4124 * resjunk columns in a sub-SELECT would always have ressortgroupref
4125 * set, but even if they don't, it seems imprudent to remove them.)
4126 */
4130 /*
4131 * If it's used by the upper query, we can't remove it.
4132 */
4134 attrs_used))
4137 /*
4138 * If it contains a set-returning function, we can't remove it since
4139 * that could change the number of rows returned by the subquery.
4140 */
4145 /*
4146 * If it contains volatile functions, we daren't remove it for fear
4147 * that the user is expecting their side-effects to happen.
4148 */
4152 /*
4153 * OK, we don't need it. Replace the expression with a NULL constant.
4154 * Preserve the exposed type of the expression, in case something
4155 * looks at the rowtype of the subquery's result.
4156 */
4160 }
4161 }
4163 /*
4164 * create_partial_bitmap_paths
4165 * Build partial bitmap heap path for the relation
4166 */
4167 void
4170 {
4174 /* Compute heap pages for bitmap heap scan */
4179 max_parallel_workers_per_gather);
4186 }
4188 /*
4189 * Compute the number of parallel workers that should be used to scan a
4190 * relation. We compute the parallel workers based on the size of the heap to
4191 * be scanned and the size of the index to be scanned, then choose a minimum
4192 * of those.
4193 *
4194 * "heap_pages" is the number of pages from the table that we expect to scan, or
4195 * -1 if we don't expect to scan any.
4196 *
4197 * "index_pages" is the number of pages from the index that we expect to scan, or
4198 * -1 if we don't expect to scan any.
4199 *
4200 * "max_workers" is caller's limit on the number of workers. This typically
4201 * comes from a GUC.
4202 */
4203 int
4206 {
4209 /*
4210 * If the user has set the parallel_workers reloption, use that; otherwise
4211 * select a default number of workers.
4212 */
4215 else
4216 {
4217 /*
4218 * If the number of pages being scanned is insufficient to justify a
4219 * parallel scan, just return zero ... unless it's an inheritance
4220 * child. In that case, we want to generate a parallel path here
4221 * anyway. It might not be worthwhile just for this relation, but
4222 * when combined with all of its inheritance siblings it may well pay
4223 * off.
4224 */
4231 {
4235 /*
4236 * Select the number of workers based on the log of the size of
4237 * the relation. This probably needs to be a good deal more
4238 * sophisticated, but we need something here for now. Note that
4239 * the upper limit of the min_parallel_table_scan_size GUC is
4240 * chosen to prevent overflow here.
4241 */
4244 {
4245 heap_parallel_workers++;
4249 }
4252 }
4255 {
4259 /* same calculation as for heap_pages above */
4262 {
4263 index_parallel_workers++;
4267 }
4271 else
4273 }
4274 }
4276 /* In no case use more than caller supplied maximum number of workers */
4280 }
4282 /*
4283 * generate_partitionwise_join_paths
4284 * Create paths representing partitionwise join for given partitioned
4285 * join relation.
4286 *
4287 * This must not be called until after we are done adding paths for all
4288 * child-joins. Otherwise, add_path might delete a path to which some path
4289 * generated here has a reference.
4290 */
4291 void
4293 {
4299 /* Handle only join relations here. */
4303 /* We've nothing to do if the relation is not partitioned. */
4307 /* The relation should have consider_partitionwise_join set. */
4310 /* Guard against stack overflow due to overly deep partition hierarchy. */
4316 /* Collect non-dummy child-joins. */
4318 {
4321 /* If it's been pruned entirely, it's certainly dummy. */
4325 /* Make partitionwise join paths for this partitioned child-join. */
4328 /* If we failed to make any path for this child, we must give up. */
4330 {
4331 /*
4332 * Mark the parent joinrel as unpartitioned so that later
4333 * functions treat it correctly.
4334 */
4337 }
4339 /* Else, identify the cheapest path for it. */
4342 /* Dummy children need not be scanned, so ignore those. */
4346 #ifdef OPTIMIZER_DEBUG
4348 #endif
4351 }
4353 /* If all child-joins are dummy, parent join is also dummy. */
4355 {
4358 }
4360 /* Build additional paths for this rel from child-join paths. */
4363 }