Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-20 Thread Tom Lane
I wrote: Hence semijoins can be rearranged just as freely as inner joins. I guess nobody checked my work, because that claim is bogus. Consider A semijoin (B innerjoin C on (Pbc)) on (Pab) =? (A semijoin B on (Pab)) innerjoin C on (Pbc) In the second form the inner join is now

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-20 Thread Robert Haas
On Fri, Feb 20, 2009 at 10:59 AM, Tom Lane t...@sss.pgh.pa.us wrote: I wrote: Hence semijoins can be rearranged just as freely as inner joins. I guess nobody checked my work, because that claim is bogus. I spent some time reading your email and thinking through the cases, but I completely

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-12 Thread Greg Stark
On 11 Feb 2009, at 00:03, Tom Lane t...@sss.pgh.pa.us wrote: Actually, that makes less sense than the antijoin case. For antijoin there is a well-defined value for the extended columns, ie null. For a semijoin the RHS values might come from any of the rows that happen to join to the current

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-12 Thread Kevin Grittner
Tom Lane t...@sss.pgh.pa.us wrote: Kevin Grittner kevin.gritt...@wicourts.gov writes: (A semijoin B on (Pab)) antijoin C on (Pbc) = A semijoin (B antijoin C on (Pbc)) on (Pab) I think this one is true, and it doesn't seem to be mentioned, unless I'm missing something. It seems

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-12 Thread Kevin Grittner
I wrote: You've got a name, and you want a list of outstanding warrants for parties with a matching name. Correction, if that was the list you wanted, you would use an inner join, not a semijoin. For purposes of this illustration I guess you would be looking for a list of parties who have

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread David Fetter
On Tue, Feb 10, 2009 at 08:12:56PM -0500, Jonah H. Harris wrote: On Tue, Feb 10, 2009 at 8:09 PM, Jonah H. Harris jonah.har...@gmail.comwrote: On Tue, Feb 10, 2009 at 3:10 PM, Tom Lane t...@sss.pgh.pa.us wrote: I wrote (in response to Kevin Grittner's recent issues): Reflecting on

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Jonah H. Harris
On Wed, Feb 11, 2009 at 8:05 AM, David Fetter da...@fetter.org wrote: As has been discussed here many, many times, the only kind of person who should be doing a patent search is a company's IP attorney, which you are not, and even if you were, under no circumstances would such a person paste

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread David Fetter
On Wed, Feb 11, 2009 at 09:36:38AM -0500, Jonah H. Harris wrote: On Wed, Feb 11, 2009 at 8:05 AM, David Fetter da...@fetter.org wrote: As has been discussed here many, many times, the only kind of person who should be doing a patent search is a company's IP attorney, which you are not,

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Jonah H. Harris
On Wed, Feb 11, 2009 at 11:19 AM, David Fetter da...@fetter.org wrote: This is a very big deal, as you are exposing every US PostgreSQL contributor to triple damages for knowing infringement. Are you saying you're going to pay all that out of your own pocket? Are you making a legal

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Stephen Frost
David, * David Fetter (da...@fetter.org) wrote: On Wed, Feb 11, 2009 at 09:36:38AM -0500, Jonah H. Harris wrote: Secondly, I don't believe there's any restriction of explicitly what can and cannot be posted on a public Postgres mailing list. We have plenty of such restrictions. Take the

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Gianni Ciolli
Hello, On Tue, Feb 10, 2009 at 09:41:46PM +0100, Dimitri Fontaine wrote: Hi, Le 10 févr. 09 à 21:10, Tom Lane a écrit : I wrote (in response to Kevin Grittner's recent issues): Reflecting on this further, I suspect there are also some bugs in the planner's rules about when semi/antijoins

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Tom Lane
David Fetter da...@fetter.org writes: On Wed, Feb 11, 2009 at 09:36:38AM -0500, Jonah H. Harris wrote: Secondly, I don't believe there's any restriction of explicitly what can and cannot be posted on a public Postgres mailing list. We have plenty of such restrictions. Take the Nazi spammer,

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Tom Lane
Gianni Ciolli gianni.cio...@2ndquadrant.it writes: On Tue, Feb 10, 2009 at 09:41:46PM +0100, Dimitri Fontaine wrote: I don't know how easy it would be to do, but maybe the Coq formal proof management system could help us here: http://coq.inria.fr/ The harder part in using coq might well be

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Kevin Grittner
Tom Lane t...@sss.pgh.pa.us wrote: I wrote (in response to Kevin Grittner's recent issues): Reflecting on this further, I suspect there are also some bugs in the planner's rules about when semi/antijoins can commute with other joins; After doing some math I've concluded this is in fact

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Kevin Grittner
I wrote: A6. [less coherent version of a question already asked and answered] Got that part on a reread of the thread. Sorry for asking that after it had been addressed. No need to answer again. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-11 Thread Tom Lane
Kevin Grittner kevin.gritt...@wicourts.gov writes: Tom Lane t...@sss.pgh.pa.us wrote: A6. (A antijoin B on (Pab)) leftjoin C on (Pbc) = A antijoin (B leftjoin C on (Pbc)) on (Pab) How do you get the first form as a starting point? Not sure if you can in SQL, but the point of the

[HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Tom Lane
I wrote (in response to Kevin Grittner's recent issues): Reflecting on this further, I suspect there are also some bugs in the planner's rules about when semi/antijoins can commute with other joins; After doing some math I've concluded this is in fact the case. Anyone want to check my work?

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Dimitri Fontaine
Hi, Le 10 févr. 09 à 21:10, Tom Lane a écrit : I wrote (in response to Kevin Grittner's recent issues): Reflecting on this further, I suspect there are also some bugs in the planner's rules about when semi/antijoins can commute with other joins; After doing some math I've concluded this

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Robert Haas
A6. (A antijoin B on (Pab)) leftjoin C on (Pbc) = A antijoin (B leftjoin C on (Pbc)) on (Pab) The second form is in fact equivalent to null-extending the A/B antijoin --- the actual contents of C cannot affect the result. So we could just I don't understand why antijoins need to

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Tom Lane
Robert Haas robertmh...@gmail.com writes: I don't understand why antijoins need to null-extend the tuple at all. Well, we are talking theoretical definition here, not implementation. But if you need an example where the column values can be referenced: select * from a left join b on

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Robert Haas
On Tue, Feb 10, 2009 at 5:03 PM, Tom Lane t...@sss.pgh.pa.us wrote: Robert Haas robertmh...@gmail.com writes: I don't understand why antijoins need to null-extend the tuple at all. Well, we are talking theoretical definition here, not implementation. But if you need an example where the

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Jonah H. Harris
On Tue, Feb 10, 2009 at 3:10 PM, Tom Lane t...@sss.pgh.pa.us wrote: I wrote (in response to Kevin Grittner's recent issues): Reflecting on this further, I suspect there are also some bugs in the planner's rules about when semi/antijoins can commute with other joins; After doing some math

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Jonah H. Harris
On Tue, Feb 10, 2009 at 8:09 PM, Jonah H. Harris jonah.har...@gmail.comwrote: On Tue, Feb 10, 2009 at 3:10 PM, Tom Lane t...@sss.pgh.pa.us wrote: I wrote (in response to Kevin Grittner's recent issues): Reflecting on this further, I suspect there are also some bugs in the planner's rules

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Tom Lane
Jonah H. Harris jonah.har...@gmail.com writes: Cripes! I just had an idea and it looks like the buggers beat me to it :( http://www.google.com/patents?id=4bqBEBAJdq=null+aware+anti-join I wonder if the USPTO is really clueless enough to accept this? Claim 1 would give Oracle ownership of

Re: [HACKERS] Optimization rules for semi and anti joins

2009-02-10 Thread Jonah H. Harris
On Tue, Feb 10, 2009 at 8:41 PM, Tom Lane t...@sss.pgh.pa.us wrote: Jonah H. Harris jonah.har...@gmail.com writes: Cripes! I just had an idea and it looks like the buggers beat me to it :( http://www.google.com/patents?id=4bqBEBAJdq=null+aware+anti-join I wonder if the USPTO is