BUG #19926: Incorrect join selectivity for <> with NULLs (related to BUG #17545)

From: PG Bug reporting form <noreply(at)postgresql(dot)org>
To: pgsql-bugs(at)lists(dot)postgresql(dot)org
Cc: 44973863(at)qq(dot)com
Subject: BUG #19926: Incorrect join selectivity for <> with NULLs (related to BUG #17545)
Date: 2026-11-20 13:13:19
Message-ID: 19926-21f3ff733b3fada7@postgresql.org
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-bugs

The following bug has been logged on the website:

Bug reference: 19926
Logged by: Zizhuan Liu
Email address: 44973863(at)qq(dot)com
PostgreSQL version: 19.0
Operating system: Linux
Description:

Hi,

While investigating BUG #17545, I noticed a related selectivity issue with
ordinary integer <> inner joins when either input contains NULLs. I am
reporting this reproduction as additional input to that work, and suggest
continuing the NULL-handling design discussion and patch review in the
existing BUG #17545 thread:
https://www.postgresql.org/message-id/flat/17545-a0ca4de888953169(at)postgresql(dot)org

The following example estimates 920000 matching pairs, but returns 80000,
even though ANALYZE has captured the complete non-NULL distribution. Query
results are correct; the issue is the planner's row estimate.

I reproduced this on a saved PostgreSQL 20devel baseline build on x86_64
Linux, compiled with GCC 13.3.0. I also checked the current upstream master
source at e7e1835e6b026589c8d0650dda4cd1ec8e0e29ea: the non-SEMI/ANTI branch
of neqjoinsel() still uses the same 1 - eqjoinsel() calculation there.

Minimal reproducer:

BEGIN;

CREATE TEMP TABLE neq_join_nulls AS
SELECT CASE WHEN g <= 600 THEN NULL::integer
WHEN g <= 800 THEN 1 ELSE 2 END AS a
FROM generate_series(1, 1000) AS g;
ANALYZE neq_join_nulls;

SELECT null_frac, most_common_vals, most_common_freqs
FROM pg_stats
WHERE schemaname =
(SELECT nspname FROM pg_namespace WHERE oid = pg_my_temp_schema())
AND tablename = 'neq_join_nulls' AND attname = 'a';

EXPLAIN (ANALYZE, TIMING OFF, SUMMARY OFF, BUFFERS OFF)
SELECT FROM neq_join_nulls x, neq_join_nulls y WHERE x.a <> y.a;

ROLLBACK;

Statistics:

null_frac | most_common_vals | most_common_freqs
-----------+------------------+-------------------
0.6 | {1,2} | {0.2,0.2}

Plan excerpt:

Nested Loop (cost=0.00..15030.50 rows=920000 width=0)
(actual rows=80000.00 loops=1)
Join Filter: (x.a <> y.a)
Rows Removed by Join Filter: 920000

There are 600 NULLs, 200 ones and 200 twos. Only 1 <> 2 and 2 <> 1
contribute, giving 200*200 + 200*200 = 80000 pairs. As a control,
x.a = y.a is both estimated and observed to return 80000 pairs.

The apparent cause is that the non-SEMI/ANTI path in neqjoinsel() returns
1 - eqjoinsel(). For a strict operator, pairs containing a NULL satisfy
neither = nor <>. Complementing the equality selectivity counts those
UNKNOWN comparisons as inequality matches.

Let E be the ordinary non-NULL equality selectivity and n1/n2 the two
NULL fractions. Under the usual independence assumption, the fraction of
pairs with two non-NULL inputs is B = (1-n1)*(1-n2). The inequality
selectivity should therefore be B-E, rather than 1-E. In this example:

E = 0.2*0.2 + 0.2*0.2 = 0.08
B = 0.4*0.4 = 0.16
current = 1-E = 0.92
NULL-adjusted = B-E = 0.08

The restriction estimator already follows the analogous principle by
subtracting nullfrac when complementing equality.

The same issue occurs with NULLs on only one side. Keeping the first table
and using a second table containing 500 ones and 500 twos gives an estimate
of 800000 versus 200000 actual pairs. With two 1000-row all-NULL inputs,
the estimate is 1000000, while the actual result is empty.

The ordinary <> case also matters when reviewing how the NULL-safe
predicates discussed in BUG #17545 should share estimator machinery.
For ordinary strict <>, every pair containing a NULL is excluded;
IS DISTINCT FROM includes pairs with exactly one NULL. With the same
ordinary equality estimate E, their pair selectivities are:

ordinary <> (1-n1)*(1-n2) - E
IS DISTINCT FROM 1 - E - n1*n2

For the data above, these are 0.08 and 0.56, respectively. Applying the
ordinary <> formula unconditionally to a shared estimator would therefore
be incorrect for IS DISTINCT FROM.

In current master, and in the v2 patch posted in that thread,
IS DISTINCT FROM is estimated through the equality estimator and then
adjusted in clausesel.c. An ordinary <> change in neqjoinsel() alone does
not change that existing path.

However, a local prototype routes IS DISTINCT FROM through its inequality
negator so that it can reuse neqjoinsel(), including its SEMI/ANTI handling.
In that design, both clauses reach the estimator with the same <> operator
OID, and the estimator needs explicit information about the NULL semantics.
The prototype passes a NULL-safe flag through plancat.c to the built-in
eqjoinsel/neqjoinsel functions as an optional sixth argument. Other catalog
estimators keep their five-argument calling convention. This is one
possible interface design to review in BUG #17545.

The prototype produces 80000 and 200000 for the two ordinary <> mixed
cases, and the usual one-row estimate floor for the empty all-NULL case.
Here E remains the ordinary equality estimate, without a NULL/NULL
contribution for NULL-safe equality. The formulas above concern pair
selectivity; SEMI/ANTI estimates measure partner existence and require
their corresponding NULL rules.

Thanks.

Browse pgsql-bugs by date

  From Date Subject
Next Message PG Bug reporting form 2026-11-20 13:21:09 BUG #19927: PostgreSQL 16: SQL dump adds experimental/incompatible options like \restrict
Previous Message ZizhuanLiu X-MAN 2026-11-20 12:58:49 Re: BUG #17545: Incorrect selectivity for IS NOT DISTINCT FROM and NULLs