pathkeys.c File Reference

#include "postgres.h"
#include "access/stratnum.h"
#include "catalog/pg_opfamily.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "partitioning/partbounds.h"
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"

Include dependency graph for pathkeys.c:

Go to the source code of this file.

Functions
static bool	pathkey_is_redundant (PathKey *new_pathkey, List *pathkeys)
static bool	matches_boolean_partition_clause (RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol)
static Var *	find_var_for_subquery_tle (RelOptInfo *rel, TargetEntry *tle)
static bool	right_merge_direction (PlannerInfo *root, PathKey *pathkey)
PathKey *	make_canonical_pathkey (PlannerInfo *root, EquivalenceClass *eclass, Oid opfamily, int strategy, bool nulls_first)
List *	append_pathkeys (List *target, List *source)
static PathKey *	make_pathkey_from_sortinfo (PlannerInfo *root, Expr *expr, Oid opfamily, Oid opcintype, Oid collation, bool reverse_sort, bool nulls_first, Index sortref, Relids rel, bool create_it)
static PathKey *	make_pathkey_from_sortop (PlannerInfo *root, Expr *expr, Oid ordering_op, bool reverse_sort, bool nulls_first, Index sortref, bool create_it)
PathKeysComparison	compare_pathkeys (List *keys1, List *keys2)
bool	pathkeys_contained_in (List *keys1, List *keys2)
static int	group_keys_reorder_by_pathkeys (List *pathkeys, List **group_pathkeys, List **group_clauses, int num_groupby_pathkeys)
List *	get_useful_group_keys_orderings (PlannerInfo *root, Path *path)
bool	pathkeys_count_contained_in (List *keys1, List *keys2, int *n_common)
Path *	get_cheapest_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, CostSelector cost_criterion, bool require_parallel_safe)
Path *	get_cheapest_fractional_path_for_pathkeys (List *paths, List *pathkeys, Relids required_outer, double fraction)
Path *	get_cheapest_parallel_safe_total_inner (List *paths)
List *	build_index_pathkeys (PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir)
static bool	partkey_is_bool_constant_for_query (RelOptInfo *partrel, int partkeycol)
List *	build_partition_pathkeys (PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys)
List *	build_expression_pathkey (PlannerInfo *root, Expr *expr, Oid opno, Relids rel, bool create_it)
List *	convert_subquery_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *subquery_pathkeys, List *subquery_tlist)
List *	build_join_pathkeys (PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, List *outer_pathkeys)
List *	make_pathkeys_for_sortclauses (PlannerInfo *root, List *sortclauses, List *tlist)
List *	make_pathkeys_for_sortclauses_extended (PlannerInfo *root, List **sortclauses, List *tlist, bool remove_redundant, bool remove_group_rtindex, bool *sortable, bool set_ec_sortref)
void	initialize_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
void	update_mergeclause_eclasses (PlannerInfo *root, RestrictInfo *restrictinfo)
List *	find_mergeclauses_for_outer_pathkeys (PlannerInfo *root, List *pathkeys, List *restrictinfos)
List *	select_outer_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel)
List *	make_inner_pathkeys_for_merge (PlannerInfo *root, List *mergeclauses, List *outer_pathkeys)
List *	trim_mergeclauses_for_inner_pathkeys (PlannerInfo *root, List *mergeclauses, List *pathkeys)
static int	pathkeys_useful_for_merging (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
static int	pathkeys_useful_for_ordering (PlannerInfo *root, List *pathkeys)
static int	pathkeys_useful_for_grouping (PlannerInfo *root, List *pathkeys)
static int	pathkeys_useful_for_distinct (PlannerInfo *root, List *pathkeys)
static int	pathkeys_useful_for_setop (PlannerInfo *root, List *pathkeys)
List *	truncate_useless_pathkeys (PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
bool	has_useful_pathkeys (PlannerInfo *root, RelOptInfo *rel)

Variables
bool	enable_group_by_reordering = true

Function Documentation

append_pathkeys()

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

Definition at line 107 of file pathkeys.c.

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

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

Referenced by adjust_group_pathkeys_for_groupagg(), and make_pathkeys_for_window().

build_expression_pathkey()

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

Definition at line 1000 of file pathkeys.c.

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

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

Referenced by set_function_pathlist().

build_index_pathkeys()

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

Definition at line 740 of file pathkeys.c.

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

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

Referenced by build_index_paths().

build_join_pathkeys()

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

Definition at line 1294 of file pathkeys.c.

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

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

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

build_partition_pathkeys()

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

Definition at line 919 of file pathkeys.c.

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

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

Referenced by generate_orderedappend_paths().

compare_pathkeys()

PathKeysComparison compare_pathkeys	(	List *	keys1,
		List *	keys2
	)

Definition at line 304 of file pathkeys.c.

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

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

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

convert_subquery_pathkeys()

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

Definition at line 1054 of file pathkeys.c.

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

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

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

find_mergeclauses_for_outer_pathkeys()

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

Definition at line 1543 of file pathkeys.c.

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

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

find_var_for_subquery_tle()

static Var * find_var_for_subquery_tle ( RelOptInfo *  rel, TargetEntry *  tle  )

static

Definition at line 1251 of file pathkeys.c.

{
    ListCell   *lc;
 
    /* If the TLE is resjunk, it's certainly not visible to the outer query */
    if (tle->resjunk)
        return NULL;
 
    /* Search the rel's targetlist to see what it will return */
    foreach(lc, rel->reltarget->exprs)
    {
        Var        *var = (Var *) lfirst(lc);
 
        /* Ignore placeholders */
        if (!IsA(var, Var))
            continue;
        Assert(var->varno == rel->relid);
 
        /* If we find a Var referencing this TLE, we're good */
        if (var->varattno == tle->resno)
            return copyObject(var); /* Make a copy for safety */
    }
    return NULL;
}

References Assert, copyObject, PathTarget::exprs, IsA, lfirst, RelOptInfo::relid, RelOptInfo::reltarget, TargetEntry::resno, Var::varattno, and Var::varno.

Referenced by convert_subquery_pathkeys().

get_cheapest_fractional_path_for_pathkeys()

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

Definition at line 666 of file pathkeys.c.

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

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

Referenced by build_minmax_path(), and generate_orderedappend_paths().

get_cheapest_parallel_safe_total_inner()

Path * get_cheapest_parallel_safe_total_inner

(

List *

paths

)

Definition at line 699 of file pathkeys.c.

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

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

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

get_cheapest_path_for_pathkeys()

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

Definition at line 620 of file pathkeys.c.

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

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

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

get_useful_group_keys_orderings()

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

Definition at line 467 of file pathkeys.c.

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

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

Referenced by add_paths_to_grouping_rel(), and create_partial_grouping_paths().

group_keys_reorder_by_pathkeys()

static int group_keys_reorder_by_pathkeys ( List *  pathkeys, List **  group_pathkeys, List **  group_clauses, int  num_groupby_pathkeys  )

static

Definition at line 370 of file pathkeys.c.

{
    List       *new_group_pathkeys = NIL,
               *new_group_clauses = NIL;
    List       *grouping_pathkeys;
    ListCell   *lc;
    int         n;
 
    if (pathkeys == NIL || *group_pathkeys == NIL)
        return 0;
 
    /*
     * We're going to search within just the first num_groupby_pathkeys of
     * *group_pathkeys.  The thing is that root->group_pathkeys is passed as
     * *group_pathkeys containing grouping pathkeys altogether with aggregate
     * pathkeys.  If we process aggregate pathkeys we could get an invalid
     * result of get_sortgroupref_clause_noerr(), because their
     * pathkey->pk_eclass->ec_sortref doesn't reference query targetlist.  So,
     * we allocate a separate list of pathkeys for lookups.
     */
    grouping_pathkeys = list_copy_head(*group_pathkeys, num_groupby_pathkeys);
 
    /*
     * Walk the pathkeys (determining ordering of the input path) and see if
     * there's a matching GROUP BY key. If we find one, we append it to the
     * list, and do the same for the clauses.
     *
     * Once we find the first pathkey without a matching GROUP BY key, the
     * rest of the pathkeys are useless and can't be used to evaluate the
     * grouping, so we abort the loop and ignore the remaining pathkeys.
     */
    foreach(lc, pathkeys)
    {
        PathKey    *pathkey = (PathKey *) lfirst(lc);
        SortGroupClause *sgc;
 
        /*
         * Pathkeys are built in a way that allows simply comparing pointers.
         * Give up if we can't find the matching pointer.  Also give up if
         * there is no sortclause reference for some reason.
         */
        if (foreach_current_index(lc) >= num_groupby_pathkeys ||
            !list_member_ptr(grouping_pathkeys, pathkey) ||
            pathkey->pk_eclass->ec_sortref == 0)
            break;
 
        /*
         * Since 1349d27 pathkey coming from underlying node can be in the
         * root->group_pathkeys but not in the processed_groupClause. So, we
         * should be careful here.
         */
        sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref,
                                            *group_clauses);
        if (!sgc)
            /* The grouping clause does not cover this pathkey */
            break;
 
        /*
         * Sort group clause should have an ordering operator as long as there
         * is an associated pathkey.
         */
        Assert(OidIsValid(sgc->sortop));
 
        new_group_pathkeys = lappend(new_group_pathkeys, pathkey);
        new_group_clauses = lappend(new_group_clauses, sgc);
    }
 
    /* remember the number of pathkeys with a matching GROUP BY key */
    n = list_length(new_group_pathkeys);
 
    /* append the remaining group pathkeys (will be treated as not sorted) */
    *group_pathkeys = list_concat_unique_ptr(new_group_pathkeys,
                                             *group_pathkeys);
    *group_clauses = list_concat_unique_ptr(new_group_clauses,
                                            *group_clauses);
 
    list_free(grouping_pathkeys);
    return n;
}

References Assert, foreach_current_index, get_sortgroupref_clause_noerr(), lappend(), lfirst, list_concat_unique_ptr(), list_copy_head(), list_free(), list_length(), list_member_ptr(), NIL, OidIsValid, and SortGroupClause::sortop.

Referenced by get_useful_group_keys_orderings().

has_useful_pathkeys()

bool has_useful_pathkeys	(	PlannerInfo *	root,
		RelOptInfo *	rel
	)

Definition at line 2315 of file pathkeys.c.

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

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

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

initialize_mergeclause_eclasses()

void initialize_mergeclause_eclasses	(	PlannerInfo *	root,
		RestrictInfo *	restrictinfo
	)

Definition at line 1462 of file pathkeys.c.

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

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

Referenced by distribute_qual_to_rels().

make_canonical_pathkey()

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

Definition at line 56 of file pathkeys.c.

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

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

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

make_inner_pathkeys_for_merge()

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

Definition at line 1854 of file pathkeys.c.

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

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

Referenced by generate_mergejoin_paths(), and sort_inner_and_outer().

make_pathkey_from_sortinfo()

static PathKey * make_pathkey_from_sortinfo ( PlannerInfo *  root, Expr *  expr, Oid  opfamily, Oid  opcintype, Oid  collation, bool  reverse_sort, bool  nulls_first, Index  sortref, Relids  rel, bool  create_it  )

static

Definition at line 198 of file pathkeys.c.

{
    int16       strategy;
    Oid         equality_op;
    List       *opfamilies;
    EquivalenceClass *eclass;
 
    strategy = reverse_sort ? BTGreaterStrategyNumber : BTLessStrategyNumber;
 
    /*
     * EquivalenceClasses need to contain opfamily lists based on the family
     * membership of mergejoinable equality operators, which could belong to
     * more than one opfamily.  So we have to look up the opfamily's equality
     * operator and get its membership.
     */
    equality_op = get_opfamily_member(opfamily,
                                      opcintype,
                                      opcintype,
                                      BTEqualStrategyNumber);
    if (!OidIsValid(equality_op))   /* shouldn't happen */
        elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
             BTEqualStrategyNumber, opcintype, opcintype, opfamily);
    opfamilies = get_mergejoin_opfamilies(equality_op);
    if (!opfamilies)            /* certainly should find some */
        elog(ERROR, "could not find opfamilies for equality operator %u",
             equality_op);
 
    /* Now find or (optionally) create a matching EquivalenceClass */
    eclass = get_eclass_for_sort_expr(root, expr,
                                      opfamilies, opcintype, collation,
                                      sortref, rel, create_it);
 
    /* Fail if no EC and !create_it */
    if (!eclass)
        return NULL;
 
    /* And finally we can find or create a PathKey node */
    return make_canonical_pathkey(root, eclass, opfamily,
                                  strategy, nulls_first);
}

