Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-16 Thread David Rowley
On Wed, Jul 16, 2014 at 9:11 AM, Tom Lane t...@sss.pgh.pa.us wrote:

 Simon Riggs si...@2ndquadrant.com writes:
  On 15 July 2014 12:58, David Rowley dgrowle...@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.


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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-15 Thread Tom Lane
David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-15 Thread Simon Riggs
On 15 July 2014 12:58, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-15 Thread Tom Lane
Simon Riggs si...@2ndquadrant.com writes:
 On 15 July 2014 12:58, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-14 Thread David Rowley
On Mon, Jul 14, 2014 at 3:00 AM, Tom Lane t...@sss.pgh.pa.us wrote:

 David Rowley dgrowle...@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.


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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-14 Thread Tom Lane
David Rowley dgrowle...@gmail.com writes:
 On Mon, Jul 14, 2014 at 3:00 AM, Tom Lane t...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-13 Thread David Rowley
On Fri, Jul 11, 2014 at 1:11 PM, Tom Lane t...@sss.pgh.pa.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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-13 Thread Andres Freund
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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-13 Thread Tom Lane
David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-11 Thread David Rowley
On Fri, Jul 11, 2014 at 1:11 PM, Tom Lane t...@sss.pgh.pa.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



Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-11 Thread Tom Lane
David Rowley dgrowle...@gmail.com writes:
 On Fri, Jul 11, 2014 at 1:11 PM, Tom Lane t...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-10 Thread Tom Lane
David Rowley dgrowle...@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,
+ 	 

Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-10 Thread 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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-09 Thread Jeevan Chalke
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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-05 Thread David Rowley
On Wed, Jul 2, 2014 at 9:25 PM, Jeevan Chalke 
jeevan.cha...@enterprisedb.com wrote:


 On Sun, Jun 29, 2014 at 4:18 PM, David Rowley dgrowle...@gmail.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




not_in_anti_join_5257082_2014-07-05.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your 

Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-02 Thread Jeevan Chalke
On Sun, Jun 29, 2014 at 4:18 PM, David Rowley dgrowle...@gmail.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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-07-02 Thread David Rowley
On Wed, Jul 2, 2014 at 9:25 PM, Jeevan Chalke 
jeevan.cha...@enterprisedb.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




Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-29 Thread David Rowley
On Fri, Jun 27, 2014 at 6:14 AM, Tom Lane t...@sss.pgh.pa.us wrote:

 David Rowley dgrowle...@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?

 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


not_in_anti_join_v0.6.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-26 Thread David Rowley
On Thu, Jun 26, 2014 at 3:52 AM, Tom Lane t...@sss.pgh.pa.us wrote:

 Simon Riggs si...@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.


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



Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-26 Thread Simon Riggs
On 26 June 2014 10:31, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-26 Thread Tom Lane
David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-25 Thread Simon Riggs
On 24 June 2014 23:22, Simon Riggs si...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-25 Thread Tom Lane
Simon Riggs si...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-24 Thread David Rowley
On Wed, Jun 11, 2014 at 9:32 PM, Marti Raudsepp ma...@juffo.org wrote:

 On Sun, Jun 8, 2014 at 3:36 PM, David Rowley dgrowle...@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.


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


not_in_anti_join_v0.5_broken.patch
Description: Binary data

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-24 Thread Simon Riggs
On 24 June 2014 11:32, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-24 Thread Simon Riggs
On 11 June 2014 17:52, Greg Stark st...@mit.edu wrote:
 On Wed, Jun 11, 2014 at 3:26 PM, Tom Lane t...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-24 Thread Tom Lane
Simon Riggs si...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-24 Thread Simon Riggs
On 24 June 2014 23:44, Tom Lane t...@sss.pgh.pa.us wrote:
 Simon Riggs si...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-24 Thread Tom Lane
Simon Riggs si...@2ndquadrant.com writes:
 On 24 June 2014 23:44, Tom Lane t...@sss.pgh.pa.us wrote:
 Simon Riggs si...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-24 Thread Simon Riggs
On 24 June 2014 23:52, Tom Lane t...@sss.pgh.pa.us wrote:
 Simon Riggs si...@2ndquadrant.com writes:
 On 24 June 2014 23:44, Tom Lane t...@sss.pgh.pa.us wrote:
 Simon Riggs si...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-11 Thread David Rowley
On Mon, Jun 9, 2014 at 11:20 PM, Marti Raudsepp ma...@juffo.org wrote:

 On Sun, Jun 8, 2014 at 3:36 PM, David Rowley dgrowle...@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.


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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-11 Thread David Rowley
On Tue, Jun 10, 2014 at 2:19 PM, Tom Lane t...@sss.pgh.pa.us wrote:

 Jeff Janes jeff.ja...@gmail.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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-11 Thread Marti Raudsepp
On Wed, Jun 11, 2014 at 11:53 AM, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-11 Thread Marti Raudsepp
On Sun, Jun 8, 2014 at 3:36 PM, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-11 Thread David Rowley
On Wed, Jun 11, 2014 at 9:32 PM, Marti Raudsepp ma...@juffo.org wrote:

 On Sun, Jun 8, 2014 at 3:36 PM, David Rowley dgrowle...@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.


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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-11 Thread Tom Lane
Marti Raudsepp ma...@juffo.org writes:
 On Wed, Jun 11, 2014 at 11:53 AM, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-11 Thread Greg Stark
On Wed, Jun 11, 2014 at 3:26 PM, Tom Lane t...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-09 Thread Martijn van Oosterhout
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   klep...@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


signature.asc
Description: Digital signature


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-09 Thread Marti Raudsepp
On Sun, Jun 8, 2014 at 3:36 PM, David Rowley dgrowle...@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 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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-09 Thread Vik Fearing
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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-09 Thread Tom Lane
Marti Raudsepp ma...@juffo.org writes:
 On Sun, Jun 8, 2014 at 3:36 PM, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-09 Thread Jeff Janes
On Sun, Jun 8, 2014 at 5:36 AM, David Rowley dgrowle...@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.

 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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-09 Thread Tom Lane
Jeff Janes jeff.ja...@gmail.com writes:
 On Sun, Jun 8, 2014 at 5:36 AM, David Rowley dgrowle...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-09 Thread Jeff Janes
On Monday, June 9, 2014, Tom Lane t...@sss.pgh.pa.us wrote:

 Jeff Janes jeff.ja...@gmail.com javascript:; writes:
  On Sun, Jun 8, 2014 at 5:36 AM, David Rowley dgrowle...@gmail.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


Re: [HACKERS] Allowing NOT IN to use ANTI joins

2014-06-09 Thread Tom Lane
Jeff Janes jeff.ja...@gmail.com writes:
 On Monday, June 9, 2014, Tom Lane t...@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


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers