Hi

I have a problem understanding the code to make certain in join are 
performed properly. Specifically I have problems understading when 
IN_UNIQUE_{INNER,OUTER} is a valid jointype.
Its in joinrels.c:make_join_rel.

Consider this example:

SELECT * FROM a,b WHERE a.id = b.id AND (a.id) IN (SELECT c.id FROM c)

the possible execution trees are {{a,b}, {c}}, {{a,c},{b}} and the code 
seems to also permit {{b,c},{a}}. It is the latter I'm having problems with.

When joining {b} and {c} it will fall through and suggest a 
IN_UNIQUE_{INNER,OUTER} jointype.

My logic is this: {c} \in {c,b} so it is a valid plan according to the 
first check.
We have an issue according to the second check and we haven't done the 
work before according to the 3rd and 4th checks.
Since the lefthand of the IN {a} is not in either {b} or {c} we skip the 
IN_JOIN{_REVERSE}.
But since one of the relations is equal to the right side {c} of the IN 
we determine that IN_UNIQUE_{INNER,OUTER} is a valid jointype.

Now, the next join between {a} and {b,c} is the one I fail to understand 
when it can ever happen...

{c} \in {a,b,c} so it is a valid plan according to the first check.
We have an issue according to the second check.
Since we have no trace of the IN's left hand {a} in {b,c} 3rd and 4th 
check says we have not done the work?!?
The final checks fail because {c} != {b,c}, thus we determine it is an 
invalid plan.

My question is: When is it ever a valid jointype to use 
IN_UNIQUE_{INNER,OUTER}? Or am I missing something?


-- 
Dennis


Fri, 05 Mar 2004 18:28:54 +0100
Dennis Haney <davh@diku.dk>
IN joining
Dennis Haney <davh@diku.dk> writes:
> Consider this example:
> SELECT * FROM a,b WHERE a.id = b.id AND (a.id) IN (SELECT c.id FROM c)
> the possible execution trees are {{a,b}, {c}}, {{a,c},{b}} and the code 
> seems to also permit {{b,c},{a}}.

No, it does not --- as you say, that would give wrong answers.  That
case is eliminated by the tests following this comment:

             * JOIN_IN technique will work if outerrel includes LHS and
             * innerrel is exactly RHS; conversely JOIN_REVERSE_IN handles
             * RHS/LHS.
             *
             * JOIN_UNIQUE_OUTER will work if outerrel is exactly RHS;
             * conversely JOIN_UNIQUE_INNER will work if innerrel is
             * exactly RHS.

Joining {b,c} to {a} does not meet any of those four allowed cases.

			regards, tom lane

Fri, 05 Mar 2004 16:04:59 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: IN joining 
Tom Lane wrote:

>Dennis Haney <davh@diku.dk> writes:
>  
>
>>Consider this example:
>>SELECT * FROM a,b WHERE a.id = b.id AND (a.id) IN (SELECT c.id FROM c)
>>the possible execution trees are {{a,b}, {c}}, {{a,c},{b}} and the code 
>>seems to also permit {{b,c},{a}}.
>>    
>>
>
>No, it does not --- as you say, that would give wrong answers.  That
>case is eliminated by the tests following this comment:
>
>             * JOIN_IN technique will work if outerrel includes LHS and
>             * innerrel is exactly RHS; conversely JOIN_REVERSE_IN handles
>             * RHS/LHS.
>             *
>             * JOIN_UNIQUE_OUTER will work if outerrel is exactly RHS;
>             * conversely JOIN_UNIQUE_INNER will work if innerrel is
>             * exactly RHS.
>
>Joining {b,c} to {a} does not meet any of those four allowed cases.
>  
>
Exactly my point... So why ever bother creating the {b,c} node which is 
legal by the above definition?


-- 
Dennis
use Inline C => q{void p(char*g){
printf("Just Another %s Hacker\n",g);}};p("Perl");










Tom Lane wrote:

Dennis Haney <davh@diku.dk> writes:
  

Consider this example:
SELECT * FROM a,b WHERE a.id = b.id AND (a.id) IN (SELECT c.id FROM c)
the possible execution trees are {{a,b}, {c}}, {{a,c},{b}} and the code 
seems to also permit {{b,c},{a}}.
    


