pg.ddx.io  pgsql-bugs@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Rahul <rahul@rhyadav.dev>
To: shihao zhong <zhong950419@gmail.com>
Cc: Rpsalmi <rpsalmi@gmail.com>
Cc: Pgsql Bugs <pgsql-bugs@lists.postgresql.org>
Cc: Guofenglinux <guofenglinux@gmail.com>
Subject: Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
Date: Mon, 5 Oct 2026 09:19:12 +0200 (CEST)
Message-ID: <P39vWJT--J-9@rhyadav.dev> (raw)
In-Reply-To: <CAGRkXqSkyW7QqriK9v-aH0QjA7s_DhtEfG0RrxEy8jO3_d6LAw@mail.gmail.com>
References: <17545-a0ca4de888953169@postgresql.org>
	<CAGRkXqSkyW7QqriK9v-aH0QjA7s_DhtEfG0RrxEy8jO3_d6LAw@mail.gmail.com>

Hi Shihao,

Thanks for picking this up.  I tested v1 on master (a464d31ff6).  It
builds without warnings, the regression tests pass, and no existing
plan changes.  Estimated vs actual rows, on two 2000-row tables with
30% NULLs and on the report's 1000 all-NULL rows:

                                   master        v1    actual
  JOIN ON a IS NOT DISTINCT FROM    28000    388000    388000
  JOIN ON a IS DISTINCT FROM      3972000   3612000   3612000
  LEFT JOIN, IS NOT DISTINCT FROM   28000    388000    388700
  report, all NULLs                     1   1000000   1000000

IS DISTINCT FROM, which Richard pointed out has the same problem, is
fixed as well.  That may be worth a sentence in the commit message,
which only describes the IS NOT DISTINCT FROM side.

EXISTS and NOT EXISTS are still off, since 0001 leaves semijoins and
antijoins alone:

                                   master        v1    actual
  EXISTS                              700       700      1300
  NOT EXISTS                         1300      1300       700

I think they're worth handling in the same patch.  NOT EXISTS with IS
NOT DISTINCT FROM is a common way to find rows missing from another
table when NULLs should match.  It also affects costing:
compute_semi_anti_join_factors() divides the inner join estimate,
which v1 raises, by the semijoin estimate, which it doesn't change.
So the average number of matches per matching outer row goes from 40
on master to 554 with v1, against 298.5 actual.

The attached patch on top of v1 handles them (it's a .txt, so cfbot
stays on v1).  For a semijoin or antijoin the "=" estimate is the
fraction of outer rows that have a match, so it adds the fraction of
outer rows whose input is NULL, since they all have a match if any
inner row's input is NULL.  It assumes there is one if it expects at
least one, and scales down if it expects fewer.  The two cases above
then come out at 1300 and 700, and the average matches at 298.5.  It
adds two tests on your tables:

                     v1   v1+patch    actual
  EXISTS             70        170       170
  NOT EXISTS        130         30        30

It works where the NOT around the DistinctExpr is estimated, not in
the DistinctExpr branch.  A plain IS DISTINCT FROM inside EXISTS is
estimated as the complement of the IS NOT DISTINCT FROM estimate, so
changing the DistinctExpr branch would lower that one too, and it is
already too low (1300 against 2000 actual rows).  With the patch it
doesn't change.

I also tried the arguments in either order, an extra key column,
all-NULL tables and the inner side cut to 200 rows, and those match
the actual rows too.  With the inner side cut to 2 rows it's 388
against 600 (28 with v1).  With NULLs on only one side nothing
changes, as expected.

One case neither version gets right is two columns of the same table
whose NULLs are in the same rows: 330 against 2000 actual rows (10 on
master), since the two null fractions are taken as independent.  I
don't think that needs handling here.

Regards,
Rahul Yadav

Attachments:

semijoin-null-matches-on-v1.txt (text/plain, 7.5K) download From a79e0facf3af849698fe3a8ef7b01739bfab060e Mon Sep 17 00:00:00 2001 From: Rahul Yadav <rahul@rhyadav.dev> 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 <rahul@rhyadav.dev> 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)

view thread (9+ messages)  latest in thread

Message-ID: <P39vWJT--J-9@rhyadav.dev>
Permalink:  ../P39vWJT--J-9@rhyadav.dev/
Also on:    postgresql.org/message-id/P39vWJT--J-9@rhyadav.dev

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-bugs@postgresql.org
  Cc: rahul@rhyadav.dev, zhong950419@gmail.com, rpsalmi@gmail.com, guofenglinux@gmail.com
  Subject: Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
  In-Reply-To: <P39vWJT--J-9@rhyadav.dev>
  References: <17545-a0ca4de888953169@postgresql.org> <CAGRkXqSkyW7QqriK9v-aH0QjA7s_DhtEfG0RrxEy8jO3_d6LAw@mail.gmail.com> <P39vWJT--J-9@rhyadav.dev>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox