| 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. It also fixes a related
ordinary <> misestimate, which I suggest reviewing here under BUG #17545.
A particularly clear ordinary <> example is statement 6 of not_eq_x1.sql
in the local test suite, run against the xman4 database:
EXPLAIN ANALYZE
SELECT FROM t_test1 x INNER JOIN t_test1 y ON x.c2 <> y.c3;
The table has 1,000 rows and c3 is entirely NULL. The reported master
estimate is 1,000,000 rows; the actual result is zero. The patched result
recorded for that statement is:
Master estimate Patched estimate Actual rows
1000000 1 0
Every comparison with y.c3 yields UNKNOWN, so no pair satisfies strict <>.
The corrected selectivity is zero; the displayed estimate of one comes
from the planner's minimum row estimate. 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. The c2 self-joins
in statement 6 of the four *_x0.sql files give these recorded results:
Predicate Patched estimate Actual rows
= 80000 80000
<> 80000 80000
IS NOT DISTINCT FROM 440000 440000
IS DISTINCT FROM 560000 560000
The ordinary 1 - E formula would instead estimate the <> 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:
= E
<> B - E
IS NOT DISTINCT FROM E + n1 * n2
IS DISTINCT FROM 1 - E - n1 * n2
SEMI/ANTI joins instead use S, the fraction of outer rows with at least
one inner partner. Statement 17 of eq_x0.sql and not_eq_x0.sql tests
x.c1 = y.c1 and x.c1 <> y.c1 inside EXISTS. Both queries are estimated at
1,000 rows and actually return 1,000. 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:
Predicate SEMI estimate/actual ANTI estimate/actual
= 1/0 1000/1000
<> 1/0 1000/1000
IS NOT DISTINCT FROM 600/600 400/400
IS DISTINCT FROM 400/400 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
through nullsafe_join_selectivity(). Only the recognized built-in
eqjoinsel/neqjoinsel procedures receive an optional sixth boolean
argument, null_safe_compare. Other procedures keep their five-argument
calling convention and legacy dispatch. IS DISTINCT FROM uses the
inequality negator only when the operator pair uses those built-in
estimators.
2. eqjoinsel() preserves ordinary = estimates and adds NULL contributions
for IS NOT DISTINCT FROM only when null_safe_compare is enabled.
Non-SEMI/ANTI joins return E + n1 * n2. For SEMI/ANTI, add NULL partners
to the existing non-NULL equality existence estimate S_eq:
S = S_eq + n_outer * min(n_inner * N_inner, 1)
Here n_outer/n_inner are the outer/inner NULL fractions, and N_inner is
the effective inner row estimate. Return S = 0 for a provably empty
inner input, reset S_eq to zero for an all-NULL inner input, and retain
the existing bound based on the inner-join estimate. eqjoinsel_inner()
and eqjoinsel_semi() retain their original algorithms and signatures,
with only their MCV matcher calls adapted. The shared match count
continues to describe only non-NULL MCV pairs.
3. For non-SEMI/ANTI joins, neqjoinsel() uses B - E for ordinary <> and
complements the NULL-safe eqjoinsel() estimate for IS DISTINCT FROM,
giving 1 - E - n1 * n2. Its SEMI/ANTI path uses distinctjoinsel_semi()
and distinctjoinsel_semi_internal() to estimate S separately under
ordinary or NULL-safe semantics, rather than simply complementing
equality existence. Optional equality match indices identify the
inner MCV equal to each outer MCV; the estimator checks for other MCVs,
NULLs where allowed, and residual values. It retains the existing hash
matching support and leaves the original statistics slots unchanged.
Both SEMI/ANTI estimators return S; the existing caller uses S and 1 - S
for SEMI and ANTI output rows, respectively.
The upper-level NULL correction discussed earlier is reasonable when the
underlying estimator returns ordinary equality selectivity. This patch
makes that distinction explicit for the built-in estimators. 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. The extra context is needed by the route
chosen here, where <> and IS DISTINCT FROM share neqjoinsel() and the same
operator OID. The optional sixth argument is an interface proposal for
review, rather than a prerequisite for fixing ordinary <> separately.
This local snapshot is v3.1.me.5, based on commit
1d657c6e013e152ed37b42a22ee9f291179ee50f. 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 <> 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. The saved
run has 16 files and 384 statements, classified by their actual SQL text:
Join type Queries Exact Zero-row floor Other differences
INNER 128 94 34 0
SEMI 72 53 19 0
ANTI 56 36 20 0
LEFT 64 41 0 23
RIGHT 64 41 0 23
Total 384 265 73 46
All actual row counts agree with counts independently calculated from
the table's value frequencies. INNER, SEMI and ANTI estimates are exact
apart from the zero-row floor. The remaining 46 differences are LEFT/RIGHT
outer-join padding estimates. No statistics on the original table were
recollected. The results were unchanged by moving NULL handling into
eqjoinsel(). Subsequent edits standardized the null_safe_compare parameter
name, clarified comments, and reduced duplicate regression cases. The
targeted planner_est regression passes. 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. 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. I suggest keeping the ordinary <> 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
Ready for Committer patch at this stage.
I will also report the selectivity misestimation for ordinary <> separately and prepare a separate patch,
so that this issue can be reviewed independently.
The attached test materials cover ordinary = and <> comparisons, NULL-safe IS [NOT] DISTINCT FROM
comparisons, and various join types:
- setup.sql — test data setup
- test_sql.tar — test SQL files
- test_result.xlsx — test results
regards,
--
ZizhuanLiu (X-MAN)
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 |
| 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 |