paths.h File Reference

#include "nodes/relation.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)
void	set_dummy_rel_pathlist (RelOptInfo *rel)
RelOptInfo *	standard_join_search (PlannerInfo *root, int levels_needed, List *initial_rels)
void	generate_gather_paths (PlannerInfo *root, RelOptInfo *rel)
int	compute_parallel_worker (RelOptInfo *rel, double heap_pages, double index_pages)
void	create_partial_bitmap_paths (PlannerInfo *root, RelOptInfo *rel, Path *bitmapqual)
void	create_index_paths (PlannerInfo *root, RelOptInfo *rel)
bool	relation_has_unique_index_for (PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist)
bool	indexcol_is_bool_constant_for_query (IndexOptInfo *index, int indexcol)
bool	match_index_to_operand (Node *operand, int indexcol, IndexOptInfo *index)
void	expand_indexqual_conditions (IndexOptInfo *index, List *indexclauses, List *indexclausecols, List **indexquals_p, List **indexqualcols_p)
void	check_index_predicates (PlannerInfo *root, RelOptInfo *rel)
Expr *	adjust_rowcompare_for_index (RowCompareExpr *clause, IndexOptInfo *index, int indexcol, List **indexcolnos, bool *var_on_left_p)
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)
bool	process_equivalence (PlannerInfo *root, RestrictInfo *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)
void	generate_base_implied_equalities (PlannerInfo *root)
List *	generate_join_implied_equalities (PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
List *	generate_join_implied_equalities_for_ecs (PlannerInfo *root, List *eclasses, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel)
bool	exprs_known_equal (PlannerInfo *root, Node *item1, Node *item2)
EquivalenceClass *	match_eclasses_to_foreign_key_col (PlannerInfo *root, ForeignKeyOptInfo *fkinfo, int colno)
void	add_child_rel_equivalences (PlannerInfo *root, AppendRelInfo *appinfo, RelOptInfo *parent_rel, RelOptInfo *child_rel)
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)
PathKeysComparison	compare_pathkeys (List *keys1, List *keys2)
bool	pathkeys_contained_in (List *keys1, List *keys2)
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_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_pathkeys (PlannerInfo *root, List *pathkeys, bool outer_keys, 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 *	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)

Variables
bool	enable_geqo
int	geqo_threshold
int	min_parallel_table_scan_size
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

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

Definition at line 119 of file paths.h.

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

Definition at line 45 of file paths.h.

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.

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

enum PathKeysComparison

Enumerator
PATHKEYS_EQUAL
PATHKEYS_BETTER1
PATHKEYS_BETTER2
PATHKEYS_DIFFERENT

Definition at line 175 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

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

Definition at line 2069 of file equivclass.c.

References add_eq_member(), adjust_appendrel_attrs(), bms_add_members(), bms_difference(), bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, lfirst, RelOptInfo::relids, RELOPT_BASEREL, and RelOptInfo::reloptkind.

Referenced by set_append_rel_size().

