diff options
-rw-r--r-- | src/backend/nodes/outfuncs.c | 1 | ||||
-rw-r--r-- | src/backend/optimizer/path/equivclass.c | 81 | ||||
-rw-r--r-- | src/backend/optimizer/plan/initsplan.c | 95 | ||||
-rw-r--r-- | src/include/nodes/relation.h | 1 | ||||
-rw-r--r-- | src/include/optimizer/planmain.h | 4 | ||||
-rw-r--r-- | src/test/regress/expected/join.out | 71 | ||||
-rw-r--r-- | src/test/regress/sql/join.sql | 32 |
7 files changed, 249 insertions, 36 deletions
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index a66ea5e048e..085a4580853 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1801,6 +1801,7 @@ _outEquivalenceMember(StringInfo str, EquivalenceMember *node) WRITE_NODE_FIELD(em_expr); WRITE_BITMAPSET_FIELD(em_relids); + WRITE_BITMAPSET_FIELD(em_nullable_relids); WRITE_BOOL_FIELD(em_is_const); WRITE_BOOL_FIELD(em_is_child); WRITE_OID_FIELD(em_datatype); diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 4e46ed94a16..00493d82e77 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -30,7 +30,7 @@ static EquivalenceMember *add_eq_member(EquivalenceClass *ec, - Expr *expr, Relids relids, + Expr *expr, Relids relids, Relids nullable_relids, bool is_child, Oid datatype); static void generate_base_implied_equalities_const(PlannerInfo *root, EquivalenceClass *ec); @@ -105,7 +105,9 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo, Expr *item1; Expr *item2; Relids item1_relids, - item2_relids; + item2_relids, + item1_nullable_relids, + item2_nullable_relids; List *opfamilies; EquivalenceClass *ec1, *ec2; @@ -162,6 +164,12 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo, 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 @@ -308,7 +316,8 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo, else if (ec1) { /* Case 3: add item2 to ec1 */ - em2 = add_eq_member(ec1, item2, item2_relids, false, item2_type); + 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 */ @@ -321,7 +330,8 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo, else if (ec2) { /* Case 3: add item1 to ec2 */ - em1 = add_eq_member(ec2, item1, item1_relids, false, item1_type); + 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 */ @@ -348,8 +358,10 @@ process_equivalence(PlannerInfo *root, RestrictInfo *restrictinfo, ec->ec_broken = false; ec->ec_sortref = 0; ec->ec_merged = NULL; - em1 = add_eq_member(ec, item1, item1_relids, false, item1_type); - em2 = add_eq_member(ec, item2, item2_relids, false, item2_type); + 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); @@ -447,12 +459,13 @@ canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation) */ static EquivalenceMember * add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, - bool is_child, Oid datatype) + Relids nullable_relids, bool is_child, Oid datatype) { EquivalenceMember *em = makeNode(EquivalenceMember); em->em_expr = expr; em->em_relids = relids; + em->em_nullable_relids = nullable_relids; em->em_is_const = false; em->em_is_child = is_child; em->em_datatype = datatype; @@ -608,7 +621,7 @@ get_eclass_for_sort_expr(PlannerInfo *root, elog(ERROR, "volatile EquivalenceClass has no sortref"); newem = add_eq_member(newec, copyObject(expr), pull_varnos((Node *) expr), - false, opcintype); + NULL, false, opcintype); /* * add_eq_member doesn't check for volatile functions, set-returning @@ -788,7 +801,9 @@ generate_base_implied_equalities_const(PlannerInfo *root, } process_implied_equality(root, eq_op, ec->ec_collation, cur_em->em_expr, const_em->em_expr, - ec->ec_relids, + bms_copy(ec->ec_relids), + bms_union(cur_em->em_nullable_relids, + const_em->em_nullable_relids), ec->ec_below_outer_join, cur_em->em_is_const); } @@ -843,7 +858,9 @@ generate_base_implied_equalities_no_const(PlannerInfo *root, } process_implied_equality(root, eq_op, ec->ec_collation, prev_em->em_expr, cur_em->em_expr, - ec->ec_relids, + bms_copy(ec->ec_relids), + bms_union(prev_em->em_nullable_relids, + cur_em->em_nullable_relids), ec->ec_below_outer_join, false); } @@ -1248,7 +1265,9 @@ create_join_clause(PlannerInfo *root, leftem->em_expr, rightem->em_expr, bms_union(leftem->em_relids, - rightem->em_relids)); + rightem->em_relids), + bms_union(leftem->em_nullable_relids, + rightem->em_nullable_relids)); /* Mark the clause as redundant, or not */ rinfo->parent_ec = parent_ec; @@ -1470,7 +1489,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo, left_type, right_type, inner_datatype; - Relids inner_relids; + Relids inner_relids, + inner_nullable_relids; ListCell *lc1; Assert(is_opclause(rinfo->clause)); @@ -1497,6 +1517,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo, inner_datatype = left_type; inner_relids = rinfo->left_relids; } + inner_nullable_relids = bms_intersect(inner_relids, + rinfo->nullable_relids); /* Scan EquivalenceClasses for a match to outervar */ foreach(lc1, root->eq_classes) @@ -1555,7 +1577,8 @@ reconsider_outer_join_clause(PlannerInfo *root, RestrictInfo *rinfo, cur_ec->ec_collation, innervar, cur_em->em_expr, - inner_relids); + bms_copy(inner_relids), + bms_copy(inner_nullable_relids)); if (process_equivalence(root, newrinfo, true)) match = true; } @@ -1589,7 +1612,9 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo) left_type, right_type; Relids left_relids, - right_relids; + right_relids, + left_nullable_relids, + right_nullable_relids; ListCell *lc1; /* Can't use an outerjoin_delayed clause here */ @@ -1605,6 +1630,10 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo) rightvar = (Expr *) get_rightop(rinfo->clause); left_relids = rinfo->left_relids; right_relids = rinfo->right_relids; + left_nullable_relids = bms_intersect(left_relids, + rinfo->nullable_relids); + right_nullable_relids = bms_intersect(right_relids, + rinfo->nullable_relids); foreach(lc1, root->eq_classes) { @@ -1690,7 +1719,8 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo) cur_ec->ec_collation, leftvar, cur_em->em_expr, - left_relids); + bms_copy(left_relids), + bms_copy(left_nullable_relids)); if (process_equivalence(root, newrinfo, true)) matchleft = true; } @@ -1703,7 +1733,8 @@ reconsider_full_join_clause(PlannerInfo *root, RestrictInfo *rinfo) cur_ec->ec_collation, rightvar, cur_em->em_expr, - right_relids); + bms_copy(right_relids), + bms_copy(right_nullable_relids)); if (process_equivalence(root, newrinfo, true)) matchright = true; } @@ -1829,11 +1860,27 @@ add_child_rel_equivalences(PlannerInfo *root, { /* Yes, generate transformed child version */ Expr *child_expr; + Relids new_nullable_relids; child_expr = (Expr *) adjust_appendrel_attrs((Node *) cur_em->em_expr, appinfo); - (void) add_eq_member(cur_ec, child_expr, child_rel->relids, + + /* + * Must translate 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, + child_rel->relids, new_nullable_relids, true, cur_em->em_datatype); } } diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 9cfc56ea541..24185a6cecb 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -52,9 +52,12 @@ static void distribute_qual_to_rels(PlannerInfo *root, Node *clause, JoinType jointype, Relids qualscope, Relids ojscope, - Relids outerjoin_nonnullable); + Relids outerjoin_nonnullable, + Relids deduced_nullable_relids); static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p, Relids *nullable_relids_p, bool is_pushed_down); +static bool check_equivalence_delay(PlannerInfo *root, + RestrictInfo *restrictinfo); static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause); static void check_mergejoinable(RestrictInfo *restrictinfo); static void check_hashjoinable(RestrictInfo *restrictinfo); @@ -353,7 +356,7 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, distribute_qual_to_rels(root, qual, false, below_outer_join, JOIN_INNER, - *qualscope, NULL, NULL); + *qualscope, NULL, NULL, NULL); } } else if (IsA(jtnode, JoinExpr)) @@ -477,7 +480,7 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join, distribute_qual_to_rels(root, qual, false, below_outer_join, j->jointype, *qualscope, - ojscope, nonnullable_rels); + ojscope, nonnullable_rels, NULL); } /* Now we can add the SpecialJoinInfo to join_info_list */ @@ -786,13 +789,19 @@ make_outerjoininfo(PlannerInfo *root, * baserels appearing on the outer (nonnullable) side of the join * (for FULL JOIN this includes both sides of the join, and must in fact * equal qualscope) + * 'deduced_nullable_relids': if is_deduced is TRUE, the nullable relids to + * impute to the clause; otherwise NULL * * 'qualscope' identifies what level of JOIN the qual came from syntactically. * 'ojscope' is needed if we decide to force the qual up to the outer-join * level, which will be ojscope not necessarily qualscope. * - * At the time this is called, root->join_info_list must contain entries for - * all and only those special joins that are syntactically below this qual. + * In normal use (when is_deduced is FALSE), at the time this is called, + * root->join_info_list must contain entries for all and only those special + * joins that are syntactically below this qual. But when is_deduced is TRUE, + * we are adding new deduced clauses after completion of deconstruct_jointree, + * so it cannot be assumed that root->join_info_list has anything to do with + * qual placement. */ static void distribute_qual_to_rels(PlannerInfo *root, Node *clause, @@ -801,7 +810,8 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, JoinType jointype, Relids qualscope, Relids ojscope, - Relids outerjoin_nonnullable) + Relids outerjoin_nonnullable, + Relids deduced_nullable_relids) { Relids relids; bool is_pushed_down; @@ -914,12 +924,13 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, * If the qual came from implied-equality deduction, it should not be * outerjoin-delayed, else deducer blew it. But we can't check this * because the join_info_list may now contain OJs above where the qual - * belongs. + * belongs. For the same reason, we must rely on caller to supply the + * correct nullable_relids set. */ Assert(!ojscope); is_pushed_down = true; outerjoin_delayed = false; - nullable_relids = NULL; + nullable_relids = deduced_nullable_relids; /* Don't feed it back for more deductions */ maybe_equivalence = false; maybe_outer_join = false; @@ -1089,7 +1100,8 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause, { if (maybe_equivalence) { - if (process_equivalence(root, restrictinfo, below_outer_join)) + if (check_equivalence_delay(root, restrictinfo) && + process_equivalence(root, restrictinfo, below_outer_join)) return; /* EC rejected it, so set left_ec/right_ec the hard way ... */ initialize_mergeclause_eclasses(root, restrictinfo); @@ -1262,6 +1274,44 @@ check_outerjoin_delay(PlannerInfo *root, } /* + * check_equivalence_delay + * Detect whether a potential equivalence clause is rendered unsafe + * by outer-join-delay considerations. Return TRUE if it's safe. + * + * The initial tests in distribute_qual_to_rels will consider a mergejoinable + * clause to be a potential equivalence clause if it is not outerjoin_delayed. + * But since the point of equivalence processing is that we will recombine the + * two sides of the clause with others, we have to check that each side + * satisfies the not-outerjoin_delayed condition on its own; otherwise it might + * not be safe to evaluate everywhere we could place a derived equivalence + * condition. + */ +static bool +check_equivalence_delay(PlannerInfo *root, + RestrictInfo *restrictinfo) +{ + Relids relids; + Relids nullable_relids; + + /* fast path if no special joins */ + if (root->join_info_list == NIL) + return true; + + /* must copy restrictinfo's relids to avoid changing it */ + relids = bms_copy(restrictinfo->left_relids); + /* check left side does not need delay */ + if (check_outerjoin_delay(root, &relids, &nullable_relids, true)) + return false; + + /* and similarly for the right side */ + relids = bms_copy(restrictinfo->right_relids); + if (check_outerjoin_delay(root, &relids, &nullable_relids, true)) + return false; + + return true; +} + +/* * check_redundant_nullability_qual * Check to see if the qual is an IS NULL qual that is redundant with * a lower JOIN_ANTI join. @@ -1371,11 +1421,20 @@ distribute_restrictinfo_to_rels(PlannerInfo *root, * variable-free. Otherwise the qual is applied at the lowest join level * that provides all its variables. * + * "nullable_relids" is the set of relids used in the expressions that are + * potentially nullable below the expressions. (This has to be supplied by + * caller because this function is used after deconstruct_jointree, so we + * don't have knowledge of where the clause items came from.) + * * "both_const" indicates whether both items are known pseudo-constant; * in this case it is worth applying eval_const_expressions() in case we * can produce constant TRUE or constant FALSE. (Otherwise it's not, * because the expressions went through eval_const_expressions already.) * + * Note: this function will copy item1 and item2, but it is caller's + * responsibility to make sure that the Relids parameters are fresh copies + * not shared with other uses. + * * This is currently used only when an EquivalenceClass is found to * contain pseudoconstants. See path/pathkeys.c for more details. */ @@ -1386,6 +1445,7 @@ process_implied_equality(PlannerInfo *root, Expr *item1, Expr *item2, Relids qualscope, + Relids nullable_relids, bool below_outer_join, bool both_const) { @@ -1419,15 +1479,12 @@ process_implied_equality(PlannerInfo *root, } } - /* Make a copy of qualscope to avoid problems if source EC changes */ - qualscope = bms_copy(qualscope); - /* * Push the new clause into all the appropriate restrictinfo lists. */ distribute_qual_to_rels(root, (Node *) clause, true, below_outer_join, JOIN_INNER, - qualscope, NULL, NULL); + qualscope, NULL, NULL, nullable_relids); } /* @@ -1436,6 +1493,10 @@ process_implied_equality(PlannerInfo *root, * This overlaps the functionality of process_implied_equality(), but we * must return the RestrictInfo, not push it into the joininfo tree. * + * Note: this function will copy item1 and item2, but it is caller's + * responsibility to make sure that the Relids parameters are fresh copies + * not shared with other uses. + * * Note: we do not do initialize_mergeclause_eclasses() here. It is * caller's responsibility that left_ec/right_ec be set as necessary. */ @@ -1444,7 +1505,8 @@ build_implied_join_equality(Oid opno, Oid collation, Expr *item1, Expr *item2, - Relids qualscope) + Relids qualscope, + Relids nullable_relids) { RestrictInfo *restrictinfo; Expr *clause; @@ -1461,9 +1523,6 @@ build_implied_join_equality(Oid opno, InvalidOid, collation); - /* Make a copy of qualscope to avoid problems if source EC changes */ - qualscope = bms_copy(qualscope); - /* * Build the RestrictInfo node itself. */ @@ -1472,7 +1531,7 @@ build_implied_join_equality(Oid opno, false, /* outerjoin_delayed */ false, /* pseudoconstant */ qualscope, /* required_relids */ - NULL); /* nullable_relids */ + nullable_relids); /* nullable_relids */ /* Set mergejoinability/hashjoinability flags */ check_mergejoinable(restrictinfo); diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index e01887d859b..14fcb5c0e97 100644 --- a/src/include/nodes/relation.h +++ b/src/include/nodes/relation.h @@ -596,6 +596,7 @@ typedef struct EquivalenceMember Expr *em_expr; /* the expression represented */ Relids em_relids; /* all relids appearing in em_expr */ + Relids em_nullable_relids; /* nullable by lower outer joins */ bool em_is_const; /* expression is pseudoconstant? */ bool em_is_child; /* derived version for a child relation? */ Oid em_datatype; /* the "nominal type" used by the opfamily */ diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h index 2f9bc032c35..a9c87f649e8 100644 --- a/src/include/optimizer/planmain.h +++ b/src/include/optimizer/planmain.h @@ -102,13 +102,15 @@ extern void process_implied_equality(PlannerInfo *root, Expr *item1, Expr *item2, Relids qualscope, + Relids nullable_relids, bool below_outer_join, bool both_const); extern RestrictInfo *build_implied_join_equality(Oid opno, Oid collation, Expr *item1, Expr *item2, - Relids qualscope); + Relids qualscope, + Relids nullable_relids); /* * prototypes for plan/analyzejoins.c diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index c0c72833339..34ead49ca62 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -2667,6 +2667,77 @@ select * from int4_tbl a full join int4_tbl b on false; (10 rows) -- +-- test handling of potential equivalence clauses above outer joins +-- +explain (costs off) +select q1, unique2, thousand, hundred + from int8_tbl a left join tenk1 b on q1 = unique2 + where coalesce(thousand,123) = q1 and q1 = coalesce(hundred,123); + QUERY PLAN +-------------------------------------------------------------------------------------- + Nested Loop Left Join + Filter: ((COALESCE(b.thousand, 123) = a.q1) AND (a.q1 = COALESCE(b.hundred, 123))) + -> Seq Scan on int8_tbl a + -> Index Scan using tenk1_unique2 on tenk1 b + Index Cond: (a.q1 = unique2) +(5 rows) + +select q1, unique2, thousand, hundred + from int8_tbl a left join tenk1 b on q1 = unique2 + where coalesce(thousand,123) = q1 and q1 = coalesce(hundred,123); + q1 | unique2 | thousand | hundred +----+---------+----------+--------- +(0 rows) + +explain (costs off) +select f1, unique2, case when unique2 is null then f1 else 0 end + from int4_tbl a left join tenk1 b on f1 = unique2 + where (case when unique2 is null then f1 else 0 end) = 0; + QUERY PLAN +-------------------------------------------------------------------- + Nested Loop Left Join + Filter: (CASE WHEN (b.unique2 IS NULL) THEN a.f1 ELSE 0 END = 0) + -> Seq Scan on int4_tbl a + -> Index Scan using tenk1_unique2 on tenk1 b + Index Cond: (a.f1 = unique2) +(5 rows) + +select f1, unique2, case when unique2 is null then f1 else 0 end + from int4_tbl a left join tenk1 b on f1 = unique2 + where (case when unique2 is null then f1 else 0 end) = 0; + f1 | unique2 | case +----+---------+------ + 0 | 0 | 0 +(1 row) + +-- +-- test ability to push constants through outer join clauses +-- +explain (costs off) + select * from int4_tbl a left join tenk1 b on f1 = unique2 where f1 = 0; + QUERY PLAN +------------------------------------------------- + Nested Loop Left Join + Join Filter: (a.f1 = b.unique2) + -> Seq Scan on int4_tbl a + Filter: (f1 = 0) + -> Index Scan using tenk1_unique2 on tenk1 b + Index Cond: (unique2 = 0) +(6 rows) + +explain (costs off) + select * from tenk1 a full join tenk1 b using(unique2) where unique2 = 42; + QUERY PLAN +------------------------------------------------- + Merge Full Join + Merge Cond: (a.unique2 = b.unique2) + -> Index Scan using tenk1_unique2 on tenk1 a + Index Cond: (unique2 = 42) + -> Index Scan using tenk1_unique2 on tenk1 b + Index Cond: (unique2 = 42) +(6 rows) + +-- -- test join removal -- begin; diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql index 2d53cf1725b..17fcc28f213 100644 --- a/src/test/regress/sql/join.sql +++ b/src/test/regress/sql/join.sql @@ -690,6 +690,38 @@ select * from int4_tbl a full join int4_tbl b on true; select * from int4_tbl a full join int4_tbl b on false; -- +-- test handling of potential equivalence clauses above outer joins +-- + +explain (costs off) +select q1, unique2, thousand, hundred + from int8_tbl a left join tenk1 b on q1 = unique2 + where coalesce(thousand,123) = q1 and q1 = coalesce(hundred,123); + +select q1, unique2, thousand, hundred + from int8_tbl a left join tenk1 b on q1 = unique2 + where coalesce(thousand,123) = q1 and q1 = coalesce(hundred,123); + +explain (costs off) +select f1, unique2, case when unique2 is null then f1 else 0 end + from int4_tbl a left join tenk1 b on f1 = unique2 + where (case when unique2 is null then f1 else 0 end) = 0; + +select f1, unique2, case when unique2 is null then f1 else 0 end + from int4_tbl a left join tenk1 b on f1 = unique2 + where (case when unique2 is null then f1 else 0 end) = 0; + +-- +-- test ability to push constants through outer join clauses +-- + +explain (costs off) + select * from int4_tbl a left join tenk1 b on f1 = unique2 where f1 = 0; + +explain (costs off) + select * from tenk1 a full join tenk1 b using(unique2) where unique2 = 42; + +-- -- test join removal -- |