postgres.git / summary / log / commit / refs
commit 763d563eaec82528fdd49c07830a2dae00567778
Author: Richard Guo <rguo@postgresql.org>
Date: Wed Sep 02 04:37:41 2026 +0000
Remove quals made redundant by reducing outer joins to antijoins
When reduce_outer_joins reduces an outer join to an antijoin, any IS
NULL qual on a Var from the antijoin's nullable side is necessarily
true. Previously, such quals were discarded later in
distribute_qual_to_rels, mainly to avoid bogus selectivity estimates.
But that discard was incomplete: the qual remained in the jointree,
while its Vars were not counted in attr_needed. Since commit
2ebf25e7d, join removal edits the jointree and expects it to contain
no other references to a removed rel, so it could remove a rel that
such a discarded qual still references, and then trip an assertion on
the qual's stale Var.
To fix, move this processing to an earlier phase: such quals are now
removed from the jointree by reduce_outer_joins itself. This way
later phases see a consistent query tree, and
check_redundant_nullability_qual is no longer needed, so remove it.
Back-patch to v16, as with commit 2ebf25e7d.
Reported-by: Tender Wang <tndrwang@gmail.com>
Author: Richard Guo <guofenglinux@gmail.com>
Reviewed-by: Tom Lane <tgl@sss.pgh.pa.us>
Discussion: https://postgr.es/m/CAHewXNk8b0TsSy4dL=CO7FXL2W3WBm0BcdP-zwNJePa-Qj4HzA@mail.gmail.com
Backpatch-through: 16
src/backend/optimizer/plan/initsplan.c | 61 ---------------------
src/backend/optimizer/prep/prepjointree.c | 89 ++++++++++++++++++++++++++++---
src/backend/optimizer/util/clauses.c | 11 ++--
src/test/regress/expected/join.out | 36 +++++++++++++
src/test/regress/sql/join.sql | 18 +++++++
5 files changed, 143 insertions(+), 72 deletions(-)
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index d8a5c242eef..74fea8ab814 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -146,7 +146,6 @@ static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
bool has_clone,
bool is_clone,
List **postponed_oj_qual_list);
-static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
static Relids get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids);
static void check_mergejoinable(RestrictInfo *restrictinfo);
static void check_hashjoinable(RestrictInfo *restrictinfo);
@@ -2871,10 +2870,6 @@ distribute_quals_to_rels(PlannerInfo *root, List *clauses,
* '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
- * at least those special joins that are syntactically below this qual.
- * (We now need that only for detection of redundant IS NULL quals.)
*/
static void
distribute_qual_to_rels(PlannerInfo *root, Node *clause,
@@ -3078,15 +3073,6 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
*/
is_pushed_down = true;
- /*
- * It's possible that this is an IS NULL clause that's redundant with
- * a lower antijoin; if so we can just discard it. We need not test
- * in any of the other cases, because this will only be possible for
- * pushed-down clauses.
- */
- if (check_redundant_nullability_qual(root, clause))
- return;
-
/* Feed qual to the equivalence machinery, if allowed by caller */
maybe_equivalence = allow_equivalence;
@@ -3253,53 +3239,6 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
distribute_restrictinfo_to_rels(root, restrictinfo);
}
-/*
- * check_redundant_nullability_qual
- * Check to see if the qual is an IS NULL qual that is redundant with
- * a lower JOIN_ANTI join.
- *
- * We want to suppress redundant IS NULL quals, not so much to save cycles
- * as to avoid generating bogus selectivity estimates for them. So if
- * redundancy is detected here, distribute_qual_to_rels() just throws away
- * the qual.
- */
-static bool
-check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
-{
- Var *forced_null_var;
- ListCell *lc;
-
- /* Check for IS NULL, and identify the Var forced to NULL */
- forced_null_var = find_forced_null_var(clause);
- if (forced_null_var == NULL)
- return false;
-
- /*
- * If the Var comes from the nullable side of a lower antijoin, the IS
- * NULL condition is necessarily true. If it's not nulled by anything,
- * there is no point in searching the join_info_list. Otherwise, we need
- * to find out whether the nulling rel is an antijoin.
- */
- if (forced_null_var->varnullingrels == NULL)
- return false;
-
- foreach(lc, root->join_info_list)
- {
- SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
-
- /*
- * This test will not succeed if sjinfo->ojrelid is zero, which is
- * possible for an antijoin that was converted from a semijoin; but in
- * such a case the Var couldn't have come from its nullable side.
- */
- if (sjinfo->jointype == JOIN_ANTI && sjinfo->ojrelid != 0 &&
- bms_is_member(sjinfo->ojrelid, forced_null_var->varnullingrels))
- return true;
- }
-
- return false;
-}
-
/*
* add_base_clause_to_rel
* Add 'restrictinfo' as a baserestrictinfo to the base relation denoted
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 3c384579ee7..165c1eeb241 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -97,6 +97,7 @@ typedef struct reduce_outer_joins_pass2_state
{
Relids inner_reduced; /* OJ relids reduced to plain inner joins */
List *partial_reduced; /* List of partially reduced FULL joins */
+ Relids anti_reduced; /* OJ relids reduced to antijoins */
} reduce_outer_joins_pass2_state;
typedef struct reduce_outer_joins_partial_state
@@ -163,6 +164,9 @@ static void reduce_outer_joins_pass2(Node *jtnode,
List *forced_null_vars);
static void report_reduced_full_join(reduce_outer_joins_pass2_state *state2,
int rtindex, Relids relids);
+static void remove_redundant_nullability_quals(Node *jtnode,
+ Relids antijoins);
+static Node *strip_redundant_nullability_quals(Node *quals, Relids antijoins);
static bool has_notnull_forced_var(PlannerInfo *root, List *forced_null_vars,
reduce_outer_joins_pass1_state *right_state);
static Node *remove_useless_results_recurse(PlannerInfo *root, Node *jtnode,
@@ -3241,8 +3245,7 @@ flatten_simple_union_all(PlannerInfo *root)
* could pass the upper WHERE, and we can conclude that what the query is
* really specifying is an anti-semijoin. We change the join type from
* JOIN_LEFT to JOIN_ANTI. The IS NULL clause then becomes redundant, and
- * must be removed to prevent bogus selectivity calculations, but we leave
- * it to distribute_qual_to_rels to get rid of such clauses.
+ * is removed at the end of this phase; see remove_redundant_nullability_quals.
*
* Also, we get rid of JOIN_RIGHT cases by flipping them around to become
* JOIN_LEFT. This saves some code here and in some later planner routines;
@@ -3279,6 +3282,7 @@ reduce_outer_joins(PlannerInfo *root)
state2.inner_reduced = NULL;
state2.partial_reduced = NIL;
+ state2.anti_reduced = NULL;
reduce_outer_joins_pass2((Node *) root->parse->jointree,
state1, &state2,
@@ -3321,6 +3325,74 @@ reduce_outer_joins(PlannerInfo *root)
full_join_relids,
statep->unreduced_side);
}
+
+ /*
+ * Finally, remove any quals made redundant by reducing outer joins to
+ * antijoins.
+ */
+ if (!bms_is_empty(state2.anti_reduced))
+ remove_redundant_nullability_quals((Node *) root->parse->jointree,
+ state2.anti_reduced);
+}
+
+/*
+ * remove_redundant_nullability_quals
+ * Remove quals made redundant by reducing outer joins to antijoins.
+ *
+ * An IS NULL qual on a Var from the nullable side of a lower antijoin is
+ * necessarily true. Keeping such a qual would not be wrong, but it would
+ * generate bogus selectivity estimates, and it could prevent join removal
+ * from later removing the rel(s) it references.
+ */
+static void
+remove_redundant_nullability_quals(Node *jtnode, Relids antijoins)
+{
+ if (jtnode == NULL)
+ return;
+ if (IsA(jtnode, RangeTblRef))
+ {
+ /* nothing to do here */
+ }
+ else if (IsA(jtnode, FromExpr))
+ {
+ FromExpr *f = (FromExpr *) jtnode;
+ ListCell *l;
+
+ foreach(l, f->fromlist)
+ remove_redundant_nullability_quals(lfirst(l), antijoins);
+ f->quals = strip_redundant_nullability_quals(f->quals, antijoins);
+ }
+ else if (IsA(jtnode, JoinExpr))
+ {
+ JoinExpr *j = (JoinExpr *) jtnode;
+
+ remove_redundant_nullability_quals(j->larg, antijoins);
+ remove_redundant_nullability_quals(j->rarg, antijoins);
+ j->quals = strip_redundant_nullability_quals(j->quals, antijoins);
+ }
+ else
+ elog(ERROR, "unrecognized jointree node type: %d",
+ (int) nodeTag(jtnode));
+}
+
+/*
+ * strip_redundant_nullability_quals
+ * Strip redundant IS NULL quals from one implicit-AND qual list.
+ */
+static Node *
+strip_redundant_nullability_quals(Node *quals, Relids antijoins)
+{
+ List *newquals = NIL;
+
+ foreach_ptr(Node, clause, castNode(List, quals))
+ {
+ Var *var = find_forced_null_var(clause);
+
+ if (var && bms_overlap(var->varnullingrels, antijoins))
+ continue;
+ newquals = lappend(newquals, clause);
+ }
+ return (Node *) newquals;
}
/*
@@ -3435,9 +3507,10 @@ reduce_outer_joins_pass1(Node *jtnode)
*
* Returns info in state2 about outer joins that were successfully simplified.
* Joins that were fully reduced to inner joins are all added to
- * state2->inner_reduced. If a full join is reduced to a left join,
- * it needs its own entry in state2->partial_reduced, since that will
- * require custom processing to remove only the correct nullingrel markers.
+ * state2->inner_reduced, and joins that became antijoins are all added to
+ * state2->anti_reduced. If a full join is reduced to a left join, it also
+ * needs its own entry in state2->partial_reduced, since that will require
+ * custom processing to remove only the correct nullingrel markers.
*/
static void
reduce_outer_joins_pass2(Node *jtnode,
@@ -3600,7 +3673,8 @@ reduce_outer_joins_pass2(Node *jtnode,
/*
* Apply the jointype change, if any, to both jointree node and RTE.
- * Also, if we changed an RTE to INNER, add its RTI to inner_reduced.
+ * Also, if we changed an RTE to INNER, add its RTI to inner_reduced;
+ * if we changed it to ANTI, add its RTI to anti_reduced.
*/
if (rtindex && jointype != j->jointype)
{
@@ -3612,6 +3686,9 @@ reduce_outer_joins_pass2(Node *jtnode,
if (jointype == JOIN_INNER)
state2->inner_reduced = bms_add_member(state2->inner_reduced,
rtindex);
+ else if (jointype == JOIN_ANTI)
+ state2->anti_reduced = bms_add_member(state2->anti_reduced,
+ rtindex);
}
j->jointype = jointype;
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 329c22bf133..c8d3901a436 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -2058,11 +2058,12 @@ find_forced_null_vars(Node *node)
* *only* nullness of the particular Var, not any other conditions.
*
* This is just the single-clause case of find_forced_null_vars(), without
- * any allowance for AND conditions. It's used by initsplan.c on individual
- * qual clauses. The reason for not just applying find_forced_null_vars()
- * is that if an AND of an IS NULL clause with something else were to somehow
- * survive AND/OR flattening, initsplan.c might get fooled into discarding
- * the whole clause when only the IS NULL part of it had been proved redundant.
+ * any allowance for AND conditions. It's used by prepjointree.c on
+ * individual qual clauses. The reason for not just applying
+ * find_forced_null_vars() is that if an AND of an IS NULL clause with
+ * something else were to somehow survive AND/OR flattening, prepjointree.c
+ * might get fooled into discarding the whole clause when only the IS NULL
+ * part of it had been proved redundant.
*/
Var *
find_forced_null_var(Node *node)
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 38b91724703..9f09e234375 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -3358,6 +3358,42 @@ where t3.a is null;
-> Seq Scan on tenk1 t1
(13 rows)
+-- Test that quals made redundant by reducing an outer join to an antijoin are
+-- removed from the jointree
+-- (fallout from the fix for bug #19560)
+create temp table tbl_anti_pk (a int primary key);
+-- t3.a IS NULL is redundant, and the t2/t3 join can be removed
+explain (costs off)
+select 1 from tbl_anti_pk t1 left join
+ (tbl_anti_pk t2 left join tbl_anti_pk t3 on t3.a = t2.a) on t2.a = t1.a
+where t2.a is null and t3.a is null;
+ QUERY PLAN
+----------------------------------------
+ Hash Anti Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on tbl_anti_pk t1
+ -> Hash
+ -> Seq Scan on tbl_anti_pk t2
+(5 rows)
+
+-- the redundant qual can also be a degenerate ON clause of an upper join
+explain (costs off)
+select 1 from tbl_anti_pk t1 left join
+ (tbl_anti_pk t2 left join
+ (tbl_anti_pk t3 left join tbl_anti_pk t5 on t5.a = t3.a) on t3.a = t2.a)
+ on t3.a is null and t5.a is null;
+ QUERY PLAN
+----------------------------------------------------
+ Nested Loop Left Join
+ -> Seq Scan on tbl_anti_pk t1
+ -> Materialize
+ -> Hash Anti Join
+ Hash Cond: (t2.a = t3.a)
+ -> Seq Scan on tbl_anti_pk t2
+ -> Hash
+ -> Seq Scan on tbl_anti_pk t3
+(8 rows)
+
rollback;
--
-- regression test for bogus RTE_GROUP entries
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index f3ba371b7e4..e6950dafca3 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -910,6 +910,24 @@ select * from tenk1 t1 left join
(tbl_anti t2 left join tbl_anti t3 on t2.c = t3.c) on t1.unique1 = t2.b
where t3.a is null;
+-- Test that quals made redundant by reducing an outer join to an antijoin are
+-- removed from the jointree
+-- (fallout from the fix for bug #19560)
+create temp table tbl_anti_pk (a int primary key);
+
+-- t3.a IS NULL is redundant, and the t2/t3 join can be removed
+explain (costs off)
+select 1 from tbl_anti_pk t1 left join
+ (tbl_anti_pk t2 left join tbl_anti_pk t3 on t3.a = t2.a) on t2.a = t1.a
+where t2.a is null and t3.a is null;
+
+-- the redundant qual can also be a degenerate ON clause of an upper join
+explain (costs off)
+select 1 from tbl_anti_pk t1 left join
+ (tbl_anti_pk t2 left join
+ (tbl_anti_pk t3 left join tbl_anti_pk t5 on t5.a = t3.a) on t3.a = t2.a)
+ on t3.a is null and t5.a is null;
+
rollback;
--
[parent: 8e6860fb9638]