{
    ListCell   *lc1;

    foreach(lc1, root->eq_classes)
    {
        EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
        ListCell   *lc2;

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

        /*
         * No point in searching if parent rel not mentioned in eclass; but we
         * can't tell that for sure if parent rel is itself a child.
         */
        if (parent_rel->reloptkind == RELOPT_BASEREL &&
            !bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
            continue;

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

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

            /* Does it reference parent_rel? */
            if (bms_overlap(cur_em->em_relids, parent_rel->relids))
            {
                /* Yes, generate transformed child version */
                Expr       *child_expr;
                Relids      new_relids;
                Relids      new_nullable_relids;

                child_expr = (Expr *)
                    adjust_appendrel_attrs(root,
                                           (Node *) cur_em->em_expr,
                                           appinfo);

                /*
                 * 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,
                                            parent_rel->relids);
                new_relids = bms_add_members(new_relids, child_rel->relids);

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

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

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

Definition at line 107 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, NULL, JoinPathExtraData::param_source_rels, RelOptInfo::relids, JoinPathExtraData::restrictlist, select_mergejoin_clauses(), JoinPathExtraData::semifactors, set_join_pathlist_hook, JoinPathExtraData::sjinfo, and sort_inner_and_outer().

Referenced by populate_joinrel_with_paths().

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

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

    /*
     * See if the inner relation is provably unique for this outer rel.
     *
     * We have some special cases: for JOIN_SEMI and JOIN_ANTI, it doesn't
     * matter since the executor can make the equivalent optimization anyway;
     * we need not expend planner cycles on proofs.  For JOIN_UNIQUE_INNER, we
     * must be considering a semijoin whose inner side is not provably unique
     * (else reduce_unique_semijoins would've simplified it), so there's no
     * point in calling innerrel_is_unique.  However, if the LHS covers all of
     * the semijoin's min_lefthand, then it's appropriate to set inner_unique
     * because the path produced by create_unique_path will be unique relative
     * to the LHS.  (If we have an LHS that's only part of the min_lefthand,
     * that is *not* true.)  For JOIN_UNIQUE_OUTER, pass JOIN_INNER to avoid
     * letting that value escape this module.
     */
    switch (jointype)
    {
        case JOIN_SEMI:
        case JOIN_ANTI:
            extra.inner_unique = false; /* well, unproven */
            break;
        case JOIN_UNIQUE_INNER:
            extra.inner_unique = bms_is_subset(sjinfo->min_lefthand,
                                               outerrel->relids);
            break;
        case JOIN_UNIQUE_OUTER:
            extra.inner_unique = innerrel_is_unique(root,
                                                    outerrel->relids,
                                                    innerrel,
                                                    JOIN_INNER,
                                                    restrictlist,
                                                    false);
            break;
        default:
            extra.inner_unique = innerrel_is_unique(root,
                                                    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, 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(joinrel->relids, sjinfo2->min_righthand) &&
            !bms_overlap(joinrel->relids, 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(joinrel->relids, sjinfo2->min_lefthand) &&
            !bms_overlap(joinrel->relids, 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);
}

Expr* adjust_rowcompare_for_index	(	RowCompareExpr *	clause,
		IndexOptInfo *	index,
		int	indexcol,
		List **	indexcolnos,
		bool *	var_on_left_p
	)

Definition at line 3824 of file indxpath.c.

References Assert, bms_is_member(), BOOLOID, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, contain_volatile_functions(), copyObject, elog, ERROR, get_commutator(), get_op_opfamily_properties(), get_op_opfamily_strategy(), get_opfamily_member(), i, IndexOptInfo::indexcollations, IndexCollMatchesExprColl, RowCompareExpr::inputcollids, InvalidOid, lappend_int(), lappend_oid(), RowCompareExpr::largs, lfirst, lfirst_oid, linitial, linitial_oid, list_copy(), list_head(), list_length(), list_make1_int, list_make1_oid, list_truncate(), lnext, make_opclause(), makeNode, match_index_to_operand(), IndexOptInfo::ncolumns, NIL, NULL, OidIsValid, RowCompareExpr::opfamilies, IndexOptInfo::opfamily, RowCompareExpr::opnos, pull_varnos(), RowCompareExpr::rargs, RowCompareExpr::rctype, IndexOptInfo::rel, RelOptInfo::relid, ROWCOMPARE_GE, and ROWCOMPARE_LE.

Referenced by expand_indexqual_rowcompare(), and fix_indexqual_references().

{
    bool        var_on_left;
    int         op_strategy;
    Oid         op_lefttype;
    Oid         op_righttype;
    int         matching_cols;
    Oid         expr_op;
    List       *opfamilies;
    List       *lefttypes;
    List       *righttypes;
    List       *new_ops;
    ListCell   *largs_cell;
    ListCell   *rargs_cell;
    ListCell   *opnos_cell;
    ListCell   *collids_cell;

    /* We have to figure out (again) how the first col matches */
    var_on_left = match_index_to_operand((Node *) linitial(clause->largs),
                                         indexcol, index);
    Assert(var_on_left ||
           match_index_to_operand((Node *) linitial(clause->rargs),
                                  indexcol, index));
    *var_on_left_p = var_on_left;

    expr_op = linitial_oid(clause->opnos);
    if (!var_on_left)
        expr_op = get_commutator(expr_op);
    get_op_opfamily_properties(expr_op, index->opfamily[indexcol], false,
                               &op_strategy,
                               &op_lefttype,
                               &op_righttype);

    /* Initialize returned list of which index columns are used */
    *indexcolnos = list_make1_int(indexcol);

    /* Build lists of the opfamilies and operator datatypes in case needed */
    opfamilies = list_make1_oid(index->opfamily[indexcol]);
    lefttypes = list_make1_oid(op_lefttype);
    righttypes = list_make1_oid(op_righttype);

    /*
     * See how many of the remaining columns match some index column in the
     * same way.  As in match_clause_to_indexcol(), the "other" side of any
     * potential index condition is OK as long as it doesn't use Vars from the
     * indexed relation.
     */
    matching_cols = 1;
    largs_cell = lnext(list_head(clause->largs));
    rargs_cell = lnext(list_head(clause->rargs));
    opnos_cell = lnext(list_head(clause->opnos));
    collids_cell = lnext(list_head(clause->inputcollids));

    while (largs_cell != NULL)
    {
        Node       *varop;
        Node       *constop;
        int         i;

        expr_op = lfirst_oid(opnos_cell);
        if (var_on_left)
        {
            varop = (Node *) lfirst(largs_cell);
            constop = (Node *) lfirst(rargs_cell);
        }
        else
        {
            varop = (Node *) lfirst(rargs_cell);
            constop = (Node *) lfirst(largs_cell);
            /* indexkey is on right, so commute the operator */
            expr_op = get_commutator(expr_op);
            if (expr_op == InvalidOid)
                break;          /* operator is not usable */
        }
        if (bms_is_member(index->rel->relid, pull_varnos(constop)))
            break;              /* no good, Var on wrong side */
        if (contain_volatile_functions(constop))
            break;              /* no good, volatile comparison value */

        /*
         * The Var side can match any column of the index.
         */
        for (i = 0; i < index->ncolumns; i++)
        {
            if (match_index_to_operand(varop, i, index) &&
                get_op_opfamily_strategy(expr_op,
                                         index->opfamily[i]) == op_strategy &&
                IndexCollMatchesExprColl(index->indexcollations[i],
                                         lfirst_oid(collids_cell)))
                break;
        }
        if (i >= index->ncolumns)
            break;              /* no match found */

        /* Add column number to returned list */
        *indexcolnos = lappend_int(*indexcolnos, i);

        /* Add opfamily and datatypes to lists */
        get_op_opfamily_properties(expr_op, index->opfamily[i], false,
                                   &op_strategy,
                                   &op_lefttype,
                                   &op_righttype);
        opfamilies = lappend_oid(opfamilies, index->opfamily[i]);
        lefttypes = lappend_oid(lefttypes, op_lefttype);
        righttypes = lappend_oid(righttypes, op_righttype);

        /* This column matches, keep scanning */
        matching_cols++;
        largs_cell = lnext(largs_cell);
        rargs_cell = lnext(rargs_cell);
        opnos_cell = lnext(opnos_cell);
        collids_cell = lnext(collids_cell);
    }

    /* Return clause as-is if it's all usable as index quals */
    if (matching_cols == list_length(clause->opnos))
        return (Expr *) clause;

    /*
     * We have to generate a subset rowcompare (possibly just one OpExpr). The
     * painful part of this is changing < to <= or > to >=, so deal with that
     * first.
     */
    if (op_strategy == BTLessEqualStrategyNumber ||
        op_strategy == BTGreaterEqualStrategyNumber)
    {
        /* easy, just use the same operators */
        new_ops = list_truncate(list_copy(clause->opnos), matching_cols);
    }
    else
    {
        ListCell   *opfamilies_cell;
        ListCell   *lefttypes_cell;
        ListCell   *righttypes_cell;

        if (op_strategy == BTLessStrategyNumber)
            op_strategy = BTLessEqualStrategyNumber;
        else if (op_strategy == BTGreaterStrategyNumber)
            op_strategy = BTGreaterEqualStrategyNumber;
        else
            elog(ERROR, "unexpected strategy number %d", op_strategy);
        new_ops = NIL;
        lefttypes_cell = list_head(lefttypes);
        righttypes_cell = list_head(righttypes);
        foreach(opfamilies_cell, opfamilies)
        {
            Oid         opfam = lfirst_oid(opfamilies_cell);
            Oid         lefttype = lfirst_oid(lefttypes_cell);
            Oid         righttype = lfirst_oid(righttypes_cell);

            expr_op = get_opfamily_member(opfam, lefttype, righttype,
                                          op_strategy);
            if (!OidIsValid(expr_op))   /* should not happen */
                elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
                     op_strategy, lefttype, righttype, opfam);
            if (!var_on_left)
            {
                expr_op = get_commutator(expr_op);
                if (!OidIsValid(expr_op))   /* should not happen */
                    elog(ERROR, "could not find commutator of operator %d(%u,%u) of opfamily %u",
                         op_strategy, lefttype, righttype, opfam);
            }
            new_ops = lappend_oid(new_ops, expr_op);
            lefttypes_cell = lnext(lefttypes_cell);
            righttypes_cell = lnext(righttypes_cell);
        }
    }

    /* If we have more than one matching col, create a subset rowcompare */
    if (matching_cols > 1)
    {
        RowCompareExpr *rc = makeNode(RowCompareExpr);

        if (var_on_left)
            rc->rctype = (RowCompareType) op_strategy;
        else
            rc->rctype = (op_strategy == BTLessEqualStrategyNumber) ?
                ROWCOMPARE_GE : ROWCOMPARE_LE;
        rc->opnos = new_ops;
        rc->opfamilies = list_truncate(list_copy(clause->opfamilies),
                                       matching_cols);
        rc->inputcollids = list_truncate(list_copy(clause->inputcollids),
                                         matching_cols);
        rc->largs = list_truncate(copyObject(clause->largs),
                                  matching_cols);
        rc->rargs = list_truncate(copyObject(clause->rargs),
                                  matching_cols);
        return (Expr *) rc;
    }
    else
    {
        return make_opclause(linitial_oid(new_ops), BOOLOID, false,
                             copyObject(linitial(clause->largs)),
                             copyObject(linitial(clause->rargs)),
                             InvalidOid,
                             linitial_oid(clause->inputcollids));
    }
}

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

Definition at line 553 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;
}

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

Definition at line 460 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, NULL, 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;

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

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

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

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

        i++;
    }

    return retval;
}

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

Definition at line 822 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);
}

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

