#include "postgres.h"
#include <limits.h>
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/appendinfo.h"
#include "optimizer/clauses.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/restrictinfo.h"
#include "utils/lsyscache.h"

Include dependency graph for equivclass.c:

Functions
static EquivalenceMember *	add_eq_member (EquivalenceClass ec, Expr expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype)

static void	generate_base_implied_equalities_const (PlannerInfo root, EquivalenceClass ec)

static void	generate_base_implied_equalities_no_const (PlannerInfo root, EquivalenceClass ec)

static void	generate_base_implied_equalities_broken (PlannerInfo root, EquivalenceClass ec)

static List *	generate_join_implied_equalities_normal (PlannerInfo root, EquivalenceClass ec, Relids join_relids, Relids outer_relids, Relids inner_relids)

static List *	generate_join_implied_equalities_broken (PlannerInfo root, EquivalenceClass ec, Relids nominal_join_relids, Relids outer_relids, Relids nominal_inner_relids, RelOptInfo *inner_rel)

static Oid	select_equality_operator (EquivalenceClass *ec, Oid lefttype, Oid righttype)

static RestrictInfo *	create_join_clause (PlannerInfo root, EquivalenceClass ec, Oid opno, EquivalenceMember leftem, EquivalenceMember rightem, EquivalenceClass *parent_ec)

static bool	reconsider_outer_join_clause (PlannerInfo root, RestrictInfo rinfo, bool outer_on_left)

static bool	reconsider_full_join_clause (PlannerInfo root, RestrictInfo rinfo)

static Bitmapset *	get_eclass_indexes_for_relids (PlannerInfo *root, Relids relids)

static Bitmapset *	get_common_eclass_indexes (PlannerInfo *root, Relids relids1, Relids relids2)

bool	process_equivalence (PlannerInfo root, RestrictInfo *p_restrictinfo, bool below_outer_join)

Expr *	canonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)

EquivalenceClass *	get_eclass_for_sort_expr (PlannerInfo root, Expr expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)

void	generate_base_implied_equalities (PlannerInfo *root)

List *	generate_join_implied_equalities (PlannerInfo root, Relids join_relids, Relids outer_relids, RelOptInfo inner_rel)

List *	generate_join_implied_equalities_for_ecs (PlannerInfo root, List eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)

void	reconsider_outer_join_clauses (PlannerInfo *root)

bool	exprs_known_equal (PlannerInfo root, Node item1, Node *item2)

EquivalenceClass *	match_eclasses_to_foreign_key_col (PlannerInfo root, ForeignKeyOptInfo fkinfo, int colno)

void	add_child_rel_equivalences (PlannerInfo root, AppendRelInfo appinfo, RelOptInfo parent_rel, RelOptInfo child_rel)

List *	generate_implied_equalities_for_column (PlannerInfo root, RelOptInfo rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)

bool	have_relevant_eclass_joinclause (PlannerInfo root, RelOptInfo rel1, RelOptInfo *rel2)

bool	has_relevant_eclass_joinclause (PlannerInfo root, RelOptInfo rel1)

bool	eclass_useful_for_merging (PlannerInfo root, EquivalenceClass eclass, RelOptInfo *rel)

bool	is_redundant_derived_clause (RestrictInfo rinfo, List clauselist)

bool	is_redundant_with_indexclauses (RestrictInfo rinfo, List indexclauses)

Function Documentation

◆ add_child_rel_equivalences()

void add_child_rel_equivalences	(	PlannerInfo *	root,
		AppendRelInfo *	appinfo,
		RelOptInfo *	parent_rel,
		RelOptInfo *	child_rel
	)

Definition at line 2222 of file equivclass.c.

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert, bms_add_member(), bms_add_members(), bms_difference(), bms_is_subset(), bms_next_member(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, PlannerInfo::ec_merging_done, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, i, IS_SIMPLE_REL, list_length(), list_nth(), RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, and RelOptInfo::top_parent_relids.

Referenced by set_append_rel_size().

 {
     int         i;
 
     /*
      * EC merging should be complete already, so we can use the parent rel's
      * eclass_indexes to avoid searching all of root->eq_classes.
      */
     Assert(root->ec_merging_done);
     Assert(IS_SIMPLE_REL(parent_rel));
 
     i = -1;
     while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
     {
         EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
         int         num_members;
 
         /*
          * If this EC contains a volatile expression, then generating child
          * EMs would be downright dangerous, so skip it.  We rely on a
          * volatile EC having only one EM.
          */
         if (cur_ec->ec_has_volatile)
             continue;
 
         /* Sanity check eclass_indexes only contain ECs for parent_rel */
         Assert(bms_is_subset(child_rel->top_parent_relids, cur_ec->ec_relids));
 
         /*
          * We don't use foreach() here because there's no point in scanning
          * newly-added child members, so we can stop after the last
          * pre-existing EC member.
          */
         num_members = list_length(cur_ec->ec_members);
         for (int pos = 0; pos < num_members; pos++)
         {
             EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
 
             if (cur_em->em_is_const)
                 continue;       /* ignore consts here */
 
             /*
              * We consider only original EC members here, not
              * already-transformed child members.  Otherwise, if some original
              * member expression references more than one appendrel, we'd get
              * an O(N^2) explosion of useless derived expressions for
              * combinations of children.
              */
             if (cur_em->em_is_child)
                 continue;       /* ignore children here */
 
             /* Does this member reference child's topmost parent rel? */
             if (bms_overlap(cur_em->em_relids, child_rel->top_parent_relids))
             {
                 /* Yes, generate transformed child version */
                 Expr       *child_expr;
                 Relids      new_relids;
                 Relids      new_nullable_relids;
 
                 if (parent_rel->reloptkind == RELOPT_BASEREL)
                 {
                     /* Simple single-level transformation */
                     child_expr = (Expr *)
                         adjust_appendrel_attrs(root,
                                                (Node *) cur_em->em_expr,
                                                1, &appinfo);
                 }
                 else
                 {
                     /* Must do multi-level transformation */
                     child_expr = (Expr *)
                         adjust_appendrel_attrs_multilevel(root,
                                                           (Node *) cur_em->em_expr,
                                                           child_rel->relids,
                                                           child_rel->top_parent_relids);
                 }
 
                 /*
                  * Transform em_relids to match.  Note we do *not* do
                  * pull_varnos(child_expr) here, as for example the
                  * transformation might have substituted a constant, but we
                  * don't want the child member to be marked as constant.
                  */
                 new_relids = bms_difference(cur_em->em_relids,
                                             child_rel->top_parent_relids);
                 new_relids = bms_add_members(new_relids, child_rel->relids);
 
                 /*
                  * And likewise for nullable_relids.  Note this code assumes
                  * parent and child relids are singletons.
                  */
                 new_nullable_relids = cur_em->em_nullable_relids;
                 if (bms_overlap(new_nullable_relids,
                                 child_rel->top_parent_relids))
                 {
                     new_nullable_relids = bms_difference(new_nullable_relids,
                                                          child_rel->top_parent_relids);
                     new_nullable_relids = bms_add_members(new_nullable_relids,
                                                           child_rel->relids);
                 }
 
                 (void) add_eq_member(cur_ec, child_expr,
                                      new_relids, new_nullable_relids,
                                      true, cur_em->em_datatype);
 
                 /* Record this EC index for the child rel */
                 child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
             }
         }
     }
 }

◆ add_eq_member()

static EquivalenceMember * add_eq_member	(	EquivalenceClass *	ec,
		Expr *	expr,
		Relids	relids,
		Relids	nullable_relids,
		bool	is_child,
		Oid	datatype
	)

static

Definition at line 549 of file equivclass.c.

References Assert, bms_add_members(), bms_is_empty(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, lappend(), and makeNode.

Referenced by add_child_rel_equivalences(), get_eclass_for_sort_expr(), and process_equivalence().

 {
     EquivalenceMember *em = makeNode(EquivalenceMember);
 
     em->em_expr = expr;
     em->em_relids = relids;
     em->em_nullable_relids = nullable_relids;
     em->em_is_const = false;
     em->em_is_child = is_child;
     em->em_datatype = datatype;
 
     if (bms_is_empty(relids))
     {
         /*
          * No Vars, assume it's a pseudoconstant.  This is correct for entries
          * generated from process_equivalence(), because a WHERE clause can't
          * contain aggregates or SRFs, and non-volatility was checked before
          * process_equivalence() ever got called.  But
          * get_eclass_for_sort_expr() has to work harder.  We put the tests
          * there not here to save cycles in the equivalence case.
          */
         Assert(!is_child);
         em->em_is_const = true;
         ec->ec_has_const = true;
         /* it can't affect ec_relids */
     }
     else if (!is_child)         /* child members don't add to ec_relids */
     {
         ec->ec_relids = bms_add_members(ec->ec_relids, relids);
     }
     ec->ec_members = lappend(ec->ec_members, em);
 
     return em;
 }

◆ canonicalize_ec_expression()

Expr* canonicalize_ec_expression	(	Expr *	expr,
		Oid	req_type,
		Oid	req_collation
	)

Definition at line 499 of file equivclass.c.

References arg, COERCE_IMPLICIT_CAST, exprCollation(), exprType(), exprTypmod(), IsA, and makeRelabelType().

Referenced by convert_subquery_pathkeys(), get_eclass_for_sort_expr(), and process_equivalence().

 {
     Oid         expr_type = exprType((Node *) expr);
 
     /*
      * For a polymorphic-input-type opclass, just keep the same exposed type.
      * RECORD opclasses work like polymorphic-type ones for this purpose.
      */
     if (IsPolymorphicType(req_type) || req_type == RECORDOID)
         req_type = expr_type;
 
     /*
      * No work if the expression exposes the right type/collation already.
      */
     if (expr_type != req_type ||
         exprCollation((Node *) expr) != req_collation)
     {
         /*
          * Strip any existing RelabelType, then add a new one if needed. This
          * is to preserve the invariant of no redundant RelabelTypes.
          *
          * If we have to change the exposed type of the stripped expression,
          * set typmod to -1 (since the new type may not have the same typmod
          * interpretation).  If we only have to change collation, preserve the
          * exposed typmod.
          */
         while (expr && IsA(expr, RelabelType))
             expr = (Expr *) ((RelabelType *) expr)->arg;
 
         if (exprType((Node *) expr) != req_type)
             expr = (Expr *) makeRelabelType(expr,
                                             req_type,
                                             -1,
                                             req_collation,
                                             COERCE_IMPLICIT_CAST);
         else if (exprCollation((Node *) expr) != req_collation)
             expr = (Expr *) makeRelabelType(expr,
                                             req_type,
                                             exprTypmod((Node *) expr),
                                             req_collation,
                                             COERCE_IMPLICIT_CAST);
     }
 
     return expr;
 }

◆ create_join_clause()

static RestrictInfo * create_join_clause	(	PlannerInfo *	root,
		EquivalenceClass *	ec,
		Oid	opno,
		EquivalenceMember *	leftem,
		EquivalenceMember *	rightem,
		EquivalenceClass *	parent_ec
	)

static

Definition at line 1535 of file equivclass.c.

References bms_union(), build_implied_join_equality(), RestrictInfo::clause, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_min_security, EquivalenceClass::ec_sources, EquivalenceMember::em_expr, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, lappend(), RestrictInfo::left_ec, RestrictInfo::left_em, lfirst, MemoryContextSwitchTo(), RestrictInfo::parent_ec, PlannerInfo::planner_cxt, RestrictInfo::right_ec, and RestrictInfo::right_em.

Referenced by generate_implied_equalities_for_column(), and generate_join_implied_equalities_normal().

 {
     RestrictInfo *rinfo;
     ListCell   *lc;
     MemoryContext oldcontext;
 
     /*
      * Search to see if we already built a RestrictInfo for this pair of
      * EquivalenceMembers.  We can use either original source clauses or
      * previously-derived clauses.  The check on opno is probably redundant,
      * but be safe ...
      */
     foreach(lc, ec->ec_sources)
     {
         rinfo = (RestrictInfo *) lfirst(lc);
         if (rinfo->left_em == leftem &&
             rinfo->right_em == rightem &&
             rinfo->parent_ec == parent_ec &&
             opno == ((OpExpr *) rinfo->clause)->opno)
             return rinfo;
     }
 
     foreach(lc, ec->ec_derives)
     {
         rinfo = (RestrictInfo *) lfirst(lc);
         if (rinfo->left_em == leftem &&
             rinfo->right_em == rightem &&
             rinfo->parent_ec == parent_ec &&
             opno == ((OpExpr *) rinfo->clause)->opno)
             return rinfo;
     }
 
     /*
      * Not there, so build it, in planner context so we can re-use it. (Not
      * important in normal planning, but definitely so in GEQO.)
      */
     oldcontext = MemoryContextSwitchTo(root->planner_cxt);
 
     rinfo = build_implied_join_equality(opno,
                                         ec->ec_collation,
                                         leftem->em_expr,
                                         rightem->em_expr,
                                         bms_union(leftem->em_relids,
                                                   rightem->em_relids),
                                         bms_union(leftem->em_nullable_relids,
                                                   rightem->em_nullable_relids),
                                         ec->ec_min_security);
 
     /* Mark the clause as redundant, or not */
     rinfo->parent_ec = parent_ec;
 
     /*
      * We know the correct values for left_ec/right_ec, ie this particular EC,
      * so we can just set them directly instead of forcing another lookup.
      */
     rinfo->left_ec = ec;
     rinfo->right_ec = ec;
 
     /* Mark it as usable with these EMs */
     rinfo->left_em = leftem;
     rinfo->right_em = rightem;
     /* and save it for possible re-use */
     ec->ec_derives = lappend(ec->ec_derives, rinfo);
 
     MemoryContextSwitchTo(oldcontext);
 
     return rinfo;
 }

◆ eclass_useful_for_merging()

bool eclass_useful_for_merging	(	PlannerInfo *	root,
		EquivalenceClass *	eclass,
		RelOptInfo *	rel
	)

Definition at line 2603 of file equivclass.c.

References Assert, bms_is_empty(), bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_relids, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, IS_OTHER_REL, lfirst, list_length(), RelOptInfo::relids, and RelOptInfo::top_parent_relids.

Referenced by get_useful_ecs_for_relation(), and pathkeys_useful_for_merging().

 {
     Relids      relids;
     ListCell   *lc;
 
     Assert(!eclass->ec_merged);
 
     /*
      * Won't generate joinclauses if const or single-member (the latter test
      * covers the volatile case too)
      */
     if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
         return false;
 
     /*
      * Note we don't test ec_broken; if we did, we'd need a separate code path
      * to look through ec_sources.  Checking the members anyway is OK as a
      * possibly-overoptimistic heuristic.
      */
 
     /* If specified rel is a child, we must consider the topmost parent rel */
     if (IS_OTHER_REL(rel))
     {
         Assert(!bms_is_empty(rel->top_parent_relids));
         relids = rel->top_parent_relids;
     }
     else
         relids = rel->relids;
 
     /* If rel already includes all members of eclass, no point in searching */
     if (bms_is_subset(eclass->ec_relids, relids))
         return false;
 
     /* To join, we need a member not in the given rel */
     foreach(lc, eclass->ec_members)
     {
         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 
         if (cur_em->em_is_child)
             continue;           /* ignore children here */
 
         if (!bms_overlap(cur_em->em_relids, relids))
             return true;
     }
 
     return false;
 }

◆ exprs_known_equal()

bool exprs_known_equal	(	PlannerInfo *	root,
		Node *	item1,
		Node *	item2
	)

Definition at line 2085 of file equivclass.c.

References EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, equal(), and lfirst.

Referenced by add_unique_group_var().

 {
     ListCell   *lc1;
 
     foreach(lc1, root->eq_classes)
     {
         EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
         bool        item1member = false;
         bool        item2member = false;
         ListCell   *lc2;
 
         /* Never match to a volatile EC */
         if (ec->ec_has_volatile)
             continue;
 
         foreach(lc2, ec->ec_members)
         {
             EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
 
             if (em->em_is_child)
                 continue;       /* ignore children here */
             if (equal(item1, em->em_expr))
                 item1member = true;
             else if (equal(item2, em->em_expr))
                 item2member = true;
             /* Exit as soon as equality is proven */
             if (item1member && item2member)
                 return true;
         }
     }
     return false;
 }

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo * root )

Definition at line 827 of file equivclass.c.

References Assert, bms_add_member(), bms_membership(), BMS_MULTIPLE, bms_next_member(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, PlannerInfo::ec_merging_done, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, PlannerInfo::eq_classes, generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), RelOptInfo::has_eclass_joins, i, lfirst, list_length(), RELOPT_BASEREL, RelOptInfo::reloptkind, and PlannerInfo::simple_rel_array.

Referenced by query_planner().

 {
     int         ec_index;
     ListCell   *lc;
 
     /*
      * At this point, we're done absorbing knowledge of equivalences in the
      * query, so no further EC merging should happen, and ECs remaining in the
      * eq_classes list can be considered canonical.  (But note that it's still
      * possible for new single-member ECs to be added through
      * get_eclass_for_sort_expr().)
      */
     root->ec_merging_done = true;
 
     ec_index = 0;
     foreach(lc, root->eq_classes)
     {
         EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
         bool        can_generate_joinclause = false;
         int         i;
 
         Assert(ec->ec_merged == NULL);  /* else shouldn't be in list */
         Assert(!ec->ec_broken); /* not yet anyway... */
 
         /*
          * Generate implied equalities that are restriction clauses.
          * Single-member ECs won't generate any deductions, either here or at
          * the join level.
          */
         if (list_length(ec->ec_members) > 1)
         {
             if (ec->ec_has_const)
                 generate_base_implied_equalities_const(root, ec);
             else
                 generate_base_implied_equalities_no_const(root, ec);
 
             /* Recover if we failed to generate required derived clauses */
             if (ec->ec_broken)
                 generate_base_implied_equalities_broken(root, ec);
 
             /* Detect whether this EC might generate join clauses */
             can_generate_joinclause =
                 (bms_membership(ec->ec_relids) == BMS_MULTIPLE);
         }
 
         /*
          * Mark the base rels cited in each eclass (which should all exist by
          * now) with the eq_classes indexes of all eclasses mentioning them.
          * This will let us avoid searching in subsequent lookups.  While
          * we're at it, we can mark base rels that have pending eclass joins;
          * this is a cheap version of has_relevant_eclass_joinclause().
          */
         i = -1;
         while ((i = bms_next_member(ec->ec_relids, i)) > 0)
         {
             RelOptInfo *rel = root->simple_rel_array[i];
 
             Assert(rel->reloptkind == RELOPT_BASEREL);
 
             rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
                                                  ec_index);
 
             if (can_generate_joinclause)
                 rel->has_eclass_joins = true;
         }
 
         ec_index++;
     }
 }

◆ generate_base_implied_equalities_broken()

static void generate_base_implied_equalities_broken	(	PlannerInfo *	root,
		EquivalenceClass *	ec
	)

static

Definition at line 1069 of file equivclass.c.

