Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.98.2) (envelope-from ) id 1xDcyl-00000000cYQ-3VOM for pgsql-bugs@arkaria.postgresql.org; Mon, 05 Oct 2026 07:19:20 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.98.2) (envelope-from ) id 1xDcyk-00000008cAg-3ZqE for pgsql-bugs@arkaria.postgresql.org; Mon, 05 Oct 2026 07:19:18 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.98.2) (envelope-from ) id 1xDcyk-00000008cAX-13vm for pgsql-bugs@lists.postgresql.org; Mon, 05 Oct 2026 07:19:18 +0000 Received: from mail.w14.tutanota.de ([185.205.69.214]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.98.2) (envelope-from ) id 1xDcyh-00000000Qwz-1vQM for pgsql-bugs@lists.postgresql.org; Mon, 05 Oct 2026 07:19:17 +0000 Received: from tutadb.w10.tutanota.de (w10.api.tuta.com [IPv6:fd:ac::d:10]) by mail.w14.tutanota.de (Postfix) with ESMTP id 4216318FDD2C5 for ; Mon, 5 Oct 2026 09:19:13 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; t=1791184752; s=s1; d=rhyadav.dev; h=From:From:To:To:Subject:Subject:Content-Description:Content-ID:Content-Type:Content-Type:Content-Transfer-Encoding:Cc:Cc:Date:Date:In-Reply-To:In-Reply-To:MIME-Version:MIME-Version:Message-ID:Message-ID:Reply-To:References:References:Sender; bh=gCUaCDvtQGumywpMqjlzBidm8YpNdZGPKJEXETcI4Bw=; b=IB1HZ8XvRE8rlXKxwS2rMgegPnR76GEuZJaLEbM01+32yZ/Wn5+yHN1TmWtnha5t u1wpd0irPA3fhOCJbsM0CKYIbb48PmsPwUuIBefczmZIIYtVs5x9zX7YnmMKO5mdQPA RVVwrSFFu5JMZO6N/qUs5yQnYkbZdS4HuVAtrDTFkOvfbHgAqORkmDF6In/8CIvJVKw 5DGrW2jV+Tq4j5rh4Bem5ZDUNeoxsElwOpFEmk864+lkhFN3wpVwiV2mvCU1FteROZw JRsc3n9OP0T94g7OF06rvg2U5CqzwBJeHWbhBxQKBW/IksZI8pcq2lb9zQM2uc2sFvp Kgr8Z1gXyw== Date: Mon, 5 Oct 2026 09:19:12 +0200 (CEST) From: Rahul To: shihao zhong Cc: Rpsalmi , Pgsql Bugs , Guofenglinux Message-ID: In-Reply-To: References: <17545-a0ca4de888953169@postgresql.org> Subject: Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_346830_1270842616.1791184753264" Feedback-ID: 01f8c5108c48fea26a092a077590a8fcdbfcdbb733bc38e3db5db9540fc242b99227bb05256e786b1fc713cdb05f073377d63f8aec9e32cbf77d26f42c5d89118b:TurnOnPrivacy!:tutamail List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk ------=_Part_346830_1270842616.1791184753264 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hi Shihao, Thanks for picking this up.=C2=A0 I tested v1 on master (a464d31ff6).=C2=A0= It builds without warnings, the regression tests pass, and no existing plan changes.=C2=A0 Estimated vs actual rows, on two 2000-row tables with 30% NULLs and on the report's 1000 all-NULL rows: =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 master=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 v1=C2=A0=C2=A0=C2=A0 actual =C2=A0 JOIN ON a IS NOT DISTINCT FROM=C2=A0=C2=A0=C2=A0 28000=C2=A0=C2=A0= =C2=A0 388000=C2=A0=C2=A0=C2=A0 388000 =C2=A0 JOIN ON a IS DISTINCT FROM=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 3972000=C2= =A0=C2=A0 3612000=C2=A0=C2=A0 3612000 =C2=A0 LEFT JOIN, IS NOT DISTINCT FROM=C2=A0=C2=A0 28000=C2=A0=C2=A0=C2=A0 = 388000=C2=A0=C2=A0=C2=A0 388700 =C2=A0 report, all NULLs=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 1=C2= =A0=C2=A0 1000000=C2=A0=C2=A0 1000000 IS DISTINCT FROM, which Richard pointed out has the same problem, is fixed as well.=C2=A0 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: =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 master=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 v1=C2=A0=C2=A0=C2=A0 actual =C2=A0 EXISTS=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 700=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0 700=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 1300 =C2=A0 NOT EXISTS=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0 1300=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 1300=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 700 I think they're worth handling in the same patch.=C2=A0 NOT EXISTS with IS NOT DISTINCT FROM is a common way to find rows missing from another table when NULLs should match.=C2=A0 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).=C2=A0 For a semijoin or antijoin the "=3D" 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.=C2=A0 It assumes there is one if it expects at least one, and scales down if it expects fewer.=C2=A0 The two cases above then come out at 1300 and 700, and the average matches at 298.5.=C2=A0 It adds two tests on your tables: =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 v1=C2=A0=C2=A0 v1+patch=C2=A0= =C2=A0=C2=A0 actual =C2=A0 EXISTS=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0 70=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 170=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0 170 =C2=A0 NOT EXISTS=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 130=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 30=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0 30 It works where the NOT around the DistinctExpr is estimated, not in the DistinctExpr branch.=C2=A0 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).=C2=A0 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.=C2=A0 With the inner side cut to 2 rows it's 388 against 600 (28 with v1).=C2=A0 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.=C2=A0 I don't think that needs handling here. Regards, Rahul Yadav ------=_Part_346830_1270842616.1791184753264 Content-Type: text/plain; charset=us-ascii; name=semijoin-null-matches-on-v1.txt Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=semijoin-null-matches-on-v1.txt 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) ------=_Part_346830_1270842616.1791184753264--