#include "nodes/pathnodes.h"

Include dependency graph for paths.h:

This graph shows which files directly or indirectly include this file:

Typedefs
typedef void(*	set_rel_pathlist_hook_type) (PlannerInfo root, RelOptInfo rel, Index rti, RangeTblEntry *rte)

typedef void(*	set_join_pathlist_hook_type) (PlannerInfo root, RelOptInfo joinrel, RelOptInfo outerrel, RelOptInfo innerrel, JoinType jointype, JoinPathExtraData *extra)

typedef RelOptInfo (	join_search_hook_type) (PlannerInfo root, int levels_needed, List initial_rels)

typedef bool(*	ec_matches_callback_type) (PlannerInfo root, RelOptInfo rel, EquivalenceClass ec, EquivalenceMember em, void *arg)

Enumerations
enum	PathKeysComparison { PATHKEYS_EQUAL , PATHKEYS_BETTER1 , PATHKEYS_BETTER2 , PATHKEYS_DIFFERENT }

Functions
RelOptInfo *	make_one_rel (PlannerInfo root, List joinlist)

RelOptInfo *	standard_join_search (PlannerInfo root, int levels_needed, List initial_rels)

void	generate_gather_paths (PlannerInfo root, RelOptInfo rel, bool override_rows)

void	generate_useful_gather_paths (PlannerInfo root, RelOptInfo rel, bool override_rows)

int	compute_parallel_worker (RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)

void	create_partial_bitmap_paths (PlannerInfo root, RelOptInfo rel, Path *bitmapqual)

void	generate_partitionwise_join_paths (PlannerInfo root, RelOptInfo rel)

void	create_index_paths (PlannerInfo root, RelOptInfo rel)

bool	relation_has_unique_index_for (PlannerInfo root, RelOptInfo rel, List restrictlist, List exprlist, List *oprlist)

bool	indexcol_is_bool_constant_for_query (PlannerInfo root, IndexOptInfo index, int indexcol)

bool	match_index_to_operand (Node operand, int indexcol, IndexOptInfo index)

void	check_index_predicates (PlannerInfo root, RelOptInfo rel)

void	create_tidscan_paths (PlannerInfo root, RelOptInfo rel)

void	add_paths_to_joinrel (PlannerInfo root, RelOptInfo joinrel, RelOptInfo outerrel, RelOptInfo innerrel, JoinType jointype, SpecialJoinInfo sjinfo, List restrictlist)

void	join_search_one_level (PlannerInfo *root, int level)

RelOptInfo *	make_join_rel (PlannerInfo root, RelOptInfo rel1, RelOptInfo *rel2)

Relids	add_outer_joins_to_relids (PlannerInfo root, Relids input_relids, SpecialJoinInfo sjinfo, List **pushed_down_joins)

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

bool	have_dangerous_phv (PlannerInfo *root, Relids outer_relids, Relids inner_params)

void	mark_dummy_rel (RelOptInfo *rel)

bool	process_equivalence (PlannerInfo root, RestrictInfo p_restrictinfo, JoinDomain jdomain)

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

void	reconsider_outer_join_clauses (PlannerInfo *root)

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

EquivalenceMember *	find_ec_member_matching_expr (EquivalenceClass ec, Expr expr, Relids relids)

EquivalenceMember *	find_computable_ec_member (PlannerInfo root, EquivalenceClass ec, List *exprs, Relids relids, bool require_parallel_safe)

bool	relation_can_be_sorted_early (PlannerInfo root, RelOptInfo rel, EquivalenceClass *ec, bool require_parallel_safe)

void	generate_base_implied_equalities (PlannerInfo *root)

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

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

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

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

RestrictInfo *	find_derived_clause_for_ec_member (EquivalenceClass ec, EquivalenceMember em)

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

void	add_child_join_rel_equivalences (PlannerInfo root, int nappinfos, AppendRelInfo appinfos, RelOptInfo parent_joinrel, RelOptInfo *child_joinrel)

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)

PathKeysComparison	compare_pathkeys (List keys1, List keys2)

bool	pathkeys_contained_in (List keys1, List keys2)

bool	pathkeys_count_contained_in (List keys1, List keys2, int *n_common)

Path *	get_cheapest_path_for_pathkeys (List paths, List pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)

Path *	get_cheapest_fractional_path_for_pathkeys (List paths, List pathkeys, Relids required_outer, double fraction)

Path *	get_cheapest_parallel_safe_total_inner (List *paths)

List *	build_index_pathkeys (PlannerInfo root, IndexOptInfo index, ScanDirection scandir)

List *	build_partition_pathkeys (PlannerInfo root, RelOptInfo partrel, ScanDirection scandir, bool *partialkeys)

List *	build_expression_pathkey (PlannerInfo root, Expr expr, Oid opno, Relids rel, bool create_it)

List *	convert_subquery_pathkeys (PlannerInfo root, RelOptInfo rel, List subquery_pathkeys, List subquery_tlist)

List *	build_join_pathkeys (PlannerInfo root, RelOptInfo joinrel, JoinType jointype, List *outer_pathkeys)

List *	make_pathkeys_for_sortclauses (PlannerInfo root, List sortclauses, List *tlist)

List *	make_pathkeys_for_sortclauses_extended (PlannerInfo root, List sortclauses, List tlist, bool remove_redundant, bool *sortable)

void	initialize_mergeclause_eclasses (PlannerInfo root, RestrictInfo restrictinfo)

void	update_mergeclause_eclasses (PlannerInfo root, RestrictInfo restrictinfo)

List *	find_mergeclauses_for_outer_pathkeys (PlannerInfo root, List pathkeys, List *restrictinfos)

List *	select_outer_pathkeys_for_merge (PlannerInfo root, List mergeclauses, RelOptInfo *joinrel)

List *	make_inner_pathkeys_for_merge (PlannerInfo root, List mergeclauses, List *outer_pathkeys)

List *	trim_mergeclauses_for_inner_pathkeys (PlannerInfo root, List mergeclauses, List *pathkeys)

List *	truncate_useless_pathkeys (PlannerInfo root, RelOptInfo rel, List *pathkeys)

bool	has_useful_pathkeys (PlannerInfo root, RelOptInfo rel)

List *	append_pathkeys (List target, List source)

PathKey *	make_canonical_pathkey (PlannerInfo root, EquivalenceClass eclass, Oid opfamily, int strategy, bool nulls_first)

void	add_paths_to_append_rel (PlannerInfo root, RelOptInfo rel, List *live_childrels)

Variables
PGDLLIMPORT bool	enable_geqo

PGDLLIMPORT int	geqo_threshold

PGDLLIMPORT int	min_parallel_table_scan_size

PGDLLIMPORT int	min_parallel_index_scan_size

PGDLLIMPORT set_rel_pathlist_hook_type	set_rel_pathlist_hook

PGDLLIMPORT set_join_pathlist_hook_type	set_join_pathlist_hook

PGDLLIMPORT join_search_hook_type	join_search_hook

Typedef Documentation

◆ ec_matches_callback_type

typedef bool(* ec_matches_callback_type) (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)

Definition at line 120 of file paths.h.

◆ join_search_hook_type

typedef RelOptInfo*(* join_search_hook_type) (PlannerInfo *root, int levels_needed, List *initial_rels)

Definition at line 45 of file paths.h.

◆ set_join_pathlist_hook_type

typedef void(* set_join_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)

Definition at line 36 of file paths.h.

◆ set_rel_pathlist_hook_type

typedef void(* set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte)

Definition at line 29 of file paths.h.

Enumeration Type Documentation

◆ PathKeysComparison

enum PathKeysComparison

Enumerator
PATHKEYS_EQUAL
PATHKEYS_BETTER1
PATHKEYS_BETTER2
PATHKEYS_DIFFERENT

Definition at line 197 of file paths.h.

 {
     PATHKEYS_EQUAL,             /* pathkeys are identical */
     PATHKEYS_BETTER1,           /* pathkey 1 is a superset of pathkey 2 */
     PATHKEYS_BETTER2,           /* vice versa */
     PATHKEYS_DIFFERENT          /* neither pathkey includes the other */
 } PathKeysComparison;

Function Documentation

◆ add_child_join_rel_equivalences()

void add_child_join_rel_equivalences	(	PlannerInfo *	root,
		int	nappinfos,
		AppendRelInfo **	appinfos,
		RelOptInfo *	parent_joinrel,
		RelOptInfo *	child_joinrel
	)

Definition at line 2743 of file equivclass.c.

 {
     Relids      top_parent_relids = child_joinrel->top_parent_relids;
     Relids      child_relids = child_joinrel->relids;
     Bitmapset  *matching_ecs;
     MemoryContext oldcontext;
     int         i;
  
     Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
  
     /* We need consider only ECs that mention the parent joinrel */
     matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
  
     /*
      * If we're being called during GEQO join planning, we still have to
      * create any new EC members in the main planner context, to avoid having
      * a corrupt EC data structure after the GEQO context is reset.  This is
      * problematic since we'll leak memory across repeated GEQO cycles.  For
      * now, though, bloat is better than crash.  If it becomes a real issue
      * we'll have to do something to avoid generating duplicate EC members.
      */
     oldcontext = MemoryContextSwitchTo(root->planner_cxt);
  
     i = -1;
     while ((i = bms_next_member(matching_ecs, 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 on get_eclass_indexes_for_relids result */
         Assert(bms_overlap(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.
              */
             if (cur_em->em_is_child)
                 continue;       /* ignore children here */
  
             /*
              * We may ignore expressions that reference a single baserel,
              * because add_child_rel_equivalences should have handled them.
              */
             if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
                 continue;
  
             /* Does this member reference child's topmost parent rel? */
             if (bms_overlap(cur_em->em_relids, top_parent_relids))
             {
                 /* Yes, generate transformed child version */
                 Expr       *child_expr;
                 Relids      new_relids;
  
                 if (parent_joinrel->reloptkind == RELOPT_JOINREL)
                 {
                     /* Simple single-level transformation */
                     child_expr = (Expr *)
                         adjust_appendrel_attrs(root,
                                                (Node *) cur_em->em_expr,
                                                nappinfos, appinfos);
                 }
                 else
                 {
                     /* Must do multi-level transformation */
                     Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
                     child_expr = (Expr *)
                         adjust_appendrel_attrs_multilevel(root,
                                                           (Node *) cur_em->em_expr,
                                                           child_joinrel,
                                                           child_joinrel->top_parent);
                 }
  
                 /*
                  * 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,
                                             top_parent_relids);
                 new_relids = bms_add_members(new_relids, child_relids);
  
                 (void) add_eq_member(cur_ec, child_expr, new_relids,
                                      cur_em->em_jdomain,
                                      cur_em, cur_em->em_datatype);
             }
         }
     }
  
     MemoryContextSwitchTo(oldcontext);
 }

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert(), bms_add_members(), bms_difference(), bms_membership(), BMS_MULTIPLE, bms_next_member(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, PlannerInfo::eq_classes, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_length(), list_nth(), MemoryContextSwitchTo(), RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, and RelOptInfo::top_parent_relids.

Referenced by build_child_join_rel().

◆ add_child_rel_equivalences()

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

Definition at line 2621 of file equivclass.c.

 {
     Relids      top_parent_relids = child_rel->top_parent_relids;
     Relids      child_relids = child_rel->relids;
     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(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.  (But add_child_join_rel_equivalences
              * may add targeted combinations for partitionwise-join purposes.)
              */
             if (cur_em->em_is_child)
                 continue;       /* ignore children here */
  
             /*
              * Consider only members that reference and can be computed at
              * child's topmost parent rel.  In particular we want to exclude
              * parent-rel Vars that have nonempty varnullingrels.  Translating
              * those might fail, if the transformed expression wouldn't be a
              * simple Var; and in any case it wouldn't produce a member that
              * has any use in creating plans for the child rel.
              */
             if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
                 !bms_is_empty(cur_em->em_relids))
             {
                 /* OK, generate transformed child version */
                 Expr       *child_expr;
                 Relids      new_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,
                                                           child_rel->top_parent);
                 }
  
                 /*
                  * 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,
                                             top_parent_relids);
                 new_relids = bms_add_members(new_relids, child_relids);
  
                 (void) add_eq_member(cur_ec, child_expr, new_relids,
                                      cur_em->em_jdomain,
                                      cur_em, cur_em->em_datatype);
  
                 /* Record this EC index for the child rel */
                 child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
             }
         }
     }
 }

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), Assert(), bms_add_member(), bms_add_members(), bms_difference(), bms_is_empty, bms_is_subset(), bms_next_member(), 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_jdomain, 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().

◆ add_outer_joins_to_relids()

Relids add_outer_joins_to_relids	(	PlannerInfo *	root,
		Relids	input_relids,
		SpecialJoinInfo *	sjinfo,
		List **	pushed_down_joins
	)

Definition at line 802 of file joinrels.c.

 {
     /* Nothing to do if this isn't an outer join with an assigned relid. */
     if (sjinfo == NULL || sjinfo->ojrelid == 0)
         return input_relids;
  
     /*
      * If it's not a left join, we have no rules that would permit executing
      * it in non-syntactic order, so just form the syntactic relid set.  (This
      * is just a quick-exit test; we'd come to the same conclusion anyway,
      * since its commute_below_l and commute_above_l sets must be empty.)
      */
     if (sjinfo->jointype != JOIN_LEFT)
         return bms_add_member(input_relids, sjinfo->ojrelid);
  
     /*
      * We cannot add the OJ relid if this join has been pushed into the RHS of
      * a syntactically-lower left join per OJ identity 3.  (If it has, then we
      * cannot claim that its outputs represent the final state of its RHS.)
      * There will not be any other OJs that can be added either, so we're
      * done.
      */
     if (!bms_is_subset(sjinfo->commute_below_l, input_relids))
         return input_relids;
  
     /* OK to add OJ's own relid */
     input_relids = bms_add_member(input_relids, sjinfo->ojrelid);
  
     /*
      * Contrariwise, if we are now forming the final result of such a commuted
      * pair of OJs, it's time to add the relid(s) of the pushed-down join(s).
      * We can skip this if this join was never a candidate to be pushed up.
      */
     if (sjinfo->commute_above_l)
     {
         Relids      commute_above_rels = bms_copy(sjinfo->commute_above_l);
         ListCell   *lc;
  
         /*
          * The current join could complete the nulling of more than one
          * pushed-down join, so we have to examine all the SpecialJoinInfos.
          * Because join_info_list was built in bottom-up order, it's
          * sufficient to traverse it once: an ojrelid we add in one loop
          * iteration would not have affected decisions of earlier iterations.
          */
         foreach(lc, root->join_info_list)
         {
             SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
  
             if (othersj == sjinfo ||
                 othersj->ojrelid == 0 || othersj->jointype != JOIN_LEFT)
                 continue;       /* definitely not interesting */
  
             if (!bms_is_member(othersj->ojrelid, commute_above_rels))
                 continue;
  
             /* Add it if not already present but conditions now satisfied */
             if (!bms_is_member(othersj->ojrelid, input_relids) &&
                 bms_is_subset(othersj->min_lefthand, input_relids) &&
                 bms_is_subset(othersj->min_righthand, input_relids) &&
                 bms_is_subset(othersj->commute_below_l, input_relids))
             {
                 input_relids = bms_add_member(input_relids, othersj->ojrelid);
                 /* report such pushed down outer joins, if asked */
                 if (pushed_down_joins != NULL)
                     *pushed_down_joins = lappend(*pushed_down_joins, othersj);
  
                 /*
                  * We must also check any joins that othersj potentially
                  * commutes with.  They likewise must appear later in
                  * join_info_list than othersj itself, so we can visit them
                  * later in this loop.
                  */
                 commute_above_rels = bms_add_members(commute_above_rels,
                                                      othersj->commute_above_l);
             }
         }
     }
  
     return input_relids;
 }

