Re: Allowing NOT IN to use ANTI joins

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.

A simple example of this (without a subquery) is:

select 1 where 3 not in (1, 2, null); returns 0 rows because 3 <> NULL is
unknown.

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);

To generate a plan like:
QUERY PLAN
-----------------------------------------------------------------
Hash Anti Join (cost=64.00..137.13 rows=1070 width=8)
Hash Cond: (a.b_id = b.id)
-> Seq Scan on a (cost=0.00..31.40 rows=2140 width=8)
-> Hash (cost=34.00..34.00 rows=2400 width=4)
-> Seq Scan on b (cost=0.00..34.00 rows=2400 width=4)

But if we then do:
ALTER TABLE b ALTER COLUMN id DROP NOT NULL;

The plan will go back to the current behaviour of:

QUERY PLAN
-------------------------------------------------------------
Seq Scan on a (cost=40.00..76.75 rows=1070 width=8)
Filter: (NOT (hashed SubPlan 1))
SubPlan 1
-> Seq Scan on b (cost=0.00..34.00 rows=2400 width=4)

Comments are welcome

Regards

David Rowley

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(at)svana(dot)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(at)gmail(dot)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 use plain unique constraints
* if all their columns are known not null, but there's a problem: we need
* to be able to represent the not-null-ness as part of the constraints added
* to *constraintDeps. FIXME whenever not-null constraints get represented
* 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(at)juffo(dot)org> writes:
> On Sun, Jun 8, 2014 at 3:36 PM, David Rowley <dgrowleyml(at)gmail(dot)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

On Sun, Jun 8, 2014 at 5:36 AM, David Rowley <dgrowleyml(at)gmail(dot)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.
>
> A simple example of this (without a subquery) is:
>
> select 1 where 3 not in (1, 2, null); returns 0 rows because 3 <> NULL is
> unknown.
>
> 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);
>
> To generate a plan like:
> QUERY PLAN
> -----------------------------------------------------------------
> Hash Anti Join (cost=64.00..137.13 rows=1070 width=8)
> Hash Cond: (a.b_id = b.id)
> -> Seq Scan on a (cost=0.00..31.40 rows=2140 width=8)
> -> Hash (cost=34.00..34.00 rows=2400 width=4)
> -> Seq Scan on b (cost=0.00..34.00 rows=2400 width=4)
>

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.

But what I can't figure out is, would that change obviate the need for your
change? Once we can correctly deal with nulls in a NOT IN list through a
hash anti join, is there a cost estimation advantage to being able to prove
that the that null can't occur? (And of course if you have code that
works, while I have vague notions of what might be, then my notion probably
does not block your code.)

Cheers,

Jeff

Jeff Janes <jeff(dot)janes(at)gmail(dot)com> writes:
> On Sun, Jun 8, 2014 at 5:36 AM, David Rowley <dgrowleyml(at)gmail(dot)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

On Monday, June 9, 2014, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Jeff Janes <jeff(dot)janes(at)gmail(dot)com <javascript:;>> writes:
> > On Sun, Jun 8, 2014 at 5:36 AM, David Rowley <dgrowleyml(at)gmail(dot)com
> <javascript:;>> 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.
>

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

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.

Cheers,

Jeff

Jeff Janes <jeff(dot)janes(at)gmail(dot)com> writes:
> On Monday, June 9, 2014, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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 Mon, Jun 9, 2014 at 11:20 PM, Marti Raudsepp <marti(at)juffo(dot)org> wrote:

> On Sun, Jun 8, 2014 at 3:36 PM, David Rowley <dgrowleyml(at)gmail(dot)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.
>
>
I tried to break this by putting a break point
in convert_ANY_sublink_to_join in session 1. Not that it really had to be
in that function, I just wanted it to stop during planning and before the
plan is executed.

-- session 1
select * from n1 where id not in(select id from n1); -- hits breakpoint in
convert_ANY_sublink_to_join

