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)
void	create_tidscan_paths (PlannerInfo *root, RelOptInfo *rel)
void	add_paths_to_joinrel (PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *outerrel, RelOptInfo *innerrel, JoinType jointype, SpecialJoinInfo *sjinfo, List *restrictlist)
void	join_search_one_level (PlannerInfo *root, int level)
RelOptInfo *	make_join_rel (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
bool	have_join_order_restriction (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
bool	have_dangerous_phv (PlannerInfo *root, Relids outer_relids, Relids inner_params)
void	mark_dummy_rel (RelOptInfo *rel)
bool	process_equivalence (PlannerInfo *root, RestrictInfo **p_restrictinfo, bool below_outer_join)
Expr *	canonicalize_ec_expression (Expr *expr, Oid req_type, Oid req_collation)
void	reconsider_outer_join_clauses (PlannerInfo *root)
EquivalenceClass *	get_eclass_for_sort_expr (PlannerInfo *root, Expr *expr, Relids nullable_relids, List *opfamilies, Oid opcintype, Oid collation, Index sortref, Relids rel, bool create_it)
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)
Expr *	find_em_expr_for_rel (EquivalenceClass *ec, RelOptInfo *rel)
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)
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_rel, RelOptInfo *child_rel)
List *	generate_implied_equalities_for_column (PlannerInfo *root, RelOptInfo *rel, ec_matches_callback_type callback, void *callback_arg, Relids prohibited_rels)
bool	have_relevant_eclass_joinclause (PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
bool	has_relevant_eclass_joinclause (PlannerInfo *root, RelOptInfo *rel1)
bool	eclass_useful_for_merging (PlannerInfo *root, EquivalenceClass *eclass, RelOptInfo *rel)
bool	is_redundant_derived_clause (RestrictInfo *rinfo, List *clauselist)
bool	is_redundant_with_indexclauses (RestrictInfo *rinfo, List *indexclauses)
PathKeysComparison	compare_pathkeys (List *keys1, List *keys2)
bool	pathkeys_contained_in (List *keys1, List *keys2)
bool	pathkeys_count_contained_in (List *keys1, List *keys2, int *n_common)
Path *	get_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Path *	get_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
Path *	get_cheapest_parallel_safe_total_inner (List *paths)
List *	build_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
List *	build_partition_pathkeys (PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys)
List *	build_expression_pathkey (PlannerInfo *root, Expr *expr, Relids nullable_relids, Oid opno, Relids rel, bool create_it)
List *	convert_subquery_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist)
List *	build_join_pathkeys (PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
List *	make_pathkeys_for_sortclauses (PlannerInfo *root, List *sortclauses, List *tlist)
void	initialize_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
void	update_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
List *	find_mergeclauses_for_outer_pathkeys (PlannerInfo *root, List *pathkeys, List *restrictinfos)
List *	select_outer_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
List *	make_inner_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
List *	trim_mergeclauses_for_inner_pathkeys (PlannerInfo *root, List *mergeclauses, List *pathkeys)
List *	truncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
bool	has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)
PathKey *	make_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
void	add_paths_to_append_rel (PlannerInfo *root, RelOptInfo *rel, List *live_childrels)

Variables
PGDLLIMPORT bool	enable_geqo
PGDLLIMPORT int	geqo_threshold
PGDLLIMPORT int	min_parallel_table_scan_size
PGDLLIMPORT int	min_parallel_index_scan_size
PGDLLIMPORT set_rel_pathlist_hook_type	set_rel_pathlist_hook
PGDLLIMPORT set_join_pathlist_hook_type	set_join_pathlist_hook
PGDLLIMPORT join_search_hook_type	join_search_hook

Typedef Documentation

ec_matches_callback_type

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

Definition at line 117 of file paths.h.

join_search_hook_type

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

Definition at line 45 of file paths.h.

set_join_pathlist_hook_type

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

Definition at line 36 of file paths.h.

set_rel_pathlist_hook_type

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

Definition at line 29 of file paths.h.

Enumeration Type Documentation

PathKeysComparison

enum PathKeysComparison

Enumerator
PATHKEYS_EQUAL
PATHKEYS_BETTER1
PATHKEYS_BETTER2
PATHKEYS_DIFFERENT

Definition at line 195 of file paths.h.

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

Function Documentation

add_child_join_rel_equivalences()

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

Definition at line 2696 of file equivclass.c.

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

Referenced by build_child_join_rel().

{
    Relids      top_parent_relids = child_joinrel->top_parent_relids;
    Relids      child_relids = child_joinrel->relids;
    Bitmapset  *matching_ecs;
    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;
                Relids      new_nullable_relids;

                if (parent_joinrel->reloptkind == RELOPT_JOINREL)
                {
                    /* Simple single-level transformation */
                    child_expr = (Expr *)
                        adjust_appendrel_attrs(root,
                                               (Node *) cur_em->em_expr,
                                               nappinfos, appinfos);
                }
                else
                {
                    /* Must do multi-level transformation */
                    Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL);
                    child_expr = (Expr *)
                        adjust_appendrel_attrs_multilevel(root,
                                                          (Node *) cur_em->em_expr,
                                                          child_relids,
                                                          top_parent_relids);
                }

                /*
                 * Transform em_relids to match.  Note we do *not* do
                 * pull_varnos(child_expr) here, as for example the
                 * transformation might have substituted a constant, but we
                 * don't want the child member to be marked as constant.
                 */
                new_relids = bms_difference(cur_em->em_relids,
                                            top_parent_relids);
                new_relids = bms_add_members(new_relids, child_relids);

                /*
                 * For nullable_relids, we must selectively replace parent
                 * nullable relids with child ones.
                 */
                new_nullable_relids = cur_em->em_nullable_relids;
                if (bms_overlap(new_nullable_relids, top_parent_relids))
                    new_nullable_relids =
                        adjust_child_relids_multilevel(root,
                                                       new_nullable_relids,
                                                       child_relids,
                                                       top_parent_relids);

                (void) add_eq_member(cur_ec, child_expr,
                                     new_relids, new_nullable_relids,
                                     true, cur_em->em_datatype);
            }
        }
    }

    MemoryContextSwitchTo(oldcontext);
}

add_child_rel_equivalences()

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

Definition at line 2568 of file equivclass.c.

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

Referenced by set_append_rel_size().

{
    Relids      top_parent_relids = child_rel->top_parent_relids;
    Relids      child_relids = child_rel->relids;
    int         i;

    /*
     * EC merging should be complete already, so we can use the parent rel's
     * eclass_indexes to avoid searching all of root->eq_classes.
     */
    Assert(root->ec_merging_done);
    Assert(IS_SIMPLE_REL(parent_rel));

    i = -1;
    while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0)
    {
        EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
        int         num_members;

        /*
         * If this EC contains a volatile expression, then generating child
         * EMs would be downright dangerous, so skip it.  We rely on a
         * volatile EC having only one EM.
         */
        if (cur_ec->ec_has_volatile)
            continue;

        /* Sanity check eclass_indexes only contain ECs for parent_rel */
        Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids));

        /*
         * We don't use foreach() here because there's no point in scanning
         * newly-added child members, so we can stop after the last
         * pre-existing EC member.
         */
        num_members = list_length(cur_ec->ec_members);
        for (int pos = 0; pos < num_members; pos++)
        {
            EquivalenceMember *cur_em = (EquivalenceMember *) list_nth(cur_ec->ec_members, pos);

            if (cur_em->em_is_const)
                continue;       /* ignore consts here */

            /*
             * We consider only original EC members here, not
             * already-transformed child members.  Otherwise, if some original
             * member expression references more than one appendrel, we'd get
             * an O(N^2) explosion of useless derived expressions for
             * combinations of children.  (But add_child_join_rel_equivalences
             * may add targeted combinations for partitionwise-join purposes.)
             */
            if (cur_em->em_is_child)
                continue;       /* ignore children here */

            /* Does this member reference child's topmost parent rel? */
            if (bms_overlap(cur_em->em_relids, top_parent_relids))
            {
                /* Yes, generate transformed child version */
                Expr       *child_expr;
                Relids      new_relids;
                Relids      new_nullable_relids;

                if (parent_rel->reloptkind == RELOPT_BASEREL)
                {
                    /* Simple single-level transformation */
                    child_expr = (Expr *)
                        adjust_appendrel_attrs(root,
                                               (Node *) cur_em->em_expr,
                                               1, &appinfo);
                }
                else
                {
                    /* Must do multi-level transformation */
                    child_expr = (Expr *)
                        adjust_appendrel_attrs_multilevel(root,
                                                          (Node *) cur_em->em_expr,
                                                          child_relids,
                                                          top_parent_relids);
                }

                /*
                 * Transform em_relids to match.  Note we do *not* do
                 * pull_varnos(child_expr) here, as for example the
                 * transformation might have substituted a constant, but we
                 * don't want the child member to be marked as constant.
                 */
                new_relids = bms_difference(cur_em->em_relids,
                                            top_parent_relids);
                new_relids = bms_add_members(new_relids, child_relids);

                /*
                 * And likewise for nullable_relids.  Note this code assumes
                 * parent and child relids are singletons.
                 */
                new_nullable_relids = cur_em->em_nullable_relids;
                if (bms_overlap(new_nullable_relids, top_parent_relids))
                {
                    new_nullable_relids = bms_difference(new_nullable_relids,
                                                         top_parent_relids);
                    new_nullable_relids = bms_add_members(new_nullable_relids,
                                                          child_relids);
                }

                (void) add_eq_member(cur_ec, child_expr,
                                     new_relids, new_nullable_relids,
                                     true, cur_em->em_datatype);

                /* Record this EC index for the child rel */
                child_rel->eclass_indexes = bms_add_member(child_rel->eclass_indexes, i);
            }
        }
    }
}

add_paths_to_append_rel()

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

Definition at line 1285 of file allpaths.c.

References accumulate_append_subpath(), add_partial_path(), add_path(), Assert, bms_equal(), RelOptInfo::cheapest_total_path, compare_pathkeys(), RelOptInfo::consider_parallel, create_append_path(), enable_parallel_append, fls(), 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, Path::param_info, RelOptInfo::partial_pathlist, AppendPath::path, PATH_REQ_OUTER, Path::pathkeys, PATHKEYS_EQUAL, RelOptInfo::pathlist, 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().