References BTEqualStrategyNumber, BTGreaterStrategyNumber, BTLessStrategyNumber, eclass(), elog, ERROR, get_eclass_for_sort_expr(), get_mergejoin_opfamilies(), get_opfamily_member(), make_canonical_pathkey(), OidIsValid, and root.

Referenced by build_expression_pathkey(), build_index_pathkeys(), build_partition_pathkeys(), and make_pathkey_from_sortop().

make_pathkey_from_sortop()

static PathKey * make_pathkey_from_sortop ( PlannerInfo *  root, Expr *  expr, Oid  ordering_op, bool  reverse_sort, bool  nulls_first, Index  sortref, bool  create_it  )

static

Definition at line 256 of file pathkeys.c.

{
    Oid         opfamily,
                opcintype,
                collation;
    int16       strategy;
 
    /* Find the operator in pg_amop --- failure shouldn't happen */
    if (!get_ordering_op_properties(ordering_op,
                                    &opfamily, &opcintype, &strategy))
        elog(ERROR, "operator %u is not a valid ordering operator",
             ordering_op);
 
    /* Because SortGroupClause doesn't carry collation, consult the expr */
    collation = exprCollation((Node *) expr);
 
    return make_pathkey_from_sortinfo(root,
                                      expr,
                                      opfamily,
                                      opcintype,
                                      collation,
                                      reverse_sort,
                                      nulls_first,
                                      sortref,
                                      NULL,
                                      create_it);
}

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

Referenced by make_pathkeys_for_sortclauses_extended().

make_pathkeys_for_sortclauses()

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

Definition at line 1335 of file pathkeys.c.

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

References Assert, make_pathkeys_for_sortclauses_extended(), and root.

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

make_pathkeys_for_sortclauses_extended()

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

Definition at line 1380 of file pathkeys.c.

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

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

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

matches_boolean_partition_clause()

static bool matches_boolean_partition_clause ( RestrictInfo *  rinfo, RelOptInfo *  partrel, int  partkeycol  )

static

Definition at line 884 of file pathkeys.c.

{
    Node       *clause = (Node *) rinfo->clause;
    Node       *partexpr = (Node *) linitial(partrel->partexprs[partkeycol]);
 
    /* Direct match? */
    if (equal(partexpr, clause))
        return true;
    /* NOT clause? */
    else if (is_notclause(clause))
    {
        Node       *arg = (Node *) get_notclausearg((Expr *) clause);
 
        if (equal(partexpr, arg))
            return true;
    }
 
    return false;
}

References arg, RestrictInfo::clause, equal(), get_notclausearg(), is_notclause(), and linitial.

Referenced by partkey_is_bool_constant_for_query().

partkey_is_bool_constant_for_query()

static bool partkey_is_bool_constant_for_query ( RelOptInfo *  partrel, int  partkeycol  )