-- session 2
alter table n2 alter column id drop not null;

insert into n2 values(null);

I see that session 2 blocks in the alter table until session 1 completes.

I've not really checked out the code in detail around when the snapshot is
taken and the transaction ID is generated, but 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?

> 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 use plain unique
> constraints
> * if all their columns are known not null, but there's a problem: we need
> * to be able to represent the not-null-ness as part of the constraints
> added
> * to *constraintDeps. FIXME whenever not-null constraints get represented
> * in pg_constraint.
>
>
I saw that, but I have to say I've not fully got my head around why that's
needed just yet.

> 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 :)
>
>
Agreed :) Originally I had put the code that does that
in convert_ANY_sublink_to_join, but at the last minute before posting the
patch I decided that it might be useful and reusable so moved it out to
that function. I'll try and think of something better, but I'm open to
ideas.

Regards

David Rowley

On Tue, Jun 10, 2014 at 2:19 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Jeff Janes <jeff(dot)janes(at)gmail(dot)com> writes:
> > 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.)
>
>
This got me thinking. It is probably a bit useless and wrong to perform a
NOT IN when the subquery in the IN() clause can have NULL values, so I
guess in any realistic useful case, the user will either have a NOT NULL
constraint on the columns, or they'll do a WHERE col IS NOT NULL, so I
should likely also allow a query such as:

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

to also perform an ANTI JOIN. I think it's just a matter of
changing targetListIsGuaranteedNotToHaveNulls so that if it does not find
the NOT NULL constraint, to check the WHERE clause of the query to see if
there's any not null quals.

I'm about to put this to the test, but if it works then I think it should
cover many more cases for using NOT IN(), I guess we're only leaving out
function calls and calculations in the target list.

Regards

David Rowley

On Wed, Jun 11, 2014 at 11:53 AM, David Rowley <dgrowleyml(at)gmail(dot)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(at)gmail(dot)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

On Wed, Jun 11, 2014 at 9:32 PM, Marti Raudsepp <marti(at)juffo(dot)org> wrote:

> On Sun, Jun 8, 2014 at 3:36 PM, David Rowley <dgrowleyml(at)gmail(dot)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.
>
>
Thanks, I actually was just looking at that. I guess I'll just need to make
sure that nothing in the targetlist comes from an outer join.

Regards

David Rowley

Marti Raudsepp <marti(at)juffo(dot)org> writes:
> On Wed, Jun 11, 2014 at 11:53 AM, David Rowley <dgrowleyml(at)gmail(dot)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(at)sss(dot)pgh(dot)pa(dot)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 Wed, Jun 11, 2014 at 9:32 PM, Marti Raudsepp <marti(at)juffo(dot)org> wrote:

> On Sun, Jun 8, 2014 at 3:36 PM, David Rowley <dgrowleyml(at)gmail(dot)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.
>
>
I'm a bit stuck on fixing this and I can't quite figure out how I should
tell if the TargetEntry is coming from an outer join.

My first attempt does not work as it seems that I'm looking up the wrong
RangeTblEntry with the following:

rte = rt_fetch(tlevar->varno, query->rtable);

if (IS_OUTER_JOIN(rte->jointype))
return true; /* Var from an outer join */

The jointype returns JOIN_INNER when loooking up the RangeTblEntry from the
TargetEntry's varno. It seems that the RangeTblEntry that I need is stored
in query->rtable, but I've just no idea how to tell which item in the list
it is. So if anyone can point me in the right direction then that would be
really useful.

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.

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.

Regards

David Rowley