{
    List       *subpaths = NIL;
    bool        subpaths_valid = true;
    List       *partial_subpaths = NIL;
    List       *pa_partial_subpaths = NIL;
    List       *pa_nonpartial_subpaths = NIL;
    bool        partial_subpaths_valid = true;
    bool        pa_subpaths_valid;
    List       *all_child_pathkeys = NIL;
    List       *all_child_outers = NIL;
    ListCell   *l;
    double      partial_rows = -1;

    /* If appropriate, consider parallel append */
    pa_subpaths_valid = enable_parallel_append && rel->consider_parallel;

    /*
     * For every non-dummy child, remember the cheapest path.  Also, identify
     * all pathkeys (orderings) and parameterizations (required_outer sets)
     * available for the non-dummy member relations.
     */
    foreach(l, live_childrels)
    {
        RelOptInfo *childrel = lfirst(l);
        ListCell   *lcp;
        Path       *cheapest_partial_path = NULL;

        /*
         * If child has an unparameterized cheapest-total path, add that to
         * the unparameterized Append path we are constructing for the parent.
         * If not, there's no workable unparameterized path.
         *
         * With partitionwise aggregates, the child rel's pathlist may be
         * empty, so don't assume that a path exists here.
         */
        if (childrel->pathlist != NIL &&
            childrel->cheapest_total_path->param_info == NULL)
            accumulate_append_subpath(childrel->cheapest_total_path,
                                      &subpaths, NULL);
        else
            subpaths_valid = false;

        /* Same idea, but for a partial plan. */
        if (childrel->partial_pathlist != NIL)
        {
            cheapest_partial_path = linitial(childrel->partial_pathlist);
            accumulate_append_subpath(cheapest_partial_path,
                                      &partial_subpaths, NULL);
        }
        else
            partial_subpaths_valid = false;

        /*
         * Same idea, but for a parallel append mixing partial and non-partial
         * paths.
         */
        if (pa_subpaths_valid)
        {
            Path       *nppath = NULL;

            nppath =
                get_cheapest_parallel_safe_total_inner(childrel->pathlist);

            if (cheapest_partial_path == NULL && nppath == NULL)
            {
                /* Neither a partial nor a parallel-safe path?  Forget it. */
                pa_subpaths_valid = false;
            }
            else if (nppath == NULL ||
                     (cheapest_partial_path != NULL &&
                      cheapest_partial_path->total_cost < nppath->total_cost))
            {
                /* Partial path is cheaper or the only option. */
                Assert(cheapest_partial_path != NULL);
                accumulate_append_subpath(cheapest_partial_path,
                                          &pa_partial_subpaths,
                                          &pa_nonpartial_subpaths);
            }
            else
            {
                /*
                 * Either we've got only a non-partial path, or we think that
                 * a single backend can execute the best non-partial path
                 * faster than all the parallel backends working together can
                 * execute the best partial path.
                 *
                 * It might make sense to be more aggressive here.  Even if
                 * the best non-partial path is more expensive than the best
                 * partial path, it could still be better to choose the
                 * non-partial path if there are several such paths that can
                 * be given to different workers.  For now, we don't try to
                 * figure that out.
                 */
                accumulate_append_subpath(nppath,
                                          &pa_nonpartial_subpaths,
                                          NULL);
            }
        }

        /*
         * Collect lists of all the available path orderings and
         * parameterizations for all the children.  We use these as a
         * heuristic to indicate which sort orderings and parameterizations we
         * should build Append and MergeAppend paths for.
         */
        foreach(lcp, childrel->pathlist)
        {
            Path       *childpath = (Path *) lfirst(lcp);
            List       *childkeys = childpath->pathkeys;
            Relids      childouter = PATH_REQ_OUTER(childpath);

            /* Unsorted paths don't contribute to pathkey list */
            if (childkeys != NIL)
            {
                ListCell   *lpk;
                bool        found = false;

                /* Have we already seen this ordering? */
                foreach(lpk, all_child_pathkeys)
                {
                    List       *existing_pathkeys = (List *) lfirst(lpk);

                    if (compare_pathkeys(existing_pathkeys,
                                         childkeys) == PATHKEYS_EQUAL)
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                {
                    /* No, so add it to all_child_pathkeys */
                    all_child_pathkeys = lappend(all_child_pathkeys,
                                                 childkeys);
                }
            }

            /* Unparameterized paths don't contribute to param-set list */
            if (childouter)
            {
                ListCell   *lco;
                bool        found = false;

                /* Have we already seen this param set? */
                foreach(lco, all_child_outers)
                {
                    Relids      existing_outers = (Relids) lfirst(lco);

                    if (bms_equal(existing_outers, childouter))
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                {
                    /* No, so add it to all_child_outers */
                    all_child_outers = lappend(all_child_outers,
                                               childouter);
                }
            }
        }
    }

    /*
     * If we found unparameterized paths for all children, build an unordered,
     * unparameterized Append path for the rel.  (Note: this is correct even
     * if we have zero or one live subpath due to constraint exclusion.)
     */
    if (subpaths_valid)
        add_path(rel, (Path *) create_append_path(root, rel, subpaths, NIL,
                                                  NIL, NULL, 0, false,
                                                  -1));

    /*
     * Consider an append of unordered, unparameterized partial paths.  Make
     * it parallel-aware if possible.
     */
    if (partial_subpaths_valid && partial_subpaths != NIL)
    {
        AppendPath *appendpath;
        ListCell   *lc;
        int         parallel_workers = 0;

        /* Find the highest number of workers requested for any subpath. */
        foreach(lc, partial_subpaths)
        {
            Path       *path = lfirst(lc);

            parallel_workers = Max(parallel_workers, path->parallel_workers);
        }
        Assert(parallel_workers > 0);

        /*
         * If the use of parallel append is permitted, always request at least
         * log2(# of children) workers.  We assume it can be useful to have
         * extra workers in this case because they will be spread out across
         * the children.  The precise formula is just a guess, but we don't
         * want to end up with a radically different answer for a table with N
         * partitions vs. an unpartitioned table with the same data, so the
         * use of some kind of log-scaling here seems to make some sense.
         */
        if (enable_parallel_append)
        {
            parallel_workers = Max(parallel_workers,
                                   fls(list_length(live_childrels)));
            parallel_workers = Min(parallel_workers,
                                   max_parallel_workers_per_gather);
        }
        Assert(parallel_workers > 0);

        /* Generate a partial append path. */
        appendpath = create_append_path(root, rel, NIL, partial_subpaths,
                                        NIL, NULL, parallel_workers,
                                        enable_parallel_append,
                                        -1);

        /*
         * Make sure any subsequent partial paths use the same row count
         * estimate.
         */
        partial_rows = appendpath->path.rows;

        /* Add the path. */
        add_partial_path(rel, (Path *) appendpath);
    }

    /*
     * Consider a parallel-aware append using a mix of partial and non-partial
     * paths.  (This only makes sense if there's at least one child which has
     * a non-partial path that is substantially cheaper than any partial path;
     * otherwise, we should use the append path added in the previous step.)
     */
    if (pa_subpaths_valid && pa_nonpartial_subpaths != NIL)
    {
        AppendPath *appendpath;
        ListCell   *lc;
        int         parallel_workers = 0;

        /*
         * Find the highest number of workers requested for any partial
         * subpath.
         */
        foreach(lc, pa_partial_subpaths)
        {
            Path       *path = lfirst(lc);

            parallel_workers = Max(parallel_workers, path->parallel_workers);
        }

        /*
         * Same formula here as above.  It's even more important in this
         * instance because the non-partial paths won't contribute anything to
         * the planned number of parallel workers.
         */
        parallel_workers = Max(parallel_workers,
                               fls(list_length(live_childrels)));
        parallel_workers = Min(parallel_workers,
                               max_parallel_workers_per_gather);
        Assert(parallel_workers > 0);

        appendpath = create_append_path(root, rel, pa_nonpartial_subpaths,
                                        pa_partial_subpaths,
                                        NIL, NULL, parallel_workers, true,
                                        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);
        }
    }
}

add_paths_to_joinrel()

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

Definition at line 123 of file joinpath.c.

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

Referenced by populate_joinrel_with_paths().

{
    JoinPathExtraData extra;
    bool        mergejoin_allowed = true;
    ListCell   *lc;
    Relids      joinrelids;

    /*
     * PlannerInfo doesn't contain the SpecialJoinInfos created for joins
     * between child relations, even if there is a SpecialJoinInfo node for
     * the join between the topmost parents. So, while calculating Relids set
     * representing the restriction, consider relids of topmost parent of
     * partitions.
     */
    if (joinrel->reloptkind == RELOPT_OTHER_JOINREL)
        joinrelids = joinrel->top_parent_relids;
    else
        joinrelids = joinrel->relids;

    extra.restrictlist = restrictlist;
    extra.mergeclause_list = NIL;
    extra.sjinfo = sjinfo;
    extra.param_source_rels = NULL;

    /*
     * See if the inner relation is provably unique for this outer rel.
     *
     * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
     * matter since the executor can make the equivalent optimization anyway;
     * we need not expend planner cycles on proofs.  For JOIN_UNIQUE_INNER, we
     * must be considering a semijoin whose inner side is not provably unique
     * (else reduce_unique_semijoins would've simplified it), so there's no
     * point in calling innerrel_is_unique.  However, if the LHS covers all of
     * the semijoin's min_lefthand, then it's appropriate to set inner_unique
     * because the path produced by create_unique_path will be unique relative
     * to the LHS.  (If we have an LHS that's only part of the min_lefthand,
     * that is *not* true.)  For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
     * letting that value escape this module.
     */
    switch (jointype)
    {
        case JOIN_SEMI:
        case JOIN_ANTI:

            /*
             * 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.
     */
    foreach(lc, root->join_info_list)
    {
        SpecialJoinInfo *sjinfo2 = (SpecialJoinInfo *) lfirst(lc);

        /*
         * SJ is relevant to this join if we have some part of its RHS
         * (possibly not all of it), and haven't yet joined to its LHS.  (This
         * test is pretty simplistic, but should be sufficient considering the
         * join has already been proven legal.)  If the SJ is relevant, it
         * presents constraints for joining to anything not in its RHS.
         */
        if (bms_overlap(joinrelids, sjinfo2->min_righthand) &&
            !bms_overlap(joinrelids, sjinfo2->min_lefthand))
            extra.param_source_rels = bms_join(extra.param_source_rels,
                                               bms_difference(root->all_baserels,
                                                              sjinfo2->min_righthand));

        /* full joins constrain both sides symmetrically */
        if (sjinfo2->jointype == JOIN_FULL &&
            bms_overlap(joinrelids, sjinfo2->min_lefthand) &&
            !bms_overlap(joinrelids, sjinfo2->min_righthand))
            extra.param_source_rels = bms_join(extra.param_source_rels,
                                               bms_difference(root->all_baserels,
                                                              sjinfo2->min_lefthand));
    }

    /*
     * However, when a LATERAL subquery is involved, there will simply not be
     * any paths for the joinrel that aren't parameterized by whatever the
     * subquery is parameterized by, unless its parameterization is resolved
     * within the joinrel.  So we might as well allow additional dependencies
     * on whatever residual lateral dependencies the joinrel will have.
     */
    extra.param_source_rels = bms_add_members(extra.param_source_rels,
                                              joinrel->lateral_relids);

    /*
     * 1. Consider mergejoin paths where both relations must be explicitly
     * sorted.  Skip this if we can't mergejoin.
     */
    if (mergejoin_allowed)
        sort_inner_and_outer(root, joinrel, outerrel, innerrel,
                             jointype, &extra);

    /*
     * 2. Consider paths where the outer relation need not be explicitly
     * sorted. This includes both nestloops and mergejoins where the outer
     * path is already ordered.  Again, skip this if we can't mergejoin.
     * (That's okay because we know that nestloop can't handle right/full
     * joins at all, so it wouldn't work in the prohibited cases either.)
     */
    if (mergejoin_allowed)
        match_unsorted_outer(root, joinrel, outerrel, innerrel,
                             jointype, &extra);

#ifdef NOT_USED

    /*
     * 3. Consider paths where the inner relation need not be explicitly
     * sorted.  This includes mergejoins only (nestloops were already built in
     * match_unsorted_outer).
     *
     * Diked out as redundant 2/13/2000 -- tgl.  There isn't any really
     * significant difference between the inner and outer side of a mergejoin,
     * so match_unsorted_inner creates no paths that aren't equivalent to
     * those made by match_unsorted_outer when add_paths_to_joinrel() is
     * invoked with the two rels given in the other order.
     */
    if (mergejoin_allowed)
        match_unsorted_inner(root, joinrel, outerrel, innerrel,
                             jointype, &extra);
#endif

    /*
     * 4. Consider paths where both outer and inner relations must be hashed
     * before being joined.  As above, disregard enable_hashjoin for full
     * joins, because there may be no other alternative.
     */
    if (enable_hashjoin || jointype == JOIN_FULL)
        hash_inner_and_outer(root, joinrel, outerrel, innerrel,
                             jointype, &extra);

    /*
     * 5. If inner and outer relations are foreign tables (or joins) belonging
     * to the same server and assigned to the same user to check access
     * permissions as, give the FDW a chance to push down joins.
     */
    if (joinrel->fdwroutine &&
        joinrel->fdwroutine->GetForeignJoinPaths)
        joinrel->fdwroutine->GetForeignJoinPaths(root, joinrel,
                                                 outerrel, innerrel,
                                                 jointype, &extra);

    /*
     * 6. Finally, give extensions a chance to manipulate the path list.
     */
    if (set_join_pathlist_hook)
        set_join_pathlist_hook(root, joinrel, outerrel, innerrel,
                               jointype, &extra);
}

build_expression_pathkey()

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

Definition at line 782 of file pathkeys.c.

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

Referenced by set_function_pathlist().

{
    List       *pathkeys;
    Oid         opfamily,
                opcintype;
    int16       strategy;
    PathKey    *cpathkey;

    /* Find the operator in pg_amop --- failure shouldn't happen */
    if (!get_ordering_op_properties(opno,
                                    &opfamily, &opcintype, &strategy))
        elog(ERROR, "operator %u is not a valid ordering operator",
             opno);

    cpathkey = make_pathkey_from_sortinfo(root,
                                          expr,
                                          nullable_relids,
                                          opfamily,
                                          opcintype,
                                          exprCollation((Node *) expr),
                                          (strategy == BTGreaterStrategyNumber),
                                          (strategy == BTGreaterStrategyNumber),
                                          0,
                                          rel,
                                          create_it);

    if (cpathkey)
        pathkeys = list_make1(cpathkey);
    else
        pathkeys = NIL;

    return pathkeys;
}

build_index_pathkeys()

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

Definition at line 523 of file pathkeys.c.

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

Referenced by build_index_paths().

{
    List       *retval = NIL;
    ListCell   *lc;
    int         i;

    if (index->sortopfamily == NULL)
        return NIL;             /* non-orderable index */

    i = 0;
    foreach(lc, index->indextlist)
    {
        TargetEntry *indextle = (TargetEntry *) lfirst(lc);
        Expr       *indexkey;
        bool        reverse_sort;
        bool        nulls_first;
        PathKey    *cpathkey;

        /*
         * INCLUDE columns are stored in index unordered, so they don't
         * support ordered index scan.
         */
        if (i >= index->nkeycolumns)
            break;

        /* We assume we don't need to make a copy of the tlist item */
        indexkey = indextle->expr;

        if (ScanDirectionIsBackward(scandir))
        {
            reverse_sort = !index->reverse_sort[i];
            nulls_first = !index->nulls_first[i];
        }
        else
        {
            reverse_sort = index->reverse_sort[i];
            nulls_first = index->nulls_first[i];
        }

        /*
         * OK, try to make a canonical pathkey for this sort key.  Note we're
         * underneath any outer joins, so nullable_relids should be NULL.
         */
        cpathkey = make_pathkey_from_sortinfo(root,
                                              indexkey,
                                              NULL,
                                              index->sortopfamily[i],
                                              index->opcintype[i],
                                              index->indexcollations[i],
                                              reverse_sort,
                                              nulls_first,
                                              0,
                                              index->rel->relids,
                                              false);

        if (cpathkey)
        {
            /*
             * We found the sort key in an EquivalenceClass, so it's relevant
             * for this query.  Add it to list, unless it's redundant.
             */
            if (!pathkey_is_redundant(cpathkey, retval))
                retval = lappend(retval, cpathkey);
        }
        else
        {
            /*
             * Boolean index keys might be redundant even if they do not
             * appear in an EquivalenceClass, because of our special treatment
             * of boolean equality conditions --- see the comment for
             * indexcol_is_bool_constant_for_query().  If that applies, we can
             * continue to examine lower-order index columns.  Otherwise, the
             * sort key is not an interesting sort order for this query, so we
             * should stop considering index columns; any lower-order sort
             * keys won't be useful either.
             */
            if (!indexcol_is_bool_constant_for_query(root, index, i))
                break;
        }

        i++;
    }

    return retval;
}

build_join_pathkeys()

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

Definition at line 1082 of file pathkeys.c.

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

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

{
    if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
        return NIL;

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

build_partition_pathkeys()

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

Definition at line 699 of file pathkeys.c.

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

Referenced by generate_orderedappend_paths().

{
    List       *retval = NIL;
    PartitionScheme partscheme = partrel->part_scheme;
    int         i;

    Assert(partscheme != NULL);
    Assert(partitions_are_ordered(partrel->boundinfo, partrel->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're considering a baserel scan, so nullable_relids should be
         * NULL.  Also, we assume the PartitionDesc lists any NULL partition
         * last, so we treat the scan like a NULLS LAST index: we have
         * nulls_first for backwards scan only.
         */
        cpathkey = make_pathkey_from_sortinfo(root,
                                              keyCol,
                                              NULL,
                                              partscheme->partopfamily[i],
                                              partscheme->partopcintype[i],
                                              partscheme->partcollation[i],
                                              ScanDirectionIsBackward(scandir),
                                              ScanDirectionIsBackward(scandir),
                                              0,
                                              partrel->relids,
                                              false);


        if (cpathkey)
        {
            /*
             * We found the sort key in an EquivalenceClass, so it's relevant
             * for this query.  Add it to list, unless it's redundant.
             */
            if (!pathkey_is_redundant(cpathkey, retval))
                retval = lappend(retval, cpathkey);
        }
        else
        {
            /*
             * Boolean partition keys might be redundant even if they do not
             * appear in an EquivalenceClass, because of our special treatment
             * of boolean equality conditions --- see the comment for
             * partkey_is_bool_constant_for_query().  If that applies, we can
             * continue to examine lower-order partition keys.  Otherwise, the
             * sort key is not an interesting sort order for this query, so we
             * should stop considering partition columns; any lower-order sort
             * keys won't be useful either.
             */
            if (!partkey_is_bool_constant_for_query(partrel, i))
            {
                *partialkeys = true;
                return retval;
            }
        }
    }

    *partialkeys = false;
    return retval;
}

canonicalize_ec_expression()

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

Definition at line 500 of file equivclass.c.

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

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

{
    Oid         expr_type = exprType((Node *) expr);

    /*
     * For a polymorphic-input-type opclass, just keep the same exposed type.
     * RECORD opclasses work like polymorphic-type ones for this purpose.
     */
    if (IsPolymorphicType(req_type) || req_type == RECORDOID)
        req_type = expr_type;

    /*
     * No work if the expression exposes the right type/collation already.
     */
    if (expr_type != req_type ||
        exprCollation((Node *) expr) != req_collation)
    {
        /*
         * 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;
}

check_index_predicates()

void check_index_predicates	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 3320 of file indxpath.c.

References PlannerInfo::all_baserels, PlannerInfo::all_result_relids, Assert, RelOptInfo::baserestrictinfo, 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, IndexOptInfo::indpred, IndexOptInfo::indrestrictinfo, IS_SIMPLE_REL, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, predicate_implied_by(), IndexOptInfo::predOK, RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, RelOptInfo::reloptkind, and PlannerInfo::rowMarks.

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

{
    List       *clauselist;
    bool        have_partial;
    bool        is_target_rel;
    Relids      otherrels;
    ListCell   *lc;

    /* Indexes are available only on base or "other" member relations. */
    Assert(IS_SIMPLE_REL(rel));

    /*
     * Initialize the indrestrictinfo lists to be identical to
     * baserestrictinfo, and check whether there are any partial indexes.  If
     * not, this is all we need to do.
     */
    have_partial = false;
    foreach(lc, rel->indexlist)
    {
        IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);

        index->indrestrictinfo = rel->baserestrictinfo;
        if (index->indpred)
            have_partial = true;
    }
    if (!have_partial)
        return;

    /*
     * Construct a list of clauses that we can assume true for the purpose of
     * proving the index(es) usable.  Restriction clauses for the rel are
     * always usable, and so are any join clauses that are "movable to" this
     * rel.  Also, we can consider any EC-derivable join clauses (which must
     * be "movable to" this rel, by definition).
     */
    clauselist = list_copy(rel->baserestrictinfo);

    /* Scan the rel's join clauses */
    foreach(lc, rel->joininfo)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);

        /* Check if clause can be moved to this rel */
        if (!join_clause_is_movable_to(rinfo, rel))
            continue;

        clauselist = lappend(clauselist, rinfo);
    }

    /*
     * Add on any equivalence-derivable join clauses.  Computing the correct
     * relid sets for generate_join_implied_equalities is slightly tricky
     * because the rel could be a child rel rather than a true baserel, and in
     * that case we must remove its parents' relid(s) from all_baserels.
     */
    if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
        otherrels = bms_difference(root->all_baserels,
                                   find_childrel_parents(root, rel));
    else
        otherrels = bms_difference(root->all_baserels, rel->relids);

    if (!bms_is_empty(otherrels))
        clauselist =
            list_concat(clauselist,
                        generate_join_implied_equalities(root,
                                                         bms_union(rel->relids,
                                                                   otherrels),
                                                         otherrels,
                                                         rel));

    /*
     * Normally we remove quals that are implied by a partial index's
     * predicate from indrestrictinfo, indicating that they need not be
     * checked explicitly by an indexscan plan using this index.  However, if
     * the rel is a target relation of UPDATE/DELETE/SELECT FOR UPDATE, we
     * cannot remove such quals from the plan, because they need to be in the
     * plan so that they will be properly rechecked by EvalPlanQual testing.
     * Some day we might want to remove such quals from the main plan anyway
     * and pass them through to EvalPlanQual via a side channel; but for now,
     * we just don't remove implied quals at all for target relations.
     */
    is_target_rel = (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);
        }
    }
}