References bms_add_member(), bms_add_members(), bms_copy(), bms_is_member(), bms_is_subset(), SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_below_l, PlannerInfo::join_info_list, JOIN_LEFT, SpecialJoinInfo::jointype, lappend(), lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, and SpecialJoinInfo::ojrelid.

Referenced by build_child_join_rel(), generate_join_implied_equalities(), make_join_rel(), and try_partitionwise_join().

◆ add_paths_to_append_rel()

void add_paths_to_append_rel	(	PlannerInfo *	root,
		RelOptInfo *	rel,
		List *	live_childrels
	)

Definition at line 1305 of file allpaths.c.

 {
     List       *subpaths = NIL;
     bool        subpaths_valid = true;
     List       *partial_subpaths = NIL;
     List       *pa_partial_subpaths = NIL;
     List       *pa_nonpartial_subpaths = NIL;
     bool        partial_subpaths_valid = true;
     bool        pa_subpaths_valid;
     List       *all_child_pathkeys = NIL;
     List       *all_child_outers = NIL;
     ListCell   *l;
     double      partial_rows = -1;
  
     /* If appropriate, consider parallel append */
     pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;
  
     /*
      * For every non-dummy child, remember the cheapest path.  Also, identify
      * all pathkeys (orderings) and parameterizations (required_outer sets)
      * available for the non-dummy member relations.
      */
     foreach(l, live_childrels)
     {
         RelOptInfo *childrel = lfirst(l);
         ListCell   *lcp;
         Path       *cheapest_partial_path = NULL;
  
         /*
          * If child has an unparameterized cheapest-total path, add that to
          * the unparameterized Append path we are constructing for the parent.
          * If not, there's no workable unparameterized path.
          *
          * With partitionwise aggregates, the child rel's pathlist may be
          * empty, so don't assume that a path exists here.
          */
         if (childrel->pathlist != NIL &&
             childrel->cheapest_total_path->param_info == NULL)
             accumulate_append_subpath(childrel->cheapest_total_path,
                                       &subpaths, NULL);
         else
             subpaths_valid = false;
  
         /* Same idea, but for a partial plan. */
         if (childrel->partial_pathlist != NIL)
         {
             cheapest_partial_path = linitial(childrel->partial_pathlist);
             accumulate_append_subpath(cheapest_partial_path,
                                       &partial_subpaths, NULL);
         }
         else
             partial_subpaths_valid = false;
  
         /*
          * Same idea, but for a parallel append mixing partial and non-partial
          * paths.
          */
         if (pa_subpaths_valid)
         {
             Path       *nppath = NULL;
  
             nppath =
                 get_cheapest_parallel_safe_total_inner(childrel->pathlist);
  
             if (cheapest_partial_path == NULL && nppath == NULL)
             {
                 /* Neither a partial nor a parallel-safe path?  Forget it. */
                 pa_subpaths_valid = false;
             }
             else if (nppath == NULL ||
                      (cheapest_partial_path != NULL &&
                       cheapest_partial_path->total_cost < nppath->total_cost))
             {
                 /* Partial path is cheaper or the only option. */
                 Assert(cheapest_partial_path != NULL);
                 accumulate_append_subpath(cheapest_partial_path,
                                           &pa_partial_subpaths,
                                           &pa_nonpartial_subpaths);
             }
             else
             {
                 /*
                  * Either we've got only a non-partial path, or we think that
                  * a single backend can execute the best non-partial path
                  * faster than all the parallel backends working together can
                  * execute the best partial path.
                  *
                  * It might make sense to be more aggressive here.  Even if
                  * the best non-partial path is more expensive than the best
                  * partial path, it could still be better to choose the
                  * non-partial path if there are several such paths that can
                  * be given to different workers.  For now, we don't try to
                  * figure that out.
                  */
                 accumulate_append_subpath(nppath,
                                           &pa_nonpartial_subpaths,
                                           NULL);
             }
         }
  
         /*
          * Collect lists of all the available path orderings and
          * parameterizations for all the children.  We use these as a
          * heuristic to indicate which sort orderings and parameterizations we
          * should build Append and MergeAppend paths for.
          */
         foreach(lcp, childrel->pathlist)
         {
             Path       *childpath = (Path *) lfirst(lcp);
             List       *childkeys = childpath->pathkeys;
             Relids      childouter = PATH_REQ_OUTER(childpath);
  
             /* Unsorted paths don't contribute to pathkey list */
             if (childkeys != NIL)
             {
                 ListCell   *lpk;
                 bool        found = false;
  
                 /* Have we already seen this ordering? */
                 foreach(lpk, all_child_pathkeys)
                 {
                     List       *existing_pathkeys = (List *) lfirst(lpk);
  
                     if (compare_pathkeys(existing_pathkeys,
                                          childkeys) == PATHKEYS_EQUAL)
                     {
                         found = true;
                         break;
                     }
                 }
                 if (!found)
                 {
                     /* No, so add it to all_child_pathkeys */
                     all_child_pathkeys = lappend(all_child_pathkeys,
                                                  childkeys);
                 }
             }
  
             /* Unparameterized paths don't contribute to param-set list */
             if (childouter)
             {
                 ListCell   *lco;
                 bool        found = false;
  
                 /* Have we already seen this param set? */
                 foreach(lco, all_child_outers)
                 {
                     Relids      existing_outers = (Relids) lfirst(lco);
  
                     if (bms_equal(existing_outers, childouter))
                     {
                         found = true;
                         break;
                     }
                 }
                 if (!found)
                 {
                     /* No, so add it to all_child_outers */
                     all_child_outers = lappend(all_child_outers,
                                                childouter);
                 }
             }
         }
     }
  
     /*
      * If we found unparameterized paths for all children, build an unordered,
      * unparameterized Append path for the rel.  (Note: this is correct even
      * if we have zero or one live subpath due to constraint exclusion.)
      */
     if (subpaths_valid)
         add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
                                                   NIL, NULL, 0, false,
                                                   -1));
  
     /*
      * Consider an append of unordered, unparameterized partial paths.  Make
      * it parallel-aware if possible.
      */
     if (partial_subpaths_valid && partial_subpaths != NIL)
     {
         AppendPath *appendpath;
         ListCell   *lc;
         int         parallel_workers = 0;
  
         /* Find the highest number of workers requested for any subpath. */
         foreach(lc, partial_subpaths)
         {
             Path       *path = lfirst(lc);
  
             parallel_workers = Max(parallel_workers, path->parallel_workers);
         }
         Assert(parallel_workers > 0);
  
         /*
          * If the use of parallel append is permitted, always request at least
          * log2(# of children) workers.  We assume it can be useful to have
          * extra workers in this case because they will be spread out across
          * the children.  The precise formula is just a guess, but we don't
          * want to end up with a radically different answer for a table with N
          * partitions vs. an unpartitioned table with the same data, so the
          * use of some kind of log-scaling here seems to make some sense.
          */
         if (enable_parallel_append)
         {
             parallel_workers = Max(parallel_workers,
                                    pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
             parallel_workers = Min(parallel_workers,
                                    max_parallel_workers_per_gather);
         }
         Assert(parallel_workers > 0);
  
         /* Generate a partial append path. */
         appendpath = create_append_path(root, rel, NIL, partial_subpaths,
                                         NIL, NULL, parallel_workers,
                                         enable_parallel_append,
                                         -1);
  
         /*
          * Make sure any subsequent partial paths use the same row count
          * estimate.
          */
         partial_rows = appendpath->path.rows;
  
         /* Add the path. */
         add_partial_path(rel, (Path *) appendpath);
     }
  
     /*
      * Consider a parallel-aware append using a mix of partial and non-partial
      * paths.  (This only makes sense if there's at least one child which has
      * a non-partial path that is substantially cheaper than any partial path;
      * otherwise, we should use the append path added in the previous step.)
      */
     if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
     {
         AppendPath *appendpath;
         ListCell   *lc;
         int         parallel_workers = 0;
  
         /*
          * Find the highest number of workers requested for any partial
          * subpath.
          */
         foreach(lc, pa_partial_subpaths)
         {
             Path       *path = lfirst(lc);
  
             parallel_workers = Max(parallel_workers, path->parallel_workers);
         }
  
         /*
          * Same formula here as above.  It's even more important in this
          * instance because the non-partial paths won't contribute anything to
          * the planned number of parallel workers.
          */
         parallel_workers = Max(parallel_workers,
                                pg_leftmost_one_pos32(list_length(live_childrels)) + 1);
         parallel_workers = Min(parallel_workers,
                                max_parallel_workers_per_gather);
         Assert(parallel_workers > 0);
  
         appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
                                         pa_partial_subpaths,
                                         NIL, NULL, parallel_workers, true,
                                         partial_rows);
         add_partial_path(rel, (Path *) appendpath);
     }
  
     /*
      * Also build unparameterized ordered append paths based on the collected
      * list of child pathkeys.
      */
     if (subpaths_valid)
         generate_orderedappend_paths(root, rel, live_childrels,
                                      all_child_pathkeys);
  
     /*
      * Build Append paths for each parameterization seen among the child rels.
      * (This may look pretty expensive, but in most cases of practical
      * interest, the child rels will expose mostly the same parameterizations,
      * so that not that many cases actually get considered here.)
      *
      * The Append node itself cannot enforce quals, so all qual checking must
      * be done in the child paths.  This means that to have a parameterized
      * Append path, we must have the exact same parameterization for each
      * child path; otherwise some children might be failing to check the
      * moved-down quals.  To make them match up, we can try to increase the
      * parameterization of lesser-parameterized paths.
      */
     foreach(l, all_child_outers)
     {
         Relids      required_outer = (Relids) lfirst(l);
         ListCell   *lcr;
  
         /* Select the child paths for an Append with this parameterization */
         subpaths = NIL;
         subpaths_valid = true;
         foreach(lcr, live_childrels)
         {
             RelOptInfo *childrel = (RelOptInfo *) lfirst(lcr);
             Path       *subpath;
  
             if (childrel->pathlist == NIL)
             {
                 /* failed to make a suitable path for this child */
                 subpaths_valid = false;
                 break;
             }
  
             subpath = get_cheapest_parameterized_child_path(root,
                                                             childrel,
                                                             required_outer);
             if (subpath == NULL)
             {
                 /* failed to make a suitable path for this child */
                 subpaths_valid = false;
                 break;
             }
             accumulate_append_subpath(subpath, &subpaths, NULL);
         }
  
         if (subpaths_valid)
             add_path(rel, (Path *)
                      create_append_path(root, rel, subpaths, NIL,
                                         NIL, required_outer, 0, false,
                                         -1));
     }
  
     /*
      * When there is only a single child relation, the Append path can inherit
      * any ordering available for the child rel's path, so that it's useful to
      * consider ordered partial paths.  Above we only considered the cheapest
      * partial path for each child, but let's also make paths using any
      * partial paths that have pathkeys.
      */
     if (list_length(live_childrels) == 1)
     {
         RelOptInfo *childrel = (RelOptInfo *) linitial(live_childrels);
  
         /* skip the cheapest partial path, since we already used that above */
         for_each_from(l, childrel->partial_pathlist, 1)
         {
             Path       *path = (Path *) lfirst(l);
             AppendPath *appendpath;
  
             /* skip paths with no pathkeys. */
             if (path->pathkeys == NIL)
                 continue;
  
             appendpath = create_append_path(root, rel, NIL, list_make1(path),
                                             NIL, NULL,
                                             path->parallel_workers, true,
                                             partial_rows);
             add_partial_path(rel, (Path *) appendpath);
         }
     }
 }

References accumulate_append_subpath(), add_partial_path(), add_path(), Assert(), bms_equal(), RelOptInfo::cheapest_total_path, compare_pathkeys(), RelOptInfo::consider_parallel, create_append_path(), enable_parallel_append, for_each_from, generate_orderedappend_paths(), get_cheapest_parallel_safe_total_inner(), get_cheapest_parameterized_child_path(), lappend(), lfirst, linitial, list_length(), list_make1, Max, max_parallel_workers_per_gather, Min, NIL, Path::parallel_workers, RelOptInfo::partial_pathlist, AppendPath::path, PATH_REQ_OUTER, Path::pathkeys, PATHKEYS_EQUAL, RelOptInfo::pathlist, pg_leftmost_one_pos32(), Path::rows, subpath(), and Path::total_cost.

Referenced by apply_scanjoin_target_to_paths(), create_partitionwise_grouping_paths(), generate_partitionwise_join_paths(), and set_append_rel_pathlist().

◆ add_paths_to_joinrel()

void add_paths_to_joinrel	(	PlannerInfo *	root,
		RelOptInfo *	joinrel,
		RelOptInfo *	outerrel,
		RelOptInfo *	innerrel,
		JoinType	jointype,
		SpecialJoinInfo *	sjinfo,
		List *	restrictlist
	)

Definition at line 123 of file joinpath.c.

 {
     JoinPathExtraData extra;
     bool        mergejoin_allowed = true;
     ListCell   *lc;
     Relids      joinrelids;
  
     /*
      * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
      * between child relations, even if there is a SpecialJoinInfo node for
      * the join between the topmost parents. So, while calculating Relids set
      * representing the restriction, consider relids of topmost parent of
      * partitions.
      */
     if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
         joinrelids = joinrel->top_parent_relids;
     else
         joinrelids = joinrel->relids;
  
     extra.restrictlist = restrictlist;
     extra.mergeclause_list = NIL;
     extra.sjinfo = sjinfo;
     extra.param_source_rels = NULL;
  
     /*
      * See if the inner relation is provably unique for this outer rel.
      *
      * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
      * matter since the executor can make the equivalent optimization anyway;
      * we need not expend planner cycles on proofs.  For JOIN_UNIQUE_INNER, we
      * must be considering a semijoin whose inner side is not provably unique
      * (else reduce_unique_semijoins would've simplified it), so there's no
      * point in calling innerrel_is_unique.  However, if the LHS covers all of
      * the semijoin's min_lefthand, then it's appropriate to set inner_unique
      * because the path produced by create_unique_path will be unique relative
      * to the LHS.  (If we have an LHS that's only part of the min_lefthand,
      * that is *not* true.)  For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
      * letting that value escape this module.
      */
     switch (jointype)
     {
         case JOIN_SEMI:
         case JOIN_ANTI:
  
             /*
              * XXX it may be worth proving this to allow a Memoize to be
              * considered for Nested Loop Semi/Anti Joins.
              */
             extra.inner_unique = false; /* well, unproven */
             break;
         case JOIN_UNIQUE_INNER:
             extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
                                                outerrel->relids);
             break;
         case JOIN_UNIQUE_OUTER:
             extra.inner_unique = innerrel_is_unique(root,
                                                     joinrel->relids,
                                                     outerrel->relids,
                                                     innerrel,
                                                     JOIN_INNER,
                                                     restrictlist,
                                                     false);
             break;
         default:
             extra.inner_unique = innerrel_is_unique(root,
                                                     joinrel->relids,
                                                     outerrel->relids,
                                                     innerrel,
                                                     jointype,
                                                     restrictlist,
                                                     false);
             break;
     }
  
     /*
      * Find potential mergejoin clauses.  We can skip this if we are not
      * interested in doing a mergejoin.  However, mergejoin may be our only
      * way of implementing a full outer join, so override enable_mergejoin if
      * it's a full join.
      */
     if (enable_mergejoin || jointype == JOIN_FULL)
         extra.mergeclause_list = select_mergejoin_clauses(root,
                                                           joinrel,
                                                           outerrel,
                                                           innerrel,
                                                           restrictlist,
                                                           jointype,
                                                           &mergejoin_allowed);
  
     /*
      * If it's SEMI, ANTI, or inner_unique join, compute correction factors
      * for cost estimation.  These will be the same for all paths.
      */
     if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
         compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
                                        jointype, sjinfo, restrictlist,
                                        &extra.semifactors);
  
     /*
      * Decide whether it's sensible to generate parameterized paths for this
      * joinrel, and if so, which relations such paths should require.  There
      * is usually no need to create a parameterized result path unless there
      * is a join order restriction that prevents joining one of our input rels
      * directly to the parameter source rel instead of joining to the other
      * input rel.  (But see allow_star_schema_join().)  This restriction
      * reduces the number of parameterized paths we have to deal with at
      * higher join levels, without compromising the quality of the resulting
      * plan.  We express the restriction as a Relids set that must overlap the
      * parameterization of any proposed join path.  Note: param_source_rels
      * should contain only baserels, not OJ relids, so starting from
      * all_baserels not all_query_rels is correct.
      */
     foreach(lc, root->join_info_list)
     {
         SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
  
         /*
          * SJ is relevant to this join if we have some part of its RHS
          * (possibly not all of it), and haven't yet joined to its LHS.  (This
          * test is pretty simplistic, but should be sufficient considering the
          * join has already been proven legal.)  If the SJ is relevant, it
          * presents constraints for joining to anything not in its RHS.
          */
         if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
             !bms_overlap(joinrelids, sjinfo2->min_lefthand))
             extra.param_source_rels = bms_join(extra.param_source_rels,
                                                bms_difference(root->all_baserels,
                                                               sjinfo2->min_righthand));
  
         /* full joins constrain both sides symmetrically */
         if (sjinfo2->jointype == JOIN_FULL &&
             bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
             !bms_overlap(joinrelids, sjinfo2->min_righthand))
             extra.param_source_rels = bms_join(extra.param_source_rels,
                                                bms_difference(root->all_baserels,
                                                               sjinfo2->min_lefthand));
     }
  
     /*
      * However, when a LATERAL subquery is involved, there will simply not be
      * any paths for the joinrel that aren't parameterized by whatever the
      * subquery is parameterized by, unless its parameterization is resolved
      * within the joinrel.  So we might as well allow additional dependencies
      * on whatever residual lateral dependencies the joinrel will have.
      */
     extra.param_source_rels = bms_add_members(extra.param_source_rels,
                                               joinrel->lateral_relids);
  
     /*
      * 1. Consider mergejoin paths where both relations must be explicitly
      * sorted.  Skip this if we can't mergejoin.
      */
     if (mergejoin_allowed)
         sort_inner_and_outer(root, joinrel, outerrel, innerrel,
                              jointype, &extra);
  
     /*
      * 2. Consider paths where the outer relation need not be explicitly
      * sorted. This includes both nestloops and mergejoins where the outer
      * path is already ordered.  Again, skip this if we can't mergejoin.
      * (That's okay because we know that nestloop can't handle
      * right/right-anti/full joins at all, so it wouldn't work in the
      * prohibited cases either.)
      */
     if (mergejoin_allowed)
         match_unsorted_outer(root, joinrel, outerrel, innerrel,
                              jointype, &extra);
  
 #ifdef NOT_USED
  
     /*
      * 3. Consider paths where the inner relation need not be explicitly
      * sorted.  This includes mergejoins only (nestloops were already built in
      * match_unsorted_outer).
      *
      * Diked out as redundant 2/13/2000 -- tgl.  There isn't any really
      * significant difference between the inner and outer side of a mergejoin,
      * so match_unsorted_inner creates no paths that aren't equivalent to
      * those made by match_unsorted_outer when add_paths_to_joinrel() is
      * invoked with the two rels given in the other order.
      */
     if (mergejoin_allowed)
         match_unsorted_inner(root, joinrel, outerrel, innerrel,
                              jointype, &extra);
 #endif
  
     /*
      * 4. Consider paths where both outer and inner relations must be hashed
      * before being joined.  As above, disregard enable_hashjoin for full
      * joins, because there may be no other alternative.
      */
     if (enable_hashjoin || jointype == JOIN_FULL)
         hash_inner_and_outer(root, joinrel, outerrel, innerrel,
                              jointype, &extra);
  
     /*
      * 5. If inner and outer relations are foreign tables (or joins) belonging
      * to the same server and assigned to the same user to check access
      * permissions as, give the FDW a chance to push down joins.
      */
     if (joinrel->fdwroutine &&
         joinrel->fdwroutine->GetForeignJoinPaths)
         joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
                                                  outerrel, innerrel,
                                                  jointype, &extra);
  
     /*
      * 6. Finally, give extensions a chance to manipulate the path list.
      */
     if (set_join_pathlist_hook)
         set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
                                jointype, &extra);
 }

References PlannerInfo::all_baserels, bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, PlannerInfo::join_info_list, JOIN_INNER, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, RelOptInfo::lateral_relids, lfirst, match_unsorted_outer(), JoinPathExtraData::mergeclause_list, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, JoinPathExtraData::param_source_rels, RelOptInfo::relids, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, JoinPathExtraData::restrictlist, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, sort_inner_and_outer(), and RelOptInfo::top_parent_relids.

Referenced by populate_joinrel_with_paths().

◆ append_pathkeys()

List* append_pathkeys	(	List *	target,
		List *	source
	)

Definition at line 105 of file pathkeys.c.

 {
     ListCell   *lc;
  
     Assert(target != NIL);
  
     foreach(lc, source)
     {
         PathKey    *pk = lfirst_node(PathKey, lc);
  
         if (!pathkey_is_redundant(pk, target))
             target = lappend(target, pk);
     }
     return target;
 }

References Assert(), lappend(), lfirst_node, NIL, pathkey_is_redundant(), and source.

Referenced by adjust_group_pathkeys_for_groupagg().

◆ build_expression_pathkey()

List* build_expression_pathkey	(	PlannerInfo *	root,
		Expr *	expr,
		Oid	opno,
		Relids	rel,
		bool	create_it
	)

Definition at line 799 of file pathkeys.c.

 {
     List       *pathkeys;
     Oid         opfamily,
                 opcintype;
     int16       strategy;
     PathKey    *cpathkey;
  
     /* Find the operator in pg_amop --- failure shouldn't happen */
     if (!get_ordering_op_properties(opno,
                                     &opfamily, &opcintype, &strategy))
         elog(ERROR, "operator %u is not a valid ordering operator",
              opno);
  
     cpathkey = make_pathkey_from_sortinfo(root,
                                           expr,
                                           opfamily,
                                           opcintype,
                                           exprCollation((Node *) expr),
                                           (strategy == BTGreaterStrategyNumber),
                                           (strategy == BTGreaterStrategyNumber),
                                           0,
                                           rel,
                                           create_it);
  
     if (cpathkey)
         pathkeys = list_make1(cpathkey);
     else
         pathkeys = NIL;
  
     return pathkeys;
 }

References BTGreaterStrategyNumber, elog(), ERROR, exprCollation(), get_ordering_op_properties(), list_make1, make_pathkey_from_sortinfo(), and NIL.

Referenced by set_function_pathlist().

◆ build_index_pathkeys()

List* build_index_pathkeys	(	PlannerInfo *	root,
		IndexOptInfo *	index,
		ScanDirection	scandir
	)

Definition at line 539 of file pathkeys.c.

 {
     List       *retval = NIL;
     ListCell   *lc;
     int         i;
  
     if (index->sortopfamily == NULL)
         return NIL;             /* non-orderable index */
  
     i = 0;
     foreach(lc, index->indextlist)
     {
         TargetEntry *indextle = (TargetEntry *) lfirst(lc);
         Expr       *indexkey;
         bool        reverse_sort;
         bool        nulls_first;
         PathKey    *cpathkey;
  
         /*
          * INCLUDE columns are stored in index unordered, so they don't
          * support ordered index scan.
          */
         if (i >= index->nkeycolumns)
             break;
  
         /* We assume we don't need to make a copy of the tlist item */
         indexkey = indextle->expr;
  
         if (ScanDirectionIsBackward(scandir))
         {
             reverse_sort = !index->reverse_sort[i];
             nulls_first = !index->nulls_first[i];
         }
         else
         {
             reverse_sort = index->reverse_sort[i];
             nulls_first = index->nulls_first[i];
         }
  
         /*
          * OK, try to make a canonical pathkey for this sort key.
          */
         cpathkey = make_pathkey_from_sortinfo(root,
                                               indexkey,
                                               index->sortopfamily[i],
                                               index->opcintype[i],
                                               index->indexcollations[i],
                                               reverse_sort,
                                               nulls_first,
                                               0,
                                               index->rel->relids,
                                               false);
  
         if (cpathkey)
         {
             /*
              * We found the sort key in an EquivalenceClass, so it's relevant
              * for this query.  Add it to list, unless it's redundant.
              */
             if (!pathkey_is_redundant(cpathkey, retval))
                 retval = lappend(retval, cpathkey);
         }
         else
         {
             /*
              * Boolean index keys might be redundant even if they do not
              * appear in an EquivalenceClass, because of our special treatment
              * of boolean equality conditions --- see the comment for
              * indexcol_is_bool_constant_for_query().  If that applies, we can
              * continue to examine lower-order index columns.  Otherwise, the
              * sort key is not an interesting sort order for this query, so we
              * should stop considering index columns; any lower-order sort
              * keys won't be useful either.
              */
             if (!indexcol_is_bool_constant_for_query(root, index, i))
                 break;
         }
  
         i++;
     }
  
     return retval;
 }

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, pathkey_is_redundant(), and ScanDirectionIsBackward.

Referenced by build_index_paths().

◆ build_join_pathkeys()

List* build_join_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	joinrel,
		JoinType	jointype,
		List *	outer_pathkeys
	)

Definition at line 1093 of file pathkeys.c.

 {
     if (jointype == JOIN_FULL ||
         jointype == JOIN_RIGHT ||
         jointype == JOIN_RIGHT_ANTI)
         return NIL;
  
     /*
      * This used to be quite a complex bit of code, but now that all pathkey
      * sublists start out life canonicalized, we don't have to do a darn thing
      * here!
      *
      * We do, however, need to truncate the pathkeys list, since it may
      * contain pathkeys that were useful for forming this joinrel but are
      * uninteresting to higher levels.
      */
     return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
 }

References JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, NIL, and truncate_useless_pathkeys().

Referenced by consider_parallel_mergejoin(), consider_parallel_nestloop(), match_unsorted_outer(), and sort_inner_and_outer().

◆ build_partition_pathkeys()

List* build_partition_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	partrel,
		ScanDirection	scandir,
		bool *	partialkeys
	)

Definition at line 718 of file pathkeys.c.

 {
     List       *retval = NIL;
     PartitionScheme partscheme = partrel->part_scheme;
     int         i;
  
     Assert(partscheme != NULL);
     Assert(partitions_are_ordered(partrel->boundinfo, partrel->live_parts));
     /* For now, we can only cope with baserels */
     Assert(IS_SIMPLE_REL(partrel));
  
     for (i = 0; i < partscheme->partnatts; i++)
     {
         PathKey    *cpathkey;
         Expr       *keyCol = (Expr *) linitial(partrel->partexprs[i]);
  
         /*
          * Try to make a canonical pathkey for this partkey.
          *
          * We assume the PartitionDesc lists any NULL partition last, so we
          * treat the scan like a NULLS LAST index: we have nulls_first for
          * backwards scan only.
          */
         cpathkey = make_pathkey_from_sortinfo(root,
                                               keyCol,
                                               partscheme->partopfamily[i],
                                               partscheme->partopcintype[i],
                                               partscheme->partcollation[i],
                                               ScanDirectionIsBackward(scandir),
                                               ScanDirectionIsBackward(scandir),
                                               0,
                                               partrel->relids,
                                               false);
  
  
         if (cpathkey)
         {
             /*
              * We found the sort key in an EquivalenceClass, so it's relevant
              * for this query.  Add it to list, unless it's redundant.
              */
             if (!pathkey_is_redundant(cpathkey, retval))
                 retval = lappend(retval, cpathkey);
         }
         else
         {
             /*
              * Boolean partition keys might be redundant even if they do not
              * appear in an EquivalenceClass, because of our special treatment
              * of boolean equality conditions --- see the comment for
              * partkey_is_bool_constant_for_query().  If that applies, we can
              * continue to examine lower-order partition keys.  Otherwise, the
              * sort key is not an interesting sort order for this query, so we
              * should stop considering partition columns; any lower-order sort
              * keys won't be useful either.
              */
             if (!partkey_is_bool_constant_for_query(partrel, i))
             {
                 *partialkeys = true;
                 return retval;
             }
         }
     }
  
     *partialkeys = false;
     return retval;
 }

References Assert(), i, IS_SIMPLE_REL, lappend(), linitial, RelOptInfo::live_parts, make_pathkey_from_sortinfo(), NIL, PartitionSchemeData::partcollation, partitions_are_ordered(), partkey_is_bool_constant_for_query(), PartitionSchemeData::partnatts, PartitionSchemeData::partopcintype, PartitionSchemeData::partopfamily, pathkey_is_redundant(), RelOptInfo::relids, and ScanDirectionIsBackward.

Referenced by generate_orderedappend_paths().

◆ canonicalize_ec_expression()

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

Definition at line 472 of file equivclass.c.

 {
     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)
     {
         /*
          * If we have to change the type of the expression, set typmod to -1,
          * since the new type may not have the same typmod interpretation.
          * When we only have to change collation, preserve the exposed typmod.
          */
         int32       req_typmod;
  
         if (expr_type != req_type)
             req_typmod = -1;
         else
             req_typmod = exprTypmod((Node *) expr);
  
         /*
          * Use applyRelabelType so that we preserve const-flatness.  This is
          * important since eval_const_expressions has already been applied.
          */
         expr = (Expr *) applyRelabelType((Node *) expr,
                                          req_type, req_typmod, req_collation,
                                          COERCE_IMPLICIT_CAST, -1, false);
     }
  
     return expr;
 }

References applyRelabelType(), COERCE_IMPLICIT_CAST, exprCollation(), exprType(), and exprTypmod().

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

◆ check_index_predicates()

void check_index_predicates	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 3295 of file indxpath.c.

 {
     List       *clauselist;
     bool        have_partial;
     bool        is_target_rel;
     Relids      otherrels;
     ListCell   *lc;
  
     /* Indexes are available only on base or "other" member relations. */
     Assert(IS_SIMPLE_REL(rel));
  
     /*
      * Initialize the indrestrictinfo lists to be identical to
      * baserestrictinfo, and check whether there are any partial indexes.  If
      * not, this is all we need to do.
      */
     have_partial = false;
     foreach(lc, rel->indexlist)
     {
         IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
  
         index->indrestrictinfo = rel->baserestrictinfo;
         if (index->indpred)
             have_partial = true;
     }
     if (!have_partial)
         return;
  
     /*
      * Construct a list of clauses that we can assume true for the purpose of
      * proving the index(es) usable.  Restriction clauses for the rel are
      * always usable, and so are any join clauses that are "movable to" this
      * rel.  Also, we can consider any EC-derivable join clauses (which must
      * be "movable to" this rel, by definition).
      */
     clauselist = list_copy(rel->baserestrictinfo);
  
     /* Scan the rel's join clauses */
     foreach(lc, rel->joininfo)
     {
         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
  
         /* Check if clause can be moved to this rel */
         if (!join_clause_is_movable_to(rinfo, rel))
             continue;
  
         clauselist = lappend(clauselist, rinfo);
     }
  
     /*
      * Add on any equivalence-derivable join clauses.  Computing the correct
      * relid sets for generate_join_implied_equalities is slightly tricky
      * because the rel could be a child rel rather than a true baserel, and in
      * that case we must subtract its parents' relid(s) from all_query_rels.
      * Additionally, we mustn't consider clauses that are only computable
      * after outer joins that can null the rel.
      */
     if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
         otherrels = bms_difference(root->all_query_rels,
                                    find_childrel_parents(root, rel));
     else
         otherrels = bms_difference(root->all_query_rels, rel->relids);
     otherrels = bms_del_members(otherrels, rel->nulling_relids);
  
     if (!bms_is_empty(otherrels))
         clauselist =
             list_concat(clauselist,
                         generate_join_implied_equalities(root,
                                                          bms_union(rel->relids,
                                                                    otherrels),
                                                          otherrels,
                                                          rel,
                                                          NULL));
  
     /*
      * Normally we remove quals that are implied by a partial index's
      * predicate from indrestrictinfo, indicating that they need not be
      * checked explicitly by an indexscan plan using this index.  However, if
      * the rel is a target relation of UPDATE/DELETE/MERGE/SELECT FOR UPDATE,
      * we cannot remove such quals from the plan, because they need to be in
      * the plan so that they will be properly rechecked by EvalPlanQual
      * testing.  Some day we might want to remove such quals from the main
      * plan anyway and pass them through to EvalPlanQual via a side channel;
      * but for now, we just don't remove implied quals at all for target
      * relations.
      */
     is_target_rel = (bms_is_member(rel->relid, root->all_result_relids) ||
                      get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
  
     /*
      * Now try to prove each index predicate true, and compute the
      * indrestrictinfo lists for partial indexes.  Note that we compute the
      * indrestrictinfo list even for non-predOK indexes; this might seem
      * wasteful, but we may be able to use such indexes in OR clauses, cf
      * generate_bitmap_or_paths().
      */
     foreach(lc, rel->indexlist)
     {
         IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
         ListCell   *lcr;
  
         if (index->indpred == NIL)
             continue;           /* ignore non-partial indexes here */
  
         if (!index->predOK)     /* don't repeat work if already proven OK */
             index->predOK = predicate_implied_by(index->indpred, clauselist,
                                                  false);
  
         /* If rel is an update target, leave indrestrictinfo as set above */
         if (is_target_rel)
             continue;
  
         /* Else compute indrestrictinfo as the non-implied quals */
         index->indrestrictinfo = NIL;
         foreach(lcr, rel->baserestrictinfo)
         {
             RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
  
             /* predicate_implied_by() assumes first arg is immutable */
             if (contain_mutable_functions((Node *) rinfo->clause) ||
                 !predicate_implied_by(list_make1(rinfo->clause),
                                       index->indpred, false))
                 index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
         }
     }
 }

References PlannerInfo::all_query_rels, PlannerInfo::all_result_relids, Assert(), RelOptInfo::baserestrictinfo, bms_del_members(), bms_difference(), bms_is_empty, bms_is_member(), bms_union(), RestrictInfo::clause, contain_mutable_functions(), find_childrel_parents(), generate_join_implied_equalities(), get_plan_rowmark(), RelOptInfo::indexlist, IS_SIMPLE_REL, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, RelOptInfo::nulling_relids, predicate_implied_by(), RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and PlannerInfo::rowMarks.

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys	(	List *	keys1,
		List *	keys2
	)

Definition at line 301 of file pathkeys.c.

 {
     ListCell   *key1,
                *key2;
  
     /*
      * Fall out quickly if we are passed two identical lists.  This mostly
      * catches the case where both are NIL, but that's common enough to
      * warrant the test.
      */
     if (keys1 == keys2)
         return PATHKEYS_EQUAL;
  
     forboth(key1, keys1, key2, keys2)
     {
         PathKey    *pathkey1 = (PathKey *) lfirst(key1);
         PathKey    *pathkey2 = (PathKey *) lfirst(key2);
  
         if (pathkey1 != pathkey2)
             return PATHKEYS_DIFFERENT;  /* no need to keep looking */
     }
  
     /*
      * If we reached the end of only one list, the other is longer and
      * therefore not a subset.
      */
     if (key1 != NULL)
         return PATHKEYS_BETTER1;    /* key1 is longer */
     if (key2 != NULL)
         return PATHKEYS_BETTER2;    /* key2 is longer */
     return PATHKEYS_EQUAL;
 }

References forboth, lfirst, PATHKEYS_BETTER1, PATHKEYS_BETTER2, PATHKEYS_DIFFERENT, and PATHKEYS_EQUAL.

Referenced by add_partial_path(), add_partial_path_precheck(), add_path(), add_path_precheck(), add_paths_to_append_rel(), adjust_group_pathkeys_for_groupagg(), pathkeys_contained_in(), and set_cheapest().

◆ compute_parallel_worker()

int compute_parallel_worker	(	RelOptInfo *	rel,
		double	heap_pages,
		double	index_pages,
		int	max_workers
	)

Definition at line 4210 of file allpaths.c.

 {
     int         parallel_workers = 0;
  
     /*
      * If the user has set the parallel_workers reloption, use that; otherwise
      * select a default number of workers.
      */
     if (rel->rel_parallel_workers != -1)
         parallel_workers = rel->rel_parallel_workers;
     else
     {
         /*
          * If the number of pages being scanned is insufficient to justify a
          * parallel scan, just return zero ... unless it's an inheritance
          * child. In that case, we want to generate a parallel path here
          * anyway.  It might not be worthwhile just for this relation, but
          * when combined with all of its inheritance siblings it may well pay
          * off.
          */
         if (rel->reloptkind == RELOPT_BASEREL &&
             ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
              (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
             return 0;
  
         if (heap_pages >= 0)
         {
             int         heap_parallel_threshold;
             int         heap_parallel_workers = 1;
  
             /*
              * Select the number of workers based on the log of the size of
              * the relation.  This probably needs to be a good deal more
              * sophisticated, but we need something here for now.  Note that
              * the upper limit of the min_parallel_table_scan_size GUC is
              * chosen to prevent overflow here.
              */
             heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
             while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
             {
                 heap_parallel_workers++;
                 heap_parallel_threshold *= 3;
                 if (heap_parallel_threshold > INT_MAX / 3)
                     break;      /* avoid overflow */
             }
  
             parallel_workers = heap_parallel_workers;
         }
  
         if (index_pages >= 0)
         {
             int         index_parallel_workers = 1;
             int         index_parallel_threshold;
  
             /* same calculation as for heap_pages above */
             index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
             while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
             {
                 index_parallel_workers++;
                 index_parallel_threshold *= 3;
                 if (index_parallel_threshold > INT_MAX / 3)
                     break;      /* avoid overflow */
             }
  
             if (parallel_workers > 0)
                 parallel_workers = Min(parallel_workers, index_parallel_workers);
             else
                 parallel_workers = index_parallel_workers;
         }
     }
  
     /* In no case use more than caller supplied maximum number of workers */
     parallel_workers = Min(parallel_workers, max_workers);
  
     return parallel_workers;
 }

References Max, Min, min_parallel_index_scan_size, min_parallel_table_scan_size, RelOptInfo::rel_parallel_workers, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by cost_index(), create_partial_bitmap_paths(), create_plain_partial_paths(), and plan_create_index_workers().

◆ convert_subquery_pathkeys()

List* convert_subquery_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	rel,
		List *	subquery_pathkeys,
		List *	subquery_tlist
	)

Definition at line 853 of file pathkeys.c.

 {
     List       *retval = NIL;
     int         retvallen = 0;
     int         outer_query_keys = list_length(root->query_pathkeys);
     ListCell   *i;
  
     foreach(i, subquery_pathkeys)
     {
         PathKey    *sub_pathkey = (PathKey *) lfirst(i);
         EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
         PathKey    *best_pathkey = NULL;
  
         if (sub_eclass->ec_has_volatile)
         {
             /*
              * If the sub_pathkey's EquivalenceClass is volatile, then it must
              * have come from an ORDER BY clause, and we have to match it to
              * that same targetlist entry.
              */
             TargetEntry *tle;
             Var        *outer_var;
  
             if (sub_eclass->ec_sortref == 0)    /* can't happen */
                 elog(ERROR, "volatile EquivalenceClass has no sortref");
             tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
             Assert(tle);
             /* Is TLE actually available to the outer query? */
             outer_var = find_var_for_subquery_tle(rel, tle);
             if (outer_var)
             {
                 /* We can represent this sub_pathkey */
                 EquivalenceMember *sub_member;
                 EquivalenceClass *outer_ec;
  
                 Assert(list_length(sub_eclass->ec_members) == 1);
                 sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
  
                 /*
                  * Note: it might look funny to be setting sortref = 0 for a
                  * reference to a volatile sub_eclass.  However, the
                  * expression is *not* volatile in the outer query: it's just
                  * a Var referencing whatever the subquery emitted. (IOW, the
                  * outer query isn't going to re-execute the volatile
                  * expression itself.)  So this is okay.
                  */
                 outer_ec =
                     get_eclass_for_sort_expr(root,
                                              (Expr *) outer_var,
                                              sub_eclass->ec_opfamilies,
                                              sub_member->em_datatype,
                                              sub_eclass->ec_collation,
                                              0,
                                              rel->relids,
                                              false);
  
                 /*
                  * If we don't find a matching EC, sub-pathkey isn't
                  * interesting to the outer query
                  */
                 if (outer_ec)
                     best_pathkey =
                         make_canonical_pathkey(root,
                                                outer_ec,
                                                sub_pathkey->pk_opfamily,
                                                sub_pathkey->pk_strategy,
                                                sub_pathkey->pk_nulls_first);
             }
         }
         else
         {
             /*
              * Otherwise, the sub_pathkey's EquivalenceClass could contain
              * multiple elements (representing knowledge that multiple items
              * are effectively equal).  Each element might match none, one, or
              * more of the output columns that are visible to the outer query.
              * This means we may have multiple possible representations of the
              * sub_pathkey in the context of the outer query.  Ideally we
              * would generate them all and put them all into an EC of the
              * outer query, thereby propagating equality knowledge up to the
              * outer query.  Right now we cannot do so, because the outer
              * query's EquivalenceClasses are already frozen when this is
              * called. Instead we prefer the one that has the highest "score"
              * (number of EC peers, plus one if it matches the outer
              * query_pathkeys). This is the most likely to be useful in the
              * outer query.
              */
             int         best_score = -1;
             ListCell   *j;
  
             foreach(j, sub_eclass->ec_members)
             {
                 EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
                 Expr       *sub_expr = sub_member->em_expr;
                 Oid         sub_expr_type = sub_member->em_datatype;
                 Oid         sub_expr_coll = sub_eclass->ec_collation;
                 ListCell   *k;
  
                 if (sub_member->em_is_child)
                     continue;   /* ignore children here */
  
                 foreach(k, subquery_tlist)
                 {
                     TargetEntry *tle = (TargetEntry *) lfirst(k);
                     Var        *outer_var;
                     Expr       *tle_expr;
                     EquivalenceClass *outer_ec;
                     PathKey    *outer_pk;
                     int         score;
  
                     /* Is TLE actually available to the outer query? */
                     outer_var = find_var_for_subquery_tle(rel, tle);
                     if (!outer_var)
                         continue;
  
                     /*
                      * The targetlist entry is considered to match if it
                      * matches after sort-key canonicalization.  That is
                      * needed since the sub_expr has been through the same
                      * process.
                      */
                     tle_expr = canonicalize_ec_expression(tle->expr,
                                                           sub_expr_type,
                                                           sub_expr_coll);
                     if (!equal(tle_expr, sub_expr))
                         continue;
  
                     /* See if we have a matching EC for the TLE */
                     outer_ec = get_eclass_for_sort_expr(root,
                                                         (Expr *) outer_var,
                                                         sub_eclass->ec_opfamilies,
                                                         sub_expr_type,
                                                         sub_expr_coll,
                                                         0,
                                                         rel->relids,
                                                         false);
  
                     /*
                      * If we don't find a matching EC, this sub-pathkey isn't
                      * interesting to the outer query
                      */
                     if (!outer_ec)
                         continue;
  
                     outer_pk = make_canonical_pathkey(root,
                                                       outer_ec,
                                                       sub_pathkey->pk_opfamily,
                                                       sub_pathkey->pk_strategy,
                                                       sub_pathkey->pk_nulls_first);
                     /* score = # of equivalence peers */
                     score = list_length(outer_ec->ec_members) - 1;
                     /* +1 if it matches the proper query_pathkeys item */
                     if (retvallen < outer_query_keys &&
                         list_nth(root->query_pathkeys, retvallen) == outer_pk)
                         score++;
                     if (score > best_score)
                     {
                         best_pathkey = outer_pk;
                         best_score = score;
                     }
                 }
             }
         }
  
         /*
          * If we couldn't find a representation of this sub_pathkey, we're
          * done (we can't use the ones to its right, either).
          */
         if (!best_pathkey)
             break;
  
         /*
          * Eliminate redundant ordering info; could happen if outer query
          * equivalences subquery keys...
          */
         if (!pathkey_is_redundant(best_pathkey, retval))
         {
             retval = lappend(retval, best_pathkey);
             retvallen++;
         }
     }
  
     return retval;
 }

References Assert(), canonicalize_ec_expression(), EquivalenceClass::ec_collation, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_sortref, elog(), EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, equal(), ERROR, TargetEntry::expr, find_var_for_subquery_tle(), get_eclass_for_sort_expr(), get_sortgroupref_tle(), i, j, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, and RelOptInfo::relids.

Referenced by set_subquery_pathlist().

◆ create_index_paths()

void create_index_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 235 of file indxpath.c.

 {
     List       *indexpaths;
     List       *bitindexpaths;
     List       *bitjoinpaths;
     List       *joinorclauses;
     IndexClauseSet rclauseset;
     IndexClauseSet jclauseset;
     IndexClauseSet eclauseset;
     ListCell   *lc;
  
     /* Skip the whole mess if no indexes */
     if (rel->indexlist == NIL)
         return;
  
     /* Bitmap paths are collected and then dealt with at the end */
     bitindexpaths = bitjoinpaths = joinorclauses = NIL;
  
     /* Examine each index in turn */
     foreach(lc, rel->indexlist)
     {
         IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
  
         /* Protect limited-size array in IndexClauseSets */
         Assert(index->nkeycolumns <= INDEX_MAX_KEYS);
  
         /*
          * Ignore partial indexes that do not match the query.
          * (generate_bitmap_or_paths() might be able to do something with
          * them, but that's of no concern here.)
          */
         if (index->indpred != NIL && !index->predOK)
             continue;
  
         /*
          * Identify the restriction clauses that can match the index.
          */
         MemSet(&rclauseset, 0, sizeof(rclauseset));
         match_restriction_clauses_to_index(root, index, &rclauseset);
  
         /*
          * Build index paths from the restriction clauses.  These will be
          * non-parameterized paths.  Plain paths go directly to add_path(),
          * bitmap paths are added to bitindexpaths to be handled below.
          */
         get_index_paths(root, rel, index, &rclauseset,
                         &bitindexpaths);
  
         /*
          * Identify the join clauses that can match the index.  For the moment
          * we keep them separate from the restriction clauses.  Note that this
          * step finds only "loose" join clauses that have not been merged into
          * EquivalenceClasses.  Also, collect join OR clauses for later.
          */
         MemSet(&jclauseset, 0, sizeof(jclauseset));
         match_join_clauses_to_index(root, rel, index,
                                     &jclauseset, &joinorclauses);
  
         /*
          * Look for EquivalenceClasses that can generate joinclauses matching
          * the index.
          */
         MemSet(&eclauseset, 0, sizeof(eclauseset));
         match_eclass_clauses_to_index(root, index,
                                       &eclauseset);
  
         /*
          * If we found any plain or eclass join clauses, build parameterized
          * index paths using them.
          */
         if (jclauseset.nonempty || eclauseset.nonempty)
             consider_index_join_clauses(root, rel, index,
                                         &rclauseset,
                                         &jclauseset,
                                         &eclauseset,
                                         &bitjoinpaths);
     }
  
     /*
      * Generate BitmapOrPaths for any suitable OR-clauses present in the
      * restriction list.  Add these to bitindexpaths.
      */
     indexpaths = generate_bitmap_or_paths(root, rel,
                                           rel->baserestrictinfo, NIL);
     bitindexpaths = list_concat(bitindexpaths, indexpaths);
  
     /*
      * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
      * the joinclause list.  Add these to bitjoinpaths.
      */
     indexpaths = generate_bitmap_or_paths(root, rel,
                                           joinorclauses, rel->baserestrictinfo);
     bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
  
     /*
      * If we found anything usable, generate a BitmapHeapPath for the most
      * promising combination of restriction bitmap index paths.  Note there
      * will be only one such path no matter how many indexes exist.  This
      * should be sufficient since there's basically only one figure of merit
      * (total cost) for such a path.
      */
     if (bitindexpaths != NIL)
     {
         Path       *bitmapqual;
         BitmapHeapPath *bpath;
  
         bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
         bpath = create_bitmap_heap_path(root, rel, bitmapqual,
                                         rel->lateral_relids, 1.0, 0);
         add_path(rel, (Path *) bpath);
  
         /* create a partial bitmap heap path */
         if (rel->consider_parallel && rel->lateral_relids == NULL)
             create_partial_bitmap_paths(root, rel, bitmapqual);
     }
  
     /*
      * Likewise, if we found anything usable, generate BitmapHeapPaths for the
      * most promising combinations of join bitmap index paths.  Our strategy
      * is to generate one such path for each distinct parameterization seen
      * among the available bitmap index paths.  This may look pretty
      * expensive, but usually there won't be very many distinct
      * parameterizations.  (This logic is quite similar to that in
      * consider_index_join_clauses, but we're working with whole paths not
      * individual clauses.)
      */
     if (bitjoinpaths != NIL)
     {
         List       *all_path_outers;
  
         /* Identify each distinct parameterization seen in bitjoinpaths */
         all_path_outers = NIL;
         foreach(lc, bitjoinpaths)
         {
             Path       *path = (Path *) lfirst(lc);
             Relids      required_outer = PATH_REQ_OUTER(path);
  
             all_path_outers = list_append_unique(all_path_outers,
                                                  required_outer);
         }
  
         /* Now, for each distinct parameterization set ... */
         foreach(lc, all_path_outers)
         {
             Relids      max_outers = (Relids) lfirst(lc);
             List       *this_path_set;
             Path       *bitmapqual;
             Relids      required_outer;
             double      loop_count;
             BitmapHeapPath *bpath;
             ListCell   *lcp;
  
             /* Identify all the bitmap join paths needing no more than that */
             this_path_set = NIL;
             foreach(lcp, bitjoinpaths)
             {
                 Path       *path = (Path *) lfirst(lcp);
  
                 if (bms_is_subset(PATH_REQ_OUTER(path), max_outers))
                     this_path_set = lappend(this_path_set, path);
             }
  
             /*
              * Add in restriction bitmap paths, since they can be used
              * together with any join paths.
              */
             this_path_set = list_concat(this_path_set, bitindexpaths);
  
             /* Select best AND combination for this parameterization */
             bitmapqual = choose_bitmap_and(root, rel, this_path_set);
  
             /* And push that path into the mix */
             required_outer = PATH_REQ_OUTER(bitmapqual);
             loop_count = get_loop_count(root, rel->relid, required_outer);
             bpath = create_bitmap_heap_path(root, rel, bitmapqual,
                                             required_outer, loop_count, 0);
             add_path(rel, (Path *) bpath);
         }
     }
 }

References add_path(), Assert(), RelOptInfo::baserestrictinfo, bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), RelOptInfo::consider_parallel, create_bitmap_heap_path(), create_partial_bitmap_paths(), generate_bitmap_or_paths(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, lappend(), RelOptInfo::lateral_relids, lfirst, list_append_unique(), list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, NIL, IndexClauseSet::nonempty, PATH_REQ_OUTER, and RelOptInfo::relid.

Referenced by set_plain_rel_pathlist().

◆ create_partial_bitmap_paths()

void create_partial_bitmap_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel,
		Path *	bitmapqual
	)

Definition at line 4174 of file allpaths.c.

 {
     int         parallel_workers;
     double      pages_fetched;
  
     /* Compute heap pages for bitmap heap scan */
     pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
                                          NULL, NULL);
  
     parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
                                                max_parallel_workers_per_gather);
  
     if (parallel_workers <= 0)
         return;
  
     add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
                                                            bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
 }