References bms_membership(), BMS_MULTIPLE, distribute_restrictinfo_to_rels(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_sources, lfirst, and RestrictInfo::required_relids.

Referenced by generate_base_implied_equalities().

 {
     ListCell   *lc;
 
     foreach(lc, ec->ec_sources)
     {
         RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
 
         if (ec->ec_has_const ||
             bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
             distribute_restrictinfo_to_rels(root, restrictinfo);
     }
 }

◆ generate_base_implied_equalities_const()

static void generate_base_implied_equalities_const	(	PlannerInfo *	root,
		EquivalenceClass *	ec
	)

static

Definition at line 901 of file equivclass.c.

References Assert, bms_copy(), bms_membership(), BMS_MULTIPLE, bms_union(), distribute_restrictinfo_to_rels(), EquivalenceClass::ec_below_outer_join, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_members, EquivalenceClass::ec_min_security, EquivalenceClass::ec_relids, EquivalenceClass::ec_sources, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, IsA, lfirst, linitial, list_length(), OidIsValid, process_implied_equality(), RestrictInfo::required_relids, and select_equality_operator().

Referenced by generate_base_implied_equalities().

 {
     EquivalenceMember *const_em = NULL;
     ListCell   *lc;
 
     /*
      * In the trivial case where we just had one "var = const" clause, push
      * the original clause back into the main planner machinery.  There is
      * nothing to be gained by doing it differently, and we save the effort to
      * re-build and re-analyze an equality clause that will be exactly
      * equivalent to the old one.
      */
     if (list_length(ec->ec_members) == 2 &&
         list_length(ec->ec_sources) == 1)
     {
         RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources);
 
         if (bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE)
         {
             distribute_restrictinfo_to_rels(root, restrictinfo);
             return;
         }
     }
 
     /*
      * Find the constant member to use.  We prefer an actual constant to
      * pseudo-constants (such as Params), because the constraint exclusion
      * machinery might be able to exclude relations on the basis of generated
      * "var = const" equalities, but "var = param" won't work for that.
      */
     foreach(lc, ec->ec_members)
     {
         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
 
         if (cur_em->em_is_const)
         {
             const_em = cur_em;
             if (IsA(cur_em->em_expr, Const))
                 break;
         }
     }
     Assert(const_em != NULL);
 
     /* Generate a derived equality against each other member */
     foreach(lc, ec->ec_members)
     {
         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
         Oid         eq_op;
 
         Assert(!cur_em->em_is_child);   /* no children yet */
         if (cur_em == const_em)
             continue;
         eq_op = select_equality_operator(ec,
                                          cur_em->em_datatype,
                                          const_em->em_datatype);
         if (!OidIsValid(eq_op))
         {
             /* failed... */
             ec->ec_broken = true;
             break;
         }
         process_implied_equality(root, eq_op, ec->ec_collation,
                                  cur_em->em_expr, const_em->em_expr,
                                  bms_copy(ec->ec_relids),
                                  bms_union(cur_em->em_nullable_relids,
                                            const_em->em_nullable_relids),
                                  ec->ec_min_security,
                                  ec->ec_below_outer_join,
                                  cur_em->em_is_const);
     }
 }

◆ generate_base_implied_equalities_no_const()

static void generate_base_implied_equalities_no_const	(	PlannerInfo *	root,
		EquivalenceClass *	ec
	)

static

Definition at line 978 of file equivclass.c.

References add_vars_to_targetlist(), Assert, bms_copy(), bms_get_singleton_member(), bms_union(), EquivalenceClass::ec_below_outer_join, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_members, EquivalenceClass::ec_min_security, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, lfirst, list_free(), OidIsValid, palloc0(), pfree(), process_implied_equality(), pull_var_clause(), PVC_INCLUDE_PLACEHOLDERS, PVC_RECURSE_AGGREGATES, PVC_RECURSE_WINDOWFUNCS, select_equality_operator(), and PlannerInfo::simple_rel_array_size.

Referenced by generate_base_implied_equalities().

 {
     EquivalenceMember **prev_ems;
     ListCell   *lc;
 
     /*
      * We scan the EC members once and track the last-seen member for each
      * base relation.  When we see another member of the same base relation,
      * we generate "prev_em = cur_em".  This results in the minimum number of
      * derived clauses, but it's possible that it will fail when a different
      * ordering would succeed.  XXX FIXME: use a UNION-FIND algorithm similar
      * to the way we build merged ECs.  (Use a list-of-lists for each rel.)
      */
     prev_ems = (EquivalenceMember **)
         palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *));
 
     foreach(lc, ec->ec_members)
     {
         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
         int         relid;
 
         Assert(!cur_em->em_is_child);   /* no children yet */
         if (!bms_get_singleton_member(cur_em->em_relids, &relid))
             continue;
         Assert(relid < root->simple_rel_array_size);
 
         if (prev_ems[relid] != NULL)
         {
             EquivalenceMember *prev_em = prev_ems[relid];
             Oid         eq_op;
 
             eq_op = select_equality_operator(ec,
                                              prev_em->em_datatype,
                                              cur_em->em_datatype);
             if (!OidIsValid(eq_op))
             {
                 /* failed... */
                 ec->ec_broken = true;
                 break;
             }
             process_implied_equality(root, eq_op, ec->ec_collation,
                                      prev_em->em_expr, cur_em->em_expr,
                                      bms_copy(ec->ec_relids),
                                      bms_union(prev_em->em_nullable_relids,
                                                cur_em->em_nullable_relids),
                                      ec->ec_min_security,
                                      ec->ec_below_outer_join,
                                      false);
         }
         prev_ems[relid] = cur_em;
     }
 
     pfree(prev_ems);
 
     /*
      * We also have to make sure that all the Vars used in the member clauses
      * will be available at any join node we might try to reference them at.
      * For the moment we force all the Vars to be available at all join nodes
      * for this eclass.  Perhaps this could be improved by doing some
      * pre-analysis of which members we prefer to join, but it's no worse than
      * what happened in the pre-8.3 code.
      */
     foreach(lc, ec->ec_members)
     {
         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
         List       *vars = pull_var_clause((Node *) cur_em->em_expr,
                                            PVC_RECURSE_AGGREGATES |
                                            PVC_RECURSE_WINDOWFUNCS |
                                            PVC_INCLUDE_PLACEHOLDERS);
 
         add_vars_to_targetlist(root, vars, ec->ec_relids, false);
         list_free(vars);
     }
 }

◆ generate_implied_equalities_for_column()

List* generate_implied_equalities_for_column	(	PlannerInfo *	root,
		RelOptInfo *	rel,
		ec_matches_callback_type	callback,
		void *	callback_arg,
		Relids	prohibited_rels
	)

Definition at line 2362 of file equivclass.c.

References Assert, bms_equal(), bms_is_subset(), bms_next_member(), bms_overlap(), callback(), create_join_clause(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, PlannerInfo::ec_merging_done, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, EquivalenceMember::em_datatype, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, PlannerInfo::eq_classes, find_childrel_parents(), i, IS_SIMPLE_REL, lappend(), lfirst, list_length(), list_nth(), NIL, OidIsValid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and select_equality_operator().

Referenced by create_tidscan_paths(), match_eclass_clauses_to_index(), and postgresGetForeignPaths().

 {
     List       *result = NIL;
     bool        is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
     Relids      parent_relids;
     int         i;
 
     /* Should be OK to rely on eclass_indexes */
     Assert(root->ec_merging_done);
 
     /* Indexes are available only on base or "other" member relations. */
     Assert(IS_SIMPLE_REL(rel));
 
     /* If it's a child rel, we'll need to know what its parent(s) are */
     if (is_child_rel)
         parent_relids = find_childrel_parents(root, rel);
     else
         parent_relids = NULL;   /* not used, but keep compiler quiet */
 
     i = -1;
     while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
     {
         EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
         EquivalenceMember *cur_em;
         ListCell   *lc2;
 
         /* Sanity check eclass_indexes only contain ECs for rel */
         Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));
 
         /*
          * Won't generate joinclauses if const or single-member (the latter
          * test covers the volatile case too)
          */
         if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
             continue;
 
         /*
          * Scan members, looking for a match to the target column.  Note that
          * child EC members are considered, but only when they belong to the
          * target relation.  (Unlike regular members, the same expression
          * could be a child member of more than one EC.  Therefore, it's
          * potentially order-dependent which EC a child relation's target
          * column gets matched to.  This is annoying but it only happens in
          * corner cases, so for now we live with just reporting the first
          * match.  See also get_eclass_for_sort_expr.)
          */
         cur_em = NULL;
         foreach(lc2, cur_ec->ec_members)
         {
             cur_em = (EquivalenceMember *) lfirst(lc2);
             if (bms_equal(cur_em->em_relids, rel->relids) &&
                 callback(root, rel, cur_ec, cur_em, callback_arg))
                 break;
             cur_em = NULL;
         }
 
         if (!cur_em)
             continue;
 
         /*
          * Found our match.  Scan the other EC members and attempt to generate
          * joinclauses.
          */
         foreach(lc2, cur_ec->ec_members)
         {
             EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
             Oid         eq_op;
             RestrictInfo *rinfo;
 
             if (other_em->em_is_child)
                 continue;       /* ignore children here */
 
             /* Make sure it'll be a join to a different rel */
             if (other_em == cur_em ||
                 bms_overlap(other_em->em_relids, rel->relids))
                 continue;
 
             /* Forget it if caller doesn't want joins to this rel */
             if (bms_overlap(other_em->em_relids, prohibited_rels))
                 continue;
 
             /*
              * Also, if this is a child rel, avoid generating a useless join
              * to its parent rel(s).
              */
             if (is_child_rel &&
                 bms_overlap(parent_relids, other_em->em_relids))
                 continue;
 
             eq_op = select_equality_operator(cur_ec,
                                              cur_em->em_datatype,
                                              other_em->em_datatype);
             if (!OidIsValid(eq_op))
                 continue;
 
             /* set parent_ec to mark as redundant with other joinclauses */
             rinfo = create_join_clause(root, cur_ec, eq_op,
                                        cur_em, other_em,
                                        cur_ec);
 
             result = lappend(result, rinfo);
         }
 
         /*
          * If somehow we failed to create any join clauses, we might as well
          * keep scanning the ECs for another match.  But if we did make any,
          * we're done, because we don't want to return non-redundant clauses.
          */
         if (result)
             break;
     }
 
     return result;
 }

◆ generate_join_implied_equalities()

List* generate_join_implied_equalities	(	PlannerInfo *	root,
		Relids	join_relids,
		Relids	outer_relids,
		RelOptInfo *	inner_rel
	)

Definition at line 1126 of file equivclass.c.

References Assert, bms_is_empty(), bms_next_member(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), get_common_eclass_indexes(), i, IS_OTHER_REL, list_concat(), list_length(), list_nth(), NIL, RelOptInfo::relids, and RelOptInfo::top_parent_relids.

Referenced by build_joinrel_restrictlist(), check_index_predicates(), get_baserel_parampathinfo(), get_joinrel_parampathinfo(), and reduce_unique_semijoins().

 {
     List       *result = NIL;
     Relids      inner_relids = inner_rel->relids;
     Relids      nominal_inner_relids;
     Relids      nominal_join_relids;
     Bitmapset * matching_ecs;
     int         i;
 
     /* If inner rel is a child, extra setup work is needed */
     if (IS_OTHER_REL(inner_rel))
     {
         Assert(!bms_is_empty(inner_rel->top_parent_relids));
 
         /* Fetch relid set for the topmost parent rel */
         nominal_inner_relids = inner_rel->top_parent_relids;
         /* ECs will be marked with the parent's relid, not the child's */
         nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
     }
     else
     {
         nominal_inner_relids = inner_relids;
         nominal_join_relids = join_relids;
     }
 
     /*
      * Get all eclasses in common between inner_rel's relids and outer_relids
      */
     matching_ecs = get_common_eclass_indexes(root, inner_rel->relids,
                                              outer_relids);
 
     i = -1;
     while ((i = bms_next_member(matching_ecs, i)) >= 0)
     {
         EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
         List       *sublist = NIL;
 
         /* ECs containing consts do not need any further enforcement */
         if (ec->ec_has_const)
             continue;
 
         /* Single-member ECs won't generate any deductions */
         if (list_length(ec->ec_members) <= 1)
             continue;
 
         /* Sanity check that this eclass overlaps the join */
         Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
 
         if (!ec->ec_broken)
             sublist = generate_join_implied_equalities_normal(root,
                                                               ec,
                                                               join_relids,
                                                               outer_relids,
                                                               inner_relids);
 
         /* Recover if we failed to generate required derived clauses */
         if (ec->ec_broken)
             sublist = generate_join_implied_equalities_broken(root,
                                                               ec,
                                                               nominal_join_relids,
                                                               outer_relids,
                                                               nominal_inner_relids,
                                                               inner_rel);
 
         result = list_concat(result, sublist);
     }
 
     return result;
 }

◆ generate_join_implied_equalities_broken()

static List * generate_join_implied_equalities_broken	(	PlannerInfo *	root,
		EquivalenceClass *	ec,
		Relids	nominal_join_relids,
		Relids	outer_relids,
		Relids	nominal_inner_relids,
		RelOptInfo *	inner_rel
	)

static

Definition at line 1451 of file equivclass.c.

References adjust_appendrel_attrs_multilevel(), bms_is_subset(), EquivalenceClass::ec_sources, IS_OTHER_REL, lappend(), lfirst, NIL, RelOptInfo::relids, RestrictInfo::required_relids, and RelOptInfo::top_parent_relids.

Referenced by generate_join_implied_equalities(), and generate_join_implied_equalities_for_ecs().

 {
     List       *result = NIL;
     ListCell   *lc;
 
     foreach(lc, ec->ec_sources)
     {
         RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
         Relids      clause_relids = restrictinfo->required_relids;
 
         if (bms_is_subset(clause_relids, nominal_join_relids) &&
             !bms_is_subset(clause_relids, outer_relids) &&
             !bms_is_subset(clause_relids, nominal_inner_relids))
             result = lappend(result, restrictinfo);
     }
 
     /*
      * If we have to translate, just brute-force apply adjust_appendrel_attrs
      * to all the RestrictInfos at once.  This will result in returning
      * RestrictInfos that are not listed in ec_derives, but there shouldn't be
      * any duplication, and it's a sufficiently narrow corner case that we
      * shouldn't sweat too much over it anyway.
      *
      * Since inner_rel might be an indirect descendant of the baserel
      * mentioned in the ec_sources clauses, we have to be prepared to apply
      * multiple levels of Var translation.
      */
     if (IS_OTHER_REL(inner_rel) && result != NIL)
         result = (List *) adjust_appendrel_attrs_multilevel(root,
                                                             (Node *) result,
                                                             inner_rel->relids,
                                                             inner_rel->top_parent_relids);
 
     return result;
 }

◆ generate_join_implied_equalities_for_ecs()

List* generate_join_implied_equalities_for_ecs	(	PlannerInfo *	root,
		List *	eclasses,
		Relids	join_relids,
		Relids	outer_relids,
		RelOptInfo *	inner_rel
	)

Definition at line 1204 of file equivclass.c.

References Assert, bms_is_empty(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), IS_OTHER_REL, lfirst, list_concat(), list_length(), NIL, RelOptInfo::relids, and RelOptInfo::top_parent_relids.

Referenced by get_joinrel_parampathinfo().

 {
     List       *result = NIL;
     Relids      inner_relids = inner_rel->relids;
     Relids      nominal_inner_relids;
     Relids      nominal_join_relids;
     ListCell   *lc;
 
     /* If inner rel is a child, extra setup work is needed */
     if (IS_OTHER_REL(inner_rel))
     {
         Assert(!bms_is_empty(inner_rel->top_parent_relids));
 
         /* Fetch relid set for the topmost parent rel */
         nominal_inner_relids = inner_rel->top_parent_relids;
         /* ECs will be marked with the parent's relid, not the child's */
         nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
     }
     else
     {
         nominal_inner_relids = inner_relids;
         nominal_join_relids = join_relids;
     }
 
     foreach(lc, eclasses)
     {
         EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
         List       *sublist = NIL;
 
         /* ECs containing consts do not need any further enforcement */
         if (ec->ec_has_const)
             continue;
 
         /* Single-member ECs won't generate any deductions */
         if (list_length(ec->ec_members) <= 1)
             continue;
 
         /* We can quickly ignore any that don't overlap the join, too */
         if (!bms_overlap(ec->ec_relids, nominal_join_relids))
             continue;
 
         if (!ec->ec_broken)
             sublist = generate_join_implied_equalities_normal(root,
                                                               ec,
                                                               join_relids,
                                                               outer_relids,
                                                               inner_relids);
 
         /* Recover if we failed to generate required derived clauses */
         if (ec->ec_broken)
             sublist = generate_join_implied_equalities_broken(root,
                                                               ec,
                                                               nominal_join_relids,
                                                               outer_relids,
                                                               nominal_inner_relids,
                                                               inner_rel);
 
         result = list_concat(result, sublist);
     }
 
     return result;
 }

◆ generate_join_implied_equalities_normal()

static List * generate_join_implied_equalities_normal	(	PlannerInfo *	root,
		EquivalenceClass *	ec,
		Relids	join_relids,
		Relids	outer_relids,
		Relids	inner_relids
	)

static

Definition at line 1275 of file equivclass.c.

References bms_is_subset(), create_join_clause(), EquivalenceClass::ec_broken, EquivalenceClass::ec_members, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_relids, exprType(), InvalidOid, IsA, lappend(), lfirst, linitial, list_concat(), NIL, OidIsValid, op_hashjoinable(), and select_equality_operator().

Referenced by generate_join_implied_equalities(), and generate_join_implied_equalities_for_ecs().

 {
     List       *result = NIL;
     List       *new_members = NIL;
     List       *outer_members = NIL;
     List       *inner_members = NIL;
     ListCell   *lc1;
 
     /*
      * First, scan the EC to identify member values that are computable at the
      * outer rel, at the inner rel, or at this relation but not in either
      * input rel.  The outer-rel members should already be enforced equal,
      * likewise for the inner-rel members.  We'll need to create clauses to
      * enforce that any newly computable members are all equal to each other
      * as well as to at least one input member, plus enforce at least one
      * outer-rel member equal to at least one inner-rel member.
      */
     foreach(lc1, ec->ec_members)
     {
         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
 
         /*
          * We don't need to check explicitly for child EC members.  This test
          * against join_relids will cause them to be ignored except when
          * considering a child inner rel, which is what we want.
          */
         if (!bms_is_subset(cur_em->em_relids, join_relids))
             continue;           /* not computable yet, or wrong child */
 
         if (bms_is_subset(cur_em->em_relids, outer_relids))
             outer_members = lappend(outer_members, cur_em);
         else if (bms_is_subset(cur_em->em_relids, inner_relids))
             inner_members = lappend(inner_members, cur_em);
         else
             new_members = lappend(new_members, cur_em);
     }
 
     /*
      * First, select the joinclause if needed.  We can equate any one outer
      * member to any one inner member, but we have to find a datatype
      * combination for which an opfamily member operator exists.  If we have
      * choices, we prefer simple Var members (possibly with RelabelType) since
      * these are (a) cheapest to compute at runtime and (b) most likely to
      * have useful statistics. Also, prefer operators that are also
      * hashjoinable.
      */
     if (outer_members && inner_members)
     {
         EquivalenceMember *best_outer_em = NULL;
         EquivalenceMember *best_inner_em = NULL;
         Oid         best_eq_op = InvalidOid;
         int         best_score = -1;
         RestrictInfo *rinfo;
 
         foreach(lc1, outer_members)
         {
             EquivalenceMember *outer_em = (EquivalenceMember *) lfirst(lc1);
             ListCell   *lc2;
 
             foreach(lc2, inner_members)
             {
                 EquivalenceMember *inner_em = (EquivalenceMember *) lfirst(lc2);
                 Oid         eq_op;
                 int         score;
 
                 eq_op = select_equality_operator(ec,
                                                  outer_em->em_datatype,
                                                  inner_em->em_datatype);
                 if (!OidIsValid(eq_op))
                     continue;
                 score = 0;
                 if (IsA(outer_em->em_expr, Var) ||
                     (IsA(outer_em->em_expr, RelabelType) &&
                      IsA(((RelabelType *) outer_em->em_expr)->arg, Var)))
                     score++;
                 if (IsA(inner_em->em_expr, Var) ||
                     (IsA(inner_em->em_expr, RelabelType) &&
                      IsA(((RelabelType *) inner_em->em_expr)->arg, Var)))
                     score++;
                 if (op_hashjoinable(eq_op,
                                     exprType((Node *) outer_em->em_expr)))
                     score++;
                 if (score > best_score)
                 {
                     best_outer_em = outer_em;
                     best_inner_em = inner_em;
                     best_eq_op = eq_op;
                     best_score = score;
                     if (best_score == 3)
                         break;  /* no need to look further */
                 }
             }
             if (best_score == 3)
                 break;          /* no need to look further */
         }
         if (best_score < 0)
         {
             /* failed... */
             ec->ec_broken = true;
             return NIL;
         }
 
         /*
          * Create clause, setting parent_ec to mark it as redundant with other
          * joinclauses
          */
         rinfo = create_join_clause(root, ec, best_eq_op,
                                    best_outer_em, best_inner_em,
                                    ec);
 
         result = lappend(result, rinfo);
     }
 
     /*
      * Now deal with building restrictions for any expressions that involve
      * Vars from both sides of the join.  We have to equate all of these to
      * each other as well as to at least one old member (if any).
      *
      * XXX as in generate_base_implied_equalities_no_const, we could be a lot
      * smarter here to avoid unnecessary failures in cross-type situations.
      * For now, use the same left-to-right method used there.
      */
     if (new_members)
     {
         List       *old_members = list_concat(outer_members, inner_members);
         EquivalenceMember *prev_em = NULL;
         RestrictInfo *rinfo;
 
         /* For now, arbitrarily take the first old_member as the one to use */
         if (old_members)
             new_members = lappend(new_members, linitial(old_members));
 
         foreach(lc1, new_members)
         {
             EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc1);
 
             if (prev_em != NULL)
             {
                 Oid         eq_op;
 
                 eq_op = select_equality_operator(ec,
                                                  prev_em->em_datatype,
                                                  cur_em->em_datatype);
                 if (!OidIsValid(eq_op))
                 {
                     /* failed... */
                     ec->ec_broken = true;
                     return NIL;
                 }
                 /* do NOT set parent_ec, this qual is not redundant! */
                 rinfo = create_join_clause(root, ec, eq_op,
                                            prev_em, cur_em,
                                            NULL);
 
                 result = lappend(result, rinfo);
             }
             prev_em = cur_em;
         }
     }
 
     return result;
 }

◆ get_common_eclass_indexes()

static Bitmapset * get_common_eclass_indexes	(	PlannerInfo *	root,
		Relids	relids1,
		Relids	relids2
	)

static

Definition at line 2748 of file equivclass.c.

References bms_get_singleton_member(), bms_int_members(), RelOptInfo::eclass_indexes, get_eclass_indexes_for_relids(), and PlannerInfo::simple_rel_array.