compare_pathkeys()

PathKeysComparison compare_pathkeys	(	List *	keys1,
		List *	keys2
	)

Definition at line 285 of file pathkeys.c.

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

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

{
    ListCell   *key1,
               *key2;

    /*
     * Fall out quickly if we are passed two identical lists.  This mostly
     * catches the case where both are NIL, but that's common enough to
     * warrant the test.
     */
    if (keys1 == keys2)
        return PATHKEYS_EQUAL;

    forboth(key1, keys1, key2, keys2)
    {
        PathKey    *pathkey1 = (PathKey *) lfirst(key1);
        PathKey    *pathkey2 = (PathKey *) lfirst(key2);

        if (pathkey1 != pathkey2)
            return PATHKEYS_DIFFERENT;  /* no need to keep looking */
    }

    /*
     * If we reached the end of only one list, the other is longer and
     * therefore not a subset.
     */
    if (key1 != NULL)
        return PATHKEYS_BETTER1;    /* key1 is longer */
    if (key2 != NULL)
        return PATHKEYS_BETTER2;    /* key2 is longer */
    return PATHKEYS_EQUAL;
}

compute_parallel_worker()

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

Definition at line 3749 of file allpaths.c.

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

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

{
    int         parallel_workers = 0;

    /*
     * If the user has set the parallel_workers reloption, use that; otherwise
     * select a default number of workers.
     */
    if (rel->rel_parallel_workers != -1)
        parallel_workers = rel->rel_parallel_workers;
    else
    {
        /*
         * If the number of pages being scanned is insufficient to justify a
         * parallel scan, just return zero ... unless it's an inheritance
         * child. In that case, we want to generate a parallel path here
         * anyway.  It might not be worthwhile just for this relation, but
         * when combined with all of its inheritance siblings it may well pay
         * off.
         */
        if (rel->reloptkind == RELOPT_BASEREL &&
            ((heap_pages >= 0 && heap_pages < min_parallel_table_scan_size) ||
             (index_pages >= 0 && index_pages < min_parallel_index_scan_size)))
            return 0;

        if (heap_pages >= 0)
        {
            int         heap_parallel_threshold;
            int         heap_parallel_workers = 1;

            /*
             * Select the number of workers based on the log of the size of
             * the relation.  This probably needs to be a good deal more
             * sophisticated, but we need something here for now.  Note that
             * the upper limit of the min_parallel_table_scan_size GUC is
             * chosen to prevent overflow here.
             */
            heap_parallel_threshold = Max(min_parallel_table_scan_size, 1);
            while (heap_pages >= (BlockNumber) (heap_parallel_threshold * 3))
            {
                heap_parallel_workers++;
                heap_parallel_threshold *= 3;
                if (heap_parallel_threshold > INT_MAX / 3)
                    break;      /* avoid overflow */
            }

            parallel_workers = heap_parallel_workers;
        }

        if (index_pages >= 0)
        {
            int         index_parallel_workers = 1;
            int         index_parallel_threshold;

            /* same calculation as for heap_pages above */
            index_parallel_threshold = Max(min_parallel_index_scan_size, 1);
            while (index_pages >= (BlockNumber) (index_parallel_threshold * 3))
            {
                index_parallel_workers++;
                index_parallel_threshold *= 3;
                if (index_parallel_threshold > INT_MAX / 3)
                    break;      /* avoid overflow */
            }

            if (parallel_workers > 0)
                parallel_workers = Min(parallel_workers, index_parallel_workers);
            else
                parallel_workers = index_parallel_workers;
        }
    }

    /* In no case use more than caller supplied maximum number of workers */
    parallel_workers = Min(parallel_workers, max_workers);

    return parallel_workers;
}

convert_subquery_pathkeys()

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

Definition at line 838 of file pathkeys.c.

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

Referenced by set_subquery_pathlist().

{
    List       *retval = NIL;
    int         retvallen = 0;
    int         outer_query_keys = list_length(root->query_pathkeys);
    ListCell   *i;

    foreach(i, subquery_pathkeys)
    {
        PathKey    *sub_pathkey = (PathKey *) lfirst(i);
        EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
        PathKey    *best_pathkey = NULL;

        if (sub_eclass->ec_has_volatile)
        {
            /*
             * If the sub_pathkey's EquivalenceClass is volatile, then it must
             * have come from an ORDER BY clause, and we have to match it to
             * that same targetlist entry.
             */
            TargetEntry *tle;
            Var        *outer_var;

            if (sub_eclass->ec_sortref == 0)    /* can't happen */
                elog(ERROR, "volatile EquivalenceClass has no sortref");
            tle = get_sortgroupref_tle(sub_eclass->ec_sortref, subquery_tlist);
            Assert(tle);
            /* Is TLE actually available to the outer query? */
            outer_var = find_var_for_subquery_tle(rel, tle);
            if (outer_var)
            {
                /* We can represent this sub_pathkey */
                EquivalenceMember *sub_member;
                EquivalenceClass *outer_ec;

                Assert(list_length(sub_eclass->ec_members) == 1);
                sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);

                /*
                 * Note: it might look funny to be setting sortref = 0 for a
                 * reference to a volatile sub_eclass.  However, the
                 * expression is *not* volatile in the outer query: it's just
                 * a Var referencing whatever the subquery emitted. (IOW, the
                 * outer query isn't going to re-execute the volatile
                 * expression itself.)  So this is okay.  Likewise, it's
                 * correct to pass nullable_relids = NULL, because we're
                 * underneath any outer joins appearing in the outer query.
                 */
                outer_ec =
                    get_eclass_for_sort_expr(root,
                                             (Expr *) outer_var,
                                             NULL,
                                             sub_eclass->ec_opfamilies,
                                             sub_member->em_datatype,
                                             sub_eclass->ec_collation,
                                             0,
                                             rel->relids,
                                             false);

                /*
                 * If we don't find a matching EC, sub-pathkey isn't
                 * interesting to the outer query
                 */
                if (outer_ec)
                    best_pathkey =
                        make_canonical_pathkey(root,
                                               outer_ec,
                                               sub_pathkey->pk_opfamily,
                                               sub_pathkey->pk_strategy,
                                               sub_pathkey->pk_nulls_first);
            }
        }
        else
        {
            /*
             * Otherwise, the sub_pathkey's EquivalenceClass could contain
             * multiple elements (representing knowledge that multiple items
             * are effectively equal).  Each element might match none, one, or
             * more of the output columns that are visible to the outer query.
             * This means we may have multiple possible representations of the
             * sub_pathkey in the context of the outer query.  Ideally we
             * would generate them all and put them all into an EC of the
             * outer query, thereby propagating equality knowledge up to the
             * outer query.  Right now we cannot do so, because the outer
             * query's EquivalenceClasses are already frozen when this is
             * called. Instead we prefer the one that has the highest "score"
             * (number of EC peers, plus one if it matches the outer
             * query_pathkeys). This is the most likely to be useful in the
             * outer query.
             */
            int         best_score = -1;
            ListCell   *j;

            foreach(j, sub_eclass->ec_members)
            {
                EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
                Expr       *sub_expr = sub_member->em_expr;
                Oid         sub_expr_type = sub_member->em_datatype;
                Oid         sub_expr_coll = sub_eclass->ec_collation;
                ListCell   *k;

                if (sub_member->em_is_child)
                    continue;   /* ignore children here */

                foreach(k, subquery_tlist)
                {
                    TargetEntry *tle = (TargetEntry *) lfirst(k);
                    Var        *outer_var;
                    Expr       *tle_expr;
                    EquivalenceClass *outer_ec;
                    PathKey    *outer_pk;
                    int         score;

                    /* Is TLE actually available to the outer query? */
                    outer_var = find_var_for_subquery_tle(rel, tle);
                    if (!outer_var)
                        continue;

                    /*
                     * The targetlist entry is considered to match if it
                     * matches after sort-key canonicalization.  That is
                     * needed since the sub_expr has been through the same
                     * process.
                     */
                    tle_expr = canonicalize_ec_expression(tle->expr,
                                                          sub_expr_type,
                                                          sub_expr_coll);
                    if (!equal(tle_expr, sub_expr))
                        continue;

                    /* See if we have a matching EC for the TLE */
                    outer_ec = get_eclass_for_sort_expr(root,
                                                        (Expr *) outer_var,
                                                        NULL,
                                                        sub_eclass->ec_opfamilies,
                                                        sub_expr_type,
                                                        sub_expr_coll,
                                                        0,
                                                        rel->relids,
                                                        false);

                    /*
                     * If we don't find a matching EC, this sub-pathkey isn't
                     * interesting to the outer query
                     */
                    if (!outer_ec)
                        continue;

                    outer_pk = make_canonical_pathkey(root,
                                                      outer_ec,
                                                      sub_pathkey->pk_opfamily,
                                                      sub_pathkey->pk_strategy,
                                                      sub_pathkey->pk_nulls_first);
                    /* score = # of equivalence peers */
                    score = list_length(outer_ec->ec_members) - 1;
                    /* +1 if it matches the proper query_pathkeys item */
                    if (retvallen < outer_query_keys &&
                        list_nth(root->query_pathkeys, retvallen) == outer_pk)
                        score++;
                    if (score > best_score)
                    {
                        best_pathkey = outer_pk;
                        best_score = score;
                    }
                }
            }
        }

        /*
         * If we couldn't find a representation of this sub_pathkey, we're
         * done (we can't use the ones to its right, either).
         */
        if (!best_pathkey)
            break;

        /*
         * Eliminate redundant ordering info; could happen if outer query
         * equivalences subquery keys...
         */
        if (!pathkey_is_redundant(best_pathkey, retval))
        {
            retval = lappend(retval, best_pathkey);
            retvallen++;
        }
    }

    return retval;
}

create_index_paths()

void create_index_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 235 of file indxpath.c.

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

Referenced by set_plain_rel_pathlist().

{
    List       *indexpaths;
    List       *bitindexpaths;
    List       *bitjoinpaths;
    List       *joinorclauses;
    IndexClauseSet rclauseset;
    IndexClauseSet jclauseset;
    IndexClauseSet eclauseset;
    ListCell   *lc;

    /* Skip the whole mess if no indexes */
    if (rel->indexlist == NIL)
        return;

    /* Bitmap paths are collected and then dealt with at the end */
    bitindexpaths = bitjoinpaths = joinorclauses = NIL;

    /* Examine each index in turn */
    foreach(lc, rel->indexlist)
    {
        IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);

        /* Protect limited-size array in IndexClauseSets */
        Assert(index->nkeycolumns <= INDEX_MAX_KEYS);

        /*
         * Ignore partial indexes that do not match the query.
         * (generate_bitmap_or_paths() might be able to do something with
         * them, but that's of no concern here.)
         */
        if (index->indpred != NIL && !index->predOK)
            continue;

        /*
         * Identify the restriction clauses that can match the index.
         */
        MemSet(&rclauseset, 0, sizeof(rclauseset));
        match_restriction_clauses_to_index(root, index, &rclauseset);

        /*
         * Build index paths from the restriction clauses.  These will be
         * non-parameterized paths.  Plain paths go directly to add_path(),
         * bitmap paths are added to bitindexpaths to be handled below.
         */
        get_index_paths(root, rel, index, &rclauseset,
                        &bitindexpaths);

        /*
         * Identify the join clauses that can match the index.  For the moment
         * we keep them separate from the restriction clauses.  Note that this
         * step finds only "loose" join clauses that have not been merged into
         * EquivalenceClasses.  Also, collect join OR clauses for later.
         */
        MemSet(&jclauseset, 0, sizeof(jclauseset));
        match_join_clauses_to_index(root, rel, index,
                                    &jclauseset, &joinorclauses);

        /*
         * Look for EquivalenceClasses that can generate joinclauses matching
         * the index.
         */
        MemSet(&eclauseset, 0, sizeof(eclauseset));
        match_eclass_clauses_to_index(root, index,
                                      &eclauseset);

        /*
         * If we found any plain or eclass join clauses, build parameterized
         * index paths using them.
         */
        if (jclauseset.nonempty || eclauseset.nonempty)
            consider_index_join_clauses(root, rel, index,
                                        &rclauseset,
                                        &jclauseset,
                                        &eclauseset,
                                        &bitjoinpaths);
    }

    /*
     * Generate BitmapOrPaths for any suitable OR-clauses present in the
     * restriction list.  Add these to bitindexpaths.
     */
    indexpaths = generate_bitmap_or_paths(root, rel,
                                          rel->baserestrictinfo, NIL);
    bitindexpaths = list_concat(bitindexpaths, indexpaths);

    /*
     * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
     * the joinclause list.  Add these to bitjoinpaths.
     */
    indexpaths = generate_bitmap_or_paths(root, rel,
                                          joinorclauses, rel->baserestrictinfo);
    bitjoinpaths = list_concat(bitjoinpaths, indexpaths);

    /*
     * If we found anything usable, generate a BitmapHeapPath for the most
     * promising combination of restriction bitmap index paths.  Note there
     * will be only one such path no matter how many indexes exist.  This
     * should be sufficient since there's basically only one figure of merit
     * (total cost) for such a path.
     */
    if (bitindexpaths != NIL)
    {
        Path       *bitmapqual;
        BitmapHeapPath *bpath;

        bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
        bpath = create_bitmap_heap_path(root, rel, bitmapqual,
                                        rel->lateral_relids, 1.0, 0);
        add_path(rel, (Path *) bpath);

        /* create a partial bitmap heap path */
        if (rel->consider_parallel && rel->lateral_relids == NULL)
            create_partial_bitmap_paths(root, rel, bitmapqual);
    }

    /*
     * Likewise, if we found anything usable, generate BitmapHeapPaths for the
     * most promising combinations of join bitmap index paths.  Our strategy
     * is to generate one such path for each distinct parameterization seen
     * among the available bitmap index paths.  This may look pretty
     * expensive, but usually there won't be very many distinct
     * parameterizations.  (This logic is quite similar to that in
     * consider_index_join_clauses, but we're working with whole paths not
     * individual clauses.)
     */
    if (bitjoinpaths != NIL)
    {
        List       *all_path_outers;
        ListCell   *lc;

        /* 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);

            if (!bms_equal_any(required_outer, all_path_outers))
                all_path_outers = lappend(all_path_outers, required_outer);
        }

        /* Now, for each distinct parameterization set ... */
        foreach(lc, all_path_outers)
        {
            Relids      max_outers = (Relids) lfirst(lc);
            List       *this_path_set;
            Path       *bitmapqual;
            Relids      required_outer;
            double      loop_count;
            BitmapHeapPath *bpath;
            ListCell   *lcp;

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

create_partial_bitmap_paths()

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

Definition at line 3713 of file allpaths.c.

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

Referenced by create_index_paths().

{
    int         parallel_workers;
    double      pages_fetched;

    /* Compute heap pages for bitmap heap scan */
    pages_fetched = compute_bitmap_pages(root, rel, bitmapqual, 1.0,
                                         NULL, NULL);

    parallel_workers = compute_parallel_worker(rel, pages_fetched, -1,
                                               max_parallel_workers_per_gather);

    if (parallel_workers <= 0)
        return;

    add_partial_path(rel, (Path *) create_bitmap_heap_path(root, rel,
                                                           bitmapqual, rel->lateral_relids, 1.0, parallel_workers));
}

create_tidscan_paths()

void create_tidscan_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 459 of file tidpath.c.

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

Referenced by set_plain_rel_pathlist().

{
    List       *tidquals;
    List       *tidrangequals;

    /*
     * If any suitable quals exist in the rel's baserestrict list, generate a
     * plain (unparameterized) TidPath with them.
     */
    tidquals = TidQualFromRestrictInfoList(root, rel->baserestrictinfo, rel);

    if (tidquals != NIL)
    {
        /*
         * This path uses no join clauses, but it could still have required
         * parameterization due to LATERAL refs in its tlist.
         */
        Relids      required_outer = rel->lateral_relids;

        add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
                                                   required_outer));
    }

    /*
     * If there are range quals in the baserestrict list, generate a
     * TidRangePath.
     */
    tidrangequals = TidRangeQualFromRestrictInfoList(rel->baserestrictinfo,
                                                     rel);

    if (tidrangequals != NIL)
    {
        /*
         * This path uses no join clauses, but it could still have required
         * parameterization due to LATERAL refs in its tlist.
         */
        Relids      required_outer = rel->lateral_relids;

        add_path(rel, (Path *) create_tidrangescan_path(root, rel,
                                                        tidrangequals,
                                                        required_outer));
    }

    /*
     * Try to generate parameterized TidPaths using equality clauses extracted
     * from EquivalenceClasses.  (This is important since simple "t1.ctid =
     * t2.ctid" clauses will turn into ECs.)
     */
    if (rel->has_eclass_joins)
    {
        List       *clauses;

        /* Generate clauses, skipping any that join to lateral_referencers */
        clauses = generate_implied_equalities_for_column(root,
                                                         rel,
                                                         ec_member_matches_ctid,
                                                         NULL,
                                                         rel->lateral_referencers);

        /* Generate a path for each usable join clause */
        BuildParameterizedTidPaths(root, rel, clauses);
    }

    /*
     * Also consider parameterized TidPaths using "loose" join quals.  Quals
     * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
     * join quals, for example.
     */
    BuildParameterizedTidPaths(root, rel, rel->joininfo);
}

eclass_useful_for_merging()

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

Definition at line 3091 of file equivclass.c.

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

Referenced by get_useful_ecs_for_relation(), and pathkeys_useful_for_merging().

{
    Relids      relids;
    ListCell   *lc;

    Assert(!eclass->ec_merged);

    /*
     * Won't generate joinclauses if const or single-member (the latter test
     * covers the volatile case too)
     */
    if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
        return false;

    /*
     * Note we don't test ec_broken; if we did, we'd need a separate code path
     * to look through ec_sources.  Checking the members anyway is OK as a
     * possibly-overoptimistic heuristic.
     */

    /* If specified rel is a child, we must consider the topmost parent rel */
    if (IS_OTHER_REL(rel))
    {
        Assert(!bms_is_empty(rel->top_parent_relids));
        relids = rel->top_parent_relids;
    }
    else
        relids = rel->relids;

    /* If rel already includes all members of eclass, no point in searching */
    if (bms_is_subset(eclass->ec_relids, relids))
        return false;

    /* To join, we need a member not in the given rel */
    foreach(lc, eclass->ec_members)
    {
        EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);

        if (cur_em->em_is_child)
            continue;           /* ignore children here */

        if (!bms_overlap(cur_em->em_relids, relids))
            return true;
    }

    return false;
}

exprs_known_equal()

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

Definition at line 2386 of file equivclass.c.

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

Referenced by add_unique_group_var().

{
    ListCell   *lc1;

    foreach(lc1, root->eq_classes)
    {
        EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
        bool        item1member = false;
        bool        item2member = false;
        ListCell   *lc2;

        /* Never match to a volatile EC */
        if (ec->ec_has_volatile)
            continue;

        foreach(lc2, ec->ec_members)
        {
            EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);

            if (em->em_is_child)
                continue;       /* ignore children here */
            if (equal(item1, em->em_expr))
                item1member = true;
            else if (equal(item2, em->em_expr))
                item2member = true;
            /* Exit as soon as equality is proven */
            if (item1member && item2member)
                return true;
        }
    }
    return false;
}

find_computable_ec_member()

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

Definition at line 851 of file equivclass.c.

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

Referenced by prepare_sort_from_pathkeys(), and relation_can_be_sorted_early().

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

find_derived_clause_for_ec_member()

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

Definition at line 2528 of file equivclass.c.

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

Referenced by get_foreign_key_join_selectivity().

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

find_ec_member_matching_expr()

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

Definition at line 786 of file equivclass.c.

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

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

find_em_expr_for_rel()

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

Definition at line 939 of file equivclass.c.

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

{
    ListCell   *lc_em;

    foreach(lc_em, ec->ec_members)
    {
        EquivalenceMember *em = lfirst(lc_em);

        if (bms_is_subset(em->em_relids, rel->relids) &&
            !bms_is_empty(em->em_relids))
        {
            /*
             * If there is more than one equivalence member whose Vars are
             * taken entirely from this relation, we'll be content to choose
             * any one of those.
             */
            return em->em_expr;
        }
    }

    /* We didn't find any suitable equivalence class expression */
    return NULL;
}

find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1262 of file pathkeys.c.

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

{
    List       *mergeclauses = NIL;
    ListCell   *i;

    /* make sure we have eclasses cached in the clauses */
    foreach(i, restrictinfos)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);

        update_mergeclause_eclasses(root, rinfo);
    }

    foreach(i, pathkeys)
    {
        PathKey    *pathkey = (PathKey *) lfirst(i);
        EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
        List       *matched_restrictinfos = NIL;
        ListCell   *j;

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

            clause_ec = rinfo->outer_is_left ?
                rinfo->left_ec : rinfo->right_ec;
            if (clause_ec == pathkey_ec)
                matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
        }

        /*
         * If we didn't find a mergeclause, we're done --- any additional
         * sort-key positions in the pathkeys are useless.  (But we can still
         * mergejoin if we found at least one mergeclause.)
         */
        if (matched_restrictinfos == NIL)
            break;

        /*
         * If we did find usable mergeclause(s) for this sort-key position,
         * add them to result list.
         */
        mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
    }

    return mergeclauses;
}

generate_base_implied_equalities()

void generate_base_implied_equalities

(

PlannerInfo *

root

)

Definition at line 1088 of file equivclass.c.

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

Referenced by query_planner().

{
    int         ec_index;
    ListCell   *lc;

    /*
     * At this point, we're done absorbing knowledge of equivalences in the
     * query, so no further EC merging should happen, and ECs remaining in the
     * eq_classes list can be considered canonical.  (But note that it's still
     * possible for new single-member ECs to be added through
     * get_eclass_for_sort_expr().)
     */
    root->ec_merging_done = true;

    ec_index = 0;
    foreach(lc, root->eq_classes)
    {
        EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
        bool        can_generate_joinclause = false;
        int         i;

        Assert(ec->ec_merged == NULL);  /* else shouldn't be in list */
        Assert(!ec->ec_broken); /* not yet anyway... */

        /*
         * Generate implied equalities that are restriction clauses.
         * Single-member ECs won't generate any deductions, either here or at
         * the join level.
         */
        if (list_length(ec->ec_members) > 1)
        {
            if (ec->ec_has_const)
                generate_base_implied_equalities_const(root, ec);
            else
                generate_base_implied_equalities_no_const(root, ec);

            /* Recover if we failed to generate required derived clauses */
            if (ec->ec_broken)
                generate_base_implied_equalities_broken(root, ec);

            /* Detect whether this EC might generate join clauses */
            can_generate_joinclause =
                (bms_membership(ec->ec_relids) == BMS_MULTIPLE);
        }

        /*
         * Mark the base rels cited in each eclass (which should all exist by
         * now) with the eq_classes indexes of all eclasses mentioning them.
         * This will let us avoid searching in subsequent lookups.  While
         * we're at it, we can mark base rels that have pending eclass joins;
         * this is a cheap version of has_relevant_eclass_joinclause().
         */
        i = -1;
        while ((i = bms_next_member(ec->ec_relids, i)) > 0)
        {
            RelOptInfo *rel = root->simple_rel_array[i];

            Assert(rel->reloptkind == RELOPT_BASEREL);

            rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
                                                 ec_index);

            if (can_generate_joinclause)
                rel->has_eclass_joins = true;
        }

        ec_index++;
    }
}

generate_gather_paths()

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

Definition at line 2608 of file allpaths.c.

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

Referenced by create_partial_distinct_paths(), and generate_useful_gather_paths().

{
    Path       *cheapest_partial_path;
    Path       *simple_gather_path;
    ListCell   *lc;
    double      rows;
    double     *rowsp = NULL;

    /* If there are no partial paths, there's nothing to do here. */
    if (rel->partial_pathlist == NIL)
        return;

    /* Should we override the rel's rowcount estimate? */
    if (override_rows)
        rowsp = &rows;

    /*
     * The output of Gather is always unsorted, so there's only one partial
     * path of interest: the cheapest one.  That will be the one at the front
     * of partial_pathlist because of the way add_partial_path works.
     */
    cheapest_partial_path = linitial(rel->partial_pathlist);
    rows =
        cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
    simple_gather_path = (Path *)
        create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
                           NULL, rowsp);
    add_path(rel, simple_gather_path);

    /*
     * For each useful ordering, we can consider an order-preserving Gather
     * Merge.
     */
    foreach(lc, rel->partial_pathlist)
    {
        Path       *subpath = (Path *) lfirst(lc);
        GatherMergePath *path;

        if (subpath->pathkeys == NIL)
            continue;

        rows = subpath->rows * subpath->parallel_workers;
        path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
                                        subpath->pathkeys, NULL, rowsp);
        add_path(rel, &path->path);
    }
}