Definition at line 456 of file equivclass.c.

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

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

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

    /*
     * For a polymorphic-input-type opclass, just keep the same exposed type.
     */
    if (IsPolymorphicType(req_type))
        req_type = expr_type;

    /*
     * No work if the expression exposes the right type/collation already.
     */
    if (expr_type != req_type ||
        exprCollation((Node *) expr) != req_collation)
    {
        /*
         * Strip any existing RelabelType, then add a new one if needed. This
         * is to preserve the invariant of no redundant RelabelTypes.
         *
         * If we have to change the exposed type of the stripped expression,
         * set typmod to -1 (since the new type may not have the same typmod
         * interpretation).  If we only have to change collation, preserve the
         * exposed typmod.
         */
        while (expr && IsA(expr, RelabelType))
            expr = (Expr *) ((RelabelType *) expr)->arg;

        if (exprType((Node *) expr) != req_type)
            expr = (Expr *) makeRelabelType(expr,
                                            req_type,
                                            -1,
                                            req_collation,
                                            COERCE_IMPLICIT_CAST);
        else if (exprCollation((Node *) expr) != req_collation)
            expr = (Expr *) makeRelabelType(expr,
                                            req_type,
                                            exprTypmod((Node *) expr),
                                            req_collation,
                                            COERCE_IMPLICIT_CAST);
    }

    return expr;
}

void check_index_predicates	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 2774 of file indxpath.c.

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

Referenced by set_plain_rel_size(), and set_tablesample_rel_size().

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

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

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

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

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

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

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

        clauselist = lappend(clauselist, rinfo);
    }

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

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

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

    /*
     * Now try to prove each index predicate true, and compute the
     * indrestrictinfo lists for partial indexes.  Note that we compute the
     * indrestrictinfo list even for non-predOK indexes; this might seem
     * wasteful, but we may be able to use such indexes in OR clauses, cf
     * generate_bitmap_or_paths().
     */
    foreach(lc, rel->indexlist)
    {
        IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
        ListCell   *lcr;

        if (index->indpred == NIL)
            continue;           /* ignore non-partial indexes here */

        if (!index->predOK)     /* don't repeat work if already proven OK */
            index->predOK = predicate_implied_by(index->indpred, clauselist,
                                                 false);

        /* If rel is an update target, leave indrestrictinfo as set above */
        if (is_target_rel)
            continue;

        /* Else compute indrestrictinfo as the non-implied quals */
        index->indrestrictinfo = NIL;
        foreach(lcr, rel->baserestrictinfo)
        {
            RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);

            /* predicate_implied_by() assumes first arg is immutable */
            if (contain_mutable_functions((Node *) rinfo->clause) ||
                !predicate_implied_by(list_make1(rinfo->clause),
                                      index->indpred, false))
                index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
        }
    }
}

PathKeysComparison compare_pathkeys	(	List *	keys1,
		List *	keys2
	)

Definition at line 278 of file pathkeys.c.

References forboth, lfirst, NULL, 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;
}

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

Definition at line 3067 of file allpaths.c.

References Max, max_parallel_workers_per_gather, 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(), and create_plain_partial_paths().

{
    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 max_parallel_workers_per_gather workers.
     */
    parallel_workers = Min(parallel_workers, max_parallel_workers_per_gather);

    return parallel_workers;
}

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

Definition at line 607 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, get_eclass_for_sort_expr(), get_sortgroupref_tle(), i, lappend(), lfirst, linitial, list_length(), list_nth(), make_canonical_pathkey(), makeVarFromTargetEntry(), NIL, NULL, pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, RelOptInfo::relid, RelOptInfo::relids, and TargetEntry::resjunk.

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;

            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);
            /* resjunk items aren't visible to outer query */
            if (!tle->resjunk)
            {
                /* We can represent this sub_pathkey */
                EquivalenceMember *sub_member;
                Expr       *outer_expr;
                EquivalenceClass *outer_ec;

                Assert(list_length(sub_eclass->ec_members) == 1);
                sub_member = (EquivalenceMember *) linitial(sub_eclass->ec_members);
                outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid, tle);

                /*
                 * 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,
                                             outer_expr,
                                             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);
                    Expr       *tle_expr;
                    Expr       *outer_expr;
                    EquivalenceClass *outer_ec;
                    PathKey    *outer_pk;
                    int         score;

                    /* resjunk items aren't visible to outer query */
                    if (tle->resjunk)
                        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;

                    /*
                     * Build a representation of this targetlist entry as an
                     * outer Var.
                     */
                    outer_expr = (Expr *) makeVarFromTargetEntry(rel->relid,
                                                                 tle);

                    /* See if we have a matching EC for that */
                    outer_ec = get_eclass_for_sort_expr(root,
                                                        outer_expr,
                                                        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;
}

void create_index_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 232 of file indxpath.c.

References add_path(), Assert, RelOptInfo::baserestrictinfo, bms_equal_any(), bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), RelOptInfo::consider_parallel, create_bitmap_heap_path(), create_partial_bitmap_paths(), forboth, generate_bitmap_or_paths(), get_bitmap_tree_required_outer(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, IndexOptInfo::indpred, lappend(), RelOptInfo::lateral_relids, lfirst, list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, IndexOptInfo::ncolumns, NIL, IndexClauseSet::nonempty, NULL, 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->ncolumns <= 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(rel, index, &rclauseset);

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

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

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

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

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

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

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

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

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

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

        /*
         * path_outer holds the parameterization of each path in bitjoinpaths
         * (to save recalculating that several times), while all_path_outers
         * holds all distinct parameterization sets.
         */
        path_outer = all_path_outers = NIL;
        foreach(lc, bitjoinpaths)
        {
            Path       *path = (Path *) lfirst(lc);
            Relids      required_outer;

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

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

            /* Identify all the bitmap join paths needing no more than that */
            this_path_set = NIL;
            forboth(lcp, bitjoinpaths, lco, path_outer)
            {
                Path       *path = (Path *) lfirst(lcp);
                Relids      p_outers = (Relids) lfirst(lco);

                if (bms_is_subset(p_outers, max_outers))
                    this_path_set = lappend(this_path_set, path);
            }

            /*
             * Add in restriction bitmap paths, since they can be used
             * together with any join paths.
             */
            this_path_set = list_concat(this_path_set, bitindexpaths);

            /* Select best AND combination for this parameterization */
            bitmapqual = choose_bitmap_and(root, rel, this_path_set);

            /* And push that path into the mix */
            required_outer = get_bitmap_tree_required_outer(bitmapqual);
            loop_count = get_loop_count(root, rel->relid, required_outer);
            bpath = create_bitmap_heap_path(root, rel, bitmapqual,
                                            required_outer, loop_count, 0);
            add_path(rel, (Path *) bpath);
        }
    }
}

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

Definition at line 3035 of file allpaths.c.

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

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

    if (parallel_workers <= 0)
        return;

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

void create_tidscan_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 253 of file tidpath.c.

References add_path(), create_tidscan_path(), RelOptInfo::lateral_relids, and TidQualFromBaseRestrictinfo().

Referenced by set_plain_rel_pathlist().