On 24 June 2014 11:32, David Rowley <dgrowleyml(at)gmail(dot)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(at)mit(dot)edu> wrote:
> On Wed, Jun 11, 2014 at 3:26 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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(at)2ndQuadrant(dot)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(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Simon Riggs <simon(at)2ndQuadrant(dot)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(at)2ndQuadrant(dot)com> writes:
> On 24 June 2014 23:44, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> Simon Riggs <simon(at)2ndQuadrant(dot)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(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Simon Riggs <simon(at)2ndQuadrant(dot)com> writes:
>> On 24 June 2014 23:44, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> Simon Riggs <simon(at)2ndQuadrant(dot)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(at)2ndquadrant(dot)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(at)2ndQuadrant(dot)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 Thu, Jun 26, 2014 at 3:52 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Simon Riggs <simon(at)2ndQuadrant(dot)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.
>
>
At first I didn't quite agree with this, but after a bit more thought I'm
coming around to it.

I had been thinking that, quite often the subquery in the NOT IN would have
a WHERE clause and not just be accessing all rows of the table, but then
it's probably very likely that when the subquery *does* contain a WHERE
clause that it's for some completely different column.. It seems a bit
weird to write NOT IN(SELECT somecol FROM table WHERE somecol = 5) it's
probably more likely to be something like NOT IN(SELECT somecol FROM table
WHERE category = 5), i.e some column that's not in the target list, and in
this case we wouldn't know that somecol couldn't be NULL.

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.

Regards

David Rowley

> 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(at)gmail(dot)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(at)gmail(dot)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

On Fri, Jun 27, 2014 at 6:14 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> David Rowley <dgrowleyml(at)gmail(dot)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?
>
> It was more of that I couldn't figure out how to do it, rather than
thinking it was not possible.

> 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.
>
>
Ok, I've implemented that in the attached. Thanks for the tip.

> 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 ended up just having the function gather up all RelIds that are on the on
the inner side. So this will just need to be called once per NOT IN clause.

> 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.)
>
>
This is being done from within pull_up_sublinks, so it's before
deconstruct_jointree.

I've attached an updated version of the patch which seems to now work
properly with outer joins.

I think I'm finally ready for a review again, so I'll update the commitfest
app.

Regards

David Rowley

On Sun, Jun 29, 2014 at 4:18 PM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> I think I'm finally ready for a review again, so I'll update the
> commitfest app.
>
>
I have reviewed this on code level.

1. Patch gets applied cleanly.
2. make/make install/make check all are fine

No issues found till now.

However some cosmetic points:

1.
* 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".

Since now, we do support NOT IN handling in convert_ANY_sublink_to_join() we
do have "under_not" parameter there too. So above comments near
convert_EXISTS_sublink_to_join() function is NO more valid.

2. Following is the unnecessary change. Can be removed:

@@ -506,6 +560,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
*node,
return NULL;
}
}
+
}
/* Else return it unmodified */
return node;

3. Typos:

a.
+ * queryTargetListListCanHaveNulls
...
+queryTargetListCanHaveNulls(Query *query)

Function name is queryTargetListCanHaveNulls() not
queryTargetListListCanHaveNulls()

b.
* For example the presense of; col IS NOT NULL, or col = 42 would
allow

presense => presence

4. get_attnotnull() throws an error for invalid relid/attnum.
But I see other get_att* functions which do not throw an error rather
returning some invalid value, eg. NULL in case of attname, InvalidOid in
case of atttype and InvalidAttrNumber in case of attnum. I have observed
that we cannot return such invalid value for type boolean and I guess that's
the reason you are throwing an error. But somehow looks unusual. You had put
a note there which is good. But yes, caller of this function should be
careful enough and should not assume its working like other get_att*()
functions.
However for this patch, I would simply accept this solution. But I wonder if
someone thinks other way round.

Testing more on SQL level.

However, assigning it to author to think on above cosmetic issues.

Thanks

--
Jeevan B Chalke
Principal Software Engineer, Product Development
EnterpriseDB Corporation
The Enterprise PostgreSQL Company

On Wed, Jul 2, 2014 at 9:25 PM, Jeevan Chalke <
jeevan(dot)chalke(at)enterprisedb(dot)com> wrote:

>
>
> Testing more on SQL level.
>
>

I'm just looking into an issue I've found in the find_inner_rels()
function, where it does not properly find the rel in the from list in
certain cases, for example:

explain select * from a where id not in (select b.id from b left outer join
c on b.id=c.id);

fails to use an ANTI JOIN, but if you remove the left join to c, it works
perfectly.

Currently I'm just getting my head around how the jointree is structured
and reading over deconstruct_jointree to see how it handles this. I may
change the function to find_outer_rels and just look for outer joins in the
function.

However, assigning it to author to think on above cosmetic issues.
>
>
Thanks for the review. I'll fix the issues you listed soon, but I'll likely
delay posting the updated patch until I have the other fix in place.

Regards

David Rowley

Thanks
>
> --
> Jeevan B Chalke
> Principal Software Engineer, Product Development
> EnterpriseDB Corporation
> The Enterprise PostgreSQL Company
>
>

On Wed, Jul 2, 2014 at 9:25 PM, Jeevan Chalke <
jeevan(dot)chalke(at)enterprisedb(dot)com> wrote:

>
> On Sun, Jun 29, 2014 at 4:18 PM, David Rowley <dgrowleyml(at)gmail(dot)com>
> wrote:
>
>> I think I'm finally ready for a review again, so I'll update the
>> commitfest app.
>>
>>
> I have reviewed this on code level.
>
> 1. Patch gets applied cleanly.
> 2. make/make install/make check all are fine
>
> No issues found till now.
>
> However some cosmetic points:
>
> 1.
> * 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".
>
> Since now, we do support NOT IN handling in convert_ANY_sublink_to_join()
> we
> do have "under_not" parameter there too. So above comments near
> convert_EXISTS_sublink_to_join() function is NO more valid.
>
>
Nice catch. I've removed the last 2 lines from that comment now.

> 2. Following is the unnecessary change. Can be removed:
>
> @@ -506,6 +560,7 @@ pull_up_sublinks_qual_recurse(PlannerInfo *root, Node
> *node,
> return NULL;
> }
> }
> +
> }
> /* Else return it unmodified */
> return node;
>
>
Removed

>
>
3. Typos:
>
> a.
> + * queryTargetListListCanHaveNulls
> ...
> +queryTargetListCanHaveNulls(Query *query)
>
> Function name is queryTargetListCanHaveNulls() not
> queryTargetListListCanHaveNulls()
>
>
Fixed.

> b.
> * For example the presense of; col IS NOT NULL, or col = 42 would
> allow
>
> presense => presence
>
>
>
Fixed.

> 4. get_attnotnull() throws an error for invalid relid/attnum.
> But I see other get_att* functions which do not throw an error rather
> returning some invalid value, eg. NULL in case of attname, InvalidOid in
> case of atttype and InvalidAttrNumber in case of attnum. I have observed
> that we cannot return such invalid value for type boolean and I guess
> that's
> the reason you are throwing an error. But somehow looks unusual. You had
> put
> a note there which is good. But yes, caller of this function should be
> careful enough and should not assume its working like other get_att*()
> functions.
> However for this patch, I would simply accept this solution. But I wonder
> if
> someone thinks other way round.
>
>
hmmm, I remember thinking about that at the time. It was a choice between
returning false or throwing an error. I decided that it probably should be
an error, as that's what get_relid_attribute_name() was doing. Just search
lsyscache.c for "cache lookup failed for attribute %d of relation %u".

>
> Testing more on SQL level.
>
>
Thank you for reviewing this. I think in the attached I've managed to nail
down the logic in find_inner_rels(). It was actually more simple than I
thought. On working on this today I also noticed that RIGHT joins can still
exist at this stage of planning and also that full joins are not
transformed. e.g: a FULL JOIN b ON a.id=b.id WHERE a.is IS NOT NULL would
later become a LEFT JOIN, but at this stage in planning, it's still a FULL
JOIN. I've added some new regression tests which test some of these join
types.

With further testing I noticed that the patch was not allowing ANTI joins
in cases like this:

explain select * from a where id not in(select x from b natural join c);

even if b.x and b.c were NOT NULL columns. This is because the TargetEntry
for x has a varno which belongs to neither b or c, it's actually the varno
for the join itself. I've added some code to detect this in
find_inner_rels(), but I'm not quite convinced yet that it's in the correct
place... I'm wondering if a future use for find_inner_rels() would need to
only see relations rather than join varnos. The code I added does get the
above query using ANTI joins, but it does have a bit of a weird quirk, in
that for it to perform an ANTI JOIN, b.x must be NOT NULL. If c.x is NOT
NULL and b.x is nullable, then there will be no ANTI JOIN. There must be
some code somewhere that chooses which of the 2 vars that should go into
the target list in for naturals joins.

The above got me thinking that the join conditions can also be used to
prove not nullness too. Take the query above as an example, x can never
actually be NULL, the condition b.x = c.x ensures that. I've only gone as
far as adding some comments which explain that this is a possible future
optimisation. I've not had time to look at this yet and I'd rather see the
patch go in without it than risk delaying this until the next commitfest...
Unless of course someone thinks it's just too weird a quirk to have in the
code.

Attached is the updated version of the patch.

Regards

David Rowley

However, assigning it to author to think on above cosmetic issues.
>
> Thanks
>
> --
> Jeevan B Chalke
> Principal Software Engineer, Product Development
> EnterpriseDB Corporation
> The Enterprise PostgreSQL Company
>
>

Hi,

> With further testing I noticed that the patch was not allowing ANTI joins
> in cases like this:
>
> explain select * from a where id not in(select x from b natural join c);
>
>
>
I too found this with natural joins and was about to report that. But its
good that you found that and fixed it as well.

I have reviewed this and didn't find any issues as such. So marking it
"Ready for Committer".

Thanks

--
Jeevan B Chalke
Principal Software Engineer, Product Development
EnterpriseDB Corporation
The Enterprise PostgreSQL Company

David Rowley <dgrowleyml(at)gmail(dot)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

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

