Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs

From: ZizhuanLiu X-MAN <44973863(at)qq(dot)com>
To: Greg Burd <greg(at)burd(dot)me>, zhong950419 <zhong950419(at)gmail(dot)com>, rahul <rahul(at)rhyadav(dot)dev>, pgsql-bugs <pgsql-bugs(at)postgresql(dot)org>
Cc: rpsalmi <rpsalmi(at)gmail(dot)com>, pgsql-bugs <pgsql-bugs(at)lists(dot)postgresql(dot)org>, guofenglinux <guofenglinux(at)gmail(dot)com>
Subject: Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs
Date: 2026-11-20 12:58:49
Message-ID: tencent_F85023353EC117B719D1BE4E147D7B593A0A@qq.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-bugs

Hi,

Building on Shihao's patch and Rahul's analysis, I would like to propose
this implementation for NULL-safe join estimates, including the IS
DISTINCT FROM SEMI/ANTI case Rahul identified. &nbsp;It also fixes a related
ordinary <&gt; misestimate, which I suggest reviewing here under BUG #17545.

A particularly clear ordinary <&gt; example is statement 6 of not_eq_x1.sql
in the local test suite, run against the xman4 database:

&nbsp; &nbsp; EXPLAIN ANALYZE
&nbsp; &nbsp; SELECT FROM t_test1 x INNER JOIN t_test1 y ON x.c2 <&gt; y.c3;

The table has 1,000 rows and c3 is entirely NULL. &nbsp;The reported master
estimate is 1,000,000 rows; the actual result is zero. &nbsp;The patched result
recorded for that statement is:

&nbsp; &nbsp; Master estimate &nbsp; &nbsp;Patched estimate &nbsp; &nbsp;Actual rows
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1000000 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0

Every comparison with y.c3 yields UNKNOWN, so no pair satisfies strict <&gt;.
The corrected selectivity is zero; the displayed estimate of one comes
from the planner's minimum row estimate. &nbsp;The comma-join spelling in
statement 2 of the same SQL file gives the same patched result.

The c2 column contains 600 NULLs, 200 ones and 200 twos. &nbsp;The c2 self-joins
in statement 6 of the four *_x0.sql files give these recorded results:

&nbsp; &nbsp; Predicate &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Patched estimate &nbsp; &nbsp;Actual rows
&nbsp; &nbsp; = &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 80000 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;80000
&nbsp; &nbsp; <&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;80000 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;80000
&nbsp; &nbsp; IS NOT DISTINCT FROM &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 440000 &nbsp; &nbsp; &nbsp; &nbsp; 440000
&nbsp; &nbsp; IS DISTINCT FROM &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 560000 &nbsp; &nbsp; &nbsp; &nbsp; 560000

The ordinary 1 - E formula would instead estimate the <&gt; case at 920,000.
For non-SEMI/ANTI inner and outer join clauses, let E be the existing
ordinary equality pair selectivity, n1/n2 the input NULL fractions, and
B = (1 - n1) * (1 - n2) the fraction of pairs with two non-NULL inputs.
The intended estimates are:

&nbsp; &nbsp; = &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; E
&nbsp; &nbsp; <&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;B - E
&nbsp; &nbsp; IS NOT DISTINCT FROM &nbsp; &nbsp;E + n1 * n2
&nbsp; &nbsp; IS DISTINCT FROM &nbsp; &nbsp; &nbsp; &nbsp;1 - E - n1 * n2

SEMI/ANTI joins instead use S, the fraction of outer rows with at least
one inner partner. &nbsp;Statement 17 of eq_x0.sql and not_eq_x0.sql tests
x.c1 = y.c1 and x.c1 <&gt; y.c1 inside EXISTS. &nbsp;Both queries are estimated at
1,000 rows and actually return 1,000. &nbsp;Every outer value has both an equal
and an unequal inner partner; complementing the equality SEMI estimate
would therefore give the wrong S for inequality.

The actual SEMI/ANTI statements 18 and 22 of the four *_x1.sql files,
using x.c2 and the all-NULL y.c3, also distinguish the NULL rules:

&nbsp; &nbsp; Predicate &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;SEMI estimate/actual &nbsp; &nbsp;ANTI estimate/actual
&nbsp; &nbsp; = &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1/0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1000/1000
&nbsp; &nbsp; <&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1/0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1000/1000
&nbsp; &nbsp; IS NOT DISTINCT FROM &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 600/600 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;400/400
&nbsp; &nbsp; IS DISTINCT FROM &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 400/400 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;600/600

The two 1/0 entries again reflect the minimum row estimate.

The implementation works as follows:

1. clausesel.c recognizes NULL-safe join clauses and passes their context
&nbsp; &nbsp;through nullsafe_join_selectivity(). &nbsp;Only the recognized built-in
&nbsp; &nbsp;eqjoinsel/neqjoinsel procedures receive an optional sixth boolean
&nbsp; &nbsp;argument, null_safe_compare. &nbsp;Other procedures keep their five-argument
&nbsp; &nbsp;calling convention and legacy dispatch. &nbsp;IS DISTINCT FROM uses the
&nbsp; &nbsp;inequality negator only when the operator pair uses those built-in
&nbsp; &nbsp;estimators.

2. eqjoinsel() preserves ordinary = estimates and adds NULL contributions
&nbsp; &nbsp;for IS NOT DISTINCT FROM only when null_safe_compare is enabled.
&nbsp; &nbsp;Non-SEMI/ANTI joins return E + n1 * n2. &nbsp;For SEMI/ANTI, add NULL partners
&nbsp; &nbsp;to the existing non-NULL equality existence estimate S_eq:

&nbsp; &nbsp; &nbsp; &nbsp;S = S_eq + n_outer * min(n_inner * N_inner, 1)

&nbsp; &nbsp;Here n_outer/n_inner are the outer/inner NULL fractions, and N_inner is
&nbsp; &nbsp;the effective inner row estimate. &nbsp;Return S = 0 for a provably empty
&nbsp; &nbsp;inner input, reset S_eq to zero for an all-NULL inner input, and retain
&nbsp; &nbsp;the existing bound based on the inner-join estimate. &nbsp;eqjoinsel_inner()
&nbsp; &nbsp;and eqjoinsel_semi() retain their original algorithms and signatures,
&nbsp; &nbsp;with only their MCV matcher calls adapted. &nbsp;The shared match count
&nbsp; &nbsp;continues to describe only non-NULL MCV pairs.

3. For non-SEMI/ANTI joins, neqjoinsel() uses B - E for ordinary <&gt; and
&nbsp; &nbsp;complements the NULL-safe eqjoinsel() estimate for IS DISTINCT FROM,
&nbsp; &nbsp;giving 1 - E - n1 * n2. &nbsp;Its SEMI/ANTI path uses distinctjoinsel_semi()
&nbsp; &nbsp;and distinctjoinsel_semi_internal() to estimate S separately under
&nbsp; &nbsp;ordinary or NULL-safe semantics, rather than simply complementing
&nbsp; &nbsp;equality existence. &nbsp;Optional equality match indices identify the
&nbsp; &nbsp;inner MCV equal to each outer MCV; the estimator checks for other MCVs,
&nbsp; &nbsp;NULLs where allowed, and residual values. &nbsp;It retains the existing hash
&nbsp; &nbsp;matching support and leaves the original statistics slots unchanged.
&nbsp; &nbsp;Both SEMI/ANTI estimators return S; the existing caller uses S and 1 - S
&nbsp; &nbsp;for SEMI and ANTI output rows, respectively.

The upper-level NULL correction discussed earlier is reasonable when the
underlying estimator returns ordinary equality selectivity. &nbsp;This patch
makes that distinction explicit for the built-in estimators. &nbsp;In the
unpatched code, IS DISTINCT FROM still uses the equality estimator followed
by an upper-level complement, so fixing ordinary neqjoinsel() alone does
not break that existing route. &nbsp;The extra context is needed by the route
chosen here, where <&gt; and IS DISTINCT FROM share neqjoinsel() and the same
operator OID. &nbsp;The optional sixth argument is an interface proposal for
review, rather than a prerequisite for fixing ordinary <&gt; separately.

This local snapshot is v3.1.me.5, based on commit
1d657c6e013e152ed37b42a22ee9f291179ee50f. &nbsp;It adds regression coverage
for the NULL rules, residual values, absent MCV lists, cross-type matching
and custom estimator procedures, and updates one existing join order
following the ordinary <&gt; correction.

The numerical results above come from the original SQL suite in
~/4_patch/test_distint_from: eq_x[0-3].sql, not_eq_x[0-3].sql,
is_not_distinct_from_x[0-3].sql and is_distinct_from_x[0-3].sql. &nbsp;The saved
run has 16 files and 384 statements, classified by their actual SQL text:

&nbsp; &nbsp; Join type &nbsp; &nbsp;Queries &nbsp; &nbsp;Exact &nbsp; &nbsp;Zero-row floor &nbsp; &nbsp;Other differences
&nbsp; &nbsp; INNER &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;128 &nbsp; &nbsp; &nbsp; 94 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;34 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0
&nbsp; &nbsp; SEMI &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;72 &nbsp; &nbsp; &nbsp; 53 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;19 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0
&nbsp; &nbsp; ANTI &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;56 &nbsp; &nbsp; &nbsp; 36 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;20 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;0
&nbsp; &nbsp; LEFT &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;64 &nbsp; &nbsp; &nbsp; 41 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 23
&nbsp; &nbsp; RIGHT &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 64 &nbsp; &nbsp; &nbsp; 41 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 23
&nbsp; &nbsp; Total &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;384 &nbsp; &nbsp; &nbsp;265 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;73 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 46

All actual row counts agree with counts independently calculated from
the table's value frequencies. &nbsp;INNER, SEMI and ANTI estimates are exact
apart from the zero-row floor. &nbsp;The remaining 46 differences are LEFT/RIGHT
outer-join padding estimates. &nbsp;No statistics on the original table were
recollected. &nbsp;The results were unchanged by moving NULL handling into
eqjoinsel(). &nbsp;Subsequent edits standardized the null_safe_compare parameter
name, clarified comments, and reduced duplicate regression cases. &nbsp;The
targeted planner_est regression passes. &nbsp;The supplied selected-tests.sql
and saved result records identify the original files and statement numbers
used above.

The patch does not reconstruct filtered inner distributions or resolve
all uncertainty about missing statistics and residual-value overlap.
Outer-join padding remains approximate, as the suite shows. &nbsp;This work
changes join estimates; restriction estimates and executor/index support
are outside its scope.

I would appreciate feedback on the estimator interface and dispatch, and
on the SEMI/ANTI heuristics. &nbsp;I suggest keeping the ordinary <&gt; reproduction
and the NULL-safe estimation changes together for review in this thread.

Discussion: https://www.postgresql.org/message-id/flat/17545-a0ca4de888953169%40postgresql.org
CommitFest: https://commitfest.postgresql.org/patch/7396/

Attached is an alternative implementation for discussion. It is not intended to supersede the current&nbsp;
Ready for Committer patch at this stage.

I will also report the selectivity misestimation for ordinary <&gt; separately and prepare a separate patch,&nbsp;
so that this issue can be reviewed independently.

The attached test materials cover ordinary = and <&gt; comparisons, NULL-safe IS [NOT] DISTINCT FROM&nbsp;
comparisons, and various join types:
- setup.sql — test data setup
- test_sql.tar — test SQL files
- test_result.xlsx — test results

regards,
--
ZizhuanLiu&nbsp;(X-MAN)&nbsp;
44973863(at)qq(dot)com

Attachment Content-Type Size
test_result.xlsx application/octet-stream 66.7 KB
setup.sql application/octet-stream 5.2 KB
test_sql.tar application/octet-stream 50.0 KB
v3-0001-Fix-join-selectivity-for-NULL-safe-comparisons-and-ordinary-inequality.patch.txt application/octet-stream 58.4 KB

In response to

Responses

Browse pgsql-bugs by date

  From Date Subject
Next Message PG Bug reporting form 2026-11-20 13:13:19 BUG #19926: Incorrect join selectivity for <> with NULLs (related to BUG #17545)
Previous Message Nitin Motiani 2026-11-20 10:52:30 Re: BUG #19922: CYCLE/SEARCH with a window in the recursive term: could not find replacement targetlist entry