References add_partial_path(), compute_bitmap_pages(), compute_parallel_worker(), create_bitmap_heap_path(), RelOptInfo::lateral_relids, and max_parallel_workers_per_gather.

Referenced by create_index_paths().

◆ create_tidscan_paths()

void create_tidscan_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 460 of file tidpath.c.

 {
     List       *tidquals;
     List       *tidrangequals;
  
     /*
      * If any suitable quals exist in the rel's baserestrict list, generate a
      * plain (unparameterized) TidPath with them.
      */
     tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);
  
     if (tidquals != NIL)
     {
         /*
          * This path uses no join clauses, but it could still have required
          * parameterization due to LATERAL refs in its tlist.
          */
         Relids      required_outer = rel->lateral_relids;
  
         add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
                                                    required_outer));
     }
  
     /*
      * If there are range quals in the baserestrict list, generate a
      * TidRangePath.
      */
     tidrangequals = TidRangeQualFromRestrictInfoList(rel->baserestrictinfo,
                                                      rel);
  
     if (tidrangequals != NIL)
     {
         /*
          * This path uses no join clauses, but it could still have required
          * parameterization due to LATERAL refs in its tlist.
          */
         Relids      required_outer = rel->lateral_relids;
  
         add_path(rel, (Path *) create_tidrangescan_path(root, rel,
                                                         tidrangequals,
                                                         required_outer));
     }
  
     /*
      * Try to generate parameterized TidPaths using equality clauses extracted
      * from EquivalenceClasses.  (This is important since simple "t1.ctid =
      * t2.ctid" clauses will turn into ECs.)
      */
     if (rel->has_eclass_joins)
     {
         List       *clauses;
  
         /* Generate clauses, skipping any that join to lateral_referencers */
         clauses = generate_implied_equalities_for_column(root,
                                                          rel,
                                                          ec_member_matches_ctid,
                                                          NULL,
                                                          rel->lateral_referencers);
  
         /* Generate a path for each usable join clause */
         BuildParameterizedTidPaths(root, rel, clauses);
     }
  
     /*
      * Also consider parameterized TidPaths using "loose" join quals.  Quals
      * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
      * join quals, for example.
      */
     BuildParameterizedTidPaths(root, rel, rel->joininfo);
 }

References add_path(), RelOptInfo::baserestrictinfo, BuildParameterizedTidPaths(), create_tidrangescan_path(), create_tidscan_path(), ec_member_matches_ctid(), generate_implied_equalities_for_column(), RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, RelOptInfo::lateral_referencers, RelOptInfo::lateral_relids, NIL, TidQualFromRestrictInfoList(), and TidRangeQualFromRestrictInfoList().

Referenced by set_plain_rel_pathlist().

◆ eclass_useful_for_merging()

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

Definition at line 3136 of file equivclass.c.

 {
     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;
 }

References Assert(), bms_is_empty, bms_is_subset(), bms_overlap(), eclass(), 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().

◆ exprs_known_equal()

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

Definition at line 2439 of file equivclass.c.

 {
     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;
 }

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().

◆ find_computable_ec_member()

EquivalenceMember* find_computable_ec_member	(	PlannerInfo *	root,
		EquivalenceClass *	ec,
		List *	exprs,
		Relids	relids,
		bool	require_parallel_safe
	)

Definition at line 825 of file equivclass.c.

 {
     ListCell   *lc;
  
     foreach(lc, ec->ec_members)
     {
         EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
         List       *exprvars;
         ListCell   *lc2;
  
         /*
          * We shouldn't be trying to sort by an equivalence class that
          * contains a constant, so no need to consider such cases any further.
          */
         if (em->em_is_const)
             continue;
  
         /*
          * Ignore child members unless they belong to the requested rel.
          */
         if (em->em_is_child &&
             !bms_is_subset(em->em_relids, relids))
             continue;
  
         /*
          * Match if all Vars and quasi-Vars are available in "exprs".
          */
         exprvars = pull_var_clause((Node *) em->em_expr,
                                    PVC_INCLUDE_AGGREGATES |
                                    PVC_INCLUDE_WINDOWFUNCS |
                                    PVC_INCLUDE_PLACEHOLDERS);
         foreach(lc2, exprvars)
         {
             if (!is_exprlist_member(lfirst(lc2), exprs))
                 break;
         }
         list_free(exprvars);
         if (lc2)
             continue;           /* we hit a non-available Var */
  
         /*
          * If requested, reject expressions that are not parallel-safe.  We
          * check this last because it's a rather expensive test.
          */
         if (require_parallel_safe &&
             !is_parallel_safe(root, (Node *) em->em_expr))
             continue;
  
         return em;              /* found usable expression */
     }
  
     return NULL;
 }

References bms_is_subset(), EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, is_exprlist_member(), is_parallel_safe(), lfirst, list_free(), pull_var_clause(), PVC_INCLUDE_AGGREGATES, PVC_INCLUDE_PLACEHOLDERS, and PVC_INCLUDE_WINDOWFUNCS.

Referenced by prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

◆ find_derived_clause_for_ec_member()

RestrictInfo* find_derived_clause_for_ec_member	(	EquivalenceClass *	ec,
		EquivalenceMember *	em
	)

Definition at line 2581 of file equivclass.c.

 {
     ListCell   *lc;
  
     Assert(ec->ec_has_const);
     Assert(!em->em_is_const);
     foreach(lc, ec->ec_derives)
     {
         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
  
         /*
          * generate_base_implied_equalities_const will have put non-const
          * members on the left side of derived clauses.
          */
         if (rinfo->left_em == em)
             return rinfo;
     }
     return NULL;
 }

References Assert(), EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceMember::em_is_const, and lfirst.

Referenced by get_foreign_key_join_selectivity().

◆ find_ec_member_matching_expr()

EquivalenceMember* find_ec_member_matching_expr	(	EquivalenceClass *	ec,
		Expr *	expr,
		Relids	relids
	)

Definition at line 760 of file equivclass.c.

 {
     ListCell   *lc;
  
     /* We ignore binary-compatible relabeling on both ends */
     while (expr && IsA(expr, RelabelType))
         expr = ((RelabelType *) expr)->arg;
  
     foreach(lc, ec->ec_members)
     {
         EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
         Expr       *emexpr;
  
         /*
          * We shouldn't be trying to sort by an equivalence class that
          * contains a constant, so no need to consider such cases any further.
          */
         if (em->em_is_const)
             continue;
  
         /*
          * Ignore child members unless they belong to the requested rel.
          */
         if (em->em_is_child &&
             !bms_is_subset(em->em_relids, relids))
             continue;
  
         /*
          * Match if same expression (after stripping relabel).
          */
         emexpr = em->em_expr;
         while (emexpr && IsA(emexpr, RelabelType))
             emexpr = ((RelabelType *) emexpr)->arg;
  
         if (equal(emexpr, expr))
             return em;
     }
  
     return NULL;
 }

References arg, bms_is_subset(), EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, equal(), IsA, and lfirst.

Referenced by make_unique_from_pathkeys(), prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

◆ find_mergeclauses_for_outer_pathkeys()

List* find_mergeclauses_for_outer_pathkeys	(	PlannerInfo *	root,
		List *	pathkeys,
		List *	restrictinfos
	)

Definition at line 1311 of file pathkeys.c.

 {
     List       *mergeclauses = NIL;
     ListCell   *i;
  
     /* make sure we have eclasses cached in the clauses */
     foreach(i, restrictinfos)
     {
         RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
  
         update_mergeclause_eclasses(root, rinfo);
     }
  
     foreach(i, pathkeys)
     {
         PathKey    *pathkey = (PathKey *) lfirst(i);
         EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
         List       *matched_restrictinfos = NIL;
         ListCell   *j;
  
         /*----------
          * A mergejoin clause matches a pathkey if it has the same EC.
          * If there are multiple matching clauses, take them all.  In plain
          * inner-join scenarios we expect only one match, because
          * equivalence-class processing will have removed any redundant
          * mergeclauses.  However, in outer-join scenarios there might be
          * multiple matches.  An example is
          *
          *  select * from a full join b
          *      on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
          *
          * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
          * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
          * we *must* do so or we will be unable to form a valid plan.
          *
          * We expect that the given pathkeys list is canonical, which means
          * no two members have the same EC, so it's not possible for this
          * code to enter the same mergeclause into the result list twice.
          *
          * It's possible that multiple matching clauses might have different
          * ECs on the other side, in which case the order we put them into our
          * result makes a difference in the pathkeys required for the inner
          * input rel.  However this routine hasn't got any info about which
          * order would be best, so we don't worry about that.
          *
          * It's also possible that the selected mergejoin clauses produce
          * a noncanonical ordering of pathkeys for the inner side, ie, we
          * might select clauses that reference b.v1, b.v2, b.v1 in that
          * order.  This is not harmful in itself, though it suggests that
          * the clauses are partially redundant.  Since the alternative is
          * to omit mergejoin clauses and thereby possibly fail to generate a
          * plan altogether, we live with it.  make_inner_pathkeys_for_merge()
          * has to delete duplicates when it constructs the inner pathkeys
          * list, and we also have to deal with such cases specially in
          * create_mergejoin_plan().
          *----------
          */
         foreach(j, restrictinfos)
         {
             RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
             EquivalenceClass *clause_ec;
  
             clause_ec = rinfo->outer_is_left ?
                 rinfo->left_ec : rinfo->right_ec;
             if (clause_ec == pathkey_ec)
                 matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
         }
  
         /*
          * If we didn't find a mergeclause, we're done --- any additional
          * sort-key positions in the pathkeys are useless.  (But we can still
          * mergejoin if we found at least one mergeclause.)
          */
         if (matched_restrictinfos == NIL)
             break;
  
         /*
          * If we did find usable mergeclause(s) for this sort-key position,
          * add them to result list.
          */
         mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
     }
  
     return mergeclauses;
 }

References i, j, lappend(), lfirst, list_concat(), NIL, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo * root )

Definition at line 1033 of file equivclass.c.

 {
     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];
  
             if (rel == NULL)    /* must be an outer join */
             {
                 Assert(bms_is_member(i, root->outer_join_rels));
                 continue;
             }
  
             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++;
     }
 }

References Assert(), bms_add_member(), bms_is_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(), PlannerInfo::outer_join_rels, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by query_planner().

◆ generate_gather_paths()

void generate_gather_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel,
		bool	override_rows
	)

Definition at line 3060 of file allpaths.c.

 {
     Path       *cheapest_partial_path;
     Path       *simple_gather_path;
     ListCell   *lc;
     double      rows;
     double     *rowsp = NULL;
  
     /* If there are no partial paths, there's nothing to do here. */
     if (rel->partial_pathlist == NIL)
         return;
  
     /* Should we override the rel's rowcount estimate? */
     if (override_rows)
         rowsp = &rows;
  
     /*
      * The output of Gather is always unsorted, so there's only one partial
      * path of interest: the cheapest one.  That will be the one at the front
      * of partial_pathlist because of the way add_partial_path works.
      */
     cheapest_partial_path = linitial(rel->partial_pathlist);
     rows =
         cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
     simple_gather_path = (Path *)
         create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
                            NULL, rowsp);
     add_path(rel, simple_gather_path);
  
     /*
      * For each useful ordering, we can consider an order-preserving Gather
      * Merge.
      */
     foreach(lc, rel->partial_pathlist)
     {
         Path       *subpath = (Path *) lfirst(lc);
         GatherMergePath *path;
  
         if (subpath->pathkeys == NIL)
             continue;
  
         rows = subpath->rows * subpath->parallel_workers;
         path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
                                         subpath->pathkeys, NULL, rowsp);
         add_path(rel, &path->path);
     }
 }

