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

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, bool below_outer_join)

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, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)

Expr *	find_em_expr_for_rel (EquivalenceClass ec, RelOptInfo rel)

void	generate_base_implied_equalities (PlannerInfo *root)

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

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

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

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

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

void	add_child_join_rel_equivalences (PlannerInfo root, int nappinfos, AppendRelInfo appinfos, RelOptInfo parent_rel, RelOptInfo *child_rel)

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

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

bool	has_relevant_eclass_joinclause (PlannerInfo root, RelOptInfo rel1)

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

bool	is_redundant_derived_clause (RestrictInfo rinfo, List clauselist)

bool	is_redundant_with_indexclauses (RestrictInfo rinfo, List indexclauses)

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, Relids nullable_relids, 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)

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)

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 116 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 181 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_rel,
		RelOptInfo *	child_rel
	)

Definition at line 2384 of file equivclass.c.

References add_eq_member(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), adjust_child_relids_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_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, get_eclass_indexes_for_relids(), i, IS_JOIN_REL, list_length(), list_nth(), RelOptInfo::relids, RELOPT_JOINREL, RELOPT_OTHER_JOINREL, RelOptInfo::reloptkind, and RelOptInfo::top_parent_relids.

Referenced by build_child_join_rel().

 {
     Relids      top_parent_relids = child_joinrel->top_parent_relids;
     Relids      child_relids = child_joinrel->relids;
     Bitmapset  *matching_ecs;
     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);
 
     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;
                 Relids      new_nullable_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_relids,
                                                           top_parent_relids);
                 }
 
                 /*
                  * Transform em_relids to match.  Note we do *not* do
                  * pull_varnos(child_expr) here, as for example the
                  * transformation might have substituted a constant, but we
                  * don't want the child member to be marked as constant.
                  */
                 new_relids = bms_difference(cur_em->em_relids,
                                             top_parent_relids);
                 new_relids = bms_add_members(new_relids, child_relids);
 
                 /*
                  * For nullable_relids, we must selectively replace parent
                  * nullable relids with child ones.
                  */
                 new_nullable_relids = cur_em->em_nullable_relids;
                 if (bms_overlap(new_nullable_relids, top_parent_relids))
                     new_nullable_relids =
                         adjust_child_relids_multilevel(root,
                                                        new_nullable_relids,
                                                        child_relids,
                                                        top_parent_relids);
 
                 (void) add_eq_member(cur_ec, child_expr,
                                      new_relids, new_nullable_relids,
                                      true, cur_em->em_datatype);
             }
         }
     }
 }

◆ add_child_rel_equivalences()

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

Definition at line 2256 of file equivclass.c.

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

Referenced by set_append_rel_size().

 {
     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 */
 
             /* 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;
                 Relids      new_nullable_relids;
 
                 if (parent_rel->reloptkind == RELOPT_BASEREL)
                 {
                     /* Simple single-level transformation */
                     child_expr = (Expr *)
                         adjust_appendrel_attrs(root,
                                                (Node *) cur_em->em_expr,
                                                1, &appinfo);
                 }
                 else
                 {
                     /* Must do multi-level transformation */
                     child_expr = (Expr *)
                         adjust_appendrel_attrs_multilevel(root,
                                                           (Node *) cur_em->em_expr,
                                                           child_relids,
                                                           top_parent_relids);
                 }
 
                 /*
                  * Transform em_relids to match.  Note we do *not* do
                  * pull_varnos(child_expr) here, as for example the
                  * transformation might have substituted a constant, but we
                  * don't want the child member to be marked as constant.
                  */
                 new_relids = bms_difference(cur_em->em_relids,
                                             top_parent_relids);
                 new_relids = bms_add_members(new_relids, child_relids);
 
                 /*
                  * And likewise for nullable_relids.  Note this code assumes
                  * parent and child relids are singletons.
                  */
                 new_nullable_relids = cur_em->em_nullable_relids;
                 if (bms_overlap(new_nullable_relids, top_parent_relids))
                 {
                     new_nullable_relids = bms_difference(new_nullable_relids,
                                                          top_parent_relids);
                     new_nullable_relids = bms_add_members(new_nullable_relids,
                                                           child_relids);
                 }
 
                 (void) add_eq_member(cur_ec, child_expr,
                                      new_relids, new_nullable_relids,
                                      true, cur_em->em_datatype);
 
                 /* Record this EC index for the child rel */
                 child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
             }
         }
     }
 }

◆ add_paths_to_append_rel()

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

Definition at line 1297 of file allpaths.c.

References accumulate_append_subpath(), add_partial_path(), add_path(), Assert, bms_equal(), bms_next_member(), RelOptInfo::cheapest_total_path, compare_pathkeys(), RelOptInfo::consider_parallel, create_append_path(), enable_parallel_append, fls(), generate_orderedappend_paths(), get_cheapest_parallel_safe_total_inner(), get_cheapest_parameterized_child_path(), IS_JOIN_REL, IS_SIMPLE_REL, lappend(), lfirst, linitial, list_concat(), list_length(), list_make1, Max, max_parallel_workers_per_gather, Min, NIL, Path::parallel_workers, Path::param_info, RelOptInfo::part_scheme, RelOptInfo::partial_pathlist, RelOptInfo::partitioned_child_rels, AppendPath::path, PATH_REQ_OUTER, Path::pathkeys, PATHKEYS_EQUAL, RelOptInfo::pathlist, RelOptInfo::relids, Path::rows, RTE_SUBQUERY, RelOptInfo::rtekind, PlannerInfo::simple_rel_array, 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().

 {
     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;
     List       *partitioned_rels = NIL;
     double      partial_rows = -1;
 
     /* If appropriate, consider parallel append */
     pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;
 
     /*
      * AppendPath generated for partitioned tables must record the RT indexes
      * of partitioned tables that are direct or indirect children of this
      * Append rel.
      *
      * AppendPath may be for a sub-query RTE (UNION ALL), in which case, 'rel'
      * itself does not represent a partitioned relation, but the child sub-
      * queries may contain references to partitioned relations.  The loop
      * below will look for such children and collect them in a list to be
      * passed to the path creation function.  (This assumes that we don't need
      * to look through multiple levels of subquery RTEs; if we ever do, we
      * could consider stuffing the list we generate here into sub-query RTE's
      * RelOptInfo, just like we do for partitioned rels, which would be used
      * when populating our parent rel with paths.  For the present, that
      * appears to be unnecessary.)
      */
     if (rel->part_scheme != NULL)
     {
         if (IS_SIMPLE_REL(rel))
             partitioned_rels = list_make1(rel->partitioned_child_rels);
         else if (IS_JOIN_REL(rel))
         {
             int         relid = -1;
             List       *partrels = NIL;
 
             /*
              * For a partitioned joinrel, concatenate the component rels'
              * partitioned_child_rels lists.
              */
             while ((relid = bms_next_member(rel->relids, relid)) >= 0)
             {
                 RelOptInfo *component;
 
                 Assert(relid >= 1 && relid < root->simple_rel_array_size);
                 component = root->simple_rel_array[relid];
                 Assert(component->part_scheme != NULL);
                 Assert(list_length(component->partitioned_child_rels) >= 1);
                 partrels = list_concat(partrels,
                                        component->partitioned_child_rels);
             }
 
             partitioned_rels = list_make1(partrels);
         }
 
         Assert(list_length(partitioned_rels) >= 1);
     }
 
     /*
      * 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;
 
         /*
          * For UNION ALLs with non-empty partitioned_child_rels, accumulate
          * the Lists of child relations.
          */
         if (rel->rtekind == RTE_SUBQUERY && childrel->partitioned_child_rels != NIL)
             partitioned_rels = lappend(partitioned_rels,
                                        childrel->partitioned_child_rels);
 
         /*
          * 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,
                                                   partitioned_rels, -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,
                                    fls(list_length(live_childrels)));
             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,
                                         partitioned_rels, -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,
                                fls(list_length(live_childrels)));
         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,
                                         partitioned_rels, 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,
                                      partitioned_rels);
 
     /*
      * 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,
                                         partitioned_rels, -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);
 
         foreach(l, childrel->partial_pathlist)
         {
             Path       *path = (Path *) lfirst(l);
             AppendPath *appendpath;
 
             /*
              * Skip paths with no pathkeys.  Also skip the cheapest partial
              * path, since we already used that above.
              */
             if (path->pathkeys == NIL ||
                 path == linitial(childrel->partial_pathlist))
                 continue;
 
             appendpath = create_append_path(root, rel, NIL, list_make1(path),
                                             NIL, NULL,
                                             path->parallel_workers, true,
                                             partitioned_rels, partial_rows);
             add_partial_path(rel, (Path *) appendpath);
         }
     }
 }

◆ 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 117 of file joinpath.c.

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, RelOptInfo::fdwroutine, FdwRoutine::GetForeignJoinPaths, 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().

 {
     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:
             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.
      */
     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/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);
 }

◆ build_expression_pathkey()

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

Definition at line 782 of file pathkeys.c.

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

Referenced by set_function_pathlist().

 {
     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,
                                           nullable_relids,
                                           opfamily,
                                           opcintype,
                                           exprCollation((Node *) expr),
                                           (strategy == BTGreaterStrategyNumber),
                                           (strategy == BTGreaterStrategyNumber),
                                           0,
                                           rel,
                                           create_it);
 
     if (cpathkey)
         pathkeys = list_make1(cpathkey);
     else
         pathkeys = NIL;
 
     return pathkeys;
 }

◆ build_index_pathkeys()

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

Definition at line 523 of file pathkeys.c.

References TargetEntry::expr, i, indexcol_is_bool_constant_for_query(), IndexOptInfo::indexcollations, IndexOptInfo::indextlist, lappend(), lfirst, make_pathkey_from_sortinfo(), NIL, IndexOptInfo::nkeycolumns, IndexOptInfo::nulls_first, IndexOptInfo::opcintype, pathkey_is_redundant(), IndexOptInfo::rel, RelOptInfo::relids, IndexOptInfo::reverse_sort, ScanDirectionIsBackward, and IndexOptInfo::sortopfamily.

Referenced by build_index_paths().

 {
     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.  Note we're
          * underneath any outer joins, so nullable_relids should be NULL.
          */
         cpathkey = make_pathkey_from_sortinfo(root,
                                               indexkey,
                                               NULL,
                                               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(index, i))
                 break;
         }
 
         i++;
     }
 
     return retval;
 }

◆ build_join_pathkeys()

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

Definition at line 1082 of file pathkeys.c.

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

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

 {
     if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
         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);
 }

◆ build_partition_pathkeys()

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

Definition at line 699 of file pathkeys.c.

References Assert, RelOptInfo::boundinfo, i, IS_SIMPLE_REL, lappend(), linitial, make_pathkey_from_sortinfo(), NIL, RelOptInfo::nparts, RelOptInfo::part_scheme, PartitionSchemeData::partcollation, RelOptInfo::partexprs, 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().

 {
     List       *retval = NIL;
     PartitionScheme partscheme = partrel->part_scheme;
     int         i;
 
     Assert(partscheme != NULL);
     Assert(partitions_are_ordered(partrel->boundinfo, partrel->nparts));
     /* 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're considering a baserel scan, so nullable_relids should be
          * NULL.  Also, 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,
                                               NULL,
                                               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;
 }

◆ canonicalize_ec_expression()

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

Definition at line 499 of file equivclass.c.

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

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

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

◆ check_index_predicates()

void check_index_predicates	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 3395 of file indxpath.c.

References PlannerInfo::all_baserels, Assert, RelOptInfo::baserestrictinfo, bms_difference(), bms_is_empty(), bms_union(), RestrictInfo::clause, contain_mutable_functions(), find_childrel_parents(), generate_join_implied_equalities(), get_plan_rowmark(), RelOptInfo::indexlist, IndexOptInfo::indpred, IndexOptInfo::indrestrictinfo, IS_SIMPLE_REL, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, PlannerInfo::parse, predicate_implied_by(), IndexOptInfo::predOK, RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, Query::resultRelation, and PlannerInfo::rowMarks.

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

 {
     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 remove its parents' relid(s) from all_baserels.
      */
     if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
         otherrels = bms_difference(root->all_baserels,
                                    find_childrel_parents(root, rel));
     else
         otherrels = bms_difference(root->all_baserels, rel->relids);
 
     if (!bms_is_empty(otherrels))
         clauselist =
             list_concat(clauselist,
                         generate_join_implied_equalities(root,
                                                          bms_union(rel->relids,
                                                                    otherrels),
                                                          otherrels,
                                                          rel));
 
     /*
      * 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/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 = (rel->relid == root->parse->resultRelation ||
                      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);
         }
     }
 }

◆ compare_pathkeys()

PathKeysComparison compare_pathkeys	(	List *	keys1,
		List *	keys2
	)

Definition at line 285 of file pathkeys.c.

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(), pathkeys_contained_in(), and set_cheapest().

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

◆ compute_parallel_worker()

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

Definition at line 3794 of file allpaths.c.

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

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

◆ convert_subquery_pathkeys()

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

Definition at line 838 of file pathkeys.c.

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, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), NIL, pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, and RelOptInfo::relids.

Referenced by set_subquery_pathlist().

 {
     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.  Likewise, it's
                  * correct to pass nullable_relids = NULL, because we're
                  * underneath any outer joins appearing in the outer query.
                  */
                 outer_ec =
                     get_eclass_for_sort_expr(root,
                                              (Expr *) outer_var,
                                              NULL,
                                              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,
                                                         NULL,
                                                         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;
 }

◆ create_index_paths()

void create_index_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 232 of file indxpath.c.

References add_path(), Assert, RelOptInfo::baserestrictinfo, bms_equal_any(), bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), RelOptInfo::consider_parallel, create_bitmap_heap_path(), create_partial_bitmap_paths(), forboth, generate_bitmap_or_paths(), get_bitmap_tree_required_outer(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, IndexOptInfo::indpred, lappend(), RelOptInfo::lateral_relids, lfirst, list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, NIL, IndexOptInfo::nkeycolumns, IndexClauseSet::nonempty, IndexOptInfo::predOK, and RelOptInfo::relid.

Referenced by set_plain_rel_pathlist().

 {
     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       *path_outer;
         List       *all_path_outers;
         ListCell   *lc;
 
         /*
          * path_outer holds the parameterization of each path in bitjoinpaths
          * (to save recalculating that several times), while all_path_outers
          * holds all distinct parameterization sets.
          */
         path_outer = all_path_outers = NIL;
         foreach(lc, bitjoinpaths)
         {
             Path       *path = (Path *) lfirst(lc);
             Relids      required_outer;
 
             required_outer = get_bitmap_tree_required_outer(path);
             path_outer = lappend(path_outer, required_outer);
             if (!bms_equal_any(required_outer, all_path_outers))
                 all_path_outers = lappend(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;
             ListCell   *lco;
 
             /* Identify all the bitmap join paths needing no more than that */
             this_path_set = NIL;
             forboth(lcp, bitjoinpaths, lco, path_outer)
             {
                 Path       *path = (Path *) lfirst(lcp);
                 Relids      p_outers = (Relids) lfirst(lco);
 
                 if (bms_is_subset(p_outers, 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 = get_bitmap_tree_required_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);
         }
     }
 }

◆ create_partial_bitmap_paths()

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

Definition at line 3758 of file allpaths.c.

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

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

◆ create_tidscan_paths()

void create_tidscan_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 385 of file tidpath.c.

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

Referenced by set_plain_rel_pathlist().

 {
     List       *tidquals;
 
     /*
      * If any suitable quals exist in the rel's baserestrict list, generate a
      * plain (unparameterized) TidPath with them.
      */
     tidquals = TidQualFromRestrictInfoList(rel->baserestrictinfo, rel);
 
     if (tidquals)
     {
         /*
          * 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));
     }
 
     /*
      * 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);
 }

◆ eclass_useful_for_merging()

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

Definition at line 2766 of file equivclass.c.

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

Referenced by get_useful_ecs_for_relation(), and pathkeys_useful_for_merging().

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

◆ exprs_known_equal()

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

Definition at line 2113 of file equivclass.c.

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

Referenced by add_unique_group_var().

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

◆ find_em_expr_for_rel()

Expr* find_em_expr_for_rel	(	EquivalenceClass *	ec,
		RelOptInfo *	rel
	)

Definition at line 782 of file equivclass.c.

References bms_is_empty(), bms_is_subset(), EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_relids, lfirst, and RelOptInfo::relids.

 {
     ListCell   *lc_em;
 
     foreach(lc_em, ec->ec_members)
     {
         EquivalenceMember *em = lfirst(lc_em);
 
         if (bms_is_subset(em->em_relids, rel->relids) &&
             !bms_is_empty(em->em_relids))
         {
             /*
              * If there is more than one equivalence member whose Vars are
              * taken entirely from this relation, we'll be content to choose
              * any one of those.
              */
             return em->em_expr;
         }
     }
 
     /* We didn't find any suitable equivalence class expression */
     return NULL;
 }

◆ find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1262 of file pathkeys.c.

References i, lappend(), RestrictInfo::left_ec, lfirst, list_concat(), NIL, RestrictInfo::outer_is_left, PathKey::pk_eclass, RestrictInfo::right_ec, and update_mergeclause_eclasses().

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

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

◆ generate_base_implied_equalities()

void generate_base_implied_equalities ( PlannerInfo * root )

Definition at line 855 of file equivclass.c.

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

Referenced by query_planner().

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

◆ generate_gather_paths()

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

Definition at line 2685 of file allpaths.c.

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

Referenced by generate_useful_gather_paths().

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

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

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

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

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

◆ generate_join_implied_equalities()

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

Definition at line 1154 of file equivclass.c.

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

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

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

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

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

Referenced by get_joinrel_parampathinfo().

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

◆ generate_partitionwise_join_paths()

void generate_partitionwise_join_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 3882 of file allpaths.c.

References add_paths_to_append_rel(), Alias::aliasname, Assert, RelOptInfo::baserestrictinfo, bms_next_member(), RelOptInfo::cheapest_parameterized_paths, RelOptInfo::cheapest_startup_path, RelOptInfo::cheapest_total_path, check_stack_depth(), RestrictInfo::clause, RelOptInfo::consider_partitionwise_join, RangeTblEntry::eref, generate_partitionwise_join_paths(), i, JoinPath::innerjoinpath, MergePath::innersortkeys, IS_DUMMY_REL, IS_JOIN_REL, IS_PARTITIONED_REL, IsA, RelOptInfo::joininfo, JoinPath::joinrestrictinfo, lappend(), lfirst, list_free(), lnext(), mark_dummy_rel(), MergePath::materialize_inner, NIL, nodeTag, RelOptInfo::nparts, JoinPath::outerjoinpath, MergePath::outersortkeys, Path::param_info, Path::parent, PlannerInfo::parse, RelOptInfo::part_rels, Path::pathkeys, RelOptInfo::pathlist, Path::pathtype, ParamPathInfo::ppi_req_outer, print_expr(), print_pathkeys(), printf, RelOptInfo::relids, RelOptInfo::reltarget, RelOptInfo::rows, Path::rows, Query::rtable, set_cheapest(), PlannerInfo::simple_rte_array, Path::startup_cost, generate_unaccent_rules::stdout, subpath(), T_AggPath, T_AppendPath, T_BitmapAndPath, T_BitmapHeapPath, T_BitmapOrPath, T_CteScan, T_CustomPath, T_ForeignPath, T_FunctionScan, T_GatherMergePath, T_GatherPath, T_GroupingSetsPath, T_GroupPath, T_GroupResultPath, T_HashPath, T_IncrementalSortPath, T_IndexPath, T_LimitPath, T_LockRowsPath, T_MaterialPath, T_MergeAppendPath, T_MergePath, T_MinMaxAggPath, T_ModifyTablePath, T_NamedTuplestoreScan, T_NestPath, T_Path, T_ProjectionPath, T_ProjectSetPath, T_RecursiveUnionPath, T_Result, T_SampleScan, T_SeqScan, T_SetOpPath, T_SortPath, T_SubqueryScanPath, T_TableFuncScan, T_TidPath, T_UniquePath, T_UpperUniquePath, T_ValuesScan, T_WindowAggPath, T_WorkTableScan, Path::total_cost, and PathTarget::width.

Referenced by generate_partitionwise_join_paths(), merge_clump(), and standard_join_search().

 {
     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;
 
         /* Add partitionwise join paths for partitioned child-joins. */
         generate_partitionwise_join_paths(root, child_rel);
 
         set_cheapest(child_rel);
 
         /* Dummy children will 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);
 }

◆ generate_useful_gather_paths()

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

Definition at line 2816 of file allpaths.c.

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

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

 {
     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);
 
     /* used for explicit (full) sort paths */
     cheapest_partial_path = linitial(rel->partial_pathlist);
 
     /*
      * Consider incremental sort paths for each interesting ordering.
      */
     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;
 
             /*
              * If the path has no ordering at all, then we can't use either
              * incremental sort or rely on implict sorting with a gather
              * merge.
              */
             if (subpath->pathkeys == NIL)
                 continue;
 
             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 (other either kind) on top of it, so
              * we can continue here.
              */
             if (is_sorted)
                 continue;
 
             /*
              * Consider regular sort for the cheapest partial path (for each
              * useful pathkeys). We know the path is not sorted, because we'd
              * not get here otherwise.
              *
              * 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 (cheapest_partial_path == subpath)
             {
                 Path       *tmp;
 
                 tmp = (Path *) create_sort_path(root,
                                                 rel,
                                                 subpath,
                                                 useful_pathkeys,
                                                 -1.0);
 
                 rows = tmp->rows * tmp->parallel_workers;
 
                 path = create_gather_merge_path(root, rel,
                                                 tmp,
                                                 rel->reltarget,
                                                 tmp->pathkeys,
                                                 NULL,
                                                 rowsp);
 
                 add_path(rel, &path->path);
 
                 /* Fall through */
             }
 
             /*
              * Consider incremental sort, but only when the subpath is already
              * partially sorted on a pathkey prefix.
              */
             if (enable_incremental_sort && presorted_keys > 0)
             {
                 Path       *tmp;
 
                 /*
                  * We should have already excluded pathkeys of length 1
                  * because then presorted_keys > 0 would imply is_sorted was
                  * true.
                  */
                 Assert(list_length(useful_pathkeys) != 1);
 
                 tmp = (Path *) create_incremental_sort_path(root,
                                                             rel,
                                                             subpath,
                                                             useful_pathkeys,
                                                             presorted_keys,
                                                             -1);
 
                 path = create_gather_merge_path(root, rel,
                                                 tmp,
                                                 rel->reltarget,
                                                 tmp->pathkeys,
                                                 NULL,
                                                 rowsp);
 
                 add_path(rel, &path->path);
             }
         }
     }
 }