static

Definition at line 844 of file pathkeys.c.

{
    PartitionScheme partscheme = partrel->part_scheme;
    ListCell   *lc;
 
    /*
     * If the partkey isn't boolean, we can't possibly get a match.
     *
     * Partitioning currently can only use built-in AMs, so checking for
     * built-in boolean opfamilies is good enough.
     */
    if (!IsBuiltinBooleanOpfamily(partscheme->partopfamily[partkeycol]))
        return false;
 
    /* Check each restriction clause for the partitioned rel */
    foreach(lc, partrel->baserestrictinfo)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
 
        /* Ignore pseudoconstant quals, they won't match */
        if (rinfo->pseudoconstant)
            continue;
 
        /* See if we can match the clause's expression to the partkey column */
        if (matches_boolean_partition_clause(rinfo, partrel, partkeycol))
            return true;
    }
 
    return false;
}

References RelOptInfo::baserestrictinfo, lfirst, matches_boolean_partition_clause(), and PartitionSchemeData::partopfamily.

Referenced by build_partition_pathkeys().

pathkey_is_redundant()

static bool pathkey_is_redundant ( PathKey *  new_pathkey, List *  pathkeys  )

static

Definition at line 159 of file pathkeys.c.

{
    EquivalenceClass *new_ec = new_pathkey->pk_eclass;
    ListCell   *lc;
 
    /* Check for EC containing a constant --- unconditionally redundant */
    if (EC_MUST_BE_REDUNDANT(new_ec))
        return true;
 
    /* If same EC already used in list, then redundant */
    foreach(lc, pathkeys)
    {
        PathKey    *old_pathkey = (PathKey *) lfirst(lc);
 
        if (new_ec == old_pathkey->pk_eclass)
            return true;
    }
 
    return false;
}

References EC_MUST_BE_REDUNDANT, and lfirst.

Referenced by append_pathkeys(), build_index_pathkeys(), build_partition_pathkeys(), convert_subquery_pathkeys(), make_inner_pathkeys_for_merge(), make_pathkeys_for_sortclauses_extended(), and select_outer_pathkeys_for_merge().

pathkeys_contained_in()

bool pathkeys_contained_in	(	List *	keys1,
		List *	keys2
	)

Definition at line 343 of file pathkeys.c.

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

References compare_pathkeys(), PATHKEYS_BETTER2, and PATHKEYS_EQUAL.

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

pathkeys_count_contained_in()

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

Definition at line 558 of file pathkeys.c.

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

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

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

pathkeys_useful_for_distinct()

static int pathkeys_useful_for_distinct ( PlannerInfo *  root, List *  pathkeys  )

static

Definition at line 2220 of file pathkeys.c.

{
    int         n_common_pathkeys;
 
    /*
     * distinct_pathkeys may have become empty if all of the pathkeys were
     * determined to be redundant.  Return 0 in this case.
     */
    if (root->distinct_pathkeys == NIL)
        return 0;
 
    /* walk the pathkeys and search for matching DISTINCT key */
    n_common_pathkeys = 0;
    foreach_node(PathKey, pathkey, pathkeys)
    {
        /* no matching DISTINCT key, we're done */
        if (!list_member_ptr(root->distinct_pathkeys, pathkey))
            break;
 
        n_common_pathkeys++;
    }
 
    return n_common_pathkeys;
}

References foreach_node, list_member_ptr(), NIL, and root.

Referenced by truncate_useless_pathkeys().

pathkeys_useful_for_grouping()

static int pathkeys_useful_for_grouping ( PlannerInfo *  root, List *  pathkeys  )

static

Definition at line 2186 of file pathkeys.c.

{
    ListCell   *key;
    int         n = 0;
 
    /* no special ordering requested for grouping */
    if (root->group_pathkeys == NIL)
        return 0;
 
    /* walk the pathkeys and search for matching group key */
    foreach(key, pathkeys)
    {
        PathKey    *pathkey = (PathKey *) lfirst(key);
 
        /* no matching group key, we're done */
        if (!list_member_ptr(root->group_pathkeys, pathkey))
            break;
 
        n++;
    }
 
    return n;
}

References sort-test::key, lfirst, list_member_ptr(), NIL, and root.

Referenced by truncate_useless_pathkeys().

pathkeys_useful_for_merging()

static int pathkeys_useful_for_merging ( PlannerInfo *  root, RelOptInfo *  rel, List *  pathkeys  )

static

Definition at line 2052 of file pathkeys.c.

