Re: [HACKERS] Allowing NOT IN to use ANTI joins
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
[HACKERS] 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 not_in_anti_join_v0.4.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