{
    Relids      required_outer;
    List       *tidquals;

    /*
     * We don't support pushing join clauses into the quals of a tidscan, but
     * it could still have required parameterization due to LATERAL refs in
     * its tlist.
     */
    required_outer = rel->lateral_relids;

    tidquals = TidQualFromBaseRestrictinfo(rel);

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

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

Definition at line 2397 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;
}

void expand_indexqual_conditions	(	IndexOptInfo *	index,
		List *	indexclauses,
		List *	indexclausecols,
		List **	indexquals_p,
		List **	indexqualcols_p
	)

Definition at line 3526 of file indxpath.c.

References IndexOptInfo::amsearchnulls, Assert, RestrictInfo::clause, elog, ERROR, expand_boolean_index_clause(), expand_indexqual_opclause(), expand_indexqual_rowcompare(), forboth, IndexOptInfo::indexcollations, is_opclause, IsA, IsBooleanOpfamily, lappend(), lappend_int(), lfirst, lfirst_int, list_concat(), list_length(), make_simple_restrictinfo, NIL, nodeTag, and IndexOptInfo::opfamily.

Referenced by create_index_path().

{
    List       *indexquals = NIL;
    List       *indexqualcols = NIL;
    ListCell   *lcc,
               *lci;

    forboth(lcc, indexclauses, lci, indexclausecols)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
        int         indexcol = lfirst_int(lci);
        Expr       *clause = rinfo->clause;
        Oid         curFamily = index->opfamily[indexcol];
        Oid         curCollation = index->indexcollations[indexcol];

        /* First check for boolean cases */
        if (IsBooleanOpfamily(curFamily))
        {
            Expr       *boolqual;

            boolqual = expand_boolean_index_clause((Node *) clause,
                                                   indexcol,
                                                   index);
            if (boolqual)
            {
                indexquals = lappend(indexquals,
                                     make_simple_restrictinfo(boolqual));
                indexqualcols = lappend_int(indexqualcols, indexcol);
                continue;
            }
        }

        /*
         * Else it must be an opclause (usual case), ScalarArrayOp,
         * RowCompare, or NullTest
         */
        if (is_opclause(clause))
        {
            indexquals = list_concat(indexquals,
                                     expand_indexqual_opclause(rinfo,
                                                               curFamily,
                                                               curCollation));
            /* expand_indexqual_opclause can produce multiple clauses */
            while (list_length(indexqualcols) < list_length(indexquals))
                indexqualcols = lappend_int(indexqualcols, indexcol);
        }
        else if (IsA(clause, ScalarArrayOpExpr))
        {
            /* no extra work at this time */
            indexquals = lappend(indexquals, rinfo);
            indexqualcols = lappend_int(indexqualcols, indexcol);
        }
        else if (IsA(clause, RowCompareExpr))
        {
            indexquals = lappend(indexquals,
                                 expand_indexqual_rowcompare(rinfo,
                                                             index,
                                                             indexcol));
            indexqualcols = lappend_int(indexqualcols, indexcol);
        }
        else if (IsA(clause, NullTest))
        {
            Assert(index->amsearchnulls);
            indexquals = lappend(indexquals, rinfo);
            indexqualcols = lappend_int(indexqualcols, indexcol);
        }
        else
            elog(ERROR, "unsupported indexqual type: %d",
                 (int) nodeTag(clause));
    }

    *indexquals_p = indexquals;
    *indexqualcols_p = indexqualcols;
}

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

Definition at line 1944 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;
}

List* find_mergeclauses_for_pathkeys	(	PlannerInfo *	root,
		List *	pathkeys,
		bool	outer_keys,
		List *	restrictinfos
	)

Definition at line 1003 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 other
         * input path.  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 other 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 it happens only with
         * redundant query conditions, we don't bother to eliminate it.
         * make_inner_pathkeys_for_merge() has to delete duplicates when
         * it constructs the canonical pathkeys list, and we also have to
         * deal with the case in create_mergejoin_plan().
         *----------
         */
        foreach(j, restrictinfos)
        {
            RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
            EquivalenceClass *clause_ec;

            if (outer_keys)
                clause_ec = rinfo->outer_is_left ?
                    rinfo->left_ec : rinfo->right_ec;
            else
                clause_ec = rinfo->outer_is_left ?
                    rinfo->right_ec : rinfo->left_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;
}

void generate_base_implied_equalities

(

PlannerInfo *

root

)

Definition at line 762 of file equivclass.c.

References Assert, EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, PlannerInfo::eq_classes, generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), RelOptInfo::has_eclass_joins, has_relevant_eclass_joinclause(), lfirst, list_length(), NULL, PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.

Referenced by query_planner().

{
    ListCell   *lc;
    Index       rti;

    foreach(lc, root->eq_classes)
    {
        EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);

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

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

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

    /*
     * This is also a handy place to mark base rels (which should all exist by
     * now) with flags showing whether they have pending eclass joins.
     */
    for (rti = 1; rti < root->simple_rel_array_size; rti++)
    {
        RelOptInfo *brel = root->simple_rel_array[rti];

        if (brel == NULL)
            continue;

        brel->has_eclass_joins = has_relevant_eclass_joinclause(root, brel);
    }
}

void generate_gather_paths	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 2199 of file allpaths.c.

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

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

{
    Path       *cheapest_partial_path;
    Path       *simple_gather_path;
    ListCell   *lc;

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

    /*
     * 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);
    simple_gather_path = (Path *)
        create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
                           NULL, NULL);
    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;

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

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

Definition at line 2173 of file equivclass.c.

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

Referenced by match_eclass_clauses_to_index(), and postgresGetForeignPaths().

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

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

    foreach(lc1, root->eq_classes)
    {
        EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
        EquivalenceMember *cur_em;
        ListCell   *lc2;

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

        /*
         * No point in searching if rel not mentioned in eclass (but we can't
         * tell that for a child rel).
         */
        if (!is_child_rel &&
            !bms_is_subset(rel->relids, cur_ec->ec_relids))
            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;
}

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

Definition at line 1033 of file equivclass.c.

References PlannerInfo::eq_classes, and generate_join_implied_equalities_for_ecs().

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

{
    return generate_join_implied_equalities_for_ecs(root,
                                                    root->eq_classes,
                                                    join_relids,
                                                    outer_relids,
                                                    inner_rel);
}

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

Definition at line 1050 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, result, and RelOptInfo::top_parent_relids.

Referenced by generate_join_implied_equalities(), and 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;
}

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

Definition at line 388 of file pathkeys.c.

References bms_is_subset(), compare_fractional_path_costs(), lfirst, NULL, 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;
}

Path* get_cheapest_parallel_safe_total_inner

(

List *

paths

)

Definition at line 421 of file pathkeys.c.

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

Referenced by 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;
}

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

Definition at line 343 of file pathkeys.c.

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

Referenced by generate_mergeappend_paths(), generate_mergejoin_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;
}

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

References add_eq_member(), bms_equal(), bms_intersect(), 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, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, PlannerInfo::eq_classes, equal(), ERROR, expression_returns_set(), lappend(), lfirst, list_copy(), makeNode, MemoryContextSwitchTo(), NIL, NULL, PlannerInfo::planner_cxt, and pull_varnos().

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    MemoryContextSwitchTo(oldcontext);

    return newec;
}

bool has_relevant_eclass_joinclause	(	PlannerInfo *	root,
		RelOptInfo *	rel1
	)