References add_path(), create_gather_merge_path(), create_gather_path(), lfirst, linitial, NIL, Path::parallel_workers, RelOptInfo::partial_pathlist, GatherMergePath::path, RelOptInfo::reltarget, Path::rows, and subpath().

Referenced by create_partial_distinct_paths(), and generate_useful_gather_paths().

◆ 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 2884 of file equivclass.c.

 {
     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;
 }

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().

◆ generate_join_implied_equalities()

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

Definition at line 1381 of file equivclass.c.

 {
     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);
         nominal_join_relids = add_outer_joins_to_relids(root,
                                                         nominal_join_relids,
                                                         sjinfo,
                                                         NULL);
     }
     else
     {
         nominal_inner_relids = inner_relids;
         nominal_join_relids = join_relids;
     }
  
     /*
      * Examine all potentially-relevant eclasses.
      *
      * If we are considering an outer join, we must include "join" clauses
      * that mention either input rel plus the outer join's relid; these
      * represent post-join filter clauses that have to be applied at this
      * join.  We don't have infrastructure that would let us identify such
      * eclasses cheaply, so just fall back to considering all eclasses
      * mentioning anything in nominal_join_relids.
      *
      * At inner joins, we can be smarter: only consider eclasses mentioning
      * both input rels.
      */
     if (sjinfo && sjinfo->ojrelid != 0)
         matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids);
     else
         matching_ecs = get_common_eclass_indexes(root, nominal_inner_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;
 }

References add_outer_joins_to_relids(), 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(), get_eclass_indexes_for_relids(), i, IS_OTHER_REL, list_concat(), list_length(), list_nth(), NIL, SpecialJoinInfo::ojrelid, 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().

◆ 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 1481 of file equivclass.c.

 {
     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;
 }

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().

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 4298 of file allpaths.c.

 {
     List       *live_children = NIL;
     int         cnt_parts;
     int         num_parts;
     RelOptInfo **part_rels;
  
     /* Handle only join relations here. */
     if (!IS_JOIN_REL(rel))
         return;
  
     /* We've nothing to do if the relation is not partitioned. */
     if (!IS_PARTITIONED_REL(rel))
         return;
  
     /* The relation should have consider_partitionwise_join set. */
     Assert(rel->consider_partitionwise_join);
  
     /* Guard against stack overflow due to overly deep partition hierarchy. */
     check_stack_depth();
  
     num_parts = rel->nparts;
     part_rels = rel->part_rels;
  
     /* Collect non-dummy child-joins. */
     for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
     {
         RelOptInfo *child_rel = part_rels[cnt_parts];
  
         /* If it's been pruned entirely, it's certainly dummy. */
         if (child_rel == NULL)
             continue;
  
         /* Make partitionwise join paths for this partitioned child-join. */
         generate_partitionwise_join_paths(root, child_rel);
  
         /* If we failed to make any path for this child, we must give up. */
         if (child_rel->pathlist == NIL)
         {
             /*
              * Mark the parent joinrel as unpartitioned so that later
              * functions treat it correctly.
              */
             rel->nparts = 0;
             return;
         }
  
         /* Else, identify the cheapest path for it. */
         set_cheapest(child_rel);
  
         /* Dummy children need not be scanned, so ignore those. */
         if (IS_DUMMY_REL(child_rel))
             continue;
  
 #ifdef OPTIMIZER_DEBUG
         debug_print_rel(root, child_rel);
 #endif
  
         live_children = lappend(live_children, child_rel);
     }
  
     /* If all child-joins are dummy, parent join is also dummy. */
     if (!live_children)
     {
         mark_dummy_rel(rel);
         return;
     }
  
     /* Build additional paths for this rel from child-join paths. */
     add_paths_to_append_rel(root, rel, live_children);
     list_free(live_children);
 }

References add_paths_to_append_rel(), Assert(), check_stack_depth(), RelOptInfo::consider_partitionwise_join, IS_DUMMY_REL, IS_JOIN_REL, IS_PARTITIONED_REL, lappend(), list_free(), mark_dummy_rel(), NIL, RelOptInfo::nparts, RelOptInfo::pathlist, and set_cheapest().

Referenced by merge_clump(), and standard_join_search().

◆ generate_useful_gather_paths()

void generate_useful_gather_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel,
		bool	override_rows
	)

Definition at line 3198 of file allpaths.c.

 {
     ListCell   *lc;
     double      rows;
     double     *rowsp = NULL;
     List       *useful_pathkeys_list = NIL;
     Path       *cheapest_partial_path = NULL;
  
     /* If there are no partial paths, there's nothing to do here. */
     if (rel->partial_pathlist == NIL)
         return;
  
     /* Should we override the rel's rowcount estimate? */
     if (override_rows)
         rowsp = &rows;
  
     /* generate the regular gather (merge) paths */
     generate_gather_paths(root, rel, override_rows);
  
     /* consider incremental sort for interesting orderings */
     useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, true);
  
     /* used for explicit (full) sort paths */
     cheapest_partial_path = linitial(rel->partial_pathlist);
  
     /*
      * Consider sorted paths for each interesting ordering. We generate both
      * incremental and full sort.
      */
     foreach(lc, useful_pathkeys_list)
     {
         List       *useful_pathkeys = lfirst(lc);
         ListCell   *lc2;
         bool        is_sorted;
         int         presorted_keys;
  
         foreach(lc2, rel->partial_pathlist)
         {
             Path       *subpath = (Path *) lfirst(lc2);
             GatherMergePath *path;
  
             is_sorted = pathkeys_count_contained_in(useful_pathkeys,
                                                     subpath->pathkeys,
                                                     &presorted_keys);
  
             /*
              * We don't need to consider the case where a subpath is already
              * fully sorted because generate_gather_paths already creates a
              * gather merge path for every subpath that has pathkeys present.
              *
              * But since the subpath is already sorted, we know we don't need
              * to consider adding a sort (full or incremental) on top of it,
              * so we can continue here.
              */
             if (is_sorted)
                 continue;
  
             /*
              * Try at least sorting the cheapest path and also try
              * incrementally sorting any path which is partially sorted
              * already (no need to deal with paths which have presorted keys
              * when incremental sort is disabled unless it's the cheapest
              * input path).
              */
             if (subpath != cheapest_partial_path &&
                 (presorted_keys == 0 || !enable_incremental_sort))
                 continue;
  
             /*
              * Consider regular sort for any path that's not presorted or if
              * incremental sort is disabled.  We've no need to consider both
              * sort and incremental sort on the same path.  We assume that
              * incremental sort is always faster when there are presorted
              * keys.
              *
              * This is not redundant with the gather paths created in
              * generate_gather_paths, because that doesn't generate ordered
              * output. Here we add an explicit sort to match the useful
              * ordering.
              */
             if (presorted_keys == 0 || !enable_incremental_sort)
             {
                 subpath = (Path *) create_sort_path(root,
                                                     rel,
                                                     subpath,
                                                     useful_pathkeys,
                                                     -1.0);
                 rows = subpath->rows * subpath->parallel_workers;
             }
             else
                 subpath = (Path *) create_incremental_sort_path(root,
                                                                 rel,
                                                                 subpath,
                                                                 useful_pathkeys,
                                                                 presorted_keys,
                                                                 -1);
             path = create_gather_merge_path(root, rel,
                                             subpath,
                                             rel->reltarget,
                                             subpath->pathkeys,
                                             NULL,
                                             rowsp);
  
             add_path(rel, &path->path);
         }
     }
 }

References add_path(), create_gather_merge_path(), create_incremental_sort_path(), create_sort_path(), enable_incremental_sort, generate_gather_paths(), get_useful_pathkeys_for_relation(), lfirst, linitial, NIL, RelOptInfo::partial_pathlist, GatherMergePath::path, pathkeys_count_contained_in(), RelOptInfo::reltarget, and subpath().

Referenced by apply_scanjoin_target_to_paths(), gather_grouping_paths(), merge_clump(), set_rel_pathlist(), and standard_join_search().

◆ get_cheapest_fractional_path_for_pathkeys()

Path* get_cheapest_fractional_path_for_pathkeys	(	List *	paths,
		List *	pathkeys,
		Relids	required_outer,
		double	fraction
	)

Definition at line 465 of file pathkeys.c.

 {
     Path       *matched_path = NULL;
     ListCell   *l;
  
     foreach(l, paths)
     {
         Path       *path = (Path *) lfirst(l);
  
         /*
          * Since cost comparison is a lot cheaper than pathkey comparison, do
          * that first.  (XXX is that still true?)
          */
         if (matched_path != NULL &&
             compare_fractional_path_costs(matched_path, path, fraction) <= 0)
             continue;
  
         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
             bms_is_subset(PATH_REQ_OUTER(path), required_outer))
             matched_path = path;
     }
     return matched_path;
 }

References bms_is_subset(), compare_fractional_path_costs(), lfirst, PATH_REQ_OUTER, Path::pathkeys, and pathkeys_contained_in().

Referenced by build_minmax_path(), and generate_orderedappend_paths().

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List * paths )

Definition at line 498 of file pathkeys.c.

 {
     ListCell   *l;
  
     foreach(l, paths)
     {
         Path       *innerpath = (Path *) lfirst(l);
  
         if (innerpath->parallel_safe &&
             bms_is_empty(PATH_REQ_OUTER(innerpath)))
             return innerpath;
     }
  
     return NULL;
 }

References bms_is_empty, lfirst, Path::parallel_safe, and PATH_REQ_OUTER.

Referenced by add_paths_to_append_rel(), hash_inner_and_outer(), match_unsorted_outer(), and sort_inner_and_outer().

◆ get_cheapest_path_for_pathkeys()

Path* get_cheapest_path_for_pathkeys	(	List *	paths,
		List *	pathkeys,
		Relids	required_outer,
		CostSelector	cost_criterion,
		bool	require_parallel_safe
	)

Definition at line 420 of file pathkeys.c.

 {
     Path       *matched_path = NULL;
     ListCell   *l;
  
     foreach(l, paths)
     {
         Path       *path = (Path *) lfirst(l);
  
         /*
          * Since cost comparison is a lot cheaper than pathkey comparison, do
          * that first.  (XXX is that still true?)
          */
         if (matched_path != NULL &&
             compare_path_costs(matched_path, path, cost_criterion) <= 0)
             continue;
  
         if (require_parallel_safe && !path->parallel_safe)
             continue;
  
         if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
             bms_is_subset(PATH_REQ_OUTER(path), required_outer))
             matched_path = path;
     }
     return matched_path;
 }

References bms_is_subset(), compare_path_costs(), lfirst, Path::parallel_safe, PATH_REQ_OUTER, Path::pathkeys, and pathkeys_contained_in().

Referenced by generate_mergejoin_paths(), generate_orderedappend_paths(), and get_cheapest_parameterized_child_path().

◆ get_eclass_for_sort_expr()

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

Definition at line 587 of file equivclass.c.

 {
     JoinDomain *jdomain;
     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);
  
     /*
      * Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER
      * BY, etc), they can be presumed to belong to the top JoinDomain.
      */
     jdomain = linitial_node(JoinDomain, root->join_domains);
  
     /*
      * 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;
  
             /*
              * Match constants only within the same JoinDomain (see
              * optimizer/README).
              */
             if (cur_em->em_is_const && cur_em->em_jdomain != jdomain)
                 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_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");
  
     /*
      * Get the precise set of relids appearing in the expression.
      */
     expr_relids = pull_varnos(root, (Node *) expr);
  
     newem = add_eq_member(newec, copyObject(expr), expr_relids,
                           jdomain, NULL, 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];
  
             if (rel == NULL)    /* must be an outer join */
             {
                 Assert(bms_is_member(i, root->outer_join_rels));
                 continue;
             }
  
             Assert(rel->reloptkind == RELOPT_BASEREL);
  
             rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
                                                  ec_index);
         }
     }
  
     MemoryContextSwitchTo(oldcontext);
  
     return newec;
 }

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

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause	(	PlannerInfo *	root,
		RelOptInfo *	rel1
	)

Definition at line 3092 of file equivclass.c.

 {
     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;
 }

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().

◆ has_useful_pathkeys()

bool has_useful_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 1985 of file pathkeys.c.

 {
     if (rel->joininfo != NIL || rel->has_eclass_joins)
         return true;            /* might be able to use pathkeys for merging */
     if (root->query_pathkeys != NIL)
         return true;            /* might be able to use them for ordering */
     return false;               /* definitely useless */
 }

References RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, NIL, and PlannerInfo::query_pathkeys.

Referenced by build_child_join_rel(), build_index_paths(), and set_append_rel_size().

◆ have_dangerous_phv()

bool have_dangerous_phv	(	PlannerInfo *	root,
		Relids	outer_relids,
		Relids	inner_params
	)

Definition at line 1305 of file joinrels.c.

 {
     ListCell   *lc;
  
     foreach(lc, root->placeholder_list)
     {
         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
  
         if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
             continue;           /* ignore, could not be a nestloop param */
         if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
             continue;           /* ignore, not relevant to this join */
         if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
             continue;           /* safe, it can be eval'd within outerrel */
         /* Otherwise, it's potentially unsafe, so reject the join */
         return true;
     }
  
     /* OK to perform the join */
     return false;
 }

References bms_is_subset(), bms_overlap(), lfirst, PlaceHolderInfo::ph_eval_at, and PlannerInfo::placeholder_list.

Referenced by join_is_legal(), and try_nestloop_path().

◆ have_join_order_restriction()

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

Definition at line 1072 of file joinrels.c.

 {
     bool        result = false;
     ListCell   *l;
  
     /*
      * If either side has a direct lateral reference to the other, attempt the
      * join regardless of outer-join considerations.
      */
     if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
         bms_overlap(rel2->relids, rel1->direct_lateral_relids))
         return true;
  
     /*
      * Likewise, if both rels are needed to compute some PlaceHolderVar,
      * attempt the join regardless of outer-join considerations.  (This is not
      * very desirable, because a PHV with a large eval_at set will cause a lot
      * of probably-useless joins to be considered, but failing to do this can
      * cause us to fail to construct a plan at all.)
      */
     foreach(l, root->placeholder_list)
     {
         PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
  
         if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
             bms_is_subset(rel2->relids, phinfo->ph_eval_at))
             return true;
     }
  
     /*
      * It's possible that the rels correspond to the left and right sides of a
      * degenerate outer join, that is, one with no joinclause mentioning the
      * non-nullable side; in which case we should force the join to occur.
      *
      * Also, the two rels could represent a clauseless join that has to be
      * completed to build up the LHS or RHS of an outer join.
      */
     foreach(l, root->join_info_list)
     {
         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
  
         /* ignore full joins --- other mechanisms handle them */
         if (sjinfo->jointype == JOIN_FULL)
             continue;
  
         /* Can we perform the SJ with these rels? */
         if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
             bms_is_subset(sjinfo->min_righthand, rel2->relids))
         {
             result = true;
             break;
         }
         if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
             bms_is_subset(sjinfo->min_righthand, rel1->relids))
         {
             result = true;
             break;
         }
  
         /*
          * Might we need to join these rels to complete the RHS?  We have to
          * use "overlap" tests since either rel might include a lower SJ that
          * has been proven to commute with this one.
          */
         if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
             bms_overlap(sjinfo->min_righthand, rel2->relids))
         {
             result = true;
             break;
         }
  
         /* Likewise for the LHS. */
         if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
             bms_overlap(sjinfo->min_lefthand, rel2->relids))
         {
             result = true;
             break;
         }
     }
  
     /*
      * We do not force the join to occur if either input rel can legally be
      * joined to anything else using joinclauses.  This essentially means that
      * clauseless bushy joins are put off as long as possible. The reason is
      * that when there is a join order restriction high up in the join tree
      * (that is, with many rels inside the LHS or RHS), we would otherwise
      * expend lots of effort considering very stupid join combinations within
      * its LHS or RHS.
      */
     if (result)
     {
         if (has_legal_joinclause(root, rel1) ||
             has_legal_joinclause(root, rel2))
             result = false;
     }
  
     return result;
 }

