Обсуждение: Allowing NOT IN to use ANTI joins

On Mon, Jun 09, 2014 at 12:36:30AM +1200, David Rowley wrote:
> Currently pull_up_sublinks_qual_recurse only changes the plan for NOT
> EXISTS queries and leaves NOT IN alone. The reason for this is because the
> values returned by a subquery in the IN clause could have NULLs.

Awesome. I've had a brief look at the patch and other than a line of
extraneous whitespace it looks sane.

Since it is only testing on NOT IN queries I don't think there are any
issues with it slowing down simple queries.

I also note you can't prove "id+1" not null. At first I thought you
might be able to prove this not null if the operator/function was
strict, but then I realised that strict only means "null if input is
null" not "output is only null if inputs are null". Pity.

Nice work.
--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> He who writes carelessly confesses thereby at the very outset that he does
> not attach much importance to his own thoughts.  -- Arthur Schopenhauer

On Sun, Jun 8, 2014 at 3:36 PM, David Rowley <dgrowleyml@gmail.com> wrote:
> Currently pull_up_sublinks_qual_recurse only changes the plan for NOT EXISTS
> queries and leaves NOT IN alone. The reason for this is because the values
> returned by a subquery in the IN clause could have NULLs.

I believe the reason why this hasn't been done yet, is that the plan
becomes invalid when another backend modifies the nullability of the
column. To get it to replan, you'd have to introduce a dependency on
the "NOT NULL" constraint, but it's impossible for now because there's
no pg_constraint entry for NOT NULLs.

The only way to consistently guarantee nullability is through primary
key constraints. Fortunately that addresses most of the use cases of
NOT IN(), in my experience.

See the comment in check_functional_grouping:
* Currently we only check to see if the rel has a primary key that is a* subset of the grouping_columns.  We could also
useplain unique constraints* if all their columns are known not null, but there's a problem: we need* to be able to
representthe not-null-ness as part of the constraints added* to *constraintDeps.  FIXME whenever not-null constraints
getrepresented* in pg_constraint.
 

The behavior you want seems somewhat similar to
check_functional_grouping; maybe you could unify it with your
targetListIsGuaranteedNotToHaveNulls at some level. (PS: that's one
ugly function name :)

Regards,
Marti

On 06/08/2014 02:36 PM, David Rowley wrote:
> +        if (!get_attnotnull(tle->resorigtbl, tle->resorigcol))
> +            return false;

As Marti says, you can't do this because NOT NULL doesn't have an oid to
attach a dependency to.  You'll have to restrict this test to primary
keys only for now.
-- 
Vik

Marti Raudsepp <marti@juffo.org> writes:
> On Sun, Jun 8, 2014 at 3:36 PM, David Rowley <dgrowleyml@gmail.com> wrote:
>> Currently pull_up_sublinks_qual_recurse only changes the plan for NOT EXISTS
>> queries and leaves NOT IN alone. The reason for this is because the values
>> returned by a subquery in the IN clause could have NULLs.

> I believe the reason why this hasn't been done yet, is that the plan
> becomes invalid when another backend modifies the nullability of the
> column. To get it to replan, you'd have to introduce a dependency on
> the "NOT NULL" constraint, but it's impossible for now because there's
> no pg_constraint entry for NOT NULLs.

I don't believe this is an issue, because we are only talking about a
*plan* depending on the NOT NULL condition.  ALTER TABLE DROP NOT NULL
would result in a relcache inval event against the table, which would
result in invalidating all cached plans mentioning the table.

I forget exactly what context we were discussing needing a NOT NULL
constraint's OID for, but it would have to be something where the
dependency was longer-lived than a plan; perhaps semantics of a view?
The existing comparable case is that a view containing ungrouped
variable references is allowed if the GROUP BY includes a primary key,
which means the semantic validity of the view depends on the pkey.
        regards, tom lane

Jeff Janes <jeff.janes@gmail.com> writes:
> On Sun, Jun 8, 2014 at 5:36 AM, David Rowley <dgrowleyml@gmail.com> wrote:
>> The attached patch allows an ANTI-join plan to be generated in cases like:
>> CREATE TABLE a (id INT PRIMARY KEY, b_id INT NOT NULL);
>> CREATE TABLE b (id INT NOT NULL);
>> SELECT * FROM a WHERE b_id NOT IN(SELECT id FROM b);

> I think this will be great, I've run into this problem often from
> applications I have no control over.  I thought a more complete, but
> probably much harder, solution would be to add some metadata to the hash
> anti-join infrastructure that tells it "If you find any nulls in the outer
> scan, stop running without returning any rows".  I think that should work
> because the outer rel already has to run completely before any rows can be
> returned.

Huh?  The point of an antijoin (or indeed most join methods) is that we
*don't* have to examine the whole inner input to make a decision.
        regards, tom lane

Jeff Janes <jeff.janes@gmail.com> writes:
> On Sun, Jun 8, 2014 at 5:36 AM, David Rowley <dgrowleyml@gmail.com> wrote:
>> The attached patch allows an ANTI-join plan to be generated in cases like:
>> CREATE TABLE a (id INT PRIMARY KEY, b_id INT NOT NULL);
>> CREATE TABLE b (id INT NOT NULL);
>> SELECT * FROM a WHERE b_id NOT IN(SELECT id FROM b);

> I think this will be great, I've run into this problem often from
> applications I have no control over.  I thought a more complete, but
> probably much harder, solution would be to add some metadata to the hash
> anti-join infrastructure that tells it "If you find any nulls in the outer
> scan, stop running without returning any rows".  I think that should work
> because the outer rel already has to run completely before any rows can be
> returned.

Huh?  The point of an antijoin (or indeed most join methods) is that we
*don't* have to examine the whole inner input to make a decision.

Jeff Janes <jeff.janes@gmail.com> writes:
> On Monday, June 9, 2014, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Huh?  The point of an antijoin (or indeed most join methods) is that we
>> *don't* have to examine the whole inner input to make a decision.

> But all hash join methods needs to examine the entire *outer* input, no?
>  Have I screwed up my terminology here?

I think you're confusing inner and outer inputs --- the sub-select inside
the NOT IN is the inner input according to the way I think about it.
But I had assumed that was what you meant already.

> If you are using NOT IN, then once you find a NULL in the outer input (if
> the outer input is the in-list: clearly you can't reverse the two inputs in
> this case), you don't even need to finish reading the outer input, nor
> start reading the inner input, because all rows are automatically excluded
> by the weird semantics of NOT IN.

The point I'm trying to make is that the goal of most join types is to
give an answer without having necessarily read all of either input.
For instance, if we tried to do this with a mergejoin it wouldn't work
reliably: it might suppose that it could accept an outer row on the basis
of no match in a higher-order sort column before it'd reached any nulls
appearing in lower-order sort columns.

