pg.ddx.io  pgsql-bugs@postgresql.org mailing list archive  
help / color / mirror / Atom feed
BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
9+ messages / 6 participants
[nested] [flat]

* BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2022-07-11 14:18  PG Bug reporting form <noreply@postgresql.org>
  0 siblings, 2 replies; 9+ messages in thread

From: PG Bug reporting form @ 2022-07-11 14:18 UTC (permalink / raw)
  To: pgsql-bugs@lists.postgresql.org; +Cc: rpsalmi@gmail.com

The following bug has been logged on the website:

Bug reference:      17545
Logged by:          Roope Salmi
Email address:      rpsalmi@gmail.com
PostgreSQL version: 14.4
Operating system:   Ubuntu 22.04
Description:        

Hi,

It appears that selectivity for "IS NOT DISTINCT FROM" clauses regard the
proportion of NULLs in the same way as "=", leading to polar opposite row
count
estimates.

In practice this causes nested loop joins to be used when that is not
appropriate. Not sure if this is a known issue, but I was unable to find
any
previous mentions of it.

Here I create a table with one column and 1000 rows of NULL. A cartesian
product
with "WHERE x.a = y.a" correctly estimates that there are around zero
matching
rows. "x.a IS NOT DISTINCT FROM y.a" incorrectly gives the same estimate,
whereas "x.a = y.a OR (x.a IS NULL AND y.a IS NULL)", which should be
equivalent, gives the correct 1000000.

postgres=# CREATE TABLE test(a INTEGER);
CREATE TABLE
postgres=# INSERT INTO test(a) SELECT NULL FROM generate_series(1, 1000);
INSERT 0 1000
postgres=# ANALYZE test;
ANALYZE
postgres=# EXPLAIN SELECT FROM test x, test y WHERE x.a = y.a;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Merge Join  (cost=127.66..137.67 rows=1 width=0)
   Merge Cond: (x.a = y.a)
   ->  Sort  (cost=63.83..66.33 rows=1000 width=4)
         Sort Key: x.a
         ->  Seq Scan on test x  (cost=0.00..14.00 rows=1000 width=4)
   ->  Sort  (cost=63.83..66.33 rows=1000 width=4)
         Sort Key: y.a
         ->  Seq Scan on test y  (cost=0.00..14.00 rows=1000 width=4)
(8 rows)

postgres=# EXPLAIN SELECT FROM test x, test y
postgres=# WHERE x.a IS NOT DISTINCT FROM y.a;
                              QUERY PLAN                              
----------------------------------------------------------------------
 Nested Loop  (cost=0.00..15030.50 rows=1 width=0)
   Join Filter: (NOT (x.a IS DISTINCT FROM y.a))
   ->  Seq Scan on test x  (cost=0.00..14.00 rows=1000 width=4)
   ->  Materialize  (cost=0.00..19.00 rows=1000 width=4)
         ->  Seq Scan on test y  (cost=0.00..14.00 rows=1000 width=4)
(5 rows)

postgres=# EXPLAIN SELECT FROM test x, test y                               
    
postgres-# WHERE x.a = y.a OR (x.a IS NULL AND y.a IS NULL);
                              QUERY PLAN                              
----------------------------------------------------------------------
 Nested Loop  (cost=0.00..15030.50 rows=1000000 width=0)
   Join Filter: ((x.a = y.a) OR ((x.a IS NULL) AND (y.a IS NULL)))
   ->  Seq Scan on test x  (cost=0.00..14.00 rows=1000 width=4)
   ->  Materialize  (cost=0.00..19.00 rows=1000 width=4)
         ->  Seq Scan on test y  (cost=0.00..14.00 rows=1000 width=4)
(5 rows)



^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2022-07-12 04:35  Richard Guo <guofenglinux@gmail.com>
  parent: PG Bug reporting form <noreply@postgresql.org>
  1 sibling, 1 reply; 9+ messages in thread

From: Richard Guo @ 2022-07-12 04:35 UTC (permalink / raw)
  To: rpsalmi@gmail.com, PostgreSQL mailing lists <pgsql-bugs@lists.postgresql.org>

On Mon, Jul 11, 2022 at 10:36 PM PG Bug reporting form <
noreply@postgresql.org> wrote:

> Hi,
>
> It appears that selectivity for "IS NOT DISTINCT FROM" clauses regard the
> proportion of NULLs in the same way as "=", leading to polar opposite row
> count
> estimates.
>
> In practice this causes nested loop joins to be used when that is not
> appropriate. Not sure if this is a known issue, but I was unable to find
> any
> previous mentions of it.


This can also happen to 'IS DISTINCT FROM'.

# EXPLAIN SELECT FROM test x, test y WHERE x.a IS DISTINCT FROM y.a;
                              QUERY PLAN
----------------------------------------------------------------------
 Nested Loop  (cost=0.00..15030.50 rows=1000000 width=0)
   Join Filter: (x.a IS DISTINCT FROM y.a)
   ->  Seq Scan on test x  (cost=0.00..14.00 rows=1000 width=4)
   ->  Materialize  (cost=0.00..19.00 rows=1000 width=4)
         ->  Seq Scan on test y  (cost=0.00..14.00 rows=1000 width=4)
(5 rows)

DistinctExpr has the same representation as OpExpr with operator "=". So
we estimate its selectivity just as if it is 'x.a = y.a', and then
invert the result.

For OpExpr 'x.a = y.a', because no MCV lists are available, we estimate
its selectivity as MIN(1/nd1,1/nd2)*(1-nullfrac1)*(1-nullfrac2). Note
that both nullfrac1 and nullfrac2 are 100% in the case, so the
selectivity is calculated as zero, and the inverted result is 1, which
is for DistinctExpr.

The comment in the codes has explained this behavior, as it says:

   /*
    * DistinctExpr has the same representation as OpExpr, but the
    * contained operator is "=" not "<>", so we must negate the result.
    * This estimation method doesn't give the right behavior for nulls,
    * but it's better than doing nothing.
    */
   if (IsA(clause, DistinctExpr))
       s1 = 1.0 - s1;

So maybe this is a known issue?

Thanks
Richard

^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2022-07-12 04:41  Tom Lane <tgl@sss.pgh.pa.us>
  parent: Richard Guo <guofenglinux@gmail.com>
  0 siblings, 0 replies; 9+ messages in thread

From: Tom Lane @ 2022-07-12 04:41 UTC (permalink / raw)
  To: Richard Guo <guofenglinux@gmail.com>; +Cc: rpsalmi@gmail.com, PostgreSQL mailing lists <pgsql-bugs@lists.postgresql.org>

Richard Guo <guofenglinux@gmail.com> writes:
> The comment in the codes has explained this behavior, as it says:
>     * This estimation method doesn't give the right behavior for nulls,
>     * but it's better than doing nothing.
> So maybe this is a known issue?

It's a nobodys-bothered-to-make-it-better issue.  In general, PG's
treatment of IS [NOT] DISTINCT FROM is pretty lame --- for example,
you might wish that IS NOT DISTINCT FROM could use an index in
the way that "=" can, but that's never been made to happen.

			regards, tom lane





^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2026-10-05 04:14  shihao zhong <zhong950419@gmail.com>
  parent: PG Bug reporting form <noreply@postgresql.org>
  1 sibling, 1 reply; 9+ messages in thread

From: shihao zhong @ 2026-10-05 04:14 UTC (permalink / raw)
  To: rpsalmi@gmail.com; pgsql-bugs@lists.postgresql.org

Hi,

Here is a patch for the estimate. IS NOT DISTINCT FROM is estimated
like "=", so row pairs with NULL on both sides are never counted. The
patch adds the product of the two null fractions to the "=" estimate.

Two tables of 2000 rows, 30% NULL, joined on
x.a IS NOT DISTINCT FROM y.a:

  master   rows=1400    actual rows=361400
  patched  rows=361400  actual rows=361400

Thanks,
Shihao

Attachments: download all (2 files, .tar.gz)

