/*------------------------------------------------------------------------- * * restrictinfo.c * RestrictInfo node manipulation routines. * * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION * src/backend/optimizer/util/restrictinfo.c * *------------------------------------------------------------------------- */ #include "postgres.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/optimizer.h" #include "optimizer/restrictinfo.h" static Expr *make_sub_restrictinfos(PlannerInfo *root, Expr *clause, bool is_pushed_down, bool has_clone, bool is_clone, bool pseudoconstant, Index security_level, Relids required_relids, Relids incompatible_relids, Relids outer_relids); /* * make_restrictinfo * * Build a RestrictInfo node containing the given subexpression. * * The is_pushed_down, has_clone, is_clone, and pseudoconstant flags for the * RestrictInfo must be supplied by the caller, as well as the correct values * for security_level, incompatible_relids, and outer_relids. * required_relids can be NULL, in which case it defaults to the actual clause * contents (i.e., clause_relids). * * We initialize fields that depend only on the given subexpression, leaving * others that depend on context (or may never be needed at all) to be filled * later. */ RestrictInfo * make_restrictinfo(PlannerInfo *root, Expr *clause, bool is_pushed_down, bool has_clone, bool is_clone, bool pseudoconstant, Index security_level, Relids required_relids, Relids incompatible_relids, Relids outer_relids) { /* * If it's an OR clause, build a modified copy with RestrictInfos inserted * above each subclause of the top-level AND/OR structure. */ if (is_orclause(clause)) return (RestrictInfo *) make_sub_restrictinfos(root, clause, is_pushed_down, has_clone, is_clone, pseudoconstant, security_level, required_relids, incompatible_relids, outer_relids); /* Shouldn't be an AND clause, else AND/OR flattening messed up */ Assert(!is_andclause(clause)); return make_plain_restrictinfo(root, clause, NULL, is_pushed_down, has_clone, is_clone, pseudoconstant, security_level, required_relids, incompatible_relids, outer_relids); } /* * make_plain_restrictinfo * * Common code for the main entry points and the recursive cases. Also, * useful while constructing RestrictInfos above OR clause, which already has * RestrictInfos above its subclauses. */ RestrictInfo * make_plain_restrictinfo(PlannerInfo *root, Expr *clause, Expr *orclause, bool is_pushed_down, bool has_clone, bool is_clone, bool pseudoconstant, Index security_level, Relids required_relids, Relids incompatible_relids, Relids outer_relids) { RestrictInfo *restrictinfo = makeNode(RestrictInfo); Relids baserels; restrictinfo->clause = clause; restrictinfo->orclause = orclause; restrictinfo->is_pushed_down = is_pushed_down; restrictinfo->pseudoconstant = pseudoconstant; restrictinfo->has_clone = has_clone; restrictinfo->is_clone = is_clone; restrictinfo->can_join = false; /* may get set below */ restrictinfo->security_level = security_level; restrictinfo->incompatible_relids = incompatible_relids; restrictinfo->outer_relids = outer_relids; /* * If it's potentially delayable by lower-level security quals, figure out * whether it's leakproof. We can skip testing this for level-zero quals, * since they would never get delayed on security grounds anyway. */ if (security_level > 0) restrictinfo->leakproof = !contain_leaked_vars((Node *) clause); else restrictinfo->leakproof = false; /* really, "don't know" */ /* * Mark volatility as unknown. The contain_volatile_functions function * will determine if there are any volatile functions when called for the * first time with this RestrictInfo. */ restrictinfo->has_volatile = VOLATILITY_UNKNOWN; /* * If it's a binary opclause, set up left/right relids info. In any case * set up the total clause relids info. */ if (is_opclause(clause) && list_length(((OpExpr *) clause)->args) == 2) { restrictinfo->left_relids = pull_varnos(root, get_leftop(clause)); restrictinfo->right_relids = pull_varnos(root, get_rightop(clause)); restrictinfo->clause_relids = bms_union(restrictinfo->left_relids, restrictinfo->right_relids); /* * Does it look like a normal join clause, i.e., a binary operator * relating expressions that come from distinct relations? If so we * might be able to use it in a join algorithm. Note that this is a * purely syntactic test that is made regardless of context. */ if (!bms_is_empty(restrictinfo->left_relids) && !bms_is_empty(restrictinfo->right_relids) && !bms_overlap(restrictinfo->left_relids, restrictinfo->right_relids)) { restrictinfo->can_join = true; /* pseudoconstant should certainly not be true */ Assert(!restrictinfo->pseudoconstant); } } else { /* Not a binary opclause, so mark left/right relid sets as empty */ restrictinfo->left_relids = NULL; restrictinfo->right_relids = NULL; /* and get the total relid set the hard way */ restrictinfo->clause_relids = pull_varnos(root, (Node *) clause); } /* required_relids defaults to clause_relids */ if (required_relids != NULL) restrictinfo->required_relids = required_relids; else restrictinfo->required_relids = restrictinfo->clause_relids; /* * Count the number of base rels appearing in clause_relids. To do this, * we just delete rels mentioned in root->outer_join_rels and count the * survivors. Because we are called during deconstruct_jointree which is * the same tree walk that populates outer_join_rels, this is a little bit * unsafe-looking; but it should be fine because the recursion in * deconstruct_jointree should already have visited any outer join that * could be mentioned in this clause. */ baserels = bms_difference(restrictinfo->clause_relids, root->outer_join_rels); restrictinfo->num_base_rels = bms_num_members(baserels); bms_free(baserels); /* * Label this RestrictInfo with a fresh serial number. */ restrictinfo->rinfo_serial = ++(root->last_rinfo_serial); /* * Fill in all the cacheable fields with "not yet set" markers. None of * these will be computed until/unless needed. Note in particular that we * don't mark a binary opclause as mergejoinable or hashjoinable here; * that happens only if it appears in the right context (top level of a * joinclause list). */ restrictinfo->parent_ec = NULL; restrictinfo->eval_cost.startup = -1; restrictinfo->norm_selec = -1; restrictinfo->outer_selec = -1; restrictinfo->mergeopfamilies = NIL; restrictinfo->left_ec = NULL; restrictinfo->right_ec = NULL; restrictinfo->left_em = NULL; restrictinfo->right_em = NULL; restrictinfo->scansel_cache = NIL; restrictinfo->outer_is_left = false; restrictinfo->hashjoinoperator = InvalidOid; restrictinfo->left_bucketsize = -1; restrictinfo->right_bucketsize = -1; restrictinfo->left_mcvfreq = -1; restrictinfo->right_mcvfreq = -1; restrictinfo->left_hasheqoperator = InvalidOid; restrictinfo->right_hasheqoperator = InvalidOid; return restrictinfo; } /* * Recursively insert sub-RestrictInfo nodes into a boolean expression. * * We put RestrictInfos above simple (non-AND/OR) clauses and above * sub-OR clauses, but not above sub-AND clauses, because there's no need. * This may seem odd but it is closely related to the fact that we use * implicit-AND lists at top level of RestrictInfo lists. Only ORs and * simple clauses are valid RestrictInfos. * * The same is_pushed_down, has_clone, is_clone, and pseudoconstant flag * values can be applied to all RestrictInfo nodes in the result. Likewise * for security_level, incompatible_relids, and outer_relids. * * The given required_relids are attached to our top-level output, * but any OR-clause constituents are allowed to default to just the * contained rels. */ static Expr * make_sub_restrictinfos(PlannerInfo *root, Expr *clause, bool is_pushed_down, bool has_clone, bool is_clone, bool pseudoconstant, Index security_level, Relids required_relids, Relids incompatible_relids, Relids outer_relids) { if (is_orclause(clause)) { List *orlist = NIL; ListCell *temp; foreach(temp, ((BoolExpr *) clause)->args) orlist = lappend(orlist, make_sub_restrictinfos(root, lfirst(temp), is_pushed_down, has_clone, is_clone, pseudoconstant, security_level, NULL, incompatible_relids, outer_relids)); return (Expr *) make_plain_restrictinfo(root, clause, make_orclause(orlist), is_pushed_down, has_clone, is_clone, pseudoconstant, security_level, required_relids, incompatible_relids, outer_relids); } else if (is_andclause(clause)) { List *andlist = NIL; ListCell *temp; foreach(temp, ((BoolExpr *) clause)->args) andlist = lappend(andlist, make_sub_restrictinfos(root, lfirst(temp), is_pushed_down, has_clone, is_clone, pseudoconstant, security_level, required_relids, incompatible_relids, outer_relids)); return make_andclause(andlist); } else return (Expr *) make_plain_restrictinfo(root, clause, NULL, is_pushed_down, has_clone, is_clone, pseudoconstant, security_level, required_relids, incompatible_relids, outer_relids); } /* * commute_restrictinfo * * Given a RestrictInfo containing a binary opclause, produce a RestrictInfo * representing the commutation of that clause. The caller must pass the * OID of the commutator operator (which it's presumably looked up, else * it would not know this is valid). * * Beware that the result shares sub-structure with the given RestrictInfo. * That's okay for the intended usage with derived index quals, but might * be hazardous if the source is subject to change. Also notice that we * assume without checking that the commutator op is a member of the same * btree and hash opclasses as the original op. */ RestrictInfo * commute_restrictinfo(RestrictInfo *rinfo, Oid comm_op) { RestrictInfo *result; OpExpr *newclause; OpExpr *clause = castNode(OpExpr, rinfo->clause); Assert(list_length(clause->args) == 2); /* flat-copy all the fields of clause ... */ newclause = makeNode(OpExpr); memcpy(newclause, clause, sizeof(OpExpr)); /* ... and adjust those we need to change to commute it */ newclause->opno = comm_op; newclause->opfuncid = InvalidOid; newclause->args = list_make2(lsecond(clause->args), linitial(clause->args)); /* likewise, flat-copy all the fields of rinfo ... */ result = makeNode(RestrictInfo); memcpy(result, rinfo, sizeof(RestrictInfo)); /* * ... and adjust those we need to change. Note in particular that we can * preserve any cached selectivity or cost estimates, since those ought to * be the same for the new clause. Likewise we can keep the source's * parent_ec. It's also important that we keep the same rinfo_serial. */ result->clause = (Expr *) newclause; result->left_relids = rinfo->right_relids; result->right_relids = rinfo->left_relids; Assert(result->orclause == NULL); result->left_ec = rinfo->right_ec; result->right_ec = rinfo->left_ec; result->left_em = rinfo->right_em; result->right_em = rinfo->left_em; result->scansel_cache = NIL; /* not worth updating this */ if (rinfo->hashjoinoperator == clause->opno) result->hashjoinoperator = comm_op; else result->hashjoinoperator = InvalidOid; result->left_bucketsize = rinfo->right_bucketsize; result->right_bucketsize = rinfo->left_bucketsize; result->left_mcvfreq = rinfo->right_mcvfreq; result->right_mcvfreq = rinfo->left_mcvfreq; result->left_hasheqoperator = InvalidOid; result->right_hasheqoperator = InvalidOid; return result; } /* * restriction_is_or_clause * * Returns t iff the restrictinfo node contains an 'or' clause. */ bool restriction_is_or_clause(RestrictInfo *restrictinfo) { if (restrictinfo->orclause != NULL) return true; else return false; } /* * restriction_is_securely_promotable * * Returns true if it's okay to evaluate this clause "early", that is before * other restriction clauses attached to the specified relation. */ bool restriction_is_securely_promotable(RestrictInfo *restrictinfo, RelOptInfo *rel) { /* * It's okay if there are no baserestrictinfo clauses for the rel that * would need to go before this one, *or* if this one is leakproof. */ if (restrictinfo->security_level <= rel->baserestrict_min_security || restrictinfo->leakproof) return true; else return false; } /* * Detect whether a RestrictInfo's clause is constant TRUE (note that it's * surely of type boolean). No such WHERE clause could survive qual * canonicalization, but equivclass.c may generate such RestrictInfos for * reasons discussed therein. We should drop them again when creating * the finished plan, which is handled by the next few functions. */ static inline bool rinfo_is_constant_true(RestrictInfo *rinfo) { return IsA(rinfo->clause, Const) && !((Const *) rinfo->clause)->constisnull && DatumGetBool(((Const *) rinfo->clause)->constvalue); } /* * get_actual_clauses * * Returns a list containing the bare clauses from 'restrictinfo_list'. * * This is only to be used in cases where none of the RestrictInfos can * be pseudoconstant clauses (for instance, it's OK on indexqual lists). */ List * get_actual_clauses(List *restrictinfo_list) { List *result = NIL; ListCell *l; foreach(l, restrictinfo_list) { RestrictInfo *rinfo = lfirst_node(RestrictInfo, l); Assert(!rinfo->pseudoconstant); Assert(!rinfo_is_constant_true(rinfo)); result = lappend(result, rinfo->clause); } return result; } /* * extract_actual_clauses * * Extract bare clauses from 'restrictinfo_list', returning either the * regular ones or the pseudoconstant ones per 'pseudoconstant'. * Constant-TRUE clauses are dropped in any case. */ List * extract_actual_clauses(List *restrictinfo_list, bool pseudoconstant) { List *result = NIL; ListCell *l; foreach(l, restrictinfo_list) { RestrictInfo *rinfo = lfirst_node(RestrictInfo, l); if (rinfo->pseudoconstant == pseudoconstant && !rinfo_is_constant_true(rinfo)) result = lappend(result, rinfo->clause); } return result; } /* * extract_actual_join_clauses * * Extract bare clauses from 'restrictinfo_list', separating those that * semantically match the join level from those that were pushed down. * Pseudoconstant and constant-TRUE clauses are excluded from the results. * * This is only used at outer joins, since for plain joins we don't care * about pushed-down-ness. */ void extract_actual_join_clauses(List *restrictinfo_list, Relids joinrelids, List **joinquals, List **otherquals) { ListCell *l; *joinquals = NIL; *otherquals = NIL; foreach(l, restrictinfo_list) { RestrictInfo *rinfo = lfirst_node(RestrictInfo, l); if (RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)) { if (!rinfo->pseudoconstant && !rinfo_is_constant_true(rinfo)) *otherquals = lappend(*otherquals, rinfo->clause); } else { /* joinquals shouldn't have been marked pseudoconstant */ Assert(!rinfo->pseudoconstant); if (!rinfo_is_constant_true(rinfo)) *joinquals = lappend(*joinquals, rinfo->clause); } } } /* * join_clause_is_movable_to * Test whether a join clause is a safe candidate for parameterization * of a scan on the specified base relation. * * A movable join clause is one that can safely be evaluated at a rel below * its normal semantic level (ie, its required_relids), if the values of * variables that it would need from other rels are provided. * * We insist that the clause actually reference the target relation; this * prevents undesirable movement of degenerate join clauses, and ensures * that there is a unique place that a clause can be moved down to. * * We cannot move an outer-join clause into the non-nullable side of its * outer join, as that would change the results (rows would be suppressed * rather than being null-extended). * * Also there must not be an outer join below the clause that would null the * Vars coming from the target relation. Otherwise the clause might give * results different from what it would give at its normal semantic level. * * Also, the join clause must not use any relations that have LATERAL * references to the target relation, since we could not put such rels on * the outer side of a nestloop with the target relation. * * Also, we reject is_clone versions of outer-join clauses. This has the * effect of preventing us from generating variant parameterized paths * that differ only in which outer joins null the parameterization rel(s). * Generating one path from the minimally-parameterized has_clone version * is sufficient. */ bool join_clause_is_movable_to(RestrictInfo *rinfo, RelOptInfo *baserel) { /* Clause must physically reference target rel */ if (!bms_is_member(baserel->relid, rinfo->clause_relids)) return false; /* Cannot move an outer-join clause into the join's outer side */ if (bms_is_member(baserel->relid, rinfo->outer_relids)) return false; /* * Target rel's Vars must not be nulled by any outer join. We can check * this without groveling through the individual Vars by seeing whether * clause_relids (which includes all such Vars' varnullingrels) includes * any outer join that can null the target rel. You might object that * this could reject the clause on the basis of an OJ relid that came from * some other rel's Var. However, that would still mean that the clause * came from above that outer join and shouldn't be pushed down; so there * should be no false positives. */ if (bms_overlap(rinfo->clause_relids, baserel->nulling_relids)) return false; /* Clause must not use any rels with LATERAL references to this rel */ if (bms_overlap(baserel->lateral_referencers, rinfo->clause_relids)) return false; /* Ignore clones, too */ if (rinfo->is_clone) return false; return true; } /* * join_clause_is_movable_into * Test whether a join clause is movable and can be evaluated within * the current join context. * * currentrelids: the relids of the proposed evaluation location * current_and_outer: the union of currentrelids and the required_outer * relids (parameterization's outer relations) * * The API would be a bit clearer if we passed the current relids and the * outer relids separately and did bms_union internally; but since most * callers need to apply this function to multiple clauses, we make the * caller perform the union. * * Obviously, the clause must only refer to Vars available from the current * relation plus the outer rels. We also check that it does reference at * least one current Var, ensuring that the clause will be pushed down to * a unique place in a parameterized join tree. And we check that we're * not pushing the clause into its outer-join outer side. * * We used to need to check that we're not pushing the clause into a lower * outer join's inner side. However, now that clause_relids includes * references to potentially-nulling outer joins, the other tests handle that * concern. If the clause references any Var coming from the inside of a * lower outer join, its clause_relids will mention that outer join, causing * the evaluability check to fail; while if it references no such Vars, the * references-a-target-rel check will fail. * * There's no check here equivalent to join_clause_is_movable_to's test on * lateral_referencers. We assume the caller wouldn't be inquiring unless * it'd verified that the proposed outer rels don't have lateral references * to the current rel(s). (If we are considering join paths with the outer * rels on the outside and the current rels on the inside, then this should * have been checked at the outset of such consideration; see join_is_legal * and the path parameterization checks in joinpath.c.) On the other hand, * in join_clause_is_movable_to we are asking whether the clause could be * moved for some valid set of outer rels, so we don't have the benefit of * relying on prior checks for lateral-reference validity. * * Likewise, we don't check is_clone here: rejecting the inappropriate * variants of a cloned clause must be handled upstream. * * Note: if this returns true, it means that the clause could be moved to * this join relation, but that doesn't mean that this is the lowest join * it could be moved to. Caller may need to make additional calls to verify * that this doesn't succeed on either of the inputs of a proposed join. * * Note: get_joinrel_parampathinfo depends on the fact that if * current_and_outer is NULL, this function will always return false * (since one or the other of the first two tests must fail). */ bool join_clause_is_movable_into(RestrictInfo *rinfo, Relids currentrelids, Relids current_and_outer) { /* Clause must be evaluable given available context */ if (!bms_is_subset(rinfo->clause_relids, current_and_outer)) return false; /* Clause must physically reference at least one target rel */ if (!bms_overlap(currentrelids, rinfo->clause_relids)) return false; /* Cannot move an outer-join clause into the join's outer side */ if (bms_overlap(currentrelids, rinfo->outer_relids)) return false; return true; }