Definition at line 2358 of file equivclass.c.

References bms_is_subset(), bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, lfirst, list_length(), and RelOptInfo::relids.

Referenced by build_join_rel(), and generate_base_implied_equalities().

{
    ListCell   *lc1;

    foreach(lc1, root->eq_classes)
    {
        EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);

        /*
         * 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_overlap(rel1->relids, ec->ec_relids) &&
            !bms_is_subset(ec->ec_relids, rel1->relids))
            return true;
    }

    return false;
}

bool has_useful_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 1558 of file pathkeys.c.

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

Referenced by 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 */
}

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

Definition at line 1152 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;
}

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

Definition at line 919 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, RelOptInfo::relids, and result.

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

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

Definition at line 2304 of file equivclass.c.

References bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, lfirst, list_length(), and RelOptInfo::relids.

Referenced by have_relevant_joinclause().

{
    ListCell   *lc1;

    foreach(lc1, root->eq_classes)
    {
        EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);

        /*
         * 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 a test on ec_relids is 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.
         */
        if (bms_overlap(rel1->relids, ec->ec_relids) &&
            bms_overlap(rel2->relids, ec->ec_relids))
            return true;
    }

    return false;
}

bool indexcol_is_bool_constant_for_query	(	IndexOptInfo *	index,
		int	indexcol
	)

Definition at line 3131 of file indxpath.c.

References RelOptInfo::baserestrictinfo, RestrictInfo::clause, IsBooleanOpfamily, 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((Node *) rinfo->clause, indexcol, index))
            return true;
    }

    return false;
}

void initialize_mergeclause_eclasses	(	PlannerInfo *	root,
		RestrictInfo *	restrictinfo
	)

Definition at line 919 of file pathkeys.c.

References Assert, RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), RestrictInfo::left_ec, RestrictInfo::mergeopfamilies, NIL, NULL, 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);
}

bool is_redundant_derived_clause	(	RestrictInfo *	rinfo,
		List *	clauselist
	)

Definition at line 2455 of file equivclass.c.

References lfirst, NULL, and RestrictInfo::parent_ec.

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

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

void join_search_one_level	(	PlannerInfo *	root,
		int	level
	)

Definition at line 54 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.
             */
            ListCell   *other_rels;

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

            make_rels_by_clause_joins(root,
                                      old_rel,
                                      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,
                                          list_head(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);
            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)
                other_rels = lnext(r);  /* only consider remaining rels */
            else
                other_rels = list_head(joinrels[other_level]);

            for_each_cell(r2, 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,
                                          list_head(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);
    }
}

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

Definition at line 51 of file pathkeys.c.

References PlannerInfo::canon_pathkeys, EquivalenceClass::ec_merged, eclass(), 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;

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

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

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

    pk = makeNode(PathKey);
    pk->pk_eclass = eclass;
    pk->pk_opfamily = opfamily;
    pk->pk_strategy = strategy;
    pk->pk_nulls_first = nulls_first;

    root->canon_pathkeys = lappend(root->canon_pathkeys, pk);

    MemoryContextSwitchTo(oldcontext);

    return pk;
}

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

Definition at line 1292 of file pathkeys.c.

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

{
    List       *pathkeys = NIL;
    EquivalenceClass *lastoeclass;
    PathKey    *opathkey;
    ListCell   *lc;
    ListCell   *lop;

    lastoeclass = NULL;
    opathkey = NULL;
    lop = list_head(outer_pathkeys);

    foreach(lc, mergeclauses)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
        EquivalenceClass *oeclass;
        EquivalenceClass *ieclass;
        PathKey    *pathkey;

        update_mergeclause_eclasses(root, rinfo);

        if (rinfo->outer_is_left)
        {
            oeclass = rinfo->left_ec;
            ieclass = rinfo->right_ec;
        }
        else
        {
            oeclass = rinfo->right_ec;
            ieclass = rinfo->left_ec;
        }

        /* outer eclass should match current or next pathkeys */
        /* we check this carefully for debugging reasons */
        if (oeclass != lastoeclass)
        {
            if (!lop)
                elog(ERROR, "too few pathkeys for mergeclauses");
            opathkey = (PathKey *) lfirst(lop);
            lop = lnext(lop);
            lastoeclass = opathkey->pk_eclass;
            if (oeclass != lastoeclass)
                elog(ERROR, "outer pathkeys do not match mergeclause");
        }

        /*
         * Often, we'll have same EC on both sides, in which case the outer
         * pathkey is also canonical for the inner side, and we can skip a
         * useless search.
         */
        if (ieclass == oeclass)
            pathkey = opathkey;
        else
            pathkey = make_canonical_pathkey(root,
                                             ieclass,
                                             opathkey->pk_opfamily,
                                             opathkey->pk_strategy,
                                             opathkey->pk_nulls_first);

        /*
         * Don't generate redundant pathkeys (can happen if multiple
         * mergeclauses refer to same EC).
         */
        if (!pathkey_is_redundant(pathkey, pathkeys))
            pathkeys = lappend(pathkeys, pathkey);
    }

    return pathkeys;
}

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

Definition at line 657 of file joinrels.c.

References Assert, bms_free(), bms_overlap(), bms_union(), build_join_rel(), SpecialJoinInfo::delay_upper_joins, is_dummy_rel(), JOIN_INNER, join_is_legal(), SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, NULL, populate_joinrel_with_paths(), RelOptInfo::relids, SpecialJoinInfo::semi_can_btree, SpecialJoinInfo::semi_can_hash, SpecialJoinInfo::semi_operators, SpecialJoinInfo::semi_rhs_exprs, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, T_SpecialJoinInfo, and SpecialJoinInfo::type.

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

{
    Relids      joinrelids;
    SpecialJoinInfo *sjinfo;
    bool        reversed;
    SpecialJoinInfo sjinfo_data;
    RelOptInfo *joinrel;
    List       *restrictlist;

    /* We should never try to join two overlapping sets of rels. */
    Assert(!bms_overlap(rel1->relids, rel2->relids));

    /* Construct Relids set that identifies the joinrel. */
    joinrelids = bms_union(rel1->relids, rel2->relids);

    /* Check validity and determine join type. */
    if (!join_is_legal(root, rel1, rel2, joinrelids,
                       &sjinfo, &reversed))
    {
        /* invalid join path */
        bms_free(joinrelids);
        return NULL;
    }

    /* Swap rels if needed to match the join info. */
    if (reversed)
    {
        RelOptInfo *trel = rel1;

        rel1 = rel2;
        rel2 = trel;
    }

    /*
     * If it's a plain inner join, then we won't have found anything in
     * join_info_list.  Make up a SpecialJoinInfo so that selectivity
     * estimation functions will know what's being joined.
     */
    if (sjinfo == NULL)
    {
        sjinfo = &sjinfo_data;
        sjinfo->type = T_SpecialJoinInfo;
        sjinfo->min_lefthand = rel1->relids;
        sjinfo->min_righthand = rel2->relids;
        sjinfo->syn_lefthand = rel1->relids;
        sjinfo->syn_righthand = rel2->relids;
        sjinfo->jointype = JOIN_INNER;
        /* we don't bother trying to make the remaining fields valid */
        sjinfo->lhs_strict = false;
        sjinfo->delay_upper_joins = false;
        sjinfo->semi_can_btree = false;
        sjinfo->semi_can_hash = false;
        sjinfo->semi_operators = NIL;
        sjinfo->semi_rhs_exprs = NIL;
    }

    /*
     * Find or build the join RelOptInfo, and compute the restrictlist that
     * goes with this particular joining.
     */
    joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
                             &restrictlist);

    /*
     * If we've already proven this join is empty, we needn't consider any
     * more paths for it.
     */
    if (is_dummy_rel(joinrel))
    {
        bms_free(joinrelids);
        return joinrel;
    }

    /* Add paths to the join relation. */
    populate_joinrel_with_paths(root, rel1, rel2, joinrel, sjinfo,
                                restrictlist);

    bms_free(joinrelids);

    return joinrel;
}

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