{
    int         useful = 0;
    ListCell   *i;
 
    foreach(i, pathkeys)
    {
        PathKey    *pathkey = (PathKey *) lfirst(i);
        bool        matched = false;
        ListCell   *j;
 
        /* If "wrong" direction, not useful for merging */
        if (!right_merge_direction(root, pathkey))
            break;
 
        /*
         * First look into the EquivalenceClass of the pathkey, to see if
         * there are any members not yet joined to the rel.  If so, it's
         * surely possible to generate a mergejoin clause using them.
         */
        if (rel->has_eclass_joins &&
            eclass_useful_for_merging(root, pathkey->pk_eclass, rel))
            matched = true;
        else
        {
            /*
             * Otherwise search the rel's joininfo list, which contains
             * non-EquivalenceClass-derivable join clauses that might
             * nonetheless be mergejoinable.
             */
            foreach(j, rel->joininfo)
            {
                RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
 
                if (restrictinfo->mergeopfamilies == NIL)
                    continue;
                update_mergeclause_eclasses(root, restrictinfo);
 
                if (pathkey->pk_eclass == restrictinfo->left_ec ||
                    pathkey->pk_eclass == restrictinfo->right_ec)
                {
                    matched = true;
                    break;
                }
            }
        }
 
        /*
         * 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)
            useful++;
        else
            break;
    }
 
    return useful;
}

References eclass_useful_for_merging(), RelOptInfo::has_eclass_joins, i, j, RelOptInfo::joininfo, lfirst, NIL, right_merge_direction(), root, and update_mergeclause_eclasses().

Referenced by truncate_useless_pathkeys().

pathkeys_useful_for_ordering()

static int pathkeys_useful_for_ordering ( PlannerInfo *  root, List *  pathkeys  )

static

Definition at line 2156 of file pathkeys.c.

{
    int         n_common_pathkeys;
 
    (void) pathkeys_count_contained_in(root->query_pathkeys, pathkeys,
                                       &n_common_pathkeys);
 
    return n_common_pathkeys;
}

References pathkeys_count_contained_in(), and root.

Referenced by truncate_useless_pathkeys().

pathkeys_useful_for_setop()

static int pathkeys_useful_for_setop ( PlannerInfo *  root, List *  pathkeys  )

static

Definition at line 2251 of file pathkeys.c.

{
    int         n_common_pathkeys;
 
    (void) pathkeys_count_contained_in(root->setop_pathkeys, pathkeys,
                                       &n_common_pathkeys);
 
    return n_common_pathkeys;
}

References pathkeys_count_contained_in(), and root.

Referenced by truncate_useless_pathkeys().

right_merge_direction()

static bool right_merge_direction ( PlannerInfo *  root, PathKey *  pathkey  )

static

Definition at line 2119 of file pathkeys.c.

{
    ListCell   *l;
 
    foreach(l, root->query_pathkeys)
    {
        PathKey    *query_pathkey = (PathKey *) lfirst(l);
 
        if (pathkey->pk_eclass == query_pathkey->pk_eclass &&
            pathkey->pk_opfamily == query_pathkey->pk_opfamily)
        {
            /*
             * Found a matching query sort column.  Prefer this pathkey's
             * direction iff it matches.  Note that we ignore pk_nulls_first,
             * which means that a sort might be needed anyway ... but we still
             * want to prefer only one of the two possible directions, and we
             * might as well use this one.
             */
            return (pathkey->pk_strategy == query_pathkey->pk_strategy);
        }
    }
 
    /* If no matching ORDER BY request, prefer the ASC direction */
    return (pathkey->pk_strategy == BTLessStrategyNumber);
}

References BTLessStrategyNumber, lfirst, PathKey::pk_opfamily, PathKey::pk_strategy, and root.

Referenced by pathkeys_useful_for_merging().

select_outer_pathkeys_for_merge()

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

Definition at line 1658 of file pathkeys.c.

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

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

Referenced by sort_inner_and_outer().

trim_mergeclauses_for_inner_pathkeys()

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

Definition at line 1957 of file pathkeys.c.

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

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

Referenced by generate_mergejoin_paths().

truncate_useless_pathkeys()

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

Definition at line 2266 of file pathkeys.c.

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

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

Referenced by build_index_paths(), and build_join_pathkeys().

update_mergeclause_eclasses()

void update_mergeclause_eclasses	(	PlannerInfo *	root,
		RestrictInfo *	restrictinfo
	)

Definition at line 1509 of file pathkeys.c.

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

References Assert, and NIL.

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

Variable Documentation

enable_group_by_reordering

bool enable_group_by_reordering = true

Definition at line 32 of file pathkeys.c.

Referenced by get_useful_group_keys_orderings().