Referenced by generate_join_implied_equalities(), and have_relevant_eclass_joinclause().

 {
     Bitmapset  *rel1ecs;
     Bitmapset  *rel2ecs;
     int         relid;
 
     rel1ecs = get_eclass_indexes_for_relids(root, relids1);
 
     /*
      * We can get away with just using the relation's eclass_indexes directly
      * when relids2 is a singleton set.
      */
     if (bms_get_singleton_member(relids2, &relid))
         rel2ecs = root->simple_rel_array[relid]->eclass_indexes;
     else
         rel2ecs = get_eclass_indexes_for_relids(root, relids2);
 
     /* Calculate and return the common EC indexes, recycling the left input. */
     return bms_int_members(rel1ecs, rel2ecs);
 }

◆ get_eclass_for_sort_expr()

EquivalenceClass* get_eclass_for_sort_expr	(	PlannerInfo *	root,
		Expr *	expr,
		Relids	nullable_relids,
		List *	opfamilies,
		Oid	opcintype,
		Oid	collation,
		Index	sortref,
		Relids	rel,
		bool	create_it
	)

Definition at line 625 of file equivclass.c.

Referenced by convert_subquery_pathkeys(), initialize_mergeclause_eclasses(), and make_pathkey_from_sortinfo().

 {
     Relids      expr_relids;
     EquivalenceClass *newec;
     EquivalenceMember *newem;
     ListCell   *lc1;
     MemoryContext oldcontext;
 
     /*
      * Ensure the expression exposes the correct type and collation.
      */
     expr = canonicalize_ec_expression(expr, opcintype, collation);
 
     /*
      * Get the precise set of nullable relids appearing in the expression.
      */
     expr_relids = pull_varnos((Node *) expr);
     nullable_relids = bms_intersect(nullable_relids, expr_relids);
 
     /*
      * Scan through the existing EquivalenceClasses for a match
      */
     foreach(lc1, root->eq_classes)
     {
         EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
         ListCell   *lc2;
 
         /*
          * Never match to a volatile EC, except when we are looking at another
          * reference to the same volatile SortGroupClause.
          */
         if (cur_ec->ec_has_volatile &&
             (sortref == 0 || sortref != cur_ec->ec_sortref))
             continue;
 
         if (collation != cur_ec->ec_collation)
             continue;
         if (!equal(opfamilies, cur_ec->ec_opfamilies))
             continue;
 
         foreach(lc2, cur_ec->ec_members)
         {
             EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 
             /*
              * Ignore child members unless they match the request.
              */
             if (cur_em->em_is_child &&
                 !bms_equal(cur_em->em_relids, rel))
                 continue;
 
             /*
              * If below an outer join, don't match constants: they're not as
              * constant as they look.
              */
             if (cur_ec->ec_below_outer_join &&
                 cur_em->em_is_const)
                 continue;
 
             if (opcintype == cur_em->em_datatype &&
                 equal(expr, cur_em->em_expr))
                 return cur_ec;  /* Match! */
         }
     }
 
     /* No match; does caller want a NULL result? */
     if (!create_it)
         return NULL;
 
     /*
      * OK, build a new single-member EC
      *
      * Here, we must be sure that we construct the EC in the right context.
      */
     oldcontext = MemoryContextSwitchTo(root->planner_cxt);
 
     newec = makeNode(EquivalenceClass);
     newec->ec_opfamilies = list_copy(opfamilies);
     newec->ec_collation = collation;
     newec->ec_members = NIL;
     newec->ec_sources = NIL;
     newec->ec_derives = NIL;
     newec->ec_relids = NULL;
     newec->ec_has_const = false;
     newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
     newec->ec_below_outer_join = false;
     newec->ec_broken = false;
     newec->ec_sortref = sortref;
     newec->ec_min_security = UINT_MAX;
     newec->ec_max_security = 0;
     newec->ec_merged = NULL;
 
     if (newec->ec_has_volatile && sortref == 0) /* should not happen */
         elog(ERROR, "volatile EquivalenceClass has no sortref");
 
     newem = add_eq_member(newec, copyObject(expr), expr_relids,
                           nullable_relids, false, opcintype);
 
     /*
      * add_eq_member doesn't check for volatile functions, set-returning
      * functions, aggregates, or window functions, but such could appear in
      * sort expressions; so we have to check whether its const-marking was
      * correct.
      */
     if (newec->ec_has_const)
     {
         if (newec->ec_has_volatile ||
             expression_returns_set((Node *) expr) ||
             contain_agg_clause((Node *) expr) ||
             contain_window_function((Node *) expr))
         {
             newec->ec_has_const = false;
             newem->em_is_const = false;
         }
     }
 
     root->eq_classes = lappend(root->eq_classes, newec);
 
     /*
      * If EC merging is already complete, we have to mop up by adding the new
      * EC to the eclass_indexes of the relation(s) mentioned in it.
      */
     if (root->ec_merging_done)
     {
         int         ec_index = list_length(root->eq_classes) - 1;
         int         i = -1;
 
         while ((i = bms_next_member(newec->ec_relids, i)) > 0)
         {
             RelOptInfo *rel = root->simple_rel_array[i];
 
             Assert(rel->reloptkind == RELOPT_BASEREL ||
                    rel->reloptkind == RELOPT_DEADREL);
 
             rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
                                                  ec_index);
         }
     }
 
     MemoryContextSwitchTo(oldcontext);
 
     return newec;
 }

◆ get_eclass_indexes_for_relids()

static Bitmapset * get_eclass_indexes_for_relids	(	PlannerInfo *	root,
		Relids	relids
	)

static

Definition at line 2724 of file equivclass.c.

References Assert, bms_add_members(), bms_next_member(), PlannerInfo::ec_merging_done, RelOptInfo::eclass_indexes, i, and PlannerInfo::simple_rel_array.

Referenced by get_common_eclass_indexes(), and has_relevant_eclass_joinclause().

 {
     Bitmapset  *ec_indexes = NULL;
     int         i = -1;
 
     /* Should be OK to rely on eclass_indexes */
     Assert(root->ec_merging_done);
 
     while ((i = bms_next_member(relids, i)) > 0)
     {
         RelOptInfo *rel = root->simple_rel_array[i];
 
         ec_indexes = bms_add_members(ec_indexes, rel->eclass_indexes);
     }
     return ec_indexes;
 }

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause	(	PlannerInfo *	root,
		RelOptInfo *	rel1
	)

Definition at line 2559 of file equivclass.c.

References bms_is_subset(), bms_next_member(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, get_eclass_indexes_for_relids(), i, list_length(), list_nth(), and RelOptInfo::relids.

Referenced by build_join_rel().

 {
     Bitmapset  *matched_ecs;
     int         i;
 
     /* Examine only eclasses mentioning rel1 */
     matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);
 
     i = -1;
     while ((i = bms_next_member(matched_ecs, i)) >= 0)
     {
         EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
                                                              i);
 
         /*
          * Won't generate joinclauses if single-member (this test covers the
          * volatile case too)
          */
         if (list_length(ec->ec_members) <= 1)
             continue;
 
         /*
          * Per the comment in have_relevant_eclass_joinclause, it's sufficient
          * to find an EC that mentions both this rel and some other rel.
          */
         if (!bms_is_subset(ec->ec_relids, rel1->relids))
             return true;
     }
 
     return false;
 }

◆ have_relevant_eclass_joinclause()

bool have_relevant_eclass_joinclause	(	PlannerInfo *	root,
		RelOptInfo *	rel1,
		RelOptInfo *	rel2
	)

Definition at line 2492 of file equivclass.c.

References Assert, bms_next_member(), bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, get_common_eclass_indexes(), i, list_length(), list_nth(), and RelOptInfo::relids.

Referenced by have_relevant_joinclause().

 {
     Bitmapset  *matching_ecs;
     int         i;
 
     /* Examine only eclasses mentioning both rel1 and rel2 */
     matching_ecs = get_common_eclass_indexes(root, rel1->relids,
                                              rel2->relids);
 
     i = -1;
     while ((i = bms_next_member(matching_ecs, i)) >= 0)
     {
         EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
                                                              i);
 
         /*
          * Sanity check that get_common_eclass_indexes gave only ECs
          * containing both rels.
          */
         Assert(bms_overlap(rel1->relids, ec->ec_relids));
         Assert(bms_overlap(rel2->relids, ec->ec_relids));
 
         /*
          * Won't generate joinclauses if single-member (this test covers the
          * volatile case too)
          */
         if (list_length(ec->ec_members) <= 1)
             continue;
 
         /*
          * We do not need to examine the individual members of the EC, because
          * all that we care about is whether each rel overlaps the relids of
          * at least one member, and get_common_eclass_indexes() and the single
          * member check above are sufficient to prove that.  (As with
          * have_relevant_joinclause(), it is not necessary that the EC be able
          * to form a joinclause relating exactly the two given rels, only that
          * it be able to form a joinclause mentioning both, and this will
          * surely be true if both of them overlap ec_relids.)
          *
          * Note we don't test ec_broken; if we did, we'd need a separate code
          * path to look through ec_sources.  Checking the membership anyway is
          * OK as a possibly-overoptimistic heuristic.
          *
          * We don't test ec_has_const either, even though a const eclass won't
          * generate real join clauses.  This is because if we had "WHERE a.x =
          * b.y and a.x = 42", it is worth considering a join between a and b,
          * since the join result is likely to be small even though it'll end
          * up being an unqualified nestloop.
          */
 
         return true;
     }
 
     return false;
 }

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause	(	RestrictInfo *	rinfo,
		List *	clauselist
	)

Definition at line 2661 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_tidscan_plan().

 {
     EquivalenceClass *parent_ec = rinfo->parent_ec;
     ListCell   *lc;
 
     /* Fail if it's not a potentially-redundant clause from some EC */
     if (parent_ec == NULL)
         return false;
 
     foreach(lc, clauselist)
     {
         RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
 
         if (otherrinfo->parent_ec == parent_ec)
             return true;
     }
 
     return false;
 }

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses	(	RestrictInfo *	rinfo,
		List *	indexclauses
	)

Definition at line 2688 of file equivclass.c.

References lfirst_node, IndexClause::lossy, RestrictInfo::parent_ec, and IndexClause::rinfo.