Definition at line 145 of file allpaths.c.

References PlannerInfo::all_baserels, Assert, bms_add_member(), bms_equal(), make_rel_from_joinlist(), NULL, RelOptInfo::relid, RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, set_base_rel_consider_startup(), set_base_rel_pathlists(), set_base_rel_sizes(), PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.

Referenced by query_planner().

{
    RelOptInfo *rel;
    Index       rti;

    /*
     * Construct the all_baserels Relids set.
     */
    root->all_baserels = NULL;
    for (rti = 1; rti < root->simple_rel_array_size; rti++)
    {
        RelOptInfo *brel = root->simple_rel_array[rti];

        /* there may be empty slots corresponding to non-baserel RTEs */
        if (brel == NULL)
            continue;

        Assert(brel->relid == rti); /* sanity check on array */

        /* ignore RTEs that are "other rels" */
        if (brel->reloptkind != RELOPT_BASEREL)
            continue;

        root->all_baserels = bms_add_member(root->all_baserels, brel->relid);
    }

    /* Mark base rels as to whether we care about fast-start plans */
    set_base_rel_consider_startup(root);

    /*
     * Compute size estimates and consider_parallel flags for each base rel,
     * then generate access paths.
     */
    set_base_rel_sizes(root);
    set_base_rel_pathlists(root);

    /*
     * Generate access paths for the entire join tree.
     */
    rel = make_rel_from_joinlist(root, joinlist);

    /*
     * The result should join all and only the query's base rels.
     */
    Assert(bms_equal(rel->relids, root->all_baserels));

    return rel;
}

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

Definition at line 865 of file pathkeys.c.

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

Referenced by generate_nonunion_path(), get_column_info_for_window(), grouping_planner(), make_pathkeys_for_window(), make_union_unique(), minmax_qp_callback(), and standard_qp_callback().

{
    List       *pathkeys = NIL;
    ListCell   *l;

    foreach(l, sortclauses)
    {
        SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
        Expr       *sortkey;
        PathKey    *pathkey;

        sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
        Assert(OidIsValid(sortcl->sortop));
        pathkey = make_pathkey_from_sortop(root,
                                           sortkey,
                                           root->nullable_baserels,
                                           sortcl->sortop,
                                           sortcl->nulls_first,
                                           sortcl->tleSortGroupRef,
                                           true);

        /* Canonical form eliminates redundant ordering keys */
        if (!pathkey_is_redundant(pathkey, pathkeys))
            pathkeys = lappend(pathkeys, pathkey);
    }
    return pathkeys;
}

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

Definition at line 1991 of file equivclass.c.

References ForeignKeyOptInfo::con_relid, ForeignKeyOptInfo::confkey, ForeignKeyOptInfo::conkey, ForeignKeyOptInfo::conpfeqop, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, equal(), get_mergejoin_opfamilies(), IsA, lfirst, NIL, NULL, ForeignKeyOptInfo::ref_relid, RangeQueryClause::var, Var::varattno, and Var::varno.

Referenced by match_foreign_keys_to_quals().

{
    Index       var1varno = fkinfo->con_relid;
    AttrNumber  var1attno = fkinfo->conkey[colno];
    Index       var2varno = fkinfo->ref_relid;
    AttrNumber  var2attno = fkinfo->confkey[colno];
    Oid         eqop = fkinfo->conpfeqop[colno];
    List       *opfamilies = NIL;   /* compute only if needed */
    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;
        /* Note: it seems okay to match to "broken" eclasses here */

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

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

            /* EM must be a Var, possibly with RelabelType */
            var = (Var *) em->em_expr;
            while (var && IsA(var, RelabelType))
                var = (Var *) ((RelabelType *) var)->arg;
            if (!(var && IsA(var, Var)))
                continue;

            /* Match? */
            if (var->varno == var1varno && var->varattno == var1attno)
                item1member = true;
            else if (var->varno == var2varno && var->varattno == var2attno)
                item2member = true;

            /* Have we found both PK and FK column in this EC? */
            if (item1member && item2member)
            {
                /*
                 * Succeed if eqop matches EC's opfamilies.  We could test
                 * this before scanning the members, but it's probably cheaper
                 * to test for member matches first.
                 */
                if (opfamilies == NIL)  /* compute if we didn't already */
                    opfamilies = get_mergejoin_opfamilies(eqop);
                if (equal(opfamilies, ec->ec_opfamilies))
                    return ec;
                /* Otherwise, done with this EC, move on to the next */
                break;
            }
        }
    }
    return NULL;
}

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

Definition at line 3180 of file indxpath.c.

References arg, elog, equal(), ERROR, i, IndexOptInfo::indexkeys, IndexOptInfo::indexprs, IsA, lfirst, list_head(), lnext, NULL, IndexOptInfo::rel, and RelOptInfo::relid.

Referenced by adjust_rowcompare_for_index(), deconstruct_indexquals(), ec_member_matches_indexcol(), expand_boolean_index_clause(), get_actual_variable_range(), match_boolean_index_clause(), match_clause_to_indexcol(), match_clause_to_ordering_op(), match_rowcompare_to_indexcol(), and relation_has_unique_index_for().

{
    int         indkey;

    /*
     * Ignore any RelabelType node above the operand.   This is needed to be
     * able to apply indexscanning in binary-compatible-operator cases. Note:
     * we can assume there is at most one RelabelType node;
     * eval_const_expressions() will have simplified if more than one.
     */
    if (operand && IsA(operand, RelabelType))
        operand = (Node *) ((RelabelType *) operand)->arg;

    indkey = index->indexkeys[indexcol];
    if (indkey != 0)
    {
        /*
         * Simple index column; operand must be a matching Var.
         */
        if (operand && IsA(operand, Var) &&
            index->rel->relid == ((Var *) operand)->varno &&
            indkey == ((Var *) operand)->varattno)
            return true;
    }
    else
    {
        /*
         * Index expression; find the correct expression.  (This search could
         * be avoided, at the cost of complicating all the callers of this
         * routine; doesn't seem worth it.)
         */
        ListCell   *indexpr_item;
        int         i;
        Node       *indexkey;

        indexpr_item = list_head(index->indexprs);
        for (i = 0; i < indexcol; i++)
        {
            if (index->indexkeys[i] == 0)
            {
                if (indexpr_item == NULL)
                    elog(ERROR, "wrong number of index expressions");
                indexpr_item = lnext(indexpr_item);
            }
        }
        if (indexpr_item == NULL)
            elog(ERROR, "wrong number of index expressions");
        indexkey = (Node *) lfirst(indexpr_item);

        /*
         * Does it match the operand?  Again, strip any relabeling.
         */
        if (indexkey && IsA(indexkey, RelabelType))
            indexkey = (Node *) ((RelabelType *) indexkey)->arg;

        if (equal(indexkey, operand))
            return true;
    }

    return false;
}