References bms_is_subset(), bms_overlap(), RelOptInfo::direct_lateral_relids, has_legal_joinclause(), JOIN_FULL, PlannerInfo::join_info_list, SpecialJoinInfo::jointype, lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, PlaceHolderInfo::ph_eval_at, PlannerInfo::placeholder_list, and RelOptInfo::relids.

Referenced by desirable_join(), join_search_one_level(), and make_rels_by_clause_joins().

◆ have_relevant_eclass_joinclause()

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

Definition at line 3016 of file equivclass.c.

 {
     Bitmapset  *matching_ecs;
     int         i;
  
     /*
      * Examine only eclasses mentioning both rel1 and rel2.
      *
      * Note that we do not consider the possibility of an eclass generating
      * "join" clauses that mention just one of the rels plus an outer join
      * that could be formed from them.  Although such clauses must be
      * correctly enforced when we form the outer join, they don't seem like
      * sufficient reason to prioritize this join over other ones.  The join
      * ordering rules will force the join to be made when necessary.
      */
     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;
 }

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().

◆ indexcol_is_bool_constant_for_query()

bool indexcol_is_bool_constant_for_query	(	PlannerInfo *	root,
		IndexOptInfo *	index,
		int	indexcol
	)

Definition at line 3662 of file indxpath.c.

 {
     ListCell   *lc;
  
     /* If the index isn't boolean, we can't possibly get a match */
     if (!IsBooleanOpfamily(index->opfamily[indexcol]))
         return false;
  
     /* Check each restriction clause for the index's rel */
     foreach(lc, index->rel->baserestrictinfo)
     {
         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
  
         /*
          * As in match_clause_to_indexcol, never match pseudoconstants to
          * indexes.  (It might be semantically okay to do so here, but the
          * odds of getting a match are negligible, so don't waste the cycles.)
          */
         if (rinfo->pseudoconstant)
             continue;
  
         /* See if we can match the clause's expression to the index column */
         if (match_boolean_index_clause(root, rinfo, indexcol, index))
             return true;
     }
  
     return false;
 }

References IsBooleanOpfamily(), lfirst, and match_boolean_index_clause().

Referenced by build_index_pathkeys().

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses	(	PlannerInfo *	root,
		RestrictInfo *	restrictinfo
	)

Definition at line 1230 of file pathkeys.c.

 {
     Expr       *clause = restrictinfo->clause;
     Oid         lefttype,
                 righttype;
  
     /* Should be a mergeclause ... */
     Assert(restrictinfo->mergeopfamilies != NIL);
     /* ... with links not yet set */
     Assert(restrictinfo->left_ec == NULL);
     Assert(restrictinfo->right_ec == NULL);
  
     /* Need the declared input types of the operator */
     op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
  
     /* Find or create a matching EquivalenceClass for each side */
     restrictinfo->left_ec =
         get_eclass_for_sort_expr(root,
                                  (Expr *) get_leftop(clause),
                                  restrictinfo->mergeopfamilies,
                                  lefttype,
                                  ((OpExpr *) clause)->inputcollid,
                                  0,
                                  NULL,
                                  true);
     restrictinfo->right_ec =
         get_eclass_for_sort_expr(root,
                                  (Expr *) get_rightop(clause),
                                  restrictinfo->mergeopfamilies,
                                  righttype,
                                  ((OpExpr *) clause)->inputcollid,
                                  0,
                                  NULL,
                                  true);
 }

References Assert(), RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), NIL, and op_input_types().

Referenced by distribute_qual_to_rels().

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause	(	RestrictInfo *	rinfo,
		List *	clauselist
	)

Definition at line 3194 of file equivclass.c.

 {
     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;
 }

References lfirst.

Referenced by create_tidscan_plan().

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses	(	RestrictInfo *	rinfo,
		List *	indexclauses
	)

Definition at line 3221 of file equivclass.c.

 {
     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;
 }

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

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

◆ join_search_one_level()

void join_search_one_level	(	PlannerInfo *	root,
		int	level
	)

Definition at line 71 of file joinrels.c.

 {
     List      **joinrels = root->join_rel_level;
     ListCell   *r;
     int         k;
  
     Assert(joinrels[level] == NIL);
  
     /* Set join_cur_level so that new joinrels are added to proper list */
     root->join_cur_level = level;
  
     /*
      * First, consider left-sided and right-sided plans, in which rels of
      * exactly level-1 member relations are joined against initial relations.
      * We prefer to join using join clauses, but if we find a rel of level-1
      * members that has no join clauses, we will generate Cartesian-product
      * joins against all initial rels not already contained in it.
      */
     foreach(r, joinrels[level - 1])
     {
         RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
  
         if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
             has_join_restriction(root, old_rel))
         {
             /*
              * There are join clauses or join order restrictions relevant to
              * this rel, so consider joins between this rel and (only) those
              * initial rels it is linked to by a clause or restriction.
              *
              * At level 2 this condition is symmetric, so there is no need to
              * look at initial rels before this one in the list; we already
              * considered such joins when we were at the earlier rel.  (The
              * mirror-image joins are handled automatically by make_join_rel.)
              * In later passes (level > 2), we join rels of the previous level
              * to each initial rel they don't already include but have a join
              * clause or restriction with.
              */
             List       *other_rels_list;
             ListCell   *other_rels;
  
             if (level == 2)     /* consider remaining initial rels */
             {
                 other_rels_list = joinrels[level - 1];
                 other_rels = lnext(other_rels_list, r);
             }
             else                /* consider all initial rels */
             {
                 other_rels_list = joinrels[1];
                 other_rels = list_head(other_rels_list);
             }
  
             make_rels_by_clause_joins(root,
                                       old_rel,
                                       other_rels_list,
                                       other_rels);
         }
         else
         {
             /*
              * Oops, we have a relation that is not joined to any other
              * relation, either directly or by join-order restrictions.
              * Cartesian product time.
              *
              * We consider a cartesian product with each not-already-included
              * initial rel, whether it has other join clauses or not.  At
              * level 2, if there are two or more clauseless initial rels, we
              * will redundantly consider joining them in both directions; but
              * such cases aren't common enough to justify adding complexity to
              * avoid the duplicated effort.
              */
             make_rels_by_clauseless_joins(root,
                                           old_rel,
                                           joinrels[1]);
         }
     }
  
     /*
      * Now, consider "bushy plans" in which relations of k initial rels are
      * joined to relations of level-k initial rels, for 2 <= k <= level-2.
      *
      * We only consider bushy-plan joins for pairs of rels where there is a
      * suitable join clause (or join order restriction), in order to avoid
      * unreasonable growth of planning time.
      */
     for (k = 2;; k++)
     {
         int         other_level = level - k;
  
         /*
          * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
          * need to go as far as the halfway point.
          */
         if (k > other_level)
             break;
  
         foreach(r, joinrels[k])
         {
             RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
             List       *other_rels_list;
             ListCell   *other_rels;
             ListCell   *r2;
  
             /*
              * We can ignore relations without join clauses here, unless they
              * participate in join-order restrictions --- then we might have
              * to force a bushy join plan.
              */
             if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
                 !has_join_restriction(root, old_rel))
                 continue;
  
             if (k == other_level)
             {
                 /* only consider remaining rels */
                 other_rels_list = joinrels[k];
                 other_rels = lnext(other_rels_list, r);
             }
             else
             {
                 other_rels_list = joinrels[other_level];
                 other_rels = list_head(other_rels_list);
             }
  
             for_each_cell(r2, other_rels_list, other_rels)
             {
                 RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
  
                 if (!bms_overlap(old_rel->relids, new_rel->relids))
                 {
                     /*
                      * OK, we can build a rel of the right level from this
                      * pair of rels.  Do so if there is at least one relevant
                      * join clause or join order restriction.
                      */
                     if (have_relevant_joinclause(root, old_rel, new_rel) ||
                         have_join_order_restriction(root, old_rel, new_rel))
                     {
                         (void) make_join_rel(root, old_rel, new_rel);
                     }
                 }
             }
         }
     }
  
     /*----------
      * Last-ditch effort: if we failed to find any usable joins so far, force
      * a set of cartesian-product joins to be generated.  This handles the
      * special case where all the available rels have join clauses but we
      * cannot use any of those clauses yet.  This can only happen when we are
      * considering a join sub-problem (a sub-joinlist) and all the rels in the
      * sub-problem have only join clauses with rels outside the sub-problem.
      * An example is
      *
      *      SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
      *      WHERE a.w = c.x and b.y = d.z;
      *
      * If the "a INNER JOIN b" sub-problem does not get flattened into the
      * upper level, we must be willing to make a cartesian join of a and b;
      * but the code above will not have done so, because it thought that both
      * a and b have joinclauses.  We consider only left-sided and right-sided
      * cartesian joins in this case (no bushy).
      *----------
      */
     if (joinrels[level] == NIL)
     {
         /*
          * This loop is just like the first one, except we always call
          * make_rels_by_clauseless_joins().
          */
         foreach(r, joinrels[level - 1])
         {
             RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
  
             make_rels_by_clauseless_joins(root,
                                           old_rel,
                                           joinrels[1]);
         }
  
         /*----------
          * When special joins are involved, there may be no legal way
          * to make an N-way join for some values of N.  For example consider
          *
          * SELECT ... FROM t1 WHERE
          *   x IN (SELECT ... FROM t2,t3 WHERE ...) AND
          *   y IN (SELECT ... FROM t4,t5 WHERE ...)
          *
          * We will flatten this query to a 5-way join problem, but there are
          * no 4-way joins that join_is_legal() will consider legal.  We have
          * to accept failure at level 4 and go on to discover a workable
          * bushy plan at level 5.
          *
          * However, if there are no special joins and no lateral references
          * then join_is_legal() should never fail, and so the following sanity
          * check is useful.
          *----------
          */
         if (joinrels[level] == NIL &&
             root->join_info_list == NIL &&
             !root->hasLateralRTEs)
             elog(ERROR, "failed to build any %d-way joins", level);
     }
 }

References Assert(), bms_overlap(), elog(), ERROR, for_each_cell, RelOptInfo::has_eclass_joins, has_join_restriction(), PlannerInfo::hasLateralRTEs, have_join_order_restriction(), have_relevant_joinclause(), PlannerInfo::join_cur_level, PlannerInfo::join_info_list, RelOptInfo::joininfo, lfirst, list_head(), lnext(), make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, and RelOptInfo::relids.

Referenced by standard_join_search().

◆ make_canonical_pathkey()

PathKey* make_canonical_pathkey	(	PlannerInfo *	root,
		EquivalenceClass *	eclass,
		Oid	opfamily,
		int	strategy,
		bool	nulls_first
	)

Definition at line 54 of file pathkeys.c.

 {
     PathKey    *pk;
     ListCell   *lc;
     MemoryContext oldcontext;
  
     /* Can't make canonical pathkeys if the set of ECs might still change */
     if (!root->ec_merging_done)
         elog(ERROR, "too soon to build canonical pathkeys");
  
     /* The passed eclass might be non-canonical, so chase up to the top */
     while (eclass->ec_merged)
         eclass = eclass->ec_merged;
  
     foreach(lc, root->canon_pathkeys)
     {
         pk = (PathKey *) lfirst(lc);
         if (eclass == pk->pk_eclass &&
             opfamily == pk->pk_opfamily &&
             strategy == pk->pk_strategy &&
             nulls_first == pk->pk_nulls_first)
             return pk;
     }
  
     /*
      * Be sure canonical pathkeys are allocated in the main planning context.
      * Not an issue in normal planning, but it is for GEQO.
      */
     oldcontext = MemoryContextSwitchTo(root->planner_cxt);
  
     pk = makeNode(PathKey);
     pk->pk_eclass = eclass;
     pk->pk_opfamily = opfamily;
     pk->pk_strategy = strategy;
     pk->pk_nulls_first = nulls_first;
  
     root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
  
     MemoryContextSwitchTo(oldcontext);
  
     return pk;
 }

References PlannerInfo::canon_pathkeys, PlannerInfo::ec_merging_done, eclass(), elog(), ERROR, lappend(), lfirst, makeNode, MemoryContextSwitchTo(), PathKey::pk_nulls_first, PathKey::pk_opfamily, and PathKey::pk_strategy.

Referenced by convert_subquery_pathkeys(), get_useful_pathkeys_for_relation(), make_inner_pathkeys_for_merge(), make_pathkey_from_sortinfo(), and select_outer_pathkeys_for_merge().

◆ make_inner_pathkeys_for_merge()

List* make_inner_pathkeys_for_merge	(	PlannerInfo *	root,
		List *	mergeclauses,
		List *	outer_pathkeys
	)

Definition at line 1622 of file pathkeys.c.

 {
     List       *pathkeys = NIL;
     EquivalenceClass *lastoeclass;
     PathKey    *opathkey;
     ListCell   *lc;
     ListCell   *lop;
  
     lastoeclass = NULL;
     opathkey = NULL;
     lop = list_head(outer_pathkeys);
  
     foreach(lc, mergeclauses)
     {
         RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
         EquivalenceClass *oeclass;
         EquivalenceClass *ieclass;
         PathKey    *pathkey;
  
         update_mergeclause_eclasses(root, rinfo);
  
         if (rinfo->outer_is_left)
         {
             oeclass = rinfo->left_ec;
             ieclass = rinfo->right_ec;
         }
         else
         {
             oeclass = rinfo->right_ec;
             ieclass = rinfo->left_ec;
         }
  
         /* outer eclass should match current or next pathkeys */
         /* we check this carefully for debugging reasons */
         if (oeclass != lastoeclass)
         {
             if (!lop)
                 elog(ERROR, "too few pathkeys for mergeclauses");
             opathkey = (PathKey *) lfirst(lop);
             lop = lnext(outer_pathkeys, lop);
             lastoeclass = opathkey->pk_eclass;
             if (oeclass != lastoeclass)
                 elog(ERROR, "outer pathkeys do not match mergeclause");
         }
  
         /*
          * Often, we'll have same EC on both sides, in which case the outer
          * pathkey is also canonical for the inner side, and we can skip a
          * useless search.
          */
         if (ieclass == oeclass)
             pathkey = opathkey;
         else
             pathkey = make_canonical_pathkey(root,
                                              ieclass,
                                              opathkey->pk_opfamily,
                                              opathkey->pk_strategy,
                                              opathkey->pk_nulls_first);
  
         /*
          * Don't generate redundant pathkeys (which can happen if multiple
          * mergeclauses refer to the same EC).  Because we do this, the output
          * pathkey list isn't necessarily ordered like the mergeclauses, which
          * complicates life for create_mergejoin_plan().  But if we didn't,
          * we'd have a noncanonical sort key list, which would be bad; for one
          * reason, it certainly wouldn't match any available sort order for
          * the input relation.
          */
         if (!pathkey_is_redundant(pathkey, pathkeys))
             pathkeys = lappend(pathkeys, pathkey);
     }
  
     return pathkeys;
 }

