diff options
Diffstat (limited to 'src/backend/optimizer/path/pathkeys.c')
| -rw-r--r-- | src/backend/optimizer/path/pathkeys.c | 291 |
1 files changed, 288 insertions, 3 deletions
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 52075fbf465..389d89f0d8d 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -11,7 +11,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.68 2005/06/09 04:18:59 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.69 2005/07/02 23:00:40 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -32,6 +32,14 @@ static PathKeyItem *makePathKeyItem(Node *key, Oid sortop, bool checkType); +static void generate_outer_join_implications(PlannerInfo *root, + List *equi_key_set, + Relids *relids); +static void process_implied_const_eq(PlannerInfo *root, + List *equi_key_set, Relids *relids, + Node *item1, Oid sortop1, + Relids item1_relids, + bool delete_it); static List *make_canonical_pathkey(PlannerInfo *root, PathKeyItem *item); static Var *find_indexkey_var(PlannerInfo *root, RelOptInfo *rel, AttrNumber varattno); @@ -193,6 +201,10 @@ add_equijoined_keys(PlannerInfo *root, RestrictInfo *restrictinfo) * functions; but we will never consider such an expression to be a pathkey * at all, because check_mergejoinable() will reject it.) * + * Also, when we have constants in an equi_key_list we can try to propagate + * the constants into outer joins; see generate_outer_join_implications + * for discussion. + * * This routine just walks the equi_key_list to find all pairwise equalities. * We call process_implied_equality (in plan/initsplan.c) to adjust the * restrictinfo datastructures for each pair. @@ -213,9 +225,10 @@ generate_implied_equalities(PlannerInfo *root) /* * A set containing only two items cannot imply any equalities - * beyond the one that created the set, so we can skip it. + * beyond the one that created the set, so we can skip it --- + * unless outer joins appear in the query. */ - if (nitems < 3) + if (nitems < 3 && !root->hasOuterJoins) continue; /* @@ -238,6 +251,20 @@ generate_implied_equalities(PlannerInfo *root) } /* + * If we have constant(s) and outer joins, try to propagate the + * constants through outer-join quals. + */ + if (have_consts && root->hasOuterJoins) + generate_outer_join_implications(root, curset, relids); + + /* + * A set containing only two items cannot imply any equalities + * beyond the one that created the set, so we can skip it. + */ + if (nitems < 3) + continue; + + /* * Match each item in the set with all that appear after it (it's * sufficient to generate A=B, need not process B=A too). */ @@ -286,6 +313,264 @@ generate_implied_equalities(PlannerInfo *root) } /* + * generate_outer_join_implications + * Generate clauses that can be deduced in outer-join situations. + * + * When we have mergejoinable clauses A = B that are outer-join clauses, + * we can't blindly combine them with other clauses A = C to deduce B = C, + * since in fact the "equality" A = B won't necessarily hold above the + * outer join (one of the variables might be NULL instead). Nonetheless + * there are cases where we can add qual clauses using transitivity. + * + * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR + * combined with a pushed-down (valid everywhere) clause OUTERVAR = CONSTANT. + * It is safe and useful to push a clause INNERVAR = CONSTANT into the + * evaluation of the inner (nullable) relation, because any inner rows not + * meeting this condition will not contribute to the outer-join result anyway. + * (Any outer rows they could join to will be eliminated by the pushed-down + * clause.) + * + * Note that the above rule does not work for full outer joins, nor for + * pushed-down restrictions on an inner-side variable; nor is it very + * interesting to consider cases where the pushed-down clause involves + * relations entirely outside the outer join, since such clauses couldn't + * be pushed into the inner side's scan anyway. So the restriction to + * outervar = pseudoconstant is not really giving up anything. + * + * For full-join cases, we can only do something useful if it's a FULL JOIN + * USING and a merged column has a restriction MERGEDVAR = CONSTANT. By + * the time it gets here, the restriction will look like + * COALESCE(LEFTVAR, RIGHTVAR) = CONSTANT + * and we will have a join clause LEFTVAR = RIGHTVAR that we can match the + * COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT + * and RIGHTVAR = CONSTANT into the input relations, since any rows not + * meeting these conditions cannot contribute to the join result. + * + * Again, there isn't any traction to be gained by trying to deal with + * clauses comparing a mergedvar to a non-pseudoconstant. So we can make + * use of the equi_key_lists to quickly find the interesting pushed-down + * clauses. The interesting outer-join clauses were accumulated for us by + * distribute_qual_to_rels. + * + * equi_key_set: a list of PathKeyItems that are known globally equivalent, + * at least one of which is a pseudoconstant. + * relids: an array of Relids sets showing the relation membership of each + * PathKeyItem in equi_key_set. + */ +static void +generate_outer_join_implications(PlannerInfo *root, + List *equi_key_set, + Relids *relids) +{ + ListCell *l1; + + /* Examine each mergejoinable outer-join clause with OUTERVAR on left */ + foreach(l1, root->left_join_clauses) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l1); + Node *leftop = get_leftop(rinfo->clause); + Node *rightop = get_rightop(rinfo->clause); + ListCell *l2; + + /* Scan to see if it matches any element of equi_key_set */ + foreach(l2, equi_key_set) + { + PathKeyItem *item1 = (PathKeyItem *) lfirst(l2); + + if (equal(leftop, item1->key) && + rinfo->left_sortop == item1->sortop) + { + /* + * Yes, so find constant member(s) of set and generate + * implied INNERVAR = CONSTANT + */ + process_implied_const_eq(root, equi_key_set, relids, + rightop, + rinfo->right_sortop, + rinfo->right_relids, + false); + /* + * We can remove the explicit outer join qual, too, + * since we now have tests forcing each of its sides + * to the same value. + */ + process_implied_equality(root, + leftop, + rightop, + rinfo->left_sortop, + rinfo->right_sortop, + rinfo->left_relids, + rinfo->right_relids, + true); + + /* No need to match against remaining set members */ + break; + } + } + } + + /* Examine each mergejoinable outer-join clause with OUTERVAR on right */ + foreach(l1, root->right_join_clauses) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l1); + Node *leftop = get_leftop(rinfo->clause); + Node *rightop = get_rightop(rinfo->clause); + ListCell *l2; + + /* Scan to see if it matches any element of equi_key_set */ + foreach(l2, equi_key_set) + { + PathKeyItem *item1 = (PathKeyItem *) lfirst(l2); + + if (equal(rightop, item1->key) && + rinfo->right_sortop == item1->sortop) + { + /* + * Yes, so find constant member(s) of set and generate + * implied INNERVAR = CONSTANT + */ + process_implied_const_eq(root, equi_key_set, relids, + leftop, + rinfo->left_sortop, + rinfo->left_relids, + false); + /* + * We can remove the explicit outer join qual, too, + * since we now have tests forcing each of its sides + * to the same value. + */ + process_implied_equality(root, + leftop, + rightop, + rinfo->left_sortop, + rinfo->right_sortop, + rinfo->left_relids, + rinfo->right_relids, + true); + + /* No need to match against remaining set members */ + break; + } + } + } + + /* Examine each mergejoinable full-join clause */ + foreach(l1, root->full_join_clauses) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(l1); + Node *leftop = get_leftop(rinfo->clause); + Node *rightop = get_rightop(rinfo->clause); + int i1 = 0; + ListCell *l2; + + /* Scan to see if it matches any element of equi_key_set */ + foreach(l2, equi_key_set) + { + PathKeyItem *item1 = (PathKeyItem *) lfirst(l2); + CoalesceExpr *cexpr = (CoalesceExpr *) item1->key; + + /* + * Try to match a pathkey containing a COALESCE() expression + * to the join clause. We can assume the COALESCE() inputs + * are in the same order as the join clause, since both were + * automatically generated in the cases we care about. + * + * XXX currently this may fail to match in cross-type cases + * because the COALESCE will contain typecast operations while + * the join clause may not (if there is a cross-type mergejoin + * operator available for the two column types). + * Is it OK to strip implicit coercions from the COALESCE + * arguments? What of the sortops in such cases? + */ + if (IsA(cexpr, CoalesceExpr) && + list_length(cexpr->args) == 2 && + equal(leftop, (Node *) linitial(cexpr->args)) && + equal(rightop, (Node *) lsecond(cexpr->args)) && + rinfo->left_sortop == item1->sortop && + rinfo->right_sortop == item1->sortop) + { + /* + * Yes, so find constant member(s) of set and generate + * implied LEFTVAR = CONSTANT + */ + process_implied_const_eq(root, equi_key_set, relids, + leftop, + rinfo->left_sortop, + rinfo->left_relids, + false); + /* ... and RIGHTVAR = CONSTANT */ + process_implied_const_eq(root, equi_key_set, relids, + rightop, + rinfo->right_sortop, + rinfo->right_relids, + false); + /* ... and remove COALESCE() = CONSTANT */ + process_implied_const_eq(root, equi_key_set, relids, + item1->key, + item1->sortop, + relids[i1], + true); + /* + * We can remove the explicit outer join qual, too, + * since we now have tests forcing each of its sides + * to the same value. + */ + process_implied_equality(root, + leftop, + rightop, + rinfo->left_sortop, + rinfo->right_sortop, + rinfo->left_relids, + rinfo->right_relids, + true); + + /* No need to match against remaining set members */ + break; + } + i1++; + } + } +} + +/* + * process_implied_const_eq + * Apply process_implied_equality with the given item and each + * pseudoconstant member of equi_key_set. + * + * This is just a subroutine to save some cruft in + * generate_outer_join_implications. equi_key_set and relids are as in + * generate_outer_join_implications, the other parameters as for + * process_implied_equality. + */ +static void +process_implied_const_eq(PlannerInfo *root, List *equi_key_set, Relids *relids, + Node *item1, Oid sortop1, Relids item1_relids, + bool delete_it) +{ + ListCell *l; + bool found = false; + int i = 0; + + foreach(l, equi_key_set) + { + PathKeyItem *item2 = (PathKeyItem *) lfirst(l); + + if (bms_is_empty(relids[i])) + { + process_implied_equality(root, + item1, item2->key, + sortop1, item2->sortop, + item1_relids, NULL, + delete_it); + found = true; + } + i++; + } + /* Caller screwed up if no constants in list */ + Assert(found); +} + +/* * exprs_known_equal * Detect whether two expressions are known equal due to equijoin clauses. * |