Referenced by create_indexscan_plan(), extract_nonindex_conditions(), and has_indexed_join_quals().

 {
     EquivalenceClass *parent_ec = rinfo->parent_ec;
     ListCell   *lc;
 
     foreach(lc, indexclauses)
     {
         IndexClause *iclause = lfirst_node(IndexClause, lc);
         RestrictInfo *otherrinfo = iclause->rinfo;
 
         /* If indexclause is lossy, it won't enforce the condition exactly */
         if (iclause->lossy)
             continue;
 
         /* Match if it's same clause (pointer equality should be enough) */
         if (rinfo == otherrinfo)
             return true;
         /* Match if derived from same EC */
         if (parent_ec && otherrinfo->parent_ec == parent_ec)
             return true;
 
         /*
          * No need to look at the derived clauses in iclause->indexquals; they
          * couldn't match if the parent clause didn't.
          */
     }
 
     return false;
 }

◆ match_eclasses_to_foreign_key_col()

EquivalenceClass* match_eclasses_to_foreign_key_col	(	PlannerInfo *	root,
		ForeignKeyOptInfo *	fkinfo,
		int	colno
	)

Definition at line 2132 of file equivclass.c.

References Assert, bms_intersect(), bms_next_member(), ForeignKeyOptInfo::con_relid, ForeignKeyOptInfo::confkey, ForeignKeyOptInfo::conkey, ForeignKeyOptInfo::conpfeqop, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, PlannerInfo::ec_merging_done, EquivalenceClass::ec_opfamilies, RelOptInfo::eclass_indexes, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, equal(), get_mergejoin_opfamilies(), i, IS_SIMPLE_REL, IsA, lfirst, list_nth(), NIL, ForeignKeyOptInfo::ref_relid, PlannerInfo::simple_rel_array, RangeQueryClause::var, Var::varattno, and Var::varno.

Referenced by match_foreign_keys_to_quals().

 {
     Index       var1varno = fkinfo->con_relid;
     AttrNumber  var1attno = fkinfo->conkey[colno];
     Index       var2varno = fkinfo->ref_relid;
     AttrNumber  var2attno = fkinfo->confkey[colno];
     Oid         eqop = fkinfo->conpfeqop[colno];
     RelOptInfo *rel1 = root->simple_rel_array[var1varno];
     RelOptInfo *rel2 = root->simple_rel_array[var2varno];
     List       *opfamilies = NIL;   /* compute only if needed */
     Bitmapset  *matching_ecs;
     int         i;
 
     /* Consider only eclasses mentioning both relations */
     Assert(root->ec_merging_done);
     Assert(IS_SIMPLE_REL(rel1));
     Assert(IS_SIMPLE_REL(rel2));
     matching_ecs = bms_intersect(rel1->eclass_indexes,
                                  rel2->eclass_indexes);
 
     i = -1;
     while ((i = bms_next_member(matching_ecs, i)) >= 0)
     {
         EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
                                                              i);
         bool        item1member = false;
         bool        item2member = false;
         ListCell   *lc2;
 
         /* Never match to a volatile EC */
         if (ec->ec_has_volatile)
             continue;
         /* Note: it seems okay to match to "broken" eclasses here */
 
         foreach(lc2, ec->ec_members)
         {
             EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
             Var        *var;
 
             if (em->em_is_child)
                 continue;       /* ignore children here */
 
             /* EM must be a Var, possibly with RelabelType */
             var = (Var *) em->em_expr;
             while (var && IsA(var, RelabelType))
                 var = (Var *) ((RelabelType *) var)->arg;
             if (!(var && IsA(var, Var)))
                 continue;
 
             /* Match? */
             if (var->varno == var1varno && var->varattno == var1attno)
                 item1member = true;
             else if (var->varno == var2varno && var->varattno == var2attno)
                 item2member = true;
 
             /* Have we found both PK and FK column in this EC? */
             if (item1member && item2member)
             {
                 /*
                  * Succeed if eqop matches EC's opfamilies.  We could test
                  * this before scanning the members, but it's probably cheaper
                  * to test for member matches first.
                  */
                 if (opfamilies == NIL)  /* compute if we didn't already */
                     opfamilies = get_mergejoin_opfamilies(eqop);
                 if (equal(opfamilies, ec->ec_opfamilies))
                     return ec;
                 /* Otherwise, done with this EC, move on to the next */
                 break;
             }
         }
     }
     return NULL;
 }

◆ process_equivalence()

bool process_equivalence	(	PlannerInfo *	root,
		RestrictInfo **	p_restrictinfo,
		bool	below_outer_join
	)

Definition at line 118 of file equivclass.c.

Referenced by distribute_qual_to_rels(), reconsider_full_join_clause(), and reconsider_outer_join_clause().

 {
     RestrictInfo *restrictinfo = *p_restrictinfo;
     Expr       *clause = restrictinfo->clause;
     Oid         opno,
                 collation,
                 item1_type,
                 item2_type;
     Expr       *item1;
     Expr       *item2;
     Relids      item1_relids,
                 item2_relids,
                 item1_nullable_relids,
                 item2_nullable_relids;
     List       *opfamilies;
     EquivalenceClass *ec1,
                *ec2;
     EquivalenceMember *em1,
                *em2;
     ListCell   *lc1;
 
     /* Should not already be marked as having generated an eclass */
     Assert(restrictinfo->left_ec == NULL);
     Assert(restrictinfo->right_ec == NULL);
 
     /* Reject if it is potentially postponable by security considerations */
     if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
         return false;
 
     /* Extract info from given clause */
     Assert(is_opclause(clause));
     opno = ((OpExpr *) clause)->opno;
     collation = ((OpExpr *) clause)->inputcollid;
     item1 = (Expr *) get_leftop(clause);
     item2 = (Expr *) get_rightop(clause);
     item1_relids = restrictinfo->left_relids;
     item2_relids = restrictinfo->right_relids;
 
     /*
      * Ensure both input expressions expose the desired collation (their types
      * should be OK already); see comments for canonicalize_ec_expression.
      */
     item1 = canonicalize_ec_expression(item1,
                                        exprType((Node *) item1),
                                        collation);
     item2 = canonicalize_ec_expression(item2,
                                        exprType((Node *) item2),
                                        collation);
 
     /*
      * Clauses of the form X=X cannot be translated into EquivalenceClasses.
      * We'd either end up with a single-entry EC, losing the knowledge that
      * the clause was present at all, or else make an EC with duplicate
      * entries, causing other issues.
      */
     if (equal(item1, item2))
     {
         /*
          * If the operator is strict, then the clause can be treated as just
          * "X IS NOT NULL".  (Since we know we are considering a top-level
          * qual, we can ignore the difference between FALSE and NULL results.)
          * It's worth making the conversion because we'll typically get a much
          * better selectivity estimate than we would for X=X.
          *
          * If the operator is not strict, we can't be sure what it will do
          * with NULLs, so don't attempt to optimize it.
          */
         set_opfuncid((OpExpr *) clause);
         if (func_strict(((OpExpr *) clause)->opfuncid))
         {
             NullTest   *ntest = makeNode(NullTest);
 
             ntest->arg = item1;
             ntest->nulltesttype = IS_NOT_NULL;
             ntest->argisrow = false;    /* correct even if composite arg */
             ntest->location = -1;
 
             *p_restrictinfo =
                 make_restrictinfo((Expr *) ntest,
                                   restrictinfo->is_pushed_down,
                                   restrictinfo->outerjoin_delayed,
                                   restrictinfo->pseudoconstant,
                                   restrictinfo->security_level,
                                   NULL,
                                   restrictinfo->outer_relids,
                                   restrictinfo->nullable_relids);
         }
         return false;
     }
 
     /*
      * If below outer join, check for strictness, else reject.
      */
     if (below_outer_join)
     {
         if (!bms_is_empty(item1_relids) &&
             contain_nonstrict_functions((Node *) item1))
             return false;       /* LHS is non-strict but not constant */
         if (!bms_is_empty(item2_relids) &&
             contain_nonstrict_functions((Node *) item2))
             return false;       /* RHS is non-strict but not constant */
     }
 
     /* Calculate nullable-relid sets for each side of the clause */
     item1_nullable_relids = bms_intersect(item1_relids,
                                           restrictinfo->nullable_relids);
     item2_nullable_relids = bms_intersect(item2_relids,
                                           restrictinfo->nullable_relids);
 
     /*
      * We use the declared input types of the operator, not exprType() of the
      * inputs, as the nominal datatypes for opfamily lookup.  This presumes
      * that btree operators are always registered with amoplefttype and
      * amoprighttype equal to their declared input types.  We will need this
      * info anyway to build EquivalenceMember nodes, and by extracting it now
      * we can use type comparisons to short-circuit some equal() tests.
      */
     op_input_types(opno, &item1_type, &item2_type);
 
     opfamilies = restrictinfo->mergeopfamilies;
 
     /*
      * Sweep through the existing EquivalenceClasses looking for matches to
      * item1 and item2.  These are the possible outcomes:
      *
      * 1. We find both in the same EC.  The equivalence is already known, so
      * there's nothing to do.
      *
      * 2. We find both in different ECs.  Merge the two ECs together.
      *
      * 3. We find just one.  Add the other to its EC.
      *
      * 4. We find neither.  Make a new, two-entry EC.
      *
      * Note: since all ECs are built through this process or the similar
      * search in get_eclass_for_sort_expr(), it's impossible that we'd match
      * an item in more than one existing nonvolatile EC.  So it's okay to stop
      * at the first match.
      */
     ec1 = ec2 = NULL;
     em1 = em2 = NULL;
     foreach(lc1, root->eq_classes)
     {
         EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
         ListCell   *lc2;
 
         /* Never match to a volatile EC */
         if (cur_ec->ec_has_volatile)
             continue;
 
         /*
          * The collation has to match; check this first since it's cheaper
          * than the opfamily comparison.
          */
         if (collation != cur_ec->ec_collation)
             continue;
 
         /*
          * A "match" requires matching sets of btree opfamilies.  Use of
          * equal() for this test has implications discussed in the comments
          * for get_mergejoin_opfamilies().
          */
         if (!equal(opfamilies, cur_ec->ec_opfamilies))
             continue;
 
         foreach(lc2, cur_ec->ec_members)
         {
             EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 
             Assert(!cur_em->em_is_child);   /* no children yet */
 
             /*
              * If below an outer join, don't match constants: they're not as
              * constant as they look.
              */
             if ((below_outer_join || cur_ec->ec_below_outer_join) &&
                 cur_em->em_is_const)
                 continue;
 
             if (!ec1 &&
                 item1_type == cur_em->em_datatype &&
                 equal(item1, cur_em->em_expr))
             {
                 ec1 = cur_ec;
                 em1 = cur_em;
                 if (ec2)
                     break;
             }
 
             if (!ec2 &&
                 item2_type == cur_em->em_datatype &&
                 equal(item2, cur_em->em_expr))
             {
                 ec2 = cur_ec;
                 em2 = cur_em;
                 if (ec1)
                     break;
             }
         }
 
         if (ec1 && ec2)
             break;
     }
 
     /* Sweep finished, what did we find? */
 
     if (ec1 && ec2)
     {
         /* If case 1, nothing to do, except add to sources */
         if (ec1 == ec2)
         {
             ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
             ec1->ec_below_outer_join |= below_outer_join;
             ec1->ec_min_security = Min(ec1->ec_min_security,
                                        restrictinfo->security_level);
             ec1->ec_max_security = Max(ec1->ec_max_security,
                                        restrictinfo->security_level);
             /* mark the RI as associated with this eclass */
             restrictinfo->left_ec = ec1;
             restrictinfo->right_ec = ec1;
             /* mark the RI as usable with this pair of EMs */
             restrictinfo->left_em = em1;
             restrictinfo->right_em = em2;
             return true;
         }
 
         /*
          * Case 2: need to merge ec1 and ec2.  This should never happen after
          * the ECs have reached canonical state; otherwise, pathkeys could be
          * rendered non-canonical by the merge, and relation eclass indexes
          * would get broken by removal of an eq_classes list entry.
          */
         if (root->ec_merging_done)
             elog(ERROR, "too late to merge equivalence classes");
 
         /*
          * We add ec2's items to ec1, then set ec2's ec_merged link to point
          * to ec1 and remove ec2 from the eq_classes list.  We cannot simply
          * delete ec2 because that could leave dangling pointers in existing
          * PathKeys.  We leave it behind with a link so that the merged EC can
          * be found.
          */
         ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
         ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
         ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
         ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
         ec1->ec_has_const |= ec2->ec_has_const;
         /* can't need to set has_volatile */
         ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
         ec1->ec_min_security = Min(ec1->ec_min_security,
                                    ec2->ec_min_security);
         ec1->ec_max_security = Max(ec1->ec_max_security,
                                    ec2->ec_max_security);
         ec2->ec_merged = ec1;
         root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
         /* just to avoid debugging confusion w/ dangling pointers: */
         ec2->ec_members = NIL;
         ec2->ec_sources = NIL;
         ec2->ec_derives = NIL;
         ec2->ec_relids = NULL;
         ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
         ec1->ec_below_outer_join |= below_outer_join;
         ec1->ec_min_security = Min(ec1->ec_min_security,
                                    restrictinfo->security_level);
         ec1->ec_max_security = Max(ec1->ec_max_security,
                                    restrictinfo->security_level);
         /* mark the RI as associated with this eclass */
         restrictinfo->left_ec = ec1;
         restrictinfo->right_ec = ec1;
         /* mark the RI as usable with this pair of EMs */
         restrictinfo->left_em = em1;
         restrictinfo->right_em = em2;
     }
     else if (ec1)
     {
         /* Case 3: add item2 to ec1 */
         em2 = add_eq_member(ec1, item2, item2_relids, item2_nullable_relids,
                             false, item2_type);
         ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
         ec1->ec_below_outer_join |= below_outer_join;
         ec1->ec_min_security = Min(ec1->ec_min_security,
                                    restrictinfo->security_level);
         ec1->ec_max_security = Max(ec1->ec_max_security,
                                    restrictinfo->security_level);
         /* mark the RI as associated with this eclass */
         restrictinfo->left_ec = ec1;
         restrictinfo->right_ec = ec1;
         /* mark the RI as usable with this pair of EMs */
         restrictinfo->left_em = em1;
         restrictinfo->right_em = em2;
     }
     else if (ec2)
     {
         /* Case 3: add item1 to ec2 */
         em1 = add_eq_member(ec2, item1, item1_relids, item1_nullable_relids,
                             false, item1_type);
         ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
         ec2->ec_below_outer_join |= below_outer_join;
         ec2->ec_min_security = Min(ec2->ec_min_security,
                                    restrictinfo->security_level);
         ec2->ec_max_security = Max(ec2->ec_max_security,
                                    restrictinfo->security_level);
         /* mark the RI as associated with this eclass */
         restrictinfo->left_ec = ec2;
         restrictinfo->right_ec = ec2;
         /* mark the RI as usable with this pair of EMs */
         restrictinfo->left_em = em1;
         restrictinfo->right_em = em2;
     }
     else
     {
         /* Case 4: make a new, two-entry EC */
         EquivalenceClass *ec = makeNode(EquivalenceClass);
 
         ec->ec_opfamilies = opfamilies;
         ec->ec_collation = collation;
         ec->ec_members = NIL;
         ec->ec_sources = list_make1(restrictinfo);
         ec->ec_derives = NIL;
         ec->ec_relids = NULL;
         ec->ec_has_const = false;
         ec->ec_has_volatile = false;
         ec->ec_below_outer_join = below_outer_join;
         ec->ec_broken = false;
         ec->ec_sortref = 0;
         ec->ec_min_security = restrictinfo->security_level;
         ec->ec_max_security = restrictinfo->security_level;
         ec->ec_merged = NULL;
         em1 = add_eq_member(ec, item1, item1_relids, item1_nullable_relids,
                             false, item1_type);
         em2 = add_eq_member(ec, item2, item2_relids, item2_nullable_relids,
                             false, item2_type);
 
         root->eq_classes = lappend(root->eq_classes, ec);
 
         /* mark the RI as associated with this eclass */
         restrictinfo->left_ec = ec;
         restrictinfo->right_ec = ec;
         /* mark the RI as usable with this pair of EMs */
         restrictinfo->left_em = em1;
         restrictinfo->right_em = em2;
     }
 
     return true;
 }

