Header And Logo
|
#include "nodes/relation.h"
Go to the source code of this file.
| typedef bool(* ec_matches_callback_type)(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg) |
| typedef RelOptInfo*(* join_search_hook_type)(PlannerInfo *root, int levels_needed, List *initial_rels) |
| enum PathKeysComparison |
Definition at line 149 of file paths.h.
{
PATHKEYS_EQUAL, /* pathkeys are identical */
PATHKEYS_BETTER1, /* pathkey 1 is a superset of pathkey 2 */
PATHKEYS_BETTER2, /* vice versa */
PATHKEYS_DIFFERENT /* neither pathkey includes the other */
} PathKeysComparison;
| void add_child_rel_equivalences | ( | PlannerInfo * | root, | |
| AppendRelInfo * | appinfo, | |||
| RelOptInfo * | parent_rel, | |||
| RelOptInfo * | child_rel | |||
| ) |
Definition at line 1905 of file equivclass.c.
References add_eq_member(), adjust_appendrel_attrs(), bms_add_members(), bms_difference(), bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_nullable_relids, EquivalenceMember::em_relids, PlannerInfo::eq_classes, lfirst, and RelOptInfo::relids.
Referenced by set_append_rel_size().
{
ListCell *lc1;
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
ListCell *lc2;
/*
* If this EC contains a volatile expression, then generating child
* EMs would be downright dangerous, so skip it. We rely on a
* volatile EC having only one EM.
*/
if (cur_ec->ec_has_volatile)
continue;
/* No point in searching if parent rel not mentioned in eclass */
if (!bms_is_subset(parent_rel->relids, cur_ec->ec_relids))
continue;
foreach(lc2, cur_ec->ec_members)
{
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
if (cur_em->em_is_const || cur_em->em_is_child)
continue; /* ignore consts and children here */
/* Does it reference parent_rel? */
if (bms_overlap(cur_em->em_relids, parent_rel->relids))
{
/* Yes, generate transformed child version */
Expr *child_expr;
Relids new_relids;
Relids new_nullable_relids;
child_expr = (Expr *)
adjust_appendrel_attrs(root,
(Node *) cur_em->em_expr,
appinfo);
/*
* Transform em_relids to match. Note we do *not* do
* pull_varnos(child_expr) here, as for example the
* transformation might have substituted a constant, but we
* don't want the child member to be marked as constant.
*/
new_relids = bms_difference(cur_em->em_relids,
parent_rel->relids);
new_relids = bms_add_members(new_relids, child_rel->relids);
/*
* And likewise for nullable_relids. Note this code assumes
* parent and child relids are singletons.
*/
new_nullable_relids = cur_em->em_nullable_relids;
if (bms_overlap(new_nullable_relids, parent_rel->relids))
{
new_nullable_relids = bms_difference(new_nullable_relids,
parent_rel->relids);
new_nullable_relids = bms_add_members(new_nullable_relids,
child_rel->relids);
}
(void) add_eq_member(cur_ec, child_expr,
new_relids, new_nullable_relids,
true, cur_em->em_datatype);
}
}
}
}
| void add_paths_to_joinrel | ( | PlannerInfo * | root, | |
| RelOptInfo * | joinrel, | |||
| RelOptInfo * | outerrel, | |||
| RelOptInfo * | innerrel, | |||
| JoinType | jointype, | |||
| SpecialJoinInfo * | sjinfo, | |||
| List * | restrictlist | |||
| ) |
Definition at line 78 of file joinpath.c.
References PlannerInfo::all_baserels, bms_difference(), bms_is_member(), bms_join(), bms_overlap(), compute_semi_anti_join_factors(), enable_hashjoin, enable_mergejoin, hash_inner_and_outer(), JOIN_ANTI, JOIN_FULL, PlannerInfo::join_info_list, JOIN_SEMI, SpecialJoinInfo::jointype, PlannerInfo::lateral_info_list, LateralJoinInfo::lateral_lhs, LateralJoinInfo::lateral_rhs, lfirst, match_unsorted_outer(), SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, RelOptInfo::relids, select_mergejoin_clauses(), and sort_inner_and_outer().
Referenced by make_join_rel().
{
List *mergeclause_list = NIL;
bool mergejoin_allowed = true;
SemiAntiJoinFactors semifactors;
Relids param_source_rels = NULL;
ListCell *lc;
/*
* Find potential mergejoin clauses. We can skip this if we are not
* interested in doing a mergejoin. However, mergejoin may be our only
* way of implementing a full outer join, so override enable_mergejoin if
* it's a full join.
*/
if (enable_mergejoin || jointype == JOIN_FULL)
mergeclause_list = select_mergejoin_clauses(root,
joinrel,
outerrel,
innerrel,
restrictlist,
jointype,
&mergejoin_allowed);
/*
* If it's SEMI or ANTI join, compute correction factors for cost
* estimation. These will be the same for all paths.
*/
if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)
compute_semi_anti_join_factors(root, outerrel, innerrel,
jointype, sjinfo, restrictlist,
&semifactors);
/*
* Decide whether it's sensible to generate parameterized paths for this
* joinrel, and if so, which relations such paths should require. There
* is no need to create a parameterized result path unless there is a join
* order restriction that prevents joining one of our input rels directly
* to the parameter source rel instead of joining to the other input rel.
* This restriction reduces the number of parameterized paths we have to
* deal with at higher join levels, without compromising the quality of
* the resulting plan. We express the restriction as a Relids set that
* must overlap the parameterization of any proposed join path.
*/
foreach(lc, root->join_info_list)
{
SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
/*
* SJ is relevant to this join if we have some part of its RHS
* (possibly not all of it), and haven't yet joined to its LHS. (This
* test is pretty simplistic, but should be sufficient considering the
* join has already been proven legal.) If the SJ is relevant, it
* presents constraints for joining to anything not in its RHS.
*/
if (bms_overlap(joinrel->relids, sjinfo->min_righthand) &&
!bms_overlap(joinrel->relids, sjinfo->min_lefthand))
param_source_rels = bms_join(param_source_rels,
bms_difference(root->all_baserels,
sjinfo->min_righthand));
/* full joins constrain both sides symmetrically */
if (sjinfo->jointype == JOIN_FULL &&
bms_overlap(joinrel->relids, sjinfo->min_lefthand) &&
!bms_overlap(joinrel->relids, sjinfo->min_righthand))
param_source_rels = bms_join(param_source_rels,
bms_difference(root->all_baserels,
sjinfo->min_lefthand));
}
/*
* However, when a LATERAL subquery is involved, we have to be a bit
* laxer, because there will simply not be any paths for the joinrel that
* aren't parameterized by whatever the subquery is parameterized by,
* unless its parameterization is resolved within the joinrel. Hence, add
* to param_source_rels anything that is laterally referenced in either
* input and is not in the join already.
*/
foreach(lc, root->lateral_info_list)
{
LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(lc);
if (bms_is_member(ljinfo->lateral_rhs, joinrel->relids))
param_source_rels = bms_join(param_source_rels,
bms_difference(ljinfo->lateral_lhs,
joinrel->relids));
}
/*
* 1. Consider mergejoin paths where both relations must be explicitly
* sorted. Skip this if we can't mergejoin.
*/
if (mergejoin_allowed)
sort_inner_and_outer(root, joinrel, outerrel, innerrel,
restrictlist, mergeclause_list, jointype,
sjinfo, param_source_rels);
/*
* 2. Consider paths where the outer relation need not be explicitly
* sorted. This includes both nestloops and mergejoins where the outer
* path is already ordered. Again, skip this if we can't mergejoin.
* (That's okay because we know that nestloop can't handle right/full
* joins at all, so it wouldn't work in the prohibited cases either.)
*/
if (mergejoin_allowed)
match_unsorted_outer(root, joinrel, outerrel, innerrel,
restrictlist, mergeclause_list, jointype,
sjinfo, &semifactors, param_source_rels);
#ifdef NOT_USED
/*
* 3. Consider paths where the inner relation need not be explicitly
* sorted. This includes mergejoins only (nestloops were already built in
* match_unsorted_outer).
*
* Diked out as redundant 2/13/2000 -- tgl. There isn't any really
* significant difference between the inner and outer side of a mergejoin,
* so match_unsorted_inner creates no paths that aren't equivalent to
* those made by match_unsorted_outer when add_paths_to_joinrel() is
* invoked with the two rels given in the other order.
*/
if (mergejoin_allowed)
match_unsorted_inner(root, joinrel, outerrel, innerrel,
restrictlist, mergeclause_list, jointype,
sjinfo, &semifactors, param_source_rels);
#endif
/*
* 4. Consider paths where both outer and inner relations must be hashed
* before being joined. As above, disregard enable_hashjoin for full
* joins, because there may be no other alternative.
*/
if (enable_hashjoin || jointype == JOIN_FULL)
hash_inner_and_outer(root, joinrel, outerrel, innerrel,
restrictlist, jointype,
sjinfo, &semifactors, param_source_rels);
}
| Expr* adjust_rowcompare_for_index | ( | RowCompareExpr * | clause, | |
| IndexOptInfo * | index, | |||
| int | indexcol, | |||
| List ** | indexcolnos, | |||
| bool * | var_on_left_p | |||
| ) |
Definition at line 3576 of file indxpath.c.
References Assert, bms_is_member(), BOOLOID, BTGreaterEqualStrategyNumber, BTGreaterStrategyNumber, BTLessEqualStrategyNumber, BTLessStrategyNumber, contain_volatile_functions(), copyObject(), elog, ERROR, get_commutator(), get_op_opfamily_properties(), get_op_opfamily_strategy(), get_opfamily_member(), i, IndexOptInfo::indexcollations, IndexCollMatchesExprColl, RowCompareExpr::inputcollids, InvalidOid, lappend_int(), lappend_oid(), RowCompareExpr::largs, lfirst, lfirst_oid, linitial, linitial_oid, list_copy(), list_head(), list_length(), list_make1_int, list_make1_oid, list_truncate(), lnext, make_opclause(), makeNode, match_index_to_operand(), IndexOptInfo::ncolumns, NULL, OidIsValid, RowCompareExpr::opfamilies, IndexOptInfo::opfamily, RowCompareExpr::opnos, pull_varnos(), RowCompareExpr::rargs, RowCompareExpr::rctype, IndexOptInfo::rel, RelOptInfo::relid, ROWCOMPARE_GE, and ROWCOMPARE_LE.
Referenced by expand_indexqual_rowcompare(), and fix_indexqual_references().
{
bool var_on_left;
int op_strategy;
Oid op_lefttype;
Oid op_righttype;
int matching_cols;
Oid expr_op;
List *opfamilies;
List *lefttypes;
List *righttypes;
List *new_ops;
ListCell *largs_cell;
ListCell *rargs_cell;
ListCell *opnos_cell;
ListCell *collids_cell;
/* We have to figure out (again) how the first col matches */
var_on_left = match_index_to_operand((Node *) linitial(clause->largs),
indexcol, index);
Assert(var_on_left ||
match_index_to_operand((Node *) linitial(clause->rargs),
indexcol, index));
*var_on_left_p = var_on_left;
expr_op = linitial_oid(clause->opnos);
if (!var_on_left)
expr_op = get_commutator(expr_op);
get_op_opfamily_properties(expr_op, index->opfamily[indexcol], false,
&op_strategy,
&op_lefttype,
&op_righttype);
/* Initialize returned list of which index columns are used */
*indexcolnos = list_make1_int(indexcol);
/* Build lists of the opfamilies and operator datatypes in case needed */
opfamilies = list_make1_oid(index->opfamily[indexcol]);
lefttypes = list_make1_oid(op_lefttype);
righttypes = list_make1_oid(op_righttype);
/*
* See how many of the remaining columns match some index column in the
* same way. As in match_clause_to_indexcol(), the "other" side of any
* potential index condition is OK as long as it doesn't use Vars from the
* indexed relation.
*/
matching_cols = 1;
largs_cell = lnext(list_head(clause->largs));
rargs_cell = lnext(list_head(clause->rargs));
opnos_cell = lnext(list_head(clause->opnos));
collids_cell = lnext(list_head(clause->inputcollids));
while (largs_cell != NULL)
{
Node *varop;
Node *constop;
int i;
expr_op = lfirst_oid(opnos_cell);
if (var_on_left)
{
varop = (Node *) lfirst(largs_cell);
constop = (Node *) lfirst(rargs_cell);
}
else
{
varop = (Node *) lfirst(rargs_cell);
constop = (Node *) lfirst(largs_cell);
/* indexkey is on right, so commute the operator */
expr_op = get_commutator(expr_op);
if (expr_op == InvalidOid)
break; /* operator is not usable */
}
if (bms_is_member(index->rel->relid, pull_varnos(constop)))
break; /* no good, Var on wrong side */
if (contain_volatile_functions(constop))
break; /* no good, volatile comparison value */
/*
* The Var side can match any column of the index.
*/
for (i = 0; i < index->ncolumns; i++)
{
if (match_index_to_operand(varop, i, index) &&
get_op_opfamily_strategy(expr_op,
index->opfamily[i]) == op_strategy &&
IndexCollMatchesExprColl(index->indexcollations[i],
lfirst_oid(collids_cell)))
break;
}
if (i >= index->ncolumns)
break; /* no match found */
/* Add column number to returned list */
*indexcolnos = lappend_int(*indexcolnos, i);
/* Add opfamily and datatypes to lists */
get_op_opfamily_properties(expr_op, index->opfamily[i], false,
&op_strategy,
&op_lefttype,
&op_righttype);
opfamilies = lappend_oid(opfamilies, index->opfamily[i]);
lefttypes = lappend_oid(lefttypes, op_lefttype);
righttypes = lappend_oid(righttypes, op_righttype);
/* This column matches, keep scanning */
matching_cols++;
largs_cell = lnext(largs_cell);
rargs_cell = lnext(rargs_cell);
opnos_cell = lnext(opnos_cell);
collids_cell = lnext(collids_cell);
}
/* Return clause as-is if it's all usable as index quals */
if (matching_cols == list_length(clause->opnos))
return (Expr *) clause;
/*
* We have to generate a subset rowcompare (possibly just one OpExpr). The
* painful part of this is changing < to <= or > to >=, so deal with that
* first.
*/
if (op_strategy == BTLessEqualStrategyNumber ||
op_strategy == BTGreaterEqualStrategyNumber)
{
/* easy, just use the same operators */
new_ops = list_truncate(list_copy(clause->opnos), matching_cols);
}
else
{
ListCell *opfamilies_cell;
ListCell *lefttypes_cell;
ListCell *righttypes_cell;
if (op_strategy == BTLessStrategyNumber)
op_strategy = BTLessEqualStrategyNumber;
else if (op_strategy == BTGreaterStrategyNumber)
op_strategy = BTGreaterEqualStrategyNumber;
else
elog(ERROR, "unexpected strategy number %d", op_strategy);
new_ops = NIL;
lefttypes_cell = list_head(lefttypes);
righttypes_cell = list_head(righttypes);
foreach(opfamilies_cell, opfamilies)
{
Oid opfam = lfirst_oid(opfamilies_cell);
Oid lefttype = lfirst_oid(lefttypes_cell);
Oid righttype = lfirst_oid(righttypes_cell);
expr_op = get_opfamily_member(opfam, lefttype, righttype,
op_strategy);
if (!OidIsValid(expr_op)) /* should not happen */
elog(ERROR, "could not find member %d(%u,%u) of opfamily %u",
op_strategy, lefttype, righttype, opfam);
if (!var_on_left)
{
expr_op = get_commutator(expr_op);
if (!OidIsValid(expr_op)) /* should not happen */
elog(ERROR, "could not find commutator of member %d(%u,%u) of opfamily %u",
op_strategy, lefttype, righttype, opfam);
}
new_ops = lappend_oid(new_ops, expr_op);
lefttypes_cell = lnext(lefttypes_cell);
righttypes_cell = lnext(righttypes_cell);
}
}
/* If we have more than one matching col, create a subset rowcompare */
if (matching_cols > 1)
{
RowCompareExpr *rc = makeNode(RowCompareExpr);
if (var_on_left)
rc->rctype = (RowCompareType) op_strategy;
else
rc->rctype = (op_strategy == BTLessEqualStrategyNumber) ?
ROWCOMPARE_GE : ROWCOMPARE_LE;
rc->opnos = new_ops;
rc->opfamilies = list_truncate(list_copy(clause->opfamilies),
matching_cols);
rc->inputcollids = list_truncate(list_copy(clause->inputcollids),
matching_cols);
rc->largs = list_truncate((List *) copyObject(clause->largs),
matching_cols);
rc->rargs = list_truncate((List *) copyObject(clause->rargs),
matching_cols);
return (Expr *) rc;
}
else
{
return make_opclause(linitial_oid(new_ops), BOOLOID, false,
copyObject(linitial(clause->largs)),
copyObject(linitial(clause->rargs)),
InvalidOid,
linitial_oid(clause->inputcollids));
}
}
| List* build_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);
}
Definition at line 421 of file equivclass.c.
References arg, COERCE_IMPLICIT_CAST, exprCollation(), exprType(), exprTypmod(), IsA, IsPolymorphicType, and makeRelabelType().
Referenced by convert_subquery_pathkeys(), get_eclass_for_sort_expr(), and process_equivalence().
{
Oid expr_type = exprType((Node *) expr);
/*
* For a polymorphic-input-type opclass, just keep the same exposed type.
*/
if (IsPolymorphicType(req_type))
req_type = expr_type;
/*
* No work if the expression exposes the right type/collation already.
*/
if (expr_type != req_type ||
exprCollation((Node *) expr) != req_collation)
{
/*
* Strip any existing RelabelType, then add a new one if needed. This
* is to preserve the invariant of no redundant RelabelTypes.
*
* If we have to change the exposed type of the stripped expression,
* set typmod to -1 (since the new type may not have the same typmod
* interpretation). If we only have to change collation, preserve the
* exposed typmod.
*/
while (expr && IsA(expr, RelabelType))
expr = (Expr *) ((RelabelType *) expr)->arg;
if (exprType((Node *) expr) != req_type)
expr = (Expr *) makeRelabelType(expr,
req_type,
-1,
req_collation,
COERCE_IMPLICIT_CAST);
else if (exprCollation((Node *) expr) != req_collation)
expr = (Expr *) makeRelabelType(expr,
req_type,
exprTypmod((Node *) expr),
req_collation,
COERCE_IMPLICIT_CAST);
}
return expr;
}
| void check_partial_indexes | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel | |||
| ) |
Definition at line 2604 of file indxpath.c.
References PlannerInfo::all_baserels, RelOptInfo::baserestrictinfo, bms_difference(), bms_is_empty(), bms_make_singleton(), bms_union(), find_childrel_appendrelinfo(), generate_join_implied_equalities(), RelOptInfo::indexlist, IndexOptInfo::indpred, join_clause_is_movable_to(), RelOptInfo::joininfo, lappend(), lfirst, list_concat(), list_copy(), NIL, AppendRelInfo::parent_relid, predicate_implied_by(), IndexOptInfo::predOK, RelOptInfo::relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, and RelOptInfo::reloptkind.
Referenced by set_plain_rel_size().
{
List *clauselist;
bool have_partial;
Relids otherrels;
ListCell *lc;
/*
* Frequently, there will be no partial indexes, so first check to make
* sure there's something useful to do here.
*/
have_partial = false;
foreach(lc, rel->indexlist)
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
if (index->indpred == NIL)
continue; /* ignore non-partial indexes */
if (index->predOK)
continue; /* don't repeat work if already proven OK */
have_partial = true;
break;
}
if (!have_partial)
return;
/*
* Construct a list of clauses that we can assume true for the purpose
* of proving the index(es) usable. Restriction clauses for the rel are
* always usable, and so are any join clauses that are "movable to" this
* rel. Also, we can consider any EC-derivable join clauses (which must
* be "movable to" this rel, by definition).
*/
clauselist = list_copy(rel->baserestrictinfo);
/* Scan the rel's join clauses */
foreach(lc, rel->joininfo)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
/* Check if clause can be moved to this rel */
if (!join_clause_is_movable_to(rinfo, rel->relid))
continue;
clauselist = lappend(clauselist, rinfo);
}
/*
* Add on any equivalence-derivable join clauses. Computing the correct
* relid sets for generate_join_implied_equalities is slightly tricky
* because the rel could be a child rel rather than a true baserel, and
* in that case we must remove its parent's relid from all_baserels.
*/
if (rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
{
/* Lookup parent->child translation data */
AppendRelInfo *appinfo = find_childrel_appendrelinfo(root, rel);
otherrels = bms_difference(root->all_baserels,
bms_make_singleton(appinfo->parent_relid));
}
else
otherrels = bms_difference(root->all_baserels, rel->relids);
if (!bms_is_empty(otherrels))
clauselist =
list_concat(clauselist,
generate_join_implied_equalities(root,
bms_union(rel->relids,
otherrels),
otherrels,
rel));
/* Now try to prove each index predicate true */
foreach(lc, rel->indexlist)
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
if (index->indpred == NIL)
continue; /* ignore non-partial indexes */
if (index->predOK)
continue; /* don't repeat work if already proven OK */
index->predOK = predicate_implied_by(index->indpred, clauselist);
}
}
| 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;
}
| void create_index_paths | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel | |||
| ) |
Definition at line 233 of file indxpath.c.
References add_path(), Assert, RelOptInfo::baserestrictinfo, bms_add_member(), bms_equal_any(), bms_is_member(), bms_is_subset(), choose_bitmap_and(), consider_index_join_clauses(), create_bitmap_heap_path(), forboth, generate_bitmap_or_paths(), get_bitmap_tree_required_outer(), get_index_paths(), get_loop_count(), INDEX_MAX_KEYS, RelOptInfo::indexlist, IndexOptInfo::indpred, lappend(), PlannerInfo::lateral_info_list, LateralJoinInfo::lateral_lhs, RelOptInfo::lateral_relids, LateralJoinInfo::lateral_rhs, lfirst, list_concat(), match_eclass_clauses_to_index(), match_join_clauses_to_index(), match_restriction_clauses_to_index(), MemSet, IndexOptInfo::ncolumns, NIL, IndexClauseSet::nonempty, IndexOptInfo::predOK, and RelOptInfo::relid.
Referenced by set_plain_rel_pathlist().
{
List *indexpaths;
List *bitindexpaths;
List *bitjoinpaths;
List *joinorclauses;
Relids lateral_referencers;
IndexClauseSet rclauseset;
IndexClauseSet jclauseset;
IndexClauseSet eclauseset;
ListCell *lc;
/* Skip the whole mess if no indexes */
if (rel->indexlist == NIL)
return;
/*
* If there are any rels that have LATERAL references to this one, we
* cannot use join quals referencing them as index quals for this one,
* since such rels would have to be on the inside not the outside of a
* nestloop join relative to this one. Create a Relids set listing all
* such rels, for use in checks of potential join clauses.
*/
lateral_referencers = NULL;
foreach(lc, root->lateral_info_list)
{
LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(lc);
if (bms_is_member(rel->relid, ljinfo->lateral_lhs))
lateral_referencers = bms_add_member(lateral_referencers,
ljinfo->lateral_rhs);
}
/* Bitmap paths are collected and then dealt with at the end */
bitindexpaths = bitjoinpaths = joinorclauses = NIL;
/* Examine each index in turn */
foreach(lc, rel->indexlist)
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
/* Protect limited-size array in IndexClauseSets */
Assert(index->ncolumns <= INDEX_MAX_KEYS);
/*
* Ignore partial indexes that do not match the query.
* (generate_bitmap_or_paths() might be able to do something with
* them, but that's of no concern here.)
*/
if (index->indpred != NIL && !index->predOK)
continue;
/*
* Identify the restriction clauses that can match the index.
*/
MemSet(&rclauseset, 0, sizeof(rclauseset));
match_restriction_clauses_to_index(rel, index, &rclauseset);
/*
* Build index paths from the restriction clauses. These will be
* non-parameterized paths. Plain paths go directly to add_path(),
* bitmap paths are added to bitindexpaths to be handled below.
*/
get_index_paths(root, rel, index, &rclauseset,
&bitindexpaths);
/*
* Identify the join clauses that can match the index. For the moment
* we keep them separate from the restriction clauses. Note that this
* step finds only "loose" join clauses that have not been merged into
* EquivalenceClasses. Also, collect join OR clauses for later.
*/
MemSet(&jclauseset, 0, sizeof(jclauseset));
match_join_clauses_to_index(root, rel, index, lateral_referencers,
&jclauseset, &joinorclauses);
/*
* Look for EquivalenceClasses that can generate joinclauses matching
* the index.
*/
MemSet(&eclauseset, 0, sizeof(eclauseset));
match_eclass_clauses_to_index(root, index, lateral_referencers,
&eclauseset);
/*
* If we found any plain or eclass join clauses, build parameterized
* index paths using them.
*/
if (jclauseset.nonempty || eclauseset.nonempty)
consider_index_join_clauses(root, rel, index,
&rclauseset,
&jclauseset,
&eclauseset,
&bitjoinpaths);
}
/*
* Generate BitmapOrPaths for any suitable OR-clauses present in the
* restriction list. Add these to bitindexpaths.
*/
indexpaths = generate_bitmap_or_paths(root, rel,
rel->baserestrictinfo, NIL,
false);
bitindexpaths = list_concat(bitindexpaths, indexpaths);
/*
* Likewise, generate BitmapOrPaths for any suitable OR-clauses present in
* the joinclause list. Add these to bitjoinpaths.
*/
indexpaths = generate_bitmap_or_paths(root, rel,
joinorclauses, rel->baserestrictinfo,
false);
bitjoinpaths = list_concat(bitjoinpaths, indexpaths);
/*
* If we found anything usable, generate a BitmapHeapPath for the most
* promising combination of restriction bitmap index paths. Note there
* will be only one such path no matter how many indexes exist. This
* should be sufficient since there's basically only one figure of merit
* (total cost) for such a path.
*/
if (bitindexpaths != NIL)
{
Path *bitmapqual;
BitmapHeapPath *bpath;
bitmapqual = choose_bitmap_and(root, rel, bitindexpaths);
bpath = create_bitmap_heap_path(root, rel, bitmapqual,
rel->lateral_relids, 1.0);
add_path(rel, (Path *) bpath);
}
/*
* Likewise, if we found anything usable, generate BitmapHeapPaths for the
* most promising combinations of join bitmap index paths. Our strategy
* is to generate one such path for each distinct parameterization seen
* among the available bitmap index paths. This may look pretty
* expensive, but usually there won't be very many distinct
* parameterizations. (This logic is quite similar to that in
* consider_index_join_clauses, but we're working with whole paths not
* individual clauses.)
*/
if (bitjoinpaths != NIL)
{
List *path_outer;
List *all_path_outers;
ListCell *lc;
/*
* path_outer holds the parameterization of each path in bitjoinpaths
* (to save recalculating that several times), while all_path_outers
* holds all distinct parameterization sets.
*/
path_outer = all_path_outers = NIL;
foreach(lc, bitjoinpaths)
{
Path *path = (Path *) lfirst(lc);
Relids required_outer;
required_outer = get_bitmap_tree_required_outer(path);
path_outer = lappend(path_outer, required_outer);
if (!bms_equal_any(required_outer, all_path_outers))
all_path_outers = lappend(all_path_outers, required_outer);
}
/* Now, for each distinct parameterization set ... */
foreach(lc, all_path_outers)
{
Relids max_outers = (Relids) lfirst(lc);
List *this_path_set;
Path *bitmapqual;
Relids required_outer;
double loop_count;
BitmapHeapPath *bpath;
ListCell *lcp;
ListCell *lco;
/* Identify all the bitmap join paths needing no more than that */
this_path_set = NIL;
forboth(lcp, bitjoinpaths, lco, path_outer)
{
Path *path = (Path *) lfirst(lcp);
Relids p_outers = (Relids) lfirst(lco);
if (bms_is_subset(p_outers, max_outers))
this_path_set = lappend(this_path_set, path);
}
/*
* Add in restriction bitmap paths, since they can be used
* together with any join paths.
*/
this_path_set = list_concat(this_path_set, bitindexpaths);
/* Select best AND combination for this parameterization */
bitmapqual = choose_bitmap_and(root, rel, this_path_set);
/* And push that path into the mix */
required_outer = get_bitmap_tree_required_outer(bitmapqual);
loop_count = get_loop_count(root, required_outer);
bpath = create_bitmap_heap_path(root, rel, bitmapqual,
required_outer, loop_count);
add_path(rel, (Path *) bpath);
}
}
}
| bool create_or_index_quals | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel | |||
| ) |
Definition at line 81 of file orindxpath.c.
References Assert, RelOptInfo::baserestrictinfo, clause_selectivity(), generate_bitmap_or_paths(), i, RelOptInfo::indexlist, IsA, join_clause_is_movable_to(), JOIN_INNER, RelOptInfo::joininfo, lfirst, linitial, list_concat(), list_length(), list_make1, make_restrictinfo_from_bitmapqual(), NIL, NULL, BitmapOrPath::path, RelOptInfo::relid, restriction_is_or_clause(), and Path::total_cost.
Referenced by set_plain_rel_size().
{
BitmapOrPath *bestpath = NULL;
RestrictInfo *bestrinfo = NULL;
List *newrinfos;
RestrictInfo *or_rinfo;
Selectivity or_selec,
orig_selec;
ListCell *i;
/* Skip the whole mess if no indexes */
if (rel->indexlist == NIL)
return false;
/*
* Find potentially interesting OR joinclauses. We can use any joinclause
* that is considered safe to move to this rel by the parameterized-path
* machinery, even though what we are going to do with it is not exactly a
* parameterized path.
*/
foreach(i, rel->joininfo)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
if (restriction_is_or_clause(rinfo) &&
join_clause_is_movable_to(rinfo, rel->relid))
{
/*
* Use the generate_bitmap_or_paths() machinery to estimate the
* value of each OR clause. We can use regular restriction
* clauses along with the OR clause contents to generate
* indexquals. We pass restriction_only = true so that any
* sub-clauses that are actually joins will be ignored.
*/
List *orpaths;
ListCell *k;
orpaths = generate_bitmap_or_paths(root, rel,
list_make1(rinfo),
rel->baserestrictinfo,
true);
/* Locate the cheapest OR path */
foreach(k, orpaths)
{
BitmapOrPath *path = (BitmapOrPath *) lfirst(k);
Assert(IsA(path, BitmapOrPath));
if (bestpath == NULL ||
path->path.total_cost < bestpath->path.total_cost)
{
bestpath = path;
bestrinfo = rinfo;
}
}
}
}
/* Fail if no suitable clauses found */
if (bestpath == NULL)
return false;
/*
* Convert the path's indexclauses structure to a RestrictInfo tree. We
* include any partial-index predicates so as to get a reasonable
* representation of what the path is actually scanning.
*/
newrinfos = make_restrictinfo_from_bitmapqual((Path *) bestpath,
true, true);
/* It's possible we get back something other than a single OR clause */
if (list_length(newrinfos) != 1)
return false;
or_rinfo = (RestrictInfo *) linitial(newrinfos);
Assert(IsA(or_rinfo, RestrictInfo));
if (!restriction_is_or_clause(or_rinfo))
return false;
/*
* OK, add it to the rel's restriction list.
*/
rel->baserestrictinfo = list_concat(rel->baserestrictinfo, newrinfos);
/*
* Adjust the original OR clause's cached selectivity to compensate for
* the selectivity of the added (but redundant) lower-level qual. This
* should result in the join rel getting approximately the same rows
* estimate as it would have gotten without all these shenanigans. (XXX
* major hack alert ... this depends on the assumption that the
* selectivity will stay cached ...)
*/
or_selec = clause_selectivity(root, (Node *) or_rinfo,
0, JOIN_INNER, NULL);
if (or_selec > 0 && or_selec < 1)
{
orig_selec = clause_selectivity(root, (Node *) bestrinfo,
0, JOIN_INNER, NULL);
bestrinfo->norm_selec = orig_selec / or_selec;
/* clamp result to sane range */
if (bestrinfo->norm_selec > 1)
bestrinfo->norm_selec = 1;
/* It isn't an outer join clause, so no need to adjust outer_selec */
}
/* Tell caller to recompute partial index status and rowcount estimate */
return true;
}
| void create_tidscan_paths | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel | |||
| ) |
Definition at line 250 of file tidpath.c.
References add_path(), RelOptInfo::baserestrictinfo, create_tidscan_path(), RelOptInfo::lateral_relids, RelOptInfo::relid, and TidQualFromRestrictinfo().
Referenced by set_plain_rel_pathlist().
{
Relids required_outer;
List *tidquals;
/*
* We don't support pushing join clauses into the quals of a tidscan, but
* it could still have required parameterization due to LATERAL refs in
* its tlist. (That can only happen if the tidscan is on a relation
* pulled up out of a UNION ALL appendrel.)
*/
required_outer = rel->lateral_relids;
tidquals = TidQualFromRestrictinfo(rel->baserestrictinfo, rel->relid);
if (tidquals)
add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
required_outer));
}
| bool eclass_useful_for_merging | ( | EquivalenceClass * | eclass, | |
| RelOptInfo * | rel | |||
| ) |
Definition at line 2268 of file equivclass.c.
References Assert, bms_is_subset(), bms_overlap(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_relids, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, lfirst, list_length(), and RelOptInfo::relids.
Referenced by pathkeys_useful_for_merging().
{
ListCell *lc;
Assert(!eclass->ec_merged);
/*
* Won't generate joinclauses if const or single-member (the latter test
* covers the volatile case too)
*/
if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1)
return false;
/*
* Note we don't test ec_broken; if we did, we'd need a separate code path
* to look through ec_sources. Checking the members anyway is OK as a
* possibly-overoptimistic heuristic.
*/
/* If rel already includes all members of eclass, no point in searching */
if (bms_is_subset(eclass->ec_relids, rel->relids))
return false;
/* To join, we need a member not in the given rel */
foreach(lc, eclass->ec_members)
{
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
if (cur_em->em_is_child)
continue; /* ignore children here */
if (!bms_overlap(cur_em->em_relids, rel->relids))
return true;
}
return false;
}
| void expand_indexqual_conditions | ( | IndexOptInfo * | index, | |
| List * | indexclauses, | |||
| List * | indexclausecols, | |||
| List ** | indexquals_p, | |||
| List ** | indexqualcols_p | |||
| ) |
Definition at line 3278 of file indxpath.c.
References IndexOptInfo::amsearchnulls, Assert, RestrictInfo::clause, elog, ERROR, expand_boolean_index_clause(), expand_indexqual_opclause(), expand_indexqual_rowcompare(), forboth, IndexOptInfo::indexcollations, is_opclause, IsA, IsBooleanOpfamily, lappend(), lappend_int(), lfirst, lfirst_int, list_concat(), list_length(), make_simple_restrictinfo, nodeTag, and IndexOptInfo::opfamily.
Referenced by create_index_path().
{
List *indexquals = NIL;
List *indexqualcols = NIL;
ListCell *lcc,
*lci;
forboth(lcc, indexclauses, lci, indexclausecols)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcc);
int indexcol = lfirst_int(lci);
Expr *clause = rinfo->clause;
Oid curFamily = index->opfamily[indexcol];
Oid curCollation = index->indexcollations[indexcol];
/* First check for boolean cases */
if (IsBooleanOpfamily(curFamily))
{
Expr *boolqual;
boolqual = expand_boolean_index_clause((Node *) clause,
indexcol,
index);
if (boolqual)
{
indexquals = lappend(indexquals,
make_simple_restrictinfo(boolqual));
indexqualcols = lappend_int(indexqualcols, indexcol);
continue;
}
}
/*
* Else it must be an opclause (usual case), ScalarArrayOp,
* RowCompare, or NullTest
*/
if (is_opclause(clause))
{
indexquals = list_concat(indexquals,
expand_indexqual_opclause(rinfo,
curFamily,
curCollation));
/* expand_indexqual_opclause can produce multiple clauses */
while (list_length(indexqualcols) < list_length(indexquals))
indexqualcols = lappend_int(indexqualcols, indexcol);
}
else if (IsA(clause, ScalarArrayOpExpr))
{
/* no extra work at this time */
indexquals = lappend(indexquals, rinfo);
indexqualcols = lappend_int(indexqualcols, indexcol);
}
else if (IsA(clause, RowCompareExpr))
{
indexquals = lappend(indexquals,
expand_indexqual_rowcompare(rinfo,
index,
indexcol));
indexqualcols = lappend_int(indexqualcols, indexcol);
}
else if (IsA(clause, NullTest))
{
Assert(index->amsearchnulls);
indexquals = lappend(indexquals, rinfo);
indexqualcols = lappend_int(indexqualcols, indexcol);
}
else
elog(ERROR, "unsupported indexqual type: %d",
(int) nodeTag(clause));
}
*indexquals_p = indexquals;
*indexqualcols_p = indexqualcols;
}
| bool exprs_known_equal | ( | PlannerInfo * | root, | |
| Node * | item1, | |||
| Node * | item2 | |||
| ) |
Definition at line 1859 of file equivclass.c.
References EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, equal(), and lfirst.
Referenced by add_unique_group_var().
{
ListCell *lc1;
foreach(lc1, root->eq_classes)
{
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
bool item1member = false;
bool item2member = false;
ListCell *lc2;
/* Never match to a volatile EC */
if (ec->ec_has_volatile)
continue;
foreach(lc2, ec->ec_members)
{
EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
if (em->em_is_child)
continue; /* ignore children here */
if (equal(item1, em->em_expr))
item1member = true;
else if (equal(item2, em->em_expr))
item2member = true;
/* Exit as soon as equality is proven */
if (item1member && item2member)
return true;
}
}
return false;
}
| List* find_mergeclauses_for_pathkeys | ( | PlannerInfo * | root, | |
| List * | pathkeys, | |||
| bool | outer_keys, | |||
| List * | restrictinfos | |||
| ) |
Definition at line 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;
}
| void generate_base_implied_equalities | ( | PlannerInfo * | root | ) |
Definition at line 710 of file equivclass.c.
References Assert, EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, PlannerInfo::eq_classes, generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), RelOptInfo::has_eclass_joins, has_relevant_eclass_joinclause(), lfirst, list_length(), NULL, PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.
Referenced by query_planner().
{
ListCell *lc;
Index rti;
foreach(lc, root->eq_classes)
{
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
Assert(ec->ec_merged == NULL); /* else shouldn't be in list */
Assert(!ec->ec_broken); /* not yet anyway... */
/* Single-member ECs won't generate any deductions */
if (list_length(ec->ec_members) <= 1)
continue;
if (ec->ec_has_const)
generate_base_implied_equalities_const(root, ec);
else
generate_base_implied_equalities_no_const(root, ec);
/* Recover if we failed to generate required derived clauses */
if (ec->ec_broken)
generate_base_implied_equalities_broken(root, ec);
}
/*
* This is also a handy place to mark base rels (which should all exist by
* now) with flags showing whether they have pending eclass joins.
*/
for (rti = 1; rti < root->simple_rel_array_size; rti++)
{
RelOptInfo *brel = root->simple_rel_array[rti];
if (brel == NULL)
continue;
brel->has_eclass_joins = has_relevant_eclass_joinclause(root, brel);
}
}
| List* generate_bitmap_or_paths | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel, | |||
| List * | clauses, | |||
| List * | other_clauses, | |||
| bool | restriction_only | |||
| ) |
Definition at line 1184 of file indxpath.c.
References and_clause(), Assert, build_paths_for_OR(), choose_bitmap_and(), create_bitmap_or_path(), drop_indexable_join_clauses(), generate_bitmap_or_paths(), IsA, lappend(), lfirst, list_concat(), list_copy(), list_make1, NIL, RestrictInfo::orclause, and restriction_is_or_clause().
Referenced by create_index_paths(), create_or_index_quals(), and generate_bitmap_or_paths().
{
List *result = NIL;
List *all_clauses;
ListCell *lc;
/*
* We can use both the current and other clauses as context for
* build_paths_for_OR; no need to remove ORs from the lists.
*/
all_clauses = list_concat(list_copy(clauses), other_clauses);
foreach(lc, clauses)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
List *pathlist;
Path *bitmapqual;
ListCell *j;
Assert(IsA(rinfo, RestrictInfo));
/* Ignore RestrictInfos that aren't ORs */
if (!restriction_is_or_clause(rinfo))
continue;
/*
* We must be able to match at least one index to each of the arms of
* the OR, else we can't use it.
*/
pathlist = NIL;
foreach(j, ((BoolExpr *) rinfo->orclause)->args)
{
Node *orarg = (Node *) lfirst(j);
List *indlist;
/* OR arguments should be ANDs or sub-RestrictInfos */
if (and_clause(orarg))
{
List *andargs = ((BoolExpr *) orarg)->args;
if (restriction_only)
andargs = drop_indexable_join_clauses(rel, andargs);
indlist = build_paths_for_OR(root, rel,
andargs,
all_clauses);
/* Recurse in case there are sub-ORs */
indlist = list_concat(indlist,
generate_bitmap_or_paths(root, rel,
andargs,
all_clauses,
restriction_only));
}
else
{
List *orargs;
Assert(IsA(orarg, RestrictInfo));
Assert(!restriction_is_or_clause((RestrictInfo *) orarg));
orargs = list_make1(orarg);
if (restriction_only)
orargs = drop_indexable_join_clauses(rel, orargs);
indlist = build_paths_for_OR(root, rel,
orargs,
all_clauses);
}
/*
* If nothing matched this arm, we can't do anything with this OR
* clause.
*/
if (indlist == NIL)
{
pathlist = NIL;
break;
}
/*
* OK, pick the most promising AND combination, and add it to
* pathlist.
*/
bitmapqual = choose_bitmap_and(root, rel, indlist);
pathlist = lappend(pathlist, bitmapqual);
}
/*
* If we have a match for every arm, then turn them into a
* BitmapOrPath, and add to result list.
*/
if (pathlist != NIL)
{
bitmapqual = (Path *) create_bitmap_or_path(root, rel, pathlist);
result = lappend(result, bitmapqual);
}
}
return result;
}
| List* generate_implied_equalities_for_column | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel, | |||
| ec_matches_callback_type | callback, | |||
| void * | callback_arg, | |||
| Relids | prohibited_rels | |||
| ) |
Definition at line 2047 of file equivclass.c.
References bms_equal(), bms_is_member(), bms_is_subset(), bms_overlap(), callback(), create_join_clause(), EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceMember::em_datatype, EquivalenceMember::em_is_child, EquivalenceMember::em_relids, PlannerInfo::eq_classes, find_childrel_appendrelinfo(), lappend(), lfirst, list_length(), OidIsValid, AppendRelInfo::parent_relid, RelOptInfo::relids, RelOptInfo::reloptkind, and select_equality_operator().
Referenced by match_eclass_clauses_to_index(), and postgresGetForeignPaths().
{
List *result = NIL;
bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
Index parent_relid;
ListCell *lc1;
/* If it's a child rel, we'll need to know what its parent is */
if (is_child_rel)
parent_relid = find_childrel_appendrelinfo(root, rel)->parent_relid;
else
parent_relid = 0; /* not used, but keep compiler quiet */
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
EquivalenceMember *cur_em;
ListCell *lc2;
/*
* Won't generate joinclauses if const or single-member (the latter
* test covers the volatile case too)
*/
if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1)
continue;
/*
* No point in searching if rel not mentioned in eclass (but we can't
* tell that for a child rel).
*/
if (!is_child_rel &&
!bms_is_subset(rel->relids, cur_ec->ec_relids))
continue;
/*
* Scan members, looking for a match to the target column. Note
* that child EC members are considered, but only when they belong to
* the target relation. (Unlike regular members, the same expression
* could be a child member of more than one EC. Therefore, it's
* potentially order-dependent which EC a child relation's target
* column gets matched to. This is annoying but it only happens in
* corner cases, so for now we live with just reporting the first
* match. See also get_eclass_for_sort_expr.)
*/
cur_em = NULL;
foreach(lc2, cur_ec->ec_members)
{
cur_em = (EquivalenceMember *) lfirst(lc2);
if (bms_equal(cur_em->em_relids, rel->relids) &&
callback(root, rel, cur_ec, cur_em, callback_arg))
break;
cur_em = NULL;
}
if (!cur_em)
continue;
/*
* Found our match. Scan the other EC members and attempt to generate
* joinclauses.
*/
foreach(lc2, cur_ec->ec_members)
{
EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
Oid eq_op;
RestrictInfo *rinfo;
if (other_em->em_is_child)
continue; /* ignore children here */
/* Make sure it'll be a join to a different rel */
if (other_em == cur_em ||
bms_overlap(other_em->em_relids, rel->relids))
continue;
/* Forget it if caller doesn't want joins to this rel */
if (bms_overlap(other_em->em_relids, prohibited_rels))
continue;
/*
* Also, if this is a child rel, avoid generating a useless join
* to its parent rel.
*/
if (is_child_rel &&
bms_is_member(parent_relid, other_em->em_relids))
continue;
eq_op = select_equality_operator(cur_ec,
cur_em->em_datatype,
other_em->em_datatype);
if (!OidIsValid(eq_op))
continue;
/* set parent_ec to mark as redundant with other joinclauses */
rinfo = create_join_clause(root, cur_ec, eq_op,
cur_em, other_em,
cur_ec);
result = lappend(result, rinfo);
}
/*
* If somehow we failed to create any join clauses, we might as well
* keep scanning the ECs for another match. But if we did make any,
* we're done, because we don't want to return non-redundant clauses.
*/
if (result)
break;
}
return result;
}
| List* generate_join_implied_equalities | ( | PlannerInfo * | root, | |
| Relids | join_relids, | |||
| Relids | outer_relids, | |||
| RelOptInfo * | inner_rel | |||
| ) |
Definition at line 979 of file equivclass.c.
References bms_make_singleton(), bms_overlap(), bms_union(), EquivalenceClass::ec_broken, EquivalenceClass::ec_has_const, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, find_childrel_appendrelinfo(), generate_join_implied_equalities_broken(), generate_join_implied_equalities_normal(), lfirst, list_concat(), list_length(), AppendRelInfo::parent_relid, RelOptInfo::relids, RELOPT_OTHER_MEMBER_REL, and RelOptInfo::reloptkind.
Referenced by build_joinrel_restrictlist(), check_partial_indexes(), get_baserel_parampathinfo(), and get_joinrel_parampathinfo().
{
List *result = NIL;
Relids inner_relids = inner_rel->relids;
Relids nominal_inner_relids;
Relids nominal_join_relids;
AppendRelInfo *inner_appinfo;
ListCell *lc;
/* If inner rel is a child, extra setup work is needed */
if (inner_rel->reloptkind == RELOPT_OTHER_MEMBER_REL)
{
/* Lookup parent->child translation data */
inner_appinfo = find_childrel_appendrelinfo(root, inner_rel);
/* Construct relids for the parent rel */
nominal_inner_relids = bms_make_singleton(inner_appinfo->parent_relid);
/* ECs will be marked with the parent's relid, not the child's */
nominal_join_relids = bms_union(outer_relids, nominal_inner_relids);
}
else
{
inner_appinfo = NULL;
nominal_inner_relids = inner_relids;
nominal_join_relids = join_relids;
}
foreach(lc, root->eq_classes)
{
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
List *sublist = NIL;
/* ECs containing consts do not need any further enforcement */
if (ec->ec_has_const)
continue;
/* Single-member ECs won't generate any deductions */
if (list_length(ec->ec_members) <= 1)
continue;
/* We can quickly ignore any that don't overlap the join, too */
if (!bms_overlap(ec->ec_relids, nominal_join_relids))
continue;
if (!ec->ec_broken)
sublist = generate_join_implied_equalities_normal(root,
ec,
join_relids,
outer_relids,
inner_relids);
/* Recover if we failed to generate required derived clauses */
if (ec->ec_broken)
sublist = generate_join_implied_equalities_broken(root,
ec,
nominal_join_relids,
outer_relids,
nominal_inner_relids,
inner_appinfo);
result = list_concat(result, sublist);
}
return result;
}
| Path* get_cheapest_fractional_path_for_pathkeys | ( | List * | paths, | |
| List * | pathkeys, | |||
| Relids | required_outer, | |||
| double | fraction | |||
| ) |
Definition at line 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;
}
| EquivalenceClass* get_eclass_for_sort_expr | ( | PlannerInfo * | root, | |
| Expr * | expr, | |||
| List * | opfamilies, | |||
| Oid | opcintype, | |||
| Oid | collation, | |||
| Index | sortref, | |||
| Relids | rel, | |||
| bool | create_it | |||
| ) |
Definition at line 539 of file equivclass.c.
References add_eq_member(), bms_equal(), canonicalize_ec_expression(), contain_agg_clause(), contain_volatile_functions(), contain_window_function(), copyObject(), EquivalenceClass::ec_below_outer_join, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, EquivalenceMember::em_relids, PlannerInfo::eq_classes, equal(), ERROR, expression_returns_set(), lappend(), lfirst, list_copy(), makeNode, MemoryContextSwitchTo(), NULL, PlannerInfo::planner_cxt, and pull_varnos().
Referenced by convert_subquery_pathkeys(), initialize_mergeclause_eclasses(), and make_pathkey_from_sortinfo().
{
EquivalenceClass *newec;
EquivalenceMember *newem;
ListCell *lc1;
MemoryContext oldcontext;
/*
* Ensure the expression exposes the correct type and collation.
*/
expr = canonicalize_ec_expression(expr, opcintype, collation);
/*
* Scan through the existing EquivalenceClasses for a match
*/
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
ListCell *lc2;
/*
* Never match to a volatile EC, except when we are looking at another
* reference to the same volatile SortGroupClause.
*/
if (cur_ec->ec_has_volatile &&
(sortref == 0 || sortref != cur_ec->ec_sortref))
continue;
if (collation != cur_ec->ec_collation)
continue;
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
foreach(lc2, cur_ec->ec_members)
{
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
/*
* Ignore child members unless they match the request.
*/
if (cur_em->em_is_child &&
!bms_equal(cur_em->em_relids, rel))
continue;
/*
* If below an outer join, don't match constants: they're not as
* constant as they look.
*/
if (cur_ec->ec_below_outer_join &&
cur_em->em_is_const)
continue;
if (opcintype == cur_em->em_datatype &&
equal(expr, cur_em->em_expr))
return cur_ec; /* Match! */
}
}
/* No match; does caller want a NULL result? */
if (!create_it)
return NULL;
/*
* OK, build a new single-member EC
*
* Here, we must be sure that we construct the EC in the right context.
*/
oldcontext = MemoryContextSwitchTo(root->planner_cxt);
newec = makeNode(EquivalenceClass);
newec->ec_opfamilies = list_copy(opfamilies);
newec->ec_collation = collation;
newec->ec_members = NIL;
newec->ec_sources = NIL;
newec->ec_derives = NIL;
newec->ec_relids = NULL;
newec->ec_has_const = false;
newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
newec->ec_below_outer_join = false;
newec->ec_broken = false;
newec->ec_sortref = sortref;
newec->ec_merged = NULL;
if (newec->ec_has_volatile && sortref == 0) /* should not happen */
elog(ERROR, "volatile EquivalenceClass has no sortref");
newem = add_eq_member(newec, copyObject(expr), pull_varnos((Node *) expr),
NULL, false, opcintype);
/*
* add_eq_member doesn't check for volatile functions, set-returning
* functions, aggregates, or window functions, but such could appear in
* sort expressions; so we have to check whether its const-marking was
* correct.
*/
if (newec->ec_has_const)
{
if (newec->ec_has_volatile ||
expression_returns_set((Node *) expr) ||
contain_agg_clause((Node *) expr) ||
contain_window_function((Node *) expr))
{
newec->ec_has_const = false;
newem->em_is_const = false;
}
}
root->eq_classes = lappend(root->eq_classes, newec);
MemoryContextSwitchTo(oldcontext);
return newec;
}
| bool has_relevant_eclass_joinclause | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel1 | |||
| ) |
Definition at line 2229 of file equivclass.c.
References bms_is_subset(), bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, lfirst, list_length(), and RelOptInfo::relids.
Referenced by build_join_rel(), and generate_base_implied_equalities().
{
ListCell *lc1;
foreach(lc1, root->eq_classes)
{
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
/*
* Won't generate joinclauses if single-member (this test covers the
* volatile case too)
*/
if (list_length(ec->ec_members) <= 1)
continue;
/*
* Per the comment in have_relevant_eclass_joinclause, it's sufficient
* to find an EC that mentions both this rel and some other rel.
*/
if (bms_overlap(rel1->relids, ec->ec_relids) &&
!bms_is_subset(ec->ec_relids, rel1->relids))
return true;
}
return false;
}
| bool has_useful_pathkeys | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel | |||
| ) |
Definition at line 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 */
}
| bool have_join_order_restriction | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel1, | |||
| RelOptInfo * | rel2 | |||
| ) |
Definition at line 818 of file joinrels.c.
References bms_is_member(), bms_is_subset(), bms_overlap(), has_legal_joinclause(), JOIN_FULL, PlannerInfo::join_info_list, SpecialJoinInfo::jointype, PlannerInfo::lateral_info_list, LateralJoinInfo::lateral_lhs, LateralJoinInfo::lateral_rhs, lfirst, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, and RelOptInfo::relids.
Referenced by desirable_join(), join_search_one_level(), and make_rels_by_clause_joins().
{
bool result = false;
ListCell *l;
/*
* If either side has a lateral reference to the other, attempt the join
* regardless of outer-join considerations.
*/
foreach(l, root->lateral_info_list)
{
LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);
if (bms_is_member(ljinfo->lateral_rhs, rel2->relids) &&
bms_overlap(ljinfo->lateral_lhs, rel1->relids))
return true;
if (bms_is_member(ljinfo->lateral_rhs, rel1->relids) &&
bms_overlap(ljinfo->lateral_lhs, rel2->relids))
return true;
}
/*
* It's possible that the rels correspond to the left and right sides of a
* degenerate outer join, that is, one with no joinclause mentioning the
* non-nullable side; in which case we should force the join to occur.
*
* Also, the two rels could represent a clauseless join that has to be
* completed to build up the LHS or RHS of an outer join.
*/
foreach(l, root->join_info_list)
{
SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
/* ignore full joins --- other mechanisms handle them */
if (sjinfo->jointype == JOIN_FULL)
continue;
/* Can we perform the SJ with these rels? */
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
bms_is_subset(sjinfo->min_righthand, rel2->relids))
{
result = true;
break;
}
if (bms_is_subset(sjinfo->min_lefthand, rel2->relids) &&
bms_is_subset(sjinfo->min_righthand, rel1->relids))
{
result = true;
break;
}
/*
* Might we need to join these rels to complete the RHS? We have to
* use "overlap" tests since either rel might include a lower SJ that
* has been proven to commute with this one.
*/
if (bms_overlap(sjinfo->min_righthand, rel1->relids) &&
bms_overlap(sjinfo->min_righthand, rel2->relids))
{
result = true;
break;
}
/* Likewise for the LHS. */
if (bms_overlap(sjinfo->min_lefthand, rel1->relids) &&
bms_overlap(sjinfo->min_lefthand, rel2->relids))
{
result = true;
break;
}
}
/*
* We do not force the join to occur if either input rel can legally be
* joined to anything else using joinclauses. This essentially means that
* clauseless bushy joins are put off as long as possible. The reason is
* that when there is a join order restriction high up in the join tree
* (that is, with many rels inside the LHS or RHS), we would otherwise
* expend lots of effort considering very stupid join combinations within
* its LHS or RHS.
*/
if (result)
{
if (has_legal_joinclause(root, rel1) ||
has_legal_joinclause(root, rel2))
result = false;
}
return result;
}
| bool have_relevant_eclass_joinclause | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel1, | |||
| RelOptInfo * | rel2 | |||
| ) |
Definition at line 2175 of file equivclass.c.
References bms_overlap(), EquivalenceClass::ec_members, EquivalenceClass::ec_relids, PlannerInfo::eq_classes, lfirst, list_length(), and RelOptInfo::relids.
Referenced by have_relevant_joinclause().
{
ListCell *lc1;
foreach(lc1, root->eq_classes)
{
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
/*
* Won't generate joinclauses if single-member (this test covers the
* volatile case too)
*/
if (list_length(ec->ec_members) <= 1)
continue;
/*
* We do not need to examine the individual members of the EC, because
* all that we care about is whether each rel overlaps the relids of
* at least one member, and a test on ec_relids is sufficient to prove
* that. (As with have_relevant_joinclause(), it is not necessary
* that the EC be able to form a joinclause relating exactly the two
* given rels, only that it be able to form a joinclause mentioning
* both, and this will surely be true if both of them overlap
* ec_relids.)
*
* Note we don't test ec_broken; if we did, we'd need a separate code
* path to look through ec_sources. Checking the membership anyway is
* OK as a possibly-overoptimistic heuristic.
*
* We don't test ec_has_const either, even though a const eclass won't
* generate real join clauses. This is because if we had "WHERE a.x =
* b.y and a.x = 42", it is worth considering a join between a and b,
* since the join result is likely to be small even though it'll end
* up being an unqualified nestloop.
*/
if (bms_overlap(rel1->relids, ec->ec_relids) &&
bms_overlap(rel2->relids, ec->ec_relids))
return true;
}
return false;
}
| 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);
}
| bool is_redundant_derived_clause | ( | RestrictInfo * | rinfo, | |
| List * | clauselist | |||
| ) |
Definition at line 2315 of file equivclass.c.
References lfirst, NULL, and RestrictInfo::parent_ec.
Referenced by create_indexscan_plan(), and has_indexed_join_quals().
{
EquivalenceClass *parent_ec = rinfo->parent_ec;
ListCell *lc;
/* Fail if it's not a potentially-redundant clause from some EC */
if (parent_ec == NULL)
return false;
foreach(lc, clauselist)
{
RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc);
if (otherrinfo->parent_ec == parent_ec)
return true;
}
return false;
}
| void join_search_one_level | ( | PlannerInfo * | root, | |
| int | level | |||
| ) |
Definition at line 51 of file joinrels.c.
References Assert, bms_overlap(), elog, ERROR, for_each_cell, RelOptInfo::has_eclass_joins, has_join_restriction(), have_join_order_restriction(), have_relevant_joinclause(), PlannerInfo::join_cur_level, PlannerInfo::join_info_list, PlannerInfo::join_rel_level, RelOptInfo::joininfo, PlannerInfo::lateral_info_list, lfirst, list_head(), lnext, make_join_rel(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), NIL, and RelOptInfo::relids.
Referenced by standard_join_search().
{
List **joinrels = root->join_rel_level;
ListCell *r;
int k;
Assert(joinrels[level] == NIL);
/* Set join_cur_level so that new joinrels are added to proper list */
root->join_cur_level = level;
/*
* First, consider left-sided and right-sided plans, in which rels of
* exactly level-1 member relations are joined against initial relations.
* We prefer to join using join clauses, but if we find a rel of level-1
* members that has no join clauses, we will generate Cartesian-product
* joins against all initial rels not already contained in it.
*/
foreach(r, joinrels[level - 1])
{
RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
if (old_rel->joininfo != NIL || old_rel->has_eclass_joins ||
has_join_restriction(root, old_rel))
{
/*
* There are join clauses or join order restrictions relevant to
* this rel, so consider joins between this rel and (only) those
* initial rels it is linked to by a clause or restriction.
*
* At level 2 this condition is symmetric, so there is no need to
* look at initial rels before this one in the list; we already
* considered such joins when we were at the earlier rel. (The
* mirror-image joins are handled automatically by make_join_rel.)
* In later passes (level > 2), we join rels of the previous level
* to each initial rel they don't already include but have a join
* clause or restriction with.
*/
ListCell *other_rels;
if (level == 2) /* consider remaining initial rels */
other_rels = lnext(r);
else /* consider all initial rels */
other_rels = list_head(joinrels[1]);
make_rels_by_clause_joins(root,
old_rel,
other_rels);
}
else
{
/*
* Oops, we have a relation that is not joined to any other
* relation, either directly or by join-order restrictions.
* Cartesian product time.
*
* We consider a cartesian product with each not-already-included
* initial rel, whether it has other join clauses or not. At
* level 2, if there are two or more clauseless initial rels, we
* will redundantly consider joining them in both directions; but
* such cases aren't common enough to justify adding complexity to
* avoid the duplicated effort.
*/
make_rels_by_clauseless_joins(root,
old_rel,
list_head(joinrels[1]));
}
}
/*
* Now, consider "bushy plans" in which relations of k initial rels are
* joined to relations of level-k initial rels, for 2 <= k <= level-2.
*
* We only consider bushy-plan joins for pairs of rels where there is a
* suitable join clause (or join order restriction), in order to avoid
* unreasonable growth of planning time.
*/
for (k = 2;; k++)
{
int other_level = level - k;
/*
* Since make_join_rel(x, y) handles both x,y and y,x cases, we only
* need to go as far as the halfway point.
*/
if (k > other_level)
break;
foreach(r, joinrels[k])
{
RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
ListCell *other_rels;
ListCell *r2;
/*
* We can ignore relations without join clauses here, unless they
* participate in join-order restrictions --- then we might have
* to force a bushy join plan.
*/
if (old_rel->joininfo == NIL && !old_rel->has_eclass_joins &&
!has_join_restriction(root, old_rel))
continue;
if (k == other_level)
other_rels = lnext(r); /* only consider remaining rels */
else
other_rels = list_head(joinrels[other_level]);
for_each_cell(r2, other_rels)
{
RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);
if (!bms_overlap(old_rel->relids, new_rel->relids))
{
/*
* OK, we can build a rel of the right level from this
* pair of rels. Do so if there is at least one relevant
* join clause or join order restriction.
*/
if (have_relevant_joinclause(root, old_rel, new_rel) ||
have_join_order_restriction(root, old_rel, new_rel))
{
(void) make_join_rel(root, old_rel, new_rel);
}
}
}
}
}
/*----------
* Last-ditch effort: if we failed to find any usable joins so far, force
* a set of cartesian-product joins to be generated. This handles the
* special case where all the available rels have join clauses but we
* cannot use any of those clauses yet. This can only happen when we are
* considering a join sub-problem (a sub-joinlist) and all the rels in the
* sub-problem have only join clauses with rels outside the sub-problem.
* An example is
*
* SELECT ... FROM a INNER JOIN b ON TRUE, c, d, ...
* WHERE a.w = c.x and b.y = d.z;
*
* If the "a INNER JOIN b" sub-problem does not get flattened into the
* upper level, we must be willing to make a cartesian join of a and b;
* but the code above will not have done so, because it thought that both
* a and b have joinclauses. We consider only left-sided and right-sided
* cartesian joins in this case (no bushy).
*----------
*/
if (joinrels[level] == NIL)
{
/*
* This loop is just like the first one, except we always call
* make_rels_by_clauseless_joins().
*/
foreach(r, joinrels[level - 1])
{
RelOptInfo *old_rel = (RelOptInfo *) lfirst(r);
make_rels_by_clauseless_joins(root,
old_rel,
list_head(joinrels[1]));
}
/*----------
* When special joins are involved, there may be no legal way
* to make an N-way join for some values of N. For example consider
*
* SELECT ... FROM t1 WHERE
* x IN (SELECT ... FROM t2,t3 WHERE ...) AND
* y IN (SELECT ... FROM t4,t5 WHERE ...)
*
* We will flatten this query to a 5-way join problem, but there are
* no 4-way joins that join_is_legal() will consider legal. We have
* to accept failure at level 4 and go on to discover a workable
* bushy plan at level 5.
*
* However, if there are no special joins and no lateral references
* then join_is_legal() should never fail, and so the following sanity
* check is useful.
*----------
*/
if (joinrels[level] == NIL &&
root->join_info_list == NIL &&
root->lateral_info_list == NIL)
elog(ERROR, "failed to build any %d-way joins", level);
}
}
| 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;
}
| RelOptInfo* make_join_rel | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel1, | |||
| RelOptInfo * | rel2 | |||
| ) |
Definition at line 577 of file joinrels.c.
References add_paths_to_joinrel(), Assert, bms_equal(), bms_free(), bms_is_subset(), bms_overlap(), bms_union(), build_join_rel(), RelOptInfo::cheapest_total_path, create_unique_path(), SpecialJoinInfo::delay_upper_joins, elog, ereport, errcode(), errmsg(), ERROR, is_dummy_rel(), JOIN_ANTI, JOIN_FULL, JOIN_INNER, join_is_legal(), JOIN_LEFT, SpecialJoinInfo::join_quals, JOIN_RIGHT, JOIN_SEMI, JOIN_UNIQUE_INNER, JOIN_UNIQUE_OUTER, SpecialJoinInfo::jointype, SpecialJoinInfo::lhs_strict, mark_dummy_rel(), SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, NULL, RelOptInfo::pathlist, RelOptInfo::relids, restriction_is_constant_false(), SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, and SpecialJoinInfo::type.
Referenced by join_search_one_level(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), and merge_clump().
{
Relids joinrelids;
SpecialJoinInfo *sjinfo;
bool reversed;
SpecialJoinInfo sjinfo_data;
RelOptInfo *joinrel;
List *restrictlist;
/* We should never try to join two overlapping sets of rels. */
Assert(!bms_overlap(rel1->relids, rel2->relids));
/* Construct Relids set that identifies the joinrel. */
joinrelids = bms_union(rel1->relids, rel2->relids);
/* Check validity and determine join type. */
if (!join_is_legal(root, rel1, rel2, joinrelids,
&sjinfo, &reversed))
{
/* invalid join path */
bms_free(joinrelids);
return NULL;
}
/* Swap rels if needed to match the join info. */
if (reversed)
{
RelOptInfo *trel = rel1;
rel1 = rel2;
rel2 = trel;
}
/*
* If it's a plain inner join, then we won't have found anything in
* join_info_list. Make up a SpecialJoinInfo so that selectivity
* estimation functions will know what's being joined.
*/
if (sjinfo == NULL)
{
sjinfo = &sjinfo_data;
sjinfo->type = T_SpecialJoinInfo;
sjinfo->min_lefthand = rel1->relids;
sjinfo->min_righthand = rel2->relids;
sjinfo->syn_lefthand = rel1->relids;
sjinfo->syn_righthand = rel2->relids;
sjinfo->jointype = JOIN_INNER;
/* we don't bother trying to make the remaining fields valid */
sjinfo->lhs_strict = false;
sjinfo->delay_upper_joins = false;
sjinfo->join_quals = NIL;
}
/*
* Find or build the join RelOptInfo, and compute the restrictlist that
* goes with this particular joining.
*/
joinrel = build_join_rel(root, joinrelids, rel1, rel2, sjinfo,
&restrictlist);
/*
* If we've already proven this join is empty, we needn't consider any
* more paths for it.
*/
if (is_dummy_rel(joinrel))
{
bms_free(joinrelids);
return joinrel;
}
/*
* Consider paths using each rel as both outer and inner. Depending on
* the join type, a provably empty outer or inner rel might mean the join
* is provably empty too; in which case throw away any previously computed
* paths and mark the join as dummy. (We do it this way since it's
* conceivable that dummy-ness of a multi-element join might only be
* noticeable for certain construction paths.)
*
* Also, a provably constant-false join restriction typically means that
* we can skip evaluating one or both sides of the join. We do this by
* marking the appropriate rel as dummy. For outer joins, a
* constant-false restriction that is pushed down still means the whole
* join is dummy, while a non-pushed-down one means that no inner rows
* will join so we can treat the inner rel as dummy.
*
* We need only consider the jointypes that appear in join_info_list, plus
* JOIN_INNER.
*/
switch (sjinfo->jointype)
{
case JOIN_INNER:
if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
restriction_is_constant_false(restrictlist, false))
{
mark_dummy_rel(joinrel);
break;
}
add_paths_to_joinrel(root, joinrel, rel1, rel2,
JOIN_INNER, sjinfo,
restrictlist);
add_paths_to_joinrel(root, joinrel, rel2, rel1,
JOIN_INNER, sjinfo,
restrictlist);
break;
case JOIN_LEFT:
if (is_dummy_rel(rel1) ||
restriction_is_constant_false(restrictlist, true))
{
mark_dummy_rel(joinrel);
break;
}
if (restriction_is_constant_false(restrictlist, false) &&
bms_is_subset(rel2->relids, sjinfo->syn_righthand))
mark_dummy_rel(rel2);
add_paths_to_joinrel(root, joinrel, rel1, rel2,
JOIN_LEFT, sjinfo,
restrictlist);
add_paths_to_joinrel(root, joinrel, rel2, rel1,
JOIN_RIGHT, sjinfo,
restrictlist);
break;
case JOIN_FULL:
if ((is_dummy_rel(rel1) && is_dummy_rel(rel2)) ||
restriction_is_constant_false(restrictlist, true))
{
mark_dummy_rel(joinrel);
break;
}
add_paths_to_joinrel(root, joinrel, rel1, rel2,
JOIN_FULL, sjinfo,
restrictlist);
add_paths_to_joinrel(root, joinrel, rel2, rel1,
JOIN_FULL, sjinfo,
restrictlist);
/*
* If there are join quals that aren't mergeable or hashable, we
* may not be able to build any valid plan. Complain here so that
* we can give a somewhat-useful error message. (Since we have no
* flexibility of planning for a full join, there's no chance of
* succeeding later with another pair of input rels.)
*/
if (joinrel->pathlist == NIL)
ereport(ERROR,
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
errmsg("FULL JOIN is only supported with merge-joinable or hash-joinable join conditions")));
break;
case JOIN_SEMI:
/*
* We might have a normal semijoin, or a case where we don't have
* enough rels to do the semijoin but can unique-ify the RHS and
* then do an innerjoin (see comments in join_is_legal). In the
* latter case we can't apply JOIN_SEMI joining.
*/
if (bms_is_subset(sjinfo->min_lefthand, rel1->relids) &&
bms_is_subset(sjinfo->min_righthand, rel2->relids))
{
if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
restriction_is_constant_false(restrictlist, false))
{
mark_dummy_rel(joinrel);
break;
}
add_paths_to_joinrel(root, joinrel, rel1, rel2,
JOIN_SEMI, sjinfo,
restrictlist);
}
/*
* If we know how to unique-ify the RHS and one input rel is
* exactly the RHS (not a superset) we can consider unique-ifying
* it and then doing a regular join. (The create_unique_path
* check here is probably redundant with what join_is_legal did,
* but if so the check is cheap because it's cached. So test
* anyway to be sure.)
*/
if (bms_equal(sjinfo->syn_righthand, rel2->relids) &&
create_unique_path(root, rel2, rel2->cheapest_total_path,
sjinfo) != NULL)
{
if (is_dummy_rel(rel1) || is_dummy_rel(rel2) ||
restriction_is_constant_false(restrictlist, false))
{
mark_dummy_rel(joinrel);
break;
}
add_paths_to_joinrel(root, joinrel, rel1, rel2,
JOIN_UNIQUE_INNER, sjinfo,
restrictlist);
add_paths_to_joinrel(root, joinrel, rel2, rel1,
JOIN_UNIQUE_OUTER, sjinfo,
restrictlist);
}
break;
case JOIN_ANTI:
if (is_dummy_rel(rel1) ||
restriction_is_constant_false(restrictlist, true))
{
mark_dummy_rel(joinrel);
break;
}
if (restriction_is_constant_false(restrictlist, false) &&
bms_is_subset(rel2->relids, sjinfo->syn_righthand))
mark_dummy_rel(rel2);
add_paths_to_joinrel(root, joinrel, rel1, rel2,
JOIN_ANTI, sjinfo,
restrictlist);
break;
default:
/* other values not expected here */
elog(ERROR, "unrecognized join type: %d", (int) sjinfo->jointype);
break;
}
bms_free(joinrelids);
return joinrel;
}
| RelOptInfo* make_one_rel | ( | PlannerInfo * | root, | |
| List * | joinlist | |||
| ) |
Definition at line 104 of file allpaths.c.
References PlannerInfo::all_baserels, Assert, bms_add_member(), bms_equal(), make_rel_from_joinlist(), NULL, RelOptInfo::relid, RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, set_base_rel_pathlists(), set_base_rel_sizes(), PlannerInfo::simple_rel_array, and PlannerInfo::simple_rel_array_size.
Referenced by query_planner().
{
RelOptInfo *rel;
Index rti;
/*
* Construct the all_baserels Relids set.
*/
root->all_baserels = NULL;
for (rti = 1; rti < root->simple_rel_array_size; rti++)
{
RelOptInfo *brel = root->simple_rel_array[rti];
/* there may be empty slots corresponding to non-baserel RTEs */
if (brel == NULL)
continue;
Assert(brel->relid == rti); /* sanity check on array */
/* ignore RTEs that are "other rels" */
if (brel->reloptkind != RELOPT_BASEREL)
continue;
root->all_baserels = bms_add_member(root->all_baserels, brel->relid);
}
/*
* Generate access paths for the base rels.
*/
set_base_rel_sizes(root);
set_base_rel_pathlists(root);
/*
* Generate access paths for the entire join tree.
*/
rel = make_rel_from_joinlist(root, joinlist);
/*
* The result should join all and only the query's base rels.
*/
Assert(bms_equal(rel->relids, root->all_baserels));
return rel;
}
| List* make_pathkeys_for_sortclauses | ( | PlannerInfo * | root, | |
| List * | sortclauses, | |||
| List * | tlist | |||
| ) |
Definition at line 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;
}
| bool match_index_to_operand | ( | Node * | operand, | |
| int | indexcol, | |||
| IndexOptInfo * | index | |||
| ) |
Definition at line 2932 of file indxpath.c.
References arg, elog, equal(), ERROR, i, IndexOptInfo::indexkeys, IndexOptInfo::indexprs, IsA, lfirst, list_head(), lnext, NULL, IndexOptInfo::rel, and RelOptInfo::relid.
Referenced by adjust_rowcompare_for_index(), btcostestimate(), ec_member_matches_indexcol(), expand_boolean_index_clause(), find_index_column(), get_actual_variable_range(), match_boolean_index_clause(), match_clause_to_indexcol(), match_clause_to_ordering_op(), match_rowcompare_to_indexcol(), and relation_has_unique_index_for().
{
int indkey;
/*
* Ignore any RelabelType node above the operand. This is needed to be
* able to apply indexscanning in binary-compatible-operator cases. Note:
* we can assume there is at most one RelabelType node;
* eval_const_expressions() will have simplified if more than one.
*/
if (operand && IsA(operand, RelabelType))
operand = (Node *) ((RelabelType *) operand)->arg;
indkey = index->indexkeys[indexcol];
if (indkey != 0)
{
/*
* Simple index column; operand must be a matching Var.
*/
if (operand && IsA(operand, Var) &&
index->rel->relid == ((Var *) operand)->varno &&
indkey == ((Var *) operand)->varattno)
return true;
}
else
{
/*
* Index expression; find the correct expression. (This search could
* be avoided, at the cost of complicating all the callers of this
* routine; doesn't seem worth it.)
*/
ListCell *indexpr_item;
int i;
Node *indexkey;
indexpr_item = list_head(index->indexprs);
for (i = 0; i < indexcol; i++)
{
if (index->indexkeys[i] == 0)
{
if (indexpr_item == NULL)
elog(ERROR, "wrong number of index expressions");
indexpr_item = lnext(indexpr_item);
}
}
if (indexpr_item == NULL)
elog(ERROR, "wrong number of index expressions");
indexkey = (Node *) lfirst(indexpr_item);
/*
* Does it match the operand? Again, strip any relabeling.
*/
if (indexkey && IsA(indexkey, RelabelType))
indexkey = (Node *) ((RelabelType *) indexkey)->arg;
if (equal(indexkey, operand))
return true;
}
return false;
}
| void mutate_eclass_expressions | ( | PlannerInfo * | root, | |
| Node *(*)() | mutator, | |||
| void * | context, | |||
| bool | include_child_exprs | |||
| ) |
Definition at line 1997 of file equivclass.c.
References EquivalenceClass::ec_members, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, PlannerInfo::eq_classes, and lfirst.
Referenced by optimize_minmax_aggregates().
{
ListCell *lc1;
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
ListCell *lc2;
foreach(lc2, cur_ec->ec_members)
{
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
if (cur_em->em_is_child && !include_child_exprs)
continue; /* ignore children unless requested */
cur_em->em_expr = (Expr *)
mutator((Node *) cur_em->em_expr, context);
}
}
}
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;
}
| bool process_equivalence | ( | PlannerInfo * | root, | |
| RestrictInfo * | restrictinfo, | |||
| bool | below_outer_join | |||
| ) |
Definition at line 98 of file equivclass.c.
References add_eq_member(), Assert, bms_intersect(), bms_is_empty(), bms_join(), PlannerInfo::canon_pathkeys, canonicalize_ec_expression(), RestrictInfo::clause, contain_nonstrict_functions(), EquivalenceClass::ec_below_outer_join, EquivalenceClass::ec_broken, EquivalenceClass::ec_collation, EquivalenceClass::ec_derives, EquivalenceClass::ec_has_const, EquivalenceClass::ec_has_volatile, EquivalenceClass::ec_members, EquivalenceClass::ec_merged, EquivalenceClass::ec_opfamilies, EquivalenceClass::ec_relids, EquivalenceClass::ec_sortref, EquivalenceClass::ec_sources, elog, EquivalenceMember::em_datatype, EquivalenceMember::em_expr, EquivalenceMember::em_is_child, EquivalenceMember::em_is_const, PlannerInfo::eq_classes, equal(), ERROR, exprType(), get_leftop(), get_rightop(), is_opclause, lappend(), RestrictInfo::left_ec, RestrictInfo::left_em, RestrictInfo::left_relids, lfirst, list_concat(), list_delete_ptr(), list_make1, makeNode, RestrictInfo::mergeopfamilies, NIL, NULL, RestrictInfo::nullable_relids, op_input_types(), RestrictInfo::right_ec, RestrictInfo::right_em, and RestrictInfo::right_relids.
Referenced by distribute_qual_to_rels(), reconsider_full_join_clause(), and reconsider_outer_join_clause().
{
Expr *clause = restrictinfo->clause;
Oid opno,
collation,
item1_type,
item2_type;
Expr *item1;
Expr *item2;
Relids item1_relids,
item2_relids,
item1_nullable_relids,
item2_nullable_relids;
List *opfamilies;
EquivalenceClass *ec1,
*ec2;
EquivalenceMember *em1,
*em2;
ListCell *lc1;
/* Should not already be marked as having generated an eclass */
Assert(restrictinfo->left_ec == NULL);
Assert(restrictinfo->right_ec == NULL);
/* Extract info from given clause */
Assert(is_opclause(clause));
opno = ((OpExpr *) clause)->opno;
collation = ((OpExpr *) clause)->inputcollid;
item1 = (Expr *) get_leftop(clause);
item2 = (Expr *) get_rightop(clause);
item1_relids = restrictinfo->left_relids;
item2_relids = restrictinfo->right_relids;
/*
* Ensure both input expressions expose the desired collation (their types
* should be OK already); see comments for canonicalize_ec_expression.
*/
item1 = canonicalize_ec_expression(item1,
exprType((Node *) item1),
collation);
item2 = canonicalize_ec_expression(item2,
exprType((Node *) item2),
collation);
/*
* Reject clauses of the form X=X. These are not as redundant as they
* might seem at first glance: assuming the operator is strict, this is
* really an expensive way to write X IS NOT NULL. So we must not risk
* just losing the clause, which would be possible if there is already a
* single-element EquivalenceClass containing X. The case is not common
* enough to be worth contorting the EC machinery for, so just reject the
* clause and let it be processed as a normal restriction clause.
*/
if (equal(item1, item2))
return false; /* X=X is not a useful equivalence */
/*
* If below outer join, check for strictness, else reject.
*/
if (below_outer_join)
{
if (!bms_is_empty(item1_relids) &&
contain_nonstrict_functions((Node *) item1))
return false; /* LHS is non-strict but not constant */
if (!bms_is_empty(item2_relids) &&
contain_nonstrict_functions((Node *) item2))
return false; /* RHS is non-strict but not constant */
}
/* Calculate nullable-relid sets for each side of the clause */
item1_nullable_relids = bms_intersect(item1_relids,
restrictinfo->nullable_relids);
item2_nullable_relids = bms_intersect(item2_relids,
restrictinfo->nullable_relids);
/*
* We use the declared input types of the operator, not exprType() of the
* inputs, as the nominal datatypes for opfamily lookup. This presumes
* that btree operators are always registered with amoplefttype and
* amoprighttype equal to their declared input types. We will need this
* info anyway to build EquivalenceMember nodes, and by extracting it now
* we can use type comparisons to short-circuit some equal() tests.
*/
op_input_types(opno, &item1_type, &item2_type);
opfamilies = restrictinfo->mergeopfamilies;
/*
* Sweep through the existing EquivalenceClasses looking for matches to
* item1 and item2. These are the possible outcomes:
*
* 1. We find both in the same EC. The equivalence is already known, so
* there's nothing to do.
*
* 2. We find both in different ECs. Merge the two ECs together.
*
* 3. We find just one. Add the other to its EC.
*
* 4. We find neither. Make a new, two-entry EC.
*
* Note: since all ECs are built through this process or the similar
* search in get_eclass_for_sort_expr(), it's impossible that we'd match
* an item in more than one existing nonvolatile EC. So it's okay to stop
* at the first match.
*/
ec1 = ec2 = NULL;
em1 = em2 = NULL;
foreach(lc1, root->eq_classes)
{
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
ListCell *lc2;
/* Never match to a volatile EC */
if (cur_ec->ec_has_volatile)
continue;
/*
* The collation has to match; check this first since it's cheaper
* than the opfamily comparison.
*/
if (collation != cur_ec->ec_collation)
continue;
/*
* A "match" requires matching sets of btree opfamilies. Use of
* equal() for this test has implications discussed in the comments
* for get_mergejoin_opfamilies().
*/
if (!equal(opfamilies, cur_ec->ec_opfamilies))
continue;
foreach(lc2, cur_ec->ec_members)
{
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
Assert(!cur_em->em_is_child); /* no children yet */
/*
* If below an outer join, don't match constants: they're not as
* constant as they look.
*/
if ((below_outer_join || cur_ec->ec_below_outer_join) &&
cur_em->em_is_const)
continue;
if (!ec1 &&
item1_type == cur_em->em_datatype &&
equal(item1, cur_em->em_expr))
{
ec1 = cur_ec;
em1 = cur_em;
if (ec2)
break;
}
if (!ec2 &&
item2_type == cur_em->em_datatype &&
equal(item2, cur_em->em_expr))
{
ec2 = cur_ec;
em2 = cur_em;
if (ec1)
break;
}
}
if (ec1 && ec2)
break;
}
/* Sweep finished, what did we find? */
if (ec1 && ec2)
{
/* If case 1, nothing to do, except add to sources */
if (ec1 == ec2)
{
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_below_outer_join |= below_outer_join;
/* mark the RI as associated with this eclass */
restrictinfo->left_ec = ec1;
restrictinfo->right_ec = ec1;
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
return true;
}
/*
* Case 2: need to merge ec1 and ec2. This should never happen after
* we've built any canonical pathkeys; if it did, those pathkeys might
* be rendered non-canonical by the merge.
*/
if (root->canon_pathkeys != NIL)
elog(ERROR, "too late to merge equivalence classes");
/*
* We add ec2's items to ec1, then set ec2's ec_merged link to point
* to ec1 and remove ec2 from the eq_classes list. We cannot simply
* delete ec2 because that could leave dangling pointers in existing
* PathKeys. We leave it behind with a link so that the merged EC can
* be found.
*/
ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members);
ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
ec1->ec_has_const |= ec2->ec_has_const;
/* can't need to set has_volatile */
ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
ec2->ec_merged = ec1;
root->eq_classes = list_delete_ptr(root->eq_classes, ec2);
/* just to avoid debugging confusion w/ dangling pointers: */
ec2->ec_members = NIL;
ec2->ec_sources = NIL;
ec2->ec_derives = NIL;
ec2->ec_relids = NULL;
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_below_outer_join |= below_outer_join;
/* mark the RI as associated with this eclass */
restrictinfo->left_ec = ec1;
restrictinfo->right_ec = ec1;
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
}
else if (ec1)
{
/* Case 3: add item2 to ec1 */
em2 = add_eq_member(ec1, item2, item2_relids, item2_nullable_relids,
false, item2_type);
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
ec1->ec_below_outer_join |= below_outer_join;
/* mark the RI as associated with this eclass */
restrictinfo->left_ec = ec1;
restrictinfo->right_ec = ec1;
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
}
else if (ec2)
{
/* Case 3: add item1 to ec2 */
em1 = add_eq_member(ec2, item1, item1_relids, item1_nullable_relids,
false, item1_type);
ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo);
ec2->ec_below_outer_join |= below_outer_join;
/* mark the RI as associated with this eclass */
restrictinfo->left_ec = ec2;
restrictinfo->right_ec = ec2;
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
}
else
{
/* Case 4: make a new, two-entry EC */
EquivalenceClass *ec = makeNode(EquivalenceClass);
ec->ec_opfamilies = opfamilies;
ec->ec_collation = collation;
ec->ec_members = NIL;
ec->ec_sources = list_make1(restrictinfo);
ec->ec_derives = NIL;
ec->ec_relids = NULL;
ec->ec_has_const = false;
ec->ec_has_volatile = false;
ec->ec_below_outer_join = below_outer_join;
ec->ec_broken = false;
ec->ec_sortref = 0;
ec->ec_merged = NULL;
em1 = add_eq_member(ec, item1, item1_relids, item1_nullable_relids,
false, item1_type);
em2 = add_eq_member(ec, item2, item2_relids, item2_nullable_relids,
false, item2_type);
root->eq_classes = lappend(root->eq_classes, ec);
/* mark the RI as associated with this eclass */
restrictinfo->left_ec = ec;
restrictinfo->right_ec = ec;
/* mark the RI as usable with this pair of EMs */
restrictinfo->left_em = em1;
restrictinfo->right_em = em2;
}
return true;
}
| void reconsider_outer_join_clauses | ( | PlannerInfo * | root | ) |
Definition at line 1451 of file equivclass.c.
References distribute_restrictinfo_to_rels(), PlannerInfo::full_join_clauses, PlannerInfo::left_join_clauses, lfirst, list_delete_cell(), list_head(), lnext, RangeQueryClause::next, RestrictInfo::norm_selec, RestrictInfo::outer_selec, reconsider_full_join_clause(), reconsider_outer_join_clause(), and PlannerInfo::right_join_clauses.
Referenced by query_planner().
{
bool found;
ListCell *cell;
ListCell *prev;
ListCell *next;
/* Outer loop repeats until we find no more deductions */
do
{
found = false;
/* Process the LEFT JOIN clauses */
prev = NULL;
for (cell = list_head(root->left_join_clauses); cell; cell = next)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
next = lnext(cell);
if (reconsider_outer_join_clause(root, rinfo, true))
{
found = true;
/* remove it from the list */
root->left_join_clauses =
list_delete_cell(root->left_join_clauses, cell, prev);
/* we throw it back anyway (see notes above) */
/* but the thrown-back clause has no extra selectivity */
rinfo->norm_selec = 2.0;
rinfo->outer_selec = 1.0;
distribute_restrictinfo_to_rels(root, rinfo);
}
else
prev = cell;
}
/* Process the RIGHT JOIN clauses */
prev = NULL;
for (cell = list_head(root->right_join_clauses); cell; cell = next)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
next = lnext(cell);
if (reconsider_outer_join_clause(root, rinfo, false))
{
found = true;
/* remove it from the list */
root->right_join_clauses =
list_delete_cell(root->right_join_clauses, cell, prev);
/* we throw it back anyway (see notes above) */
/* but the thrown-back clause has no extra selectivity */
rinfo->norm_selec = 2.0;
rinfo->outer_selec = 1.0;
distribute_restrictinfo_to_rels(root, rinfo);
}
else
prev = cell;
}
/* Process the FULL JOIN clauses */
prev = NULL;
for (cell = list_head(root->full_join_clauses); cell; cell = next)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
next = lnext(cell);
if (reconsider_full_join_clause(root, rinfo))
{
found = true;
/* remove it from the list */
root->full_join_clauses =
list_delete_cell(root->full_join_clauses, cell, prev);
/* we throw it back anyway (see notes above) */
/* but the thrown-back clause has no extra selectivity */
rinfo->norm_selec = 2.0;
rinfo->outer_selec = 1.0;
distribute_restrictinfo_to_rels(root, rinfo);
}
else
prev = cell;
}
} while (found);
/* Now, any remaining clauses have to be thrown back */
foreach(cell, root->left_join_clauses)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
distribute_restrictinfo_to_rels(root, rinfo);
}
foreach(cell, root->right_join_clauses)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
distribute_restrictinfo_to_rels(root, rinfo);
}
foreach(cell, root->full_join_clauses)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(cell);
distribute_restrictinfo_to_rels(root, rinfo);
}
}
| bool relation_has_unique_index_for | ( | PlannerInfo * | root, | |
| RelOptInfo * | rel, | |||
| List * | restrictlist, | |||
| List * | exprlist, | |||
| List * | oprlist | |||
| ) |
Definition at line 2758 of file indxpath.c.
References Assert, RelOptInfo::baserestrictinfo, bms_is_empty(), RestrictInfo::clause, forboth, get_leftop(), get_rightop(), IndexOptInfo::immediate, RelOptInfo::indexlist, IndexOptInfo::indpred, lappend(), RestrictInfo::left_relids, lfirst, lfirst_oid, list_length(), list_member_oid(), match_index_to_operand(), RestrictInfo::mergeopfamilies, IndexOptInfo::ncolumns, NIL, op_in_opfamily(), IndexOptInfo::opfamily, RestrictInfo::outer_is_left, IndexOptInfo::predOK, RestrictInfo::right_relids, and IndexOptInfo::unique.
Referenced by create_unique_path(), and join_is_removable().
{
ListCell *ic;
Assert(list_length(exprlist) == list_length(oprlist));
/* Short-circuit if no indexes... */
if (rel->indexlist == NIL)
return false;
/*
* Examine the rel's restriction clauses for usable var = const clauses
* that we can add to the restrictlist.
*/
foreach(ic, rel->baserestrictinfo)
{
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(ic);
/*
* Note: can_join won't be set for a restriction clause, but
* mergeopfamilies will be if it has a mergejoinable operator and
* doesn't contain volatile functions.
*/
if (restrictinfo->mergeopfamilies == NIL)
continue; /* not mergejoinable */
/*
* The clause certainly doesn't refer to anything but the given rel.
* If either side is pseudoconstant then we can use it.
*/
if (bms_is_empty(restrictinfo->left_relids))
{
/* righthand side is inner */
restrictinfo->outer_is_left = true;
}
else if (bms_is_empty(restrictinfo->right_relids))
{
/* lefthand side is inner */
restrictinfo->outer_is_left = false;
}
else
continue;
/* OK, add to list */
restrictlist = lappend(restrictlist, restrictinfo);
}
/* Short-circuit the easy case */
if (restrictlist == NIL && exprlist == NIL)
return false;
/* Examine each index of the relation ... */
foreach(ic, rel->indexlist)
{
IndexOptInfo *ind = (IndexOptInfo *) lfirst(ic);
int c;
/*
* If the index is not unique, or not immediately enforced, or if it's
* a partial index that doesn't match the query, it's useless here.
*/
if (!ind->unique || !ind->immediate ||
(ind->indpred != NIL && !ind->predOK))
continue;
/*
* Try to find each index column in the lists of conditions. This is
* O(N^2) or worse, but we expect all the lists to be short.
*/
for (c = 0; c < ind->ncolumns; c++)
{
bool matched = false;
ListCell *lc;
ListCell *lc2;
foreach(lc, restrictlist)
{
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
Node *rexpr;
/*
* The condition's equality operator must be a member of the
* index opfamily, else it is not asserting the right kind of
* equality behavior for this index. We check this first
* since it's probably cheaper than match_index_to_operand().
*/
if (!list_member_oid(rinfo->mergeopfamilies, ind->opfamily[c]))
continue;
/*
* XXX at some point we may need to check collations here too.
* For the moment we assume all collations reduce to the same
* notion of equality.
*/
/* OK, see if the condition operand matches the index key */
if (rinfo->outer_is_left)
rexpr = get_rightop(rinfo->clause);
else
rexpr = get_leftop(rinfo->clause);
if (match_index_to_operand(rexpr, c, ind))
{
matched = true; /* column is unique */
break;
}
}
if (matched)
continue;
forboth(lc, exprlist, lc2, oprlist)
{
Node *expr = (Node *) lfirst(lc);
Oid opr = lfirst_oid(lc2);
/* See if the expression matches the index key */
if (!match_index_to_operand(expr, c, ind))
continue;
/*
* The equality operator must be a member of the index
* opfamily, else it is not asserting the right kind of
* equality behavior for this index. We assume the caller
* determined it is an equality operator, so we don't need to
* check any more tightly than this.
*/
if (!op_in_opfamily(opr, ind->opfamily[c]))
continue;
/*
* XXX at some point we may need to check collations here too.
* For the moment we assume all collations reduce to the same
* notion of equality.
*/
matched = true; /* column is unique */
break;
}
if (!matched)
break; /* no match; this index doesn't help us */
}
/* Matched all columns of this index? */
if (c == ind->ncolumns)
return true;
}
return false;
}
| 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;
}
| RelOptInfo* standard_join_search | ( | PlannerInfo * | root, | |
| int | levels_needed, | |||
| List * | initial_rels | |||
| ) |
Definition at line 1469 of file allpaths.c.
References Assert, elog, ERROR, PlannerInfo::join_rel_level, join_search_one_level(), lfirst, linitial, list_length(), NIL, NULL, palloc0(), and set_cheapest().
Referenced by make_rel_from_joinlist().
{
int lev;
RelOptInfo *rel;
/*
* This function cannot be invoked recursively within any one planning
* problem, so join_rel_level[] can't be in use already.
*/
Assert(root->join_rel_level == NULL);
/*
* We employ a simple "dynamic programming" algorithm: we first find all
* ways to build joins of two jointree items, then all ways to build joins
* of three items (from two-item joins and single items), then four-item
* joins, and so on until we have considered all ways to join all the
* items into one rel.
*
* root->join_rel_level[j] is a list of all the j-item rels. Initially we
* set root->join_rel_level[1] to represent all the single-jointree-item
* relations.
*/
root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));
root->join_rel_level[1] = initial_rels;
for (lev = 2; lev <= levels_needed; lev++)
{
ListCell *lc;
/*
* Determine all possible pairs of relations to be joined at this
* level, and build paths for making each one from every available
* pair of lower-level relations.
*/
join_search_one_level(root, lev);
/*
* Do cleanup work on each just-processed rel.
*/
foreach(lc, root->join_rel_level[lev])
{
rel = (RelOptInfo *) lfirst(lc);
/* Find and save the cheapest paths for this rel */
set_cheapest(rel);
#ifdef OPTIMIZER_DEBUG
debug_print_rel(root, rel);
#endif
}
}
/*
* We should have a single rel at the final level.
*/
if (root->join_rel_level[levels_needed] == NIL)
elog(ERROR, "failed to build any %d-way joins", levels_needed);
Assert(list_length(root->join_rel_level[levels_needed]) == 1);
rel = (RelOptInfo *) linitial(root->join_rel_level[levels_needed]);
root->join_rel_level = NULL;
return rel;
}
| 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;
}
Definition at line 43 of file allpaths.c.
Referenced by make_rel_from_joinlist().
| int geqo_threshold |
Definition at line 44 of file allpaths.c.
Referenced by make_rel_from_joinlist().
| PGDLLIMPORT join_search_hook_type join_search_hook |
Definition at line 47 of file allpaths.c.
Referenced by make_rel_from_joinlist().
1.7.1