paths.h File Reference

#include "nodes/pathnodes.h"

Include dependency graph for paths.h:

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

Go to the source code of this file.

Typedefs
typedef void(*	set_rel_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *rel, Index rti, RangeTblEntry *rte)
typedef void(*	set_join_pathlist_hook_type) (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, JoinPathExtraData *extra)
typedef RelOptInfo *(*	join_search_hook_type) (PlannerInfo *root, int levels_needed, List *initial_rels)
typedef bool(*	ec_matches_callback_type) (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg)

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

Functions
RelOptInfo *	make_one_rel (PlannerInfo *root, List *joinlist)
RelOptInfo *	standard_join_search (PlannerInfo *root, int levels_needed, List *initial_rels)
void	generate_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
void	generate_useful_gather_paths (PlannerInfo *root, RelOptInfo *rel, bool override_rows)
int	compute_parallel_worker (RelOptInfo *rel, double heap_pages, double index_pages, int max_workers)
void	create_partial_bitmap_paths (PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
void	generate_partitionwise_join_paths (PlannerInfo *root, RelOptInfo *rel)
void	create_index_paths (PlannerInfo *root, RelOptInfo *rel)
bool	relation_has_unique_index_for (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
bool	indexcol_is_bool_constant_for_query (PlannerInfo *root, IndexOptInfo *index, int indexcol)
bool	match_index_to_operand (Node *operand, int indexcol, IndexOptInfo *index)
void	check_index_predicates (PlannerInfo *root, RelOptInfo *rel)
bool	create_tidscan_paths (PlannerInfo *root, RelOptInfo *rel)
void	add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
void	join_search_one_level (PlannerInfo *root, int level)
RelOptInfo *	make_join_rel (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
Relids	add_outer_joins_to_relids (PlannerInfo *root, Relids input_relids, SpecialJoinInfo *sjinfo, List **pushed_down_joins)
bool	have_join_order_restriction (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
bool	have_dangerous_phv (PlannerInfo *root, Relids outer_relids, Relids inner_params)
void	mark_dummy_rel (RelOptInfo *rel)
void	init_dummy_sjinfo (SpecialJoinInfo *sjinfo, Relids left_relids, Relids right_relids)
bool	process_equivalence (PlannerInfo *root, RestrictInfo **p_restrictinfo, JoinDomain *jdomain)
Expr *	canonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)
void	reconsider_outer_join_clauses (PlannerInfo *root)
EquivalenceClass *	get_eclass_for_sort_expr (PlannerInfo *root, Expr *expr, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
EquivalenceMember *	find_ec_member_matching_expr (EquivalenceClass *ec, Expr *expr, Relids relids)
EquivalenceMember *	find_computable_ec_member (PlannerInfo *root, EquivalenceClass *ec, List *exprs, Relids relids, bool require_parallel_safe)
bool	relation_can_be_sorted_early (PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, bool require_parallel_safe)
void	generate_base_implied_equalities (PlannerInfo *root)
List *	generate_join_implied_equalities (PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
List *	generate_join_implied_equalities_for_ecs (PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
bool	exprs_known_equal (PlannerInfo *root, Node *item1, Node *item2)
EquivalenceClass *	match_eclasses_to_foreign_key_col (PlannerInfo *root, ForeignKeyOptInfo *fkinfo, int colno)
RestrictInfo *	find_derived_clause_for_ec_member (EquivalenceClass *ec, EquivalenceMember *em)
void	add_child_rel_equivalences (PlannerInfo *root, AppendRelInfo *appinfo, RelOptInfo *parent_rel, RelOptInfo *child_rel)
void	add_child_join_rel_equivalences (PlannerInfo *root, int nappinfos, AppendRelInfo **appinfos, RelOptInfo *parent_joinrel, RelOptInfo *child_joinrel)
void	add_setop_child_rel_equivalences (PlannerInfo *root, RelOptInfo *child_rel, List *child_tlist, List *setop_pathkeys)
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)
List *	get_useful_group_keys_orderings (PlannerInfo *root, Path *path)
Path *	get_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Path *	get_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
Path *	get_cheapest_parallel_safe_total_inner (List *paths)
List *	build_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
List *	build_partition_pathkeys (PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys)
List *	build_expression_pathkey (PlannerInfo *root, Expr *expr, Oid opno, Relids rel, bool create_it)
List *	convert_subquery_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist)
List *	build_join_pathkeys (PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
List *	make_pathkeys_for_sortclauses (PlannerInfo *root, List *sortclauses, List *tlist)
List *	make_pathkeys_for_sortclauses_extended (PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool *sortable, bool set_ec_sortref)
void	initialize_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
void	update_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
List *	find_mergeclauses_for_outer_pathkeys (PlannerInfo *root, List *pathkeys, List *restrictinfos)
List *	select_outer_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
List *	make_inner_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
List *	trim_mergeclauses_for_inner_pathkeys (PlannerInfo *root, List *mergeclauses, List *pathkeys)
List *	truncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
bool	has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
List *	append_pathkeys (List *target, List *source)
PathKey *	make_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
void	add_paths_to_append_rel (PlannerInfo *root, RelOptInfo *rel, List *live_childrels)

Variables
PGDLLIMPORT bool	enable_geqo
PGDLLIMPORT int	geqo_threshold
PGDLLIMPORT int	min_parallel_table_scan_size
PGDLLIMPORT int	min_parallel_index_scan_size
PGDLLIMPORT bool	enable_group_by_reordering
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 119 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 46 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 37 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 30 of file paths.h.

Enumeration Type Documentation

PathKeysComparison

enum PathKeysComparison

Enumerator
PATHKEYS_EQUAL
PATHKEYS_BETTER1
PATHKEYS_BETTER2
PATHKEYS_DIFFERENT

Definition at line 200 of file paths.h.

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

Function Documentation

add_child_join_rel_equivalences()

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

Definition at line 2758 of file equivclass.c.

{
    Relids      top_parent_relids = child_joinrel->top_parent_relids;
    Relids      child_relids = child_joinrel->relids;
    Bitmapset  *matching_ecs;
    MemoryContext oldcontext;
    int         i;
 
    Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel));
 
    /* We need consider only ECs that mention the parent joinrel */
    matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids);
 
    /*
     * If we're being called during GEQO join planning, we still have to
     * create any new EC members in the main planner context, to avoid having
     * a corrupt EC data structure after the GEQO context is reset.  This is
     * problematic since we'll leak memory across repeated GEQO cycles.  For
     * now, though, bloat is better than crash.  If it becomes a real issue
     * we'll have to do something to avoid generating duplicate EC members.
     */
    oldcontext = MemoryContextSwitchTo(root->planner_cxt);
 
    i = -1;
    while ((i = bms_next_member(matching_ecs, i)) >= 0)
    {
        EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
        int         num_members;
 
        /*
         * If this EC contains a volatile expression, then generating child
         * EMs would be downright dangerous, so skip it.  We rely on a
         * volatile EC having only one EM.
         */
        if (cur_ec->ec_has_volatile)
            continue;
 
        /* Sanity check on get_eclass_indexes_for_relids result */
        Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids));
 
        /*
         * We don't use foreach() here because there's no point in scanning
         * newly-added child members, so we can stop after the last
         * pre-existing EC member.
         */
        num_members = list_length(cur_ec->ec_members);
        for (int pos = 0; pos < num_members; pos++)
        {
            EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
 
            if (cur_em->em_is_const)
                continue;       /* ignore consts here */
 
            /*
             * We consider only original EC members here, not
             * already-transformed child members.
             */
            if (cur_em->em_is_child)
                continue;       /* ignore children here */
 
            /*
             * We may ignore expressions that reference a single baserel,
             * because add_child_rel_equivalences should have handled them.
             */
            if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE)
                continue;
 
            /* Does this member reference child's topmost parent rel? */
            if (bms_overlap(cur_em->em_relids, top_parent_relids))
            {
                /* Yes, generate transformed child version */
                Expr       *child_expr;
                Relids      new_relids;
 
                if (parent_joinrel->reloptkind == RELOPT_JOINREL)
                {
                    /* Simple single-level transformation */
                    child_expr = (Expr *)
                        adjust_appendrel_attrs(root,
                                               (Node *) cur_em->em_expr,
                                               nappinfos, appinfos);
                }
                else
                {
                    /* Must do multi-level transformation */
                    Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
                    child_expr = (Expr *)
                        adjust_appendrel_attrs_multilevel(root,
                                                          (Node *) cur_em->em_expr,
                                                          child_joinrel,
                                                          child_joinrel->top_parent);
                }
 
                /*
                 * Transform em_relids to match.  Note we do *not* do
                 * pull_varnos(child_expr) here, as for example the
                 * transformation might have substituted a constant, but we
                 * don't want the child member to be marked as constant.
                 */
                new_relids = bms_difference(cur_em->em_relids,
                                            top_parent_relids);
                new_relids = bms_add_members(new_relids, child_relids);
 
                (void) add_eq_member(cur_ec, child_expr, new_relids,
                                     cur_em->em_jdomain,
                                     cur_em, cur_em->em_datatype);
            }
        }
    }
 
    MemoryContextSwitchTo(oldcontext);
}

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

