| blob | 9dfeb4ffd4bc3696caa899bb97206da43d1effec |
1 /*-------------------------------------------------------------------------
2 *
3 * relnode.c
4 * Relation-node lookup/construction routines
5 *
6 * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/optimizer/util/relnode.c
12 *
13 *-------------------------------------------------------------------------
14 */
17 #include <limits.h>
39 {
60 Relids both_input_relids,
80 JoinType jointype);
88 /*
89 * setup_simple_rel_arrays
90 * Prepare the arrays we use for quickly accessing base relations
91 * and AppendRelInfos.
92 */
93 void
95 {
97 Index rti;
100 /* Arrays are accessed using RT indexes (1..N) */
104 /*
105 * simple_rel_array is initialized to all NULLs, since no RelOptInfos
106 * exist yet. It'll be filled by later calls to build_simple_rel().
107 */
111 /* simple_rte_array is an array equivalent of the rtable list */
116 {
120 }
122 /* append_rel_array is not needed if there are no AppendRelInfos */
124 {
127 }
132 /*
133 * append_rel_array is filled with any already-existing AppendRelInfos,
134 * which currently could only come from UNION ALL flattening. We might
135 * add more later during inheritance expansion, but it's the
136 * responsibility of the expansion code to update the array properly.
137 */
139 {
143 /* Sanity check */
150 }
151 }
153 /*
154 * expand_planner_arrays
155 * Expand the PlannerInfo's per-RTE arrays by add_size members
156 * and initialize the newly added entries to NULLs
157 *
158 * Note: this causes the append_rel_array to become allocated even if
159 * it was not before. This is okay for current uses, because we only call
160 * this when adding child relations, which always have AppendRelInfos.
161 */
162 void
164 {
175 repalloc0_array(root->simple_rte_array, RangeTblEntry *, root->simple_rel_array_size, new_size);
179 repalloc0_array(root->append_rel_array, AppendRelInfo *, root->simple_rel_array_size, new_size);
180 else
185 }
187 /*
188 * build_simple_rel
189 * Construct a new RelOptInfo for a base relation or 'other' relation.
190 */
191 RelOptInfo *
193 {
197 /* Rel should not exist already */
202 /* Fetch RTE for relation */
210 /* cheap startup cost is interesting iff not all tuples to be retrieved */
224 /* min_attr, max_attr, attr_needed, attr_widths are set below */
238 {
243 /*
244 * For any RELATION rte, we need a userid with which to check
245 * permission access. Baserels simply use their own
246 * RTEPermissionInfo's checkAsUser.
247 *
248 * For otherrels normally there's no RTEPermissionInfo, so we use the
249 * parent's, which normally has one. The exceptional case is that the
250 * parent is a subquery, in which case the otherrel will have its own.
251 */
255 {
260 }
261 else
263 }
264 else
289 /*
290 * Pass assorted information down the inheritance hierarchy.
291 */
293 {
294 /* We keep back-links to immediate parent and topmost parent. */
299 /*
300 * A child rel is below the same outer joins as its parent. (We
301 * presume this info was already calculated for the parent.)
302 */
305 /*
306 * Also propagate lateral-reference information from appendrel parent
307 * rels to their child rels. We intentionally give each child rel the
308 * same minimum parameterization, even though it's quite possible that
309 * some don't reference all the lateral rels. This is because any
310 * append path for the parent will have to have the same
311 * parameterization for every child anyway, and there's no value in
312 * forcing extra reparameterize_path() calls. Similarly, a lateral
313 * reference to the parent prevents use of otherwise-movable join rels
314 * for each child.
315 *
316 * It's possible for child rels to have their own children, in which
317 * case the topmost parent's lateral info propagates all the way down.
318 */
322 }
323 else
324 {
332 }
334 /* Check type of rtable entry */
336 {
338 /* Table --- retrieve statistics from the system catalogs */
348 /*
349 * Subquery, function, tablefunc, values list, CTE, or ENR --- set
350 * up attr range and arrays
351 *
352 * Note: 0 is included in range to support whole-row Vars
353 */
362 /* RTE_RESULT has no columns, nor could it have whole-row Var */
372 }
374 /*
375 * Copy the parent's quals to the child, with appropriate substitution of
376 * variables. If any constant false or NULL clauses turn up, we can mark
377 * the child as dummy right away. (We must do this immediately so that
378 * pruning works correctly when recursing in expand_partitioned_rtentry.)
379 */
381 {
386 {
387 /*
388 * Some restriction clause reduced to constant FALSE or NULL after
389 * substitution, so this child need not be scanned.
390 */
392 }
393 }
395 /* Save the finished struct in the query's simple_rel_array */
399 }
401 /*
402 * find_base_rel
403 * Find a base or otherrel relation entry, which must already exist.
404 */
405 RelOptInfo *
407 {
410 /* use an unsigned comparison to prevent negative array element access */
412 {
416 }
421 }
423 /*
424 * find_base_rel_ignore_join
425 * Find a base or otherrel relation entry, which must already exist.
426 *
427 * Unlike find_base_rel, if relid references an outer join then this
428 * will return NULL rather than raising an error. This is convenient
429 * for callers that must deal with relid sets including both base and
430 * outer joins.
431 */
432 RelOptInfo *
434 {
435 /* use an unsigned comparison to prevent negative array element access */
437 {
445 /*
446 * We could just return NULL here, but for debugging purposes it seems
447 * best to actually verify that the relid is an outer join and not
448 * something weird.
449 */
453 }
458 }
460 /*
461 * build_join_rel_hash
462 * Construct the auxiliary hash table for join relations.
463 */
464 static void
466 {
468 HASHCTL hash_ctl;
471 /* Create the hash table */
482 /* Insert all the already-existing joinrels */
484 {
491 HASH_ENTER,
495 }
498 }
500 /*
501 * find_join_rel
502 * Returns relation entry corresponding to 'relids' (a set of RT indexes),
503 * or NULL if none exists. This is for join relations.
504 */
505 RelOptInfo *
507 {
508 /*
509 * Switch to using hash lookup when list grows "too long". The threshold
510 * is arbitrary and is known only here.
511 */
515 /*
516 * Use either hashtable lookup or linear search, as appropriate.
517 *
518 * Note: the seemingly redundant hashkey variable is used to avoid taking
519 * the address of relids; unless the compiler is exceedingly smart, doing
520 * so would force relids out of a register and thus probably slow down the
521 * list-search case.
522 */
524 {
530 HASH_FIND,
531 NULL);
534 }
535 else
536 {
540 {
545 }
546 }
549 }
551 /*
552 * set_foreign_rel_properties
553 * Set up foreign-join fields if outer and inner relation are foreign
554 * tables (or joins) belonging to the same server and assigned to the same
555 * user to check access permissions as.
556 *
557 * In addition to an exact match of userid, we allow the case where one side
558 * has zero userid (implying current user) and the other side has explicit
559 * userid that happens to equal the current user; but in that case, pushdown of
560 * the join is only valid for the current user. The useridiscurrent field
561 * records whether we had to make such an assumption for this join or any
562 * sub-join.
563 *
564 * Otherwise these fields are left invalid, so GetForeignJoinPaths will not be
565 * called for the join relation.
566 */
567 static void
570 {
573 {
575 {
580 }
583 {
588 }
591 {
596 }
597 }
598 }
600 /*
601 * add_join_rel
602 * Add given join relation to the list of join relations in the given
603 * PlannerInfo. Also add it to the auxiliary hashtable if there is one.
604 */
605 static void
607 {
608 /* GEQO requires us to append the new joinrel to the end of the list! */
611 /* store it into the auxiliary hashtable if there is one. */
613 {
619 HASH_ENTER,
623 }
624 }
626 /*
627 * build_join_rel
628 * Returns relation entry corresponding to the union of two given rels,
629 * creating a new relation entry if none already exists.
630 *
631 * 'joinrelids' is the Relids set that uniquely identifies the join
632 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
633 * joined
634 * 'sjinfo': join context info
635 * 'pushed_down_joins': any pushed-down outer joins that are now completed
636 * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr
637 * receives the list of RestrictInfo nodes that apply to this
638 * particular pair of joinable relations.
639 *
640 * restrictlist_ptr makes the routine's API a little grotty, but it saves
641 * duplicated calculation of the restrictlist...
642 */
643 RelOptInfo *
645 Relids joinrelids,
651 {
655 /* This function should be used only for join between parents. */
658 /*
659 * See if we already have a joinrel for this set of base rels.
660 */
664 {
665 /*
666 * Yes, so we only need to figure the restrictlist for this particular
667 * pair of component relations.
668 */
671 joinrel,
672 outer_rel,
673 inner_rel,
674 sjinfo);
676 }
678 /*
679 * Nope, so make one.
680 */
685 /* cheap startup cost is interesting iff not all tuples to be retrieved */
697 /* init direct_lateral_relids from children; we'll finish it up below */
750 /* Compute information relevant to the foreign relations. */
753 /*
754 * Fill the joinrel's tlist with just the Vars and PHVs that need to be
755 * output from this join (ie, are needed for higher joinclauses or final
756 * output).
757 *
758 * NOTE: the tlist order for a join rel will depend on which pair of outer
759 * and inner rels we first try to build it from. But the contents should
760 * be the same regardless.
761 */
768 /*
769 * add_placeholders_to_joinrel also took care of adding the ph_lateral
770 * sets of any PlaceHolderVars computed here to direct_lateral_relids, so
771 * now we can finish computing that. This is much like the computation of
772 * the transitively-closed lateral_relids in min_join_parameterization,
773 * except that here we *do* have to consider the added PHVs.
774 */
778 /*
779 * Construct restrict and join clause lists for the new joinrel. (The
780 * caller might or might not need the restrictlist, but I need it anyway
781 * for set_joinrel_size_estimates().)
782 */
785 sjinfo);
790 /*
791 * This is also the right place to check whether the joinrel has any
792 * pending EquivalenceClass joins.
793 */
796 /* Store the partition information. */
798 restrictlist);
800 /*
801 * Set estimates of the joinrel's size.
802 */
806 /*
807 * Set the consider_parallel flag if this joinrel could potentially be
808 * scanned within a parallel worker. If this flag is false for either
809 * inner_rel or outer_rel, then it must be false for the joinrel also.
810 * Even if both are true, there might be parallel-restricted expressions
811 * in the targetlist or quals.
812 *
813 * Note that if there are more than two rels in this relation, they could
814 * be divided between inner_rel and outer_rel in any arbitrary way. We
815 * assume this doesn't matter, because we should hit all the same baserels
816 * and joinclauses while building up to this joinrel no matter which we
817 * take; therefore, we should make the same decision here however we get
818 * here.
819 */
825 /* Add the joinrel to the PlannerInfo. */
828 /*
829 * Also, if dynamic-programming join search is active, add the new joinrel
830 * to the appropriate sublist. Note: you might think the Assert on number
831 * of members should be for equality, but some of the level 1 rels might
832 * have been joinrels already, so we can only assert <=.
833 */
835 {
840 }
843 }
845 /*
846 * build_child_join_rel
847 * Builds RelOptInfo representing join between given two child relations.
848 *
849 * 'outer_rel' and 'inner_rel' are the RelOptInfos of child relations being
850 * joined
851 * 'parent_joinrel' is the RelOptInfo representing the join between parent
852 * relations. Some of the members of new RelOptInfo are produced by
853 * translating corresponding members of this RelOptInfo
854 * 'restrictlist': list of RestrictInfo nodes that apply to this particular
855 * pair of joinable relations
856 * 'sjinfo': child join's join-type details
857 */
858 RelOptInfo *
862 {
867 /* Only joins between "other" relations land here. */
870 /* The parent joinrel should have consider_partitionwise_join set. */
873 /*
874 * Find the AppendRelInfo structures for the child baserels. We'll need
875 * these for computing the child join's relid set, and later for mapping
876 * Vars to the child rel.
877 */
887 /* cheap startup cost is interesting iff not all tuples to be retrieved */
943 /* Compute information relevant to foreign relations. */
946 /* Set up reltarget struct */
950 /* Construct joininfo list. */
953 nappinfos,
954 appinfos);
956 /*
957 * Lateral relids referred in child join will be same as that referred in
958 * the parent relation.
959 */
963 /*
964 * If the parent joinrel has pending equivalence classes, so does the
965 * child.
966 */
969 /* Is the join between partitions itself partitioned? */
971 restrictlist);
973 /* Child joinrel is parallel safe if parent is parallel safe. */
976 /* Set estimates of the child-joinrel's size. */
980 /* We build the join only once. */
983 /* Add the relation to the PlannerInfo. */
986 /*
987 * We might need EquivalenceClass members corresponding to the child join,
988 * so that we can represent sort pathkeys for it. As with children of
989 * baserels, we shouldn't need this unless there are relevant eclass joins
990 * (implying that a merge join might be possible) or pathkeys to sort by.
991 */
1000 }
1002 /*
1003 * min_join_parameterization
1004 *
1005 * Determine the minimum possible parameterization of a joinrel, that is, the
1006 * set of other rels it contains LATERAL references to. We save this value in
1007 * the join's RelOptInfo. This function is split out of build_join_rel()
1008 * because join_is_legal() needs the value to check a prospective join.
1009 */
1010 Relids
1012 Relids joinrelids,
1015 {
1016 Relids result;
1018 /*
1019 * Basically we just need the union of the inputs' lateral_relids, less
1020 * whatever is already in the join.
1021 *
1022 * It's not immediately obvious that this is a valid way to compute the
1023 * result, because it might seem that we're ignoring possible lateral refs
1024 * of PlaceHolderVars that are due to be computed at the join but not in
1025 * either input. However, because create_lateral_join_info() already
1026 * charged all such PHV refs to each member baserel of the join, they'll
1027 * be accounted for already in the inputs' lateral_relids. Likewise, we
1028 * do not need to worry about doing transitive closure here, because that
1029 * was already accounted for in the original baserel lateral_relids.
1030 */
1034 }
1036 /*
1037 * build_joinrel_tlist
1038 * Builds a join relation's target list from an input relation.
1039 * (This is invoked twice to handle the two input relations.)
1040 *
1041 * The join's targetlist includes all Vars of its member relations that
1042 * will still be needed above the join. This subroutine adds all such
1043 * Vars from the specified input rel's tlist to the join rel's tlist.
1044 * Likewise for any PlaceHolderVars emitted by the input rel.
1045 *
1046 * We also compute the expected width of the join's output, making use
1047 * of data that was cached at the baserel level by set_rel_width().
1048 *
1049 * Pass can_null as true if the join is an outer join that can null Vars
1050 * from this input relation. If so, we will (normally) add the join's relid
1051 * to the nulling bitmaps of Vars and PHVs bubbled up from the input.
1052 *
1053 * When forming an outer join's target list, special handling is needed in
1054 * case the outer join was commuted with another one per outer join identity 3
1055 * (see optimizer/README). We must take steps to ensure that the output Vars
1056 * have the same nulling bitmaps that they would if the two joins had been
1057 * done in syntactic order; else they won't match Vars appearing higher in
1058 * the query tree. An exception to the match-the-syntactic-order rule is
1059 * that when an outer join is pushed down into another one's RHS per identity
1060 * 3, we can't mark its Vars as nulled until the now-upper outer join is also
1061 * completed. So we need to do three things:
1062 *
1063 * First, we add the outer join's relid to the nulling bitmap only if the
1064 * outer join has been completely performed and the Var or PHV actually
1065 * comes from within the syntactically nullable side(s) of the outer join.
1066 * This takes care of the possibility that we have transformed
1067 * (A leftjoin B on (Pab)) leftjoin C on (Pbc)
1068 * to
1069 * A leftjoin (B leftjoin C on (Pbc)) on (Pab)
1070 * Here the pushed-down B/C join cannot mark C columns as nulled yet,
1071 * while the now-upper A/B join must not mark C columns as nulled by itself.
1072 *
1073 * Second, perform the same operation for each SpecialJoinInfo listed in
1074 * pushed_down_joins (which, in this example, would be the B/C join when
1075 * we are at the now-upper A/B join). This allows the now-upper join to
1076 * complete the marking of "C" Vars that now have fully valid values.
1077 *
1078 * Third, any relid in sjinfo->commute_above_r that is already part of
1079 * the joinrel is added to the nulling bitmaps of nullable Vars and PHVs.
1080 * This takes care of the reverse case where we implement
1081 * A leftjoin (B leftjoin C on (Pbc)) on (Pab)
1082 * as
1083 * (A leftjoin B on (Pab)) leftjoin C on (Pbc)
1084 * The C columns emitted by the B/C join need to be shown as nulled by both
1085 * the B/C and A/B joins, even though they've not physically traversed the
1086 * A/B join.
1087 */
1088 static void
1094 {
1101 {
1104 /*
1105 * For a PlaceHolderVar, we have to look up the PlaceHolderInfo.
1106 */
1108 {
1112 /* Is it still needed above this joinrel? */
1114 {
1115 /*
1116 * Yup, add it to the output. If this join potentially nulls
1117 * this input, we have to update the PHV's phnullingrels,
1118 * which means making a copy.
1119 */
1121 {
1123 /* See comments above to understand this logic */
1132 {
1139 }
1143 relids));
1144 }
1147 phv);
1148 /* Bubbling up the precomputed result has cost zero */
1150 }
1152 }
1154 /*
1155 * Otherwise, anything in a baserel or joinrel targetlist ought to be
1156 * a Var. (More general cases can only appear in appendrel child
1157 * rels, which will never be seen here.)
1158 */
1164 {
1165 /* UPDATE/DELETE/MERGE row identity vars are always needed */
1169 /* Update reltarget width estimate from RowIdentityVarInfo */
1171 }
1172 else
1173 {
1177 /* Get the Var's original base rel */
1180 /* Is it still needed above this joinrel? */
1185 /* Update reltarget width estimate from baserel's attr_widths */
1187 }
1189 /*
1190 * Add the Var to the output. If this join potentially nulls this
1191 * input, we have to update the Var's varnullingrels, which means
1192 * making a copy. But note that we don't ever add nullingrel bits to
1193 * row identity Vars (cf. comments in setrefs.c).
1194 */
1196 {
1198 /* See comments above to understand this logic */
1207 {
1214 }
1218 relids));
1219 }
1222 var);
1224 /* Vars have cost zero, so no need to adjust reltarget->cost */
1225 }
1228 }
1230 /*
1231 * build_joinrel_restrictlist
1232 * build_joinrel_joinlist
1233 * These routines build lists of restriction and join clauses for a
1234 * join relation from the joininfo lists of the relations it joins.
1235 *
1236 * These routines are separate because the restriction list must be
1237 * built afresh for each pair of input sub-relations we consider, whereas
1238 * the join list need only be computed once for any join RelOptInfo.
1239 * The join list is fully determined by the set of rels making up the
1240 * joinrel, so we should get the same results (up to ordering) from any
1241 * candidate pair of sub-relations. But the restriction list is whatever
1242 * is not handled in the sub-relations, so it depends on which
1243 * sub-relations are considered.
1244 *
1245 * If a join clause from an input relation refers to base+OJ rels still not
1246 * present in the joinrel, then it is still a join clause for the joinrel;
1247 * we put it into the joininfo list for the joinrel. Otherwise,
1248 * the clause is now a restrict clause for the joined relation, and we
1249 * return it to the caller of build_joinrel_restrictlist() to be stored in
1250 * join paths made from this pair of sub-relations. (It will not need to
1251 * be considered further up the join tree.)
1252 *
1253 * In many cases we will find the same RestrictInfos in both input
1254 * relations' joinlists, so be careful to eliminate duplicates.
1255 * Pointer equality should be a sufficient test for dups, since all
1256 * the various joinlist entries ultimately refer to RestrictInfos
1257 * pushed into them by distribute_restrictinfo_to_rels().
1258 *
1259 * 'joinrel' is a join relation node
1260 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
1261 * to form joinrel.
1262 * 'sjinfo': join context info
1263 *
1264 * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
1265 * whereas build_joinrel_joinlist() stores its results in the joinrel's
1266 * joininfo list. One or the other must accept each given clause!
1267 *
1268 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
1269 * up to the join relation. I believe this is no longer necessary, because
1270 * RestrictInfo nodes are no longer context-dependent. Instead, just include
1271 * the original nodes in the lists made for the join relation.
1272 */
1279 {
1281 Relids both_input_relids;
1285 /*
1286 * Collect all the clauses that syntactically belong at this level,
1287 * eliminating any duplicates (important since we will see many of the
1288 * same clauses arriving from both input relations).
1289 */
1295 /*
1296 * Add on any clauses derived from EquivalenceClasses. These cannot be
1297 * redundant with the clauses in the joininfo lists, so don't bother
1298 * checking.
1299 */
1304 inner_rel,
1305 sjinfo));
1308 }
1310 static void
1314 {
1317 /*
1318 * Collect all the clauses that syntactically belong above this level,
1319 * eliminating any duplicates (important since we will see many of the
1320 * same clauses arriving from both input relations).
1321 */
1326 }
1332 Relids both_input_relids,
1334 {
1338 {
1342 {
1343 /*
1344 * This clause should become a restriction clause for the joinrel,
1345 * since it refers to no outside rels. However, if it's a clone
1346 * clause then it might be too late to evaluate it, so we have to
1347 * check. (If it is too late, just ignore the clause, taking it
1348 * on faith that another clone was or will be selected.) Clone
1349 * clauses should always be outer-join clauses, so we compare
1350 * against both_input_relids.
1351 */
1353 {
1359 }
1360 else
1361 {
1362 /*
1363 * For non-clone clauses, we just Assert it's OK. These might
1364 * be either join or filter clauses; if it's a join clause
1365 * then it should not refer to the current join's output.
1366 * (There is little point in checking incompatible_relids,
1367 * because it'll be NULL.)
1368 */
1371 both_input_relids));
1372 }
1374 /*
1375 * OK, so add it to the list, being careful to eliminate
1376 * duplicates. (Since RestrictInfo nodes in different joinlists
1377 * will have been multiply-linked rather than copied, pointer
1378 * equality should be a sufficient test.)
1379 */
1381 }
1382 else
1383 {
1384 /*
1385 * This clause is still a join clause at this level, so we ignore
1386 * it in this routine.
1387 */
1388 }
1389 }
1392 }
1398 {
1401 /* Expected to be called only for join between parent relations. */
1405 {
1409 {
1410 /*
1411 * This clause becomes a restriction clause for the joinrel, since
1412 * it refers to no outside rels. So we can ignore it in this
1413 * routine.
1414 */
1415 }
1416 else
1417 {
1418 /*
1419 * This clause is still a join clause at this level, so add it to
1420 * the new joininfo list, being careful to eliminate duplicates.
1421 * (Since RestrictInfo nodes in different joinlists will have been
1422 * multiply-linked rather than copied, pointer equality should be
1423 * a sufficient test.)
1424 */
1426 }
1427 }
1430 }
1433 /*
1434 * fetch_upper_rel
1435 * Build a RelOptInfo describing some post-scan/join query processing,
1436 * or return a pre-existing one if somebody already built it.
1437 *
1438 * An "upper" relation is identified by an UpperRelationKind and a Relids set.
1439 * The meaning of the Relids set is not specified here, and very likely will
1440 * vary for different relation kinds.
1441 *
1442 * Most of the fields in an upper-level RelOptInfo are not used and are not
1443 * set here (though makeNode should ensure they're zeroes). We basically only
1444 * care about fields that are of interest to add_path() and set_cheapest().
1445 */
1446 RelOptInfo *
1448 {
1452 /*
1453 * For the moment, our indexing data structure is just a List for each
1454 * relation kind. If we ever get so many of one kind that this stops
1455 * working well, we can improve it. No code outside this function should
1456 * assume anything about how to find a particular upperrel.
1457 */
1459 /* If we already made this upperrel for the query, return it */
1461 {
1466 }
1472 /* cheap startup cost is interesting iff not all tuples to be retrieved */
1486 }
1489 /*
1490 * find_childrel_parents
1491 * Compute the set of parent relids of an appendrel child rel.
1492 *
1493 * Since appendrels can be nested, a child could have multiple levels of
1494 * appendrel ancestors. This function computes a Relids set of all the
1495 * parent relation IDs.
1496 */
1497 Relids
1499 {
1505 do
1506 {
1512 /* traverse up to the parent rel, loop if it's also a child rel */
1519 }
1522 /*
1523 * get_baserel_parampathinfo
1524 * Get the ParamPathInfo for a parameterized path for a base relation,
1525 * constructing one if we don't have one already.
1526 *
1527 * This centralizes estimating the rowcounts for parameterized paths.
1528 * We need to cache those to be sure we use the same rowcount for all paths
1529 * of the same parameterization for a given rel. This is also a convenient
1530 * place to determine which movable join clauses the parameterized path will
1531 * be responsible for evaluating.
1532 */
1533 ParamPathInfo *
1535 Relids required_outer)
1536 {
1538 Relids joinrelids;
1544 /* If rel has LATERAL refs, every path for it should account for them */
1547 /* Unparameterized paths have no ParamPathInfo */
1553 /* If we already have a PPI for this parameterization, just return it */
1557 /*
1558 * Identify all joinclauses that are movable to this base rel given this
1559 * parameterization.
1560 */
1564 {
1569 joinrelids))
1571 }
1573 /*
1574 * Add in joinclauses generated by EquivalenceClasses, too. (These
1575 * necessarily satisfy join_clause_is_movable_into.)
1576 */
1579 joinrelids,
1580 required_outer,
1581 baserel,
1582 NULL));
1584 /* Compute set of serial numbers of the enforced clauses */
1587 {
1591 }
1593 /* Estimate the number of rows returned by the parameterized scan */
1596 /* And now we can build the ParamPathInfo */
1605 }
1607 /*
1608 * get_joinrel_parampathinfo
1609 * Get the ParamPathInfo for a parameterized path for a join relation,
1610 * constructing one if we don't have one already.
1611 *
1612 * This centralizes estimating the rowcounts for parameterized paths.
1613 * We need to cache those to be sure we use the same rowcount for all paths
1614 * of the same parameterization for a given rel. This is also a convenient
1615 * place to determine which movable join clauses the parameterized path will
1616 * be responsible for evaluating.
1617 *
1618 * outer_path and inner_path are a pair of input paths that can be used to
1619 * construct the join, and restrict_clauses is the list of regular join
1620 * clauses (including clauses derived from EquivalenceClasses) that must be
1621 * applied at the join node when using these inputs.
1622 *
1623 * Unlike the situation for base rels, the set of movable join clauses to be
1624 * enforced at a join varies with the selected pair of input paths, so we
1625 * must calculate that and pass it back, even if we already have a matching
1626 * ParamPathInfo. We handle this by adding any clauses moved down to this
1627 * join to *restrict_clauses, which is an in/out parameter. (The addition
1628 * is done in such a way as to not modify the passed-in List structure.)
1629 *
1630 * Note: when considering a nestloop join, the caller must have removed from
1631 * restrict_clauses any movable clauses that are themselves scheduled to be
1632 * pushed into the right-hand path. We do not do that here since it's
1633 * unnecessary for other join types.
1634 */
1635 ParamPathInfo *
1640 Relids required_outer,
1642 {
1644 Relids join_and_req;
1645 Relids outer_and_req;
1646 Relids inner_and_req;
1653 /* If rel has LATERAL refs, every path for it should account for them */
1656 /* Unparameterized paths have no ParamPathInfo or extra join clauses */
1662 /*
1663 * Identify all joinclauses that are movable to this join rel given this
1664 * parameterization. These are the clauses that are movable into this
1665 * join, but not movable into either input path. Treat an unparameterized
1666 * input path as not accepting parameterized clauses (because it won't,
1667 * per the shortcut exit above), even though the joinclause movement rules
1668 * might allow the same clauses to be moved into a parameterized path for
1669 * that rel.
1670 */
1675 else
1680 else
1685 {
1690 join_and_req) &&
1693 outer_and_req) &&
1696 inner_and_req))
1698 }
1700 /* Consider joinclauses generated by EquivalenceClasses, too */
1702 join_and_req,
1703 required_outer,
1704 joinrel,
1705 NULL);
1706 /* We only want ones that aren't movable to lower levels */
1709 {
1714 join_and_req));
1717 outer_and_req))
1721 inner_and_req))
1722 {
1723 /* drop if movable into RHS, but remember EC for use below */
1727 }
1729 }
1731 /*
1732 * EquivalenceClasses are harder to deal with than we could wish, because
1733 * of the fact that a given EC can generate different clauses depending on
1734 * context. Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
1735 * LHS and RHS of the current join and Z is in required_outer, and further
1736 * suppose that the inner_path is parameterized by both X and Z. The code
1737 * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
1738 * and in the latter case will have discarded it as being movable into the
1739 * RHS. However, the EC machinery might have produced either Y.Y = X.X or
1740 * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
1741 * not have produced both, and we can't readily tell from here which one
1742 * it did pick. If we add no clause to this join, we'll end up with
1743 * insufficient enforcement of the EC; either Z.Z or X.X will fail to be
1744 * constrained to be equal to the other members of the EC. (When we come
1745 * to join Z to this X/Y path, we will certainly drop whichever EC clause
1746 * is generated at that join, so this omission won't get fixed later.)
1747 *
1748 * To handle this, for each EC we discarded such a clause from, try to
1749 * generate a clause connecting the required_outer rels to the join's LHS
1750 * ("Z.Z = X.X" in the terms of the above example). If successful, and if
1751 * the clause can't be moved to the LHS, add it to the current join's
1752 * restriction clauses. (If an EC cannot generate such a clause then it
1753 * has nothing that needs to be enforced here, while if the clause can be
1754 * moved into the LHS then it should have been enforced within that path.)
1755 *
1756 * Note that we don't need similar processing for ECs whose clause was
1757 * considered to be movable into the LHS, because the LHS can't refer to
1758 * the RHS so there is no comparable ambiguity about what it might
1759 * actually be enforcing internally.
1760 */
1762 {
1763 Relids real_outer_and_req;
1766 required_outer);
1767 eclauses =
1769 dropped_ecs,
1770 real_outer_and_req,
1771 required_outer,
1774 {
1779 real_outer_and_req));
1782 outer_and_req))
1784 }
1785 }
1787 /*
1788 * Now, attach the identified moved-down clauses to the caller's
1789 * restrict_clauses list. By using list_concat in this order, we leave
1790 * the original list structure of restrict_clauses undamaged.
1791 */
1794 /* If we already have a PPI for this parameterization, just return it */
1798 /* Estimate the number of rows returned by the parameterized join */
1800 outer_path,
1801 inner_path,
1802 sjinfo,
1805 /*
1806 * And now we can build the ParamPathInfo. No point in saving the
1807 * input-pair-dependent clause list, though.
1808 *
1809 * Note: in GEQO mode, we'll be called in a temporary memory context, but
1810 * the joinrel structure is there too, so no problem.
1811 */
1820 }
1822 /*
1823 * get_appendrel_parampathinfo
1824 * Get the ParamPathInfo for a parameterized path for an append relation.
1825 *
1826 * For an append relation, the rowcount estimate will just be the sum of
1827 * the estimates for its children. However, we still need a ParamPathInfo
1828 * to flag the fact that the path requires parameters. So this just creates
1829 * a suitable struct with zero ppi_rows (and no ppi_clauses either, since
1830 * the Append node isn't responsible for checking quals).
1831 */
1832 ParamPathInfo *
1834 {
1837 /* If rel has LATERAL refs, every path for it should account for them */
1840 /* Unparameterized paths have no ParamPathInfo */
1846 /* If we already have a PPI for this parameterization, just return it */
1850 /* Else build the ParamPathInfo */
1859 }
1861 /*
1862 * Returns a ParamPathInfo for the parameterization given by required_outer, if
1863 * already available in the given rel. Returns NULL otherwise.
1864 */
1865 ParamPathInfo *
1867 {
1871 {
1876 }
1879 }
1881 /*
1882 * get_param_path_clause_serials
1883 * Given a parameterized Path, return the set of pushed-down clauses
1884 * (identified by rinfo_serial numbers) enforced within the Path.
1885 */
1886 Bitmapset *
1888 {
1894 {
1895 /*
1896 * For a join path, combine clauses enforced within either input path
1897 * with those enforced as joinrestrictinfo in this path. Note that
1898 * joinrestrictinfo may include some non-pushed-down clauses, but for
1899 * current purposes it's okay if we include those in the result. (To
1900 * be more careful, we could check for clause_relids overlapping the
1901 * path parameterization, but it's not worth the cycles for now.)
1902 */
1913 {
1917 }
1919 }
1921 {
1922 /*
1923 * For an appendrel, take the intersection of the sets of clauses
1924 * enforced in each input path.
1925 */
1932 {
1939 else
1941 }
1943 }
1945 {
1946 /* Same as AppendPath case */
1953 {
1960 else
1962 }
1964 }
1965 else
1966 {
1967 /*
1968 * Otherwise, it's a baserel path and we can use the
1969 * previously-computed set of serial numbers.
1970 */
1972 }
1973 }
1975 /*
1976 * build_joinrel_partition_info
1977 * Checks if the two relations being joined can use partitionwise join
1978 * and if yes, initialize partitioning information of the resulting
1979 * partitioned join relation.
1980 */
1981 static void
1986 {
1987 PartitionScheme part_scheme;
1989 /* Nothing to do if partitionwise join technique is disabled. */
1991 {
1994 }
1996 /*
1997 * We can only consider this join as an input to further partitionwise
1998 * joins if (a) the input relations are partitioned and have
1999 * consider_partitionwise_join=true, (b) the partition schemes match, and
2000 * (c) we can identify an equi-join between the partition keys. Note that
2001 * if it were possible for have_partkey_equi_join to return different
2002 * answers for the same joinrel depending on which join ordering we try
2003 * first, this logic would break. That shouldn't happen, though, because
2004 * of the way the query planner deduces implied equalities and reorders
2005 * the joins. Please see optimizer/README for details.
2006 */
2013 {
2016 }
2020 /*
2021 * This function will be called only once for each joinrel, hence it
2022 * should not have partitioning fields filled yet.
2023 */
2028 /*
2029 * If the join relation is partitioned, it uses the same partitioning
2030 * scheme as the joining relations.
2031 *
2032 * Note: we calculate the partition bounds, number of partitions, and
2033 * child-join relations of the join relation in try_partitionwise_join().
2034 */
2039 /*
2040 * Set the consider_partitionwise_join flag.
2041 */
2045 }
2047 /*
2048 * have_partkey_equi_join
2049 *
2050 * Returns true if there exist equi-join conditions involving pairs
2051 * of matching partition keys of the relations being joined for all
2052 * partition keys.
2053 */
2054 static bool
2058 {
2065 /*
2066 * This function must only be called when the joined relations have same
2067 * partitioning scheme.
2068 */
2074 {
2082 /* If processing an outer join, only use its own join clauses. */
2087 /* Skip clauses which can not be used for a join. */
2091 /* Skip clauses which are not equality conditions. */
2095 /* Should be OK to assume it's an OpExpr. */
2098 /* Match the operands to the relation. */
2101 {
2104 }
2107 {
2110 }
2111 else
2114 /*
2115 * Now we need to know whether the join operator is strict; see
2116 * comments in pathnodes.h.
2117 */
2120 /*
2121 * Vars appearing in the relation's partition keys will not have any
2122 * varnullingrels, but those in expr1 and expr2 will if we're above
2123 * outer joins that could null the respective rels. It's okay to
2124 * match anyway, if the join operator is strict.
2125 */
2127 {
2131 NULL);
2135 NULL);
2136 }
2138 /*
2139 * Only clauses referencing the partition keys are useful for
2140 * partitionwise join.
2141 */
2149 /*
2150 * If the clause refers to keys at different ordinal positions, it can
2151 * not be used for partitionwise join.
2152 */
2156 /*
2157 * The clause allows partitionwise join only if it uses the same
2158 * operator family as that specified by the partition key.
2159 */
2161 {
2166 }
2171 /* Mark the partition key as having an equi-join clause. */
2173 }
2175 /* Check whether every partition key has an equi-join condition. */
2177 {
2180 }
2183 }
2185 /*
2186 * match_expr_to_partition_keys
2187 *
2188 * Tries to match an expression to one of the nullable or non-nullable
2189 * partition keys of "rel". Returns the matched key's ordinal position,
2190 * or -1 if the expression could not be matched to any of the keys.
2191 *
2192 * strict_op must be true if the expression will be compared with the
2193 * partition key using a strict operator. This allows us to consider
2194 * nullable as well as nonnullable partition keys.
2195 */
2196 static int
2198 {
2201 /* This function should be called only for partitioned relations. */
2206 /* Remove any relabel decorations. */
2211 {
2214 /* We can always match to the non-nullable partition keys. */
2216 {
2219 }
2224 /*
2225 * If it's a strict join operator then a NULL partition key on one
2226 * side will not join to any partition key on the other side, and in
2227 * particular such a row can't join to a row from a different
2228 * partition on the other side. So, it's okay to search the nullable
2229 * partition keys as well.
2230 */
2232 {
2235 }
2236 }
2239 }
2241 /*
2242 * set_joinrel_partition_key_exprs
2243 * Initialize partition key expressions for a partitioned joinrel.
2244 */
2245 static void
2248 JoinType jointype)
2249 {
2257 /*
2258 * The joinrel's partition expressions are the same as those of the input
2259 * rels, but we must properly classify them as nullable or not in the
2260 * joinrel's output. (Also, we add some more partition expressions if
2261 * it's a FULL JOIN.)
2262 */
2264 {
2265 /* mark these const to enforce that we copy them properly */
2275 {
2276 /*
2277 * A join relation resulting from an INNER join may be
2278 * regarded as partitioned by either of the inner and outer
2279 * relation keys. For example, A INNER JOIN B ON A.a = B.b
2280 * can be regarded as partitioned on either A.a or B.b. So we
2281 * add both keys to the joinrel's partexpr lists. However,
2282 * anything that was already nullable still has to be treated
2283 * as nullable.
2284 */
2288 inner_null_expr);
2291 /*
2292 * A join relation resulting from a SEMI or ANTI join may be
2293 * regarded as partitioned by the outer relation keys. The
2294 * inner relation's keys are no longer interesting; since they
2295 * aren't visible in the join output, nothing could join to
2296 * them.
2297 */
2304 /*
2305 * A join relation resulting from a LEFT OUTER JOIN likewise
2306 * may be regarded as partitioned on the (non-nullable) outer
2307 * relation keys. The inner (nullable) relation keys are okay
2308 * as partition keys for further joins as long as they involve
2309 * strict join operators.
2310 */
2314 outer_null_expr);
2316 inner_null_expr);
2319 /*
2320 * For FULL OUTER JOINs, both relations are nullable, so the
2321 * resulting join relation may be regarded as partitioned on
2322 * either of inner and outer relation keys, but only for joins
2323 * that involve strict join operators.
2324 */
2327 inner_expr);
2329 outer_null_expr);
2331 inner_null_expr);
2333 /*
2334 * Also add CoalesceExprs corresponding to each possible
2335 * full-join output variable (that is, left side coalesced to
2336 * right side), so that we can match equijoin expressions
2337 * using those variables. We really only need these for
2338 * columns merged by JOIN USING, and only with the pairs of
2339 * input items that correspond to the data structures that
2340 * parse analysis would build for such variables. But it's
2341 * hard to tell which those are, so just make all the pairs.
2342 * Extra items in the nullable_partexprs list won't cause big
2343 * problems. (It's possible that such items will get matched
2344 * to user-written COALESCEs, but it should still be valid to
2345 * partition on those, since they're going to be either the
2346 * partition column or NULL; it's the same argument as for
2347 * partitionwise nesting of any outer join.) We assume no
2348 * type coercions are needed to make the coalesce expressions,
2349 * since columns of different types won't have gotten
2350 * classified as the same PartitionScheme. Note that we
2351 * intentionally leave out the varnullingrels decoration that
2352 * would ordinarily appear on the Vars inside these
2353 * CoalesceExprs, because have_partkey_equi_join will strip
2354 * varnullingrels from the expressions it will compare to the
2355 * partexprs.
2356 */
2358 {
2363 {
2372 }
2373 }
2378 }
2382 }
2383 }
2385 /*
2386 * build_child_join_reltarget
2387 * Set up a child-join relation's reltarget from a parent-join relation.
2388 */
2389 static void
2395 {
2396 /* Build the targetlist */
2402 /* Set the cost and width fields */
2406 }