◆ reconsider_full_join_clause()

static bool reconsider_full_join_clause	(	PlannerInfo *	root,
		RestrictInfo *	rinfo
	)

static

Definition at line 1908 of file equivclass.c.

References CoalesceExpr::args, Assert, bms_copy(), bms_intersect(), build_implied_join_equality(), RestrictInfo::clause, EquivalenceClass::ec_collation, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, PlannerInfo::eq_classes, equal(), get_leftop(), get_rightop(), is_opclause(), IsA, RestrictInfo::left_relids, lfirst, linitial, list_delete_ptr(), list_length(), lsecond, RestrictInfo::mergeopfamilies, RestrictInfo::nullable_relids, OidIsValid, op_input_types(), RestrictInfo::outerjoin_delayed, process_equivalence(), RestrictInfo::right_relids, and select_equality_operator().

Referenced by reconsider_outer_join_clauses().

 {
     Expr       *leftvar;
     Expr       *rightvar;
     Oid         opno,
                 collation,
                 left_type,
                 right_type;
     Relids      left_relids,
                 right_relids,
                 left_nullable_relids,
                 right_nullable_relids;
     ListCell   *lc1;
 
     /* Can't use an outerjoin_delayed clause here */
     if (rinfo->outerjoin_delayed)
         return false;
 
     /* Extract needed info from the clause */
     Assert(is_opclause(rinfo->clause));
     opno = ((OpExpr *) rinfo->clause)->opno;
     collation = ((OpExpr *) rinfo->clause)->inputcollid;
     op_input_types(opno, &left_type, &right_type);
     leftvar = (Expr *) get_leftop(rinfo->clause);
     rightvar = (Expr *) get_rightop(rinfo->clause);
     left_relids = rinfo->left_relids;
     right_relids = rinfo->right_relids;
     left_nullable_relids = bms_intersect(left_relids,
                                          rinfo->nullable_relids);
     right_nullable_relids = bms_intersect(right_relids,
                                           rinfo->nullable_relids);
 
     foreach(lc1, root->eq_classes)
     {
         EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
         EquivalenceMember *coal_em = NULL;
         bool        match;
         bool        matchleft;
         bool        matchright;
         ListCell   *lc2;
 
         /* Ignore EC unless it contains pseudoconstants */
         if (!cur_ec->ec_has_const)
             continue;
         /* Never match to a volatile EC */
         if (cur_ec->ec_has_volatile)
             continue;
         /* It has to match the outer-join clause as to semantics, too */
         if (collation != cur_ec->ec_collation)
             continue;
         if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
             continue;
 
         /*
          * Does it contain a COALESCE(leftvar, rightvar) construct?
          *
          * We can assume the COALESCE() inputs are in the same order as the
          * join clause, since both were automatically generated in the cases
          * we care about.
          *
          * XXX currently this may fail to match in cross-type cases because
          * the COALESCE will contain typecast operations while the join clause
          * may not (if there is a cross-type mergejoin operator available for
          * the two column types). Is it OK to strip implicit coercions from
          * the COALESCE arguments?
          */
         match = false;
         foreach(lc2, cur_ec->ec_members)
         {
             coal_em = (EquivalenceMember *) lfirst(lc2);
             Assert(!coal_em->em_is_child);  /* no children yet */
             if (IsA(coal_em->em_expr, CoalesceExpr))
             {
                 CoalesceExpr *cexpr = (CoalesceExpr *) coal_em->em_expr;
                 Node       *cfirst;
                 Node       *csecond;
 
                 if (list_length(cexpr->args) != 2)
                     continue;
                 cfirst = (Node *) linitial(cexpr->args);
                 csecond = (Node *) lsecond(cexpr->args);
 
                 if (equal(leftvar, cfirst) && equal(rightvar, csecond))
                 {
                     match = true;
                     break;
                 }
             }
         }
         if (!match)
             continue;           /* no match, so ignore this EC */
 
         /*
          * Yes it does!  Try to generate clauses LEFTVAR = CONSTANT and
          * RIGHTVAR = CONSTANT for each CONSTANT in the EC.  Note that we must
          * succeed with at least one constant for each var before we can
          * decide to throw away the outer-join clause.
          */
         matchleft = matchright = false;
         foreach(lc2, cur_ec->ec_members)
         {
             EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
             Oid         eq_op;
             RestrictInfo *newrinfo;
 
             if (!cur_em->em_is_const)
                 continue;       /* ignore non-const members */
             eq_op = select_equality_operator(cur_ec,
                                              left_type,
                                              cur_em->em_datatype);
             if (OidIsValid(eq_op))
             {
                 newrinfo = build_implied_join_equality(eq_op,
                                                        cur_ec->ec_collation,
                                                        leftvar,
                                                        cur_em->em_expr,
                                                        bms_copy(left_relids),
                                                        bms_copy(left_nullable_relids),
                                                        cur_ec->ec_min_security);
                 if (process_equivalence(root, &newrinfo, true))
                     matchleft = true;
             }
             eq_op = select_equality_operator(cur_ec,
                                              right_type,
                                              cur_em->em_datatype);
             if (OidIsValid(eq_op))
             {
                 newrinfo = build_implied_join_equality(eq_op,
                                                        cur_ec->ec_collation,
                                                        rightvar,
                                                        cur_em->em_expr,
                                                        bms_copy(right_relids),
                                                        bms_copy(right_nullable_relids),
                                                        cur_ec->ec_min_security);
                 if (process_equivalence(root, &newrinfo, true))
                     matchright = true;
             }
         }
 
         /*
          * If we were able to equate both vars to constants, we're done, and
          * we can throw away the full-join clause as redundant.  Moreover, we
          * can remove the COALESCE entry from the EC, since the added
          * restrictions ensure it will always have the expected value. (We
          * don't bother trying to update ec_relids or ec_sources.)
          */
         if (matchleft && matchright)
         {
             cur_ec->ec_members = list_delete_ptr(cur_ec->ec_members, coal_em);
             return true;
         }
 
         /*
          * Otherwise, fall out of the search loop, since we know the COALESCE
          * appears in at most one EC (XXX might stop being true if we allow
          * stripping of coercions above?)
          */
         break;
     }
 
     return false;               /* failed to make any deduction */
 }