v1-0001-Count-NULL-pairs-in-IS-NOT-DISTINCT-FROM-selectiv.patch (application/octet-stream, 3.0K) download From cfe0851bc00880ef244938ee5cfdc241d8951049 Mon Sep 17 00:00:00 2001 From: shihao zhong <zhong950419@gmail.com> Date: Sun, 4 Oct 2026 23:30:36 -0400 Subject: [PATCH v1 1/2] Count NULL pairs in IS [NOT] DISTINCT FROM selectivity clause_selectivity() estimated IS NOT DISTINCT FROM the same as "=", so rows with both inputs NULL were not counted. Add the product of the two null fractions before negating. Semijoins and antijoins are left as they were. Discussion: https://postgr.es/m/17545-a0ca4de888953169@postgresql.org --- src/backend/optimizer/path/clausesel.c | 37 ++++++++++++++++++++++++-- 1 file changed, 35 insertions(+), 2 deletions(-) diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c index 25c4d177ad9..53de0018bd6 100644 --- a/src/backend/optimizer/path/clausesel.c +++ b/src/backend/optimizer/path/clausesel.c @@ -14,6 +14,8 @@ */ #include "postgres.h" +#include "access/htup_details.h" +#include "catalog/pg_statistic.h" #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/optimizer.h" @@ -42,6 +44,7 @@ static void addRangeClause(RangeQueryClause **rqlist, Node *clause, bool varonleft, bool isLTsel, Selectivity s2); static RelOptInfo *find_single_rel_for_clauses(PlannerInfo *root, List *clauses); +static double expr_nullfrac(PlannerInfo *root, Node *expr); static Selectivity clauselist_selectivity_or(PlannerInfo *root, List *clauses, int varRelid, @@ -577,6 +580,25 @@ find_single_rel_for_clauses(PlannerInfo *root, List *clauses) return NULL; /* no clauses */ } +/* + * expr_nullfrac - + * Return the null fraction of an expression, or zero if we have no + * statistics for it. + */ +static double +expr_nullfrac(PlannerInfo *root, Node *expr) +{ + VariableStatData vardata; + double nullfrac = 0.0; + + examine_variable(root, expr, 0, &vardata); + if (HeapTupleIsValid(vardata.statsTuple)) + nullfrac = ((Form_pg_statistic) GETSTRUCT(vardata.statsTuple))->stanullfrac; + ReleaseVariableStats(vardata); + + return nullfrac; +} + /* * treat_as_join_clause - * Decide whether an operator clause is to be handled by the @@ -854,11 +876,22 @@ clause_selectivity_ext(PlannerInfo *root, /* * DistinctExpr has the same representation as OpExpr, but the * contained operator is "=" not "<>", so we must negate the result. - * This estimation method doesn't give the right behavior for nulls, - * but it's better than doing nothing. + * 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. */ if (IsA(clause, DistinctExpr)) + { + if (sjinfo == NULL || + (sjinfo->jointype != JOIN_SEMI && + sjinfo->jointype != JOIN_ANTI)) + { + s1 += expr_nullfrac(root, linitial(opclause->args)) * + expr_nullfrac(root, lsecond(opclause->args)); + CLAMP_PROBABILITY(s1); + } s1 = 1.0 - s1; + } } else if (is_funcclause(clause)) { -- 2.37.1 (Apple Git-137.1)
v1-0002-Add-row-estimate-tests-for-IS-NOT-DISTINCT-FROM.patch (application/octet-stream, 4.2K) download From 31077001143c5a580759c9f82231ee9a532c9aa7 Mon Sep 17 00:00:00 2001 From: shihao zhong <zhong950419@gmail.com> Date: Sun, 4 Oct 2026 23:30:37 -0400 Subject: [PATCH v1 2/2] Add row estimate tests for IS [NOT] DISTINCT FROM Check that join estimates count rows with NULL on both sides. Discussion: https://postgr.es/m/17545-a0ca4de888953169@postgresql.org --- src/test/regress/expected/planner_est.out | 36 +++++++++++++++++++++++ src/test/regress/sql/planner_est.sql | 25 ++++++++++++++++ 2 files changed, 61 insertions(+) diff --git a/src/test/regress/expected/planner_est.out b/src/test/regress/expected/planner_est.out index 236cb274a78..07b88e5229d 100644 --- a/src/test/regress/expected/planner_est.out +++ b/src/test/regress/expected/planner_est.out @@ -221,4 +221,40 @@ EXPLAIN (COSTS OFF) SELECT * FROM char_table_1 WHERE c < 'Q'; Filter: (c < 'Q'::"char") (2 rows) +-- +-- Test IS [NOT] DISTINCT FROM join estimates with NULLs on both sides. Only +-- the top plan line is shown, since the rest is not stable across platforms. +-- +CREATE TEMP TABLE distinct_t1 AS + SELECT CASE WHEN i > 30 THEN i END AS a FROM generate_series(1, 100) i; +CREATE TEMP TABLE distinct_t2 AS + SELECT CASE WHEN i > 100 THEN i - 100 END AS a FROM generate_series(1, 200) i; +ANALYZE distinct_t1, distinct_t2; +-- Ensure pairs of NULLs are counted +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a IS NOT DISTINCT FROM t2.a;$$, +true, true, false, true) LIMIT 1; + explain_mask_costs +-------------------------------------------------------------------------- + Nested Loop (cost=N..N rows=3070 width=N) (actual rows=3070.00 loops=1) +(1 row) + +-- The equivalent OR clause should get about the same estimate +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a = t2.a OR (t1.a IS NULL AND t2.a IS NULL);$$, +true, true, false, true) LIMIT 1; + explain_mask_costs +-------------------------------------------------------------------------- + Nested Loop (cost=N..N rows=3060 width=N) (actual rows=3070.00 loops=1) +(1 row) + +-- Ensure pairs of NULLs are not counted +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; + explain_mask_costs +---------------------------------------------------------------------------- + Nested Loop (cost=N..N rows=16930 width=N) (actual rows=16930.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 2b696a4e4e5..e5e42ad8d0d 100644 --- a/src/test/regress/sql/planner_est.sql +++ b/src/test/regress/sql/planner_est.sql @@ -153,4 +153,29 @@ CREATE TEMP TABLE char_table_1 AS ANALYZE char_table_1; EXPLAIN (COSTS OFF) SELECT * FROM char_table_1 WHERE c < 'Q'; +-- +-- Test IS [NOT] DISTINCT FROM join estimates with NULLs on both sides. Only +-- the top plan line is shown, since the rest is not stable across platforms. +-- +CREATE TEMP TABLE distinct_t1 AS + SELECT CASE WHEN i > 30 THEN i END AS a FROM generate_series(1, 100) i; +CREATE TEMP TABLE distinct_t2 AS + SELECT CASE WHEN i > 100 THEN i - 100 END AS a FROM generate_series(1, 200) i; +ANALYZE distinct_t1, distinct_t2; + +-- Ensure pairs of NULLs are counted +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a IS NOT DISTINCT FROM t2.a;$$, +true, true, false, true) LIMIT 1; + +-- The equivalent OR clause should get about the same estimate +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a = t2.a OR (t1.a IS NULL AND t2.a IS NULL);$$, +true, true, false, true) LIMIT 1; + +-- Ensure pairs of NULLs are not counted +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; + DROP FUNCTION explain_mask_costs(text, bool, bool, bool, bool); -- 2.37.1 (Apple Git-137.1)
^ permalink raw reply [nested|flat] 9+ messages in thread

* Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2026-10-05 07:19  Rahul <rahul@rhyadav.dev>
  parent: shihao zhong <zhong950419@gmail.com>
  0 siblings, 2 replies; 9+ messages in thread

From: Rahul @ 2026-10-05 07:19 UTC (permalink / raw)
  To: shihao zhong <zhong950419@gmail.com>; +Cc: Rpsalmi <rpsalmi@gmail.com>; Pgsql Bugs <pgsql-bugs@lists.postgresql.org>; Guofenglinux <guofenglinux@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)
^ permalink raw reply [nested|flat] 9+ messages in thread

* Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2026-10-05 15:10  shihao zhong <zhong950419@gmail.com>
  parent: Rahul <rahul@rhyadav.dev>
  1 sibling, 0 replies; 9+ messages in thread

From: shihao zhong @ 2026-10-05 15:10 UTC (permalink / raw)
  To: Rahul <rahul@rhyadav.dev>; +Cc: Rpsalmi <rpsalmi@gmail.com>; Pgsql Bugs <pgsql-bugs@lists.postgresql.org>; Guofenglinux <guofenglinux@gmail.com>

Hi Rahul,

Thanks for testing, and for the patch. I agree that EXISTS and NOT
EXISTS should be handled too.

v2 is attached, with your patch merged in and you as co-author. The
commit message of 0001 now mentions IS DISTINCT FROM too.

My test get the same numbers as you.

Thanks,
Shihao

Attachments: download all (2 files, .tar.gz)

v2-0001-Count-NULL-pairs-in-IS-NOT-DISTINCT-FROM-selectiv.patch (application/octet-stream, 5.8K) download From 4aacc66df3abca1b85b3d030d5a91fb65a5b8fef Mon Sep 17 00:00:00 2001 From: shihao zhong <zhong950419@gmail.com> Date: Mon, 5 Oct 2026 11:08:32 -0400 Subject: [PATCH v2 1/2] Count NULL pairs in IS [NOT] DISTINCT FROM selectivity clause_selectivity() estimated IS NOT DISTINCT FROM the same as "=", so rows with both inputs NULL were not counted. Add the product of the two null fractions before negating, which fixes IS DISTINCT FROM too. For semijoins and antijoins, add the fraction of outer rows whose input is NULL, scaled down if less than one inner NULL is expected. Co-authored-by: Rahul Yadav <rahul@rhyadav.dev> Discussion: https://postgr.es/m/17545-a0ca4de888953169@postgresql.org --- src/backend/optimizer/path/clausesel.c | 103 ++++++++++++++++++++++++- 1 file changed, 100 insertions(+), 3 deletions(-) diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c index 25c4d177ad9..04db29d335f 100644 --- a/src/backend/optimizer/path/clausesel.c +++ b/src/backend/optimizer/path/clausesel.c @@ -14,6 +14,8 @@ */ #include "postgres.h" +#include "access/htup_details.h" +#include "catalog/pg_statistic.h" #include "nodes/nodeFuncs.h" #include "optimizer/clauses.h" #include "optimizer/optimizer.h" @@ -42,6 +44,9 @@ static void addRangeClause(RangeQueryClause **rqlist, Node *clause, bool varonleft, bool isLTsel, Selectivity s2); 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, @@ -577,6 +582,68 @@ find_single_rel_for_clauses(PlannerInfo *root, List *clauses) return NULL; /* no clauses */ } +/* + * expr_nullfrac - + * Return the null fraction of an expression, or zero if we have no + * statistics for it. + */ +static double +expr_nullfrac(PlannerInfo *root, Node *expr) +{ + VariableStatData vardata; + double nullfrac = 0.0; + + examine_variable(root, expr, 0, &vardata); + if (HeapTupleIsValid(vardata.statsTuple)) + nullfrac = ((Form_pg_statistic) GETSTRUCT(vardata.statsTuple))->stanullfrac; + ReleaseVariableStats(vardata); + + 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 @@ -797,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)) { @@ -854,11 +939,23 @@ clause_selectivity_ext(PlannerInfo *root, /* * DistinctExpr has the same representation as OpExpr, but the * contained operator is "=" not "<>", so we must negate the result. - * This estimation method doesn't give the right behavior for nulls, - * but it's better than doing nothing. + * 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; see the NOT + * case above for those. */ if (IsA(clause, DistinctExpr)) + { + if (sjinfo == NULL || + (sjinfo->jointype != JOIN_SEMI && + sjinfo->jointype != JOIN_ANTI)) + { + s1 += expr_nullfrac(root, linitial(opclause->args)) * + expr_nullfrac(root, lsecond(opclause->args)); + CLAMP_PROBABILITY(s1); + } s1 = 1.0 - s1; + } } else if (is_funcclause(clause)) { -- 2.37.1 (Apple Git-137.1)
v2-0002-Add-row-estimate-tests-for-IS-NOT-DISTINCT-FROM.patch (application/octet-stream, 5.6K) download From 6d1a0a477d9ea978025e321833b87038153e5719 Mon Sep 17 00:00:00 2001 From: shihao zhong <zhong950419@gmail.com> Date: Mon, 5 Oct 2026 11:08:32 -0400 Subject: [PATCH v2 2/2] Add row estimate tests for IS [NOT] DISTINCT FROM Check that join, semijoin and antijoin estimates count rows with NULL on both sides. Co-authored-by: Rahul Yadav <rahul@rhyadav.dev> Discussion: https://postgr.es/m/17545-a0ca4de888953169@postgresql.org --- src/test/regress/expected/planner_est.out | 55 +++++++++++++++++++++++ src/test/regress/sql/planner_est.sql | 36 +++++++++++++++ 2 files changed, 91 insertions(+) diff --git a/src/test/regress/expected/planner_est.out b/src/test/regress/expected/planner_est.out index 236cb274a78..66ea7afd3fd 100644 --- a/src/test/regress/expected/planner_est.out +++ b/src/test/regress/expected/planner_est.out @@ -221,4 +221,59 @@ EXPLAIN (COSTS OFF) SELECT * FROM char_table_1 WHERE c < 'Q'; Filter: (c < 'Q'::"char") (2 rows) +-- +-- Test IS [NOT] DISTINCT FROM join estimates with NULLs on both sides. Only +-- the top plan line is shown, since the rest is not stable across platforms. +-- +CREATE TEMP TABLE distinct_t1 AS + SELECT CASE WHEN i > 30 THEN i END AS a FROM generate_series(1, 100) i; +CREATE TEMP TABLE distinct_t2 AS + SELECT CASE WHEN i > 100 THEN i - 100 END AS a FROM generate_series(1, 200) i; +ANALYZE distinct_t1, distinct_t2; +-- Ensure pairs of NULLs are counted +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a IS NOT DISTINCT FROM t2.a;$$, +true, true, false, true) LIMIT 1; + explain_mask_costs +-------------------------------------------------------------------------- + Nested Loop (cost=N..N rows=3070 width=N) (actual rows=3070.00 loops=1) +(1 row) + +-- The equivalent OR clause should get about the same estimate +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a = t2.a OR (t1.a IS NULL AND t2.a IS NULL);$$, +true, true, false, true) LIMIT 1; + explain_mask_costs +-------------------------------------------------------------------------- + Nested Loop (cost=N..N rows=3060 width=N) (actual rows=3070.00 loops=1) +(1 row) + +-- Ensure pairs of NULLs are not counted +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; + explain_mask_costs +---------------------------------------------------------------------------- + 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 2b696a4e4e5..58e812cd6ec 100644 --- a/src/test/regress/sql/planner_est.sql +++ b/src/test/regress/sql/planner_est.sql @@ -153,4 +153,40 @@ CREATE TEMP TABLE char_table_1 AS ANALYZE char_table_1; EXPLAIN (COSTS OFF) SELECT * FROM char_table_1 WHERE c < 'Q'; +-- +-- Test IS [NOT] DISTINCT FROM join estimates with NULLs on both sides. Only +-- the top plan line is shown, since the rest is not stable across platforms. +-- +CREATE TEMP TABLE distinct_t1 AS + SELECT CASE WHEN i > 30 THEN i END AS a FROM generate_series(1, 100) i; +CREATE TEMP TABLE distinct_t2 AS + SELECT CASE WHEN i > 100 THEN i - 100 END AS a FROM generate_series(1, 200) i; +ANALYZE distinct_t1, distinct_t2; + +-- Ensure pairs of NULLs are counted +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a IS NOT DISTINCT FROM t2.a;$$, +true, true, false, true) LIMIT 1; + +-- The equivalent OR clause should get about the same estimate +SELECT * FROM explain_mask_costs($$ +SELECT * FROM distinct_t1 t1 JOIN distinct_t2 t2 ON t1.a = t2.a OR (t1.a IS NULL AND t2.a IS NULL);$$, +true, true, false, true) LIMIT 1; + +-- Ensure pairs of NULLs are not counted +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.37.1 (Apple Git-137.1)
^ permalink raw reply [nested|flat] 9+ messages in thread

* Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2026-10-05 16:57  Rahul <rahul@rhyadav.dev>
  parent: Rahul <rahul@rhyadav.dev>
  1 sibling, 1 reply; 9+ messages in thread

From: Rahul @ 2026-10-05 16:57 UTC (permalink / raw)
  To: shihao zhong <zhong950419@gmail.com>; +Cc: Rpsalmi <rpsalmi@gmail.com>; Pgsql Bugs <pgsql-bugs@lists.postgresql.org>; Guofenglinux <guofenglinux@gmail.com>

Hi Shihao,

Thanks for merging it.  v2 gives exactly the same code as v1 plus my
patch, which is what I tested, and it applies cleanly to current
master.

Could you add it to the next commitfest so it doesn't get lost?

Regards,
Rahul Yadav










^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2026-10-05 18:38  shihao zhong <zhong950419@gmail.com>
  parent: Rahul <rahul@rhyadav.dev>
  0 siblings, 0 replies; 9+ messages in thread

From: shihao zhong @ 2026-10-05 18:38 UTC (permalink / raw)
  To: Rahul <rahul@rhyadav.dev>; +Cc: Rpsalmi <rpsalmi@gmail.com>; Pgsql Bugs <pgsql-bugs@lists.postgresql.org>; Guofenglinux <guofenglinux@gmail.com>

Hi Rahul,

https://commitfest.postgresql.org/patch/7396/

Thanks,
Shihao

^ permalink  raw  reply  [nested|flat] 9+ messages in thread

* Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
@ 2026-10-26 13:18  Greg Burd <greg@burd.me>
  0 siblings, 0 replies; 9+ messages in thread

From: Greg Burd @ 2026-10-26 13:18 UTC (permalink / raw)
  To: pgsql-bugs; +Cc: zhong950419@gmail.com; rahul@rhyadav.dev; rpsalmi@gmail.com; pgsql-bugs@lists.postgresql.org; guofenglinux@gmail.com

On Mon, 5 Oct 2026 14:38:05 -0400, shihao zhong <zhong950419@gmail.com> wrote:
> Hi Rahul,
> 
> https://commitfest.postgresql.org/patch/7396/
> 
> Thanks,
> Shihao

Hey Shihao,

First off, thanks for working on this.  This issue caught my attention,
so I measured the selectivity error this fixes in an effort to quantify
the size of it, and it turns out to be large in the join case.

I tested on master at the patch's merge-base (126976a8ffc) and
master+v2.  For a join on t1.a IS NOT DISTINCT FROM t2.a, where both
columns carry NULLs, the estimate must count NULL-NULL pairs as matching
(NULL IS NOT DISTINCT FROM NULL is true).  So I had a solver run a
differential selectivity check over 120 randomized two-table joins with
varied NULL fractions and distinct counts, estimate vs actual rows:

   master:   worst case off by 4915x
   master+v2: worst case 1.0x (exact on every case I generated)

The ScalarArrayOp sibling the patch also touches, col <> ALL (ARRAY[..
NULL]), estimates within 1.5x of actual on the patched build.

One note on reproducing it: the error is specific to the join path.  My
first attempt used IS NOT DISTINCT FROM as a scalar filter (WHERE a IS
NOT DISTINCT FROM <const>), where master already estimates well, so a
scalar-only test would wrongly suggest nothing was wrong.  The patch's
planner_est.sql exercises the join form, which is where the 4915x comes
from.

+1 for the patch.

best.

-greg







^ permalink  raw  reply  [nested|flat] 9+ messages in thread


end of thread, other threads:[~2026-10-26 13:18 UTC | newest]

Thread overview: 9+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2022-07-11 14:18 BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs PG Bug reporting form <noreply@postgresql.org>
2022-07-12 04:35 ` Richard Guo <guofenglinux@gmail.com>
2022-07-12 04:41   ` Tom Lane <tgl@sss.pgh.pa.us>
2026-10-05 04:14 ` shihao zhong <zhong950419@gmail.com>
2026-10-05 07:19   ` Rahul <rahul@rhyadav.dev>
2026-10-05 15:10     ` shihao zhong <zhong950419@gmail.com>
2026-10-05 16:57     ` Rahul <rahul@rhyadav.dev>
2026-10-05 18:38       ` shihao zhong <zhong950419@gmail.com>
2026-10-26 13:18 Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs Greg Burd <greg@burd.me>

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