◆ 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 449 of file pathkeys.c.

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

Referenced by build_minmax_path().

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

◆ get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner ( List * paths )

Definition at line 482 of file pathkeys.c.

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

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

◆ 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 404 of file pathkeys.c.

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

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

◆ get_eclass_for_sort_expr()

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

Definition at line 625 of file equivclass.c.

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

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

◆ has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause	(	PlannerInfo *	root,
		RelOptInfo *	rel1
	)

Definition at line 2722 of file equivclass.c.

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

Referenced by build_join_rel().

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

◆ has_useful_pathkeys()

bool has_useful_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 1910 of file pathkeys.c.

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

 {
     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 */
 }

◆ have_dangerous_phv()

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

Definition at line 1184 of file joinrels.c.

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

Referenced by join_is_legal(), and try_nestloop_path().

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

◆ have_join_order_restriction()

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

Definition at line 951 of file joinrels.c.

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

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

◆ have_relevant_eclass_joinclause()

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

Definition at line 2655 of file equivclass.c.

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

Referenced by have_relevant_joinclause().

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

◆ indexcol_is_bool_constant_for_query()

bool indexcol_is_bool_constant_for_query	(	IndexOptInfo *	index,
		int	indexcol
	)

Definition at line 3757 of file indxpath.c.