You might be right that we could hot-wire the hash join case in
particular, but I'm failing to see the point of expending lots of extra
effort in order to deliver a useless answer faster.  If there are NULLs
in the inner input, then NOT IN is simply the wrong query to make, and
giving an empty output in a relatively short amount of time isn't going
to help clue the user in on that.  (If the SQL standard would let us do
so, I'd be arguing for throwing an error if we found a NULL.)
        regards, tom lane

On Wed, Jun 11, 2014 at 11:53 AM, David Rowley <dgrowleyml@gmail.com> wrote:
>> The only way to consistently guarantee nullability is through primary
>> key constraints. Fortunately that addresses most of the use cases of
>> NOT IN(), in my experience.

>> See the comment in check_functional_grouping:

> I saw that, but I have to say I've not fully got my head around why that's
> needed just yet.

I was wrong, see Tom's reply to my email. It's OK to rely on
attnotnull for optimization decisions. The plan will be invalidated
automatically when the nullability of a referenced column changes.

check_functional_grouping needs special treatment because it decides
whether to accept/reject views; and if it has allowed creating a view,
it needs to guarantee that the dependent constraint isn't dropped for
a longer term.

> as long as the transaction id
> is taken before we start planning in session 1 then it should not matter if
> another session drops the constraint and inserts a NULL value as we won't
> see that NULL value in our transaction... I'd assume that the transaction
> has to start before it grabs the table defs that are required for planning.
> Or have I got something wrong?

1. You're assuming that query plans can only survive for the length of
a transaction. That's not true, prepared query plans can span many
transactions.

2. Also a FOR UPDATE clause can return values "from the future", if
another transaction has modified the value and already committed.

But this whole issue is moot anyway, the plan will get invalidated
when the nullability changes.

Regards,
Marti

On Sun, Jun 8, 2014 at 3:36 PM, David Rowley <dgrowleyml@gmail.com> wrote:
> Currently pull_up_sublinks_qual_recurse only changes the plan for NOT EXISTS
> queries and leaves NOT IN alone. The reason for this is because the values
> returned by a subquery in the IN clause could have NULLs.

There's a bug in targetListIsGuaranteedNotToHaveNulls, you have to
drill deeper into the query to guarantee the nullability of a result
column. If a table is OUTER JOINed, it can return NULLs even if the
original column specification has NOT NULL.

This test case produces incorrect results with your patch:

create table a (x int not null);
create table b (x int not null, y int not null);
insert into a values(1);
select * from a where x not in (select y from a left join b using (x));

Unpatched version correctly returns 0 rows since "y" will be NULL.
Your patch returns the value 1 from a.

Regards,
Marti

Marti Raudsepp <marti@juffo.org> writes:
> On Wed, Jun 11, 2014 at 11:53 AM, David Rowley <dgrowleyml@gmail.com> wrote:
>> as long as the transaction id
>> is taken before we start planning in session 1 then it should not matter if
>> another session drops the constraint and inserts a NULL value as we won't
>> see that NULL value in our transaction... I'd assume that the transaction
>> has to start before it grabs the table defs that are required for planning.
>> Or have I got something wrong?

> 1. You're assuming that query plans can only survive for the length of
> a transaction. That's not true, prepared query plans can span many
> transactions.

> 2. Also a FOR UPDATE clause can return values "from the future", if
> another transaction has modified the value and already committed.

> But this whole issue is moot anyway, the plan will get invalidated
> when the nullability changes.

Right.  The key point for David's concern is that we always hold (at
least) AccessShareLock on every relation used in a query, continuously
from rewrite through to the end of execution.  This will block any attempt
by other transactions to make schema changes in the relation(s).
In the case of re-using a prepared plan, we re-acquire all these locks
and then check to see if we received any invalidation messages that
render the plan invalid; if not, we can proceed to execution with the same
safety guarantees as originally.  (If we did, we replan starting from the
raw parse tree.)

If we didn't have mechanisms like this, we'd have far worse hazards from
ALTER TABLE than whether the planner made an incorrect join optimization.
Consider ALTER COLUMN TYPE for instance.
        regards, tom lane

On Wed, Jun 11, 2014 at 3:26 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> If we didn't have mechanisms like this, we'd have far worse hazards from
> ALTER TABLE than whether the planner made an incorrect join optimization.
> Consider ALTER COLUMN TYPE for instance.

Obviously not general cases of ALTER COLUMN TYPE but dropping a NULL
constraint seems like the kind of change targeted by Simon's "reduce
lock strength" patch that I'm sure he's still interested in. I think
that patch, while full of dragons to steer around, is something that
will keep coming up again and again in the future. It's a huge
operational risk that even these short exclusive locks can cause a
huge production outage if they happen to get queued up behind a
reporting query.

I don't think it changes anything for this patch -- right now the
world is arranged the way Tom described -- but it's something to keep
in mind when we talk about lock strength reduction and the impact on
existing queries. For example if there's an UPDATE query in repeatable
read mode that has an IN clause like this and was optimized
accordingly then any lock strength reduction patch would have to
beware that an ALTER TABLE that dropped the NULL clause might impact
the update query.

Incidentally, Oracle has a feature for online schema changes that we
might end up having to implement something similar. The good news is
we have the infrastructure to maybe do it. The idea is to start
capturing all the changes to the table using something like our
logical changeset extraction. Then do the equivalent of "create
newtable as select ... from oldtable" to create the new schema, then
start replaying the accumulated changes to the new table. Eventually
when the change queue drains then get an exclusive lock, drain any new
changes, and swap in the new table with the new schema.

-- 
greg

On 24 June 2014 11:32, David Rowley <dgrowleyml@gmail.com> wrote:

> So if anyone can point me in the right direction then that would be
> really useful.

Many things can be added simply, but most things can't. It seems we
just don't have that information. If we did, Tom would have done this
already.

> On a more positive or even slightly exciting note I think I've managed to
> devise a way that ANTI JOINS can be used for NOT IN much more often. It
> seems that find_nonnullable_vars will analyse a quals list to find
> expressions that mean that the var cannot be NULL. This means we can perform
> ANTI JOINS for NOT IN with queries like:
>
> SELECT * FROM a WHERE id NOT IN(SELECT nullable_col FROM b WHERE
> nullable_col = 1);
> or
> SELECT * FROM a WHERE id NOT IN(SELECT nullable_col FROM b WHERE
> nullable_col IS NOT NULL);
>
> (The attached patch implements this)
>
> the nullable_col =1 will mean that nullable_col cannot be NULL, so the ANTI
> JOIN can be performed safely. I think this combined with the NOT NULL check
> will cover probably just about all valid uses of NOT IN with a subquery...
> unless of course I've assumed something wrongly about find_nonnullable_vars.
> I just need the correct RangeTblEntry in order to determine if the
> TargetEntry is from an out join.

This is the better way to go. It's much better to have explicit proof
its not null than a possibly long chain of metadata that might be
buggy.

> The attached patch is a broken implemention that still needs the lookup code
> fixed to reference the correct RTE. The failing regression tests show where
> the problems lie.
>
> Any help on this would be really appreciated.

I'd suggest we just drop the targetlist approach completely.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

On 11 June 2014 17:52, Greg Stark <stark@mit.edu> wrote:
> On Wed, Jun 11, 2014 at 3:26 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> If we didn't have mechanisms like this, we'd have far worse hazards from
>> ALTER TABLE than whether the planner made an incorrect join optimization.
>> Consider ALTER COLUMN TYPE for instance.
>
> Obviously not general cases of ALTER COLUMN TYPE but dropping a NULL
> constraint seems like the kind of change targeted by Simon's "reduce
> lock strength" patch that I'm sure he's still interested in. I think
> that patch, while full of dragons to steer around, is something that
> will keep coming up again and again in the future. It's a huge
> operational risk that even these short exclusive locks can cause a
> huge production outage if they happen to get queued up behind a
> reporting query.

The focus of the lock strength reduction was around actions that lock
the table for extended periods. So it was mostly about adding things.
All the DROP actions are still AccessExclusiveLocks and will be for a
while.

Having said that, any join plan that relies upon a constraint will
still be valid even if we drop a constraint while the plan executes
because any new writes will not be visible to the executing join plan.
If we are relaxing a constraint, then a writable query that still
thinks a constraint exists won't cause a problem - it may error out
when it need not, but that's not so bad as to be worth worrying about.

So I think we can remove a NOT NULL constraint without too much problem.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

Simon Riggs <simon@2ndQuadrant.com> writes:
> Having said that, any join plan that relies upon a constraint will
> still be valid even if we drop a constraint while the plan executes
> because any new writes will not be visible to the executing join plan.

mumble ... EvalPlanQual ?
        regards, tom lane

On 24 June 2014 23:44, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Simon Riggs <simon@2ndQuadrant.com> writes:
>> Having said that, any join plan that relies upon a constraint will
>> still be valid even if we drop a constraint while the plan executes
>> because any new writes will not be visible to the executing join plan.
>
> mumble ... EvalPlanQual ?

As long as we are relaxing a constraint, we are OK if an earlier
snapshot thinks its dealing with a tighter constraint whereas the new
reality is a relaxed constraint.

The worst that could happen is we hit an ERROR from a constraint that
was in force at the start of the query, so for consistency we really
should be enforcing the same constraint throughout the lifetime of the
query.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

Simon Riggs <simon@2ndQuadrant.com> writes:
> On 24 June 2014 23:44, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Simon Riggs <simon@2ndQuadrant.com> writes:
>>> Having said that, any join plan that relies upon a constraint will
>>> still be valid even if we drop a constraint while the plan executes
>>> because any new writes will not be visible to the executing join plan.

>> mumble ... EvalPlanQual ?

> As long as we are relaxing a constraint, we are OK if an earlier
> snapshot thinks its dealing with a tighter constraint whereas the new
> reality is a relaxed constraint.