On Fri, Jul 11, 2014 at 1:11 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> 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.
>
>
:-( seems I didn't do my analysis very well on that one.

> 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.
It's basically what I had to do with the WIP patch I have here for SEMI
JOIN removal, where when a IN() or EXISTS type join could be removed due to
the existence of a foreign key, the NULL values still need to be filtered
out.

Perhaps it would be possible for a future patch to check get_attnotnull and
remove these again in eval_const_expressions, if the column can't be null.

Thanks for taking the time to fix up the weirdness with the NATURAL joins
and also making use of the join condition to prove not null-ability.

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

Regards

David Rowley

> 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(at)gmail(dot)com> writes:
> On Fri, Jul 11, 2014 at 1:11 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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 Fri, Jul 11, 2014 at 1:11 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> 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
>
> ?
>
>
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 reason for this is that there's a special case with "WHERE col NOT
IN(SELECT id from empty_relation)", this is effectively the same as "WHERE
true", so we should see *all* rows, even ones where col is null. Adding a
col IS NOT NULL cannot be done as it would filter out the NULLs in this
special case.

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.

Regards

David Rowley

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(at)gmail(dot)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

On Mon, Jul 14, 2014 at 3:00 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> David Rowley <dgrowleyml(at)gmail(dot)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.
>
>
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? At least the planning
overhead is limited to query's that have NOT IN clauses.

I'm still quite positive about the patch. I think that it would just be a
matter of modifying query_outputs_are_not_nullable() giving it a nice new
name and changing the parameter list to accept not only a Query, but also a
List of Expr. Likely this would be quite a nice reusable function that
likely could be used in a handful of other places in the planner to
optimise various other cases.

When I first decided to work on this I was more interested in getting some
planner knowledge about NOT NULL constraints than I was interested in
speeding up NOT IN, but it seemed like a perfect target or even "excuse" to
draft up some code that checks if an expr can never be NULL.

Since the patch has not been marked as rejected I was thinking that I'd
take a bash at fixing it up, but if you think this is a waste of time,
please let me know.

Regards

David Rowley

David Rowley <dgrowleyml(at)gmail(dot)com> writes:
> On Mon, Jul 14, 2014 at 3:00 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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

On Mon, Jul 14, 2014 at 8:55 PM, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

>
> Since the patch has not been marked as rejected I was thinking that I'd
> take a bash at fixing it up, but if you think this is a waste of time,
> please let me know.
>
>
>
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.

I've attached a delta, which is the changes I've made on top of Tom's
cleaned up version of my patch, and also a full patch.

I've also performed some benchmarks to try to determine how much time it
takes to execute this null checking code. I ended up hacking the code a
little for the benchmarks and just put the null checking function in a
tight loop that performed 100000 iterations.

Like:
if (under_not)
{
int x;
bool result;
for (x = 0; x < 100000; x++)
{
result = is_NOTANY_compatible_with_antijoin(parse, sublink);
}
if (!result)
return NULL;
}

I then ran 6 queries, 3 times each through the planner and grabbed the
"Planning Time" from the explain analyze result.
I then removed the extra looping code (seen above) and compiled the code as
it is with the attached patch.
I then ran each of the 6 queries again 3 times each and noted down the
"Planning Time from the explain analyze result.

In my results I assumed that the first set of times divided by 100000
would be the time taken to perform the NULL checks... This is not quite
accurate, but all the other planning work was quite well drowned out by the
100k loop.

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've attached the complete results in html format. I've also attached the
schema that I used and all 6 queries tested.

Here's 2 points which I think are important to note about the planning time
overhead of this patch:
1. There is no additional overhead if the query has no NOT IN clause.
2. The test queries 3 and 6 were to benchmark the overhead of when the NOT
NULL test fails. The slowest of these was test 3 which added just under
0.5% to the planning time. The query that added a 2.3% overhead performed
an ANTI JOIN, so likely the reduction in execution time more than made up
for the extra planning time.

Regards

David Rowley

David Rowley <dgrowleyml(at)gmail(dot)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(at)gmail(dot)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(at)2ndQuadrant(dot)com> writes:
> On 15 July 2014 12:58, David Rowley <dgrowleyml(at)gmail(dot)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

On Wed, Jul 16, 2014 at 9:11 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Simon Riggs <simon(at)2ndQuadrant(dot)com> writes:
> > On 15 July 2014 12:58, David Rowley <dgrowleyml(at)gmail(dot)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.
>
>
I do think Simon has a good point, maybe it's not something for this patch,
but perhaps other planner patches that potentially optimise queries that
could have been executed more efficiently if they had been written in
another way.

Since the planning time has been added to EXPLAIN ANALYZE I have noticed
that in many very simple queries that quite often planning time is longer
than execution time, so I really do understand the concern that we don't
want to slow the planner down for these super fast queries. But on the
other hand, if this extra 1-2 microseconds that the NOT IN optimisation was
being frowned upon and the patch had been rejected based on that, at the
other end of the scale, I wouldn't think it was too impossible for spending
that extra 2 microseconds to translate into shaving a few hours off of the
execution time of a query being run in an OLAP type workload. If that was
the case then having not spent the 2 extra microseconds seems quite funny,
but there's no real way to tell I guess unless we invented something to
skip the known costly optimisations on first pass then re-plan the whole
query with the planning strength knob turned to the maximum if the final
query cost more than N.

Off course such a idea would make bad plans even harder to debug, so it's
far from perfect, but I'm not seeing other options for the best of both
worlds.

Regards

David Rowley