References elog(), ERROR, lappend(), lfirst, list_head(), lnext(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

◆ make_join_rel()

RelOptInfo* make_join_rel	(	PlannerInfo *	root,
		RelOptInfo *	rel1,
		RelOptInfo *	rel2
	)

Definition at line 689 of file joinrels.c.

 {
     Relids      joinrelids;
     SpecialJoinInfo *sjinfo;
     bool        reversed;
     List       *pushed_down_joins = NIL;
     SpecialJoinInfo sjinfo_data;
     RelOptInfo *joinrel;
     List       *restrictlist;
  
     /* We should never try to join two overlapping sets of rels. */
     Assert(!bms_overlap(rel1->relids, rel2->relids));
  
     /* Construct Relids set that identifies the joinrel (without OJ as yet). */
     joinrelids = bms_union(rel1->relids, rel2->relids);
  
     /* Check validity and determine join type. */
     if (!join_is_legal(root, rel1, rel2, joinrelids,
                        &sjinfo, &reversed))
     {
         /* invalid join path */
         bms_free(joinrelids);
         return NULL;
     }
  
     /*
      * Add outer join relid(s) to form the canonical relids.  Any added outer
      * joins besides sjinfo itself are appended to pushed_down_joins.
      */
     joinrelids = add_outer_joins_to_relids(root, joinrelids, sjinfo,
                                            &pushed_down_joins);
  
     /* Swap rels if needed to match the join info. */
     if (reversed)
     {
         RelOptInfo *trel = rel1;
  
         rel1 = rel2;
         rel2 = trel;
     }
  
     /*
      * If it's a plain inner join, then we won't have found anything in
      * join_info_list.  Make up a SpecialJoinInfo so that selectivity
      * estimation functions will know what's being joined.
      */
     if (sjinfo == NULL)
     {
         sjinfo = &sjinfo_data;
         sjinfo->type = T_SpecialJoinInfo;
         sjinfo->min_lefthand = rel1->relids;
         sjinfo->min_righthand = rel2->relids;
         sjinfo->syn_lefthand = rel1->relids;
         sjinfo->syn_righthand = rel2->relids;
         sjinfo->jointype = JOIN_INNER;
         sjinfo->ojrelid = 0;
         sjinfo->commute_above_l = NULL;
         sjinfo->commute_above_r = NULL;
         sjinfo->commute_below_l = NULL;
         sjinfo->commute_below_r = NULL;
         /* we don't bother trying to make the remaining fields valid */
         sjinfo->lhs_strict = false;
         sjinfo->semi_can_btree = false;
         sjinfo->semi_can_hash = false;
         sjinfo->semi_operators = NIL;
         sjinfo->semi_rhs_exprs = NIL;
     }
  
     /*
      * Find or build the join RelOptInfo, and compute the restrictlist that
      * goes with this particular joining.
      */
     joinrel = build_join_rel(root, joinrelids, rel1, rel2,
                              sjinfo, pushed_down_joins,
                              &restrictlist);
  
     /*
      * If we've already proven this join is empty, we needn't consider any
      * more paths for it.
      */
     if (is_dummy_rel(joinrel))
     {
         bms_free(joinrelids);
         return joinrel;
     }
  
     /* Add paths to the join relation. */
     populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
                                 restrictlist);
  
     bms_free(joinrelids);
  
     return joinrel;
 }

References add_outer_joins_to_relids(), Assert(), bms_free(), bms_overlap(), bms_union(), build_join_rel(), SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, SpecialJoinInfo::commute_below_r, is_dummy_rel(), JOIN_INNER, join_is_legal(), SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SpecialJoinInfo::ojrelid, populate_joinrel_with_paths(), RelOptInfo::relids, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by join_search_one_level(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), and merge_clump().

◆ make_one_rel()

RelOptInfo* make_one_rel	(	PlannerInfo *	root,
		List *	joinlist
	)

Definition at line 174 of file allpaths.c.

 {
     RelOptInfo *rel;
     Index       rti;
     double      total_pages;
  
     /* Mark base rels as to whether we care about fast-start plans */
     set_base_rel_consider_startup(root);
  
     /*
      * Compute size estimates and consider_parallel flags for each base rel.
      */
     set_base_rel_sizes(root);
  
     /*
      * We should now have size estimates for every actual table involved in
      * the query, and we also know which if any have been deleted from the
      * query by join removal, pruned by partition pruning, or eliminated by
      * constraint exclusion.  So we can now compute total_table_pages.
      *
      * Note that appendrels are not double-counted here, even though we don't
      * bother to distinguish RelOptInfos for appendrel parents, because the
      * parents will have pages = 0.
      *
      * XXX if a table is self-joined, we will count it once per appearance,
      * which perhaps is the wrong thing ... but that's not completely clear,
      * and detecting self-joins here is difficult, so ignore it for now.
      */
     total_pages = 0;
     for (rti = 1; rti < root->simple_rel_array_size; rti++)
     {
         RelOptInfo *brel = root->simple_rel_array[rti];
  
         /* there may be empty slots corresponding to non-baserel RTEs */
         if (brel == NULL)
             continue;
  
         Assert(brel->relid == rti); /* sanity check on array */
  
         if (IS_DUMMY_REL(brel))
             continue;
  
         if (IS_SIMPLE_REL(brel))
             total_pages += (double) brel->pages;
     }
     root->total_table_pages = total_pages;
  
     /*
      * Generate access paths for each base rel.
      */
     set_base_rel_pathlists(root);
  
     /*
      * Generate access paths for the entire join tree.
      */
     rel = make_rel_from_joinlist(root, joinlist);
  
     /*
      * The result should join all and only the query's base + outer-join rels.
      */
     Assert(bms_equal(rel->relids, root->all_query_rels));
  
     return rel;
 }

References PlannerInfo::all_query_rels, Assert(), bms_equal(), IS_DUMMY_REL, IS_SIMPLE_REL, make_rel_from_joinlist(), RelOptInfo::pages, RelOptInfo::relid, RelOptInfo::relids, set_base_rel_consider_startup(), set_base_rel_pathlists(), set_base_rel_sizes(), PlannerInfo::simple_rel_array_size, and PlannerInfo::total_table_pages.

Referenced by query_planner().

◆ make_pathkeys_for_sortclauses()

List* make_pathkeys_for_sortclauses	(	PlannerInfo *	root,
		List *	sortclauses,
		List *	tlist
	)

Definition at line 1131 of file pathkeys.c.

 {
     List       *result;
     bool        sortable;
  
     result = make_pathkeys_for_sortclauses_extended(root,
                                                     &sortclauses,
                                                     tlist,
                                                     false,
                                                     &sortable);
     /* It's caller error if not all clauses were sortable */
     Assert(sortable);
     return result;
 }

References Assert(), and make_pathkeys_for_sortclauses_extended().

Referenced by adjust_group_pathkeys_for_groupagg(), generate_nonunion_paths(), grouping_planner(), make_pathkeys_for_window(), make_union_unique(), minmax_qp_callback(), and standard_qp_callback().

◆ make_pathkeys_for_sortclauses_extended()

List* make_pathkeys_for_sortclauses_extended	(	PlannerInfo *	root,
		List **	sortclauses,
		List *	tlist,
		bool	remove_redundant,
		bool *	sortable
	)

Definition at line 1168 of file pathkeys.c.

 {
     List       *pathkeys = NIL;
     ListCell   *l;
  
     *sortable = true;
     foreach(l, *sortclauses)
     {
         SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
         Expr       *sortkey;
         PathKey    *pathkey;
  
         sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
         if (!OidIsValid(sortcl->sortop))
         {
             *sortable = false;
             continue;
         }
         pathkey = make_pathkey_from_sortop(root,
                                            sortkey,
                                            sortcl->sortop,
                                            sortcl->nulls_first,
                                            sortcl->tleSortGroupRef,
                                            true);
  
         /* Canonical form eliminates redundant ordering keys */
         if (!pathkey_is_redundant(pathkey, pathkeys))
             pathkeys = lappend(pathkeys, pathkey);
         else if (remove_redundant)
             *sortclauses = foreach_delete_current(*sortclauses, l);
     }
     return pathkeys;
 }

References foreach_delete_current, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), NIL, SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), SortGroupClause::sortop, and SortGroupClause::tleSortGroupRef.

Referenced by make_pathkeys_for_sortclauses(), and standard_qp_callback().

◆ mark_dummy_rel()

void mark_dummy_rel ( RelOptInfo * rel )

Definition at line 1382 of file joinrels.c.

 {
     MemoryContext oldcontext;
  
     /* Already marked? */
     if (is_dummy_rel(rel))
         return;
  
     /* No, so choose correct context to make the dummy path in */
     oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
  
     /* Set dummy size estimate */
     rel->rows = 0;
  
     /* Evict any previously chosen paths */
     rel->pathlist = NIL;
     rel->partial_pathlist = NIL;
  
     /* Set up the dummy path */
     add_path(rel, (Path *) create_append_path(NULL, rel, NIL, NIL,
                                               NIL, rel->lateral_relids,
                                               0, false, -1));
  
     /* Set or update cheapest_total_path and related fields */
     set_cheapest(rel);
  
     MemoryContextSwitchTo(oldcontext);
 }

References add_path(), create_append_path(), GetMemoryChunkContext(), is_dummy_rel(), RelOptInfo::lateral_relids, MemoryContextSwitchTo(), NIL, RelOptInfo::partial_pathlist, RelOptInfo::pathlist, RelOptInfo::rows, and set_cheapest().

Referenced by build_simple_rel(), generate_partitionwise_join_paths(), and populate_joinrel_with_paths().

◆ match_eclasses_to_foreign_key_col()

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

Definition at line 2490 of file equivclass.c.

 {
     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);
         EquivalenceMember *item1_em = NULL;
         EquivalenceMember *item2_em = NULL;
         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)
                 item1_em = em;
             else if (var->varno == var2varno && var->varattno == var2attno)
                 item2_em = em;
  
             /* Have we found both PK and FK column in this EC? */
             if (item1_em && item2_em)
             {
                 /*
                  * 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))
                 {
                     fkinfo->eclass[colno] = ec;
                     fkinfo->fk_eclass_member[colno] = item2_em;
                     return ec;
                 }
                 /* Otherwise, done with this EC, move on to the next */
                 break;
             }
         }
     }
     return NULL;
 }

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

Referenced by match_foreign_keys_to_quals().

◆ match_index_to_operand()

bool match_index_to_operand	(	Node *	operand,
		int	indexcol,
		IndexOptInfo *	index
	)

Definition at line 3713 of file indxpath.c.

 {
     int         indkey;
  
     /*
      * Ignore any RelabelType node above the operand.   This is needed to be
      * able to apply indexscanning in binary-compatible-operator cases. Note:
      * we can assume there is at most one RelabelType node;
      * eval_const_expressions() will have simplified if more than one.
      */
     if (operand && IsA(operand, RelabelType))
         operand = (Node *) ((RelabelType *) operand)->arg;
  
     indkey = index->indexkeys[indexcol];
     if (indkey != 0)
     {
         /*
          * Simple index column; operand must be a matching Var.
          */
         if (operand && IsA(operand, Var) &&
             index->rel->relid == ((Var *) operand)->varno &&
             indkey == ((Var *) operand)->varattno &&
             ((Var *) operand)->varnullingrels == NULL)
             return true;
     }
     else
     {
         /*
          * Index expression; find the correct expression.  (This search could
          * be avoided, at the cost of complicating all the callers of this
          * routine; doesn't seem worth it.)
          */
         ListCell   *indexpr_item;
         int         i;
         Node       *indexkey;
  
         indexpr_item = list_head(index->indexprs);
         for (i = 0; i < indexcol; i++)
         {
             if (index->indexkeys[i] == 0)
             {
                 if (indexpr_item == NULL)
                     elog(ERROR, "wrong number of index expressions");
                 indexpr_item = lnext(index->indexprs, indexpr_item);
             }
         }
         if (indexpr_item == NULL)
             elog(ERROR, "wrong number of index expressions");
         indexkey = (Node *) lfirst(indexpr_item);
  
         /*
          * Does it match the operand?  Again, strip any relabeling.
          */
         if (indexkey && IsA(indexkey, RelabelType))
             indexkey = (Node *) ((RelabelType *) indexkey)->arg;
  
         if (equal(indexkey, operand))
             return true;
     }
  
     return false;
 }

References arg, elog(), equal(), ERROR, i, IsA, lfirst, list_head(), and lnext().

Referenced by ec_member_matches_indexcol(), expand_indexqual_rowcompare(), get_actual_variable_range(), match_boolean_index_clause(), match_clause_to_indexcol(), match_clause_to_ordering_op(), match_funcclause_to_indexcol(), match_opclause_to_indexcol(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), and relation_has_unique_index_for().

◆ pathkeys_contained_in()

bool pathkeys_contained_in	(	List *	keys1,
		List *	keys2
	)

Definition at line 340 of file pathkeys.c.

 {
     switch (compare_pathkeys(keys1, keys2))
     {
         case PATHKEYS_EQUAL:
         case PATHKEYS_BETTER2:
             return true;
         default:
             break;
     }
     return false;
 }

References compare_pathkeys(), PATHKEYS_BETTER2, and PATHKEYS_EQUAL.

Referenced by add_paths_with_pathkeys_for_rel(), adjust_foreign_grouping_path_cost(), consider_groupingsets_paths(), cost_append(), create_append_plan(), create_gather_merge_path(), create_gather_merge_plan(), create_merge_append_path(), create_merge_append_plan(), create_ordered_paths(), gather_grouping_paths(), generate_mergejoin_paths(), generate_orderedappend_paths(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_path_for_pathkeys(), try_mergejoin_path(), and try_partial_mergejoin_path().

◆ pathkeys_count_contained_in()

bool pathkeys_count_contained_in	(	List *	keys1,
		List *	keys2,
		int *	n_common
	)

Definition at line 359 of file pathkeys.c.

 {
     int         n = 0;
     ListCell   *key1,
                *key2;
  
     /*
      * See if we can avoiding looping through both lists. This optimization
      * gains us several percent in planning time in a worst-case test.
      */
     if (keys1 == keys2)
     {
         *n_common = list_length(keys1);
         return true;
     }
     else if (keys1 == NIL)
     {
         *n_common = 0;
         return true;
     }
     else if (keys2 == NIL)
     {
         *n_common = 0;
         return false;
     }
  
     /*
      * If both lists are non-empty, iterate through both to find out how many
      * items are shared.
      */
     forboth(key1, keys1, key2, keys2)
     {
         PathKey    *pathkey1 = (PathKey *) lfirst(key1);
         PathKey    *pathkey2 = (PathKey *) lfirst(key2);
  
         if (pathkey1 != pathkey2)
         {
             *n_common = n;
             return false;
         }
         n++;
     }
  
     /* If we ended with a null value, then we've processed the whole list. */
     *n_common = n;
     return (key1 == NULL);
 }

References forboth, lfirst, list_length(), and NIL.

Referenced by add_paths_to_grouping_rel(), create_final_distinct_paths(), create_one_window_path(), create_ordered_paths(), create_partial_distinct_paths(), create_partial_grouping_paths(), create_window_paths(), gather_grouping_paths(), generate_useful_gather_paths(), and pathkeys_useful_for_ordering().

◆ process_equivalence()

bool process_equivalence	(	PlannerInfo *	root,
		RestrictInfo **	p_restrictinfo,
		JoinDomain *	jdomain
	)

Definition at line 118 of file equivclass.c.

 {
     RestrictInfo *restrictinfo = *p_restrictinfo;
     Expr       *clause = restrictinfo->clause;
     Oid         opno,
                 collation,
                 item1_type,
                 item2_type;
     Expr       *item1;
     Expr       *item2;
     Relids      item1_relids,
                 item2_relids;
     List       *opfamilies;
     EquivalenceClass *ec1,
                *ec2;
     EquivalenceMember *em1,
                *em2;
     ListCell   *lc1;
     int         ec2_idx;
  
     /* 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(root,
                                   (Expr *) ntest,
                                   restrictinfo->is_pushed_down,
                                   restrictinfo->has_clone,
                                   restrictinfo->is_clone,
                                   restrictinfo->pseudoconstant,
                                   restrictinfo->security_level,
                                   NULL,
                                   restrictinfo->incompatible_relids,
                                   restrictinfo->outer_relids);
         }
         return false;
     }
  
     /*
      * 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;
     ec2_idx = -1;
     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-&

Typedefs

Enumerations

Functions

Variables