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

Hi Richard,

v1 applies to today's master and make check is green with it. Three things
and a comment nit.

1) +1 on the varlevelsup check Ayush proposed. Since make check passes on v1
as posted, nothing in the suite reaches the case; 0001 attached is his
one-liner plus a test that fails without it.

2) The same collision has a second instance, on the sub-select output side, and
this patch makes it reachable from an ordinary qual. With v1:

\pset null '<NULL>'
CREATE TEMP TABLE output_outer_t (a int);
CREATE TEMP TABLE output_local_t (a int);
CREATE TEMP TABLE output_inner_t (a int);
INSERT INTO output_outer_t VALUES (NULL), (10);
INSERT INTO output_local_t VALUES (1);
INSERT INTO output_inner_t VALUES (1);

SELECT o.a,
ARRAY(SELECT l.a
FROM output_local_t l
WHERE l.a IS NOT NULL
AND l.a NOT IN (SELECT o.a
FROM output_inner_t i
WHERE i.a IS NOT NULL)) AS vals
FROM output_outer_t o
ORDER BY o.a NULLS FIRST;
a | vals
--------+------
<NULL> | {1}
10 | {1}
(2 rows)

and master:

a | vals
--------+------
<NULL> | {}
10 | {1}
(2 rows)

For o.a = NULL the inner sub-select returns one NULL, so the NOT IN is NULL and
vals is empty. The sub-select's output o.a is an upper-level Var, and
query_outputs_are_not_nullable() looks it up with

if (!mbms_is_member(var->varno,
var->varattno - FirstLowInvalidHeapAttributeNumber,
nonnullable_vars))

which finds i.a there: same varno and varattno, different varlevelsup. That
fallback is on master already; what the patch adds is the proof for l.a, and
that is what brings the conversion within reach here. 0001 doesn't cover it --
l.a is a Var of its own level, so the check there has nothing to say about it.
I've posted that one separately, with a fix [1].

3) Planning cost. N conjuncts of the form

t.cK NOT IN (SELECT s.dK FROM s)

with t's columns nullable and s's NOT NULL, so the sub-select side is provable
and the outer side never is. Same configure for every build.

The "control" column below is not a fix, it's an attribution check: the v1
binary again, but with every left-hand side written as (t.cK + 0), so that

if (nonnullable_quals != NIL && IsA(expr, Var))

is false and the new fallback is never entered. If the cost were coming from
somewhere else in the patch it would still be there. It also means no NOT IN
can be converted, which is why it isn't a way out.

EXPLAIN (SUMMARY ON, COSTS OFF), Planning Time, median of 10, in ms:

N master v1 v1 control v1 + 0002
20 0.7 0.9 0.7 0.7
40 1.5 2.3 1.4 1.5
80 3.3 6.6 3.5 3.5
160 8.8 21.4 8.6 9.0
320 32.6 102.3 32.9 33.7

Memory is where it shows up worst. EXPLAIN (MEMORY), used, in kB:

N master v1 v1 control v1 + 0002
20 642 1235 659 671
40 1263 3628 1297 1322
80 2506 11951 2574 2624
160 4993 42743 5128 5229
320 9970 160911 10240 10442

master doubles with N; v1 goes up by 2.9x, 3.3x, 3.6x, 3.8x. At N=320 that is
10MB against 157MB, for one statement's planning. The control column tracks
master throughout, so the extra is that block and nothing else.

It's this, in sublink_testexpr_is_not_nullable():

if (!computed_nonnullable_vars)
{
List *flat_quals;

flat_quals = (List *)
flatten_join_alias_vars(root, root->parse,
(Node *) nonnullable_quals);
nonnullable_vars = find_nonnullable_vars((Node *) flat_quals);
computed_nonnullable_vars = true;
}

guarded by a flag that is declared in that same function:

bool computed_nonnullable_vars = false;

so it lives for one call and the work is redone for the next NOT IN.
nonnullable_quals is the node's whole WHERE clause, sublinks and their
subqueries included, and flatten_join_alias_vars() copies all of it; nothing
frees the copies and prepjointree doesn't run in a context of its own, so all N
are live until the statement is done planning. Dropping just that one call
takes N=320 from 102ms back to 36ms, and the memory all the way back to
master's 9970kB; the 3.6ms left over is find_nonnullable_vars() walking the
same list N times.

It doesn't take hundreds of NOT INs once the sub-selects aren't trivial. Same
measurement, with the conjuncts instead of the form

t.cK NOT IN (SELECT s.dK FROM s WHERE s.dK <> 0 AND s.dK <> 1 AND ...)

The <> terms are only there to grow the sub-select's qual tree without adding
anything else to plan; the flatten happens before preprocess_expression, so
they are still all there when the copy is made.

shape master v1 v1 + 0002
10 NOT INs, 50 quals each 1166kB 2431kB 1292kB
10 NOT INs, 400 quals each 6887kB 15886kB 7787kB
40 NOT INs, 100 quals each 7909kB 45811kB 8856kB

0002 attached passes the quals in a small struct and derives the Var set on
first use, so every SubLink at one jointree node shares one derivation. It
also tests the sub-select's output columns before the outer expressions, since
that is only a scan of its target list -- it doesn't help the shapes above,
where the cheap test passes, but it skips the work entirely for a NOT IN whose
sub-select outputs are nullable and which therefore could never have been
converted. What is left over above master in the last column is the one
derivation 0002 still has to do. Both patches are on top of v1, and make check
is green with them.

A comment thing. The JOIN_LEFT branch already says

* safe for this node's own quals, since a sublink pulled up
* here goes into the right side.

which is the right reason, but stops just short of it: going into the right
side is what puts the ON quals above the anti-join rather than below it as in
the FromExpr and JOIN_INNER cases, and that is the argument from quals above
which the commit message defers -- one step from the case it rules out. What
makes it sound here is which side the anti-join lands on, so maybe

* safe for this node's own quals, since a sublink pulled up
* here goes into the right side.
+ *
+ * The ON quals then end up above the anti-join rather than
+ * below it, unlike the FromExpr and JOIN_INNER cases. That
+ * is sound because the anti-join is on the nullable side: a
+ * row it lets through with a NULL left-hand side fails the
+ * ON qual and joins with nothing, which is what the original
+ * NOT IN did with it.
*/

and the mirror of it in JOIN_RIGHT. Incidentally that case is the only thing
the new traversal buys over find_subquery_safe_quals(), which collects the same
quals under the same rules everywhere else.

[1] https://postgr.es/m/CAHWVJhGuaFFRpmq4j%2BmcMcm_HC5QOT7LZsC9bf9b7BCBmvbfMA%40mail.gmail.com

Thanks,
Rui