bool pathkeys_contained_in	(	List *	keys1,
		List *	keys2
	)

Definition at line 317 of file pathkeys.c.

References compare_pathkeys(), PATHKEYS_BETTER2, and PATHKEYS_EQUAL.

Referenced by consider_groupingsets_paths(), create_distinct_paths(), create_gather_merge_path(), create_gather_merge_plan(), create_grouping_paths(), create_merge_append_path(), create_merge_append_plan(), create_one_window_path(), create_ordered_paths(), create_window_paths(), generate_mergejoin_paths(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_path_for_pathkeys(), pathkeys_useful_for_ordering(), try_mergejoin_path(), and try_partial_mergejoin_path().

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

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

Definition at line 107 of file equivclass.c.

References add_eq_member(), Assert, bms_intersect(), bms_is_empty(), bms_join(), PlannerInfo::canon_pathkeys, canonicalize_ec_expression(), RestrictInfo::clause, contain_nonstrict_functions(), 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, EquivalenceClass::ec_min_security, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, PlannerInfo::eq_classes, equal(), ERROR, exprType(), get_leftop(), get_rightop(), is_opclause, lappend(), RestrictInfo::leakproof, RestrictInfo::left_ec, RestrictInfo::left_em, RestrictInfo::left_relids, lfirst, list_concat(), list_delete_ptr(), list_make1, makeNode, Max, RestrictInfo::mergeopfamilies, Min, NIL, NULL, RestrictInfo::nullable_relids, op_input_types(), RestrictInfo::right_ec, RestrictInfo::right_em, RestrictInfo::right_relids, and RestrictInfo::security_level.

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

{
    Expr       *clause = restrictinfo->clause;
    Oid         opno,
                collation,
                item1_type,
                item2_type;
    Expr       *item1;
    Expr       *item2;
    Relids      item1_relids,
                item2_relids,
                item1_nullable_relids,
                item2_nullable_relids;
    List       *opfamilies;
    EquivalenceClass *ec1,
               *ec2;
    EquivalenceMember *em1,
               *em2;
    ListCell   *lc1;

    /* Should not already be marked as having generated an eclass */
    Assert(restrictinfo->left_ec == NULL);
    Assert(restrictinfo->right_ec == NULL);

    /* Reject if it is potentially postponable by security considerations */
    if (restrictinfo->security_level > 0 && !restrictinfo->leakproof)
        return false;

    /* Extract info from given clause */
    Assert(is_opclause(clause));
    opno = ((OpExpr *) clause)->opno;
    collation = ((OpExpr *) clause)->inputcollid;
    item1 = (Expr *) get_leftop(clause);
    item2 = (Expr *) get_rightop(clause);
    item1_relids = restrictinfo->left_relids;
    item2_relids = restrictinfo->right_relids;

    /*
     * Ensure both input expressions expose the desired collation (their types
     * should be OK already); see comments for canonicalize_ec_expression.
     */
    item1 = canonicalize_ec_expression(item1,
                                       exprType((Node *) item1),
                                       collation);
    item2 = canonicalize_ec_expression(item2,
                                       exprType((Node *) item2),
                                       collation);

    /*
     * Reject clauses of the form X=X.  These are not as redundant as they
     * might seem at first glance: assuming the operator is strict, this is
     * really an expensive way to write X IS NOT NULL.  So we must not risk
     * just losing the clause, which would be possible if there is already a
     * single-element EquivalenceClass containing X.  The case is not common
     * enough to be worth contorting the EC machinery for, so just reject the
     * clause and let it be processed as a normal restriction clause.
     */
    if (equal(item1, item2))
        return false;           /* X=X is not a useful equivalence */

    /*
     * If below outer join, check for strictness, else reject.
     */
    if (below_outer_join)
    {
        if (!bms_is_empty(item1_relids) &&
            contain_nonstrict_functions((Node *) item1))
            return false;       /* LHS is non-strict but not constant */
        if (!bms_is_empty(item2_relids) &&
            contain_nonstrict_functions((Node *) item2))
            return false;       /* RHS is non-strict but not constant */
    }

    /* Calculate nullable-relid sets for each side of the clause */
    item1_nullable_relids = bms_intersect(item1_relids,
                                          restrictinfo->nullable_relids);
    item2_nullable_relids = bms_intersect(item2_relids,
                                          restrictinfo->nullable_relids);

    /*
     * We use the declared input types of the operator, not exprType() of the
     * inputs, as the nominal datatypes for opfamily lookup.  This presumes
     * that btree operators are always registered with amoplefttype and
     * amoprighttype equal to their declared input types.  We will need this
     * info anyway to build EquivalenceMember nodes, and by extracting it now
     * we can use type comparisons to short-circuit some equal() tests.
     */
    op_input_types(opno, &item1_type, &item2_type);

    opfamilies = restrictinfo->mergeopfamilies;

    /*
     * Sweep through the existing EquivalenceClasses looking for matches to
     * item1 and item2.  These are the possible outcomes:
     *
     * 1. We find both in the same EC.  The equivalence is already known, so
     * there's nothing to do.
     *
     * 2. We find both in different ECs.  Merge the two ECs together.
     *
     * 3. We find just one.  Add the other to its EC.
     *
     * 4. We find neither.  Make a new, two-entry EC.
     *
     * Note: since all ECs are built through this process or the similar
     * search in get_eclass_for_sort_expr(), it's impossible that we'd match
     * an item in more than one existing nonvolatile EC.  So it's okay to stop
     * at the first match.
     */
    ec1 = ec2 = NULL;
    em1 = em2 = NULL;
    foreach(lc1, root->eq_classes)
    {
        EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
        ListCell   *lc2;

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

        /*
         * The collation has to match; check this first since it's cheaper
         * than the opfamily comparison.
         */
        if (collation != cur_ec->ec_collation)
            continue;

        /*
         * A "match" requires matching sets of btree opfamilies.  Use of
         * equal() for this test has implications discussed in the comments
         * for get_mergejoin_opfamilies().
         */
        if (!equal(opfamilies, cur_ec->ec_opfamilies))
            continue;

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

            Assert(!cur_em->em_is_child);   /* no children yet */

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

            if (!ec1 &&
                item1_type == cur_em->em_datatype &&
                equal(item1, cur_em->em_expr))
            {
                ec1 = cur_ec;
                em1 = cur_em;
                if (ec2)
                    break;
            }

            if (!ec2 &&
                item2_type == cur_em->em_datatype &&
                equal(item2, cur_em->em_expr))
            {
                ec2 = cur_ec;
                em2 = cur_em;
                if (ec1)
                    break;
            }
        }

        if (ec1 && ec2)
            break;
    }

    /* Sweep finished, what did we find? */

    if (ec1 && ec2)
    {
        /* If case 1, nothing to do, except add to sources */
        if (ec1 == ec2)
        {
            ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
            ec1->ec_below_outer_join |= below_outer_join;
            ec1->ec_min_security = Min(ec1->ec_min_security,
                                       restrictinfo->security_level);
            ec1->ec_max_security = Max(ec1->ec_max_security,
                                       restrictinfo->security_level);
            /* mark the RI as associated with this eclass */
            restrictinfo->left_ec = ec1;
            restrictinfo->right_ec = ec1;
            /* mark the RI as usable with this pair of EMs */
            restrictinfo->left_em = em1;
            restrictinfo->right_em = em2;
            return true;
        }

        /*
         * Case 2: need to merge ec1 and ec2.  This should never happen after
         * we've built any canonical pathkeys; if it did, those pathkeys might
         * be rendered non-canonical by the merge.
         */
        if (root->canon_pathkeys != NIL)
            elog(ERROR, "too late to merge equivalence classes");

        /*
         * We add ec2's items to ec1, then set ec2's ec_merged link to point
         * to ec1 and remove ec2 from the eq_classes list.  We cannot simply
         * delete ec2 because that could leave dangling pointers in existing
         * PathKeys.  We leave it behind with a link so that the merged EC can
         * be found.
         */
        ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
        ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
        ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
        ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
        ec1->ec_has_const |= ec2->ec_has_const;
        /* can't need to set has_volatile */
        ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
        ec1->ec_min_security = Min(ec1->ec_min_security,
                                   ec2->ec_min_security);
        ec1->ec_max_security = Max(ec1->ec_max_security,
                                   ec2->ec_max_security);
        ec2->ec_merged = ec1;
        root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
        /* just to avoid debugging confusion w/ dangling pointers: */
        ec2->ec_members = NIL;
        ec2->ec_sources = NIL;
        ec2->ec_derives = NIL;
        ec2->ec_relids = NULL;
        ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
        ec1->ec_below_outer_join |= below_outer_join;
        ec1->ec_min_security = Min(ec1->ec_min_security,
                                   restrictinfo->security_level);
        ec1->ec_max_security = Max(ec1->ec_max_security,
                                   restrictinfo->security_level);
        /* mark the RI as associated with this eclass */
        restrictinfo->left_ec = ec1;
        restrictinfo->right_ec = ec1;
        /* mark the RI as usable with this pair of EMs */
        restrictinfo->left_em = em1;
        restrictinfo->right_em = em2;
    }
    else if (ec1)
    {
        /* Case 3: add item2 to ec1 */
        em2 = add_eq_member(ec1, item2, item2_relids, item2_nullable_relids,
                            false, item2_type);
        ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
        ec1->ec_below_outer_join |= below_outer_join;
        ec1->ec_min_security = Min(ec1->ec_min_security,
                                   restrictinfo->security_level);
        ec1->ec_max_security = Max(ec1->ec_max_security,
                                   restrictinfo->security_level);
        /* mark the RI as associated with this eclass */
        restrictinfo->left_ec = ec1;
        restrictinfo->right_ec = ec1;
        /* mark the RI as usable with this pair of EMs */
        restrictinfo->left_em = em1;
        restrictinfo->right_em = em2;
    }
    else if (ec2)
    {
        /* Case 3: add item1 to ec2 */
        em1 = add_eq_member(ec2, item1, item1_relids, item1_nullable_relids,
                            false, item1_type);
        ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
        ec2->ec_below_outer_join |= below_outer_join;
        ec2->ec_min_security = Min(ec2->ec_min_security,
                                   restrictinfo->security_level);
        ec2->ec_max_security = Max(ec2->ec_max_security,
                                   restrictinfo->security_level);
        /* mark the RI as associated with this eclass */
        restrictinfo->left_ec = ec2;
        restrictinfo->right_ec = ec2;
        /* mark the RI as usable with this pair of EMs */
        restrictinfo->left_em = em1;
        restrictinfo->right_em = em2;
    }
    else
    {
        /* Case 4: make a new, two-entry EC */
        EquivalenceClass *ec = makeNode(EquivalenceClass);

        ec->ec_opfamilies = opfamilies;
        ec->ec_collation = collation;
        ec->ec_members = NIL;
        ec->ec_sources = list_make1(restrictinfo);
        ec->ec_derives = NIL;
        ec->ec_relids = NULL;
        ec->ec_has_const = false;
        ec->ec_has_volatile = false;
        ec->ec_below_outer_join = below_outer_join;
        ec->ec_broken = false;
        ec->ec_sortref = 0;
        ec->ec_min_security = restrictinfo->security_level;
        ec->ec_max_security = restrictinfo->security_level;
        ec->ec_merged = NULL;
        em1 = add_eq_member(ec, item1, item1_relids, item1_nullable_relids,
                            false, item1_type);
        em2 = add_eq_member(ec, item2, item2_relids, item2_nullable_relids,
                            false, item2_type);

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

        /* mark the RI as associated with this eclass */
        restrictinfo->left_ec = ec;
        restrictinfo->right_ec = ec;
        /* mark the RI as usable with this pair of EMs */
        restrictinfo->left_em = em1;
        restrictinfo->right_em = em2;
    }

    return true;
}

void reconsider_outer_join_clauses

(

PlannerInfo *

root

)

Definition at line 1533 of file equivclass.c.

References distribute_restrictinfo_to_rels(), PlannerInfo::full_join_clauses, PlannerInfo::left_join_clauses, lfirst, list_delete_cell(), list_head(), lnext, next, RestrictInfo::norm_selec, NULL, RestrictInfo::outer_selec, reconsider_full_join_clause(), reconsider_outer_join_clause(), and PlannerInfo::right_join_clauses.

Referenced by query_planner().

{
    bool        found;
    ListCell   *cell;
    ListCell   *prev;
    ListCell   *next;

    /* Outer loop repeats until we find no more deductions */
    do
    {
        found = false;

        /* Process the LEFT JOIN clauses */
        prev = NULL;
        for (cell = list_head(root->left_join_clauses); cell; cell = next)
        {
            RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);

            next = lnext(cell);
            if (reconsider_outer_join_clause(root, rinfo, true))
            {
                found = true;
                /* remove it from the list */
                root->left_join_clauses =
                    list_delete_cell(root->left_join_clauses, cell, prev);
                /* we throw it back anyway (see notes above) */
                /* but the thrown-back clause has no extra selectivity */
                rinfo->norm_selec = 2.0;
                rinfo->outer_selec = 1.0;
                distribute_restrictinfo_to_rels(root, rinfo);
            }
            else
                prev = cell;
        }

        /* Process the RIGHT JOIN clauses */
        prev = NULL;
        for (cell = list_head(root->right_join_clauses); cell; cell = next)
        {
            RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);

            next = lnext(cell);
            if (reconsider_outer_join_clause(root, rinfo, false))
            {
                found = true;
                /* remove it from the list */
                root->right_join_clauses =
                    list_delete_cell(root->right_join_clauses, cell, prev);
                /* we throw it back anyway (see notes above) */
                /* but the thrown-back clause has no extra selectivity */
                rinfo->norm_selec = 2.0;
                rinfo->outer_selec = 1.0;
                distribute_restrictinfo_to_rels(root, rinfo);
            }
            else
                prev = cell;
        }

        /* Process the FULL JOIN clauses */
        prev = NULL;
        for (cell = list_head(root->full_join_clauses); cell; cell = next)
        {
            RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);

            next = lnext(cell);
            if (reconsider_full_join_clause(root, rinfo))
            {
                found =