No, it does not --- as you say, that would give wrong answers.  That
case is eliminated by the tests following this comment:

             * JOIN_IN technique will work if outerrel includes LHS and
             * innerrel is exactly RHS; conversely JOIN_REVERSE_IN handles
             * RHS/LHS.
             *
             * JOIN_UNIQUE_OUTER will work if outerrel is exactly RHS;
             * conversely JOIN_UNIQUE_INNER will work if innerrel is
             * exactly RHS.

Joining {b,c} to {a} does not meet any of those four allowed cases.
  

Exactly my point... So why ever bother creating the {b,c} node which is
legal by the above definition?


-- 
Dennis
use Inline C => q{void p(char*g){
printf("Just Another %s Hacker\n",g);}};p("Perl");
Fri, 05 Mar 2004 22:32:03 +0100
Dennis Haney <davh@diku.dk>
Re: IN joining
Dennis Haney <davh@diku.dk> writes:
>> Joining {b,c} to {a} does not meet any of those four allowed cases.
>> 
> Exactly my point... So why ever bother creating the {b,c} node which is 
> legal by the above definition?

We don't, because there is no such join clause.

			regards, tom lane

Fri, 05 Mar 2004 18:08:55 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: IN joining 
Tom Lane wrote:

>Dennis Haney <davh@diku.dk> writes:
>  
>
>>>Joining {b,c} to {a} does not meet any of those four allowed cases.
>>>
>>>      
>>>
>>Exactly my point... So why ever bother creating the {b,c} node which is 
>>legal by the above definition?
>>    
>>
>
>We don't, because there is no such join clause.
>
>  
>
No, but we create the equality via the implied equality mechanism...

select * from a, b where a.id = b.id3 and a.id in (select c.id2 from c);

rtable is (after in-optimization):
resno   refname         relid   inFromCl
-----   ---------       -----   --------
1       a     17143           inFromCl
2       b     17151           inFromCl
3       IN_subquery     [subquery]
4       c     17147           inFromCl

in gdb:
break joinrels.c:563
commands
call bms_is_subset(ininfo->lefthand, rel1->relids)
call bms_equal(ininfo->righthand, rel2->relids)
call bms_is_subset(ininfo->lefthand, rel2->relids)
call bms_equal(ininfo->righthand, rel1->relids)
x/t rel1->relids.words
x/t rel2->relids.words
x/t joinrelids.words
p jointype
printf "%s\n", 
pretty_format_node_dump(nodeToString(((RestrictInfo*)((RestrictInfo*)restrictlist)->clause)->clause))
end

then we get this join:

Breakpoint 4, make_join_rel (root=0x8307bc8, rel1=0x8316920, 
rel2=0x8316b10, jointype=JOIN_UNIQUE_INNER)
    at joinrels.c:563
563             switch (jointype)
$92 = 0 '\0'
$93 = 1 '\001'
$94 = 0 '\0'
$95 = 0 '\0'
0x83169ac:      00000000000000000000000000000100
0x8316b9c:      00000000000000000000000000010000
0x832670c:      00000000000000000000000000010100
$96 = JOIN_UNIQUE_INNER
   {OPEXPR
   :opno 96
   :opfuncid 0
   :opresulttype 16
   :opretset false
   :args (
      {VAR
      :varno 4
      :varattno 1
      :vartype 23
      :vartypmod -1
      :varlevelsup 0
      :varnoold 4
      :varoattno 1
      }

      {VAR
      :varno 2
      :varattno 1
      :vartype 23
      :vartypmod -1
      :varlevelsup 0
      :varnoold 2
      :varoattno 1
      }
   )
   }


-- 
Dennis








Tom Lane wrote:

Dennis Haney <davh@diku.dk> writes:
  


Joining {b,c} to {a} does not meet any of those four allowed cases.

      

Exactly my point... So why ever bother creating the {b,c} node which is 
legal by the above definition?
    


We don't, because there is no such join clause.

  

No, but we create the equality via the implied equality mechanism...

select * from a, b where a.id = b.id3 and a.id in (select c.id2 from c);

rtable is (after in-optimization):
resno   refname         relid   inFromCl
-----   ---------       -----   --------
1       a     17143           inFromCl
2       b     17151           inFromCl
3       IN_subquery     [subquery]
4       c     17147           inFromCl

