From a79e0facf3af849698fe3a8ef7b01739bfab060e Mon Sep 17 00:00:00 2001 From: Rahul Yadav Date: Mon, 5 Oct 2026 07:46:46 +0100 Subject: [PATCH] Count NULL matches for IS NOT DISTINCT FROM in semi/antijoins The previous commit leaves semijoins and antijoins alone, so in EXISTS and NOT EXISTS an outer row whose input is NULL is still estimated to have no match under IS NOT DISTINCT FROM. With 30% NULLs on both sides, EXISTS was estimated at 700 rows against 1300 actual rows, and NOT EXISTS at 1300 against 700. For these joins the "=" estimate is the fraction of outer rows that have a match. Add the fraction of outer rows whose input is NULL, since they all have a match if any inner row's input is NULL. Assume there is one if we expect at least one, and scale it down if we expect fewer. Do this where the NOT around the DistinctExpr is estimated. A plain IS DISTINCT FROM in a semijoin is estimated as the complement of the IS NOT DISTINCT FROM estimate, so adding the NULL matches to the DistinctExpr itself would lower that estimate too, and it is already too low (1300 against 2000 actual rows in the same test). Author: Rahul Yadav Discussion: https://postgr.es/m/17545-a0ca4de888953169@postgresql.org --- src/backend/optimizer/path/clausesel.c | 68 ++++++++++++++++++++++- src/test/regress/expected/planner_est.out | 19 +++++++ src/test/regress/sql/planner_est.sql | 11 ++++ 3 files changed, 96 insertions(+), 2 deletions(-) diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c index 53de0018bd..04db29d335 100644 --- a/src/backend/optimizer/path/clausesel.c +++ b/src/backend/optimizer/path/clausesel.c @@ -45,6 +45,8 @@ static void addRangeClause(RangeQueryClause **rqlist, Node *clause, static RelOptInfo *find_single_rel_for_clauses(PlannerInfo *root, List *clauses); static double expr_nullfrac(PlannerInfo *root, Node *expr); +static Selectivity semijoin_nulls_selectivity(PlannerInfo *root, List *args, + SpecialJoinInfo *sjinfo); static Selectivity clauselist_selectivity_or(PlannerInfo *root, List *clauses, int varRelid, @@ -599,6 +601,49 @@ expr_nullfrac(PlannerInfo *root, Node *expr) return nullfrac; } +/* + * semijoin_nulls_selectivity - + * For "x IS NOT DISTINCT FROM y" as a semijoin or antijoin clause, + * estimate the fraction of outer rows whose input is null and that have + * an inner row whose input is null to match. + */ +static Selectivity +semijoin_nulls_selectivity(PlannerInfo *root, List *args, + SpecialJoinInfo *sjinfo) +{ + VariableStatData vardata1; + VariableStatData vardata2; + VariableStatData *outer; + VariableStatData *inner; + bool join_is_reversed; + double outer_nullfrac = 0.0; + double inner_nulls = 0.0; + + get_join_variables(root, args, sjinfo, + &vardata1, &vardata2, &join_is_reversed); + outer = join_is_reversed ? &vardata2 : &vardata1; + inner = join_is_reversed ? &vardata1 : &vardata2; + + if (HeapTupleIsValid(outer->statsTuple)) + outer_nullfrac = + ((Form_pg_statistic) GETSTRUCT(outer->statsTuple))->stanullfrac; + + /* + * The outer rows with a null input all have a match if there is at least + * one inner row with a null input. Assume that if we expect at least + * one, and scale it down if we expect fewer. + */ + if (HeapTupleIsValid(inner->statsTuple) && inner->rel) + inner_nulls = + ((Form_pg_statistic) GETSTRUCT(inner->statsTuple))->stanullfrac * + inner->rel->rows; + + ReleaseVariableStats(vardata1); + ReleaseVariableStats(vardata2); + + return outer_nullfrac * Min(inner_nulls, 1.0); +} + /* * treat_as_join_clause - * Decide whether an operator clause is to be handled by the @@ -819,13 +864,31 @@ clause_selectivity_ext(PlannerInfo *root, } else if (is_notclause(clause)) { + Node *arg = (Node *) get_notclausearg((Expr *) clause); + /* inverse of the selectivity of the underlying clause */ s1 = 1.0 - clause_selectivity_ext(root, - (Node *) get_notclausearg((Expr *) clause), + arg, varRelid, jointype, sjinfo, use_extended_stats); + + /* + * "x IS NOT DISTINCT FROM y" is NOT of a DistinctExpr. As a semijoin + * or antijoin clause, its estimate so far is that of "x = y", the + * fraction of outer rows having a non-null match. Add the outer rows + * whose input is null and that can match an inner null. + */ + if (IsA(arg, DistinctExpr) && + treat_as_join_clause(root, arg, rinfo, varRelid, sjinfo) && + (sjinfo->jointype == JOIN_SEMI || sjinfo->jointype == JOIN_ANTI)) + { + s1 += semijoin_nulls_selectivity(root, + ((DistinctExpr *) arg)->args, + sjinfo); + CLAMP_PROBABILITY(s1); + } } else if (is_andclause(clause)) { @@ -878,7 +941,8 @@ clause_selectivity_ext(PlannerInfo *root, * contained operator is "=" not "<>", so we must negate the result. * First add the fraction of rows having both inputs null, which "=" * does not count. We don't do that for semijoins and antijoins, - * where the "=" estimate is not a fraction of row pairs. + * where the "=" estimate is not a fraction of row pairs; see the NOT + * case above for those. */ if (IsA(clause, DistinctExpr)) { diff --git a/src/test/regress/expected/planner_est.out b/src/test/regress/expected/planner_est.out index 07b88e5229..66ea7afd3f 100644 --- a/src/test/regress/expected/planner_est.out +++ b/src/test/regress/expected/planner_est.out @@ -257,4 +257,23 @@ true, true, false, true) LIMIT 1; Nested Loop (cost=N..N rows=16930 width=N) (actual rows=16930.00 loops=1) (1 row) +-- Ensure NULLs are matched in semijoins and antijoins +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t2 t2 WHERE EXISTS + (SELECT 1 FROM distinct_t1 t1 WHERE t1.a IS NOT DISTINCT FROM t2.a);$$, +true, true, false, true) LIMIT 1; + explain_mask_costs +---------------------------------------------------------------------------------- + Nested Loop Semi Join (cost=N..N rows=170 width=N) (actual rows=170.00 loops=1) +(1 row) + +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t2 t2 WHERE NOT EXISTS + (SELECT 1 FROM distinct_t1 t1 WHERE t1.a IS NOT DISTINCT FROM t2.a);$$, +true, true, false, true) LIMIT 1; + explain_mask_costs +-------------------------------------------------------------------------------- + Nested Loop Anti Join (cost=N..N rows=30 width=N) (actual rows=30.00 loops=1) +(1 row) + DROP FUNCTION explain_mask_costs(text, bool, bool, bool, bool); diff --git a/src/test/regress/sql/planner_est.sql b/src/test/regress/sql/planner_est.sql index e5e42ad8d0..58e812cd6e 100644 --- a/src/test/regress/sql/planner_est.sql +++ b/src/test/regress/sql/planner_est.sql @@ -178,4 +178,15 @@ SELECT * FROM explain_mask_costs($$ SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a IS DISTINCT FROM t2.a;$$, true, true, false, true) LIMIT 1; +-- Ensure NULLs are matched in semijoins and antijoins +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t2 t2 WHERE EXISTS + (SELECT 1 FROM distinct_t1 t1 WHERE t1.a IS NOT DISTINCT FROM t2.a);$$, +true, true, false, true) LIMIT 1; + +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t2 t2 WHERE NOT EXISTS + (SELECT 1 FROM distinct_t1 t1 WHERE t1.a IS NOT DISTINCT FROM t2.a);$$, +true, true, false, true) LIMIT 1; + DROP FUNCTION explain_mask_costs(text, bool, bool, bool, bool); -- 2.50.1 (Apple Git-155)