I guess I should have been more explicit: EvalPlanQual processing could
see newer versions of tuples that might not satisfy the constraints the
plan was designed against.  Now, this is true only for the tuple that's
the target of the UPDATE/DELETE, so it's possible you could prove that
there's no problem --- but it would take careful analysis of the specific
semantics of the constraints in question.  I don't believe the argument
you've made here holds up.
        regards, tom lane

On 24 June 2014 23:52, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Simon Riggs <simon@2ndQuadrant.com> writes:
>> On 24 June 2014 23:44, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> Simon Riggs <simon@2ndQuadrant.com> writes:
>>>> Having said that, any join plan that relies upon a constraint will
>>>> still be valid even if we drop a constraint while the plan executes
>>>> because any new writes will not be visible to the executing join plan.
>
>>> mumble ... EvalPlanQual ?
>
>> As long as we are relaxing a constraint, we are OK if an earlier
>> snapshot thinks its dealing with a tighter constraint whereas the new
>> reality is a relaxed constraint.
>
> I guess I should have been more explicit: EvalPlanQual processing could
> see newer versions of tuples that might not satisfy the constraints the
> plan was designed against.  Now, this is true only for the tuple that's
> the target of the UPDATE/DELETE, so it's possible you could prove that
> there's no problem --- but it would take careful analysis of the specific
> semantics of the constraints in question.  I don't believe the argument
> you've made here holds up.

OK, thanks for raising that. You're better at seeing these things than I.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

On 24 June 2014 23:22, Simon Riggs <simon@2ndquadrant.com> wrote:

>> On a more positive or even slightly exciting note I think I've managed to
>> devise a way that ANTI JOINS can be used for NOT IN much more often. It
>> seems that find_nonnullable_vars will analyse a quals list to find
>> expressions that mean that the var cannot be NULL. This means we can perform
>> ANTI JOINS for NOT IN with queries like:
>>
>> SELECT * FROM a WHERE id NOT IN(SELECT nullable_col FROM b WHERE
>> nullable_col = 1);
>> or
>> SELECT * FROM a WHERE id NOT IN(SELECT nullable_col FROM b WHERE
>> nullable_col IS NOT NULL);
>>
>> (The attached patch implements this)
>>
>> the nullable_col =1 will mean that nullable_col cannot be NULL, so the ANTI
>> JOIN can be performed safely. I think this combined with the NOT NULL check
>> will cover probably just about all valid uses of NOT IN with a subquery...
>> unless of course I've assumed something wrongly about find_nonnullable_vars.
>> I just need the correct RangeTblEntry in order to determine if the
>> TargetEntry is from an out join.
>
> This is the better way to go. It's much better to have explicit proof
> its not null than a possibly long chain of metadata that might be
> buggy.
>
>> The attached patch is a broken implemention that still needs the lookup code
>> fixed to reference the correct RTE. The failing regression tests show where
>> the problems lie.
>>
>> Any help on this would be really appreciated.
>
> I'd suggest we just drop the targetlist approach completely.

To be clearer, what I mean is we use only the direct proof approach,
for queries like this
 SELECT * FROM a WHERE id NOT IN(SELECT unknown_col FROM b WHERE
unknown_col IS NOT NULL);

and we don't try to do it for queries like this
 SELECT * FROM a WHERE id NOT IN(SELECT not_null_column FROM b);

because we don't know the full provenance of "not_null_column" in all
cases and that info is (currently) unreliable.

Once we have the transform working for one case, we can try to extend
the cases covered.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

Simon Riggs <simon@2ndQuadrant.com> writes:
> To be clearer, what I mean is we use only the direct proof approach,
> for queries like this

>   SELECT * FROM a WHERE id NOT IN(SELECT unknown_col FROM b WHERE
> unknown_col IS NOT NULL);

> and we don't try to do it for queries like this

>   SELECT * FROM a WHERE id NOT IN(SELECT not_null_column FROM b);

> because we don't know the full provenance of "not_null_column" in all
> cases and that info is (currently) unreliable.

FWIW, I think that would largely cripple the usefulness of the patch.
If you can tell people to rewrite their queries, you might as well
tell them to rewrite into NOT EXISTS.  The real-world queries that
we're trying to improve invariably look like the latter case not the
former, because people who are running into this problem usually
aren't even thinking about the possibility of NULLs.

I would actually say that if we only have the bandwidth to get one of
these cases done, it should be the second one not the first.  It's
unclear to me that checking for the first case would even be worth
the planner cycles it'd cost.
        regards, tom lane

On 26 June 2014 10:31, David Rowley <dgrowleyml@gmail.com> wrote:

> If there's no way to tell that the target entry comes from a left join, then
> would it be a bit too quirky to just do the NOT NULL checking when
> list_length(query->rtable) == 1 ? or maybe even loop over query->rtable and
> abort if we find an outer join type? it seems a bit hackish, but perhaps it
> would please more people than it would surprise.

We don't know enough about joins at present, so we only allow it when
there are no joins (i.e. length == 1). That's just a statement of
reality, not a hack.

I would agree with Tom that the common usage is to do NOT IN against a
table with no where clause, so this would hit the most frequent use
case.

Maybe Tom will have a flash of insight before commit, or maybe we
figure out a way to extend it later.

Let's document it and move on.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

David Rowley <dgrowleyml@gmail.com> writes:
> If there's no way to tell that the target entry comes from a left join,
> then would it be a bit too quirky to just do the NOT NULL checking when
> list_length(query->rtable) == 1 ? or maybe even loop over query->rtable and
> abort if we find an outer join type? it seems a bit hackish, but perhaps it
> would please more people than it would surprise.

Why do you think you can't tell if the column is coming from the wrong
side of a left join?

I don't recall right now if there is already machinery in the planner for
this, but we could certainly deconstruct the from-clause enough to tell
that.

It's not hard to imagine a little function that recursively descends the
join tree, not bothering to descend into the nullable sides of outer
joins, and returns "true" if it finds a RangeTableRef for the desired RTE.
If it doesn't find the RTE in the not-nullable parts of the FROM clause,
then presumably it's nullable.

The only thing wrong with that approach is if you have to call the
function many times, in which case discovering the information from
scratch each time could get expensive.

I believe deconstruct_jointree already keeps track of whether it's
underneath an outer join, so if we were doing this later than that,
I'd advocate making sure it saves the needed information.  But I suppose
you're trying to do this before that.  It might be that you could
easily save aside similar information during the earlier steps in
prepjointree.c.  (Sorry for not having examined the patch yet, else
I'd probably have a more concrete suggestion.)
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> Attached is the updated version of the patch.

I spent some time fooling with this patch, cleaning up the join-alias
issue as well as more-cosmetic things.  However, while testing it
I realized that the whole thing is based on a false premise: to equate
a NOT IN with an antijoin, we'd have to prove not only that the inner
side is non-nullable, but that the outer comparison values are too.
Here's an example:

regression=# create table zt1 (f1 int);
CREATE TABLE
regression=# insert into zt1 values(1);
INSERT 0 1
regression=# insert into zt1 values(2);
INSERT 0 1
regression=# insert into zt1 values(null);
INSERT 0 1
regression=# create table zt2 (f1 int not null);
CREATE TABLE
regression=# insert into zt2 values(1);
INSERT 0 1

With the patch in place, we get

regression=# explain select * from zt1 where f1 not in (select f1 from zt2);
                            QUERY PLAN
-------------------------------------------------------------------
 Hash Anti Join  (cost=64.00..144.80 rows=1200 width=4)
   Hash Cond: (zt1.f1 = zt2.f1)
   ->  Seq Scan on zt1  (cost=0.00..34.00 rows=2400 width=4)
   ->  Hash  (cost=34.00..34.00 rows=2400 width=4)
         ->  Seq Scan on zt2  (cost=0.00..34.00 rows=2400 width=4)
 Planning time: 0.646 ms
(6 rows)

regression=# select * from zt1 where f1 not in (select f1 from zt2);
 f1
----
  2

(2 rows)

which is the wrong answer, as demonstrated by comparison to the result
without optimization:

regression=# alter table zt2 alter column f1 drop not null;
ALTER TABLE
regression=# explain select * from zt1 where f1 not in (select f1 from zt2);
                          QUERY PLAN
---------------------------------------------------------------
 Seq Scan on zt1  (cost=40.00..80.00 rows=1200 width=4)
   Filter: (NOT (hashed SubPlan 1))
   SubPlan 1
     ->  Seq Scan on zt2  (cost=0.00..34.00 rows=2400 width=4)
 Planning time: 0.163 ms
(5 rows)

regression=# select * from zt1 where f1 not in (select f1 from zt2);
 f1
----
  2
(1 row)

We could no doubt fix this by also insisting that the left-side vars
be provably not null, but that's going to make the patch even slower
and even less often applicable.  I'm feeling discouraged about whether
this is worth doing in this form.

For the archives' sake, I attach an updated version with the fixes
I'd applied so far.

            regards, tom lane

diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
index 3e7dc85..4b44662 100644
*** a/src/backend/optimizer/plan/subselect.c
--- b/src/backend/optimizer/plan/subselect.c
*************** SS_process_ctes(PlannerInfo *root)
*** 1195,1205 ****
   * If so, form a JoinExpr and return it.  Return NULL if the SubLink cannot
   * be converted to a join.
   *
!  * The only non-obvious input parameter is available_rels: this is the set
!  * of query rels that can safely be referenced in the sublink expression.
!  * (We must restrict this to avoid changing the semantics when a sublink
!  * is present in an outer join's ON qual.)  The conversion must fail if
!  * the converted qual would reference any but these parent-query relids.
   *
   * On success, the returned JoinExpr has larg = NULL and rarg = the jointree
   * item representing the pulled-up subquery.  The caller must set larg to
--- 1195,1208 ----
   * If so, form a JoinExpr and return it.  Return NULL if the SubLink cannot
   * be converted to a join.
   *
!  * If under_not is true, the caller actually found NOT (ANY SubLink),
!  * so that what we must try to build is an ANTI not SEMI join.
!  *
!  * available_rels is the set of query rels that can safely be referenced
!  * in the sublink expression.  (We must restrict this to avoid changing the
!  * semantics when a sublink is present in an outer join's ON qual.)
!  * The conversion must fail if the converted qual would reference any but
!  * these parent-query relids.
   *
   * On success, the returned JoinExpr has larg = NULL and rarg = the jointree
   * item representing the pulled-up subquery.  The caller must set larg to
*************** SS_process_ctes(PlannerInfo *root)
*** 1222,1228 ****
   */
  JoinExpr *
  convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
!                             Relids available_rels)
  {
      JoinExpr   *result;
      Query       *parse = root->parse;
--- 1225,1231 ----
   */
  JoinExpr *
  convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
!                             bool under_not, Relids available_rels)
  {
      JoinExpr   *result;
      Query       *parse = root->parse;
*************** convert_ANY_sublink_to_join(PlannerInfo
*** 1237,1242 ****
--- 1240,1254 ----
      Assert(sublink->subLinkType == ANY_SUBLINK);

      /*
+      * Per SQL spec, NOT IN is not ordinarily equivalent to an anti-join, so
+      * that by default we have to fail when under_not.  However, if we can
+      * prove that the sub-select's output columns are all certainly not NULL,
+      * then it's safe to convert NOT IN to an anti-join.
+      */
+     if (under_not && !query_outputs_are_not_nullable(subselect))
+         return NULL;
+
+     /*
       * The sub-select must not refer to any Vars of the parent query. (Vars of
       * higher levels should be okay, though.)
       */
*************** convert_ANY_sublink_to_join(PlannerInfo
*** 1302,1308 ****
       * And finally, build the JoinExpr node.
       */
      result = makeNode(JoinExpr);
!     result->jointype = JOIN_SEMI;
      result->isNatural = false;
      result->larg = NULL;        /* caller must fill this in */
      result->rarg = (Node *) rtr;
--- 1314,1320 ----
       * And finally, build the JoinExpr node.
       */
      result = makeNode(JoinExpr);
!     result->jointype = under_not ? JOIN_ANTI : JOIN_SEMI;
      result->isNatural = false;
      result->larg = NULL;        /* caller must fill this in */
      result->rarg = (Node *) rtr;
*************** convert_ANY_sublink_to_join(PlannerInfo
*** 1317,1325 ****
  /*
   * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
   *
!  * The API of this function is identical to convert_ANY_sublink_to_join's,
!  * except that we also support the case where the caller has found NOT EXISTS,
!  * so we need an additional input parameter "under_not".
   */
  JoinExpr *
  convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
--- 1329,1335 ----
  /*
   * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
   *
!  * The API of this function is identical to convert_ANY_sublink_to_join's.
   */
  JoinExpr *
  convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 9cb1378..3a116c7 100644
*** a/src/backend/optimizer/prep/prepjointree.c
--- b/src/backend/optimizer/prep/prepjointree.c
*************** pull_up_sublinks_qual_recurse(PlannerInf
*** 334,340 ****
          /* Is it a convertible ANY or EXISTS clause? */
          if (sublink->subLinkType == ANY_SUBLINK)
          {
!             if ((j = convert_ANY_sublink_to_join(root, sublink,
                                                   available_rels1)) != NULL)
              {
                  /* Yes; insert the new join node into the join tree */
--- 334,340 ----
          /* Is it a convertible ANY or EXISTS clause? */
          if (sublink->subLinkType == ANY_SUBLINK)
          {
!             if ((j = convert_ANY_sublink_to_join(root, sublink, false,
                                                   available_rels1)) != NULL)
              {
                  /* Yes; insert the new join node into the join tree */
*************** pull_up_sublinks_qual_recurse(PlannerInf
*** 360,366 ****
                  return NULL;
              }
              if (available_rels2 != NULL &&
!                 (j = convert_ANY_sublink_to_join(root, sublink,
                                                   available_rels2)) != NULL)
              {
                  /* Yes; insert the new join node into the join tree */
--- 360,366 ----
                  return NULL;
              }
              if (available_rels2 != NULL &&
!                 (j = convert_ANY_sublink_to_join(root, sublink, false,
                                                   available_rels2)) != NULL)
              {
                  /* Yes; insert the new join node into the join tree */
*************** pull_up_sublinks_qual_recurse(PlannerInf
*** 445,458 ****
      }
      if (not_clause(node))
      {
!         /* If the immediate argument of NOT is EXISTS, try to convert */
          SubLink    *sublink = (SubLink *) get_notclausearg((Expr *) node);
          JoinExpr   *j;
          Relids        child_rels;

          if (sublink && IsA(sublink, SubLink))
          {
!             if (sublink->subLinkType == EXISTS_SUBLINK)
              {
                  if ((j = convert_EXISTS_sublink_to_join(root, sublink, true,
                                                     available_rels1)) != NULL)
--- 445,512 ----
      }
      if (not_clause(node))
      {
!         /* If the immediate argument of NOT is ANY or EXISTS, try to convert */
          SubLink    *sublink = (SubLink *) get_notclausearg((Expr *) node);
          JoinExpr   *j;
          Relids        child_rels;

          if (sublink && IsA(sublink, SubLink))
          {
!             if (sublink->subLinkType == ANY_SUBLINK)
!             {
!                 if ((j = convert_ANY_sublink_to_join(root, sublink, true,
!                                                    available_rels1)) != NULL)
!                 {
!                     /* Yes; insert the new join node into the join tree */
!                     j->larg = *jtlink1;
!                     *jtlink1 = (Node *) j;
!                     /* Recursively process pulled-up jointree nodes */
!                     j->rarg = pull_up_sublinks_jointree_recurse(root,
!                                                                 j->rarg,
!                                                                 &child_rels);
!
!                     /*
!                      * Now recursively process the pulled-up quals.  Because
!                      * we are underneath a NOT, we can't pull up sublinks that
!                      * reference the left-hand stuff, but it's still okay to
!                      * pull up sublinks referencing j->rarg.
!                      */
!                     j->quals = pull_up_sublinks_qual_recurse(root,
!                                                              j->quals,
!                                                              &j->rarg,
!                                                              child_rels,
!                                                              NULL, NULL);
!                     /* Return NULL representing constant TRUE */
!                     return NULL;
!                 }
!                 if (available_rels2 != NULL &&
!                     (j = convert_ANY_sublink_to_join(root, sublink, true,
!                                                    available_rels2)) != NULL)
!                 {
!                     /* Yes; insert the new join node into the join tree */
!                     j->larg = *jtlink2;
!                     *jtlink2 = (Node *) j;
!                     /* Recursively process pulled-up jointree nodes */
!                     j->rarg = pull_up_sublinks_jointree_recurse(root,
!                                                                 j->rarg,
!                                                                 &child_rels);
!
!                     /*
!                      * Now recursively process the pulled-up quals.  Because
!                      * we are underneath a NOT, we can't pull up sublinks that
!                      * reference the left-hand stuff, but it's still okay to
!                      * pull up sublinks referencing j->rarg.
!                      */
!                     j->quals = pull_up_sublinks_qual_recurse(root,
!                                                              j->quals,
!                                                              &j->rarg,
!                                                              child_rels,
!                                                              NULL, NULL);
!                     /* Return NULL representing constant TRUE */
!                     return NULL;
!                 }
!             }
!             else if (sublink->subLinkType == EXISTS_SUBLINK)
              {
                  if ((j = convert_EXISTS_sublink_to_join(root, sublink, true,
                                                     available_rels1)) != NULL)
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 19b5cf7..f8e3eaa 100644
*** a/src/backend/optimizer/util/clauses.c
--- b/src/backend/optimizer/util/clauses.c
***************
*** 40,45 ****
--- 40,46 ----
  #include "parser/parse_agg.h"
  #include "parser/parse_coerce.h"
  #include "parser/parse_func.h"
+ #include "parser/parsetree.h"
  #include "rewrite/rewriteManip.h"
  #include "tcop/tcopprot.h"
  #include "utils/acl.h"
*************** static bool contain_nonstrict_functions_
*** 100,105 ****
--- 101,108 ----
  static bool contain_leaky_functions_walker(Node *node, void *context);
  static Relids find_nonnullable_rels_walker(Node *node, bool top_level);
  static List *find_nonnullable_vars_walker(Node *node, bool top_level);
+ static void find_innerjoined_rels(Node *jtnode,
+                       Relids *innerjoined_rels, List **usable_quals);
  static bool is_strict_saop(ScalarArrayOpExpr *expr, bool falseOK);
  static Node *eval_const_expressions_mutator(Node *node,
                                 eval_const_expressions_context *context);
*************** contain_leaky_functions_walker(Node *nod
*** 1459,1464 ****
--- 1462,1471 ----
                                    context);
  }

+ /*****************************************************************************
+  *          Nullability analysis
+  *****************************************************************************/
+
  /*
   * find_nonnullable_rels
   *        Determine which base rels are forced nonnullable by given clause.
*************** find_nonnullable_rels_walker(Node *node,
*** 1685,1691 ****
   * but here we assume that the input is a Boolean expression, and wish to
   * see if NULL inputs will provably cause a FALSE-or-NULL result.  We expect
   * the expression to have been AND/OR flattened and converted to implicit-AND
!  * format.
   *
   * The result is a palloc'd List, but we have not copied the member Var nodes.
   * Also, we don't bother trying to eliminate duplicate entries.
--- 1692,1698 ----
   * but here we assume that the input is a Boolean expression, and wish to
   * see if NULL inputs will provably cause a FALSE-or-NULL result.  We expect
   * the expression to have been AND/OR flattened and converted to implicit-AND
!  * format (but the results are still good if it wasn't AND/OR flattened).
   *
   * The result is a palloc'd List, but we have not copied the member Var nodes.
   * Also, we don't bother trying to eliminate duplicate entries.
*************** find_forced_null_var(Node *node)
*** 1987,1992 ****
--- 1994,2241 ----
  }

  /*
+  * query_outputs_are_not_nullable
+  *        Returns TRUE if the output values of the Query are certainly not NULL.
+  *        All output columns must return non-NULL to answer TRUE.
+  *
+  * The reason this takes a Query, and not just an individual tlist expression,
+  * is so that we can make use of the query's WHERE/ON clauses to prove it does
+  * not return nulls.
+  *
+  * In current usage, the passed sub-Query hasn't yet been through any planner
+  * processing.  This means that applying find_nonnullable_vars() to its WHERE
+  * clauses isn't really ideal: for lack of const-simplification, we might be
+  * unable to prove not-nullness in some cases where we could have proved it
+  * afterwards.  However, we should not get any false positive results.
+  *
+  * Like the other forms of nullability analysis above, we can err on the
+  * side of conservatism: if we're not sure, it's okay to return FALSE.
+  */
+ bool
+ query_outputs_are_not_nullable(Query *query)
+ {
+     PlannerInfo subroot;
+     Relids        innerjoined_rels = NULL;
+     bool        computed_innerjoined_rels = false;
+     List       *usable_quals = NIL;
+     List       *nonnullable_vars = NIL;
+     bool        computed_nonnullable_vars = false;
+     ListCell   *tl;
+
+     /*
+      * If the query contains set operations, punt.  The set ops themselves
+      * couldn't introduce nulls that weren't in their inputs, but the tlist
+      * present in the top-level query is just dummy and won't give us useful
+      * info.  We could get an answer by recursing to examine each leaf query,
+      * but for the moment it doesn't seem worth the extra complication.
+      *
+      * Note that we needn't consider other top-level operators such as
+      * DISTINCT, GROUP BY, etc, as those will not introduce nulls either.
+      */
+     if (query->setOperations)
+         return false;
+
+     /*
+      * We need a PlannerInfo to pass to flatten_join_alias_vars.  Fortunately,
+      * we can cons up an entirely dummy one, because only the "parse" link in
+      * the struct is used by flatten_join_alias_vars.
+      */
+     MemSet(&subroot, 0, sizeof(subroot));
+     subroot.parse = query;
+
+     /*
+      * Examine each targetlist entry to prove that it can't produce NULL.
+      */
+     foreach(tl, query->targetList)
+     {
+         TargetEntry *tle = (TargetEntry *) lfirst(tl);
+         Expr       *expr = tle->expr;
+
+         /* Resjunk columns can be ignored: they don't produce output values */
+         if (tle->resjunk)
+             continue;
+
+         /*
+          * For the most part we don't try to deal with anything more complex
+          * than Consts and Vars; but it seems worthwhile to look through
+          * binary relabelings, since we know those don't introduce nulls.
+          */
+         while (expr && IsA(expr, RelabelType))
+             expr = ((RelabelType *) expr)->arg;
+
+         if (expr == NULL)        /* paranoia */
+             return false;
+
+         if (IsA(expr, Const))
+         {
+             /* Consts are easy: they're either null or not. */
+             if (((Const *) expr)->constisnull)
+                 return false;
+         }
+         else if (IsA(expr, Var))
+         {
+             Var           *var = (Var *) expr;
+
+             /* Currently, we punt for any nonlocal Vars */
+             if (var->varlevelsup != 0)
+                 return false;
+
+             /*
+              * Since the subquery hasn't yet been through expression
+              * preprocessing, we must apply flatten_join_alias_vars to the
+              * given Var, and to any Vars found by find_nonnullable_vars, to
+              * avoid being fooled by join aliases.  If we get something other
+              * than a plain Var out of the substitution, punt.
+              */
+             var = (Var *) flatten_join_alias_vars(&subroot, (Node *) var);
+
+             if (!IsA(var, Var))
+                 return false;
+             Assert(var->varlevelsup == 0);
+
+             /*
+              * We don't bother to compute innerjoined_rels and usable_quals
+              * until we've found a Var we must analyze.
+              */
+             if (!computed_innerjoined_rels)
+             {
+                 find_innerjoined_rels((Node *) query->jointree,
+                                       &innerjoined_rels, &usable_quals);
+                 computed_innerjoined_rels = true;
+             }
+
+             /*
+              * If Var is from a plain relation, and that relation is not on
+              * the nullable side of any outer join, and its column is marked
+              * NOT NULL according to the catalogs, it can't produce NULL.
+              */
+             if (bms_is_member(var->varno, innerjoined_rels))
+             {
+                 RangeTblEntry *rte = rt_fetch(var->varno, query->rtable);
+
+                 if (rte->rtekind == RTE_RELATION &&
+                     get_attnotnull(rte->relid, var->varattno))
+                     continue;    /* cannot produce NULL */
+             }
+
+             /*
+              * Even if that didn't work, we can conclude that the Var is not
+              * nullable if find_nonnullable_vars can find a "var IS NOT NULL"
+              * or similarly strict condition among the usable_quals.  Compute
+              * the list of Vars having such quals if we didn't already.
+              */
+             if (!computed_nonnullable_vars)
+             {
+                 nonnullable_vars = find_nonnullable_vars((Node *) usable_quals);
+                 nonnullable_vars = (List *)
+                     flatten_join_alias_vars(&subroot,
+                                             (Node *) nonnullable_vars);
+                 /* We don't bother removing any non-Vars from the result */
+                 computed_nonnullable_vars = true;
+             }
+
+             if (!list_member(nonnullable_vars, var))
+                 return false;    /* we failed to prove the Var non-null */
+         }
+         else
+         {
+             /* Not a Const or Var; punt */
+             return false;
+         }
+     }
+
+     return true;                /* query cannot emit NULLs */
+ }
+
+ /*
+  * find_innerjoined_rels
+  *        Traverse jointree to locate non-outerjoined-rels and quals above them
+  *
+  * We fill innerjoined_rels with the relids of all rels that are not below
+  * the nullable side of any outer join (which would cause their Vars to be
+  * possibly NULL regardless of what's in the catalogs).  In the same scan,
+  * we locate all WHERE and JOIN/ON quals that constrain these rels, and add
+  * them to the usable_quals list (forming a list with implicit-AND semantics).
+  *
+  * Top-level caller must initialize innerjoined_rels/usable_quals to NULL/NIL.
+  */
+ static void
+ find_innerjoined_rels(Node *jtnode,
+                       Relids *innerjoined_rels, List **usable_quals)
+ {
+     if (jtnode == NULL)
+         return;
+     if (IsA(jtnode, RangeTblRef))
+     {
+         int            varno = ((RangeTblRef *) jtnode)->rtindex;
+
+         *innerjoined_rels = bms_add_member(*innerjoined_rels, varno);
+     }
+     else if (IsA(jtnode, FromExpr))
+     {
+         FromExpr   *f = (FromExpr *) jtnode;
+         ListCell   *lc;
+
+         /* All elements of the FROM list are allowable */
+         foreach(lc, f->fromlist)
+             find_innerjoined_rels((Node *) lfirst(lc),
+                                   innerjoined_rels, usable_quals);
+         /* ... and its WHERE quals are too */
+         if (f->quals)
+             *usable_quals = lappend(*usable_quals, f->quals);
+     }
+     else if (IsA(jtnode, JoinExpr))
+     {
+         JoinExpr   *j = (JoinExpr *) jtnode;
+
+         switch (j->jointype)
+         {
+             case JOIN_INNER:
+                 /* visit both children */
+                 find_innerjoined_rels(j->larg,
+                                       innerjoined_rels, usable_quals);
+                 find_innerjoined_rels(j->rarg,
+                                       innerjoined_rels, usable_quals);
+                 /* and grab the ON quals too */
+                 if (j->quals)
+                     *usable_quals = lappend(*usable_quals, j->quals);
+                 break;
+
+             case JOIN_LEFT:
+             case JOIN_SEMI:
+             case JOIN_ANTI:
+
+                 /*
+                  * Only the left input is possibly non-nullable; furthermore,
+                  * the quals of this join don't constrain the left input.
+                  * Note: we probably can't see SEMI or ANTI joins at this
+                  * point, but if we do, we can treat them like LEFT joins.
+                  */
+                 find_innerjoined_rels(j->larg,
+                                       innerjoined_rels, usable_quals);
+                 break;
+
+             case JOIN_RIGHT:
+                 /* Reverse of the above case */
+                 find_innerjoined_rels(j->rarg,
+                                       innerjoined_rels, usable_quals);
+                 break;
+
+             case JOIN_FULL:
+                 /* Neither side is non-nullable, so stop descending */
+                 break;
+
+             default:
+                 elog(ERROR, "unrecognized join type: %d",
+                      (int) j->jointype);
+         }
+     }
+     else
+         elog(ERROR, "unrecognized node type: %d",
+              (int) nodeTag(jtnode));
+ }
+
+ /*
   * Can we treat a ScalarArrayOpExpr as strict?
   *
   * If "falseOK" is true, then a "false" result can be considered strict,
diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c
index 4b5ef99..1d581a8 100644
*** a/src/backend/utils/cache/lsyscache.c
--- b/src/backend/utils/cache/lsyscache.c
*************** get_atttypetypmodcoll(Oid relid, AttrNum
*** 972,977 ****
--- 972,1004 ----
      ReleaseSysCache(tp);
  }

+ /*
+  * get_attnotnull
+  *
+  *        Given the relation id and the attribute number,
+  *        return the "attnotnull" field from the attribute relation.
+  */
+ bool
+ get_attnotnull(Oid relid, AttrNumber attnum)
+ {
+     HeapTuple    tp;
+
+     tp = SearchSysCache2(ATTNUM,
+                          ObjectIdGetDatum(relid),
+                          Int16GetDatum(attnum));
+     if (HeapTupleIsValid(tp))
+     {
+         Form_pg_attribute att_tup = (Form_pg_attribute) GETSTRUCT(tp);
+         bool        result;
+
+         result = att_tup->attnotnull;
+         ReleaseSysCache(tp);
+         return result;
+     }
+     else
+         return false;
+ }
+
  /*                ---------- COLLATION CACHE ----------                     */

  /*
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index dd991b1..5b25d01 100644
*** a/src/include/optimizer/clauses.h
--- b/src/include/optimizer/clauses.h
*************** extern Relids find_nonnullable_rels(Node
*** 69,74 ****
--- 69,75 ----
  extern List *find_nonnullable_vars(Node *clause);
  extern List *find_forced_null_vars(Node *clause);
  extern Var *find_forced_null_var(Node *clause);
+ extern bool query_outputs_are_not_nullable(Query *query);

  extern bool is_pseudo_constant_clause(Node *clause);
  extern bool is_pseudo_constant_clause_relids(Node *clause, Relids relids);
diff --git a/src/include/optimizer/subselect.h b/src/include/optimizer/subselect.h
index 5607e98..3e8bfe7 100644
*** a/src/include/optimizer/subselect.h
--- b/src/include/optimizer/subselect.h
***************
*** 18,23 ****
--- 18,24 ----
  extern void SS_process_ctes(PlannerInfo *root);
  extern JoinExpr *convert_ANY_sublink_to_join(PlannerInfo *root,
                              SubLink *sublink,
+                             bool under_not,
                              Relids available_rels);
  extern JoinExpr *convert_EXISTS_sublink_to_join(PlannerInfo *root,
                                 SubLink *sublink,
diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h
index f46460a..3ec200a 100644
*** a/src/include/utils/lsyscache.h
--- b/src/include/utils/lsyscache.h
*************** extern Oid    get_atttype(Oid relid, AttrNu
*** 70,75 ****
--- 70,76 ----
  extern int32 get_atttypmod(Oid relid, AttrNumber attnum);
  extern void get_atttypetypmodcoll(Oid relid, AttrNumber attnum,
                        Oid *typid, int32 *typmod, Oid *collid);
+ extern bool get_attnotnull(Oid relid, AttrNumber attnum);
  extern char *get_collation_name(Oid colloid);
  extern char *get_constraint_name(Oid conoid);
  extern Oid    get_opclass_family(Oid opclass);
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index d85a717..b63f7ac 100644
*** a/src/test/regress/expected/subselect.out
--- b/src/test/regress/expected/subselect.out
*************** select nextval('ts1');
*** 803,805 ****
--- 803,1103 ----
        11
  (1 row)

+ --
+ -- Check NOT IN performs an ANTI JOIN when NULLs are not possible
+ -- in the target list of the subquery.
+ --
+ BEGIN;
+ CREATE TEMP TABLE a (id INT PRIMARY KEY);
+ CREATE TEMP TABLE b (x INT NOT NULL, y INT);
+ CREATE TEMP TABLE c (z INT NOT NULL);
+ -- ANTI JOIN. x is defined as NOT NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT x FROM b);
+                QUERY PLAN
+ -----------------------------------------
+  Merge Anti Join
+    Merge Cond: (a.id = b.x)
+    ->  Index Only Scan using a_pkey on a
+    ->  Sort
+          Sort Key: b.x
+          ->  Seq Scan on b
+ (6 rows)
+
+ -- No ANTI JOIN, y can be NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b);
+              QUERY PLAN
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Seq Scan on b
+ (4 rows)
+
+ -- No ANTI JOIN, x is NOT NULL, but we don't know if + 1 will change that.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT x+1 FROM b);
+              QUERY PLAN
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Seq Scan on b
+ (4 rows)
+
+ -- ANTI JOIN 1 is a Const that is not null.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT 1 FROM b);
+         QUERY PLAN
+ ---------------------------
+  Nested Loop Anti Join
+    Join Filter: (a.id = 1)
+    ->  Seq Scan on a
+    ->  Materialize
+          ->  Seq Scan on b
+ (5 rows)
+
+ -- No ANTI JOIN, results contain a NULL Const
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT NULL::int FROM b);
+              QUERY PLAN
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Seq Scan on b
+ (4 rows)
+
+ -- ANTI JOIN y = 1 means y can't be NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1);
+           QUERY PLAN
+ -------------------------------
+  Hash Anti Join
+    Hash Cond: (a.id = b.y)
+    ->  Seq Scan on a
+    ->  Hash
+          ->  Seq Scan on b
+                Filter: (y = 1)
+ (6 rows)
+
+ -- No ANTI JOIN, OR condition does not ensure y = 1
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1 OR x = 1);
+                QUERY PLAN
+ ----------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Seq Scan on b
+            Filter: ((y = 1) OR (x = 1))
+ (5 rows)
+
+ -- No ANTI JOIN, OR condition does not ensure y = 1 or y = 2
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND (y = 2 OR x = 2));
+                             QUERY PLAN
+ -------------------------------------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Seq Scan on b
+            Filter: (((y = 1) OR (x = 1)) AND ((y = 2) OR (x = 2)))
+ (5 rows)
+
+ -- ANTI JOIN y must be 2, so can't be NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND y = 2);
+                         QUERY PLAN
+ ----------------------------------------------------------
+  Hash Anti Join
+    Hash Cond: (a.id = b.y)
+    ->  Seq Scan on a
+    ->  Hash
+          ->  Seq Scan on b
+                Filter: ((y = 2) AND ((y = 1) OR (x = 1)))
+ (6 rows)
+
+ -- ANTI JOIN y can be 1 or 2, but can't be null.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR y = 2));
+                  QUERY PLAN
+ --------------------------------------------
+  Hash Anti Join
+    Hash Cond: (a.id = b.y)
+    ->  Seq Scan on a
+    ->  Hash
+          ->  Seq Scan on b
+                Filter: ((y = 1) OR (y = 2))
+ (6 rows)
+
+ -- No ANTI JOIN c.z is from a left outer join so it can have nulls.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z);
+              QUERY PLAN
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Merge Left Join
+            Merge Cond: (b.x = c.z)
+            ->  Sort
+                  Sort Key: b.x
+                  ->  Seq Scan on b
+            ->  Sort
+                  Sort Key: c.z
+                  ->  Seq Scan on c
+ (11 rows)
+
+ -- ANTI JOIN, c.z is not from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
+                      QUERY PLAN
+ -----------------------------------------------------
+  Merge Left Join
+    Merge Cond: (c.z = b.x)
+    ->  Sort
+          Sort Key: c.z
+          ->  Merge Anti Join
+                Merge Cond: (a.id = c.z)
+                ->  Index Only Scan using a_pkey on a
+                ->  Sort
+                      Sort Key: c.z
+                      ->  Seq Scan on c
+    ->  Sort
+          Sort Key: b.x
+          ->  Seq Scan on b
+ (13 rows)
+
+ -- No ANTI JOIN, b.x is from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z);
+              QUERY PLAN
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Merge Right Join
+            Merge Cond: (b.x = c.z)
+            ->  Sort
+                  Sort Key: b.x
+                  ->  Seq Scan on b
+            ->  Sort
+                  Sort Key: c.z
+                  ->  Seq Scan on c
+ (11 rows)
+
+ -- No ANTI JOIN, c.z is not from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z);
+              QUERY PLAN
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Merge Full Join
+            Merge Cond: (b.x = c.z)
+            ->  Sort
+                  Sort Key: b.x
+                  ->  Seq Scan on b
+            ->  Sort
+                  Sort Key: c.z
+                  ->  Seq Scan on c
+ (11 rows)
+
+ -- No ANTI JOIN, b.x is from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL JOIN c ON b.x = c.z);
+              QUERY PLAN
+ ------------------------------------
+  Seq Scan on a
+    Filter: (NOT (hashed SubPlan 1))
+    SubPlan 1
+      ->  Merge Full Join
+            Merge Cond: (b.x = c.z)
+            ->  Sort
+                  Sort Key: b.x
+                  ->  Seq Scan on b
+            ->  Sort
+                  Sort Key: c.z
+                  ->  Seq Scan on c
+ (11 rows)
+
+ -- ANTI JOIN, c.z is from an inner join and has a NOT NULL constraint.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b INNER JOIN c ON b.x = c.z);
+                QUERY PLAN
+ -----------------------------------------
+  Merge Anti Join
+    Merge Cond: (a.id = c.z)
+    ->  Index Only Scan using a_pkey on a
+    ->  Materialize
+          ->  Merge Join
+                Merge Cond: (b.x = c.z)
+                ->  Sort
+                      Sort Key: b.x
+                      ->  Seq Scan on b
+                ->  Sort
+                      Sort Key: c.z
+                      ->  Seq Scan on c
+ (12 rows)
+
+ -- ANTI JOIN, c.z must be 1
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHERE c.z = 1);
+                 QUERY PLAN
+ -------------------------------------------
+  Hash Anti Join
+    Hash Cond: (a.id = c.z)
+    ->  Seq Scan on a
+    ->  Hash
+          ->  Nested Loop
+                ->  Seq Scan on c
+                      Filter: (z = 1)
+                ->  Materialize
+                      ->  Seq Scan on b
+                            Filter: (x = 1)
+ (10 rows)
+
+ -- ANTI JOIN, c.z can't be NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHERE c.z IS NOT NULL);
+                     QUERY PLAN
+ ---------------------------------------------------
+  Merge Anti Join
+    Merge Cond: (a.id = c.z)
+    ->  Index Only Scan using a_pkey on a
+    ->  Materialize
+          ->  Merge Join
+                Merge Cond: (b.x = c.z)
+                ->  Sort
+                      Sort Key: b.x
+                      ->  Seq Scan on b
+                ->  Sort
+                      Sort Key: c.z
+                      ->  Seq Scan on c
+                            Filter: (z IS NOT NULL)
+ (13 rows)
+
+ ALTER TABLE c ADD COLUMN x INT;
+ -- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c);
+                QUERY PLAN
+ -----------------------------------------
+  Merge Anti Join
+    Merge Cond: (a.id = b.x)
+    ->  Index Only Scan using a_pkey on a
+    ->  Materialize
+          ->  Merge Join
+                Merge Cond: (b.x = c.x)
+                ->  Sort
+                      Sort Key: b.x
+                      ->  Seq Scan on b
+                ->  Sort
+                      Sort Key: c.x
+                      ->  Seq Scan on c
+ (12 rows)
+
+ ROLLBACK;
diff --git a/src/test/regress/sql/subselect.sql b/src/test/regress/sql/subselect.sql
index c3b4773..c3ca67f 100644
*** a/src/test/regress/sql/subselect.sql
--- b/src/test/regress/sql/subselect.sql
*************** select * from
*** 444,446 ****
--- 444,538 ----
    order by 1;

  select nextval('ts1');
+
+ --
+ -- Check NOT IN performs an ANTI JOIN when NULLs are not possible
+ -- in the target list of the subquery.
+ --
+
+ BEGIN;
+
+ CREATE TEMP TABLE a (id INT PRIMARY KEY);
+ CREATE TEMP TABLE b (x INT NOT NULL, y INT);
+ CREATE TEMP TABLE c (z INT NOT NULL);
+
+ -- ANTI JOIN. x is defined as NOT NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT x FROM b);
+
+ -- No ANTI JOIN, y can be NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b);
+
+ -- No ANTI JOIN, x is NOT NULL, but we don't know if + 1 will change that.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT x+1 FROM b);
+
+ -- ANTI JOIN 1 is a Const that is not null.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT 1 FROM b);
+
+ -- No ANTI JOIN, results contain a NULL Const
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT NULL::int FROM b);
+
+ -- ANTI JOIN y = 1 means y can't be NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1);
+
+ -- No ANTI JOIN, OR condition does not ensure y = 1
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE y = 1 OR x = 1);
+
+ -- No ANTI JOIN, OR condition does not ensure y = 1 or y = 2
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND (y = 2 OR x = 2));
+
+ -- ANTI JOIN y must be 2, so can't be NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR x = 1) AND y = 2);
+
+ -- ANTI JOIN y can be 1 or 2, but can't be null.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT y FROM b WHERE (y = 1 OR y = 2));
+
+ -- No ANTI JOIN c.z is from a left outer join so it can have nulls.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z);
+
+ -- ANTI JOIN, c.z is not from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b RIGHT JOIN c ON b.x = c.z);
+
+ -- No ANTI JOIN, b.x is from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b RIGHT JOIN c ON b.x = c.z);
+
+ -- No ANTI JOIN, c.z is not from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b FULL JOIN c ON b.x = c.z);
+
+ -- No ANTI JOIN, b.x is from an outer join
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT b.x FROM b FULL JOIN c ON b.x = c.z);
+
+ -- ANTI JOIN, c.z is from an inner join and has a NOT NULL constraint.
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b INNER JOIN c ON b.x = c.z);
+
+ -- ANTI JOIN, c.z must be 1
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHERE c.z = 1);
+
+ -- ANTI JOIN, c.z can't be NULL
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT c.z FROM b LEFT JOIN c ON b.x = c.z WHERE c.z IS NOT NULL);
+
+ ALTER TABLE c ADD COLUMN x INT;
+
+ -- ANTI JOIN, x cannot be NULL as b.x has a NOT NULL constraint
+ EXPLAIN (COSTS OFF)
+ SELECT * FROM a WHERE id NOT IN (SELECT x FROM b NATURAL JOIN c);
+
+
+ ROLLBACK;

I wrote:
> We could no doubt fix this by also insisting that the left-side vars
> be provably not null, but that's going to make the patch even slower
> and even less often applicable.  I'm feeling discouraged about whether
> this is worth doing in this form.

Hm ... actually, there might be a better answer: what about transforming
  WHERE (x,y) NOT IN (SELECT provably-not-null-values FROM ...)

to
  WHERE <antijoin condition> AND x IS NOT NULL AND y IS NOT NULL

?

Of course this would require x/y not being volatile, but if they are,
we're not going to get far with optimizing the query anyhow.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> On Fri, Jul 11, 2014 at 1:11 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Hm ... actually, there might be a better answer: what about transforming
>> WHERE (x,y) NOT IN (SELECT provably-not-null-values FROM ...)
>> to
>> WHERE <antijoin condition> AND x IS NOT NULL AND y IS NOT NULL

> I think this is the way to go.

> I'll try and get some time soon to look into adding the IS NOT NULL quals,
> unless you were thinking of looking again?

Go for it, I've got a lot of other stuff on my plate.
        regards, tom lane

On 2014-07-13 23:06:15 +1200, David Rowley wrote:
> I had another look at this and it appears you were right the first time, we
> need to ensure there's no NULLs on both sides of the join condition.

The patch is currently marked as 'ready for committer' - that doesn't
seem to correspond to the discussion. Marked as 'Waiting for Author'. Ok?

Greetings,

Andres Freund

-- Andres Freund                       http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training &
Services

David Rowley <dgrowleyml@gmail.com> writes:
> I had another look at this and it appears you were right the first time, we
> need to ensure there's no NULLs on both sides of the join condition.

Ugh.  I'm back to being discouraged about the usefulness of the
optimization.

> The only other way I could imagine fixing this would be to have some other
> sort of join type that always met the join condition if the right side of
> the join had no tuples... Of course I'm not suggesting it gets implemented
> this way, I'm just otherwise out of ideas.

IIRC, we looked into implementing a true NOT IN join operator years ago.
Not only is it messy as can be, but there are patents in the area :-(.
So anything more than the most brain-dead-simple approach would be
risky.

I could see implementing a variant join operator in the hash join code,
since there you get to look at the entire inner relation before you have
to give any answers.  You could easily detect both empty-inner and
inner-contains-nulls and modify the results of matching appropriately.
However, it's not apparent how that could be made to work for either
mergejoin or nestloop-with-inner-index-scan, which greatly limits the
usefulness of the approach.  Worse yet, I think this'd be at best a
marginal improvement on the existing hashed-subplan code path.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> On Mon, Jul 14, 2014 at 3:00 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Ugh.  I'm back to being discouraged about the usefulness of the
>> optimization.

> Are you worried about the planning overhead of the not null checks, or is
> it more that you think there's a much smaller chance of a real world
> situation that the optimisation will succeed?

Both.  We need to look at how much it costs the planner to run these
checks, and think about how many real queries it will help for.  The
first is quantifiable, the second probably not so much :-( but we still
need to ask the question.
        regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:
> I've made some changes to the patch so that it only allows the conversion
> to ANTI JOIN to take place if both the outer query's expressions AND the
> subquery's target list can be proved not to have NULLs.

This coding doesn't fill me with warm fuzzy feelings.
query_outputs_are_not_nullable, as originally constituted, knew that it
was attempting to prove the query's tlist non-nullable; that's the reason
for the setop restriction, and it also justifies looking at all the
available quals.  If you're trying to make a similar proof for expressions
occurring in a random qual clause, I don't think you can safely look at
quals coming from higher syntactic nesting levels.  And on the other side
of the coin, outer joins occurring above the syntactic level of the NOT IN
aren't reason to dismiss using an antijoin, because they don't null
variables appearing in it.

It might be possible to fix that by passing in the jointree node at which
the NOT IN is to be evaluated, and doing the find_innerjoined_rels search
for the outer-query exprs from there rather than always from the jointree
root.  I've not thought carefully about this though.

> I found that the call to is_NOTANY_compatible_with_antijoin adds about 0.2%
> and 2.3% to total planning time. Though the 2.3% was quite an extreme case,
> and the 0.2% was the most simple case I could think of.

Hm.  Since, as you say, the cost is 0 unless there's a NOT IN, that seems
to indicate that we can afford this test ... as long as it does something
often enough to be useful.  I'm still a bit doubtful about that.  However,
it does give us the option of telling people that they can fix their
queries by adding "WHERE x IS NOT NULL", so maybe that's helpful enough
even if it doesn't fix real-world queries right out of the gate.

Since we're at the end of the June commitfest, I'm going to mark this
patch Returned With Feedback in the commitfest list.
        regards, tom lane

On 15 July 2014 12:58, David Rowley <dgrowleyml@gmail.com> wrote:

> I found that the call to is_NOTANY_compatible_with_antijoin adds about 0.2%
> and 2.3% to total planning time. Though the 2.3% was quite an extreme case,
> and the 0.2% was the most simple case I could think of.

I think its quite important that we don't apply every single
optimization we can think of in all cases. Fast planning of short
requests is as important as good planning of longer requests.

Is there a way we can only run this extra test when we have reasonable
idea that there is potential to save significant costs? Or put another
way, can we look at ways to skip the test if its not likely to add
value. Obviously, if we have a good feeling that we might save lots of
execution time then any additional planning time is easier to justify.

-- Simon Riggs                   http://www.2ndQuadrant.com/PostgreSQL Development, 24x7 Support, Training & Services

Simon Riggs <simon@2ndQuadrant.com> writes:
> On 15 July 2014 12:58, David Rowley <dgrowleyml@gmail.com> wrote:
>> I found that the call to is_NOTANY_compatible_with_antijoin adds about 0.2%
>> and 2.3% to total planning time. Though the 2.3% was quite an extreme case,
>> and the 0.2% was the most simple case I could think of.

> Is there a way we can only run this extra test when we have reasonable
> idea that there is potential to save significant costs?

Well, all of this cost occurs only when we find a NOT IN clause in a place
where we could conceivably turn it into an antijoin.  I think it's
unquestionably a win to make that transformation if possible.  My concern
about it is mainly that the whole thing is a band-aid for naively written
queries, and it seems likely to me that naively written queries aren't
going to be amenable to making the proof we need.  But we can't tell that
for sure without doing exactly the work the patch does.
        regards, tom lane