Referenced by build_child_join_rel().

add_child_rel_equivalences()

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

Definition at line 2636 of file equivclass.c.

{
    Relids      top_parent_relids = child_rel->top_parent_relids;
    Relids      child_relids = child_rel->relids;
    int         i;
 
    /*
     * EC merging should be complete already, so we can use the parent rel's
     * eclass_indexes to avoid searching all of root->eq_classes.
     */
    Assert(root->ec_merging_done);
    Assert(IS_SIMPLE_REL(parent_rel));
 
    i = -1;
    while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
    {
        EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
        int         num_members;
 
        /*
         * If this EC contains a volatile expression, then generating child
         * EMs would be downright dangerous, so skip it.  We rely on a
         * volatile EC having only one EM.
         */
        if (cur_ec->ec_has_volatile)
            continue;
 
        /* Sanity check eclass_indexes only contain ECs for parent_rel */
        Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));
 
        /*
         * We don't use foreach() here because there's no point in scanning
         * newly-added child members, so we can stop after the last
         * pre-existing EC member.
         */
        num_members = list_length(cur_ec->ec_members);
        for (int pos = 0; pos < num_members; pos++)
        {
            EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);
 
            if (cur_em->em_is_const)
                continue;       /* ignore consts here */
 
            /*
             * We consider only original EC members here, not
             * already-transformed child members.  Otherwise, if some original
             * member expression references more than one appendrel, we'd get
             * an O(N^2) explosion of useless derived expressions for
             * combinations of children.  (But add_child_join_rel_equivalences
             * may add targeted combinations for partitionwise-join purposes.)
             */
            if (cur_em->em_is_child)
                continue;       /* ignore children here */
 
            /*
             * Consider only members that reference and can be computed at
             * child's topmost parent rel.  In particular we want to exclude
             * parent-rel Vars that have nonempty varnullingrels.  Translating
             * those might fail, if the transformed expression wouldn't be a
             * simple Var; and in any case it wouldn't produce a member that
             * has any use in creating plans for the child rel.
             */
            if (bms_is_subset(cur_em->em_relids, top_parent_relids) &&
                !bms_is_empty(cur_em->em_relids))
            {
                /* OK, generate transformed child version */
                Expr       *child_expr;
                Relids      new_relids;
 
                if (parent_rel->reloptkind == RELOPT_BASEREL)
                {
                    /* Simple single-level transformation */
                    child_expr = (Expr *)
                        adjust_appendrel_attrs(root,
                                               (Node *) cur_em->em_expr,
                                               1, &appinfo);
                }
                else
                {
                    /* Must do multi-level transformation */
                    child_expr = (Expr *)
                        adjust_appendrel_attrs_multilevel(root,
                                                          (Node *) cur_em->em_expr,
                                                          child_rel,
                                                          child_rel->top_parent);
                }
 
                /*
                 * Transform em_relids to match.  Note we do *not* do
                 * pull_varnos(child_expr) here, as for example the
                 * transformation might have substituted a constant, but we
                 * don't want the child member to be marked as constant.
                 */
                new_relids = bms_difference(cur_em->em_relids,
                                            top_parent_relids);
                new_relids = bms_add_members(new_relids, child_relids);
 
                (void) add_eq_member(cur_ec, child_expr, new_relids,
                                     cur_em->em_jdomain,
                                     cur_em, cur_em->em_datatype);
 
                /* Record this EC index for the child rel */
                child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
            }
        }
    }
}

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

Referenced by set_append_rel_size().

add_outer_joins_to_relids()

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

Definition at line 801 of file joinrels.c.

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

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

Referenced by generate_join_implied_equalities(), and make_join_rel().

add_paths_to_append_rel()

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

Definition at line 1310 of file allpaths.c.

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

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

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

add_paths_to_joinrel()

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

Definition at line 125 of file joinpath.c.

{
    JoinPathExtraData extra;
    bool        mergejoin_allowed = true;
    ListCell   *lc;
    Relids      joinrelids;
 
    /*
     * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
     * between child relations, even if there is a SpecialJoinInfo node for
     * the join between the topmost parents. So, while calculating Relids set
     * representing the restriction, consider relids of topmost parent of
     * partitions.
     */
    if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
        joinrelids = joinrel->top_parent_relids;
    else
        joinrelids = joinrel->relids;
 
    extra.restrictlist = restrictlist;
    extra.mergeclause_list = NIL;
    extra.sjinfo = sjinfo;
    extra.param_source_rels = NULL;
 
    /*
     * See if the inner relation is provably unique for this outer rel.
     *
     * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
     * matter since the executor can make the equivalent optimization anyway;
     * we need not expend planner cycles on proofs.  For JOIN_UNIQUE_INNER, we
     * must be considering a semijoin whose inner side is not provably unique
     * (else reduce_unique_semijoins would've simplified it), so there's no
     * point in calling innerrel_is_unique.  However, if the LHS covers all of
     * the semijoin's min_lefthand, then it's appropriate to set inner_unique
     * because the path produced by create_unique_path will be unique relative
     * to the LHS.  (If we have an LHS that's only part of the min_lefthand,
     * that is *not* true.)  For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
     * letting that value escape this module.
     */
    switch (jointype)
    {
        case JOIN_SEMI:
        case JOIN_ANTI:
 
            /*
             * XXX it may be worth proving this to allow a Memoize to be
             * considered for Nested Loop Semi/Anti Joins.
             */
            extra.inner_unique = false; /* well, unproven */
            break;
        case JOIN_UNIQUE_INNER:
            extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
                                               outerrel->relids);
            break;
        case JOIN_UNIQUE_OUTER:
            extra.inner_unique = innerrel_is_unique(root,
                                                    joinrel->relids,
                                                    outerrel->relids,
                                                    innerrel,
                                                    JOIN_INNER,
                                                    restrictlist,
                                                    false);
            break;
        default:
            extra.inner_unique = innerrel_is_unique(root,
                                                    joinrel->relids,
                                                    outerrel->relids,
                                                    innerrel,
                                                    jointype,
                                                    restrictlist,
                                                    false);
            break;
    }
 
    /*
     * Find potential mergejoin clauses.  We can skip this if we are not
     * interested in doing a mergejoin.  However, mergejoin may be our only
     * way of implementing a full outer join, so override enable_mergejoin if
     * it's a full join.
     */
    if (enable_mergejoin || jointype == JOIN_FULL)
        extra.mergeclause_list = select_mergejoin_clauses(root,
                                                          joinrel,
                                                          outerrel,
                                                          innerrel,
                                                          restrictlist,
                                                          jointype,
                                                          &mergejoin_allowed);
 
    /*
     * If it's SEMI, ANTI, or inner_unique join, compute correction factors
     * for cost estimation.  These will be the same for all paths.
     */
    if (jointype == JOIN_SEMI || jointype == JOIN_ANTI || extra.inner_unique)
        compute_semi_anti_join_factors(root, joinrel, outerrel, innerrel,
                                       jointype, sjinfo, restrictlist,
                                       &extra.semifactors);
 
    /*
     * Decide whether it's sensible to generate parameterized paths for this
     * joinrel, and if so, which relations such paths should require.  There
     * is usually no need to create a parameterized result path unless there
     * is a join order restriction that prevents joining one of our input rels
     * directly to the parameter source rel instead of joining to the other
     * input rel.  (But see allow_star_schema_join().)  This restriction
     * reduces the number of parameterized paths we have to deal with at
     * higher join levels, without compromising the quality of the resulting
     * plan.  We express the restriction as a Relids set that must overlap the
     * parameterization of any proposed join path.  Note: param_source_rels
     * should contain only baserels, not OJ relids, so starting from
     * all_baserels not all_query_rels is correct.
     */
    foreach(lc, root->join_info_list)
    {
        SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);
 
        /*
         * SJ is relevant to this join if we have some part of its RHS
         * (possibly not all of it), and haven't yet joined to its LHS.  (This
         * test is pretty simplistic, but should be sufficient considering the
         * join has already been proven legal.)  If the SJ is relevant, it
         * presents constraints for joining to anything not in its RHS.
         */
        if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
            !bms_overlap(joinrelids, sjinfo2->min_lefthand))
            extra.param_source_rels = bms_join(extra.param_source_rels,
                                               bms_difference(root->all_baserels,
                                                              sjinfo2->min_righthand));
 
        /* full joins constrain both sides symmetrically */
        if (sjinfo2->jointype == JOIN_FULL &&
            bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
            !bms_overlap(joinrelids, sjinfo2->min_righthand))
            extra.param_source_rels = bms_join(extra.param_source_rels,
                                               bms_difference(root->all_baserels,
                                                              sjinfo2->min_lefthand));
    }
 
    /*
     * However, when a LATERAL subquery is involved, there will simply not be
     * any paths for the joinrel that aren't parameterized by whatever the
     * subquery is parameterized by, unless its parameterization is resolved
     * within the joinrel.  So we might as well allow additional dependencies
     * on whatever residual lateral dependencies the joinrel will have.
     */
    extra.param_source_rels = bms_add_members(extra.param_source_rels,
                                              joinrel->lateral_relids);
 
    /*
     * 1. Consider mergejoin paths where both relations must be explicitly
     * sorted.  Skip this if we can't mergejoin.
     */
    if (mergejoin_allowed)
        sort_inner_and_outer(root, joinrel, outerrel, innerrel,
                             jointype, &extra);
 
    /*
     * 2. Consider paths where the outer relation need not be explicitly
     * sorted. This includes both nestloops and mergejoins where the outer
     * path is already ordered.  Again, skip this if we can't mergejoin.
     * (That's okay because we know that nestloop can't handle
     * right/right-anti/right-semi/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.  They
     * could add new paths (such as CustomPaths) by calling add_path(), or
     * add_partial_path() if parallel aware.  They could also delete or modify
     * paths added by the core code.
     */
    if (set_join_pathlist_hook)
        set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
                               jointype, &extra);
}

References bms_add_members(), bms_difference(), bms_is_subset(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, hash_inner_and_outer(), JoinPathExtraData::inner_unique, innerrel_is_unique(), JOIN_ANTI, JOIN_FULL, 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, root, 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().

add_setop_child_rel_equivalences()

void add_setop_child_rel_equivalences	(	PlannerInfo *	root,
		RelOptInfo *	child_rel,
		List *	child_tlist,
		List *	setop_pathkeys
	)

Definition at line 2888 of file equivclass.c.

{
    ListCell   *lc;
    ListCell   *lc2 = list_head(setop_pathkeys);
 
    foreach(lc, child_tlist)
    {
        TargetEntry *tle = lfirst_node(TargetEntry, lc);
        EquivalenceMember *parent_em;
        PathKey    *pk;
 
        if (tle->resjunk)
            continue;
 
        if (lc2 == NULL)
            elog(ERROR, "too few pathkeys for set operation");
 
        pk = lfirst_node(PathKey, lc2);
        parent_em = linitial(pk->pk_eclass->ec_members);
 
        /*
         * We can safely pass the parent member as the first member in the
         * ec_members list as this is added first in generate_union_paths,
         * likewise, the JoinDomain can be that of the initial member of the
         * Pathkey's EquivalenceClass.
         */
        add_eq_member(pk->pk_eclass,
                      tle->expr,
                      child_rel->relids,
                      parent_em->em_jdomain,
                      parent_em,
                      exprType((Node *) tle->expr));
 
        lc2 = lnext(setop_pathkeys, lc2);
    }
 
    /*
     * transformSetOperationStmt() ensures that the targetlist never contains
     * any resjunk columns, so all eclasses that exist in 'root' must have
     * received a new member in the loop above.  Add them to the child_rel's
     * eclass_indexes.
     */
    child_rel->eclass_indexes = bms_add_range(child_rel->eclass_indexes, 0,
                                              list_length(root->eq_classes) - 1);
}

References add_eq_member(), bms_add_range(), RelOptInfo::eclass_indexes, elog, EquivalenceMember::em_jdomain, ERROR, TargetEntry::expr, exprType(), lfirst_node, linitial, list_head(), list_length(), lnext(), RelOptInfo::relids, and root.

Referenced by build_setop_child_paths().

append_pathkeys()

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

Definition at line 106 of file pathkeys.c.

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

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

Referenced by adjust_group_pathkeys_for_groupagg(), and make_pathkeys_for_window().

build_expression_pathkey()

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

Definition at line 998 of file pathkeys.c.

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

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

Referenced by set_function_pathlist().

build_index_pathkeys()

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

Definition at line 738 of file pathkeys.c.

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

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

Referenced by build_index_paths().

build_join_pathkeys()

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

Definition at line 1292 of file pathkeys.c.

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

References Assert, JOIN_FULL, JOIN_RIGHT, JOIN_RIGHT_ANTI, JOIN_RIGHT_SEMI, NIL, root, and truncate_useless_pathkeys().

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

build_partition_pathkeys()

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

Definition at line 917 of file pathkeys.c.

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

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

Referenced by generate_orderedappend_paths().

canonicalize_ec_expression()

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

Definition at line 472 of file equivclass.c.

{
    Oid         expr_type = exprType((Node *) expr);
 
    /*
     * For a polymorphic-input-type opclass, just keep the same exposed type.
     * RECORD opclasses work like polymorphic-type ones for this purpose.
     */
    if (IsPolymorphicType(req_type) || req_type == RECORDOID)
        req_type = expr_type;
 
    /*
     * No work if the expression exposes the right type/collation already.
     */
    if (expr_type != req_type ||
        exprCollation((Node *) expr) != req_collation)
    {
        /*
         * If we have to change the type of the expression, set typmod to -1,
         * since the new type may not have the same typmod interpretation.
         * When we only have to change collation, preserve the exposed typmod.
         */
        int32       req_typmod;
 
        if (expr_type != req_type)
            req_typmod = -1;
        else
            req_typmod = exprTypmod((Node *) expr);
 
        /*
         * Use applyRelabelType so that we preserve const-flatness.  This is
         * important since eval_const_expressions has already been applied.
         */
        expr = (Expr *) applyRelabelType((Node *) expr,
                                         req_type, req_typmod, req_collation,
                                         COERCE_IMPLICIT_CAST, -1, false);
    }
 
    return expr;
}

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

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

check_index_predicates()

void check_index_predicates	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 3244 of file indxpath.c.

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

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

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

compare_pathkeys()

PathKeysComparison compare_pathkeys	(	List *	keys1,
		List *	keys2
	)

Definition at line 302 of file pathkeys.c.

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

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

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

compute_parallel_worker()

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

Definition at line 4210 of file allpaths.c.

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

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

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

convert_subquery_pathkeys()

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

Definition at line 1052 of file pathkeys.c.

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

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

Referenced by build_setop_child_paths(), set_cte_pathlist(), and set_subquery_pathlist().

create_index_paths()

void create_index_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 234 of file indxpath.c.

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

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

Referenced by set_plain_rel_pathlist().

create_partial_bitmap_paths()

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

Definition at line 4174 of file allpaths.c.

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

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

Referenced by create_index_paths().

create_tidscan_paths()

bool create_tidscan_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 498 of file tidpath.c.

{
    List       *tidquals;
    List       *tidrangequals;
    bool        isCurrentOf;
 
    /*
     * If any suitable quals exist in the rel's baserestrict list, generate a
     * plain (unparameterized) TidPath with them.
     *
     * We skip this when enable_tidscan = false, except when the qual is
     * CurrentOfExpr. In that case, a TID scan is the only correct path.
     */
    tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel,
                                           &isCurrentOf);
 
    if (tidquals != NIL && (enable_tidscan || isCurrentOf))
    {
        /*
         * 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));
 
        /*
         * When the qual is CurrentOfExpr, the path that we just added is the
         * only one the executor can handle, so we should return before adding
         * any others. Returning true lets the caller know not to add any
         * others, either.
         */
        if (isCurrentOf)
            return true;
    }
 
    /* Skip the rest if TID scans are disabled. */
    if (!enable_tidscan)
        return false;
 
    /*
     * If there are range quals in the baserestrict list, generate a
     * TidRangePath.
     */
    tidrangequals = TidRangeQualFromRestrictInfoList(rel->baserestrictinfo,
                                                     rel);
 
    if (tidrangequals != NIL)
    {
        /*
         * This path uses no join clauses, but it could still have required
         * parameterization due to LATERAL refs in its tlist.
         */
        Relids      required_outer = rel->lateral_relids;
 
        add_path(rel, (Path *) create_tidrangescan_path(root, rel,
                                                        tidrangequals,
                                                        required_outer));
    }
 
    /*
     * Try to generate parameterized TidPaths using equality clauses extracted
     * from EquivalenceClasses.  (This is important since simple "t1.ctid =
     * t2.ctid" clauses will turn into ECs.)
     */
    if (rel->has_eclass_joins)
    {
        List       *clauses;
 
        /* Generate clauses, skipping any that join to lateral_referencers */
        clauses = generate_implied_equalities_for_column(root,
                                                         rel,
                                                         ec_member_matches_ctid,
                                                         NULL,
                                                         rel->lateral_referencers);
 
        /* Generate a path for each usable join clause */
        BuildParameterizedTidPaths(root, rel, clauses);
    }
 
    /*
     * Also consider parameterized TidPaths using "loose" join quals.  Quals
     * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
     * join quals, for example.
     */
    BuildParameterizedTidPaths(root, rel, rel->joininfo);
 
    return false;
}

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

Referenced by set_plain_rel_pathlist().

eclass_useful_for_merging()

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

Definition at line 3212 of file equivclass.c.

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

References Assert, bms_is_empty, bms_is_subset(), bms_overlap(), eclass(), EquivalenceMember::em_is_child, EquivalenceMember::em_relids, IS_OTHER_REL, lfirst, list_length(), RelOptInfo::relids, and RelOptInfo::top_parent_relids.

Referenced by get_useful_ecs_for_relation(), and pathkeys_useful_for_merging().

exprs_known_equal()

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

Definition at line 2454 of file equivclass.c.

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

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

Referenced by add_unique_group_var().

find_computable_ec_member()

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

Definition at line 825 of file equivclass.c.

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

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

Referenced by prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

find_derived_clause_for_ec_member()

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

Definition at line 2596 of file equivclass.c.

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

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

Referenced by get_foreign_key_join_selectivity().

find_ec_member_matching_expr()

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

Definition at line 760 of file equivclass.c.

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

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

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

find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1527 of file pathkeys.c.

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

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

generate_base_implied_equalities()

void generate_base_implied_equalities

(

PlannerInfo *

root

)

Definition at line 1033 of file equivclass.c.

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

References Assert, bms_add_member(), bms_is_member(), bms_membership(), BMS_MULTIPLE, bms_next_member(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_relids, RelOptInfo::eclass_indexes, 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 root.

Referenced by query_planner().

generate_gather_paths()

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

Definition at line 3060 of file allpaths.c.

{
    Path       *cheapest_partial_path;
    Path       *simple_gather_path;
    ListCell   *lc;
    double      rows;
    double     *rowsp = NULL;
 
    /* If there are no partial paths, there's nothing to do here. */
    if (rel->partial_pathlist == NIL)
        return;
 
    /* Should we override the rel's rowcount estimate? */
    if (override_rows)
        rowsp = &rows;
 
    /*
     * The output of Gather is always unsorted, so there's only one partial
     * path of interest: the cheapest one.  That will be the one at the front
     * of partial_pathlist because of the way add_partial_path works.
     */
    cheapest_partial_path = linitial(rel->partial_pathlist);
    rows = compute_gather_rows(cheapest_partial_path);
    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 = compute_gather_rows(subpath);
        path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
                                        subpath->pathkeys, NULL, rowsp);
        add_path(rel, &path->path);
    }
}

References add_path(), compute_gather_rows(), create_gather_merge_path(), create_gather_path(), lfirst, linitial, NIL, RelOptInfo::partial_pathlist, GatherMergePath::path, RelOptInfo::reltarget, root, and subpath().

Referenced by generate_useful_gather_paths().

generate_implied_equalities_for_column()

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

Definition at line 2960 of file equivclass.c.

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

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

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

generate_join_implied_equalities()

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

Definition at line 1381 of file equivclass.c.

{
    List       *result = NIL;
    Relids      inner_relids = inner_rel->relids;
    Relids      nominal_inner_relids;
    Relids      nominal_join_relids;
    Bitmapset  *matching_ecs;
    int         i;
 
    /* If inner rel is a child, extra setup work is needed */
    if (IS_OTHER_REL(inner_rel))
    {
        Assert(!bms_is_empty(inner_rel->top_parent_relids));
 
        /* Fetch relid set for the topmost parent rel */
        nominal_inner_relids = inner_rel->top_parent_relids;
        /* ECs will be marked with the parent's relid, not the child's */
        nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
        nominal_join_relids = add_outer_joins_to_relids(root,
                                                        nominal_join_relids,
                                                        sjinfo,
                                                        NULL);
    }
    else
    {
        nominal_inner_relids = inner_relids;
        nominal_join_relids = join_relids;
    }
 
    /*
     * Examine all potentially-relevant eclasses.
     *
     * If we are considering an outer join, we must include "join" clauses
     * that mention either input rel plus the outer join's relid; these
     * represent post-join filter clauses that have to be applied at this
     * join.  We don't have infrastructure that would let us identify such
     * eclasses cheaply, so just fall back to considering all eclasses
     * mentioning anything in nominal_join_relids.
     *
     * At inner joins, we can be smarter: only consider eclasses mentioning
     * both input rels.
     */
    if (sjinfo && sjinfo->ojrelid != 0)
        matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids);
    else
        matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids,
                                                 outer_relids);
 
    i = -1;
    while ((i = bms_next_member(matching_ecs, i)) >= 0)
    {
        EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
        List       *sublist = NIL;
 
        /* ECs containing consts do not need any further enforcement */
        if (ec->ec_has_const)
            continue;
 
        /* Single-member ECs won't generate any deductions */
        if (list_length(ec->ec_members) <= 1)
            continue;
 
        /* Sanity check that this eclass overlaps the join */
        Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
 
        if (!ec->ec_broken)
            sublist = generate_join_implied_equalities_normal(root,
                                                              ec,
                                                              join_relids,
                                                              outer_relids,
                                                              inner_relids);
 
        /* Recover if we failed to generate required derived clauses */
        if (ec->ec_broken)
            sublist = generate_join_implied_equalities_broken(root,
                                                              ec,
                                                              nominal_join_relids,
                                                              outer_relids,
                                                              nominal_inner_relids,
                                                              inner_rel);
 
        result = list_concat(result, sublist);
    }
 
    return result;
}

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

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

generate_join_implied_equalities_for_ecs()

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

Definition at line 1481 of file equivclass.c.

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

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

Referenced by get_joinrel_parampathinfo().

generate_partitionwise_join_paths()

void generate_partitionwise_join_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 4298 of file allpaths.c.

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

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

Referenced by merge_clump(), and standard_join_search().

generate_useful_gather_paths()

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

Definition at line 3197 of file allpaths.c.

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

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

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

get_cheapest_fractional_path_for_pathkeys()

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

Definition at line 664 of file pathkeys.c.

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

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

Referenced by build_minmax_path(), and generate_orderedappend_paths().

get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner

(

List *

paths

)

Definition at line 697 of file pathkeys.c.

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

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

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

get_cheapest_path_for_pathkeys()

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

Definition at line 618 of file pathkeys.c.

{
    Path       *matched_path = NULL;
    ListCell   *l;
 
    foreach(l, paths)
    {
        Path       *path = (Path *) lfirst(l);
 
        /* If required, reject paths that are not parallel-safe */
        if (require_parallel_safe && !path->parallel_safe)
            continue;
 
        /*
         * 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 (pathkeys_contained_in(pathkeys, path->pathkeys) &&
            bms_is_subset(PATH_REQ_OUTER(path), required_outer))
            matched_path = path;
    }
    return matched_path;
}

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

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

get_eclass_for_sort_expr()

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

Definition at line 587 of file equivclass.c.

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

References add_eq_member(), Assert, bms_add_member(), bms_equal(), bms_is_member(), bms_next_member(), canonicalize_ec_expression(), contain_agg_clause(), contain_volatile_functions(), contain_window_function(), copyObject, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, RelOptInfo::eclass_indexes, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, equal(), ERROR, expression_returns_set(), i, lappend(), lfirst, linitial_node, list_copy(), list_length(), makeNode, MemoryContextSwitchTo(), NIL, pull_varnos(), RELOPT_BASEREL, RelOptInfo::reloptkind, and root.

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

get_useful_group_keys_orderings()

List* get_useful_group_keys_orderings	(	PlannerInfo *	root,
		Path *	path
	)

Definition at line 465 of file pathkeys.c.

{
    Query      *parse = root->parse;
    List       *infos = NIL;
    GroupByOrdering *info;
 
    List       *pathkeys = root->group_pathkeys;
    List       *clauses = root->processed_groupClause;
 
    /* always return at least the original pathkeys/clauses */
    info = makeNode(GroupByOrdering);
    info->pathkeys = pathkeys;
    info->clauses = clauses;
    infos = lappend(infos, info);
 
    /*
     * Should we try generating alternative orderings of the group keys? If
     * not, we produce only the order specified in the query, i.e. the
     * optimization is effectively disabled.
     */
    if (!enable_group_by_reordering)
        return infos;
 
    /*
     * Grouping sets have own and more complex logic to decide the ordering.
     */
    if (parse->groupingSets)
        return infos;
 
    /*
     * If the path is sorted in some way, try reordering the group keys to
     * match the path as much of the ordering as possible.  Then thanks to
     * incremental sort we would get this sort as cheap as possible.
     */
    if (path->pathkeys &&
        !pathkeys_contained_in(path->pathkeys, root->group_pathkeys))
    {
        int         n;
 
        n = group_keys_reorder_by_pathkeys(path->pathkeys, &pathkeys, &clauses,
                                           root->num_groupby_pathkeys);
 
        if (n > 0 &&
            (enable_incremental_sort || n == root->num_groupby_pathkeys) &&
            compare_pathkeys(pathkeys, root->group_pathkeys) != PATHKEYS_EQUAL)
        {
            info = makeNode(GroupByOrdering);
            info->pathkeys = pathkeys;
            info->clauses = clauses;
 
            infos = lappend(infos, info);
        }
    }
 
#ifdef USE_ASSERT_CHECKING
    {
        GroupByOrdering *pinfo = linitial_node(GroupByOrdering, infos);
        ListCell   *lc;
 
        /* Test consistency of info structures */
        for_each_from(lc, infos, 1)
        {
            ListCell   *lc1,
                       *lc2;
 
            info = lfirst_node(GroupByOrdering, lc);
 
            Assert(list_length(info->clauses) == list_length(pinfo->clauses));
            Assert(list_length(info->pathkeys) == list_length(pinfo->pathkeys));
            Assert(list_difference(info->clauses, pinfo->clauses) == NIL);
            Assert(list_difference_ptr(info->pathkeys, pinfo->pathkeys) == NIL);
 
            forboth(lc1, info->clauses, lc2, info->pathkeys)
            {
                SortGroupClause *sgc = lfirst_node(SortGroupClause, lc1);
                PathKey    *pk = lfirst_node(PathKey, lc2);
 
                Assert(pk->pk_eclass->ec_sortref == sgc->tleSortGroupRef);
            }
        }
    }
#endif
    return infos;
}

References Assert, GroupByOrdering::clauses, compare_pathkeys(), enable_group_by_reordering, enable_incremental_sort, for_each_from, forboth, group_keys_reorder_by_pathkeys(), lappend(), lfirst_node, linitial_node, list_difference(), list_difference_ptr(), list_length(), makeNode, NIL, parse(), GroupByOrdering::pathkeys, Path::pathkeys, pathkeys_contained_in(), PATHKEYS_EQUAL, root, and SortGroupClause::tleSortGroupRef.

Referenced by add_paths_to_grouping_rel(), and create_partial_grouping_paths().

has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause	(	PlannerInfo *	root,
		RelOptInfo *	rel1
	)

Definition at line 3168 of file equivclass.c.

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

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

Referenced by build_join_rel().

has_useful_pathkeys()

bool has_useful_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 2261 of file pathkeys.c.

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

References RelOptInfo::has_eclass_joins, RelOptInfo::joininfo, NIL, and root.

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

have_dangerous_phv()

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

Definition at line 1307 of file joinrels.c.

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

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

Referenced by join_is_legal(), and try_nestloop_path().

have_join_order_restriction()

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

Definition at line 1074 of file joinrels.c.

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

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

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

have_relevant_eclass_joinclause()

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

Definition at line 3092 of file equivclass.c.

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

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

Referenced by have_relevant_joinclause().

indexcol_is_bool_constant_for_query()

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

Definition at line 3614 of file indxpath.c.

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

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

Referenced by build_index_pathkeys().

init_dummy_sjinfo()

void init_dummy_sjinfo	(	SpecialJoinInfo *	sjinfo,
		Relids	left_relids,
		Relids	right_relids
	)

Definition at line 669 of file joinrels.c.

{
    sjinfo->type = T_SpecialJoinInfo;
    sjinfo->min_lefthand = left_relids;
    sjinfo->min_righthand = right_relids;
    sjinfo->syn_lefthand = left_relids;
    sjinfo->syn_righthand = right_relids;
    sjinfo->jointype = JOIN_INNER;
    sjinfo->ojrelid = 0;
    sjinfo->commute_above_l = NULL;
    sjinfo->commute_above_r = NULL;
    sjinfo->commute_below_l = NULL;
    sjinfo->commute_below_r = NULL;
    /* we don't bother trying to make the remaining fields valid */
    sjinfo->lhs_strict = false;
    sjinfo->semi_can_btree = false;
    sjinfo->semi_can_hash = false;
    sjinfo->semi_operators = NIL;
    sjinfo->semi_rhs_exprs = NIL;
}

References SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, SpecialJoinInfo::commute_below_r, JOIN_INNER, SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, SpecialJoinInfo::ojrelid, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by approx_tuple_count(), build_child_join_sjinfo(), compute_semi_anti_join_factors(), consider_new_or_clause(), and make_join_rel().

initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses	(	PlannerInfo *	root,
		RestrictInfo *	restrictinfo
	)

Definition at line 1446 of file pathkeys.c.

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

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

Referenced by distribute_qual_to_rels().

is_redundant_derived_clause()

bool is_redundant_derived_clause	(	RestrictInfo *	rinfo,
		List *	clauselist
	)

Definition at line 3270 of file equivclass.c.

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

References lfirst.

Referenced by create_tidscan_plan().

is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses	(	RestrictInfo *	rinfo,
		List *	indexclauses
	)

Definition at line 3297 of file equivclass.c.

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

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

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

join_search_one_level()

void join_search_one_level	(	PlannerInfo *	root,
		int	level
	)

Definition at line 72 of file joinrels.c.

{
    List      **joinrels = root->join_rel_level;
    ListCell   *r;
    int         k;
 
    Assert(joinrels[level] == NIL);
 
    /* Set join_cur_level so that new joinrels are added to proper list */
    root->join_cur_level = level;
 
    /*
     * First, consider left-sided and right-sided plans, in which rels of
     * exactly level-1 member relations are joined against initial relations.
     * We prefer to join using join clauses, but if we find a rel of level-1
     * members that has no join clauses, we will generate Cartesian-product
     * joins against all initial rels not already contained in it.
     */
    foreach(r, joinrels[level - 1])
    {
        RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 
        if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
            has_join_restriction(root, old_rel))
        {
            int         first_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.
             */
            if (level == 2)     /* consider remaining initial rels */
                first_rel = foreach_current_index(r) + 1;
            else
                first_rel = 0;
 
            make_rels_by_clause_joins(root, old_rel, joinrels[1], first_rel);
        }
        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);
            int         first_rel;
            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 */
                first_rel = foreach_current_index(r) + 1;
            else
                first_rel = 0;
 
            for_each_from(r2, joinrels[other_level], first_rel)
            {
                RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
 
                if (!bms_overlap(old_rel->relids, new_rel->relids))
                {
                    /*
                     * OK, we can build a rel of the right level from this
                     * pair of rels.  Do so if there is at least one relevant
                     * join clause or join order restriction.
                     */
                    if (have_relevant_joinclause(root, old_rel, new_rel) ||
                        have_join_order_restriction(root, old_rel, new_rel))
                    {
                        (void) make_join_rel(root, old_rel, new_rel);
                    }
                }
            }
        }
    }
 
    /*----------
     * Last-ditch effort: if we failed to find any usable joins so far, force
     * a set of cartesian-product joins to be generated.  This handles the
     * special case where all the available rels have join clauses but we
     * cannot use any of those clauses yet.  This can only happen when we are
     * considering a join sub-problem (a sub-joinlist) and all the rels in the
     * sub-problem have only join clauses with rels outside the sub-problem.
     * An example is
     *
     *      SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
     *      WHERE a.w = c.x and b.y = d.z;
     *
     * If the "a INNER JOIN b" sub-problem does not get flattened into the
     * upper level, we must be willing to make a cartesian join of a and b;
     * but the code above will not have done so, because it thought that both
     * a and b have joinclauses.  We consider only left-sided and right-sided
     * cartesian joins in this case (no bushy).
     *----------
     */
    if (joinrels[level] == NIL)
    {
        /*
         * This loop is just like the first one, except we always call
         * make_rels_by_clauseless_joins().
         */
        foreach(r, joinrels[level - 1])
        {
            RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
 
            make_rels_by_clauseless_joins(root,
                                          old_rel,
                                          joinrels[1]);
        }
 
        /*----------
         * When special joins are involved, there may be no legal way
         * to make an N-way join for some values of N.  For example consider
         *
         * SELECT ... FROM t1 WHERE
         *   x IN (SELECT ... FROM t2,t3 WHERE ...) AND
         *   y IN (SELECT ... FROM t4,t5 WHERE ...)
         *
         * We will flatten this query to a 5-way join problem, but there are
         * no 4-way joins that join_is_legal() will consider legal.  We have
         * to accept failure at level 4 and go on to discover a workable
         * bushy plan at level 5.
         *
         * However, if there are no special joins and no lateral references
         * then join_is_legal() should never fail, and so the following sanity
         * check is useful.
         *----------
         */
        if (joinrels[level] == NIL &&
            root->join_info_list == NIL &&
            !root->hasLateralRTEs)
            elog(ERROR, "failed to build any %d-way joins", level);
    }
}

References Assert, bms_overlap(), elog, ERROR, for_each_from, foreach_current_index, RelOptInfo::has_eclass_joins, has_join_restriction(), have_join_order_restriction(), have_relevant_joinclause(), RelOptInfo::joininfo, lfirst, make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, RelOptInfo::relids, and root.

Referenced by standard_join_search().

make_canonical_pathkey()

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

Definition at line 55 of file pathkeys.c.

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

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

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

make_inner_pathkeys_for_merge()

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

Definition at line 1838 of file pathkeys.c.

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

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

make_join_rel()

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

Definition at line 704 of file joinrels.c.

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

References add_outer_joins_to_relids(), Assert, bms_free(), bms_overlap(), bms_union(), build_join_rel(), init_dummy_sjinfo(), is_dummy_rel(), join_is_legal(), NIL, populate_joinrel_with_paths(), RelOptInfo::relids, and root.

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

make_one_rel()

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

Definition at line 171 of file allpaths.c.

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

References Assert, bms_equal(), IS_DUMMY_REL, IS_SIMPLE_REL, make_rel_from_joinlist(), RelOptInfo::pages, RelOptInfo::relid, RelOptInfo::relids, root, set_base_rel_consider_startup(), set_base_rel_pathlists(), and set_base_rel_sizes().

Referenced by query_planner().

make_pathkeys_for_sortclauses()

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

Definition at line 1333 of file pathkeys.c.

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

References Assert, make_pathkeys_for_sortclauses_extended(), and root.

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

make_pathkeys_for_sortclauses_extended()

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

Definition at line 1374 of file pathkeys.c.