◆ reconsider_outer_join_clause()

static bool reconsider_outer_join_clause	(	PlannerInfo *	root,
		RestrictInfo *	rinfo,
		bool	outer_on_left
	)

static

Definition at line 1783 of file equivclass.c.

References Assert, bms_copy(), bms_intersect(), build_implied_join_equality(), RestrictInfo::clause, EquivalenceClass::ec_collation, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, PlannerInfo::eq_classes, equal(), get_leftop(), get_rightop(), is_opclause(), RestrictInfo::left_relids, lfirst, RestrictInfo::mergeopfamilies, RestrictInfo::nullable_relids, OidIsValid, op_input_types(), op_strict(), RestrictInfo::outerjoin_delayed, process_equivalence(), RestrictInfo::right_relids, and select_equality_operator().

Referenced by reconsider_outer_join_clauses().

 {
     Expr       *outervar,
                *innervar;
     Oid         opno,
                 collation,
                 left_type,
                 right_type,
                 inner_datatype;
     Relids      inner_relids,
                 inner_nullable_relids;
     ListCell   *lc1;
 
     Assert(is_opclause(rinfo->clause));
     opno = ((OpExpr *) rinfo->clause)->opno;
     collation = ((OpExpr *) rinfo->clause)->inputcollid;
 
     /* If clause is outerjoin_delayed, operator must be strict */
     if (rinfo->outerjoin_delayed && !op_strict(opno))
         return false;
 
     /* Extract needed info from the clause */
     op_input_types(opno, &left_type, &right_type);
     if (outer_on_left)
     {
         outervar = (Expr *) get_leftop(rinfo->clause);
         innervar = (Expr *) get_rightop(rinfo->clause);
         inner_datatype = right_type;
         inner_relids = rinfo->right_relids;
     }
     else
     {
         outervar = (Expr *) get_rightop(rinfo->clause);
         innervar = (Expr *) get_leftop(rinfo->clause);
         inner_datatype = left_type;
         inner_relids = rinfo->left_relids;
     }
     inner_nullable_relids = bms_intersect(inner_relids,
                                           rinfo->nullable_relids);
 
     /* Scan EquivalenceClasses for a match to outervar */
     foreach(lc1, root->eq_classes)
     {
         EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
         bool        match;
         ListCell   *lc2;
 
         /* Ignore EC unless it contains pseudoconstants */
         if (!cur_ec->ec_has_const)
             continue;
         /* Never match to a volatile EC */
         if (cur_ec->ec_has_volatile)
             continue;
         /* It has to match the outer-join clause as to semantics, too */
         if (collation != cur_ec->ec_collation)
             continue;
         if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies))
             continue;
         /* Does it contain a match to outervar? */
         match = false;
         foreach(lc2, cur_ec->ec_members)
         {
             EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
 
             Assert(!cur_em->em_is_child);   /* no children yet */
             if (equal(outervar, cur_em->em_expr))
             {
                 match = true;
                 break;
             }
         }
         if (!match)
             continue;           /* no match, so ignore this EC */
 
         /*
          * Yes it does!  Try to generate a clause INNERVAR = CONSTANT for each
          * CONSTANT in the EC.  Note that we must succeed with at least one
          * constant before we can decide to throw away the outer-join clause.
          */
         match = false;
         foreach(lc2, cur_ec->ec_members)
         {
             EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
             Oid         eq_op;
             RestrictInfo *newrinfo;
 
             if (!cur_em->em_is_const)
                 continue;       /* ignore non-const members */
             eq_op = select_equality_operator(cur_ec,
                                              inner_datatype,
                                              cur_em->em_datatype);
             if (!OidIsValid(eq_op))
                 continue;       /* can't generate equality */
             newrinfo = build_implied_join_equality(eq_op,
                                                    cur_ec->ec_collation,
                                                    innervar,
                                                    cur_em->em_expr,
                                                    bms_copy(inner_relids),
                                                    bms_copy(inner_nullable_relids),
                                                    cur_ec->ec_min_security);
             if (process_equivalence(root, &newrinfo, true))
                 match = true;
         }
 
         /*
          * If we were able to equate INNERVAR to any constant, report success.
          * Otherwise, fall out of the search loop, since we know the OUTERVAR
          * appears in at most one EC.
          */
         if (match)
             return true;
         else
             break;
     }
 
     return false;               /* failed to make any deduction */
 }

◆ reconsider_outer_join_clauses()

void reconsider_outer_join_clauses ( PlannerInfo * root )

Definition at line 1688 of file equivclass.c.

References distribute_restrictinfo_to_rels(), foreach_delete_current, PlannerInfo::full_join_clauses, PlannerInfo::left_join_clauses, lfirst, RestrictInfo::norm_selec, RestrictInfo::outer_selec, reconsider_full_join_clause(), reconsider_outer_join_clause(), and PlannerInfo::right_join_clauses.

Referenced by query_planner().

 {
     bool        found;
     ListCell   *cell;
 
     /* Outer loop repeats until we find no more deductions */
     do
     {
         found = false;
 
         /* Process the LEFT JOIN clauses */
         foreach(cell, root->left_join_clauses)
         {
             RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
             if (reconsider_outer_join_clause(root, rinfo, true))
             {
                 found = true;
                 /* remove it from the list */
                 root->left_join_clauses =
                     foreach_delete_current(root->left_join_clauses, cell);
                 /* we throw it back anyway (see notes above) */
                 /* but the thrown-back clause has no extra selectivity */
                 rinfo->norm_selec = 2.0;
                 rinfo->outer_selec = 1.0;
                 distribute_restrictinfo_to_rels(root, rinfo);
             }
         }
 
         /* Process the RIGHT JOIN clauses */
         foreach(cell, root->right_join_clauses)
         {
             RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
             if (reconsider_outer_join_clause(root, rinfo, false))
             {
                 found = true;
                 /* remove it from the list */
                 root->right_join_clauses =
                     foreach_delete_current(root->right_join_clauses, cell);
                 /* we throw it back anyway (see notes above) */
                 /* but the thrown-back clause has no extra selectivity */
                 rinfo->norm_selec = 2.0;
                 rinfo->outer_selec = 1.0;
                 distribute_restrictinfo_to_rels(root, rinfo);
             }
         }
 
         /* Process the FULL JOIN clauses */
         foreach(cell, root->full_join_clauses)
         {
             RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
             if (reconsider_full_join_clause(root, rinfo))
             {
                 found = true;
                 /* remove it from the list */
                 root->full_join_clauses =
                     foreach_delete_current(root->full_join_clauses, cell);
                 /* we throw it back anyway (see notes above) */
                 /* but the thrown-back clause has no extra selectivity */
                 rinfo->norm_selec = 2.0;
                 rinfo->outer_selec = 1.0;
                 distribute_restrictinfo_to_rels(root, rinfo);
             }
         }
     } while (found);
 
     /* Now, any remaining clauses have to be thrown back */
     foreach(cell, root->left_join_clauses)
     {
         RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
         distribute_restrictinfo_to_rels(root, rinfo);
     }
     foreach(cell, root->right_join_clauses)
     {
         RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
         distribute_restrictinfo_to_rels(root, rinfo);
     }
     foreach(cell, root->full_join_clauses)
     {
         RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
 
         distribute_restrictinfo_to_rels(root, rinfo);
     }
 }

◆ select_equality_operator()

static Oid select_equality_operator	(	EquivalenceClass *	ec,
		Oid	lefttype,
		Oid	righttype
	)

static

Definition at line 1500 of file equivclass.c.

References BTEqualStrategyNumber, EquivalenceClass::ec_max_security, EquivalenceClass::ec_opfamilies, get_func_leakproof(), get_opcode(), get_opfamily_member(), InvalidOid, lfirst_oid, and OidIsValid.

Referenced by generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), generate_implied_equalities_for_column(), generate_join_implied_equalities_normal(), reconsider_full_join_clause(), and reconsider_outer_join_clause().

 {
     ListCell   *lc;
 
     foreach(lc, ec->ec_opfamilies)
     {
         Oid         opfamily = lfirst_oid(lc);
         Oid         opno;
 
         opno = get_opfamily_member(opfamily, lefttype, righttype,
                                    BTEqualStrategyNumber);
         if (!OidIsValid(opno))
             continue;
         /* If no barrier quals in query, don't worry about leaky operators */
         if (ec->ec_max_security == 0)
             return opno;
         /* Otherwise, insist that selected operators be leakproof */
         if (get_func_leakproof(get_opcode(opno)))
             return opno;
     }
     return InvalidOid;
 }

Functions

Function Documentation

◆ add_child_rel_equivalences()

◆ add_eq_member()

◆ canonicalize_ec_expression()

◆ create_join_clause()

◆ eclass_useful_for_merging()

◆ exprs_known_equal()

◆ generate_base_implied_equalities()

◆ generate_base_implied_equalities_broken()

◆ generate_base_implied_equalities_const()

◆ generate_base_implied_equalities_no_const()

◆ generate_implied_equalities_for_column()

◆ generate_join_implied_equalities()

◆ generate_join_implied_equalities_broken()

◆ generate_join_implied_equalities_for_ecs()

◆ generate_join_implied_equalities_normal()

◆ get_common_eclass_indexes()

◆ get_eclass_for_sort_expr()

◆ get_eclass_indexes_for_relids()

◆ has_relevant_eclass_joinclause()

◆ have_relevant_eclass_joinclause()

◆ is_redundant_derived_clause()

◆ is_redundant_with_indexclauses()

◆ match_eclasses_to_foreign_key_col()

◆ process_equivalence()

◆ reconsider_full_join_clause()

◆ reconsider_outer_join_clause()

◆ reconsider_outer_join_clauses()

◆ select_equality_operator()