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

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