Re: Prove a NOT IN's left-hand expressions non-nullable from quals

Hi Richard,

v2 applies to master (d29d469bece), builds warning-free and make check is
green, and both of last round's items are fixed.

I diffed v2's results against master's on generated 2-3 rel jointrees, 1377
of which convert where master doesn't, and on partitioned and inheritance
parents, views, UNION ALL, CTEs, UPDATE and DELETE. No differences in what
I ran. Three things, none of them about correctness.

1) One shape the sharing doesn't reach. A node's SafeQualsInfo carries every
safe qual at or below it:

passquals = list_concat(leftsafequals, rightsafequals);
if (j->quals)
passquals = lappend(passquals, j->quals);

and the derivation flattens that whole list, once per node:

flat_quals = (List *)
flatten_join_alias_vars(root, root->parse, (Node *) sqinfo->quals);
sqinfo->nonnullable_vars = find_nonnullable_vars((Node *) flat_quals);
sqinfo->computed = true;

For example, with N joins each carrying one NOT IN:

SELECT count(*) FROM t
JOIN j1 ON (t.c1 NOT IN (SELECT s.d1 FROM s
WHERE s.filler = 0 OR s.filler = 1 OR ...))
JOIN j2 ON (t.c2 NOT IN (SELECT s.d2 FROM s
WHERE s.filler = 0 OR s.filler = 1 OR ...))
...

t's columns are nullable and no qual proves otherwise, so nothing is converted;
the s.filler terms are padding, 400 per sub-select, to make each copied qual
big enough to measure. EXPLAIN (MEMORY) used, in kB:

N master v2 v2+0001 v2-master v2+0001-master
1 751 841 841 90 90
4 2989 3889 3350 900 361
6 4653 6543 5194 1890 541
8 6402 9641 7122 3239 720
10 7886 12835 8786 4949 900

One flattened copy of one such ON clause -- one sub-select with its 400
s.filler terms -- is 90 kB, which the N=1 row measures on its own; the last
two columns are then 90 kB * N(N+1)/2 and 90 kB * N, to within a kB. With a
couple of small NOT INs this is negligible; the concern is that it grows as
N(N+1)/2 in their number and linearly in their size, and none of it is freed
until planning is done.

0001 attached keeps each node's own qual and a list of its children instead:

typedef struct SafeQualsInfo
{
- List *quals; /* qual clauses, with implicit-AND semantics */
+ Node *quals; /* this node's own WHERE or ON qual, or NULL */
+ List *children; /* child SafeQualsInfos whose quals apply */
List *nonnullable_vars; /* multibitmapset; valid if computed */
bool computed;
} SafeQualsInfo;

so the same place now reads

sqinfo = make_safe_quals_info(j->quals,
safe_quals_children(leftsafequals,
rightsafequals));

and derives bottom-up, cached per node. Same Vars proven, same conversions:
the 1377 plans above are identical to v2's, and make check is green.

2) The two tests run in the wrong order for the usual case:

if (under_not &&
/* flattens the whole node's clause, once per node */
(!sublink_testexpr_is_not_nullable(root, sublink, sqinfo) ||
/* flattens this sub-select's quals, once per NOT IN */
!query_outputs_are_not_nullable(subselect)))
return NULL;

With the small sub-selects most NOT INs have, the first is the more expensive
of the two. || short-circuits left to right, so it always runs first,
including when the second one was going to fail anyway. For example:

SELECT * FROM ot
WHERE ot.c1 IS NOT NULL
AND ot.c1 NOT IN (SELECT os.d1 FROM os WHERE os.filler = 0 OR ...);

os.d1 is nullable and no qual proves otherwise, so the second test fails and
this can never become an anti-join. But ot.c1 IS NOT NULL satisfies the
first, so the derivation runs in full before the second rejects it. Below is
the same measurement with the two tests swapped: N=40 such conjuncts in one
WHERE clause, sub-selects of Q quals each, EXPLAIN (MEMORY) used in kB, and no
conversion possible in any row.

Q master before swap after swap saved
2 690 822 730 92 69%
10 1204 1542 1377 165 48%
50 3709 5052 4534 518 38%
400 25689 35843 32233 3610 35%

So query_outputs_are_not_nullable is the one that should run first in almost
every query -- which is what the 0002 I posted last round did. It only loses
where the left-hand side isn't a plain Var: there the first test fails without
ever touching the quals, so v2 costs nothing over master and the swap is what
adds. The same 40 conjuncts with the left-hand sides written (ot.c1 + 0):

Q master before swap after swap cost
2 723 723 755 32
10 1238 1238 1402 164
50 3743 3743 4560 817
400 25723 25723 32258 6535

But (ot.c1 + 0) is rare -- a NOT IN's left-hand side is a column in almost
everything I've seen. The swap changes nothing observable either way: same
rows and same plans as v2 on the generated queries above, and make check is
green.

3) No test reaches this:

while (IsA(expr, RelabelType))
expr = ((RelabelType *) expr)->arg;

make check is green with those two lines removed. They aren't dead code
though:

CREATE TABLE tv (a varchar);
CREATE TABLE sv (b varchar NOT NULL);
SELECT * FROM tv WHERE a IS NOT NULL AND a NOT IN (SELECT b FROM sv);

gives a Hash Anti Join on v2, and a SubPlan with the two lines taken back
out; a domain over int behaves the same.

Thanks,
Rui