in gdb:
break joinrels.c:563
commands
call bms_is_subset(ininfo->lefthand, rel1->relids)
call bms_equal(ininfo->righthand, rel2->relids)
call bms_is_subset(ininfo->lefthand, rel2->relids)
call bms_equal(ininfo->righthand, rel1->relids)
x/t rel1->relids.words
x/t rel2->relids.words
x/t joinrelids.words
p jointype
printf "%s\n",
pretty_format_node_dump(nodeToString(((RestrictInfo*)((RestrictInfo*)restrictlist)->clause)->clause))
end

then we get this join:

Breakpoint 4, make_join_rel (root=0x8307bc8, rel1=0x8316920,
rel2=0x8316b10, jointype=JOIN_UNIQUE_INNER)
    at joinrels.c:563
563             switch (jointype)
$92 = 0 '\0'
$93 = 1 '\001'
$94 = 0 '\0'
$95 = 0 '\0'
0x83169ac:      00000000000000000000000000000100
0x8316b9c:      00000000000000000000000000010000
0x832670c:      00000000000000000000000000010100
$96 = JOIN_UNIQUE_INNER
   {OPEXPR
   :opno 96
   :opfuncid 0
   :opresulttype 16
   :opretset false
   :args (
      {VAR
      :varno 4
      :varattno 1
      :vartype 23
      :vartypmod -1
      :varlevelsup 0
      :varnoold 4
      :varoattno 1
      }

      {VAR
      :varno 2
      :varattno 1
      :vartype 23
      :vartypmod -1
      :varlevelsup 0
      :varnoold 2
      :varoattno 1
      }
   )
   }


-- 
Dennis
Mon, 08 Mar 2004 15:03:40 +0100
Dennis Haney <davh@diku.dk>
Re: IN joining
Dennis Haney <davh@diku.dk> writes:
>>> Exactly my point... So why ever bother creating the {b,c} node which is 
>>> legal by the above definition?
>> 
>> We don't, because there is no such join clause.
>> 
> No, but we create the equality via the implied equality mechanism...

> select * from a, b where a.id = b.id3 and a.id in (select c.id2 from c);

Oh, I had forgotten that your original example involved an implied
equality.  I don't see that anything is wrong though.  The join path
that will result from considering the implied equality will be like

	((UNIQUE-ified subselect) INNER JOIN b) INNER JOIN a

which is perfectly legal and perhaps even a winner.  Once you stick a
UNIQUE on top of the IN's subselect, you can treat the IN as exactly
like a plain equality join.

[ thinks a bit... ]  Actually I guess there is a problem here: we won't
actually generate that plan, because this test is too strict:

            /*
             * If we already joined IN's RHS to any part of its LHS in
             * either input path, then this join is not constrained (the
             * necessary work was done at a lower level).
             */
            if (bms_overlap(ininfo->lefthand, rel1->relids) &&
                bms_is_subset(ininfo->righthand, rel1->relids))
                continue;
            if (bms_overlap(ininfo->lefthand, rel2->relids) &&
                bms_is_subset(ininfo->righthand, rel2->relids))
                continue;

I think it should be

            /*
             * If we already joined IN's RHS to anything else in
             * either input path, then this join is not constrained (the
             * necessary work was done at a lower level).
             */
            if (bms_is_subset(ininfo->righthand, rel1->relids) &&
                !bms_equal(ininfo->righthand, rel1->relids))
                continue;
            if (bms_is_subset(ininfo->righthand, rel2->relids) &&
                !bms_equal(ininfo->righthand, rel2->relids))
                continue;

Comments?

			regards, tom lane

Mon, 08 Mar 2004 10:44:05 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: IN joining 
Tom Lane wrote:

[SNIP: a repetion of my first post ;) ]

>I think it should be
>
>            /*
>             * If we already joined IN's RHS to anything else in
>             * either input path, then this join is not constrained (the
>             * necessary work was done at a lower level).
>             */
>            if (bms_is_subset(ininfo->righthand, rel1->relids) &&
>                !bms_equal(ininfo->righthand, rel1->relids))
>                continue;
>            if (bms_is_subset(ininfo->righthand, rel2->relids) &&
>                !bms_equal(ininfo->righthand, rel2->relids))
>                continue;
>
>Comments?
>  
>
It's good.
It was pretty much what I was thinking was wrong to begin with.
Whether the generated plans are valid is a different issue ;)

-- 
Dennis


Mon, 08 Mar 2004 17:04:48 +0100
Dennis Haney <davh@diku.dk>
Re: IN joining