Header And Logo
|
#include "postgres.h"#include "access/skey.h"#include "nodes/makefuncs.h"#include "nodes/nodeFuncs.h"#include "nodes/plannodes.h"#include "optimizer/clauses.h"#include "optimizer/pathnode.h"#include "optimizer/paths.h"#include "optimizer/tlist.h"#include "utils/lsyscache.h"
Go to the source code of this file.
| List* build_index_pathkeys | ( | PlannerInfo * | root, | |
| IndexOptInfo * | index, | |||
| ScanDirection | scandir | |||
| ) |
Definition at line 430 of file pathkeys.c.
References TargetEntry::expr, i, IndexOptInfo::indexcollations, IndexOptInfo::indextlist, lappend(), lfirst, make_pathkey_from_sortinfo(), 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 */
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 the sort key isn't already present in any EquivalenceClass, then
* it's not an interesting sort order for this query. So we can stop
* now --- lower-order sort keys aren't useful either.
*/
if (!cpathkey)
break;
/* Add to list unless redundant */
if (!pathkey_is_redundant(cpathkey, retval))
retval = lappend(retval, cpathkey);
i++;
}
return retval;
}
| List* build_join_pathkeys | ( | PlannerInfo * | root, | |
| RelOptInfo * | joinrel, | |||
| JoinType | jointype, | |||
| List * | outer_pathkeys | |||
| ) |
Definition at line 719 of file pathkeys.c.
References JOIN_FULL, JOIN_RIGHT, and truncate_useless_pathkeys().
Referenced by 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);
}
| PathKeysComparison compare_pathkeys | ( | List * | keys1, | |
| List * | keys2 | |||
| ) |
Definition at line 275 of file pathkeys.c.
References forboth, lfirst, and NULL.
Referenced by add_path(), add_path_precheck(), pathkeys_contained_in(), set_append_rel_pathlist(), 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;
}
| List* convert_subquery_pathkeys | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel, | |||
| List * | subquery_pathkeys | |||
| ) |
Definition at line 508 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(), pathkey_is_redundant(), PathKey::pk_eclass, PathKey::pk_nulls_first, PathKey::pk_opfamily, PathKey::pk_strategy, PlannerInfo::query_pathkeys, RelOptInfo::relid, RelOptInfo::relids, TargetEntry::resjunk, RelOptInfo::subplan, and Plan::targetlist.
Referenced by set_subquery_pathlist().
{
List *retval = NIL;
int retvallen = 0;
int outer_query_keys = list_length(root->query_pathkeys);
List *sub_tlist = rel->subplan->targetlist;
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, sub_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.
*/
outer_ec =
get_eclass_for_sort_expr(root,
outer_expr,
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, sub_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,
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;
}
| List* find_mergeclauses_for_pathkeys | ( | PlannerInfo * | root, | |
| List * | pathkeys, | |||
| bool | outer_keys, | |||
| List * | restrictinfos | |||
| ) |
Definition at line 890 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 match_unsorted_outer(), 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;
}
| Path* get_cheapest_fractional_path_for_pathkeys | ( | List * | paths, | |
| List * | pathkeys, | |||
| Relids | required_outer, | |||
| double | fraction | |||
| ) |
Definition at line 380 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 query_planner().
{
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_path_for_pathkeys | ( | List * | paths, | |
| List * | pathkeys, | |||
| Relids | required_outer, | |||
| CostSelector | cost_criterion | |||
| ) |
Definition at line 339 of file pathkeys.c.
References bms_is_subset(), compare_path_costs(), lfirst, NULL, PATH_REQ_OUTER, Path::pathkeys, and pathkeys_contained_in().
Referenced by generate_mergeappend_paths(), match_unsorted_outer(), and set_append_rel_pathlist().
{
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 (pathkeys_contained_in(pathkeys, path->pathkeys) &&
bms_is_subset(PATH_REQ_OUTER(path), required_outer))
matched_path = path;
}
return matched_path;
}
| bool has_useful_pathkeys | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel | |||
| ) |
Definition at line 1445 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 */
}
| void initialize_mergeclause_eclasses | ( | PlannerInfo * | root, | |
| RestrictInfo * | restrictinfo | |||
| ) |
Definition at line 808 of file pathkeys.c.
References Assert, RestrictInfo::clause, get_eclass_for_sort_expr(), get_leftop(), get_rightop(), RestrictInfo::left_ec, RestrictInfo::mergeopfamilies, NIL, NULL, 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->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);
}
| static PathKey * make_canonical_pathkey | ( | PlannerInfo * | root, | |
| EquivalenceClass * | eclass, | |||
| Oid | opfamily, | |||
| int | strategy, | |||
| bool | nulls_first | |||
| ) | [static] |
Definition at line 54 of file pathkeys.c.
References PlannerInfo::canon_pathkeys, EquivalenceClass::ec_merged, 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(), 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 1179 of file pathkeys.c.
References elog, ERROR, lappend(), RestrictInfo::left_ec, lfirst, list_head(), lnext, make_canonical_pathkey(), 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 match_unsorted_outer(), 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;
}
| 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 170 of file pathkeys.c.
References BTEqualStrategyNumber, BTGreaterStrategyNumber, elog, ERROR, get_eclass_for_sort_expr(), get_mergejoin_opfamilies(), get_opfamily_member(), make_canonical_pathkey(), and OidIsValid.
Referenced by build_index_pathkeys(), and make_pathkey_from_sortop().
{
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, "could not find equality operator for opfamily %u",
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);
}
| static PathKey* make_pathkey_from_sortop | ( | PlannerInfo * | root, | |
| Expr * | expr, | |||
| Oid | ordering_op, | |||
| bool | nulls_first, | |||
| Index | sortref, | |||
| bool | create_it | |||
| ) | [static] |
Definition at line 228 of file pathkeys.c.
References BTGreaterStrategyNumber, elog, ERROR, exprCollation(), get_ordering_op_properties(), make_pathkey_from_sortinfo(), and NULL.
Referenced by make_pathkeys_for_sortclauses().
{
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,
(strategy == BTGreaterStrategyNumber),
nulls_first,
sortref,
NULL,
create_it);
}
| List* make_pathkeys_for_sortclauses | ( | PlannerInfo * | root, | |
| List * | sortclauses, | |||
| List * | tlist | |||
| ) |
Definition at line 755 of file pathkeys.c.
References Assert, get_sortgroupclause_expr(), lappend(), lfirst, make_pathkey_from_sortop(), SortGroupClause::nulls_first, OidIsValid, pathkey_is_redundant(), SortGroupClause::sortop, and SortGroupClause::tleSortGroupRef.
Referenced by get_column_info_for_window(), grouping_planner(), make_pathkeys_for_window(), 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,
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;
}
Definition at line 131 of file pathkeys.c.
References EC_MUST_BE_REDUNDANT, lfirst, and PathKey::pk_eclass.
Referenced by build_index_pathkeys(), convert_subquery_pathkeys(), make_inner_pathkeys_for_merge(), make_pathkeys_for_sortclauses(), and select_outer_pathkeys_for_merge().
{
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;
}
Definition at line 314 of file pathkeys.c.
References compare_pathkeys(), PATHKEYS_BETTER2, and PATHKEYS_EQUAL.
Referenced by build_minmax_path(), choose_hashed_distinct(), choose_hashed_grouping(), create_merge_append_path(), create_merge_append_plan(), get_cheapest_fractional_path_for_pathkeys(), get_cheapest_path_for_pathkeys(), grouping_planner(), match_unsorted_outer(), pathkeys_useful_for_ordering(), query_planner(), and try_mergejoin_path().
{
switch (compare_pathkeys(keys1, keys2))
{
case PATHKEYS_EQUAL:
case PATHKEYS_BETTER2:
return true;
default:
break;
}
return false;
}
| static int pathkeys_useful_for_merging | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel, | |||
| List * | pathkeys | |||
| ) | [static] |
Definition at line 1280 of file pathkeys.c.
References eclass_useful_for_merging(), RelOptInfo::has_eclass_joins, i, RelOptInfo::joininfo, RestrictInfo::left_ec, lfirst, RestrictInfo::mergeopfamilies, NIL, PathKey::pk_eclass, RestrictInfo::right_ec, right_merge_direction(), and update_mergeclause_eclasses().
Referenced by truncate_useless_pathkeys().
{
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(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;
}
| static int pathkeys_useful_for_ordering | ( | PlannerInfo * | root, | |
| List * | pathkeys | |||
| ) | [static] |
Definition at line 1383 of file pathkeys.c.
References list_length(), NIL, pathkeys_contained_in(), and PlannerInfo::query_pathkeys.
Referenced by truncate_useless_pathkeys().
{
if (root->query_pathkeys == NIL)
return 0; /* no special ordering requested */
if (pathkeys == NIL)
return 0; /* unordered path */
if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
{
/* It's useful ... or at least the first N keys are */
return list_length(root->query_pathkeys);
}
return 0; /* path ordering not useful */
}
| static bool right_merge_direction | ( | PlannerInfo * | root, | |
| PathKey * | pathkey | |||
| ) | [static] |
Definition at line 1347 of file pathkeys.c.
References BTLessStrategyNumber, lfirst, PathKey::pk_eclass, PathKey::pk_opfamily, PathKey::pk_strategy, and PlannerInfo::query_pathkeys.
Referenced by pathkeys_useful_for_merging().
{
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);
}
| List* select_outer_pathkeys_for_merge | ( | PlannerInfo * | root, | |
| List * | mergeclauses, | |||
| RelOptInfo * | joinrel | |||
| ) |
Definition at line 1007 of file pathkeys.c.
References Assert, bms_overlap(), BTLessStrategyNumber, EquivalenceClass::ec_members, EquivalenceClass::ec_opfamilies, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, lappend(), RestrictInfo::left_ec, lfirst, linitial_oid, list_copy(), list_length(), make_canonical_pathkey(), NULL, RestrictInfo::outer_is_left, palloc(), pathkey_is_redundant(), pfree(), PathKey::pk_eclass, PlannerInfo::query_pathkeys, RelOptInfo::relids, RestrictInfo::right_ec, and update_mergeclause_eclasses().
Referenced by sort_inner_and_outer().
{
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. There is
* no percentage in a partial match, though, so we have to have 'em all.
*/
if (root->query_pathkeys)
{
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 */
}
/* 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;
}
}
}
}
}
/*
* 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;
}
| List* truncate_useless_pathkeys | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel, | |||
| List * | pathkeys | |||
| ) |
Definition at line 1405 of file pathkeys.c.
References list_copy(), list_length(), list_truncate(), pathkeys_useful_for_merging(), and pathkeys_useful_for_ordering().
Referenced by build_index_paths(), and build_join_pathkeys().
{
int nuseful;
int nuseful2;
nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
nuseful2 = pathkeys_useful_for_ordering(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_truncate(list_copy(pathkeys), nuseful);
}
| void update_mergeclause_eclasses | ( | PlannerInfo * | root, | |
| RestrictInfo * | restrictinfo | |||
| ) |
Definition at line 855 of file pathkeys.c.
References Assert, EquivalenceClass::ec_merged, RestrictInfo::left_ec, RestrictInfo::mergeopfamilies, NIL, NULL, and RestrictInfo::right_ec.
Referenced by find_mergeclauses_for_pathkeys(), make_inner_pathkeys_for_merge(), pathkeys_useful_for_merging(), select_mergejoin_clauses(), and select_outer_pathkeys_for_merge().
{
/* 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;
}
1.7.1