pg.ddx.io pgsql-hackers@postgresql.org mailing list archive
help / color / mirror / Atom feedIN joining
7+ messages / 2 participants
[nested] [flat]
* IN joining
@ 2004-03-05 17:28 Dennis Haney <davh@diku.dk>
0 siblings, 1 reply; 7+ messages in thread
From: Dennis Haney @ 2004-03-05 17:28 UTC (permalink / raw)
To: pgsql-hackers
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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: IN joining
@ 2004-03-05 21:04 Tom Lane <tgl@sss.pgh.pa.us>
parent: Dennis Haney <davh@diku.dk>
0 siblings, 1 reply; 7+ messages in thread
From: Tom Lane @ 2004-03-05 21:04 UTC (permalink / raw)
To: Dennis Haney <davh@diku.dk>; +Cc: pgsql-hackers
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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: IN joining
@ 2004-03-05 21:32 Dennis Haney <davh@diku.dk>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 7+ messages in thread
From: Dennis Haney @ 2004-03-05 21:32 UTC (permalink / raw)
To: pgsql-hackers
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");
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: IN joining
@ 2004-03-05 23:08 Tom Lane <tgl@sss.pgh.pa.us>
parent: Dennis Haney <davh@diku.dk>
0 siblings, 1 reply; 7+ messages in thread
From: Tom Lane @ 2004-03-05 23:08 UTC (permalink / raw)
To: Dennis Haney <davh@diku.dk>; +Cc: pgsql-hackers
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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: IN joining
@ 2004-03-08 14:03 Dennis Haney <davh@diku.dk>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 7+ messages in thread
From: Dennis Haney @ 2004-03-08 14:03 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-hackers
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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: IN joining
@ 2004-03-08 15:44 Tom Lane <tgl@sss.pgh.pa.us>
parent: Dennis Haney <davh@diku.dk>
0 siblings, 1 reply; 7+ messages in thread
From: Tom Lane @ 2004-03-08 15:44 UTC (permalink / raw)
To: Dennis Haney <davh@diku.dk>; +Cc: pgsql-hackers
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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: IN joining
@ 2004-03-08 16:04 Dennis Haney <davh@diku.dk>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 7+ messages in thread
From: Dennis Haney @ 2004-03-08 16:04 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-hackers
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
^ permalink raw reply [nested|flat] 7+ messages in thread
end of thread, other threads:[~2004-03-08 16:04 UTC | newest]
Thread overview: 7+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2004-03-05 17:28 IN joining Dennis Haney <davh@diku.dk>
2004-03-05 21:04 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-03-05 21:32 ` Dennis Haney <davh@diku.dk>
2004-03-05 23:08 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-03-08 14:03 ` Dennis Haney <davh@diku.dk>
2004-03-08 15:44 ` Tom Lane <tgl@sss.pgh.pa.us>
2004-03-08 16:04 ` Dennis Haney <davh@diku.dk>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox