1/*-------------------------------------------------------------------------
4 * Routines for simplifying joins after initial query analysis
6 * While we do a great deal of join simplification in prep/prepjointree.c,
7 * certain optimizations cannot be performed at that stage for lack of
8 * detailed information about the query. The routines here are invoked
9 * after initsplan.c has done its work, and can do additional join removal
10 * and simplification steps based on the information extracted. The penalty
11 * is that we have to work harder to clean up after ourselves when we modify
12 * the query, since the derived data structures have to be updated too.
14 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
15 * Portions Copyright (c) 1994, Regents of the University of California
19 * src/backend/optimizer/plan/analyzejoins.c
21 *-------------------------------------------------------------------------
38 * Utility structure. A sorting procedure is needed to simplify the search
39 * of SJE-candidate baserels referencing the same database relation. Having
40 * collected all baserels from the query jointree, the planner sorts them
41 * according to the reloid value, groups them with the next pass and attempts
42 * to remove self-joins.
44 * Preliminary sorting prevents quadratic behavior that can be harmful in the
45 * case of numerous joins.
60 int relid,
int ojrelid);
63 int relid,
int subst);
67 List *clause_list,
List **extra_clauses);
75 List **extra_clauses);
82 * remove_useless_joins
83 * Check for relations that don't actually need to be joined at all,
84 * and remove them from the query.
86 * We are passed the current joinlist and return the updated list. Other
87 * data structures that have to be updated are accessible via "root".
95 * We are only interested in relations that are left-joined to, so we can
96 * scan the join_info_list to find them easily.
99 foreach(lc,
root->join_info_list)
105 /* Skip if not removable */
110 * Currently, join_is_removable can only succeed when the sjinfo's
111 * righthand is a single baserel. Remove that rel from the query and
118 /* We verify that exactly one reference gets removed from joinlist */
122 elog(
ERROR,
"failed to find relation %d in joinlist", innerrelid);
125 * We can delete this SpecialJoinInfo from the list too, since it's no
126 * longer of interest. (Since we'll restart the foreach loop
127 * immediately, we don't bother with foreach_delete_current.)
132 * Restart the scan. This is necessary to ensure we find all
133 * removable joins independently of ordering of the join_info_list
134 * (note that removal of attr_needed bits may make a join appear
135 * removable that did not before).
145 * Check whether we need not perform this special join at all, because
146 * it will just duplicate its left input.
148 * This is true for a left join for which the join condition cannot match
149 * more than one inner-side row. (There are other possibly interesting
150 * cases, but we don't have the infrastructure to prove them.) We also
151 * have to check that the inner side doesn't generate any variables needed
166 * Must be a left join to a single baserel, else we aren't going to be
167 * able to do anything with it.
176 * Never try to eliminate a left join to the query result rel. Although
177 * the case is syntactically impossible in standard SQL, MERGE will build
178 * a join tree that looks exactly like that.
180 if (innerrelid ==
root->parse->resultRelation)
186 * Before we go to the effort of checking whether any innerrel variables
187 * are needed above the join, make a quick check to eliminate cases in
188 * which we will surely be unable to prove uniqueness of the innerrel.
193 /* Compute the relid set for the join we are considering */
200 * We can't remove the join if any inner-rel attributes are used above the
201 * join. Here, "above" the join includes pushed-down conditions, so we
202 * should reject if attr_needed includes the OJ's own relid; therefore,
203 * compare to inputrelids not joinrelids.
205 * As a micro-optimization, it seems better to start with max_attr and
206 * count down rather than starting with min_attr and counting up, on the
207 * theory that the system attributes are somewhat less likely to be wanted
208 * and should be tested last.
214 if (!
bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
219 * Similarly check that the inner rel isn't needed by any PlaceHolderVars
220 * that will be used above the join. The PHV case is a little bit more
221 * complicated, because PHVs may have been assigned a ph_eval_at location
222 * that includes the innerrel, yet their contained expression might not
223 * actually reference the innerrel (it could be just a constant, for
224 * instance). If such a PHV is due to be evaluated above the join then it
225 * needn't prevent join removal.
227 foreach(l,
root->placeholder_list)
232 return false;
/* it references innerrel laterally */
234 continue;
/* it definitely doesn't reference innerrel */
236 continue;
/* PHV is not used above the join */
238 return false;
/* it has to be evaluated below the join */
241 * We need to be sure there will still be a place to evaluate the PHV
242 * if we remove the join, ie that ph_eval_at wouldn't become empty.
245 return false;
/* there isn't any other place to eval PHV */
246 /* Check contained expression last, since this is a bit expensive */
249 return false;
/* contained expression references innerrel */
253 * Search for mergejoinable clauses that constrain the inner rel against
254 * either the outer rel or a pseudoconstant. If an operator is
255 * mergejoinable then it behaves like equality for some btree opclass, so
256 * it's what we want. The mergejoinability test also eliminates clauses
257 * containing volatile functions, which we couldn't depend on.
264 * If the current join commutes with some other outer join(s) via
265 * outer join identity 3, there will be multiple clones of its join
266 * clauses in the joininfo list. We want to consider only the
267 * has_clone form of such clauses. Processing more than one form
268 * would be wasteful, and also some of the others would confuse the
269 * RINFO_IS_PUSHED_DOWN test below.
272 continue;
/* ignore it */
275 * If it's not a join clause for this outer join, we can't use it.
276 * Note that if the clause is pushed-down, then it is logically from
277 * above the outer join, even if it references no other rels (it might
278 * be from WHERE, for example).
281 continue;
/* ignore; not useful here */
283 /* Ignore if it's not a mergejoinable clause */
284 if (!restrictinfo->can_join ||
285 restrictinfo->mergeopfamilies ==
NIL)
286 continue;
/* not mergejoinable */
289 * Check if the clause has the form "outer op inner" or "inner op
290 * outer", and if so mark which side is inner.
294 continue;
/* no good for these input relations */
296 /* OK, add to list */
297 clause_list =
lappend(clause_list, restrictinfo);
301 * Now that we have the relevant equality join clauses, try to prove the
308 * Some day it would be nice to check for other methods of establishing
316 * Remove the target rel->relid and references to the target join from the
317 * planner's data structures, having determined that there is no need
318 * to include them in the query. Optionally replace them with subst if subst
321 * This function updates only parts needed for both left-join removal and
329 int relid = rel->
relid;
334 * Update all_baserels and related relid sets.
348 * Likewise remove references from SpecialJoinInfo data structures.
350 * This is relevant in case the outer join we're deleting is nested inside
351 * other outer joins: the upper joins' relid sets have to be adjusted. The
352 * RHS of the target outer join will be made empty here, but that's OK
353 * since caller will delete that SpecialJoinInfo entirely.
355 foreach(l,
root->join_info_list)
360 * initsplan.c is fairly cavalier about allowing SpecialJoinInfos'
361 * lefthand/righthand relid sets to be shared with other data
362 * structures. Ensure that we don't modify the original relid sets.
363 * (The commute_xxx sets are always per-SpecialJoinInfo though.)
369 /* Now remove relid from the sets: */
379 /* Remove sjinfo->ojrelid bits from the sets: */
388 /* relid cannot appear in these fields, but ojrelid can: */
408 * Likewise remove references from PlaceHolderVar data structures,
409 * removing any no-longer-needed placeholders entirely. We remove PHV
410 * only for left-join removal. With self-join elimination, PHVs already
411 * get moved to the remaining relation, where they might still be needed.
412 * It might also happen that we skip the removal of some PHVs that could
413 * be removed. However, the overhead of extra PHVs is small compared to
414 * the complexity of analysis needed to remove them.
416 * Removal is a bit trickier than it might seem: we can remove PHVs that
417 * are used at the target rel and/or in the join qual, but not those that
418 * are used at join partner rels or above the join. It's not that easy to
419 * distinguish PHVs used at partner rels from those used in the join qual,
420 * since they will both have ph_needed sets that are subsets of
421 * joinrelids. However, a PHV used at a partner rel could not have the
422 * target rel in ph_eval_at, so we check that while deciding whether to
423 * remove or just update the PHV. There is no corresponding test in
424 * join_is_removable because it doesn't need to distinguish those cases.
426 foreach(l,
root->placeholder_list)
431 if (sjinfo != NULL &&
437 * This code shouldn't be executed if one relation is substituted
438 * with another: in this case, the placeholder may be employed in
439 * a filter inside the scan node the SJE removes.
443 root->placeholder_array[phinfo->
phid] = NULL;
454 /* Reduce ph_needed to contain only "relation 0"; see below */
463 * ph_lateral might contain rels mentioned in ph_eval_at after the
464 * replacement, remove them.
467 /* ph_lateral might or might not be empty */
483 * Likewise remove references from EquivalenceClasses.
485 foreach(l,
root->eq_classes)
495 * Finally, we must recompute per-Var attr_needed and per-PlaceHolderVar
496 * ph_needed relid sets. These have to be known accurately, else we may
497 * fail to remove other now-removable outer joins. And our removal of the
498 * join clause(s) for this outer join may mean that Vars that were
499 * formerly needed no longer are. So we have to do this honestly by
500 * repeating the construction of those relid sets. We can cheat to one
501 * small extent: we can avoid re-examining the targetlist and HAVING qual
502 * by preserving "relation 0" bits from the existing relid sets. This is
503 * safe because we'd never remove such references.
505 * So, start by removing all other bits from attr_needed sets and
506 * lateral_vars lists. (We already did this above for ph_needed.)
508 for (rti = 1; rti <
root->simple_rel_array_size; rti++)
513 /* there may be empty slots corresponding to non-baserel RTEs */
514 if (otherrel == NULL)
517 Assert(otherrel->
relid == rti);
/* sanity check on array */
526 otherrel->attr_needed[attroff] = NULL;
536 * Remove the target relid and references to the target join from the
537 * planner's data structures, having determined that there is no need
538 * to include them in the query.
540 * We are not terribly thorough here. We only bother to update parts of
541 * the planner's data structures that will actually be consulted later.
554 /* Compute the relid set for the join we are considering */
562 * Remove any joinquals referencing the rel from the joininfo lists.
564 * In some cases, a joinqual has to be put back after deleting its
565 * reference to the target rel. This can occur for pseudoconstant and
566 * outerjoin-delayed quals, which can get marked as requiring the rel in
567 * order to force them to be evaluated at or above the join. We can't
568 * just discard them, though. Only quals that logically belonged to the
569 * outer join being discarded should be removed from the query.
571 * We might encounter a qual that is a clone of a deletable qual with some
572 * outer-join relids added (see deconstruct_distribute_oj_quals). To
573 * ensure we get rid of such clones as well, add the relids of all OJs
574 * commutable with this one to the set we test against for
577 join_plus_commute =
bms_union(joinrelids,
583 * We must make a copy of the rel's old joininfo list before starting the
584 * loop, because otherwise remove_join_clause_from_rels would destroy the
585 * list while we're scanning it.
588 foreach(l, joininfos)
597 * There might be references to relid or ojrelid in the
598 * RestrictInfo's relid sets, as a consequence of PHVs having had
599 * ph_eval_at sets that include those. We already checked above
600 * that any such PHV is safe (and updated its ph_eval_at), so we
601 * can just drop those references.
606 * Cross-check that the clause itself does not reference the
607 * target rel or join.
609#ifdef USE_ASSERT_CHECKING
618 /* Now throw it back into the joininfo lists */
624 * There may be references to the rel in root->fkey_list, but if so,
625 * match_foreign_keys_to_quals() will get rid of them.
629 * Now remove the rel from the baserel array to prevent it from being
630 * referenced again. (We can't do this earlier because
631 * remove_join_clause_from_rels will touch it.)
633 root->simple_rel_array[relid] = NULL;
634 root->simple_rte_array[relid] = NULL;
636 /* And nuke the RelOptInfo, just in case there's another access path */
640 * Now repeat construction of attr_needed bits coming from all other
650 * Remove any references to relid or ojrelid from the RestrictInfo.
652 * We only bother to clean out bits in clause_relids and required_relids,
653 * not nullingrel bits in contained Vars and PHVs. (This might have to be
654 * improved sometime.) However, if the RestrictInfo contains an OR clause
655 * we have to also clean up the sub-clauses.
661 * initsplan.c is fairly cavalier about allowing RestrictInfos to share
662 * relid sets with other RestrictInfos, and SpecialJoinInfos too. Make
663 * sure this RestrictInfo has its own relid sets before we modify them.
664 * (In present usage, clause_relids is probably not shared, but
665 * required_relids could be; let's not assume anything.)
667 rinfo->clause_relids =
bms_copy(rinfo->clause_relids);
668 rinfo->clause_relids =
bms_del_member(rinfo->clause_relids, relid);
669 rinfo->clause_relids =
bms_del_member(rinfo->clause_relids, ojrelid);
670 /* Likewise for required_relids */
675 /* If it's an OR, recurse to clean up sub-clauses */
681 foreach(lc, ((
BoolExpr *) rinfo->orclause)->args)
685 /* OR arguments should be ANDs or sub-RestrictInfos */
691 foreach(lc2, andargs)
709 * Remove any references to relid or sjinfo->ojrelid (if sjinfo != NULL)
710 * from the EquivalenceClass.
712 * Like remove_rel_from_restrictinfo, we don't worry about cleaning out
713 * any nullingrel bits in contained Vars and PHVs. (This might have to be
714 * improved sometime.) We do need to fix the EC and EM relid sets to ensure
715 * that implied join equalities will be generated at the appropriate join
720 int relid,
int subst)
724 /* Fix up the EC's overall relids */
731 * We don't expect any EC child members to exist at this point. Ensure
732 * that's the case, otherwise, we might be getting asked to do something
733 * this function hasn't been coded for.
738 * Fix up the member expressions. Any non-const member that ends with
739 * empty em_relids must be a Var or PHV of the removed relation. We don't
740 * need it anymore, so we can drop it.
760 /* Fix up the source clauses, in case we can re-use them later */
773 * Rather than expend code on fixing up any already-derived clauses, just
774 * drop them. (At this point, any such clauses would be base restriction
775 * clauses, which we'd not need anymore anyway.)
781 * Remove any occurrences of the target relid from a joinlist structure.
783 * It's easiest to build a whole new list structure, so we handle it that
784 * way. Efficiency is not a big deal here.
786 * *nremoved is incremented by the number of occurrences removed (there
787 * should be exactly one, but the caller checks that).
795 foreach(jl, joinlist)
806 result =
lappend(result, jlnode);
810 /* Recurse to handle subproblem */
815 /* Avoid including empty sub-lists in the result */
817 result =
lappend(result, sublist);
821 elog(
ERROR,
"unrecognized joinlist node type: %d",
831 * reduce_unique_semijoins
832 * Check for semijoins that can be simplified to plain inner joins
833 * because the inner relation is provably unique for the join clauses.
835 * Ideally this would happen during reduce_outer_joins, but we don't have
836 * enough information at that point.
838 * To perform the strength reduction when applicable, we need only delete
839 * the semijoin's SpecialJoinInfo from root->join_info_list. (We don't
840 * bother fixing the join type attributed to it in the query jointree,
841 * since that won't be consulted again.)
849 * Scan the join_info_list to find semijoins.
851 foreach(lc,
root->join_info_list)
860 * Must be a semijoin to a single baserel, else we aren't going to be
861 * able to do anything with it.
872 * Before we trouble to run generate_join_implied_equalities, make a
873 * quick check to eliminate cases in which we will surely be unable to
874 * prove uniqueness of the innerrel.
879 /* Compute the relid set for the join we are considering */
881 Assert(sjinfo->
ojrelid == 0);
/* SEMI joins don't have RT indexes */
884 * Since we're only considering a single-rel RHS, any join clauses it
885 * has must be clauses linking it to the semijoin's min_lefthand. We
886 * can also consider EC-derived join clauses.
896 /* Test whether the innerrel is unique for those clauses. */
902 /* OK, remove the SpecialJoinInfo from the list. */
909 * rel_supports_distinctness
910 * Could the relation possibly be proven distinct on some set of columns?
912 * This is effectively a pre-checking function for rel_is_distinct_for().
913 * It must return true if rel_is_distinct_for() could possibly return true
914 * with this rel, but it should not expend a lot of cycles. The idea is
915 * that callers can avoid doing possibly-expensive processing to compute
916 * rel_is_distinct_for()'s argument lists if the call could not possibly
922 /* We only know about baserels ... */
928 * For a plain relation, we only know how to prove uniqueness by
929 * reference to unique indexes. Make sure there's at least one
930 * suitable unique index. It must be immediately enforced, and not a
931 * partial index. (Keep these conditions in sync with
932 * relation_has_unique_index_for!)
940 if (
ind->unique &&
ind->immediate &&
ind->indpred ==
NIL)
948 /* Check if the subquery has any qualities that support distinctness */
952 /* We have no proof rules for any other rtekinds. */
957 * rel_is_distinct_for
958 * Does the relation return only distinct rows according to clause_list?
960 * clause_list is a list of join restriction clauses involving this rel and
961 * some other one. Return true if no two rows emitted by this rel could
962 * possibly join to the same row of the other rel.
964 * The caller must have already determined that each condition is a
965 * mergejoinable equality with an expression in this relation on one side, and
966 * an expression not involving this relation on the other. The transient
967 * outer_is_left flag is used to identify which side references this relation:
968 * left side if outer_is_left is false, right side if it is true.
970 * Note that the passed-in clause_list may be destructively modified! This
971 * is OK for current uses, because the clause_list is built by the caller for
972 * the sole purpose of passing to this function.
974 * (*extra_clauses) to be set to the right sides of baserestrictinfo clauses,
975 * looking like "x = const" if distinctness is derived from such clauses, not
976 * joininfo clauses. Pass NULL to the extra_clauses if this value is not
981 List **extra_clauses)
984 * We could skip a couple of tests here if we assume all callers checked
985 * rel_supports_distinctness first, but it doesn't seem worth taking any
993 * Examine the indexes to see if we have a matching unique index.
994 * relation_has_unique_index_for automatically adds any usable
995 * restriction clauses for the rel, so we needn't do that here.
1003 Query *subquery =
root->simple_rte_array[relid]->subquery;
1009 * Build the argument lists for query_is_distinct_for: a list of
1010 * output column numbers that the query needs to be distinct over, and
1011 * a list of equality operators that the output columns need to be
1012 * distinct according to.
1014 * (XXX we are not considering restriction clauses attached to the
1015 * subquery; is that worth doing?)
1017 foreach(l, clause_list)
1024 * Get the equality operator we need uniqueness according to.
1025 * (This might be a cross-type operator and thus not exactly the
1026 * same operator the subquery would consider; that's all right
1027 * since query_is_distinct_for can resolve such cases.) The
1028 * caller's mergejoinability test should have selected only
1033 /* caller identified the inner side for us */
1034 if (rinfo->outer_is_left)
1040 * We may ignore any RelabelType node above the operand. (There
1041 * won't be more than one, since eval_const_expressions() has been
1048 * If inner side isn't a Var referencing a subquery output column,
1049 * this clause doesn't help us.
1051 if (!var || !
IsA(var,
Var) ||
1067 * query_supports_distinctness - could the query possibly be proven distinct
1068 * on some set of output columns?
1070 * This is effectively a pre-checking function for query_is_distinct_for().
1071 * It must return true if query_is_distinct_for() could possibly return true
1072 * with this query, but it should not expend a lot of cycles. The idea is
1073 * that callers can avoid doing possibly-expensive processing to compute
1074 * query_is_distinct_for()'s argument lists if the call could not possibly
1080 /* SRFs break distinctness except with DISTINCT, see below */
1084 /* check for features we can prove distinctness with */
1097 * query_is_distinct_for - does query never return duplicates of the
1098 * specified columns?
1100 * query is a not-yet-planned subquery (in current usage, it's always from
1101 * a subquery RTE, which the planner avoids scribbling on).
1103 * colnos is an integer list of output column numbers (resno's). We are
1104 * interested in whether rows consisting of just these columns are certain
1105 * to be distinct. "Distinctness" is defined according to whether the
1106 * corresponding upper-level equality operators listed in opids would think
1107 * the values are distinct. (Note: the opids entries could be cross-type
1108 * operators, and thus not exactly the equality operators that the subquery
1109 * would use itself. We use equality_ops_are_compatible() to check
1110 * compatibility. That looks at opfamily membership for index AMs that have
1111 * declared that they support consistent equality semantics within an
1112 * opfamily, and so should give trustworthy answers for all operators that we
1113 * might need to deal with here.)
1124 * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
1125 * columns in the DISTINCT clause appear in colnos and operator semantics
1126 * match. This is true even if there are SRFs in the DISTINCT columns or
1127 * elsewhere in the tlist.
1140 break;
/* exit early if no match */
1142 if (l == NULL)
/* had matches for all? */
1147 * Otherwise, a set-returning function in the query's targetlist can
1148 * result in returning duplicate rows, despite any grouping that might
1149 * occur before tlist evaluation. (If all tlist SRFs are within GROUP BY
1150 * columns, it would be safe because they'd be expanded before grouping.
1151 * But it doesn't currently seem worth the effort to check for that.)
1153 if (query->hasTargetSRFs)
1157 * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
1158 * the grouped columns appear in colnos and operator semantics match.
1171 break;
/* exit early if no match */
1173 if (l == NULL)
/* had matches for all? */
1179 * If we have grouping sets with expressions, we probably don't have
1180 * uniqueness and analysis would be hard. Punt.
1186 * If we have no groupClause (therefore no grouping expressions), we
1187 * might have one or many empty grouping sets. If there's just one,
1188 * then we're returning only one row and are certainly unique. But
1189 * otherwise, we know we're certainly not unique.
1200 * If we have no GROUP BY, but do have aggregates or HAVING, then the
1201 * result is at most one row so it's surely unique, for any operators.
1208 * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
1221 /* We're good if all the nonjunk output columns are in colnos */
1229 continue;
/* ignore resjunk columns */
1231 /* non-resjunk columns should have grouping clauses */
1234 lg =
lnext(topop->groupClauses, lg);
1239 break;
/* exit early if no match */
1241 if (l == NULL)
/* had matches for all? */
1247 * XXX Are there any other cases in which we can easily see the result
1250 * If you do add more smarts to this function, be sure to update
1251 * query_supports_distinctness() to match.
1258 * distinct_col_search - subroutine for query_is_distinct_for
1260 * If colno is in colnos, return the corresponding element of opids,
1261 * else return InvalidOid. (Ordinarily colnos would not contain duplicates,
1262 * but if it does, we arbitrarily select the first match.)
1270 forboth(lc1, colnos, lc2, opids)
1280 * innerrel_is_unique
1281 * Check if the innerrel provably contains at most one tuple matching any
1282 * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1284 * We need an actual RelOptInfo for the innerrel, but it's sufficient to
1285 * identify the outerrel by its Relids. This asymmetry supports use of this
1286 * function before joinrels have been built. (The caller is expected to
1287 * also supply the joinrelids, just to save recalculating that.)
1289 * The proof must be made based only on clauses that will be "joinquals"
1290 * rather than "otherquals" at execution. For an inner join there's no
1291 * difference; but if the join is outer, we must ignore pushed-down quals,
1292 * as those will become "otherquals". Note that this means the answer might
1293 * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
1294 * answer without regard to that, callers must take care not to call this
1295 * with jointypes that would be classified differently by IS_OUTER_JOIN().
1297 * The actual proof is undertaken by is_innerrel_unique_for(); this function
1298 * is a frontend that is mainly concerned with caching the answers.
1299 * In particular, the force_cache argument allows overriding the internal
1300 * heuristic about whether to cache negative answers; it should be "true"
1301 * if making an inquiry that is not part of the normal bottom-up join search
1314 jointype, restrictlist, force_cache, NULL);
1318 * innerrel_is_unique_ext
1319 * Do the same as innerrel_is_unique(), but also set to (*extra_clauses)
1320 * additional clauses from a baserestrictinfo list used to prove the
1323 * A non-NULL extra_clauses indicates that we're checking for self-join and
1324 * correspondingly dealing with filtered clauses.
1334 List **extra_clauses)
1340 bool self_join = (extra_clauses != NULL);
1342 /* Certainly can't prove uniqueness when there are no joinclauses */
1343 if (restrictlist ==
NIL)
1347 * Make a quick check to eliminate cases in which we will surely be unable
1348 * to prove uniqueness of the innerrel.
1354 * Query the cache to see if we've managed to prove that innerrel is
1355 * unique for any subset of this outerrel. For non-self-join search, we
1356 * don't need an exact match, as extra outerrels can't make the innerrel
1357 * any less unique (or more formally, the restrictlist for a join to a
1358 * superset outerrel must be a superset of the conditions we successfully
1359 * used before). For self-join search, we require an exact match of
1360 * outerrels because we need extra clauses to be valid for our case. Also,
1361 * for self-join checking we've filtered the clauses list. Thus, we can
1362 * match only the result cached for a self-join search for another
1375 return true;
/* Success! */
1380 * Conversely, we may have already determined that this outerrel, or some
1381 * superset thereof, cannot prove this innerrel to be unique.
1391 /* No cached information, so try to make the proof. */
1393 jointype, restrictlist,
1394 self_join ? &outer_exprs : NULL))
1397 * Cache the positive result for future probes, being sure to keep it
1398 * in the planner_cxt even if we are working in GEQO.
1400 * Note: one might consider trying to isolate the minimal subset of
1401 * the outerrels that proved the innerrel unique. But it's not worth
1402 * the trouble, because the planner builds up joinrels incrementally
1403 * and so we'll see the minimally sufficient outerrels before any
1404 * supersets of them anyway.
1416 *extra_clauses = outer_exprs;
1417 return true;
/* Success! */
1422 * None of the join conditions for outerrel proved innerrel unique, so
1423 * we can safely reject this outerrel or any subset of it in future
1426 * However, in normal planning mode, caching this knowledge is totally
1427 * pointless; it won't be queried again, because we build up joinrels
1428 * from smaller to larger. It's only useful when using GEQO or
1429 * another planner extension that attempts planning multiple times.
1431 * Also, allow callers to override that heuristic and force caching;
1432 * that's useful for reduce_unique_semijoins, which calls here before
1433 * the normal join search starts.
1435 if (force_cache ||
root->assumeReplanning)
1449 * is_innerrel_unique_for
1450 * Check if the innerrel provably contains at most one tuple matching any
1451 * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1460 List **extra_clauses)
1466 * Search for mergejoinable clauses that constrain the inner rel against
1467 * the outer rel. If an operator is mergejoinable then it behaves like
1468 * equality for some btree opclass, so it's what we want. The
1469 * mergejoinability test also eliminates clauses containing volatile
1470 * functions, which we couldn't depend on.
1472 foreach(lc, restrictlist)
1477 * As noted above, if it's a pushed-down clause and we're at an outer
1478 * join, we can't use it.
1484 /* Ignore if it's not a mergejoinable clause */
1485 if (!restrictinfo->can_join ||
1486 restrictinfo->mergeopfamilies ==
NIL)
1487 continue;
/* not mergejoinable */
1490 * Check if the clause has the form "outer op inner" or "inner op
1491 * outer", and if so mark which side is inner.
1495 continue;
/* no good for these input relations */
1497 /* OK, add to the list */
1498 clause_list =
lappend(clause_list, restrictinfo);
1501 /* Let rel_is_distinct_for() do the hard work */
1506 * Update EC members to point to the remaining relation instead of the removed
1507 * one, removing duplicates.
1509 * Restriction clauses for base relations are already distributed to
1510 * the respective baserestrictinfo lists (see
1511 * generate_implied_equalities_for_column). The above code has already processed
1512 * this list and updated these clauses to reference the remaining
1513 * relation, so that we can skip them here based on their relids.
1515 * Likewise, we have already processed the join clauses that join the
1516 * removed relation to the remaining one.
1518 * Finally, there might be join clauses tying the removed relation to
1519 * some third relation. We can't just delete the source clauses and
1520 * regenerate them from the EC because the corresponding equality
1521 * operators might be missing (see the handling of ec_broken).
1522 * Therefore, we will update the references in the source clauses.
1524 * Derived clauses can be generated again, so it is simpler just to
1534 * We don't expect any EC child members to exist at this point. Ensure
1535 * that's the case, otherwise, we might be getting asked to do something
1536 * this function hasn't been coded for.
1542 bool is_redundant =
false;
1546 new_members =
lappend(new_members, em);
1551 em->em_jdomain->jd_relids =
adjust_relid_set(em->em_jdomain->jd_relids, from, to);
1553 /* We only process inner joins */
1559 if (!
equal(em->em_relids, other->em_relids))
1562 if (
equal(em->em_expr, other->em_expr))
1564 is_redundant =
true;
1570 new_members =
lappend(new_members, em);
1578 /* Update EC source expressions */
1581 bool is_redundant =
false;
1585 new_sources =
lappend(new_sources, rinfo);
1593 * After switching the clause to the remaining relation, check it for
1594 * redundancy with existing ones. We don't have to check for
1595 * redundancy with derived clauses, because we've just deleted them.
1599 if (!
equal(rinfo->clause_relids, other->clause_relids))
1602 if (
equal(rinfo->clause, other->clause))
1604 is_redundant =
true;
1610 new_sources =
lappend(new_sources, rinfo);
1619 * "Logically" compares two RestrictInfo's ignoring the 'rinfo_serial' field,
1620 * which makes almost every RestrictInfo unique. This type of comparison is
1621 * useful when removing duplicates while moving RestrictInfo's from removed
1622 * relation to remaining relation during self-join elimination.
1624 * XXX: In the future, we might remove the 'rinfo_serial' field completely and
1625 * get rid of this function.
1630 int saved_rinfo_serial =
a->rinfo_serial;
1633 a->rinfo_serial =
b->rinfo_serial;
1635 a->rinfo_serial = saved_rinfo_serial;
1641 * This function adds all non-redundant clauses to the keeping relation
1642 * during self-join elimination. That is a contradictory operation. On the
1643 * one hand, we reduce the length of the `restrict` lists, which can
1644 * impact planning or executing time. Additionally, we improve the
1645 * accuracy of cardinality estimation. On the other hand, it is one more
1646 * place that can make planning time much longer in specific cases. It
1647 * would have been better to avoid calling the equal() function here, but
1648 * it's the only way to detect duplicated inequality expressions.
1650 * (*keep_rinfo_list) is given by pointer because it might be altered by
1651 * distribute_restrictinfo_to_rels().
1655 List *rinfo_candidates,
1656 List **keep_rinfo_list,
1657 Index removed_relid)
1661 bool is_redundant =
false;
1667 if (!
bms_equal(src->clause_relids, rinfo->clause_relids))
1668 /* Can't compare trivially different clauses */
1672 (rinfo->parent_ec != NULL &&
1673 src->parent_ec == rinfo->parent_ec) ||
1676 is_redundant =
true;
1686 * A custom callback for ChangeVarNodesExtended() providing
1687 * Self-join elimination (SJE) related functionality
1689 * SJE needs to skip the RangeTblRef node
1690 * type. During SJE's last step, remove_rel_from_joinlist() removes
1691 * remaining RangeTblRefs with target relid. If ChangeVarNodes() replaces
1692 * the target relid before, remove_rel_from_joinlist() fails to identify
1693 * the nodes to delete.
1695 * SJE also needs to change the relids within RestrictInfo's.
1710 bool clause_relids_is_multiple =
1714 * Recurse down into clauses if the target relation is present in
1715 * clause_relids or required_relids. We must check required_relids
1716 * because the relation not present in clause_relids might still be
1717 * present somewhere in orclause.
1722 Relids new_clause_relids;
1732 * Incrementally adjust num_base_rels based on the change of
1733 * clause_relids, which could contain both base relids and
1734 * outer-join relids. This operation is legal until we remove
1740 rinfo->clause_relids = new_clause_relids;
1741 rinfo->left_relids =
1743 rinfo->right_relids =
1758 if (rinfo->mergeopfamilies &&
1760 clause_relids_is_multiple &&
1770 * For self-join elimination, changing varnos could transform
1771 * "t1.a = t2.a" into "t1.a = t1.a". That is always true as long
1772 * as "t1.a" is not null. We use qual() to check for such a case,
1773 * and then we replace the qual for a check for not null
1776 if (leftOp != NULL &&
equal(leftOp, rightOp))
1780 ntest->
arg = leftOp;
1782 ntest->argisrow =
false;
1785 rinfo->mergeopfamilies =
NIL;
1786 rinfo->left_em = NULL;
1787 rinfo->right_em = NULL;
1789 Assert(rinfo->orclause == NULL);
1798 * Remove a relation after we have proven that it participates only in an
1799 * unneeded unique self-join.
1801 * Replace any links in planner info structures.
1803 * Transfer join and restriction clauses from the removed relation to the
1804 * remaining one. We change the Vars of the clause to point to the
1805 * remaining relation instead of the removed one. The clauses that require
1806 * a subset of joinrelids become restriction clauses of the remaining
1807 * relation, and others remain join clauses. We append them to
1808 * baserestrictinfo and joininfo, respectively, trying not to introduce
1811 * We also have to process the 'joinclauses' list here, because it
1812 * contains EC-derived join clauses which must become filter clauses. It
1813 * is not enough to just correct the ECs because the EC-derived
1814 * restrictions are generated before join removal (see
1815 * generate_base_implied_equalities).
1817 * NOTE: Remember to keep the code in sync with PlannerInfo to be sure all
1818 * cached relids and relid bitmapsets can be correctly cleaned during the
1819 * self-join elimination procedure.
1836 * Replace the index of the removing table with the keeping one. The
1837 * technique of removing/distributing restrictinfo is used here to attach
1838 * just appeared (for keeping relation) join clauses and avoid adding
1839 * duplicates of those that already exist in the joininfo list.
1849 jinfo_candidates =
lappend(jinfo_candidates, rinfo);
1851 binfo_candidates =
lappend(binfo_candidates, rinfo);
1855 * Concatenate restrictlist to the list of base restrictions of the
1856 * removing table just to simplify the replacement procedure: all of them
1857 * weren't connected to any keeping relations and need to be added to some
1868 jinfo_candidates =
lappend(jinfo_candidates, rinfo);
1870 binfo_candidates =
lappend(binfo_candidates, rinfo);
1874 * Now, add all non-redundant clauses to the keeping relation.
1885 * Arrange equivalence classes, mentioned removing a table, with the
1886 * keeping one: varno of removing table should be replaced in members and
1887 * sources lists. Also, remove duplicated elements if this replacement
1888 * procedure created them.
1900 * Transfer the targetlist and attr_needed flags.
1913 for (
i = toKeep->
min_attr; i <= toKeep->max_attr;
i++)
1917 toRemove->attr_needed[attno] =
adjust_relid_set(toRemove->attr_needed[attno],
1919 toKeep->attr_needed[attno] =
bms_add_members(toKeep->attr_needed[attno],
1920 toRemove->attr_needed[attno]);
1924 * If the removed relation has a row mark, transfer it to the remaining
1927 * If both rels have row marks, just keep the one corresponding to the
1928 * remaining relation because we verified earlier that they have the same
1941 /* Shouldn't have inheritance children here. */
1949 * Replace varno in all the query structures, except nodes RangeTblRef
1950 * otherwise later remove_rel_from_joinlist will yield errors.
1955 /* Replace links in the planner info */
1958 /* At last, replace varno in root targetlist and HAVING clause */
1969 * There may be references to the rel in root->fkey_list, but if so,
1970 * match_foreign_keys_to_quals() will get rid of them.
1974 * Finally, remove the rel from the baserel array to prevent it from being
1975 * referenced again. (We can't do this earlier because
1976 * remove_join_clause_from_rels will touch it.)
1978 root->simple_rel_array[toRemove->
relid] = NULL;
1979 root->simple_rte_array[toRemove->
relid] = NULL;
1981 /* And nuke the RelOptInfo, just in case there's another access path. */
1986 * Now repeat construction of attr_needed bits coming from all other
1996 * split_selfjoin_quals
1997 * Processes 'joinquals' by building two lists: one containing the quals
1998 * where the columns/exprs are on either side of the join match and
1999 * another one containing the remaining quals.
2001 * 'joinquals' must only contain quals for a RTE_RELATION being joined to
2006 List **otherjoinquals,
int from,
int to)
2017 /* In general, clause looks like F(arg1) = G(arg2) */
2018 if (!rinfo->mergeopfamilies ||
2023 ojoinquals =
lappend(ojoinquals, rinfo);
2027 expr = (
OpExpr *) rinfo->clause;
2031 ojoinquals =
lappend(ojoinquals, rinfo);
2044 * Quite an expensive operation, narrowing the use case. For example,
2045 * when we have cast of the same var to different (but compatible)
2053 if (
equal(leftexpr, rightexpr))
2054 sjoinquals =
lappend(sjoinquals, rinfo);
2056 ojoinquals =
lappend(ojoinquals, rinfo);
2059 *selfjoinquals = sjoinquals;
2060 *otherjoinquals = ojoinquals;
2064 * Check for a case when uniqueness is at least partly derived from a
2065 * baserestrictinfo clause. In this case, we have a chance to return only
2066 * one row (if such clauses on both sides of SJ are equal) or nothing (if they
2078 bool matched =
false;
2082 /* Only filters like f(R.x1,...,R.xN) == expr we should consider. */
2096 * Compare these left and right sides with the corresponding sides of
2097 * the outer's filters. If no one is detected - return immediately.
2104 if (orinfo->mergeopfamilies ==
NIL)
2105 /* Don't consider clauses that aren't similar to 'F(X)=G(Y)' */
2115 if (
equal(iclause, oclause) &&
equal(c1, c2))
2130 * Find and remove unique self-joins in a group of base relations that have
2133 * Returns a set of relids that were removed.
2139 int k;
/* Index of kept relation */
2140 int r = -1;
/* Index of removed relation */
2150 Relids joinrelids = NULL;
2153 List *selfjoinquals;
2154 List *otherjoinquals;
2156 bool jinfo_check =
true;
2161 /* A sanity check: the relations have the same Oid. */
2163 root->simple_rte_array[r]->relid);
2166 * It is impossible to eliminate the join of two relations if they
2167 * belong to different rules of order. Otherwise, the planner
2168 * can't find any variants of the correct query plan.
2170 foreach(lc,
root->join_info_list)
2179 jinfo_check =
false;
2187 * Check Row Marks equivalence. We can't remove the join if the
2188 * relations have row marks of different strength (e.g., one is
2189 * locked FOR UPDATE, and another just has ROW_MARK_REFERENCE for
2190 * EvalPlanQual rechecking).
2192 foreach(lc,
root->rowMarks)
2196 if (rowMark->
rti == r)
2201 else if (rowMark->
rti == k)
2214 * We only deal with base rels here, so their relids bitset
2215 * contains only one member -- their relid.
2221 * PHVs should not impose any constraints on removing self-joins.
2225 * At this stage, joininfo lists of inner and outer can contain
2226 * only clauses required for a superior outer join that can't
2227 * influence this optimization. So, we can avoid to call the
2228 * build_joinrel_restrictlist() routine.
2233 if (restrictlist ==
NIL)
2237 * Process restrictlist to separate the self-join quals from the
2238 * other quals. e.g., "x = x" goes to selfjoinquals and "a = b" to
2248 * To enable SJE for the only degenerate case without any self
2249 * join clauses at all, add baserestrictinfo to this list. The
2250 * degenerate case works only if both sides have the same clause.
2251 * So doesn't matter which side to add.
2256 * Determine if the rrel can duplicate outer rows. We must bypass
2257 * the unique rel cache here since we're possibly using a subset
2258 * of join quals. We can use 'force_cache' == true when all join
2259 * quals are self-join quals. Otherwise, we could end up putting
2260 * false negatives in the cache.
2269 * 'uclauses' is the copy of outer->baserestrictinfo that are
2270 * associated with an index. We proved by matching selfjoinquals
2271 * to a unique index that the outer relation has at most one
2272 * matching row for each inner row. Sometimes that is not enough.
2273 * e.g. "WHERE s1.b = s2.b AND s1.a = 1 AND s2.a = 2" when the
2274 * unique index is (a,b). Having non-empty uclauses, we must
2275 * validate that the inner baserestrictinfo contains the same
2276 * expressions, or we won't match the same row on each side of the
2283 * Remove rrel ReloptInfo from the planner structures and the
2284 * corresponding row mark.
2290 /* We have removed the outer relation, try the next one. */
2299 * Gather indexes of base relations from the joinlist and try to eliminate self
2312 /* Collect indexes of base relations of the join tree */
2313 foreach(jl, joinlist)
2323 * We only consider ordinary relations as candidates to be
2324 * removed, and these relations should not have TABLESAMPLE
2325 * clauses specified. Removing a relation with TABLESAMPLE clause
2326 * could potentially change the syntax of the query. Because of
2327 * UPDATE/DELETE EPQ mechanism, currently Query->resultRelation or
2328 * Query->mergeTargetRelation associated rel cannot be eliminated.
2331 rte->relkind == RELKIND_RELATION &&
2333 varno !=
root->parse->resultRelation &&
2334 varno !=
root->parse->mergeTargetRelation)
2342 /* Recursively go inside the sub-joinlist */
2347 elog(
ERROR,
"unrecognized joinlist node type: %d",
2353 /* Need at least two relations for the join */
2358 * In order to find relations with the same oid we first build an array of
2359 * candidates and then sort it by oid.
2368 candidates[
j].
reloid =
root->simple_rte_array[
i]->relid;
2376 * Iteratively form a group of relation indexes with the same oid and
2377 * launch the routine that detects self-joins in this group and removes
2378 * excessive range table entries.
2380 * At the end of the iteration, exclude the group from the overall relids
2381 * list. So each next iteration of the cycle will involve less and less
2385 for (
j = 1;
j < numRels + 1;
j++)
2387 if (
j == numRels || candidates[
j].reloid != candidates[
i].reloid)
2391 /* Create a group of relation indexes with the same oid */
2403 * Try to remove self-joins from a group of identical entries.
2404 * Make the next attempt iteratively - if something is deleted
2405 * from a group, changes in clauses and equivalence classes
2406 * can give us a chance to find more candidates.
2421 /* Single relation, just remove it from the set */
2434 * Compare self-join candidates by their oids.
2449 * Find and remove useless self joins.
2451 * Search for joins where a relation is joined to itself. If the join clause
2452 * for each tuple from one side of the join is proven to match the same
2453 * physical row (or nothing) on the other side, that self-join can be
2454 * eliminated from the query. Suitable join clauses are assumed to be in the
2455 * form of X = X, and can be replaced with NOT NULL clauses.
2457 * For the sake of simplicity, we don't apply this optimization to special
2458 * joins. Here is a list of what we could do in some particular cases:
2459 * 'a a1 semi join a a2': is reduced to inner by reduce_unique_semijoins,
2460 * and then removed normally.
2461 * 'a a1 anti join a a2': could simplify to a scan with 'outer quals AND
2462 * (IS NULL on join columns OR NOT inner quals)'.
2463 * 'a a1 left join a a2': could simplify to a scan like inner but without
2464 * NOT NULL conditions on join columns.
2465 * 'a a1 left join (a a2 join b)': can't simplify this, because join to b
2466 * can both remove rows and introduce duplicates.
2468 * To search for removable joins, we order all the relations on their Oid,
2469 * go over each set with the same Oid, and consider each pair of relations
2472 * To remove the join, we mark one of the participating relations as dead
2473 * and rewrite all references to it to point to the remaining relation.
2474 * This includes modifying RestrictInfos, EquivalenceClasses, and
2475 * EquivalenceMembers. We also have to modify the row marks. The join clauses
2476 * of the removed relation become either restriction or join clauses, based on
2477 * whether they reference any relations not participating in the removed join.
2479 * 'joinlist' is the top-level joinlist of the query. If it has any
2480 * references to the removed relations, we update them to point to the
2494 * Merge pairs of relations participated in self-join. Remove unnecessary
2495 * range table entries.
2501 /* At the end, remove orphaned relation links */
2508 elog(
ERROR,
"failed to find relation %d in joinlist", relid);
static int self_join_candidates_cmp(const void *a, const void *b)
static bool match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses, Index relid)
static bool replace_relid_callback(Node *node, ChangeVarNodes_context *context)
static void split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals, List **otherjoinquals, int from, int to)
static void add_non_redundant_clauses(PlannerInfo *root, List *rinfo_candidates, List **keep_rinfo_list, Index removed_relid)
static void remove_rel_from_query(PlannerInfo *root, RelOptInfo *rel, int subst, SpecialJoinInfo *sjinfo, Relids joinrelids)
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
static List * remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
static void remove_leftjoinrel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
bool query_is_distinct_for(Query *query, List *colnos, List *opids)
static Relids remove_self_joins_one_group(PlannerInfo *root, Relids relids)
List * remove_useless_joins(PlannerInfo *root, List *joinlist)
static Oid distinct_col_search(int colno, List *colnos, List *opids)
static bool is_innerrel_unique_for(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, List **extra_clauses)
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list, List **extra_clauses)
bool innerrel_is_unique_ext(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache, List **extra_clauses)
static void remove_rel_from_eclass(EquivalenceClass *ec, SpecialJoinInfo *sjinfo, int relid, int subst)
List * remove_useless_self_joins(PlannerInfo *root, List *joinlist)
bool query_supports_distinctness(Query *query)
static void update_eclasses(EquivalenceClass *ec, int from, int to)
static bool restrict_infos_logically_equal(RestrictInfo *a, RestrictInfo *b)
static Relids remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
void reduce_unique_semijoins(PlannerInfo *root)
bool enable_self_join_elimination
static void remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
static void remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark, RelOptInfo *toKeep, RelOptInfo *toRemove, List *restrictlist)
Bitmapset * bms_difference(const Bitmapset *a, const Bitmapset *b)
Bitmapset * bms_make_singleton(int x)
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
int bms_next_member(const Bitmapset *a, int prevbit)
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Bitmapset * bms_del_member(Bitmapset *a, int x)
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
int bms_singleton_member(const Bitmapset *a)
void bms_free(Bitmapset *a)
int bms_num_members(const Bitmapset *a)
bool bms_is_member(int x, const Bitmapset *a)
Bitmapset * bms_add_member(Bitmapset *a, int x)
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
BMS_Membership bms_membership(const Bitmapset *a)
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Bitmapset * bms_copy(const Bitmapset *a)
#define OidIsValid(objectId)
bool equal(const void *a, const void *b)
void rebuild_eclass_attr_needed(PlannerInfo *root)
void ec_clear_derived_clauses(EquivalenceClass *ec)
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Assert(PointerIsAligned(start, uint64))
bool relation_has_unique_index_for(PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List **extra_clauses)
void rebuild_lateral_attr_needed(PlannerInfo *root)
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
void rebuild_joinclause_attr_needed(PlannerInfo *root)
if(TABLE==NULL||TABLE_index==NULL)
void remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
List * list_delete_ptr(List *list, void *datum)
List * lappend(List *list, void *datum)
List * list_concat(List *list1, const List *list2)
List * list_delete_cell(List *list, ListCell *cell)
List * list_copy(const List *oldlist)
List * lappend_int(List *list, int datum)
List * lappend_oid(List *list, Oid datum)
void list_free(List *list)
bool list_member(const List *list, const void *datum)
bool equality_ops_are_compatible(Oid opno1, Oid opno2)
void pfree(void *pointer)
static bool is_andclause(const void *clause)
static bool is_orclause(const void *clause)
static Node * get_rightop(const void *clause)
static bool is_opclause(const void *clause)
static Node * get_leftop(const void *clause)
#define IsA(nodeptr, _type_)
#define IS_OUTER_JOIN(jointype)
#define castNode(_type_, nodeptr)
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
#define lfirst_node(type, lc)
static int list_length(const List *l)
#define forboth(cell1, list1, cell2, list2)
#define foreach_delete_current(lst, var_or_cell)
static void * list_nth(const List *list, int n)
#define foreach_node(type, var, lst)
static ListCell * list_head(const List *l)
static ListCell * lnext(const List *l, const ListCell *c)
void rebuild_placeholder_attr_needed(PlannerInfo *root)
#define qsort(a, b, c, d)
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
bool ChangeVarNodesWalkExpression(Node *node, ChangeVarNodes_context *context)
Relids adjust_relid_set(Relids relids, int oldrelid, int newrelid)
void ChangeVarNodesExtended(Node *node, int rt_index, int new_index, int sublevels_up, ChangeVarNodes_callback callback)
NullTestType nulltesttype
struct TableSampleClause * tablesample
struct PathTarget * reltarget
List * non_unique_for_rels
Bitmapset * eclass_indexes
Relids incompatible_relids
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Relids pull_varnos(PlannerInfo *root, Node *node)