generate_implied_equalities_for_column()

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

Definition at line 2850 of file equivclass.c.

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

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

{
    List       *result = NIL;
    bool        is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
    Relids      parent_relids;
    int         i;

    /* Should be OK to rely on eclass_indexes */
    Assert(root->ec_merging_done);

    /* Indexes are available only on base or "other" member relations. */
    Assert(IS_SIMPLE_REL(rel));

    /* If it's a child rel, we'll need to know what its parent(s) are */
    if (is_child_rel)
        parent_relids = find_childrel_parents(root, rel);
    else
        parent_relids = NULL;   /* not used, but keep compiler quiet */

    i = -1;
    while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0)
    {
        EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
        EquivalenceMember *cur_em;
        ListCell   *lc2;

        /* Sanity check eclass_indexes only contain ECs for rel */
        Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids));

        /*
         * Won't generate joinclauses if const or single-member (the latter
         * test covers the volatile case too)
         */
        if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
            continue;

        /*
         * Scan members, looking for a match to the target column.  Note that
         * child EC members are considered, but only when they belong to the
         * target relation.  (Unlike regular members, the same expression
         * could be a child member of more than one EC.  Therefore, it's
         * potentially order-dependent which EC a child relation's target
         * column gets matched to.  This is annoying but it only happens in
         * corner cases, so for now we live with just reporting the first
         * match.  See also get_eclass_for_sort_expr.)
         */
        cur_em = NULL;
        foreach(lc2, cur_ec->ec_members)
        {
            cur_em = (EquivalenceMember *) lfirst(lc2);
            if (bms_equal(cur_em->em_relids, rel->relids) &&
                callback(root, rel, cur_ec, cur_em, callback_arg))
                break;
            cur_em = NULL;
        }

        if (!cur_em)
            continue;

        /*
         * Found our match.  Scan the other EC members and attempt to generate
         * joinclauses.
         */
        foreach(lc2, cur_ec->ec_members)
        {
            EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
            Oid         eq_op;
            RestrictInfo *rinfo;

            if (other_em->em_is_child)
                continue;       /* ignore children here */

            /* Make sure it'll be a join to a different rel */
            if (other_em == cur_em ||
                bms_overlap(other_em->em_relids, rel->relids))
                continue;

            /* Forget it if caller doesn't want joins to this rel */
            if (bms_overlap(other_em->em_relids, prohibited_rels))
                continue;

            /*
             * Also, if this is a child rel, avoid generating a useless join
             * to its parent rel(s).
             */
            if (is_child_rel &&
                bms_overlap(parent_relids, other_em->em_relids))
                continue;

            eq_op = select_equality_operator(cur_ec,
                                             cur_em->em_datatype,
                                             other_em->em_datatype);
            if (!OidIsValid(eq_op))
                continue;

            /* set parent_ec to mark as redundant with other joinclauses */
            rinfo = create_join_clause(root, cur_ec, eq_op,
                                       cur_em, other_em,
                                       cur_ec);

            result = lappend(result, rinfo);
        }

        /*
         * If somehow we failed to create any join clauses, we might as well
         * keep scanning the ECs for another match.  But if we did make any,
         * we're done, because we don't want to return non-redundant clauses.
         */
        if (result)
            break;
    }

    return result;
}

generate_join_implied_equalities()

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

Definition at line 1421 of file equivclass.c.

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

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

{
    List       *result = NIL;
    Relids      inner_relids = inner_rel->relids;
    Relids      nominal_inner_relids;
    Relids      nominal_join_relids;
    Bitmapset  *matching_ecs;
    int         i;

    /* If inner rel is a child, extra setup work is needed */
    if (IS_OTHER_REL(inner_rel))
    {
        Assert(!bms_is_empty(inner_rel->top_parent_relids));

        /* Fetch relid set for the topmost parent rel */
        nominal_inner_relids = inner_rel->top_parent_relids;
        /* ECs will be marked with the parent's relid, not the child's */
        nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
    }
    else
    {
        nominal_inner_relids = inner_relids;
        nominal_join_relids = join_relids;
    }

    /*
     * Get all eclasses that mention both inner and outer sides of the join
     */
    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;
}

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

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

Referenced by get_joinrel_parampathinfo().

{
    List       *result = NIL;
    Relids      inner_relids = inner_rel->relids;
    Relids      nominal_inner_relids;
    Relids      nominal_join_relids;
    ListCell   *lc;

    /* If inner rel is a child, extra setup work is needed */
    if (IS_OTHER_REL(inner_rel))
    {
        Assert(!bms_is_empty(inner_rel->top_parent_relids));

        /* Fetch relid set for the topmost parent rel */
        nominal_inner_relids = inner_rel->top_parent_relids;
        /* ECs will be marked with the parent's relid, not the child's */
        nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
    }
    else
    {
        nominal_inner_relids = inner_relids;
        nominal_join_relids = join_relids;
    }

    foreach(lc, eclasses)
    {
        EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
        List       *sublist = NIL;

        /* ECs containing consts do not need any further enforcement */
        if (ec->ec_has_const)
            continue;

        /* Single-member ECs won't generate any deductions */
        if (list_length(ec->ec_members) <= 1)
            continue;

        /* We can quickly ignore any that don't overlap the join, too */
        if (!bms_overlap(ec->ec_relids, nominal_join_relids))
            continue;

        if (!ec->ec_broken)
            sublist = generate_join_implied_equalities_normal(root,
                                                              ec,
                                                              join_relids,
                                                              outer_relids,
                                                              inner_relids);

        /* Recover if we failed to generate required derived clauses */
        if (ec->ec_broken)
            sublist = generate_join_implied_equalities_broken(root,
                                                              ec,
                                                              nominal_join_relids,
                                                              outer_relids,
                                                              nominal_inner_relids,
                                                              inner_rel);

        result = list_concat(result, sublist);
    }

    return result;
}

generate_partitionwise_join_paths()

void generate_partitionwise_join_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 3837 of file allpaths.c.

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

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

{
    List       *live_children = NIL;
    int         cnt_parts;
    int         num_parts;
    RelOptInfo **part_rels;

    /* Handle only join relations here. */
    if (!IS_JOIN_REL(rel))
        return;

    /* We've nothing to do if the relation is not partitioned. */
    if (!IS_PARTITIONED_REL(rel))
        return;

    /* The relation should have consider_partitionwise_join set. */
    Assert(rel->consider_partitionwise_join);

    /* Guard against stack overflow due to overly deep partition hierarchy. */
    check_stack_depth();

    num_parts = rel->nparts;
    part_rels = rel->part_rels;

    /* Collect non-dummy child-joins. */
    for (cnt_parts = 0; cnt_parts < num_parts; cnt_parts++)
    {
        RelOptInfo *child_rel = part_rels[cnt_parts];

        /* If it's been pruned entirely, it's certainly dummy. */
        if (child_rel == NULL)
            continue;

        /* Add partitionwise join paths for partitioned child-joins. */
        generate_partitionwise_join_paths(root, child_rel);

        set_cheapest(child_rel);

        /* Dummy children will not be scanned, so ignore those. */
        if (IS_DUMMY_REL(child_rel))
            continue;

#ifdef OPTIMIZER_DEBUG
        debug_print_rel(root, child_rel);
#endif

        live_children = lappend(live_children, child_rel);
    }

    /* If all child-joins are dummy, parent join is also dummy. */
    if (!live_children)
    {
        mark_dummy_rel(rel);
        return;
    }

    /* Build additional paths for this rel from child-join paths. */
    add_paths_to_append_rel(root, rel, live_children);
    list_free(live_children);
}

generate_useful_gather_paths()

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

Definition at line 2746 of file allpaths.c.

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

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

{
    ListCell   *lc;
    double      rows;
    double     *rowsp = NULL;
    List       *useful_pathkeys_list = NIL;
    Path       *cheapest_partial_path = NULL;

    /* If there are no partial paths, there's nothing to do here. */
    if (rel->partial_pathlist == NIL)
        return;

    /* Should we override the rel's rowcount estimate? */
    if (override_rows)
        rowsp = &rows;

    /* generate the regular gather (merge) paths */
    generate_gather_paths(root, rel, override_rows);

    /* consider incremental sort for interesting orderings */
    useful_pathkeys_list = get_useful_pathkeys_for_relation(root, rel, 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;

            /*
             * Consider regular sort for the cheapest partial path (for each
             * useful pathkeys). We know the path is not sorted, because we'd
             * not get here otherwise.
             *
             * This is not redundant with the gather paths created in
             * generate_gather_paths, because that doesn't generate ordered
             * output. Here we add an explicit sort to match the useful
             * ordering.
             */
            if (cheapest_partial_path == subpath)
            {
                Path       *tmp;

                tmp = (Path *) create_sort_path(root,
                                                rel,
                                                subpath,
                                                useful_pathkeys,
                                                -1.0);

                rows = tmp->rows * tmp->parallel_workers;

                path = create_gather_merge_path(root, rel,
                                                tmp,
                                                rel->reltarget,
                                                tmp->pathkeys,
                                                NULL,
                                                rowsp);

                add_path(rel, &path->path);

                /* Fall through */
            }

            /*
             * Consider incremental sort, but only when the subpath is already
             * partially sorted on a pathkey prefix.
             */
            if (enable_incremental_sort && presorted_keys > 0)
            {
                Path       *tmp;

                /*
                 * We should have already excluded pathkeys of length 1
                 * because then presorted_keys > 0 would imply is_sorted was
                 * true.
                 */
                Assert(list_length(useful_pathkeys) != 1);

                tmp = (Path *) create_incremental_sort_path(root,
                                                            rel,
                                                            subpath,
                                                            useful_pathkeys,
                                                            presorted_keys,
                                                            -1);

                path = create_gather_merge_path(root, rel,
                                                tmp,
                                                rel->reltarget,
                                                tmp->pathkeys,
                                                NULL,
                                                rowsp);

                add_path(rel, &path->path);
            }
        }
    }
}

get_cheapest_fractional_path_for_pathkeys()

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

Definition at line 449 of file pathkeys.c.

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

Referenced by build_minmax_path().

{
    Path       *matched_path = NULL;
    ListCell   *l;

    foreach(l, paths)
    {
        Path       *path = (Path *) lfirst(l);

        /*
         * Since cost comparison is a lot cheaper than pathkey comparison, do
         * that first.  (XXX is that still true?)
         */
        if (matched_path != NULL &&
            compare_fractional_path_costs(matched_path, path, fraction) <= 0)
            continue;

        if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
            bms_is_subset(PATH_REQ_OUTER(path), required_outer))
            matched_path = path;
    }
    return matched_path;
}

get_cheapest_parallel_safe_total_inner()

Path* get_cheapest_parallel_safe_total_inner

(

List *

paths

)

Definition at line 482 of file pathkeys.c.

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

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

{
    ListCell   *l;

    foreach(l, paths)
    {
        Path       *innerpath = (Path *) lfirst(l);

        if (innerpath->parallel_safe &&
            bms_is_empty(PATH_REQ_OUTER(innerpath)))
            return innerpath;
    }

    return NULL;
}

get_cheapest_path_for_pathkeys()

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

Definition at line 404 of file pathkeys.c.

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

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

{
    Path       *matched_path = NULL;
    ListCell   *l;

    foreach(l, paths)
    {
        Path       *path = (Path *) lfirst(l);

        /*
         * Since cost comparison is a lot cheaper than pathkey comparison, do
         * that first.  (XXX is that still true?)
         */
        if (matched_path != NULL &&
            compare_path_costs(matched_path, path, cost_criterion) <= 0)
            continue;

        if (require_parallel_safe && !path->parallel_safe)
            continue;

        if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
            bms_is_subset(PATH_REQ_OUTER(path), required_outer))
            matched_path = path;
    }
    return matched_path;
}

get_eclass_for_sort_expr()

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

Definition at line 621 of file equivclass.c.

References add_eq_member(), Assert, bms_add_member(), bms_equal(), bms_intersect(), bms_next_member(), canonicalize_ec_expression(), contain_agg_clause(), contain_volatile_functions(), contain_window_function(), copyObject, EquivalenceClass::ec_below_outer_join, 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, PlannerInfo::ec_merging_done, 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_relids, PlannerInfo::eq_classes, equal(), ERROR, expression_returns_set(), i, lappend(), lfirst, list_copy(), list_length(), makeNode, MemoryContextSwitchTo(), NIL, PlannerInfo::planner_cxt, pull_varnos(), RELOPT_BASEREL, RELOPT_DEADREL, RelOptInfo::reloptkind, and PlannerInfo::simple_rel_array.

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

{
    Relids      expr_relids;
    EquivalenceClass *newec;
    EquivalenceMember *newem;
    ListCell   *lc1;
    MemoryContext oldcontext;

    /*
     * Ensure the expression exposes the correct type and collation.
     */
    expr = canonicalize_ec_expression(expr, opcintype, collation);

    /*
     * Scan through the existing EquivalenceClasses for a match
     */
    foreach(lc1, root->eq_classes)
    {
        EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
        ListCell   *lc2;

        /*
         * Never match to a volatile EC, except when we are looking at another
         * reference to the same volatile SortGroupClause.
         */
        if (cur_ec->ec_has_volatile &&
            (sortref == 0 || sortref != cur_ec->ec_sortref))
            continue;

        if (collation != cur_ec->ec_collation)
            continue;
        if (!equal(opfamilies, cur_ec->ec_opfamilies))
            continue;

        foreach(lc2, cur_ec->ec_members)
        {
            EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);

            /*
             * Ignore child members unless they match the request.
             */
            if (cur_em->em_is_child &&
                !bms_equal(cur_em->em_relids, rel))
                continue;

            /*
             * If below an outer join, don't match constants: they're not as
             * constant as they look.
             */
            if (cur_ec->ec_below_outer_join &&
                cur_em->em_is_const)
                continue;

            if (opcintype == cur_em->em_datatype &&
                equal(expr, cur_em->em_expr))
                return cur_ec;  /* Match! */
        }
    }

    /* No match; does caller want a NULL result? */
    if (!create_it)
        return NULL;

    /*
     * OK, build a new single-member EC
     *
     * Here, we must be sure that we construct the EC in the right context.
     */
    oldcontext = MemoryContextSwitchTo(root->planner_cxt);

    newec = makeNode(EquivalenceClass);
    newec->ec_opfamilies = list_copy(opfamilies);
    newec->ec_collation = collation;
    newec->ec_members = NIL;
    newec->ec_sources = NIL;
    newec->ec_derives = NIL;
    newec->ec_relids = NULL;
    newec->ec_has_const = false;
    newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
    newec->ec_below_outer_join = false;
    newec->ec_broken = false;
    newec->ec_sortref = sortref;
    newec->ec_min_security = UINT_MAX;
    newec->ec_max_security = 0;
    newec->ec_merged = NULL;

    if (newec->ec_has_volatile && sortref == 0) /* should not happen */
        elog(ERROR, "volatile EquivalenceClass has no sortref");

    /*
     * Get the precise set of nullable relids appearing in the expression.
     */
    expr_relids = pull_varnos(root, (Node *) expr);
    nullable_relids = bms_intersect(nullable_relids, expr_relids);

    newem = add_eq_member(newec, copyObject(expr), expr_relids,
                          nullable_relids, false, opcintype);

    /*
     * add_eq_member doesn't check for volatile functions, set-returning
     * functions, aggregates, or window functions, but such could appear in
     * sort expressions; so we have to check whether its const-marking was
     * correct.
     */
    if (newec->ec_has_const)
    {
        if (newec->ec_has_volatile ||
            expression_returns_set((Node *) expr) ||
            contain_agg_clause((Node *) expr) ||
            contain_window_function((Node *) expr))
        {
            newec->ec_has_const = false;
            newem->em_is_const = false;
        }
    }

    root->eq_classes = lappend(root->eq_classes, newec);

    /*
     * If EC merging is already complete, we have to mop up by adding the new
     * EC to the eclass_indexes of the relation(s) mentioned in it.
     */
    if (root->ec_merging_done)
    {
        int         ec_index = list_length(root->eq_classes) - 1;
        int         i = -1;

        while ((i = bms_next_member(newec->ec_relids, i)) > 0)
        {
            RelOptInfo *rel = root->simple_rel_array[i];

            Assert(rel->reloptkind == RELOPT_BASEREL ||
                   rel->reloptkind == RELOPT_DEADREL);

            rel->eclass_indexes = bms_add_member(rel->eclass_indexes,
                                                 ec_index);
        }
    }

    MemoryContextSwitchTo(oldcontext);

    return newec;
}

has_relevant_eclass_joinclause()

bool has_relevant_eclass_joinclause	(	PlannerInfo *	root,
		RelOptInfo *	rel1
	)

Definition at line 3047 of file equivclass.c.

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

Referenced by build_join_rel().

{
    Bitmapset  *matched_ecs;
    int         i;

    /* Examine only eclasses mentioning rel1 */
    matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids);

    i = -1;
    while ((i = bms_next_member(matched_ecs, i)) >= 0)
    {
        EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
                                                             i);

        /*
         * Won't generate joinclauses if single-member (this test covers the
         * volatile case too)
         */
        if (list_length(ec->ec_members) <= 1)
            continue;

        /*
         * Per the comment in have_relevant_eclass_joinclause, it's sufficient
         * to find an EC that mentions both this rel and some other rel.
         */
        if (!bms_is_subset(ec->ec_relids, rel1->relids))
            return true;
    }

    return false;
}

has_useful_pathkeys()

bool has_useful_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 1910 of file pathkeys.c.

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

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

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

have_dangerous_phv()

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

Definition at line 1184 of file joinrels.c.

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

Referenced by join_is_legal(), and try_nestloop_path().

{
    ListCell   *lc;

    foreach(lc, root->placeholder_list)
    {
        PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);

        if (!bms_is_subset(phinfo->ph_eval_at, inner_params))
            continue;           /* ignore, could not be a nestloop param */
        if (!bms_overlap(phinfo->ph_eval_at, outer_relids))
            continue;           /* ignore, not relevant to this join */
        if (bms_is_subset(phinfo->ph_eval_at, outer_relids))
            continue;           /* safe, it can be eval'd within outerrel */
        /* Otherwise, it's potentially unsafe, so reject the join */
        return true;
    }

    /* OK to perform the join */
    return false;
}

have_join_order_restriction()

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

Definition at line 951 of file joinrels.c.

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

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

{
    bool        result = false;
    ListCell   *l;

    /*
     * If either side has a direct lateral reference to the other, attempt the
     * join regardless of outer-join considerations.
     */
    if (bms_overlap(rel1->relids, rel2->direct_lateral_relids) ||
        bms_overlap(rel2->relids, rel1->direct_lateral_relids))
        return true;

    /*
     * Likewise, if both rels are needed to compute some PlaceHolderVar,
     * attempt the join regardless of outer-join considerations.  (This is not
     * very desirable, because a PHV with a large eval_at set will cause a lot
     * of probably-useless joins to be considered, but failing to do this can
     * cause us to fail to construct a plan at all.)
     */
    foreach(l, root->placeholder_list)
    {
        PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);

        if (bms_is_subset(rel1->relids, phinfo->ph_eval_at) &&
            bms_is_subset(rel2->relids, phinfo->ph_eval_at))
            return true;
    }

    /*
     * It's possible that the rels correspond to the left and right sides of a
     * degenerate outer join, that is, one with no joinclause mentioning the
     * non-nullable side; in which case we should force the join to occur.
     *
     * Also, the two rels could represent a clauseless join that has to be
     * completed to build up the LHS or RHS of an outer join.
     */
    foreach(l, root->join_info_list)
    {
        SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);

        /* ignore full joins --- other mechanisms handle them */
        if (sjinfo->jointype == JOIN_FULL)
            continue;

        /* Can we perform the SJ with these rels? */
        if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
            bms_is_subset(sjinfo->min_righthand, rel2->relids))
        {
            result = true;
            break;
        }
        if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
            bms_is_subset(sjinfo->min_righthand, rel1->relids))
        {
            result = true;
            break;
        }

        /*
         * Might we need to join these rels to complete the RHS?  We have to
         * use "overlap" tests since either rel might include a lower SJ that
         * has been proven to commute with this one.
         */
        if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
            bms_overlap(sjinfo->min_righthand, rel2->relids))
        {
            result = true;
            break;
        }

        /* Likewise for the LHS. */
        if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
            bms_overlap(sjinfo->min_lefthand, rel2->relids))
        {
            result = true;
            break;
        }
    }

    /*
     * We do not force the join to occur if either input rel can legally be
     * joined to anything else using joinclauses.  This essentially means that
     * clauseless bushy joins are put off as long as possible. The reason is
     * that when there is a join order restriction high up in the join tree
     * (that is, with many rels inside the LHS or RHS), we would otherwise
     * expend lots of effort considering very stupid join combinations within
     * its LHS or RHS.
     */
    if (result)
    {
        if (has_legal_joinclause(root, rel1) ||
            has_legal_joinclause(root, rel2))
            result = false;
    }

    return result;
}

have_relevant_eclass_joinclause()

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

Definition at line 2980 of file equivclass.c.

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

Referenced by have_relevant_joinclause().

{
    Bitmapset  *matching_ecs;
    int         i;

    /* Examine only eclasses mentioning both rel1 and rel2 */
    matching_ecs = get_common_eclass_indexes(root, rel1->relids,
                                             rel2->relids);

    i = -1;
    while ((i = bms_next_member(matching_ecs, i)) >= 0)
    {
        EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
                                                             i);

        /*
         * Sanity check that get_common_eclass_indexes gave only ECs
         * containing both rels.
         */
        Assert(bms_overlap(rel1->relids, ec->ec_relids));
        Assert(bms_overlap(rel2->relids, ec->ec_relids));

        /*
         * Won't generate joinclauses if single-member (this test covers the
         * volatile case too)
         */
        if (list_length(ec->ec_members) <= 1)
            continue;

        /*
         * We do not need to examine the individual members of the EC, because
         * all that we care about is whether each rel overlaps the relids of
         * at least one member, and get_common_eclass_indexes() and the single
         * member check above are sufficient to prove that.  (As with
         * have_relevant_joinclause(), it is not necessary that the EC be able
         * to form a joinclause relating exactly the two given rels, only that
         * it be able to form a joinclause mentioning both, and this will
         * surely be true if both of them overlap ec_relids.)
         *
         * Note we don't test ec_broken; if we did, we'd need a separate code
         * path to look through ec_sources.  Checking the membership anyway is
         * OK as a possibly-overoptimistic heuristic.
         *
         * We don't test ec_has_const either, even though a const eclass won't
         * generate real join clauses.  This is because if we had "WHERE a.x =
         * b.y and a.x = 42", it is worth considering a join between a and b,
         * since the join result is likely to be small even though it'll end
         * up being an unqualified nestloop.
         */

        return true;
    }

    return false;
}