References RelOptInfo::baserestrictinfo, lfirst, match_boolean_index_clause(), IndexOptInfo::opfamily, RestrictInfo::pseudoconstant, and IndexOptInfo::rel.

Referenced by build_index_pathkeys().

 {
     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(rinfo, indexcol, index))
             return true;
     }
 
     return false;
 }

◆ initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses	(	PlannerInfo *	root,
		RestrictInfo *	restrictinfo
	)

Definition at line 1179 of file pathkeys.c.

References Assert, RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), RestrictInfo::left_ec, RestrictInfo::mergeopfamilies, NIL, RestrictInfo::nullable_relids, op_input_types(), and RestrictInfo::right_ec.

Referenced by distribute_qual_to_rels().

 {
     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->nullable_relids,
                                  restrictinfo->mergeopfamilies,
                                  lefttype,
                                  ((OpExpr *) clause)->inputcollid,
                                  0,
                                  NULL,
                                  true);
     restrictinfo->right_ec =
         get_eclass_for_sort_expr(root,
                                  (Expr *) get_rightop(clause),
                                  restrictinfo->nullable_relids,
                                  restrictinfo->mergeopfamilies,
                                  righttype,
                                  ((OpExpr *) clause)->inputcollid,
                                  0,
                                  NULL,
                                  true);
 }

◆ is_redundant_derived_clause()

bool is_redundant_derived_clause	(	RestrictInfo *	rinfo,
		List *	clauselist
	)

Definition at line 2824 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_tidscan_plan().

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

◆ is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses	(	RestrictInfo *	rinfo,
		List *	indexclauses
	)

Definition at line 2851 of file equivclass.c.

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

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

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

◆ join_search_one_level()

void join_search_one_level	(	PlannerInfo *	root,
		int	level
	)

Definition at line 71 of file joinrels.c.

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, PlannerInfo::join_rel_level, 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().

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

◆ 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.

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

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

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

◆ make_inner_pathkeys_for_merge()

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

Definition at line 1547 of file pathkeys.c.

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