{
    List       *pathkeys = NIL;
    ListCell   *l;
 
    *sortable = true;
    foreach(l, *sortclauses)
    {
        SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
        Expr       *sortkey;
        PathKey    *pathkey;
 
        sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
        if (!OidIsValid(sortcl->sortop))
        {
            *sortable = false;
            continue;
        }
        pathkey = make_pathkey_from_sortop(root,
                                           sortkey,
                                           sortcl->sortop,
                                           sortcl->nulls_first,
                                           sortcl->tleSortGroupRef,
                                           true);
        if (pathkey->pk_eclass->ec_sortref == 0 && set_ec_sortref)
        {
            /*
             * Copy the sortref if it hasn't been set yet.  That may happen if
             * the EquivalenceClass was constructed from a WHERE clause, i.e.
             * it doesn't have a target reference at all.
             */
            pathkey->pk_eclass->ec_sortref = sortcl->tleSortGroupRef;
        }
 
        /* Canonical form eliminates redundant ordering keys */
        if (!pathkey_is_redundant(pathkey, pathkeys))
            pathkeys = lappend(pathkeys, pathkey);
        else if (remove_redundant)
            *sortclauses = foreach_delete_current(*sortclauses, l);
    }
    return pathkeys;
}

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

Referenced by make_pathkeys_for_sortclauses(), make_pathkeys_for_window(), and standard_qp_callback().

mark_dummy_rel()

void mark_dummy_rel

(

RelOptInfo *

rel

)

Definition at line 1384 of file joinrels.c.

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

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

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

match_eclasses_to_foreign_key_col()

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

Definition at line 2505 of file equivclass.c.

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

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

Referenced by match_foreign_keys_to_quals().

match_index_to_operand()

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

Definition at line 3665 of file indxpath.c.

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

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

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

pathkeys_contained_in()

bool pathkeys_contained_in	(	List *	keys1,
		List *	keys2
	)

Definition at line 341 of file pathkeys.c.

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

References compare_pathkeys(), PATHKEYS_BETTER2, and PATHKEYS_EQUAL.

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

pathkeys_count_contained_in()

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

Definition at line 556 of file pathkeys.c.

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

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

Referenced by build_setop_child_paths(), create_final_distinct_paths(), create_one_window_path(), create_ordered_paths(), create_partial_distinct_paths(), create_window_paths(), gather_grouping_paths(), generate_useful_gather_paths(), make_ordered_path(), pathkeys_useful_for_ordering(), and pathkeys_useful_for_setop().

process_equivalence()

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

Definition at line 118 of file equivclass.c.

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

References add_eq_member(), NullTest::arg, Assert, bms_join(), canonicalize_ec_expression(), RestrictInfo::clause, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_max_security, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_jdomain, equal(), ERROR, exprType(), foreach_current_index, func_strict(), get_leftop(), get_rightop(), RestrictInfo::has_clone, RestrictInfo::incompatible_relids, RestrictInfo::is_clone, IS_NOT_NULL, is_opclause(), RestrictInfo::is_pushed_down, lappend(), lfirst, list_concat(), list_delete_nth_cell(), list_make1, NullTest::location, make_restrictinfo(), makeNode, Max, Min, NIL, NullTest::nulltesttype, op_input_types(), RestrictInfo::outer_relids, root, RestrictInfo::security_level, and set_opfuncid().

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

reconsider_outer_join_clauses()

void reconsider_outer_join_clauses

(

PlannerInfo *

root

)

Definition at line 1997 of file equivclass.c.

{
    bool        found;
    ListCell   *cell;
 
    /* Outer loop repeats until we find no more deductions */
    do
    {
        found = false;
 
        /* Process the LEFT JOIN clauses */
        foreach(cell, root->left_join_clauses)
        {
            OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
 
            if (reconsider_outer_join_clause(root, ojcinfo, true))
            {
                RestrictInfo *rinfo = ojcinfo->rinfo;
 
                found = true;
                /* remove it from the list */
                root->left_join_clauses =
                    foreach_delete_current(root->left_join_clauses, cell);
                /* throw back a dummy replacement clause (see notes above) */
                rinfo = make_restrictinfo(root,
                                          (Expr *) makeBoolConst(true, false),
                                          rinfo->is_pushed_down,
                                          rinfo->has_clone,
                                          rinfo->is_clone,
                                          false,    /* pseudoconstant */
                                          0,    /* security_level */
                                          rinfo->required_relids,
                                          rinfo->incompatible_relids,
                                          rinfo->outer_relids);
                distribute_restrictinfo_to_rels(root, rinfo);
            }
        }
 
        /* Process the RIGHT JOIN clauses */
        foreach(cell, root->right_join_clauses)
        {
            OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
 
            if (reconsider_outer_join_clause(root, ojcinfo, false))
            {
                RestrictInfo *rinfo = ojcinfo->rinfo;
 
                found = true;
                /* remove it from the list */
                root->right_join_clauses =
                    foreach_delete_current(root->right_join_clauses, cell);
                /* throw back a dummy replacement clause (see notes above) */
                rinfo = make_restrictinfo(root,
                                          (Expr *) makeBoolConst(true, false),
                                          rinfo->is_pushed_down,
                                          rinfo->has_clone,
                                          rinfo->is_clone,
                                          false,    /* pseudoconstant */
                                          0,    /* security_level */
                                          rinfo->required_relids,
                                          rinfo->incompatible_relids,
                                          rinfo->outer_relids);
                distribute_restrictinfo_to_rels(root, rinfo);
            }
        }
 
        /* Process the FULL JOIN clauses */
        foreach(cell, root->full_join_clauses)
        {
            OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
 
            if (reconsider_full_join_clause(root, ojcinfo))
            {
                RestrictInfo *rinfo = ojcinfo->rinfo;
 
                found = true;
                /* remove it from the list */
                root->full_join_clauses =
                    foreach_delete_current(root->full_join_clauses, cell);
                /* throw back a dummy replacement clause (see notes above) */
                rinfo = make_restrictinfo(root,
                                          (Expr *) makeBoolConst(true, false),
                                          rinfo->is_pushed_down,
                                          rinfo->has_clone,
                                          rinfo->is_clone,
                                          false,    /* pseudoconstant */
                                          0,    /* security_level */
                                          rinfo->required_relids,
                                          rinfo->incompatible_relids,
                                          rinfo->outer_relids);
                distribute_restrictinfo_to_rels(root, rinfo);
            }
        }
    } while (found);
 
    /* Now, any remaining clauses have to be thrown back */
    foreach(cell, root->left_join_clauses)
    {
        OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
 
        distribute_restrictinfo_to_rels(root, ojcinfo->rinfo);
    }
    foreach(cell, root->right_join_clauses)
    {
        OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
 
        distribute_restrictinfo_to_rels(root, ojcinfo->rinfo);
    }
    foreach(cell, root->full_join_clauses)
    {
        OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell);
 
        distribute_restrictinfo_to_rels(root, ojcinfo->rinfo);
    }
}

References distribute_restrictinfo_to_rels(), foreach_delete_current, RestrictInfo::has_clone, RestrictInfo::incompatible_relids, RestrictInfo::is_clone, RestrictInfo::is_pushed_down, lfirst, make_restrictinfo(), makeBoolConst(), RestrictInfo::outer_relids, reconsider_full_join_clause(), reconsider_outer_join_clause(), RestrictInfo::required_relids, OuterJoinClauseInfo::rinfo, and root.

Referenced by query_planner().

relation_can_be_sorted_early()

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

Definition at line 922 of file equivclass.c.

{
    PathTarget *target = rel->reltarget;
    EquivalenceMember *em;
    ListCell   *lc;
 
    /*
     * Reject volatile ECs immediately; such sorts must always be postponed.
     */
    if (ec->ec_has_volatile)
        return false;
 
    /*
     * Try to find an EM directly matching some reltarget member.
     */
    foreach(lc, target->exprs)
    {
        Expr       *targetexpr = (Expr *) lfirst(lc);
 
        em = find_ec_member_matching_expr(ec, targetexpr, rel->relids);
        if (!em)
            continue;
 
        /*
         * Reject expressions involving set-returning functions, as those
         * can't be computed early either.  (Note: this test and the following
         * one are effectively checking properties of targetexpr, so there's
         * no point in asking whether some other EC member would be better.)
         */
        if (expression_returns_set((Node *) em->em_expr))
            continue;
 
        /*
         * If requested, reject expressions that are not parallel-safe.  We
         * check this last because it's a rather expensive test.
         */
        if (require_parallel_safe &&
            !is_parallel_safe(root, (Node *) em->em_expr))
            continue;
 
        return true;
    }
 
    /*
     * Try to find an expression computable from the reltarget.
     */
    em = find_computable_ec_member(root, ec, target->exprs, rel->relids,
                                   require_parallel_safe);
    if (!em)
        return false;
 
    /*
     * Reject expressions involving set-returning functions, as those can't be
     * computed early either.  (There's no point in looking for another EC
     * member in this case; since SRFs can't appear in WHERE, they cannot
     * belong to multi-member ECs.)
     */
    if (expression_returns_set((Node *) em->em_expr))
        return false;
 
    return true;
}

References EquivalenceClass::ec_has_volatile, EquivalenceMember::em_expr, expression_returns_set(), PathTarget::exprs, find_computable_ec_member(), find_ec_member_matching_expr(), is_parallel_safe(), lfirst, RelOptInfo::relids, RelOptInfo::reltarget, and root.

Referenced by get_useful_pathkeys_for_relation().

relation_has_unique_index_for()

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

Definition at line 3440 of file indxpath.c.

{
    ListCell   *ic;
 
    Assert(list_length(exprlist) == list_length(oprlist));
 
    /* Short-circuit if no indexes... */
    if (rel->indexlist == NIL)
        return false;
 
    /*
     * Examine the rel's restriction clauses for usable var = const clauses
     * that we can add to the restrictlist.
     */
    foreach(ic, rel->baserestrictinfo)
    {
        RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(ic);
 
        /*
         * Note: can_join won't be set for a restriction clause, but
         * mergeopfamilies will be if it has a mergejoinable operator and
         * doesn't contain volatile functions.
         */
        if (restrictinfo->mergeopfamilies == NIL)
            continue;           /* not mergejoinable */
 
        /*
         * The clause certainly doesn't refer to anything but the given rel.
         * If either side is pseudoconstant then we can use it.
         */
        if (bms_is_empty(restrictinfo->left_relids))
        {
            /* righthand side is inner */
            restrictinfo->outer_is_left = true;
        }
        else if (bms_is_empty(restrictinfo->right_relids))
        {
            /* lefthand side is inner */
            restrictinfo->outer_is_left = false;
        }
        else
            continue;
 
        /* OK, add to list */
        restrictlist = lappend(restrictlist, restrictinfo);
    }
 
    /* Short-circuit the easy case */
    if (restrictlist == NIL && exprlist == NIL)
        return false;
 
    /* Examine each index of the relation ... */
    foreach(ic, rel->indexlist)
    {
        IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
        int         c;
 
        /*
         * If the index is not unique, or not immediately enforced, or if it's
         * a partial index, it's useless here.  We're unable to make use of
         * predOK partial unique indexes due to the fact that
         * check_index_predicates() also makes use of join predicates to
         * determine if the partial index is usable. Here we need proofs that
         * hold true before any joins are evaluated.
         */
        if (!ind->unique || !ind->immediate || ind->indpred != NIL)
            continue;
 
        /*
         * Try to find each index column in the lists of conditions.  This is
         * O(N^2) or worse, but we expect all the lists to be short.
         */
        for (c = 0; c < ind->nkeycolumns; c++)
        {
            bool        matched = false;
            ListCell   *lc;
            ListCell   *lc2;
 
            foreach(lc, restrictlist)
            {
                RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
                Node       *rexpr;
 
                /*
                 * The condition's equality operator must be a member of the
                 * index opfamily, else it is not asserting the right kind of
                 * equality behavior for this index.  We check this first
                 * since it's probably cheaper than match_index_to_operand().
                 */
                if (!list_member_oid(rinfo->mergeopfamilies, ind->opfamily[c]))
                    continue;
 
                /*
                 * XXX at some point we may need to check collations here too.
                 * For the moment we assume all collations reduce to the same
                 * notion of equality.
                 */
 
                /* OK, see if the condition operand matches the index key */
                if (rinfo->outer_is_left)
                    rexpr = get_rightop(rinfo->clause);
                else
                    rexpr = get_leftop(rinfo->clause);
 
                if (match_index_to_operand(rexpr, c, ind))
                {
                    matched = true; /* column is unique */
                    break;
                }
            }
 
            if (matched)
                continue;
 
            forboth(lc, exprlist, lc2, oprlist)
            {
                Node       *expr = (Node *) lfirst(lc);
                Oid         opr = lfirst_oid(lc2);
 
                /* See if the expression matches the index key */
                if (!match_index_to_operand(expr, c, ind))
                    continue;
 
                /*
                 * The equality operator must be a member of the index
                 * opfamily, else it is not asserting the right kind of
                 * equality behavior for this index.  We assume the caller
                 * determined it is an equality operator, so we don't need to
                 * check any more tightly than this.
                 */
                if (!op_in_opfamily(opr, ind->opfamily[c]))
                    continue;
 
                /*
                 * XXX at some point we may need to check collations here too.
                 * For the moment we assume all collations reduce to the same
                 * notion of equality.
                 */
 
                matched = true; /* column is unique */
                break;
            }
 
            if (!matched)
                break;          /* no match; this index doesn't help us */
        }
 
        /* Matched all key columns of this index? */
        if (c == ind->nkeycolumns)
            return true;
    }
 
    return false;
}

References Assert, RelOptInfo::baserestrictinfo, bms_is_empty, RestrictInfo::clause, forboth, get_leftop(), get_rightop(), RelOptInfo::indexlist, lappend(), lfirst, lfirst_oid, list_length(), list_member_oid(), match_index_to_operand(), NIL, and op_in_opfamily().

Referenced by create_unique_path(), and rel_is_distinct_for().

select_outer_pathkeys_for_merge()

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

Definition at line 1642 of file pathkeys.c.

{
    List       *pathkeys = NIL;
    int         nClauses = list_length(mergeclauses);
    EquivalenceClass **ecs;
    int        *scores;
    int         necs;
    ListCell   *lc;
    int         j;
 
    /* Might have no mergeclauses */
    if (nClauses == 0)
        return NIL;
 
    /*
     * Make arrays of the ECs used by the mergeclauses (dropping any
     * duplicates) and their "popularity" scores.
     */
    ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
    scores = (int *) palloc(nClauses * sizeof(int));
    necs = 0;
 
    foreach(lc, mergeclauses)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
        EquivalenceClass *oeclass;
        int         score;
        ListCell   *lc2;
 
        /* get the outer eclass */
        update_mergeclause_eclasses(root, rinfo);
 
        if (rinfo->outer_is_left)
            oeclass = rinfo->left_ec;
        else
            oeclass = rinfo->right_ec;
 
        /* reject duplicates */
        for (j = 0; j < necs; j++)
        {
            if (ecs[j] == oeclass)
                break;
        }
        if (j < necs)
            continue;
 
        /* compute score */
        score = 0;
        foreach(lc2, oeclass->ec_members)
        {
            EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
 
            /* Potential future join partner? */
            if (!em->em_is_const && !em->em_is_child &&
                !bms_overlap(em->em_relids, joinrel->relids))
                score++;
        }
 
        ecs[necs] = oeclass;
        scores[necs] = score;
        necs++;
    }
 
    /*
     * Find out if we have all the ECs mentioned in query_pathkeys; if so we
     * can generate a sort order that's also useful for final output. If we
     * only have a prefix of the query_pathkeys, and that prefix is the entire
     * join condition, then it's useful to use the prefix as the pathkeys as
     * this increases the chances that an incremental sort will be able to be
     * used by the upper planner.
     */
    if (root->query_pathkeys)
    {
        int         matches = 0;
 
        foreach(lc, root->query_pathkeys)
        {
            PathKey    *query_pathkey = (PathKey *) lfirst(lc);
            EquivalenceClass *query_ec = query_pathkey->pk_eclass;
 
            for (j = 0; j < necs; j++)
            {
                if (ecs[j] == query_ec)
                    break;      /* found match */
            }
            if (j >= necs)
                break;          /* didn't find match */
 
            matches++;
        }
        /* if we got to the end of the list, we have them all */
        if (lc == NULL)
        {
            /* copy query_pathkeys as starting point for our output */
            pathkeys = list_copy(root->query_pathkeys);
            /* mark their ECs as already-emitted */
            foreach(lc, root->query_pathkeys)
            {
                PathKey    *query_pathkey = (PathKey *) lfirst(lc);
                EquivalenceClass *query_ec = query_pathkey->pk_eclass;
 
                for (j = 0; j < necs; j++)
                {
                    if (ecs[j] == query_ec)
                    {
                        scores[j] = -1;
                        break;
                    }
                }
            }
        }
 
        /*
         * If we didn't match to all of the query_pathkeys, but did match to
         * all of the join clauses then we'll make use of these as partially
         * sorted input is better than nothing for the upper planner as it may
         * lead to incremental sorts instead of full sorts.
         */
        else if (matches == nClauses)
        {
            pathkeys = list_copy_head(root->query_pathkeys, matches);
 
            /* we have all of the join pathkeys, so nothing more to do */
            pfree(ecs);
            pfree(scores);
 
            return pathkeys;
        }
    }
 
    /*
     * Add remaining ECs to the list in popularity order, using a default sort
     * ordering.  (We could use qsort() here, but the list length is usually
     * so small it's not worth it.)
     */
    for (;;)
    {
        int         best_j;
        int         best_score;
        EquivalenceClass *ec;
        PathKey    *pathkey;
 
        best_j = 0;
        best_score = scores[0];
        for (j = 1; j < necs; j++)
        {
            if (scores[j] > best_score)
            {
                best_j = j;
                best_score = scores[j];
            }
        }
        if (best_score < 0)
            break;              /* all done */
        ec = ecs[best_j];
        scores[best_j] = -1;
        pathkey = make_canonical_pathkey(root,
                                         ec,
                                         linitial_oid(ec->ec_opfamilies),
                                         BTLessStrategyNumber,
                                         false);
        /* can't be redundant because no duplicate ECs */
        Assert(!pathkey_is_redundant(pathkey, pathkeys));
        pathkeys = lappend(pathkeys, pathkey);
    }
 
    pfree(ecs);
    pfree(scores);
 
    return pathkeys;
}

References Assert, bms_overlap(), BTLessStrategyNumber, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, j, lappend(), lfirst, linitial_oid, list_copy(), list_copy_head(), list_length(), make_canonical_pathkey(), NIL, palloc(), pathkey_is_redundant(), pfree(), RelOptInfo::relids, root, and update_mergeclause_eclasses().

Referenced by sort_inner_and_outer().

standard_join_search()

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

Definition at line 3418 of file allpaths.c.

{
    int         lev;
    RelOptInfo *rel;
 
    /*
     * This function cannot be invoked recursively within any one planning
     * problem, so join_rel_level[] can't be in use already.
     */
    Assert(root->join_rel_level == NULL);
 
    /*
     * We employ a simple "dynamic programming" algorithm: we first find all
     * ways to build joins of two jointree items, then all ways to build joins
     * of three items (from two-item joins and single items), then four-item
     * joins, and so on until we have considered all ways to join all the
     * items into one rel.
     *
     * root->join_rel_level[j] is a list of all the j-item rels.  Initially we
     * set root->join_rel_level[1] to represent all the single-jointree-item
     * relations.
     */
    root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
 
    root->join_rel_level[1] = initial_rels;
 
    for (lev = 2; lev <= levels_needed; lev++)
    {
        ListCell   *lc;
 
        /*
         * Determine all possible pairs of relations to be joined at this
         * level, and build paths for making each one from every available
         * pair of lower-level relations.
         */
        join_search_one_level(root, lev);
 
        /*
         * Run generate_partitionwise_join_paths() and
         * generate_useful_gather_paths() for each just-processed joinrel.  We
         * could not do this earlier because both regular and partial paths
         * can get added to a particular joinrel at multiple times within
         * join_search_one_level.
         *
         * After that, we're done creating paths for the joinrel, so run
         * set_cheapest().
         */
        foreach(lc, root->join_rel_level[lev])
        {
            rel = (RelOptInfo *) lfirst(lc);
 
            /* Create paths for partitionwise joins. */
            generate_partitionwise_join_paths(root, rel);
 
            /*
             * Except for the topmost scan/join rel, consider gathering
             * partial paths.  We'll do the same for the topmost scan/join rel
             * once we know the final targetlist (see grouping_planner's and
             * its call to apply_scanjoin_target_to_paths).
             */
            if (!bms_equal(rel->relids, root->all_query_rels))
                generate_useful_gather_paths(root, rel, false);
 
            /* Find and save the cheapest paths for this rel */
            set_cheapest(rel);
 
#ifdef OPTIMIZER_DEBUG
            pprint(rel);
#endif
        }
    }
 
    /*
     * We should have a single rel at the final level.
     */
    if (root->join_rel_level[levels_needed] == NIL)
        elog(ERROR, "failed to build any %d-way joins", levels_needed);
    Assert(list_length(root->join_rel_level[levels_needed]) == 1);
 
    rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
 
    root->join_rel_level = NULL;
 
    return rel;
}

References Assert, bms_equal(), elog, ERROR, generate_partitionwise_join_paths(), generate_useful_gather_paths(), join_search_one_level(), lfirst, linitial, list_length(), NIL, palloc0(), pprint(), RelOptInfo::relids, root, and set_cheapest().

Referenced by make_rel_from_joinlist().

trim_mergeclauses_for_inner_pathkeys()

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

Definition at line 1941 of file pathkeys.c.

{
    List       *new_mergeclauses = NIL;
    PathKey    *pathkey;
    EquivalenceClass *pathkey_ec;
    bool        matched_pathkey;
    ListCell   *lip;
    ListCell   *i;
 
    /* No pathkeys => no mergeclauses (though we don't expect this case) */
    if (pathkeys == NIL)
        return NIL;
    /* Initialize to consider first pathkey */
    lip = list_head(pathkeys);
    pathkey = (PathKey *) lfirst(lip);
    pathkey_ec = pathkey->pk_eclass;
    lip = lnext(pathkeys, lip);
    matched_pathkey = false;
 
    /* Scan mergeclauses to see how many we can use */
    foreach(i, mergeclauses)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
        EquivalenceClass *clause_ec;
 
        /* Assume we needn't do update_mergeclause_eclasses again here */
 
        /* Check clause's inner-rel EC against current pathkey */
        clause_ec = rinfo->outer_is_left ?
            rinfo->right_ec : rinfo->left_ec;
 
        /* If we don't have a match, attempt to advance to next pathkey */
        if (clause_ec != pathkey_ec)
        {
            /* If we had no clauses matching this inner pathkey, must stop */
            if (!matched_pathkey)
                break;
 
            /* Advance to next inner pathkey, if any */
            if (lip == NULL)
                break;
            pathkey = (PathKey *) lfirst(lip);
            pathkey_ec = pathkey->pk_eclass;
            lip = lnext(pathkeys, lip);
            matched_pathkey = false;
        }
 
        /* If mergeclause matches current inner pathkey, we can use it */
        if (clause_ec == pathkey_ec)
        {
            new_mergeclauses = lappend(new_mergeclauses, rinfo);
            matched_pathkey = true;
        }
        else
        {
            /* Else, no hope of adding any more mergeclauses */
            break;
        }
    }
 
    return new_mergeclauses;
}

References i, lappend(), lfirst, list_head(), lnext(), and NIL.

Referenced by generate_mergejoin_paths().

truncate_useless_pathkeys()

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

Definition at line 2215 of file pathkeys.c.

{
    int         nuseful;
    int         nuseful2;
 
    nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
    nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
    if (nuseful2 > nuseful)
        nuseful = nuseful2;
    nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
    if (nuseful2 > nuseful)
        nuseful = nuseful2;
    nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
    if (nuseful2 > nuseful)
        nuseful = nuseful2;
 
    /*
     * Note: not safe to modify input list destructively, but we can avoid
     * copying the list if we're not actually going to change it
     */
    if (nuseful == 0)
        return NIL;
    else if (nuseful == list_length(pathkeys))
        return pathkeys;
    else
        return list_copy_head(pathkeys, nuseful);
}

References list_copy_head(), list_length(), NIL, pathkeys_useful_for_grouping(), pathkeys_useful_for_merging(), pathkeys_useful_for_ordering(), pathkeys_useful_for_setop(), and root.

Referenced by build_index_paths(), and build_join_pathkeys().

update_mergeclause_eclasses()

void update_mergeclause_eclasses	(	PlannerInfo *	root,
		RestrictInfo *	restrictinfo
	)

Definition at line 1493 of file pathkeys.c.

{
    /* Should be a merge clause ... */
    Assert(restrictinfo->mergeopfamilies != NIL);
    /* ... with pointers already set */
    Assert(restrictinfo->left_ec != NULL);
    Assert(restrictinfo->right_ec != NULL);
 
    /* Chase up to the top as needed */
    while (restrictinfo->left_ec->ec_merged)
        restrictinfo->left_ec = restrictinfo->left_ec->ec_merged;
    while (restrictinfo->right_ec->ec_merged)
        restrictinfo->right_ec = restrictinfo->right_ec->ec_merged;
}

References Assert, and NIL.

Referenced by find_mergeclauses_for_outer_pathkeys(), get_useful_ecs_for_relation(), make_inner_pathkeys_for_merge(), pathkeys_useful_for_merging(), select_mergejoin_clauses(), and select_outer_pathkeys_for_merge().

Variable Documentation

enable_geqo

PGDLLIMPORT bool enable_geqo

extern

Definition at line 79 of file allpaths.c.

Referenced by make_rel_from_joinlist().

enable_group_by_reordering

PGDLLIMPORT bool enable_group_by_reordering

extern

Definition at line 31 of file pathkeys.c.

Referenced by get_useful_group_keys_orderings().

geqo_threshold

PGDLLIMPORT int geqo_threshold

extern

Definition at line 80 of file allpaths.c.

Referenced by make_rel_from_joinlist().

join_search_hook

PGDLLIMPORT join_search_hook_type join_search_hook

extern

Definition at line 88 of file allpaths.c.

Referenced by make_rel_from_joinlist().

min_parallel_index_scan_size

PGDLLIMPORT int min_parallel_index_scan_size

extern

Definition at line 82 of file allpaths.c.

Referenced by compute_parallel_worker(), and parallel_vacuum_compute_workers().

min_parallel_table_scan_size

PGDLLIMPORT int min_parallel_table_scan_size

extern

Definition at line 81 of file allpaths.c.

Referenced by compute_parallel_worker().

set_join_pathlist_hook

PGDLLIMPORT set_join_pathlist_hook_type set_join_pathlist_hook

extern

Definition at line 31 of file joinpath.c.

Referenced by add_paths_to_joinrel().

set_rel_pathlist_hook

PGDLLIMPORT set_rel_pathlist_hook_type set_rel_pathlist_hook

extern

Definition at line 85 of file allpaths.c.

Referenced by set_rel_pathlist().