indexcol_is_bool_constant_for_query()

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

Definition at line 3682 of file indxpath.c.

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

Referenced by build_index_pathkeys().

{
    ListCell   *lc;

    /* If the index isn't boolean, we can't possibly get a match */
    if (!IsBooleanOpfamily(index->opfamily[indexcol]))
        return false;

    /* Check each restriction clause for the index's rel */
    foreach(lc, index->rel->baserestrictinfo)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);

        /*
         * As in match_clause_to_indexcol, never match pseudoconstants to
         * indexes.  (It might be semantically okay to do so here, but the
         * odds of getting a match are negligible, so don't waste the cycles.)
         */
        if (rinfo->pseudoconstant)
            continue;

        /* See if we can match the clause's expression to the index column */
        if (match_boolean_index_clause(root, rinfo, indexcol, index))
            return true;
    }

    return false;
}

initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses	(	PlannerInfo *	root,
		RestrictInfo *	restrictinfo
	)

Definition at line 1179 of file pathkeys.c.

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

Referenced by distribute_qual_to_rels().

{
    Expr       *clause = restrictinfo->clause;
    Oid         lefttype,
                righttype;

    /* Should be a mergeclause ... */
    Assert(restrictinfo->mergeopfamilies != NIL);
    /* ... with links not yet set */
    Assert(restrictinfo->left_ec == NULL);
    Assert(restrictinfo->right_ec == NULL);

    /* Need the declared input types of the operator */
    op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);

    /* Find or create a matching EquivalenceClass for each side */
    restrictinfo->left_ec =
        get_eclass_for_sort_expr(root,
                                 (Expr *) get_leftop(clause),
                                 restrictinfo->nullable_relids,
                                 restrictinfo->mergeopfamilies,
                                 lefttype,
                                 ((OpExpr *) clause)->inputcollid,
                                 0,
                                 NULL,
                                 true);
    restrictinfo->right_ec =
        get_eclass_for_sort_expr(root,
                                 (Expr *) get_rightop(clause),
                                 restrictinfo->nullable_relids,
                                 restrictinfo->mergeopfamilies,
                                 righttype,
                                 ((OpExpr *) clause)->inputcollid,
                                 0,
                                 NULL,
                                 true);
}

is_redundant_derived_clause()

bool is_redundant_derived_clause	(	RestrictInfo *	rinfo,
		List *	clauselist
	)

Definition at line 3149 of file equivclass.c.

References lfirst, and RestrictInfo::parent_ec.

Referenced by create_tidscan_plan().

{
    EquivalenceClass *parent_ec = rinfo->parent_ec;
    ListCell   *lc;

    /* Fail if it's not a potentially-redundant clause from some EC */
    if (parent_ec == NULL)
        return false;

    foreach(lc, clauselist)
    {
        RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);

        if (otherrinfo->parent_ec == parent_ec)
            return true;
    }

    return false;
}

is_redundant_with_indexclauses()

bool is_redundant_with_indexclauses	(	RestrictInfo *	rinfo,
		List *	indexclauses
	)

Definition at line 3176 of file equivclass.c.

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

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

{
    EquivalenceClass *parent_ec = rinfo->parent_ec;
    ListCell   *lc;

    foreach(lc, indexclauses)
    {
        IndexClause *iclause = lfirst_node(IndexClause, lc);
        RestrictInfo *otherrinfo = iclause->rinfo;

        /* If indexclause is lossy, it won't enforce the condition exactly */
        if (iclause->lossy)
            continue;

        /* Match if it's same clause (pointer equality should be enough) */
        if (rinfo == otherrinfo)
            return true;
        /* Match if derived from same EC */
        if (parent_ec && otherrinfo->parent_ec == parent_ec)
            return true;

        /*
         * No need to look at the derived clauses in iclause->indexquals; they
         * couldn't match if the parent clause didn't.
         */
    }

    return false;
}

join_search_one_level()

void join_search_one_level	(	PlannerInfo *	root,
		int	level
	)

Definition at line 71 of file joinrels.c.

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

Referenced by standard_join_search().

{
    List      **joinrels = root->join_rel_level;
    ListCell   *r;
    int         k;

    Assert(joinrels[level] == NIL);

    /* Set join_cur_level so that new joinrels are added to proper list */
    root->join_cur_level = level;

    /*
     * First, consider left-sided and right-sided plans, in which rels of
     * exactly level-1 member relations are joined against initial relations.
     * We prefer to join using join clauses, but if we find a rel of level-1
     * members that has no join clauses, we will generate Cartesian-product
     * joins against all initial rels not already contained in it.
     */
    foreach(r, joinrels[level - 1])
    {
        RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);

        if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
            has_join_restriction(root, old_rel))
        {
            /*
             * There are join clauses or join order restrictions relevant to
             * this rel, so consider joins between this rel and (only) those
             * initial rels it is linked to by a clause or restriction.
             *
             * At level 2 this condition is symmetric, so there is no need to
             * look at initial rels before this one in the list; we already
             * considered such joins when we were at the earlier rel.  (The
             * mirror-image joins are handled automatically by make_join_rel.)
             * In later passes (level > 2), we join rels of the previous level
             * to each initial rel they don't already include but have a join
             * clause or restriction with.
             */
            List       *other_rels_list;
            ListCell   *other_rels;

            if (level == 2)     /* consider remaining initial rels */
            {
                other_rels_list = joinrels[level - 1];
                other_rels = lnext(other_rels_list, r);
            }
            else                /* consider all initial rels */
            {
                other_rels_list = joinrels[1];
                other_rels = list_head(other_rels_list);
            }

            make_rels_by_clause_joins(root,
                                      old_rel,
                                      other_rels_list,
                                      other_rels);
        }
        else
        {
            /*
             * Oops, we have a relation that is not joined to any other
             * relation, either directly or by join-order restrictions.
             * Cartesian product time.
             *
             * We consider a cartesian product with each not-already-included
             * initial rel, whether it has other join clauses or not.  At
             * level 2, if there are two or more clauseless initial rels, we
             * will redundantly consider joining them in both directions; but
             * such cases aren't common enough to justify adding complexity to
             * avoid the duplicated effort.
             */
            make_rels_by_clauseless_joins(root,
                                          old_rel,
                                          joinrels[1]);
        }
    }

    /*
     * Now, consider "bushy plans" in which relations of k initial rels are
     * joined to relations of level-k initial rels, for 2 <= k <= level-2.
     *
     * We only consider bushy-plan joins for pairs of rels where there is a
     * suitable join clause (or join order restriction), in order to avoid
     * unreasonable growth of planning time.
     */
    for (k = 2;; k++)
    {
        int         other_level = level - k;

        /*
         * Since make_join_rel(x, y) handles both x,y and y,x cases, we only
         * need to go as far as the halfway point.
         */
        if (k > other_level)
            break;

        foreach(r, joinrels[k])
        {
            RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
            List       *other_rels_list;
            ListCell   *other_rels;
            ListCell   *r2;

            /*
             * We can ignore relations without join clauses here, unless they
             * participate in join-order restrictions --- then we might have
             * to force a bushy join plan.
             */
            if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
                !has_join_restriction(root, old_rel))
                continue;

            if (k == other_level)
            {
                /* only consider remaining rels */
                other_rels_list = joinrels[k];
                other_rels = lnext(other_rels_list, r);
            }
            else
            {
                other_rels_list = joinrels[other_level];
                other_rels = list_head(other_rels_list);
            }

            for_each_cell(r2, other_rels_list, other_rels)
            {
                RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);

                if (!bms_overlap(old_rel->relids, new_rel->relids))
                {
                    /*
                     * OK, we can build a rel of the right level from this
                     * pair of rels.  Do so if there is at least one relevant
                     * join clause or join order restriction.
                     */
                    if (have_relevant_joinclause(root, old_rel, new_rel) ||
                        have_join_order_restriction(root, old_rel, new_rel))
                    {
                        (void) make_join_rel(root, old_rel, new_rel);
                    }
                }
            }
        }
    }

    /*----------
     * Last-ditch effort: if we failed to find any usable joins so far, force
     * a set of cartesian-product joins to be generated.  This handles the
     * special case where all the available rels have join clauses but we
     * cannot use any of those clauses yet.  This can only happen when we are
     * considering a join sub-problem (a sub-joinlist) and all the rels in the
     * sub-problem have only join clauses with rels outside the sub-problem.
     * An example is
     *
     *      SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
     *      WHERE a.w = c.x and b.y = d.z;
     *
     * If the "a INNER JOIN b" sub-problem does not get flattened into the
     * upper level, we must be willing to make a cartesian join of a and b;
     * but the code above will not have done so, because it thought that both
     * a and b have joinclauses.  We consider only left-sided and right-sided
     * cartesian joins in this case (no bushy).
     *----------
     */
    if (joinrels[level] == NIL)
    {
        /*
         * This loop is just like the first one, except we always call
         * make_rels_by_clauseless_joins().
         */
        foreach(r, joinrels[level - 1])
        {
            RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);

            make_rels_by_clauseless_joins(root,
                                          old_rel,
                                          joinrels[1]);
        }

        /*----------
         * When special joins are involved, there may be no legal way
         * to make an N-way join for some values of N.  For example consider
         *
         * SELECT ... FROM t1 WHERE
         *   x IN (SELECT ... FROM t2,t3 WHERE ...) AND
         *   y IN (SELECT ... FROM t4,t5 WHERE ...)
         *
         * We will flatten this query to a 5-way join problem, but there are
         * no 4-way joins that join_is_legal() will consider legal.  We have
         * to accept failure at level 4 and go on to discover a workable
         * bushy plan at level 5.
         *
         * However, if there are no special joins and no lateral references
         * then join_is_legal() should never fail, and so the following sanity
         * check is useful.
         *----------
         */
        if (joinrels[level] == NIL &&
            root->join_info_list == NIL &&
            !root->hasLateralRTEs)
            elog(ERROR, "failed to build any %d-way joins", level);
    }
}

make_canonical_pathkey()

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

Definition at line 54 of file pathkeys.c.

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

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

{
    PathKey    *pk;
    ListCell   *lc;
    MemoryContext oldcontext;

    /* Can't make canonical pathkeys if the set of ECs might still change */
    if (!root->ec_merging_done)
        elog(ERROR, "too soon to build canonical pathkeys");

    /* The passed eclass might be non-canonical, so chase up to the top */
    while (eclass->ec_merged)
        eclass = eclass->ec_merged;

    foreach(lc, root->canon_pathkeys)
    {
        pk = (PathKey *) lfirst(lc);
        if (eclass == pk->pk_eclass &&
            opfamily == pk->pk_opfamily &&
            strategy == pk->pk_strategy &&
            nulls_first == pk->pk_nulls_first)
            return pk;
    }

    /*
     * Be sure canonical pathkeys are allocated in the main planning context.
     * Not an issue in normal planning, but it is for GEQO.
     */
    oldcontext = MemoryContextSwitchTo(root->planner_cxt);

    pk = makeNode(PathKey);
    pk->pk_eclass = eclass;
    pk->pk_opfamily = opfamily;